EP0124097A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Method for storing and retrieving data in a data base
Assignee: Wang Laboratories Inc
•
Filing: 1984-04-26
•
Granted: —
•
Expires: 2004-04-26
Abstract
Abstract A method for fast storing large amounts of data in data base and for fast retrieving data in that base using inverted lists, without substantially increasing the storage space over that of the original data base and without sacrificing on data amenable of fast searching, is disclosed. The method allows for very efficient storage of the inverted lists. The inverted lists require much less storage space than the original data base and allows users to maintain inverted lists for all fields in the data base. The data base comprises a self-descriptive index key format having variable length data fields so that the data base system manipulation is independent of the type and arrangement of the data being stored and retrieved. The data is characterized by three index variables which represent the data table, the record in that table, and a particular field within that record. Each table is composed of data imbedded in the B-tree index structure of the data base. In order to access records using the field variables, the data base edditionally includes an inverted B-tree index logically related to the original index. The operation of the index may be enhanced by the use of date compression and the use of a sparse array bit map to represent the record associated with each filed.
Inventors
- 👤 Amnon Waisman
- 👤 Andrew Mark Weiss
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-10-29 23:36
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/90; G06F16/901; G06F16/9017; G06F16/902; G06F16/20; G06F16/22; G06F16/2228; G06F16/2246; G06F16/30; G06F16/31; G06F16/316; G06F16/319; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933
Claims Analysis
Total Claims: 9
Claim 1
Independent Claim
297 words
A method of storing and retrieving data in a data base comprising the steps of: providing a plurality of data tables, each data table including a plurality of records; identifying each data table by assigning a unique record index value to each data table; assigning each record within a data table a record serial number unique to that record within the data table; dividing the record serial numbers of each data table into ranges, each range including a predetermined number of record serial numbers, and each range being assigned a consecutive range value; dividing the records in each data table into a plurality of fields wherein each field within a data table is identified by a field index value and wherein each field within a data table contains data values of a selected type; providing a plurality of inverted list tables, each inverted list table being associated with a respective one of the data tables, including the steps of: creating a plurality of keys, each key being associated with a particular field and representing the occurance of a particular data value in that field; providing one or more pointers associated with each key and representative of the record serial numbers of the records which contain the data value represented by the associated key, each pointer including a range value and a sparse array bit map; and identifying the records in a selected data table having a specified data value stored in a selected field, including the steps of: determining the key which is associated with the selected field and which represents the specified data value; searching the inverted list table associated with the selected data table to find the determined key; and retrieving the data in the records represented by the pointers associated with the determined key.
Claim 2
Independent Claim
297 words
A method of storing and retrieving data in a data base comprising the steps of: providing a plurality of data tables, each data table including a plurality of records; identifying each data table by assigning a unique record index value to each data table; assigning each record within a data table a record serial number unique to that record within the data table; dividing the record serial numbers of each data table into ranges, each range including a predetermined number of record serial numbers, and each range being assigned a consecutive range value; dividing the records in each data table into a plurality of fields wherein each field within a data table is identified by a field index value and wherein each field within a data table contains data values of a selected type; providing a plurality of inverted list tables, each inverted list table being associated with a respective one of the data tables, including the steps of: creating a plurality of keys, each key being associated with a particular field and representing the occurance of a particular data value in that field; providing one or more pointers associated with each key and representative of the record serial numbers of the records which contain the data value represented by the associated key, each pointer including a range value and a sparse array bit map; and identifying the records in a selected data table having a specified data value stored in a selected field, including the steps of: determining the key which is associated with the selected field and which represents the specified data value; searching the inverted list table associated with the selected data table to find the determined key; and retrieving the data in the records represented by the pointers associated with the determined key.
Claim 3
Dependent Claim
212 words
The method of claim 1 wherein the step of providing a sparse array bit map includes the steps of: determining a plurality of bottom level bytes, each byte having an equal plurality of bottom level bits, wherein the number of bottom level bits in said bottom level bytes is equal to the number of record serial numbers in each range and wherein each bottom level bit is associated with a respective one of said record serial numbers in each range; encoding the presence of each record serial number within a range by setting the bottom level bit which is associated with each such record serial number; determining a plurality of upper level bytes, including a top level byte and a plurality of bytes on one or more intermediate levels such that the number of bits in the bytes in each level is equal to the number of bytes in the next lower level, each bit in each upper level byte being associated with a respective one of the bytes on the next lower level; setting the bits in the upper level bytes whose associated byte in the next lower level contains at least one set bit; and storing the bottom level and upper level bytes which contain one or more set bytes.
Claim 4
Dependent Claim
55 words
The method of claim 2 wherein the step of determining a plurality of upper level bytes includes the steps of: providing a top level byte having n bits; and providing one intermediate level having n bytes including n 2 bits, whereby n 3 record serial numbers within a range are represented by the sparse array.
Claim 5
Dependent Claim
39 words
The method of claim 2 wherein the step of providing a plurality of upper level bytes includes the step of providing a top level byte having eight bits and one intermediate level having eight bytes of eight bits each.
Claim 6
Independent Claim
459 words
A method of storing and retrieving data in a data base comprising the steps of: providing a plurality of data tables, each data table including a plurality of records; identifying each data table by assigning a unique record index variable to each data table; assigning each record within a data table a record serial number unique to that record within the data table; dividing the record serial numbers of each data table into ranges, each range including a predetermined number of record serial numbers, and each range being assigned a consecutive range value; dividing the records in each data table into a plurality of fields wherein each field within a data table is identified by a field index variable and wherein each field within a data table contains data values of a selected type; providing a plurality of inverted list tables equal in number to the number of data tables, each inverted list table being associated with a respective one of the data tables, each inverted list table including the steps of: creating a plurality of keys, each key being associated with a particular field and representing the occurance of a particular data value in the associated field; and providing one or more pointers associated with each key and representative of the record serial numbers of the records which contain the data value represented by the associated key, each pointer including a range value representative of the occurrence in the inverted list table of one or more record serial numbers within the range and a sparse array bit map associated with each range value and representative of which record serial numbers within the associated range occur in the inverted list table; providing within a first data table from among said plurality of data tables a designated field representative of a relationship between each of the records in the first data table and selected records from a second data table; and storing said relationship in the data base by storing in the designated field data representative of the record serial numbers of said selected records from the second data table, said representative data including the range values of the record serial numbers of the selected records and a sparse array bit map associated with each range value and representative of the record serial numbers of the selected records; and identifying the records in a selected data table having a specified data value stored in a selected field, including the steps of: determining the key which is associated with the selected field and which represents the specified data value; searching the inverted list table associated with the selected data table to find the determined key; and retrieving the data in the records represented by the pointers associated with the determined key.
Claim 7
Independent Claim
459 words
A method of storing and retrieving data in a data base comprising the steps of: providing a plurality of data tables, each data table including a plurality of records; identifying each data table by assigning a unique record index variable to each data table; assigning each record within a data table a record serial number unique to that record within the data table; dividing the record serial numbers of each data table into ranges, each range including a predetermined number of record serial numbers, and each range being assigned a consecutive range value; dividing the records in each data table into a plurality of fields wherein each field within a data table is identified by a field index variable and wherein each field within a data table contains data values of a selected type; providing a plurality of inverted list tables equal in number to the number of data tables, each inverted list table being associated with a respective one of the data tables, each inverted list table including the steps of: creating a plurality of keys, each key being associated with a particular field and representing the occurance of a particular data value in the associated field; and providing one or more pointers associated with each key and representative of the record serial numbers of the records which contain the data value represented by the associated key, each pointer including a range value representative of the occurrence in the inverted list table of one or more record serial numbers within the range and a sparse array bit map associated with each range value and representative of which record serial numbers within the associated range occur in the inverted list table; providing within a first data table from among said plurality of data tables a designated field representative of a relationship between each of the records in the first data table and selected records from a second data table; and storing said relationship in the data base by storing in the designated field data representative of the record serial numbers of said selected records from the second data table, said representative data including the range values of the record serial numbers of the selected records and a sparse array bit map associated with each range value and representative of the record serial numbers of the selected records; and identifying the records in a selected data table having a specified data value stored in a selected field, including the steps of: determining the key which is associated with the selected field and which represents the specified data value; searching the inverted list table associated with the selected data table to find the determined key; and retrieving the data in the records represented by the pointers associated with the determined key.
Claim 8
Independent Claim
106 words
A method according to any of claims 1 to 5, comprising the steps of: generating a B-tree index having a plurality of levels and storing the data values in the data base within the B-tree as entries in the bottom level of the B-tree; and wherein each data entry includes a key part and an associated data value, the key part including the record identifier value, the record serial number, and the field index value of the associated data value; and storing each data value in the data base immediately following the associated key, whereby each key provides a logical address of its associated data value.
Claim 9
Independent Claim
97 words
A method according to any of claims 1 to 6 wherein inverted lists of record serial numbers are stored in the data base, including the steps of: dividing the list of possible record serial numbers into ranges having a predetermined number of record serial numbers, each range being assigned a consecutive range value; selecting the range values for each range which contains at least one record serial number which occurs in the inverted list; and encoding the position in each selected range of each record serial number in the inverted list by means of a sparse array.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.