Conjunctive Query Answering for Directional Rules

Markus KrötzschMarkus Krötzsch, Sebastian RudolphSebastian Rudolph

Markus Krötzsch, Sebastian Rudolph
Conjunctive Query Answering for Directional Rules
Technical Report, Institut AIFB, KIT, May 2012. Technical Report

Details
Bibtex

KurzfassungAbstract
This paper introduces Directional Rules, a new extension of Datalog with existential quantifiers in rule heads in the spirit of formalisms like tuple-generating dependencies, Datalog+/- and forall-exists-rules that 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.
Forschungsgruppe:Research Group: Computational LogicComputational Logic, Wissensbasierte SystemeKnowledge-Based Systems

@techreport{KR2012,
  author      = {Markus Kr{\"{o}}tzsch and Sebastian Rudolph},
  title       = {Conjunctive Query Answering for Directional Rules},
  institution = {Institut {AIFB,} {KIT}},
  year        = {2012},
  month       = {May}
}