{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,22]],"date-time":"2026-10-22T01:35:28Z","timestamp":1792632928530,"version":"4.5.0"},"reference-count":12,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1981,8]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1137\/0210030","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:24:20Z","timestamp":1109226260000},"page":"405-421","source":"Crossref","is-referenced-by-count":271,"title":["Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational Expressions"],"prefix":"10.1137","volume":"10","author":[{"given":"A. V.","family":"Aho","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Y.","family":"Sagiv","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"T. G.","family":"Szymanski","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"J. D.","family":"Ullman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,13]]},"reference":[{"key":"R1","volume-title":"The design and analysis of computer algorithms","author":"Aho Alfred V.","year":"1975"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1145\/320107.320112"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1137\/0208017"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"Ashok K. Chandra, Philip M. Merlin,  Optimal implementation of conjunctive queries in relational data bases,  Conference Record of the Ninth Annual ACM Symposium on Theory of Computing (Boulder, Colo., 1977), Assoc. Comput. Mach., New York,  1977,  77\u201390 58:8576","DOI":"10.1145\/800105.803397"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1145\/362384.362685"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322228"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1137\/0202024"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"P. G. Selinger, M. M. Astrahan, D. D. Chamberlin, R. A. Lorie, T. G. Price,  Access path selection in a relational database management system,  Proc. ACM SIGMOD Conference on Management of Data, Boston, MA,  1979,  23\u201324","DOI":"10.1145\/582095.582099"},{"key":"R9","unstructured":"Jeffrey D. Ullman, Principles of database systems, Computer Science Press, Rockville, Md., 1980, 379\u201380j:680020416.68086"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1145\/320473.320479"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"M. Yannakakis, C. Papadimitriou,  Algebraic dependencies,  Proc. 21st Annual IEEE Symposium on Foundations of Computer Science,  1980,  328\u2013332","DOI":"10.1109\/SFCS.1980.10"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1145\/320071.320072"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0210030","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:34:31Z","timestamp":1787337271000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0210030"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1981,8]]},"references-count":12,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1981,8]]}},"alternative-id":["10.1137\/0210030"],"URL":"https:\/\/doi.org\/10.1137\/0210030","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1981,8]]}}}