Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational Expressions
A. V. Aho, Yehoshua Sagiv, Thomas G. Szymanski, Jeffrey David Ullman · SIAM Journal on Computing · 1981
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.