CW 2004_07

Bert Van Nuffelen
Abductive constraint logic programming: implementation and applications

Advisor(s): Danny De Schreye, Marc Denecker

Abstract

Abductive reasoning is a form of reasoning that arises naturally in the context of Declarative Problem Solving. The expert formulates his domain knowledge of the problem as a logic theory. A solution of the problem is then the outcome of reasoning process that acts on this logic theory. For many problems, the reasoning task that is required for solving the problem requires the computation of an interpretation for a relation so that the query is entailed by the logic theory augmented with this interpretation. This inference is called abduction.

This dissertation consists of two parts. The first part discusses the development of an abductive constraint logic solver, called the Asystem, for the knowledge representation language ID-Logic. We show how to transform ID-Logic theories to normal abductive logic programs which form the input of the Asystem. Procedurally, the Asystem is a mixture of existing abductive logic procedures, i.e. SLDNFA, IFF and ACLP. Typical for the procedure is the use of (existing) subsolvers to perform a part of the reasoning. The procedure is sound and complete w.r.t. the three-valued completion semantics. Our main contributions are at the implementation level. In order to obtain an efficient system good design decisions must be made. In particular, we discuss specialized data structures, the evaluation of the inference rules, the organization of the search tree, efficient equality reasoning and the integration of a finite domain constraint solver. The system is validated experimentally using classical AI problems.

In the second part of the dissertation, we present our contributions to the problem domain of the integration of multiple independent databases. We address two issues in this domain. The first concerns the differences in the ontologies between the databases. Each database stores information in a language which is often different from other databases. Merging the information in the databases requires that these languages are related in a formal way with each other. Our solution presents an ID-Logic mediator-based system that integrates the information of the databases by relating the database's languages with a common global language. The second issue that is addressed is contradictory information. When data from independent databases are merged, contradictions with respect to a set of integrity constraints may arise. We present two approaches to restore in a coherent way the consistency of an inconsistent database based on repairs, i.e. a special kind of database updates. One approach considers represent the problem as an abductive logic theory and it uses the Asystem as computational engine to compute the (most preferred) repairs. In the other approach the repairs are the models of propositional theory, that is derived from the data and the integrity constraints by an elegant encoding.

text.pdf (3.1M) / text.ps (2.0M) / mailto: dtai team