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

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 redundant instances of said tuple space along one or more of said dimensions of said tuple space, so that partitions of each of said instances overlap partitions of other of said instances within said tuple space; and

storing each resulting partition on a separate one of a plurality of nodes of a repository, wherein assignment of each partition to a node is based on a location of said each resulting partition in said tuple space;

wherein said database handles a transaction restricted along less than all of said partitioned dimensions of said tuple space by accessing a single of said nodes.

2. The method of claim 1 , wherein said step of partitioning comprises partitioning each of two or more redundant instances of said tuple space along a different one or more of said dimensions of said tuple space.

3. The method of claim 1 , wherein said step of partitioning comprises partitioning each of two or more redundant instances of said tuple space along a single one of said dimensions of said tuple space.

4. The method of claim 1 , wherein said plurality of nodes comprises any of:

a plurality of physical nodes;

a plurality of virtual nodes; and

a combination of physical and virtual nodes.

5. 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.

6. The method of claim 1 , further comprising the step of:

indexing said database.

7. The method of claim 6 , 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.

8. The method of claim 1 , further comprising the step of:

identifying at least one tuple satisfying a transaction that is restricted along one or more restricted dimensions of said tuple space among said dimensions of said tuple space by identifying a partition along said restricted dimensions of said tuple space that contains said tuple and accessing the node on which said identified partition is stored.

9. The method of claim 1 , wherein the step of:

identifying at least one tuple satisfying a transaction that is restricted along a single dimension of said tuple space comprises the steps of:

searching an index to identify at least one partition containing said tuple; and

accessing the node that stores the partition containing the identified tuple.

10. 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:

partitoning each of two or more redundant instances of said tuple space along one or more of said dimensions of said tuple space, so that partitions of each of said instances overlap partitions of other of said instances within said tuple space; and

storing each resulting partition on a separate one of a plurality of nodes of a repository, wherein assignment of each partition to a node is based on a location of said each resulting partition in said tuple space;

wherein said database handles a transaction restricted along less than all of said partitioned dimensions of said tuple space by accessing a single of said nodes.

11. The computer program product of claim 10 , wherein said step of partitioning comprises partitioning each of two or more redundant instances of said tuple space along a different one or more of said dimensions of said tuple space.

12. The computer program product of claim 10 , wherein said step of partitioning comprises partitioning each of two or more redundant instances of said tuple space along a single one of said dimensions of said tuple space.

13. The computer program product of claim 10 , wherein said plurality of nodes comprises any of:

a plurality of physical nodes;

a plurality of virtual nodes; and

a combination of physical and virtual nodes.

14. The computer program product of claim 10 , 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.

15. The computer program product of claim 10 , said method further comprising the step of:

indexing said database.

16. The computer program product of claim 15 , 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.

17. The computer program product of claim 10 , said method further comprising the steps of:

identifying at least one tuple satisfying a transaction that is restricted along one or more restricted dimensions of said tuple space among said dimensions of said tuple space by identifying a partition along said restricted dimensions of said tuple space that contains said tuple; and

accessing the node on which said identified partition is stored.

18. The computer program product of claim 10 , wherein the step of:

identifying at least one tuple satisfying a transaction that is restricted along a single dimension of said tuple space comprises the steps of:

searching an index to identify at least one partition containing said tuple; and

accessing the node that stores the partition containing the identified tuple.

19. A system for partitioning a database storing tuples within a tuple space having a plurality of dimensions, comprising:

a plurality of nodes comprising at least one data storage device; and

at least one processor programmed for:

partitioning each of two or more redundant instances of said tuple space along one or more of said dimensions of said tuple space, so that partitions of each of said instances overlap partitions of other of said instances within said tuple space; and

storing each resulting partition on a separate one of said plurality of nodes, wherein assignment of each partition to a node is based on a location of said each resulting partition in said tuple space; wherein

said database handles a transaction restricted along less than all of said partitioned dimensions of said tuple space by accessing a single one of said nodes.

20. The system of claim 19 , wherein the plurality of nodes comprises any of:

a plurality of physical nodes;

a plurality of virtual nodes; and

a combination of physical and virtual nodes.

21. The system of claim 19 , wherein said at least one processor comprises any of:

a single physical processor;

a plurality of physical processors;

a plurality of virtual processors running on a single computer; and

a plurality of virtual processors running on at least one computer.

22. The system of claim 19 , wherein said at least one processor comprises:

a single processor in communication with a single node;

a single processor in communication with a plurality of nodes; and

a plurality of processors in communication with a plurality of nodes.

23. The system of claim 19 , further comprising at least one processor programmed for managing storage of said partitions on said nodes.

24. The system of claim 19 , further comprising a processor programmed to provide an index to said multidimensional database partitioned in the same manner as said multidimensional database is partitioned.

25. The system of claim 24 , wherein said index comprises one of:

at least one data storage device storing therein 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;

at least one data storage device storing therein a global partitioned index, wherein the index is partitioned using a different partitioning key from the underlying database; and

at least one data storage device storing therein a non-partitioned index.

26. The system of claim 19 , 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 processor by means of a network connection.

27. The system of claim 19 , where said at least one processor is further programmed for:

identifying at least one tuple satisfying a transaction that is restricted along one or more restricted dimensions of said tuple space among said dimensions of said tuple space by identifying a partition along said restricted dimensions of said tuple space that contains said tuple and accessing the node on which said identified partition is stored.

28. The system of claim 19 , wherein said at least one processor is further programmed for:

partitioning each of two or more redundant instances of said tuple space along a different one or more of said dimensions of said tuple space.

29. The system of claim 19 , wherein said at least one processor is further programmed for:

partitioning each of two or more redundant instances of said tuple space along a single one of said dimensions of said tuple space.

30. The system of claim 19 , wherein said at least one 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.