Value-instance-connectivity computer-implemented database

• US 7,076,507 B1
• Filed: 12/23/2002
• Issued: 07/11/2006
• 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): ALAM, SHAHID AL
• Application Number:
  US10/329,296
• Time in Patent Office: 1,296 Days
• Field of Search: 707/2, 707/3, 707/102, 707/103.R, 707/200, 707/206, 707/5, 707/10, 707/100, 709/201, 709/203, 711/118
• US Class Current: 1/1
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

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. Low cardinality fields may be combined into a single field having values representing the various combinations of the original fields. In one embodiment, the “combined field” contains only instantiated combinations. In another embodiment, the combined field contains all values in the Cartesian product of the original fields, preferably in nested sort order. In yet another embodiment, the original fields are padded with dummy values so that their cardinalities are a power of two, causing each subfield in the combined field to fall on a bit boundary. In still another embodiment, containerization techniques are used to reduce the space required for representing the complete set of all possible values in the Cartesian product of the original fields.

Claims

1. A system for storing a first 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, and a second plurality of tuples, each tuple comprising at least a first attribute, that is the same as the first attribute of the first plurality of tuples, having a first attribute value and a second attribute, different than the second attribute of the first plurality of tuples, having a second attribute value, the system comprising:

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

a first instance store identifying instances of the first attribute value associated with each tuple in the first plurality of tuples;

a second instance store identifying instances of the first attribute value associated with each tuple in the second plurality of tuples;

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

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

2. The system of claim 1 wherein at least one of the first and second cardinality stores contains information indicating that there are zero occurrences of an instance of at least one value.

3. A method for storing a first 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, and a second plurality of tuples, each tuple comprising at least a first attribute, that is the same as the first attribute of the first plurality of tuples, having a first attribute value and a second attribute, different than the second attribute of the first plurality of tuples, having a second attribute value, the method comprising the steps of:

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

storing in a first instance store information identifying instances of the first attribute value associated with each tuple in the first plurality of tuples;

storing in a second instance store information identifying instances of the first attribute value associated with each tuple in the second plurality of tuples;

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

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

4. The method of claim 3 wherein at least one of the first and second cardinality stores contains information indicating that there are zero occurrences of an instance of at least one value.