TREITEL@SU-SUSHI.ARPA (Richard Treitel) (05/23/86)
PhD oral examination Tuesday June 3rd 1986 at 3 p.m. Building 200, Room 34 "Sequentialising Logic Programs" Richard Treitel In "expert systems" and other applications of logic programming, the issue arises of whether to use rules for forward or backward inference, i.e. whether deduction should be driven by the facts available to the rule or the goals that are put to it. Often some mixture of the two is cheaper than using either exclusively. I show that, under two restrictive assumptions, optimal choices of directions for the rules can be made in time polynomial in the number of rules in a recursion-free logic program. If either of these restrictions is abandoned, the optimal choice is NP-complete. I present a search algorithm for the easiest of the cases so obtained. A related issue is the ordering of the terms in a rule, which can have a strong effect on the computational cost of using the rule. Algorithms for ordering terms optimally are known, but all of them rely on the direction of inference being fixed in advance, and they apply only to a single rule considered in isolation. A more general algorithm is developed, and a way is shown to incorporate it into the choice of rule directions. This also leads to an NP-complete problem. Some attention is paid to the model of execution cost for logic programs on which these results are based. Logic programs involving recursion are not covered by this work because no satisfactory cost model exists for them.