Value-instance-connectivity computer-implemented database

• US 6,009,432 A
• Filed: 07/08/1998
• Issued: 12/28/1999
• Est. Priority Date: 07/08/1998
• Status: Expired due to Fees

• Current Assignee: Required Technologies Incorporated
• Original Assignee: Required Technologies Incorporated
• Inventors: Tarin, Stephen A.
• Primary Examiner(s): Choules, Jack M.
• Assistant Examiner(s): ALAM, SHAHID AL
• Application Number:
  US09/112,078
• Time in Patent Office: 538 Days
• Field of Search: 707/2, 707/3, 707/4, 707/10, 707/100, 707/102, 707/103
• US Class Current: 1/1
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure

Abstract

A computer-implemented database and method providing an efficient, ordered reduced space representation of multi-dimensional data. The data values for each attribute is stored in a manner that provides an advantage in, for example, space usage and/or speed of access, such as in sort order and/or condensed form. 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.

Claims

1. A computer-implemented database comprising:

a. one or more sets of data value elements, each data value element having a position in one of the one or more sets of data value elements and a data value;

b. at least a first and a second set of instance elements, each instance element having a position in its respective set of instance elements and an instance value, and each set of instance elements corresponding to an attribute,

c. wherein for a first instance element in the first set of instance elements

(i) a first associated data value element in the one or more sets of data value elements is derived from the first instance element'"'"'s position, and

(ii) a single second instance element in the second set of instance elements, whose position in the second set of instance elements is different from the first instance element'"'"'s position in the first set of instance elements, is derived from the first instance element'"'"'s instance value, and

d. further wherein

(i) a second associated data value element in the one or more sets of data value elements is associated with the second instance element and at least one other element in the second set of instance elements, and

(ii) the first instance element can be derived from the second instance element independent of the first instance element'"'"'s value.

2. The database of claim 1, wherein the second instance element is a next element.

3. The database of claim 1, wherein one of the one or more sets of data value elements is sorted.

4. The database of claim 1, wherein one of the one or more sets of data value elements is condensed such that the set comprises unique data values.

5. The database of claim 1, wherein one of the one or more sets of data values is condensed, such that the set comprises unique data values, and sorted.

6. The database of claim 5 wherein the first associated data value element is in the condensed set of data value elements and further comprising:

a displacement set of displacement elements associated with the condensed set of data value elements, each element in the displacement set having a position in the displacement set and a displacement value, wherein the first associated data value element is further derived from the displacement set.

7. The database of claim 6 wherein each element in the displacement set has a single associated element in the condensed set of data value elements derived from its position.

8. The database of claim 6 wherein each element in the displacement set is associated with a range of elements in the first instance set, each element in the range being associated with the same data value element.

9. The database of claim 8 wherein the displacement value of an element in the displacement set specifies a first position in its associated range of positions.

10. The database of claim 8 wherein the displacement value of an element in the displacement set specifies a last position in its associated range of positions.

11. The database of claim 8 wherein the displacement value of an element in the displacement set specifies the number of positions in its associated range of positions.

12. The database of claim 1, wherein all data value elements having equal data values have contiguous positions in one of the one or more sets of data value elements.

13. The database of claim 1 wherein one of the one or more sets of data value elements is an algorithm that generates a sequence of unique values and, for each data value in the sequence, a position of the data value in the one set of data value elements is given by the position the value would have in the sequence if all data values were generated by the algorithm.

14. The database of claim 1 wherein the second associated data value element is in a condensed set of data value elements and further comprising:

a. a displacement set of displacement elements associated with the condensed set of data value elements, each displacement element having a position in the displacement set and a displacement value,

b. an occurrence set of occurrence elements associated with the first set of instance elements, each occurrence element having a position in the occurrence set and an occurrence value, and

c. wherein

(i) the second instance element is further derived from the displacement set and the occurrence set, and

(ii) the second associated data value element is derived from the first instance element'"'"'s instance value.

15. The database of claim 14 wherein the second instance element is derived from a displacement set element whose position is given by the first instance element'"'"'s instance value and an occurrence set element whose position is given by the first instance element'"'"'s position.

16. The database of claim 14 wherein the second instance element is derived from summing the value of a displacement set element whose position is given by the first instance element'"'"'s instance value and the value of an occurrence list element whose position is given by the first instance element'"'"'s position.

17. The database of claim 1 wherein a group of associated instance elements comprising the second instance element and all associated instance elements derived from the second instance element'"'"'s instance value includes the first instance element.

18. The database of claim 17 wherein each associated instance elements in the group of associated elements that is derived independently of the first instance element is unique.

19. A computer-implemented database comprising:

a. one or more sets of data value elements, each data value element having a position in one of the one or more sets of data value elements and a data value;

b. at least a first and a second set of instance elements, each instance element having a position in its respective set of instance elements and an instance value, and each set of instance elements corresponding to an attribute,

c. wherein for a first instance element in the first set of instance elements

(i) a first associated data value element in the one or more sets of data value elements, derived from the first instance element'"'"'s position, is associated with the first instance element and at least one other element in the first set of instance elements, and

(ii) a single second instance element in the second set of instance elements, whose position in the second set of instance elements is different from the first instance element'"'"'s position in the first set of instance elements, is derived from the first instance element'"'"'s instance value, and

d. further wherein

(i) a second associated data value element in the one or more sets of data value elements is associated with the second instance element and at least one other element in the second set of instance elements, and

(ii) the first instance element can be derived from the second instance element independent of the first instance element'"'"'s value.

20. A computer-implemented database comprising:

a. two or more attribute sets comprising data values and instance elements, each instance element associated with one data value and having a position and contents;

b. connectivity information uniquely associating each instance element with a specific instance element in at least one other attribute set;

c. wherein connectivity information for a first instance element associated with a first data value in a first attribute set associates the first instance element with a second instance element that is a specific one of a plurality of instance elements associated with a second data value in a second attribute set and

d. wherein the position of the second instance element is independent of the position of the first instance element.

21. The database of claim 20 wherein the connectivity information for the first instance element comprises the contents of the first instance element.

22. The database of claim 21 wherein each data value has a position and wherein the data values in the second attribute set are unique and sorted.

23. The database of claim 22 wherein the second attribute set further comprises displacement information that identifies the instance elements in the second attribute set that are associated with the second data value.

24. The database of claim 23 wherein the first attribute set further comprises occurrence information identifying the occurrence number of the second instance element among instances of the second data value in the second attribute set and wherein the connectivity information for the first instance element further comprises the occurrence information for the first attribute set and the displacement information for the second attribute set.