Hierarchical knowledge bases and efficient disjunctive reasoning

Abstract

We combine ideas from relation-based data management with class hierarchies to obtain Hierarchical Knowledge Bases, which have greater expressive power while maintaining the benefits of predictable and efficient information processing. We then consider the problem of reasoning with certain limited forms of disjunctive information. We show that hierarchical knowledge bases can be used for efficient approximate reasoning with such information. The significant features of our approach include a well-conditioned trade between efficiency and accuracy, with a sound and complete limit case, and approximations guided by the structure of the domain theory. Because of the structure imposed on the knowledge base, it is possible to characterize the potential error in any approximation. 1 Introduction It is fashionable to view a knowledge base (KB) as an integral utility invoked by a problem-solving program. To be useful in tasks such as robot guidance, such a KB subsystem must perform efficiently...