Systems and methods for data storage and retrieval using algebraic optimization

• US 7,769,754 B2
• Filed: 05/15/2006
• Issued: 08/03/2010
• 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): Shmatov; Alexey
• Application Number:
  US11/383,478
• Publication Number:
  US 20070276785A1
• Time in Patent Office: 1,541 Days
• Field of Search: 709/201, 707/999.002, 707/736
• US Class Current: 707/736
• CPC Class Codes: G06F 16/2453 Query optimisation

Abstract

Systems and methods for storing and accessing data. A relation store may be used to store algebraic relations between data sets. 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. Optimization criteria may be based on an estimate of the amount of data required to be transferred and/or the amount of time required to transfer data sets from storage in order to calculate the collection of algebraic relations. The optimization criteria may distinguish among equivalent data sets containing the same logical data in different physical formats or in different locations. 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.

Claims

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

providing a data set information store in the memory;

storing identifiers for a plurality of data sets in the data set information store;

providing a relation store in the memory;

storing a plurality of algebraic relations defining relationships between the plurality of data sets, each of the algebraic relations in the plurality of algebraic relations comprising 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;

receiving a plurality of statements that each reference at least one respective data set identified in the data set information store;

using the statements to define additional data sets;

storing identifiers for the additional data sets in the data set information store;

using the statements to compose a plurality of additional algebraic relations that each define a relationship between at least one of the additional data sets and at least one other data set identified in the data set information store;

receiving a request for the requested data set;

using at least some of the plurality of additional algebraic relations to compose a plurality of collections of algebraic relations that define a result equal to the requested data set, including generating new algebraic relations that were not previously available at the time the requested data set is first requested;

determining a cost for each of the plurality of collections of algebraic relations, wherein the cost is based, at least in part, on an estimate of the transfer time required to retrieve the data sets from the data store required to calculate the requested data set from the collection of algebraic relations;

selecting the collection of algebraic relations with the lowest cost; and

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

2. The method of claim 1, wherein composing the plurality of collections of algebraic relations further comprises composing at least one algebraic relation defining the requested data set and generating a plurality of collections of algebraic relations that are algebraically equivalent to the at least one algebraic relation defining the requested data set.

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

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

5. The method of claim 1 further comprising allocating algebraic relations from the selected collection to the at least one processor for parallel processing.

6. The method of claim 1, wherein the step of determining cost further comprises allocating cost for retrieving a respective data set from the data store only once if the respective data set is referenced in a collection of algebraic relations more than one time.

7. The method of claim 1, wherein composing the plurality of collections of algebraic relations further comprises generating collections of algebraic relations that differentiate between equivalent data sets containing the same logical data in different physical formats.

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

9. The method of claim 7, further comprising:

providing a 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, at least in part, on the format of the data sets referenced in the selected collection of algebraic relations; and

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

10. The method of claim 7, wherein the equivalent data sets include a first data set in a first format and a second data set in a second format that has a larger size than the first format, wherein the step of selecting the collection of algebraic relations with the lowest cost further comprises selecting the data collection that references the second data set if the second data set is available over a data channel with a higher transfer speed than the first data set.

11. The method of claim 7, wherein the equivalent data sets include a first data set available in non-volatile storage in a first format and a second data set available in a volatile memory in a second format that has a larger size than the first format, wherein the step of selecting the collection of algebraic relations with the lowest cost further comprises selecting the collection of algebraic relations that references the second data set.

12. The method of claim 1, wherein composing the plurality of collections of algebraic relations further comprises generating collections of algebraic relations that differentiate between equivalent data sets containing the same logical data in different storage locations.

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

14. 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;

the step of determining cost further comprises estimating the transfer time required to obtain the equivalent data sets from the data store; and

the step of selecting the collection of algebraic relations with the lowest cost further comprises selecting the collection of algebraic relations that references the equivalent data set that has the lowest estimated transfer time.

15. 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 storage locations;

the step of determining cost further comprises estimating the transfer time required to obtain the equivalent data sets from the data store; and

the step of selecting the collection of algebraic relations with the lowest cost further comprises selecting the collection of algebraic relations that references the equivalent data set that has the lowest estimated transfer time.

16. The method of claim 1, further comprising:

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

17. A computer system implemented method for storing a specified data set, the computer system comprising at least one processor, memory and a data store, the method comprising:

providing a data set information store in the memory;

storing identifiers for a plurality of data sets in the data set information store;

providing a relation store in the memory;

storing a plurality of algebraic relations defining relationships between a plurality of data sets, each of the algebraic relations in the first plurality of algebraic relations comprising 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;

receiving a plurality of statements that each reference at least one respective data set identified in the data set information store;

using the statements to define additional data sets;

storing identifiers for the additional data sets in the data set information store;

using the statements to compose a plurality of additional algebraic relations that each define a relationship between at least one of the additional data sets and at least one other data set identified in the data set information store;

receiving a request for the specified data set;

using at least some of the plurality of additional algebraic relations from the relation store to compose a plurality of collections of algebraic relations that define a result equal to the specified data set, including generating new algebraic relations that were not previously available at the time the specified data set is first requested;

determining a cost for each of the plurality of collections of algebraic relations, wherein the cost is based, at least in part, on an estimate of the transfer time required to retrieve the data sets from the data store required to calculate the requested data set from the collection of algebraic relations;

selecting the collection of algebraic relations with the lowest cost; and

using the selected collection of algebraic relations to calculate the specified data set; and

storing the specified data set that has been calculated from the selected collection of algebraic relations in the data store.

18. The method of claim 17, wherein composing the plurality of collections of algebraic relations further comprises composing at least one algebraic relation defining the specified data set and generating a plurality of collections of algebraic relations that are algebraically equivalent to the at least one algebraic relation defining the specified data set.