Effects of Updates on Optimality in Tries

AbstractThe double chained tree is used as the basis for organizing files in a database system. We model such systems with a trie, a tree in which leaves correspond to records from a file. Retrieval proceeds by following a path in a trie from the root to a leaf, where the edge taken at each node is determined by some attribute value of the query. For a given file, altering the order in which attributes are tested can change the size of the resulting trie; tries with minimum size are considered optimum. We explore the preservation of optimality under the operations of inserting a record into the file, deleting a specific record from the file, and deleting an arbitrary record from the file, showing that even for binary files, a single update may be sufficient to make all optimum tries nonoptimum. Finding an indexing set for a file consists of finding a subset of the attributes which distinguish all records. We show that given a minimum size indexing set, a single insertion or deletion may change the file so that no superset or subset, respectively, can be a minimum indexing set for the new file