5.21

Modify the recursive query in Figure 5.16 to define a relation

prereq_depth(course_id,prereq_id,depth)

where the attribute depth indicates how many levels of intermediate prerequisites there are between the course and the prerequisite. Direct prerequisites have a depth of 0. Note that a prerequisite course may have multiple depths and thus may appear more than once.

---

Note that the below query is going to give us an infinite table, if there is a cycle in the prereq relation. For example suppose course A has course B as a prerequisite and course B has course A as a prerequisite (i.e. the tuples (A,B) and (B,A) both appear inside of prereq). In the query of Figure 5.16 since there was no attribute varying (like we have depth here), fixed point will be reached even if there are such cycles. (Read more in section 5.4.2).

WITH RECURSIVE prereq_depth(course_id,prereq_id,depth) AS (
    SELECT course_id,prereq_id,0 AS depth
    FROM prereq
    UNION
    SELECT prereq_depth.course_id, prereq.prereq_id, prereq_depth.depth + 1
    FROM prereq_depth, prereq
    WHERE prereq_depth.prereq_id = prereq.course_id 
)
SELECT * FROM prereq_depth;

The following query tries to solve this problem.

CREATE TABLE temp_prereq (
    course_id VARCHAR(8),
    prereq_id VARCHAR(8),
    PRIMARY KEY (course_id,prereq_id)
);

-- make_sure_it_is_not_duplicate returns true if it is the first time
-- that (course_id,prereq_id) is passed into the function. false otherwise.
CREATE OR REPLACE FUNCTION make_sure_it_is_not_duplicate(course_id VARCHAR(8), prereq_id VARCHAR(8))
RETURNS BOOLEAN AS 
$$
BEGIN
    IF ((course_id,prereq_id) IN (SELECT * FROM temp_prereq)) THEN
        RETURN 'f'; -- it is a duplicate
    ELSE 
        INSERT INTO temp_prereq VALUES (course_id, prereq_id);
        RETURN 't'; -- not a duplicate
    END IF;
END;
$$
LANGUAGE plpgsql;

WITH RECURSIVE prereq_depth(course_id,prereq_id,depth) AS (
    SELECT course_id,prereq_id,0 AS depth
    FROM prereq 
    WHERE make_sure_it_is_not_duplicate(course_id,prereq_id) AND 
        course_id <> prereq_id -- the case where the course is a prerequisite of itself.
    UNION
    SELECT prereq_depth.course_id, prereq.prereq_id, prereq_depth.depth + 1
    FROM prereq_depth, prereq
    WHERE prereq_depth.prereq_id = prereq.course_id 
        AND make_sure_it_is_not_duplicate(prereq_depth.course_id, prereq.prereq_id)
)
SELECT * FROM prereq_depth;

-- we don't need temp_prereq anymore. It has served its purpose.
DROP TABLE temp_prereq;