Stage-oe-small.jpg

Techreport3026: Unterschied zwischen den Versionen

Aus Aifbportal
Wechseln zu:Navigation, Suche
 
(Eine dazwischenliegende Version desselben Benutzers wird nicht angezeigt)
Zeile 17: Zeile 17:
 
}}
 
}}
 
{{Publikation Details
 
{{Publikation Details
|Abstract=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.
+
|Abstract=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.
 
+
|Download=TR-DirectionalRules.pdf,
 
|Projekt=ExpresST
 
|Projekt=ExpresST
 
|Forschungsgruppe=Wissensmanagement
 
|Forschungsgruppe=Wissensmanagement
 
}}
 
}}

Aktuelle Version vom 25. Mai 2012, 15:02 Uhr


Conjunctive Query Answering for Directional Rules




Published: 2012 Mai
Type: Technical Report
Institution: Institut AIFB, KIT
Erscheinungsort / Ort: Karlsruhe
Archivierungsnummer:3026

BibTeX



Kurzfassung
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.

Download: Media:TR-DirectionalRules.pdf

Projekt

ExpresST



Forschungsgruppe

Wissensmanagement


Forschungsgebiet