CHAPTER 6
Relational Algebra and Relational Calculus
From Chapter 5 of Connolly & Begg 6Ed
© Pearson Education Limited 1995, 2005
2
Chapter 6 - Objectives
• Meaning of the term relational completeness.
• How to form queries in relational algebra.
• How to form queries in tuple relational calculus.
• How to form queries in domain relational calculus.
• Categories of relational DML.
© Pearson Education Limited 1995, 2005
3
Introduction
click below
click relational algebra
relational calculus
• Relational algebra and relational calculus are formal
languages associated with the relational model.
• Informally, relational algebra is a (high-level)
procedural language and relational calculus is a non-
procedural language.
• However, formally both are equivalent to one another.
• A language that produces a relation that can be derived
using relational calculus is relationally complete.
© Pearson Education Limited 1995, 2005
4
Relational Algebra
• Relational algebra operations work on one or more
relations to define another relation without changing the
original relations.
• Both operands and results are relations, so output from
one operation can become input to another operation.
• Allows expressions to be nested, just as in arithmetic.
This property is called closure.
© Pearson Education Limited 1995, 2005
5
Relational Algebra
• Five basic operations in relational algebra: Selection,
Projection, Cartesian product, Union, and Set
Difference.
• These perform most of the data retrieval operations
needed.
• Also have Join, Intersection, and Division operations,
which can be expressed in terms of 5 basic operations.
© Pearson Education Limited 1995, 2005
6
Relational Algebra Operations
select + where select column
© Pearson Education Limited 1995, 2005
7
Relational Algebra Operations
© Pearson Education Limited 1995, 2005
8
Selection (or Restriction)
• spredicate (R)
• Works on a single relation R and defines a relation that
contains only those tuples (rows) of R that satisfy the specified
condition (predicate).
© Pearson Education Limited 1995, 2005
9
Example - Selection (or Restriction)
• List all staff with a salary greater than £10,000.
ssalary > 10000 (Staff) SELECT *
FROM Staff
WHERE salary>10000 ;
© Pearson Education Limited 1995, 2005
10
Projection
• Pcol1, . . . , coln(R)
• 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.
© Pearson Education Limited 1995, 2005
11
Example - Projection
• Produce a list of salaries for all staff, showing only
staffNo, fName, lName, and salary details.
PstaffNo, fName, lName, salary(Staff) SELECT staffNo, fName, lName, salary
FROM Staff;
© Pearson Education Limited 1995, 2005
12
Union
• RÈS
• Union of two relations R and S defines a relation that contains
all the tuples of R, or S, or both R and S, duplicate tuples being
eliminated.
• R and S must be union-compatible.
• If R and S have I and J tuples, respectively, union is
obtained by concatenating them into one relation with
a maximum of (I + J) tuples.
© Pearson Education Limited 1995, 2005
13
Example - Union
• List all cities where there is either a branch office or a
property for rent.
Pcity(Branch) È Pcity(PropertyForRent)
© Pearson Education Limited 1995, 2005
14
Set Difference
• R–S
• Defines a relation consisting of the tuples that are in relation
R, but not in S.
• R and S must be union-compatible.
© Pearson Education Limited 1995, 2005
15
Example - Set Difference
• List all cities where there is a branch office but no
properties for rent.
Pcity(Branch) – Pcity(PropertyForRent)
© Pearson Education Limited 1995, 2005
16
Intersection
• RÇS
• Defines a relation consisting of the set of all tuples that
are in both R and S.
• R and S must be union-compatible.
• Expressed using basic operations:
R Ç S = R – (R – S)
© Pearson Education Limited 1995, 2005
17
Example - Intersection
• List all cities where there is both a branch office and
at least one property for rent.
Pcity(Branch) Ç Pcity(PropertyForRent)
© Pearson Education Limited 1995, 2005
18
Cartesian product
• RXS
• Defines a relation that is the concatenation of every tuple of
relation R with every tuple of relation S.
© Pearson Education Limited 1995, 2005
19
Example - Cartesian product
• List the names and comments of all clients who have
viewed a property for rent.
(PclientNo, fName, lName(Client)) X (PclientNo, propertyNo,
comment (Viewing))
directly do cartesian product
don't have any condition
© Pearson Education Limited 1995, 2005
20
Example - Cartesian product and
Selection
• Use selection operation to extract those tuples where
[Link] = [Link].
[Link] = [Link]((ÕclientNo, fName, lName(Client)) C
(ÕclientNo, propertyNo, comment(Viewing)))
green = condition
! Cartesian product and Selection can be reduced to a single
operation called a Join.
© Pearson Education Limited 1995, 2005
21
Join Operations
• Join is a derivative of Cartesian product.
• Equivalent to performing a Selection, using join
predicate as selection formula, over Cartesian product
of the two operand relations.
• One of the most difficult operations to implement
efficiently in an RDBMS and one reason why RDBMSs
have intrinsic performance problems.
because when cartesian product large data it will become a very very large data & take a long time
© Pearson Education Limited 1995, 2005
22
Join Operations
• Various forms of join operation
• Theta join
• Equijoin (a particular type of Theta join)
• Natural join
• Outer join
• Semijoin
© Pearson Education Limited 1995, 2005
23
Theta join (q-join)
• R F S F is a condition
• Defines a relation that contains tuples satisfying the
predicate F from the Cartesian product of R and S.
• The predicate F is of the form [Link] q [Link] where q may be
one of the comparison operators (<, £, >, ³, =, ¹).
© Pearson Education Limited 1995, 2005
24
Theta join (q-join)
• Can rewrite Theta join using basic Selection and
Cartesian product operations.
R FS = sF (R C S)
! Degree of a Theta join is sum of degrees of the
operand relations R and S. If predicate F contains
only equality (=), the term Equijoin is used.
© Pearson Education Limited 1995, 2005
25
Example - Equijoin
• List the names and comments of all clients who have
viewed a property for rent.
(PclientNo, fName, lName(Client)) [Link] = [Link] (PclientNo,
propertyNo, comment(Viewing))
© Pearson Education Limited 1995, 2005
26
Natural join
• R S
• An Equijoin of the two relations R and S over all common
attributes x. One occurrence of each common attribute is
eliminated from the result.
© Pearson Education Limited 1995, 2005
27
Example - Natural join
• List the names and comments of all clients who have
viewed a property for rent.
(PclientNo, fName, lName(Client))
(PclientNo, propertyNo, comment(Viewing))
Display only one clientNo
© Pearson Education Limited 1995, 2005
28
Outer join
• To display rows in the result that do not have matching
values in the join column, use Outer join.
• R S
• (Left) outer join is join in which tuples from R that do not
have matching values in common columns of S are also
included in result relation.
© Pearson Education Limited 1995, 2005
29
Example - Left Outer join
• Produce a status report on property viewings.
PpropertyNo, street, city(PropertyForRent) Viewing
© Pearson Education Limited 1995, 2005
30
Semijoin
• R FS
• Defines a relation that contains the tuples of R that participate in
the join of R with S.
! Can rewrite Semijoin using Projection and Join:
R FS = PA(R F S) , A is the set of all
attributes for R
© Pearson Education Limited 1995, 2005
31
Example - Semijoin
• List complete details of all staff who work at the branch in
Glasgow.
Staff [Link]=[Link](scity=‘Glasgow’(Branch))
© Pearson Education Limited 1995, 2005
32
Division
•R ÷ S
• Defines a relation over the attributes C that consists
of set of tuples from R that match combination of
every tuple in S.
• Expressed using basic operations:
T1 ¬ PC(R)
T2 ¬ PC((S X T1) – R)
T ¬ T1 – T2
© Pearson Education Limited 1995, 2005
33
Example - Division
• Identify all clients who have viewed all properties with
three rooms.
(PclientNo, propertyNo(Viewing)) ÷
(PpropertyNo(srooms = 3 (PropertyForRent)))
© Pearson Education Limited 1995, 2005
34
Aggregate Operations
• ÁAL(R)
• Applies aggregate function list, AL, to R to define a relation
over the aggregate list.
• AL contains one or more (<aggregate_function>, <attribute>)
pairs .
• Main aggregate functions are: COUNT, SUM, AVG,
MIN, and MAX.
© Pearson Education Limited 1995, 2005
Example – Aggregate Operations
• How many properties cost more than £350 per
month to rent?
rR(myCount) ÁCOUNT propertyNo (σrent > 350
(PropertyForRent))
r : rename operator
35
© Pearson Education Limited 1995, 2005
36
Grouping Operation
• GAÁAL(R)
• Groups tuples of R by grouping attributes, GA, and then
applies aggregate function list, AL, to define a new relation.
• AL contains one or more (<aggregate_function>, <attribute>)
pairs.
• Resulting relation contains the grouping attributes, GA, along
with results of each of the aggregate functions.
© Pearson Education Limited 1995, 2005
Example – Grouping Operation
• Find the number of staff working in each branch
and the sum of their salaries.
rR(branchNo, myCount, mySum)
branchNo Á COUNT staffNo, SUM salary (Staff)
37
© Pearson Education Limited 1995, 2005
38
Relational Calculus
• Relational calculus query specifies what is to be
retrieved rather than how to retrieve it.
• No description of how to evaluate a query.
• In first-order logic (or predicate calculus), predicate is
a truth-valued function with arguments.
• When we substitute values for the arguments,
function yields an expression, called a proposition,
which can be either true or false.
© Pearson Education Limited 1995, 2005
39
Relational Calculus
• If predicate contains a variable (e.g. ‘x is a member of
staff’), there must be a range for x.
• When we substitute some values of this range for x,
proposition may be true; for other values, it may be
false.
• When applied to databases, relational calculus has
forms: tuple and domain.
© Pearson Education Limited 1995, 2005
40
Tuple Relational Calculus
• Interested in finding tuples for which a predicate is true.
Based on use of tuple variables.
• Tuple variable is a variable that ‘ranges over’ a named
relation: i.e., variable whose only permitted values are
tuples of the relation.
• Specify range of a tuple variable S as the Staff relation as:
Staff(S)
• To find set of all tuples S such that P(S) is true:
{S | P(S)}
© Pearson Education Limited 1995, 2005
41
Tuple Relational Calculus - Example
• To find details of all staff earning more than £10,000:
{S | Staff(S) Ù [Link] > 10000}
• To find a particular attribute, such as salary, write:
{[Link] | Staff(S) Ù [Link] > 10000}
© Pearson Education Limited 1995, 2005
42
Tuple Relational Calculus
• Can use two quantifiers to tell how many instances the
predicate applies to:
• Existential quantifier $ (‘there exists’)
• Universal quantifier " (‘for all’)
• Tuple variables qualified by " or $ are called bound
variables, otherwise called free variables.
© Pearson Education Limited 1995, 2005
43
Tuple Relational Calculus
• Existential quantifier used in formulae that must be true
for at least one instance, such as:
Staff(S) Ù ($B)(Branch(B) Ù
([Link] = [Link]) Ù [Link] = ‘London’)
• Means ‘There exists a Branch tuple with same
branchNo as the branchNo of the current Staff
tuple, S, and is located in London’.
© Pearson Education Limited 1995, 2005
44
Tuple Relational Calculus
• Universal quantifier is used in statements about every
instance, such as:
("B) ([Link] ¹ ‘Paris’)
• Means ‘For all Branch tuples, the address is not in Paris’.
• Can also use ~($B) ([Link] = ‘Paris’) which means ‘There
are no branches with an address in Paris’.
© Pearson Education Limited 1995, 2005
45
Tuple Relational Calculus
• Formulae should be unambiguous and make sense.
• A (well-formed) formula is made out of atoms:
• R(Si), where Si is a tuple variable and R is a relation
• Si.a1 q Sj.a2
• Si.a1 q c
• Can recursively build up formulae from atoms:
• An atom is a formula ^ : and
v : or
• If F1 and F2 are formulae, so are their conjunction, F1 Ù
F2; disjunction, F1 Ú F2; and negation, ~F1
• If F is a formula with free variable X, then ($X)(F) and
("X)(F) are also formulae.
© Pearson Education Limited 1995, 2005
46
Example - Tuple Relational Calculus
• List the names of all managers who earn more than
£25,000. | = that
tuple variable
{[Link], [Link] | Staff(S) Ù
[Link] = ‘Manager’ Ù [Link] > 25000}
• List the staff who manage properties for rent in Glasgow.
{S | Staff(S) Ù ($P) (PropertyForRent(P) Ù ([Link] = [Link]) Ù
[Link] = ‘Glasgow’)}
© Pearson Education Limited 1995, 2005
47
Example - Tuple Relational Calculus
• List the names of staff who currently do not manage any
properties.
{[Link], [Link] | Staff(S) Ù (~($P) (PropertyForRent(P)Ù([Link]
= [Link])))}
Or
{[Link], [Link] | Staff(S) Ù (("P) (~PropertyForRent(P) Ú
~([Link] = [Link])))}
© Pearson Education Limited 1995, 2005
48
Example - Tuple Relational Calculus
• List the names of clients who have viewed a property for
rent in Glasgow.
{[Link], [Link] | Client(C) Ù (($V)($P)
(Viewing(V) Ù PropertyForRent(P) Ù
([Link] = [Link]) Ù
([Link]=[Link]) Ù
[Link] =‘Glasgow’))}
© Pearson Education Limited 1995, 2005
49
Tuple Relational Calculus
• Expressions can generate an infinite set.
For example:
{S | ~Staff(S)}
• To avoid this, add restriction that all values in result must
be values in the domain of the expression.
© Pearson Education Limited 1995, 2005
50
Domain Relational Calculus
• Uses variables that take values from domains instead
of tuples of relations.
• If F(d1, d2, . . . , dn) stands for a formula composed of
atoms and d1, d2, . . . , dn represent domain variables,
then:
{d1, d2, . . . , dn | F(d1, d2, . . . , dn)}
is a general domain relational calculus expression.
© Pearson Education Limited 1995, 2005
51
Example - Domain Relational Calculus
• Find the names of all managers who earn more than
£25,000. Nickname of attribute
sNum
{fN, lN | ($sN, posn, sex, DOB, sal, bN)
(Staff (sN, fN, lN, posn, sex, DOB, sal, bN) Ù
posn = ‘Manager’ Ù sal > 25000)}
© Pearson Education Limited 1995, 2005
52
Example - Domain Relational Calculus
• List the staff who manage properties for rent in
Glasgow.
{sN, fN, lN, posn, sex, DOB, sal, bN |
($sN1,cty)(Staff(sN,fN,lN,posn,sex,DOB,sal,bN) Ù
PropertyForRent(pN, st, cty, pc, typ, rms,
rnt, oN, sN1, bN1) Ù
(sN=sN1) Ù cty=‘Glasgow’)}
© Pearson Education Limited 1995, 2005
53
Example - Domain Relational Calculus
• List the names of staff who currently do not manage
any properties for rent.
{fN, lN | ($sN)
(Staff(sN,fN,lN,posn,sex,DOB,sal,bN) Ù
(~($sN1) (PropertyForRent(pN, st, cty, pc, typ,
rms, rnt, oN, sN1, bN1) Ù (sN=sN1))))}
© Pearson Education Limited 1995, 2005
54
Example - Domain Relational Calculus
• List the names of clients who have viewed a property
for rent in Glasgow.
{fN, lN | ($cN, cN1, pN, pN1, cty)
(Client(cN, fN, lN,tel, pT, mR) Ù
Viewing(cN1, pN1, dt, cmt) Ù
PropertyForRent(pN, st, cty, pc, typ,
rms, rnt,oN, sN, bN) Ù
(cN = cN1) Ù (pN = pN1) Ù cty = ‘Glasgow’)}
© Pearson Education Limited 1995, 2005
55
Domain Relational Calculus
• When restricted to safe expressions, domain relational
calculus is equivalent to tuple relational calculus
restricted to safe expressions, which is equivalent to
relational algebra.
• Means every relational algebra expression has an
equivalent relational calculus expression, and vice versa.
© Pearson Education Limited 1995, 2005
56
Other Languages
• Transform-oriented languages are non-procedural
languages that use relations to transform input data
into required outputs (e.g. SQL).
• Graphical languages provide user with picture of the
structure of the relation. User fills in example of what
is wanted and system returns required data in that
format (e.g. QBE).
© Pearson Education Limited 1995, 2005
57
Other Languages
• 4GLs can create complete customized application using
limited set of commands in a user-friendly, often menu-
driven environment.
• Some systems accept a form of natural language,
sometimes called a 5GL, although this development is still
at an early stage.
© Pearson Education Limited 1995, 2005