4 TupleLists

  A TupleList is an internal data structure (a singly-linked list of locators into Stable) used by programs to represent sets of tuples. Search routines generate a TupleList for each single-key query. Multiple-key queries generate multiple TupleLists that are merged in a manner consistent with the type of query. Library routines accept, manipulate, and return these lists instead of dealing with tuples directly. The values of the tuples can be extracted by following the locators.

More precisely, a TupleList node contains the following information:

• The unique serial number of the tuple
• A locator for the tuple in Stable (if applicable)
• The type of the tuple: original for tuples in Stable, change for tuples in the Changes directory, and addition for tuples in the Additions directory

Attribute values are not directly described by TupleLists. Figure 5 shows the relationship between a TupleList and the various qddb files.

  
Figure 5: TupleLists and a qddb relation

TupleLists allow us to prune the solution set of a search before any tuples are read from the relation. The binary operations available on TupleLists are set union, intersection, and exclusion. We perform these operations by traversing the two TupleLists in the appropriate manner. We keep these lists sorted by serial number to make the cost of all operations linear in the combined size of the two TupleLists.

For example, we might want to find a particular paper written by several people in a bibliography relation. The intersection of the TupleLists that are produced by the individual searches for each person produces a reasonable list.