Data complexity of Answering Unions of Conjunctive Queries in SHIQ

Technical Report, Faculty of Computer Science, Free University of Bozen-Bolzano. Technical report 2006.

The novel context of accessing and querying large data repositories through ontologies that are formalized in terms of expressive DLs requires on the one hand to consider query answering as the primary inference technique, and on the other hand to optimize it with respect to the size of the data, which dominates the size of ontologies. While the complexity of DLs has been studied extensively, data complexity in expressive DLs has been characterized only for answering atomic queries, and was still open for more expressive query languages, such as unions of conjunctive queries (UCQs). In this paper we advocate the need for studying this problem, and provide a significant technical contribution in this direction. Specifically, we prove a tight coNP upper bound for answering UCQs over SHIQ knowledge bases. We thus establish that for a whole range of DLs from AL to SHIQ , answering UCQs has coNP-complete data complexity. We obtain our result by a novel tableaux-based algorithm for checking query entailment, inspired by the one in [Levy&Rousset'98], but which manages the technical challenges of simultaneous transitive roles and number restrictions (which leads to a DL lacking the finite model property).

@techreport{TR-FUB-2006-03,
   title = "Data complexity of Answering Unions of Conjunctive Queries in
SHIQ      ",
   year = "2006",
   author = "Magdalena Ortiz and Diego Calvanese and Thomas Eiter",
   institution = "Faculty of Computer Science, Free University of
Bozen-Bolzano",
}