3 File structure

Each qddb relation is implemented as a Unix directory containing several files and subdirectories. The name of the relation is the same as the name of the directory that contains these files. All files are in Ascii. Some files are structure files, which assist in performing searches. Structure files generally point into other files by means of locators, which are (offset, length) integer pairs. The files are as follows.

1. Schema - The schema for the relation, following the syntax given in Figure 2 above.
2. Stable - A file containing all stable tuples in the relation. They are represented in storage format, in which tuples are separated by blank lines, and every attribute starts on a new line with an identifier, which is an (attribute identifier, instance number) pair. Nested attributes include another such pair for each level of nesting. For example, the apartment number of a student's second address has the identifier ``%3.2.1.1.3.1'', meaning that the attribute is the second instance of the third attribute given by the schema in Figure 1. The meaning of this particular attribute identifier can be summarized as follows:
   • 3.2 = Address: second instance
   • 1.1 = Street: first instance
   • 3.1 = Apartment: first instance
   Each tuple has an implicitly defined attribute called $NUMBER$ used as a unique identifier for that tuple in the relation. Identifier ``%0'' stores both the unique identifier and a validity flag (either ``V'' or ``I''). The whole tuple can be marked invalid (during an update, for example) by changing this flag; since Stable has the same length afterward, all locators pointing into it are still usable.
3. Index - A structure file containing all hash buckets for the hash table. Each bucket contains zero or more entries. Each entry contains a key followed by a list of locators for that key into Stable.
4. HashTable - A structure file containing the hash table. Each entry contains a locator into Index, the number of keys that hash to this entry, and the value of the hash function for this entry (so sparse tables are efficiently represented). The number of buckets, hence the size of the hash table, is computed at stabilization time to keep the number of collisions reasonably small without making the table excessively long. The default hash size may be overridden by the hashsize option in the Schema.
5. Stable.key - A structure file containing a complete list of locators for the tuples in Stable. This file is useful at stabilization time and whenever a program needs to read all tuples in the relation.
6. Changes - A directory containing a file for each tuple that has been updated since the relation was last stabilized. Each such file is named by the serial number of the affected tuple and contains that tuple in storage format. The affected tuples are marked invalid in Stable.
7. Additions - A directory containing a file for each tuple that has been added since the relation was last stabilized. Each such file is named by the serial number of the affected tuple and contains that tuple in storage format.
8. Additions/NextEntry - A file containing the next serial number to be used when a tuple is added.

Typically, programs that query the relation initialize themselves by bringing HashTable into memory. Thereafter, a query on a single key requires (1) computing the key's hash value, (2) examining the hash table to find the locator into Index for the associated bucket, (3) reading a contiguous section of Index to obtain locators into Stable for the tuples containing that key, and (4) reading a contiguous section of Stable for each tuple to be presented. The list of locators built in step (3) is stored in an internal form called a TupleList (see Section 4), which can be manipulated before step (4), for example, to remove unwanted entries. Thus, the solution set X of a simple query on stable data can be obtained in |X|+2 read system calls, including the one needed to bring the hash table into memory.

Each query must also search instable data. The additional cost is one extra open/read pair plus one read of the Changes or Additions directories for each changed or added tuple. Thus, the number of excess open/read system calls is directly proportional to the number of added and updated tuples in the relation, that is, the number of tuples in the instable part.

In addition to the extra system calls, instable relations also require significant computation, because a string-search routine like fgrep must be used to determine the presence of keys.

We have considered an alternative implementation: to log all updates in a single Log file, with locators to that file stored in a separate structure file called LogLocators. Each update would require invalidating the appropriate entry in LogLocators and appending the update to Log. This representation has the advantage that there are fewer open calls needed to search updated tuples. (Open calls are potentially expensive.) The log file approach is therefore more efficient than our current method for querying instable parts of a highly modified relation.

The log file representation has the disadvantage that it requires more computation to perform an update. Also, simultaneous updates to different tuples require record locking in potentially many portions of the two files. Our current approach has the advantage of less complicated storage management and the expense of only a single pair of open/write calls per update. Opening a single file for exclusive use is sufficient to prevent race conditions and allows all tuples to be updated at once.

We accept the performance penalty of our method for instable relations because we assume that relations are changed infrequently; however, we believe that log files would be a useful addition to qddb.