Efficiently Computable Datalog^E Programs

Marco Manna

Info

Date	8th May 2012 (week , Trinity Term 2012)
Time	11:30
Place	147

Abstract

Datalog^E 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^E undecidable, in the general case. The results presented in this talk enable powerful, yet decidable and efficient reasoning (query answering) on top of Datalog^E programs. On the theoretical side, we define the class of parsimonious Datalog^E 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^E, while preserving the same (data and combined) complexity of query answering over Datalog, although the addition of existential quantifiers. On the practical side, we describe a bottom-up evaluation strategy for Shy programs. We implemented this strategy inside the DLV system, enhancing the computation by a number of optimization techniques to result in DLV^E -- a powerful system for answering conjunctive queries over Shy programs, which is profitably applicable to ontology-based query answering. Moreover, we discuss an experimental analysis that compares DLV^E with a number of state-of-the-art systems for ontology-based query answering. The results confirm the effectiveness of DLV^E.