Systems and Methods for Providing Data Sets Using a Store of Albegraic Relations

• US 20070276802A1
• 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,613,734 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99948 Application of database or data structure, e.g. distributed, multimedia, or image

Abstract

Systems and methods for storing and accessing data. A query language statement may request a data set from the system. Data sets may be composed from the query language statement and other algebraic relations from prior query language statements may be provided in a relation store. The store of algebraic relations may be accumulated over time. The composed algebraic relations and stored algebraic relations may be used to provide the requested data set. Alternative collections of algebraic relations may be generated and evaluated to determine an optimized collection of algebraic relations to use in providing the 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 of providing a requested data set comprising:

receiving a plurality of query language statements that do not request the requested data set;

composing a plurality of algebraic relations between data sets based on the query language statements; and

providing the requested data set based, at least in part, on the plurality of algebraic relations composed from the query language statements.

2. The method of claim 1, wherein the query language statements specify 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 the query language statements specify at least one data set that has not been stored in the data store at the time the request for the requested data set is received.

4. The method of claim 3, wherein the step of using at least some of the algebraic relations composed from the query language statements to calculated the requested data set further comprises using the at least one data set that has not been stored in the data store at the time the request for the requested data set is received.

5. The method of claim 1, wherein each of the algebraic relations has. a single operator and a number of operands in the range of from one to three.

6. The method of claim 1, wherein the query language statements are based on a relational data model.

7. The method of claim 1, wherein the query language statements are based on a markup language model.

8. The method of claim 1, wherein at least one of the query language statements is based on a relational data model and at least one of the query language statements is based on a markup language model.

9. A method of providing a requested data set comprising:

providing a relation store containing a plurality of algebraic relations composed from a plurality of query language statements;

using at least some of the algebraic relations from the relation store to compose a collection of algebraic relations that defines a result equal to the requested data set; and

calculating the requested data set from the collection of algebraic relations.

10. The method of claim 9, further comprising:

receiving a query language statement requesting the requested data set;

composing a plurality of additional algebraic relations based on the query language statement requesting the requested data set; and

using at least some of the additional algebraic relations to compose the collection of algebraic relations.

11. The method of claim 10 further comprising defining at least one new data set by composing an algebraic relation based on a portion of the data sets referenced in the query language statement;

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

12. A method of providing a requested data set comprising:

providing a relation store containing a plurality of algebraic relations composed from a plurality of query language statements;

using at least some of the algebraic relations from the relation store to compose 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 calculate the requested data set.

13. The method of claim 12 further comprising storing each collection of algebraic relations in a tree data structure.

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

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

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

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

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

19. The method of claim 16, further comprising:

providing a plurality of functions, 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.

20. The method of claim 18, further comprising:

providing plurality of functions, 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 one of the equivalent data sets; and

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