2020/2/25
1
Relational Algebra
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) 2020/2/25 3
where
2/25/2020 4
• Example: Select the enrolment records for the students of person 1.
𝜎𝜎 𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆=1 𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸
Enrolment#
Supervisee
Supervisor
Department
Name
2 3 4
3 4 5
1 1 1
Comp.Sci Comp.Sci Comp.Sci
Ph.D. M.Sc. 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
4 5
1 1
Comp.Sci Comp.Sci
M.Sc 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. Comp.Sci Comp.Sci
Ph.D. Ph.D. M.Sc.
2020/2/25
9
Properties:
• if
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
then
10
Properties:
• if
π
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)π (RUS))=π (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 = Name
Enrolment#
Supervisee
Supervisor
Department
Name
1 3 4
1 4 5
2 1 1
Psych. Comp.Sci Comp.Sci
Ph.D. M.Sc M.Sc
Person#
1 3 4 5 2
Dr C.C.Chen Ms K.Juliff Ms J.Gledhill Ms B.K.Lee Dr R.G.Wilkinson
2020/2/25 15
3.4 INTERSECTION
• Isthesettheoreticintersectionofthetuplesoftwo
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 4 5
Ms K. Juliff Ms J. Gledhill Ms B.K. Lee
2020/2/25 18
3.6 CARTESIAN PRODUCT
Example:
E’ment#
𝑟𝑟×𝑠𝑠={𝑡𝑡1||𝑡𝑡2:𝑡𝑡1 ∈𝑟𝑟and𝑡𝑡2 ∈𝑠𝑠}
Where 𝑡𝑡1||𝑡𝑡2 indicates the concatenation of tuples.
ENROLMENT × RESEARCHER S’ee S’or
1 1 2 2 3 3 4
12 12 31 31 41 41 51 51
D’ment
Psych. Psych. Comp.Sci Comp.Sci Comp.Sci Comp.Sci Comp.Sci Comp.Sci
E’ment. Name
Ph.D. Ph.D. Ph.D. Ph.D. M.Sc. M.Sc. M.Sc. M.Sc.
Person#
1 2 1 2 1 2 1 2
R’cher. Name
Dr C.C. Chen
Dr R.G.Wilkinson Dr C.C. Chen
Dr R.G.Wilkinson Dr C.C. Chen
Dr R.G.Wilkinson Dr C.C. Chen
Dr R.G.Wilkinson
2020/2/25 4 19
R1 ← ENROLMENT × RESEARCHER 𝜎𝜎 𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆=𝑃𝑃𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝐷𝐷# 𝐸𝐸𝑅 =
More useful is:
E’ment#
S’ee
S’or
D’ment
E’ment. Name
Person#
R’cher. Name
1 2 3 4
1 3 4 5
2 1 1 1
Psych. Comp.Sci. Comp.Sci. Comp.Sci.
Ph.D. Ph.D. M.Sc. M.Sc.
2 1 1 1
Dr R.G.Wilkinson Dr C.C. Chen
Dr C.C. Chen
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) =
E’ment#
S’ee
S’or
R’cher. Name
D’ment
E’ment. Name
1 2 3 4
1 3 4 5
2 1 1 1
Dr R.G.Wilkinson Dr C.C. Chen
Dr C.C. Chen
Dr C.C. Chen
Psych. Comp.Sci. Comp.Sci. Comp.Sci.
Ph.D. Ph.D. M.Sc. M.Sc.
• The last of these is also known as natural join, the next to last is equi-join.
2020/2/25 21
3.7 JOIN
Is used to combine related tuples from two relations.
𝑟𝑟⋈ 𝑠𝑠={𝑡𝑡 ||𝑡𝑡 :𝑡𝑡 ∈𝑟𝑟and𝑡𝑡 ∈𝑠𝑠and𝐵𝐵}
• 3.7.1 Theta-join
𝐵𝐵
121 2
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,
R (A, B) ⋈ S (B, C) ⋈ T (C, D)
2020/2/25 25
how do you define the join result? Why?
• Notes:
1. In a natural join, there may be several pairs of join attributes.
Example:
COURSE
Department
Name
By
Comp.Sci Comp.Sci. Psychology
Ph.D. M.Sc. M.Sc.
Research
Research Coursework
𝐸𝐸𝑁𝑁𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝑁𝑁𝐸𝐸⋈ 𝐷𝐷𝑆𝑆𝑆𝑆𝑁𝑁𝑆𝑆𝐷𝐷𝑁𝑁𝑆𝑆𝐷𝐷𝐷𝐷,𝑁𝑁𝑁𝑁𝑁𝑁𝑆𝑆 ,(𝐷𝐷𝑆𝑆𝑆𝑆𝑁𝑁𝑆𝑆𝐷𝐷𝑁𝑁𝑆𝑆𝐷𝐷𝐷𝐷,𝑁𝑁𝑁𝑁𝑁𝑁𝑆𝑆) 𝑅𝑅𝐸𝐸𝐶𝐶𝐸𝐸𝑆𝑆𝐸𝐸
Calculate
• 2.Ifthepairsofjoiningattributesareexactlythosethat are identically named, we can write
2020/2/25
ENROLMENT⋈COURSE
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 a1 a2 a3 a4 a5 a5
b1 b2 b1 b2 b1 b1 b2
Q
B
b1 b2
𝑃𝑃÷𝑄𝑄=
A
a1 a5
2020/2/25
28
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