3.1.1 · Selection, projection, rename; composing operations

0 · Recall Warm-up

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

What is the primary key of a table that maps an M:N relationship? from Lesson 2.4.2
In a relation, can two tuples be identical? from Lesson 2.1.1
What does ∧ mean in a condition, and when is p ∧ q true? from Lesson 0.2.3

1 · The Hook

The tables are built. Now the college asks questions: "Which CS students have CGPA above 8?" "Which departments have students at all?" A query language answers them. Relational algebra (RA) is the mathematical one: a few operators, each taking relations in and giving a relation out. SQL is built on it, and GATE asks you to evaluate RA expressions by hand.

From now on, this is the running database:

roll	name	dept	cgpa
1	Asha	CS	9.1
2	Bhavin	EE	7.8
3	Chirag	CS	8.4
4	Diya	ME	6.9

STUDENT

cid	title	dept	credits
C1	DBMS	CS	4
C2	Networks	CS	3
C3	Circuits	EE	4
C4	Thermo	ME	3

COURSE

roll	cid	grade
1	C1	A
1	C2	B
1	C3	A
2	C3	B
3	C1	B
3	C2	A
4	C4	C

ENROLL

2 · Predict First

"List the departments of all students": take the dept column of STUDENT. How many rows does the answer have: 4 or 3?

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

3 · Core Concept

Predict First — the answer

3: {CS, EE, ME}. Relational algebra works on sets, so the second CS is removed. (SQL would show 4 rows unless told otherwise; Lesson 3.3.3.)

Selection σ: pick rows

σcondition(R) returns the tuples of R that satisfy the condition. The schema stays the same.

σdept = 'CS'(STUDENT) = {(1, Asha, CS, 9.1), (3, Chirag, CS, 8.4)}.

Conditions use comparisons (=, ≠, <, ≤, >, ≥) between attributes and constants, joined by ∧, ∨, ¬.
Degree of the result = degree of R. Cardinality: 0 ≤ |σ(R)| ≤ |R|.
Commutative: σc1(σc2(R)) = σc2(σc1(R)) = σc1 ∧ c2(R).

Projection π: pick columns

πattribute list(R) keeps only the listed attributes and removes duplicate tuples.

πdept(STUDENT) = {CS, EE, ME}: 3 tuples, not 4.

Degree of the result = number of listed attributes. Cardinality: 1 ≤ |π(R)| ≤ |R| for non-empty R. If the list contains a key of R, no duplicates arise and |π(R)| = |R|.
Cascade: πL1(πL2(R)) = πL1(R) when L1 ⊆ L2. (πname(πroll, name(STUDENT)) is fine; πroll, name(πname(STUDENT)) is an error: roll is gone.)

Rename ρ

ρS(R) gives R the new name S; ρS(B1, B2, …)(R) also renames its attributes. Needed when a relation is used twice in one query (Lesson 3.1.6) or to make attribute names match.

Composing operators

Operators nest: the output of one is the input of the next. Evaluate from the inside out.

πname(σdept = 'CS' ∧ cgpa > 8.5(STUDENT)) = {Asha}.

The same query can be written as a sequence using assignment (←): T ← σdept = 'CS'(STUDENT); Result ← πname(σcgpa > 8.5(T)).

4 · Visual

STUDENT                      σ dept='CS'                π name
roll name   dept cgpa        (keeps rows)               (keeps columns, removes duplicates)
 1   Asha    CS  9.1   -->    1  Asha   CS 9.1   -->     Asha
 2   Bhavin  EE  7.8          3  Chirag CS 8.4           Chirag
 3   Chirag  CS  8.4
 4   Diya    ME  6.9         degree 4, 2 tuples         degree 1, 2 tuples

5 · Worked Examples

Example 1 Easy

Evaluate σcredits = 4(COURSE) and πtitle(σcredits = 4(COURSE)).

Solution

σ: {(C1, DBMS, CS, 4), (C3, Circuits, EE, 4)}. πtitle of that: {DBMS, Circuits}.

Example 2 Medium

How many tuples are in πcid(σgrade = 'A'(ENROLL))?

Solution

grade A rows: (1, C1), (1, C3), (3, C2). Projection on cid: {C1, C3, C2} = 3 tuples.

Example 3 GATE

How many tuples are in πdept(σcgpa > 7(STUDENT))? And in πroll(ENROLL)?

Solution

cgpa > 7: Asha (CS), Bhavin (EE), Chirag (CS) → πdept = {CS, EE}: 2. πroll(ENROLL) = {1, 2, 3, 4}: 4 (seven rows, duplicates removed).

6 · GATE Traps

π removes duplicates in relational algebra; count distinct values, not rows.
σ never changes the columns; π never filters by condition.
πL1(πL2(R)) is valid only if L1 ⊆ L2.
If the projected list includes a key, the cardinality does not drop.
Selection conditions test one tuple at a time; "the student with the highest CGPA" cannot be written as a single σ (Lesson 3.1.6).

7 · Memory Hook

"σ is a Sieve for rows, π is a Pair of scissors for columns (and it throws away repeats)."

8 · Connect the Dots

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · NAT · 1 mark(s) — Projection

How many tuples are in πdept(COURSE)?

Numerical answer: ________

Q2 · NAT · 1 mark(s) — Selection

How many tuples are in σroll = 1(ENROLL)?

Numerical answer: ________

Q3 · MCQ · 1 mark(s) — Degree

The degree of πroll, grade(σcid = 'C1'(ENROLL)) is:

(A) 7
(B) 3
(C) 2
(D) 1

Q4 · MCQ · 2 mark(s) — Composition

πname(σdept = 'CS' ∨ cgpa < 7(STUDENT)) returns:

(A) {Asha, Chirag}
(B) {Asha, Chirag, Diya}
(C) {Asha, Bhavin, Chirag, Diya}
(D) {Diya}

Q5 · MSQ · 2 mark(s) — Laws

Which equalities always hold for any relation R with attributes A, B, C?

(A) σc1(σc2(R)) = σc1 ∧ c2(R)
(B) πA(πA, B(R)) = πA(R)
(C) πA, B(πA(R)) = πA, B(R)
(D) |πA(R)| ≤ |R|

10 · Rule Card

σ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.

11 · Concept Ledger

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

query languagerelational algebra (RA)selection σprojection πrename ρassignment ←set semantics (no duplicates in RA results)

12 · Answer Vault

Reveal answers when you’re ready

Recall Warm-up

The primary keys of both entity types together.
No: a relation is a set of tuples.
AND; true only when both p and q are true.