A Proof Procedure for Data Dependencies
- 20 September 1984
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 31 (4) , 718-741
- https://doi.org/10.1145/1634.1636
Abstract
A class of dependencies, tuple and equality generating dependencies, is defined, and the chase process is generalized to deal with these dependenetes. For total dependencies the chase is an exponential ttme decision procedure for the implication problem, and in some restricted cases it can be modified to run m polynomial Ume. For nontotal dependencies the chase is only a proof procedure. However, several cases for which it is a decision procedure are shown. It is also shown that equality is redundant for deciding implication of tuple-generating dependencies, and is "almost redundant" for dec~ding implication of equality-generating dependencies.Keywords
This publication has 30 references indexed in Scilit:
- Algebraic dependenciesJournal of Computer and System Sciences, 1982
- Template DependenciesJournal of the ACM, 1982
- Subset Dependencies and a Completeness Result for a Subclass of Embedded Multivalued DependenciesJournal of the ACM, 1982
- A normal form for relational databases that is based on domains and keysACM Transactions on Database Systems, 1981
- An Equivalence Between Relational Database Dependencies and a Fragment of Propositional LogicJournal of the ACM, 1981
- Decompositions and functional dependencies in relationsACM Transactions on Database Systems, 1980
- On the menbership problem for functional and multivalued dependencies in relational databasesACM Transactions on Database Systems, 1980
- The interaction of integrity constraints in an information systemJournal of Computer and System Sciences, 1980
- 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