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

• US 7,877,370 B2
• Filed: 05/15/2006
• Issued: 01/25/2011
• 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): Ali; Mohammad
• Assistant Examiner(s): Hocker; John P
• Application Number:
  US11/383,476
• Publication Number:
  US 20070276784A1
• Time in Patent Office: 1,716 Days
• Field of Search: 707 1- 10, 707/708, 707/713, 707999001-99901
• US Class Current: 707/708
• 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 system implemented method, the computer system comprising at least one processor, memory and a data store, the method comprising:

(A) receiving a first query language statement referencing a plurality of data sets;

(B) providing a data set information store for storing information regarding the data sets specified in the first query language statement,

(C) 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;

(D) composing a first plurality of algebraic relations referencing the data sets specified in the first query language statement, wherein each of the algebraic relations in the first plurality of algebraic relations comprises a respective first expression including a symbolic representation of at least a first respective data set, a respective second expression including a symbolic representation of at least a second respective data set, and a relational operator symbolically defining a mathematical relationship between the respective first expression and the respective second expression;

(E) storing the first plurality of algebraic relations in a relation store in the memory;

(F) after storing the first plurality of algebraic relations in the relation store, receiving a second query language statement referencing a second plurality of data sets;

(G) composing a second plurality of algebraic relations referencing the data sets specified in the second query language statement;

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

(I) using the at least one processor to provide a data set in response to the second query language statement using at least one algebraic relation from the first plurality of algebraic relations and at least one algebraic relation from the second plurality of algebraic relations; and

(J) 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; and

(H) removing algebraic relations from the relation store that reference the data sets removed from the data set information store.

2. The method of claim 1 further comprising:

defining at least one new data set by composing an algebraic relation referencing at least one of the data sets specified in the second query language statement; and

storing the algebraic relation for the new data set in the relation store.

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

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

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

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

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

6. The method of claim 1, further comprising a data store for storing at least some of the data sets, wherein the data set information store includes information regarding at least one data set that is defined by an algebraic relation in the relation store and is not stored in the data store.

7. The method of claim 1, further comprising a data store for storing at least some of the data sets, wherein the data set information store includes information regarding at least one unrealized data set that is not stored in the data set store and is defined by an algebraic relation in the relation store that references a data set having temporal information prior to the specified time, wherein the step of temporally redefining the data set information store further comprising storing the unrealized data set in the data set store before removing the data set having temporal information prior to the specified time from the data set information store.

8. The method of claim 1, wherein the second plurality of algebraic relations composed from the second query language statement includes at least one algebraic relation having a single operator and a number of operands in the range of from one to three.

9. The method of claim 2 wherein the algebraic relation for the new data set has a single operator and a number of operands in the range of from one to three.

10. The method of claim 1, wherein the second query language statement is based on a relational data model.

11. The method of claim 1, wherein the second query language statement is received in an structured query language (SQL) format.

12. The method of claim 1, wherein the second query language statement is based on a markup language model.

13. The method of claim 1, wherein the second query language statement is received in an XQuery format.

14. The method of claim 1, wherein the second query language statement requests a data set to be provided and the relation store includes other algebraic relations for data sets that are not composed from the second query language statement, the method further comprising using at least some of the other algebraic relations to provide the requested data set.

15. The method of claim 1, wherein providing the data set in response to the second query language statement further comprises:

providing a plurality of collections of algebraic relations defining a result equal to the requested data set;

applying optimization criteria to select one of the collections of algebraic relations, wherein the selected collection of algebraic relations includes the at least one algebraic relation from the first plurality of algebraic relations and the at least one algebraic relation from the second plurality of algebraic relations; and

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

16. The method of claim 15, further comprising storing each collection of algebraic relations in a tree data structure.

17. The method of claim 15, further comprising allocating the algebraic relations from the selected collection to processing resources for parallel processing.

18. The method of claim 15, wherein the optimization criteria includes a costing algorithm.

19. The method of claim 15, wherein the optimization criteria includes a costing algorithm and the selected collection of algebraic relations has the least cost according to the costing algorithm.

20. The method of claim 15, wherein the optimization criteria is based, at least in part, on an estimate of the time required to retrieve data sets from storage that are required in order to calculate each of the collections of algebraic relations.

21. The method of claim 15, wherein the optimization criteria is based, at least in part, on the amount of data to be retrieved from storage to calculate each of the collections of algebraic relations.

22. The method of claim 15, wherein:

the optimization criteria is based, at least in part, on a cost for retrieving data sets from storage required to calculate each of the collections of algebraic relations; and

the optimization criteria allocates the cost for retrieving a respective data set from storage only once if the respective data set is referenced in a collection of algebraic relations more than one time.

23. The method of claim 15, wherein the step of providing a plurality of collections of algebraic relations includes:

retrieving an algebraic relation from the relation store that defines the requested data set; and

generating a plurality of collections of algebraic relations that are algebraically equivalent to the retrieved algebraic relation.

24. The method of claim 15, wherein the plurality of collections of algebraic relations further includes at least two collections of algebraic relations that are not algebraically equivalent to one another, but will both provide a result equal to the requested data set.

25. The method of claim 15, wherein the step of providing a plurality of collections of algebraic relations includes generating collections of algebraic relations that differentiate between equivalent data sets containing the same logical data in different physical formats.

26. The method of claim 25, wherein the different physical formats are selected from the group consisting of comma separated value format, tab delimited value format, binary string format, fixed offset format and markup language format.

27. The method of claim 25, wherein at least some of the equivalent data sets are available over different data channels.

28. The method of claim 15, wherein:

the collections of algebraic relations reference at least two equivalent data sets containing the same logical data in different physical formats; and

the step of applying the optimization criteria further comprises estimating the transfer time required to obtain the equivalent data sets from storage and selecting one of the equivalent data sets that has the lowest estimated transfer time.

29. The method of claim 15, further comprising:

providing plurality of functions for calculating algebraic relations, wherein the plurality of functions includes at least two algebraically equivalent functions that operate on data sets in different physical formats; and

using at least some of the functions to provide the requested data set.

30. The method of claim 28, further comprising:

providing plurality of functions for calculating algebraic relations, wherein the plurality of functions includes at least two algebraically equivalent functions that operate on data sets in different physical formats;

selecting one of the algebraically equivalent functions based on the format of the selected equivalent data set to be retrieved from storage; and

using at least some of the functions to realize the requested data set, including the selected one of the algebraically equivalent functions.