Conjunctive Queries for EL with Role Composition


Markus Krötzsch, Sebastian Rudolph

Conjunctive Queries for EL with Role Composition

Abstract. EL++ is a rather expressive description logic (DL) that still admits polynomial time inferencing for many reasoning tasks. Conjunctive queries are an important means for expressive querying on DL knowledge bases. In this paper, we address the problem of computing conjunctive query entailment for EL++ knowledge bases. As it turns out, querying unrestricted EL++ is actually undecidable, but we identify restrictions under which query answering becomes decidable and even tractable. To the best of our knowledge, the presented algorithm is the first to answer conjunctive queries in a description logic that admits general role inclusion axioms.

Published at DL2007 (Workshop paper)

Download PDF (last update: June 01 2007)

Citation details

  • Markus Krötzsch, Sebastian Rudolph. Conjunctive Queries for EL with Role Composition. In Proceedings of the 20th International Workshop on Description Logics (DL-07). CEUR Workshop ProceedingsProperty "Publisher" has a restricted application area and cannot be used as annotation property by a user. 2007.


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 this work. I suggest to read and cite this improved version instead of the older workshop publication.

The slides I presented at DL2007 are available online:


Description logics, Query languages