METHOD FOR INFORMATION STORAGE AND RETRIEVAL

• US 3,670,310 A
• Filed: 09/16/1970
• Issued: 06/13/1972
• Est. Priority Date: 09/16/1970
• Status: Expired due to Term

• Current Assignee: Bansi U. Bharwani, Harry Kaplowitz
• Original Assignee: Bansi U. Bharwani, Harry Kaplowitz
• Inventors: Bharwani, Bansi U., Kaplowitz, Harry
• Primary Examiner(s): Henon, Paul J.
• Assistant Examiner(s): Nusbaum, Mark Edward
• Application Number:
  US05/072,953
• Time in Patent Office: 636 Days
• Field of Search: 340/172.5 235/157
• US Class Current: 1/1
• CPC Class Codes: G06F 16/902 using more than one table in sequence, i.e. systems with three or more layers
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

A data storage and retrieval system based upon a three file concept is disclosed. The computer oriented system comprises at least an index, search, and data file. Access to the file structure is through the index file wherein a plurality of keywords are stored. Each keyword, either individually or in combination, is used to identify one or more data records stored in the data file. A plurality of paths through the search file, called chains, whose links comprise links addresses, provide a connection between the index and data files. Keywords are automatically generated from field values contained in data records. Updating of these field values initiates the automatic updating of keywords in the index and search files. In addition, to conserve file space, the allocation of space for keywords in the index file is made adjustable. Provision is made for marking items as deleted and for bypassing deleted items during searching. Provision is also made for the addition of a single item as a data record without using the loading procedure used to initially load the data base.

Claims

1. In a computer controlled information storage and retrieval system of the type including index, search and data files, a method for updating a data record comprising the steps of:

a. providiNg a data file storing data records identified by keywords, said data records including field values, b. providing an index file storing said keywords, each keyword being stored in an index record, each index record also containing the keyword in coded form, an address pointer and a frequency count of the number of search records which contain the keyword, said index file further including a trailer record containing the next available keyword code, c. providing a search file storing groups of keywords, each group termed a search record, there being a one-to-one correspondence between search records and data records in the data file, an index record being logically connected to said search file by an address pointer, common keywords in the search file being logically connected by link addresses, d. changing at least one file value in a data record, e. determining if the changed field value is also a keyword, and f. automatically updating the search and index files to reflect the changed field value if said field value is a keyword.

2. The computer controlled information storage and retrieval system of claim 1 wherein said step of determining includes providing table means for storing fields and an indication for each field stored of its status as a keyword and scanning said table to determine if a field is a keyword.

3. The computer controlled information storage and retrieval system of claim 2 wherein said step of automatically updating includes:

adding a new keyword to the search record corresponding to the data record being changed, modifying the chain of link addresses associated with the new keyword to include said search record, deleting the keyword in said search record corresponding to the field value being deleted, and modifying the chain of link addresses associated with said deleted keyword to delete said search record address from the deleted keyword associated chain of link addresses.

4. In the computer controlled information storage and retrieval system of claim 1 said step automatically updating includes the step of removing a keyword from a selected search record comprising the steps of:

a. scanning said index file for said keyword;

b. scanning said search file for said selected search record;

c. writing the selected index record corresponding to the keyword to be removed in core storage;

d. writing the selected search record in core storage;

e. extracting the link address in said selected search record corresponding to the keyword to be removed and storing it in core storage;

f. bypassing said selected search record by inserting the link address corresponding to the keyword to be removed into the search record whose link address, corresponding to the keyword to be removed, points to said selected search record;

g. decrementing the frequency count in the selected index record by one;

h. comparing the frequency count to zero;

i. rewriting the selected index record in the index file if the frequency count is other than zero;

j. removing said selected keyword from said selected search record; and

k. rewriting said selected search record in said search file.

5. The method of claim 4 wherein the step of bypassing said selected search record includes the step of comparing the address of said selected search record with the address pointer associated with said selected index record to determine if they are equal.

6. The method of claim 5 when said step of comparing said address pointer with said address of said selected search record indicates that the address of said selected search record is equal to the address pointer, further comprising the step of:

changing said address pointer to indicate the address of said selected search record.

7. The method of claim 5, when said step of comparing said address pointer with said address of said selected search record indicates that the address represented by said selected search record is not equal to Said address pointer, further comprising the steps of:

a. reading each search record specified by the link addresses associated with the selected keyword;

b. comparing the selected keyword associated link addresses with the selected search record address to determine equality each time a search record is read;

c. writing the search record which contains the link address corresponding to the selected search record in core storage;

d. rewriting the link address to correspond to said extracted link address, to update the search record; and

e. rewriting the updated search record in the search file.

8. In the computer controlled information storage and retrieval system of claim 1 said step of automatically updating includes the step of adding a selected keyword to a selected search record when said keyword has been previously stored in said index file comprising the steps of:

a. scanning said index file for said selected keyword;

b. reading out and storing in core storage said selected keyword index record;

c. extracting the address pointer from said read out index record and storing it in core storage; and

d. updating said search file and index file to incorporate said selected keyword in said selected search file and to incorporate said selected search record in a search on said selected keyword.

9. The method of claim 8 wherein said step of updating includes the step of comparing the address of said selected search record with said address pointer to determine which indicates a higher search file address.

10. The method of claim 9, when said selected search record address is higher than the address indicated by said address pointer, further comprising the steps of:

a. reading out and storing in core storage said selected search record;

b. writing said selected keyword in said selected search record;

c. writing a link address corresponding to the selected keyword and equal to said address pointer in said selected search record;

d. rewriting said selected search record in the search file;

e. deleting said address pointer from said selected index record;

f. rewriting said address pointer setting it equal to the address of said selected search record; and

g. rewriting said selected index record in the index file.

11. The method of claim 9, when said selected search record address is not higher than the address indicated by said address pointer, further comprising the steps of:

a. reading each search record specified by the link addresses associated with the selected keyword;

b. comparing, each time a search record is read, the selected keyword associated link address with the selected search record address to determine which indicates a higher search file address;

c. writing said selected search record in core storage when the first search record containing a selected keyword associated link address lower than the address of said selected search record is found;

d. writing said selected keyword in said selected search record;

e. writing a selected keyword associated link address equal to the link address in said first search record in said selected search record;

f. rewriting said selected search record in the search file;

g. writing said first search record in core storage;

h. deleting from said first search record said selected keyword associated link address;

i. writing a selected keyword associated link address equal to the address of said selected search record in said first search record; and

j. rewriting said first search record in the search file.

12. In the computer controlled information storage and retrieval system of claim 1 said step of automatically updating includes the step of adding a selected keyword to a selected search record when said keyword has not been previously stored in the index file comprising the steps of:

a. reading said trailer record to determine the next sequential code to be assigned a newly Entered keyword;

b. writing said keyword and said next code in core storage;

c. adding an address pointer to said keyword in core storage corresponding to the address of said selected search record to form an index record;

d. writing said selected search record in core storage;

e. writing said next code in said selected search record;

f. writing a selected keyword associated link address of zero in said selected search record;

g. writing said selected search record in the search file; and

h. writing said index record in the index file.

13. In a computer controlled information storage and retrieval system of the type including a data file for storing data items, an index file for storing keywords which identify the data items and a search file for storing groups of keywords, each group being termed a search record and corresponding to only one data record, a method for updating the system comprising:

a. adding a single data record to said data file, b. writing the keywords associated with said added data record in core storage, c. writing in core storage, for each keyword, its link address, d. writing the keywords and their link addresses on the search file to form a search record, e. writing in core storage each keyword in the new search record not previously stored in the index file, and f. writing said keywords not previously stored in said index file on said index file.

14. In a computer controlled information storage and retrieval system of the type including data, search and index files, a method for adding a single data record to the data file while updating the search and index files to reflect the added data record, comprising:

a. providing a data file storing data records identified by keywords, b. providing an index file storing keywords, each keyword being stored in an index record, each index record also comprising its keyword in coded form, said index file further including a trailer record indicating a next available code assignable to a keyword. c. providing a search file storing groups of coded keywords, said groups of keywords termed search records, there being a one-to-one correspondence between the search records and data records, each of said index records containing an address pointer to logically connect said each index record to one search record containing the keyword defined by the index record, common keywords in the search file being logically connected by a link address, d. writing said single data record in core storage, e. extracting keywords from said data item, f. writing said data record in the data file, g. writing a search record corresponding to said added data record in core storage and updating the index file to reflect the keywords in the keywords in said corresponding search record, and h. writing said corresponding search record in said file.

15. The method of claim 14 wherein said step of writing said corresponding search record includes the step of scanning the index file for said extracted keywords to determine if all extracted keywords are in the index file.

16. The method of claim 15, when at least one of the extracted keywords is not in the indexed file, the step of writing the search record in core storage comprising, for each keyword not in the index file, the further steps of:

a. reading said trailer record to determine the next available code;

b. assigning said code in core storage to the extracted keyword not in the index file;

c. assigning in core storage an address pointer indicating the address of said corresponding search record to said extracted keyword not in the index file;

d. updating said trailer record to indicate the next available code;

e. writing said code for said keyword in said corresponding search record;

f. writing a link address corresponding to said extracted keyword not in the index file equal to zero in said corresponding search record;

g. rewritIng said corresponding search record in said search file; and

h. writing said extracted keyword, its code and address pointer into the index file.

17. The method of claim 15, when at least one of said extracted keywords is in said index file, the step of writing the search record in core, comprising for each extracted keyword in said index file the further steps of:

a. reading the index file for the index record corresponding to said each extracted keyword in the index file;

b. determining the code and address pointer corresponding to said each extracted keyword;

c assigning in core storage said corresponding code to said each extracted keyword;

d. assigning in core storage said corresponding address pointer to said each extracted keyword;

e. writing said corresponding index record in core storage;

f. deleting the address pointer in said corresponding index record;

g. inserting an address pointer corresponding to the address of said corresponding search record in said corresponding index record; and

h. writing said extracted keyword, its code and address pointer into the index file.

18. In a computer controlled information storage and retrieval system of the type comprising three files termed the index, search and data files, said index file containing a plurality of keywords, said search file containing a plurality of search records, each comprising a group of keywords in coded form, and said data file containing a plurality of data records, said data records including field values, there being a one-to-one correspondence between the data records and the search file records, a method for deriving keywords directly from data field values in said data records comprising the steps of:

a. building a table in core storage containing all fields used in the data records;

b. adding a key flag to each field which is to be a keyword to denote that the field value in each data record corresponding to the field is to be a keyword;

c. constructing a data record in core storage;

d. scanning said table for all field values which are to be made keywords; and

e. extracting from the data record those field values to be made keywords.

19. The method of claim 18 further comprising the steps of:

a. storing said extracted keywords in core storage;

b. assigning to each keyword the data file and search file addresses of said item which said keyword is used to at least partially identify;

c. assigning a code to each keyword; and

d. writing each keyword along with its code and its highest search file address into said index file.

20. In an information storage and retrieval system comprising an index, search and data file said index file containing a plurality of keywords, each of said keywords containing an address pointer to an address in said search file, said search file containing said plurality of keywords grouped to form unique search records, each keyword in said group of keywords containing a link address of another search record containing the same keyword and said data file containing a plurality of data records wherein there is a one-to-one correspondence between the data records and the records in said search file, a method for retrieving information stored in said data file which allows for the selective stopping and restarting of a search, through the search file comprising the steps of:

a. reading a query into the system and breaking it into words;

b. compiling the keywords contained in said query into an array including with each keyword its address pointer as well as the number of said groups of keywords in which it can be found, said number being its frequency count;

c. grouping the keywords in said query into terms, each term being one or more keywords separated in the query by the word and;

d. determining which keyword term has the minimum summed frequency count;

e. locating the highest address pointer in said keyword term with the minimum summed fRequency count, f. reading said search record identified by said highest address pointer;

g. comparing all keywords in said query with all keywords in said read search record;

h. reading the data record in said data file when said keywords in said read search record corresponds to said query;

i. updating the highest address pointer to indicate the link address in the search record read;

j. stopping the search process, to carry out some other operation; and

k. restarting said search process at the point left off by restarting the search at the search record indicated by the link address previously stored in the array of keywords.

21. In a computer controlled information storage and retrieval system of the type including index, search and data files, a method for allocating storage space in core storage comprising:

a. providing a data file storing data records, b. providing an index file storing keywords which identify the data records, each keyword having associated therewith at least a coded keyword and an address pointer, said keyword and its associated information being termed an index record, c. providing a search file storing groups of keywords, each group termed a search record, each search record corresponding to only one data record, common keywords in said search file being logically connected by link addresses, d. entering into the system the maximum allowable keyword length, e. computing the index record length from said keyword length, f. computing the maximum allowable keyword length from said computed index record length, and g. allocating keyword storage space in core storage on the basis of the computed keyword length.

22. In a computer controlled information storage and retrieval system of the type including index, search and data files, a method for deleting data records from a search operation comprising:

a. providing a data file storing data records, b. providing an index file storing keywords which identify the data items, c. providing a search file storing groups of keywords, said groups of keywords termed search records, there being a one-to-one correspondence between said search records and said data records, common keywords in said search file being logically connected by link addresses, d. designating with a flag and not deleting those search records corresponding to the data records to be deleted from a search operation, and e. bypassing, during a search, all search records containing said flag.