1

INTRODUCTION

Data vs. Information:

Data (used as both singular and plural) is the known fact that can be recorded and have
implicit meaning.

Information is the refined data. When data is processed and presented in a form
suitable for human interpretation, it is called information. Data is the raw material and
information is the finished goods.

Data Processing Information

(I/P) (O/P)

For Example: A list of students showing Regd. No, Name, Address, Course, Marks
obtained in each paper is called student’s data.

List of students who secured more than 50% marks is information.

Data base: A collection of logically interrelated data stored together with controlled
redundancy to meet the needs of an organization is called database.

Example: University database, Banking database, Hospital database etc.

Components of Database:

 Data item: distinct piece of information

 Relationships: association between data items
 Constraints: Predicates that define correct database states
 Schema: description of the database

Database-management system (DBMS): It is a collection of interrelated data and a set

a programs to access those data. It is basically a computerized record keeping system
which stores information and allows users to add, delete, change, retrieve, and update
that information on demand.

𝐷𝑎𝑡𝑎𝑏𝑎𝑠𝑒 + 𝐷𝐵𝑀𝑆 𝑆𝑜𝑓𝑡𝑤𝑎𝑟𝑒 = 𝐷𝑎𝑡𝑎𝑏𝑎𝑠𝑒 𝑠𝑦𝑠𝑡𝑒𝑚

Example: Banking system is an example of DBMS which keeps information about the
customers and has a number of application programs:

 To open a new A/C.

 To debit or credit an A/C.
 To check balance
 To generate mini or, monthly statement etc

Dr. A. K. Panda
2

Advantages of DBMS:

 Redundancy can be reduced: In non database system or file processing system

each department or, application has its own files. Hence the same piece of
information is replicated in several files which is called data redundancy. There
are several disadvantages of data redundancy; First, valuable storage space is
wasted. Second, same data is entered into different files unnecessarily. Third,
inconsistency. In a database system, this consistency can be controlled.
 Inconsistency can be avoided: Data redundancy leads to data inconsistency.
When the same data is duplicated and changes are made at one site, which is not
propagated to the other site, it gives rise to inconsistency. Then the two entries
regarding the same data will not agree. At such times the data is said to be
inconsistent. Since data redundancy is controlled in DBMS, the database system
enforces consistency by updating each occurrence of a data item when change
occurs.
 Integrity can be maintained: Integrity means that data entered into the
database is both accurate and consistent. Therefore, data values being entered
for storage can be checked to ensure that they fall within a specified range and
are of the correct format. Centralized control of the data helps in permitting the
administrator to define integrity constraints to the data in the database.
 Data can be shared: A database system permits multiple users to share a
database concurrently.
 Security restrictions can be applied: Security is the protection of database
from unauthorized users. Data is very important to an organization and may be
confidential. Such confidential data must be accessed by authorized users.
Different authorization checks can be established by DBA for each type of access
(Retrieve, modify, delete, etc.) to every piece of information in the database.
 New applications can be developed easily: It reduces the cost and time for
developing new applications. Since the database is already designed and
implemented, the programmer develops only application programs to query the
database.
 Standard can be enforced: With the central control of the database, the DBA
can enforce standards. Applicable standards might include any of the following:
departmental, installation, organizational, industry, corporate, national or
international.

Sl. No File Management Database Management

1. It is a small system like a C++ or It is a large system like Oracle.
COBOL Program
2. It is relatively cheap. It is relatively expensive.
3. It has simple structure It has complex structure
4. It needs very little preliminary It needs vast preliminary design

Dr. A. K. Panda
3

design.
5. It is not secure It is more secure.
6. It is often single user oriented It is multiple user oriented.
7. It has isolated data It has shared data.
8. It has simple primitive It has complex and sophisticated
backup/recovery mechanism backup/recovery.

Characteristics of DBMS:

1. Self describing nature of DBMS: A database system contains not only the
database itself but also a complete definition or description of the database
structure and constraints. This definition is called metadata i.e. data about data
which is stored in a catalog called data dictionary. Hence data dictionary is a
data structure that stores metadata.
2. Data independence and data abstraction: In DBMS there is insulation between
data and programs called program-data independence. Hence data can be
changed without changing application programs. A DBMS provides users with a
conceptual representation of data that does not include many of the details of
how the data is stored or how the operations are implemented. This is called
program-operation independence. The characteristic that allows program-data
independence and program-operation independence is called data abstraction.
3. Support of multiple views of the data: A database typically has many users,
each of whom may require a different perspective or view of the database. A
view is a virtual data that is derived from the database files. Users may not need
to aware of whether the data they refer to is stored derived. A multiuser DBMS
provides different views for multiple users of the same database.
4. Data sharing and multiuser transaction processing: A multiuser DBMS allow
multiple users to access the database at the same time. A concurrency control
s/w is loaded to control multiple transactions.

Components of DBMS:

The database management system can be divided into five major components, they are:

1. Hardware: Hardware consists of hard disks, I/O channels for data, and any
other physical component involved before any data is successfully stored into
the memory.
2. Software: It is a set of programs which is used to work with such hardware
3. Data: It is the fact that can be recorded.
4. Procedures: It is the set of instructions in a certain order to achieve desired
results.
5. Database Access Language: It is a simple language designed to write
commands to access, insert, update and delete data stored in any database.

Dr. A. K. Panda
4

People in the Database Environment:

1. Data Base Administrator (DBA):

An individual person or group of persons having central control over DBMS is called
DBA. They are the persons who are most familiar with the database and responsible for
creating, modifying and maintaining three levels of database. The DBA is also
responsible for authorizing access to the database, coordinating and monitoring its use
and acquiring software and hardware resources as needed.

Functions of DBA:

 Defining conceptual schema and database creation

 Storage structure and access method definition
 Granting authorization to the users
 Physical organization modification
 Routine maintenance: making periodical back-ups of the database
 Job monitoring: making appropriate adjustment or tuning of the database.

2. Database Designers:

There are two types of data base designers:

1. Logical Database Designer: The logical database designer is concerned with

identifying the data (i.e. the entities and attributes), the relationships between
the data, and the constraints on the data that is to be stored in the database. The
logical database designer must have a thorough and complete understanding of
the organization’s data and its business rules.
2. Physical database designer: The physical database designer decides how the
logical database design is to be physically realized. This involves:
 Mapping the logical database design into a set of tables and integrity
constraints;
 Selecting specific storage structures and access methods for the data to
achieve good performance.
 Designing any security measures required on the data.

3. Application Programmers:

Application programmers write database application programs that provide the

required functionality for the end-users. They work from a specification produced by
the system analysts. Each program contains statements that request the DBMS to
perform some operation on the database.

4. End-Users:

The end-users are the clients for the database, which has been designed and
implemented. There are two types of end-users:

Dr. A. K. Panda
5

1. Naïve users: There users are typically unaware of the DBMS. They access the
database through specially written application programs. They invoke database
operations by entering simple commands or choosing options from the menu.
They do not know anything about the database.
2. Sophisticated users: These users are familiar with the structure of the database
and the facilities offered by the DBMS. Sophisticated users may use a high level
query language such as SQL to perform the required operation.

DATA BASE SYSTEM ARCHITECTURE

There are two types of architectures:

 Two-tier architecture: In this type of architecture, the application is partitioned

into a component that resides at the client machines, which invokes database
system functionality at the server machine through query language statements.
Application program interface standards are used for interaction between the
client and the server.
In 1971, Database Task Group (DBTG) proposed a two-tier architecture

 Three-tier architecture: In this type of architecture, the client machine acts as

a front-end and does not contain any database calls. The client end
communicates with an application server, usually through a forms interface. The
application server in turn communicates with a database system to access data.
This type of architecture is appropriate for large applications and for
applications that run on the World Wide Web (WWW). In 1975, ANSI-SPARC
(American National Standards Institute- Standards Planning and Requirements
committee) produced three-tier architecture.

Schema, Subschema and Instances:

Schema: The overall description of the database is called as database schema. It is also a
plan or outline that describes the records at a particular level.

Employee

EMP_ID ENAME ADDRESS SEX BASIC DEPT_ID

Department

DEPT_ID DNAME LOCATION

Fig: Schema diagram

Dr. A. K. Panda
6

Subschema: A subschema (or, scheme) is a subset of the schema and inherits the same
property that a schema has. It is an application programmer’s or, user’s view of the data
item types and record types. It gives the users a window through which he or, she can
view only part of the databases.

ENAME ADDRESS SEX BASIC

EMP_ID ENAME ADDRESS DEPT_ID DNAME

Fig: Subschema viewed by two application programs derived from above schema.

Instance: The collection of information stored in the database at any point of time is
called as an instance of the database.

DEPT_ID DNAME LOCATION

001 MCA East
002 MBA North
003 Humanities Central

Fig: Instances of Department table.

Three Level Architecture/ 3-tier Architecture/ ANSI-SPARC Database

Architecture:

In 1975, ANSI-SPARC (American National Standards Institute- Standards Planning and

Requirements committee) produced three-tier architecture. The crucial feature of this
architecture is concept of schema.

The architecture is divided into three levels:

 External level or external schema

 Conceptual level or conceptual schema
 Internal level or internal schema

Dr. A. K. Panda
7

External External External

External Level
Schema Schema
… Schema

External-Conceptual Mapping Logical data Independence

Conceptual Level Conceptual Schema

Conceptual-Internal Mapping Physical data Independence

Internal Level Physical Schema

Physical Data
Organization Database

1. External Level: This level describes the part of the database that is relevant to
each user.
2. Conceptual level: This level describes what data is stored in the database and
the relationships among the data.
3. Internal Level: This level describes how data is stored in the database.

Data Independence:

It means that upper levels are unaffected by changes in lower levels. It is achieved
through use of three levels of data abstraction.

There are two types of data independence:

1. Physical data independence: It indicates that physical storage structure or

devices used for storing data can be changed without affecting the conceptual
schema or, any of the external views. This change is absorbed by
conceptual/internal mapping.
2. Logical data independence: It means that conceptual schema can be changed
without affecting the existing external schemas. Users are shielded from change
in the logical structure of the data. Changes to conceptual schema , such as the
addition and deletion of entries, addition and deletion of attributes, or addition
and deletion of relationships are possible without changing existing external
schemas or having to rewrite application programs.

Dr. A. K. Panda
8

Note: It is difficult to achieve logical data independence than physical data

independence because logical data independence requires flexibility in the design of
database and the programmer has to foresee the future requirements or
modifications in the design.

Difference between Physical data independence & Logical data Independence:

Physical data Independence Logical data Independence

It is the ability to modify the physical It is ability to modify the conceptual
schema without causing application schema without causing application
programs to be rewritten. programs to be rewritten.
Modifications at this level are necessary Modifications at this level are necessary
to improve performance whenever the logical structure of the
database is altered.
It is not difficult to be achieved. It is more difficult to be achieved
because application programs are
dependent on the logical structure of the
data that they access.
It provides immunity of conceptual or It provides immunity of external
external schemas. schemas or application programs.

DATA MODEL

It is a collection of conceptual tools for describing data, data relationships, data

semantics (Integrity) and consistency constraints.

Basically there are 3 types of data models:

1. Conceptual data model/object based data model: It focuses on logical nature

of the data representation. It is concerned with what is represented in the in the
database rather than how it is represented. It uses the concept of entities,
attributes, and relationships. EX: ER model, object-oriented data model.

ER Model: It is a detailed logical representation of data for an organization. The

E-R model is expressed in terms of entities, the relationships (or, associations)
among those entities and the attributes (or properties) of both the entities and
their relationships. An E-R model is normally expressed as an entity-relationship
diagram (or E-R diagram or ERD) which is a graphical representation of an E-R
model.
Object-oriented Data Model: The Object-Oriented Model in DBMS is the data
model where data is stored in the form of objects. This model is used to
represent real-world entities. The data and data relationship is stored together
in a single entity known as an object in the Object Oriented Model.

Dr. A. K. Panda
9

Data Model

Conceptual Physical Implementation

Model Model Model

Hierarchical Network Relational

Model Model Model

2. Physical data model: It provides concepts that describe the details of how data
is stored in the computer. Concepts provided by physical data models are
generally meant for computer specialists, not for the typical end-users. Physical
data models describes how data is stored as files in computer by representing
information such as record format, record orderings, and access paths. EX:
unifying model, frame memory model.

3. Implementation/representational/ record based data models: It provides

concepts that may be understood by the end users and also contain how data is
organized within computer. This model hides some details of data storage but
can be implemented in a direct way. EX: Hierarchical model, Network Model,
Relational model.

Hierarchical Model:

A hierarchical data model is a data model which the data is organized into a tree like
structure with one-to-many relationships between different types of data. The structure
allows repeating information using parent/child relationships: each parent can have
many children but each child only has one parent. All attributes of a specific record are
listed under an entity type.

Dr. A. K. Panda
10

Network Model:

The data in the network model are represented by collection of records and
relationships among data are represented by links, which can be viewed as pointers.
The main difference between this model and the hierarchical model is that any record
can have several parents in the network model. It uses a graph instead of a hierarchical
tree. This data model is used to map many-to-many relationship.

Relational Model:

The Relational Model uses a collection of tables both data and the relationship among
those data. Each table have multiple columns and each column has a unique name.

ENTITY-RLATIONSHIP MODEL

An entity-relationship model is a popular high level conceptual data model. It is a

detailed logical representation of data for an organization. The E-R model is expressed
in terms of entities, the relationships (or, associations) among those entities and the
attributes (or properties) of both the entities and their relationships. An E-R model is
normally expressed as an entity-relationship diagram (or E-R diagram or ERD) which is
a graphical representation of an E-R model.

Components of E-R model:

 Entities
 Attributes
 Relationships

Entity: An entity is a person, place, object, event or concept that is uniquely identifiable.
An entity is called entity instance or entity occurrence.

Entity type (or set): It is a collection of entities that share common properties or
characteristics.

Representation of an entity type in ERD:

Example: Person: EMPLOYEE, STUDENT, PATIENT

Dr. A. K. Panda
11

Place: STORE, WAREHOUSE, STATE

Object: MACHINE, BUILDING, AUTOMOBILE

Event: SALE, REGISTRATION, RENEWAL

Concept: ACCOUNT, COURSE, WORK CENTRE

Attribute: An attribute is a property or characteristic of an entity type that is of interest

to the organization.

Representation of an attribute in ERD:

Example:

Entity Type Associated attributes

EMPLOYEE Emp-id, Ename, Address, Basic, Date- of- birth, Skill
STUDENT Regd-no, Name, Address, Date-of-birth, Father’s-name,
AUTOMOBILE Vehicle-No, Engine-No, Chesses-No, Color, Weight,
Horsepower

Classification of attributes:

Simple vs. Composite Attribute:

An attribute that cannot be broken down into smaller components that are meaningful
for the organization is called simple attribute or atomic attribute.

Example: Emp-id, age, Basic, color, horsepower etc.

An attribute composed of multiple components, each with an independent existence is

called composite attribute.

Name: First-Name, Middle-Name, Last-Name

Address: Plot-No, Area, Locality, PO, City, Pin

Date of birth: Day, Month, Year

Representation of Composite attribute:

Dr. A. K. Panda
12

Single-valued vs. Multivalued attribute:

An attribute that holds a single value for a single entity is called single-valued attribute
and an attribute that holds multiple values for a single entity is called Multivalued
attribute.

Example: Single-valued: Empid, Ename, Basic etc.

Multivalued: Degree, Skill, hobby, Telephone-no etc.

Representations of Multivalued attribute:

Stored vs. Derived Attribute:

An attribute whose value is derived from value of another attribute is called derived
attribute and from which it is derived is called stored attribute.

Example: Stored: Date-Of-Birth, Basic, Date-Of-Joining

Derived: Age, Gross-salary, Experience

Representation of derived attribute:

Required vs. Optional Attribute:

An attribute that must be present for each entity instance is called a required attribute,
whereas an attribute that may not have a value is called an optional attribute.

Example: Required: Roll-No, Name, Fathers’-Name

Optional: Hons, Spouse-Name

Representation of Required attribute: *

Attribute Domain: Every attribute has a domain. A domain determines the type of data
values that are permitted for that attribute.

Dr. A. K. Panda
13

KEYS:

 Super Key: An attribute or, a set of attributes that uniquely identifies an entity
in the entity type is called Super Key.
 Candidate Key: A super key is said to be a candidate key if no proper subset of it
is a super key. That means minimal super key is called candidate key.
 Primary Key: An entity type may have one or more possible candidate keys, one
of which is selected to be primary key. Database designer selects one of the
candidate key as primary key.
 Composite key or concatenated key: A primary key that consists of two or
more attributes is called a composite key.
 Alternate key: A candidate key that is not selected as primary key is called an
alternate key.
 Secondary key: An attribute or, a set of attributes that is used to identify the
entities which have a certain property is called secondary key.

Relationship:

It is an association between instances of one or more entity types that is interest to the
organization.

Relationship type:

It is a meaningful association between entity types.

Representation of relationship type in ERD:

Degree of a Relationship:

It is the number of entity types that participate in that relationship. The three most
common relationship degrees in E-R models are unary (degree 1), binary (degree 2),
and ternary (degree 3).

 Unary Relationship (or recursive relationship): It is a relationship between

the instances of a single entity type.

PERSON
EMPLOYEE

Is married
to
Manages

 Binary Relationship: It is relationship between the instances of two entity types

and is the most common type of relationship encountered in data modeling.

Dr. A. K. Panda
14

EMPLOYEE Works for DEPARTMENT

STUDENT Registers
COURSE
for

 Ternary relationship: It is a simultaneous relationship among the instances of

three entity types.

Quantity

VENDOR Supplies WAREHOUSE

PART

Hours

SUBJECT Teaches STUDENT

TEACHER

Structural Constraints:

There are certain constraints which may be placed on participating entities in a

relationship.

1. Cardinality Constraint:

It specifies the number of instances of one entity that can be associated with each
instance of another entity. There are three basic types of cardinality constraints:

 One-to-one (1:1): A relationship is said to be on-to-one if one instance of an

entity type A is associated with one other instance of another entity type B.

Dr. A. K. Panda
15

1 1
A R B

 One-to many (1: N): A relationship is said to be one-to-many if one instance of an

entity type A is associated with zero, one or many instances of another entity
type B, but for one instance of entity type B there is only one instance of entity
type A.
1 N
A R B

 Many-to-many (M:N): A relationship is said to be many-to-many if one instance

of an entity type A is associated with one, zero or many instances of another
entity type B, and one instance of entity type B is associated with one, zero or
many instances of entity type A.

M N
A R B

2. Participation Constraint:
It specifies whether the existence of an entity depends on its being related to
another entity via the relationship type. There are two types of participation
constraints:

The participation is said to be total (mandatory) if an entity’s existence requires the

existence of an associated entity in a particular relationship.

The participation is said to be partial (Optional) if the occurrence of one entity does not
require the occurrence of another corresponding entity in a relationship.

Representation partial participation:

Example:

EMPLOYEE Claims DEPENDENT

3. MIN/MAX Constraints:
The participation of an entity type in relationship type can be associated by a
pair of integers (MIN, MAX) as follows:

(MIN, MAX)
A R

Dr. A. K. Panda
16

It means that each entity instance of the entity type A participates in at least MIN
and at most MAX relationship instances at any point of time.

Note: If MIN = 0, then the participation is partial and if MIN > 0, then the
participation is total.

Example:

(1, 1) (4, N)
EMPLOYEE Works for DEPARTMENT

Each employee works for at least one department and at most one department and
each department have at least 4 employees and at most unlimited employees.

Weak entity types:

The entity type that does not have sufficient attributes to form a primary key is
called a weak entity type. On the other hand, an entity type that has a primary key is
called strong entity type.

Note: The participation of weak entity type is always total but the converse is not
true.

Representation of weak entity type in ERD:

Example:
EMPLOYEE Claims DEPENDENT

Identifying Relationship:

A relationship in which the primary key of the parent entity is used as a part of the
primary key of the dependent entity is called identifying relationship.

Representation in ERD:

Partial Key:

It is a set of attributes that uniquely identify weak entities that are related to the
same owner entity.

Dr. A. K. Panda
17

Representation in ERD:

Example:

City
Street
Ename
Sex
Empid State Dname Birth date
Addres
s (1, 1)
(0, N)
EMPLOYEE Claims DEPENDENT

Notations used in ER diagrams:

Sl. Symbol Meaning

No.
1. Entity type

2. Weak Entity type

3. Attribute

4. Multi-valued Attribute

5. Derived Attribute

6. Primary key Attribute

7. Partial key Attribute

…
8. Composite Attribute

9. Relationship

10. Identifying Relationship

11. Link between attribute and

entity type
E R
12. Partial participation of E in R

Dr. A. K. Panda
18

13. E R Total participation of E in R

1 1
14. E1 R E2 One-to-One relationship

1 N
15. E1 R E2 One-to-Many relationship

M N
16. E1 R E2 Many-to-Many relationship

(MIN, MAX)
17. E R MIN/ MAX Constraint

Example:

Draw an ER diagram of book club. The book club has members. The book club sells
books to its members. The members place orders for books, which the book club
fulfils. Each order contains one or more than one book. An author can write more
than one book and a book can have more than one author. A book is published by a
publisher but a publisher publishes many books. The book club sells many books.

(1, 1) (1, N)
MEMBER Enrolls in BOOK_CLUB

(0, N) (1, N) (1, N)

AUTHOR
Fulfils
Places
Sells (1, N)

(1, 1)
(1, 1) (1, N)
(1, 1)
ORDER
BOOK Writes
(1, 1)
(1, N)
(1, 1)

Publishes

(1, N)

Contains PUBLISHER
Dr. A. K. Panda
 19

Example: ER diagram of Project handling company.

Locality City Locality City

State StreetNo State

PlotNo
Start-date
Address Location

Ename Sex Cname

Experience Comp-id No-of-Emp

Emp-id
(0, 1) (1, 1)
Manages
EMPLOYEE COMPANY
(1, 1) (M, N)

1 N Works for (0, N)

(1, N)

Controls

(1, 1)
Supervises (1, N)
Works on PROJECT

Proj-id Location

Hours Pname

Dr. A. K. Panda
 20

Example: ER diagram of banking organization.

Locality City

Plot-No State
Locality City

Address Plot-No State

Cname Sex Type Address Ename

Cust-id Emp-id experience

M N
CUSTOMER Cust-Banker EMPLOYEE Manages
1

1
N
Balance
Deposits ACCOUNT
A/C-No
N

Borrows
Transaction-Date

Opens

N 1
Loan-No N 1
LOAN Loan-branch BRANCH
Amount 1

Branch-Name Assets

City

Loan
Payment

PAYMENT

Payment-No Payment-Date

Payment-Amount

Dr. A. K. Panda
21

Example: ER diagram of Order Management System

Example: ER diagram of Library management System

Dr. A. K. Panda
22

ENHANCED ENITY RELATIONSHIP (EER) MODEL

The EER model consists of all the concepts of E-R model together with the following
additional concepts:

 Specialization
 Generalization
 Categorization

Subtype or, Subclass: It is a sub-grouping of the entities in an entity type that is

meaningful to the organization and that shares common attributes or relationships
distinct from other sub-groupings.

Supertype or, Superclass: It is a generic entity type that has a relationship with one or
more subtypes.

Example:

Employee: (Full Time Employee, Part time Employee, Consultant)

Account: (SB A/C, Current A/C, Loan A/C, RD A/C, FD A/C)

Notation of Supertype/Subtype relationships:

Shared Attributes

SUPERTYPE

SUBCLASS-1 SUBCLASS-2 …… SUBCLASS-n

Unique attributes Unique attributes

Unique attributes

Dr. A. K. Panda
23

Attribute Inheritance:

It is a property by which subtype entities inherit values of all attributes and instance of
all relationships of the Supertype.

Specialization:

It is a top-down process. It is a process of defining one or more subtypes of the

Supertype and forming Supertype / subtype relationships.

Pname S
Patient-id Admin-Date P
G E
E C
PATIENT
N I
E A
R L
A I
L Z
I A
Z T
INPATIENT OUT-PATIENT
A I
T O
I N
O
N Check-back-Date Date-discharged

Generalization:

It is a bottom-up process. The reverse process of specialization is called generalization.

It is a process of defining a more general entity type from a set of more specialized
entity types.

Specifying Constraints on Specialization and Generalization:

The two most important types of constraints are:

 Participation constraint
 Disjointness constraint

Dr. A. K. Panda
24

Participation Constraint:

It is a type of constraint that addresses the question whether an instance of a Supertype

must also be a member of at least one subtype. There are two types of participation
constraints:

 Total Participation
 Partial participation

Total participation constraint: It specifies that each entity of the supertype must be a
member of some subtype in the Specialization/ Generalization.

Representation in ERD:
SUPERTYPE

Example:
Ename

Empid Address

EMPLOYEE

FULL TIME EMP HOURLY EMP CONSULTANT

Annual-Salary Hourly-rate Contract-no Billing-rate

Partial Participation Constraint:

It specifies that a member of the Supertype need not belong to any of its subtypes of a
specialization/generalization.

Representation in ERD: SUPERTYPE

Dr. A. K. Panda
25

Example:

Make Model

V-Name Engine-No
Vehicle-No Chassis-No

VEHICLE

BUS TRUCK BIKE

No-of-Passengers Capacity Type

Disjointness Constraint:

It is a type of constraint that addresses the question whether an entity of a Supertype

may simultaneously be a member of two or more subtypes. There are two types of
Disjointness constraints:

 Disjoint Constraint
 Overlapping constraint

Disjoint Constraint:

It specifies that an entity of a Supertype is a member of at most one of the subtypes.

Representation in ERD:
SUPERTYPE

Dr. A. K. Panda
26

Example:

Name

A/C-No Address

ACCOUNT

SAVING A/C CURRENT A/C LOAN A/C

Min-Balance Overdraft-Amt EMI

Overlapping Constraint:

It specifies that an entity of a Supertype may simultaneously be a member of two or

more subtypes.

Representation in ERD:
SUPERTYPE

Example:

Ename Description
Empid Salary Part-No Type

EMPLOYEE PART

O
O

MANUFACURED PART PURCHASED PART

UNION MEMBER CLUB MEMBER

Routine-No Unit-Price

Dr. A. K. Panda
27

Hence, we have following four possible constraints on specialization/generalization:

 Disjoint, total
 Disjoint, partial
 Overlapping, total
 Overlapping, partial

Supertype/ subtype hierarchy:

It is a hierarchical arrangement of supertypes and subtypes, where each subtype has

only one supertype.

Example:
Name
Person-id Address

PERSON

O
Major
Date-hired

EMPLOYEE ALUMNUS STUDENT

Salary Degree Regd-No

d d

Year
Section
Regd-no
FACULTY STAFF GRADUATE UNDER GRADUATE

Rank Position
CGPA Percentage

Categorization:

It is the process of modeling of a single subtype (or subclass) with a relationship that
involves more than one distinct supertype (or superclass).
…
Representation in ERD: Supertype-1 Supertype-2 Supertype-n

SUBTYPE Dr. A. K. Panda

 28

Example:
EMPLOYEE DEPARTMENT COMPANY

OWNER

Example: EER diagram of Hospital database

Total-Cost
I-code Unit-Price
Name
T-Code Price
N
Is billed ITEM
for TEST

Name Specialty
Name
Phy-id
Patient-id Admit-date Tel-No
M
PATIENT Advices PHYSICIAN

Age [Link]
Name
d
Prescribes
DRUG
OUT-PATIENT IN-PATIENT 1
Date Quantity N

Company
Checkbackdate Discharge-date

Is assigned Price Sells

Time

[Link] Name
Type 1 Price

ROOM PHARMACY
Treat-Code Room-No Bed-No
Roomid

TREATMENT Treats

Date Result

Description Time

Dr. A. K. Panda
 RELATIONAL DATA MODEL

The relational model was first introduced in 1970 by Dr. E. F. Codd of IBM. The relational model
represents data in the form of tables.

Terminologies related to relational model:

 Relation: It is a named two dimensional table of data with rows and columns.
 Attribute: It is a named column of a relation.
 Domain: It is a set allowable value of an attribute.
 Tuple: It is a row of a relation.
 Degree: The degree of a relation is the no. of attributes it contains.
 Cardinality: The cardinality of a relation is the number of tuples it contains.
 Relational Database: It is a collection of normalized or structured relations with distinct
relation names.

Types of Keys:

 Super key: An attribute or, a set of attributes that uniquely identifies a tuple with in a
relation is called Super Key.
 Candidate Key: A super key is said to be a candidate key if no proper subset of it is a
super key. That means minimal super key is called candidate key.
 Primary Key: A relation may have one or more possible candidate keys, one of
which is selected to be the primary key. Database designer selects one of the candidate key
as primary key.
 Composite key or concatenated key: A primary key that consists of two or more
attributes is called a composite key.
 Alternate key: A candidate key that is not selected as primary key is called an
alternate key.
AK = CK - PK
 Secondary key: An attribute or, a set of attributes that is used to identify the entities
which have a certain property is called secondary key.
 Foreign key: An attribute in a relation that serves as the primary key of another relation is
called in the same database is called foreign key.

Properties of relations:

1. Each relation (or table) in a database has a unique name.

Dr. A. K. Panda
 2. An entry at the intersection of each row and column is atomic (or single valued). There can
be no multivalued attribute in a relation.
3. Each row is unique; no two rows in a relation are identical.
4. Each attribute (or column) within a table has a unique name.
5. The order of the attributes (left to right) has no significance. The columns of a relation can
be interchanged without changing the meaning or use of the relation.
6. The order of the tuples has no significance. The rows of a relation may be interchanged or
stored in any sequence.

Integrity Constraints:

Relational data model includes several constraints whose purpose is to maintain the accuracy and
integrity of the data in the database. The major types of integrity constraints are:

 Domain constraint (Check): It specifies that the value of each attribute A must be atomic
value from the domain of A.
 Key constraint (unique): It specifies that all tuples in a relation must be distinct.
 Entity Integrity constraint (not null): It specifies that primary key cannot accept null
values.
 Referential Integrity Constraint (Foreign key): It specifies the value of the referencing
attribute (Foreign key) is either null or it is equal to value of the referenced attribute.

Example:

Referencing Relation: EMPLOYEE (Emp-id, E-name, Address, Dept-id)

Referenced relation: DEPT (Dept-id, D-name, Location)

In the referencing relation EMPLOYEE, value of the referencing attribute Dept-id is either null or it takes
any value of the Dept-id column in DEPT relation.

Query Languages:

A query language is a language in which user requests information from the database. Query languages
can be categorized as either procedural or non-procedural.

 Procedural language: In a procedural language the user instructs the system to perform a
sequence of operations on the database to compute the desired result (e.g. relational algebra).
 Non-procedural language: In a non-procedural language, the user describes the desired
information without giving a specific procedure for obtaining that information (e.g. tuple calculus
and domain calculus).

Dr. A. K. Panda
 RELATIONAL ALGEBRA

It is a procedural query language. It consists of a set of relational operators that takes one or more
relations as input and produces a new relation as its result.

Different relational algebraic operations:

 Unary operations:
1. Select ()
2. Project ()
3. Assignment ()
4. Rename()
 Binary operations:
 Set theoretic operations:
5. Union (U)
6. Intersection()
7. Difference (-)
8. Cartesian product (×)
 Other binary operations:
9. Join (⋈)
10. Division(÷)

Selection operation ():

The select operator () is used to extract specified rows from a table that satisfies a selection condition.
The result of it is a horizontal subset of the relation.

General form: <selection condition>(R)

Example:

Consider the following schema of a relational database:

Employee (Emp-no, Name, Sex, address, Salary, Dept-no)

Dept (Dept-no, D-name, Location)

Express the following queries in relational algebra:

Q: Get the employees whose salary is less than 10,000.

Salary > 10000 (Employee)

Q: Get the information of all female employees:

Sex = ‘f’ (Employee)

Dr. A. K. Panda
 Q: Get all departments of location north:
Location = ‘north’ (Dept)

Projection operation ():

The project operator () is used to extract specified columns from a table. The result of it is a vertical
subset of the relation.

General form: <attribute list> (R)

Example:

Q: Get the name of all employees:

Name (Employee)

Q: Get the name and address of all employees:

Name, Address (Employee)

Q: Get the name and address of all female employees:

Name, Address (Sex = ‘f’ (Employee))

Assignment operation ():

The assignment operator () is used to assign part of a relational expression into temporary relation
variable. This relation variable may be used in subsequent expressions.

General form: <relation variable>  <relational expression>

Example:

Q: Get the name and address of all female employees who work in dept-no 5:

R1  (Sex = ‘f’)  (Dept-no = 5) (Employee)

Result   Name, Address (R1)

Rename operation ():

The rename operator () is used to rename either the relation names or, the attribute names or, both.

General form 1: S(R): It returns the relation R under a new name S.

S (E) : It returns the result of expression E under the name S.

Dr. A. K. Panda
 General form 2: (B1, B2, …, Bn) (R): It renames attribute Ai as Bi for i = 1 to n.

General form 3: S (B1, B2, … , Bn) (R): It renames attribute Ai as Bi for i = 1 to n and relation R as
S.

Example:

Q: Rename relation Employee as EMP:

Emp (Employee)

Q: Rename D-name as Name and Location as Loc in Dept relation:

(Dept-no, Name, Loc) (Dept)

Q: Find the name and salary of all employees and rename the new relation as Esal and name as
Ename and salary as sal.

Esal (Ename, sal) (Name, Salary (Employee))

Union operation (U):

The union, intersection and difference operations between two relations R 1 and R2 are valid if the
following conditions are satisfied.

1. R1 and R2 must have same number of attributes.

2. The domain of the ith attribute of R1 and the ith attribute of R2 must be same for all i.

The union of two relations R1 and R2 denoted by R1 U R2 is a relation that includes all tuples that appear
either in R1 or, in R2 or, in both.

R1 Emp-no Name Phone R2 Emp-no Name Phone

001 Ashok 9437091129 002 Satya 9437229391

002 Satya 9437229391 004 Ansuman 9439916463

003 Sunil 8895730489 006 Pranab 9861103311

008 Deepak 9437286097

Dr. A. K. Panda
 R 1  R2 Emp-no Name Phone

001 Ashok 9437091129

002 Satya 9437229391

003 Sunil 8895730489

004 Ansuman 9439916463

006 Pranab 9861103311

008 Deepak 9437286097

Intersection operation ():

The intersection of two relations R1 and R2 denoted by R1  R2 is a relation that includes only those tuples
that appear in both of R1 and R2.

R1  R2 Emp-no Name Phone

002 Satya 94372293

91

Set difference operation ( - ):

The difference of two relations R1 and R2 denoted by R1 - R2 is a relation that includes only those tuples
that appear in R1 but not in R2.

R1 - R2 Emp-no Name Phone

001 Ashok 9437091129

003 Sunil 8895730489

Note: Difference operation is non-commutative and non-associative.

Cartesian Product operation (×):

The Cartesian product (×) of two relations is the concatenation of tuples belonging to two relations.

If No. of attributes of R1 = x and No. of attributes of R2 = y then No. of attributes of R1 × R2 = x + y.

If No. of tuples of R1 = m and No. of tuples of R2 = n then No. of tuples of R1 × R2 = mn.

Dr. A. K. Panda
 R1 Emp-no Name Phone R3 Dept-no D-name
001 Ashok 9437091129 D1 Mca
002 Satya 9437229391 D2 Mba
003 Sunil 8895730489

R1 × R3 Emp-no Name Phone Dept-no D-name

001 Ashok 9437091129 D1 Mca

001 Ashok 9437091129 D2 Mba

002 Satya 9437229391 D1 Mca

002 Satya 9437229391 D2 Mba

003 Sunil 8895730489 D1 Mca

003 Sunil 8895730489 D2 Mba

Example:

Consider the following schema of a relational database:

Consider the following schema of a relational database:

Employee (Emp-no, Name, Sex, address, Salary, Dept-no)

Dependent (Emp-no, D-name, sex)

Express the following queries in relational algebra:

Q: Get all female employee names and their dependent names:

R1  sex = ‘f’ (Employee)

R2  Emp-no, Name (R1)

R3  R1 × R2

R4   Employee. Emp-no = Dependent. Emp-no (R3)

Result  Name, D-name (R4)

Dr. A. K. Panda
Join operation (⋈):

The join operator (⋈) is used to combine related tuples from two relations into single tuples. It is the
combination of Cartesian product and selection. There are various forms of join operations such as theta
join, equijoin, natural join, semi join, and outer join.

1. Theta () join:

Theta join (-join) is used to define a relation that contains tuples satisfying the predicate F from the
Cartesian product of two relations.

General Form:

R ⋈ R.a  S.b S , where  stands for some comparison operator like =, , , , , .

R ⋈ R.a  S.b S   R.a  S.b (R × S)

2. Equijoin:

It is a special case of -join. If the -operator is “=” then it is called equi-join.

Example:

Consider the following schema of a relational database:

Employee (Emp-no, Name, Sex, address, Salary, Dept-no)

Dependent (Emp-no, D-name, sex)

Dept (Dept-no, D-name, location)

Express the following queries in relational algebra:

Q: Get all female employee names and their dependent names:

R1  Employee ⋈ Employee. Emp-no = Dependent. Emp-no Dependent

R2  sex = ‘f’ (R1)

Result  name, D-name(R2)

Q: Get the name of all employees who work for the department located at south.

R1  Employee ⋈ Employee. Dept-no = Dept. Dept-no Dept

R2  location = “South” (R1)

Result  name (R2)

Dr. A. K. Panda
 3. Natural Join (⋈):

The natural join operator performs a Cartesian product of two relations, performs a selection forcing
equality on those attributes that are common to two relations and finally removes duplicate attributes. It
performs an equijoin over all the attributes in two relations that have the same name.

General form: R⋈S

If degree of R = m and degree of S = n then degree of R ⋈ S = m + n – c, where c is the number of common

attributes.

Example:

R A B C S C D E A B C D E
R⋈ S
a1 b1 c1 c1 d1 e1 a1 b1 c1 d1 e1
a2 b2 c2 a3 b3 c3 d2 e2
c3 d2 e2
a3 b3 c3
c4 d3 e3
a5 b4 c5
c6 d4 e4

Example:

Express the following queries in relational algebra for the given schema of the above example:

Q: Get all female employee names and their dependent names:

R1  Employee ⋈ Dependent

R2  sex = ‘f’ (R1)

Result  Name, D-name (R2)

Q: Get the name of all employees who work for the department located at north.

R1  Employee ⋈ Dept

R2  location = “North” (R1)

Result  Name (R2)

4. Semi join (⊳):

The semi join operator (⊳) performs a natural join of two relations and then projects over the attributes
of the first operand. The advantage of semi join is that it decreases the number of tuples that need to be
handled to form the join.
Dr. A. K. Panda
 General form: R⊳S

R ⊳ S  A (R ⋈ S), where A is the set of attributes of R.

Example:

R A B C S C D E A B C
R⊳S
a1 b1 c1 c1 d1 e1 a1 b1 c1
a2 b2 c2 a3 b3 c3
c3 d2 e2
a3 b3 c3
c4 d3 e3
a5 b4 c5
c6 d4 e4

Example:

Express the following query in relational algebra for the given schema of the above example:

Q: Get the information of all employees who work for the department located at north.

R1   location = “North” (Dept)

Result  Employee ⊳ Dept

5. Outer join:

The outer join operation is an extension of the join operation to deal with missing information. There are
three forms of the operation: left outer join ( ), right outer join (⋉) and full outer join ( ).

a) Left outer join ( ):

The left outer join ( ) is a join in which the tuples from the left relation that do not have matching values
in the common attributes of the right relation are also included in the result relation. Missing values in
the right relation are set to null.

b) Right outer join ( ):

The right outer join ( ) is symmetric with the left outer join. It is a join in which the tuples from the
right relation that do not have matching values in the common attributes of the left relation are also
included in the result relation. Missing values in the left relation are set to null.

c) Full outer join ( ):

R S = (R S) U (R S).

Dr. A. K. Panda
A left outer join keeps every tuple in the left relation in the result. Similarly, a right outer join keeps every
tuple in the right relation in the result. A full outer join keeps all tuples in the both relations, padding
tuples with nulls when no matching tuple are found.

Example:

R A B C S C D E A B C D E
R⋈ S
a1 b1 c1 c1 d1 e1 a1 b1 c1 d1 e1
a2 b2 c2 a3 b3 c3 d2 e2
c3 d2 e2
a3 b3 c3
c4 d3 e3
a5 b4 c5
c6 d4 e4

R S A B C D E

a1 b1 c1 d1 e1

a2 b2 c2 Null null

a3 b3 c3 d2 e2

a5 b4 c5 Null null

R S A B C D E
R S A B C D E
a1 b1 c1 d1 e1
a1 b1 c1 d1 e1
a3 b3 c3 d2 e2 a2 b2 c2 Null null
Null Null c4 d3 e3 a3 b3 c3 d2 e2
Null Null c6 d4 e4 a5 b4 c5 Null null

Null Null c4 d3 e3

Null Null c6 d4 e4

Dr. A. K. Panda
Division operation ():

The division relation divides a dividend relation R of degree (m + n) by a divisor relation S of degree n
and produces a resultant relation of degree m.

Let Z be the set of attributes of R and X be the set of attributes of X, then set of attributes of R  S is Z – X.
A tuple t is in R  S if for every tuple ts in S there is a tuple tr in R satisfying the following two conditions:

tr [X] = ts [X]
tr [Z – X] = t [Z – x]

This means that the tuple t will appear in R  S if t appears in R in combination with every tuple in S.

R A B S B RS A
a1 b1 b1 a1
a1 b2 b2 a3
a1 b3 b3
a2 b1

a3 b1

a3 b2

a3 b3

a4 b3

Aggregate Functions:

Aggregate functions take collection of values and return a single value as a result. These functions are
used in simple statistical queries that summarize information from the database tuples. Common
aggregate functions are COUNT, SUM, AVG, MAX and MIN

 COUNT: It is used for counting number of tuples or values.

 SUM: It is used for totaling the number of values.
 AVG: It is used to find average of number of values.
 MAX: It is used to find maximum value in a collection.
 MIN: It is used to find minimum value in a collection.

General form:

<gruping attributes> ℱ<function list> (R)

Dr. A. K. Panda
Example:

Consider the following schema:

EMPLOYEE (Eno, Ename, Address, Salary, Dno)

DEPT (Dno, Dname, Location)

Q: Retrieve each department number, the number of employees in the department and their
average salary:
R(Dno, No-of-employees, average-sal) (Dno, ℱ COUNT Eno, AVGsalary(EMPLOYEE))
Q: Find number of employees and maximum salary of all employees:
ℱ COUNT Eno, MAXsalary(EMPLOYEE)
Q: Count number of departments:
ℱ COUNT Dno (DEPT)

6.3 Modification Operations:

Relational algebra consists of operations to add, delete and update information in a database. The
modification operations are expressed using the assignment operation.

1. Deletion:

A tuple in a relation can be deleted by using following operation:

RR–E

Where R is the existing relation and E is the relational algebraic expression to select required tuples to be
deleted.

Example:

Consider the following schema of a relational database:

Employee (Emp-no, name, sex, address, salary, dept-no)

Dependent (Emp-no, D-name, sex)

Dept (dept-no, D-name, location)

Q: Delete the departments located at ‘north’.

Dept  Dept - location = ‘north’ (Dept)

Q: Delete all employees who get more than 10,000 salaries.

Employee  Employee - Salary  10,000 (Employee)

2. Insertion:

A tuple or a set of tuples can be inserted to a relation by using following operation:

Dr. A. K. Panda
 RRE

Where R is the relation to which the tuples to be inserted and E is either a specified tuple to be inserted
or it is a relational algebraic expression whose result is a set of tuples.

Q: Insert the fact that mathematics department having department number d5 is opened in the
location south.

Dept  Dept  {d5, “mathematics”, “south”}

Q: Assume that there exist a relation ‘Emp’ having same field as Employee to keep information of
part time employees. Insert the employees of department d2 of table emp to employee.

Employee  Employee  Dept_no = d2 (Emp)

3. Updating:

A value in a tuple of a relation can be updated by using following operation:

R  ∏F1 ,F2 ,……,Fn (R)

where each Fi is either the ith attribute of R, if the ith attribute is not updated or, if the ith attribute is to be
updated, Fi is an algebraic expression involving only constants and the attributes of R, that gives the new
value for the attribute.

Q: Increase salary of every employee by 10%.

Employee   emp_no, name, sex, address, salary * 1.10, dept_no (Employee)

Exercises

Exercise 1: Consider the following schema:

SUPPLIERS (Sno, Sname, status, city)

PARTS (Pno, Pname, Color, weight, city)

PROJECTS (Jno, Pname, City)

SHIPMENT (Sno, Pno, Jno, Quantity)

Answer the following queries in relational algebra:

a) Get supplier names of suppliers who supply part P2.

b) Get name of all suppliers who supply red parts.
c) Get name of suppliers who supply both blue and black parts.
d) Get supplier number of suppliers who supply all parts

Dr. A. K. Panda
 e) Get name of suppliers who supply all parts.
f) Get supplier numbers for suppliers who supply at least all those parts supplied by supplier
S2.
g) Get supplier names for suppliers who do not supply part P2.
h) Get full details of all projects in Mumbai.
i) Get supplier number for suppliers who supply project j1.
j) Get all shipments where the quantity is in the range 300 to 750 inclusive.
k) Get part number for parts supplied by a supplier in Mumbai to a project in Mumbai.
l) Get all pairs of city names such that a supplier in the first city supplies a project in the
second city.
m) Get part number for parts supplied to any project by a supplier in the same city as that
project.
n) Get project numbers for projects supplied by at least one supplier not in the same city.
o) Get the total number projects supplied by supplier S1.
p) Get the total quantity of part P1 supplied by supplier S1.
q) For each part being supplied to a project, get the part number, the project number, and the
corresponding total quantity.
r) Get part numbers of parts supplied to some project in an average quantity of more than
350.

Solution:

a) Sname (SUPPLIERS ⋈ (pno= p2 (SHIPMENT))

b) Sname (SUPPLIERS ⋈ SHIPMENT ⋈ (color = ‘Red’ (PARTS)))

c) Sname, Color (SUPPLIERS ⋈ (SHIPMENT ⋈ PARTS))  Color(color = ‘blue’ or color = ‘black’ (PARTS))

d) Sno, Pno (SHIPMENT)  Pno (PARTS)

e) Sname (SUPPLIERS ⋈ (Sno, Pno (SHIPMENT)  Pno (PARTS)))

f) Sno, Pno (SHIPMENT)  Pno (Sno = S2(SHIPMENT))

g) Sname (SUPPLIERS ⋈ (Sno (SUPPLIERS) - Sno (pno= p2 (SHIPMENT)))

h) City = ‘Mumbai’ (PROJECTS)

Dr. A. K. Panda
 i) Sno (jno= j1 (SHIPMENT))

j) 300  Quantity  700 (SHIPMENT)

k) Pno (Sno (city = ‘Mumbai’ (SUPPLIERS)) ⋈ ((Jno (city = ‘Mumbai’ (PROJECTS)) ⋈ SHIPMENT))
l) City,City1 ((Sno = Sid  Jno = Jid  City  City1) (Sno, Jno, City (SUPPLIERS ⋈ SHIPMENT)  ((Sid, Jid, City1) (Sno,
Jno, City (PROJECTS ⋈ SHIPMENT)))) )

m) Pno ((SUPPLIERS ⋈ SHIPMENT) ⋈ PROJECTS))

n) Jno ((Sno = Sid  Jno = Jid  City  City1) (Sno, Jno, City (SUPPLIERS ⋈ SHIPMENT)  ((Sid, Jid, City1) (Sno, Jno,
City (PROJECTS ⋈ SHIPMENT)))))

o) ℱ COUNTJno (Sno = S1 (SHIPMENT))

p) ℱ SUMQuantity (Sno = S1  Pno = P1 (SHIPMENT))

q) Pno, Jno ℱ SUMQuantity (SHIPMENT)

r) Pno ((Avg-qty  350 ((Pno, Avg-qty( Pnoℱ AVGQuantity (SHIPMENT))))

Exercise 2:

Consider the following relational schema:

EMPLOYEE (person-name, street, city)

WORKS (person-name, company-name, salary)

COMPANY (company-name, city)

MANAGES (person-name, manager-name)

Express the following queries in relational algebra:

a) Find the names of all employees who work for TCS.

b) Find the names and cities of residence of all employees who work for TCS.
c) Find the names, street addresses, and cities of residence of all employees who work for TCS
and earn more than Rs. 500000 per annum.
d) Find the names of all employees in this database who live in the same city as the company
for which they work.

Dr. A. K. Panda
 e) Find the names of all employees who live in the same city and the same street as do their
managers.
f) Find the names of all employees in this database who do not work for TCS.
g) Find the names of all employees in this database who earn more than every employee of
Infosys.
h) Assume that the companies are located in several cities. Find all companies located in every
city in which TCS is located.
i) Delete all tuples in the WORKS relation for employees of Infosys.
j) Modify the database so that Ashok now lives in Chennai.
k) Give all employees a 10% salary raise.
l) Find the sum of the salaries of all employees in the WORKS relation.

Solution:

a) person-name (company-name = ‘TCS’ (WORKS)

b) person-name, city (EMPLOYEE ⋈ (company-name = ‘TCS’ (WORKS)

c) person-name, street, city (salary > 500000 ^ company-name = ‘TCS’ (WORKS ⋈ EMPLOYEE)

d) person-name (WORKS ⋈ EMPLOYEE ⋈ COMPANY)

e) person-name ((EMPLOYEE ⋈ MANAGES) ⋈ manager-name = [Link]-name ^ employee. street =

[Link] ^ employee. city = [Link] (employee2(EMPLOYEE))

f) person-name (company-name  ‘TCS’ (WORKS)

g) person-name (WORKS) - person-name (WORKS ⋈works. salary  [Link] (works2 (company-name =

‘Infosys’ (WORKS))))

h) COMPANY  City (Company-name = ‘TCS’ (COMPANY))

i) WORKS  WORKS - company-name = ‘Infosys’ (WORKS)

j) EMPLOYEE  person-name, street, “Chennai” ( person-name = “Ashok”(COMPANY)

k) WORKS  Person-name, company-name, salary * 1.10 (WORKS)

l) ℱ SUM salary (WORKS)

Dr. A. K. Panda
Exercise 3:

Consider the following relation schema:

SAILORS (sid, sname, rating, age)

RESERVES (sid, bid, day)

BOATS (bid, bname, color)

Express the following queries in relational algebra:

a) Find the names of sailors who have reserved boat 103.

b) Find the names of sailors who have reserved a red boat.
c) Find the colors of boats reserved by Ashis.
d) Find the names of sailors who have reserved at least one boat.
e) Find the names of sailors who have reserved a red or a green boat.
f) Find the names of sailors who have reserved a red and a green boat.
g) Find the names of sailors who have reserved at least two boats.
h) Find the supplier id of sailors with age over 20 who have not reserved a red boat.
i) Find the names of sailors who have reserved all boats.
j) Find the names of sailors who have reserved all boats called Interlake.

Solution:

a) sname ((bid = 103(RESERVES)) ⋈ SAILORS)

b) sname ((color = ‘red’ (BOATS)) ⋈ RESERVES ⋈ SAILORS))

c) color ((sname = ‘Ashis’ (SAILORS)) ⋈ RESERVES ⋈ BOATS)

d) sname (SAILORS ⋈ RESERVES)

e) sname((color = ‘red’ v color = ‘green’(BOATS)) ⋈ RESERVES ⋈ SAILORS)

f) R1 sid ((color = ‘red’ (BOATS)) ⋈ RESERVES)

R2 sid ((color = ‘green’ (BOATS)) ⋈ RESERVES)
R3  R1 R2
R4  R3 ⋈ SAILORS
Result  sname(R4)

g) R1  Reservation1(sid1, sname, bid1) (sid, sname, bid (SAILORS ⋈ RESERVES))

R1  Reservation2 (sid2, bid2) (sid, , bid (SAILORS ⋈ RESERVES))
Dr. A. K. Panda
 R3  (sid1 = sid2)  (bid1  bid2) (R1 x R2)
Result  sname (R3)

h) sid(age  20(SAILORS)) - (sid(color = ‘red’((RESERVES ⋈ SAILORS)))

R1 sid, bid(RESERVES) R2 bid(BOATS) R3  R1  R2
Result  sname(R3 ⋈ SAILORS)

i) R1 sid, bid(RESERVES) R2 bid (BOATS)) R3  R1  R2

Result  sname(R3 ⋈ SAILORS)

j) R1 sid, bid(RESERVES) R2 bid(bname = ‘interlake’ (BOATS)) R3  R1  R2

Result  sname(R3 ⋈ SAILORS)

Dr. A. K. Panda
 FUNCTIONAL DEPENDENCY & DECOMPOSITION OF A RELATION

Functional dependency:

It is a constraint between two attributes or two set of attributes of the same relation. Let r
be a relation and X and Y be arbitrary subset of set of attributes of r. Then we say that X
functionally determines Y or, Y is functionally dependent on X denoted by:

XY

if 𝑡1 [𝑋] = 𝑡2 [𝑋] then 𝑡1 [𝑌] = 𝑡2 [𝑌] for all pair of tuples t1 and t2 in r. In other words,
whenever two tuples of r agree on their X value, they also agree on their Y value.

The left side and right sides of an FD are called determinant and dependent respectively.

Trivial and Non-trivial FD:

A functional dependency X  Y is said to be a trivial functional dependency if Y  X,

otherwise it is called non-trivial functional dependency.

Inference rules for Functional dependencies:

Fundamental Rules or, Armstrong’s axioms:

Rule 1:Reflexivity (inclusion): If Y X, then X  Y.

Rule 2:Augmentation: If X  Y, then XZ  YZ.

Rule 3:Transitivity: If X  Y and Y Z then X  Z.

The above three rules are called Armstrong’s Axioms.

Note: Armstrong’s Axioms are sound and Complete, They are sound because for a given set
of functionally dependencies F, no additional FDs not implied by F can be derived by using
these axioms. They are complete because all FDs implied by F can be derived from F by
using these axioms.

Additional rules of Inference:

Rule 4:Decomposition or projective: If X  YZ, then X  Y and X  Z.

Rule 5:Union or, Additive If X  Y and X  Z, then X  YZ.

Rule 6:Pseudo transitive If X  Y and WY  Z, then WX  Z.

Dr. A. K. Panda
Proof of Decomposition Rule:

1. X  YZ (Assumption)
2. YZ  Y (Using reflexive rule as Y  YZ)
3. XY (From 1 & 2 and by using transitive rule)
4. YZ  Z (Using reflexive rule as Z  YZ)
5. XZ (From 1 & 4 and by transitive rule)

Proof of Union rule:

1. XY (Assumption)
2. XZ (Assumption)
3. X  XY (From 1 and by Augmentation rule)
4. XY  YZ (From 2 and by Augmentation rule)
5. X  YZ (From 3 & 4 and by transitive rule)

Proof of Pseudo Transitive Rule:

1. XY (Assumption)
2. WY  Z (Assumption)
3. WX  WY (From 1 and by Augmentation Rule)
4. WX  Z (From 3 & 2 and by transitive rule)

Closure of a set of attributes X (i.e. X+)

Let X be a set of attributes that appears in the left hand side of some functional
dependencies in F. Then the closure of X i.e. X + is the set of attributes that are functionally
determined by X.

Algorithm to compute X+:

Input: A set of functional dependencies F and a set of attributes X.

Output: The closure X+ of X under the functional dependencies in F.

Initialize X+ = X.
repeat
oldX+ = X+.
for each functional dependency Y  Z in F do
if Y  X+ then X+ = X+ U Z.
until (X+ = oldX+)

Dr. A. K. Panda
Example:

Compute closure {A, B}+ under the following set of functional dependencies F:

F = {A  BC, E  CF, B  E, CD  EF}

Solution:

Initialize {A, B}+ = {A, B}

Iteration 1:

Old {A, B}+ = {A, B}+ = {A, B}

A  BC and A  {A,B}  {A, B}+ = {A, B}+ U {B, C} = {A, B, C}

E  CF but E  {A, B, C}  {A, B}+ = {A, B}+ = {A, B, C}

B  E and B  {A,B, C}  {A, B}+ = {A, B}+ U {E} = {A, B, C,E}

CD  EF but CD  {A, B, C, E}  {A, B}+ = {A, B}+ = {A, B, C, E}

Old {A, B}+  {A, B}+

Iteration 2:

Old {A, B}+ = {A, B}+ = {A, B, C, E}

A  BC and A  {A,B, C, E}  {A, B}+ = {A, B}+ U {B, C} = {A, B, C, E}

E  CF and E  {A, B, C, E}  {A, B}+ = {A, B}+ U {C, F} = {A, B, C, E, F}

B  E and B  {A,B, C, E, F}  {A, B}+ = {A, B}+ U {E} = {A, B, C,E, F}

CD  EF but CD  {A, B, C, E, F}  {A, B}+ = {A, B}+ = {A, B, C, E, F}

Old {A, B}+  {A, B}+

Iteration 3:

Old {A, B}+ = {A, B}+ = {A, B, C, E, F}

A  BC and A  {A,B, C, E, F}  {A, B}+ = {A, B}+ U {B, C} = {A, B, C, E, F}

E  CF and E  {A, B, C, E, F}  {A, B}+ = {A, B}+ U {C, F} = {A, B, C, E, F}

B  E and B  {A,B, C, E, F}  {A, B}+ = {A, B}+ U {E} = {A, B, C,E, F}

CD  EF but CD  {A, B, C, E, F}  {A, B}+ = {A, B}+ = {A, B, C, E, F}

Dr. A. K. Panda
Since Old {A, B}+ = {A, B}+ , {A, B}+ = {A, B, C, E. F}

Example:

Compute closure {B, C, D}+ under the following set of functional dependencies F:

F = {A  BC, CD  E, E  C, D  AEH, ABH  BD, DH  BC}

Ans: {B, C, D}+ = {A, B, C, D, E, H}

Example: Compute the closure of {A, B}, i.e. {A, B} + under the set of functional
dependencies F = {AB  C, BC  AD, D  E, CF  B}

Ans: {A, B}+ = {A, B, C, D, E}

Redundant Functional dependencies:

A functional dependency X  Y in the set of functional dependencies F is redundant if it can

be derived from the other functional dependencies in the set.

Algorithm (called membership algorithm) to find redundant FDs:

Input: A set of FDs F and a FD of F i.e. A  B.

Output: A decision whether the FD: A  B is redundant.

1. Set F = F – {A  B}
2. Find closure of the determinant A i.e. A+ under F.
3. If the dependent B  A+ then the FD: A  B is redundant;
else A  B is non-redundant.

Example:

Remove any redundant functional dependencies from the following set of functional
dependencies:

F = {A  B, C  D, AC  E, BD  E }

Solution:

1. F = F – {A  B} = {C  D, AC  E, BD  E }
A + = {A} which is not a super set of B.
Hence, A  B is non-redundant.
2. F = F – {C  D} = {A  B, AC  E, BD  E }
C + = {C} which is not a super set of D.
Hence, C  D is non-redundant.

Dr. A. K. Panda
 3. F = F – {AC  E} = {A  B,C  D, BD  E}
{A, C} + = {A, B, C, D, E} which is a super set of E.
Hence, AC  E is redundant.
4. F = F – {BD  E} = {A  B,C  D, AC  E}
{B, D} + = {B, D} which is not a super set of E.
Hence, BD  E is non-redundant.

Cover:

A set of functional dependencies F is said to cover a set of functional dependencies E, if

every FD in E is in F+.

Example: Let E = {A  BC, B  C} and F = {A B, B  C, A  D} then F covers E.

Equivalence of sets of Functional Dependencies:

Two set of functional dependencies E and F over a relation scheme R are said to be
equivalent if the closure of E is identically equal to the closure of F i.e. E + = F+.

Note: Two set of FDs E and F are equivalent if and only if E covers F and F covers E.

Example: Let E = {A  B, B  A, B  C, A  C, CA} and F = {A  B, B  C, C  A}.

Since E covers F and F covers E, Hence E and F are equivalent.

Example: Given a two sets F1 and F2 of functional dependencies for a relation:

F1: A  B, AB  C, D  AC, D  E

F2: A  BC, D  AE

Are the two sets equivalent?

Solution: 1. A  B (Given in F1)

2. AB  C (Given in F1)

3. D  AC (Given in F1)

4. D  E (Given in F1)

5. A  BC (From 1 and 2 and by pseutransitive rule)

6. D  A (From 3 and by decomposition rule)

7. D  C (From 3 and by decomposition rule)

Dr. A. K. Panda
 8. D  AE (From 6 & 4 and by union rule)

Hence, F1 covers F2.

1. A  BC (Given in F2)
2. D  AE (Given in F2)
3. A  B (From 1 and by decomposition rule)
4. A  C (From 1 and by decomposition rule)
5. AB  CB (From 4 and by augmentation rule)
6. AB  C (From 5 and by decomposition rule)
7. D  A (From 2 and by decomposition rule)
8. D  C (From 7 & 4 and by transitive rule)
9. D  AC (From 7 & 8 and by union rule)
10. D  E (From 2 and by decomposition rule)

Hence, F2 covers F1.

F1 and F2 are equivalent.

Minimal Set of Functional Dependencies:

A set of functional dependencies F is minimal or, irreducible if and only if it satisfies the
following conditions:

(i) The R.H.S. of every FD in F involves just one attribute i.e. it is a singleton set.
(ii) The L.H.S. (determinant) of every FD in F is minimal, that means no attribute can be
discarded from the determinant without changing the closure F +.
(iii) No FD in F can be discarded from F without changing the closure F +.

Example:

Find the minimal set of functional dependencies that is equivalent to the following set of
FDs:

F = {A  BC, B  C, A  B, AB  C, AC  D}

Ans: {A  B, B  C, A  D}

Minimal cover or Canonical cover of a set of Functional Dependencies:

The minimal cover of a set of functional dependencies F is the minimal set of dependencies
Fmin that is equivalent to F.

Dr. A. K. Panda
Example:

Find the minimal cover of a set of FDs: F = {A  BC, B  C, A  B, AB  C, AC  D}

Ans: {A  B, B  C, A  D}

Algorithm to compute minimal cover Fmin for F:

Input: A set of functional Dependencies F.

Output: Minimal cover Fmin for F.

1. Initialize Fmin = F.
2. Replace each FD A  B1 B2 B3 ... Bn in Fmin by n different FDs A  B1, A  B2, A  B3,
…, A  Bn.
3. for each functional dependency A  B in Fmin
for each attribute X  A
if ((Fmin – {A  B}) U ((A – {X})  B)) is equivalent to Fmin then
replace A  B with (A – {X})  B in Fmin
4. for each remaining functional dependency A  B in Fmin
if (Fmin – {A  B}) is equivalent to Fmin then remove A  B from Fmin.

Note: Minimal cover of a set of FDs may not be unique.

Example:

Find the minimal cover Fmin for the following set of FDs F:

F = {AB  C, C  A, BC  D, ACD  B, BE  C, CE  FA, CF  BD, D  EF}

Ans:

Fmin = {AB  C, C  A, BC  D, BE  C, CE  F, CF  B, D  E, D  F}

Fmin = {AB  C, C  A, BC  D, CD  B, BE  C, CE  F, CF  D, D  E, D  F}

Example:

Find the minimal cover Fmin for the following set of FDs F:

F = {A  BC, CD  E, E  C, D  AEH, ABH  BD, DH  BC}

Ans: Fmin = {A  B, A  C, E  C, D  A, D  E, D  H, AH  D}

Example:

Find the minimal cover Fmin for the following set of FDs F:

Dr. A. K. Panda
F = {A  BC, AC  D, D  B, AB  D}

Ans: Fmin = {A  B, A  C, A  D, D  B}

Decomposition of a relation:

The decomposition of a relation scheme R = {A1, A2, … , An} is its replacement by a set of
relation schemes D = {R1, R2, …, Rk}, such that

Ri  R for 1  i  k

and R1  R2  …  Rk = R.

Properties of good Decomposition:

1. Lossless-Join decomposition: A decomposition D = {R1, R2, …, Rk} of a relation scheme

R is said to have lossless-Join property with respect to the set of FDs F on R if, for every
relation state r of R that satisfies F, [∏R1 (r) ⋈ ∏R2 (r) ⋈ … ⋈ ∏Rk (r)] = 𝑟.

Example: Consider a relation scheme R(A, B, C) with a set of functional dependencies F =

{A  B, A  C} is decomposed into two relations R1 and R2 that are defines by following
two projections:

R1 = projection of R over A, B
R2 = projection of R over A, C
The decomposition is lossless if R = R 1 ⋈ R2 and the decomposition is lossy if R  R1 ⋈ R2.

Dr. A. K. Panda
 R A B C

a1 b1 c1
F: A  B
AC a2 b2 c2

a3 b2 c1

a3 b1 c2

DECOMPOSE

R1 A B R2 A C
F2: A  C
a1 b1 a 1 c1
F1: A  B
a2 b2 a 2 c2

a3 b2 a 3 c1

a3 b1 a 3 c2

Join

R A B C

a 1 b 1 c1
F: A  B
AC a 2 b 2 c2

a 3 b 2 c1

a 3 b 1 c2

Since R1 ⋈ R2 = R, the decomposition is lossless.

Dr. A. K. Panda
 Algorithm to determine whether decomposition is Lossless:

Input: A relation scheme R with a set of FDs F and a decomposition D = {R 1, R2, …, Rk} of R.

Output: A decision whether D is lossless.

1. Construct a blank table S with n columns and k rows, where each column j
corresponds to attribute Aj and each row i corresponds to relation scheme Ri.
2. for each row i representing relation scheme Ri
for each column j representing attribute Aj
if Aj is in Ri then set S[i, j] = aj
else
set S[i, j] = bij.
3. repeat
for each FD X  Y in F
for all rows in S that have the same symbols in the columns
corresponding to attributes in X
if one of the symbol in the Y column is aj then make the other aj
else if the symbols are bij and blj then make them both bij or blj

until no more changes can be made to the table S.

4. If there is at least one row with all ‘a’ symbols i.e. a1, a2, …, ak then the D is Lossless
else D is lossy.

Example:

Let R(A, B, C, D, E) be a relation scheme with a set of functional dependencies F = {A  C, B

 C, C  D, DE  C, CE  A}. Suppose that R is decomposed into R1(A, D), R2(A, B),
R3(B,E), R4(C, D, E) and R5(A, E). Determine whether the decomposition is lossless.

Solution:

Initialization: Iteration 1: A  C implies Iteration 1: B  C implies

A B C D E A B C D E A B C D E

R1 a1 b12 b13 a4 b15 R1 a1 b12 b13 a4 b15 R1 a1 b12 b13 a4 b15

R2 a1 a2 b23 b24 b25 R2 a1 a2 b13 b24 b25 R2 a1 a2 b13 b24 b25

R3 b31 a2 b33 b34 a5 R3 b31 a2 b33 b34 a5 R3 b31 a2 b13 b34 a5

R4 b41 b42 a3 a4 a5 R4 b41 b42 a3 a4 a5 R4 b41 b42 a3 a4 a5

R5 a1 b52 b53 b54 a5 R5 a1 b52 b13 b54 a5 R5 a1 b52 b13 b54 a5

Dr. A. K. Panda
Iteration 1: C  D implies Iteration 1: DE  C implies Iteration 1: CE  A implies
A B C D E A B C D E A B C D E
R1 a1 b12 b13 a4 b15 R1 a1 b12 b13 a4 b15 R1 a1 b12 b13 a4 b15
R2 a1 a2 b13 a4 b25 R2 a1 a2 b13 a4 b25 R2 a1 a2 b13 a4 b25
R3 b31 a2 b13 a4 a5 R3 b31 a2 a3 a4 a5 R3 a1 a2 a3 a4 a5
R4 b41 b42 a3 a4 a5 R4 b41 b42 a3 a4 a5 R4 a1 b42 a3 a4 a5
R5 a1 b52 b13 a4 a5 R5 a1 b52 a3 a4 a5 R5 a1 b52 a3 a4 a5

Since third row of the table contains all ‘a’ symbols, the decomposition is lossless.

2. Dependency-Preserving Decomposition: A decomposition D = {R1, R2, …, Rk} of a

relation scheme R is said to be dependency-preserving with respect to F if the union of the
projections of F on each Ri in D is equivalent to F.

i.e. F+ = {F1  F2  … …  Fk}+

Where Fi is the set of functional dependencies of relation scheme Ri for i = 1 to k.

Example:

Let R (A, B, C, D) be a relation scheme with a set of functional dependencies F = {A  B, B

 C, C  D, D  A}. Suppose that R is decomposed into R1 (A, B), R2 (B, C) and R3 (C,D).
Determine whether the decomposition preserves dependency.

Solution:

F+ = { A  B, A  C, A  D, B  C, B  D, B  A, C  D, C A, C  B, D  A, D  B, D 
C}

F1 = Set of functional dependencies of R1 = {A  B, B  A}

F2 = Set of functional dependencies of R2 = {B  C, C  B}

F3 = Set of functional dependencies of R3 = {C  D, D  C}

F1  F2  F3 = {A  B, B  A, B  C, C  B, C  D, D  C}

{F1  F2  F3}+ = { A  B, A  C, A  D, B  C, B  D, B  A, C  D, C A, C  B, D  A,
D  B, D  C}

Dr. A. K. Panda
Since, F+ = {F1  F2  … …  Fk}+ , the decomposition preserves dependency.

EXERCISE

No.1: Consider the relation scheme SUPPLIES (Supplier, Part, Contract, Quantity) with a set
of functional dependencies:

F= {Contract  Part,

Part  Supplier

Supplier, Contract  Quantity}

Now the relation is decomposed into following two relations:
SUPPLIERS (Supplier, Part, Quantity)
CONTRACTS (Contract, Part)
a) Explain whether any information has been lost in this decomposition.
b) Explain whether any information has been lost if the decomposition is changed to
SUPPLIERS (Contract, Part, Quantity)
CONTRACTS (Contract, Supplier)

No.2: A relation R (A, B, C, D) is given. For each of the following set of FDs, assuming they
are the only dependencies that hold for R, state whether or not the proposed
decomposition of R into smaller relations is a good decomposition. Briefly explain your
answer why or why not.

a) B  C, D  A; decomposed into BC and AD.

b) AB  C, C  A, C  D; decomposed into ACD and BC.
c) A  BC, C  AD; decomposed into ABC and AD.
d) A  B, B  C, C  D; decomposed into AB, AD and CD.
e) A  B, B  C, C  D; decomposed into AB and ACD.

No.3: Remove any redundant FDs from the following set of FDs:

F1: A  B, B  C, AD  C

F2: XY  V, ZW  V, VX  Y, W  Y, Z  X

F3: PQ  R, PS  Q, QS  P, PR  Q, S  R

No.4: Given the set of functional dependencies {A  BCD, CD  E, E  CD, D  AH, ABH 
BD, DH BC}, find a minimal cover. Is this the only minimal cover?

No.5: Given a relation scheme R (A, B, C, D, E, F) with a set of dependencies F = {A  CE, B

 D, C  ADE, BD  F}, Find the closure of BCD.

Dr. A. K. Panda
No.6: For each of the following relation schema Ri with a set of functional dependencies
determine key(s) of Ri.

a) R1(A, B, C, D) with FDs A  B, B  C, and B  D.

b) R2(A, B, C, D) with FDs AB  C, C  D, and D  A.
c) R3(A, B, C, D) with FDs AB  C, BC  D, CD  A, and AD  B
d) R4(A, B, C, D) with FDs A  B, B  C, C  D, D  A.

Dr. A. K. Panda
 Normalization

It is a process of converting complex data structure into simple and stable data structure. It
is also the process of successively reducing relations with anomalies to produce smaller,
well structured relations.

Need of Normalization: Normalization is needed to overcome following four undesirable

problems:

 Redundancy
 Update Anomalies.
 Insertion Anomalies.
 Deletion Anomalies.

Objectives of Normalization:

1. Minimize data redundancy, thereby avoiding anomalies and conserving storage

space.
2. Simplify the enforcement of referential integrity constraints.
3. Make it easier to maintain data (insert, update, and delete)
4. Provide a better design that is an improved representation of the real world and a
stronger basis for future growth.

Properties of Normalized relations:

1. No data value should be duplicated in different rows unnecessarily.

2. A value must be specified for every attribute in a row.
3. Each relation should be self contained. In other words, if a row from a relation is
deleted, important information should not be accidentally lost.
4. When a row is added to a relation, other relations in the same database should not
be affected.
5. A value of an attribute in a tuple may be changed independent of other tuples in the
relation and other relations of the same database.

Steps of Normalization:

Normalization can be accomplished and understood in stages, each of which corresponds

to a normal form. A normal form is a state of a relation that results from applying simple
rules regarding functional dependencies, multivalued dependencies and join dependencies.

Dr. A. K. Panda
 Table with Multivalued
attributes
Remove multivalued
attributes

First Normal Form

(1NF)
Remove partial
dependencies
Second Normal Form
(2NF)
Remove transitive
dependencies

Third Normal Form

(3NF)
Remove remaining
anomalies resulting from
multiple candidate keys
Boyce-Codd Normal
Form (BCNF)
Remove multivalued
dependencies

Fourth Normal Form

(4NF)

Remove remaining
anomalies
Fifth Normal Form
(5NF/ PJNF)

First Normal Form (1NF):

A relation is in first normal form (1NF) if there are no repeating groups i.e. the value at the
intersection of each row and column is atomic.

Dr. A. K. Panda
Grade Regd- Name Addres Major Subject Sub- Teache Taddre Grade
Report No s -code title r ss
085001 Ashis GGP HRM PCS01 HRP C.S. CSPur A
PCS02 HRD BMD MV B
085013 Anup BJB System PCS05 DS SSM ABC O
PCS06 DBMS AKP XYZ B
PCS07 AI PKM PQR D
085016 Rahul VSS Finance PCS08 SAPM AS MV A
PCS09 FS SD VSS C
PCS11 PA MB MNO B

The above table is not in 1NF because there are entries with more than one value, which
can be converted into 1NF relation by filling in the missing entries of each incomplete row
of the table with the copies of their corresponding non-repeating attributes.

Grade Regd- Name Addres Major Subject Sub- Teache Taddre Grade
Report No s -code title r ss
085001 Ashis GGP HRM PCS01 HRP C.S. CSPur A
085001 Ashis GGP HRM PCS02 HRD BMD MV B
085013 Anup BJB System PCS05 DS SSM ABC O
085013 Anup BJB System PCS06 DBMS AKP XYZ B
085013 Anup BJB System PCS07 AI PKM PQR D
085016 Rahul VSS Finance PCS08 SAPM AS MV A
085016 Rahul VSS Finance PCS09 FS SD VSS C
085016 Rahul VSS Finance PCS11 PA MB MNO B

Problems with 1NF:

1NF contains redundant information. For example the above relation GRADE-REPORT is in
1NF with primary key {Regd.-No, Subject-code} which has the following problems:

1. Redundancy: The student’s name, address and major are repeated for each subject
he is registered for.
2. Update Anomaly: As a consequence of the redundancy, we may update the address
in one tuple, while leaving it unchanged in another. Thus we would not have a
unique address for each student.
3. Insertion Anomaly: It is not possible to record the address of a teacher, unless he is
assigned to at least one subject.
4. Deletion anomaly: If a subject is registered by only one student and a teacher is
assigned to teach only that subject and if the said student discontinues the course,

Dr. A. K. Panda
 the information of the student cannot be deleted. If we do so information of the
teacher will be lost.

Second Normal Form (2NF):

A relation is in second normal from (2NF) if it is in 1NF and every non-key (nonprime)
attribute is fully functionally dependent on the primary key.

Prime attribute & Nonprime attribute: An attribute A of a relation R is called a prime

attribute if A is part of any candidate key of R. If A is not part of any candidate key R, A is
called a nonprime attribute.

Fully Functionally Dependency: A functional dependency X  Y is said to be a fully

functional dependency if there exists no proper subset Z of X such that Z  Y.

Partial Functional Dependency: A functional dependency X  Y is said to be a partial

functional dependency if there exists at least one proper subset Z of X such that Z  Y.

Note: A relation that is in first normal form will be in second normal form if any one of
following conditions is satisfied:

1. The primary key consists of only one attribute.

2. No non-key attributes exist in the relation.
3. Every nonprime attribute of the relation is fully functionally dependent on each
relation key.

Removing partial dependencies:

1. Create a new relation containing determinant of a partial dependency which is the

primary key in the new relation.
2. Move the non-key attributes that are dependent on this primary key attribute (or
attributes) from the old relation to the new relation.

In the relation Grade-report following functional dependencies hold:

Regd-No  Name, Address, Major

Sub-Code  Sub-Title, Teacher

Teacher  T-Address

Regd-No, Sub-Code  Grade.

The relation GRADE_REPORT can be decomposed into following 2NF relations:

STUDENT (Regd-No, Name, Address, Major)

Dr. A. K. Panda
SUBJECT (Sub-Code, Sub-Title, Teacher, T-Address)

GRADE-REPORT (Regd-No, Sub-Code, Grade)

Third Normal Form (3NF):

A relation is in third normal form if it is in second normal form and there exists no
transitive dependency.

Transitive Dependency: Let X and Y be the set of attributes such that X  Y holds but Y 
X does not hold and Z be a set of attributes that in not in X and not in Y for which Y  Z
holds, then Z is transitively dependent on X.

In other words, a functional dependency between two or more non-key attributes is called
transitive dependency.

Removing transitive Dependencies:

1. For each non-key attribute (or set of attributes) that is a determinant in a relation,
create a new relation. The attribute becomes the primary key of the new relation.
2. Move all of the attributes that are functionally dependent on the attribute from the
old to the new relation.
3. Leave the attribute (which serves as a primary key in the new relation) in the old
relation to serve as foreign key that allows us to associate the two relations.

The relations STUDENT and GRADE-REPORT are in 3NF, But the relation SUBJECT is not in
3NF because there is a functional dependency between non-key attributes (Teacher  T-
Address).

The relation SUBJECT can be decomposed into following 3NF relations:

SUBJECT (Sub-Code, Sub-Title, Teacher)

TEACHER (Teacher, T-address)

BCNF:

A relation is in Boyce-codd normal form (BCNF) if every determinant in the relation is a

candidate key.

Algorithm for decomposition into BCNF:

Input: A relation scheme R that is not in BCNF and a set FDs F of R.

Output: A decomposition D = {R1, R2, …, Rk}, where each Ri is in BCNF.

Dr. A. K. Panda
 1. Initialize D = R.
2. repeat
Choose a relation scheme Ri in D that is not in BCNF
if X  Y be a FD of Ri that violates BCNF then
Replace Ri in D by two relation schemes Ri – Y and X  Y.

until each Ri in D is in BCNF.

Note: This algorithm guarantees Lossless, but does not guarantee dependency preserving.

Algorithm for decomposition into 3NF (Synthesis Algorithm):

Input: A relation scheme R that is not in 3NF and a set FDs F of R.

Output: A decomposition D = {R1, R2, …, Rk}, where each Ri is in 3NF.

1. Find a minimal cover F1 of F.

2. Partition F1 into groups G1, G2, … where each group Gi has an identical determinant.
3. For each group Gi in F1, if X  A1, X  A2, …, X  An are the dependencies of Gi then
create a relation scheme Ri in D with attributes X  {A1}  {A2}  …  {An} where X
is the key of Ri.
4. If none of the relation scheme in D contains a key of R, then include a relation
scheme in D which contains key of R.
5. Eliminate redundant relation schemes from D. A relation scheme Ri is said to be
redundant if attribute set of Ri is a subset of another relation scheme Rj in D.

Note: This algorithm guarantees both Lossless and dependency preserving. If step 4 is
removed, the algorithm will guarantee dependency preserving, but will not guarantee
lossless.

Example:

Consider a relation scheme R(A, B, C, D, E, F, G) with the following FDs:

F = {D  A, DF  C, DA  B, A  F, EF  B, E  A, B  D, DA  B, EB  C, AB  C, G 
B, C  B}

Using synthesis algorithm, decompose R into 3NF relation schemes.

Solution:

Step 1: Fmin = {D  C, D  A, D  B, B  D, E  B, G  B, A  F, C  B}

Step 2: G1 = {D  C, D  A, D  B}, G2 = {B  D}, G3 = {E  B}, G4 = {G  B}, G5 = {A  F},

G6 = {C  B}

Dr. A. K. Panda
Step 3: D = {R1(D, C, A, B), R2(B, D),R3(E, B),R4(G, B),R5(A, F),R6(C, B)}

Step 4: Since none of the relation scheme in D contains key of R, a new relation R 7(E, G)
containing key of R is included in D.

D = { R1(D, C, A, B), R2(B, D),R3(E, B),R4(G, B),R5(A, F),R6(C, B), R7(E, G)}

Step 5: Eliminating the redundant relation schemes R2(B, D) and R6(C, B) we get the
following 3NF relation schemes:

D = { R1(D, C, A, B), R2(E, B),R3(G, B),R4(A, F), R5(E, G)}, where the key attributes are
underlined.

Example:

Consider the following relation scheme:

CONTRACTS (Contract-id, Supplier-id, Project-id, Dept-id, Part-id, Quantity, Value)

With a set of FDs: F = { Contract-id  Supplier-id, Project-id, Dept-id, Part-id,

Quantity, Value,

Project-id, Part-id  Contract-id,

Supplier-id, Dept-id  Part-id,

Project-id  Supplier-id }

a) What is the highest normal form of the CONTRACTS relation?

b) If It is not in 3NF, decompose it into 3NF relation schemes.
c) If it is not in BCNF, decomose it into BCNF relation schemes.
d) In each case (b) and (c), after decomposition check whether the decomposition is
lossless and dependency preserving.

Solution:

a) The primary key consists of only one attribute i.e. Contract-id. Hence the relation
CONTRACTS is in 2NF. Since there is a FD between non-key attributes, the relation is
not in 3NF. Hence the highest normal form of the relation is 2NF.
b) Given relation scheme R(C, S, J, D, P, Q, V) with a set of FDs:
F = {C  S J D P Q V, JP  C, SD  P, J  S}

Fmin = {C  J, C  D, C  Q, C  V, JP  C, SD  P, J  S}

 D1 = {R1(C, J, D, Q, V), R2(J, P, C), R3(S, D, P), R4(J, S)}, where each Ri is in 3NF.

Dr. A. K. Panda
 c) In the FD: SD  P, SD is not a key. Hence R is decomposed into R1(S, D, P) and R2(C,
S, J, D, Q, V).
In R2, there is a FD: J  S and J is not a key. Hence R2 is decomposed into R2(J, S) and
R3(C, J, D, Q, V).
 D2 = {R1(S, D, P), R2(J, S), R3(C, J, D, Q, V)}, where each Ri is in BCNF.
d) We can verify that D1 is a loss-less join and dependency preserving decomposition
and D2 is loss-less but does not preserve dependency.

Example: Consider a relation scheme R (A, B, C, D, E) with a set of FDs

F = {A  B, BC  E, ED  A}.

a) List all keys of R.

b) Is R in 3NF?
c) Is R in BCNF

Ans:

a) Three possible keys: ACD, BCD and ECD.

b) Since partial dependency exists, R is not in 2NF. Therefore R is not in 3NF.
c) In the FD: A  B, the determinant A is not a key. Hence, R is not in BCNF.

Example: Consider a relation scheme R (A, B, C, D, E, F, G, H, I, J) with a set of FDs F = {AB

 C, A  DE, B  F, F  GH, D  IJ}. What is the key for R? Decompose R into 2NF and
then 3NF relations.

Ans:

AB is the key for R.

2NF decomposition

A  D,E,I,J
R1(A, D, E, I, J) B  F, G, H
R R2(B, F, G, H)
R2(A, B, C, F, G, H)
R3(A, B, C)

Hence D = {R1(A, D, E, I, J), R2(B, F, G, H), R3(A, B, C)}, where each Ri is in 2NF.

3NF decomposition

D  I,J
R1(D, I, J)
R1(A, D, E, I, J)
R2(A, D, E)
Dr. A. K. Panda
 F  GH
R3(F, G, H)
R2(B, F, G, H)
R4(B, F)

R3(A, B, C) is already in 3NF because there is only one non-key attribute.

Hence D = { R1(D, I, J), R2(A, D, E), R3(F, G, H), R4(B, F), R5(A, B, C)}, where each Ri is in 3NF.

Example: Decompose the same relation scheme R (A, B, C, D, E, F, G, H, I, J) into 3NF

relation schemes by using synthesis algorithm.

Solution:

F = {AB  C, A  DE, B  F, F  GH, D  IJ}

Fmin = {AB  C, A  DE, B  F, F  GH, D  IJ}

D = { R1(A, B, C), R2(A, D, E), R3(B, F), R4(F, G, H), R5(D, I, J)}

Example: Consider R (A, B, C, D) be a relation scheme. For each of the following sets of FDs,
assuming those are the only dependencies that hold for R, do the following:

a) Indentify the candidate key(s) for R.

b) Identify the best normal form that R satisfies.
c) If R is not in BCNF, decompose it into a set of BCNF relations.
d) After decomposition, determine whether it is lossless and dependency preserving.

1) C  D, C  A, B  C
2) B  C, D  A
3) ABC  D, D  A
4) A  B, BC  D, A  C
5) AB  C, AB  D, C  A, D  B.

Solution:

1) (a) Since B does not appear in the RHS of any FD and B + = {A, B, C, D}, Hence B is the
only candidate key.
(b) Since primary key contains a single attribute, R is in 2NF, but it is not in 3NF
because there exists FD between non-key attributes. Therefore, the best normal form of
R is 2NF.
(c) D = {R1(C, D), R2(A, C), R3(B, C)}

Dr. A. K. Panda
 (d) D is both loss-less and dependency preserving.
2) (a) Since BD does not appear in the RHS of any FD and {B,D} + = {A, B, C, D}, Hence BD is
the only candidate key.
(b) Since partial dependency exists, R is not in 2NF. Therefore, the best normal
form of R is 1NF.
(c) D = {R1(B, C), R2(A, D), R3(B, D)}
(d) D is both loss-less and dependency preserving.
3) (a) Since BC does not appear in the RHS of any FD, and {B,C}+  {A, B, C, D}, Hence BC is
part of the key. ABC and BCD are the keys.
(b) Since there is no partial dependency, R is in 2NF. It is also in 3NF because
there exists only one non-key attribute. It is not in BCNF because for the FD D  A, D is
not a key of R. Therefore, the best normal form of R is 3NF.
(c) D = {R1(A, D), R2(B, C, D)}, where each Ri is in BCNF.
(d) D is loss-less but does not preserve the dependency ABC  D.
4) (a) Since A does not appear in the RHS of any FD and A + = {A, B, C, D}, Hence A is the
only candidate key.
(b) Since primary key contains a single attribute, R is in 2NF, but it is not in 3NF
because there exists a FD between non-key attributes i.e. BC  D. Therefore, the best
normal form of R is 2NF.
(c) D = {R1(B, C, D), R2(A, B, C)}
(d) D is both loss-less and dependency preserving.
5) (a) AB, BC, CD, AD are the keys of R.
(b) If AB is considered as PK, there is no FD between non-key attributes. Hence, R is in
3NF. It is not in BCNF because for the FD: C  A, C is not a key. Therefore, The best
normal form of R is 3NF.
(c) D = { R1(A, C), R2(B, D), R3(C, D)}
(d) D is loss-less but does not preserve dependency.

Multivalued Dependency (MVD):

Let R be a relation scheme and X and Y be subsets of the attributes of R. The multivalued
dependency X  Y (X multi-determines Y) is said to hold over R if in every legal instance r
of R, each X value is associated with a set of Y values and this set is independent of the
values in the other attributes.

In other words, X  Y holds on R if for all pair of tuples t1 and t2 in r, if t1 and t2 have
same value for X then we must get two tuples t3 and t4 in r by interchanging Y value for t1
and t2.

Dr. A. K. Panda
 Example:

EPS Emp-id Proj-id Skill EPS Emp-id Proj-id Skill

101 P1 Coding 101 P1 Coding
P2 Testing 101 P1 Testing
Maintenance 101 P1 Maintenance
102 P2 Analysis 101 P2 Coding
P3 Coding 101 P2 Testing
1. Each employee is assigned to multiple projects. 101 P2 Maintenance
2. Each employee has multiple skills. 102 P2 Analysis
3. Projects that are assigned to an employee are 102 P2 Testing
independent of the skill of the employee. 102 P3 Analysis
102 P3 Testing

The multivalued facts about employees are independent of each other.

Hence, Emp-id  Proj-id and Emp-id  Skill

Inference rules for multivalued dependencies:

Rule 1:Reflexivity (inclusion): If Y X, then X  Y.

Rule 2:Augmentation: If X  Y and Z  W, then WX  YZ.

Rule 3:Transitivity: If X  Y and Y Z then X  (Z – Y).

Rule 4: Complementation: If X  Y, then X  R – XY.

Rule 5: Replication: If X  Y, then X  Y.

Rule 6: Coalescence: If X  Y and there is a W such that W  Y is empty, W

 Z and Z  Y, then X  Z.

Trivial and Nontrivial MVD: An MVD X  Y in a relation R is called a trivial MVD if

a) Y is a subset of X, or
b) X  Y = R.

Otherwise, it is called a non-trivial MVD.

Dr. A. K. Panda
Fourth Normal Form (4NF):

A relation R is said to be in fourth normal form (4NF) if it is in BCNF and for every non-
trivial MVD X  Y that holds over R, X is a super key for R.

Example:

STB Subject Teacher Book

DBMS AKP Navathe
DBMS AKP Korth
DBMS PSK Navathe
DBMS PSK Korth
PC AKP Navathe
PC AKP Walpole
PC AKP Trivedi

Subject  Teacher and Subject  Book.

The relation STB is not in 4NF because Subject  Teacher is a nontrivial MVD and
Subject is not a key. Hence the relation STB can be decomposed into two relations ST
(Subject, Teacher) and SB (Subject, Book). Each of these relations is in 4NF.

Algorithm for decomposition into 4NF:

Input: A relation scheme R that is not in 4NF and a set functional and multivalued
dependencies F of R.

Output: A decomposition D = {R1, R2, …, Rk}, where each Ri is in 4NF.

1. Initialize D = R.
2. repeat
Choose a relation scheme Ri in D that is not in 4NF
if X  Y be a MVD of Ri that violates 4NF then
replace Ri in D by two relation schemes Ri – Y and X  Y.

until each Ri in D is in 4NF.

Note: This algorithm guarantees Lossless but does not guarantee dependency preserving.

Ques: Explain why 4NF is a normal form more desirable than BCNF.

Ans: 4NF is more desirable than BCNF because it reduces the repetition of information. If
we consider a BCNF schema not in 4NF, we observe that decomposition into 4NF does not

Dr. A. K. Panda
loose information provided that lossless join decomposition is used, yet redundancy is
reduced.

Join Dependency (JD): A Join dependency (JD) denoted by JD (R1, R2, …, Rn) is said to hold
over a relation schema R if R1, R2, …, Rn is a lossless-join decomposition of R.

Trivial Join Dependency: A join dependency specified on a relation schema R is said to a

trivial JD if one of the relation schema Ri in JD (R1, R2, …, Rn) is equal to R.

Fifth Normal Form (5NF): It is also called Project Join Normal Form (PJNF). A relation R is
said to be in fifth normal form (5NF) if for every JD (R 1, R2, …, Rn) that holds over R, one of
the following conditions is satisfied.

 The join dependency is trivial.

 Every Ri is a super key of R.

In other words, a relation R is in 5NF if it is 4Nf and it cannot be further non-loss

decomposed.

Example:

SPL Supplier Part Location

S1 P1 L2
S1 P2 L1
S2 P1 L1
S1 P1 L1
The relation SPL is in 4NF.
There exists a non trivial join dependency JD (R 1, R2, R3) as given below:

S P P L L S
S1 P1 P1 L2 L2 S1
S1 P2 P2 L1 L1 S1
S2 P1 P1 L1 L2 S2

Join

SPL Supplier Part Location

S1 P1 L2
S1 P2 L1
S2 P1 L1
Dr. A. K. Panda
S1 P1 L1
 Hence the relation SPL is not in 5NF which is decomposed into three 5NF relations:

R1 (Supplier, Part), R2 (Part, Location) and R3 (Location, Supplier), where each Ri is

in 5NF.

EXERCISE

No.1: Consider the following collection of relations and dependencies. Assume that each
relation is obtained through decomposition from a relation with attributes ABCDEFGHI and
that all the known dependencies over relation ABCDEFGHI are listed for each question.
(The questions are independent of each other, obviously, since the given dependencies
over ABCDEFGHI are different.) For each (sub) relation:
(a) State the strongest normal form that the relation is in.
(b) If it is not in BCNF, decompose it into a collection of BCNF relations.

1. R1(A,C,B,D,E), A → B, C → D
2. R2(A,B,F), AC → E, B → F
3. R3(A,D), D → G, G → H
4. R4(D,C,H,G), A → I, I → A
5. R5(A,I,C,E)

Answer:
1. 1NF. BCNF decomposition: D = {R1(AB), R2(CD), R3(ACE)}.
2. 1NF. BCNF decomposition: D = { R1(AB), R2(BF)}
3. BCNF.
4. BCNF.
5. BCNF.

NO.2: A relation R (A, B, C) has the FDs AB  C and C  A. Is R is in 3NF or in BCNF?

Justify your answer.

Ans: R is not in 3NF because there is only one non-key attribute. It is not in BCNF because
in the FD: C  A, C is not a key of R.

No. 3: A relation R (A, B, C, D) has FD C  B. Is R is in 3NF? Justify your answer.

Ans: R is not in 3NF because C  B is a FD between non-key attributes.

No. 4: Give an example of a relation scheme, R and a set of dependencies such that R is in
BCNF but is not in 4NF.

Ans: R(A, B, C, D, E) with a set of dependencies:

Dr. A. K. Panda
 A →→ BC,
B →→ CD
E →→ AD

No. 5: Prove that any relation scheme with two attributes is in BCNF.

Ans: Consider a relation scheme R (A, B). The only possible non-trivial FDs are A  B and
B  A. There are four possible cases:
1. No FD holds in R. In this case, the key is {A, B} and the relation satisfies BCNF.
2. Only A  B holds. In this case, the key is {A} and the relation satisfies BCNF.
3. Only B  A holds. In this case, the key is {B} and the relation satisfies BCNF.
4. Both A  B and B  A hold. In this case, there are two keys {A} and {B} and
the relation satisfies BCNF.

No.6: Consider the following relations:

CAR_SALE (Car#, Date-sold, Salesman#, Commission%, Discount-amt)
Assume that a car may be sold by multiple salesmen and hence {Car#, Salesman#} is
the primary key. Additional dependencies are: Date-sold  Discount-amt and
Salesman#  Commission%. Based on the given primary key, is this relation in 1NF,
2NF, or 3NF? Why or why not? How would you successively normalize it
completely?
Ans: The relation is in 1NF but not in 2NF.
To normalize,
2NF decomposition:
R1(Car#, Date-sold, Discount-amt)
R2(Car#, Salesman#)
R3(Salesman#, Commission%)
3NF decomposition:
R1(Car#, Date-sold)
R2(Date-sold, Discount-amt)
R3(Car#, Salesman#)
R4(Salesman#, Commission%)

Dr. A. K. Panda
 1

TRANSACTION PROCESSING

Transaction: It is a single execution of a program. Executing the same program several

times will generate several transactions. A transaction is a series of Reads and Writes of
database objects.

Example:

Read (A);

A = A + 1;

Write (A).

Properties of Transaction:

There are four important properties of transactions:

1. Atomicity: A transaction is an atomic unit of processing. It is either performed in its

entirely or not performed at all. It is also called all-or-nothing property.
2. Consistency Preservation: Each transaction run by itself with no concurrent
execution of other transactions must preserve the consistency of the database. It
means that if a transaction is successful, then the database must reflect the new
changes. If it fails, then the database must be returned to its previous state.
3. Isolation: Transactions are isolated or protected from the effects of concurrently
scheduling of other transactions. If several transactions are executed concurrently
then the results must be same as if they were executed serially in some order.
4. Durability: The effect of a completed or committed transaction should persist even
after a system’s failure. Once a transaction commits, then a change is made in the
database and this change must not be lost because of any failure.

Transaction States and Actions:

Read/ Write
Begin T End T Commit
Active Partially Committed
Committed

Abort Abort

Failed Terminated

Dr. A. K. Panda
2

Transaction Actions: There are 5 actions of transaction

1. Begin- Transaction: marks the beginning of each transaction.

2. Read or, Write: specify read or write operations on the database items.
3. End-Transaction: specifies that READ and WRITE operations have ended and
marks the end of transaction execution.
4. Commit-Transaction: indicates that the transaction is completed successfully.
5. Abort or, Rollback: indicates that transaction is completed unsuccessfully.

Transaction States:

1. Active State: It is the initial state. The transaction stays in this state while it
is executing.
2. Partially committed State: When the final statement has been executed, we say the
transaction is in partially committed state.
3. Failed State: When the normal execution can no longer proceed, we say that
the transaction is in failed state.
4. Committed State: When a transaction is completed successfully, it comes to
committed state.
5. Terminated State: It is the final state. When transaction is leaving the system, we
say that it is in terminated state.

Schedule:

A schedule is a sequence of actions or operations (for example, reading, writing,

aborting or committing) that is constructed by merging the actions of a set of transactions,
respecting the sequence of actions within each transaction.

Transaction Transaction
T1 T2
Read A
Write A
Read B
Write B
Read C
Write C

Dr. A. K. Panda
3

Types of Schedule:

There are 5 types of schedules namely:

1. Complete Schedule
2. Serial Schedule
3. Non-serial schedule
4. Equivalent Schedule
5. Serializable Schedule

1. Complete Schedule: A schedule that contains either an abort or a commit for each
transaction, whose actions are listed in it, is called a complete schedule.

2. Serial Schedule: A schedule is said to be a serial schedule if the actions of different

transactions are not interleaved. A schedule is serial if its actions consist of all the actions
of one transaction, then all the actions of another transaction, and so on, with no mixing of
the actions.

3. Non-serial Schedule: A schedule in which the operations from a group of concurrent

transactions are interleaved is called a non-serial schedule.

4. Equivalent Schedule: Two schedules are said to be equivalent schedules if they produce
the same result on any database state. Two equivalent schedules always produce identical
results.

5. Serializable Schedule: A non-serial schedule that is equivalent to some serial execution

of transactions is known as a Serializable schedule. A schedule is Serializable if its effect on
the database state is same as that of some serial schedule, regardless of what the initial
state of the database is.

Example:

Consider two transactions T1 and T2 in the following non-serial schedule S1; T1 transfers Rs.
1000 from A/C A to A/C B and T2 transfers Rs. 2000 from A/C B to A/C C:

Dr. A. K. Panda
4

Schedule S1 Schedule S2 Schedule S3

Transaction Transaction Transaction Transaction Transaction Transaction

T1 T2 T1 T2 T1 T2
Read A Read A Read B
Read B A = A – 1000 B = B – 2000
A = A – 1000 Write A Write B
B = B – 2000 Read B Read C
Write A B = B + 1000 C = C + 2000
Write B Write B Write C
Read B Read B Read A
Read C B = B – 2000 A = A – 1000
B = B + 1000 Write B Write A
C = C + 2000 Read C Read B
Write B C = C + 2000 B = B + 1000
Write C Write C Write B

The effect of schedule S1 is same as effect of two serial schedules S 2 and S3. Hence the
schedule S1 is Serializable.

Schedule S4

Transaction T1 Transaction T2 Effect of Database

Read A A = 5000, B = 6000, C = 7000
A = A – 1000 A = 5000, B = 6000, C = 7000
Read B A = 5000, B = 6000, C = 7000
Write A A = 4000, B = 6000, C = 7000
B = B – 2000 A = 4000, B = 6000, C = 7000
Read B A = 4000, B = 6000, C = 7000
Write B A = 4000, B = 4000, C = 7000
B = B + 1000 A = 4000, B = 4000, C = 7000
Read C A = 4000, B = 4000, C = 7000
Write B A = 4000, B = 8000, C = 7000
C = C + 2000 A = 4000, B = 8000, C = 7000
Write C A = 4000, B = 8000, C = 9000

The effect of S4 is not same as any serial schedule (S2 or S3). Hence S4 is non-Serializable.

Dr. A. K. Panda
5

Conflicts:

Two actions in a schedule are said to conflict if they satisfy all three of the following
conditions:

1. They belong to different transactions.

2. They access the same data item X.
3. At least one of them is a Write(x).

In Serializability, the order of read and write operations are important and the following
serializability rules are given below:

 If two transactions only read a data item, they do not conflict and the order is not
important.
 If two transactions either read or write completely separate data items, they do not
conflict and the order is not important.
 If one transaction writes a data item and another either reads or writes the same
data item, the order of execution is important.

Types of Serializability:

1. Conflict Serializability:

A schedule S is said to be conflict Serializable if it is conflict equivalent to a serial schedule.

Conflict Equivalence: Two schedules S1 and S2 are said to be conflict equivalent if they can
be turned one into the other by a sequence of non-conflicting swaps of adjacent actions.

Example: Consider the following non serial schedule S5 :

Schedule S5

Transaction Transaction
T1 T2
Read A
Write A
Read A
Write A
Read B
Write B
Read B
Write B

Dr. A. K. Panda
6

The above schedule can be converted into a serial schedule by non-conflicting swaps of
adjacent actions as given below:

Initial Schedule S5 Stage 1: Schedule S5 Stage 2: Schedule S5

Transaction Transaction Transaction Transaction Transaction Transaction

T1 T2 T1 T2 T1 T2
Read A Read A Read A
Write A Write A Write A
Read A Read A Read B
Write A Read B Read A
Read B Write A Write A
Write B Write B Write B
Read B Read B Read B
Write B Write B Write B

Stage 3: Schedule S5 Stage 4: Schedule S5

Transaction Transaction Transaction Transaction

T1 T2 T1 T2
Read A Read A
Write A Write A
Read B Read B
Read A Write B
Write B Read A
Write A Write A
Read B Read B
Write B Write B

2. View Serializability:

A schedule S is said to be view Serializable if it is view equivalent to a serial schedule.

View Equivalence: Two schedules S1 and S2 are said to be view equivalent if following
three conditions are satisfied:

1. For each data item X, if transaction Ti reads the initial value of X in schedule S 1, then
transaction Ti must in schedule S2, also read the initial value of X.
2. For each data item X, if transaction T i executes Read(X) in schedule S1 and if that
value was produced by a Write(X) operation executed by Transaction T j, then the
Read(X) operation of Transaction Ti must in schedule S2 also read the value of X that
was produced by the same Write(X) operation of transaction T j.

Dr. A. K. Panda
7

3. For each data item X, the transaction (if any) that performs the final Write(X)
operation in schedule S1 must perform the final Write(X) operation in schedule S 2.

Algorithm for serializability Test:

Input: Schedule S for the concurrent execution Transactions T 1, T2, … …, Tk.

Output: A decision whether S is Serializable.

1. For each transaction Ti participating in schedule S, create a node labeled T i in the

precedence graph.
2. For each case in S, where Tj executes a Read(X) after Ti executes a Write(X), create a
directed edge from Ti to Tj.
3. For each case in S, where Tj executes a Write(X) after Ti executes a Read(X), create a
directed edge from Ti to Tj.
4. For each case in S, where Tj executes a Write(X) after Ti executes a Write(X), create a
directed edge from Ti to Tj.
5. If the Precedence graph has no cycles, then the schedule S is Serializable,
else
Schedule S is Non-Serializable.

Example: Consider the following Schedule S6

Transaction Transaction T2 Transaction

T1 T3
Read A
Read (B)
A = f1(A)
Read(C)
B = f2(B)
Write(B)
C = f3(C)
Write(C)
Write A
Read(B)
Read(A)
A = f4(A)
Read C
Write(A)
C = f5(C)
Write(C)
B = f6(B)
Write(B)

Dr. A. K. Panda
8

Precedence Graph of S6:

T1 T2

T3

Since, the precedence graph contains a cycle; the schedule S 6 is non-serializable.

Example: Consider the following Schedule S7:

Transaction Transaction T2 Transaction

T1 T3
Read A
A = f1(A)
Read C
Write A
C = f2(C)
Read (B)
Write(C)
Read(A)
Read(C)
B = f3(B)
Write(B)
C = f4(C)
Read(B)
Write(C)
A = f5(A)
Write(A)
B = f6(B)
Write(B)

T1 T2
Precedence Graph of S7:

T3

Recoverability:

The process of restoring the database to a correct state in the event of a failure is called
database recovery. If a transaction fails we need to undo the effect of the transaction and
bring the database to the consistent state prior to the start of the transaction. So when a

Dr. A. K. Panda
9

transaction aborts, all the transactions dependent on the aborted transaction also should
be aborted and rolled back.

There are three types of schedules based on recoverability:

1. Recoverable Schedule: A recoverable schedule is one where, for each pair of

transactions T1 and T2, for T2 to read a data item previously written by T 1, the commit
operation of T1 should appear before the commit operation of T 2.

Example:
Non-recoverable Schedule S8

Transaction Transaction
T1 T2
Read A
Write A
Read A
Write A
Commit
Read B
…
…

In schedule S8, T2 has read the value written by T1. If T1 fails before it commits, we must
abort T2 to ensure atomicity. But this is not possible as transaction T 2 has already been
committed. This situation is an example of non-recoverable schedule.

2. Non-cascading Schedule: A non-cascading schedule is one where, for each pair of

transactions T1 and T2, for T2 to read a data item previously written by T 1, the commit
operation of T1 should appear before the read operation of T 2.

Example:
Cascading Schedule S9

Transaction T1 Transaction T2 Transaction T3

Read A
Write A
… Read A
… Read B
… Write B
… … Read B
… …

In Schedule S9, T1 writes a value that is read by T2. T2 writes a value that is read by T3.
Suppose at that point transaction T1 fails, so T1 is rolled back. Since T2 is dependent on T1, it
also should be rolled back. Since T 3 is dependent on T2 it too has to be rolled back. This

Dr. A. K. Panda
10

phenomenon, in which a single transaction failure leads to a series of rollbacks, is called a

cascading rollback.

Cascading rollback is not desirable, as it leads to undoing a significant amount of work.

3. Strict Schedule: A schedule in which transactions can neither read nor write a data item
‘X’ until the last transaction that wrote the data item ‘X’ has committed or aborted.

Example:
Strict Schedule S10 Strict Schedule S11

Transaction Transaction Transaction Transaction

T1 T2 T1 T2
Read A Read A
Write A Write A
Commit Abort
Read A Read A
Write A Write A
… …

Dr. A. K. Panda
11

CONCURRENCY CONTROL

It is the process of managing simultaneous execution transactions in a multiprocessing

database system without having them interfere with one another. This property of DBMS
allows many transactions to access the same database at the same time without interfering
with each other.

Need of Concurrency Control:

Concurrency control is needed to avoid following three concurrency problems:

1. Lost update Problem: A successfully completed update operation by one user can be
overwritten by another user. This is known as lost update problem.

Example: Suppose T1 is executing concurrently with transaction T2. T1 is withdrawing Rs.

100 from an account with balance A, initially Rs. 5000 and T 2 is depositing Rs. 1000 into the
same account. If the transactions are executed serially, one after the other with no
interleaving of operations, the final balance would be Rs. 5900.

Schedule S12

Transaction Transaction T2 A/C

T1 Balance
Read A 5000
Read A 5000
A = A + 1000 5000
A = A – 100 5000
Write A 6000
Write A 4900
Commit 4900
Commit 4900

Here T2’s update is lost.

2. Uncommitted dependency Problem/ Dirty read problem: The uncommitted

dependency problem occurs when one transaction is allowed to see the intermediate
results of another transaction before it is committed.

Dr. A. K. Panda
12

Example: Schedule S13

Transaction Transaction T2 A/C

T1 Balance
Read A 5000
A = A + 1000 5000
Write A 6000
Read A 6000
A = A – 100 Abort 6000
Write A 5900
Commit 5900

Since the transaction T2 has aborted, the database should be restored to the original state.
But before the roll back is performed, transaction T 1 reads the A/C balance and starts
executing. So instead of a balance of 4900 (since only T 1 was committed), it is ended with a
wrong result of 5900. This is happened only because T 1 was permitted to read the
intermediate result of transaction T2.

This read is known as Dirty Read and the problem is known as dirty read problem.

3. Inconsistent Analysis Problem: The problem of inconsistent analysis occurs when a

transaction reads several values but a second transaction updates some of them during the
execution of the first.

Example: Suppose that there are two concurrent transactions T 1 and T2, where T2 is
totaling the balances of A/C A (Rs. 4000), A/C B (Rs. 5000) and A/C C (Rs. 3000) and T 1 is
transferring Rs.500 from A/C A to A/C C.

Schedule S14

Transaction Transaction T2 Effect of Database

T1
Sum = 0 A = 4000, B = 5000, C = 3000, Sum = 0
Read A A = 4000, B = 5000, C = 3000, Sum = 0
Read A A = 4000, B = 5000, C = 3000, Sum = 0
A = A – 500 A = 4000, B = 5000, C = 3000, Sum = 0
Sum = Sum + A A = 4000, B = 5000, C = 3000, Sum = 4000
Write A A = 3500, B = 5000, C = 3000, Sum = 4000
Read B A = 3500, B = 5000, C = 3000, Sum = 4000
Read C A = 3500, B = 5000, C = 3000, Sum = 4000
Sum = Sum + B A = 3500, B = 5000, C = 3000, Sum = 9000
C = C + 500 A = 3500, B = 5000, C = 3000, Sum = 9000
Write C A = 3500, B = 5000, C = 3500, Sum = 9000
Read C A = 3500, B = 5000, C = 3500, Sum = 9000

Dr. A. K. Panda
13

Sum = Sum + C A = 3500, B = 5000, C = 3500, Sum = 12500

Print Sum A = 3500, B = 5000, C = 3500, Sum = 12500

If Rs. 500 is transferred from A/C A to A/C C, Total Balance of three A/Cs should remain
same i.e. Rs. 12000. But effect of the above schedule is total balance is Rs. 12500.

Different Concurrency Control Techniques:

1. Binary Locking Technique:

It is a procedure used to control concurrent access to data. When one transaction is

accessing the database, a lock may deny access to other transactions to prevent incorrect
results. A binary lock has two states- Locked and Unlocked.

If Lock (A) = 1, then item A cannot be accessed.

If Lock (A) = 0, then item A can be accessed.

A transaction T requests an access to an item A by issuing a Lock (A) operation. If Lock (A)
= 1, the transaction is forced to wait. If Lock A) = 0, then transaction T is allowed to access
item A. When T’s access is over, it issues an unlock (A) operation which sets Lock (A) to 0.

Example: Consider the following schedule:

Schedule S15

Transaction T1 Transaction T2
Read A
Read A
A=A–1
A=A+1
Write A
Write A

Due to concurrent execution of transactions the update of T 1 is lost. The problem can be
solved by providing a lock on item A.

Dr. A. K. Panda
14

Transaction Transaction
T1 T2
Lock (A)
Read A
A=A–1
Write A
Unlock (A)
Lock (A)
Read A
A=A+1
Write A
Unlock (A)

Rule followed during Binary Locking: Each transaction (say, T) must follow the following
rules:

1. A transaction T must issue Lock (A) operation before any Read (A) or Write (A)
operations are performed in T.
2. T must issue the Unlock (A) operation after all Read (A) and Write (A) operations
are completed in T.
3. T will not issue a Lock (A) operation if it already holds the lock on item A.
4. T will not issue an Unlock (A) operation unless it already holds the lock on item A.
5. At most only one transaction can hold the lock on a particular item.

Note: Binary locking does not guarantee serializability.

Example: Consider the following Schedule S16.

Transaction Transaction T2 Transaction

T1 T3
Lock (A)
Lock (B)
Lock (C)
Unlock (B)
Lock (B)
Unlock (A)
Lock (A)
Unlock (C)
Unlock (A)
Lock (A)
Lock (C)
Unlock (B)
Unlock (C)
Unlock (A)

Dr. A. K. Panda
15

The above schedule follows Binary locking protocol, but the schedule is not Serializable
whose precedence graph is given below.

T1 T2

T3

Example: Consider the following Schedule S17. There are two concurrent transactions T1
and T2, where T2 is totaling the balances of A/C A (Rs. 4000) and A/C B (Rs. 3000) and T 1 is
transferring Rs.100 from A/C A to A/C B.

Transaction Transaction T2 Effect of Database

T1
Lock (A) A = 4000, B = 3000
Read A A = 4000, B = 3000
A = A – 100 A = 4000, B = 3000
Write A A = 3900, B = 3000
Unlock (A) A = 3900, B = 3000
Lock (A) A = 3900, B = 3000
Read A A = 3900, B = 3000
Lock (B) A = 3900, B = 3000
Read B A = 3900, B = 3000
Sum = A + B A = 3900, B = 3000
Print (Sum) A = 3900, B = 3000, Sum =
Unlock (B) 6900
Unlock (A) A = 3900, B = 3000, Sum =
Lock (B) 6900
Read B A = 3900, B = 3000, Sum =
B = B + 100 6900
Write B A = 3900, B = 3000, Sum =
Unlock (B) 6900
A = 3900, B = 3000, Sum =
6900
A = 3900, B = 3000, Sum =
6900
A = 3900, B = 3100, Sum =
6900
A = 3900, B = 3100, Sum =
6900

The above schedule S17 is non0serializable because total balance is not equal to 7000.

Dr. A. K. Panda
16

2. Shared/ exclusive (Read/ Write) Locking Technique:

When several transactions try to access the same data item for reading purpose only, then
we should allow the access. But, if a transaction is to write an item A, it must have exclusive
access to A. For this purpose there are two modes of locking:

Shared Lock (Read Lock): The intention of this mode of locking is to ensure that the data
item does not undergo any modifications while it is locked in this mode. Any number of
transactions can concurrently lock and access a data item in the shared mode. But none of
them can modify it. A data item locked in the shared mode cannot be locked in the exclusive
mode until the shared lock is released.

Exclusive Lock (Write Lock): The intention of this mode of locking is to provide exclusive
use of the data item to one transaction. If a transaction has Write lock on a data item, it can
both read and update the data item and no other transaction issue a shared or exclusive
lock until write lock is released.

Rule followed during Shared/ exclusive Locking: Each transaction (say, T) must follow
the following rules:

1. Any transaction that needs to access a data item must first lock the item requesting
a read lock for read only access or a write Lock for both read access and write
access.
2. If the item is not already locked by other transaction, the lock will be granted.
3. If the item is currently locked, the Database system determines whether the request
is compatible with the existing lock. If a read lock is requested on an item that
already has a read lock on it, the request will be granted otherwise, the transaction
must wait until the existing write lock is released.
4. A transaction continues to hold a lock until it explicitly releases it either during
execution or, when it terminates (aborts or commits). It is only when the write lock
has been released that the effects of the write operation will be made visible to
other transactions.

Note: Shared/ exclusive (Read/ Write) Locking does not guarantee serializability.

Example: Consider the following Schedule S18 where T1 is a transaction that transfers Rs.
1000 from A/C A to A/C B and T2 is a transaction that increases A and B by 10%.

Dr. A. K. Panda
17

Transaction Transaction T2 Effect Of Database

T1
Wlock (A)
Read (A)
A = A – 1000
Write (A)
Unlock (A)
Wlock(A)
Read (A)
A = A + A*0.10
Write (A)
Unlock (A)
Wlock (B)
Read (B)
B = B + B*0.10
Write (B)
Unlock (B)
Wlock (B)
Read (B)
B = B + 1000
Write (B)
Unlock (B)

The above Schedule follows R/W Locking protocol but non-Serializable whose precedence
graph is given below:

T1 T2

Test of serializability for schedules with Read/ Write Locks:

Input: Schedule S for the concurrent execution Transactions T 1, T2, … …, Tk.

Output: A decision whether S is Serializable.

1. For each transaction Ti participating in schedule S, create a node labeled T i in the

precedence graph.
2. For each case in S, where Tj issues a Rlock (X) after Ti issues a Wlock (X), create a
directed edge from Ti to Tj.
3. For each case in S, where Tj issues a Wlock (X) after Ti issues a Rlock (X), create a
directed edge from Ti to Tj.

Dr. A. K. Panda
18

4. For each case in S, where Tj issues a Wlock(X) after Ti issues a Wlock (X), create a
directed edge from Ti to Tj.
5. If the Precedence graph has no cycles, then the schedule S is Serializable,
else
Schedule S is Non-Serializable.

3. Two-phase locking (2PL):

It is a method or a protocol of controlling concurrent processing in which all locking

operations precede the first unlocking operation. Thus, a transaction is said to follow the
two-phase locking protocol if all locking operations precede the first unlocking operation in
the transaction.

Thus, each transaction of a schedule consists of two phases:

1. Expanding Phase/Growing Phase/ Acquire Phase: in which a transaction acquires all

the locks needed but cannot release any locks.
2. Shrinking Phase/ Release Phase: in which a transaction releases all locks but cannot
acquire any new locks.

Rules for 2PL:

 A transaction must acquire a lock on an item before operating on the item. The lock
may be Rlock or Wlock depending on the type of access needed.
 Once a transaction releases a single lock, it can never acquire any new lock.

Advantage of 2PL: 2PL guarantees Serializability.

Theorem: If S is any schedule of two phase transactions, then S is Serializable.

Proof: Assume that S is non-serializable.

 The precedence graph G for S has a cycle T1  T2  … …  Tp  T1.

 Some lock by T2 follows an unlock by T1, some lock by T3 follows an unlock by T2
and so on and finally a lock by T1 follows an unlock by Tp.
 A lock of T1 follows an unlock by T1, which is a contradiction

 S is serializable (Proved).

Limitation of 2PL:

There are two problems associated with 2PL protocols:

a) Cascading rollback
b) Deadlock

Dr. A. K. Panda
19

a) Cascading rollback: It is a phenomenon in which a single rollback leads to a series of

transaction rollbacks.

How to solve cascading rollback Problem?

There are two solutions to this problem:

 Strict two-phase locking protocol.

 Rigorous two-phase locking protocol.

Strict two-phase Locking (Strict 2PL):

A transaction is said to follow strict two-phase locking protocol if it follows two-phase

locking protocol and all exclusive locks taken by the transaction must be held until the
transaction commits. Cascading rollback can be avoided by using strict 2PL.

Rigorous two-phase locking protocol:

A transaction is said to follow rigorous two-phase locking protocol if it follows two-phase

locking protocol and all locks (shared or exclusive) taken by the transaction must be held
until the transaction commits. With rigorous 2PL, transactions can be serialized in the
order in which they commit.

Deadlock:

A deadlock is a condition in which two or more transactions in a set are each waiting for
locks held by some other transaction in the set. Neither transaction can continue because
each transaction in the set is on the queue, waiting for one of the other transactions in the
set to release the lock on an item.

Schedule S19
Transaction Transaction
T1 T2
Wlock (A)
Wlock (B)
Read A
Read B
A = A – 100
B = B + 1000
Write A
Write B
Wlock (B)
WAIT Wlock (A)
WAIT WAIT
WAIT WAIT

Dr. A. K. Panda
20

… …

There are two general techniques for handling deadlock:

1. Deadlock prevention
2. Deadlock detection and recovery

1. Deadlock Prevention:

In deadlock prevention the DBMS looks ahead to determine if a transaction would cause a
deadlock and never allows a deadlock to occur. There are two approaches to prevent
deadlock:

a) Using Time Stamp: Time stamp is a unique identifier created by the DBMS that
indicates the relative starting time of each transaction. In this approach DBMS
decides whether to wait or abort and rollback a transaction by using any one of
following two techniques:
(i) Wait-Die:
 If the requesting transaction Ti is older than the transaction Tj that
holds the lock on the requested data item (TS [Ti]  TS [Tj]) then the
requesting transaction Ti is allowed to wait.
 If the requesting transaction Ti is younger than the transaction Tj (TS
[Ti]  TS [Tj]) then the requesting transaction Ti is aborted (Ti dies)
and restarted with the same time stamp.
(ii) Wound-Wait:
 If the requesting transaction Ti is older than Tj (TS [Ti]  TS [Tj]) then
Tj is aborted and restarted with the same time stamp (the younger
transaction is wounded or suspended by the older transaction).
 If TS [Ti]  TS [Tj] then Ti is allowed to wait.

b) Not using Time Stamp:

(i) No waiting (NW) Method: If a transaction is unable to obtain a lock, it is
immediately aborted and then restarted after a certain time delay without
checking whether a deadlock will actually occur or not.
(ii) Cautious waiting Method: Suppose that Transaction Ti tries to obtain a lock
an item A previous locked by transaction Tj
 If Tj is not blocked (not waiting for some other locked item) then T i is
blocked and allowed to wait,
Otherwise, Ti is aborted.

Dr. A. K. Panda
21

 If both are blocked, then find block times b(Ti) and b(Tj) of Ti and Tj
respectively then
if b[Ti]  b[Tj] then Ti is blocked and allowed to wait Tj.

2. Deadlock detection and recovery:

Deadlock detection is usually handled by the construction of wait-for graph (WFG),

showing the transaction dependencies. The WFG is constructed as follows:

(i) Create a node for each transaction.

(ii) Create a directed edge from Ti to Tj if transaction Ti is waiting to lock an item that is
currently locked by Tj.
(iii) If WFG contains a cycle, then Deadlock occurs.

Recovery from deadlock: To recover from a deadlock, the cycles in the WFG must be
broken. The most common method of doing this is to rollback one or more transactions in
the cycles until the system exhibits no further deadlock situation. Choosing which
transaction to rollback is known as victim selection.

4. Timestamp Ordering:

In this method, a serial order is created among the concurrent transactions by assigning to
each transaction a unique non decreasing number called timestamp. Besides the timestamp
of each transaction, each data item has two timestamps: read timestamp and write
timestamp.

 RTS(X): This is the largest time stamp among all transactions that have successfully
read item X.
 WTS(X): This is the largest of all timestamps of transactions that have
successfully written item X.

Procedure:

1. If transaction T needs to read an item X that has already updated by a younger

transaction i.e. TS [T]  WTS [X], then T is aborted and restarted with a new time
stamp.
2. If transaction T needs to write an item X whose value has already been read by a
younger transaction i.e. TS [T]  RTS [X] then, T is aborted and restarted with a new
timestamp.
3. If transaction T needs to write an item X whose value has already been written by a
younger transaction, i.e. TS [T]  WTS [X] then the write operation is ignored.

Dr. A. K. Panda
22

Example: Consider the following schedule S20 that follows Time stamp ordering and the
schedule is serializable.

Schedule S20 A B
Transaction Transaction Transaction RTS = 0 RTS = 0
T1 T2 T3 WTS = 0 WTS = 0
(Time Stamp (Time stamp (Time Stamp
10) 11) 12)
Read A RTS =
A = A – 100 10
Write A
Read B Read A WTS = RTS = 10
B = B + 100 A = A – 500 10
Write B Write A RTS = WTS = 10
Read B Read A 11 RTS = 11
B = B + 500
Write B WTS = WTS = 11
Read B 11 RTS = 12
C=A+B RTS =
Print C 12

Note: Time stamp ordered schedulers does not create deadlock, they may lead to livelock.

5. Multiversion concurrency control Technique:

In Multiversion concurrency control schemes, each Write(X) creates a new version of X.

When a Read(X) is issued, the scheduler selects the version of X to be read.

Let {X1, X2, …, Xn} denote the versions of a data item X. Besides its value, each version Xi
contains following two timestamps.

Dr. A. K. Panda
23

1. RTS (Xi): The read time stamp of Xi is the largest of all the timestamps of
transactions that have successfully read the version X i.
2. WTS (Xi): The write timestamp of Xi is the timestamp of the transaction that
created the version Xi.

In this scheme, if a transaction Tj successfully executes Write(X) , a new version X n + 1 of X is

created with RTS (Xn + 1) = WTS (Xn + 1) = TS (Tj)

The read timestamp of version X i is updated whenever a transaction Tk with TS (Tk)  RTS
(Xi) reads the version Xi and RTS (Xi) is changed to RTS (Xi) = TS (Tk)

To ensure serializability, the following two rules are used:

1. If transaction T issues a Read(X) operation, find the version of X (say Xj) that has the
largest WTS (Xj) value that is also less than or equal to TS (T); then return the value
of Xj to T and update RTS (Xj) as follows:
RTS (Xj) = Max [ TS (T), RTS (Xj)
2. If transaction T issues a Write(X) operation, and the version of X (say Xj) that has
the largest WTS (Xj) value that is also less than or equal to TS (T); then abort and
rollback.
Otherwise,
Create a new version of X (say Xj + 1) with RTS (Xj + 1) = WTS (Xj + 1) =TS (T)

6. Validation (Optimistic) concurrency control Technique:

In an optimistic concurrency control, execution of a transaction T is classified into

following three phases:

1. Read Phase: The transaction T reads data items from the database and stores these
values in local variables. All write operations are performed on the local variables
without modifying the actual database.
2. Validation Phase: In this phase, appropriate checks are performed to determine
whether the transaction updates can be carried out on the database without causing
violation of serializability.
3. Write Phase: This phase comes after successful completion of the validation phase.
If the validation phase is successful, the transaction updates are applied to the
database; otherwise, the transaction T is rolled back.

Dr. A. K. Panda
24

DATABASE RECOVERY

Database recovery is the process of restoring the database to a correct (consistent) state in
the event of a failure.

Database recovery Techniques:

1. Shadow Paging:

This technique does not require the use of a log file in a single-user environment, though a
log is needed in a multiuser environment for concurrency control. Shadow paging
considers the database to be made up of a number of fixed size disk pages or disk blocks for
recovery purposes.

This technique maintains two directories during the life of a transaction- a current
directory and a shadow directory. When the transaction starts, the two directories are the
same. The shadow directory is saved to the disk and the current directory is used by the
transaction.

During the transaction execution, the shadow directory is never modified. When a write
operation is performed on a data item, a new copy of the modified database page is created,
but the old copy of that page not overwritten. The new copy is written somewhere else. The
current directory entry is modified to point to the disk block. The shadow directory will be
still pointing to the old unmodified disk block as it is not updated and the old disk block is
not overwritten.

2
1
1 3 2
2 3
3 4 4
4 5
5
5 6
6 6 7
7 8
8 7

Current 8 Shadow
Directory Directory
9

10
Dr. A. K. Panda
Pages on disk
25

To recover from a transaction failure, it is sufficient to free the modified database page and
discard the current directory. The state of the database before the start of the transaction is
available through the shadow directory and that state is recovered by reinstating the
shadow directory.

Committing a transaction is done by discarding the shadow directory. Thus the current
directory is used to record all updates to the database. When a transaction completes, the
current directory becomes the shadow directory. Since the recovery using the shadow
paging technique requires neither an undo nor a redo, it is classified as NO-UNDO/ NO-
REDO algorithm.

Advantages of shadow Paging:

 The overhead of maintaining the transaction log file is eliminated.

 Since there are no need for undo or redo operations, recovery is significantly faster.

Disadvantages of Shadow paging:

 Data fragmentation or scattering.

 Need for periodic garbage collection to reclaim inaccessible blocks.

2. The ARIES Algorithm:

ARIES is a recovery algorithm that is designed to work with a steal, no-force approach.
ARIES recovers from a system crash in three phases:

1. Analysis: This phase identifies the dirty pages in the buffer (i.e. the changes that
have not been written to disk) and active transactions at the time of the crash.
2. Redo: This phase repeats all actions, starting from an appropriate point in the log,
and restores the database state to what it was at the time of the crash.
3. Undo: This phase undoes the actions of transactions that did not commit, so that
the database reflects only the actions of committed transactions.

There are three main principles behind the ARIES algorithm:

 Write-ahead logging: Any change to a database object is first recorded in the log;
the record in the log must be written to stable storage before the change to the
database object is written to disk.

Dr. A. K. Panda
26

 Repeating history during Redo: Upon restart following crash, ARIES retraces all
actions of the DBMS before the crash and brings the system back to the exact state
that it was in at the time of the crash.
 Logging changes during Undo: Changes made to the database while undoing a
transaction are logged in order to ensure that such an action is not repeated in the
event of repeated restarts.

Dr. A. K. Panda