Specifying Constraints for Detecting Inconsistencies in A Conceptual Graph Knowledge Base

Introduction

The purpose of this paper is to propose a strategy for automatically detecting inconsistencies in a conceptual graph (CG) knowledge base. (See (Sowa, 1984; Sowa, 2008) for background on CGs.) For the purposes of this paper, a knowledge base is any collection of CGs that is used for a specific purpose. The CGs in a knowledge base are normally used to make inferences and draw conclusions. Obviously, if there are inconsistencies in a knowledge base, they may lead to unsound or incorrect conclusions. There are several ways to deal with inconsistencies; in some cases, it is possible to work around them; in other cases, it is necessary to correct or remove them. No matter how they are handled, the inconsistencies must be first detected before they can be dealt with, and therefore it is important for a knowledge base system to have efficient strategies for detecting inconsistencies.

There are many different definitions of the term knowledge base. For example, in Zhao & Shen (1990), the author's definition of a knowledge base is a system that deals with incomplete data, and must be able to incorporate new data, or learn new facts, as it is used. For the purposes of this work, a knowledge base is defined as a collection of CGs that will be used by an automated system for a specific purpose. An example of a knowledge base would be an inventory system for a factory that keeps track of what items are in stock, what items had been ordered, etc. Whatever the purpose of the knowledge base content, it is generally used to perform calculations, make a decision or manipulate other knowledge. The accuracy of these activities depends on the accuracy of the data items.

In this paper, we are interested only in knowledge bases that are intended to be logically consistent. Morell (1988), for example, describes inconsistency as when the knowledge base “asserts something that is not true of the modelled domain”. Liu, Easterbrook & Mylopoulos (2002) considers a knowledge base inconsistent if it “contains conflicting information about the system, and/or violates predefined constraints.” Our work focuses on consistency between a knowledge base's content and its rules. For example, if the factory's inventory system lists a certain crate as being stored in two different locations, that would be an inconsistency because it is physically impossible for one object to be in two places. If a query tried to determine which items were being stored in a particular section of the warehouse, the results may be incorrect. The results may indicate that the crate in question was stored in one section, when it is actually in another, or it may indicate that there are two of the same crates in stock. For the purpose of this paper, an inconsistency is considered to be a knowledge base subset that describes a situation that cannot exist, according to the knowledge base's rules.

Of course, there are many kinds of inconsistency, and therefore a completely general strategy would be intractable. For the purposes of this paper, inconsistency occurs when some part of a knowledge base violates the constraints set forth in a set of specific rules. In this work, both the constraints and the knowledge base are represented as conceptual graphs. The structure of the constraint graphs is one of the main contributions of this paper, and is described in detail later. There are no restrictions on the structure of the knowledge base itself. The detection procedure starts with a set of constraints, and then scans the remaining graphs for violations of each constraint.

We do not concern ourselves with how an inconsistency originates. An inconsistency might occur when the data in a knowledge base does not match what it is supposed to be modeling in some domain. Data added to the knowledge base can be incorrect, or in conflict with existing data. The knowledge base rules can change, and formerly consistent data can conflict with the new rules. An example of the former situation is when two knowledge bases are merged, as in work by Liu, Qi & Bell (2006). The approach they take assumes one knowledge base to be consistent, and uses this as a reference. The other knowledge bases to be merged are ranked based on their consistency with the reference knowledge base. Their algorithm uses possibilistic logic to determine which parts of the merged knowledge bases are to be kept, and which discarded as inconsistent (Liu et al. 2006).