Published: 2012 Mai
Type: Technical Report
Institution: Institut AIFB, KIT
Erscheinungsort / Ort: Karlsruhe
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 both data and program 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.