Abstract

Description Logics (DLs) play an important role in the Semantic Web as the foundation of ontology language OWL DL. The standard DLs, based on the classical logic, are more suitable to describe concepts that are crisp and well-defined in nature. However, for many emerging applications, we also need to deal with uncertainty. In recent years, a number of proposals have been put forward for incorporating uncertainty in DL frameworks. While much progress has been made on the representation and reasoning of the uncertainty knowledge, query optimization in this context has received little attention. In this thesis, we tackle this problem in both theoretical and practical aspects by taking a generic approach. We first propose the [Special characters omitted.] framework which extends the standard DL [Special characters omitted.] with uncertainty. This is done by extending each component of the [Special characters omitted.] framework, including the description language, the knowledge base, and the reasoning procedure. In particular, the resulting semantics of the description language is captured using the certainty lattice and the combination functions. The knowledge base is extended by associating with each axiom and assertion a certainty value and a pair of combination functions to interpret the concepts that appear in the axiom/assertion. A sound, complete, and terminating tableau reasoning procedure is developed to handle such uncertainty knowledge bases. An interesting feature of the [Special characters omitted.] framework is that, by simply tuning the combination functions that are associated with the axioms and assertions, different notions of uncertainty can be modeled and reasoned with, using a single reasoning procedure. Using this framework as the basis, we then investigate optimization techniques in our context. We adapt existing optimization techniques developed for standard DLs and other software systems to deal with uncertainty. New techniques are also developed to optimize the handling of uncertainty constraints generated by the reasoning procedure. In terms of practical contribution, we developed a running prototype, URDL - an Uncertainty Reasoner for DL [Special characters omitted.] , which implements the proposed optimization techniques. Experimental results show the practical merits of the [Special characters omitted.] framework, as well as the effectiveness of the proposed optimization techniques, especially when dealing with large knowledge bases.