On the completeness of the semigraphoid axioms for deriving arbitrary from saturated conditional independence statements

• We study derivability of arbitrary from saturated CI statements under semigraphoids.
• We characterize completeness of the semigraphoid axioms in this problem context.
• The above results hold regardless of the semantics given to the CI statements.
• We apply the results to several interpretations of CI statements.

Conditional independence (CI) statements occur in several areas of computer science and artificial intelligence, e.g., as embedded multivalued dependencies in database theory, disjunctive association rules in data mining, and probabilistic CI statements in probability theory. Although, syntactically, such constraints can always be represented in the form I(A,B|C)I(A,B|C), with A, B, and C subsets of some universe S, their semantics is very dependent on their interpretation, and, therefore, inference rules valid under one interpretation need not be valid under another. However, all aforementioned interpretations obey the so-called semigraphoid axioms. In this paper, we consider the restricted case of deriving arbitrary CI statements from so-called saturated ones, i.e., which involve all elements of S. Our main result is a necessary and sufficient condition under which the semigraphoid axioms are also complete for such derivations. Finally, we apply these results to the examples mentioned above to show that, for these semantics, the semigraphoid axioms are both sound and complete for the derivation of arbitrary CI statements from saturated ones.