Check out the new USENIX Web site.
Computing SystemsUSENIX


Volume 9, Number 2

Spring 1996

Pages 93-118

Schema and Tuple Trees: An Intuitive Structure for Representing Relational Data

By Eric H. Herrin, II and Raphael A. Finkel


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 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.

Pages 119-130

Setting Interrupt Priorities in Software via Interrupt Queueing and Processor Level Virtualisation

By Geoff Collyer


When hardware interrupt priorities don't match the needs of software, operating system designers often just suffer in silence. We describe another solution here: simulating the hardware priority interrupt queueing mechanism in software, but assigning the (software) interrupt priorities as we wish. This was done on an AMD 29200 microcontroller which has effectively only two interrupt levels: the clock and everything else.

Pages 131-152

Checking for Race Conditions in File Accesses

By Matt Bishop


Flaws due to race conditions in which the binding of a name to an object changes between repeated references occur in many programs. We examine one type of this flaw in the UNIX operating system, and describe a semantic method for detecting possible instances of this problem. We present the results of one such analysis in which a previously undiscovered race condition flaw was found.

Pages 153-154

Contributors to This Issue


?Need help? Use our Contacts page.
Last changed: May 16, 1997 pc
'Systems index
Publications index