{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,5]],"date-time":"2026-10-05T18:54:06Z","timestamp":1791226446092,"version":"4.1.0"},"reference-count":27,"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":[[1979,5]]},"abstract":"<jats:p>Many database queries can be formulated in terms of expressions whose operands represent tables of information (relations) and whose operators are the relational operations select, project, and join. This paper studies the equivalence problem for these relational expressions, with expression optimization in mind. A matrix, called a tableau, is proposed as a natural representative for the value of an expression. It is shown how tableaux can be made to reflect functional dependencies among attributes. A polynomial time algorithm is presented for the equivalence of tableaux that correspond to an important subset of expressions, although the equivalence problem is shown to be NP-complete under slightly more general circumstances.<\/jats:p>","DOI":"10.1137\/0208017","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:03:31Z","timestamp":1109225011000},"page":"218-246","source":"Crossref","is-referenced-by-count":255,"title":["Equivalences among Relational Expressions"],"prefix":"10.1137","volume":"8","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":"J. D.","family":"Ullman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,13]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"A. V. Aho, C. Beeri, J. D. Ullman,  The theory of joins in relational databases (extended abstract),  18th Annual Symposium on Foundations of Computer Science (Providence, R.I., 1977), IEEE Comput. Sci., Long Beach, Calif.,  1977,  107\u2013113 MR0489101","DOI":"10.1109\/SFCS.1977.33"},{"key":"R2","volume-title":"The design and analysis of computer algorithms","author":"Aho Alfred V.","year":"1975"},{"key":"R3","volume-title":"Design and optimization of compilers (Courant Comput. Sci. Sympos. 5, New York Univ., New York, 1971)","author":"Aho A. V.","year":"1972"},{"key":"R4","first-page":"580","volume-title":"Information processing 74 (Proc. IFIP Congress, Stockholm, 1974)","author":"Armstrong W. W.","year":"1974"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1145\/320493.320489"},{"key":"R6","unstructured":"P. A. Bernstein, C. Beeri,  An algorithmic approach to normalization of relational database schemes, TR, CSRG-73, Computer Science Research Group, University of Toronto,  1976, Sept."},{"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,  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 MR0489103","DOI":"10.1145\/800105.803397"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1145\/362384.362685"},{"key":"R10","first-page":"33","volume-title":"Data Base Systems","author":"Codd E. F.","year":"1972"},{"key":"R11","first-page":"65","volume-title":"Data Base Systems","author":"Codd E. F.","year":"1972"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"S. A. Cook,  The complexity of theorem proving procedures,  Proc. 3rd Annual ACM Symposium on Theory of Computing,  1971,  151\u2013158, May 0253.68020","DOI":"10.1145\/800157.805047"},{"key":"R13","volume-title":"An Introduction to Database Systems","author":"Date C. J.","year":"1977"},{"key":"R14","unstructured":"C. Delobel, Ph.D. Thesis,  Contributions theor\u00e9tiques \u00e0 la conception d'un syst\u00e8me d'informations, Univ. of Grenoble,  1973, Oct."},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1145\/320557.320571"},{"key":"R16","volume-title":"Computers and intractability","author":"Garey Michael R.","year":"1979"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1147\/rd.203.0244"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"J. Minker,  Performing inferences over relational databases,  Proc. ACM SIGMOD International Conference on Management of Data, San Jose, California,  1975,  79\u201391, May","DOI":"10.1145\/500080.500092"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2694-6_4"},{"key":"R21","unstructured":"R. M. Pecherer,  Efficient evaluation of expressions in a relational algebra,  Proc. ACM Pacific Conf.,  1975,  44\u201349, April"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1145\/320576.320580"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1145\/361020.361025"},{"key":"R24","unstructured":"M. Stonebraker, L. A. Rowe,  Observations on data manipulation languages and their embedding in general purpose programming languages, 2 TR UCB\/ERL M77-53, University of California, Berkeley,  1977, July"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1145\/320473.320479"},{"key":"R26","unstructured":"C. Zaniolo,  Analysis and design of relational schemata for database systems, Tech. Rept., UCLA-ENG-7769, Department of Computer Science, UCLA,  1976, July"},{"key":"R27","doi-asserted-by":"crossref","unstructured":"M. M. Zloof,  Query-by-Example: the invocation and definition of tables and forms,  Proc. ACM International Conf. on Very Large Data Bases,  1975,  1\u201324, Sept.","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\/0208017","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:30:24Z","timestamp":1787337024000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0208017"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1979,5]]},"references-count":27,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1979,5]]}},"alternative-id":["10.1137\/0208017"],"URL":"https:\/\/doi.org\/10.1137\/0208017","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1979,5]]}}}