TY - GEN

T1 - Query Patterns for Existential Rules

AU - Civili, Cristina

AU - Rosati, Riccardo

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-642-33203-6_5

DO - 10.1007/978-3-642-33203-6_5

M3 - Conference contribution

SN - 978-3-642-33202-9

T3 - Lecture Notes in Computer Science

SP - 42

EP - 57

BT - Web Reasoning and Rule Systems

PB - Springer Berlin Heidelberg

ER -