1;3409;0c An Algorithm for Inferring Multivalued Dependencies with an Application to Propositional Logic

An Algorithm for Inferring Multivalued Dependencies with an Application to Propositional Logic

Journal of the ACM, vol. 27, no. 2, 1980
Pages: 250-262DOI: 10.1145/322186.322190

JACM

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.