4.1 The stable and the slippery

All the data for a relation are stored within the directory that names the relation. Data that haven't changed recently are all stored in Database. You generally don't want to look at this file, but if you do, you will find that it is in Ascii with one block of lines per tuple, separated by a blank line from the next tuple. Each attribute has a line of its own, but only if the attribute has a non-empty value for that tuple. Each line has a cryptic first part that identifies which attribute it refers to. For example, a line like:

  %2.1.4.5.6.1 Frederick Douglass

refers to the second attribute, first instance, and that this attribute is structured; the line refers to the fourth subattribute, which is expandable; we are dealing with the fifth instance, which is itself structured; we are dealing with the sixth sub-subattribute, first instance. The value of this sub-subattribute is ``Frederick Douglass.'' If the value contains a linefeed, the linefeed is preceded by ``\'' to avoid confusing the Qddb routines.

The actual format of a tuple is shown in Figure 4.1. The ``V'' means that the tuple is valid, that is, it has not been modified or deleted. Invalid tuples, denoted by an ``I'' instead of a ``V,'' are generally ignored by Qddb. Each line begins with a ``%'' character, immediately followed by a list of numbers delimited by periods (``.''). These numbers are pairs of the form attribute.instance, except for the ``%0'' attribute, which just holds Qddb information about the tuple.

  
Figure 4.1: A Qddb tuple in external format

The first attribute in Figure 4.1 is equivalent to the Book.ISBN attribute of our Library relation. The first attribute's number is %1.1.1.1. This number states that it is the first attribute at level 1 in the schema, that is, Book, and that this attribute is in the first instance of Book. The second pair states that this attribute corresponds to the first instance of ISBN (the first attribute at level 2 within the attribute Book). Attributes with empty values are absent from the tuple. Disk space is often at a premium, so we don't reserve space for empty attribute values. Although we don't store empty attributes on disk, we do fill in the empty spots when the tuples are in memory.

To make searches fast, Qddb maintains structure files that allow it to find tuples quickly in Database, which can grow very long (hundreds of megabytes), and which you certainly don't want to scan through from beginning to end. These files include HashTable, KeyIndex, NumericIndex, Index, and Database.key. They are described in some detail in Section 4.3. You don't need to look through these files, but they are also Ascii, so you certainly may if you want.

Whenever you change or add a tuple to your Qddb database, the entire tuple is replaced or added. But the structure files wouldn't work if Qddb actually modified the Database file. Instead, changes are placed in a subdirectory called Changes, with one file for each changed tuple. The name of the file is the serial number of the tuple that has been changed. Qddb subtly substitutes an ``I'' (for ``invalid'') for a ``V'' (for ``valid'') in the first line of the tuple in Database to indicate to the search routines that if they find this tuple, they should ignore its version in Database. New tuples are placed in a different subdirectory called Additions, again, one file per tuple.