Systems and Methods for Data Storage and Retrieval Using Algebraic Optimization

• US 20070276785A1
• 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,769,754 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 from storage 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 in the data store. 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 providing a requested data set, comprising:

providing a plurality of algebraic relations defining relationships between a plurality of data sets;

using at least some of the plurality of algebraic relations to compose a plurality of collections of algebraic relations that define a result equal to the requested data set;

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 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 using at least some of the plurality of algebraic relations to generate new algebraic relations that were not previously available at the time the requested data set is first requested.

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

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

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

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

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

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

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

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

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

12. 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 storage; 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.

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

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

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

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

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

18. A method for storing a specified data set, comprising:

providing a plurality of algebraic relations defining relationships between a plurality of data sets;

using at least some of the plurality of algebraic relations to compose a plurality of collections of algebraic relations that define a result equal to the specified data set;

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

19. The method of claim 18, wherein composing the plurality of collections of algebraic relations further comprises generating new algebraic relations that were not previously available at the time the specified data set is first specified.

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

21. A method for providing a requested data set:

providing a storage system for storing data sets;

composing at least two alternative algebraic relations that each define a result equal to the requested data set, including a first algebraic relation based on a first collection of data sets stored in the storage system and a second algebraic relation based on a second collection of data sets stored in the storage system;

selecting between the first algebraic relation and the second algebraic relation based, at least in part, on an estimate of the transfer time required to retrieve the first collection of data sets from the storage system in order to use the first algebraic relation to calculate the requested data set and on an estimate of the transfer time required to retrieve the second collection of data sets from the storage system in order to use the second algebraic relation to calculate the requested data set; and

using the selected algebraic relation to calculate the requested data set.