Conditional Independence
Definition
Random variables $X$ and $Y$ are conditionally independent given $Z$ (written $X \perp\!\!\!\perp Y \mid Z$) if
$$ p(x, y \mid z) = p(x \mid z)\, p(y \mid z). $$Equivalently, $p(x \mid y, z) = p(x \mid z)$: knowing $Y$ provides no additional information about $X$ once $Z$ is known.
Role in Graphical Models
Conditional independence relationships are encoded by the structure of a DAG. The pruning algorithm determines whether $X \perp\!\!\!\perp Y \mid Z$ from the graph topology.