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


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.



Valid XHTML 1.0 Strict