Inferring a tree from lowest common ancestors with an application to the optimization of relational expressions. Aho, A. V., Sagiv, Y., Szymanski, T. G., & Ullman, J. D. SIAM J Comput, 10(3):405–421, 1981. doi abstract bibtex 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.
@Article{aho81inferring,
author = {Alfred V. Aho and Yehoshua Sagiv and Thomas G. Szymanski and Jeffrey D. Ullman},
title = {Inferring a tree from lowest common ancestors with an application to the optimization of relational expressions},
journal = {SIAM J Comput},
year = {1981},
volume = {10},
number = {3},
pages = {405--421},
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.},
doi = {10.1137/0210030},
keywords = {phylogenetics},
}
Downloads: 0
{"_id":"6CG6wjQqoXe9CbSwH","bibbaseid":"aho-sagiv-szymanski-ullman-inferringatreefromlowestcommonancestorswithanapplicationtotheoptimizationofrelationalexpressions-1981","authorIDs":[],"author_short":["Aho, A. V.","Sagiv, Y.","Szymanski, T. G.","Ullman, J. D."],"bibdata":{"bibtype":"article","type":"article","author":[{"firstnames":["Alfred","V."],"propositions":[],"lastnames":["Aho"],"suffixes":[]},{"firstnames":["Yehoshua"],"propositions":[],"lastnames":["Sagiv"],"suffixes":[]},{"firstnames":["Thomas","G."],"propositions":[],"lastnames":["Szymanski"],"suffixes":[]},{"firstnames":["Jeffrey","D."],"propositions":[],"lastnames":["Ullman"],"suffixes":[]}],"title":"Inferring a tree from lowest common ancestors with an application to the optimization of relational expressions","journal":"SIAM J Comput","year":"1981","volume":"10","number":"3","pages":"405–421","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.","doi":"10.1137/0210030","keywords":"phylogenetics","bibtex":"@Article{aho81inferring,\n author = {Alfred V. Aho and Yehoshua Sagiv and Thomas G. Szymanski and Jeffrey D. Ullman},\n title = {Inferring a tree from lowest common ancestors with an application to the optimization of relational expressions},\n journal = {SIAM J Comput},\n year = {1981},\n volume = {10},\n number = {3},\n pages = {405--421},\n 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.},\n doi = {10.1137/0210030},\n keywords = {phylogenetics},\n}\n\n","author_short":["Aho, A. V.","Sagiv, Y.","Szymanski, T. G.","Ullman, J. D."],"key":"aho81inferring","id":"aho81inferring","bibbaseid":"aho-sagiv-szymanski-ullman-inferringatreefromlowestcommonancestorswithanapplicationtotheoptimizationofrelationalexpressions-1981","role":"author","urls":{},"keyword":["phylogenetics"],"metadata":{"authorlinks":{}}},"bibtype":"article","biburl":"https://git.bio.informatik.uni-jena.de/fleisch/literature/raw/master/group-literature.bib","creationDate":"2019-11-19T16:50:41.422Z","downloads":0,"keywords":["phylogenetics"],"search_terms":["inferring","tree","lowest","common","ancestors","application","optimization","relational","expressions","aho","sagiv","szymanski","ullman"],"title":"Inferring a tree from lowest common ancestors with an application to the optimization of relational expressions","year":1981,"dataSources":["C5FtkvWWggFfMJTFX"]}