TL;DR
This paper tackles the challenge of answering complex queries with negation in rule-based systems by introducing new rule classes and a system called ECOMPLETO. They demonstrate that their approach can efficiently produce finite query rewritings, even for ontologies with intricate relationships.
What Problem Does This Paper Address?
Answering queries in knowledge bases often involves using rules to infer new information. Conjunctive query rewriting is a key technique for this, aiming to transform an input query into an equivalent one that doesn't require the original rules. However, this process becomes significantly more complex when dealing with:
- Disjunctive existential rules: Rules where the consequence (head) can be one of several possibilities.
- Universally quantified negation: Queries that ask "for all X, is it NOT the case that Y?". This is a tricky form of negation that makes standard query answering difficult.
The core problem is that finding a finite and complete rewriting for such complex queries is often undecidable. This means there's no guarantee that a rewriting will always exist, or that it will be finite. The paper aims to identify conditions and methods that do guarantee finite rewritings, making query answering more practical and efficient.
Methods
The paper introduces several key contributions:
- New Rule Classes: They define "connected linear rules" and "connected domain restricted rules." These are specific types of existential rules that have a desirable property: they guarantee a finite unification set (fus). A fus is a set of rules that ensures finite UCQ-rewritings for any query. These new classes are more expressive than previously known fus classes.
- Disconnected Disjunction: To extend the fus property to disjunctive existential rules, they introduce "disconnected disjunction." This concept ensures that even when rules have multiple possible outcomes (disjunctions), the rewriting process remains manageable.
- ECOMPLETO System: They present ECOMPLETO, a system implemented in Elixir, designed to perform query rewriting for UCQs with universally quantified negation within the disjunctive existential rules framework. It also extends the DLGP+ format for specifying these rules and queries.
- Algorithm 1 (rewritek/2): This algorithm is central to ECOMPLETO. It iteratively applies rewriting steps, alternating between handling existential rules and disjunctive existential rules. This process continues until a fixed point is reached, meaning no new rules or queries can be generated.
Datasets
The paper uses two ontologies for evaluation:
- Lehigh University Benchmark (LUBM): An established benchmark for OWL knowledge bases, enriched with additional axioms.
- TRAVEL ontology: A smaller ontology containing 10 disjoint class axioms.
Both ontologies were translated into existential rules for the experiments.
Key Insights and Ideas
- Bridging Undecidability: The core challenge is the inherent undecidability of finite rewritings. By introducing specific rule classes (connected linear, connected domain restricted) and the concept of disconnected disjunction, the authors provide a way to guarantee finite rewritings in many practical scenarios.
- Expressiveness vs. Fus Property: The newly introduced rule classes are more expressive than existing ones that guarantee the fus property. This means they can capture more complex relationships while still ensuring finite rewritings, offering a better trade-off.
- ECOMPLETO's Practicality: The development of ECOMPLETO demonstrates that these theoretical advancements can be translated into a working system capable of handling complex queries with negation.
- Ontology Complexity Matters: The experimental results highlight that the performance of query rewriting is significantly influenced by the complexity of the ontology. Simpler ontologies lead to much faster processing.
Key Results
- ECOMPLETO successfully produced finite UCQ-rewritings for all 500 queries generated for both the LUBM and TRAVEL ontologies.
- The rewriting process for the TRAVEL ontology was, on average, 500 times faster than for the LUBM ontology.
- The TRAVEL ontology required approximately one-third of the RAM compared to the LUBM ontology for rewriting.
- Clustering analysis of the LUBM experiments revealed distinct groups of queries based on their runtime and memory consumption, with some correlation to the size of the generated UCQ-rewriting.
Limitations and Future Work
- Fus Property Not Proven for All Ontologies: The authors state they could not prove the fus property for the existential rules derived from the LUBM and TRAVEL ontologies used in their experiments. This means that while ECOMPLETO produced finite rewritings in these cases, a theoretical guarantee for these specific rule sets was not established.
- Algorithm Termination: While Algorithm 1 is designed to terminate, the paper notes that if the set of existential rules is not a fus, the process of generating new rules could potentially continue indefinitely. The paper relies on the fus property to ensure termination.
- Future Work: The paper suggests that the developed system and techniques can be further applied to more complex scenarios, including those with answer variables in queries and more intricate ontology structures. The extension of DLGP+ is also a step towards more expressive knowledge representation.
Summary updated