Query answering in expressive description logics : techniques and complexity results

Abstract

Description Logics (DLs) sind eine Familie von Logiken die speziell entwickelt wurden, um Wissen zu repräsentieren und Schlüsse daraus zu ziehen. Sie erlauben es, einen bestimmten Wissensbereich mittels einer Wissensbasis zu modellieren, wenn auch sie es für gewöhnlich nicht erlauben, auf dieses Wissen flexibel zuzugreifen. Das hat eine Forschungsrichtung motiviert, die das Ziel hat, die traditionellen Inferenzdienste für DLs auf den Datenzugriff mittels Datenbankanfragesprachen auszuweiten. Allerdings sind bisher wenige Algorithmen vorgeschlagen worden, die dieses Problem für ausdrucksstarke DLs lösen. Außerdem wären die bisher verfügbaren Techniken sehr komplex, und die genaue Komplexität des Problems war noch offen. In dieser Dissertation analysieren wir die Anfragebeantwortung in ausdrucksstarken DLs, wir schlagen neue worst-case optimale Inferenztechniken vor, und wir leiten neue Komplexitätsresultate für das Problem ab. Wir verwenden ausdrucksstarke Automatenmodelle, um einen neuen Algorithmus zu entwickeln, der fast alle der verwendeten Konstrukte behandeln kann. Dieser ermöglicht es uns, die Entscheidbarkeitsgrenze und die oberen Komplexitätsschranken stark zu verbessern, sowohl bezüglich der Anfragesprache, als auch bezüglich der DL. Wir verwenden auch sogenannte knots für Algorithmen, um einige obere Komplexitätsschranken zu verbessern. Als weiteres Resultat identifizieren wir eine neue Komplexitätsquelle, die es uns erlaubt, die genaue Komplexität der Anfragenbeantwortung für eine grosse Anzahl von ausdrucksstarken DLs exakt zu bestimmen.<br />

Description Logics (DLs) are a family of logics specially tailored for knowledge representation and reasoning, widely appreciated for their suitability for representing complex structures of knowledge. They provide reasoning services over knowledge bases describing application domains, and have been deployed in a wide range of fields. Current DL systems, however, lack suitable means access the information they describe, which is a big limitation in several application areas.<br />For this reason, answering database-like queries over knowledge bases has become an important research topic. However, for the so-call expressive DLs only few algorithms for query answering were available and little was known about the computational costs of the problem. In this thesis we study query answering in expressive DLs, explore novel reasoning techniques with the emphasis on worst-case optimal algorithms, and derive new computational complexity results. First we use rich models of automata to develop a query answering algorithm that supports most of the popular modeling constructs. This allows us to significantly push the frontier of decidability and complexity upper bounds for query answering to very expressive DLs and very reach query languages. As second tool we employ the knot technique to develop algorithms with a more refined control of the sources of complexity, obtaining improved complexity upper bounds in some cases. Such algorithms are also optimal in data complexity. They are also appealing for implementations, as they support knowledge compilation and encodings into Datalog. Finally, we identify transitive roles and role inclusions as a costly pair of constructors that makes query answering theoretically harder that standard reasoning.<br />This helps us to characterize the precise complexity of query answering in a wide range of expressive DLs.