Value-instance-connectivity computer-implemented database field of the invention

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.

1 . A system for storing and retrieving tuples comprising: a collection of a number of instances corresponding to a value of a first attribute; a cardinality element corresponding to the number of instances; wherein the cardinality element is updated each time the number of instances changes and wherein at least one instance indicates at least one other instance corresponding to a value of a second attribute and the second attribute is different from the first attribute. 
   
   
       2 . A system for storing and retrieving tuples comprising: a collection of a number of instances corresponding to a value of a first attribute; a cardinality element corresponding to the number of instances; wherein the value can be derived from the cardinality element and wherein at least one instance indicates at least one other instance corresponding to a value of a second attribute and the second attribute is different from the first attribute. 
   
   
       3 . 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:
 for at least two tuples having identical first attribute values and identical second attribute values, a single instance element that identifies the first attribute value and the second attribute value, and a cardinality element comprising information regarding the number of tuples having the identical first and second attribute values.   
   
   
       4 . The system of  claim 3  wherein the instance element comprises the cardinality element. 
   
   
       5 . 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 the values of the first and second attributes of the plurality tuples;   b. an instance store identifying instances of the values in the value store associated with each tuple;   c. a connectivity store storing information regarding relationships among instances; and   d. a cardinality store storing information representing frequencies of occurrence of instances of equal value, wherein a particular value in the value store associated with a particular instance in the instance store is derived using the cardinality store.   
   
   
       6 . The system of  claim 5  wherein the instance store and the connectivity store are not distinct.