APICe » Publications » Questions and Answers: Reasoning and Querying in Description Logic

Questions and Answers: Reasoning and Querying in Description Logic

Sergio Tessaris
Description Logics (DLs) are a family of formal languages for describing complex structured classes. These languages contain boolean operators and quantification over class attributes, as well as the specification of elements of the classes and their properties. DL knowledge bases (KBs) consist of a terminological part which describes the general organisation of the classes, and an assertional part for describing the properties of individuals. In spite of its inherent intractability, practical algorithms have been recently developed for purely terminological reasoning; when individuals are introduced there is still a lack of results. This thesis constitutes an advance in the direction of the development of DL systems providing efficient and powerful reasoning in presence of individuals. We choose an expressive DL (SHf), which has been previously studied from the terminological perspective (i.e. without individuals), and we investigate the problem of reasoning with individuals. SHf extends the standard DL ALC with transitive roles, role hierarchy, and attributes. This extension enables the representation of general inclusion axioms using a technique called internalisation. This thesis investigates two automated reasoning problems: KB satisfiability and query answering. KB satisfiability is the fundamental problem of deciding whether a given KB does not contain any contradiction. This problem is not only important for delivering consistent KBs, but most of the reasoning tasks for DL systems can be reduced to KB satisfiability. We show how the technique of precompletion, which has previously only be used in less expressive DLs, can be used in our expressive DL. A serious shortcoming of many Description Logic based knowledge representation systems is the inadequacy of their query languages. We present a novel technique that can be used to provide an expressive query language for such systems. One of the main advantages of this approach is that, being based on a reduction to knowledge base satisfiability, it can easily be adapted to most existing (and future) Description Logic implementations. We believe that providing Description Logic systems with an expressive query language for interrogating the knowledge base will significantly increase their utility.
April 2001.
	Author = {Tessaris, Sergio},
	Month = apr,
	Organisation = {Department of Computer Science, University of Manchester},
	School = {Doctorate of Philosophy in the Faculty of Science and Engineering},
	Title = {Questions and Answers: Reasoning and Querying in Description Logic},
	Year = 2001}