Relational Algebra
Relational Algebra
2020/2/25 1
3. Relational Algebra
• Relational Algebra is a procedural DML.
• It specifies operations on relations to define
new relations:
Select, Project, Union, Intersection,
Difference, Cartesian Product, Join, Divide.
2020/2/25 2
3.1 SELECT
• Selects a subset of the tuples of a relation r, satisfying some condition.
𝜎𝜎𝐵𝐵 𝑟𝑟 = 𝑡𝑡 ∈ 𝑟𝑟:𝐵𝐵(𝑡𝑡)
• B is the selection condition, composed of selection clauses combined
using AND, OR and NOT.
• A selection clause has the form
or
(join, introduce later)
where
2020/2/25 3
2/25/2020 4
• Example: Select the enrolment records for the
students of person 1.
𝜎𝜎 𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆=1 𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸
Enrolment# Supervisee Supervisor Department Name
2 3 1 Comp.Sci Ph.D.
3 4 1 Comp.Sci M.Sc.
4 5 1 Comp.Sci M.Sc.
2020/2/25 5
• Example: Select the enrolment records for
person 1’s non-Ph.D. students:
𝜎𝜎 𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆=1 AND NOT 𝑁𝑁𝑁𝑁𝑁𝑁𝑆𝑆≠”𝑃𝑃𝑃𝑃.𝐷𝐷” 𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸
Enrolment# Supervisee Supervisor Department Name
3 4 1 Comp.Sci M.Sc
4 5 1 Comp.Sci M.Sc
2020/2/25 6
Properties:
• Commutative:
σ
σ
• Consecutive selects can be combined:
σ
σ
2020/2/25 7
3.2 PROJECT
• Projects onto a subset X of the attributes of a
relation.
𝜋𝜋𝑋𝑋 𝑟𝑟 = 𝑡𝑡 𝑋𝑋 : 𝑡𝑡 ∈ 𝑟𝑟
• Remember that a tuple, t is a mapping from
attributes to elements of their domains. t[X] is
the restriction of that mapping to the set of
attributes X.
2020/2/25 8
• Example: Which courses are students enrolled
in?
𝜋𝜋𝐷𝐷𝑆𝑆𝑆𝑆𝑁𝑁𝑆𝑆𝐷𝐷𝑁𝑁𝑆𝑆𝐷𝐷𝐷𝐷,𝑁𝑁𝑁𝑁𝑁𝑁𝑆𝑆 𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸 =
Department Name
Psych. Ph.D.
Comp.Sci Ph.D.
Comp.Sci M.Sc.
2020/2/25 9
Properties:
• if
π
else
The operation is not well defined.
• commutes with selection:
πX (σB(R)) = σB (πX(R))
Exercise: Verify the above with:
π{Department} (σ (Department=“Psychology”)(ENROLMENT)).
2020/2/25 10
Properties:
• if
π
else
The operation is not well defined.
• commutes with selection: B cannot be specified outside of X
πX (σB(R)) = σB (πX(R))
Exercise: Verify the above with:
π{Department} (σ (Department=“Psychology”)(ENROLMENT)).
2020/2/25 11
Questions
1) π (R U S)) = π (R) U π (S)?
2) π (R ∩ S)) = π (R) ∩ π (S)?
2020/2/25 12
Answer:
2) π (R ∩ S)) ≠ π (R) ∩ π (S)
Example:
R = (Animal, Cat), S = (Animal, Dog)
π: project on the first column
π (R ∩ S)) = {}
π (R) ∩ π (S) = {Animal}
2020/2/25 13
3.3 UNION
• Is the set theoretic union of the tuples of two
relations.
𝑟𝑟 ∪ 𝑠𝑠 = {𝑡𝑡: 𝑡𝑡 ∈ 𝑟𝑟 𝑜𝑜𝑟𝑟 𝑡𝑡 ∈ 𝑠𝑠}
• Note: Requires R and S to be union compatible:
that there is a 1-1 correspondence between
their attributes, in which corresponding
attributes are over the same domain.
2020/2/25 14
• Example:
R1 ← σ (Supervisor=2) (ENROLMENT)
R2 ← σ (Name=“M.Sc′′) (ENROLMENT)
R1 ∪ R2 =
• Example: STUDENT ∪ RESEARCHER =
Enrolment# Supervisee Supervisor Department Name
1 1 2 Psych. Ph.D.
3 4 1 Comp.Sci M.Sc
4 5 1 Comp.Sci M.Sc
Person# Name
1 Dr C.C.Chen
3 Ms K.Juliff
4 Ms J.Gledhill
5 Ms B.K.Lee
2 Dr R.G.Wilkinson2020/2/25 15
3.4 INTERSECTION
• Is the set theoretic intersection of the tuples of two
relations.
𝑟𝑟 ∩ 𝑠𝑠 = 𝑡𝑡: 𝑡𝑡 ∈ 𝑟𝑟 𝑎𝑎𝑎𝑎𝑎𝑎 𝑡𝑡 ∈ 𝑠𝑠 .
• Example:
R1 ← σ (Supervisor=1) (ENROLMENT)
R2 ← σ (Name=“Ph.D.′′) (ENROLMENT)
R1 ∩ R2 =
Enrolment# Supervisee Supervisor Department Name
2 3 1 Comp.Sci. Ph.D.
2020/2/25 16
• Example: STUDENT ∩ RESEARCHER =
Person# Name
1 Dr C.C. Chen
2020/2/25 17
3.5 DIFFERENCE
• Is the set difference of the tuples of two
relations.
𝑟𝑟 − 𝑠𝑠 = {𝑡𝑡: 𝑡𝑡 ∈ 𝑟𝑟 and 𝑡𝑡∉𝑠𝑠}
• Example: STUDENT − RESEARCHER =
Person# Name
3 Ms K. Juliff
4 Ms J. Gledhill
5 Ms B.K. Lee
2020/2/25 18
3.6 CARTESIAN PRODUCT
𝑟𝑟 × 𝑠𝑠 = {𝑡𝑡1||𝑡𝑡2: 𝑡𝑡1 ∈ 𝑟𝑟 and 𝑡𝑡2 ∈ 𝑠𝑠}
Where 𝑡𝑡1||𝑡𝑡2 indicates the concatenation of tuples.
Example:
ENROLMENT × RESEARCHER
E’ment# S’ee S’or D’ment E’ment.
Name
Person# R’cher. Name
1 1 2 Psych. Ph.D. 1 Dr C.C. Chen
1 1 2 Psych. Ph.D. 2 Dr R.G.Wilkinson
2 3 1 Comp.Sci Ph.D. 1 Dr C.C. Chen
2 3 1 Comp.Sci Ph.D. 2 Dr R.G.Wilkinson
3 4 1 Comp.Sci M.Sc. 1 Dr C.C. Chen
3 4 1 Comp.Sci M.Sc. 2 Dr R.G.Wilkinson
4 5 1 Comp.Sci M.Sc. 1 Dr C.C. Chen
4 5 1 Comp.Sci M.Sc. 2 Dr R.G.Wilkinson2020/2/25 19
More useful is:
R1 ← ENROLMENT × RESEARCHER
𝜎𝜎 𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆=𝑃𝑃𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝐷𝐷# 𝐸𝐸𝑅 =
E’ment# S’ee S’or D’ment E’ment.
Name
Person# R’cher. Name
1 1 2 Psych. Ph.D. 2 Dr R.G.Wilkinson
2 3 1 Comp.Sci. Ph.D. 1 Dr C.C. Chen
3 4 1 Comp.Sci. M.Sc. 1 Dr C.C. Chen
4 5 1 Comp.Sci. M.Sc. 1 Dr C.C. Chen
2020/2/25 20
• or even better:
R1 ← ENROLMENT × RESEARCHER
R2 ← σ(Supervisor=Person#)(R1) =
π{E′ment#,S′ee,S′or,R′cher.Name,D′ment,E′ment.Name}(R2) =
• The last of these is also known as natural join, the next to last is
equi-join.
E’ment# S’ee S’or R’cher. Name D’ment E’ment. Name
1 1 2 Dr R.G.Wilkinson Psych. Ph.D.
2 3 1 Dr C.C. Chen Comp.Sci. Ph.D.
3 4 1 Dr C.C. Chen Comp.Sci. M.Sc.
4 5 1 Dr C.C. Chen Comp.Sci. M.Sc.
2020/2/25 21
3.7 JOIN
Is used to combine related tuples from two
relations.
• 3.7.1 Theta-join
𝑟𝑟 ⋈ 𝐵𝐵 𝑠𝑠 = {𝑡𝑡1||𝑡𝑡2: 𝑡𝑡1 ∈ 𝑟𝑟 and 𝑡𝑡2 ∈ 𝑠𝑠 and 𝐵𝐵}
B is composed of conditions (combined with AND)
of the form 𝐴𝐴𝑆𝑆𝜃𝜃 𝐵𝐵𝑗𝑗where 𝐴𝐴𝑆𝑆 is an attribute of R,
𝐵𝐵𝑗𝑗 is an attribute of S, and 𝜃𝜃 is a comparison
operator.
2020/2/25 22
• 3.7.2 Equi-join
Is a theta-join where each comparison operator
is “=”.
Example:
𝐸𝐸𝑁𝑁𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝑁𝑁𝐸𝐸⋈
𝐸𝐸𝐸𝐸𝑆𝑆𝐸𝐸𝑅𝑅𝐸𝐸𝑅𝑅𝑃𝑃𝐸𝐸𝐸𝐸 (𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆=𝑃𝑃𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝐷𝐷#)
2020/2/25 23
• 3.7.3 Natural join
Is an equi-join where only one attribute from
each comparison is retained.
Example:
• Question: If two relations have no join
attributes,
how do you define the join result? Why?
𝐸𝐸𝑁𝑁𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝑁𝑁𝐸𝐸⋈
𝐸𝐸𝐸𝐸𝑆𝑆𝐸𝐸𝑅𝑅𝐸𝐸𝑅𝑅𝑃𝑃𝐸𝐸𝐸𝐸 𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆 ,(𝑃𝑃𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝐷𝐷#)
2020/2/25 24
• 3.7.3 Natural join
Is an equi-join where only one attribute from
each comparison is retained.
Example:
• Question: If two relations have no join
attributes,
how do you define the join result? Why?
R (A, B) ⋈ S (B, C) ⋈ T (C, D)
𝐸𝐸𝑁𝑁𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝑁𝑁𝐸𝐸⋈
𝐸𝐸𝐸𝐸𝑆𝑆𝐸𝐸𝑅𝑅𝐸𝐸𝑅𝑅𝑃𝑃𝐸𝐸𝐸𝐸 𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆 ,(𝑃𝑃𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝐷𝐷#)
2020/2/25 25
• Notes:
1. In a natural join, there may be several pairs of
join attributes.
Example:
Calculate
𝐸𝐸𝑁𝑁𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝑁𝑁𝐸𝐸⋈
𝑅𝑅𝐸𝐸𝐶𝐶𝐸𝐸𝑆𝑆𝐸𝐸 𝐷𝐷𝑆𝑆𝑆𝑆𝑁𝑁𝑆𝑆𝐷𝐷𝑁𝑁𝑆𝑆𝐷𝐷𝐷𝐷,𝑁𝑁𝑁𝑁𝑁𝑁𝑆𝑆 ,(𝐷𝐷𝑆𝑆𝑆𝑆𝑁𝑁𝑆𝑆𝐷𝐷𝑁𝑁𝑆𝑆𝐷𝐷𝐷𝐷,𝑁𝑁𝑁𝑁𝑁𝑁𝑆𝑆)
• 2. If the pairs of joining attributes are exactly those that
are identically named, we can write
ENROLMENT⋈COURSE
COURSE
Department Name By
Comp.Sci Ph.D. Research
Comp.Sci. M.Sc. Research
Psychology M.Sc. Coursework
2020/2/25 26
3.8 DIVIDE
Suppose R is a relation over Z, S over X with
X ⊆ Z. Let Y = Z − X. Then R ÷ S is a relation
over Y ,
R ÷ S = {t : t × S ⊆ R }
2020/2/25 27
Example:
P
A B
a1 b1
a1 b2
a2 b1
a3 b2
a4 b1
a5 b1
a5 b2
Q
B
b1
b2
𝑃𝑃 ÷ 𝑄𝑄 =
2020/2/25 28
A
a1
a5
Typical use: Which courses are offered by all
departments?
𝐶𝐶𝐸𝐸𝐶𝐶𝐸𝐸𝐶𝐶𝐸𝐸 ÷ (𝜋𝜋{𝐷𝐷𝑆𝑆𝑆𝑆𝑁𝑁𝑆𝑆𝐷𝐷𝑁𝑁𝑆𝑆𝐷𝐷𝐷𝐷}𝐶𝐶𝐸𝐸𝐶𝐶𝐸𝐸𝐶𝐶𝐸𝐸)
Note: {σ, π,∪,−,×} are sufficient to define all these
operations: this is a relationally complete set of
operators.
2020/2/25 29
Relational Algebra
3. Relational Algebra
3.1 SELECT
Slide Number 4
Slide Number 5
Slide Number 6
Slide Number 7
3.2 PROJECT
Slide Number 9
Slide Number 10
Slide Number 11
Slide Number 12
Slide Number 13
3.3 UNION
Slide Number 15
3.4 INTERSECTION
Slide Number 17
3.5 DIFFERENCE
3.6 CARTESIAN PRODUCT
Slide Number 20
Slide Number 21
3.7 JOIN
Slide Number 23
Slide Number 24
Slide Number 25
Slide Number 26
3.8 DIVIDE
Slide Number 28
Slide Number 29