Reasoning in Hybrid Knowledge Bases

Description Logics (DLs) have become a standard formalism to represent ontologies, which are conceptualizations or richer data models to describe a specific domain of an application area like business modelling, biomedicine or security, to mention a few. In particular, in the context of the Semantic Web, DL-based ontologies have been designated via the Web Ontology Language (OWL) as a standard for describing the semantics of complex web resources, in order to make automated data access for computers possible such that they can understand the meaning of data. Driven by the need to overcome limitations of DLs and to integrate them into application programs, research on tools and methods has been launched to access DL ontologies via query languages in a declarative manner like a database, and on combining DLs with other formalisms for knowledge representation. Most important are here rule languages, which play a dominant role in databases, as query languages that are more powerful than standard query languages like SQL, and in Artificial Intelligence, where advanced rule languages serve as tools for declarative problem solving. For hybrid knowledge bases, which consist of a rule and an ontology part, many questions regarding the semantics, the relationship of different formalizations among each other, and the computation of query results that naturally emerge were unanswered. The present project has tackled these issues and achieved several results. First, a clear understanding of the relationship between different proposals for hybrid knowledge bases has been gained, in that their relative expressiveness (what can be expressed in the one proposal but not in the other) and possible embeddings (that hybrid knowledge bases in the one formalism can be translated into ones of the other) has been settled. Second, the computational cost of evaluating queries and of model building in several hybrid knowledge base formalisms has been characterized, with a special focus on answering SQL-style queries (so called conjunctive queries), which are at the heart of ontology access in applications. These characterizations provide a picture of the computational nature and sources of complexity for the evaluation, which has guided the development of novel reasoning techniques and efficient algorithms for computing query results and model building, which have led to significant advances and improvements. Selected algorithms have with further optimizations been implemented in experimental software prototypes, which have been explored in application contexts such as enterprise modelling and semantics enriched route planning.