Systems and methods for indirect algebraic partitioning

• US 8,583,687 B1
• Filed: 05/15/2012
• Issued: 11/12/2013
• Est. Priority Date: 05/15/2012
• Status: Active Grant

• Current Assignee: Algebraix Data Corp.
• Original Assignee: Algebraix Data Corp.
• Inventors: Piedmonte, Christopher M., Rogers, William A.
• Primary Examiner(s): Alam, Shahid
• Assistant Examiner(s): Sultana, Nargis
• Application Number:
  US13/472,271
• Publication Number:
  US 20130311513A1
• Time in Patent Office: 546 Days
• Field of Search: 707/776, 707/736, 707/737, 707/769, 707/802
• US Class Current: 707/776
• CPC Class Codes: G06F 16/278 Data partitioning, e.g. horizontal or vertical partitioning

Abstract

Systems and methods for storing and accessing data. Example embodiments may perform optimization based on patterns of requests received by the system and relations between data sets identified by the system. Example embodiments may identify restrictions on a data set based on a different data set. Conditions for automatically algebraically partitioning the data set based on a constituent of a different data set may be evaluated, including evaluation of the relationship between the data sets and identification of a pattern of statements restricting the data set using the same logical structure. If the conditions are met, component data sets and a partition data set may be algebraically defined based on ranges applied to constituent(s) of the other data set. The component data sets may also be realized in storage to physically partition the data set.

Claims

1. A computer system comprising:

(a) at least one processor;

(b) at least one memory, wherein the at least one memory includes a relation store for storing a plurality of algebraic relations;

(c) a storage system, including a data store for storing a plurality of data sets; and

(d) at least one program module, the program module stored in the memory and configured to be executed by the processor, including;

instructions for composing a plurality of algebraic relations between data sets;

instructions for storing the plurality of algebraic relations in the relation store;

instructions for receiving a first statement referencing a first data set and a second data set;

instructions for determining whether the first statement specifies at least one constituent of the first data set for restricting the second data set, wherein the constituent is not included in the second data set;

instructions for determining whether a condition for indirect partitioning of the second data set based on the constituent of the first data set is satisfied;

instructions for automatically defining component data sets if the condition for indirect partitioning is satisfied, wherein each component data set includes a distinct component of the second data set defined, at least in part, by a selection criteria based on the constituent of the first data set;

instructions for storing in the relation store, for each component data set, at least one algebraic relation referencing the respective component data set;

instructions for receiving a second statement that requests a requested data set; and

instructions for providing the requested data set, including;

instructions for composing a collection of algebraic relations defining a result equal to the requested data set, including at least one algebraic relation from the relation store that references at least one of the component data sets; and

instructions for calculating the requested data set using the collection of algebraic relations.

2. The computer system of claim 1 wherein the instructions for determining the condition for indirect partitioning include instructions for evaluating a relationship between the first data set and the second data set.

3. The computer system of claim 1 wherein the instructions for determining the condition for indirect partitioning include instructions for determining whether a relationship between the first data set and the second data set is a one-to-one or one-to-many relationship.

4. The computer system of claim 1 wherein the instructions for determining the condition for indirect partitioning include instructions for determining whether a relationship between the first data set and the second data set is based on a key for the first data set.

5. The computer system of claim 1 wherein the instructions for determining the condition for indirect partitioning include instructions for determining whether a relationship between the first data set and the second data set is based on a constituent of the first data set that is distinct for each member of the first data set.

6. The computer system of claim 1 wherein the instructions for determining the condition for indirect partitioning include instructions for determining whether the relation store includes at least a threshold number of algebraic relations that restrict the second data set based on the constituent of the first data set.

7. The computer system of claim 6 wherein the threshold number is at least two.

8. The computer system of claim 1 wherein the instructions for determining the condition for indirect partitioning include instructions for identifying a pattern of restrictions of the second data set based on the constituent of the first data set.

9. The computer system of claim 1 wherein the instructions for determining the condition for indirect partitioning include instructions for identifying a pattern of restrictions against the second data set having the same logical structure as the restriction specified by the first statement.

10. The computer system of claim 1 wherein the instructions for determining the condition for indirect partitioning include instructions for determining that the second data set is larger than a threshold size.

11. The computer system of claim 1 wherein the instructions for automatically defining component data sets include instructions for joining the first data set and the second data set.

12. The computer system of claim 11 wherein the instructions for automatically defining component data sets include instructions for removing elements of the first data set from the joined data set.

13. The computer system of claim 11 wherein the instructions for automatically defining component data sets include instructions for partitioning the joined data set based, at least in part, on distinct ranges applied to the constituent of the first data set.

14. The computer system of claim 12 wherein the instructions for automatically defining component data sets include instructions for partitioning the joined data set based, at least in part, on distinct ranges applied to the constituent of the first data set.

15. The computer system of claim 1 wherein the instructions for composing the collection of algebraic relations include instructions for selecting at least one component data set to reference in the collection of algebraic relations by intersecting a restriction composed from the second statement with the collection of component data sets.

16. The computer system of claim 1 wherein the instructions for providing the requested data set include instructions for composing and evaluating a plurality of alternative collections of algebraic relations defining a result equal to the requested data set, wherein at least one of the alternative collections includes at least one algebraic relation from the relation store that references at least one of the component data sets.

17. The computer system of claim 1 wherein the instructions for providing the requested data set include instructions for calculating at least one of the component data sets.

18. The computer system of claim 17 further comprising instructions for realizing the component data set in the data store.

19. The computer system of claim 1 further comprising instructions for realizing each of the component data sets in the data store.

20. The computer system of claim 19 wherein the instructions for realizing each of the component data sets in the data store include instructions for calculating at least some of the component data sets as part of a background process.

21. The computer system of claim 1 wherein the instructions for composing the plurality of algebraic relations include instructions for composing algebraic relations from a plurality of statements received by the system over time.

22. The computer system of claim 1 further comprising instructions for indirectly partitioning the second data set into a collection of different component data sets.

23. The computer system of claim 1 further comprising instructions for indirectly partitioning the second data set based on at least one constituent of a third data set, wherein the constituent of the third data set is not included in the first data set or the second data set.

24. The computer system of claim 23, further comprising instructions for determining that there is a one-to-one or one-to-many relationship between members of the third data set and the members of the second data set.

25. The computer system of claim 1 further comprising instructions for indirectly partitioning a third data set based, at least in part, on the constituent of the first data set, further comprising instructions for determining that there is a one-to-one or one-to-many relationship between members of the second data set and the members of the third data set.

26. The computer system of claim 1 further comprising instructions for indirectly partitioning a plurality of other data sets.

27. The computer system of claim 1 further comprising instructions for directly partitioning the first data set based on the constituent of the first data set.

28. The computer system of claim 14 further comprising instructions for partitioning the first data set based, at least in part, on the distinct ranges applied to the constituent of the first data set.

29. The computer system of claim 1 further comprising instructions for:

defining at least one partition data set based on the component data sets, wherein the partition data set has a higher mathematical class than the second data set; and

adding at least one algebraic relation referencing the partition data set to the relation store;

wherein the instructions for providing the requested data set further comprise instructions for using the algebraic relation referencing the partition data set to compose the collection of algebraic relations.

30. The computer system of claim 29 wherein the second data set is a clan and the partition data set is a hoard.

31. A computer-program product for use in conjunction with a computer system, the computer-program product comprising a non-transitory computer-readable storage medium and a computer-program mechanism embedded therein, including:

instructions for composing a plurality of algebraic relations between data sets;

instructions for storing the plurality of algebraic relations in a relation store;

instructions for receiving a first statement referencing a first data set and a second data set;

instructions for determining whether the first statement specifies at least one constituent of the first data set for restricting the second data set, wherein the constituent is not included in the second data set;

instructions for determining whether a condition for indirect partitioning of the second data set based on the constituent of the first data set is satisfied;

instructions for automatically defining component data sets if the condition for indirect partitioning is satisfied, wherein each component data set includes a distinct component of the second data set defined, at least in part, by a selection criteria based on the constituent of the first data set;

instructions for storing in the relation store, for each component data set, at least one algebraic relation referencing the respective component data set;

instructions for receiving a second statement that requests a requested data set; and

instructions for providing the requested data set, including;

instructions for composing a collection of algebraic relations defining a result equal to the requested data set, including at least one algebraic relation from the relation store that references at least one of the component data sets; and

instructions for calculating the requested data set using the collection of algebraic relations.

32. A computer implemented method for partitioning a data set comprising:

composing a plurality of algebraic relations between data sets;

storing the plurality of algebraic relations in a relation store;

receiving a first statement referencing a first data set and a second data set;

determining, by a computer, whether the first statement specifies at least one constituent of the first data set for restricting the second data set, wherein the constituent is not included in the second data set;

determining, by the computer, whether a condition for indirect partitioning of the second data set based on the constituent of the first data set is satisfied;

automatically defining, by the computer, component data sets if the condition for indirect partitioning is satisfied, wherein each component data set includes a distinct component of the second data set defined, at least in part, by a selection criteria based on the constituent of the first data set;

storing in the relation store, for each component data set, at least one algebraic relation referencing the respective component data set;

receiving a second statement that requests a requested data set; and

providing the requested data set, including;

composing, by the computer, a collection of algebraic relations defining a result equal to the requested data set, including at least one algebraic relation from the relation store that references at least one of the component data sets; and

calculating, by the computer, the requested data set using the collection of algebraic relations.