Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational Expressions

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.