Chapter 5: Relational Algebra and Relational Calculus

1
Chapter 5. Relational Algebra
5.1. The Relational Algebra
5.2. Unary Operations
5.3. Set Operations
5.4. Binary Relational Operations
5.5. Additional Relational Operations

2
The Relational Algebra and Relational Calculus

• A data model must include a set of operations to manipulate the database, in addition to the
data model's concepts for defining database structure and constraints.

• The basic set of operations for the relational model is the relational algebra.

• These operations enable a user to specify basic retrieval requests.

• The result of retrieval is a new relation, which may have been formed from one or more
relations.

3
The Relational Algebra cont’d

• The algebra operations thus produce new relations, which can be further manipulated
using operations of the same algebra.

• A sequence of relational algebra operations forms a relational algebra expression, whose

result will also be a relation that represents the result of a database query (or retrieval
request).

4
• Two mathematical Query Languages form the basis for Relational languages

• Relational Algebra

• Relational Calculus

• Understanding Algebra is key to understanding SQL, query processing!

5
Relational Algebra

• Relational algebra is a theoretical language with operations that work on one or more
relations to define another relation without changing the original relation.

• The output from one operation can become the input to another operation (nesting is
possible)

6
7
• There are Six basic operations

• Selection (  ) Selects a subset of rows from relation.

• Projection (  ) Deletes unwanted columns from relation.

• Cross-product ( x ) Allows us to combine two relations.

• Set-difference ( - ) Tuples in relation 1, but not in relation 2.

• Union ( U ) Tuples in relation1 or in relation 2.

• Rename(ρ)- used to rename relation or attribute or both.

• Additional operations: Intersection, join, division Not essential, but (very!) useful.

• Using these we can build up sophisticated database queries.

8
Basic operations

Unary Operations

1. Selection Operation

2. Project Operation

3. Rename (ρ-rho)

9
The SELECT Operation
• The SELECT operation is used to select a subset of the tuples from a relation that satisfy a
selection condition.

• One can consider the SELECT operation to be a filter that keeps only those tuples that satisfy
a qualifying condition.

• No duplicates in result!

• Schema of result identical to schema of (only) input relation.

• Result relation can be the input for another relational algebra operation! (Operator
composition.)

10
The SELECT Operation
• The format of SELECT operation is:
• σ (Selection condition/or predicate)(R)

• Where the symbol σ (sigma) is used to denote the SELECT operator and the selection condition is a
Boolean expression specified on the attributes of relation R.

• Notice that R is generally a relational algebra expression whose result is a relation-the simplest such
expression is just the name of a database relation.

• The select operation works on one relation

• The relation resulting from the SELECT operation has the same attributes as R.
Selection condition
<attribute name> <comparison op> <constant value>,
or
<attribute name> <comparison op> <attribute name> 11
The SELECT Operation (Cont’d)

• where <attribute name> is the name of an attribute of R,

• <comparison op> is normally one of the operators {=, <, >=, >,>=, #}, and <constant
value> is a constant value from the attribute domain.

• Clauses can be arbitrarily connected by the Boolean operators AND, OR, and NOT to
form a general selection condition.

• The SELECT operator is unary; that is, it is applied to a single relation. Moreover, the
selection operation is applied to each tuple individually; hence, selection conditions cannot
involve more than one tuple.

12
The SELECT Operation (Cont’d)

13
 Example: Consider the following relation

Specify the following queries on the Company database schema, using the relational operators. Also show the
result of each query.

1. Select tuples for all employees who work in department 4

Solution:
σ DNO=4(Employee)
14
2. List all employees with a salary greater than $10000.

Solution:

σ ( SALARY > 25,000) (Employee)

More complex predicate can be generated using the logical operators Ʌ (AND) ,
V (OR) and ~ (NOT)

15
2. Select the tuples for all employees who either work in department 4 and make over $25,000
per year, or work in department 5 and make over $30,000,
Solution
σ ((DNO=4 AND SALARY > 25,000) OR (DNO=5 AND SALARY > 30,000))(Employee)

• Notice that the SELECT operation is commutative; that is,

• σ <cond 1>((σ <cond2>(R)) = (σ <cond 2> ( σ <cond 1>(R))

• Hence, a sequence of SELECTs can be applied in any order. In addition, we can always
combine a cascade of SELECT operations into a single SELECT operation with a
conjunctive (AND) condition; that is:
σ <cond 1>( σ <cond2>(...(σ <condn>(R)) = (σ <cond l > AND <cond2> AND. . AND
<condn>(R)
16
The PROJECT Operation
• The PROJECT operation selects certain columns from the table and discards the other
columns.

• If we are interested in only certain attributes of a relation, we use the PROJECT

operation to project the relation over these attributes only.

• The general form of the PROJECT operation is

  <attribute list> (R)

• Where

 (pi) is the symbol used to represent the PROJECT operation, and <attribute list> is
the desired list of attributes from the attributes of relation R.

17
The PROJECT Operation (Cont’d)

18
The PROJECT Operation (Cont’d)
• The result of the PROJECT operation has only the attributes specified in <attribute list>
in the same order as they appear in the list.

• Hence, its degree is equal to the number of attributes in <attribute list>.

• If the attribute list includes only non-key attributes of R, duplicate tuples are likely to
occur. The PROJECT operation removes any duplicate tuples, so the result of the
PROJECT operation is a set of tuples, and hence a valid relation. This is known as
duplicate elimination.

• The number of tuples in a relation resulting from a PROJECT operation is always less
than or equal to the number of tuples in R

• Commutatively does not hold on PROJECT

19
Example: Consider the Customers table shown below.
Customers
CustomerID CustomerName Status
1 Google Active
2 Amazon Active
3 Apple Inactive
4 Alibaba Active
Output
1. Retrieve CustomerName and
Status CustomerName Status
Google Active
Solution
Amazon Active
Π CustomerName, Status (Customers) Apple Inactiv
e
Alibaba Active 20
Exercise: Using the staff table shown below, retrieve the salary,staffNo,Fname of each staff.

21
Rename (ρ-rho)
• Rename is a unary operation
• The rename operator ρ (rho) can be used to rename relation or attribute or both.

The format is:

ρ S(B1, B2.... Bn) (R), this renames the relation R to S and the attributes of R to
B1, B2,…Bn
or
ρ S(R) , The renames the Relation R to S
or
ρ (B1,B2 ...,Bn)(R), This renames the attributes of R to B1,B2,..Bn)

22
• Alternative to the rename operator is to use arrow:
A B this renames B to A
Example: Retrieve the first name, last name, and salary of all employees who work in
department number 5.


Solution:
FNAME, LNAME, SEX σDNO= 5 (Employee)
The result of this operation has no relation name.

• Alternatively, we can do the operation as sequence of operations by holding the intermediate

results on new relations with names as follows:

Temp σDNO= 5 (Employee) , Here Temp is relation name

Result FNAME, LNAME, SEX (Temp), Here result is relation name
We can also rename attribute names on the result relation as follows:

Result (FIRSTNAME, LASTNAME, SEX) FNAME, LNAME, SEX (Temp),

23
Set Operations

a. Union
b. Intersection
c. Set-Difference

24
Definition: Two relations R(A1, A2, ... , An) and S(B 1, B2, ... , Bn) are said to be union
compatible if they have the same degree n and if dom(Ai) = dom(Bi) for 1 <=i<= n.

This means that the two relations have the same number of attributes, and each
corresponding pair of attributes has the same domain.

• The three operations union, intersection, and set difference are defined on two union-
compatible relations R and S as follows:

25
Union Operation

• The union of two relations R and S, denoted by R U S, is a relation that includes all
tuples that are either in R or in S or in both R and S. Duplicate tuples are eliminated.
R and S must be union-compatible.

• In some cases, the Projection operation may be used to make two relations union
compatible.

26
Example: Union Operation

sid sname rating age sid sname rating age

R S 28 yuppy 9 35.0
22 dustin 7 45.0
31 lubber 8 55.5
31 lubber 8 55.5 44 guppy 5 35.0
58 rusty 10 35.0 58 rusty 10 35.0

Ru S
sid sname rating age
22 dustin 7 45.0
31 lubber 8 55.5
58 rusty 10 35.0
44 guppy 5 35.0
28 yuppy 9 35.0 27
Intersection Operation
• The intersection result of this operation, denoted by R n S, is a relation that includes all
tuples that are in both Rand S.
.
R S

sid sname rating age sid sname rating age

22 dustin 7 45.0 28 yuppy 9 35.0
31 lubber 8 55.5
31 lubber 8 55.5
44 guppy 5 35.0
58 rusty 10 35.0
58 rusty 10 35.0
RnS
sid sname rating age
31 lubber 8 55.5
58 rusty 10 35.0 28
Set difference Operation (or MINUS):

• The result of this operation, denoted by R - S, is a relation that includes all tuples that
are in R but not in S. R and S must be union compatible.

• We will adopt the convention that the resulting relation has the same attribute names
as the first relation R. It is always possible to rename the attributes in the result using
the rename operator.

29
Example: Set difference Operation

sid sname rating age sid sname rating age

R S 28 yuppy 9 35.0
22 dustin 7 45.0
31 lubber 8 55.5
31 lubber 8 55.5 44 guppy 5 35.0
58 rusty 10 35.0 58 rusty 10 35.0

R-S
sid sname rating age
22 dustin 7 45.0

30
The Cartesian Product (Or Cross Product) Operation
• The Cartesian product of two relations R and S , denoted by RxS, defines a relation
that is the concatenation of every tuple of relation R with every tuple of relation S.

• That is, each row of R is paired with each row of S.

• In general, the result of R(A 1 , A2, ... , An) X S(B1, B2, ... , Bm) is a relation Q with
degree n + m attributes Q(A1 , A2 ... , An ,B1 , B2, ... , Bm), in that order.

• The resulting relation Q has one tuple for each combination of tuples-one from R
and one from S.

• Hence, if R has n tuples and S has m tuples, then Rx S will have n*m tuples.

31
Example: Cross Product

Relation 1: Students Relation 2: Courses

StudentID Name CourseID CourseName

1 Alice 101 Math

2 Bob 102 Physics

103 Chemistry

Resulting Relation: Students × Courses

StudentID Name CourseID CourseName
1 Alice 101 Math
1 Alice 102 Physics
1 Alice 103 Chemistry
2 Bob 101 Math
2 Bob 102 Physic
2 Bob 102 Physic 32
Derived Operators

• Derived operators are built using basic operators and include operations like join,
intersection, and division.

• These operators help perform more complex queries by combining basic

operations to meet specific data retrieval needs

33
Derived Operators

Join Operations

• A join is a binary operation that combines tuples from two relations (tables) based
on a specified condition, producing a new relation.

• Join allows data from multiple tables to be combined

• The Join operation is denoted by ⋈

• Join operation is essentially a Cartesian product followed by a selection criterion.

• Join operation also allows joining variously related tuples from different relations.

34
Types of JOIN:

Various forms of join operation are:

[Link] Joins:
a. Theta join or Conditional Join
b. EQUI join
c. Natural join

2. Outer join:
a. Left Outer Join
b. Right Outer Join
c. Full Outer Join

35
Inner Join:

• Combines two or more tables based on related columns and returns only rows that have
matching values among tables.

• In an inner join, only those tuples that satisfy the matching criteria are included, while
the rest are excluded

36
Various types of Inner Joins:
a. Theta join or Conditional Join

b. Equi join

c. Natural join

37
a. Theta Join or Conditional Join:
• The general case of JOIN operation is called a Theta join. It is denoted by symbol:

A ⋈θ B

• Theta join can use any conditions in the selection criteria.

• A general join condition is of the form:

Condition> AND <condition> AND ... AND <condition> ,where each

condition is of the form , Ai θBj , Ai is an attribute of R, Bj is an attribute of S, Ai

and Bj have the same domain, and θ (theta) is one of the comparison operators {=,
<, >, <=,>=, #}
38
A ⋈θ B = σ θ (A x B) where σ is the selection operation and X is the Cartesian

product.

Result: Includes all pairs of tuples from A and B where the condition theta θ is true.

39
 Employee Relation (E):

EmpID Name DeptID

1 Alice 10
2 Bob 20
3 Charlie 30

Department Relation (D):

DeptID DeptName
10 HR
20 IT
40 Sales
40
Example1 : Find employees and their departments where the department ID
matches
(i.e., [Link]=[Link]).

Solution:
E ⋈[Link]=[Link]

Result:

EmpID Name DeptID DeptID DeptName

1 Alice 10 10 HR
2 Bob 20 20 IT
41
For example 2, consider the following two tables.

42
Example 2: Find employees who earn more than $55,000 and are in the
HR department

Solution:

Employees ⨝ ([Link] > 55000 AND [Link] =

[Link] AND [Link] = 'HR‘) Departments

43
b. Equi join (Using an Equality Condition)

• When a theta join uses only equivalence (=) condition, it becomes an Equi join.

• Equi join is a special case of theta (or conditional) join where the condition contains
equalities (=).

Example:
The previous example , E⋈[Link]=[Link] D is an equi-join because the condition is equality. The
result is the same as above.

44
c. Natural Join (⋈)
• Natural join does not use any comparison operator

• We can perform a Natural Join only if there is at least one common attribute that exists between
two relations. In addition, the attributes must have the same name and domain.

• A natural join matches tuples based on all attributes with the same name in both relations, and it
eliminates duplicate columns in the result.

Syntax:

A ⋈ B , The join implicitly uses equality on common attributes (e.g., if both relations have an
attribute named DeptID, it performs [Link]=[Link])

Result: Combines tuples where common attributes are equal and includes each common
attribute only once.
45
Note:
⇒ The natural join of two relations can be obtained by applying a projection operation to
the equi join of two relations. In terms of basic operators:
⇒ Natural Join = Cartesian Product + Selection + Projection

46
 Employee Relation (E):

EmpID Name DeptID

1 Alice 10
2 Bob 20
3 Charlie 30

Department Relation (D):

DeptID DeptName
10 HR
20 IT
40 Sales
47
Example: For the two tables in the previous slide, the result of E ⋈ D is:

EmpID Name DeptID DeptName

1 Alice 10 HR
2 Bob 20 IT

48
2. Outer Joins

• Outer Join contains matching tuples that satisfy the matching condition, along with some or
all tuples that do not satisfy the matching condition.

• It is based on both matched and unmatched tuples.

• It contains all rows from either one or both relations and uses NULL values.

• NULL signifies that the value is unknown or does not exist.

49
2. Outer Joins (Cont’d)

• There are three kinds of outer joins

a. Left outer join (R S)

b. Right outer join (R ⟖ S)

c. Full outer join( R ⟗ S )

50
2. Outer Joins (Cont’d)

a. Left outer join (R S)

• When applying join on two relations R and S, some tuples of R or S do not appear in the
result set if they do not satisfy the join conditions. However:
• In Left outer join, all the tuples from the Left relation are included in the resulting
relation. The tuples of R that do not satisfy the join condition will have values as NULL
for attributes of S.
• In short:
 All records from the left table
 Only matching records from the right table

51
2. Outer Joins (Cont’d)

52
Example:

53
b. Right Outer Join: ( R S )

• All the tuples from the Right relation, S, are included in the resulting relation.

• If there are tuples in S without any matching tuple in R, then the R-attributes of resulting
relation are made NULL.

• All records from the right table

• Only matching records from the left table

54
Example:

CID Course CID Name

100 Database 100 Ravi
102 Electronics 102 Jiya
NULL NULL 104 Raju

55
c. Full Outer Join: ( R S)
• All the tuples from both participating relations are included in the resulting relation.
If there are no matching tuples for both relations, their respective unmatched
attributes are made NULL.

• All records from both tables

56
CID Course CID Name
100 Database 100 Ravi
101 Mechanics NULL NULL
102 Electronics 102 Jiya
NULL NULL 104 Raju
57
Division (÷)
• Division is used to find tuples in one relation that are related to all tuples in another
relation.

Example: We have two tables

• Query is to find students who are
Student_Course (Dividend Table):
Course(Divisor) enrolled in all courses listed in the
SID CID CID Course table. In this case, students must
101 C1 C1 be enrolled in both C1 and C2.
101 C2 C2
Student_Course(Student_ID, Course_ID)÷ Course(Course_ID)
102 C1
SID
103 C1 Output Table:
101
103 C2
103 58
Exercise: Use the schema given below to answer which follow

59
Queries

1. Find the names of employees who work on all the projects controlled by department
number 5.

2. Retrieve the name and address of all employees who work for the 'Research'
department.

3. For every project located in 'Stafford', list the project number, the controlling
department number, and the department manager's last name, address, and birth date.

60
Retrieve the names of employees who have no dependents.


This is an example of the type of query that uses the MINUS (SET DIFFERENCE) operation.


ALL_EMPS  SSN (EMPLOYEE)

EMPS_WITH_DEPS (SSN)  ESSN (DEPENDENT)

EMPS_WITHOUT_DEPS  (ALL_EMPS - EMPS_WITH_DEPS)
RESULT LNAME, FNAME (EMPS_WITHOUT_DEPS * EMPLOYEE)

61