The Logic of Representing Dependencies by Directed Graphs

Judea Pearl, Thomas Verma

Data-dependencies of the type "x can tell us more about y given that we already know z" can be represented in various formalisms: Probabilistic Dependencies, Embedded-Multi-Valued Dependencies, Undirected Graphs and Directed-Acyclic Graphs (DAGs). This paper provides an axiomatic basis, called a semi-graphoid which captures the structure common to all four types of dependencies and explores the expressive power of DAGs in representing various types of data dependencies. It is shown that DAGs can represent a richer set of dependencies than undirected graphs, that DAGs completely represent the closure of their specification bases, and that they offer an effective computational device for testing membership in that closure as well as inferring new dependencies from given inputs. These properties might explain the prevailing use of DAGs in causal reasoning and semantic nets.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.