Lesson 11: Relational Algebra I: Unary and Set Operations¶
Unary operations and set operations
About this lesson
Course: Database Management Systems
Unit 3: Relational Data Model · 7 Lecture Hours
Lesson duration: 2 lectures
Reading: Elmasri & Navathe, Ch. 8.1, 8.2
Learning Outcomes
- Explain what relational algebra is and why the closure property matters.
- Apply SELECT (σ), PROJECT (π) and RENAME (ρ) correctly.
- Apply the set operations ∪, ∩, −, × and state the union compatibility requirement.
- Write nested and sequential expressions, and build query trees.
- Predict the exact cardinality and degree of every intermediate result.
11.1 What Relational Algebra Is¶
Relational algebra
A formal language for the relational model, consisting of a set of operations that take one or two relations as input and produce a new relation as output.
Three properties make it important:
1. It is closed. Every operation returns a relation, so the output of one operation can be the input of the next. This is the closure property, and it is what allows arbitrarily complex expressions to be built.
2. It is procedural. An expression specifies not only what is wanted but an order of operations — unlike SQL, which is declarative. This is exactly why it matters practically: the DBMS query optimiser translates SQL into relational algebra, then rewrites the algebra into a cheaper but equivalent expression. Understanding algebra is understanding what the optimiser does.
3. It defines the yardstick of expressive power. A query language is called relationally complete if it can express every relational-algebra query. SQL is relationally complete (and more).
Why study it if we have SQL?
Because it is the semantics of SQL. Every SELECT statement is compiled into an algebra expression. Query optimisation, the theory of query equivalence, and the definition of relational completeness are all stated in algebra. It is also far more precise than English for stating exactly what a query means.
The operations¶
| Group | Operation | Symbol | Arity |
|---|---|---|---|
| Unary | SELECT | σ (sigma) | 1 |
| PROJECT | π (pi) | 1 | |
| RENAME | ρ (rho) | 1 | |
| Set | UNION | ∪ | 2 |
| INTERSECTION | ∩ | 2 | |
| SET DIFFERENCE (MINUS) | − | 2 | |
| CARTESIAN PRODUCT | × | 2 | |
| Join (Lesson 4) | JOIN, DIVISION | ⋈, ÷ | 2 |
The complete (minimal) set
{ σ, π, ∪, −, × } is a complete set: every other relational-algebra operation can be expressed in terms of these five. For instance R ∩ S = R − (R − S) and R ⋈ S = σ<sub>condition</sub>(R × S).
The other operations exist for convenience and efficiency, not for expressive power.
11.2 The Running Example¶
Use these three relations throughout.
STUDENT
| Rollno | Name | Dateofbirth |
|---|---|---|
| X2019 | Ankit Sharma | 2001-03-14 |
| X2020 | Riya Verma | 2002-05-11 |
| Z1188 | Sana Iqbal | 2001-11-02 |
| Z2049 | Arjun Nair | 2003-01-25 |
| X3001 | Aditi Rao | 2001-07-09 |
COURSE
| SID | Cname | TotalSeats | Duration | Coursetype | TeacherInCharge |
|---|---|---|---|---|---|
| CS01 | Computer Science | 60 | 3 | Fulltime | R. K. Gupta |
| CH01 | Chemistry | 45 | 3 | Fulltime | S. Menon |
| MA02 | Mathematics | 50 | 3 | Parttime | A. Gupta |
| EN03 | English | 40 | 3 | Parttime | P. Das |
| PH01 | Physics | 40 | 3 | Fulltime | V. Rao |
ADMISSION
| Rollno | SID | Dateofadmission |
|---|---|---|
| X2019 | CS01 | 2019-07-15 |
| X2019 | MA02 | 2019-08-01 |
| X2020 | CS01 | 2019-07-16 |
| Z1188 | CH01 | 2019-07-18 |
| Z1188 | EN03 | 2019-08-05 |
| X3001 | MA02 | 2019-07-20 |
Note that Z2049 Arjun Nair has no admission — this makes several later examples interesting. PH01 Physics has no students.
11.3 SELECT (σ) — choosing rows¶
SELECT
σ<sub><condition></sub>(R)
Returns the set of tuples of R that satisfy the condition. It is a horizontal partition — it chooses rows.
- The result has the same degree as
R(same attributes). 0 ≤ |σ<sub>c</sub>(R)| ≤ |R|.- The condition is a Boolean expression over
<attribute> <comparison> <constant-or-attribute>, combined with AND (∧), OR (∨), NOT (¬). - Comparison operators:
=, ≠, <, ≤, >, ≥. - SELECT is commutative:
σ<sub>c1</sub>(σ<sub>c2</sub>(R)) = σ<sub>c2</sub>(σ<sub>c1</sub>(R)) = σ<sub>c1 ∧ c2</sub>(R).
Example 1. All full-time courses.
σ<sub>Coursetype = 'Fulltime'</sub>(COURSE)
| SID | Cname | TotalSeats | Duration | Coursetype | TeacherInCharge |
|---|---|---|---|---|---|
| CS01 | Computer Science | 60 | 3 | Fulltime | R. K. Gupta |
| CH01 | Chemistry | 45 | 3 | Fulltime | S. Menon |
| PH01 | Physics | 40 | 3 | Fulltime | V. Rao |
Degree 6, cardinality 3.
Example 2. Full-time courses with more than 40 seats.
σ<sub>Coursetype = 'Fulltime' ∧ TotalSeats > 40</sub>(COURSE) → CS01, CH01. Cardinality 2.
Example 3. Courses that are part-time or have fewer than 45 seats.
σ<sub>Coursetype = 'Parttime' ∨ TotalSeats < 45</sub>(COURSE) → MA02, EN03, PH01. Cardinality 3.
The commonest error
Writing σ<sub>Cname = 'Computer Science' ∧ Cname = 'Chemistry'</sub>(COURSE) to get both courses. This returns zero tuples: the condition is evaluated one tuple at a time, and no single course is called both things. The correct operator is ∨.
Say it aloud as "for each row, is it true that..." and the error becomes obvious.
11.4 PROJECT (π) — choosing columns¶
PROJECT
π<sub><attribute list></sub>(R)
Returns a relation containing only the listed attributes, in the listed order, with duplicate tuples removed. It is a vertical partition — it chooses columns.
- Degree = number of attributes in the list.
|π<sub>L</sub>(R)| ≤ |R|, with equality if and only ifLcontains a superkey ofR.- PROJECT is not commutative:
π<sub>L1</sub>(π<sub>L2</sub>(R))is valid only ifL1 ⊆ L2, and then equalsπ<sub>L1</sub>(R).
Example 4. Names and types of all courses.
π<sub>Cname, Coursetype</sub>(COURSE)
| Cname | Coursetype |
|---|---|
| Computer Science | Fulltime |
| Chemistry | Fulltime |
| Mathematics | Parttime |
| English | Parttime |
| Physics | Fulltime |
Degree 2, cardinality 5.
Example 5 — duplicate elimination. π<sub>Coursetype</sub>(COURSE)
| Coursetype |
|---|
| Fulltime |
| Parttime |
Cardinality 2, not 5. PROJECT returns a set, so Fulltime (which occurred three times) appears once.
PROJECT vs SQL SELECT
Relational algebra PROJECT always removes duplicates, because a relation is a set.
SQL's SELECT Coursetype FROM COURSE returns five rows, because SQL tables are multisets. To match the algebra you must write SELECT DISTINCT Coursetype FROM COURSE.
π corresponds to SELECT DISTINCT, not to SELECT. This is a very common examination point.
Example 6 — no duplicates removed. π<sub>SID, Cname</sub>(COURSE) has cardinality 5, because the list contains SID, which is a key. Whenever the projection list contains a superkey, no duplicates can arise.
11.5 RENAME (ρ) — changing names¶
RENAME
Three forms:
ρ<sub>S</sub>(R) — rename the relation to S, keeping attribute names.
ρ<sub>(B1, B2, ..., Bn)</sub>(R) — rename the attributes to B1 ... Bn, keeping the relation name.
ρ<sub>S(B1, ..., Bn)</sub>(R) — rename both.
RENAME exists for two essential purposes:
- Self-joins and self-products.
EMPLOYEE × EMPLOYEEis ambiguous — whichSsnis which? Renaming one copy disambiguates. - Resolving name clashes before a set operation that requires union compatibility.
Example 7. ρ<sub>SUPERVISOR(SupSsn, SupName, SupSalary)</sub>(EMPLOYEE) produces a copy of EMPLOYEE under a new name with new attribute names, usable alongside the original.
Sequential notation — the practical alternative¶
Rather than nesting deeply, name each intermediate result:
FULLTIME ← σ Coursetype='Fulltime' (COURSE)
BIG_FULLTIME ← σ TotalSeats>40 (FULLTIME)
RESULT ← π Cname (BIG_FULLTIME)
This is equivalent to π<sub>Cname</sub>(σ<sub>Coursetype='Fulltime' ∧ TotalSeats>40</sub>(COURSE)) and is far easier to read, check and mark. Use it in examinations for any query needing more than two operations.
11.6 Set Operations¶
Union compatibility¶
Union compatibility (type compatibility)
Two relations R(A1,...,An) and S(B1,...,Bm) are union compatible if:
- They have the same degree:
n = m. - Corresponding attributes have the same domain:
dom(Ai) = dom(Bi)for alli.
Attribute names need not match; by convention the result takes the names from the first relation.
∪, ∩ and − all require union compatibility. × does not.
For the examples, let:
CS_STUDENTS ← π<sub>Rollno</sub>(σ<sub>SID='CS01'</sub>(ADMISSION))= {X2019, X2020}MA_STUDENTS ← π<sub>Rollno</sub>(σ<sub>SID='MA02'</sub>(ADMISSION))= {X2019, X3001}
UNION (∪)¶
UNION
R ∪ S = all tuples that are in R, or in S, or in both. Duplicates are removed.
max(|R|, |S|) ≤ |R ∪ S| ≤ |R| + |S|. Commutative and associative.
Example 8. Students in Computer Science or Mathematics.
CS_STUDENTS ∪ MA_STUDENTS = {X2019, X2020, X3001}. Cardinality 3, not 4 — X2019 appears in both and is counted once.
INTERSECTION (∩)¶
INTERSECTION
R ∩ S = tuples in both. 0 ≤ |R ∩ S| ≤ min(|R|, |S|). Commutative and associative.
Not primitive: R ∩ S = R − (R − S).
Example 9. Students in Computer Science and Mathematics.
CS_STUDENTS ∩ MA_STUDENTS = {X2019}. Cardinality 1.
'and' in English is usually ∩, not ∧
"Students taking CS01 and MA02" cannot be σ<sub>SID='CS01' ∧ SID='MA02'</sub>(ADMISSION), which returns nothing (Section 3.3). The two facts live in different tuples, so they must be combined by intersecting two sets of roll numbers.
Rule: when "and" applies to two facts about the same entity recorded in different rows, use ∩ (or a join). Use ∧ only when both conditions apply to the same row.
SET DIFFERENCE (−)¶
SET DIFFERENCE
R − S = tuples in R that are not in S. Not commutative: R − S ≠ S − R.
0 ≤ |R − S| ≤ |R|.
Example 10. Students in Computer Science but not Mathematics.
CS_STUDENTS − MA_STUDENTS = {X2020}.
MA_STUDENTS − CS_STUDENTS = {X3001} — a different answer, confirming non-commutativity.
Example 11 — the important pattern. Students admitted to no course.
ALL_STUDENTS ← π Rollno (STUDENT) = {X2019,X2020,Z1188,Z2049,X3001}
ADMITTED ← π Rollno (ADMISSION) = {X2019,X2020,Z1188,X3001}
RESULT ← ALL_STUDENTS − ADMITTED = {Z2049}
Then π<sub>Name</sub>(STUDENT ⋈ RESULT) gives Arjun Nair.
The universal 'NOT / NONE' pattern
Any query of the form "find X that has no Y" or "...that is not related to..." is answered by set difference:
(all X) − (X that do have Y)
Compute the positive set first, then subtract it from the universe. This pattern appears in almost every examination.
CARTESIAN PRODUCT (×)¶
CARTESIAN PRODUCT (CROSS PRODUCT / CROSS JOIN)
R(A1,...,An) × S(B1,...,Bm) produces a relation Q(A1,...,An,B1,...,Bm) containing every combination of a tuple of R with a tuple of S.
- Degree =
n + m(degrees add). - Cardinality =
|R| × |S|(cardinalities multiply). - Union compatibility is not required.
- Commutative and associative up to attribute order.
Example 12. STUDENT × COURSE has degree 3 + 6 = 9 and cardinality 5 × 5 = 25.
Most of those 25 rows are meaningless — they pair a student with a course they never took.
× alone is almost never what you want
The Cartesian product is useful only when immediately followed by a SELECT that keeps the meaningful combinations:
σ<sub>STUDENT.Rollno = ADMISSION.Rollno</sub>(STUDENT × ADMISSION)
This combination — product then select — is so common that it is given its own name: the JOIN (Lesson 4). An accidental × without a matching condition is the classic cause of a query that returns millions of rows.
Example 13 — product followed by selection. Names of students admitted to CS01.
T1 ← σ SID='CS01' (ADMISSION) 2 tuples
T2 ← STUDENT × T1 5 × 2 = 10 tuples, degree 6
T3 ← σ STUDENT.Rollno = T1.Rollno (T2) 2 tuples
RESULT ← π Name (T3)
| Name |
|---|
| Ankit Sharma |
| Riya Verma |
11.7 Query Trees¶
Every algebra expression can be drawn as a tree: leaves are base relations, internal nodes are operations, and evaluation proceeds bottom-up. This is exactly the internal representation the optimiser manipulates.
Query: names of students admitted to 'CS01'
π Name
|
σ STUDENT.Rollno = ADMISSION.Rollno
|
×
/ \
STUDENT σ SID='CS01'
|
ADMISSION
Read bottom-up: filter ADMISSION, cross with STUDENT,
keep matching pairs, project the name.
A first optimisation rule
Compare two equivalent expressions:
(a) π<sub>Name</sub>(σ<sub>Rollno=Rollno ∧ SID='CS01'</sub>(STUDENT × ADMISSION)) — the product makes 5 × 6 = 30 tuples, then filters.
(b) π<sub>Name</sub>(σ<sub>Rollno=Rollno</sub>(STUDENT × σ<sub>SID='CS01'</sub>(ADMISSION))) — filter first, so the product makes only 5 × 2 = 10 tuples.
Both give the same answer; (b) does a third of the work. The rule is push selections down the tree, as close to the leaves as possible. This is the single most important heuristic in query optimisation, and it is why the optimiser works in algebra.
11.8 Solved Questions¶
Solved Question 1
Q. What is relational algebra? State the closure property and the complete set of operations. Why is relational algebra important given that we use SQL?
A. Relational algebra is a formal, procedural query language for the relational model, consisting of operations that take one or two relations as input and produce a relation as output.
The closure property states that every operation returns a relation. Because the output is the same kind of object as the input, operations can be composed without limit, which is what makes complex expressions and query trees possible.
The complete (minimal) set is {σ, π, ∪, −, ×}. Every other operation is definable from these — for example R ∩ S = R − (R − S) and R ⋈<sub>c</sub> S = σ<sub>c</sub>(R × S). The additional operations exist for convenience and efficiency, not for expressive power.
Importance despite SQL: relational algebra is the semantics of SQL. A DBMS parses a SQL statement, translates it into an algebra expression, and the query optimiser then rewrites that expression into an equivalent but cheaper one — pushing selections down, reordering joins — before generating an execution plan. Algebra also gives the precise definition of query equivalence, and defines relational completeness, the standard by which a query language's expressive power is measured.
Solved Question 2
Q. Distinguish SELECT from PROJECT. State the exact cardinality relationship of each to its input, and explain when |π<sub>L</sub>(R)| = |R|.
A.
| SELECT (σ) | PROJECT (π) | |
|---|---|---|
| Chooses | Rows (horizontal) | Columns (vertical) |
| Notation | σ<sub>condition</sub>(R) |
π<sub>attribute list</sub>(R) |
| Degree of result | Same as R |
Number of attributes listed |
| Cardinality | 0 ≤ result ≤ |R| |
1 ≤ result ≤ |R| (for non-empty R) |
| Removes duplicates | Not applicable — cannot create them | Yes, always |
| Commutative with itself | Yes | No |
| SQL equivalent | WHERE clause |
SELECT DISTINCT column list |
When |π<sub>L</sub>(R)| = |R|: exactly when the projection list L contains a superkey of R. A superkey guarantees that no two tuples agree on all of L, so no duplicates can arise and none are removed.
Illustration. π<sub>SID, Cname</sub>(COURSE) has cardinality 5 = |COURSE|, because SID is a key. But π<sub>Coursetype</sub>(COURSE) has cardinality 2, because Coursetype is not a superkey and three Fulltime tuples collapse into one.
Solved Question 3
Q. Write relational algebra for each, using the running example, and give the result.
a. Roll numbers and names of students born in 2001.
b. Names of part-time courses with more than 40 seats.
c. Distinct course types offered.
d. Names of students admitted to CS01.
e. Roll numbers of students admitted to CS01 but not MA02.
f. Roll numbers of students admitted to no course.
A.
a. π<sub>Rollno, Name</sub>(σ<sub>Dateofbirth ≥ '2001-01-01' ∧ Dateofbirth ≤ '2001-12-31'</sub>(STUDENT))
| Rollno | Name |
|---|---|
| X2019 | Ankit Sharma |
| Z1188 | Sana Iqbal |
| X3001 | Aditi Rao |
b. π<sub>Cname</sub>(σ<sub>Coursetype='Parttime' ∧ TotalSeats>40</sub>(COURSE)) → {Mathematics}. (EN03 English has exactly 40, so it is excluded by the strict >.)
c. π<sub>Coursetype</sub>(COURSE) → {Fulltime, Parttime}. Cardinality 2, because PROJECT removes duplicates.
d.
T1 ← σ SID='CS01' (ADMISSION)
T2 ← σ STUDENT.Rollno = T1.Rollno (STUDENT × T1)
RESULT ← π Name (T2)
e.
CS ← π Rollno (σ SID='CS01' (ADMISSION)) = {X2019, X2020}
MA ← π Rollno (σ SID='MA02' (ADMISSION)) = {X2019, X3001}
RESULT ← CS − MA = {X2020}
σ<sub>SID='CS01' ∧ SID≠'MA02'</sub> would be wrong — it returns both CS students, since the two facts live in different tuples.
f.
RESULT ← π Rollno (STUDENT) − π Rollno (ADMISSION) = {Z2049}
Solved Question 4
Q. Define union compatibility. Which operations require it? Given R(A,B) with 5 tuples and S(C,D) with 3 tuples where dom(A)=dom(C) and dom(B)=dom(D), state the degree and the possible range of cardinality of R ∪ S, R ∩ S, R − S and R × S.
A. Two relations are union compatible if they have the same degree and corresponding attributes have the same domains. Attribute names need not agree; the result conventionally takes the names of the first operand.
∪, ∩ and − require union compatibility. × does not — indeed its purpose is to combine relations of different shapes.
Here R and S are union compatible: both have degree 2 with matching domains.
| Expression | Degree | Cardinality range | Explanation |
|---|---|---|---|
R ∪ S |
2 | 5 to 8 | At least max(5,3)=5 if S ⊆ R; at most 5+3=8 if disjoint. |
R ∩ S |
2 | 0 to 3 | At least 0 if disjoint; at most min(5,3)=3 if S ⊆ R. |
R − S |
2 | 2 to 5 | At most 5 if disjoint; at least 5−3=2 if S ⊆ R. |
R × S |
4 | exactly 15 | Degrees add (2+2); cardinalities multiply (5×3). |
Note that R × S has a fixed cardinality, whereas the set operations depend on how much the relations overlap.
Solved Question 5
Q. Show that σ<sub>c1</sub>(σ<sub>c2</sub>(R)) = σ<sub>c1 ∧ c2</sub>(R) and that π is not commutative. Why do these facts matter?
A.
Cascading of SELECT. A tuple t is in σ<sub>c1</sub>(σ<sub>c2</sub>(R)) if and only if t ∈ R, t satisfies c2 (to survive the inner select), and t satisfies c1 (to survive the outer). That is precisely the condition for t to satisfy c1 ∧ c2 while being in R, so the two expressions contain exactly the same tuples. Since conjunction is commutative, the order of the two selects is also immaterial:
σ<sub>c1</sub>(σ<sub>c2</sub>(R)) = σ<sub>c2</sub>(σ<sub>c1</sub>(R)) = σ<sub>c1 ∧ c2</sub>(R)
PROJECT is not commutative. π<sub>L1</sub>(π<sub>L2</sub>(R)) is even defined only when L1 ⊆ L2, because the inner projection has already discarded every attribute not in L2. When it is defined, it equals π<sub>L1</sub>(R).
Counter-example. π<sub>Name</sub>(π<sub>Rollno</sub>(STUDENT)) is invalid — Name no longer exists after the inner projection — whereas π<sub>Rollno</sub>(π<sub>Rollno, Name</sub>(STUDENT)) is valid and equals π<sub>Rollno</sub>(STUDENT).
Why it matters. These are query-equivalence rules, and the optimiser uses them constantly. Cascading lets a single conjunctive selection be split into several, each of which can then be pushed down the query tree to a different leaf — reducing the size of intermediate results before an expensive product or join. The projection rule lets the optimiser drop unneeded columns early, reducing the width of intermediate tuples. Both directly reduce the amount of data moved and are among the first transformations any optimiser applies.
Solved Question 6
Q. Explain why σ<sub>SID='CS01' ∧ SID='MA02'</sub>(ADMISSION) is wrong for "students in both CS01 and MA02", and give the correct expression.
A. The expression returns the empty relation.
SELECT evaluates its condition one tuple at a time. Each tuple of ADMISSION has exactly one value of SID, so SID='CS01' ∧ SID='MA02' asks for a single value that is simultaneously equal to two different constants — impossible. No tuple can satisfy it.
The error is a category mistake: the English "and" here joins two facts about the same student, and those two facts are recorded in two different tuples. A tuple-at-a-time condition cannot see both at once.
Correct expression — form the two sets of roll numbers and intersect them:
CS ← π Rollno (σ SID='CS01' (ADMISSION)) = {X2019, X2020}
MA ← π Rollno (σ SID='MA02' (ADMISSION)) = {X2019, X3001}
RESULT ← CS ∩ MA = {X2019}
Equivalently, using difference alone: CS − (CS − MA).
The general rule. Use ∧ when both conditions describe the same tuple (Coursetype='Fulltime' ∧ TotalSeats>40). Use ∩ (or a self-join) when the conditions describe different tuples relating to the same entity.
11.9 Exercises¶
Use the running example relations for all computational questions.
A. Short answer
- State the closure property and why it matters.
- Give the complete set of relational algebra operations.
- What is the degree and cardinality of
σ<sub>c</sub>(R)relative toR? - When does PROJECT not reduce cardinality?
- Define union compatibility. Which operations require it?
- Why is RENAME necessary?
- Give the cardinality and degree of
R × Sin terms of those ofRandS.
B. Write the relational algebra
- Names of all students.
- Details of courses with duration 3 and type Parttime.
- Roll numbers of students admitted on or after 2019-08-01.
- Distinct teachers-in-charge.
- Names of courses taught by a teacher whose name contains "Gupta". (State any assumption about string operators.)
- Roll numbers of students admitted to both
CS01andMA02. - Roll numbers of students admitted to
CS01orCH01. - Roll numbers of students admitted to
CH01but notCS01. - Names of students not admitted to any course.
- Names of students admitted to at least one part-time course.
SIDs of courses with no students admitted.- Names of students born in 2001 who are admitted to
MA02. - Roll numbers of students admitted to more than one course. (Hint: you will need a product of
ADMISSIONwith a renamed copy of itself.)
C. Compute the result
- For each of questions 8 to 20, give the actual resulting relation from the sample data.
- Give the degree and cardinality of:
a.
STUDENT × COURSEb.STUDENT × ADMISSIONc.σ<sub>Coursetype='Fulltime'</sub>(COURSE) × σ<sub>SID='CS01'</sub>(ADMISSION)d.π<sub>Rollno</sub>(ADMISSION)e.π<sub>Rollno, SID</sub>(ADMISSION) R(A,B)has 8 tuples andS(A,B)has 5. State the minimum and maximum cardinality ofR ∪ S,R ∩ S,R − S,S − RandR × S.
D. Analytical
- Prove that
R ∩ S = R − (R − S), by showing that a tuple is in one side if and only if it is in the other. - Draw the query tree for question 19, then draw an optimised version and explain the improvement, quantifying the number of tuples in the intermediate results in each case.
- Explain why
π<sub>Name</sub>(σ<sub>SID='CS01'</sub>(STUDENT × ADMISSION))may give a wrong answer. Correct it. - Is
R − (S − T) = (R − S) ∪ (R ∩ T)? Justify with a proof or a counter-example. - Under what conditions is
π<sub>L</sub>(σ<sub>c</sub>(R)) = σ<sub>c</sub>(π<sub>L</sub>(R))? Give an example where they differ.
E. Objective — True or False with reason
- SELECT is commutative.
- PROJECT is commutative.
R ∪ Smay have more tuples than|R| + |S|.R − S = S − RwhenRandSare union compatible.- Cartesian product requires union compatibility.
πin relational algebra corresponds to SQLSELECTwithoutDISTINCT.σ<sub>A=1 ∧ A=2</sub>(R)is always empty.
Answers to Section E
- True.
σ<sub>c1</sub>(σ<sub>c2</sub>(R)) = σ<sub>c2</sub>(σ<sub>c1</sub>(R)) = σ<sub>c1 ∧ c2</sub>(R). - False.
π<sub>L1</sub>(π<sub>L2</sub>(R))is defined only ifL1 ⊆ L2; reversing the order is generally invalid. - False. Duplicates are removed, so
|R ∪ S| ≤ |R| + |S|. - False. Difference is not commutative; equality holds only in the special case
R = S. - False. Only ∪, ∩ and − require it. Cartesian product exists precisely to combine relations of different shapes.
- False. It corresponds to
SELECT DISTINCT, because PROJECT always removes duplicates. - True. An attribute has one value per tuple, so it cannot equal two distinct constants at once.
Lesson Summary
- Relational algebra is procedural and closed; the complete set is
{σ, π, ∪, −, ×}. - σ chooses rows (same degree, fewer or equal tuples); π chooses columns and always removes duplicates — so it matches
SELECT DISTINCT, notSELECT. |π<sub>L</sub>(R)| = |R|exactly whenLcontains a superkey.- ∪, ∩, − require union compatibility; × does not, and multiplies cardinalities while adding degrees.
- Use ∧ for two conditions on the same tuple; use ∩ for two facts in different tuples.
- "Find X with no Y" = (all X) − (X with Y).
- Push selections down the query tree — the first rule of optimisation.