---
title: "Optimize relational algebra query: music"
subject: "Database Management System"
chapter: 5
key: "semester_6/database_management_system:optimize-query-music-instructor"
source: https://www.bctengineer.com/q/semester_6/database_management_system/optimize-query-music-instructor
site: BCT Engineering
---

# Optimize relational algebra query: music

Database Management System · Chapter 5: Query Processing & Optimization

- Asked in: year not given
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_6/database_management_system/optimize-query-music-instructor
- Whole chapter: https://www.bctengineer.com/md/semester_6/database_management_system/chapter-5

## Question

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

## Short answer

Push σ dept='music' to instructor. Project early: Π ID,name(instructor), Π ID,course_id(teaches), Π course_id,title(course). Join filtered instructor with teaches then course.

## Answer

**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)

```text
Π 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

```text
            Π 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.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What is the first optimization applied to the query?
   A. Move the selection dept_name = music down onto instructor
   B. Delete the projection
   C. Join course first
   D. Replace join by product
   Answer: A. dept_name belongs to instructor, so the selection is applied before the joins to reduce intermediate size. (Key point: Push selection down)

2. Why project early on each relation?
   A. To keep only the attributes needed later and shrink intermediate results
   B. To remove all keys
   C. To avoid joins
   D. To change the answer
   Answer: A. Cutting columns before joining reduces tuple width and the disk blocks read. (Key point: Early projection)

3. Which join order is preferred in the optimized expression?
   A. course with teaches first
   B. Filtered instructor with teaches first, then with course
   C. instructor with course
   D. All joins at once after the selection
   Answer: B. The small filtered instructor result is joined first so the first intermediate result is small. (Key point: Join order)

## Close variants set in other exams

- [Optimize query with year 2009 condition](https://www.bctengineer.com/question.md?key=semester_6%2Fdatabase_management_system%3Aoptimize-query-music-2009) — Database Management System, chapter 5

## Related in Database Management System

- [RA: computer dept employees and supervisors](https://www.bctengineer.com/question.md?key=semester_6%2Fdatabase_management_system%3Ara-computer-emp-supervisor) — Database Management System, chapter 3
- [RA: delete Electrical dept projects](https://www.bctengineer.com/question.md?key=semester_6%2Fdatabase_management_system%3Ara-delete-electrical-projects) — Database Management System, chapter 3