Systems and methods for data manipulation using multiple storage formats

• US 7,720,806 B2
• Filed: 05/15/2006
• Issued: 05/18/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,479
• Publication Number:
  US 20070276786A1
• Time in Patent Office: 1,464 Days
• Field of Search: None
• US Class Current: 707/719
• CPC Class Codes: G06F 16/2453 Query optimisation

Abstract

Systems and methods for storing and accessing data. Algebraic relations may be composed that each define a result equal to a requested data set. The algebraic relations may reference other data sets in storage. Some of the data sets may contain the same logical data stored in different physical formats and/or in different locations in the data store. One of the algebraic relations may be selected for use in providing the requested data set based, at least in part, on the physical format and/or locations of the data sets referenced in the algebraic relations. In other examples, algebraic relations may be selected based, at least in part, on the speed and available bandwidth of the channel(s) used to retrieve data sets referenced in the algebraic relation. Functions may be used to calculate the algebraic relation using the data sets retrieved from storage. The functions may be format specific based on the physical formats of the data sets provided as operands to the functions.

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 relation store in the memory;

storing a plurality of data sets in the data store, including at least a first data set and a second data set, wherein the date store includes a volatile memory and a non-volatile storage medium and wherein the first data set and the second data set contain the same logical data stored in different physical formats, the first data set being stored in a first physical format having a first size and the second data set being stored in a second physical format having a second size that is smaller than the first size;

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 at least the first data set stored in the data store and a second algebraic relation based on at least the second data set stored in the data store, wherein the first algebraic relation and the second algebraic relation each comprise 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 algebraic relation and the second algebraic relation in the relation store;

determining that the first data set is available in the volatile memory; and

selecting the first algebraic relation to calculate the requested data set.

2. The method of claim 1, wherein the physical format of the first data set is selected from the group consisting of comma separated value format, tab delimited value format, binary string format, fixed offset format and markup language format.

3. The method of claim 2, wherein the physical format of the second data set is selected from the group consisting of comma separated value format, tab delimited value format, binary string format, fixed offset format and markup language format.

4. The method of claim 1, further comprising providing a plurality of functions, wherein the plurality of functions includes a first function that operates on a data set in the physical format of the first data set and a second function that operates on a data set in the physical format of the second data set, wherein the first function and the second function are algebraically equivalent;

and

using the first algebraic relation and the first function to calculate the requested data set.

5. The method of claim 1, wherein the data store includes a plurality of data channels and the first data set and the second data set are available over different data channels.

6. The method of claim 5, wherein the first data set in the first physical format is available over a first data channel having a first data transfer rate, and the second data set in the second physical format is available over a second data channel having a second data transfer rate, the method further comprising:

determining a first cost based, at least in part, on the first size and the first data transfer rate; and

determining a second cost based, at least in part, on the second size and the second data transfer rate;

wherein the step of selecting the first algebraic relation to calculate the requested data set further comprises determining that the first cost is lower than the second cost.

7. The method of claim 1, further comprising:

providing a plurality of functions for operating on the data sets in the plurality of physical formats, wherein each function is configured to operate on at least one operand in a respective one of the physical formats;

selecting one of the plurality of functions that is configured to operate on an operand in the first physical format of the first data set; and

using the selected function to calculate the requested data set from the first algebraic relation.

8. The method of claim 7, wherein the first algebraic relation specifies at least one operation and the selected function corresponds to the specified operation.

9. The method of claim 7, wherein the plurality of functions includes algebraically equivalent functions configured to operate on operands in different physical formats.

10. The method of claim 9, wherein the step of selecting the first algebraic relation further comprises selecting the first algebraic relation from a plurality of algebraic relations in the relation store that each define a result equal to the requested data set.

11. The method of claim 10, wherein the step of selecting the first algebraic relation further comprises selecting the algebraic relation based, at least in part, on an estimate of the time required to retrieve the first data set from the data store.

12. The method of claim 7, wherein the step of selecting the first algebraic relation further comprises selecting the first algebraic relation from a plurality of algebraic relations in the relation store that each define a result equal to the requested data set.