Fast Inference Based on the Set Theory

Abstract

During the last decade, model of knowledge based on rules loses its positions in information systems. However, production model of knowledge is still popular in expert system and decision making systems, particularly, in situation centers. The main problem of reasoning from rules is exponential complexity of search. Logical inference usually operates with axioms recorded in plain texts or XML-like files. That means the facts and rules are processed in the order they are written in the source file. It is acceptable for small knowledge bases but when the number of facts increases the reasoning time gets non-acceptable. In this paper, we propose an approach implementing well known techniques to accelerate search – indexing of facts in the knowledge base.

Let say all the facts consist of tuples (subject, predicate, object). First, we enumerate all the facts in the knowledge base. Then, we build the indices. Each index relates to a term and contains the facts’ numbers having this term in a corresponding role (as a subject, as a predicate, or as an object). When the search meets a rule containing particular values in the antecedents (conditions of rules) the inference engine does not need to scan entire knowledge base. Instead, it extracts only facts containing the terms in the proper roles. Moreover, by applying to indices the intersection operation we can dramatically shorten the list of facts that should be processed by rules. In the paper, we show that in some cases set operations under indices allow to eliminate the inference at all because it makes possible to get the final result directly from indices.

In contrary to well known RETE algorithm, our approach does not need to build prefix trees before the processing of each rule. The indices are to be updated only when the new facts appear. The inference acceleration depends on the query. The more explicit query is the better results the search demonstrates.