{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T08:27:08Z","timestamp":1787387228986,"version":"build-2736575974"},"reference-count":20,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1983,5]]},"abstract":"<jats:p>An important step in the optimization of queries in relational databases is minimizing the number of join operations in the evaluation of a query. It is shown that three subclasses of tableaux (including the subclass of simple tableaux) have $O(n^2 )$ time equivalence and minimization algorithms. Since tableaux are nonprocedural representations of relational expressions over select, project and join, these minimization algorithms can be used to minimize the number of join operators in expressions whose tableaux belong to one of these subclasses.<\/jats:p>","DOI":"10.1137\/0212020","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:05:53Z","timestamp":1109225153000},"page":"316-328","source":"Crossref","is-referenced-by-count":16,"title":["Quadratic Algorithms for Minimizing Joins in Restricted Relational Expressions"],"prefix":"10.1137","volume":"12","author":[{"given":"Yehoshua","family":"Sagiv","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,31]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1145\/320083.320091"},{"key":"R2","volume-title":"The design and analysis of computer algorithms","author":"Aho Alfred V.","year":"1975"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1137\/0208017"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1145\/320107.320112"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1137\/0210030"},{"key":"R6","first-page":"580","volume-title":"Information processing 74 (Proc. IFIP Congress, Stockholm, 1974)","author":"Armstrong W. W.","year":"1974"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"C. Beeri, R. Fagin, J. H. Howard,  A complete axiomatization for functional and multivalued dependencies,  Proc. ACM-SIGMOD International Conference on the Management of Data, Toronto, Canada,  1977,  47\u201361, August","DOI":"10.1145\/509404.509414"},{"key":"R8","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, May 58:8576","DOI":"10.1145\/800105.803397"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1145\/362384.362685"},{"key":"R10","first-page":"65","volume-title":"Data Base Systems","author":"Codd E. F.","year":"1972"},{"key":"R11","volume-title":"Computers and intractability","author":"Garey Michael R.","year":"1979"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1147\/rd.203.0244"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"J. Minker,  Performing inferences over relational databases,  Proc. ACM-SIGMOD International Conference on Management of Data, San Jose, CA,  1975,  79\u201391, May","DOI":"10.1145\/500080.500092"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2694-6_4"},{"key":"R15","unstructured":"R. M. Pecherer,  Efficient evaluation of expressions in a relational algebra,  Proc. ACM Pacific Conference, San Jose, CA,  1975,  44\u201349, April"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322221"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1145\/361020.361025"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1145\/320473.320479"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"M. Yannakakis, C. H. Papadimitriou,  Algebraic dependencies,  Proc. 21st Symposium on Foundations of Computer Science, Syracuse, N. Y.,  1980,  328\u2013332, October","DOI":"10.1109\/SFCS.1980.10"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"M. M. Zloof,  Query-by-example: The invocation and definition of tables and forms,  Proc. ACM International Conference on Very Large Data Bases, New York,  1975,  1\u201324, September","DOI":"10.1145\/1282480.1282482"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0212020","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:40:42Z","timestamp":1787337642000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0212020"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1983,5]]},"references-count":20,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1983,5]]}},"alternative-id":["10.1137\/0212020"],"URL":"https:\/\/doi.org\/10.1137\/0212020","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1983,5]]}}}