Systems and Methods for Data Storage and Retrieval Using Algebraic Relations Composed From Query Language Statements

• US 20070276784A1
• Filed: 05/15/2006
• Published: 11/29/2007
• Est. Priority Date: 05/15/2006
• Status: Active Grant

• Current Assignee: Algebraix Data Corp.
• Original Assignee: Algebraix Data Corp.
• Inventors: Piedmonte, Christopher
• Granted Patent: US 7,877,370 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 method for establishing algebraic relations from a query language statement comprising:

providing a relation store for storing algebraic relations between data sets;

receiving a query language statement referencing a plurality of data sets;

composing a plurality of algebraic relations referencing the data sets specified in the query language statement; and

storing the plurality of algebraic relations in the relation 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 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 query language statement 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.

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 query language statement has not been stored in the data store at the time the query language statement is received.

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

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

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

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

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

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

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

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

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

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

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

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

18. The method of claim 1, wherein the query language statement requests a data set to be provided, the method further comprising using at least some of the plurality of algebraic relations composed from the query language statement to provide the requested data set.

19. The method of claim 1, wherein the 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 query language statement, the method further comprising using at least some of the other algebraic relations to provide the requested data set.

20. The method of claim 18, wherein the 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 query language statement, the method further comprising using at least some of the other algebraic relations to provide the requested data set.

21. The method of claim 1, wherein the query language statement requests a data set to be provided, the method further comprising:

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; and

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

22. The method of claim 20, further comprising:

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; and

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

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

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

25. The method of claim 21, wherein the optimization criteria includes a costing algorithm.

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

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

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

29. The method of claim 22, wherein the optimization criteria is based, at least in part, on an estimate of the transfer speed of the data channel for retrieving the data sets required to calculate each of the collections of algebraic relations.

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

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

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

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

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

35. The method of claim 21, 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 storage locations.

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

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

38. The method of claim 21, wherein:

the collections of algebraic relations reference at least two equivalent data sets containing the same logical data in different storage locations; 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.

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

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