Abstract. We present an algorithm for constructing a tree to satisfy a set of lineage constraints on common ancestors. We then apply this algorithm to synthesize a relational algebra expression from a simple tableau, a problem arising in the theory of relational databases. Key words, tree algorithms, lowest common ancestors, relational databases, relational algebra, tableaux, query optimization, join minimization 1. A tree discovery problem. In a rooted tree, the lowest common ancestor of two nodes x and y, denoted (x, y), is the node a that is an ancestor of both x and y such that no proper descendant of a is also an ancestor of both x and y. Suppose we are told a tree T has leaves numbered 1, 2, .., n, and we are given a set of constraints on the lowest common ancestors of certain pairs of leaves. In particular, suppose the constraints are of the form (i,/) < (k, l) where /" and k 1, meaning that the lowest common ancestor of and j is a proper descendant of the lowest common ancestor of k and l. Note that the order of and j in (i, j) and of k and in (k, l) are irrelevant. From a set of constraints of this form, can we reconstruct T, or determine that no such tree exists? Example 1. Suppose we are given the constraints (1.1) (1, 2) < (1, 3), (3, 4) < (1, 5), (3, 5)< (2, 4). One possible tree T consonant with these constraints is shown in Fig. 1 . However, if we add the constraint (4, 5) < (1, 2), then it can be shown that no tree can simultaneously satisfy all these constraints. In this paper we give an efficient algorithm for solving this problem. We then present an application of this algorithm to the problem of synthesizing a relational algebra expression from a simple tableau. 2. Finding the tree. The central idea behind the solution is to determine for a potential tree T the sets of leaves that are descendants of each child of the root of T. Call these sets $1, $2,'", St. We may assume r=>2, since if a tree satisfying a set of * Received by the editors July 10, 1979, and There are two conditions that these sets must satisfy for each constraint (i, ])< (k, t). (1) and ] must be in the same set. Otherwise (i,/') is the root of T, and the root cannot be a proper descendant of (k, l). (2) Either k and are in different sets, or i,/', k and are all together in one set. Otherwise (i, ]) cannot be a proper descendant of (k, l). We shall also show that conditions (1) and (2) are sufficient. Thus, if we can partition the nodes into two or more sets satisfying (1) and (2), and if we can recursively build trees for each set, then a tree exists; otherwise, one does not. Given a set of constraints C, we define a partition rrc on the leaves 1, 2,..., n using the following rules" (2) is used. If we add to (1.1) the constraint (4, 5) < (1, 2) , to obtain the set (1, 2) < (1, 3), (3, 4) < (1, 5), (3, 5)< (2, 4), (4, 5) < (1, 2), then by rule (2) the two blocks must be merged, yielding a trivial partition. Since a necessary condition for the existence of a tree is that rrc have more than one block, we can immediately infer that this new set of constraints is not satisfied by any tree. In Fig. 2 we present a recursive algorithm to build a tree T satisfying a set of constraints C on a nonempty set of nodes S. It returns the null tree if no tree exists. The basic idea is to compute the partition rrc, check that it has at least two blocks $1, $2, ', &, r -> 2, and construct the sets of constraints C,,, 1 _-< rn _<-r, such that C, is C restricted to those constraints that involve members of S, only. THeOReM 1. If BUILD(S, C) returns a nonnull tree T, then T satisfies the constraint set C. Proof. We proceed by induction on the size of S. The basis, one node, is trivial. Suppose then that the theorem is true for all sets smaller than S. Because every recursive invocation of BUILD is applied to a set of strictly smaller size than S, we can assume that all recursive calls of BUILD obey the inductive hypothesis. We must show that all constraints in C are satisfied by T. Accordingly, let (1) is applied to a constraint (i, f)<(k, l) causing the blocks containing and j, say B1 and B2, to be merged. By induction, all the nodes in B1 and B2 are contained, respectively, in the subtrees rooted at n and nz, two children of the root. If n n2, then (i, j) is the root of T. But then no constraint of the form (i, ) < (k, l) can be satisfied by T, violating our assumption that T satisfied C. We must therefore have rtx n: and all the nodes in B tO Bz are descendants of the same child of the root. has only one block, or BUILD(S,, C,) returns the null tree for some m. In the first case, it follows from Lemma 1 that the root of T has only one child. But then T', which is T with the root removed, provides a smaller counterexample to the theorem. In the second case, where BUILD(S,, C,,) returns the null tree, let S,, be contained in the subtree rooted at child n of the root of T. Define T' to be the subtree of T with root n, after deleting all leaves not in $,, and any interior nodes none of whose descendant leaves are in $,,. Then T' satisfies C,,, T' is smaller than T, yet BUILD(S,, C,,) does not construct a nonnull tree. Thus T together with C was not the smallest counterexample to the theorem, as supposed. As a single node cannot be counterexample to the theorem, we conclude that the theorem has no smallest counterexample. Since a counterexample, if one exists, is finite, there can be no counterexample at all, from which we conclude the theorem. Example 3. Suppose we are given the constraints (1,3)<(2,5) (1, 4)< (3, 7) (2, 6) < (4, 8) (3, 4) < (2, 6) (4, 5) < (1, 9) (7, 8) < (2, 10) (7, 8) < (7, 10) (8,10) < (5, 9). Rule (1) function of n, the number of constraints, and f, a function specifying the time needed to partition a set of constraints. We shall see that the use of the naive partitioning algorithm leads to an O(n3) implementation of BUILD. By using a more sophisticated partitioning algorithm, the overall running time can be reduced to O(n 2 log n). Moreover, by imposing the restriction that all constraints be of the form (i, ]) < (i, k), we can further reduce the running time to O(n2). Section 4 of this paper presents a database application in which problems of this restricted form arise naturally. LEMMA 2. Let f(n) be the time needed to partition a set of n constraints subject to rules (1) and (2) of the previous section. Iff is monotonically nondecreasing, then the time consumed by BUILD when applied to a set of n constraints is O(nf(n)). Proof. The worst-case running time occurs when the algorithm succeeds in synthesizing a nonnull tree, so we shall restrict our attention to analyzing this case. We shall proceed by assigning a cost to each node of the tree and summing the costs. Since the top level call on BUILD involves n constraints, each of which can introduce at most 4n leaves into the tree, the synthesized tree has at most 4n leaves. (Leaves not mentioned in any constraint can be made children of the root of the final tree.) Because the branching factor at each internal node is at least 2, the number of internal nodes cannot exceed 4n 1. At each internal node, BUILD partitions some subset of the original constraints and then spends a constant amount of time (exclusive of recursive calls) processing each block of the partition. Since f is monotonic, f(n) is certainly an upper bound on the cost of performing each partition. Moreover, since f must grow at least linearly with its argument, we can neglect the cost of distributing the constraints over the blocks of the partition when compared with f(n) and charge each internal node O(f(n)) units of time. Thus the time charged to all internal nodes is O((4n 1)f(n)) O(nf(n)). Since BUILD spends a constant amount of time at each leaf, the contribution of the leaves to the running time is O(n) for a total over all nodes of O(nf(n)). 71 The problem of producing a fast implementation of BUILD thus reduces to one of producing a fast partitioning algorithm. Let us first address this problem for the special case mentioned earlier. Proof. By Lemma 2, it suffices to show how to partition a set of n constraints in O(n) time. When all constraints are of the form (i, ])< (i, k), rule (2) of the partition constructing algorithm of 2 need never be applied explicitly. To see this, suppose that and k are in the same block. By rule (1), and ] must also be in the same block, and thus by transitivity, i, ], and k are all in the same block. Accordingly, it suffices to implement rule (1) alone. If we take each leaf appearing in one or more constraints to be a node, and each constraint (i, ]) < (i, k) Proof. By Lemma 2, it suffices to show how to partition a set of n constraints in O(n log n) time. Blocks of the partition will be maintained using a set merging algorithm that supports the following operations" (1) Given an element i, find the set that currently belongs to. (2) Given two sets, merge them together and assign them a common name. Fig. 4 . Before proceeding, notice that each constraint gives rise to one command, which is immediately placed on O in step (2), and two copies of an implication, say p q =), r s, which are placed on different lists. At most one of these copies will eventually cause the command r s to be placed on Q, and this will happen when a merge operation first causes p and q to become elements of the same block. Thus the total number of commands enqueued is at most 2n (n in step (2) and n in step (3)). The time spent in steps (1) and (2) is clearly O(n). The time expended by the inner for loop of Step (3) is O(n log n) because each copy of an implication is only considered in this loop when it is being moved from a shorter to a longer list. Since no more than n-1 merges can be performed, no implication can be moved more than log: n-1 times. Thus the amount of work done in the inner for loop is O(n log n). The time spent in the rest of step (3), exclusive of the inner for loop, is expended in removing at most 2n commands from Q, doing at most O(n) finds and comparisons, and performing at most n 1 merges. This clearly requires O(n log n) time, and so the total time used by the algorithm in O(n log n). 71 Extensions. The tree synthesis algorithm of 2 and 3 can be extended to handle a more general set of constraints than the ones considered so far. More specifically, we can handle any collection of constraints of the following types' (1) (i, j) < (k, l), (2) (i,/') _-< (k, l), (3) (i, j)= (k, l) (4) (i, j) is comparable to (k, l), (5) (i, j) is incomparable to (k, l). In the above constraints, two nodes of a tree are said to be comparable if one is the ancestor of the other, and incomparable otherwise. As before, there exists a set of rules for partitioning the leaves of the tree into disjoint sets so that the leaves in each set are descendants of a different child of the root. The appropriate set of rules are" (1) If (i, ])< (k, l) is a constraint, then and/" are in the same block of rc. (6) If (i, ]) is incomparable to (k, l) is a constraint, then is in the same block as ], and k is in the same block as I. (7) No two leaves are in the same block of 7rc unless it follows from (1) through (6). These rules can shown to be both necessary and sufficient conditions for constructing a tree obeying a set of constraints (if one exists) using the procedure BUILD. Each rule involves adding one case to each of Theorem 1 and Lemma 1. A straightforward modification of the partitioning algorithm in 3 allows us to handle this wider class of constraints without increasing the running time claimed in Theorem 3. For a further generalization of this problem, see [6] . In [3] it was shown that the value of an SPJ-expression can be represented in terms of a two-dimensional matrix called a tableau. A join-minimization procedure for SPJ-expressions was outlined in which a tableau is constructed from a given SPJexpression E. The tableau is then transformed into an equivalent minimum row tableau. From this minimum row tableau we can then construct an SPJ-expression that has the fewest joins of any relational expression equivalent to the original expression E. Unfortunately relation is just the "current value" of a relation scheme. The relation is said to be defined on the set of attributes of the relation scheme. The operators select, project and join are defined as follows. (1) Select. Let r be a relation on a set of attributes X, A an attribute in X, and c a value from the domain of A. Then the selection A c applied to r, written O'A= (r), is the subset of r having value c for attribute A. (2) Project. Let r be a relation on a set of attributes X. Let Y be a subset of X. We define y(r), the projection of r onto Y, to be the relation obtained by removing all the components of the tuples of r that do not belong to Y and removing duplicate tuples. Representation oI SPJ-expressions by tableaux. Given an SPJ-expression E, we can construct a tableau T to represent the expression in the following manner. The construction proceeds inductively on the form of E. (1) If E is a single relation scheme R, then the tableau T for E has one row and a summary such that: (i) If A is an attribute in R, then in the column for A tableau T has the same
In particular, Aho et al. REF presented an algorithm that, given a set of ordinal constraints ahead of time, finds a tree consistent with the constraints (or determines that none exists).
Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational Expressions
SIAM J. Comput.
SIAM J. Comput.
Mathematics Computer Science