Systems and Methods for Data Storage and Retrieval Using Virtual Data Sets

• US 20070266000A1
• Filed: 05/15/2006
• Published: 11/15/2007
• Est. Priority Date: 05/15/2006
• Status: Active Grant

• Current Assignee: Algebraix LLC
• Original Assignee: Algebraix Data Corp.
• Inventors: Piedmonte, Christopher
• Granted Patent: US 7,865,503 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/245 Query processing

Abstract

Systems and methods for storing and accessing data using virtual data sets. Data sets may be removed from a data store and defined by algebraic relations between other data sets that are realized in the data store. A flag may be set to indicate that the data set is virtual. Criteria may be established for determining when a data set should be virtualized. For example, the criteria may be based on the size of the data set, the number of times it has been referenced and/or the frequency with which the data set has been accessed in the data store. A data set may also be optimized by partitioning the data set into subsets. The original data set may then be removed from the data store. An algebraic relation may be composed that defines the data set based on the subsets realized in the data store. The algebraic relation for the virtual data set may be used for optimizing access to other data sets even though the virtual data set is not realized.

Claims

1. A method for storing data sets comprising:

providing a data store;

providing a data set information store for storing information regarding a plurality of data sets, including information specifying whether each respective data set is realized in the data store;

providing a relation store for storing a plurality of algebraic relations between the data sets;

establishing a criteria for virtualization of data sets in the data set information store;

identifying at least one data set that is realized in the data store and meets the criteria for virtualization;

determining that the relation store includes at least one algebraic relation defining the identified data set based upon at least one other data set that is realized in the data store;

removing the identified data set from the data store; and

changing the information regarding the identified data set in the data set information store to indicate that the identified data set is not realized in the data store.

2. The method of claim 1, wherein the criteria for virtualization include the size of the respective data set.

3. The method of claim 1, wherein the criteria for virtualization include the number of times that the data set has been referenced.

4. The method of claim 1, wherein the criteria for virtualization include the frequency which the respective data set has been accessed in the data store.

5. The method of claim 1, wherein the algebraic relation defining the identified data set references at least two other data sets that are realized in the data store.

6. The method of claim 1, wherein the at least one other data set used to define the identified data set contains the same logical data in a different physical format.

7. The method of claim 6, wherein the physical format in which the identified data set is stored is larger than the physical format of the at least one other data set.

8. The method of claim 7, wherein the physical format in which the identified data set is stored 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.

9. The method of claim 7, wherein the physical format in which the at least one other data set is stored 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.

10. The method of claim 1, further comprising using the algebraic relation defining the identified data set to provide a requested data set without realizing the identified data set.

11. The method of claim 10, wherein the step of using the algebraic relation defining the identified data set to provide a requested data set further comprises:

composing a plurality of collections of algebraic relations defining the requested data set, wherein the algebraic relation defining the identified data is used to compose at least one of the collections of algebraic relations;

applying an optimization criteria to select one of the collections of algebraic relations to calculate the requested data set;

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

12. The method of claim 11, wherein the algebraic relation defining the identified data is used as a substitution for a reference to the identified data set in at least one of the collections of algebraic relations.

13. A method for storing data sets comprising:

providing a data store;

providing a data set information store for storing information regarding a plurality of data sets, including information specifying whether each respective data set is realized in the data store;

providing a relation store for storing a plurality of algebraic relations between the data sets;

selecting at least one data set from the data set information store that is realized in the data store;

adding data sets to the data set information store that are subsets of the selected data set and realizing the added data sets in the data store;

adding an algebraic relation to the relation store that defines the selected data set based on the added data sets;

removing the selected data set from the data store; and

changing the information regarding the selected data set in the data set information store to indicate that the selected data set is not realized in the data store.

14. The method of claim 13, further comprising:

receiving a statement requesting a requested data set, wherein the statement includes an expression referencing the selected data set;

composing an algebraic relation having a result equal to the requested data set, wherein the algebraic relation includes an expression referencing at least one of the added subsets as a substitution for the expression referencing the selected data set;

using the algebraic relation to calculate the requested data set.

15. The method of claim 13, wherein the added data sets are partitions of the selected data set having equal cardinality.

16. The method of claim 13, wherein the added data sets are subsets defined by ranges of scalar values for a data item that is included in the selected data set.

17. A method for storing data sets comprising:

providing a relation store for storing algebraic relations between data sets;

providing a data store for storing data sets, including at least a first data set, a second data set and a third data set;

composing an algebraic relation that defines the first data set using at least the second data set and the third data set;

adding the algebraic relation to the relation store; and

removing the first data set from the data store after the algebraic relation has been added to the relation store.

18. The method of claim 17, wherein at least one of the second data set and the third data set is stored in the data store in a physical format different from the physical format in which the first data set is stored in the data store.

19. The method of claim 18, wherein the physical format in which the first data set is stored 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.

20. The method of claim 17 further comprising:

providing a data set information store for storing information regarding a plurality of data sets, including information indicating that the first data set, the second data set and the third data set are realized in the data store; and

changing the information regarding the first data set in the data set information store to indicate that the first data set is not realized in the data store.