Two Upper Bounds for Conjunctive Query Answering in SHIQ

Carsten LutzCarsten Lutz

Download

Carsten Lutz
Two Upper Bounds for Conjunctive Query Answering in SHIQ
Proceedings of the 21st International Workshop on Description Logics (DL2008), volume 353 of CEUR-WS, 2008

Details
Bibtex

KurzfassungAbstract
We have shown recently that, in extensions of ALC that involve inverse roles, conjunctive query answering is harder than satisfiability: it is 2-ExpTime-complete in general and NExpTime-hard if queries are connected and contain at least one answer variable. In this paper, we show that, in SHIQ without inverse roles (and without transitive roles in the query), conjunctive query answering is only ExpTime-complete and thus not harder than satisfiability. We also show that the mentioned NExpTime-lower bound is tight.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@inproceedings{ Lutz-DL08,
  author = {Carsten {Lutz}},
  booktitle = {Proceedings of the 21st International Workshop on Description Logics ({DL2008})},
  series = {CEUR-WS},
  title = {Two Upper Bounds for Conjunctive Query Answering in SHIQ},
  volume = {353},
  year = {2008},
}