Design an algorithm for maintaining join indices incrementally—that is, so that the addition of new tuples to the relations involved in the join do not require the entire join to be recomputed from scratch.

Question

What will be an ideal response?

Answer 1

Consider a join index for an equi-join of tables A and B. Implement the index as an integrated B+ tree. The search key is the index into A of a particular row. Each leaf entry contains a pair < p, q > where p is a search key value and q is the index of a row in B that satis?es the equi-join condition with respect to the row with index p in A. When a row with index a is added to A the index of each row, with index b, in B that joins with it is computed and the entry < a, b > is added to the tree. Computing the equi-join involves scanning the leaf level once. Since all entries corresponding to a particular row of A are in sequence at that level, only a single scan of A is required. The number of accesses to B depends on the number of rows in the equi-join.
Adding a row to B also requires that we ?rst ?nd the rids of all the matching tuples in A and then insert the appropriate pairs of rids in the join index.
If a row is deleted from A, we can ?nd all the index entries for that row in the B+ tree and delete them. Deleting the rows of B requires more work because we cannot easily ?nd the corresponding index entries in the join index, since the search key of the B+ tree has the rid of A, not of B, as the ?rst component. Thus, we might have to scan all the leaves of that tree in order to ?nd the index entries to delete.