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

Mechanism for Generating Unclustered Link Structures in a Relational Database System

IP.com Disclosure Number: IPCOM000089803D
Original Publication Date: 1977-Dec-01
Included in the Prior Art Database: 2005-Mar-05
Document File: 3 page(s) / 47K

Publishing Venue

IBM

Related People

Choy, DM: AUTHOR [+2]

Abstract

A link structure in a relational database system is a physical structure of pointers connecting records from two relations. In order for this structure to be created, the relations must satisfy the following: 1. They have to have a set of common domains, called the link domains. 2. One of the relations, called the parent relation, must have the property that for every set of values of the link domains there is at most one record instance in the relation.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 51% of the total text.

Page 1 of 3

Mechanism for Generating Unclustered Link Structures in a Relational Database System

A link structure in a relational database system is a physical structure of pointers connecting records from two relations. In order for this structure to be created, the relations must satisfy the following:
1. They have to have a set of common domains, called the link domains.
2. One of the relations, called the parent relation, must have the property that for every set of values of the link domains there is at most one record instance in the relation.

The other relation participating in the link is called the child relation.

A link structure relates each record in the parent relation, called a parent record, with all those records in the child relation which agree in value with the parent record in the link domains. These records of the child relation are the children of the given parent and are said to be twins. A link structure may also specify an order among the twins. This order is determined by the values the children records have on a set of domains called the order domains.

There are many ways of implementing a link structure. To illustrate our generative machinery, we assume the following: In the parent record, a physical pointer is set to point to the first (in the link order) of its children. In every child, a pointer is set to point to its next twin. The last twin in the link order points back to its parent. Each pointer contains the logical address, called TID, of the target record. This physical structure facilitates the retrieval of a parent and its children. Such retrieval is required when a JOIN operation [*] is performed between relations. Other pointers may also be implemented in the child relation pointing from a child to its previous twin and/or its parent. Furthermore, a parent may contain a pointer pointing to its last child. The mechanism presented here can accommodate all these situations.

A link structure is said to be clustered if the actual occurrences of a set of children are physically close to the actual occurrence of their parent. There are many cases in which a link cannot be clustered. The typical two are: (1) When a particular relation is a child relation in more than one link. In this case, it is very likely that the children of a given parent in one link do not share the same parent in the second link. Any physical placement of the records will probably keep, at most, one link clustered. (2) When a link is dynamically created, i.e., during the normal database operation after the records have been loaded. In this case, it is likely that sets of children in the new link are not physically close to their parents.

The proposed mechanism to generate an unclustered link structure between a parent relation R1 and a child relation R2 is illustrated in the figure. It consists of five basic steps: Step 1: A scan of all records of R1 and R2 is done in their physical order. For each record of R1 found, a record in a sequ...