The Complexity of Why-Provenance for Datalog Queries

Explainability of AI systems requires understanding computational limits: The paper reveals that computing explanations (why-provenance) for recursive database queries is computationally intractable—meaning it becomes exponentially harder as data grows. This finding is important for responsible AI because it shows that some types of explanations may be theoretically difficult to provide at scale, which organizations need to understand when designing explainable systems.

Non-recursive queries offer a practical path forward: The research demonstrates that explanations for non-recursive queries are "highly tractable," meaning they can be computed efficiently. This suggests that responsible AI systems can achieve explainability for certain types of logical operations without prohibitive computational costs, providing a realistic starting point for implementation.

Practical solutions exist despite theoretical complexity: Despite proving that recursive query explanations are intractable in theory, the authors experimentally confirmed using SAT solvers that "making why-provenance for (recursive) Datalog queries work in practice is not an unrealistic goal." This indicates that responsible AI practitioners shouldn't abandon explainability efforts for complex systems, as engineering solutions may bridge the gap between theory and practice.

Explainability is foundational for trustworthy AI systems: The paper emphasizes that explaining why a database query produces a result is "essential" for Explainable AI, particularly in ontology-based applications. This underscores that transparency about how AI systems reach conclusions is a critical component of responsible AI development.