Query Patterns for Existential Rules

Cristina Civili, Riccardo Rosati

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.
Original languageEnglish
Title of host publicationWeb Reasoning and Rule Systems
Subtitle of host publication6th International Conference, RR 2012, Vienna, Austria, September 10-12, 2012. Proceedings
PublisherSpringer Berlin Heidelberg
Number of pages16
ISBN (Electronic)978-3-642-33203-6
ISBN (Print)978-3-642-33202-9
Publication statusPublished - 2012

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Berlin Heidelberg
ISSN (Print)0302-9743

Fingerprint Dive into the research topics of 'Query Patterns for Existential Rules'. Together they form a unique fingerprint.

Cite this