## Solutions - Relational Algebra Workshop 6

---
### Exercise 1. Follow each step of the algorithm to produce an optimised query tree.

* Relational Algebra:

$$
  \pi_{name}((\sigma_{Major='CS' AND Year≥3}(Student)) 
 $$
 $$
  \bowtie_{Student.SID = Enroll.SID} (\sigma_{Term='2025-S1' AND Grade='HD'}(Enroll)))
$$


STAGE 0 (Naive)

                     π[Student.Name]
                                |
σ[Enroll.SID=Student.SID ∧ Student.Major='CS' ∧ Student.Year≥3 ∧ Enroll.Term='2025-S1' ∧ Enroll.Grade='HD']
                                |
                         Student × Enroll


STAGE 1 (Break conjunctive selection)

                     π[Student.Name]
                                |
                     σ[Enroll.SID=Student.SID]
                                |
                     σ[Student.Major='CS']
                                |
                      σ[Student.Year≥3]
                                |
                     σ[Enroll.Term='2025-S1']
                                |
                      σ[Enroll.Grade='HD']
                                |
                         Student × Enroll


STAGE 2 (Push single-table selections to leaves)

                     π[Student.Name]
                                |
                     σ[Enroll.SID=Student.SID]
                                |
                                ×
                               / \
          σ[Major='CS' ∧ Year≥3]   σ[Term='2025-S1' ∧ Grade='HD']
                    |                             |
                Student                        Enroll


STAGE 3 (Reorder binary ops — trivial with 2 relations)
-- no change


STAGE 4 (Replace × + join-σ with explicit join)

                     π[Student.Name]
                                |
                 ⋈[Student.SID = Enroll.SID]
                       /                     \
σ[Major='CS' ∧ Year≥3]                       σ[Term='2025-S1' ∧ Grade='HD']
          |                                                |
       Student                                            Enroll


STAGE 5 (Push projections)

                     π[Name]
                        |
                     ⋈[SID]
                    /       \
            π[SID, Name]    π[SID]
               |              |
    σ[Major='CS' ∧ Year≥3]   σ[Term='2025-S1' ∧ Grade='HD']
               |              |
            Student          Enroll


STAGE 6 (Executable subtrees summary)

* Per-relation pipelines:
  * `π[SID,Name](σ[Major='CS' ∧ Year≥3](Student))`
  *` π[SID](σ[Term='2025-S1' ∧ Grade='HD'](Enroll))`
* Final join: `⋈[SID], then π[Name]`




### Exercise 2. Follow each step of the algorithm to produce an optimised query tree.

Relational Algebra:

$$
  \pi_{name, Title} (( \sigma_{Major='CS' AND Year>=3}(Student))
$$
$$
  \bowtie_{Student.SID = Enroll.SID}( \sigma_{Term='2025-S1' AND Grade='HD'}(Enroll))
$$
$$
\bowtie_{Enroll.CID = Course.CID} (\sigma_{Dept='CS' AND Credits>=6}(Course)))
$$

STAGE 0 (Naive)

                       π[Student.Name, Course.Title]
                                    |
σ[Student.SID=Enroll.SID ∧ Enroll.CID=Course.CID ∧
  Student.Major='CS' ∧ Student.Year≥3 ∧
  Enroll.Term='2025-S1' ∧ Enroll.Grade='HD' ∧
  Course.Dept='CS' ∧ Course.Credits≥6]
                                    |
                   (Student × Enroll × Course)


STAGE 1 (Break conjunctive selection)

                       π[Student.Name, Course.Title]
                                    |
                          σ[Student.SID=Enroll.SID]
                                    |
                          σ[Enroll.CID=Course.CID]
                                    |
                          σ[Student.Major='CS']
                                    |
                           σ[Student.Year≥3]
                                    |
                          σ[Enroll.Term='2025-S1']
                                    |
                           σ[Enroll.Grade='HD']
                                    |
                            σ[Course.Dept='CS']
                                    |
                           σ[Course.Credits≥6]
                                    |
                   (Student × Enroll × Course)


STAGE 2 (Push single-table selections to leaves)

                       π[Student.Name, Course.Title]
                                    |
                          σ[Student.SID=Enroll.SID]
                                    |
                          σ[Enroll.CID=Course.CID]
                                    |
                                  ×
                                 / \
                               ×     σ[Dept='CS' ∧ Credits≥6]
                              / \                |
        σ[Major='CS' ∧ Year≥3]   σ[Term='2025-S1' ∧ Grade='HD']   Course
                 |                          |
              Student                     Enroll


* STAGE 3 (Reorder to join the most selective first)
* Heuristic: (Enroll' ⋈[CID] Course') first, then ⋈[SID] Student'
* (structure realized in Stage 4)


STAGE 4 (Replace × + join-σ with explicit joins)

                       π[Student.Name, Course.Title]
                                    |
                         ⋈[Enroll.SID = Student.SID]
                                /                   \
                 ⋈[Enroll.CID = Course.CID]         σ[Major='CS' ∧ Year≥3]
                       /                 \                      |
      σ[Term='2025-S1' ∧ Grade='HD']     σ[Dept='CS' ∧ Credits≥6]   Student
                    |                                  |
                 Enroll                              Course


STAGE 5 (Push projections)

                       π[Name, Title]
                              |
                           ⋈[SID]
                         /        \
                     ⋈[CID]     π[SID, Name]
                    /     \          |
         π[SID, CID]     π[CID, Title]   σ[Major='CS' ∧ Year≥3]
            |                 |                 |
σ[Term='2025-S1' ∧ Grade='HD']  σ[Dept='CS' ∧ Credits≥6]       Student
            |                 |
          Enroll            Course


STAGE 6 (Executable subtrees summary)

* Per-relation pipelines:
  * `π[SID,Name](σ[Major='CS' ∧ Year≥3](Student))`
  * `π[SID,CID](σ[Term='2025-S1' ∧ Grade='HD'](Enroll))`
  * `π[CID,Title](σ[Dept='CS' ∧ Credits≥6](Course))`
* Joins:
  * First `⋈[CID] (Enroll' with Course')`
  * Then `⋈[SID] with Student'`
* Final `π[Name, Title]`

### Exercise 3. Follow each step of the algorithm to produce an optimised query tree.

================================================================================

* Stage 0 (baseline, naive plan)

Initial Relational algebra (everything at once):

$$
  \pi_{S.Name, C.Title, I.IName} (\sigma_θ(S × E × C × T × I))
$$

where θ is the conjunction of all predicates above.

Query tree:

                     π[S.Name, C.Title, I.IName]
                                |
                              σ[θ]
                                |
       ×────────────────────────────────────────────────×
       |                       |                        |
      S                       E                         ×
                                                     ┌──┴──┐
                                                     C     ×
                                                          ┌┴┐
                                                          T I

================================================================================

Step 1: Break conjunctive selections (rule 1)

* Relational algebra (split σ into a cascade):
* π_{S.Name, C.Title, I.IName}
*  σ_{E.SID=S.SID}
 * σ_{E.CID=C.CID}
 * σ_{T.CID=C.CID}
 * σ_{T.IID=I.IID}
 * σ_{T.Term=E.Term}
 * σ_{S.Major='CS'}
 * σ_{S.Year≥3}
 * σ_{E.Term='2025-S1'}
 * σ_{E.Grade='HD'}
 * σ_{C.Dept='CS'}
 * σ_{C.Credits≥6'}
 * σ_{I.Dept='CS'}
 * ( S × E × C × T × I )

Query tree (σ nodes listed top-down for readability):

                     π[S.Name, C.Title, I.IName]
                                |
                  σ[E.SID=S.SID] → σ[E.CID=C.CID] → σ[T.CID=C.CID]
                       → σ[T.IID=I.IID] → σ[T.Term=E.Term]
                       → σ[S.Major='CS'] → σ[S.Year≥3]
                       → σ[E.Term='2025-S1'] → σ[E.Grade='HD']
                       → σ[C.Dept='CS'] → σ[C.Credits≥6]
                       → σ[I.Dept='CS']
                                |
                       ×────────────────────×
                       |                    |
                      S                   (E × (C × (T × I)))

================================================================================

Step 2: Push selections down (rule 2: commutativity and “as far down as possible”)

* Single-relation σ push to leaves: S, E, C, I.
* Multi-relation σ (join conditions) must stay above the relevant combinations.

* Relational algebra (group per-relation selections):
* Let S' = σ_{S.Major='CS' ∧ S.Year≥3}(S)
* Let E' = σ_{E.Term='2025-S1' ∧ E.Grade='HD'}(E)
* Let C' = σ_{C.Dept='CS' ∧ C.Credits≥6}(C)
* Let I' = σ_{I.Dept='CS'}(I)

* π_{S.Name, C.Title, I.IName}
 * σ_{E.SID=S.SID}
 * σ_{E.CID=C.CID}
 * σ_{T.CID=C.CID}
 * σ_{T.IID=I.IID}
 * σ_{T.Term=E.Term}
 * ( S' × E' × C' × T × I' )

Query tree:

                     π[S.Name, C.Title, I.IName]
                                |
         σ[E.SID=S.SID] σ[E.CID=C.CID] σ[T.CID=C.CID] σ[T.IID=I.IID] σ[T.Term=E.Term]
                                |
                ×───────────────────────────────────────────────────────────×
                |                      |                |        |          |
              S' (leaf)               E' (leaf)        C'     T (leaf)     I' (leaf)

================================================================================

Step 3: Reorder joins using associativity/commutativity; execute most selective first

* Heuristic (with example selectivities):
* C' (~180 rows) ⋈ T (5k) on CID reduces T drastically (only CS courses with ≥6 credits).
* Join with I' (50 rows) on IID is highly selective (CS instructors only).
* E' (3k) then joins on (CID, Term), further reducing.
* S' (5k) joins on SID to add names.

* We aim to join small, selective subtrees first to keep intermediates small:
* Plan order: ((C' ⋈_{CID} T) ⋈_{IID} I') ⋈_{(CID,Term)} E' ⋈_{SID} S'

Query tree shape (reordered binary ops; still selections + × conceptually):

                     π[S.Name, C.Title, I.IName]
                                |
                   σ[join-preds applied at each join]
                                |
                           ⋈ on SID
                           /       \
                       ( ... )     S'
                         |
                    ⋈ on (CID,Term)
                    /             \
                 ( ... )          E'
                   |
                ⋈ on IID
                /       \
           (C' ⋈ on CID T)      I'

================================================================================

Step 4: Replace Cartesian product + σ with explicit JOINs

* Relational algebra (explicit joins; selections already pushed to leaves):
* J1 = C' ⋈_{C.CID = T.CID} T
* J2 = J1 ⋈_{T.IID = I.IID} I'
* J3 = J2 ⋈_{C.CID = E.CID ∧ T.Term = E.Term} E'
* J4 = J3 ⋈_{E.SID = S.SID} S'
* Result = π_{S.Name, C.Title, I.IName}(J4)

Query tree (explicit ⋈ with predicates):

                     π[S.Name, C.Title, I.IName]
                                |
                          ⋈[E.SID = S.SID]
                          /               \
                 ⋈[C.CID=E.CID ∧ T.Term=E.Term]   S'
                        /             \
                 ⋈[T.IID=I.IID]       E'
                   /         \
            ⋈[C.CID=T.CID]    I'
              /        \
             C'         T

================================================================================

Step 5: Push projections (retain only attributes needed for later joins or final output)

* Required attributes:
* Final: S.Name, C.Title, I.IName.
* Join keys:
  * S': SID (to join), Name (final)
  * E': SID, CID, Term (to join), Grade no longer needed after selection
  * C': CID (to join), Title (final)
  * T: CID, Term, IID (to join)
  * I': IID (to join), IName (final)

Add per-leaf projections after selections:

* S'' = π_{SID, Name}(S')
* E'' = π_{SID, CID, Term}(E')
* C'' = π_{CID, Title}(C')
* T'  = π_{CID, Term, IID}(T)
* I'' = π_{IID, IName}(I')

* Relational algebra (with projections in-tree):
* Result =

$$
   \pi_{S.Name, C.Title, I.IName}( (C) 
$$
$$
   \bowtie_{C.CID=T.CID} (T) 
$$
$$
   \bowtie_{T.IID=I.IID} (I)
$$
$$
   \bowtie_{C.CID=E.CID ∧ T.Term=E.Term} (E)
$$
$$
   \bowtie_{E.SID=S.SID} (S) )
$$

Query tree (showing π pushed to leaves):

                     π[S.Name, C.Title, I.IName]
                                |
                          ⋈[E.SID = S.SID]
                          /               \
                 ⋈[C.CID=E.CID ∧ T.Term=E.Term]   π_{SID,Name}(S')
                        /             \
                 ⋈[T.IID=I.IID]       π_{SID,CID,Term}(E')
                   /         \
         ⋈[C.CID=T.CID]      π_{IID,IName}(I')
           /        \
 π_{CID,Title}(C')   π_{CID,Term,IID}(T)

Notes:
* This eliminates unused columns early, reducing tuple width and I/O.
* All joins are equi-joins (ideal for hash join or merge join).

================================================================================

Step 6: Identify executable subtrees (algorithm/grouping choices)

* Good execution grouping with common algorithms:
* G1: Scan/Index + Filter + Project per base:
  * S'': index/bitmap on (Major, Year) if available; output (SID, Name).
  * E'': index on (Term, Grade) or on Term with predicate on Grade; output (SID, CID, Term).
  * C'': index on (Dept, Credits); output (CID, Title).
  * I'': index on (Dept); output (IID, IName).
  * T': scan/project to (CID, Term, IID).

* G2: Hash join subtree for course-teaching-instructor:
 * J1 = HashJoin key CID: build on small C'' (180 rows), probe T' (5k).
 * J2 = HashJoin key IID: build on small I'' (50 rows), probe J1.
 * Output carries only (CID, Term, IID, Title, IName).

* G3: Composite-key hash join with enrollment:
 * J3 = HashJoin key (CID, Term): build on J2 (small), probe E'' (3k).
 * Output retains (SID, Title, IName, CID, Term).

- G4: Final hash join with students:
 * J4 = HashJoin key SID: build on S'' (5k), probe J3 (~ up to a few thousand rows).
 * Final project to (Name, Title, IName).

This plan respects:
- Push-down of σ and π (Stages 2 and 5),
- Reordering to join the most selective subtrees first (Stage 3),
- Replacing × + σ by ⋈ (Stage 4),
- Grouping into natural hash-joinable blocks (Stage 6).

================================================================================

Summary of the optimized relational algebra

* Let:
 *  S'' = π_{SID, Name}(σ_{Major='CS' ∧ Year≥3}(Student))
 *  E'' = π_{SID, CID, Term}(σ_{Term='2025-S1' ∧ Grade='HD'}(Enroll))
 *  C'' = π_{CID, Title}(σ_{Dept='CS' ∧ Credits≥6}(Course))
 *  T'  = π_{CID, Term, IID}(Teaches)
 *  I'' = π_{IID, IName}(σ_{Dept='CS'}(Instructor))

Final:
π_{Name, Title, IName}(
  (
    (
      (C'' ⋈_{CID} T')
      ⋈_{IID} I''
    )
    ⋈_{(CID,Term)} E''
  )
  ⋈_{SID} S''
)

This is the end result of the six stages, with selections and projections pushed down, joins reordered for selectivity, and ×+σ rewritten as equi-joins.


---
 Remember that there are multiple ways to solve these problems, if you are unsure, post your solution in the workshop forums for discussion.