Shared tuple method and system for generating keys to access a database

• US 5,530,854 A
• Filed: 07/06/1995
• Issued: 06/25/1996
• Est. Priority Date: 09/25/1992
• Status: Expired due to Fees

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Scott, Eric D., Priddy, Charles A., Emery, Richard T.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): HOMERE, JEAN RAYMOND
• Application Number:
  US08/499,012
• Time in Patent Office: 355 Days
• Field of Search: 395/600, 395/300, 395/444, 395/848, 364/DIG. 1
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: H04Q 3/54533 Configuration data, translation, passwords, databases

Abstract

A shared tuple method for storing data in a database which supports modification of view relations without causing anomalous changes to logically unrelated tuples in the same or other relations. A generated key is generated by the database which uniquely identifies data in a child tuple. As a result, virtual parent relations are referenced by an original primary key, but has its underlying attribute values stored in one or more secondary relations whose access is gained through stored generated keys. The application interface is unaffected, because the system transparently pieces together the virtual relation from the primary and one or more secondary relations.

Claims

1. In a relational database system having a plurality of predefined relations, said plurality of relations comprising one or more tuples for storing data, a system for minimizing database size comprising:

a plurality of child tuples each containing unique data and a link to another child tuple, said child tuples being organized into a plurality of linked lists;

an index list comprising a plurality of links to linked list of child tuples;

a plurality of parent tuples containing data and one or more generated keys, each of said generated keys uniquely identifying one of said plurality of child tuples; and

means for inserting a data item, said means for inserting including means for determining whether said data item exists in said database by deriving an offset into said index list, following said link in said index list at said derived offset to one of said plurality of linked list of child tuples, and determining whether said data item is contained in any of said child tuples in said linked list;

means responsive to said determining means determining that said data item exists in said data base for returning a generated key to the child tuple in which that data item exists; and

means responsive to said determining means determining that said data item does not exist in said database for adding said data item to a child tuple and returning a generated key to that child tuple;

so that said plurality of child tuples may be referenced from one or more of said plurality of parent tuples at the same time, whereby said unique data is stored once, but may be reference multiple times, and data contents of said parent tuples may be changed by changing generated keys in parent tuples.

2. A database system in accordance with claim 1 wherein said unique data in said child tuples includes a generated key of another child tuple in order to minimize the size of child tuples.

3. A database system in accordance with claim 1 wherein said unique data in said child tuples includes a plurality of generated keys of other child tuples in order to further minimize the size of child tuples.

4. A database system in accordance with claim 1 wherein said database is resident in a memory, said memory being divided into data pages, wherein each of said generated keys defines an offset into a data page in memory.

5. A database system in accordance with claim 1 wherein said means for adding comprises:

means for linking said allocated child tuple to said index list into a selected one of said linked lists.

6. A method for storing data in a database system, said database including a plurality of relations, said relations having one or more parent tuples and one or more child tuples each having a location in memory for storing data, said method comprising the steps of:

storing each unique data item in one of said child tuples;

generating one or more generated keys, each of said generated keys uniquely identifying said location in memory of said one of said child tuples; and

assigning one or more of said generated keys to said parent tuples such that a parent tuple references said one or more unique data items and assigning one or more of said generated keys to said child tuples such that a child tuple may reference one or more of said unique data items, whereby multiple parent and child tuples may reference the same child tuple.

7. A method for allocating data in a database system, said database including a plurality of relations, said relations having one or more parent tuples for storing data and one or more child tuples for storing unique data items, said parent tuples having a generated key uniquely identifying each of said child tuples which may be referenced by one or more parent tuples, said child tuples having links to other child tuples forming a plurality of linked lists of child tuples, said database system including an index list, each entry in said index list having a link to a first child tuple of one of said plurality of linked lists of child tuples, said method comprising the steps of:

determining whether the data to be allocated exists in a child tuple in said database by deriving an offset into said index list, following said link in said index list at said offset to a first child tuple of one of said plurality of linked lists, and following said linked list to determine whether said data to be allocated is contained in any of said child tuples in said linked list;

if said data to be allocated is not found, deriving further offsets into said index list a predetermined number of times, following said link in said index list starting at each of said further offsets to a first child tuple in a further one of said plurality of linked lists, and determining whether said unique data item is contained in any of said child tuples in said further linked list;

returning said generated key for said child tuple if said data is determined to exist; and

if said data does not exist in said database, allocating a child tuple for said data and returning a new generated key for said allocated child tuple.

8. A method according to claim 7 further including the step of:

linking said allocated child tuple to said index list into a selected one of said linked lists.