Data base management system for real-time applications

• US 4,961,139 A
• Filed: 06/30/1988
• Issued: 10/02/1990
• Est. Priority Date: 06/30/1988
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Company (HP Inc.)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Wright, Michael J., Givens, Cynthia, Liu, Ching Chao, Fatehi, Feyzi, Hong, Le Thieu
• Primary Examiner(s): Fleming, Michael R.
• Assistant Examiner(s): Ray, Gopal C.
• Application Number:
  US07/213,578
• Time in Patent Office: 824 Days
• Field of Search: 364/200, 364/900
• US Class Current: 1/1
• CPC Class Codes: G06F 16/00 Information retrieval; Database structures therefor; File system structures therefor
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database

Abstract

A real-time database provides the predictable, high speed data access required for on-line applications, while providing flexible searching capabilities. The data retrieval routines include the option to "read-through-lock" to access data in locked data tables, the capability to directly access to data using tuple identifiers, and the capability to directly access unformatted data from input areas which contain blocks of unformatted data. The data updating routines include an option to omit index updating when updating data and an option to update data in a locked data table. Multiple indexes can be defined for a data table. Thus, high speed searches can be performed based on a variety of data fields. The data storage and retrieval mechanisms are independent and there are hash index tables that connect the multiple index keys to the data tables. The data table structure includes a column defined for storing tuple identifier strings. These tuple identifiers can be used as pointers for chaining to related data stored in other data tables. The datas base has relatively small programmatic memory. There is a common structure for user data tables, index tables and system tables. The database includes a minimum number of routines with certain routines providing multiple functionality.

Claims

1. A data base management system for controlling storage, retrieval and modification of information in a data collection contained in storage devices in a data processing system, said data collection comprising a plurality of data records stored as tuples in data tables, and unformatted data stored in input areas, comprising:

(a) mans for defining an index on a data table by specifying the selected ones of the tuple entries of the data table that comprise the key value for the index;

(b) hash index table means for storing tuple identifiers arranged so that the hash index tuple numbers resulting from applying a hashing function to a given key value for an index correspond to the hash index table locations containing the tuple identifiers associated with data table locations containing data with the given key value;

(c) first data storage means for storing data as tuples in data tables, with each tuple in a location associated with a tuple identifier uniquely identifying the tuple, comprising;

(i) means for inserting a data tuple to be stored in an available location in the data table, the location having a first tuple identifier;

(ii) means for applying a hashing function to the key value for the index, to determine a hash index tuple number corresponding to a location in a hash index table; and

(iii) means for storing the firs tuple identifier in the hash index table location corresponding to the determined hash index tuple number;

(iv) means for outputting the tuple identifier corresponding to the location in the data table where the data tuple was stored;

(d) second data storage means for storing unformatted data in blocks of memory space defined as input areas, and for outputting an input area identifier and the physical address of the stored unformatted data;

(e) first data retrieval means for providing indirect access to data in a data table on the basis of a key value, comprising;

(i) means for applying a hashing function to the key value to determine the location of a tuple identifier in a hash index table; and

(ii) means for retrieving the data from the location associated with the tuple identifier in the data table;

(f) second data retrieval means for providing direct access to data in a data tale on the basis of a tuple identifier, comprising means for retrieving the data from the location associated with the tuple identifier in the data table;

(g) third data retrieval means for providing direct access unformatted data from input areas, comprising means for retrieving unformatted data using a physical address for the data, and means for retrieving data using an input area identifier and an offset value; and

(h) data modification means for updating data in the data table, comprising means for selectively updating the hash index table or not updating the hash index table when modifying data in an indexed data table.

2. The data base management system according to claim 1, further comprising:

means for locking the data in a data table to indicate that the data should not be accessed or updated;

wherein said first data retrieval means further comprises means for selectively accessing data in locked data tables; and

wherein said data modification means further comprises means for selectively updating data in locked data tables.

3. A method for storing and retrieving data tuples in data tables in a database so that more than one index can be defined for a data table, each location in the data table associated with a unique tuple identifier, the method for storing comprising the steps of:

(a) defining at least one index on a data table by specifying the entries of the data table that comprise the key value for the index;

(b) inserting a data tuple to be stored in an available location in the data table;

(c) applying a hashing function to the key value for the index, to determine a hash index tuple number corresponding to a location in a hash index table; and

(d) storing the first tuple identifier in the hash index table location corresponding to the determined hash index tuple number;

(e) repeating steps b. through d. above for each index defined on the data table; and

(f) outputting the tuple identifier corresponding to the location in the data table where the data tuple was stored; and

the method for retrieving data tuples comprising the steps of;

(a) applying a hashing function to the key value to determine a tuple identifier for a location in a hash index table;

(b) retrieving the tuple identifier from the location in the hash index table; and

(c) retrieving the data tuple from the location in the data table associated with the tuple identifier retrieved from the hash table.