1 Introduction

Qddb is a database suite that attempts to provide a limited amount of function with high efficiency. It incorporates the following unusual ideas.

• A combination of hashing and indexing is used for quick retrieval. A complete inverted index is searched by hashing. Updates create data outside the scope of the hash table that must be searched in a less efficient manner.
• Although its exterior appears similar to other packages utilizing the relational model, qddb allows attribute values to be missing or multiple and of any length.
• Attribute values are stored as arbitrary-length Ascii strings. Ordinary text editors are used as data-entry and update tools.
• Attributes can be structured to contain other attributes.

Qddb remedies many inefficiencies of general database packages when the data are relatively stable, that is, when the data are changed infrequently. We concentrate on minimizing the number of system calls (open and read calls) per query, since they are significantly more time-consuming than small in-memory searches and computation. Our file structure is designed to minimize system calls in the case of a stable relation, but it still performs acceptably for a relation with instable parts.

A stable relation is one that has not been updated since the last stabilization. We provide a stabilization routine that parses the entire relation into keys and builds a hash table for quick retrieval of tuples that contain any given key. This process may require a significant amount of time in comparison to other database operations, but the time is not excessive. An instable relation is one that has been updated after the last stabilization; the instable parts of a relation are the tuples that have been added or updated since stabilization.

A key is defined to be any sequence of characters delimited by white space or punctuation in any attribute value of a tuple. This definition is not crucial to our approach, but serves as a useful convention. We could have been more restrictive (to uncommon English words) or more inclusive (to all strings). Retrieval time is not affected by how restrictive we are, but the size of one of the auxiliary files and the time to stabilize is dependent on how many distinct keys appear in a relation.

This paper begins by discussing the syntax and semantics of the files that comprise a relation. We analyze the operations on these files to demonstrate the performance benefits of our approach. The in-memory structures used by qddb programs are presented and analyzed to show how we use them to implement QSQL, a version of the query language SQL appropriate to qddb semantics. We then turn to enhancements of the basic model. We show how extra structure files can make some searches faster. Finally, we discuss drawbacks to our approach and how an implementor might overcome them.