Abstract
Datalog∃ is the extension of Datalog,
allowing existentially quantified variables in rule heads. This language
is highly expressive and enables easy and powerful knowledge-modeling,
but the presence of existentially quantified variables makes reasoning
over Datalog∃ undecidable, in the general case. The results
in this paper enable powerful, yet decidable and efficient reasoning
(query answering) on top of Datalog∃ programs.
On the theoretical side, we define the class of parsimonious
Datalog∃ programs, and show that it allows of decidable and
efficiently-computable reasoning. Unfortunately, we can demonstrate
that recognizing parsimony is undecidable. However, we single out Shy,
an easily recognizable fragment of parsimonious programs, that significantly
extends both Datalog and Linear-Datalog∃, while preserving
the same (data and combined) complexity of query answering over Datalog,
although the addition of existential quantifiers.
On the practical side, we implement a bottom-up evaluation
strategy for Shy programs inside the DLV system, enhancing the computation
by a number of optimization techniques to result in DLV∃
-- a powerful system for answering conjunctive queries over Shy programs,
which is profitably applicable to ontology-based query answering. Moreover,
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 in the benchmark domain.
Dowloads
_______________________________________________________________________________________________
|