On the menbership problem for functional and multivalued dependencies in relational databases
- 1 September 1980
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Database Systems
- Vol. 5 (3), 241-259
- https://doi.org/10.1145/320613.320614
Abstract
The problem of whether a given dependency in a database relation can be derived from a given set of dependencies is investigated. We show that the problem can be decided in polynomial time when the given set consists of either multivalued dependencies only or of both functional and multivalued dependencies and the given dependency is also either a functional or a multivalued dependency. These results hold when the derivations are restricted not to use the complementation rule.Keywords
This publication has 8 references indexed in Scilit:
- Inferences of multivalued dependencies in fixed and undetermined universesTheoretical Computer Science, 1980
- Decision Problems for Multivalued Dependencies in Relational DatabasesSIAM Journal on Computing, 1979
- Computational problems related to the design of normal form relational schemasACM Transactions on Database Systems, 1979
- On Axiomatizing Multivalued Dependencies in Relational DatabasesJournal of the ACM, 1979
- Functional Dependencies in a Relational Database and Propositional LogicIBM Journal of Research and Development, 1977
- Multivalued dependencies and a new normal form for relational databasesACM Transactions on Database Systems, 1977
- A complete axiomatization for functional and multivalued dependencies in database relationsPublished by Association for Computing Machinery (ACM) ,1977
- Synthesizing third normal form relations from functional dependenciesACM Transactions on Database Systems, 1976