Relational Algebra (Part 2)

Core relational-algebra operators (review from last lecture)

• Given two relations R1(A, B, C) and R2(A, B, C).

• Selection: $\sigma<em>{A > 100}(R</em>1)$

• Projection: $\pi<em>{A, B}(R</em>1)$

• Union: R1  R2 (written as $R<em>1 \cup R</em>2$)

• Intersection: $R<em>1 \cap R</em>2$

• Difference: $R<em>1 - R</em>2$

• Natural join: $R<em>1 \bowtie R</em>2$

• Theta join: $R<em>1 \bowtie</em>{\;R1.A = R2.A \land R1.B < R2.B\;} R_2$

  • Example form shown: $R<em>1 \bowtie</em>{R1.A=R2.A \text{ AND } R1.B < R2.B} R_2$

This Lecture: additional operators and concepts

• Assignment (overview): T1 := $\sigma<em>{A > 100}(R</em>1)$

• Rename: rtest(A’, B’, C’) R1 (rename attributes of R1)

• Duplicate Elimination: d

• Extended Projection: P (projection with new attributes created via arithmetic)

• Grouping and Aggregation: g

Conceptual example and workflow visuals

• Concept: Make another copy of a table and give it a new name (rename/copy). Example: Evaluation1 := Quiz1; Over85 := $\sigma_{Score > 85}(Quiz1)$

• Note: All attribute names are retained when copied/renamed.

• Example data (Quiz1):

  • Name Score: Alice 70, Bob 90, Cathy 80, David 100

• Evaluation1 (copy of Quiz1 with only high scorers): Name Score: Bob 90, David 100

• Over85 (results of the selection on Quiz1): shows entries with Score > 85

Step-down into simpler representations

• Useful to break down steps: e.g., queries like q (PName Students) ⋈ (PName Volunteer)

• Equivalent representation:

  • q R1 := PName(Students)

  • q R2 := PName(Volunteer)

  • q R1 ⋈ R2

• This decomposition helps readability and maintainability of queries.

Rename (detailed example)

• Rename operation (r) allows changing attribute names without altering data.

• Example:

  • q: rEvaluation1 ← Quiz1

  • q rEval1(SName, QScore)

  • Original Quiz1 with attributes (Name, Score) and data unchanged; after rename: Evaluation1(SName, QScore) and rEval1(Name, Score) (aliases)

• This clarifies how output attributes are labeled in subsequent steps.

Exercise style and techniques (high level)

• Example problem: Find students who score higher than Cathy in Quiz1.

  • Start with R1 := select where Name = 'Cathy' in Quiz1

  • Build a second relation R2 by joining Quiz1 with R1 on the condition Quiz1.Score > R1.Score

  • Project desired attributes, producing a final list of students with higher scores than Cathy.

• Another common pattern: isolate the max (highest) score via aggregation, then join back to find the corresponding student(s).

Exercise: highest-scoring student in Quiz1 (rigorous approach)

• Step 1: R1 := Quiz1 ⋈ (Score = MaxScore) where MaxScore = MAX(Score) in Quiz1

• Step 2: R2 := Quiz1 ⋈ (Quiz1.Score = MaxScore) R1

• Step 3: R3 := π_Name(R2) (project only the Name column)

• Result example (from slides):

  • Quiz1: Name Score – Alice 70, Bob 90, Cathy 80, David 100

  • Quiz1 MaxScore = 100

  • R3 yields: David 100 (Name: David)

• Note: Aggregates can only be used with the aggregation operation g (grouping) in this context.

Exercise: second-highest in Quiz1

• Outline (as shown):

  • R1 := gMAX(Score) → MaxScore (Quiz1)

  • R2 := Quiz1 ⋈ (Score = MaxScore) (R1)

  • R3 := π_Name, Score(R2)

  • R4 := Quiz1 − R3 (subtract found max entry)

  • R5 := gMAX(Score) → 2ndMaxScore(R4)

  • R6 := R4 ⋈ (Score = 2ndMaxScore(R5))

• Example outcome: 2nd highest score is 90 (e.g., Bob with 90), depending on data order.

Exercise: per-school highest-scoring student in Quiz1

• Goal: For each School, find the student who scores the highest in Quiz1.

• Steps shown:

  • R1 := Quiz1 ⋈ Student

  • R2 := g School, MAX(Score) → MaxScore(R1) (group by School, compute per-school max)

  • R3 := R1 ⋈ (R1.School = R2.School) AND (Score = MaxScore(R1))

  • R3 := π_Name, Score(R3)

• Example results format:

  • Quiz1: Name Score; School mapping, e.g., Alice 70 SCSE; Bob 90 EEE; Cathy 80 EEE; David 100 SCSE

  • Final per-school max results: SCSE → 100, EEE → 90

Exercise: all courses from SCSE taken by a student

• Problem: Find students who have taken all courses offered by SCSE.

• Approach (as shown):

  • R1 := sSchool = 'SCSE' ∧ CrsSch (restriction on School SCSE courses in CrsSch)

  • R2 := Grades ⋈ (R1) (join Grades with SCSE courses)

  • R3 := g_Name, COUNT(Course) → CrsCNT(R2) (count courses taken by each student within SCSE)

  • R4 := g_COUNT(Course) → ScseCNT(R1) (count total SCSE courses offered)

  • R5 := R3 ⋈ CrsCNT = ScseCNT(R4) (students whose taken count matches total SCSE courses)

  • R6 := π_Name(R5) (names of students who took all SCSE courses)

• Example data (subset shown):

  • Grades: (Alice, DB, A), (Alice, DM, C), (Bob, DB, B), (Bob, NN, B), (Cathy, SP, B)

  • CrsSch contains: (DB, SCSE), (DM, SCSE), (NN, EEE), (SP, EEE)

• Resulting set includes students who have taken all SCSE courses (e.g., Alice and Bob in the example, depending on data).

Exercise: per-school students who have taken all courses in the school

• Problem: For each school, find students who have taken all courses offered in that school.

• Approach (as shown):

  • R1 := Grades ⋈ CrsSch (join grades with courses in each school)

  • R2 := g_Name, School, COUNT(Course) → CrsCNT(R1) (per-student per-school course counts)

  • R3 := g_School, COUNT(Course) → CrsCNT(CrsSch) (per-school course counts from CrsSch)

  • R4 := R2 ⋈ R2.School = R3.School AND R2.CrsCNT = R3.CrsCNT (match student counts to school totals)

  • R5 := π_Name(R4) (names of students who took all courses in their school)

• Example data (subset shown):

  • Grades: (Alice, DB, A), (Alice, DM, C), (Bob, DB, B), (Bob, NN, B), (Cathy, SP, B)

  • CrsSch: (DB, SCSE), (DM, SCSE), (NN, EEE), (SP, EEE)

• Result: List of students per school who took all courses offered by that school (e.g., Alice for SCSE, Bob for EEE, etc.).

Extended projection (P): creating new attributes via arithmetic

• Concept: Similar to ordinary projection, but allows creation of new attributes via arithmetic expressions.

• Example 1: For each student, total score in Quiz1 and Quiz2:

  • Expression: TotalScores = Quiz1 + Quiz2

  • Projection: $\pi_{Name, TotalScores}(R)$

  • Data example:

  • Name: Alice, Quiz1: 70, Quiz2: 90 → TotalScores: 160

  • Bob: 90, 80 → 170

  • Cathy: 80, 100 → 180

  • David: 100, 90 → 190

• Example 2: For each student, average score in Quiz1 and Quiz2:

  • Expression: Average = (Quiz1 + Quiz2) / 2

  • Projection: $\pi_{Name, Average}(R)$

  • Data example:

  • Alice: (70 + 90)/2 = 80

  • Bob: (90 + 80)/2 = 85

  • Cathy: (80 + 100)/2 = 90

  • David: (100 + 90)/2 = 95

Grouping and Aggregation (g)

• Purpose: Compute aggregate statistics by grouping (by attributes).

• Common aggregates: $\mathrm{MAX}(\cdot), \mathrm{MIN}(\cdot), \mathrm{AVG}(\cdot), \mathrm{SUM}(\cdot), \mathrm{COUNT}(\cdot)$

• Notation:

  • g_{GroupKey} , AGG(Attr) → ResultAttr

• Example: Find the highest score in Quiz1

  • Query form: $g_{\text{(none)}}(\mathrm{MAX}(Score)) \rightarrow \text{MaxScore}$ in Quiz1

  • Data example (Quiz1):

  • Alice SCSE 90

  • Bob EEE 80

  • Cathy EEE 100

  • David SCSE 90

  • Result: Quiz1 MaxScore = 100

• Example: Find the lowest score in Quiz1

  • $g_{\text{(none)}}(\mathrm{MIN}(Score)) \rightarrow \text{MinScore}$

  • Result: 80

• Example: Find the average score in Quiz1

  • $g_{\text{(none)}}, \mathrm{AVG}(Score) \rightarrow \text{AvgScore}$

  • Result: AvgScore = 90

  • Per-tuple display example included (Alice 90, Bob 80, Cathy 100, David 90 in Quiz1; AvgScore 90)

• Example: Find the sum of scores in Quiz1

  • $g_{\text{(none)}}, \mathrm{SUM}(Score) \rightarrow \text{SumScore}$

  • Result: SumScore = 360

• Example: Find the number of students in Quiz1

  • $g_{\text{(none)}}, \mathrm{COUNT}(Name) \rightarrow \text{NumStu}$

  • Also shown: COUNT(School) and COUNT(Score) yield NumStu = 4

• Advanced grouping examples

  • Find the average GPA in each school:

  • $g_{School}, \mathrm{AVG}(GPA) \rightarrow \text{AvgGPA}$

  • Data example: Student rows with School and GPA; per-school averages computed (SCSE: 3.8, EEE: 3.2). A per-student table is also shown alongside.

  • Find the average GPA and the highest GPA in each school:

  • $g_{School}, \mathrm{AVG}(GPA) \rightarrow \text{AvgGPA},\; \mathrm{MAX}(GPA) \rightarrow \text{MaxGPA}$

  • Example results: SCSE AvgGPA 3.8, MaxGPA 4; EEE AvgGPA 3.2, MaxGPA 3.4

  • Grouping by composite keys: $g_{School, Year}, \mathrm{AVG}(GPA) \rightarrow \text{AvgGPA}$

  • Example results show GPA per (School, Year) groups and per-school Year aggregates.

Example: end-to-end uses of grouping/aggregation

• Example: Find the student that scores the highest in Quiz1

  • Important note: Aggregates must be used with g (not standalone).

  • Steps (as shown):

  • R1 := gMAX(Score) → MaxScore(Quiz1)

  • R2 := Quiz1 ⋈ Score = MaxScore

  • R3 := π_Name(R2)

  • Result example: David with 100 (MaxScore 100)

• Example: Find the student that scores the second highest in Quiz1

  • Steps: as described in slides, using MaxScore, removing the top scorer, then taking the next max, etc.

Summary of notation and practical tips

• Basic operations:

  • Selection: $\sigma_{condition}(R)$

  • Projection: $\pi_{attributes}(R)$

  • Union: $R<em>1 \cup R</em>2$

  • Intersection: $R<em>1 \cap R</em>2$

  • Difference: $R<em>1 - R</em>2$

  • Natural join: $R<em>1 \bowtie R</em>2$

  • Theta join: $R<em>1 \bowtie</em>{condition} R_2$

• Extended constructs:

  • Rename: rename attributes of a relation (e.g., to align with subsequent operations)

  • Duplicate elimination: $d(R)$

  • Extended projection: project with new attributes via arithmetic (e.g., TotalScores = Quiz1 + Quiz2)

  • Grouping and aggregation: $g_{GroupKey}(AGG(Attribute)) \rightarrow Output$

• Practical patterns to remember:

  • Break complex queries into smaller steps (as shown with R1, R2, R3, …) to improve readability.

  • Use aggregation (g) to compute max/min/avg/sum/count, and then join back to identify the corresponding tuples.

  • For per-group results (e.g., per school), include the grouping keys (School, Year, etc.) in the g operation to partition the data.

  • For multiple aggregations in one query, include multiple AGG(Attribute) parts in the g operation (e.g., AVG(GPA) and MAX(GPA)).

Quick reference: selected formulas and notations

• Selection: $\sigma<em>{A > 100}(R</em>1)$

• Projection: $\pi<em>{A,B}(R</em>1)$

• Union/Intersection/Difference: $R<em>1 \cup R</em>2,\, R<em>1 \cap R</em>2,\, R<em>1 - R</em>2$

• Natural join: $R<em>1 \bowtie R</em>2$

• Theta join: $R<em>1 \bowtie</em>{R1.A=R2.A \land R1.B < R2.B} R_2$

• Rename: e.g., $\rho_{A'\leftarrow A, B'\leftarrow B}(R)$ or rtest(A', B', C') R1

• Duplicate elimination: $d(R)$

• Extended projection example: TotalScores = Quiz1 + Quiz2, then $\pi_{Name, TotalScores}(R)$

• Arithmetic average example: Average = \frac{Quiz1 + Quiz2}{2}, then $\pi_{Name, Average}(R)$

• Aggregation notation (examples):

  • Highest score: $g_{\text{,}} \mathrm{MAX}(Score) \rightarrow \text{MaxScore}$

  • Lowest score: $g_{\text{,}} \mathrm{MIN}(Score) \rightarrow \text{MinScore}$

  • Average: $g_{\text{,}} \mathrm{AVG}(Score) \rightarrow \text{AvgScore}$

  • Sum: $g_{\text{,}} \mathrm{SUM}(Score) \rightarrow \text{SumScore}$

  • Count: $g_{\text{,}} \mathrm{COUNT}(Name) \rightarrow \text{NumStu}$

• Example: per-school average GPA

  • $g_{School}, \mathrm{AVG}(GPA) \rightarrow \text{AvgGPA}$ with sample output: SCSE 3.8, EEE 3.2

• Example: per-school highest GPA

  • $g_{School}, \mathrm{AVG}(GPA) \rightarrow \text{AvgGPA}, \mathrm{MAX}(GPA) \rightarrow \text{MaxGPA}$ with outputs like: SCSE AvgGPA 3.8, MaxGPA 4; EEE AvgGPA 3.2, MaxGPA 3.4

• Composite grouping: $g_{School, Year}, \mathrm{AVG}(GPA) \rightarrow \text{AvgGPA}$ to group by a two-attribute key

Next: Relational Algebra (3)

• The next lecture continues with Relational Algebra (3) [see last page: “Next lecture: Topic 5: Relational Algebra (3)”].

• Focus areas will likely extend to more complex aggregations, joins, and practical query optimization strategies.