Stavros S. Cosmadakis
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.
- {CFP} M.A. Casanova, R. Fagin, C.H. Papadimitriou, "Inclusion Dependencies and their Interaction with Functional Dependencies", Proc. ACM SIGACT-SIGMOD PODS (1982). (also IBM RJ3380). Google Scholar
Digital Library
- {CV} M.A. Casanova, V.M.P. Vidal, "Towards a Sound View Integration Methodology", Proc. ACM SIGACT-SIGMOD PODS (1983). Google ScholarDigital Library
- {Co} E.F. Codd, "Extending the Database Relational Model to Capture More Meaning", ACM TODS 4,4 (1980). Google ScholarDigital Library
- {ChV} A. Chandra and M.Y. Vardi, "The Implication Problem for Functional and Inclusion Dependencies is Undecidable", March 1983.Google Scholar
- {D} C. Date, "Referential Integrity", Proc. VLDB (1981).Google Scholar
- {F1} R. Fagin, "A Normal Form for Relational Databases that is Based on Domains and Keys", ACM TODS 6,3 (1981). Google ScholarDigital Library
- {F2} R. Fagin, private communication, August 1983.Google Scholar
- {GJ} M.R. Garey, D.S. Johnson, "Computers and Intractability: a Guide to the Theory of NP-Completeness", Freeman (1979). Google ScholarDigital Library
- {JK} D.S. Johnson, A. Klug, "Testing Containment of Conjunctive Queries under Functional and Inclusion Dependencies", Proc. ACM SIGACT-SIGMOD PODS (1982). Google ScholarDigital Library
- {KCV} P.C. Kanellakis, S.S. Cosmadakis, M.Y. Vardi. "Unary Inclusion Dependencies have Polynomial Time Inference Problems". Proc. 15th ACM STOC (1983). Google ScholarDigital Library
- {K} P.C. Kanellakis, "On the Computational Complexity of Cardinality Constraints in Relational Databases", IPL 11,2 (1980).Google ScholarCross Ref
- {LMG} K. Laver, A.O. Mendelzon, M.H. Graham, "Functional Dependencies on Cyclic Database Schemes". Proc. ACM SIGMOD (1983). Google ScholarDigital Library
- {M} J.C. Mitchell. "The Implication Problem for Functional and Inclusion Dependencies", Proc. ACM SIGACT-SIGMOD PODS (1983). Google ScholarDigital Library
- {Sc} E. Sciore, "Inclusion Dependencies and the Universal Instance", Proc. ACM SIGACT-SIGMOD PODS (1983). Google ScholarDigital Library
- {SS} J.M. Smith, D.C.P. Smith, "Database Abstractions: Aggregation", CACM 20,6 (1977). Google ScholarDigital Library
Recommendations
Inclusion dependencies and their interaction with functional dependencies
PODS '82: Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systemsInclusion dependencies, or INDs (which can say, for example, that every manager is an employee) are studied, including their interaction with functional dependencies, or FDs. A simple complete axiomatization for INDs is presented, and the decision ...
Extending inclusion dependencies with conditions
This paper introduces a class of conditional inclusion dependencies (CINDs), which extends inclusion dependencies (INDs) by enforcing patterns of semantically related data values. We show that CINDs are useful not only in data cleaning, but also in ...
Inclusion dependencies and their interaction with functional dependencies in SQL
Driven by the SQL standard, we investigate simple and partial inclusion dependencies (INDs) with not null constraints. Implication of simple INDs and not null constraints is not finitely axiomatizable. We propose not null inclusion dependencies (NNINDs) ...
Comments