Interactive enquiry system

• US 4,186,438 A
• Filed: 03/16/1977
• Issued: 01/29/1980
• Est. Priority Date: 03/17/1976
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Simmons, John, Middleton, Brian H., Robinson, Thomas E., Benson, Paul H., Pinnell, Martin C., Kingdom-Hockings, Michael L., Sheeler, Richard E.
• Primary Examiner(s): Nusbaum, Mark E.
• Application Number:
  US05/778,181
• Time in Patent Office: 1,049 Days
• Field of Search: 364/200 MS File, 364/900 MS File
• US Class Current: 711/113
• CPC Class Codes: G06F 12/10 Address translation
• CPC Class Codes: G06Q 10/02 Reservations, e.g. for tickets, services or events
• CPC Class Codes: G07B 1/02 employing selectable printing plates

Abstract

Described is an interactive enquiry system in which a complete data base is contained at a host computer. Local terminal sub-systems are remotely connected to the host with each local sub-system containing a local data base. Each local data base is dynamically maintained so that the most frequently used pages are retained in local storage. If storage space needs to be created, the least frequently used pages are discarded from the local data base.

Claims

1. In an interactive enquiry system of the type comprising a host data processor, a central data store controlled by the host processor and adapted to store a data base, a plurality of local subsystems connectible to the host processor, each local subsystem including a local data processor for controlling access to the host processor and a local data store comprising a random access memory and a magnetic disk file connected to the local processor and adapted to store part of the data base, at least one enquiry terminal in each local subsystem connected to the local processor for accessing any accessible item in the data base stored in the central store,

wherein the random access memory portion of the local data store is divided into a first part adapted to store items accessed from the data base and a second part adapted to store a directory entry for each item stored within the first part, each directory entry containing a count which is an indication of the frequency of use of its associated item, said local processor updating said count whenever its associated item is used, said local subsystem further comprising:

means operable when said first part has no space for a newly accessed item to scan the directory entries and determine the least frequently used items, and;

means responsive to said scanning means to delete at least one of said least frequently used items to create sufficient space for the newly accessed item.

2. An interactive enquiry system as claimed in claim 1, in which the random access memory is so arranged that the boundary between the first part and the second part is floating.

3. An interactive enquiry system as claimed in claim 1 wherein each subsystem further comprises:

means adapted to store items in selected tracks on said magnetic disc file and to store on said disc file associated directory entries which include an indication of the frequency of use of their associated items;

means for searching said disc file directory entries whenever a requested item is not found in said random access memory to determine whether the requested item is stored on said magnetic disc, and;

means operable when the disc file has no space for a newly accessed item to scan said disc file directory to locate least frequently used item or items and adapted to delete the least frequently used item or items to create sufficient space for the newly accessed item.

4. An interactive enquiry system as claimed in claim 3, wherein each subsystem further comprises:

means for storing a directory entry associated with a particular item on the same track as that particular item.

5. An interactive enquiry system as claimed in claim 4, wherein each subsystem further comprises:

means for performing a hashing operation on a number identifying an item to determine in which track or group of tracks that item should be stored.

6. An interactive enquiry system as claimed in claim 5, wherein each magnetic disc file includes a plurality of dedicated tracks for storing items, said dedicated tracks being divided into a plurality of storage blocks and at least one dedicated directory track containing a plurality of sectors corresponding in number to the number of storage blocks, each directory sector containing an entry identifying the item stored in the corresponding storage block.

7. An interactive enquiry system as claim in claim 3, wherein each disc file includes a pair of directory tracks each divided into a plurality of sectors equal in number to the number of storage blocks, a directory entry for each block being contained partly in one of the pair and partly in the other of the pair.

8. An interactive enquiry system as claimed in claim 7, wherein each subsystem further comprises:

means operable when a required item is not within the random access memory for simultaneously accessing the disc file and the central store and adapted to cancel the request to the central store when the item is first received from the disc file and alternately to cancel the request to the disc file when the item is first received from the central store.

9. An interactive enquiry system as claimed in claim 1 wherein said local subsystem further comprises:

means for associating a frequency of use count with each item stored in the local store, and;

means for increasing the count associated with a particular item whenever that item is accessed.

10. An interactive enquiry system as claimed in claim 1 wherein each subsystem further comprises:

means for associating a frequency of use count with each item stored in the local store;

means for assigning a high count whenever the particular item is accessed, and;

means for periodically decreasing the count for all items stored in the local store.

11. In an interactive enquiry system of the type comprising a host data processor, a central data store controlled by the host processor and adapted to store a tree structured data base, a plurality of local subsystems connectible to the host processor, each local subsystem including a local data processor for controlling access to the host processor and a local data store connected to the local processor and adapted to store part of the data base, at least one enquiry terminal in each local subsystem connected to the local processor for accessing any accessible item in the data base stored in the central store, the method of concentrating most frequently used pages of said tree structured data base toward one end of a page buffer in a random access memory portion of said local data store comprising the steps of:

(1) determining if sufficient space exists in said page buffer to store a page retrieved from said tree structured data base at said host processor and proceeding to step 5 if sufficient space exists;

(2) determining if the number of pages in a first push down stack of pages within said page buffer exceeds a predefined minimum number and proceeding to step 4 if said minimum is not exceeded;

(3) deleting the bottom most page from said first push down stack and proceeding to step 1;

(4) deleting the bottom most page from a second push down stack of pages within said page buffer and proceeding to step 1;

(5) adding said retrieved page to the top of said first push down stack if the page level number of said retrieved page is above a predefined threshold number and adding said retrieved page to the top of said second push down stack if said page level number is below said predefined threshold number.