{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:25:14Z","timestamp":1787340314350,"version":"build-2736575974"},"reference-count":22,"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":[[1981,5]]},"abstract":"<jats:p>We investigate the question of when two database schemes embody the same information. We argue that this question reduces to the equivalence of the sets of fixed points of the project-join mappings associated with the two database schemes in question. When data dependencies are given, we need only consider those fixed points that satisfy the dependencies. A polynomial algorithm to test the equivalence of database schemes, when there are no dependencies, is given. We also provide an exponential algorithm to handle the case where there are functional and\/or multivalued dependencies. Furthermore, we give a polynomial time test to determine whether a project-join mapping preserves a set of functional dependencies, and a polynomial time algorithm for equivalence of database schemes whose project-join mappings do preserve the given set of functional dependencies. Lastly, we introduce the \u201cupdate sets\u201d approach to database design as an application of these results.<\/jats:p>","DOI":"10.1137\/0210025","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:24:20Z","timestamp":1109226260000},"page":"352-370","source":"Crossref","is-referenced-by-count":50,"title":["Equivalence of Relational Database Schemes"],"prefix":"10.1137","volume":"10","author":[{"given":"Catriel","family":"Beeri","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alberto O.","family":"Mendelzon","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yehoshua","family":"Sagiv","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jeffrey D.","family":"Ullman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,8,2]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1145\/320083.320091"},{"key":"R2","unstructured":"The ANSI\/X3\/SPARC framework,  1978, ANSI\/X3\/SPARC, D. Tsichritzis and A. Klug, eds., AFIPS Press"},{"key":"R3","first-page":"580","volume-title":"Information processing 74 (Proc. IFIP Congress, Stockholm, 1974)","author":"Armstrong W. W.","year":"1974"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1137\/0208017"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1145\/320107.320112"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1145\/320064.320066"},{"key":"R7","unstructured":"C. Beeri, P. Bernstein, N. Goodman,  A sophisticate's introduction to database normalization theory,  Proc. 4th Int. Conf. on Very Large Data Bases, West Berlin,  1978,  113\u2013124"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1145\/320493.320489"},{"key":"R9","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":"R10","doi-asserted-by":"publisher","DOI":"10.1145\/362384.362685"},{"key":"R11","unstructured":"E. F. Codd,  R.  Rustin,  Further normalization of the data base relational model,  Data Base Systems, Courant Computer Science Symp. 6, Prentice-Hall, Englewood Cliffs, NJ,  1972,  33\u201364"},{"key":"R12","first-page":"23","volume":"7","author":"Codd E. F.","year":"1975","journal-title":"FDT"},{"key":"R13","unstructured":"C. Delobel, Masters Thesis,  Contributions th\u00e9oretiques \u00e0 la conception et \u00e0 l'\u00e9valuation d'un syst\u00e8me d'informations appliqu\u00e9 \u00e0 la gestion, Th\u00e8se d'\u00e9tat, Univ. de Grenoble,  1973, October"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1145\/320557.320571"},{"key":"R15","volume-title":"Modelling in Data Base Management Systems","author":"Hall P.","year":"1976"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1145\/984378.984379"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1145\/320107.320115"},{"key":"R18","volume-title":"Information Processing '77","author":"Nijssen G. M.","year":"1977"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1145\/320576.320580"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-08921-7_102"},{"key":"R21","unstructured":"C. Zaniolo, Ph.D. Thesis,  Analysis and design of relational schemata for database systems, Computer Science Dept., University of California, Los Angeles,  1976, TR UCLA-ENG-7669, July"},{"key":"R22","unstructured":"C. Zaniolo,  Relational views in data base systems; support for queries,  Proc. COMPSAC 77, November 8-11, Chicago, IL,  1977"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0210025","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:29:32Z","timestamp":1787336972000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0210025"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1981,5]]},"references-count":22,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1981,5]]}},"alternative-id":["10.1137\/0210025"],"URL":"https:\/\/doi.org\/10.1137\/0210025","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1981,5]]}}}