Abdallah EL Asmar

 Relational algebra is a Procedural Query Language that provides a Theoretical Foundation

for relational database.
▪ This language permits to query data stored in a relational database, using operators
that allow to retrieve data from one or more relations according to specific conditions.
▪ Query Language : Indicate What to do? What data is expected?
▪ Procedural Language : Instruct How to do? How to retrieve the expecting data?
 Relational algebra operations
▪ Work on one or more relations to define another relation without changing the
original relations.

One or Resulting
more Operation relation
relations

Abdallah EL Asmar 2
 Relational algebra operations
▪ Both operands and results are relations, so output from one operation can become
input to another operation.
One or Resulting
more Operation relation
relations
And other
Resulting Operation relations
relation

 Relational algebra expression

▪ A sequence of relational algebra operations
▪ It represents an asked question (Query) to a database.

Abdallah EL Asmar 3
 Relation Attributes, Columns
name

Person person_id first_name last_name birth_date Relation schema

1156 Fadi Farid 11,02/1997 Degree (Arity) :
1234 Sami Karam 12/07/2001 Number of columns
Tuples,
2315 Karim Karim 15/08/2002
Rows
1789 Karim Karam 05/09/1998
2472 Rami Ram 04/08/2002

Cardinality :
Number of rows

Abdallah EL Asmar 4
➢ Unary Operations
Operation applied to a single relation
▪ Selection (Restriction)
▪ Projection
▪ Renaming
➢ Binary Operations
Operation applied to two relations
❑ Set Operations ❑ Relational Operations
▪ Union ▪ Join
▪ Intersection • Inner join
▪ Difference • Outer join
▪ Cross Product (Cartesian Product) ▪ Division

Abdallah EL Asmar 5
▪ Unary operation
▪ Notation: σ < selection condition > (R)
where <selection condition>
▪ may have Boolean conditions AND, OR, and NOT
▪ has clauses of the form:
<attribute name> <comparison op> <constant value>
or
<attribute name> <comparison op> <attribute name>
comparison operator : = <> > >= < <=
▪ Applied independently to each individual tuple in operand relation
▪ The result of σ < selection condition>(R) is a relation S, having the same schema as R, with a
subset of the tuples of R that satisfies a selection condition.

Abdallah EL Asmar 6
Person id name Gender age city
10 Karim Man 25 Tyre
30 Fouad Man 33 Saida
20 Samer Man 32 Beirut
50 Leila Woman 33 Beirut
40 Sarah Woman 25 Byblos

S1  σ Age > 30 (Person) S2  σ Age > 3 AND city = ‘Saida’ (Person)

S1 id name Gender age City S2 id name Gender age City
30 Fouad Man 33 Saida 30 Fouad Man 33 Saida
20 Samer Man 32 Beirut
50 Leila Woman 33 Beirut

Abdallah EL Asmar 7
 The Selection operation is commutative ;
σ <condition1> (σ <condition2> (R)) = σ <condition2> (σ <condition1> (R))

 A cascade of Selection operations can be applied in any order;

σ <condition1>(σ <condition2> (σ <condition3> (R))) =
σ <condition2> (σ <condition3> (σ <condition1> (R)))

 A cascade of Selection operations can be replaced by a single Selection with the

conjunction of all conditions;
σ <condition1>(σ <condition2> (σ <condition3> (R))) =
σ <condition1> AND <condition2> AND <condition3> (R)

Abdallah EL Asmar 8
▪ Unary operation
▪ Notation: π < list of columns >(R)
▪ The result of π < list of columns >(R) is a relation S having as schema the list of
mentioned columns.
▪ Projection eliminates duplicate tuples
Person id name Gender age city
S2  π name, age (Person)
10 Karim Man 25 Tyre S2 name age
30 Fouad Man 33 Saida Karim 25
S1  π age (Person) Fouad 33
20 Samer Man 32 Beirut
50 Leila Woman 33 Beirut S1 age Samer 32
40 Sarah Woman 25 Byblos 25 Leila 33
33 Sarah 25
32

Abdallah EL Asmar 9
 In projection, a column can be the result of an expression relating existing columns.
Employee id name basic_salary bonus
10 Karim 1000 100
30 Fouad 1100 150
20 Samer 900 80
50 Leila 1200 180
40 Sarah 1100 140

R name basic_salary + bonus

Karim 1100
R  π name, (basic_salary + bonus) (Employee) Fouad 1250
Samer 980
Leila 1380
Sarah 1240

Abdallah EL Asmar 10
 The cardinality (number of tuples) the projection result π <list> (R) is always less
than or equal to the cardinality of R.
 If the list of attributes includes a key of R, then the result cardinality is equal to the
cardinality of R.
 π <list1> (π <list2> (R)) = π <list1> (R)
as long as <list2> includes the attributes of<list1>

Abdallah EL Asmar 11
▪ Unary operation
▪ The Renaming operator is ρ
▪ Allows to rename relations and attributes, it can be expressed by one of the
following forms:
o ρ S (B1, B2, …, Bn) (R) is a relation renamed S based on R with column names B1,
B2, …...BN.
o ρ S (R) is a relation renamed S based on R ; (S has the column names as R).
o ρ (B1, B2, …, Bn) (R) is a relation which does not specify a name, with column names
B1, B2, …...BN.
R  π name, (basic_salary + bonus) (Employee)

Result  π EmployeeName, Salary (R)

Abdallah EL Asmar 12
▪ A relational algebra query is a series of operations applied to the database
relations.
▪ If we want to apply several relational algebra operations one after another:
o we can write the operations as a single relational algebra expression by
nesting the operations
Or
o we can apply one operation at a time and create intermediate result
relations. In this case, we must give names to these relations.

Abdallah EL Asmar 13
 Example
Employee (id, first-name, last-name, salary, depNb)
 To find first name, last name and salary of all employees of the department number
5, we must apply a RESTRICTION and a PROJECTION.
◦ We can write a single relational algebra expression as follows:
π last-name, first-name, salary(σDepNb = 5 (Employee))

◦ OR, we can explicitly show the sequence of operations, by applying a name to

each intermediate relation:
EmpDep5 ← σ DNO = 5(Employee)
Result ← π last-name, first-name, salary(EmpDep5)

Abdallah EL Asmar 14
 Binary operations derived from the theory of sets
 Four operations: Union, Intersection, Difference, Cross Product
 Notation:
◦ Union: R1 U R2
◦ Intersection: R1 ∩ R2
◦ Minus (Difference): R1 – R2
◦ Cross Product : R x S

 R1 and R2 must have the same schema

 R et S can have different schemas

Abdallah EL Asmar 15
 For Union, Intersection and Difference (Minus) Operations:
◦ R1 U R2 R1 ∩ R2 R1 – R2
❖R1 and R2 should have the same schema (same number of columns and same
order of domains); they may have different column names.
❖The results of these operations are relations with the same schema as R1 and
R2 (the results columns take the same names as the first relation R1 columns)

Abdallah EL Asmar 16
 Union : R3  R1 U R2
❖ Merges two relations
❖ R3 tuples are all tuples that belong to R1 or R2.
❖ Duplicated tuples are eliminated.
❖

R1 id name R2 id name
1 Karim 1 Karim
2 Wael 2 Wael
3 Kamil 4 Ahmad

R3 id name
1 Karim
2 Wael
3 Kamil
4 Ahmad
Abdallah EL Asmar 17
 Intersection : R3  R1 ∩ R2
❖ Get a relation that contains the common tuples of R1 and R2 (the tuples that
belong to R1 and R2 at the same time).
❖

R1 id Name R2 id Name
1 Karim 1 Karim
2 Wael 2 Wael
3 Kamil 4 Ahmad

R3 id Name
1 Karim
2 Wael

Abdallah EL Asmar 18
 Union and intersection are commutative operations; then
R1 U R2 = R2 U R1 R1 ∩ R2 = R2 ∩ R1
 The intersection and union can be treated as n-ary operations applicable to any
number of relations because they are associative operations; then
R U (S U T) = (R U S) U T
(R ∩ S) ∩ T = R ∩ (S ∩ T)

Abdallah EL Asmar 19
 Minus : R3 = R1 – R2
❖ Get a relation that contains tuples of R1 that don't belong to R2.
❖

R1 id name R2 id name
1 Karim 1 Karim
2 Wael 2 Wael
3 Kamil 4 Ahmad

R3 id name
3 Kamil
Minus properties
Minus operation is not commutative; then, in general: R - S ≠ S – R

Abdallah EL Asmar 20
 Cross product : Q  R x S
 Allows to concatenate the tuples of R and S
 R and S have different schemas
 The result of R (A1, A2,..., An) x S(B1, B2,..., Bm) is a relation Q with n + m
columns: Q (A1, A2,..., An, B1, B2,..., Bm),
 The Q relation has the tuples that result from the concatenation of each R tuple
with all S tuples..

 Properties of Cross product

 Commutative operation: R x S = S x R
 Associative operation: R x (S x T) = (R x S) x T

Abdallah EL Asmar 21
 Cross product: Q  R * S

R id Name S code City

1 Karim 10 Byblos
2 Wael 20 Tyre
3 Kamil

Q id Name code City

1 Karim 10 Byblos
1 Karim 20 Tyre
2 Wael 10 Byblos
2 Wael 20 Tyre
3 Kamil 10 Byblos
3 Kamil 20 Tyre

Abdallah EL Asmar 22
❖ Join
➢Natural Jointure

❖ Outer Join
➢ Left Outer Join
➢ Right Outer Join
➢ Full Outer Join

❖ Division

Abdallah EL Asmar 23
 Join operation: Q  R S
Condition

 Allows to concatenate the tuples of R and S according to a condition.

 It is a Cross product followed by a selection operation
 The join condition is a logical expression specified on the attributes of R and S. It
has the following form:
[Link] comparison-operator [Link]
Comparison operators : = <> > >= < <=
 This operation is very important for any relational database, as it helps to deal with
relationships.
 Join properties
 Commutative operation

Abdallah EL Asmar 24
 QR S
[Link] > [Link]

R id Price S id cost
1 10 1 9
2 8 2 8
3 11 3 11

Q id1 Price id2 cost

1 10 1 9
1 10 2 8
3 11 1 9
3 11 2 8

Abdallah EL Asmar 25
 The natural join of relations R and S is a join having as a condition an equality of
the common attributes of R and S.
[Link] = [Link]
 The natural join is used to express the referential constraints between relations.
 In general, R and S are linked by the Parent - Child link
[Link] = [Link]
 It uses the same notation of the join operation but without specifying the condition
(implicit condition).

Abdallah EL Asmar 26
 Q  R S

R idG Group S idp Product idG

10 Computer 1 J5 prime 20
20 Phone 2 Note 8 20
30 Tablet 3 HP 10
4 Sony 10
The implicit condition is: [Link] = [Link]

Q idG1 Group idp Product idG2

10 Computer 3 HP 10
10 Computer 4 Sony 10
20 Phone 1 J5 prime 20
20 Phone 2 Note 8 20

Abdallah EL Asmar 27
 The outer join of R and S relations is a join of these relations enriched by tuples not
participating in the join.

 There are three types of outer join:

➢ Left outer join: R S
Condition
Join between R and S + any tuple of R not participating in the join
➢Right outer join: R S
Condition
Join between R and S + any tuple of S not participating in the join
➢ Full outer join: R S
Condition
Join between R and S + any tuple of R and S not participating in the join

Abdallah EL Asmar 28
 R A B S C D
10 5 1 10
20 6 2 20
30 4 3 40
Join condition : R.A = S.D

Left outer join Right outer join Full outer join

A B C D A B C D A B C D
10 5 1 10 10 5 1 10 10 5 1 10
20 6 2 20 20 6 2 20 20 6 2 20
30 4 3 40 30 4
3 40

Abdallah EL Asmar 29
 Division operation : T  R ÷ S
 The schema of S must be a sub-schema of R
R (A1, A2, ….Ap, Ap+1, ….An) ; S (A1, A2, ….Ap)
 The schema of T is the sub-schema of R which groups together all the columns of
R which do not belong to the schema of S
T (Ap+1, ….An) ;
 For a tuple t will appear in the T result of DIVISION, the values of t must appear in
R in combination with each tuple of S.

Abdallah EL Asmar 30
 TR÷S
R Sid Sname Cid Cname S Cid Cname
1 Jad 10 Java 10 Java
2 Sami 10 Java 20 C++
3 Fadi 20 C++ 30 PHP
1 Jad 20 C++
2 Sami 20 C++
1 Jad 30 PHP

T Sid Sname
1 Jad

Abdallah EL Asmar 31
 Basic Operations
Restriction (σ), Projection (Π), union U, Difference (-), Cross Product (x)
 Derivative Operations
Intersection, Join, and Division
 The set of basic operations is called the Complete Set of Relational Operations.
 Any expression of relational algebra can be expressed by a combination of the
Complete set.
➢For example:
R ∩ S = R − (R − S) = S − (S − R)
R S = σ < join condition > (R x S)
Condition

Abdallah EL Asmar 32