Conjunctive Queries for EL with Role Composition

From International Center for Computational Logic

Toggle side column

Conjunctive Queries for EL with Role Composition

Markus KrötzschMarkus Krötzsch,  Sebastian RudolphSebastian Rudolph
Conjunctive Queries for EL with Role Composition


Markus Krötzsch, Sebastian Rudolph
Conjunctive Queries for EL with Role Composition
In D. Calvanese, E. Franconi, V. Haarslev, D. Lembo, B. Motik, A.-Y. Turhan and S. Tessaris, eds., Proceedings of the 20th International Workshop on Description Logics (DL2007), volume 250 of CEUR Workshop Proceedings, June 2007. CEUR-WS.org
  • KurzfassungAbstract
    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.
  • Bemerkung: Note: A revised and extended version of this work has been published in the 2014 journal paper The Complexity of Answering Conjunctive and Navigational Queries over OWL 2 EL Knowledge Bases. It should be preferred for most purposes.
  • Forschungsgruppe:Research Group: Computational LogicComputational LogicWissensbasierte SystemeKnowledge-Based Systems
@inproceedings{KR2007,
  author    = {Markus Kr{\"{o}}tzsch and Sebastian Rudolph},
  title     = {Conjunctive Queries for {EL} with Role Composition},
  editor    = {D. Calvanese and E. Franconi and V. Haarslev and D. Lembo and B.
               Motik and A.-Y. Turhan and S. Tessaris},
  booktitle = {Proceedings of the 20th International Workshop on Description
               Logics (DL2007)},
  series    = {CEUR Workshop Proceedings},
  volume    = {250},
  publisher = {CEUR-WS.org},
  year      = {2007},
  month     = {June}
}