Subgoal order for query optimization in logic databases
Katherine A. Morris · 1992
Logic database systems are an approach to the problem of creating more powerful databases. A logic database system allows us to express queries in a single language rather than embedding relational queries in a conventional programming language such as C. NAIL! is a logic database system, and its query language is similar to the logic programming language Prolog. NAIL! rules, which are declarative, and may be recursive, define predicates that can be queried. Since the rules are declarative, the NAIL! system must optimize them to find the best subgoal ordering for each query. The subgoal ordering problem also occurs in other contexts, such as AI planning systems, logic programming languages like Prolog, and conventional relational database systems. This work addresses the subgoal ordering problem in NAIL!, and compares it to other models. We present an efficient algorithm to find a feasible subgoal order for rules, and prove that it will always find a subgoal order if it is possible to do so. The algorithm uses a greedy approach to the problem; a special property of the search space (the fact that we are finding all solutions to queries) means this approach works without running into the usual problems encountered by greedy algorithms. We describe an extension to the greedy algorithm that handles the cases of left- and right-linear recursive rules. We also give heuristics that can improve its performance further. Pre-compilation of the structure of the arguments may be used to produce more optimizations of the subgoal order.