Chapter 2: Relational algebra
Additional Relational Operators
Lectured by : SEAK Leng
1 2011 - 2012
Relational algebra
2
Operation based query language
Operation
Basic operations:
•Selection
•Projection
•Cross Product
•Union
•Different
•Rename
Additional operations:
•Intersection
•Join
•Division
Complex query and query tree
Relational algebra
3
6 basic operators in relational algebra:
1. Select 𝜎 selects a subset of tuples from reln.
2. Project 𝜋 selects a subset of columns from reln.
3. Cartesian product × allows to combine two relations.
4. Set-difference − tuples in reln. 1, but not in reln2.
5. Union ∪ tuples in reln1 plus tuples in reln2.
6. Rename 𝜌 renames attribute(s) and relation.
Relational algebra
4
Additional operators in relational algebra:
1. Intersection ∩
2. Join ⋈<𝑗𝑜𝑖𝑛 𝑐𝑜𝑛𝑑𝑖𝑡𝑖𝑜𝑛>
3. National Join ⋈
4. Division ÷
Some operators can be expressed in term of others.
Set of relational algebra operation { 𝜎, 𝜋, ∪, 𝜌, −, ×} is complete.
Other relational algebra operations can be expressed as a sequence
of operations from this set.
8. Assignment Operator
5
Denoted by = or ⟵ . It is a binary operator.
Assignment must always be made to a temporary relation variable.
provides a convenient way to express complex queries.
Ex1: 𝜋FName, LName (𝜎𝐷𝑁𝑜=2 (𝐸𝑚𝑝𝑙𝑜𝑦𝑒𝑒)) Employee
ID FName LName Salary DNo
FName LName 1 Sok Dara 3000 3
Sam Sambath 2 Sam Sambath 4000 2
Sok Piseth 3 Sok Piseth 2500 2
TEMP ⟵ 𝜎𝐷𝑁𝑜=2 𝐸𝑚𝑝𝑙𝑜𝑦𝑒𝑒 R FirstName LastName
Sam Sambath
R(FirstName, LastName) ⟵ 𝜋𝐹𝑁𝑎𝑚𝑒,𝐿𝑁𝑎𝑚𝑒 (TEMP)
Sok Piseth
8. Assignment Operator
6
Sometimes easier to write expressions a piece at a time.
Incrementaldevelopment
Documentation of steps involved.
Example2: in-line RA expression:
𝜋𝑆𝑡𝑁𝑎𝑚𝑒 (𝜎𝑆𝑇𝑈𝐷𝐸𝑁𝑇.𝑆𝑡𝐼𝑑=𝑏𝑜𝑟𝑟𝑜𝑤𝑠.𝑆𝑡𝐼𝑑 (𝜎𝑀𝑎𝑗𝑜𝑟="𝐶𝑆" (𝑆𝑇𝑈𝐷𝐸𝑁𝑇𝑆) × 𝑏𝑜𝑟𝑟𝑜𝑤𝑠))
Equivalent sequence of operations by using temporary relation variable:
T1 ⟵ 𝜎𝑀𝑎𝑗𝑜𝑟="𝐶𝑆" 𝑆𝑇𝑈𝐷𝐸𝑁𝑇𝑆
𝑇2 ⟵ 𝜎𝑇1.𝑆𝑡𝐼𝑑=𝑏𝑜𝑟𝑟𝑜𝑤𝑠.𝑆𝑡𝐼𝑑 (𝑇1 × 𝑏𝑜𝑟𝑟𝑜𝑤𝑠)
Result ⟵ 𝜋𝑆𝑡𝑁𝑎𝑚𝑒 𝑇2
1. Set-Intersection
7
R ∩ S . It is binary operation. Relations must be union-compatible.
Includes all tuples that are in both R and S.
Derivation: R ∩ S = R – (R – S) or
R ∩ S = (R ∪ S) – ((R − S) ∪ (S − R))
STUDENT VOLUNTEER
FN LN FN LN FN LN
Ousa Ang Ousa Ang Ousa Ang
Sreylen Chab Sreylen Chab Sreylen Chab
Chhit Chharng
Pich Din
Sanwathnak Chhay
R S R∩S
2. Join Operation
8
Binary operator.
Syntax: R ⋈<𝑗𝑜𝑖𝑛 𝑐𝑜𝑛𝑑𝑖𝑡𝑖𝑜𝑛> S
Combines related tuples from 2 relations into a single relation.
Like Cartesian Product, combine tuples from 2 relations into single
“longer” tuples, but only those that satisfy matching condition .
Derivation: R ⋈<𝑗𝑜𝑖𝑛 𝑐𝑜𝑛𝑑𝑖𝑡𝑖𝑜𝑛> S = 𝜎<𝑗𝑜𝑖𝑛 𝑐𝑜𝑛𝑑𝑖𝑡𝑖𝑜𝑛> (𝑅 × 𝑆)
R(a1,
a2, a3); S(b1, b2, b3)
R ⋈<𝑗𝑜𝑖𝑛 𝑐𝑜𝑛𝑑𝑖𝑡𝑖𝑜𝑛> S = T (a1, a2, a3, b1, b2, b3)
Ex: Department ⋈𝑀𝑔𝑟_𝐼𝐷=𝐸𝐼𝐷 Employee
2. Join Operation
9
Ex: to retrieve the details of the manager of each department.
Employee EID FName LName DNo
Department DNo DName Mgr_ID
1 Sok Dara 3
1 GIC 4
2 Sam Sambath 2
2 GCA 2
3 Sok Piseth 2
4 Sokhan Nita 1
Dept_Mgr ← Department ⋈𝑀𝑔𝑟_𝐼𝐷=𝐸𝐼𝐷 Employee Temp ← Department × Employee
Dept_Mgr ← σMrg_ID=EID (Temp)
Result of the join operation:
Dept_Mgr DNo DName Mgr_ID EID FName LName DNo
1 GIC 4 4 Sokhan Nita 1
2 GCA 2 2 Sam Sambath 2
Theta Join Operation
10
Condition Join or Theta-join or inner join a is attribute of R
< 𝑗𝑜𝑖𝑛 𝑐𝑜𝑛𝑑𝑖𝑡𝑖𝑜𝑛 > : 𝑎𝜃𝑏 b is attribute of S
Syntax: R ⋈𝑎𝜃𝑏 S 𝜃 ∈ {=, ≠, >, ≥, <, ≤}
Ex:
R A B S C A B C
20 25 50 80 40 35
80 40 35
R ⋈𝐵>𝐶 S
Practice
11
Write the result from the following RA expression
1. 𝑟 ⋈𝐵<𝐷 𝑠
Equi-join Operation
13
If condition involves only the comparison operator “=”, the condition
join is also called Equi-Join.
Employee EID FName LName DNo
Department DNo DName Mgr_ID 1 Sok Dara 3
1 GIC 4 2 Sam Sambath 2
2 GCA 2 3 Sok Piseth 2
4 Sokhan Nita 1
Dept_Mgr ← Department ⋈𝑀𝑔𝑟.𝐼𝐷=𝐸𝐼𝐷 Employee
Dept_Mgr DNo DName Mgr_ID EID FName LName DNo
1 GIC 4 4 Sokhan Nita 1
2 GCA 2 2 Sam Sambath 2
Practice
14
Write the result from the following RA expression
2. 𝑟 ⋈𝐶=𝑆𝐶 𝜌𝑆 𝑆𝐶,𝐷 s
Natural join
16
Can be performed only if there is a common R A B C S C D
attribute in between the Relation. 80 40 101 101 P1
Syntax: R ⋈ S or R∗S 30 45 101 102 P2
No join condition. 89 50 102 103 P3
Equi-join on attributes having identical names followed
by protection to remove duplicate attributes.
R⋈S
Given the relations R(A, B, C, D) and S(B, D, E)
A B C D
1. National join can be applied if R ∩ 𝑆 ≠ ∅
80 40 101 P1
2. The result schema is (A, B, C , D, E)
30 45 101 P1
3. And the result of r ⋈ s is defined as:
89 50 102 P2
r ⋈ s = 𝜋𝑟.𝐴, 𝑟.𝐵, 𝑟.𝐶, 𝑟.𝐷, 𝑠.𝐸 𝜎𝑟.𝐵=𝑠.𝐵 ∧ 𝑟.𝐷=𝑠.𝐷 𝑟 × 𝑠
Natural join
17
Ex1: to retrieve the details of the department of each project.
PROJECT PID PName DNum DEPARTMENT DNum DName Mgr_ID
101 ProjectX 1 1 GIC 4
102 ProjectY 2 2 GCA 2
103 ProjectZ 2
Proj_Dept ← PROJECT ⋈ DEPARTMENT
Proj_Dept
PID PName DNum DName Mgr_ID
101 ProjectX 1 GIC 4
Result of the Natural join:
102 ProjectY 2 GCA 2
103 ProjectZ 2 GCA 2
Natural join
18
Ex2: to retrieve the details of the department of each project.
PROJECT PID PName DNum DEPARTMENT DNo DName Mgr_ID
101 ProjectX 1 1 GIC 4
102 ProjectY 2 2 GCA 2
103 ProjectZ 2
Proj_Dept ← PROJECT ⋈ 𝜌 𝐷𝑁𝑢𝑚, 𝐷𝑁𝑎𝑚𝑒, 𝑀𝑔𝑟_𝐼𝐷 (DEPARTMENT)
DEPT ← 𝜌 𝐷𝑁𝑢𝑚, 𝐷𝑁𝑎𝑚𝑒, 𝑀𝑔𝑟_𝐼𝐷 (DEPARTMENT)
Proj_Dept ← PROJECT ⋈ DEPT
Natural join
19
Ex2: to retrieve the details of the department of each project.
PROJECT PID PName DNum DEPARTMENT DNo DName Mgr_ID
101 ProjectX 1 1 GIC 4
102 ProjectY 2 2 GCA 2
103 ProjectZ 2
Proj_Dept ← PROJECT ⋈ 𝜌 𝐷𝑁𝑢𝑚, 𝐷𝑁𝑎𝑚𝑒, 𝑀𝑔𝑟_𝐼𝐷 (DEPARTMENT)
Proj_Dept
PID PName DNum DName Mgr_ID
101 ProjectX 1 GIC 4
Result of the Natural join:
102 ProjectY 2 GCA 2
103 ProjectZ 2 GCA 2
Natural join
20
Ex3: to retrieve the details of the department of the projectY.
PROJECT PID PName DNum DEPARTMENT DNum DName Mgr_ID
101 ProjectX 1 1 GIC 4
102 ProjectY 2 2 GCA 2
103 ProjectZ 2
Proj_Dept ← 𝜎𝑃𝑁𝑎𝑚𝑒="𝑃𝑟𝑜𝑗𝑒𝑐𝑡𝑌" (PROJECT) ⋈ DEPARTMENT
Proj_Dept
Result of the Natural join: PID PName DNum DName Mgr_ID
102 ProjectY 2 GCA 2
Practice
21
Write the result from the following RA expression
3. 𝑟 ⋈ 𝑠
Practice: Write RA Expression
23
1. List all students’ name and the name of the course they enroll in.
Course Student
CID Cname StudentID Sname
C1 Math 1 Chea Nary
C2 Physic 2 Sok Polin
3 Yi Sophea
StudentCourse
#StudentID #CID
1 C1
1 C2
2 C2
2 C1
3 C2
Practice: Write RA Expression
Who has taken a course taught by Anderson? Find their name, course
number, semester and year.
3. Division
28
Syntax: 𝑅 ÷ 𝑆
Precondition: attributes in S must be subset of attributes in R, 𝑆 ⊆ 𝑅 .
Let 𝑟, 𝑠 be relations on schemas R and S, respectively where
R( A1, … Am , B1 , … Bn)
S( B1 , … Bn)
The result of 𝑟 ÷ 𝑠 is a relation on schema R – S = (A1, … Am)
Suited for queries that includes the phrase “for all”.
The result of the division operator 𝑟 ÷ 𝑠 consists of the set of tuples
from 𝑟 defined over the attributes R-S that match the combination of
every tuples in 𝑠 .
3. Division
29
Syntax: 𝑅 ÷ 𝑆 or 𝑅 ∕ 𝑆
Suited for queries that includes the phrase “for all”.
The result of the division operator 𝑟 ÷ 𝑠 consists of the set of tuples
from 𝑟 defined over the attributes R-S that match the combination of
every tuples in 𝑠 .
Precondition: attributes in S must be subset of attributes in R, 𝑆 ⊆ 𝑅 .
Let 𝑟, 𝑠 be relations on schemas R and S, respectively where
R( A1, … Am , B1 , … Bn);
S( B1 , … Bn)
The result of 𝑟 ÷ 𝑠 is a relation on schema R – S = (A1, … Am)
3. Division
30
Ex1:
3. Division
31
Division: 𝑅÷𝑆
= 𝜋𝑦 𝑅 − 𝜋𝑦 ((𝜋𝑦 (𝑅) × 𝑆) − 𝑅)
Where R(x, y) and S(y), y are attributes in 𝑅 and not is 𝑆.
T1 ⟵ 𝜋𝑦 R
T2 ⟵ 𝜋𝑦 ( T1 × S − R)
Result ⟵ T1 − T2
3. Division
32
Ex2: To retrieve the Employee ID (EID) of the employees working on all
projects.
EMPLOYEE EID PID PROJECT PID
Result EID
1001 1 1 1002
1002 1 2
1002 2
1003 2
Sol: Result ⟵ EMPLOYEE ÷ PROJECT
Or Result ⟵
πEID EMPLOYEE − πEID ((πEID (EMPLOYEE) × PROJECT) − EMPLOYEE)
3. Division
33
Ex2: To retrieve the Employee ID (EID) of the employees working on all
projects. 𝑦 T1 × S
EMPLOYEE EID PID PROJECT PID
T1 EID EID PID
R 1001 1 S 1 1001 1001 1
1002 1 2 1002 1001 2
1002 2 1003 1002 1
1003 2 (T1 × S ) − R T2 1002 2
EID 1003 1
EID PID
T1 ⟵ 𝜋𝑦 R 1003 2
1001 2 1001
T2 ⟵ 𝜋𝑦 ( T1 × S − R) 1003 1 1003 Result EID
1002
Result ⟵ T1 − T2
3. Division
34
Ex3: which students take all the courses ?
StudentCourse Course
#StudentID #CID CID Cname
1 C1 C1 Math
1 C2 C2 Physic
2 C2
2 C1
3 C2
StudentID
2
3. Division
35
Ex3: which students take all the courses ?
StudentCourse Course
#StudentID #CID CID Cname StudentID CID
1 C1
1 C1 C1 Math
1 C2
1 C2 C2 Physic
2 C1
2 C2
2 C2
2 C1
3 C1
3 C2
3 C2
𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝐶𝑜𝑢𝑟𝑠𝑒 ÷ 𝜋𝐶𝐼𝐷 𝐶𝑜𝑢𝑟𝑠𝑒
StudentID = 𝜋𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝐼𝐷 𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝐶𝑜𝑢𝑟𝑠𝑒 − 𝜋𝑠𝑡𝑢𝑑𝑒𝑛𝑡𝐼𝐷 (
1 𝜋𝑠𝑡𝑢𝑑𝑒𝑛𝑡𝐼𝐷 𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝐶𝑜𝑢𝑟𝑠𝑒 × 𝜋𝐶𝐼𝐷 𝐶𝑜𝑢𝑟𝑠𝑒 − 𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝐶𝑜𝑢𝑟𝑠𝑒
2 )
3. Division
36
Practice: which employees work on all the critical projects?
Reference
38
R. Ramakrishnan et J. Gehrke Database Management Systems. 2003
(troisième édition)
Jean-Marc Petit(2011). Fondamentaux de la modélisation des
données. Département Informatique-INSA de Lyon
