Browse Prior Art Database

Space Minimizing Method for First-Change/First-Out Database Keys

IP.com Disclosure Number: IPCOM000100100D
Original Publication Date: 1990-Mar-01
Included in the Prior Art Database: 2005-Mar-15
Document File: 4 page(s) / 140K

Publishing Venue

IBM

Related People

Ricard, GR: AUTHOR [+3]

Abstract

A COBOL specification defines a collating order for duplicate keys in indexes as First-Change/First-Out (FCFO) order. FCFO is analogous to the commonly used LIFO/FIFO order with the difference being that key order among duplicates is determined chronologically. The earliest key to change collates first; the latest to change collates last. Described is a method for minimizing the amount of excess storage required to maintain the duplicate key ordering information. The method has no dependencies on the system hardware clock/calendar functions so time changes for such things as Daylight Savings Time or power outages do not affect duplicate key collating order.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 42% of the total text.

Space Minimizing Method for First-Change/First-Out Database Keys

       A COBOL specification defines a collating order for
duplicate keys in indexes as First-Change/First-Out (FCFO) order.
FCFO is analogous to the commonly used LIFO/FIFO order with the
difference being that key order among duplicates is determined
chronologically.  The earliest key to change collates first; the
latest to change collates last.  Described is a method for minimizing
the amount of excess storage required to maintain the duplicate key
ordering information.  The method has no dependencies on the system
hardware clock/calendar functions so time changes for such things as
Daylight Savings Time or power outages do not affect duplicate key
collating order.  Additionally, the method does not require any
additional storage space for the data base records themselves, and
the FCFO ordering is maintained even if the index is saved and
restored onto another system.

      As each FCFO key is stored in the index, a check is made to
see if any duplicate keys exist.  If no duplicate exists, the key is
inserted with only a single additional byte of '00'X, which indicates
that it is the first among duplicates.  If a matching key is found,
the key is inserted with a five-byte timestamp, with the timestamp
supplied by a monotonically increasing value that starts with the
value '0100000000'X.  This starting value ensures that all duplicates
following the first will collate following the format of the first
duplicate.  Since most keys will not have any duplicates, this method
minimizes the amount of space required in the index to one byte per
key for those that do not have any duplicates.  When inserting
duplicate keys, there is no need to modify the first (or any other)
key that has already been inserted.  The two formats of keys can
coexist within one set of duplicates.  As each duplicate key is
inserted, the timestamp is incremented, thereby assuring that
duplicate keys maintain the order in which they were inserted.

      When an index search is made, a check must be made against the
length of the key.  If a long key is found, it is known that the
format of the key is of the second form. Short keys are known to be
of the first duplicate format.

      The format for the first occurrence of a new key to an index
follows:

                            (Image Omitted)

      The user key data is supplied by the user and is used as the
primary key field to determine order.  The '00'X byte is placed
following the user key data to force this key to collate prior to
subsequent keys that have duplicate user key data.  The Relative
Address (RA) is used internally to locate the actual database record
being referred to by the key.

      The '00'X byte at position n+1 will always collate prior to the
first byte of the logical timestamp since the timestamp is always
>'00'X and both begin in the same position.  This will guar...