View-based query answering over description logic ontologies
Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, Riccardo Rosati · 2008
Abstract. Description Logics (DLs) provide the formal foundation for ontology languages, and they have been advocated as formalisms for modeling the domain of interest in various settings, including the Semantic Web, data and information integration, and ontology-based data access. An important requirement there is the ability to answer complex database-like queries, while taking into account both ex-tensional and intensional domain knowledge. The task of answering queries has been investigated intensively in the last years for a variety of DLs, and consider-ing both data complexity, i.e., the complexity measured in the size of the exten-sional information only, and combined complexity. On the one hand, it has been shown to be in general (exponentially) more difficult than the standard reasoning tasks of concept satisfiability and subsumption; on the other hand a broad range of techniques have been developed. We overview here some of the key techniques developed in the last years for query answering over DL ontologies, ranging from rewriting based approaches for lightweight DLs, to tableaux algorithms, and tech-niques based on automata on infinite trees for very expressive DLs. The associated results, accompanied by matching lower bounds, have contributed to shaping the computational complexity picture for ontology-based query answering. 1