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. Owing to their high expressiveness, such rules make the evaluation of queries undecidable, even when the latter are atomic. Decidable generalizations of Datalog by 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 article demonstrate that it is definitely possible to enable fast yet powerful query answering over existential rules that strictly generalize Datalog by ensuring decidability without any complexity overhead. On the theoretical side, we define the class of parsimonious programs that 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 queries. Shy also generalizes 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 assess its efficiency, we carry out an experimental analysis, evaluating DLV ∃ performances for ontology-based query answering on both real-world and synthetic ontologies.

Abstract Magic sets are a Datalog to Datalog rewriting technique to optimize query answering. The rewritten program focuses on a portion of the stable model(s) of the input program which is sufficient to answer the given query. However, the rewriting may introduce new recursive definitions, which can involve even negation and aggregations, and may slow down program evaluation. This paper enhances the magic set technique by preventing the creation of (new) recursive definitions in the rewritten program. It turns out that the new version of magic sets is closed for Datalog programs with stratified negation and aggregations, which is very convenient to obtain efficient computation of the stable model of the rewritten program. Moreover, the rewritten program is further optimized by the elimination of subsumed rules and by the efficient handling of the cases where binding propagation is lost. The research was stimulated by a challenge on the exploitation of Datalog/dlv for efficient reasoning on large ontologies. All proposed techniques have been hence implemented in the dlv system, and tested for ontological reasoning, confirming their effectiveness.

Existential rules generalize Datalog with existential quantification in the head. Natively, Datalog is interpreted under a closed-world semantics, while existential rules typically employ the open-world assumption. The interpretation domain in the latter case is enlarged by infinitely many "anonymous" individuals. Then, in any rule, each variable ranges over all individuals, even if not needed or required. In this paper, we enhance existential rules by closed-world variables to consciously reason on the properties of "known" (non-anonymous) and arbitrary individuals in different ways. Accordingly, we uniformly generalize the basic classes of existential rules that ensure decidability of ontology-based query answering. For them, after observing that decidability is preserved, we prove that a strict increase in expressiveness is gained, and in most cases the computational complexity is not altered.