Browse Prior Art Database

Mechanism for Optimizing Execution Speed of Goals in Logic Programs

IP.com Disclosure Number: IPCOM000062150D
Original Publication Date: 1986-Oct-01
Included in the Prior Art Database: 2005-Mar-09
Document File: 2 page(s) / 14K

Publishing Venue

IBM

Related People

Natarajan, KS: AUTHOR

Abstract

An automatic mechanism for optimizing the execution efficiency of logic programming applications by providing an adaptive search to speed up the execution of logic programs. A learning mechanism is proposed to select a near optimum sequence for selecting Horn clause subgoals that is determined by actual usage of the program. A logic program which contains a plurality of Horn clauses may have a goal stated so that it can be achieved or proved by successfully evaluating one of many alternate Horn clauses in sequence until one of them succeeds or all of them fail. A Horn clause consists of a head, namely a goal, stated as a conjunction of subgoals. All of the subgoals must be satisfied in order to prove the satisfiability of the Horn clause and achieve the Horn clause goal.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 51% of the total text.

Page 1 of 2

Mechanism for Optimizing Execution Speed of Goals in Logic Programs

An automatic mechanism for optimizing the execution efficiency of logic programming applications by providing an adaptive search to speed up the execution of logic programs. A learning mechanism is proposed to select a near optimum sequence for selecting Horn clause subgoals that is determined by actual usage of the program. A logic program which contains a plurality of Horn clauses may have a goal stated so that it can be achieved or proved by successfully evaluating one of many alternate Horn clauses in sequence until one of them succeeds or all of them fail. A Horn clause consists of a head, namely a goal, stated as a conjunction of subgoals. All of the subgoals must be satisfied in order to prove the satisfiability of the Horn clause and achieve the Horn clause goal. The average cost of achieving a goal depends upon the probability of success and the cost of evaluation of the different Horn clauses. The average cost may be minimized by optimizing the order of evaluation of the individual Horn clauses. The costs and probability of success of Horn clauses can be estimated by monitoring program execution which can in turn be used for automatic optimization of the search effort required to prove goals. The problem addressed here is the minimization of the average cost of evaluation of the individual Horn clauses. Since Horn clause evaluation is a fundamental operation in logic program execution, the efficiency with which the individual Horn clauses are evaluated is crucial to the overall run-time performance of logic programs. A Horn clause is evaluated by testing the subgoals in sequence until all subgoals are found satisfiable, or until one is found that cannot be satisfied in a manner consistent with the subgoals tested earlier in the sequence. The order in which subgoals within a Horn clause are considered significantly affects the average cost of evaluating the clause. The adaptive approach described minimizes the average execution cost by automatically adjusting to an optimal execution sequence that is determined by actual usage of the program. Associated with each subgoal are 1) the cost of deciding whether the subgoal is satisfiable, based on, for example, the number of instructions or execution time and 2) the probability of satisfying the subgoal. It has been proven that the optimal ordering of the subgoals orders them by ascending values of the ratios of their costs to the probabilities of their unsatisfiability when the probability of satisfying distinct goals in a Horn clause are independent of each other. In real logic programs the cost and probability values associated with subgoals are dependent upon the sequence in which they are considered. The learning mechanism...