Write a recursive SQL query that returns tuples of the form From,To,Distance, which represent direct or indirect ?ights (i.e., ?ights composed of one or more segments) and the aggregate distance over all segments for each such ?ight. (If there are several ways to reach B from A and the total distance is di?erent in each case, then the output would have several tuples such as A,B,1000,

A,B,1500, etc.) The exact query is: Find al l tuples of the above form provided that the distance is less than 10,000 .

Consider the following relational schema:



DirectFlight(From,To,Distance)



WITH RECURSIVE IndirectFlight(From,To,Distance) AS

       (  (SELECT * FROM DirectFlight D

           WHERE D.Distance < 10000)

           UNION

          (SELECT From, To, D.Distance+I.Distance

               FROM DirectFlight D, IndirectFlight I

               WHERE D.To = I.From AND D.Distance+I.Distance < 10000) )

           SELECT * FROM IndirectFlight

The iterative evaluation procedure for this query terminates, because the values for the Distance attribute cannot grow inde?nitely due to the upper bound on distances. Note that there is another way to write this query, which might or might not terminate depending on whether the query optimizer is smart enough:



WITH RECURSIVE IndirectFlight1(From,To,Distance) AS

       (   (SELECT * FROM DirectFlight)

            UNION

           (SELECT From, To, D.Distance+I.Distance

            FROM DirectFlight D, IndirectFlight1 I

            WHERE D.To = I.From) )

     SELECT *

     FROM IndirectFlight1 I

     WHERE I.Distance < 10000

The di?erence is that now the selection is done in the query rather than in the recursive de?nition. By itself, the recursively de?ned relation IndirectFlight1 is in?nite and the iterative procedure will never end. However, the optimizer might notice the selection condition in the outer query, I.Distance < 10000, and push it to the recursive part during the evaluation, thereby essentially reducing the problem to the ?rst solution above. Algorithms for doing this kind of optimization for recursive queries are well known, but vendors might choose to not implement them.