Browse Prior Art Database

Use of Expression Trees for Saving Space in Relational Data Bases

IP.com Disclosure Number: IPCOM000085943D
Original Publication Date: 1976-Jun-01
Included in the Prior Art Database: 2005-Mar-03
Document File: 3 page(s) / 58K

Publishing Venue

IBM

Related People

Chandra, AK: AUTHOR [+2]

Abstract

The present method describes how certain relations in data bases can be stored as expression trees, thereby realizing substantial savings in space. Relations in a data base, if stored as a sequence of tuples, can be thought of as an expression tree of the form.

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 53% of the total text.

Page 1 of 3

Use of Expression Trees for Saving Space in Relational Data Bases

The present method describes how certain relations in data bases can be stored as expression trees, thereby realizing substantial savings in space. Relations in a data base, if stored as a sequence of tuples, can be thought of as an expression tree of the form.

The present method uses more general expression trees using operators other than just "union" e.g., join and negation. An index may be used to point into the expression tree. A strategy consists of maintaining the tree in some specified shape, and of implementing the basic primitives such as direct search for a tuple, sequential search, insertion and deletion.

The following strategy is suggested for storing relations which have the property that they can "almost" be decomposed by taking certain projections. The expression tree has the shapes in Fig. 2. where R1, R2, R3, R4 are relations, stored as in Fig. 1. Consider columns of relations to have names, and "join" performs an eq-join (see [1]) on all columns with similar names. Thus if two relations with no common column names are joined, the result is a concatenation (sometimes called a Cartesian product). Union and negation (in Fig. 2) of relations are like set-theoretic union and negation, with the proviso that missing columns are considered to be filled in by all possible elements that could be filled in that column.

As an example, consider an automobile dealership that carries four makes of cars (A,B,C,D) that come in six colors (red, blue, green, gold, white, black), manual or automatic transmission (MT, AT), manual or power steering and brakes (MS, MB, PS, PB), cylinders V4, V6 and V8, and three body styles (2 door, 3 door (Hatchback), 4 door). However, models C, D do not come in V4, D does not come in MT or MS, and has no 3 door version. Also model A does not normally come in white, but there is one specially built white A with MT, MS, MB, V4, 2 door. This information, if represented as a single relation would have 1129 tuples having 7903 items. As an expression tree, however, it is represented in Fig. 3 (omitting unions and joins with a single argument), - with only 29 tuples having 41 items.

An advantage of this approach is that entries correspond closely to the way one thinks about the information for...