M. Studeny: Conditional independence relations have no finite complete characterization. In Information Theory, Statistical Decision Functions and Random Processes. Transactions of the 11th Prague Conference vol. B (S. Kubik, J.A. Visek eds.), Kluwer, Dordrecht - Boston - London (also Academia, Prague) 1992, pp. 377-396.

The hypothesis of existence of a finite characterization of conditional independence relations (= structures) is refused. This result is shown to be equivalent to the non-existence of a simple deductive system describing relationships among conditional independence statements (it is a certain type of syntactic description). However, under the assumption that the conditional independence relations are grasped the existence of a countable characterization of conditional independence relations is proved. Finally, the problem of characterization of conditional independence relations is shown to be diverse from an analogical problem of axiomatization of embedded multivalued dependencies arising in the theory of relational databases.

AMS classification 68T30, 03B30, 60A05, 68P15

stochastic conditional independence
syntactic description of conditional independence
embedded multivalued dependency

A pdf copy (converted postscript version) (253kB) is available.

The paper is motivated by the problem raised in the following work:

The paper builds on the following works: