Using Integrity Constraints to Control Search in Knowledge Base Systems

Terry Gaasterland, Mark Giuliano, Anne Litcher, Yuan Liu, and Jack Minker

Computer Science Department,
	 University of Maryland
	 College Park

The complete paper is available in:

Abstract

A knowledge base system stores and manipulates a body of knowledge which consists of a set of rules and facts. An expert system may be defined as a metainterpreter over a knowledge base that provides a variety of facilities including answer generation, explanation, and interactive browsing. The rules and facts in a knowledge base capture syntactic information. In contrast, integrity constraints contribute semantic information about the represented knowledge. They impose restrictions on the states of the world that a knowledge base can model. Typically, integrity constraints are used to update and maintain the knowledge base, but they can also be a powerful tool for answering queries.
A logic programming system augmented with constraint processing, data storage, and data manipulation capabilities forms the basis for a knowledge base system. Both a run-time and a compile-time approach to using integrity constraints in logic programming systems to identify and eliminate unproductive search activity have been implemented within an existing parallel logic programming system, PRISM. The extended system provides the basis for a series of experiments which demonstrate that significant classes of knowledge representation domains can use integrity constraints effectively. We show that using constraints to process a query can reduce search space and response time. Furthermore, we show that in certain cases the compile-time approach reduces response time much more than the run-time approach. ^L

Bibliography

Chakravarthy, U. (1985). Semantic Query Optimization in Deductive Databases. PhD thesis, University of Maryland, Department of Computer Science, College Park.
Chakravarthy, U., Grant, J., and Minker, J.(1987). Foundations of semantic query optimization for deductive databases. In Minker, J., editor, Foundations of Deductive Databases and Logic Programming, pages 243-274. Morgan-Kaufmann.
Chakravarthy, U., Grant, J., and Minker, J.(1990). Logic based approach to semantic query optimization. ACM Transactions on Database Systems, 5(2):62-207.
Clark, K., McCabe, F., and Gregory, S. (1982). Ic-prolog language features. In Clark, K. and S-A. Tarnlund, S.-A., editors, Logic Programming, pages 253-266. Academic Press, New York.
Giuliano, M. (1990). The Control and Execution of Parallel Logic Programs. PhD thesis, University of Maryland, Department of Computer Science, College Park.
Giuliano, M., Kohli, M., Minker, J., and Durand, I. (1990). Prism: A testbed for parallel control. In Kanal, L. and Kumar, V., editors, Parallel Algorithms for Machine Intelligence.
Grant, J. and Minker, J.(1990). Integrity constraints in knowledge based systems. In Adeli, H., editor, Knowledge Engineering, pages 1-25. McGraw-Hill Publishers.
Kasif, S., Kohli, M., and Minker, J.(1983). Prism: A parallel inference system for problem solving. Technical Report TR-1243, University of Maryland, College Park, Dept. of Computer Science.
Kohli, M. (1987). Controlling the Execution of Logic Programs. PhD thesis, University of Maryland, Department of Computer Science, College Park.
Kohli, M. and Minker, J.(1983). Control in logic programs using integrity constraints. In Proceed- ings of Logic Programming Workshop, Universidade Nova de Lisboa, Portugal.
Kowalski, R. and Sadri, F. (1986). An application of general purpose theorem proving to database integrity. In Minker, J., editor, Proc. Workshop on Foundations of Deductive Databases and Logic Programming, pages 477-517, August 18-22, Washington, D.C.
Kowalski, R. A. and Kuehner, D. (1971). Linear Resolution with Selection Function. Artificial Intelligence, 2:227-260.
Lobo, J. and Minker, J.(1988). A metainterpreter to semantically optimize queries in deductive databases. In Kerschberg, L., editor, Proc. Workshop on Expert Database Systems, pages 387-420, Tysons Corner, Virginia.
Nakagawa, H. (1985). Prolog program transformations and tree manipulation algorithms. Journal of Logic Programming, 2(2).
Reiter, R. (1978). Deductive question answering on relational databases. In Minker, H. G. J., editor, Logic and Data Bases, pages 149-177. Plenum Press, New York.
Robinson, J. (1965). A Machine-Oriented Logic Based on the Resolution Principle. J.ACM, 12(1).
T.Gaasterland, Minker, J., and Rajasekar, A. (1990a). Deductive database systems and knowledge base systems. In Proceedings of VIA 90, Barcelona, Spain.
T.Gaasterland, Minker, J., and Rajasekar, A. (1990b). Knowledge base systems: A deductive database approach. In AAAI Workshop on Knowledge Base Management Systems, Boston, Massachusetts.