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

Access Restriction
Subscribed

 Author Sagiv, Yehoshua Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1980 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Abstract An algorithm is given for deciding whether a functional or a multivalued dependency $\textit{&sgr;}$ (with a right-hand side $\textit{Y})$ is implied by a set of functional and multivalued dependencies &Sgr;. The running time of the algorithm is $\textit{O}(|$ $\textit{Y}$ |‖&Sgr;‖), where $\textit{Y}$ is the number of attributes in $\textit{Y}$ and ‖&Sgr;‖ is the size of the description of &Sgr;. The problem of constructing the dependency basis of a set of attributes $\textit{X}$ is also investigated. It is shown that the dependency basis can be found in $\textit{O}(\textit{S}‖&Sgr;‖)$ time, where $\textit{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. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1980-04-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 27 Issue Number 2 Page Count 13 Starting Page 250 Ending Page 262

#### Open content in new tab

Source: ACM Digital Library