Systems and methods for data storage and retrieval using algebraic relations composed from query language statements

• US 8,032,509 B2
• Filed: 01/14/2011
• Issued: 10/04/2011
• 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): Hocker; John P
• Application Number:
  US13/007,522
• Publication Number:
  US 20110113025A1
• Time in Patent Office: 263 Days
• Field of Search: 707/708, 707/713
• US Class Current: 707/708
• 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 computer system comprising:

(a) at least one processor;

(b) at least one memory, wherein the at least one memory includes a relation store and a data set information store; and

(c) computer program instructions stored in the memory and configured to be executed by the processor to provide a requested data set, including;

(i) instructions for receiving a first query language statement referencing a plurality of data sets;

(ii) instructions for storing information in the data set information store regarding the data sets referenced in the first query language statement, including temporal information regarding the data sets referenced in the first query language statement;

(iii) instructions for composing a first plurality of algebraic relations referencing the data sets specified in the first query language statement, 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;

(iv) instructions for storing the first plurality of algebraic relations in the relation store;

(v) instructions for receiving a second query language statement referencing a second plurality of data sets;

(vi) instructions for composing a second plurality of algebraic relations referencing the data sets specified in the second query language statement;

(vii) instructions for storing the second plurality of algebraic relations in the relation store;

(viii) instructions for providing the requested data set in response to the second query language statement using at least one algebraic relation from the first plurality of algebraic relations and at least one algebraic relation from the second plurality of algebraic relations; and

(ix) instructions for removing at least some of the first plurality of algebraic relations from the relation store based, at least in part, on the temporal information regarding the data sets referenced in the first query language statement.

2. The computer system of claim 1 wherein the computer program instructions further comprise:

instructions for defining at least one new data set by composing an algebraic relation referencing at least one of the data sets specified in the second query language statement; and

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

3. The computer system of claim 1, wherein the data sets specified in the second query language statement include at least one explicit data set, the computer program instructions further comprising:

instructions for associating a data set identifier with the explicit data set; and

instructions for storing the data set identifier in the data set information store.

4. The computer system 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 second query language statement has not been stored in the data store at the time the second query language statement is received.

5. The computer system of claim 1, wherein the 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 computer system of claim 1, 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 computer system 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 computer system of claim 5, wherein the computer program instructions further comprise instructions for 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 computer system of claim 8, wherein the instructions for removing at least some of the first plurality of algebraic relations further comprise instructions for removing algebraic relations from the relation store that reference the data sets removed from the data set information store.

10. The computer system 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 computer system 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 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 instructions for temporally redefining the data set information store further comprise instructions for storing the unrealized data set in the data store before removing the data set having temporal information prior to the specified time from the data set information store.

12. The computer system of claim 1, wherein the second plurality of algebraic relations composed from the second query language statement have a single operator and a number of operands in the range of from one to three.

13. The computer system 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 computer system of claim 1, wherein the second query language statement is based on a relational data model.

15. The computer system of claim 1, wherein the second query language statement is received in an structured query language (SQL) format.

16. The computer system of claim 1, wherein the second query language statement is based on a markup language model.

17. The computer system of claim 1, wherein the second query language statement is received in an XQuery format.

18. The computer system of claim 1, wherein the second query language statement requests the requested data set to be provided and the relation store includes other algebraic relations for data sets that are not composed from the second query language statement, the computer program instructions further comprising instructions for using at least some of the other algebraic relations to provide the requested data set.

19. The computer system of claim 1, wherein the second query language statement requests the requested data set to be provided and the requested data set is different from each of the data sets referenced in the first query language statement.