Systems and methods for providing data sets using a store of albegraic relations

• US 7,613,734 B2
• Filed: 05/15/2006
• Issued: 11/03/2009
• 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): Corrielus; Jean M
• Application Number:
  US11/383,477
• Publication Number:
  US 20070276802A1
• Time in Patent Office: 1,268 Days
• Field of Search: 707/2, 707/3, 707/4, 707/5, 707/10, 707/104.1, 707/203
• 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 computer system implemented method of providing a requested data set, the computer system comprising at least one processor, memory, and a data store, the method comprising:

receiving a first plurality of query language statements that request a first plurality of data sets, wherein at least some of the data sets from the first plurality of data sets are stored in the data store and wherein the first plurality of query language statements specify at least one explicit data set;

associating a data set identifier with each of the explicit data sets specified in the first plurality of query language statements;

composing a first plurality of algebraic relations between data sets based on the first plurality of query language statements, 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;

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

receiving a subsequent query language statement requesting the requested data set, wherein the requested data set is different than each of the data sets in the first plurality of data sets;

using at least some of the first plurality of 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, wherein the optimization criteria is based, at least in part, on a cost for retrieving data sets from the data store required to calculate each of the collections of algebraic relations;

calculating the requested data set using the selected collection of algebraic relations; and

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

2. The method of claim 1, the method further comprising:

storing the data set identifier for each of the explicit data sets in a data set information store.

3. The method of claim 1, wherein the first plurality of query language statements specify at least one data set that has not been stored in the data store at the time the subsequent query language statement requesting the requested data set is received.

4. The method of claim 3, further comprising calculating the requested data set using the at least one data set that has not been stored in the data store at the time the subsequent query language statement requesting 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 first plurality of query language statements are based on a relational data model.

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

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

9. The method of claim 1, further comprising:

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

creating a collection of algebraic relations using at least some of the additional algebraic relations.

10. The method of claim 9 further comprising:

defining at least one new data set by composing an algebraic relation based on the query language statement requesting the requested data set; and

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

11. The method of claim 1 further comprising storing each collection of algebraic relations in a tree data structure in the memory.

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

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

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

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

16. The method of claim 1, wherein the collections of algebraic relations reference at least two equivalent data sets containing the same logical data in different physical formats;

estimating a 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.

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

18. The method of claim 16, 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 execute the requested data set, including the selected one of the algebraically equivalent functions.