Relational Operations as BDD Operations
Introduction: Now we see how to represent relations as BDD's. But to implement an algorithm like Algorithm (incremental evaluation of Datalog programs), we need to manipulate BDD's in a way that reflects how the relations themselves are manipulated. Here are the principal operations on relations that we need to perform:
- Initialization: We need to create a BDD that represents a single tuple of a relation. We'll assemble these into BDD's that represent large relations by taking the union.
- Union: To take the union of relations, we take the logical OR of the boolean functions that represent the relations. This operation is needed not only to construct initial relations, but also to combine the results of several rules for the same head predicate, and to accumulate new facts into the set of old facts, as in the incremental Algorithm 12.18.
- Projection: When we evaluate a rule body, we need to construct the head relation that is implied by the true tuples of the body. In terms of the BDD that represents the relation, we need to eliminate the nodes that are labeled by those boolean variables that do not represent components of the head. We may also need to rename the variables in the BDD to correspond to the boolean variables for the components of the head relation.
- Join: To find the assignments of values to variables that make a rule body true, we need to "join" the relations corresponding to each of the subgoals. For example, suppose we have two subgoals r(A,B) k s(B, C). The join of the relations for these subgoals is the set of (a, 6, c) triples such that (a, 6) is a tuple in the relation for r, and (6, c) is a tuple in the relation for s. We shall see that, after renaming boolean variables in BDD's so the components for the two B's agree in variable names, the operation on BDD's is similar to the logical AND, which in turn is similar to the OR operation on BDD's that implements the union.
BDD's for Single Tuples: To initialize a relation, we need to have a way to construct a BDD for thefunction that is true for a single truth assignment. Suppose the boolean variablesare Xi,x2, . . . ,xn, and the truth assignment is a\a2 . . . . an, where each aiis either 0 or 1. The BDD will have one node Ni for each Xi. If = 0, thenthe high edge from Ni leads to the leaf 0, and the low edge leads to Ni \, or tothe leaf 1 if i = n. If a» = 1, then we do the same, but the high and low edgesare reversed.
This strategy gives us a BDD that checks whether each Xi has the correct value, for i = 1,2,... , n. As soon as we find an incorrect value, we jump directly to the 0 leaf. We only wind up at the 1 leaf if all variables have their correct value. As an example, look ahead to Fig. 12.33(b). This BDD represents the function that is true if and only if x = y = 0, i.e., the truth assignment 00.
Union: We shall give in detail an algorithm for taking the logical OR of BDD's, thatis, the union of the relations represented by the BDD's.
Algorithm: Union of BDD's.
INPUT: Two ordered BDD's with the same set of variables, in the same order.
OUTPUT: A BDD representing the function that is the logical OR of the two boolean functions represented by the input BDD's.
METHOD: We shall describe a recursive procedure for combining two BDD's. The induction is on the size of the set of variables appearing in the BDD's.
BASIS: Zero variables. The BDD's must both be leaves, labeled either 0 or 1. The output is the leaf labeled 1 if either input is 1, or the leaf labeled 0 if both are 0.
INDUCTION: Suppose there are k variables, yi,y2,... ,yu found among the two BDD's. Do the following:
1. If necessary, use inverse short-circuiting to add a new root so that both BDD's have a root labeled y\.
2. Let the two roots be N and M; let their low children be Ao and Mo, and let their high children be N\ and M\. Recursively apply this algorithm to the BDD's rooted at Ao and M0 . Also, recursively apply this algorithm to the BDD's rooted at N\ and Mx . The first of these BDD's represents the function that is true for all truth assignments that have y\ — 0 and that make one or both of the given BDD's true. The second represents the same for the truth assignments with y\ = 1.
3. Create a new root node labeled y\. Its low child is the root of the first recursively constructed BDD, and its high child is the root of the second BDD.
4. Merge the two leaves labeled 0 and the two leaves labeled 1 in the combined BDD just constructed.
5. Apply merging and short-circuiting where possible to simplify the BDD.