Worst-case Optimal Conjunctive Query Answering for an Expressive Description Logic without Inverses

Magdalena Ortiz, Mantas Simkus, Thomas Eiter

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.

Subjects: 11.1 Description Logics; 9.2 Computational Complexity

Submitted: Apr 15, 2008

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.