bibtex

An algorithm is given for deciding whether a functional or a multivalued dependency &sgr; (with a right-hand side Y) is implied by a set of functional and multivalued dependencies &Sgr;. The running time of the algorithm is O(| Y |‖&Sgr;‖), where Y is the number of attributes in Y and ‖&Sgr;‖ is the size of the description of &Sgr;. 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‖&Sgr;‖) 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.