The Implication Problem for Functional and Inclusion Dependencies is Undecidable
- 1 August 1985
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 14 (3) , 671-677
- https://doi.org/10.1137/0214049
Abstract
The implication problem for a class of dependencies is the following: given a finite set of dependencies, determine if they logically imply another dependency. We show that the implication problem is undecidable for the class of functional and inclusion dependencies. This holds true even if the inclusion dependencies are restricted to be binary. It may be noted that the implication problem is known to be decidable for functional and unary inclusion dependencies and also for inclusion dependencies without functional dependencies.Keywords
This publication has 10 references indexed in Scilit:
- The word problem for cancellation semigroups with zeroThe Journal of Symbolic Logic, 1984
- Inclusion dependencies and their interaction with functional dependenciesJournal of Computer and System Sciences, 1984
- The implication and finite implication problems for typed template dependenciesJournal of Computer and System Sciences, 1984
- Testing containment of conjunctive queries under functional and inclusion dependenciesJournal of Computer and System Sciences, 1984
- Formal Systems for Tuple and Equality Generating DependenciesSIAM Journal on Computing, 1984
- Armstrong databases for functional and inclusion dependenciesInformation Processing Letters, 1983
- A normal form for relational databases that is based on domains and keysACM Transactions on Database Systems, 1981
- Computational problems related to the design of normal form relational schemasACM Transactions on Database Systems, 1979
- Synthesizing third normal form relations from functional dependenciesACM Transactions on Database Systems, 1976
- Recursive Unsolvability of a problem of ThueThe Journal of Symbolic Logic, 1947