Stage-oe-small.jpg

Inproceedings3025: Unterschied zwischen den Versionen

Aus Aifbportal
Wechseln zu:Navigation, Suche
Zeile 13: Zeile 13:
 
{{Inproceedings
 
{{Inproceedings
 
|Referiert=True
 
|Referiert=True
|Title=Status QIO: Conjunctive Query Entailment is Decidable
+
|Title=Worst-case Optimal Reasoning for the Horn-DL Fragments of OWL 1 and 2
 
|Year=2010
 
|Year=2010
 
|Month=Mai
 
|Month=Mai
Zeile 21: Zeile 21:
 
}}
 
}}
 
{{Publikation Details
 
{{Publikation Details
|Abstract=Description Logics (DLs) are knowledge representation formalisms that provide, for example, the logical underpinning of the W3C OWL standards. Conjunctive queries (CQs), the standard query language in databases, have recently gained significant attention for querying DL knowledge bases. Several different techniques are available for a wide range of DLs. Nevertheless, for OWL DL and OWL 2, decidability of CQ entailment is an open problem. So far, the combination of nominals, inverse roles, and number restrictions caused unsolvable problems. We tackle this problem and present a decidability result for entailment of unions of CQs in a DL with all three problematic constructors. For queries with only simple roles, our result also shows decidability in the logic that underpins OWL DL and we believe that the presented results will pave the way for further progress towards CQ entailment decision procedures for OWL DL and OWL 2.
+
|Abstract=Horn fragments of Description Logics (DLs) are popular due to their beneficial trade-off between expressive power and computational complexity. Despite their  potential, and partly due to the intricate interaction of nominals (O), inverses (I) and counting (Q), such fragments had not been studied so far for the DLs SHOIQ and SROIQ that underly OWL 1 and 2.
 +
In this paper, we present a polynomial and modular translation from Horn-SHOIQ knowledge bases into Datalog, which shows that standard reasoning tasks are feasible in deterministic single exponential time. This improves over the previously known upper bounds, and contrasts the known NExpTime completeness of full SHOIQ. Thereby Horn-SHOIQ stands out as the first ExpTime-complete DL that allows simultaneously for O, I, and Q. In addition, we show that standard reasoning in Horn-SROIQ is 2ExpTime-complete.
 +
Despite their high expressiveness, both Horn-SHOIQ and Horn-SROIQ have polynomial data complexity. This makes them particularly attractive for reasoning in semantically enriched systems with large data sets. A promising first step in this direction could be achieved exploiting existing Datalog engines, along the lines of our translation.
 
|Projekt=ExpresST, ReaSem
 
|Projekt=ExpresST, ReaSem
 
|Forschungsgruppe=Wissensmanagement
 
|Forschungsgruppe=Wissensmanagement
Zeile 29: Zeile 31:
 
}}
 
}}
 
{{Forschungsgebiet Auswahl
 
{{Forschungsgebiet Auswahl
|Forschungsgebiet=Entscheidbarketisprobleme
+
|Forschungsgebiet=Komplexitätstheorie
 
}}
 
}}
 
{{Forschungsgebiet Auswahl
 
{{Forschungsgebiet Auswahl
Zeile 35: Zeile 37:
 
}}
 
}}
 
{{Forschungsgebiet Auswahl
 
{{Forschungsgebiet Auswahl
|Forschungsgebiet=Modelltheorie
+
|Forschungsgebiet=Logikprogrammierung
 
}}
 
}}

Version vom 22. Januar 2010, 16:59 Uhr


Worst-case Optimal Reasoning for the Horn-DL Fragments of OWL 1 and 2


Worst-case Optimal Reasoning for the Horn-DL Fragments of OWL 1 and 2



Published: 2010 Mai

Buchtitel: Principles of Knowledge Representation and Reasoning: Proceedings of the Eleventh International Conference
Verlag: AAAI Press

Referierte VeröffentlichungNote: to appear

BibTeX

Kurzfassung
Horn fragments of Description Logics (DLs) are popular due to their beneficial trade-off between expressive power and computational complexity. Despite their potential, and partly due to the intricate interaction of nominals (O), inverses (I) and counting (Q), such fragments had not been studied so far for the DLs SHOIQ and SROIQ that underly OWL 1 and 2. In this paper, we present a polynomial and modular translation from Horn-SHOIQ knowledge bases into Datalog, which shows that standard reasoning tasks are feasible in deterministic single exponential time. This improves over the previously known upper bounds, and contrasts the known NExpTime completeness of full SHOIQ. Thereby Horn-SHOIQ stands out as the first ExpTime-complete DL that allows simultaneously for O, I, and Q. In addition, we show that standard reasoning in Horn-SROIQ is 2ExpTime-complete. Despite their high expressiveness, both Horn-SHOIQ and Horn-SROIQ have polynomial data complexity. This makes them particularly attractive for reasoning in semantically enriched systems with large data sets. A promising first step in this direction could be achieved exploiting existing Datalog engines, along the lines of our translation.


Projekt

ExpresSTReaSem



Forschungsgruppe

Wissensmanagement


Forschungsgebiet

Beschreibungslogik, Komplexitätstheorie, Logik, Logikprogrammierung