Conjunctive Query Answering for the Description Logic SHIQ

Birte Glimm, Ian Horrocks, Carsten Lutz, Ulrike Sattler

IJCAI 2007 pp. 399-404

doi:10.1613/jair.2372 /ijcai/2007/glimm2007ijcai-conjunctive/

Abstract

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.

PDF IJCAI Semantic Scholar

Cite

Text

Glimm et al. "Conjunctive Query Answering for the Description Logic SHIQ." International Joint Conference on Artificial Intelligence, 2007. doi:10.1613/jair.2372

Markdown

[Glimm et al. "Conjunctive Query Answering for the Description Logic SHIQ." International Joint Conference on Artificial Intelligence, 2007.](https://mlanthology.org/ijcai/2007/glimm2007ijcai-conjunctive/) doi:10.1613/jair.2372

BibTeX

@inproceedings{glimm2007ijcai-conjunctive,
  title     = {{Conjunctive Query Answering for the Description Logic SHIQ}},
  author    = {Glimm, Birte and Horrocks, Ian and Lutz, Carsten and Sattler, Ulrike},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year      = {2007},
  pages     = {399-404},
  doi       = {10.1613/jair.2372},
  url       = {https://mlanthology.org/ijcai/2007/glimm2007ijcai-conjunctive/}
}