# The Complexity of Why-Provenance for Datalog Queries

**Authors:** Marco Calautti, Ester Livshits, Andreas Pieris, Markus Schneider  
**arXiv:** [2303.12773](https://arxiv.org/abs/2303.12773)  
**Date:** 2023-03-22  
**Summary page:** https://www.summarizepaper.com/en/paper/2303.12773v1/

## Key points

- Explainable AI aims to understand why a database query result is obtained
- Why-provenance is a standard way to explain a query result by providing information about the witnesses to that result
- Computational complexity of why-provenance for Datalog queries remains unexplored
- Why-provenance for recursive queries, even with limited linear recursion, is an intractable problem
- Non-recursive queries are highly tractable for why-provenance
- Unambiguous proof trees are introduced to overcome arbitrary proof trees' conceptual limitations and do not affect the data complexity of the why-provenance problem
- SAT solvers can help compute why-provenance efficiently and make it applicable in practice for (recursive) Datalog queries
- Future research should provide a complete classification of the data complexity of the why-provenance problem as a dichotomy result and explore combined complexity when Datalog queries are part of input.
- Thorough experimental evaluations are necessary to better understand our SAT-based machinery's practical application potential.
- Understanding why a database query result is obtained through explainability techniques like why-provenance is crucial towards achieving Explainable AI goals in ontology-based applications using expressive database query languages like Datalog.

## Summary

The goal of Explainable AI is to understand why a database query result is obtained, especially with the increasing use of expressive database query languages like Datalog in ontology-based applications. One standard way to explain a query result is through why-provenance, which provides information about the witnesses to a query result in the form of subsets of the input database that are sufficient to derive that result. Despite decades of intensive study on why-provenance for Datalog queries, its computational complexity remains unexplored. In this work, we aim to fill this gap by pinpointing the data complexity of why-provenance for Datalog queries and key subclasses thereof. We find that why-provenance for recursive queries, even if limited to linear recursion, is an intractable problem. However, for non-recursive queries, it is highly tractable. To overcome arbitrary proof trees' conceptual limitations, we introduce the new class of unambiguous proof trees and show that they do not affect the data complexity of the why-provenance problem. Furthermore, we experimentally confirm that exploiting SAT solvers can help compute why-provenance efficiently and make it applicable in practice for (recursive) Datalog queries. Our approach's end-to-end runtime outperforms other approaches in demanding scenarios while being comparable in simpler ones. Future research should provide a complete classification of the data complexity of the why-provenance problem as a dichotomy result and explore combined complexity when Datalog queries are part of input. Additionally, more thorough experimental evaluations are necessary to better understand our SAT-based machinery's practical application potential. Overall, understanding why a database query result is obtained through explainability techniques like why-provenance is crucial towards achieving Explainable AI goals in ontology-based applications using expressive database query languages like Datalog.