Completeness Guarantees for Incomplete Ontology Reasoners: Theory and Practice

18^th October 2011, 16:00 ALT
Dr. Bernardo Cuenca Grau
Department of Computer Science
University of Oxford
UK

Abstract

Due to the practical need for scalable query answering, developers of
ontology-based applications are often forced to use incomplete
reasoners---that is, reasoners which fail to derive all answers for at least
one query, ontology, and data set accepted as valid inputs.

The lack of completeness guarantees, however, may be unacceptable for
applications in areas such as health care and defence, where missing answers
can adversely affect the application's functionality. Furthermore, even if an
application can tolerate some level of incompleteness, it is often
advantageous to estimate how many and what kind of answers are being lost.

In this talk, I will present a novel logic-based framework that allows one
to check whether a reasoner is complete for a fixed query Q and ontology
T---that is, whether the reasoner is guaranteed to compute all answers to
Q w.r.t. T and an arbitrary data set D. Since ontologies are often fixed at
application design time (or change relatively infrequently), this approach
allows application developers to check whether a reasoner known to be
incomplete in general is actually complete for the kinds of input relevant for
the application at hand.

These results provide a theoretical and practical foundation for the design
of future ontology-based information systems that maximise scalability while
minimising or even eliminating incompleteness of query answers.