Abstract
Answering conjunctive queries (CQs) has been recognized as a key task for the usage of Description Logics (DLs) in a number of applications. The problem has been studied by many authors, who developed a number of different techniques for it. We present a novel method for CQ answering based on knots, which are schematic trees of dept h 1. It yields an algorithm for CQ answering that works in exponential time for ALCH and for large classes of CQs in SH. This improves over previous algorithms which require double exponential time and is worst-case optimal, as already satisfiability testing in ALC is EXPTIMEcomplete. Our result reconfirms Lutz.s result that inverse roles cause an exponential jump in complexity, being the problem 2EXPTIME-complete for ALCI. The algorithm is CONP, and hence also worst-case optimal, under data complexity.

URL:
http://rewerse.net/publications/rewerse-publications.html#REWERSE-RP-2008-029

BibTeX:

@inproceedings{REWERSE-RP-2008-029,
	author = {Magdalena Ortiz and Mantas Šimkus and Thomas Eiter},
	title = {Conjunctive Query Answering in SH using Knots},
	booktitle = {Proceedings of 21st International Workshop on Description Logics, Dresden, Germany (13th--16th May 2008)},
	year = {2008},
	volume = {353},
	url = {http://rewerse.net/publications/rewerse-publications.html#REWERSE-RP-2008-029}
}