AAAI Publications, Thirteenth International Conference on the Principles of Knowledge Representation and Reasoning

Font Size: 
Non-Uniform Data Complexity of Query Answering in Description Logics
Carsten Lutz, Frank Wolter

Last modified: 2012-05-17


In ontology-based data access (OBDA), ontologies are used as an interface for querying instance data. Since in typical applications the size of the data is much larger than the size of the ontology and query, data complexity is the most important complexity measure. In this paper, we propose a new method for investigating data complexity in OBDA: instead of classifying whole logics according to their complexity, we aim at classifying each individual ontology within a given master language. Our results include a P/coNP-dichotomy theorem for ontologies of depth one in the description logic ALCFI, the equivalence of a P/coNP-dichotomy theorem for ALC/ALCI-ontologies of unrestricted depth to the famous dichotomy conjecture for CSPs by Feder and Vardi, and a non-P/coNP-dichotomy theorem for ALCF-ontologies.


Data complexity;OBDA;CSP;conjunctive query;ontology

Full Text: PDF