Inproceedings3153: Unterschied zwischen den Versionen
Sru (Diskussion | Beiträge) (Die Seite wurde neu angelegt: „{{Publikation Erster Autor |ErsterAutorNachname=Ortiz |ErsterAutorVorname=Magdalena }} {{Publikation Author |Rank=2 |Author=Sebastian Rudolph }} {{Publikation Aut…“) |
Sru (Diskussion | Beiträge) |
||
Zeile 21: | Zeile 21: | ||
{{Publikation Details | {{Publikation Details | ||
|Abstract=The high computational complexity of the expressive Description Logics (DLs) that underlie the OWL standard has motivated the study of their Horn fragments, which are usually tractable in data complexity and can also have lower combined complexity, particularly for query answering. In this paper we provide algorithms for answering conjunctive 2-way regular path queries (2CRPQs), a nontrivial generalization of plain conjunctive queries, in the Horn fragments of the DLs SHOIQ and SROIQ underlying OWL 1 and OWL 2. We show that the combined complexity of the problem is ExpTime-complete for Horn-SHOIQ and 2ExpTime-complete for the more expressive Horn-SROIQ, but is PTime-complete in data complexity for both. In contrast, even decidability of plain conjunctive queries is still open for full SHOIQ and SROIQ. These are the first completeness results for query answering in DLs with inverses, nominals, and counting, and show that for the considered logics the problem is not more expensive than standard reasoning. | |Abstract=The high computational complexity of the expressive Description Logics (DLs) that underlie the OWL standard has motivated the study of their Horn fragments, which are usually tractable in data complexity and can also have lower combined complexity, particularly for query answering. In this paper we provide algorithms for answering conjunctive 2-way regular path queries (2CRPQs), a nontrivial generalization of plain conjunctive queries, in the Horn fragments of the DLs SHOIQ and SROIQ underlying OWL 1 and OWL 2. We show that the combined complexity of the problem is ExpTime-complete for Horn-SHOIQ and 2ExpTime-complete for the more expressive Horn-SROIQ, but is PTime-complete in data complexity for both. In contrast, even decidability of plain conjunctive queries is still open for full SHOIQ and SROIQ. These are the first completeness results for query answering in DLs with inverses, nominals, and counting, and show that for the considered logics the problem is not more expensive than standard reasoning. | ||
+ | |Download=ORS-IJCAI2011-CQ4HornSROIQ.pdf, | ||
|Projekt=ExpresST | |Projekt=ExpresST | ||
|Forschungsgruppe=Wissensmanagement | |Forschungsgruppe=Wissensmanagement |
Version vom 5. Juli 2011, 11:45 Uhr
Query Answering in the Horn Fragments of the Description Logics SHOIQ and SROIQ
Query Answering in the Horn Fragments of the Description Logics SHOIQ and SROIQ
Published: 2011
Juli
Buchtitel: Proceedings of the 22nd International Joint Conference on Artificial Intelligence
Verlag: IJCAI 2011
Referierte Veröffentlichung
BibTeX
Kurzfassung
The high computational complexity of the expressive Description Logics (DLs) that underlie the OWL standard has motivated the study of their Horn fragments, which are usually tractable in data complexity and can also have lower combined complexity, particularly for query answering. In this paper we provide algorithms for answering conjunctive 2-way regular path queries (2CRPQs), a nontrivial generalization of plain conjunctive queries, in the Horn fragments of the DLs SHOIQ and SROIQ underlying OWL 1 and OWL 2. We show that the combined complexity of the problem is ExpTime-complete for Horn-SHOIQ and 2ExpTime-complete for the more expressive Horn-SROIQ, but is PTime-complete in data complexity for both. In contrast, even decidability of plain conjunctive queries is still open for full SHOIQ and SROIQ. These are the first completeness results for query answering in DLs with inverses, nominals, and counting, and show that for the considered logics the problem is not more expensive than standard reasoning.
Download: Media:ORS-IJCAI2011-CQ4HornSROIQ.pdf
Beschreibungslogik, Komplexitätstheorie, Logik