Joins, division and expression trees

Why it exists

The six basic operators are enough in theory but awkward in practice: a join is a selection over a product, "for all" needs a complicated expression, and a query written naively can be thousands of times slower than an equivalent one. This page adds the operators actually used and explains how an expression is evaluated and rewritten.

Prerequisites

You need the basic operators and their laws (relational algebra).

Precise definitions

• Theta join $R \bowtie_\theta S = \sigma_\theta(R \times S)$; an equijoin is a theta join whose condition is a conjunction of equalities; the natural join is the equijoin on all common attributes with one copy of each kept.
• Left outer join R ⟕ S: the natural join together with the tuples of $R$ that have no match, padded with NULL for the attributes of $S$. Right outer join R ⟖ S: the same for $S$. Full outer join R ⟗ S: both.
• Semijoin $R \ltimes S = \pi_{R}(R \bowtie S)$: the tuples of $R$ that have a match in $S$ (only the attributes of $R$).
• Division. Let $R(X \cup Y)$ and $S(Y)$. Then $R \div S = \{ t \text{ over } X : \text{for every } s \in S, \ (t, s) \in R \}$. It answers "for all" queries.
• Grouping and aggregation $_{G}\gamma_{f_1(A_1), \ldots}(R)$: group the tuples by the attributes in $G$ and compute aggregates (COUNT, SUM, AVG, MIN, MAX) per group.

How it works

Outer joins

The inner join loses Tara (no department: her did is NULL, and NULL never matches) and the department IT (no employee). The outer joins bring back the unmatched side with NULLs. All three results were also computed by a real database engine (LEFT JOIN, RIGHT JOIN, FULL JOIN) and are identical. Relations of sizes $r$ and $s$: inner $\le$ left, right $\le$ full, and each outer join is at least $\max$ of the corresponding operand size when that operand is preserved.

Division

"Students enrolled in all the courses of Req" cannot be done with a join alone. Division is defined by an expression of the basic operators:

$R \div S = \pi_X(R) - \pi_X\bigl((\pi_X(R) \times S) - R\bigr).$

Read it as: take every candidate $x$ (first term); build all pairs of a candidate with a required value; subtract the pairs that really exist in $R$ to get the missing pairs; project to the candidates that miss something; subtract them from the candidates.

Only student 1 has both C1 and C2. The identity was checked on 300 random instances and against the double-NOT-EXISTS query a real engine runs. Properties: $(R \div S) \times S \subseteq R$; if $S$ is empty the result is every candidate ($\pi_X(R)$); the result has at most $|\pi_X(R)|$ tuples.

Typical shapes. "Employees who work on all projects": $\pi_{\text{eid}, \text{pid}}(\text{Works}) \div \pi_{\text{pid}}(\text{Project})$. "Students who passed all courses taught by X": divide by the (projected) set of those courses. If the divisor is chosen by a condition, apply the selection to the divisor first.

Grouping and aggregates

$_{\text{dept}}\gamma_{\text{COUNT}(\text{sid})}(\text{Student})$ gives one tuple per department with the number of students. Aggregates ignore NULLs (except COUNT(*)). Grouping is where the algebra goes beyond the basic operators: it cannot be expressed with $\sigma, \pi, \cup, -, \times$. SQL's GROUP BY and HAVING are its direct counterparts (joins and aggregates).

Expression trees and equivalence rules

A query is evaluated as a tree whose leaves are relations and whose inner nodes are operators; each node produces an intermediate relation consumed by its parent. Two expressions are equivalent if they give the same result on every instance. Rules used by the optimiser:

1. Selections cascade and commute: $\sigma_{p \wedge q}(R) = \sigma_p(\sigma_q(R))$.
2. A selection followed by a product is a join: $\sigma_\theta(R \times S) = R \bowtie_\theta S$.
3. A selection that mentions attributes of one operand only can be pushed into it: $\sigma_p(R \bowtie S) = \sigma_p(R) \bowtie S$.
4. Joins are commutative and associative, so the order can be chosen.
5. Projection can be pushed down if the attributes needed above (including join attributes) are kept.
6. Selection distributes over union and difference: $\sigma_p(R \cup S) = \sigma_p(R) \cup \sigma_p(S)$, $\sigma_p(R - S) = \sigma_p(R) - \sigma_p(S)$. Projection distributes over union but not over difference or intersection.

Heuristic optimisation

Rules of thumb: (1) break conjunctive selections apart; (2) push selections as far toward the leaves as possible; (3) replace selection-over-product by joins; (4) do the most selective (smallest-result) joins first; (5) push projections down, keeping what is needed later. The goal is to keep the intermediate relations small. The query "attributes of the CS students' enrolments" can be written three ways, all with the same 4 result tuples:

Plan 1 builds the whole product (20 tuples) before selecting. Plan 2 pushes the selection into Student first (2 tuples), then joins (4). Plan 3 joins first (5 tuples) and selects after (4). Work (sum of the intermediate sizes, a crude cost measure): 24, 6 and 9. On realistic tables the differences are huge, which is why the order matters even though the results are equal.

Worked examples

Cheat box

Traps and GATE patterns

Connections

SQL's JOIN, LEFT JOIN, GROUP BY and NOT EXISTS correspond to these operators (joins and aggregates); the same queries can be written in calculus (tuple relational calculus); the base operators are on the previous page.

PYQs

Consider the following three relations in a relational
database:
Employee(eId, eName)
 Brand(bId, bName)
 Own(eId, bId)
Which of the following relational algebra expressions
returns the set of eIds who own all the brands?

Consider the relations r(A, B) and s(B, C), where s,B is a
primary key and r.B is a foreign key referencing s.B.
Consider the query:

DATABASE MANAGEMENT  SYSTEM

Q: r ⟕ (σ B<5 (s))

Let LOJ denote the natural left outer-join operation.
Assume that r and s contain no null values.

Which one of the following queries is NOT equivalent
to Q?

Consider a database that has the relation schema
 CR(StudentName, CourseName). An instance of the
schema CR is as given below:
CR Table

Student Name
Course Name
SA
CA
SA
CB
SA
CC
SB
CB
SB
CC
SC
CA
SC
CB
SC
CC
SD
CA
SD
CB
SD
CC
SD
CD
SE
CD
SE
CA
SE
CB
SF
CA
SF
CB
SF
CC

The following query is run on the database:
T1 ← π CourseName (σ StudentName = 'SA' (CR))
T2 ← CR ÷ T1
The number of rows in T2 is ______.

Consider two relations R1(A, B) with the tuples (1, 5), (3,
7) and R2(A, C) = (1, 7), (4, 9).

Assume that R(A, B, C) is the full natural outer join of R1
and R2. Consider the following tuples of the form (A, B,
C): a = (1,5, null), b = (1, null, 7), c = (3, null, 9), d = (4, 7,
null), e = (1, 5, 7), f = (3, 7, null), g = (4, null, 9). Which
one of the following statements is correct?

Consider the relational schema given below, where eld
of the relation dependent is a foreign key referring to
empld of the relation employee. Assume that every
employee has at least one associated dependent in the
dependent relation.

employee(empld,empName,empAge)

dependent(depld, eld,depName, depAge).

Consider the following relational algebra query:

ΠempId ( employee ) -ΠempId ( employee
⋈(empId=eID )∧( empAge ≤ depAge ) dependent )

The above query evaluates to the set of emplds of
employees whose age is greater than that of

Let R and S be relational schemes such that R = {a, b,
c} and S = {c}. Now consider the following queries on
the database:
         1  πR-S(r) -πR-S(πR-S(r) × s-πR-S,S(r))

         2. {t|t∈πR-S(r) ∧∀u∈s(∃v∈r(u= v[S] ∧t=
v[R-S]))}

        3. {t|t∈πR-S(r) ∧∀v∈r(∃u∈s(u= v[S] ∧t=
v[R-S]))}

4. Select R.a, R.b

  From R, S
 Where R.c = S.c

Which of the above queries are equivalent?

Information about a collection of students is given by
the relation
studInfo(studId, name, sex).

The relation enroll(studId, courseId) gives which
student has enrolled for (or taken) what course(s).

Assume that every course is taken by at least one male
and at least one female student.

What does the following relational algebra expression
represent?

πcourceId ((πstudId (σsex = 'female' ( studInfo )) ×
             πcourseId ( enroll )) - enroll )

A database table T1 has 2000 records and occupies 80
disk blocks. Another table T2 has 400 records and
occupies 20 disk blocks. These two tables have to be
joined as per a specified join condition that needs to be
evaluated for every pair of records from these two
tables. The memory buffer space available can hold
exactly one block of records for T1 and one block of
records for T2 simultaneously at any point in time. No
index is available on either table. If Nested-loop join
algorithm is employed to perform the join, with the
most appropriate choice of table to be used in outer
loop, the number of block accesses required for reading
the data are  .

A database table T1 has 2000 records and occupies 80 disk
blocks. Another table T2 has 400 records and occupies 20
disk blocks. These two tables have to be joined as per a
specified join condition that needs to be evaluated for every
pair of records from these two tables. The memory buffer
space available can hold exactly one block of records for
T1 and one block of records for T2 simultaneously at any
point in time. No index is available on either table. If,
instead of Nested-loop join, Block nested-loop join is used,
again with the most appropriate choice of table in the outer
loop, the reduction in number of block accesses required
for reading the data will be

Self-check

Revision card

References