Conjunctive Queries for a Tractable Fragment of OWL1.1
Markus Krötzsch, Sebastian Rudolph, Pascal Hitzler
Conjunctive Queries for a Tractable Fragment of OWL1.1
Abstract. Despite the success of the Web Ontology Language OWL, the development of expressive means for querying OWL knowledge bases is still an open issue. In this paper, we investigate how a very natural and desirable form of queries – namely conjunctive ones – can be used in conjunction with OWL such that one of the major design criteria of the latter – namely decidability – can be retained. More precisely, we show that querying the tractable fragment EL++ of OWL 1.1 is decidable. We also provide a complexity analysis and show that querying unrestricted EL++ is undecidable.
Published at ISWC2007 (Conference paper)
Download PDF (last update: November 1st 2007)
Citation details
- Markus Krötzsch, Sebastian Rudolph, Pascal Hitzler. Conjunctive Queries for a Tractable Fragment of OWL1.1. In Karl Aberer, Key-Sun Choi, Natasha Noy, Dean Allemang, Kyung-Il Lee, Lyndon Nixon, Jennifer Golbeck, Peter Mika, Diana Maynard, Riichiro Mizoguchi, Guus Schreiber, Philippe Cudré-Mauroux, eds.: Proceedings of the 6th International Semantic Web Conference (ISWC-07), pp. 310–323. SpringerProperty "Publisher" has a restricted application area and cannot be used as annotation property by a user. 2007.
author = {Markus Kr\"{o}tzsch and Sebastian Rudolph
and Pascal Hitzler},
title = {Conjunctive Queries for a Tractable Fragment of
{OWL}~1.1},
pages = {310--323},
crossref = {iswc07}
}
@proceedings{iswc07,
editor = {Karl Aberer and Key-Sun Choi and Natasha Noy
and Dean Allemang and Kyung-Il Lee
and Lyndon Nixon and Jennifer Golbeck
and Peter Mika and Diana Maynard
and Riichiro Mizoguchi and Guus Schreiber
and Philippe Cudr\'{e}-Mauroux},
title = {Proceedings of the 6th International Semantic Web
Conference (ISWC'07)},
booktitle = {Proceedings of the 6th International Semantic Web
Conference (ISWC'07)},
publisher = {Springer},
series = {LNCS},
volume = {4825},
year = {2007}
}
Remarks
The much more recent journal paper The Complexity of Answering Conjunctive and Navigational Queries over OWL 2 EL Knowledge Bases is an extended and revised version of most of the material of this work. I suggest to read and cite this improved version instead of the older workshop publication.
I have presented this work at ISWC2007:
Some further slides on the topic are found on the page about Conjunctive Queries for EL with Role Composition (an earlier version, which later led to the journal paper).
