Reference: Levy, A. Y. & Sagiv, Y. Controlling Inference Using the Query Tree. Knowledge Systems Laboratory, January, 1993.
Abstract: Controlling inference is a key to scaling up AI systems. This paper describes methods for controlling inference in Horn rule knowledge bases using a powerful tool, the {\em query tree}. The query tree is a finite structure that encodes all the possible derivations of a query. It shows which facts in the knowledge base may be used in a derivation of the query. Furthermore, it encodes all the possible sequences of rule applications and database lookups that can result in answers to the query. Consequently, it can be used to control search both by ignoring certain facts and by guiding the search of the problem solver to pursue only useful paths. The distinguishing characteristic of the query tree is that under certain conditions, it encodes {\em only} useful derivation paths and tells us {\em precisely} which facts can be used in a derivation of the query. We present experimental results showing that in practice, using the query tree to control search leads to significant savings.