Division and for-all queries

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

1. What does R ⟕ S add to R ⋈ S? from Lesson 3.1.4
2. Write "for all x, P(x)" using ∃. from Lesson 0.2.3
3. What does "not" in English usually become in RA? from Lesson 3.1.2

1 · The Hook

"Students who took every CS course." Selection checks one row; join checks one pair; neither can say "every". The trick from Lesson 0.2.3 is to turn for all into no counter-example: find the students who are missing some CS course, and subtract them. Relational algebra packages this trick into one operator: division.

2 · Predict First

CS courses are C1 and C2. From ENROLL, which students took both?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

Predict First — the answer

Roll 1 (C1, C2, C3) and roll 3 (C1, C2). Roll 2 took only C3; roll 4 took only C4. Answer {1, 3}: πroll, cid(ENROLL) ÷ πcid(σdept='CS'(COURSE)).

Definition

Let R have attributes X ∪ Y and S have attributes Y. R ÷ S is the set of X-values x such that for every tuple y in S, the tuple (x, y) is in R.

• Result attributes: X = attributes of R not in S.
• Read it as: "x's whose set of partners in R contains all of S".

Division from basic operators

1. Candidates: C = πX(R).
2. Every pair that should exist: C × S.
3. Pairs that are missing: (C × S) − R.
4. Candidates with something missing: πX((C × S) − R).
5. R ÷ S = πX(R) − πX((πX(R) × S) − R).

This is ∀ = ¬∃¬ in algebra form: keep candidates for whom no missing pair exists.

Worked trace

R = πroll, cid(ENROLL), S = {C1, C2}.

1. C = {1, 2, 3, 4}.
2. C × S = 8 pairs.
3. Missing = {(2, C1), (2, C2), (4, C1), (4, C2)}.
4. πroll(missing) = {2, 4}.
5. {1, 2, 3, 4} − {2, 4} = {1, 3}.

Edge cases

• If S is empty, every candidate qualifies (vacuous truth): R ÷ ∅ = πX(R).
• Division uses only candidates in R: a student with no enrolment at all is never in the result, even if S is empty.
• Dividing by all courses {C1, C2, C3, C4}: nobody took all four → ∅.

Size rule

Recognising division

Words: every, all, each of, at least all the. "Students who took all courses taught in their department" or "suppliers who supply every red part". Always divide a relation with (answer attributes, matching attributes) by a relation of matching attributes only: project both carefully first.

4 · Visual

R = π roll,cid (ENROLL)        S = CS courses        candidates x S          missing pairs
roll cid                       cid                   (1,C1)(1,C2)            (2,C1)(2,C2)
 1  C1                          C1                   (2,C1)(2,C2)            (4,C1)(4,C2)
 1  C2                          C2                   (3,C1)(3,C2)
 1  C3                                               (4,C1)(4,C2)            students missing
 2  C3                                                                       something: {2,4}
 3  C1
 3  C2                         R ÷ S = {1,2,3,4} - {2,4} = {1,3}
 4  C4

5 · Worked Examples

Example 1 Easy

R(A, B) = {(a1, b1), (a1, b2), (a2, b1), (a3, b2)}, S(B) = {b1, b2}. Find R ÷ S.

Solution

a1 has b1 and b2 → in. a2 lacks b2, a3 lacks b1. R ÷ S = {a1}.

Example 2 Medium

Find the rolls of students who took every EE course.

Solution

EE courses = {C3}. Students with C3: rolls 1 and 2. πroll, cid(ENROLL) ÷ πcid(σdept='EE'(COURSE)) = {1, 2}.

Example 3 GATE

R has 12 tuples and S has 4 tuples. What is the maximum possible size of R ÷ S? What is it if S is empty and πX(R) has 5 tuples?

Solution

Each answer value needs 4 tuples of R: at most ⌊12/4⌋ = 3. If S is empty, every candidate qualifies: 5.

8 · Connect the Dots

Lessons 3.1.1–3.1.4 covered "some" (∃) queries; this lesson covered "every" (∀) with division. Next: rewriting expressions into equivalent faster forms, min/max questions on result sizes, and the extended operators for counting and summing.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · MCQ · 2 mark(s) — Evaluate

πroll, cid(ENROLL) ÷ πcid(σcredits = 4(COURSE)) returns:

1. (A) {1, 3}
2. (B) {1, 2}
3. (C) {1}
4. (D) ∅

Q2 · NAT · 2 mark(s) — Division

R(A, B) = {(1, x), (1, y), (1, z), (2, x), (2, y), (3, x), (3, z), (4, y)}, S(B) = {x, y}. How many tuples in R ÷ S?

Numerical answer: ________

Q3 · NAT · 1 mark(s) — Empty divisor

R(A, B) has 9 tuples with 4 distinct A values. How many tuples in R ÷ S if S(B) is empty?

Numerical answer: ________

Q4 · MCQ · 1 mark(s) — Formula

Which equals R(X, Y) ÷ S(Y)?

1. (A) πX(R ⋈ S)
2. (B) πX(R) − πX((πX(R) × S) − R)
3. (C) πX(R × S) − R
4. (D) πX(R) ∩ S

Q5 · NAT · 2 mark(s) — Size bound

R has 20 tuples and S has 6 (non-empty). What is the maximum possible |R ÷ S|?

Numerical answer: ________

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

division ÷for-all querymissing pairscandidatesvacuous divisordivision formula