Relational Algebra: Division and Outer Joins (Part 3)

Division (÷)

  • Definition: Given a relation R1(A, B) and a relation R2(B), the division R1 ÷ R2 returns the set of A-values that are associated with every B in R2.

    • Formal intuition: the result contains those A for which, for all B present in R2, the pair (A, B) is in R1.

    • Formal notation (one way):
      R1(A,B)÷R2(B)=a∣∀b∈πB(R2):(a,b)∈R1R1(A,B) \div R2(B) = { a \mid \forall b \in \pi_B(R2): (a,b) \in R1 }

    • Note on attributes: In general, the result contains the attributes of R1 that are not in R2. If R1 has attributes (A, B) and R2 has (B), the result will have attribute A (potentially with duplicates removed).

    • Key idea: Find all A-values that are linked to every B-value present in R2.

  • Intuition and interpretation:

    • Intuitive interpretation: “Find the A that is related to all B values in R2.”

    • In words: identify the entities in R1 that are associated with every item in R2.

  • General pattern and properties:

    • The operation yields a relation with attributes from R1 that are not in R2.

    • It is often used to express “universal quantification” over the second relation (e.g., have joined all clubs, own all Apple products).

  • Example 1: Find each person that owns all Apple products

    • Data setup:

    • R1 = Owns(Name, Product)

      • Alice, iPhone

      • Alice, iPad

      • Bob, iPhone

      • Cathy, iPad

    • AppleP(Product, Price)

      • iPhone, 999

      • iPad, 699

    • Query: Owns ÷ AppleP

    • Semantics: return the set of Name values such that for every product in AppleP, (Name, Product) is in Owns.

    • Result: Only Alice satisfies owning both Apple products (iPhone and iPad).

  • Example 2: Find each person that has joined all clubs

    • Data setup:

    • R1 = Joins(Name, Club)

      • Alice, ABC

      • Bob, DEF

      • Bob, ABC

      • Cathy, DEF

    • Clubs = {ABC, DEF}

    • Query: Joins ÷ Clubs

    • Result: Bob is the only person who joined all clubs (ABC and DEF).

    • Note: If no A in R1 is associated with every B in R2, the division yields an empty result (No result).

  • Correcting a potential pitfall with AppleP example (price attribute):

    • If you attempt Owns ÷ AppleP where AppleP = (Product, Price) but Owns has (Name, Product) only, the result is defined over the A-attributes of R1 not in R2. A common mistake is to try to include attributes that appear in R2 (e.g., Price) in the division result; those are not retained in the division result.

    • Correct form to illustrate a nontrivial result when R1 has additional attributes:

    • R1 = Owns(Name, Product, Since)

    • R2 = AppleP(Product, Price)

    • Result: Name, Since (only attributes from R1 not in R2).

    • Concrete observation from the slides:

    • With Owns(Name, Product, Since) and AppleP(Product, Price), the division Owns ÷ AppleP yields rows containing Name and Since for those Names that own all Apple products (iPhone and iPad). Example result for the dataset shown:

      • Alice 2013

      • Alice 2013

      • Bob 2013

      • Bob 2010

    • The extra Product attribute is eliminated in the division result; you get the Name–Since combinations that accompany ownership of all Apple products.

  • Exercise-related notes (Week 6 slides):

    • Exercise 1 (SCSE courses):

    • R1 := sSchool = 'SCSE' CrsSch

    • R2 := PCourse

    • R3 := PName, Course (Grades)

    • R4 := R3 ÷ R2

    • Sample result structure (Name, Course, Grade):

      • Alice, DB, A

      • Alice, DM, C

      • Bob, DB, B

      • Bob, NN, B

      • Cathy, SP, B

      • Cathy, NN, A

    • Exercise 2 (SCSE all courses but not all EEE):

    • R1 := PCourse (sSchool = 'SCSE' CrsSch)

    • R2 := PName, Course (Grades)

    • R3 := R2 ÷ R1

    • R4 := PCourse (sSchool = 'EEE' CrsSch)

    • R5 := PName, Course (Grades)

    • R6 := R3 – (R5 ÷ R4)

    • Sample result structure (Name, Course, Grade):

      • Alice, DB, A

      • Alice, DM, C

      • Bob, DB, B

      • Bob, NN, B

      • Cathy, SP, B

      • Cathy, NN, A

    • Interpretation: Identify students who have taken all SCSE courses but not all EEE courses.

Left Outerjoin (⋈L)

  • Definition and behavior:

    • Syntax: R1 ⋈L_condition R2

    • Semantics: All tuples from the left relation R1 are retained. For matching tuples in R2, their attributes are joined; for left tuples with no match in R2, the right-side attributes are filled with NULLs.

    • Example (SCSE donations):

    • Given:

      • Students(Name, School):

      • Alice, SCSE

      • Bob, EEE

      • Cathy, CEE

      • David, SCSE

      • Donations(Name, School, Amount):

      • Cathy, CEE, 100

      • David, SCSE, 200

      • Eddie, EEE, 300

      • Fred, SCSE, 400

    • Query: Students ⋈L Donations (join on matching Name and possibly School when natural join is used)

    • Result concept: For each student, include Donation.Amount if present; otherwise Amount = NULL.

    • Expected result structure (Name, School, Amount):

      • Alice, SCSE, NULL

      • Bob, EEE, NULL

      • Cathy, CEE, 100

      • David, SCSE, 200

  • Variant with explicit theta-join condition (Sname = Name) keeps all attributes from both sides and fills NULLs where there is no match, e.g. for Cathy, David alignments, etc.

Right Outerjoin (⋈R)

  • Definition and behavior:

    • Syntax: R1 ⋈R_condition R2

    • Semantics: All tuples from the right relation R2 are retained. If there is no matching tuple in R1, the left-side attributes are filled with NULLs.

    • Example (donors and schools):

    • With the same Students and Donations, the right outer join yields all donors from Donations, with their school filled when known from Students and NULL when not found in Students.

    • Result structure (Name, School, Amount) from the slide example:

      • Cathy, CEE, 100

      • David, SCSE, 200

      • Eddie, NULL, 300

      • Fred, NULL, 400

    • Variant (Sname = Name) preserves all attributes and uses NULLs to indicate non-matches on the left side as appropriate.

Full Outerjoin (⋈)

  • Definition and behavior:

    • Semantics: The combination of left and right outer joins. All tuples from both R1 and R2 are retained. Where there are no matches, NULLs fill the missing side.

    • Example (Students ⋈ Donations):

    • Result structure (Name, School, Amount) with NULLs where there is no match on either side.

    • Example rows (illustrative):

      • Alice, SCSE, NULL

      • Bob, NULL, NULL

      • Cathy, CEE, 100

      • David, SCSE, 200

      • Eddie, NULL, NULL

      • Fred, NULL, 400

Example: Counting male stars in movies (Relational Algebra workflow)

  • Scenario: For each movie, count the number of male movie stars cast in the movie.

  • Data pieces:

    • Stars(Name, Gender, Birth)

    • John, Male, 1980

    • Meg, Female, 1981

    • Steve, Male, 1990

    • CastIn(Name, Movie, Year)

    • John, Batman, 2012

    • Steve, Batman, 2012

    • Meg, The Women, 2008

  • Method 1 (R1 → filter, R2 → join, R3 → group):

    • R1 := sGender = 'Male' Stars

    • R2 := CastIn ⋈L R1

    • R3 := gMovie, COUNT(Gender) à MaleStars (R2)

    • Result example (Movie, MaleStars):

    • Batman, 2

    • The Women, 0

  • Method 2 (alternative counting using name grouping):

    • R1 := sGender = 'Male' Stars

    • R2 := gName, COUNT(Gender) à Male (R1)

    • R3 := CastIn ⋈L R2

    • R4 := gMovie, SUM(Male) à MaleStars (R3)

    • Result example (Movie, MaleStars):

    • Batman, 2

    • The Women, 0

  • Notes on intermediate results:

    • With the given dataset, Batman has 2 male stars (John and Steve).

    • The Women has 0 male stars (Meg is female).

    • Different counting strategies yield consistent final tallies, illustrating two equivalent approaches to aggregation after joins.

Quick dataset references from the slides

  • Example: Dataset for division with AppleP and Owns (illustrative values)

    • Owns(Name, Product) rows: {Alice,iPhone}, {Alice,iPad}, {Bob,iPhone}, {Cathy,iPad}

    • AppleP(Product, Price) rows: {iPhone, 999}, {iPad, 699}

  • Example: Dataset for SCSE/EEE exercises (Grades table excerpt)

    • Names: Alice, Bob, Cathy

    • Courses: DB, DM, NN, SP

    • Grades: A, B, C, etc.

    • CrsSch mapping (course to school): {DB, DM → SCSE}, {NN, SP → EEE}

  • Example: Donation dataset for left/right outer joins

    • Students(Name, School): Alice/SCSE, Bob/EEE, Cathy/CEE, David/SCSE

    • Donations(Name, School, Amount): Cathy/CEE/100, David/SCSE/200, Eddie/EEE/300, Fred/SCSE/400

  • Last lecture operations (brief recap):

    • T1 := σA > 100 (R1) // selection

    • Rename: rtest(A', B', C')

    • Duplicate Elimination: δ or d

    • Extended Projection: P

    • Grouping and Aggregation: g

    • These are used to build more complex relational algebra expressions and to prepare the basis for division and joins in practice.

  • Real-world relevance and implications:

    • Division enables universal quantification queries common in access control, inventory, and user-coverage checks (e.g., who has all required items).

    • Outer joins (left, right, full) are essential when you want to preserve information from one side regardless of matches on the other side, which is important in reporting and data integration.

    • Counting and aggregation after joins enable analytics (e.g., how many male stars per movie) and can be implemented via grouping/aggregation operations in relational algebra or SQL.

  • References to core principles:

    • Division embodies a universal quantification concept over a relation.

    • Outer joins extend standard join semantics to preserve unmatched tuples, which is critical for preserving domain knowledge in datasets with incomplete matches.

Note: The examples above and the exact numbers are taken from the provided slides. In practice, ensure that the attribute names and join conditions match your schema when applying division or outer joins to your own data.