dblp.uni-trier.de www.dagstuhl.de www.uni-trier.de

Functional and Inclusion Dependencies: A Graph Theoretic Approach.

Stavros S. Cosmadakis, Paris C. Kanellakis: Functional and Inclusion Dependencies: A Graph Theoretic Approach. PODS 1984: 29-37
@inproceedings{DBLP:conf/pods/CosmadakisK84,
  author    = {Stavros S. Cosmadakis and
               Paris C. Kanellakis},
  editor    = {Daniel J. Rosenkrantz and
               Ronald Fagin},
  title     = {Functional and Inclusion Dependencies: A Graph Theoretic Approach},
  booktitle = {Proceedings of the Third ACM SIGACT-SIGMOD Symposium on Principles
               of Database Systems, April 2-4, 1984, Waterloo, Ontario, Canada},
  publisher = {ACM},
  year      = {1984},
  isbn      = {0-89791-128-8},
  pages     = {29-37},
  ee        = {http://doi.acm.org/10.1145/588011.588016, db/conf/pods/CosmadakisK84.html},
  crossref  = {DBLP:conf/pods/84},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

We present a new graph theoretic approach to the implication problem for functional (FD) and inclusion (IND) dependencies. Using this methodology we prove decidability for the case of typed IND's and acyclic FD's. We provide new lower bounds for the implication of typed, acyclic IND's and FD's - NP-hardness and PSPACE-hardness for bounded domains. Finally, we show that there is no k-ary complete axiomatization for implication of FD's, even when we have pairwise consistency, i.e., all possible typed IND's hold.

Copyright © 1984 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

Daniel J. Rosenkrantz, Ronald Fagin (Eds.): Proceedings of the Third ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, April 2-4, 1984, Waterloo, Ontario, Canada. ACM 1984, ISBN 0-89791-128-8
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Online Edition: ACM Digital Library


References

[CFP]
Marco A. Casanova, Ronald Fagin, Christos H. Papadimitriou: Inclusion Dependencies and Their Interaction with Functional Dependencies. PODS 1982: 171-176 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[CV]
Marco A. Casanova, Vânia Maria Ponte Vidal: Towards a Sound View Integration Methodology. PODS 1983: 36-47 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Co]
E. F. Codd: Extending the Database Relational Model to Capture More Meaning. ACM Trans. Database Syst. 4(4): 397-434(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[ChV]
Ashok K. Chandra, Moshe Y. Vardi: The Implication Problem for Functional and Inclusion Dependencies is Undecidable. SIAM J. Comput. 14(3): 671-677(1985) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[D]
C. J. Date: Referential Integrity. VLDB 1981: 2-12 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[F1]
Ronald Fagin: A Normal Form for Relational Databases That Is Based on Domians and Keys. ACM Trans. Database Syst. 6(3): 387-415(1981) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[F2]
...
[GJ]
M. R. Garey, David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman 1979, ISBN 0-7167-1044-7
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[JK]
David S. Johnson, Anthony C. Klug: Testing Containment of Conjunctive Queries Under Functional and Inclusion Dependencies. PODS 1982: 164-169 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KCV]
Paris C. Kanellakis, Stavros S. Cosmadakis, Moshe Y. Vardi: Unary Inclusion Dependencies have Polynomial Time Inference Problems (Extended Abstract). STOC 1983: 264-277 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[K]
Paris C. Kanellakis: On the Computational Complexity of Cardinality Constraints in Relational Databases. Inf. Process. Lett. 11(2): 98-101(1980) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[LMG]
Kent Laver, Alberto O. Mendelzon, Marc H. Graham: Functional Dependencies on Cyclic Database Schemes. SIGMOD Conference 1983: 79-91 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[M]
John C. Mitchell: The Implication Problem for Functional and Inclusion Dependencies. Information and Control 56(3): 154-173(1983) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Sc]
Edward Sciore: Inclusion Dependencies and the Universal Instance. PODS 1983: 48-57 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SS]
John Miles Smith, Diane C. P. Smith: Database Abstractions: Aggregation. Commun. ACM 20(6): 405-413(1977) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Last update Fri Sep 14 17:28:24 2012 CET by the DBLP TeamThis material is Open Data Data released under the ODC-BY 1.0 license — See also our legal information page