Query patterns for existential rules

In this paper we study query answering over ontologies expressed in Datalog+/–, i.e., datalog with existential variables in rule heads. Differently from previous proposals, we focus on subclasses of unions of conjunctive queries (UCQs), rather than on the whole class of UCQs. To identify subclasses of UCQs, we introduce the notion of conjunctive query pattern. Given a class of queries Q expressed by a conjunctive query pattern, we study decidability and complexity of answering queries in Q over a Datalog+/– program. In particular, we define an algorithm that, given a Datalog+/– program P and a class of queries Q, is able to compute a simplified Datalog+/– program P′ that is equivalent to P with respect to answering queries in Q. We show that such an algorithm constitutes both a theoretical and a practical interesting tool for studying query answering over ontologies expressed in terms of Datalog+/– rules.