Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-12-01
2003-01-28
Alam, Hosain T. (Department: 2172)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000
Reexamination Certificate
active
06513041
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to computer-implemented databases and, in particular, to an efficient, ordered, reduced-space representation of multi-dimensional data.
BACKGROUND OF THE INVENTION
State of the art database management systems (DBMS's), like the underlying data files out of which and on top of which they historically grew, continue to store and manipulate data in a manner that closely mirrors the users' view of the data. Users typically think of data as a sequence of records (or “tuples”), each logically composed of a fixed number of “fields” (or “attributes”) that contain specific content about the entity described by that record. This view is naturally represented by a logical table (or “relation”) structure (referred to herein as a “record-based table”), such as a rectilinear grid, in which the rows represent records and the columns represent fields.
The long-standing existence of record-based tables and their correspondence to a conventional user view, in the absence of generally recognized drawbacks, has led to their nearly universal acceptance as the major underlying internal representation of databases. Yet record-based tables contain key structural weaknesses including high levels of unorderedness and redundancy that have traditionally been regarded as unavoidable. For example, such tables can be sorted or grouped (i.e., the contiguous positioning of identical values) on at most one criterion (based upon column values or some function of either column values or multiple column values). This limitation renders essential database functions, such as querying and updating, on all criteria other than this privileged one awkward and overly resource-intensive.
The above deficiencies inhere in the fundamental properties of the record-based table structure, in particular, the requirement that the positioning of each field be made co-linear with all other fields in the same record. This arbitrary positioning of fields in record-based table structures excludes all other arrangements. It thus obscures natural and exploitable latent data relationships that are revealed by more ordered, condensed and efficient data arrangements. Moreover, the inability of record-based tables to effectively group or sort data leads to negative characteristics of state of the art DBMS's such as unorderedness, redundancy, cumbersomeness, algorithmic inefficiencies and performance instabilities.
Database research provides palliatives for these problems, but fails to uncover and address their underlying cause (i.e., the reliance on record-based table structures). For example, the inability to represent a natural, multi-dimensional grouping within the confines of a record-based table structure has led to the creation of index-based data structures. These supplementary structures are inherently and often massively redundant, but they establish groupings and orderings that cannot be directly represented using a conventional table. Index-based structures typically grow to be overly lengthy, convoluted and are cumbersome to maintain, optimize and especially update. Examples of common indexes are b-trees, t-trees, star-indexes, and various bit maps.
Other supplementary structures developed in the prior art have different drawbacks. For example, hash tables can provide rapid querying of individual data items, but their lack of sort ordering render them unsuitable for range queries or for any other operation that requires returning data in a specific order.
The ability to maintain an ordered, non-redundant, multi-dimensional data set, using flexible sorting and/or grouping criteria, is extremely useful to database management. Sorted data makes rapid searching and updating possible via, for example, binary search algorithms and insertion sorts. Grouped data enables condensation that reduces space requirements and further increases the speed of, for example, searching and updating.
A system of data storage in which most or all columns of a data table can be stored in grouped and/or sorted order is thus extremely desirable. Previous studies have investigated “fully inverted databases,” which index each column through traditional methods, preserving all the inadequacies of records and indexes. Additionally, the bloated storage requirements necessary to accommodate complete indexing tend to make fully inverted databases impractical, especially, but not only, in main memory databases.
SUMMARY OF THE INVENTION
It is therefore an object of the present invention to provide a fully or partially ordered (e.g., grouped and/or sorted) database without the deficiencies characteristic of the prior art, as mentioned above.
Briefly, instead of structuring a database as a table in which each row is a record and each column contains the fields in the record, as in earlier databases, the present invention permutes or otherwise modifies the columns to provide an advantage in, for example, space usage and/or speed of access, such that the rows no longer necessarily correspond to individual records. For example, one such modification is to condense the column by eliminating redundant values (which reduces memory usage); another is sort-ordering the column, ensuring that value groups will always appear in some particular order (which can greatly reduce the time required to search a column for a particular value); still another is to both condense and sort a column. Other permutations and modifications with other advantages are also possible. The table of permuted/modified values is referred to herein as the “value table.”
Logically, though not necessarily physically, separate data structures provide the information needed to reconstruct the “records” in the database. In particular, they provide “instance” and “connectivity” information, where instance information identifies the instances of each value in the field that is in a record and connectivity information associates each instance with a specific instance of a value in at least one other field.
In one embodiment of the invention, both the instance and connectivity information is provided in a table, referred to herein as the “instance table.” Each column in the instance table corresponds to an attribute of the records in the database and is associated with a column in the value table that contains the values for that attribute (and possibly other attributes). Each cell (row/column location) in the instance table has a position (in one embodiment of the invention, its row number) and an instance value (the contents of the cell). An associated cell in the associated column of the value table is derived from each instance cell's position. Also, an associated instance cell in another column of the instance table that belongs to the same record is derived from each instance cell's instance value. Thus, in this embodiment, an instance cell's position identifies the value which the cell is an instance of and an instance cell's contents provides the connectivity information associating the instance with another instance cell in another field. A record can then be reconstructed starting at a cell in the instance table by deriving, from the cell's position, the associated value cell in the value table and, from the cell's instance value, the position of the associated instance cell, and repeating this process at the associated instance cell and so forth, with a last cell in the chain providing, in one embodiment, the corresponding position of the starting cell.
If a column of the value table is sorted but not condensed, the value table column and the associated column in the instance table has, in one embodiment of the invention, the same number of rows. An instance cell's associated value cell is, in this one embodiment, the value cell in the associated value table column having the same row number as the instance cell. An instance cell's associated instance cell (i.e., cell in another column of the instance table belonging to the same record) is the cell in a specified column having the r
Alam Hosain T.
Alam Shahid
Pennie & Edmonds LLP
Required Technologies, Inc.
LandOfFree
Value-instance-connectivity computer-implemented database does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Value-instance-connectivity computer-implemented database, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Value-instance-connectivity computer-implemented database will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3058765