Fast query answering over existential rules
Nicola Leone and Marco Manna and Giorgio Terracina and Pierfrancesco Veltri
|
|
|
 |
University
of Calabria, Department of Mathematics Via P. Bucci 30B/31B - 87036 Arcavacata di Rende (CS) - ITALY |
Enhancing Datalog with existential quantification gives rise to Datalog∃, a powerful knowledge representation
language widely used in ontology-based query answering. In this setting, a conjunctive query is evaluated
over a Datalog∃ program consisting of extensional data paired with so-called "existential" rules. Due
to their high expressiveness, such rules make the evaluation of queries undecidable, even when the latter
are atomic. Decidable generalizations of Datalog existential rules have been proposed in the literature (such
as weakly-acyclic and weakly-guarded); but they pay the price of higher computational complexity, hindering
the implementation of effective systems. Conversely, the results in this paper demonstrate that it is
definitely possible to enable fast yet powerful query answering over existential rules, ensuring decidability
without any complexity overhead.
On the theoretical side, we define the class of parsimonious programs which guarantees decidability of
atomic queries. We then strengthen this class to strongly parsimonious programs ensuring decidability also
for conjunctive queries. Since parsimony is an undecidable property, we single out Shy, an easily recognizable
class of strongly parsimonious programs that generalizes Datalog while preserving its complexity even
under conjunctive query evaluation. Shy generalizes also the class of linear existential programs, while it is
uncomparable to the other main classes ensuring decidability.
On the practical side, we exploit our results to implement DLV∃, an effective system for query answering
over parsimonious existential rules. To asses its efficiency, we carry out an experimental analysis, comparing
DLV∃ against a number of state-of-the-art systems for ontology-based query answering. The results confirm
the effectiveness of DLV∃, which outperforms all other systems.
- The paper submitted to TOCL (2017)
- DLV∃: the system + the user manual
- Benchmarks for DLV∃ (Latest version)
- Benchmarks for DLV∃ (Old version)
_______________________________________________________________________________________________