Causality and Minimal Supports in Recursive Datalog
Databases
Summary
The authors explore why explanations for answers in recursive rule systems can be more complex than in non-recursive ones. They focus on deletion-based explanations, identifying minimal sets of input facts that cause a particular result, and represent these sets using hypergraphs. They show how this approach distinguishes non-recursive queries from recursive Datalog, with specific results for reachability problems and connections to graph theory concepts. The authors also prove that some related decision problems are computationally hard.
Authors
Ratan Bahadur Thapa, Steffen Staab
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.