Module-2

Textbook:1
Chapter 5.1 to 5.3
Relational data model and relational
database constraints
 Relational Model
• Relational Model Concepts
• Relational Model Constraints and Relational
Database Schemas
• Update Operations and Dealing with
Constraint Violations
 Relational Model Concepts
• The Relational data model was first introduced by Ted
Codd of IBM Research in 1970.

• The first commercial implementations of the

relational model became available in the early 1980s,
such as the SQL system by IBM and the Oracle
DBMS.

• Current popular commercial relational DBMSs

(RDBMSs) include DB2 (from IBM), Oracle (from
Oracle), Sybase DBMS (now from SAP), and SQL
Server and Microsoft Access (from Microsoft)
,MySQL (from Oracle) and PostgreSQL.
 Relational Model Concepts
• The relational model represents the database as
a collection of relations.
• Relation: A table of values
• Each row in the table represents a collection of
related data values.
• A row represents a fact that typically
corresponds to a real-world entity or
relationship.
In the formal relational model terminology,
• a row is called a tuple,
• a column header is called an attribute, and
• the table is called a relation.
• The data type describing the types of values
that can appear in each column is represented
by a domain of possible values.
Domains, Attributes, Tuples, and Relations
• A domain D is a set of atomic values.

• By atomic we mean that each value in the domain is

indivisible

• Social_security_numbers: The set of valid nine-digit Social

Security numbers.

• Names: The set of character strings that represent names of

persons.

• Employee_ages: Possible ages of employees in a company;

each must be an integer value between 15 and 80.
• A relation schema R, denoted by R(A1, A2, … ,
An), is made up of a relation name R and a list of
attributes, A1, A2, … , An.
• The degree (or arity) of a relation is the number of
attributes n of its relation schema.
Ex: A relation of degree seven
STUDENT(Name,Ssn,Home_phone,Address,Office_
phone, Age, Gpa)
• A relation (or relation state) r of the relation
schema R(A1, A2, … , An), also denoted by r(R),
is a set of n-tuples. r={t1,t2,…,tn}
• Each tuple is an ordered list of n values
t=<v1, v2, … , vn>, where each value vi, is an
element of dom (Ai) or is a special NULL value.
• Relation intension for the relation schema R
• Relation extension for a relation state r(R)
• an example of a STUDENT relation, which
corresponds to the STUDENT schema
• STUDENT(Name, Ssn, Home_phone, Address,
Office_phone, Age, Gpa)
 CHARACTERISTICS OF RELATIONS
1. Ordering of tuples in a relation
2. Ordering of attributes in a relation schema
3. Values in a tuple
4. Interpretation (meaning) of a relation
 1. Ordering of tuples in a relation r(R)

• A relation is defined as a set of tuples. Elements of a

set have no order among them.
• The tuples are not considered to be ordered, even
though they appear to be in the tabular form.
2. Ordering of attributes in a relation schema R
• The order of attributes and their values is not that
important as long as the correspondence between
attributes and values is maintained.
• Tuples can be considered as a set of (<attribute>
,<value) pairs. The ordering of attributes is not
important because the attribute name appears with
its value
 3. Values and NULLs in the tuple
• All values are considered atomic , that is it is not divisible.
Hence, composite and multivalued attributes are not
allowed.
• A special null value is used to represent values that are
unknown or inapplicable to certain tuples.
Example:
• STUDENT tuples have NULL values for ‘office-phone’
attribute, because student do not have an office.

• Another student has NULL for home-phone, because

either he does not have a phone or he has one but we do
not know it.
4. Interpretation (meaning ) of a relation
• Each tuple in the relation can be interpreted
as particular instance of relation

Example:
• The schema of the STUDENT relation asserts
that, in general, a student entity has a name ,
ssn , home-phone address
 Notations used
• A relation schema R of degree n is denoted by R(A1, A2, … , An).
• The uppercase letters Q, R, S denote relation names.
• The lowercase letters q, r, s denote relation states.
• The letters t, u, v denote tuples.
• In general, the name of a relation schema such as STUDENT also indicates
the current set of tuples in that relation—the current relation state—
whereas STUDENT(Name, Ssn, …) refers only to the relation schema.
• An attribute A can be qualified with the relation name R to which it
belongs by using the dot notation R.A—for example, [Link] or
[Link]. This is because the same name may be used for two
attributes in different relations.
• An n-tuple t in a relation r(R) is denoted by t =<v1,v2, ….., vn> , where vi is
the value corresponding to attribute Ai.

The following notation refers to component values of tuples:

• Both t[Ai] and [Link] (and sometimes t[i]) refer to the value vi in t for
attribute Ai.
• Both t[Au, Aw, … , Az] and t.(Au, Aw, … , Az), where Au, Aw, … , Az is a list
of attributes from R, refer to the subtuple of values from t corresponding
to the attributes specified in the list.
 Types of keys in DBMS
• A key in DBMS is an attribute or a set of
attributes that help to uniquely identify a tuple
(or row) in a relation (or table).

• Keys are also used to establish relationships

between the different tables and columns of a
relational database

• Individual values in a key are called key values

 Types of keys in DBMS
• Super key
• Candidate key
• Primary key
• Alternate key
• Foreign key
• Partial key
• Composite key/compound key
• Unique key
• Secondary key
 Super Key
• A super key is a set of attributes that can identify each tuple uniquely in the
given relation.
• A super key is not restricted to have any specific number of attributes.
• Thus, a super key may consist of any number of attributes.

• Example:

• Student ( roll , name , AdharNo , age , Email , class )

(roll) ,(AdharNo), (Email), (roll,AdharNo), (roll,Email), (roll,AdharNoroll,Email),

( roll , name , class , section ),( class , section roll ),(class ,sectio , roll ,Email ),
( name , address , AdharNo)………..etc

NOTE-

• All the attributes in a super key are definitely sufficient to identify each
tuple uniquely in the given relation but all of them may not be necessary
 Candidate key
• CANDIDATE KEY in DBMS is a set of attributes that
uniquely identify tuples in a table.
• Candidate Key is a super key with no repeated
attributes.
• The Primary key should be selected from the candidate
keys.
• Every table must have at least a single candidate key.
• A table can have multiple candidate keys but only a
single primary key.
 PRIMARY KEY
• PRIMARY KEY in DBMS is a attribute(column) in a
Relation that uniquely identify every tuple(row) in that
Relation(table) .
• The Primary Key can’t be a duplicate - meaning the
same value can’t appear more than once in the table.
• A table cannot have more than one primary key.

Rules for defining Primary key:

• Two rows can’t have the same primary key value
• It must for every row to have a primary key value.
• The primary key field cannot be null.
• The value in a primary key column can never be
modified or updated if any foreign key refers to that
primary key.
 ALTERNATE KEYS
• ALTERNATE KEYS is a column or group of
columns in a table that uniquely identify every
row in that table.
• A table can have multiple choices for a
primary key but only one can be set as the
primary key.
• All the keys which are not primary key are
called an Alternate Key.
 FOREIGN KEY
• FOREIGN KEY is a attribute(column) that
creates a relationship between two
Relation(tables).
• The purpose of Foreign keys is to maintain
data integrity and allow navigation between
two different instances of an entity.
• It acts as a cross-reference between two
tables as it references the primary key of
another table.
 COMPOUND KEY/composite key
• COMPOUND KEY has two or more attributes that allow you
to uniquely recognize a specific record.
• It is possible that each column may not be unique by itself
within the database.
• However, when combined with the other column or columns
the combination of composite keys become unique.
• The purpose of the compound key in database is to uniquely
identify each record in the table
 Relational Model Constraints
and Relational Database Schemas
Relational Model Constraints on databases can generally be divided
into three main categories:
1. Constraints that are inherent in the data model known as inherent
model-based constraints or implicit constraints.

2. Constraints that can be directly expressed in the schemas of the

data model, typically by specifying them in the DDL known as
schema-based constraints or explicit constraints.

3. Constraints that cannot be directly expressed in the schemas of

the data model, and hence must be expressed and enforced by
the application programs or in some other way known as
application-based or semantic constraints or business rules.

• The schema-based constraints include domain constraints, key

constraints, constraints on NULLs, entity integrity constraints, and
referential integrity constraints.
 schema-based constraints or explicit
constraints.

• Domain constraints
• Key constraints, constraints on nulls
• Entity integrity constraints, and
• Referential integrity constraints.
 Domain Constraints
• Domain constraint defines the domain or set
of values for an attribute
• Domain constraints specify that within each
tuple, the value of each attribute A must be an
atomic value from the domain dom(A).

STU_I
Name Age
D

S001 Akshay 20

S002 Abhishek 21

S003 Shashank 20

S004 Rahul A
 2. Key Constraints and Constraints on NULL
Values
• In the formal relational model, a relation is defined as a set of
tuples.

• By definition, all elements of a set are distinct; hence, all tuples in

a relation must also be distinct.

• This means that no two tuples can have the same combination of
values for all their attributes. Usually, there are other subsets of
attributes of a relation schema R with the property that no two
tuples in any relation state r of R should have the same
combination of values for these attributes.

• Suppose that we denote one such subset of attributes by SK; then

for any two distinct tuples t1 and t2 in a relation state r of R, we
have the constraint that:
t1[SK] ≠ t2[SK]
 Constraints on NULL
• Another constraint on attributes specifies
whether NULL values are permitted or not ?.
• For example, if every STUDENT tuple must
have a valid, non-NULL value for the Name
attribute, then Name of STUDENT is
constrained to be NOT NULL.
• The definitions and constraints we have
discussed so far apply to single relations and
their attributes.
• A relational database usually contains many
relations, with tuples in relations that are
related in various ways.
Relational Databases and Relational Database
Schemas

• A relational database schema S is a set of

relation schemas S = {R1, R2, … , Rm} and a set
of integrity constraints IC.
• A relational database state DB of S is a set of
relation states DB = {r1, r2, … , rm} such that
each ri is a state of Ri and such that the ri
relation states satisfy the integrity constraints
specified in IC.
 3. Entity Integrity, Referential
Integrity, and Foreign Keys
• The entity integrity constraint states that no
primary key value can be NULL.
• This is because the primary key value is used to
identify individual tuples in a relation.
• Having NULL values for the primary key implies
that we cannot identify some tuples.
 Referential integrity constraint
• Key constraints and entity integrity constraints
are specified on individual relations.
• The referential integrity constraint is
specified between two relations and is used to
maintain the consistency among tuples in the
two relations.
• For example, the attribute Dno of EMPLOYEE gives
the department number for which each employee
works; hence, its value in every EMPLOYEE tuple
must match the Dnumber value of some tuple in the
DEPARTMENT relation.
 Referential integrity constraint

• The referential integrity constraint states that a

tuple in one relation that refers to another
relation must refer to an existing tuple in that
relation.
• To define Referential Integrity, the concept of a
Foreign Key is used.
• The conditions for a foreign key, given below,
specify a referential integrity constraint between
the two relation schemas R1 and R2.
A set of attributes FK in relation schema R1 is a foreign
key of R1 that references relation R2 if it satisfies the
following rules:
1. The attributes in FK have the same domain(s) as the
primary key attributes PK of R2;
2. A value of FK in a tuple t1 of the relation R1 either
occurs as a value of PK for some tuple t2 in the
relation R2 or is NULL.
• In the EMPLOYEE relation, the attribute Dno
refers to the department for which an
employee works.
• We designate Dno to be a foreign key of
EMPLOYEE referencing the DEPARTMENT
relation.
• We can diagrammatically display referential
integrity constraints by drawing a directed arc
from each foreign key to the relation it
references.
• For clarity, the arrowhead may point to the
primary key of the referenced relation.
 Update Operations, Transactions,
and Dealing with Constraint
Violations
There are three basic operations that can change the
states of relations in the database:
• Insert, Delete, and Update (or Modify).
• Insert is used to insert one or more new tuples in a
relation.
• Delete is used to delete tuples.
• Update (or Modify) is used to change the values of
some attributes in existing tuples.
 The Insert Operation:
The Insert operation provides a list of attribute values for a new tuple t
that is to be inserted into a relation R.

Insert can violate any of the four types of constraints.

1. Domain constraints can be violated if an attribute value is given that
does not appear in the corresponding domain or is not of the
appropriate data type.

2. Key constraints can be violated if a key value in the new tuple t already
exists in another tuple in the relation r(R).

3. Entity integrity can be violated if any part of the primary key of the
new tuple t is NULL.

4. Referential integrity can be violated if the value of any foreign key in t

refers to a tuple that does not exist in the referenced relation.
 The Delete Operation

• The Delete operation can violate only referential

integrity.

• This occurs if the tuple being deleted is referenced

by foreign keys from other tuples in the database.

• To specify deletion, a condition on the attributes of

the relation selects the tuple (or tuples) to be
deleted.
• Several options are available if a deletion operation causes
a violation.

• The first option, called restrict, is to reject the deletion.

• The second option, called cascade, is to attempt to cascade

(or propagate) the deletion by deleting tuples that
reference the tuple that is being deleted. For example, in
operation 2, the DBMS could automatically delete the
offending tuples from WORKS_ON with Essn = ‘999887777’.

• A third option, called set null or set default, is to modify the

referencing attribute values that cause the violation; each
such value is either set to NULL or changed to reference
another default valid tuple.
 The Update Operation
• The Update (or Modify) operation is used to
change the values of one or more attributes in
a tuple (or tuples) of some relation R.

• It is necessary to specify a condition on the

attributes of the relation to select the tuple
(or tuples) to be modified.
 The Transaction Concept
• A transaction is an action or series of actions that
are being performed by a single user or
application program, which reads or updates the
contents of the database.

• A transaction can be defined as a logical unit of

work on the database. This may be an entire
program, a piece of a program, or a single
command (like the SQL commands such as
INSERT or UPDATE), and it may engage in any
number of operations on the database.
•
The Transaction Concept
• The transaction has the four properties. These
are used to maintain consistency in a
database, before and after the transaction.

• Atomicity
• Consistency
• Isolation
• Durability
 Atomicity

• It states that all operations of the transaction take place at once if

not, the transaction is aborted.

• There is no midway, i.e., the transaction cannot occur partially. Each

transaction is treated as one unit and either run to completion or is
not executed at all.

Atomicity involves the following two operations:

• Abort: If a transaction aborts then all the changes made are not
visible.
• Commit: If a transaction commits then all the changes made are
visible
 Consistency

• The integrity constraints are maintained so that the

database is consistent before and after the transaction.

• The execution of a transaction will leave a database in

either its prior stable state or a new stable state.

• The consistent property of database states that every

transaction sees a consistent database instance.

• The transaction is used to transform the database from

one consistent state to another consistent state.
 Isolation

• It shows that the data which is used at the

time of execution of a transaction cannot be
used by the second transaction until the first
one is completed.

• In isolation, if the transaction T1 is being

executed and using the data item X, then that
data item can't be accessed by any other
transaction T2 until the transaction T1 ends.
 Durability

• The durability property is used to indicate the performance

of the database's consistent state. It states that the
transaction made the permanent changes.

• They cannot be lost by the erroneous operation of a faulty

transaction or by the system failure. When a transaction is
completed, then the database reaches a state known as the
consistent state. That consistent state cannot be lost, even
in the event of a system's failure.

• The recovery subsystem of the DBMS has the responsibility

of Durability property
 The Relational Algebra
• Data model must include a set of operations to
manipulate the database.
• The set of operations for the relational model
is the relational algebra.
• These operations enable a user to specify basic
retrieval requests.
• The result of a retrieval query is a new
relation.
Textbook:1
Chapter 8.1 to 8.5
Relational Algebra
 The Relational Algebra
• The basic set of operations for the relational
model is known as the relational algebra.

• These operations enable a user to specify basic

retrieval requests.

• The result of a retrieval is a new relation, which

may have been formed from one or more
relations.
• 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.
 Unary Relational Operations
SELECT and PROJECT
SELECT Operation
• SELECT operation is used to select a subset of the
tuples from a relation that satisfy a selection
condition.
• It is a filter that keeps only those tuples that satisfy a
qualifying condition – those satisfying the condition
are selected while others are discarded.

• The SELECT operation R produces a relation S that

has the same schema as R.
• Example: select the EMPLOYEE tuples whose
department number is 4 the following notation
is used:

DNO = 4 (EMPLOYEE)
• Example: select the EMPLOYEE tuples whose
salary is greater than $30,000
SALARY > 30,000 (EMPLOYEE)
• DNO = 4 (EMPLOYEE)
SALARY > 30,000 (EMPLOYEE)
 SELECT Operation

• In general, the select operation is denoted by

 <selection condition>(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
<selection condition>
<attribute name> <comparison op> <constant value>

Or

• <attribute name> <comparison op> <attribute name>

where <attribute name> is the name of an attribute of

R,
<comparison op> is normally one of the operators
{=, <, ≤, >, ≥, ≠},

• Clauses can be connected by the standard Boolean

operators and, or, and not to form a general selection
condition.
• Select the tuples for all employees who work in
department 4 and make over $25,000 per year:

σ (Dno=4 AND Salary>25000) (EMPLOYEE)

---------------------------------------------------------------
•select the employees who either work in department 4
or work in department 5 :
• select the tuples for all employees who
either work in department 4 or work in
department 5

σ (Dno=4 OR Dno=5) (EMPLOYEE)

• 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:
• 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:

σ(Dno=4 AND Salary>25000) OR (Dno=5 AND

Salary>30000) (EMPLOYEE)
 Unary Relational Operations
SELECT Operation Properties

• SELECT operation is commutative; that is,

σ<cond1>(σ<cond2>(R)) =
σ<cond2>(σ<cond1>(R))
• We can always combine a cascade (or
sequence) of SELECT operations into a single
SELECT operation with a conjunctive (AND)
condition; that is,
• σ<cond1>(σ<cond2>(... (σ<condn>(R)) ...)) =
σ<cond1> AND<cond2> AND...AND
<condn>(R)
• In SQL, the SELECT condition is typically
specified in the WHERE clause of a query.
• For example, the following operation:
σDno=4 AND Salary>25000 (EMPLOYEE)
would correspond to the following SQL query:

SELECT *
FROM EMPLOYEE
WHERE Dno=4 AND Salary>25000;
 Unary Relational Operations
• PROJECT Operation
• This operation selects certain columns from
the table and discards the other columns.

• The PROJECT creates a vertical partitioning

one with the needed columns (attributes)
containing results of the operation and other
containing the discarded Columns.
Example: To list each employee’s first and last
name and salary, the following is used:

 LNAME, FNAME,SALARY (EMPLOYEE)

 PROJECT Operation
• 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.
• In SQL, the PROJECT attribute list is specified
in the SELECT clause of a query.
• For example, the following operation:

π Salary(EMPLOYEE)
• would correspond to the following SQL query:
SELECT DISTINCT Salary
FROM EMPLOYEE
 Sequences of Operations and the
RENAME Operation
Retrieve the first name, last name, and salary of all
employees who work in department number 5.
• We must apply a SELECT and a PROJECT
operation.
• We can write a single relational algebra expression,
also known as an in-line expression, as follows:

πFname, Lname, Salary(σDno=5(EMPLOYEE))

 πFname, Lname, Salary(σDno=5(EMPLOYEE))

•πFname, Lname,
Salary( σDno=5(EMPLOYEE))
• The sequence of operations, giving a name to each
intermediate relation, and using the assignment
operation, denoted by ← (left arrow), as

DEP5_EMPS ← σ (EMPLOYEE)
Dno=5

RESULT ← πFname, Lname, Salary(DEP5_EMPS)

• We can rename the attributes in the
intermediate and result relations.
 RENAME operation
• Can rename either the relation name or the attribute
names, or both—as a unary operator.

• The general RENAME operation when applied to a

relation R of degree n is denoted by any of the
following three forms:

• where the symbol ρ(rho) is used to denote the

RENAME operator
• In SQL, expression would correspond to the
following SQL query:
• Renaming in SQL is accomplished by aliasing using
AS, as in the following example:

SELECT Fname, Lname, Salary

FROM EMPLOYEE
WHERE Dno=5

SELECT [Link] AS First_name, [Link] AS

Last_name, [Link] AS Salary
FROM EMPLOYEE AS E
WHERE [Link]=5
Relational Algebra Operations from Set Theory
The UNION ,INTERSECTION,MINUS Operations

• These are binary operations.

• The two relations on which any of these three operations are
applied must have the same type of tuples.
• This condition is called union compatibility or type
compatibility.

Union compatibility or Type compatibility

• The two relations have the same number of attributes and each
corresponding pair of attributes has the same domain.
 UNION Operation
The result of this operation, denoted by
R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 . STUDENT ∪ INSTRUCTOR
 Intersection Operation
The result of this operation, denoted by R  S, is a
relation that includes all tuples that are in both R
and S.
 Set Difference (or MINUS)
Operation
The result of this operation, denoted by R - S, is a relation
that includes all tuples that are in R but not in S.
• Both UNION and INTERSECTION are commutative operations; that is,

R ∪ S = S ∪ R and R ∩ S = S ∩ R

• Both UNION and INTERSECTION can be treated as n-ary operations

applicable to any number of relations because both are also associative
operations; that is,

R ∪ (S ∪ T ) = (R ∪ S) ∪ T and (R ∩ S) ∩ T = R ∩ (S ∩ T)

• The MINUS operation is not commutative

R−S≠S−R

• The INTERSECTION can be expressed in terms of union and set difference

as follows:

R ∩ S = ((R ∪ S) − (R − S)) − (S − R)
The CARTESIAN PRODUCT (CROSS PRODUCT)
Operation

• CARTESIAN PRODUCT operation—also known as

CROSS PRODUCT or CROSS JOIN—which is denoted
by ×.

• A binary set operation, but the relations on which it

is applied do not have to be union compatible.

• This set operation produces a new element by

combining every tuple from one relation with every
tuple from the other relation .
• The result of R(A1, A2,…,An) × S(B1, B2,…,
Bm) is a relation Q with degree n + m attributes
Q(A1, A2, … , An, B1, B2, … , Bm), in that order

• If R has n1 tuples, and S has n2 tuples, then R × S

will have n1 * n2 tuples.
Example, suppose that we want to retrieve a list of names
of each female employee’s dependents. We can do this
as follows:

FEMALE_EMPS ← σSex=‘F’(EMPLOYEE)
EMPNAMES ← πFname, Lname, Ssn(FEMALE_EMPS)
EMP_DEPENDENTS ← EMPNAMES × DEPENDENT
ACTUAL_DEPENDENTS ← σSsn=Essn(EMP_DEPENDENTS)
RESULT ← πFname, Lname, Dependent_name(ACTUAL_DEPENDENTS)
 Binary Relational Operations:
JOIN and DIVISION
• The JOIN Operation
• The JOIN operation, denoted by , is used
to combine related tuples from two relations
into single tuples.
Ex: Retrieve the name of the manager of each
department.
• The result of the JOIN is a relation Q with n + m
attributes Q(A1, A2, … , An, B1, B2, … , Bm) in
that order;
• Q has one tuple for each combination of tuples—
one from R and one from S—whenever the
combination satisfies the join condition.
• Main difference between CARTESIAN
PRODUCT and JOIN.
• In JOIN, only combinations of tuples
satisfying the join condition appear in the
result, whereas in the CARTESIAN
PRODUCT all combinations of tuples are
included in the result.
• If <join condition> is of the form Ai θ Bj, Ai is an
attribute of R, Bj is an attribute of S and θ (theta) is
one of the comparison operators {=, <, ≤, >, ≥, ≠}
,then JOIN operation with such a general join
condition is called a THETA JOIN.
 Variations of JOIN: The EQUIJOIN and
NATURAL JOIN
• JOIN, where the only comparison operator used is =,
is called an EQUIJOIN.
• Ex:

• In the result of an EQUIJOIN we always have one or

more pairs of attributes that have identical values in
every tuple.
NATURAL JOIN
• In the result of an EQUIJOIN we always have one or
more pairs of attributes that have identical values in
every tuple.
• One of each pair of attributes with identical values is
superfluous, a new operation called NATURAL
JOIN—denoted by *—was created to get rid of the
second (superfluous) attribute in an EQUIJOIN
condition.
• The NATURAL JOIN requires that the two join
attributes (or each pair of join attributes) have the same
name in both relations.
• If this is not the case, a renaming operation is applied
first.
• Retrieve each PROJECT tuple with the
DEPARTMENT tuple that controls the project.
• The attribute Dnum is called the join attribute for
the NATURAL JOIN operation.
• If the attributes on which the natural join is specified
already have the same names in both relations,
renaming is unnecessary.
• Example:
• Retrieve department tuples along with their location
details.

DEPT_LOCS ← DEPARTMENT * DEPT_LOCATIONS

• DEPT_LOCS ← DEPARTMENT * DEPT_LOCATIONS
 A Complete Set of Relational Algebra
Operations
• It has been shown that the set of relational
algebra operations {σ, π, ∪, ρ, –, ×} is a complete
set;
• that is, any of the other original relational algebra
operations can be expressed as a sequence of
operations from this set.
For example,
• The INTERSECTION operation can be
expressed by using UNION and MINUS as
follows:

• R ∩ S ≡ (R ∪ S) – ((R – S) ∪ (S – R))
• A JOIN operation can be specified as a
CARTESIAN PRODUCT followed by a SELECT
operation, as we discussed:

• A NATURAL JOIN can be specified as a

CARTESIAN PRODUCT preceded by RENAME
and followed by SELECT and PROJECT
operations.
 The DIVISION Operation
• The DIVISION operation is denoted by ÷
• The DIVISION operation is applied to two
relations R(Z) ÷ S(X), where the attributes of S
are a subset of the attributes of R; that is,
X ⊆ Z.
• Let Y be the set of attributes of R that are not
attributes of S; that is,
Y = Z – X.
• R(Z) ÷ S(X), X ⊆ Z, Y = Z – X
• The result of DIVISION is a relation
T(Y) =R(Z) ÷ S(X)
that includes a tuple t such that, t must appear
in R in combination with every tuple in S.
Ex: T ← R ÷ S.
 The DIVISION Operation
• The division operator is used for queries which
involve the ‘all’.
• R1 ÷ R2 = tuples of R1 associated with all
tuples of R2.
• Retrieve the sid of the students who enrolled
in all the courses R
• It will retrieve only those lecturer from
relation R who has taken a subject “Prolog”
from relation S.
• It will retrieve only those lecturer from
relation R who has taken a subject “Prolog”
and “Database”(ALL) from relation S.
•
• Retrieve the details of employee whose name
is ‘John Smith’.
Retrieve the project numbers that ‘John Smith’ works on.
Retrieve the names of employees who work on all
the projects that ‘John Smith’ works on.
 Additional Relational Operations
• Some common database requests cannot be
performed with the original relational algebra
operations.
• In this section we define additional operations
to express these requests.
• Examples of such operations include retrieving
the average or total salary of all employees or the
total number of employee tuples.
 Additional Relational Operations
Aggregate Functions and Grouping

• Specify mathematical aggregate functions

• Applied to collections of numeric values

include SUM, AVERAGE, MAXIMUM, and
MINIMUM.

• The COUNT function is used for counting

tuples or values.
 Aggregate Functions and Grouping

• Another common type of request involves

grouping the tuples in a relation by the value
of some of their attributes and then applying an
aggregate function independently to each
group.
• We can define an AGGREGATE FUNCTION
operation, using the symbol ℱ(pronounced script
F), to specify these types of requests as follows:
• ℱMAXIMUM Salary (Employee)
retrieves the maximum salary value from the
Employee relation
• ℱMINIMUM Salary (Employee)
retrieves the minimum Salary value from the
Employee relation
• ℱSUM Salary (Employee)
retrieves the sum of the Salary from the
Employee relation
 <grouping attributes> ℱ <function list> (R)

• where <grouping attributes> is a list of attributes

of the relation specified in R, and
• <function list> is a list of (<function>
<attribute>) pairs.

• The resulting relation has the grouping attributes

plus one attribute for each element in the function
list.
 DNO ℱCOUNT SSN, AVERAGE Salary (Employee)
groups employees by DNO (department number)
and computes the count of employees and average
salary per department.
DNO ℱCOUNT SSN, AVERAGE Salary (Employee)
• If no grouping attributes are specified, the
functions are applied to all the tuples in the
relation, so the resulting relation has a single
tuple only.

DNO ℱCOUNT SSN, AVERAGE Salary (Employee)

ℱ COUNT Ssn, AVERAGE Salary(EMPLOYEE)

ℱ COUNT Ssn, AVERAGE Salary(EMPLOYEE)
 Recursive Closure Operations
• Another type of operation that, cannot be
specified in the basic original relational algebra
is recursive closure.

• This operation is applied to a recursive

relationship between tuples of the same type,
such as the relationship between an employee
and a supervisor.
• An example of a recursive operation is to retrieve
all supervisees of an employee e at all levels—that
is, all employees e′ directly supervised by e, all
employees e′′ directly supervised by each
employee e′, all employees e″′ directly supervised
by each employee e″, and so on.
• An operation called the transitive closure of
relations has been proposed to compute the
recursive relationship.
For example, to specify the Ssns of all employees e
directly supervised—at level one—by the employee
e whose name is ‘James Borg’ we can apply the
following operation:

BORG_SSN ← πSsn(σFname=‘James’ AND Lname= ‘Borg’(EMPLOYEE))

SUPERVISION(Ssn1, Ssn2) ← πSsn,Super_ssn(EMPLOYEE)
RESULT1(Ssn) ← πSsn1(SUPERVISION Ssn2=SsnBORG_SSN)
• To retrieve all employees supervised by Borg at level
2—that is, all employees e’’ supervised by some
employee e’ who is directly supervised by Borg—we
can apply another JOIN to the result of the first query,
as follows:

• RESULT2(Ssn) ← πSsn1(SUPERVISION Ssn2=SsnRESULT1)

• To get both sets of employees supervised at levels 1

and 2 by ‘James Borg’, we can apply the UNION
operation to the two results, as follows:

• RESULT ← RESULT2 U RESULT1

 OUTER JOIN Operations
• Additional extensions to the JOIN operation that are necessary to
specify certain types of queries.

• The JOIN operations match(combine) tuples that satisfy the join

condition.

• For a NATURAL JOIN operation R * S, only tuples from R that have

matching tuples in S—and vice versa—appear in the result.

• Hence, tuples without a matching (or related) tuple are

eliminated from the JOIN result.

• Tuples with NULL values in the join attributes are also

eliminated. This type of join, where tuples with no match are
eliminated, is known as an inner join.
 OUTER JOIN Operations
• A set of operations, called outer joins, is used
for the case where the user wants to keep
• all the tuples in R,
• or all those in S,
• or all those in both relations in the result of the
JOIN, regardless of whether or not they have
matching tuples in the other relation.
 OUTER JOIN Operations
• LEFT OUTER JOIN
• RIGHT OUTER JOIN
• FULL OUTER JOIN
• The LEFT OUTER JOIN operation denoted
by, keeps every tuple in the first, or left,
relation R;
• If no matching tuple is found in S, then the
attributes of S in the join result are filled or
padded with NULL values.
• R S
R S
• RIGHT OUTER JOIN, denoted by keeps
every tuple in the second, or right, relation S in
the result of R S.
• If no matching tuple is found in R, then the
attributes of R in the join result are filled or
padded with NULL values.
R S
• A third operation, FULL OUTER JOIN,
denoted by , keeps all tuples in both the left
and the right relations.
• When no matching tuples are found, padding
them with NULL values as needed.
R S
• List employee names as well as the name of the
departments they manage if they happen to manage a
department.
 The OUTER UNION Operation
• The OUTER UNION operation takes the union
of tuples from two relations that are partially
compatible, meaning that only some of their
attributes, are union compatible.

• The attributes that are union compatible are

represented only once in the result, and those
attributes that are not union compatible from
either relation are also kept in the result relation.
 The OUTER UNION Operation
• R(X, Y) and S(X, Z)
• X is union compatible
• The result relation T(X, Y, Z)
• Matching will be combined (unioned) into a
single tuple.
• Tuples in either relation that have no matching
tuple in the other relation are padded with
NULL values.
• FACULTY (Name, Ssn, Dept)
• STUDENT (Name, Ssn, Class)
• The resulting relation,
FACULTY_OR_STUDENT(Name, Ssn, Dept,Class)
 Notation for Query Trees
• Describes about the notation typically used in
relational systems to represent queries internally.

• The notation is called a query tree or sometimes it is

known as a query evaluation tree or query execution
tree.

• It includes the relational algebra operations being

executed and is used as a possible data structure for
the internal representation of the query in an RDBMS.

• A query tree is a tree data structure that corresponds

to a relational algebra expression.
• It represents the input relations of the query as leaf
nodes of the tree, and represents the relational
algebra operations as internal nodes.
• An execution of the query tree consists of
executing an internal node operation whenever its
operands (represented by its child nodes) are
available, and then replacing that internal node by
the relation that results from executing the
operation.
• The execution terminates when the root node is
executed and produces the result relation for the
query.
• 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.
Examples of Queries in
Relational Algebra
 Examples of Queries in Relational
Algebra
[Link] the name and address of all employees
whose salary>10000.

πFname, Lname, Address( SALARY > 10,000 (EMPLOYEE)

[Link] the name and address of all employees
who work for the ‘Research’ department.
[Link] every project located in ‘Stafford’, list the
project number, the controlling department
number, and the department manager’s Ssn.
[Link] every project located in ‘Stafford’, list the
project number, the controlling department
number, and the department manager’s Ssn.
[Link] every project located in ‘Stafford’, list the
project number, the controlling department number,
and the department manager’s last name.
[Link] every project located in ‘Stafford’, list the
project number, the controlling department
number, and the department manager’s last
name.
5. List the project numbers controlled by
department number 5.
6. Find the names of employees who work on all the
projects controlled by department number 5
Retrieve the number of employees and their
average salary.

ℱ COUNT SSN, AVERAGE Salary (EMPLOYEE)

For each department retrieve department
number, number of employees and their
average salary

DNO ℱCOUNT SSN, AVERAGE Salary (EMPLOYEE)

For each employee, get the number of projects
and number of hours worked on projects.
For each employee, get the number of projects
and number of hours worked on projects.

Essn ℱCOUNT Pno, SUM Hours (WORKS_ON)

• 10 .Retrieve the names of employees who
have dependents.
• [Link] the names of employees who
have no dependents.
[Link] the names of employees who have
no dependents.
12. List the names of managers who have at
least one dependent.
12. List the names of managers who have at
least one dependent.
 Mapping conceptual
design into a logical
design
Relational Database Design Using
ER-to-Relational Mapping
 ER-to-Relational Mapping
Algorithm

Step 1: Mapping of Regular Entity Types

Step 2: Mapping of Weak Entity Types
Step 3: Mapping of Binary 1:1 Relation Types
Step 4: Mapping of Binary 1:N Relationship
Types.
Step 5: Mapping of Binary M:N Relationship
Types.
Step 6: Mapping of Multivalued attributes.
Step 7: Mapping of N-ary Relationship Types.
 Step 1: Mapping of Regular Entity
Types
• For each regular (strong) entity type E in the ER
schema, create a relation R that includes all the
simple attributes of E.
• Include only the simple component attributes of a
composite attribute.
• Choose one of the key attributes of E as the
primary key for R.
• example,
• we create the relations EMPLOYEE,
DEPARTMENT, and PROJECT to correspond
to the regular entity types EMPLOYEE,
DEPARTMENT, and PROJECT.
 Step 2: Mapping of Weak Entity Types

• For each weak entity type W in the ER schema

with owner entity type E, create a relation R and
include all simple attributes (or simple
components of composite attributes) of W as
attributes of R.

• Include as foreign key attributes of R, the

primary key attribute(s) of the relation(s) that
correspond to the owner entity type(s).
• example, create the relation DEPENDENT in this
step to correspond to the weak entity type
DEPENDENT.
• Include the primary key Ssn of the EMPLOYEE
relation—which corresponds to the owner entity
type—as a foreign key attribute of DEPENDENT;
• Rename it Essn.
 Step 3: Mapping of Binary 1:1
Relationship Types
• For each binary 1:1 relationship type R in the ER
schema, identify the relations S and T that
correspond to the entity types participating in R.
• There are three possible approaches:
(1) the foreign key approach,
(2) the merged relationship approach, and
(3)the cross reference or relationship relation
approach. The first approach is the most useful
• Foreign key approach:
• Choose one of the relations—S, say—and include
as a foreign key in S the primary key of T.
• Choose an entity type with total participation in R
in the role of S.
• Include all the simple attributes (or simple
components of composite attributes) of the 1:1
relationship type R as attributes of S.
• example, map the 1:1 relationship type
MANAGES by choosing the participating entity
type DEPARTMENT to serve in the role of S
because its participation in the MANAGES
relationship type is total .
• Include the primary key of the EMPLOYEE
relation as foreign key in the DEPARTMENT
relation and rename it to Mgr_ssn.
• Include the simple attribute Start_date of the
MANAGES relationship type in the
DEPARTMENT relation and rename it
Mgr_start_date
• Merged relation approach:
• An alternative mapping of a 1:1 relationship
type is to merge the two entity types and the
relationship into a single relation.
• This is possible when both participations are
total.
• Cross-reference or relationship relation
approach: The third option is to set up a third
relation R.
• The relation R will include the primary key
attributes of S and T as foreign keys to S and T.
• The primary key of R will be one of the two
foreign keys, and the other foreign key will be
a unique key of R.
Step 4: Mapping of Binary 1:N Relationship Types.
• The foreign key approach:
• For each regular binary 1:N relationship type
R, identify the relation S that represents the
participating entity type at the N-side of the
relationship type.
• Include as foreign key in S the primary key of
the relation T that represents the other entity
type participating in R;
• example, we map the 1:N relationship types WORKS_FOR,
CONTROLS, and SUPERVISION
 Step 5: Mapping of Binary M:N
Relationship Types
• For each binary M:N relationship type R, create
a new relation S to represent R.
• Include as foreign key attributes in S the
primary keys of the relations that represent the
participating entity types; their combination will
form the primary key of S.
• Also include any simple attributes of the M:N
relationship type (or simple components of
composite attributes) as attributes of S.
 Step 6: Mapping of Multivalued
Attributes.
• For each multivalued attribute A, create a new
relation R.
• This relation R will include an attribute
corresponding to A, plus the primary key attribute
K—as a foreign key in R—of the relation that
represents the entity type or relationship type that
has A as a multivalued attribute.
• The primary key of R is the combination of A and K.
• example, we create a relation DEPT_LOCATIONS.
Step 7: Mapping of N-ary Relationship
Types.
• Relationship relation option.
• For each n-ary relationship type R, where n > 2,
create a new relationship relation S to represent R.
• Include as foreign key attributes in S the primary
keys of the relations that represent the
participating entity types.
• The primary key of S is usually a combination of
all the foreign keys that reference the relations
representing the participating entity types.
The ER diagram for Movie database.
The ER diagram for Hospital database