Two Upper Bounds for Conjunctive Query Answering in SHIQ

From International Center for Computational Logic

Toggle side column

Two Upper Bounds for Conjunctive Query Answering in SHIQ

Carsten LutzCarsten Lutz
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
  • 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: Automatentheorie
@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},
}