next up previous
Next: 1 Introduction

Schema and Tuple Trees: An Intuitive Structure for Representing Relational Data
Appears in Computing Systems, Volume 9, Number 2
Copyright (c) 1996 by the USENIX Association

Eric H. Herrin, II - Raphael A. Finkel

University of Kentucky


Qddb is a publicly available database suite designed for applications in which the data is a set of records, each of contains hierarchical structure. For example, a database of patients contains a record for each patient; each patient record has multiple copies of visit substructures. Records containing such nested and replicated attributes are equivalent to the join of traditional relational tables. Qddb records therefore allow the data to be recorded in a more natural fashion than relational tables.

The presentation of data in Qddb is unusual but intuitive; the user usually views a subset of a full relational row at any given time.

This paper presents schema and tuple trees, the underlying structures of a Qddb database. Instead of a set of full relational rows representing the join of several tables, the tuple tree represents the tables in a compressed form. Related data are stored and displayed together, which allows the application designer to build an application in a relatively small amount of time. The algorithms for search and presentation are quite efficient.

Herrin Software Development, Inc.