Inferring a tree from lowest common ancestors with an application to the optimization of relational expressions 

 -  SIAM Journal on Compiting, 10(3), p.405-421, 1981 .
<br/><br/> 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. 
<br/><br/><label>Subjects--Topical Terms: </label><br/>TREE ALGORITHMS<br/>LOWEST COMMON ANCESTORS<br/>RELATIONAL DATABASES<br/>RELATIONAL ALGEBRA<br/>TABLEAUX<br/>QUERY OPTIMIZATION<br/>JOIN MINIMIZATION