Search

An algorithm is given for deciding whether a functional or a multivalued dependency σ (with a right-hand side Y ) is implied by a set of functional and multivalued dependencies Σ. The running time of the algorithm is O (| Y |‖Σ‖), where Y is the number of attributes in Y and ‖Σ‖ is the size of the description of Σ. The problem of constructing the dependency basis of a set of attributes X is also investigated. It is shown that the dependency basis can be found in O ( S ‖Σ‖) time, where S is the number of sets in the dependency basis. Since functional and multivalued dependencies correspond to a subclass of propositional logic (that can be viewed as a generalization of Horn clauses), the algorithm given is also an efficient inference procedure for this subclass of propositional logic.

It is known that there is an eqmvalence between functional dependencies m a relatmonal database and a certain fragment of proposmonal logic Thins eqmvalence is extended to include both functional and multivalued dependencmes. Thus, for each dependency there is a corresponding statement m proposmonal logic. It ms then shown that a dependency (funcuonal or multivalued) is a consequence of a set of dependencies ff and only ff the corresponding proposiuonal statement ~s a consequence of the corresponding set of proposmonal statements. Examples are given to show that these techniques are valuable mn provmdmg much shorter proofs of theorems about dependencies than have been obtained by more tradmonal means It is shown that this eqmvalence cannot be extended to include either join dependencies or embedded multmvalued dependencies.