3.1.6 · Equivalent expressions; min/max tuples in a result; extended RA (aggregation)

0 · Recall Warm-up

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

What is R ÷ S when S is empty? from Lesson 3.1.5
What is the degree of a natural join of R and S? from Lesson 3.1.3
Bounds of |R ∩ S| for |R| = r, |S| = s? from Lesson 3.1.2

1 · The Hook

Three last RA skills cover the remaining GATE questions: (1) deciding whether two expressions are equivalent (and which runs faster); (2) finding the minimum and maximum number of tuples an expression can return; (3) answering "highest CGPA" and "number of students per department", which basic RA can only do with a trick, and extended RA does directly.

2 · Predict First

Basic RA has no "max". How can you find the highest CGPA in STUDENT using only σ, π, ×, ρ and −?

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

3 · Core Concept

Predict First — the answer

Find every CGPA that is smaller than some other CGPA (pair STUDENT with a renamed copy and select S1.cgpa < S2.cgpa). Subtract those from all CGPAs. What remains is the maximum: {9.1}.

Equivalent expressions (rewrite rules)

σc1 ∧ c2(R) = σc1(σc2(R)); σ commutes.
Push selections down: σc(R ⋈ S) = σc(R) ⋈ S when c uses only R's attributes.
σ distributes over ∪, ∩ and −: σc(R − S) = σc(R) − σc(S).
π distributes over ∪: πL(R ∪ S) = πL(R) ∪ πL(S).
π does not distribute over − or ∩. R = {(1, x)}, S = {(1, y)}: πA(R − S) = {1} but πA(R) − πA(S) = ∅.
⋈ is commutative and associative (natural join); × too. − is neither.

Pushing σ (and π) down makes intermediate results smaller, which is how query optimisers speed queries up.

Min and max tuples

For |R| = r, |S| = s:

Expression	Min	Max
σc(R)	0	r
πL(R) (R non-empty)	1	r
R ∪ S	max(r, s)	r + s
R ∩ S	0	min(r, s)
R − S	max(0, r − s)	r
R × S	r·s	r·s
R ⋈ S	0	r·s
R ⟕ S	r	r·s (and at least r)
R ÷ S (S non-empty)	0	⌊r/s⌋

Keys tighten these: if the join attribute is a key of S and a non-NULL FK in R, |R ⋈ S| = r exactly.

Max without aggregation

Max of A in R: πA(R) − πR1.A(σR1.A < R2.A(ρR1(R) × ρR2(R))).

The second part holds every value that has a bigger value somewhere: everything except the maximum. Use > for the minimum.

Extended RA

Aggregation γ: grouping attributesγfunctions(R). Functions: COUNT, SUM, AVG, MIN, MAX.

deptγCOUNT(roll)(STUDENT) = {(CS, 2), (EE, 1), (ME, 1)}. With no grouping attributes, γMAX(cgpa)(STUDENT) = {(9.1)}.
Generalised projection: πroll, credits × 10(…) allows arithmetic in the list.
Outer joins (Lesson 3.1.4) are also part of extended RA.

Which operators are basic?

The basic set {σ, π, ∪, −, ×, ρ} can express everything else in basic RA: ∩ = R − (R − S); ⋈ = σ(×) then π; ÷ by the formula of Lesson 3.1.5.

4 · Visual

Max cgpa:  S1 x S2 (16 pairs)  -> keep S1.cgpa < S2.cgpa  -> π S1.cgpa
           values that lose to someone:  7.8, 8.4, 6.9
           all values:                   9.1, 7.8, 8.4, 6.9
           all - losers =                9.1          (the maximum)

5 · Worked Examples

Example 1 Easy

Are πname(σdept='CS'(STUDENT)) and σdept='CS'(πname(STUDENT)) equivalent?

Solution

No. The second is not even valid: after πname, the attribute dept no longer exists, so the selection cannot test it.

Example 2 Medium

R(A, B) has 5 tuples and S(B, C) has 4. Give the min and max of |R ⋈ S|. What if B is the key of S and a non-NULL foreign key in R?

Solution

In general 0 to 20. With B a key of S and a non-NULL FK in R, each R tuple matches exactly one S tuple: exactly 5.

Example 3 GATE

Compute cidγCOUNT(roll)(ENROLL) and the RA "max" expression applied to COURSE.credits.

Solution

γ: {(C1, 2), (C2, 2), (C3, 2), (C4, 1)}. Max credits: values {4, 3}; values smaller than another: {3}; result {4}.

6 · GATE Traps

π does not distribute over − (or ∩).
Pushing σ below a join is legal only if the condition uses one side's attributes.
"Max" in basic RA needs a self-product with renaming; forgetting ρ makes the condition ambiguous.
|πL(R)| ≥ 1 needs R non-empty.
R ⟕ S has at least |R| tuples.

7 · Memory Hook

"Push the sieve down, never push the scissors through a minus." And for max: "The champion is whoever never loses."

8 · Connect the Dots

Chapter 3.1 is complete: all of relational algebra. Next: the Chapter 3.1 Lock-in, then the same questions in a second, logic-based language, tuple relational calculus, which says what to find instead of how.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · MCQ · 1 mark(s) — Equivalence

Which equality does not hold in general?

(A) πL(R − S) = πL(R) − πL(S)
(B) πL(R ∪ S) = πL(R) ∪ πL(S)
(C) σc(R ∪ S) = σc(R) ∪ σc(S)
(D) σc(R − S) = σc(R) − σc(S)

Q2 · NAT · 2 mark(s) — Max tuples

R(A, B) has 6 tuples and S(B, C) has 5. What is the maximum number of tuples in R ⋈ S?

Numerical answer: ________

Q3 · NAT · 2 mark(s) — Min tuples

R has 7 tuples and S has 3, union compatible. What is the minimum number of tuples in R ∪ S?

Numerical answer: ________

Q4 · NAT · 1 mark(s) — Aggregation

How many tuples are in deptγCOUNT(cid)(COURSE)?

Numerical answer: ________

Q5 · MCQ · 2 mark(s) — Max trick

πA(R) − πR1.A(σR1.A > R2.A(ρR1(R) × ρR2(R))) returns:

(A) all A values
(B) the maximum A
(C) the minimum A
(D) the empty set

10 · Rule Card

σ 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: σ, π, ∪, −, ×, ρ.

11 · Concept Ledger

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

equivalent expressionspushing selections downquery optimisation (idea)min/max result sizesmax/min via self-productaggregation γgeneralised projectionbasic RA operator set

12 · Answer Vault

Reveal answers when you’re ready

Recall Warm-up

πX(R): every candidate qualifies.
deg(R) + deg(S) − number of common attributes.
0 to min(r, s).