Redundant, multi-dimensional data partitioning: methods, program product and system

Abstract

Horizontal partitioning can handle a transaction by accessing a single node only if the transaction is restricted along the single partitioned dimension. Composite partitioning allows for partitioning along more than one dimension, but can only handle a transaction by accessing a single node if the transaction is limited along all partitioned dimensions. A partitioning method partitions a tuple space along more than one dimension and, by storing tuples redundantly, allows transactions restricted along one or more of the partitioned dimensions to be handled by accessing a single node. Other embodiments include a computer program product and a system for partitioning a tuple space.

1 . A computer-implemented method for partitioning a database storing tuples within a tuple space having a plurality of dimensions, comprising the steps of:
 partitioning each of two or more separate instances of said tuple space along one or more of said dimensions, so that partitions of each of said instances overlap partitions of other of said instances within said tuple space; and   storing each resulting partition separately from all other resulting partitions;   handling a transaction restricted along less than all of said partitioned dimensions of said tuple space by accessing a single one of said partitions.   
     
     
         2 . The method of  claim 1 , wherein said step of partitioning comprises partitioning each of two or more separate instances of said tuple space along a different one or more of said dimensions. 
     
     
         3 . The method of  claim 1 , wherein said step of partitioning comprises partitioning each of two or more separate instances of said tuple space along a single one of said dimensions. 
     
     
         4 . The method of  claim 1 , wherein said step of partitioning comprises any of the steps of:
 partitioning an instance according to at least one key range;   partitioning an instance according to a list containing at least one explicitly stated value;   partitioning an instance based on a computed hash key; and   partitioning an instance according to an interval definition.   
     
     
         5 . The method of  claim 1 , further comprising the step of:
 indexing said database.   
     
     
         6 . The method of  claim 5 , wherein said step of indexing said database comprises any of the steps of:
 providing a local index, wherein said local index is partitioned in the same manner as the underlying instance so that each partition of said local index corresponds to a single partition of said underlying instance;   providing a global partitioned index, wherein said global partitioned index is partitioned in a different manner from the underlying instance; and   providing a non-partitioned index.   
     
     
         7 . The method of  claim 1 , further comprising the steps of:
 identifying at least one tuple satisfying a transaction that is restricted along one or more restricted dimensions among said dimensions by identifying a partition along said restricted dimensions that contains said tuple; and   accessing said identified partition.   
     
     
         8 . The method of  claim 7 , wherein the step of:
 identifying at least one tuple satisfying a transaction that is restricted along a single dimension comprises the step of:   searching an index to identify at least one partition containing said tuple.   
     
     
         9 . A computer program product comprising a tangible computer-readable medium embodying computer-readable instructions, which instructions, when executed by a processing module, implement a method for partitioning a database storing tuples within a tuple space having a plurality of dimensions, the method comprising the steps of:
 partitioning each of two or more separate instances of said tuple space along one or more of said dimensions, so that partitions of each of said instances overlap partitions of other of said instances within said tuple space;   storing each resulting partition separately from all other resulting partitions;   handling a transaction restricted along less than all of said partitioned dimensions of said tuple space by accessing a single one of said partitions.   
     
     
         10 . The computer program product of  claim 9 , wherein said step of partitioning comprises partitioning each of two or more separate instances of said tuple space along a different one or more of said dimensions. 
     
     
         11 . The computer program product of  claim 9 , wherein said step of partitioning comprises partitioning each of two or more separate instances of said tuple space along a single one of said dimensions. 
     
     
         12 . The computer program product of  claim 9 , wherein said step of partitioning comprises any of the steps of:
 partitioning an instance according to at least one key range;   partitioning an instance according to a list containing at least one explicitly stated value;   partitioning an instance based on a computed hash key; and   partitioning an instance according to an interval definition.   
     
     
         13 . The computer program product of  claim 9 , said method further comprising the step of:
 indexing said database.   
     
     
         14 . The computer program product of  claim 13 , wherein said step of indexing said database comprises any of the steps of:
 providing a local index, wherein said local index is partitioned in the same manner as the underlying instance so that each partition of said local index corresponds to a single partition of said underlying instance;   providing a global partitioned index, wherein said global partitioned index is partitioned in a different manner from the underlying instance; and   providing a non-partitioned index.   
     
     
         15 . The computer program product of  claim 9 , said method further comprising the steps of:
 identifying at least one tuple satisfying a transaction that is restricted along one or more restricted dimensions among said dimensions by identifying a partition along said restricted dimensions that contains said tuple and   accessing said identified partition.   
     
     
         16 . The computer program product of  claim 15 , wherein the step of:
 identifying at least one tuple satisfying a transaction that is restricted along a single dimension comprises the step of:   searching an index to identify at least one partition containing said tuple   
     
     
         17 . A system for partitioning a database storing tuples within a tuple space having a plurality of dimensions, comprising:
 at least one processing module programmed for:
 partitioning each of two or more separate instances of said tuple space along one or more of said dimensions, so that partitions of each of said instances overlap partitions of other of said instances within said tuple space; 
 storing each resulting partition separately from all other resulting partitions; and 
 handling a transaction restricted along less than all of said partitioned dimensions by accessing a single one of said partitions. 
   
     
     
         18 . The system of  claim 17 , wherein said at least one processing module comprises any of:
 a single physical processing module;   a plurality of physical processing modules;   a plurality of virtual processing modules running on a single computer; and   a plurality of virtual processing modules running a plurality of computers.   
     
     
         19 . The system of  claim 17 , further comprising at least one engine for managing storage of said partitions. 
     
     
         20 . The system of  claim 17 , further comprising a processing module programmed to provide an index to said multidimensional database partitioned in the same manner as said multidimensional database is partitioned. 
     
     
         21 . The system of  claim 20 , wherein said index comprises one of:
 a local index, wherein the index is partitioned in the same manner as the underlying partitioned database so that each partition of said index corresponds to a single partition of the underlying database;   a global partitioned index, wherein the index is partitioned using a different partitioning key from the underlying database; and   a non-partitioned index.   
     
     
         22 . The system of  claim 17 , further comprising any of:
 at least one mainframe computer; and   at least one client computer;   wherein said at least one mainframe computer and said at least one client computer are in communication with said at least one processing module by means of a network connection.   
     
     
         23 . The system of  claim 17 , wherein said processing module is further programmed for:
 identifying at least one tuple satisfying a transaction that is restricted along one or more restricted dimensions among said dimensions by identifying a partition along said restricted dimensions that contains said tuple and   accessing said identified partition.   
     
     
         24 . The system of  claim 17 , wherein said processing module is further programmed for:
 partitioning each of two or more separate instances of said tuple space along a different one or more of said dimensions.   
     
     
         25 . The system of  claim 17 , wherein said processing module is further programmed for:
 partitioning each of two or more separate instances of said tuple space along a single one of said dimensions.   
     
     
         26 . The system of  claim 17 , wherein said processor programmed for partitioning is further programmed for any of:
 partitioning an instance according to at least one key range;   partitioning an instance according to a list containing at least one explicitly stated value;   partitioning an instance based on a computed hash key; and   partitioning an instance according to an interval definition.