Lesson 12: Relational Algebra II: Joins, Division and Aggregation¶
Joins, outer joins, division and aggregation
About this lesson
Course: Database Management Systems
Unit 3: Relational Data Model · 7 Lecture Hours
Lesson duration: 2 lectures
Reading: Elmasri & Navathe, Ch. 8.3, 8.4, 8.5
Learning Outcomes
- Apply theta join, equijoin and natural join, and state the differences precisely.
- Apply left, right and full outer joins, and explain when each is needed.
- Apply semi-join and anti-join.
- Recognise and solve division (÷) problems — the "for all" queries.
- Use aggregate functions and grouping (
ℱ). - Compose multi-step queries and reason about intermediate cardinalities.
12.1 The Join Operations¶
Lesson 3 ended with the observation that × followed by σ is the useful combination. That combination is the JOIN.
Theta join (⋈θ)¶
Theta join
R ⋈<sub><condition></sub> S = σ<sub><condition></sub>(R × S)
Combines each tuple of R with each tuple of S, keeping only pairs satisfying the condition. The condition may use any comparison operator: =, ≠, <, ≤, >, ≥.
- Degree = degree(R) + degree(S). All attributes of both are kept.
- Cardinality:
0 ≤ |R ⋈<sub>θ</sub> S| ≤ |R| × |S|.
Example 1. Pairs of courses where the first has strictly more seats than the second.
COURSE ⋈<sub>TotalSeats > TotalSeats2</sub> ρ<sub>C2(SID2,Cname2,TotalSeats2,...)</sub>(COURSE)
The rename is essential — without it the condition cannot say which TotalSeats is meant.
Equijoin¶
Equijoin
A theta join in which every comparison in the condition is equality (=).
Its defining feature: the result contains two identical columns for each equality — one from each relation.
Example 2. STUDENT ⋈<sub>STUDENT.Rollno = ADMISSION.Rollno</sub> ADMISSION
| STUDENT.Rollno | Name | Dateofbirth | ADMISSION.Rollno | SID | Dateofadmission |
|---|---|---|---|---|---|
| X2019 | Ankit Sharma | 2001-03-14 | X2019 | CS01 | 2019-07-15 |
| X2019 | Ankit Sharma | 2001-03-14 | X2019 | MA02 | 2019-08-01 |
| X2020 | Riya Verma | 2002-05-11 | X2020 | CS01 | 2019-07-16 |
| Z1188 | Sana Iqbal | 2001-11-02 | Z1188 | CH01 | 2019-07-18 |
| Z1188 | Sana Iqbal | 2001-11-02 | Z1188 | EN03 | 2019-08-05 |
| X3001 | Aditi Rao | 2001-07-09 | X3001 | MA02 | 2019-07-20 |
Degree 3 + 3 = 6, cardinality 6. Note Rollno appears twice, redundantly — and Z2049 Arjun Nair, having no admission, has disappeared.
Natural join (⋈ or *)¶
Natural join
R ⋈ S
An equijoin on all attributes with the same name in both relations, with the duplicate columns removed — each common attribute appears once.
- Degree = degree(R) + degree(S) − (number of common attributes).
- If there are no common attributes, the natural join degenerates to the Cartesian product.
Example 3. STUDENT ⋈ ADMISSION — the common attribute is Rollno.
| Rollno | Name | Dateofbirth | SID | Dateofadmission |
|---|---|---|---|---|
| X2019 | Ankit Sharma | 2001-03-14 | CS01 | 2019-07-15 |
| X2019 | Ankit Sharma | 2001-03-14 | MA02 | 2019-08-01 |
| X2020 | Riya Verma | 2002-05-11 | CS01 | 2019-07-16 |
| Z1188 | Sana Iqbal | 2001-11-02 | CH01 | 2019-07-18 |
| Z1188 | Sana Iqbal | 2001-11-02 | EN03 | 2019-08-05 |
| X3001 | Aditi Rao | 2001-07-09 | MA02 | 2019-07-20 |
Degree 3 + 3 − 1 = 5. Rollno appears once.
Example 4 — three-way natural join. STUDENT ⋈ ADMISSION ⋈ COURSE joins on Rollno and then on SID, giving degree 3 + 3 + 6 − 1 − 1 = 10 and cardinality 6.
The danger of natural join
Natural join matches on name, not on meaning. If STUDENT and COURSE both happened to have an attribute called Name, then STUDENT ⋈ COURSE would silently join student names to course names — producing nonsense with no error message.
For this reason many practitioners avoid NATURAL JOIN in production SQL and write the join condition explicitly. Rename first when in doubt.
Comparison¶
| Theta join | Equijoin | Natural join | |
|---|---|---|---|
| Condition | Any comparison | Equality only | Implicit: equality on all same-named attributes |
| Condition written? | Yes | Yes | No |
| Duplicate columns | May occur | Always occur | Removed |
| Degree | d(R)+d(S) |
d(R)+d(S) |
d(R)+d(S) − #common |
| No matching attributes | — | — | Becomes R × S |
12.2 Outer Joins¶
The joins above are inner joins: unmatched tuples are lost. Arjun Nair vanished from Example 3, and PH01 Physics never appears at all. Outer joins preserve them.
The three outer joins
Left outer join R ⟕ S — every tuple of R appears; where there is no match in S, the S attributes are filled with NULL.
Right outer join R ⟖ S — every tuple of S appears; unmatched R attributes become NULL.
Full outer join R ⟗ S — every tuple of both appears; unmatched attributes on either side become NULL.
Example 5. STUDENT ⟕ ADMISSION — keep every student, matched or not.
| Rollno | Name | Dateofbirth | SID | Dateofadmission |
|---|---|---|---|---|
| X2019 | Ankit Sharma | 2001-03-14 | CS01 | 2019-07-15 |
| X2019 | Ankit Sharma | 2001-03-14 | MA02 | 2019-08-01 |
| X2020 | Riya Verma | 2002-05-11 | CS01 | 2019-07-16 |
| Z1188 | Sana Iqbal | 2001-11-02 | CH01 | 2019-07-18 |
| Z1188 | Sana Iqbal | 2001-11-02 | EN03 | 2019-08-05 |
| Z2049 | Arjun Nair | 2003-01-25 | NULL | NULL |
| X3001 | Aditi Rao | 2001-07-09 | MA02 | 2019-07-20 |
Cardinality 7 — Arjun Nair is preserved with NULLs.
The outer-join trick for 'find those with none'
Lesson 3 solved "students admitted to no course" with set difference. An outer join gives an alternative:
π<sub>Name</sub>(σ<sub>SID IS NULL</sub>(STUDENT ⟕ ADMISSION)) → {Arjun Nair}
Keep everybody, then keep only the rows where the match failed. In SQL this is the well-known LEFT JOIN ... WHERE ... IS NULL idiom, and it is often faster than NOT IN.
Example 6. Courses with no students: π<sub>Cname</sub>(σ<sub>Rollno IS NULL</sub>(COURSE ⟕ ADMISSION)) → {Physics}.
12.3 Semi-join and Anti-join¶
Semi-join (⋉)
R ⋉ S = the tuples of R that have at least one matching tuple in S. Only R's attributes are returned, and each qualifying tuple appears once.
R ⋉ S = π<sub>attributes of R</sub>(R ⋈ S)
Anti-join (▷)
R ▷ S = the tuples of R with no matching tuple in S.
R ▷ S = R − (R ⋉ S)
Example 7. STUDENT ⋉ ADMISSION = the four students who have at least one admission — each listed once, even X2019 who has two.
Example 8. STUDENT ▷ ADMISSION = {Arjun Nair} — a third way to express the "no course" query.
These correspond to SQL's EXISTS and NOT EXISTS, and optimisers use them heavily because they avoid producing the wide, duplicated intermediate result that a full join would.
12.4 DIVISION (÷) — the "for all" operation¶
The hardest operation, and the one examinations love. It answers queries containing "for all", "every" or "all of the".
Division
Let R(Z) and S(X) where X ⊆ Z, and let Y = Z − X (the attributes of R not in S).
R ÷ S is a relation over Y containing every tuple t such that for every tuple s in S, the combined tuple ⟨t, s⟩ appears in R.
In words: the Y-values that are paired with all the X-values in S.
How to spot a division problem
The English contains "all", "every", or "each" applied to a set — for example:
- Students admitted to all part-time courses.
- Suppliers who supply every part.
- Employees who work on all projects controlled by department 5.
If the query says "at least one", it is a join. If it says "all", it is a division.
Worked example¶
Query: roll numbers of students admitted to all part-time courses.
Step 1 — the divisor. The set of part-time course IDs:
PT ← π SID (σ Coursetype='Parttime' (COURSE))
| SID |
|---|
| MA02 |
| EN03 |
Step 2 — the dividend. The (student, course) pairs:
SC ← π Rollno, SID (ADMISSION)
| Rollno | SID |
|---|---|
| X2019 | CS01 |
| X2019 | MA02 |
| X2020 | CS01 |
| Z1188 | CH01 |
| Z1188 | EN03 |
| X3001 | MA02 |
Step 3 — divide. RESULT ← SC ÷ PT
Check each student against both required courses:
| Student | Has MA02? | Has EN03? | In result? |
|---|---|---|---|
| X2019 | yes | no | no |
| X2020 | no | no | no |
| Z1188 | no | yes | no |
| X3001 | yes | no | no |
Result: empty. No student is admitted to both part-time courses. (This is a correct and instructive answer — verify it rather than assuming a non-empty result.)
Second illustration, so the operation is seen to work. Divide by PT2 = {MA02} alone: the answer is {X2019, X3001} — both students admitted to MA02.
Division from the basic operations¶
Division is not primitive. It is defined as:
R(Z) ÷ S(X), where Y = Z − X
T1 ← π Y (R) -- every candidate Y value
T2 ← π Y ( (T1 × S) − R ) -- candidates MISSING some pairing
RESULT ← T1 − T2 -- candidates missing NOTHING
Reading the definition. T1 × S builds every pairing that would have to exist. Subtracting R leaves the pairings that are missing. Projecting onto Y names the candidates that are disqualified. Removing them from T1 leaves exactly those paired with everything.
Trace with SC ÷ PT:
T1 = π Rollno (SC) = {X2019, X2020, Z1188, X3001}
T1 × PT = {(X2019,MA02),(X2019,EN03),(X2020,MA02),(X2020,EN03),
(Z1188,MA02),(Z1188,EN03),(X3001,MA02),(X3001,EN03)}
(T1 × PT) − SC = {(X2019,EN03),(X2020,MA02),(X2020,EN03),
(Z1188,MA02),(X3001,EN03)} -- the missing pairings
T2 = π Rollno(...) = {X2019, X2020, Z1188, X3001} -- all disqualified
RESULT = T1 − T2 = { } -- empty, as computed above
Division and SQL
SQL has no division operator. A division query is written either as a double NOT EXISTS ("there is no required course for which there is no admission") or by counting ("the number of distinct required courses this student has equals the total number of required courses"). Both idioms are shown in Unit 4, Lesson 5.
12.5 Aggregate Functions and Grouping¶
The operations so far cannot compute a count, sum or average — these produce a single value from a set of tuples, which no set operation does. An extra operator is required.
Aggregate function operation
<sub><grouping attributes></sub> ℱ <sub><function list></sub> (R)
Group the tuples of R by the grouping attributes, then apply each aggregate function to each group. If the grouping list is empty, the whole relation is one group.
Functions: COUNT, SUM, AVG, MAX, MIN.
Example 9 — no grouping. Total number of admissions.
ℱ<sub>COUNT(Rollno)</sub>(ADMISSION) → a single tuple, 6.
Example 10 — grouping. Number of students admitted to each course.
<sub>SID</sub>ℱ<sub>COUNT(Rollno)</sub>(ADMISSION)
| SID | COUNT(Rollno) |
|---|---|
| CS01 | 2 |
| MA02 | 2 |
| CH01 | 1 |
| EN03 | 1 |
Note that PH01 does not appear — it has no tuples in ADMISSION, so it forms no group. To include it with a count of 0, first take an outer join with COURSE. This is exactly the LEFT JOIN + COUNT idiom of Unit 4.
Example 11 — several functions. <sub>Coursetype</sub>ℱ<sub>COUNT(SID), AVG(TotalSeats), MAX(TotalSeats)</sub>(COURSE)
| Coursetype | COUNT(SID) | AVG(TotalSeats) | MAX(TotalSeats) |
|---|---|---|---|
| Fulltime | 3 | 48.33 | 60 |
| Parttime | 2 | 45.00 | 50 |
Aggregates and NULL
All aggregate functions ignore NULLs, with one exception: COUNT(*) counts rows, including those that are entirely NULL in the counted column.
So COUNT(*) and COUNT(SomeColumn) differ whenever that column contains NULLs — a distinction that matters constantly after an outer join.
12.6 A Complete Operations Table¶
| Operation | Symbol | Purpose | Degree of result | Cardinality of result |
|---|---|---|---|---|
| SELECT | σ | Choose rows | same as R |
0 … |R| |
| PROJECT | π | Choose columns, remove duplicates | |L| |
1 … |R| |
| RENAME | ρ | Rename relation / attributes | same | same |
| UNION | ∪ | Tuples in either | same | max … |R|+|S| |
| INTERSECTION | ∩ | Tuples in both | same | 0 … min |
| DIFFERENCE | − | Tuples in R not in S |
same | 0 … |R| |
| CARTESIAN PRODUCT | × | All combinations | d(R)+d(S) |
|R| × |S| |
| THETA JOIN | ⋈θ | Combine on a condition | d(R)+d(S) |
0 … |R|×|S| |
| EQUIJOIN | ⋈= | Combine on equality | d(R)+d(S) |
0 … |R|×|S| |
| NATURAL JOIN | ⋈ | Equijoin on same-named attributes, dedup columns | d(R)+d(S)−c |
0 … |R|×|S| |
| LEFT OUTER JOIN | ⟕ | Keep all of R |
d(R)+d(S) |
≥ |R| |
| RIGHT OUTER JOIN | ⟖ | Keep all of S |
d(R)+d(S) |
≥ |S| |
| FULL OUTER JOIN | ⟗ | Keep all of both | d(R)+d(S) |
≥ max(|R|,|S|) |
| SEMI-JOIN | ⋉ | Tuples of R having a match |
d(R) |
0 … |R| |
| ANTI-JOIN | ▷ | Tuples of R having no match |
d(R) |
0 … |R| |
| DIVISION | ÷ | "For all" | d(R)−d(S) |
0 … |π<sub>Y</sub>(R)| |
| AGGREGATE | ℱ | Group and compute | |G| + |F| |
number of groups |
12.7 Solved Questions¶
Solved Question 1
Q. Distinguish theta join, equijoin and natural join. Give the degree of each for STUDENT (degree 3) and ADMISSION (degree 3) with one common attribute.
A.
A theta join R ⋈<sub>θ</sub> S = σ<sub>θ</sub>(R × S) combines tuples satisfying any condition θ, which may use any comparison operator.
An equijoin is the special case in which every comparison in θ is equality. Its characteristic consequence is that the result contains two identical columns for each equated pair.
A natural join R ⋈ S is an equijoin on all identically-named attributes, written without an explicit condition, and with the duplicate columns removed.
| Theta | Equi | Natural | |
|---|---|---|---|
| Condition | any operator | = only |
implicit |
| Written explicitly | yes | yes | no |
| Duplicate columns | possible | always | removed |
| Degree here | 3+3 = 6 |
3+3 = 6 |
3+3−1 = 5 |
Two cautions. If the relations share no attribute name, the natural join silently becomes the Cartesian product. And because it matches on name rather than meaning, an accidental shared name (say both relations having Name) produces a meaningless join with no error — which is why explicit join conditions are preferred in production code.
Solved Question 2
Q. What is an outer join? Explain the three kinds and give a query that requires each.
A. An inner join discards tuples with no matching partner. An outer join preserves them, padding the missing side with NULLs.
Left outer join R ⟕ S keeps every tuple of R.
Query: "List every student with their courses, including students with no admission."
STUDENT ⟕ ADMISSION — Arjun Nair appears with NULLs.
Right outer join R ⟖ S keeps every tuple of S.
Query: "List every course with its students, including courses with none."
ADMISSION ⟖ COURSE — Physics appears with NULLs.
Full outer join R ⟗ S keeps every tuple of both.
Query: "List all students and all courses, showing admissions where they exist, and flagging both unadmitted students and empty courses."
STUDENT ⟗ ADMISSION combined appropriately — both Arjun Nair and unmatched admissions would be preserved.
Why outer joins matter. They are essential whenever a report must show a zero. An inner join produces no row for a course with no students, so the course silently disappears from the report; a left outer join produces a row with NULL, which COUNT then reports as 0. Note that RIGHT OUTER JOIN is redundant in principle — R ⟖ S equals S ⟕ R — and is provided only for convenience.
Solved Question 3
Q. Define division. Express it using the basic operations. Solve: "roll numbers of students admitted to all full-time courses."
A. Definition. For R(Z) and S(X) with X ⊆ Z and Y = Z − X, the division R ÷ S is the set of Y-tuples t such that for every s ∈ S, the tuple ⟨t, s⟩ is in R.
In terms of the basic operations:
T1 ← π Y (R)
T2 ← π Y ( (T1 × S) − R )
R ÷ S ← T1 − T2
T1 × S enumerates every pairing that would be required; subtracting R leaves the missing pairings; projecting names the disqualified candidates; removing them leaves those missing nothing.
Solution.
FT ← π SID (σ Coursetype='Fulltime' (COURSE)) = {CS01, CH01, PH01}
SC ← π Rollno, SID (ADMISSION)
RESULT ← SC ÷ FT
Checking each student against all three required courses:
| Student | CS01 | CH01 | PH01 | Qualifies? |
|---|---|---|---|---|
| X2019 | yes | no | no | no |
| X2020 | yes | no | no | no |
| Z1188 | no | yes | no | no |
| X3001 | no | no | no | no |
Result: empty. Indeed no student can qualify, since PH01 has no admissions at all — so no student is paired with it, and every candidate is disqualified.
Note on the empty divisor. If the divisor S were empty, the condition "for every s ∈ S" is vacuously true, so R ÷ S would return all of π<sub>Y</sub>(R). This edge case is worth stating in an examination answer.
Solved Question 4
Q. Write relational algebra for each, and give the result from the sample data.
a. Names of students and the names of courses they are admitted to. b. Names of students admitted to a part-time course. c. Names of courses with no students. d. For each course type, the number of courses and the average seats. e. Name of the course with the most students admitted.
A.
a. π<sub>Name, Cname</sub>(STUDENT ⋈ ADMISSION ⋈ COURSE)
| Name | Cname |
|---|---|
| Ankit Sharma | Computer Science |
| Ankit Sharma | Mathematics |
| Riya Verma | Computer Science |
| Sana Iqbal | Chemistry |
| Sana Iqbal | English |
| Aditi Rao | Mathematics |
b. π<sub>Name</sub>(STUDENT ⋈ ADMISSION ⋈ σ<sub>Coursetype='Parttime'</sub>(COURSE)) → {Ankit Sharma, Sana Iqbal, Aditi Rao}.
Note the selection is pushed onto COURSE before the join — the optimisation rule of Lesson 3.
c. π<sub>Cname</sub>(σ<sub>Rollno IS NULL</sub>(COURSE ⟕ ADMISSION)) → {Physics}.
Equivalently by difference: π<sub>Cname</sub>(COURSE ⋈ (π<sub>SID</sub>(COURSE) − π<sub>SID</sub>(ADMISSION))).
d. <sub>Coursetype</sub>ℱ<sub>COUNT(SID), AVG(TotalSeats)</sub>(COURSE)
| Coursetype | COUNT | AVG |
|---|---|---|
| Fulltime | 3 | 48.33 |
| Parttime | 2 | 45.00 |
e. This needs two steps, because "the maximum" must be computed before it can be matched.
CNT ← SID ℱ COUNT(Rollno) AS n (ADMISSION) -- {(CS01,2),(MA02,2),(CH01,1),(EN03,1)}
MAXN ← ℱ MAX(n) AS m (CNT) -- {(2)}
TOP ← π SID ( CNT ⋈ n = m MAXN ) -- {CS01, MA02}
RESULT← π Cname (COURSE ⋈ TOP) -- {Computer Science, Mathematics}
Two courses tie at 2 students, and both are correctly returned — a reminder that "the maximum" queries must handle ties.
Solved Question 5
Q. Explain semi-join and anti-join, express each using the basic operations, and state why an optimiser prefers them.
A. The semi-join R ⋉ S returns the tuples of R that have at least one match in S, projected back onto R's attributes, with each qualifying tuple appearing once:
R ⋉ S = π<sub>attributes of R</sub>(R ⋈ S)
The anti-join R ▷ S returns the tuples of R with no match:
R ▷ S = R − (R ⋉ S)
Examples. STUDENT ⋉ ADMISSION = the four students with at least one admission — X2019 appears once, though he has two admissions. STUDENT ▷ ADMISSION = {Arjun Nair}.
Why the optimiser prefers them. A full join between STUDENT and ADMISSION produces a result that is both wider (all attributes of both relations) and taller (one row per matching pair, so X2019 is duplicated). If the query only asks which students have an admission, all that extra data is built and then thrown away by a projection.
A semi-join can be evaluated by scanning R and, for each tuple, stopping at the first match in S — no duplication, no wide intermediate tuples. In distributed databases the saving is larger still: only the join column need be shipped across the network, not whole tuples.
These operations correspond directly to SQL's EXISTS and NOT EXISTS, which is why those constructs are often faster than the equivalent IN/NOT IN on large tables.
Solved Question 6
Q. Given R(A,B) with 10 tuples and S(B,C) with 6 tuples, where B is common, state the degree and the possible cardinality range of: R × S, R ⋈ S, R ⟕ S, R ⋉ S. Assume B is a key of S.
A.
| Expression | Degree | Cardinality | Reasoning |
|---|---|---|---|
R × S |
2 + 2 = 4 |
exactly 60 | Degrees add, cardinalities multiply: 10 × 6. |
R ⋈ S |
2 + 2 − 1 = 3 |
0 to 10 | Since B is a key of S, each tuple of R matches at most one tuple of S. So the join can never exceed |R| = 10, and is 0 if no B value of R occurs in S. |
R ⟕ S |
3 |
exactly 10 | Every tuple of R appears exactly once — matched (at most one partner, since B is a key of S) or padded with NULLs. |
R ⋉ S |
2 | 0 to 10 | Only R's attributes; a subset of R's tuples. |
The key insight. Without the assumption that B is a key of S, the natural join could produce up to 10 × 6 = 60 tuples in the worst case (if every R tuple matched every S tuple, which requires all B values equal). Declaring B a key of S caps the join at |R|.
This is precisely the reasoning a query optimiser performs: it uses key and foreign-key constraints from the catalog to estimate intermediate result sizes, and those estimates determine the join order it chooses. Good constraints therefore make for good query plans — another practical reason to declare keys properly.
12.8 Exercises¶
Use the running relations from Lesson 3.
A. Short answer
- Express the theta join in terms of
σand×. - What is the degree of a natural join of relations of degree 4 and 5 with 2 common attributes?
- What happens to a natural join when the relations have no common attribute names?
- Distinguish inner join from outer join.
- Define semi-join and anti-join.
- When does a query require division?
- What does
R ÷ Sreturn whenSis empty?
B. Write the relational algebra
- Names of students and their dates of admission.
- Names of students admitted to a course taught by a teacher named 'A. Gupta'.
- Names and seat counts of all courses, including those with no students.
- Names of students admitted to at least two courses.
- Names of students admitted to all part-time courses.
- Names of students admitted to all courses taught by teachers whose name contains 'Gupta'.
- For each student, the number of courses they are admitted to.
- For each course, the name and the number of vacant seats.
- The name of the course with the fewest students.
- Names of students who are admitted to
CS01but to no part-time course. - Pairs of distinct students admitted to the same course. (Take care to avoid listing each pair twice.)
- Names of courses in which every admitted student was born in 2001.
- Names of teachers who are in charge of both a full-time and a part-time course.
C. Compute
- Give the actual result of each of questions 8 to 20 from the sample data.
- Give degree and cardinality:
a.
STUDENT ⋈ ADMISSION ⋈ COURSEb.STUDENT ⟕ ADMISSIONc.COURSE ⟕ ADMISSIONd.STUDENT ⋉ ADMISSIONe.STUDENT ▷ ADMISSIONf.π<sub>Rollno,SID</sub>(ADMISSION) ÷ π<sub>SID</sub>(σ<sub>Coursetype='Parttime'</sub>(COURSE)) R(A,B)has 12 tuples,S(B,C)has 4,Bis a key ofS, and everyBvalue inRoccurs inS. Give the exact cardinality ofR ⋈ S,R ⟕ S,R ⟖ SandR ⋉ S.
D. Analytical
- Prove that
R ⟕ SandS ⟖ Rproduce the same set of tuples (up to attribute order). - Show step by step, with intermediate tables, that the basic-operation definition of division gives the right answer for
π<sub>Rollno,SID</sub>(ADMISSION) ÷ {MA02}. - Explain why
π<sub>Cname</sub>(σ<sub>Rollno IS NULL</sub>(COURSE ⟕ ADMISSION))andπ<sub>Cname</sub>(COURSE) − π<sub>Cname</sub>(COURSE ⋈ ADMISSION)give the same answer. Which would you expect to be faster, and why? - A student writes
<sub>SID</sub>ℱ<sub>COUNT(Rollno)</sub>(COURSE ⟕ ADMISSION)to count students per course including empty courses. Does it give 0 forPH01? Explain carefully, and give the correct expression. - Explain why declaring a foreign key helps the query optimiser estimate join sizes.
- Rewrite
π<sub>Name</sub>(σ<sub>Coursetype='Parttime'</sub>(STUDENT ⋈ ADMISSION ⋈ COURSE))in an optimised form and quantify the reduction in intermediate result sizes.
E. Objective — True or False with reason
- A natural join always produces fewer tuples than a Cartesian product.
- An equijoin removes duplicate columns.
R ⟕ Salways has at least|R|tuples.- Division is a primitive operation.
COUNT(*)andCOUNT(A)always give the same answer.- A semi-join may return duplicate tuples of
R. R ⋈ S = S ⋈ R.
Answers to Section E
- False. If every tuple of
Rmatches every tuple ofSon the common attributes, the natural join has|R|×|S|tuples, the same as the product (minus the duplicated columns). It is never more, but it need not be fewer. - False. An equijoin keeps both columns; the natural join removes the duplicate.
- True. Every tuple of
Rappears at least once, padded with NULLs if unmatched — and more than once if it has several partners. - False. It is definable from
π,×and−; it exists for convenience. - False. They differ whenever
Acontains NULLs:COUNT(*)counts rows,COUNT(A)counts non-NULL values. - False. By definition each qualifying tuple of
Rappears exactly once, however many matches it has. - True as a set of tuples; the attribute order may differ, which is immaterial under the (attribute, value)-pair definition of a tuple.
Lesson Summary
- Theta join =
σon a product; equijoin = theta join with=only, keeping duplicate columns; natural join = equijoin on same-named attributes, removing them. Degree of natural join =d(R)+d(S) − #common. - Outer joins preserve unmatched tuples with NULLs — essential whenever a report must show a zero.
- Semi-join and anti-join return only
R's attributes, without duplication; they correspond toEXISTSandNOT EXISTS. - Division answers "for all" queries; it is not primitive, and SQL has no operator for it — use double
NOT EXISTSor counting. - Aggregation
ℱgroups and computes; aggregates ignore NULLs exceptCOUNT(*); empty groups do not appear unless an outer join is used first.
End of Unit 3. Next: Unit 4, Lesson 1 — SQL and Data Definition.