Database Systems and

Concepts
L06

Chapter 6
The Relational Algebra and
Relational Calculus
 Topics to be covered
 Outline
 Introduction to Databases
 Data Modeling Using ER-Mod
 Constraints
 Relational Algebra & Relational Calculus
 Structured Query Language
 Optimization
 Concurrency Control and Recovery
 Object & Object-Relational Databases
 Database Security, Adv. Modeling & Distribution
2
 Outline
 Languages for dBs
 Relational Algebra
– RA Operations From Set Theory
• Union, Intersection, Difference
• Divide (Read)
– Other Relational Operators
• Select, Project,
• Join (Read)
 Examples (COMPANY)
3
 Languages for dBs
 DDL: Data Definition Language
– Describes operations on the DB structure (DB
schema).
• table creation, modification, deletion, …
• definition of attribute domains, primary keys, integrity
constraints, (either intra-relational or inter-relational).
– Mainly used by DB designers during the database
implementation.
 DML: Data Manipulation Language
– Describes operations on the data stored in the DB
(DB Instance)
– The Operations here include:
• Update (changes content of dB without changing the schema)
• Query (i.e. a fxn, that given the dB, produces a relation.)

4
 Query Languages for Relational Databases
 Foundations of DB languages can be studied with
reference to query languages.
 There are two different kinds of query languages:
– Procedural Languages:
• One describes the procedure that may be followed to obtain
the results (“how”)
• Relational Algebra
– Declarative Languages
• Describe the properties of the result, rather than the procedure
used to obtain it (“what”).
• Relational Calculus (theoretical)
• Structured Query Language – SQL (real but only partially
declarative).
• Query by Example – QBE (real). 5
 Relational Algebra
 A collection of operators that:
– are defined on relations
– produce relations as results
– can be combined to form complex expressions.
 Operators
– traditional set theory: union, intersection, difference;
– more specific operators:
renaming, selection, projection
– The most important: join
• Natural join
• Cartesian product
• Theta-join
6
 Union, Intersection & Difference
 Relations are sets, so we can apply set
operators;
 However, we want the results to be
relations (homogeneous sets of tuples).
 Therefore it is meaningful to apply union,
intersection, difference only to pairs of
relations defined over the same attributes.
Note that these do not alter the original
relations, but produce new relations.
7
 Relational Algebra Operations
From Set Theory
 Type Compatibility
– The operand relations:
R1(A1, A2, ..., An) and
R2(B1, B2, ..., Bn)
– must have the same number of attributes, and
the domains of corresponding attributes must be
compatible; that is, dom(Ai)=dom(Bi) for i=1, 2,
..., n.

– The resulting relation for R1R2,R1  R2, or R1-

R2 has the same attribute names as the first
operand relation R1 (by convention).
8
 Union
 The union of two relations R and S is the set of
tuples t such that t R t S, T = R  S.

Graduates
Number Surname Age
7274 Robinson 37
7432 O'Malley 39 Graduates  Managers
9824 Darkes 38 Number Surname Age
7274 Robinson 37
Managers  7432 O'Malley 39
Number Surname Age 9797 O'Malley 56
9797 O'Malley 56 9824 Darkes 38
7432 O'Malley 39
9824 Darkes 38
 Intersection
 The intersection of two relations R and S is the
set of tuples t such that t R t S, T = R  S.

Graduates
Number Surname Age
7274 Robinson 37
7432 O'Malley 39 Graduates  Managers
9824 Darkes 38 Number Surname Age
7432 O'Malley 39
Managers  9824 Darkes 38
Number Surname Age
9797 O'Malley 56
7432 O'Malley 39
9824 Darkes 38
 Difference
 The difference of two relations R and S is the set
of tuples t such that t R t  S, i.e. T = R – S.

Graduates
Number Surname Age
7274 Robinson 37
7432 O'Malley 39 Graduates – Managers
9824 Darkes 38 Number Surname Age
7274 Robinson 37
Managers –
Number Surname Age
9797 O'Malley 56
7432 O'Malley 39
9824 Darkes 38
 Properties of Operators
 Commutative Property
RS=SR
RS=SR
 Associative Property
R  (S  T) = (R  S)  T
R  (S  T) = (R  S)  T
 Set Difference is not Commutative
R–SS–R

12
A meaningful but impossible Union

 The problem: Father and Mother are different

names, but both represent a “Parent”.
 The solution: rename attributes!
13
 Renaming
 This is a unary operator which changes
attribute names for a relation without
changing any values.
 Notation: ρOldName→NewName(r)
Example, ρFather→Parent(Paternity)
 If there are two or more attributes involved in
a renaming operation, then ordering is
meaningful:
e.g., ρBranch, Salary → Location, Pay(Employees)
14
Example of Renaming

15
Renaming and Union
Renaming and Union with more attributes
Unary Relational Operations (cont.)
 Rename Operation (cont.)
 The rename operator is 
The general Rename operation can be expressed by any
of the following forms:
 S (B1, B2, …, Bn ) (R) is a renamed relationS based on R with
column names B1, B1, …..Bn
 S ( R) is a renamed relationS based on R (which does
not specify column names).

 (B1, B2, …, Bn ) (R) is a renamed relationwith column names

B1, B1, …..Bn which does not specify a new relation name.

18
 Select, Project, and Join
 Now let us turn to the other three
Relational Algebra Operators
– Select
– Project, and
– Join
 Note that Select & Project are
Unary operators.
19
 Select
 Select operation works on a single relation R
and defines a relation that contains only those
tuples (rows) of R that satisfy the specified
condition (predicate).

 Select is used for horizontal “decompositions.” 20

 Select (Cont)
 The SELECT operation is denoted by  (sigma).
– The selection condition acts as a filter
– Keeps only those tuples that satisfy the qualifying
condition
– Tuples satisfying the condition are selected whereas the
other tuples are discarded (filtered out)

– Select the employee tuples whose salary is greater than

$30,000:
 SALARY > 30,000 (EMPLOYEE)

21
 Examples
1. Select the EMPLOYEE tuples whose department
number is 4:  DNO = 4 (EMPLOYEE)
 Examples
1. Select the EMPLOYEE tuples whose department
number is 4:  DNO = 4 (EMPLOYEE)
 Examples
1. Select the EMPLOYEE tuples whose department
number is 4:  DNO = 4 (EMPLOYEE)
 Examples
2. Select the employee tuples whose salary is greater
than $40,000:  SALARY  40,000 (EMPLOYEE)
 SELECT Operation Properties
 The SELECT operation  <selection condition>(R)
produces a relation S that has the same schema
(same attributes) as R
 SELECT  is commutative:
 <condition1>( < condition2> (R)) =
 <condition2> ( < condition1> (R))
 Because of commutativity property, a cascade
(sequence) of SELECT operations may be
applied in any order:
<cond1>(<cond2> (<cond3> (R)) =
<cond2> (<cond3> (<cond1> ( R))) 26
 SELECT Operation Properties
 A cascade of SELECT operations may be
replaced by a single selection with a
conjunction of all the conditions:

<cond1>(< cond2> (<cond3>(R)) =

 <cond1> AND < cond2> AND < cond3>(R)))
 The number of tuples in the result of a
SELECT is less than (or equal to) the
number of tuples in the input relation R
27
 Example 3
 (DNo = 4 AND Salary >25000) OR (DNo = 5 AND Salary >30000)
 Project
 Project (π) operation
works on a single relation
R and defines a relation
that contains a vertical
subset of R, extracting the
values of specified
attributes and eliminating
duplicates.

 Project is used for Vertical

“decompositions.”
29
 Examples
 Example: To list each employee’s first and last
name and salary, thefollowing is used:
πLNAME, FNAME,SALARY (EMPLOYEE)
 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.
 The project operation removes any duplicate tuples,
so the result of the project operation is a set of
tuples and hence a valid relation.
30
 Example 4
π (LName, FName, Salary)EMPLOYEE
 Example 4
π (LName, FName, Salary)EMPLOYEE
Projection, Another Example
PROJECT Operation Properties
 The number of tuples in the result of
projection π <list> (R) is always less or
equal to the number of tuples in R.
– If the list of attributes includes a key of
R, then the number of tuples is equal to
the number of tuples in R.
– π <list1> (π <list2> (R) ) = π <list1> (R) as long
as <list2> contains the attributes in <list1>

34
 Class Exercise
 Use Relational Algebra to specify the
following queries on the COMPANY
dB:
– Retrieve the SSNs of all employees who
work more than 10 hrs/wk on ProductX.
– Find the names of all employees who are
directly supervised by ‘Franklin Wong.’
– Find the names of all employees who earn
either 25k or 45k.

36
 Database State for COMPANY
All examples discussed below refer to the COMPANY database shown here.

39