Magdalena Ortiz, Mantas Šimkus, Thomas Eiter:
Worst-case Optimal Conjunctive Query Answering for an
Expressive Description Logic without Inverses.
Abstract
Answering conjunctive queries (CQs) has been recognized as a
key task for the usage of Description Logics (DLs) in a number of
applications, and has thus been studied by many authors. In this paper, we
present an algorithm for this problem in the DL ALCH which works in
exponential time. It improves over previous algorithms which require
double exponential time and is worst-case optimal, as already
satisfiability testing in ALC is ExpTime-complete. Furthermore, it shows
that inverse roles cause an exponential jump in complexity; as recently
shown, the problem is 2ExpTime-complete for ALCI. The algorithm is based
on a technique that compiles knowledge bases into sets of trees of depth
1. It is in coNP under data complexity (i.e., if the taxonomy part and the
query are fixed), thus worst-case optimal. An extension from ALCH to DLs
with further constructs is possible.
URL:
http://rewerse.net/publications/rewerse-publications.html#REWERSE-RP-2008-028
@inproceedings{REWERSE-RP-2008-028, author = {Magdalena Ortiz and Mantas Šimkus and Thomas Eiter}, title = {Worst-case Optimal Conjunctive Query Answering for an Expressive Description Logic without Inverses}, booktitle = {Proceedings of Twenty-Third AAAI Conference on Artificial Intelligence, Chicago, Illinois, USA (13th--17th July 2008)}, year = {2008}, organization = {AAAI}, pages = {504--510}, url = {http://rewerse.net/publications/rewerse-publications.html#REWERSE-RP-2008-028} }