next up previous
Next: 2 A motivating example Up: Schema and Tuple Trees: Previous: Schema and Tuple Trees:

1 Introduction

  Conventional relational database implementations can be cumbersome to use and program. A single database often requires many tables of interrelated information. The relationship between the tables is well-defined but can be difficult to translate into a usable application. Allowing an arbitrary number of values in a field generally requires that the field be linked to a separate table built for just that purpose. The links between tables are often unique identifiers that the user must invent and that the application must check for uniqueness and consistency across tables. Each extra table therefore places a burden on the designer, the database programmer, and the end user.

To avoid a proliferation of tables, designers tend to limit the number of values in a field (such as the number of addresses an individual may have). The result can be frustrating to users who need to deal with exceptional cases that do not fit these limits.

This paper shows how Qddb [Herrin, II & Finkel 1991] alleviates most of the tedious work involved in designing relational tables that have fields that may have an arbitrary number of instances. The Qddb technique has other surprising and helpful characteristics.

We begin with a small example to show how a schema tree can be used to define a database. Next, we discuss the relationship between schema trees and tuple trees. Finally, we concentrate on tuple trees and their characteristics, including intuitive presentation forms and algorithms for generating those presentations.

Herrin Software Development, Inc.