Approximation Logics for Subclasses of Probabilistic Conditional Independence and Hierarchical Dependence on Incomplete Data

Probabilistic conditional independence constitutes a principled approach to handle knowledge and uncertainty in artificial intelligence, and is fundamental in probability theory and multivariate statistics. Similarly, first-order hierarchical dependence provides an expressive framework to capture the semantics of an application domain within a database system, and is essential for the design of databases. For complete data it is well known that the implication problem associated with probabilistic conditional independence is not axiomatizable by a finite set of Horn rules (Studený, Conditional independence relations have no finite complete characterization. In: Kubik, S., Visek, J. (eds.) Transactions of the 11th Prague Conference on Information Theory, Statistical Decision Functions and Random Processes, pp. 377–396. Kluwer, Dordrecht, 1992), and the implication problem for first-order hierarchical dependence is undecidable (Herrmann, Inf. Comput. 122(2):221–235, 1995). Moreover, both implication problems do not coincide (Studený, Conditional independence relations have no finite complete characterization. In: Kubik, S., Visek, J. (eds.) Transactions of the 11th Prague Conference on Information Theory, Statistical Decision Functions and Random Processes, pp. 377–396. Kluwer, Dordrecht, 1992) and neither of them is equivalent to the implication problem of some fragment of Boolean propositional logic (Sagiv et al., J. ACM 28(3):435–453, 1981). In this article, generalized saturated conditional independence and full first-order hierarchical dependence over incomplete data are investigated as expressive subclasses of probabilistic conditional independence and first-order hierarchical dependence, respectively. The associated implication problems are axiomatized by a finite set of Horn rules, and both shown to coincide with that of a propositional fragment under interpretations in the well-known approximation logic $$\mathcal{S}$$ -3. Here, the propositional variables in the set $$\mathcal{S}$$ are interpreted classically, and correspond to random variables as well as attributes on which incomplete data is not permitted to occur.