Relational Algebra (Part 1)

Lecture Overview

• Topic: Relational Algebra (1)

• Focus: Motivation for relational algebra and relational algebraic operators

• Core operators introduced:

  • Selection: $\sigma$A > 100 R_1

  • Projection: $\pi$ A, B R_1

  • 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: R1 \bowtie{R1.A=R2.A \text{ AND } R1.B < R2.B}} R_2

• The material covers examples, properties, and common pitfalls of combining operators.

Why Relational Algebra? Motivation

• There is a complete design flow for a database application:

  • Use ER-diagrams for conceptual design.

  • Transform ER-diagrams into a database schema (tables).

  • Normalize the schema and insert tuples.

  • Query the data using a query language.

• RA provides a formal, mathematical basis for queries on relations (tables).

• SQL provides a user-facing query language; RA provides the algebraic foundation that underpins SQL queries.

• Visual: User interacts with a Query Interface; Processing Engine executes the RA or SQL query against the Database.

Relational Algebra: Basic Concepts

• A relation is a table with a fixed schema (attribute names and types).

• Relational algebra uses operators to form new relations from existing ones.

• Example relations used in slides:

  • Students(ID, Name, Age, School)

  • Results(ID, Name, Age, School)

  • Grades(Name, Course, Grade)

  • CrsSch(Name, School)

• Basic notations:

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

  • Projection: $\pi_{A,B,…}(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>{\text{condition}} R_2$

• Note: In union, intersection, and difference, the two operands must have the same schema (same set of attributes).

• For natural join, the join is performed on common attributes; the common attributes appear only once in the result.

Selection (σ) — Row-wise Operation

• Meaning: filter rows based on a predicate.

• Example 1: Find the student named Alice

  • Given Students(ID, Name, Age, School):

  • (1234, Alice, 20, SCSE), (5678, Bob, 20, EEE), (3742, Cathy, 22, SCSE), (9413, David, 21, CEE)

  • Query: $\sigma_{\text{Name} = 'Alice'}(\text{Students})$

  • Result: only (1234, Alice, 20, SCSE)

• Example 2: Find students in SCSE

  • Query: $\sigma_{\text{School} = 'SCSE'}(\text{Students})$

  • Result: (1234, Alice, 20, SCSE), (3742, Cathy, 22, SCSE)

• Example 3: Find SCSE students under 21

  • Query: $\sigma_{\text{School} = 'SCSE' \land \text{Age} < 21}(\text{Students})$

  • Result: (1234, Alice, 20, SCSE)

• Example 4: Find students who are either in SCSE or under 21

  • Query: $\sigma<em>{\text{School} = 'SCSE'}(\text{Students}) \; \cup \; \sigma</em>{\text{Age} < 21}(\text{Students})$

  • Result: union of {Alice in SCSE, Cathy in SCSE} with {Alice 20 SCSE, Bob 20 EEE, David 21 CEE}

• Key point: Selection operates on rows; it does not alter the schema.

Projection (π) — Column-wise Operation

• Meaning: produce a relation with a subset of columns (attributes).

• Example: Find IDs and Names of all students

  • Query: $\pi_{\text{ID}, \text{Name}}(\text{Students})$

  • Result: { (1234, Alice), (5678, Bob), (3742, Cathy), (9413, David) }

• Important: Projection reduces attributes; it may impact subsequent operations that require certain attributes.

Combining Operators: Example

• Example: Find IDs and Names of all students in SCSE

  • Step 1: Selection: $\sigma_{\text{School} = 'SCSE'}(\text{Students})$

  • Step 2: Projection: $\pi<em>{\text{ID}, \text{Name}}(\sigma</em>{\text{School} = 'SCSE'}(\text{Students}))$

  • Result: { (1234, Alice), (3742, Cathy) }

• Wrong approach (to illustrate order-of-ops pitfall): projection before selection

  • If you project first to (ID, Name) and then apply a selection based on School, you lose the School attribute, so the selection cannot be performed.

  • Correct approach is to apply selection first, then projection: $\pi<em>{\text{ID}, \text{Name}}(\sigma</em>{\text{School} = 'SCSE'}(\text{Students}))$

Union (⋃) — Set Union

• Meaning: combine tuples from two relations with the same schema, removing duplicates.

• Example: Students ⋃ Volunteer, given:

  • Students(Name, Age): { (Alice, 20), (Bob, 21), (Cathy, 22), (David, 21) }

  • Volunteer(Name, Age): { (Alice, 20), (Bob, 21), (Cathy, 22), (David, 21), (Eddie, 43), (Fred, 35) }

• Result: { (Alice, 20), (Bob, 21), (Cathy, 22), (David, 21), (Eddie, 43), (Fred, 35) }

• Note: Duplicates are automatically removed.

Intersection (⋂)

• Meaning: return tuples that appear in both relations; duplicates removed.

• Example: (PName Students) ⋂ Volunteer

  • If PName is a projection to Name, then the intersection yields names appearing in both sets, e.g., { Cathy, David } (depending on data).

• Note: The two operands must have the same schema; for intersection, the attributes must align exactly.

Difference (−)

• Meaning: find tuples that are in the first relation but not in the second.

• Example: Students − Volunteer

  • Result: tuples that are in Students but not in Volunteer, e.g., { Alice, Bob } if Cathy and David are in Volunteer as well.

• Note: Duplicates are automatically removed in the result.

Natural Join (⋈)

• Meaning: join two relations on their common attributes; common attributes appear only once in the result.

• Example 1: Natural join on NRIC between Students and Phones

  • Students: (NRIC, Name)

  • Phones: (NRIC, Name, Number)

  • Result: (NRIC, Name, Number) with the matching NRICs; if a student has multiple phone numbers, there will be multiple rows for that student (one per phone).

  • Sample match: NRIC 11, Name Alice connects to Number 9123234 and 8635168; NRIC 33, Cathy connects to 8213654.

• Example 2: Natural join between Students and Donations

  • Donations: (Name, School, Amount)

  • Students: (Name, School)

  • Result: (Name, School, Amount) for students who donated; e.g., Cathy (CEE, 100), David (SCSE, 200), Eddie (SCSE, 300), Fred (??? 400).

• Example 3 (SCSE donors): (Students ⋈ Donations) with a condition on School can yield only matching rows where the student donated and the student’s school matches the Donations table as appropriate.

Theta Join (⋈ with condition)

• Meaning: a join with an arbitrary condition, not limited to equality on shared attributes.

• General form: $R<em>1 \bowtie</em>{\text{condition}} R_2$

• Note: Unlike natural join, attributes may be duplicated in the result; duplicates are not automatically removed.

• Example 1: Donors joined to Students on name equality

  • Condition: Sname = Name between Students and Donations

  • Result: Rows combining matching records; may include both student and donation attributes.

• Example 2: Inequality join (Quiz scores)

  • Data: Quiz1(Name, Score1), Quiz2(Name, Score2)

  • Join: Quiz1.Name = Quiz2.Name AND Quiz1.Score1 < Quiz2.Score2

  • Result: Pairs of (Name, Score1, Name, Score2) where the same student appears in both quizzes and Score2 is greater.

  • Note: When attributes have the same name, qualify with table names to avoid ambiguity (e.g., Quiz1.Score, Quiz2.Score).

• Takeaway: Theta joins enable a wide range of relational comparisons beyond simple equality.

Cartesian Product (×)

• Meaning: cross product of two relations; yields every combination of tuples from the two relations.

• Notation: $R \times S$

• Example: Students × Donations

  • Students: (Name, Age)

  • Donations: (Name, School, Amount)

  • Result: All combinations of a student with a donation entry; not a meaningful query by itself but a building block for joins.

• Practical use: Typically followed by a selection (σ) to restrict to meaningful pairs.

Important Evaluation Notes

• Order of operations matters in some cases due to attribute visibility:

  • Projecting away attributes used in a subsequent selection can make the selection impossible to evaluate.

  • Example: π{ID, Name}(σ{School='SCSE'}(Students)) is fine; but σ{School='SCSE'}(π{ID, Name}(Students)) may not be possible if School is not projected.

• Replacement rules: RA allows many equivalences; e.g., you can push selections before/after projections when safe, but you must ensure the required attributes for the predicate are preserved.

• Schema compatibility rules:

  • Union, Intersection, and Difference require the same attribute names and order (same schema).

  • For Union, you can project each side to a common schema first if needed (e.g., (PName Students) ∪ Volunteer).

• Natural join automatically eliminates duplicates of common attributes; theta joins do not.

• When using projection with multiple attributes, consider whether you still need attributes for subsequent operations (e.g., selections, joins).

Exercise Highlights (Representative Queries)

• Exercise 1: Find the students who have taken DB and DM, but not AI or CG

  • Let Grades(Name, Course, Grade) and use projection to Name: $G<em>{DB} = \pi</em>{Name}(\sigma_{Course='DB'}(Grades))$

  • Let $G<em>{DM} = \pi</em>{Name}(\sigma_{Course='DM'}(Grades))$

  • Let $G<em>{AI} = \pi</em>{Name}(\sigma<em>{Course='AI'}(Grades))$ and $G</em>{CG} = \pi<em>{Name}(\sigma</em>{Course='CG'}(Grades))$

  • Excluded set: $G<em>{AI\cup CG} = G</em>{AI} \cup G_{CG}$

  • Final: $(G<em>{DB} \cap G</em>{DM}) - G_{AI\cup CG}$

  • Intuition: Names who took both DB and DM but neither AI nor CG.

• Exercise 2: Find the students who have taken only EEE courses

  • Use projections and set-difference to exclude non-EEE course takers.

  • A typical pattern: Names with only EEE courses after removing those who took any non-EEE course.

• Exercise 3: Find the students who have taken SCSE courses but not EEE courses

  • Use a combination of natural joins (or joins on course-school mappings) and set difference to exclude those who took EEE.

• Exercise 4: Find the students who have taken SCSE courses and not EEE courses (alternative formulations)

  • Often expressed as: $PName( Grades \bowtie (sSchool='SCSE' CrsSch)) - PName( Grades \bowtie (sSchool='EEE' CrsSch))$

  • Depending on schema, you may project to Name first, or keep additional attributes as needed to enforce the condition.

Additional Natural Join Examples (Practical Artefacts)

• NRIC/Phone Join (Students ⋈ Phones)

  • Students: (NRIC, Name)

  • Phones: (NRIC, Name, Number)

  • Result: Each student with all their phone numbers; if a student has multiple numbers, multiple rows appear (one per Number).

• Donor Join (Students ⋈ Donations)

  • Students: (Name, School)

  • Donations: (Name, School, Amount)

  • Result: For students who donated, include their Name, School, and donation Amount.

• SCSE Donors (Students ⋈ Donations with filter)

  • Example: For SCSE students who donated, include their Name, School, and donated Amount.

• Practical note: Natural joins are convenient when two relations share attributes with the same names and semantics; theta joins provide more flexible criteria.

Summary of Key Points

• Relational Algebra provides a formal toolkit for querying relations with operators: σ (selection), π (projection), ⋃ (union), ⋂ (intersection), − (difference), ⋈ (natural join), and ⋈ with conditions (theta join).

• The order of operations matters when composing RA expressions; ensure required attributes are preserved for downstream operations.

• Schema compatibility rules are crucial for union/intersection/difference (same attributes).

• Natural join removes duplicate common attributes; theta joins do not inherently deduplicate.

• Cartesian product is a fundamental operation that, when combined with σ, can form many useful queries but often produces large intermediate results; it is typically followed by a σ to filter.

• Exercises demonstrate composing multiple RA operators to express non-trivial queries (e.g., take-all-but-exclude patterns, multi-join conditions).

Next: Relational Algebra (2)

• The next lecture continues with deeper RA topics and more complex query formulations.