Optimize relational algebra query: music

Query: Π name, title (σ dept-name = "music" (instructor ⋈ Π course_id, title (teaches ⋈ course)))

Assumed schema: instructor(ID, name, dept_name, salary), teaches(ID, course_id, sec_id, semester, year), course(course_id, title, dept_name, credits).

(Note: as printed, the projection Π course_id, title removes ID, so the join with instructor would have no common attribute. The intended expression is the standard textbook form, with the projection on course only, and the answer below is written that way.)

Original expression tree (as written)

Π name,title
  |
σ dept_name="music"
  |
  ⋈
 /  \
instructor   ⋈
            /  \
       teaches  Π course_id,title
                    |
                  course

The selection is applied last, after all the relations have been joined. The join of instructor, teaches and course produces a large intermediate result, although only the music instructors are needed.

Heuristic rules used

1. Perform selection as early as possible (push σ down), using the rule σθ(E1 ⋈ E2) = σθ(E1) ⋈ E2 when θ involves only attributes of E1. The attribute dept_name belongs to instructor.
2. Perform projection early: keep only the attributes needed later (ID, name, course_id, title).
3. Join the small relations first: choose the join order so that the smallest intermediate result is created first (joins are associative and commutative).

Step by step

1. Move the selection to instructor:

   Π name,title ( σ dept_name="music"(instructor) ⋈ (teaches ⋈ Π course_id,title(course)) )

2. Associate the joins so that the filtered instructor meets teaches first:

   Π name,title ( ( σ dept_name="music"(instructor) ⋈ teaches ) ⋈ Π course_id,title(course) )

3. Push projections: after the selection, instructor needs only ID and name, and teaches needs only ID and course_id:

   Π name,title ( ( Π ID,name( σ dept_name="music"(instructor) ) ⋈ Π ID,course_id(teaches) ) ⋈ Π course_id,title(course) )

Optimized expression and tree

            Π name,title
                 |
            ⋈ (course_id)
           /             \
       ⋈ (ID)         Π course_id,title
      /      \                |
Π ID,name   Π ID,course_id  course
    |              |
σ dept=music    teaches
    |
instructor

Only the music instructors flow into the first join, and each relation is cut down to the needed columns before it is joined. The intermediate results are much smaller, so fewer disk blocks are read and fewer tuples are compared.