Conjunctive Query Answering for Directional Rules

This paper introduces Directional Rules, a new extension of Datalog
with existential quantifiers in rule heads in the spirit of formalisms like tuplegenerating
dependencies, Datalog+=􀀀 and 89-rules that have attracted new interest
recently. As opposed to known decidable classes of such existential rules, Directional
Rules support complex join conditions as required for expressing transitivity.
Nonetheless, the new language suggests surprisingly simple algorithms
for answering a broad class of conjunctive queries in polynomial time regarding
data complexity. In contrast, answering unrestricted conjunctive queries is undecidable,
and we propose further restrictions and more complex algorithms for
recovering decidability in the general case. Besides their immediate use for data
integration and data exchange, Directional Rules are of particular interest since
they can capture large real-world ontologies that could hitherto be modelled in
description logics only, even though they are mostly used in database-driven applications.