On functional dependencies in q-Horn theories

This paper studies functional dependencies in q-Horn theories, and discusse s their use in knowledge condensation. We introduce compact model-based rep resentations of q-Horn theories, analyze the structure of functional depend encies in q-Horn theories, and show that every minimal functional dependenc y in a q-Horn theory Sigma can be expressed either by a single term or by a single clause. We also prove that the set of all minimal functional depend encies in Sigma is quasi-acyclic. We then develop polynomial time algorithm s for recognizing whether a given functional dependency holds in a q-Horn t heory, which is represented either by a q-Horn CNF or as the q-Horn envelop e of a set of models. Finally, we show that every q-Horn theory has a uniqu e condensation, and can be condensed in polynomial time. (C) 2001 Elsevier Science B.V. All rights reserved.