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 
References
- [CFP]
- Marco A. Casanova, Ronald Fagin, Christos H. Papadimitriou:
Inclusion Dependencies and Their Interaction with Functional Dependencies.
PODS 1982: 171-176
- [CV]
- Marco A. Casanova, Vânia Maria Ponte Vidal:
Towards a Sound View Integration Methodology.
PODS 1983: 36-47
- [Co]
- E. F. Codd:
Extending the Database Relational Model to Capture More Meaning.
ACM Trans. Database Syst. 4(4): 397-434(1979)
- [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)
- [D]
- C. J. Date:
Referential Integrity.
VLDB 1981: 2-12
- [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)
- [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
- [JK]
- David S. Johnson, Anthony C. Klug:
Testing Containment of Conjunctive Queries Under Functional and Inclusion Dependencies.
PODS 1982: 164-169
- [KCV]
- Paris C. Kanellakis, Stavros S. Cosmadakis, Moshe Y. Vardi:
Unary Inclusion Dependencies have Polynomial Time Inference Problems (Extended Abstract).
STOC 1983: 264-277
- [K]
- Paris C. Kanellakis:
On the Computational Complexity of Cardinality Constraints in Relational Databases.
Inf. Process. Lett. 11(2): 98-101(1980)
- [LMG]
- Kent Laver, Alberto O. Mendelzon, Marc H. Graham:
Functional Dependencies on Cyclic Database Schemes.
SIGMOD Conference 1983: 79-91
- [M]
- John C. Mitchell:
The Implication Problem for Functional and Inclusion Dependencies.
Information and Control 56(3): 154-173(1983)
- [Sc]
- Edward Sciore:
Inclusion Dependencies and the Universal Instance.
PODS 1983: 48-57
- [SS]
- John Miles Smith, Diane C. P. Smith:
Database Abstractions: Aggregation.
Commun. ACM 20(6): 405-413(1977)
Last update Fri Sep 14 17:28:24 2012
CET by the DBLP Team — 
Data released under the ODC-BY 1.0 license — See also our legal information page
