A · Compressed recap
σ keeps rows, π keeps columns and removes duplicates, ρ renames. ∪ ∩ − need union compatibility; − is not commutative; R ∩ S = R − (R − S). × multiplies sizes; theta join = σ(×); natural join matches all same-named attributes (watch for dept!) and keeps one copy; no common attributes → ×. Outer joins keep dangling tuples with NULL padding (left/right/full). Division R ÷ S answers "for all": πX(R) − πX((πX(R) × S) − R); R ÷ ∅ = πX(R).
Rewrites: push σ down, π distributes over ∪ only. Bounds: ∪ max..sum, ∩ 0..min, − max(0,r−s)..r, ⋈ 0..r·s, ⟕ ≥ r. Max via self-product; extended RA adds γ.
B · Merged rule card
3.1.1 Selection, projection, rename; composing operations
- σc(R): rows satisfying c; same degree; 0 ≤ |σ| ≤ |R|; σ commutes and cascades into ∧.
- πL(R): listed columns, duplicates removed; degree = |L|; |π| ≤ |R|, equal if L contains a key.
- πL1(πL2(R)) = πL1(R) if L1 ⊆ L2.
- ρ renames a relation and/or its attributes.
- Nest operators or use ← assignment; evaluate inside out.
3.1.2 Union, intersection, difference; union compatibility
- ∪, ∩, − need union compatibility: same degree, matching domains.
- R ∩ S = R − (R − S); − is not commutative.
- Bounds: ∪ max(r,s)..r+s; ∩ 0..min(r,s); − max(0,r−s)..r.
- English "not" → everyone − those who did.
3.1.3 Cartesian product, theta join, equijoin, natural join
- R × S: degree adds, cardinality multiplies.
- Theta join = σθ(R × S); equijoin uses =, keeps both columns.
- Natural join: equality on all same-named attributes, one copy kept; degree = sum − common.
- No common attributes → ×; all common → ∩.
- |R ⋈ S| ∈ [0, |R|·|S|]; = |R| if join attributes are S's key and a non-NULL FK in R.
3.1.4 Outer joins: left, right, full
- R ⟕ S: join + unmatched R (NULL right). R ⟖ S: join + unmatched S (NULL left). R ⟗ S: both.
- Sizes: ⟕ = matches + unmatched R ≥ |R|; ⟗ = matches + unmatched R + unmatched S.
- R ⟖ S ≡ S ⟕ R (up to column order).
- "X with no Y": σY-col is null(X ⟕ Y) or π(X) − π(Y).
3.1.5 Division and for-all queries
- R(X, Y) ÷ S(Y) = X-values paired in R with every Y-tuple of S.
- = πX(R) − πX((πX(R) × S) − R).
- R ÷ ∅ = πX(R); candidates come only from R.
- |R ÷ S| ≤ ⌊|R|/|S|⌋ for non-empty S.
- Project dividend to (answer, match) and divisor to (match) first.
3.1.6 Equivalent expressions; min/max tuples in a result; extended RA (aggregation)
- σ cascades, commutes, distributes over ∪ ∩ −; push σ below ⋈ if it uses one side.
- π distributes over ∪ only.
- Bounds: ∪ max..sum; ∩ 0..min; − max(0,r−s)..r; × = r·s; ⋈ 0..r·s; ⟕ ≥ r; ÷ ≤ ⌊r/s⌋.
- Max A = πA(R) − πR1.A(σR1.A < R2.A(ρR1(R) × ρR2(R))); use > for min.
- Extended: γ aggregation (COUNT SUM AVG MIN MAX with grouping), generalised projection, outer joins.
- Basic set: σ, π, ∪, −, ×, ρ.
C · Interleaved GATE-style questions
Q1 · NAT · 1 mark(s) — Projection
How many tuples are in πgrade(ENROLL)?
Numerical answer: ________
Q2 · MCQ · 1 mark(s) — Selection
σdept='CS' ∧ cgpa < 9(STUDENT) returns:
- (A) {Chirag}
- (B) {Asha, Chirag}
- (C) ∅
- (D) {Asha}
Q3 · NAT · 2 mark(s) — Natural join trap
How many tuples are in πroll(ENROLL ⋈ COURSE ⋈ STUDENT), all natural joins?
Numerical answer: ________
Q4 · MCQ · 1 mark(s) — Set ops
πroll(STUDENT) − πroll(σgrade='B'(ENROLL)) is:
- (A) {1, 3}
- (B) {4}
- (C) {1, 2, 3}
- (D) {2, 4}
Q5 · NAT · 2 mark(s) — Outer join
R(A, B) = {(1, p), (2, q), (3, r), (4, r)}, S(B, C) = {(r, 7), (s, 8)}. How many tuples are in R ⟗ S?
Numerical answer: ________
Q6 · MCQ · 2 mark(s) — Division
Which students took every course of 3 credits?
- (A) {4}
- (B) {1}
- (C) {1, 3}
- (D) ∅
Q7 · NAT · 2 mark(s) — Bounds
| R | = 9, | S | = 4 (union compatible). What is | R ∩ S | + | R − S | ? |
|---|
Numerical answer: ________
Q8 · MSQ · 2 mark(s) — Rewrites
Which are valid rewrites when c uses only attributes of R?
- (A) σc(R × S) = σc(R) × S
- (B) πA(R − S) = πA(R) − πA(S)
- (C) σc(R ⋈ S) = σc(R) ⋈ S
- (D) R ⋈ S = S ⋈ R (natural join, up to column order)
Q9 · NAT · 1 mark(s) — Product
What is the degree of STUDENT × ENROLL?
Numerical answer: ________
D · Answer Vault
Reveal answers when you’re ready
Q1 Answer: 3 · 1 mark(s)
{A, B, C}.
Re-read: Lesson 3.1.1 — Selection, projection, rename; composing operations
Q2 Answer: (A) · 1 mark(s)
Chirag (CS, 8.4).
- (B) is wrong: Asha fails cgpa < 9.
- (C) is wrong: Chirag qualifies.
- (D) is wrong: Asha has 9.1.
Re-read: Lesson 3.1.1 — Selection, projection, rename; composing operations
Q3 Answer: 4 · 2 mark(s)
Joins on cid, then roll and dept: survivors (1,C1),(1,C2),(2,C3),(3,C1),(3,C2),(4,C4) → rolls {1,2,3,4}.
Re-read: Lesson 3.1.3 — Cartesian product, theta join, equijoin, natural join
Q4 Answer: (B) · 1 mark(s)
Grade B rows: (1, C2), (2, C3), (3, C1) → {1, 2, 3}. {1, 2, 3, 4} − {1, 2, 3} = {4}.
- (A) is wrong: Those got B grades.
- (C) is wrong: That is the subtracted set.
- (D) is wrong: Roll 2 got a B in C3.
Re-read: Lesson 3.1.2 — Union, intersection, difference; union compatibility
Q5 Answer: 5 · 2 mark(s)
Matches: (3, r, 7), (4, r, 7). Unmatched R: 1, 2. Unmatched S: s. 2 + 2 + 1 = 5.
Re-read: Lesson 3.1.4 — Outer joins: left, right, full
Q6 Answer: (D) · 2 mark(s)
3-credit courses: C2 (CS) and C4 (ME). Nobody took both.
- (A) is wrong: Roll 4 lacks C2.
- (B) is wrong: Roll 1 lacks C4.
- (C) is wrong: Roll 3 lacks C4.
Re-read: Lesson 3.1.5 — Division and for-all queries
Q7 Answer: 9 · 2 mark(s)
R ∩ S and R − S split R exactly: always 9.
Re-read: Lesson 3.1.6 — Equivalent expressions; min/max tuples in a result; extended RA (aggregation)
Q8 Answer: (A) (C) (D) · 2 mark(s)
Projection does not distribute over difference.
- (B) is wrong: Not valid in general.
Re-read: Lesson 3.1.6 — Equivalent expressions; min/max tuples in a result; extended RA (aggregation)
Q9 Answer: 7 · 1 mark(s)
4 + 3.
Re-read: Lesson 3.1.3 — Cartesian product, theta join, equijoin, natural join