Efficiently Computable Datalog∃ Programs

Nicola Leone and Marco Manna and Giorgio Terracina and Pierfrancesco Veltri

 
University of Calabria - Department of Mathematics University of Calabria, Department of Mathematics
Via P. Bucci 30B/31B - 87036 Arcavacata di Rende (CS) - ITALY


  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

_______________________________________________________________________________________________
 

Valid XHTML 1.0 Strict