Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Generation of Short Unique Key Values for Database Tables

IP.com Disclosure Number: IPCOM000105171D
Original Publication Date: 1993-Jun-01
Included in the Prior Art Database: 2005-Mar-19
Document File: 4 page(s) / 184K

Publishing Venue

IBM

Related People

Mehovic, F: AUTHOR

Abstract

It is often needed in database implementations to generate unique keys for entity instances, which we will call objects. These keys are primary keys in the table in which the objects reside, and are, likely, foreign keys in the tables which refer to those objects. The problem of assuring that those keys are unique is an old one, and the developers usually resort to using time stamps, possibly concatenated with other values, such as the computer address of those objects. This, however, results in those unique keys being too long, in some cases even 32 bytes even though the actual number of distinct objects may never exceed 64K, which is representable with only 2 bytes.

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

Generation of Short Unique Key Values for Database Tables

      It is often needed in database implementations to generate
unique keys for entity instances, which we will call objects.  These
keys are primary keys in the table in which the objects reside, and
are, likely, foreign keys in the tables which refer to those objects.
The problem of assuring that those keys are unique is an old one, and
the developers usually resort to using time stamps, possibly
concatenated with other values, such as the computer address of those
objects.  This, however, results in those unique keys being too long,
in some cases even 32 bytes even though the actual number of distinct
objects may never exceed 64K, which is representable with only 2
bytes.  The long keys, then, may considerably degrade the performance
of the database, due to having fewer objects per physical page, and,
even more importantly, having much fewer key values in the associated
index pages.  Our goal is, then, to generate the unique keys as short
as possible, yet to make the generation process easy to implement.

      The solution to the problem above is based on the fact that
there is, almost always, an index on the table of object over the
unique key, to which we will refer simply as key.  The other
assumption is that very few objects live extraordinarily longer than
the average object, where life of an object is defined as the time
expired between its creation and its deletion.  Most objects satisfy
this assumption.  Some examples are calendar entry objects, meetings
and daily reminder notes, in a calendar database.  These objects
become obsolete after a certain number of months and then they are
either deleted or stored away and then deleted.  Another example
would be employee objects in an employee database, where no employee
will exist in the employee table for longer than 80 years, for
example.

      The procedure to generate short unique keys is as follows:
first determine what would be the average number of distinct object
in the table.  As an example, there are 64K objects, on average (64K
= 2 to the power of 16 = 65536).  Then define the size of the unique
key sufficiently large so that the number of objects is only a small
fraction of the key domain.  In our example let the key length be 4
bytes with the domain of 4096M (4096 = 2 to the power of 32 =
4,294,967,296), so that only 64K/4096M = 0.001526% of the domain is
used, on average.  With no loss of generality, assume that our keys
are unsigned integers, so in this example, the values range from 0 to
4096M-1.  Then we assign the unique keys as the objects are created
(inserted into the table) in a descending sequence starting from the
maximum domain value or in an ascending sequence starting from the
minimum domain value.  The former was used in the example, thus start
assigning the keys starting from the value of 4096M-1.  Every time a
new object is inserted, a search was made for the minimum e...