TL;DR
This paper introduces Datalog(S), a new language that extends Datalog with set manipulation capabilities, allowing for more expressive logical reasoning. They demonstrate how Datalog(S) programs can be translated into a decidable fragment of existential rules, enabling existing rule engines to solve complex reasoning problems that were previously intractable due to computational complexity.
What Problem Does This Paper Address?
Rule-based reasoning is fundamental in artificial intelligence and knowledge representation. While Datalog is a popular and efficient rule language, it lacks the expressiveness to handle certain complex logical constructs, particularly those involving sets or existential quantifiers. Extending Datalog with these features often leads to undecidability or extremely high computational complexity, making practical reasoning infeasible. Existing existential rule reasoners, while powerful, are often limited by decidable fragments that guarantee termination, restricting their applicability to problems with polynomial data complexity. This paper addresses the dilemma of either dealing with massive rule sets or being confined to simpler problems by proposing a new approach that leverages a more expressive intermediate language (Datalog(S)) to unlock complex reasoning capabilities within existing, terminating existential rule engines.
Methods
The core of the paper is the introduction of Datalog(S), a sorted logic that extends Datalog with built-in support for sets. This includes predicates like set membership ($\in$) and subset ($\subseteq$), as well as set operations like union ($\cup$). Datalog(S) rules have specific constraints to ensure that set variables are properly grounded.
The key technical contribution is a polynomial-time translation from Datalog(S) programs into a specific set of existential rules. This translation uses a set of auxiliary rules (Rsu) to simulate set operations and relationships using nulls and specific predicates like SU (Singleton Union) and getSU. The translation carefully handles set variables and operations, ensuring that the expressive power of Datalog(S) is preserved. The paper also defines an "admissible" class of existential rules that are compatible with this translation and guarantee termination of the chase procedure.
Datasets
The paper evaluates their approach using several large and diverse ontologies from the Oxford Ontology Repository, including GO x-anatomy, GO x-taxon, Gazetteer, ChEBI mol. function, and NCI. They also use benchmark datasets created by sampling data for the Reactome knowledge base and a synthetic benchmark called UOBM.
Key Insights and Ideas
- Datalog(S) as a bridge: Datalog(S) acts as a convenient, high-level language for expressing complex reasoning algorithms that are difficult to formulate directly in existential rules. This makes it an excellent tool for prototyping and developing new reasoning procedures.
- Simulating sets with existential rules: The paper demonstrates a clever way to represent and manipulate sets using a fixed set of existential rules and nulls, effectively "compiling" set-based reasoning into a standard rule-based framework.
- Unlocking expressive power within termination guarantees: By translating Datalog(S) into a specific fragment of existential rules, the authors show that complex reasoning tasks can be performed by existing rule engines while still guaranteeing termination, overcoming a major limitation of previous approaches.
- EXPTIME-complete data complexity: The paper establishes that Datalog(S) has EXPTIME-complete data complexity, which, while high, is necessary for the expressive power they achieve and aligns with the complexity of the target existential rule fragment.
Key Results
- Datalog(S) is EXPTIME-complete: The paper proves that checking fact entailment for Datalog(S) is EXPTIME-complete for both data and combined complexity.
- Polynomial translation to existential rules: A polynomial-time translation from Datalog(S) programs to a set of existential rules is presented, preserving logical consequences.
- Practical evaluation on DL reasoning: The approach was successfully applied to implement classification for Horn-ALC description logic, achieving competitive performance on large ontologies using the VLog rule engine.
- Guarded rules reasoning: The framework is shown to be applicable to reasoning with guarded existential rules, leading to a fixed existential rule set that can handle arbitrary guarded rules encoded as facts.
Limitations and Future Work
- High data complexity: While the approach enables expressive reasoning, the EXPTIME-complete data complexity means that performance can still degrade significantly with large input datasets.
- Rule engine optimization: The paper notes that while their approach enables complex reasoning, optimized DL reasoners are significantly faster. Future work could focus on further optimizing rule engines for the specific types of rules generated by their translation.
- Exploration of new fragments: The authors suggest that their work might inspire the development of new, more convenient decidable fragments of existential rules that are not covered by existing criteria.
Summary updated