Answering conjunctive queries in the $\mathcal{SHIQ}$ description logic

Birte GlimmBirte Glimm, Carsten LutzCarsten Lutz, Ian HorrocksIan Horrocks, Ulrike SattlerUlrike Sattler

$Answering conjunctive queries in the $\mathcal{SHIQ}$ description logic$

Download

Birte Glimm, Carsten Lutz, Ian Horrocks, Ulrike Sattler
Answering conjunctive queries in the $\mathcal{SHIQ}$ description logic
In Manuela {Veloso}, eds., Proceedings of the Twentieth International Joint Conference on Artificial Intelligence (IJCAI'07), 299--404, 2007. AAAI Press

Details
Bibtex

KurzfassungAbstract
Conjunctive queries play an important role as an expressive query

 language for Description Logics (DLs). Although modern DLs
 usually provide for transitive roles, it was an open problem whether
 conjunctive query answering over DL knowledge bases is decidable if
 transitive roles are admitted in the query. In this paper, we
 consider conjunctive queries over knowledge bases formulated in the
 popular DL SHIQ and allow transitive roles in both the query and
 the knowledge base. We show that query answering is decidable and
 establish the following complexity bounds: regarding combined
 complexity, we devise a deterministic algorithm for query answering
 that needs time single exponential in the size of the KB and double
 exponential in the size of the query. Regarding data complexity, we

prove co-NP-completeness.

Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@inproceedings{ GliHoLuSa-07,
  author = {Birte {Glimm} and Carsten {Lutz} and Ian {Horrocks} and Ulrike {Sattler}},
  booktitle = {Proceedings of the Twentieth International Joint Conference on Artificial Intelligence (IJCAI'07)},
  editor = {Manuela {Veloso}},
  pages = {299--404},
  publisher = {AAAI Press},
  title = {Answering conjunctive queries in the $\mathcal{SHIQ}$ description logic},
  year = {2007},
}