Systems and methods for data storage and retrieval using algebraic relations composed from query language statements

• US 8,380,695 B2
• Filed: 08/19/2011
• Issued: 02/19/2013
• Est. Priority Date: 05/15/2006
• Status: Active Grant

• Current Assignee: Algebraix Data Corp.
• Original Assignee: Algebraix Data Corp.
• Inventors: Piedmonte, Christopher M.
• Primary Examiner(s): Btit, Jacob F.
• Assistant Examiner(s): Hocker, John P
• Application Number:
  US13/214,014
• Publication Number:
  US 20120041943A1
• Time in Patent Office: 550 Days
• Field of Search: 707/707, 707/708
• US Class Current: 707/707
• CPC Class Codes: G06F 16/2433 Query languages
• CPC Class Codes: G06F 16/2453 Query optimisation

Abstract

Systems and methods for storing and accessing data. A query language statement may reference a plurality of data sets and a plurality of algebraic relations between the data sets may be composed from the query language statement. The algebraic relations may be used to define new data sets and to optimize access to data sets. A store of algebraic relations may be accumulated over time. Alternative collections of algebraic relations may be generated and evaluated to determine an optimized collection of algebraic relations to use in calculating and providing a requested data set. The optimization may be performed using the algebraic relations rather than retrieving underlying data sets from storage. As a result, optimization may be performed at processor speeds to minimize the amount of time required for data to be retrieved from slower storage.

Claims

1. A computer implemented method for providing a requested data set, the computer comprising at least one processor and at least one memory, the method comprising:

(a) providing a relation store in the memory;

(b) receiving a plurality of query language statements;

(c) accumulating a first plurality of algebraic relations in the relation store over time as the query language statements are received, including for each respective query language statement;

(i) composing, by the computer, at least one algebraic relation from the respective query language statement, wherein the algebraic relation comprises a respective first expression including a symbolic representation of at least a first respective data set specified by the respective query language statement, a respective second expression including a symbolic representation of at least a second respective data set specified by the respective query language statement, and a relational operator symbolically defining a mathematical relationship between the respective first expression and the respective second expression; and

(ii) storing the algebraic relation in the relation store;

(d) composing, by the computer, a second plurality of algebraic relations based, at least in part, on a pattern of the query language statements that have been received;

(e) storing the second plurality of algebraic relations in the relation store;

(f) receiving a request for the requested data set;

(g) composing, by the computer, a plurality of collections of algebraic relations defining a result equal to the requested data set using at least some of the algebraic relations stored in the relation store, including at least one of the algebraic relations from the second plurality of algebraic relations;

(h) applying optimization criteria to select one of the collections of algebraic relations; and

(i) using the selected collection of algebraic relations to provide the requested data set.

2. The method of claim 1, wherein the data sets specified in at least one of the query language statements include at least one explicit data set, the method further comprising:

providing a data set information store for storing information regarding the data sets;

associating a data set identifier with the explicit data set; and

storing the data set identifier in the data set information store.

3. The method of claim 1, further comprising providing a data store for storing at least some of the data sets, wherein at least one of the data sets specified in at least one of the query language statements has not been stored in the data store at the time the query language statement is received.

4. The method of claim 1, further comprising providing a data set information store for storing information regarding the data sets, wherein temporal information is associated with each of the data sets in the data set information store to indicate the time at which information regarding the data set is added to the data set information store.

5. The method of claim 4, further comprising temporally redefining the data set information store by removing data sets from the data set information store that are associated with temporal information prior to a specified time.

6. The method of claim 5, further comprising removing algebraic relations from the relation store that reference the data sets removed from the data set information store.

7. The method of claim 1, further comprising providing a data set information store for storing information regarding the data sets, wherein the data set information store includes a unique identifier and an external identifier associated with each data set in the data information store and wherein the external identifier is the same for at least some of the data sets.

8. The method of claim 1, wherein the first plurality of algebraic relations composed from the query language statements each have a single operator and a number of operands in the range of from one to three.

9. The method of claim 1, wherein each of the query language statements is received in an structured query language (SQL) format.

10. The method of claim 1, wherein the pattern comprises a plurality of restrictions against a respective data set using a range of scalar values.

11. The method of claim 1, wherein the pattern comprises a plurality of requests requiring only a subset of domains of a respective data set.

12. The method of claim 1, wherein composing the second plurality of algebraic relations comprises partitioning a respective data set into a plurality of data sets that are each a subset of the respective data set, and storing an algebraic relation in the relation store for each of the subsets.

13. The method of claim 12, further comprising calculating each of the subsets.

14. The method of claim 12, further comprising providing a data set information store and storing a data set identifier in the data set information store for each of the subsets.

15. The method of claim 12, further comprising providing a data store and storing each of the subsets in the data store.

16. A computer system comprising:

at least one processor;

at least one memory, wherein the memory includes a relation store;

computer program instructions stored in the memory and configured to be executed by the processor to provide a requested data set, including;

(a) instructions for receiving a plurality of query language statements;

(b) instructions for accumulating a first plurality of algebraic relations in the relation store over time as the query language statements are received, including for each respective query language statement;

(i) composing at least one algebraic relation from the respective query language statement, wherein the algebraic relation comprises a respective first expression including a symbolic representation of at least a first respective data set specified by the respective query language statement, a respective second expression including a symbolic representation of at least a second respective data set specified by the respective query language statement, and a relational operator symbolically defining a mathematical relationship between the respective first expression and the respective second expression; and

(ii) storing the algebraic relations in the relation store;

(c) instructions for composing a second plurality of algebraic relations based, at least in part, on a pattern of the query language statements that have been received;

(d) instructions for storing the second plurality of algebraic relations in the relation store;

(e) instructions for receiving a request for a requested data set;

(f) instructions for composing a plurality of collections of algebraic relations defining a result equal to the requested data set using at least some of the algebraic relations stored in the relation store, including at least one of the algebraic relations from the second plurality of algebraic relations;

(g) instructions for applying optimization criteria to select one of the collections of algebraic relations; and

(h) instructions for using the selected collection of algebraic relations to provide the requested data set.

17. The system of claim 16, wherein the pattern comprises a plurality of restrictions against a respective data set using a range of scalar values.

18. The system of claim 16, wherein the pattern comprises a plurality of requests requiring only a subset of domains of a respective data set.

19. The system of claim 16, wherein the instructions for composing the second plurality of algebraic relations comprise instructions for partitioning a respective data set into a plurality of data sets that are each a subset of the respective data set and storing an algebraic relation in the relation store for each of the subsets.

20. The system of claim 19, further comprising instructions for calculating each of the subsets.

21. The system of claim 19, further comprising a data set information store in the memory and instructions for storing a data set identifier in the data set information store for each of the subsets.

22. The system of claim 19, further comprising a storage system including a data store and instructions for storing each of the subsets in the data store.