KIT | KIT-Bibliothek | Impressum | Datenschutz

Conjunctive Query Answering for Directional Rules

Krötzsch, Markus; Rudolph, Sebastian

Abstract:
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.

Open Access Logo


Zugehörige Institution(en) am KIT Institut für Angewandte Informatik und Formale Beschreibungsverfahren (AIFB)
Publikationstyp Forschungsbericht
Jahr 2012
Sprache Englisch
Identifikator KITopen-ID: 1000091505
Verlag KIT, Karlsruhe
Umfang 19 S.
Serie AIFB, Technical Report ; 3026
Externe Relationen Abstract/Volltext
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page