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.

Computer Science & Information Technology

You might also like to view...

Choose the correct number expression in the following sentence. _____members will be selected to represent the club at the state competition.

A. ?11 B. ?Eleven

Computer Science & Information Technology

?Which of the following is the default overflow property?

A. ?visible B. ?hidden C. ?scroll D. ?auto

Computer Science & Information Technology

How wide are all equipment racks?

A. 16 inches B. 19 inches C. 20 inches D. 24 inches

Computer Science & Information Technology

Which of the following is true about algebraic expressions?

a) parentheses are needed in all algebraic expressions b) infix expressions do not require precedence rules c) postfix expressions do not require association rules d) fully parenthesized expressions are difficult to recognize and evaluate

Computer Science & Information Technology