ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Conjunctive Query Equivalence of Keyed Relational Schemas.

Joseph Albert, Yannis E. Ioannidis, Raghu Ramakrishnan: Conjunctive Query Equivalence of Keyed Relational Schemas. PODS 1997: 44-50
@inproceedings{DBLP:conf/pods/AlbertIR97,
  author    = {Joseph Albert and
               Yannis E. Ioannidis and
               Raghu Ramakrishnan},
  title     = {Conjunctive Query Equivalence of Keyed Relational Schemas},
  booktitle = {Proceedings of the Sixteenth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, May 12-14, 1997, Tucson, Arizona},
  publisher = {ACM Press},
  year      = {1997},
  isbn      = {0-89791-910-6},
  pages     = {44-50},
  ee        = {http://doi.acm.org/10.1145/263661.263667, db/conf/pods/AlbertIR97.html},
  crossref  = {DBLP:conf/pods/97},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

The notion of when two schemas are equivalent is fundamental to database design, schema integration, and data model translation. An important notion of schema equivalence, query equivalence was introduced in [3], and used to evaluate the correctness of schema transformations. The logically equivalent notion of calculous equivalence, as well as three progessively weaker notions of schema equivalence were introduced in 1984 by Hull [9, 10], who showed that two schemas with no dependencies are equivalent (under all four notions of equivalence) if and only if they are identical (up to renaming and re-ordering of attributes and relations). Hull also conjectured that the same result holds for schemas with primary keys. In this work, we resolve the conjecture in the affirmative for the case of query equivalence based on mappings using conjunctive queries with equality selections.

Copyright © 1997 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ... BibTeX

Printed Edition

Proceedings of the Sixteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 12-14, 1997, Tucson, Arizona. ACM Press 1997, ISBN 0-89791-910-6
Contents BibTeX

Online Edition: ACM Digital Library

[Index Terms]
[Full Text in PDF Format, 1218 KB]

References

[1]
...
[2]
Adarsh K. Arora, C. Robert Carlson: The Information Preserving Properties of Relational Database Transformations. VLDB 1978: 352-359 BibTeX
[3]
Paolo Atzeni, Giorgio Ausiello, Carlo Batini, Marina Moscarini: Inclusion and Equivalence between Relational Database Schemata. Theor. Comput. Sci. 19: 267-285(1982) BibTeX
[4]
Carlo Batini, Maurizio Lenzerini, Shamkant B. Navathe: A Comparative Analysis of Methodologies for Database Schema Integration. ACM Comput. Surv. 18(4): 323-364(1986) BibTeX
[5]
Catriel Beeri, Philip A. Bernstein, Nathan Goodman: A Sophisticate's Introduction to Database Normalization Theory. VLDB 1978: 113-124 BibTeX
[6]
Catriel Beeri, Alberto O. Mendelzon, Yehoshua Sagiv, Jeffrey D. Ullman: Equivalence of Relational Database Schemes. SIAM J. Comput. 10(2): 352-370(1981) BibTeX
[7]
E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) BibTeX
[8]
...
[9]
Richard Hull: Relative Information Capacity of Simple Relational Database Schemata. PODS 1984: 97-109 BibTeX
[10]
Richard Hull: Relative Information Capacity of Simple Relational Database Schemata. SIAM J. Comput. 15(3): 856-886(1986) BibTeX
[11]
Tok Wang Ling, Frank Wm. Tompa, Tiko Kameda: An Improved Third Normal Form for Relational Databases. ACM Trans. Database Syst. 6(2): 329-346(1981) BibTeX
[12]
David Maier, Alberto O. Mendelzon, Fereidoon Sadri, Jeffrey D. Ullman: Adequacy of Decompositions of Relational Databases. J. Comput. Syst. Sci. 21(3): 368-379(1980) BibTeX
[13]
Renée J. Miller, Yannis E. Ioannidis, Raghu Ramakrishnan: The Use of Information Capacity in Schema Integration and Translation. VLDB 1993: 120-133 BibTeX
[14]
Jorma Rissanen: On Equivalences of Database Schemes. PODS 1982: 23-26 BibTeX
[15]
Arnon Rosenthal, David S. Reiner: Theoretically Sound Transformations for Practical Database Design. ER 1987: 115-131 BibTeX
[16]
Amit P. Sheth, James A. Larson: Federated Database Systems for Managing Distributed, Heterogeneous, and Autonomous Databases. ACM Comput. Surv. 22(3): 183-236(1990) BibTeX
[17]
Carlo Zaniolo: A New Normal Form for the Design of Relational Database Schemata. ACM Trans. Database Syst. 7(3): 489-499(1982) BibTeX

Referenced by

  1. Richard Hull: Managing Semantic Heterogeneity in Databases: A Theoretical Perspective. PODS 1997: 51-61
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:34:16 2009