Causality and Minimal Supports in Recursive Datalog

Abstract

Recursive rule evaluation can make explanation harder than in nonrecursive query answering. For fixed unions of conjunctive queries, each explanation is bounded by the query body. For recursive rules, the same answer may depend on large supports, and the number of minimal supports may be exponential in the input. We study this gap through deletion-based explanation, using inclusion-minimal endogenous input facts that entail the atom together with fixed background facts. We organize these supports as a hypergraph and prove that it determines actual causes, counterfactual causes, responsibility, and deletion robustness. The resulting view separates nonrecursive queries from recursive Datalog at the level of minimal input explanations. For positive-length reachability, minimal supports are exactly simple directed paths, and deletion robustness is the minimum directed edge cut. We also prove invariance under fixed-goal equivalent positive Datalog programs and an NP-hardness calibration for the robustness threshold problem.