DATABASE MANAGEMENT

SYSTEMS

UNIT-II
CH-1 RELATIONAL ALGEBRA
AND CALCULUS
 Relational Query Languages
• Query languages: Allow manipulation and retrieval of
data from a database.
• Relational model supports simple, powerful query
languages:
– Strong formal foundation based on logic.
– Allows for much optimization.
• Query Languages != programming languages!
– QLs not expected to be “Turing complete”.
– QLs not intended to be used for complex calculations.
– QLs support easy, efficient access to large data sets.

3
 Formal Relational Query Languages
Two mathematical Query Languages form the
basis for “real” languages (e.g. SQL), and for
implementation:
• Relational Algebra: More operational, very useful
for representing execution plans.
• Relational Calculus: Lets users describe what
they want, rather than how to compute it. (Non-
operational, declarative.)
 Understanding Algebra & Calculus is key to
understanding SQL, query processing!
4
 Preliminaries
• A query is applied to relation instances, and the
result of a query is also a relation instance.
– Schemas of input relations for a query are fixed
– The schema for the result of a given query is also fixed!
Determined by definition of query language constructs.
• Positional vs. named-field notation:
– Positional notation easier for formal definitions, named-
field notation more readable.
– Both used in SQL

5
 sid bid day
R1
Example Instances 22 101 10/10/96
• “Sailors” and “Reserves” relations
58 103 11/12/96
for our examples.
• We’ll use positional or named field
notation, assume that names of S1 sid sname rating age
fields in query results are
`inherited’ from names of fields in
22 dustin 7 45.0
query input relations. 31 lubber 8 55.5
58 rusty 10 35.0
S2
sid sname rating age
28 yuppy 9 35.0
31 lubber 8 55.5
44 guppy 5 35.0
B1 58 rusty 10 35.0 6
• The Relational Algebra is used to define the ways in which
relations (tables) can be operated to manipulate their
data.
• It is used as the basis of SQL for relational databases, and
illustrates the basic operations required of any DML.
• This Algebra is composed of Unary operations (involving a
single table) and Binary operations (involving multiple
tables).
• There are two formal query languages associated with
the relational model.
 Relational algebra
 Relational calculus
• Query languages are specialized languages for asking
questions, or queries, that involve the data in a database.
• Queries in Relational algebra are composed
using a collection of operators, and each
query describes a step-by-step procedure for
computing the desired answer; that is,
queries are specified in an operational
manner.
• Relational calculus, in which a query
describes the desired answer without
specifying how the answer is to be
computed; this nonprocedural style of
querying is called declarative.
RELATIONAL ALGEBRA
• Relational algebra is one of the two formal query
languages associated with the relational model.
• Relational algebra is a procedural query language, which
takes instances of relations as input and yields instances
of relations as output.
• It uses operators to perform queries. An operator can be
either unary or binary.
• They accept relations as their input and yield relations as
their output.
• Relational algebra is performed recursively on a relation
and intermediate results are also considered relations.
• Each relational query describes a step-by-step
procedure for computing the desired answer,
based on the order in which operators are
applied in the query.
• The procedural nature of the algebra allows us
to think of an algebra expression as a recipe,
or a plan, for evaluating a query, and
relational systems in fact use algebra
expressions to represent query evaluation
plans.
Sailors(sid: integer, sname: string, rating: integer, age: real)
Boats(bid: integer, bname: string, color: string)
Reserves(sid: integer, bid: integer, day: date)
SELECTION
Relational algebra includes operators to select
rows from a relation () and to project columns ().
• These operations allow us to manipulate data in
a single relation.
rating>8(S2)
• The selection operator species the tuples to
retain through a selection condition.
• In general, the selection condition is a Boolean
combination (i.e., an expression using the
logical connectives ˄ and ˅) of terms that
have the form
attribute op constant
or
attribute1 op attribute2
• where op is one of the comparison operators
<,<=,=, ≠, >=, or >.
PROJECTION
• The projection operator allows us to extract
columns from a relation; for example,
• we can find out all sailor names and ratings
by using .
• The expression sname,rating(S2)
• For example, we can compute the names and ratings of
highly rated sailors by combining two of the preceding
queries.
• sname,rating(σrating>8(S2))
Renaming
• Renaming operator is designated by ρ(rho).
•The expression ρ(R(F¯),E) takes an arbitrary
relational algebra expression E and returns an
instance of a (new) relation called R.
• R contains the same tuples as the result of E, and
has the same schema as E, but some fields are
renamed.
• The field names in relation R are the same as in E,
except for fields renamed in the renaming list F ¯,
which is a list of terms having the form oldname
→ newname or position → newname.
For example, the expression
(R(1 → sid1, 5 → sid2) S1xR1)
returns a relation that contains the tuples
shown which has the following schema:
R(sid1:integer, sname: string, rating: integer,
age: real, sid2: integer, bid: integer,day: dates).
• S1 x R1: Each row of S1 paired with each row of R1.
• Q: How many rows in the result?
• Result schema has one field per field of S1 and R1, with
field names `inherited’ if possible.
– May have a naming conflict: Both S1 and R1 have a field
with the same name.
– In this case, can use the renaming operator:
Set Operations
The following standard operations on sets are also available in
relational algebra:
union(Ս),
intersection (Ո),
set-difference (−),
cross-product (X).
Union: RՍS returns a relation instance containing all tuples
that occur in either relation instance R or relation instance S
(or both). R and S must be union-compatible, and the schema
of the result is defined to be identical to the schema of R.
• Two relation instances are said to be union-compatible if
the following conditions hold:
- they have the same number of the fields, and
- corresponding fields, taken in order from left to right, have
the same domains.
Intersection: RՈS returns a relation instance
containing all tuples that occur in both R and S.
The relations R and S must be union-compatible,
and the schema of the result is defined to be
identical to the schema of R.
Set-difference: R−S returns a relation instance
containing all tuples that occur in R but not in S.
The relations R and S must be union-compatible,
and the schema of the result is defined to be
identical to the schema of R.
Cross-product: RxS returns a relation instance
whose schema contains all the fields of R (in the
same order as they appear in R) followed by all the
fields of S(in the same order as they appear in S).
The result of RxS contains one tuple ‹r, s› (the
concatenation of tuples r and s) for each pair of
tuples rεR; sεS. The cross-product operation is
sometimes called Cartesian product.
What is Join in DBMS?
• Join in DBMS is a binary operation which
allows you to combine join product and
selection in one single statement. The goal of
creating a join condition is that it helps you to
combine the data from two or more DBMS
tables. The tables in DBMS are associated
usingofthe
Types primary key and foreign keys.
Join
• There are mainly two types of joins in DBMS:
• Inner Joins: Theta, Natural, EQUI
• Outer Join: Left, Right, Full
• Inner Join
• Inner Join is used to return rows from both tables
which satisfy the given condition. It is the most widely
used join operation and can be considered as a
default join-type
• An Inner join or equijoin is a comparator-based join
which uses equality comparisons in the join-
predicate. However, if you use other comparison
operators like “>” it can’t be called equijoin.
• Inner Join further divided into three subtypes:
• Theta join
• Natural join
• EQUI join
• Theta Join
• Theta Join allows you to merge two tables
based on the condition represented by theta.
Theta joins work for all comparison operators.
It is denoted by symbol θ. The general case of
JOIN operation is called a Theta join.
• Syntax:
• A ⋈θ B
Theta join can use any conditions in the selection criteria.
Consider the following tables.

For example:
A⋈ A.column 2 > B.column 2
(B)
• EQUI Join
• EQUI Join is done when a Theta join uses only the
equivalence condition. EQUI join is the most difficult
operation to implement efficiently in an RDBMS, and
one reason why RDBMS have essential performance
problems.
• For example:
• A ⋈ A.column 2 = B.column 2 (B)
• Natural Join (⋈)
• Natural Join does not utilize any of the comparison
operators. In this type of join, the attributes should
have the same name and domain. In Natural Join,
there should be at least one common attribute
between two relations.
• It performs selection forming equality on those
attributes which appear in both relations and
eliminates the duplicate attributes.
• Example:
• Consider the following two tables
• Outer Join
• An Outer Join doesn’t require each record in the two join tables to
have a matching record. In this type of join, the table retains each
record even if no other matching record exists.
• Three types of Outer Joins are:
• Left Outer Join
• Right Outer Join
• Full Outer Join
• Left Outer Join (A ⟕ B)
• Left Outer Join returns all the rows from the table on the left even
if no matching rows have been found in the table on the right.
When no matching record is found in the table on the right, NULL
is returned.
• Right Outer Join ( A ⟖ B )
• Right Outer Join returns all the columns from
the table on the right even if no matching
rows have been found in the table on the left.
Where no matches have been found in the
table on the left, NULL is returned. RIGHT
outer JOIN is the opposite of LEFT JOIN
• In our example, let’s assume that you need to
get the names of members and movies rented
by them. Now we have a new member who
has not rented any movie yet.
• Full Outer Join ( A ⟗ B)
• In a Full Outer Join , all tuples from both
relations are included in the result,
irrespective of the matching condition.
• Example:
• A⟗B
 Division

Division operator A/B can be applied if and only if:

• Attributes of B is proper subset of Attributes of A.
• The relation returned by division operator will
have attributes = (All attributes of A – All
Attributes of B)
• The relation returned by division operator will
return those tuples from relation A which are
associated to every B’s tuple.
For e.g.
• Consider two relation instances A and B in which
A has (exactly) two fields x and y and B has just
one field y, with the same domain as in A.
• We define the division operation AlB as the set of
all x values (in the form of unary tuples) such that
for every y value in (a tuple of) B, there is a tuple
(x,y) in A.
Table1 :STUDENT_SPORTS Table2: ALL_SPORTS

ROLL_NO SPORTS SPORTS

1 Badminton Badminton
2 Cricket Cricket
2 Badminton
4 Badminton
• To apply division operator as
STUDENT_SPORTS/ ALL_SPORTS

The operation is valid as

• attributes in ALL_SPORTS is a proper subset of attributes in
STUDENT_SPORTS.
• The attributes in resulting relation will have attributes
{ROLL_NO,SPORTS}-{SPORTS}=ROLL_NO
• The tuples in resulting relation will have those ROLL_NO which
are associated with all B’s tuple {Badminton, Cricket}.
• ROLL_NO 1 and 4 are associated to Badminton only. ROLL_NO
2 is associated to all tuples of B. So the resulting relation will
ROLL_NO
be:
2
example
(Q1) Find the names of sailors who have reserved boat 103.
A) Select s.sname from sailor s, reserves r where s.sid=r.sid and r.bid=103;
(Q2) Find the names of sailors who have reserved a red boat.
B) Select s.sname from sailor s, reserves r, boats b where
r.bid=b.bid and s.sid=r.sid and b.color = “red”;

(Q3) Find the colors of boats reserved by Lubber.

C) Select b.color from sailor s, reserves r, boats b where s.sname=lubber and
s.sid=r.sid and r.bid=b.bid;

(Q4) Find the names of sailors who have reserved at least one boat.
A) Select s.sname from sailor s, reserves r, boats b where r.bid=b.bid and s.sid=r.sid ;

(Q5) Find the names of sailors who have reserved a red boat and green boat.
D) A) Select s.sname from sailor s, reserves r, boats b where b.color = “red” AND
“green” and r.bid=b.bid and s.sid=r.sid;
Find sid’s of the sailors whose age>35
Select s.sid from sailor s where age>35
Find the name of the sailors and dates reserved by the sailors
Select s.sname, r.day from sailor s , reserves r where s.sid=r.sid;
Find the name and color of the boat of that sailor
select s.sname, b.color from sailor s, boat b, reserves r where s.sid=r.sid and r.bid=b.bid;
Find name and boat names of the sailors.
Select s.sname , b.bname from sailor s , boat b, reserves r where s.sid=r.sid and r.bid=b.bid;
Find the name of the sailor who have reserved a boat
select s.sname from sailor s , reserves r where s.sid=r.sid;
Find the name of the sailor who has reserved a boat 101
select s.sname from sailor s , reserves r where s.sid=r.sid and r.bid=101;
Find name of the sailor who has reserved a green boat
Select s.sname from sailor s , reserves r, boats b where b.color=“green” and s.sid=r.sid and
r.bid=b.bid;
Find the color of the boat reserved by Horatio.
select b.color from sailor s, reserves r, boats b where s.sid=r.sid and r.bid=b.bid and
s.sname=“horatio”;
Find the name of the sailor who has reserved a red or blue boat.
Select s.sname from sailor s, reserves r, boats b where s.sid=r.sid and r.bid=b.bid and
b.color=“red” or “blue”;
Find sid’s of sailor whose age>35 and who has not reserved a green boat.
Select s.sid from sailor s, reserves r, boat b where s.age>35 and s.sid=r.sid and
r.bid=b.bid and b.color!=“green”;
Find the name of all the sailors whose rating>8 and age>30
Select s.sname from sailor s where s.rating>8 INTERSECT Select s.sname from
sailor s where s.age >30
Find the name of the sailor who has reserved a red or a green boat
Select s.sname from sailor s, reserves r, boats b where s.sid=r.sid and
r.bid=b.bid and b.color=“red” UNION Select s.sname from sailor s, reserves r,
boats b where s.sid=r.sid and r.bid=b.bid and b.color=“green”;
Find the name of the sailors who has reserved both red and green boat
Select s.sname from sailor s, resreves r, boats b where s.sid=r.sid and
r.bid=b.bid and b.color=“red” INTERSECT Select s.sname from sailor s, resreves
r, boats b where s.sid=r.sid and r.bid=b.bid and b.color=“green” ;
Find the name of sailors who has reserved a red boat but not green boat
Select s.sname from sailor s, resreves r, boats b where s.sid=r.sid and
r.bid=b.bid and b.color=“red” MINUS Select s.sname from sailor s, resreves r,
boats b where s.sid=r.sid and r.bid=b.bid and b.color=“green” ;
Find the name of the sailor’s who has reserved atleast two boats.
select s.sid,count(b.bid) from sailors s, reserves r where s.sid=r.sid group by
r.sid having count(r.bid) > = 2;
Find the name of all sailors who has reserved all boats
SELECT S.sname FROM Sailors S WHERE NOT EXISTS ((SELECT B.bid FROM
Boats B) EXCEPT (SELECT R.bid FROM Reserves R WHERE R.sid=S.sid));
Find the names of sailors who has reserved all Interlake boat
select * from sailors where sid in(select sid from reserves inner join boats on
reserves.bid = boats.bid where boats.bname='Interlake');
Find the name of all sailors who has reserved all dipper boat
select * from sailors where sid in(select sid from reserves inner join boats on
reserves.bid = boats.bid where boats.bname=’dipper’);
 Relational Calculus
• Relational Algebra is a procedural query language to
fetch data and which also explains how it is done
• Relational Calculus in non-procedural query language
and has no description about how the query will work
or the data will be fetched.
• It only focusses on what to do, and not on how to do it.
• Relational Calculus exists in two forms:
1. Tuple Relational Calculus (TRC)
2. Domain Relational Calculus (DRC)
 Tuple Relational Calculus (TRC)
• The tuple relational calculus is specified to select
the tuples in a relation.
• TRC is used for selecting those tuples that satisfy
the given condition.
• In TRC, filtering variable uses the tuples of a
relation.
• The result of the relation can have one or more
tuples.
• Notation:
{t | P(t)} or {t | Condition (t)}
• where t = resulting tuples,
P(t) = known as Predicate and these are the
conditions that are used to fetch t
• Thus, it generates set of all tuples , such that
Predicate P(t) is true for t.
• P(t) may have various conditions logically combined
with OR (∨), AND (∧), NOT(¬).
• We can also specify column name using a . dot
operator, with the tuple variable to only get a certain
attribute(column) in result.
 It also uses quantifiers:

• ∃ t ∈ r (Q(t)) : ”there exists” a tuple in t in

relation r such that predicate Q(t) is true.

• ∀ t ∈ r (Q(t)) : predicate Q(t) is true “for all”

tuples in relation r.
 Example

-Find all sailors with a rating above 7.

{S.sname I S ϵ Sailors Ʌ S.rating > 7}

Table: Student
First_Name Last_Name Age
Ajeet Singh 30
Chaitanya Singh 31
Rajeev Bhatia 27
Carl Pratap 28

-To fetch names of students, from Student, with age greater

than 17
-Query to display the last name of those students
where age is greater than 30
{ t.Last_Name | Student(t) AND t.age > 30 }

-Query to display all the details of students where

Last name is ‘Singh’
{ t | Student(t) AND t.Last_Name = 'Singh' }
Table: Loan
Loan number Branch name Amount
L33 ABC 10000
L35 DEF 15000
L49 GHI 9000
L98 DEF 65000
Q) Find the branch-name, loan number and
amount for loans over 9000
{t|t ∈ loan ∧ t[amount] >9000}
 Domain Relational Calculus (DRC)
• In domain relational calculus, filtering is done based on
the domain of the attributes and not based on the tuple
values.
• In Domain Relational Calculus, a query is expressed as,
{ < x1, x2, x3, ..., xn > | P (x1, x2, x3, ..., xn ) }
• where, < x1, x2, x3, …, xn > represents resulting domains
of attributes and P (x1, x2, x3, …, xn ) represents the
condition or formula equivalent to the Predicate calculus.
• Predicate Calculus Formula:
 Set of all comparison operators
 Set of connectives like and, or, not
 Set of quantifiers
 Example
First_Name Last_Name Age
Ajeet Singh 30
Chaitanya Singh 31
Rajeev Bhatia 27
Carl Pratap 28
 Example
• Query to find the first name and age of students
where student age is greater than 27
{< First_Name, Age > | ∈ Student ∧ Age > 27}

{< First_Name, Age > | ∈ Student ∧ Age > 28 ∧

First_Name like ‘c%’}
Table-2: Loan
Loan number Branch name Amount
L01 Main 200
L03 Main 150
L10 Sub 90
L08 Main 60

Find the loan number, branch, amount of loans of

greater than or equal to 100 amount.

{<l, b, a> | <l, b, a> ∈ loan ∧ (a >= 100)}