METHOD OF STORING AND RETRIEVING RECORDS

• US 3,568,155 A
• Filed: 04/10/1967
• Issued: 03/02/1971
• Est. Priority Date: 04/10/1967
• Status: Expired due to Term

• Current Assignee: Chacko T. Abraham, Dwijendra K. Ray-Chaudhuri, Sakti P. Ghosh
• Original Assignee: Chacko T. Abraham, Dwijendra K. Ray-Chaudhuri, Sakti P. Ghosh
• Inventors: Abraham, Chacko T., Ghosh, Sakti P., Ray-chaudhuri, Dwijendra K.
• Application Number:
  US04/629,485
• Time in Patent Office: 1,422 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9014 hash tables
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing

Abstract

The method is embodied in a data processing apparatus in which a plurality of records, each having a number of different attributes, are stored in the memory file of the machine and the file is then interrogated to retrieve those records which include a particular combination of attributes. The records are first prepared in machine readable form and applied as an input to the machine. The machine circuitry is controlled to store each input record in the memory file of the machine. The attributes for each record are analyzed in predetermined combinations of two or more attributes, and the address for each stored record is stored in one or more buckets in the memory file according to the combination(s) of attributes in each record. After the records are stored, the file is interrogated by applying input queries which specify certain combinations of attributes. From each input query, the machine circuitry is controlled to locate the bucket in which the addresses of all records which satisfy the query are stored. These addresses are then read out and used to retrieve the records themselves from the record file. In order to minimize the redundancy of storage of the addresses of the records, the addresses are grouped in buckets in the memory file in predetermined unique combinations of k+1 (e.g. 4) attributes, where k (e.g. 3) is the number of attributes in the queries for which the system is principally designed. In each such bucket the record addresses are arranged in k+2 (e.g. 5) subbuckets. The addresses for all records including all of the k+1 (e.g. 4) attributes are stored in one subbucket and the remaining addresses in that bucket are stored in the remaining k+1 (e.g. 4) subbuckets according to which of the combinations of k (e.g. 3) only of the k+1 (e.g. 4) attributes are present in the record identified by this particular address.

Claims

1. The method of operating a data processing machine to store a plurality of records each having a number of attributes in a file from which the records can be retrieved in response to queries specifying particular combinations of said attributes, comprising the steps of:

a. storing the records in an addressable memory file of the machine;

b. storing the addresses of the stored records in a plurality of buckets at different locations in said memory file with each of said buckets having stored therein the aDdresses for all those records that include at least one particular combination of at least two of said attributes; and

c. retrieving records from said file by applying queries specifying particular combinations of attributes to circuitry within said machine which specifies the locations in the memory file of the addresses of those records which satisfy the particular queried combinations;

wherein said queries specify particular combinations of k attributes, where k >

OR = 2, and at least some of the buckets include the addresses for all of the records that include k attributes out of a unique set of k+1 attributes, and each address is stored only once in each such bucket, wherein each such bucket includes k+2 subbuckets and with the addresses of all records which include all of the k+1 attributes for the bucket being stored in one subbucket and all of the addresses for the remaining records that include one of the k+1 unique combinations of k only of the k+1 attributes for that bucket being stored in a corresponding one of the remaining subbuckets, and wherein, when one of the queries applied to said circuitry in said machine specifies a particular combination of k attributes of the unique set of k+1 attributes for one of such buckets, the method includes the step of reading out both the one subbucket which stores the addresses of all of the records that include the unique set of k+1 attributes for that bucket and the one of the remaining sub-buckets which stores the addresses of the records that include the particular combination of k attributes specified by the query.

2. The method of claim 1 including the step of controlling said machine to first encode each of the particular attributes, which are combined into the query, into signals representing a multiorder binary value, and applying said signals representative of said encoded binary values to circuitry within the machine which uniquely specifies the locations in the memory file of the addresses of those records which satisfy the particular queried combination.

3. The method of claim 2 wherein each of the k multiorder binary values encoded by the machine for each query correspond to the coordinates for a point in a particular finite geometry, and the k points corresponding to the query satisfies at least one linear equation for that geometry.

4. The method of claim 2 wherein the k multiorder binary values correspond to at least certain of said queries represent k points on a single line in said geometry.

5. The method of claim 4 wherein the single line represented by the k points in said geometry includes a further point, said further point corresponding to a different multiorder binary value representing a different attribute, the attributes for said k points and said further point corresponding to the unique set of k+1 points for one of said buckets.

6. The method of claim 3 wherein the linear equation satisfied by the k multiorder binary values corresponding to certain queries is an equation for a plane in said finite geometry.

7. A method of arranging a group of records, each having attributes, into the memory file of a data processing machine from which all records identified by any unique one of a plurality of l /(l-k) (k) possible combinations of k of the l attributes can be retrieved in response to a query identifying one of the unique combinations of k attributes, where l >

or = k >

or = 2 said method comprising the steps of;

a. storing the records in an addressable memory file of the machine;

b. and storing the addresses for the stored records in a group of buckets in the memory file of the machine with each of a plurality of said buckets having stored therein thE addresses for all records including combinations of at least k attributes of a unique set of k+1 of the l attributes, and no set of k of the attributes being common to any one of the unique sets of k+1 of the l attributes for each bucket;

c. including the step of arranging the addresses within each bucket in said plurality into k+2 subbuckets, with the addresses of all records which include all of the k+1 attributes for the bucket being stored in one subbucket, and all of the addresses for the remaining records that include one of the k+1 unique combinations of k only of the k+1 attributes for that bucket being stored in a corresponding one of the remaining subbuckets.

8. The method of claim 7 wherein l 7, k 2, and the addresses for said records are stored in seven buckets, each of which includes four subbuckets.

9. The method of claim 7 wherein l 8, k 3, and the addresses for all of said records are stored in 14 buckets each of which includes five subbuckets.