Technical Report, Faculty of Computer Science, Free University of Bozen-Bolzano. Technical report 2005.
Recently, Description Logics (DLs) gained increasing attention as they provide the formal foundation for the standard ontology languages for the Semantic Web, notably OWL-DL and OWL-Lite. In the Semantic Web and domains such as Enterprise Application Integration and Data Integration, ontologies are increasingly seen also as a mechanism to access and query data repositories. This novel context poses an original combination of challenges that has not been addressed before: (i) sufficient expressive power of the DL to capture common data modeling constructs; (ii) well established and flexible query mechanisms such as those provided by conjunctive queries; (iii) optimization of inference techniques with respect to the size of the data, which typically dominates the size of the intentional level of ontologies. This calls for investigating data complexity of query answering in expressive DLs. While combined complexity has been studied extensively, and data complexity has been characterized for answering atomic queries only, a precise characterization of data complexity for answering conjunctive queries over expressive DLs was still open. In this paper we close this problem, and prove a tight coNP upper bound for data complexity of conjunctive query answering in expressive DLs up to SHIQ . We thus establish that conjunctive query answering has coNP-complete data complexity for a whole range of DLs from AL to SHIQ . We obtain our result by providing a novel tableaux-based algorithm to check query entailment. In the algorithm, we had to manage the technical challenges caused by the simultaneous presence of transitive roles and number restrictions, leading to a DL lacking the finite model property. Notably, our technique provides also the first decidability result for answering conjunctive queries that may contain transitive roles.
@techreport{TR-FUB-2005-11,
title = "Characterizing Data Complexity for Conjunctive Query Answering
in Expressive Description Logics",
year = "2005",
author = "Magdalena Ortiz and Diego Calvanese and Thomas Eiter and
Enrico Franconi",
institution = "Faculty of Computer Science, Free University of
Bozen-Bolzano",
}