Value-instance connectivity computer-implemented database

• US 20080059412A1
• Filed: 08/31/2006
• Published: 03/06/2008
• Est. Priority Date: 08/31/2006
• Status: Abandoned Application

• Current Assignee: Stephen A. Tarin
• Original Assignee: Stephen A. Tarin
• Inventors: Tarin, Stephen A.
• Application Number:
  US11/514,675
• Publication Number:
  US 20080059412A1
• Time in Patent Office: Days
• US Class Current: 707/2
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP

Abstract

A computer-implemented database and method providing an efficient, ordered reduced space representation of multi-dimensional data. The data values for each attribute are stored in a manner that provides an advantage in, for example, space usage and/or speed of access, such as in condensed form and/or sort order. Instances of each data value for an attribute are identified by instance elements, each of which is associated with one data value. Connectivity information is provided for each instance element that uniquely associates each instance element with a specific instance of a data value for another attribute. In accordance with one aspect of the invention, low cardinality fields (attributes) may be combined into a single field (referred to as a “combined field”) having values representing the various combinations of the original fields. In accordance with another aspect of the invention, the data values for several fields may be stored in a single value list (referred to as a “union column”). Still another aspect of the invention is to apply redundancy elimination techniques, utilizing in some cases union columns, possibly together with combined fields, in order to reduce the space needed to store the database.

Claims

1. A system for storing a plurality of tuples, each tuple comprising at least a first attribute having a first attribute value and a second attribute having a second attribute value, the system comprising:

a. a value store storing, for each of the plurality of tuples, the first attribute value and the second attribute value;

b. a first instance store identifying instances of the first attribute value and the second attribute value associated with each tuple;

c. a second instance store identifying instances of the first attribute value associated with each tuple.

2. The system of claim 1 wherein

a. the value store further stores, for each of the plurality of tuples, a key value identifying the tuple'"'"'s first attribute value and the tuple'"'"'s second attribute value and

b. the first and second instance stores further identifies instances of the key value associated with each tuple.

3. The system of claim 2 wherein, for each of the plurality of tuples, the key value is derived from the tuple'"'"'s first attribute value and the tuple'"'"'s second attribute value.

4. The system of claim 2 wherein, for each of the plurality of tuples, the first attribute value is a key value identifying the tuple'"'"'s second attribute value.

5. The system of claim 2 wherein one or more key values are each a concatenation of the first attribute value and the second attribute value.

6. The system of claim 2 wherein each of the values of the first and second attributes are associated with an index and wherein one or more key values are each a concatenation of a first index associated with the key value'"'"'s first attribute and a second index associated with the key value'"'"'s second attribute.

7. The system of claim 6 wherein the index associated with each of the values is derived from the position of the value in the value store.

8. The system of claim 6 wherein the index associated with the each of the values is a hash value.

9. The system of claim 2 wherein each key value is unique and identifies a combination of a particular first attribute value and a particular second attribute value.

10. The system of claim 1 further comprising

a. a first cardinality store storing information representing frequencies of occurrence of instances of equal value in the first instance store, wherein a particular value in the value store associated with a particular instance in the first instance store can be derived using the cardinality store;

and

b. a second cardinality store storing information representing frequencies of occurrence of instances of equal value in the second instance store, wherein a particular value in the value store associated with a particular instance in the second instance store can be derived using the cardinality store.

11. The system of claim 10 wherein

a. the value store further stores, for each of the plurality of tuples, a key value identifying the tuple'"'"'s first attribute value and the tuple'"'"'s second attribute value;

and wherein the first and second instance store further identifies instances of the key value in the value store associated with each tuple, and

b. the first cardinality store further stores information representing, for each key value, frequencies of occurrence of instances of equal value in the first instance store, wherein a particular key value in the value store associated with a particular instance of a key value in the first instance store can be derived using the cardinality store.

12. A method of storing a plurality of tuples, each tuple comprising at least a first attribute having a first attribute value and a second attribute having a second attribute value, the method comprising:

a. for each of the plurality of tuples, storing the first attribute value and the second attribute value in a value store;

b. storing, in a first instance store, pointers to the first attribute value and the second attribute value associated with each tuple; and

c. storing, in a second instance store, pointers to the first attribute value associated with each tuple.

13. The method of claim 12 further comprising:

a. for each of the plurality of tuples, storing a key value identifying the tuple'"'"'s first attribute value and the tuple'"'"'s second attribute value in the value store;

b. storing pointers to the key value in the first instance store; and

c. storing pointers to the key value in the second instance store.

14. The method of claim 13 further comprising, for each of the plurality of tuples, deriving the key value from the tuple'"'"'s first attribute value and the tuple'"'"'s second attribute value.

15. The method of claim 13 wherein, for each of the plurality of tuples, the first attribute value is a key value identifying the tuple'"'"'s second attribute value.

16. The method of claim 13 further comprising, for at least one of the plurality of tuples, deriving a key value by concatenating the first attribute value and the second attribute value.

17. The method of claim 13 further comprising associating each of the value of the first and second attributes with an index.

18. The method of claim 17 wherein associating each of the value of the first and second attributes with an index comprises:

a. associating the key value'"'"'s first attribute with a first index; and

b. associating the key value'"'"'s second attribute with a second index.

19. The method of claim 17 further comprising deriving the index from the position of the associated value in the value store.

20. The method of claim 17 further comprising computing a hash value of the value of the first and second attribute.

21. The method of claim 13, wherein each key value is unique and identifies a combination of a particular first attribute value and a particular second attribute value.

22. The method of claim 12 further comprising:

a. storing information representing frequencies of occurrence of instances of equal value in the first instance store in a first cardinality store, wherein a particular value in the value store associated with a particular instance in the first instance store can be derived using the cardinality store; and

b. storing information representing frequencies of occurrence of instances of equal value in the second instance store a second cardinality store, wherein a particular value in the value store associated with a particular instance in the second instance store can be derived using the cardinality store.

23. The method of claim 22 further comprising:

a. for each of the plurality of tuples, storing a key value identifying the tuple'"'"'s first attribute value and the tuple'"'"'s second attribute value in the value store,

b. storing, in the first and second instance stores, pointer to instances of the key value in the value store associated with each tuple, and

c. for each key value, storing, in the first cardinality store, information representing frequencies of occurrence of instances of equal value in the first instance store, wherein a particular key value in the value store associated with a particular instance of a key value in the first instance store can be derived using the cardinality store.