Abstract
Reasoning in disjunctive Datalog is computationally expensive, typically reaching co-NP-complete complexity. This paper addresses the challenge of Datalog-rewritability—transforming complex disjunctive programs into plain Datalog to leverage efficient reasoning engines. The authors prove that a program is rewritable if and only if it is equivalent to a linear disjunctive program. They introduce Weakly Linear (WL) Datalog and an iterative unfolding algorithm to achieve this transformation, demonstrating significant performance improvements on real-world ontologies.
Introduction
In Knowledge Representation, a fundamental trade-off exists between the expressiveness of a logic and the efficiency of its reasoning. Plain Datalog is highly efficient (PTIME data complexity) but lacks the power of disjunction. Disjunctive Datalog allows for "OR" statements, making it more expressive but significantly slower.
This research investigates Datalog Rewritability: the conditions under which a disjunctive program can be mathematically transformed into plain Datalog without loss of semantics. By identifying these conditions, researchers can utilize high-performance Datalog engines to solve complex reasoning tasks that were previously intractable at scale.
Theoretical Framework and Methods
The core theoretical contribution is the Linearity Characterization. The authors demonstrate that a disjunctive program is Datalog-rewritable if and only if it is equivalent to a linear disjunctive program—one where each rule contains at most one "defined" atom in its body.
To bridge the gap between theory and practice, the authors propose Weakly Linear (WL) Datalog. In WL programs, the linearity constraint is relaxed to only apply to rules that depend on disjunctive choices. They prove that all WL programs are Datalog-rewritable.
The Unfolding Procedure
To transform non-WL programs into a rewritable format, the authors developed a symbolic substitution method known as "unfolding." This iterative process simplifies complex rules until they meet the WL criteria.
Additionally, the authors introduced the $RL^\sqcup$ Ontology Profile, extending the standard OWL 2 RL language with disjunctive axioms. This allows complex ontologies to be mapped directly to WL programs for efficient processing.
Experimental Evaluation
The approach was tested using a variety of datasets, including 118 non-Horn ontologies from BioPortal, the University Ontology Benchmark (UOBM), and a disjunction-extended version of DBpedia.
Key Results
The Rewrite procedure successfully transformed approximately 34% of the tested complex programs into plain Datalog. When these rewritten programs were executed using the RDFox engine, the performance gains were substantial compared to traditional reasoners like HermiT and Pellet.
As shown in the results, the proposed approach consistently outperformed existing tools, often by several orders of magnitude. For instance, on the U01 dataset, the rewritten program was processed in under one second, while HermiT and Pellet required hundreds of seconds. Furthermore, the scalability of this method allowed for the precomputation of the massive DBpedia dataset in just 48 seconds—a task beyond the memory capacity of standard disjunctive reasoners.
Conclusion and Future Work
This work establishes linearity as the structural "sweet spot" for Datalog rewritability. While the unfolding procedure is a "best-effort" algorithm and may not find a rewrite for every program, its success on real-world ontologies is significant.
Future research directions include refining the unfolding procedure to increase its robustness and extending these techniques to even more expressive logic fragments, such as $SHIQ$. Additionally, addressing non-monotonic reasoning (e.g., negation-as-failure) remains an open challenge for this framework.
Summary updated