Synthesizing Least Fixed Point Queries Into Non-Recursive Iterative Programs

1. Motivation

We present an algorithm for synthesizing a non­ recursive, iterative program from a Least Fixed Point query (defined later). There are three reasons why such a synthesis will be of interest to researchers in AI in general, and to researchers in program synthesis in particular:

1. It (efficiently) solves a real world problem of practical utility for database workers.
2. The method was derived using techniques from logic programming systems. In particular the backward-chaining depth-first problem solving metaphor leads to an intuitive understanding of the algorithm. Thus a link between logic programming and program synthesis is illustrated.
3. Finally, it illustrates the idea that if programs can be classified into domains (e.g. sort programs, list processing programs etc.) then may be we can derive algorithms for synthesizing programs within a domain.

...2. Background

Consider a relational expression of the form

(Throughout this paper we shall assume that the degree of the left and right hand sides of all such equations is the same). A LFP of (1) is a relation R" such that R" - f(R") and R" !;;;; S for any S satisfying (1). Examples of such LFP operations are calculating the number of flights between two cities during a given time period, finding the lowest-level manager common

Synthesizing Least Fixed Point Queries into Non-recursive Iterative Programs

Shamim A. Naqvi

Bell Laboratories Murray Hill, NJ 'l7974 Lawrence J. Henschen

Northwestern University

Evanston, IL 60201

to a group of employees, and determining whether there is an active circuit connecting two points. None of the above can be couched in relational algebra [AHO].

In studying the question of how powerful a data query language should be, Aho and Ullman [AHO] postulated two general principles and noted that Least Fixed Point (LFP) queries satisfy those principles but cannot be supported by the traditional relational calculus [CODD]. Since in general a LFP of (1) may not exist [TARS], a relation R can be constructed inductively by specifying the basis and inductive rules:

To support LFP queries, [AHO] recommends the addition of iteration and assignment operators to relational algebra. Thus (2) can be written as

In [AHO] it is further shown that if in (2) there is only one occurrence of R in f(R) then certain optimizations can be performed in the calculation of the LFP through (3). In this paper we present a method of automatically synthesizing a non-recursive while-loop program, i.e. a program like (3) except that it will be non-recursive, from a LFP query of the form of (2). Such a transformation would have the following points of interest for database researchers:

1. The non-procedural nature of relational algebra is preserved although it would take a fairly sophisticated user to write a LFP query.
2. No theorem-proving is required to support LFP queries as in [WRIG] though our method is grounded in the resolution principle of Robinson [ROB].

1. The program derived for (2) is non-recursive.
2. With a slight abuse of notation of (2), link queries (defined later) of QBE [ZLOO] can also be supported in the same framework.

3. Intuitive Explanation of tbe Algorithm

It is simpler to develop and explain the algorithm by assuming that the LFP query will be written in relational calculus. Thus, equation (2) becomes

As an example, consider a database containing the relations father(x,y) and parent(u,v) for particular values of x, y, u and v. Then a query asking for (certain kinds of) ancestors of a person 'a' can be stated as follows:

A few comments on the notation are in order. First, all variables are assumed to be universally quantified. Second, the syntax, on purpose, is like that of PROLOG [PERE]. Third, any base predicate (i.e., a relation occurring in the database) with at least one argument instantiated to a constant represents a retrieval request. Thus, the expression parent(w,a) can be read as "an-· parent", select from the parent relation those tuples whose second components have the value 'a'. Fourth, we have purposefully chosen a somewhat obscure and incomplete definition of ancestors. This is to highlight a distinction later. Finally, our method of handling LFP queries (as described below) has two advantages over a PROLOG system. It not only works for left-recursive assertions but is also independent of the order of the assertions. In fact, putting the above query to a PROLOG system will cause an infinite com pu ta tion.

In order to proceed with an intuitive description of our method, we need to specify how a backward-chaining problem-solving system works. Given an assertion of the form

and a problem, C, such a problem-solving system matches the problem to the head, i.e. left-hand side of the assertion. If the match succeeds then the original problem, C, is replaced by the subproblems gl, g2, .... , i.e. the body of the assertion, with the matching substitution applied to the subproblems. If the head of more than one assertion matches a problem then the system has to make a choice.

Now, assume we have a backward-chaining problemsolving system and, further, that a problem p(x,y, .... ) is solvable only if at least one of the variables x,y, ... is instantiated to a constant. Finally, it is evident that a LFP query can be replaced by a view. Thus, (4) can be replaced by the query

We now describe how a backward-chaining problem­ solving system would solve (5) using (6a) and (6b). From this description, our method will become obvious.

To solve (5), we match it with the head of (6a) and (6b). Since (5) matches both the assertions, let us choose (6a) first. The matching substitution is {u+-w,v --a}, and, thus, the original problem is replaced by the body of (6a), namely, father(w,a). This subproblem is solvable and, in fact, yields a first set of answers which we can collect in a relation, say ancestor. From (5) and (6b), the original problem is replaced by the body of (6b) with the matching substitution applied. This yields ancestor(w,y), parent(y,a) . Proceeding in a depth-first manner, the subproblem ancestor(w,y) is not solvable, but parent(y,a) is and yields a set of values for 'y'. These values for 'y' are substituted back into the failed subproblem ancestor(w,y) and this subproblem is asked again. Once again we have a choice between (6a) and (6b) and the above process repeats.

The above iterative pattern can be captured in the following steps:

1. Retrieve father(w,a) and insert these tuples into the answer relation, ancestor.
2. Stack the value 'a'.
3. Pop a value from the stack and assign it to 'z'.
4. Retrieve parent(y,z) and use these new values of 'y' to retrieve father(w,y). Also stack these values of 'y'. Collect tuples retrieved for father(w,y) in ancestor.
5. Go to step 3.

The corresponding program form is:

• /* all variables accept a set of values */

ancestor U eval(father(w,a)) insert-in-queue(Q,a) while (Q ¢ empty) do z +- remove-from-queue(Q) ----(A) eval (parent (y,z)) ancestor U evai(father(w,y)) insert-in-queue(Q,y)

Insert-in-queue(Q,a) inserts the value 'a' into queue Q if 'a' has not been inserted into Q before in the current computation. Finally, remove-from-queue(Q) removes the top element of Q.

Let us now consider a right-recursive definition of the above LFP query.

Once again, a similar problem solver would solve the above query as follows: (7) and (8) yield the primitive subproblem father(w,a) . From (7) and (9), to solve ancestor(w,a) solve parent(w,y) and ancestor(y,a) . Clearly parent(w,y) cannot be effectively solved because we do not know either 'w' or 'y'. To solve ancestor(y,a) reuse (8). This yields a value for 'y' which makes parent(w,y) solvable. In this case the program form is as follow:

ancestor U eval(father(w,a)) insert-in-queue(Q,a) while (Q ~ empty) do z ..... remove-from-queue(Q) eva! (father(y ,z)) ---(B) od ancestor U eva! (parent ( w ,y)) insert-on-queue(Q,y)

Program forms (A) and (B) are similar. In order to illustrate the difference we make the following definitions. Consider a LFP query written as

Let us call the expression

---(lOb)

the inductive residue (IR), and the expression

as the basis residue (BR). Thus from (5), (6a) and (6b) the basis residue is father(u,v) and the inductive residue is parent(y,z) . Now notice that the program forms (A) and (B) differ in the order in which the basis and inductive residue expressions are used. If we call the constants specified in the basis step R0 -+ R as driver cOnstants, we are lead to the general program form (C) shown in Fig. 1.

The only thing left to explain is the order in which BR and IR expressions are to be used. This order can be elucidated as follows. Consider an LFP query stated as (lOa) and (lOb). Hypothesize solving R in (lOa) by using (lOb) . This generates the subproblems

Now, by examination, if the subproblem R in the above expression is solvable (i.e. at least one of its variables is known) then the order is "evaHIR); R U evaHBR)", otherwise it is "evaHBR); R U eval OR) ·.

R U eval(BR) insert-in-queue(Q,driver constants) while (Q ~ empty) do od z +- remove-from-queue(Q) eva! (BR or IR) ---(C) R U eva! (IR or BR) insert-in-queue(Q,new driver constants)

4. Algorithm

Input: A LFP query written in the form of a basis step

and an inductive step

Output: A program of the form of (C) above.

Method:

• l . Find the Basis Residue (BR) and the Inductive Residue (IR) .
• Decide on the order of the BR and IR expressions as follows: Match the head of the BR expression (II) to the head of the IR expression ( 12). Apply the matching substitution to the body of (12) and if the subproblem, R, in the body of (12) is solvable then the order is {eva! OR); R U eval (BR)} else the order is {eva! (BR); R U eval(IR)}.
• Substitute the BR and IR expressions (in the right order) into the program skeleton (C).

A proof that the program form above produces correct answers is given in [HEN]. Briefly, correct answers are those values logically implied by the definitions. Our process is essentially supported resolution which is sound and complete, so that all and only answers are generated. Clearly, if the relation R is not cyclic, the stack must become empty at some point. Certain kinds of cyclicity (e.g. reflexivity ) can be easily recognized by slight additions to the algorithm. In any case, a more elaborate termination test for the while-loop, based on remembering the derivation of each value added to R, yields termination in all cases. See [HEN] for details.

The transformation algorithm itself has complexity based on identifying cycles in a (clause connectivity) graph and on unification, both of which admit efficient algorithms. The general case allows for programs representing non-tail recursive definitions as well. In these cases, the eval(IR) part of the loop includes an expanding formula corresponding to the non-tail recursive part of the definition.

Although, we give preference to select operations over joins, this is not required. However, most of the time it is obviously more efficient. For example, in the expression

parent (xI ,x2) & parent (x2,x3) & parent (x3,x4)

& father(x4,a)

it makes no sense to form the join of parent (x 1 ,x2) and parent(x2,x3) to start with. A feature of the method is that the form of the database requests is known beforehand so that optimizing these requests on the basis of the physical organization of the database as well as on the basis of redundancy in the set of requests could be carried out when the program is synthesized.

5. Conclusion

We have presented a method which, without using theorem-proving, transforms a LFP query expressed as a recursive definition into a non-recursive program. The use of this method permits one to process LFP queries posed in a conventional relational calculus.

6. Acknowledgements

Dan Fishman pointed out some errors and omissions in an earlier draft of this paper. Earlier drafts were also read and commented upon by Kevin Wilkinson, John Linderman and an annonymous referee at Bell Laboratories. We thank all of them.