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

• US 20110113025A1
• Filed: 01/14/2011
• Published: 05/12/2011
• Est. Priority Date: 05/15/2006
• Status: Active Grant

• Current Assignee: Algebraix Data Corp.
• Original Assignee: Algebraix Data Corp.
• Inventors: Piedmonte, Christopher M.
• Granted Patent: US 8,032,509 B2
• Time in Patent Office: Days
• US Class Current: 707/713
• 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;

storing the plurality of algebraic relations in the relation store;

receiving a subsequent query language statement requesting a requested data set; and

providing the requested data set in response to the subsequent query language statement using at least one of the plurality of algebraic relations stored 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-40. -40. (canceled)