Sergio Tessaris
Doctorate of Philosophy in the Faculty of Science and Engineering
Department of Computer Science, University of Manchester
April 2001
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.
