Introduction
In Explainable AI (XAI), understanding the rationale behind a database query result is as critical as the result itself. For Datalog—a logic-based language central to knowledge graphs and ontologies—this is addressed through why-provenance, which identifies minimal subsets of input data sufficient to derive a specific answer. However, traditional approaches struggle with high computational complexity for recursive queries and often produce "unnatural" explanations, such as cyclic derivations. This paper presents a high-performance, incremental approach that transforms the why-provenance problem into a SAT-solving task, enabling microsecond-level explanation generation.
Methods: Unambiguous Proof Trees and SAT Encoding
The core innovation lies in structural refinement and efficient encoding. The authors introduce unambiguous proof trees, a novel constraint where every occurrence of a specific fact within a derivation tree is derived using the same rule and children. This constraint eliminates redundant or conflicting explanations and allows proof trees to be represented as compact Compressed Directed Acyclic Graphs (DAGs).
The existence of these Compressed DAGs is translated into a Boolean formula ($\phi$) that enforces consistency, rootedness (starting from the query answer), validity (adherence to Datalog rules), and acyclicity. By utilizing a SAT solver (specifically Glucose), the system can incrementally enumerate explanations. After each discovery, a "blocking clause" is added to the formula, preventing duplicate results and facilitating a fast, on-demand stream of explanations.
Experimental Evaluation
The system was evaluated across diverse Datalog scenarios, including social and financial networks (TClosure), medical data (Doctors), clinical ontologies (Galen), software verification (Andersen), and large-scale system logs (CSDA) with up to 44 million tuples.
Key results demonstrate significant improvements in speed and scalability:
- Efficiency: On-demand explanations were typically generated with microsecond delays.
- Scalability: The system successfully processed datasets with tens of millions of facts, such as the CSDA Linux dataset, where previous state-of-the-art methods often failed or timed out.
- Comparative Performance: In the Galen benchmark, the SAT-based approach completed in seconds, whereas rule-based alternatives frequently exceeded a 5-minute timeout.
Discussion and Future Work
The shift to "unambiguity" is the primary driver of efficiency, making the SAT encoding compact enough for practical use. Interestingly, the SAT solver is rarely the bottleneck; instead, most execution time is consumed by the Datalog engine (DLV) during the initial "downward closure" pre-processing step, which prunes irrelevant facts.
Future research will focus on optimizing this pre-processing bottleneck and extending the framework to more expressive logic languages, such as those incorporating negation or existential rules. Additionally, user studies are planned to empirically verify if "unambiguous" trees are indeed more intuitive for human users compared to standard provenance models.
Summary updated