Testing Containment of Conjunctive Queries Under Functional and Inclusion Dependencies.

David S. Johnson, Anthony C. Klug: Testing Containment of Conjunctive Queries Under Functional and Inclusion Dependencies. PODS 1982: 164-169

@inproceedings{DBLP:conf/pods/JohnsonK82,
  author    = {David S. Johnson and
               Anthony C. Klug},
  title     = {Testing Containment of Conjunctive Queries Under Functional and
               Inclusion Dependencies},
  booktitle = {Proceedings of the ACM Symposium on Principles of Database Systems,
               March 29-31, 1982, Los Angeles, California},
  publisher = {ACM},
  year      = {1982},
  pages     = {164-169},
  ee        = {http://doi.acm.org/10.1145/588111.588138, db/conf/pods/JohnsonK82.html},
  crossref  = {DBLP:conf/pods/82},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

BibTeX

Abstract

We consider the problem of optimizing conjunctive queries in the presence of inclusion and functional dependencies. We show that the problem of containment (and hence those of equivalence and non-minimality) is in NP when either (a) there are no functional dependencies or (b) the set of dependencies is what we call key-based. These results assume that infinite databases are allowed. If only finite databases are allowed, new containments may arise, as we illustrate by an example. We also prove a "compactness" theorem that shows that no such examples can exist for case (b).

Copyright © 1982 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 ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
UNIX/LINUX/Mac: use mount point /pods8298/... or /cdrom/...

Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
UNIX/LINUX/Mac: use mount point /aDVD1/... or /cdrom/...

BibTeX

Printed Edition

Proceedings of the ACM Symposium on Principles of Database Systems, March 29-31, 1982, Los Angeles, California. ACM 1982
Contents BibTeX

Online Edition: ACM Digital Library

References

[1]: Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman: Equivalences Among Relational Expressions. SIAM J. Comput. 8(2): 218-246(1979) BibTeX
[2]: Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman: Efficient Optimization of a Class of Relational Expressions. ACM Trans. Database Syst. 4(4): 435-454(1979) BibTeX
[3]: Marco A. Casanova, Ronald Fagin, Christos H. Papadimitriou: Inclusion Dependencies and Their Interaction with Functional Dependencies. PODS 1982: 171-176 BibTeX
[4]: Ashok K. Chandra, Harry R. Lewis, Johann A. Makowsky: Embedded Implicational Dependencies and their Inference Problem. STOC 1981: 342-354 BibTeX
[5]: Ashok K. Chandra, Philip M. Merlin: Optimal Implementation of Conjunctive Queries in Relational Data Bases. STOC 1977: 77-90 BibTeX
[6]: E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) BibTeX
[7]: E. F. Codd: Extending the Database Relational Model to Capture More Meaning. ACM Trans. Database Syst. 4(4): 397-434(1979) BibTeX
[8]: Ronald Fagin: A Normal Form for Relational Databases That Is Based on Domians and Keys. ACM Trans. Database Syst. 6(3): 387-415(1981) BibTeX
[9]: David S. Johnson, Anthony C. Klug: Optimizing Conjunctive Queries When Attribute Domains Are not Disjoint (Extended Abstract). FOCS 1981: 203-211 BibTeX
[10]: Anthony C. Klug: Entity-Relationship Views over Uninterpreted Enterprise Schemas. ER 1979: 39-60 BibTeX
[11]: David Maier, Alberto O. Mendelzon, Yehoshua Sagiv: Testing Implications of Data Dependencies. ACM Trans. Database Syst. 4(4): 455-469(1979) BibTeX
[12]: John Miles Smith, Diane C. P. Smith: Database Abstractions: Aggregation. Commun. ACM 20(6): 405-413(1977) BibTeX
[13]: Carlo Zaniolo: Design of Relational Views over Network Schemas. SIGMOD Conference 1979: 179-190 BibTeX

Referenced by

Yannis E. Ioannidis, Raghu Ramakrishnan: Containment of Conjunctive Queries: Beyond Relations as Sets. ACM Trans. Database Syst. 20(3): 288-324(1995)
Matthias Jarke, Jürgen Koch: Query Optimization in Database Systems. ACM Comput. Surv. 16(2): 111-152(1984)
Matthias Jarke, James Clifford, Yannis Vassiliou: An Optimizing Prolog Front-End to a Relational Query System. SIGMOD Conference 1984: 296-306
Stavros S. Cosmadakis, Paris C. Kanellakis: Functional and Inclusion Dependencies: A Graph Theoretic Approach. PODS 1984: 29-37
Robert Brown, Douglas Stott Parker Jr.: LAURA: A Formal Data Model and her Logical Design Methodology. VLDB 1983: 206-218
Kent Laver, Alberto O. Mendelzon, Marc H. Graham: Functional Dependencies on Cyclic Database Schemes. SIGMOD Conference 1983: 79-91
Edward Sciore: Inclusion Dependencies and the Universal Instance. PODS 1983: 48-57
John C. Mitchell: Inference Rules for Functional and Inclusion Dependencies. PODS 1983: 58-69
Marco A. Casanova, Ronald Fagin, Christos H. Papadimitriou: Inclusion Dependencies and Their Interaction with Functional Dependencies. PODS 1982: 171-176

BibTeX

ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]