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},
editor = {Alberto O. Mendelzon and
Z. Meral {\"O}zsoyoglu},
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,
USA},
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}
}
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 ...
Printed Edition
Alberto O. Mendelzon, Z. Meral Özsoyoglu (Eds.):
Proceedings of the Sixteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 12-14, 1997, Tucson, Arizona, USA.
ACM Press 1997, ISBN 0-89791-910-6
Contents 
[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
- [3]
- Paolo Atzeni, Giorgio Ausiello, Carlo Batini, Marina Moscarini:
Inclusion and Equivalence between Relational Database Schemata.
Theor. Comput. Sci. 19: 267-285(1982)
- [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)
- [5]
- Catriel Beeri, Philip A. Bernstein, Nathan Goodman:
A Sophisticate's Introduction to Database Normalization Theory.
VLDB 1978: 113-124
- [6]
- Catriel Beeri, Alberto O. Mendelzon, Yehoshua Sagiv, Jeffrey D. Ullman:
Equivalence of Relational Database Schemes.
SIAM J. Comput. 10(2): 352-370(1981)
- [7]
- E. F. Codd:
A Relational Model of Data for Large Shared Data Banks.
Commun. ACM 13(6): 377-387(1970)
- [8]
- ...
- [9]
- Richard Hull:
Relative Information Capacity of Simple Relational Database Schemata.
PODS 1984: 97-109
- [10]
- Richard Hull:
Relative Information Capacity of Simple Relational Database Schemata.
SIAM J. Comput. 15(3): 856-886(1986)
- [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)
- [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)
- [13]
- Renée J. Miller, Yannis E. Ioannidis, Raghu Ramakrishnan:
The Use of Information Capacity in Schema Integration and Translation.
VLDB 1993: 120-133
- [14]
- Jorma Rissanen:
On Equivalences of Database Schemes.
PODS 1982: 23-26
- [15]
- Arnon Rosenthal, David S. Reiner:
Theoretically Sound Transformations for Practical Database Design.
ER 1987: 115-131
- [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)
- [17]
- Carlo Zaniolo:
A New Normal Form for the Design of Relational Database Schemata.
ACM Trans. Database Syst. 7(3): 489-499(1982)
Last update Thu May 24 04:40:32 2012
CET by the DBLP Team — 
Data released under the ODC-BY 1.0 license — See also our legal information page
