1.

Write Short notes on

Data model and its types (Nov 2014)
(or)
Explain the different groups of data models with suitable examples? (Apr 2019)
DATA MODELS IN DBMS
A Data Model is a logical structure of Database. It describes the design of database to reflect
entities, attributes, relationship among data, constrains etc.
Types of Data Models:
Object based logical Models – Describe data at the conceptual and view levels.
1. E-R Model
An entity–relationship model (ER model) is a systematic way of describing and defining a
business process. An ER model is typically implemented as a database. The main components
of E-R model are: entity set and relationship set.

2. Object oriented Model

An object data model is a data model based on object-oriented programming, associating
methods (procedures) with objects that can benefit from class hierarchies. Thus, “objects” are
levels of abstraction that include attributes and behavior
Record based logical Models – Like Object based model, they also describe data at the
conceptual and view levels. These models specify logical structure of database with records,
fields and attributes.
1. Relational Model
In relational model, the data and relationships are represented by collection of inter-related
tables. Each table is a group of column and rows, where column represents attribute of an
entity and rows represents records.
Sample relationship Model: Student table with 3 columns and three records.
Stu_Id Stu_Name Stu_Age
111 Ashish 23
123 Saurav 22
169 Lester 24
2. Hierarchical Model
In hierarchical model, data is organized into a tree like structure with each record is having one
parent record and many children. The main drawback of this model is that, it can have only one to
many relationships between nodes. Sample Hierarchical Model Diagram:
 3. Network Model – Network Model is same as hierarchical model except that it has
graph-like structure rather than a tree-based structure. Unlike hierarchical model, this
model allows each record to have more than one parent record.
Physical Data Models – These models describe data at the lowest level of abstraction.
Three Schema Architecture

The goal of the three schema architecture is to separate the user applications and the physical
database. The schemas can be defined at the following levels:
1. The internal level – has an internal schema which describes the physical storage
structure of the database. Uses a physical data model and describes the complete details
of data storage and access paths for the database.

2. The conceptual level – has a conceptual schema which describes the structure of the
database for users. It hides the details of the physical storage structures, and
concentrates on describing entities, data types, relationships, user operations and
constraints. Usually a representational data model is used to describe the conceptual
schema.

3. The External or View level – includes external schemas or user vies. Each external
schema describes the part of the database that a particular user group is interested in and
hides the rest of the database from that user group. Represented using the
representational data model.

The three schema architecture is used to visualize the schema levels in a database. The three
schemas are only descriptions of data, the data only actually exists is at the physical level.

2. With the help of a neat block diagram explain the basic architecture of a
database management system? (NOV 2015) ( or)
Briefly explain about Database System Architecture? (JUN 2016) (or)
 Explain the overall architecture of the database system in detail? (MAY 2017) (OR)
State and explain the architecture of DBMS? (NOV 2017, Nov 2019)
The architecture of a database system is greatly influenced by the underlying computer system on which the
database system runs. Database systems can be centralized, or client-server, where one server machine executes
work on behalf of multiple client machines. Database systems can also be designed to exploit parallel computer
architectures. Distributed databases span multiple geographically separated machines.

Figure 1.3: Database System Architecture

A database system is partitioned into modules that deal with each of the responsibilities of the overall system. The
functional components of a database system can be broadly divided into the storage manager and the query
processor components. The storage manager is important because databases typically require a large amount of
storage space. The query processor is important because it helps the database system simplify and facilitate access
to data.

It is the job of the database system to translate updates and queries written in a nonprocedural language, at the logical
level, into an efficient sequence of operations at the physical level.

Database applications are usually partitioned into two or three parts, as in Figure 1.4. In a two-tier architecture, the
application resides at the client machine, where it invokes database system functionality at the server machine
through query language statements. Application program interface standards like ODBC and JDBC are used for
interaction between the client and the server. In contrast, in a three-tier architecture, the client machine acts as
merely a front end and does not contain any direct database calls. Instead, 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. The business logic of the
application, which says what actions to carry out under what conditions, is embedded in the application server, instead
of being distributed across multiple clients. Three-tier applications are more appropriate for large applications,
and for applications that run on the WorldWideWeb.
 Figure 1.4: Two-tier and three-tier architectures.

Query Processor:
The query processor components include
· DDL interpreter, which interprets DDL statements and records the definitions in the data dictionary.
· DML compiler, which translates DML statements in a query language into an evaluation plan consisting of
low-level instructions that the query evaluation engine understands.
A query can usually be translated into any of a number of alternative evaluation plans that all give the same
result. The DML compiler also performs query optimization, that is, it picks the lowest cost evaluation plan
from among the alternatives.
Query evaluation engine, which executes low-level instructions generated by the DML compiler.

Storage Manager:

A storage manager is a program module that provides the interface between the lowlevel data stored in the database
and the application programs and queries submitted to the system. The storage manager is responsible for the
interaction with the file manager. The raw data are stored on the disk using the file system, which is usually provided
by a conventional operating system. The storage manager translates the various DML statements into low-level file-
system commands. Thus, the storage manager is responsible for storing, retrieving, and updating data in the
database.
The storage manager components include:
· Authorization and integrity manager, which tests for the satisfaction of integrity constraints and checks the
authority of users to access data.
· Transaction manager, which ensures that the database remains in a consistent (correct) state despite
system failures, and that concurrent transaction executions proceed without conflicting.
· File manager, which manages the allocation of space on disk storage and the data structures used to
represent information stored on disk.
· Buffer manager, which is responsible for fetching data from disk storage into main memory, and deciding what
data to cache in main memory. The buffer manager is a critical part of the database system, since it enables the
database to handle data sizes that are much larger than the size of main memory.

Transaction Manager:
A transaction is a collection of operations that performs a single logical function in a database application. Each
transaction is a unit of both atomicity and consistency. Thus, we require that transactions do not violate any
database-consistency constraints. That is, if the database was consistent when a transaction started, the database
must be consistent when the transaction successfully terminates. Transaction - manager ensures that the database
remains in a consistent (correct) state despite system failures (e.g., power failures and operating system
crashes) and transaction failures.
COMPONENTS OF DBMS
Database Users
Users are differentiated by the way they expect to interact with the system
• Application programmers
• Sophisticated users
• Naïve users
• Database Administrator
• Specialized users etc,.

Application programmers:
Professionals who write application programs and using these application
programs they interact with the database system
Sophisticated users :
These user interact with the database system without writing programs, But they
submit queries to retrieve the information
Specialized users:
Who write specialized database applications to interact with the database system.
Naïve users:
Interacts with the database system by invoking some application programs that
have been written
previously by application programmers
Eg : people accessing database over the web
Database Administrator:
Coordinates all the activities of the database system; the database administrator has a
good understanding of
the enterprise’s information resources and needs.
 Schema definition
 Access method definition
 Schema and physical organization modification
 Granting user authority to access the database
 Monitoring performance
Storage Manager
The Storage Manager include these following components/modules
 Authorization Manager
 Transaction Manager
 File Manager
 Buffer Manager
 Storage manager is a program module that provides the interface between the low-
level data stored in the database and the application programs and queries submitted to
the system.
 The storage manager is responsible to the following tasks:
 interaction with the file manager
 efficient storing, retrieving and updating of data
Authorization Manager
 Checks whether the user is an authorized person or not
 Test the satisfaction of integrity constraints
Transaction Manager
Responsible for concurrent transaction execution It ensures that the database remains in
a consistent state despite of the system failure.

4. Briefly explain about views of data? (JUN 2016)

Data Abstraction ( View ) in DBMS:
Database contains three levels of abstraction namely,
Internal or Physical level: describes the physical structure of the database. The
internal schema uses a physical data model and describes the complete details of data
storage and access paths for the database.
Conceptual or Logical level: describes the structure of the whole database for a
community of users. The conceptual schema hides the details of physical storage
structures and concentrates on describing entities, data types, relationships, user
operations and constraints, data stored in database, and the relationships among the
data.
External or View level: includes number of external schemas or user views. Each
external schema describes the part of the database that a particular user group is
interested in and hides the rest of the database from that user group.
The below figure shows the levels of abstraction.

users
users

External External View External View

Schema

1
Logical Conceptual or Logical Level
Schema

Physical Internal or Physical Level

Schema
Mapping:
The transformation of requests and results from one level to another is called as mapping.
Schema
It is the logical structure of the database. The tow types of schema are:
Physical schema represents database design at the physical level
Logical schema represents database design at the logical level

Instance – the actual content of the database at a particular point in time is called the instance of the
schema
Data Independence
The ability to change a schema at one level without affecting the higher level schemas is called as
data independence. There are two types of data independence:
Physical Data Independence – is the ability to modify the physical or internal schema without
changing the logical or external schemas.
Logical Data Independence – is the ability to modify logical or conceptual schema without
changing the external schemas or application programs.
5. Explain select, project and Cartesian product operations in relational algebra with an
example? (NOV 2016, APR 2018)
Relational Algebra
Relational algebra is a procedural query language, which takes instances of relations as input and yields
instances of relations as output. It uses operators to perform queries. An operator can be either unary or
binary. They accept relations as their input and yield relations as their output. Relational algebra is
performed recursively on a relation and intermediate results are also considered relations.
The fundamental operations of relational algebra are as follows −
 Select
 Project
 Union
 Set different
 Cartesian product
 Rename
We will discuss all these operations in the following sections.
Select Operation (σ)
It selects tuples that satisfy the given predicate from a relation.
Notation − σp(r)
Where σ stands for selection predicate and r stands for relation. p is prepositional logic formula which
may use connectors like and, or, and not. These terms may use relational operators like − =, ≠, ≥, < , >, ≤.
For example −
σsubject = "database"(Books)
Output − Selects tuples from books where subject is
'database'. σsubject = "database" and price = "450"(Books)
Output − Selects tuples from books where subject is 'database' and 'price' is 450.
σsubject = "database" and price = "450" or year > "2010"(Books)
Output − Selects tuples from books where subject is 'database' and 'price' is 450 or those books
published after 2010.
Project Operation (∏)
It projects column(s) that satisfy a given predicate.
Notation − ∏A1, A2, An (r)
Where A1, A2 , An are attribute names of relation r.
Duplicate rows are automatically eliminated, as relation is a set.
For example −
∏subject, author (Books)
Selects and projects columns named as subject and author from the relation Books.
Union Operation (𝖴)
It performs binary union between two given relations and is defined as −
r 𝖴 s = { t | t ∈ r or t ∈ s}
Notation − r U s
Where r and s are either database relations or relation result set (temporary relation).
For a union operation to be valid, the following conditions must hold −
 r, and s must have the same number of attributes.
 Attribute domains must be compatible.
 Duplicate tuples are automatically eliminated.
∏ author (Books) 𝖴 ∏ author (Articles)
Output − Projects the names of the authors who have either written a book or an article or both.
Set Difference (−)
The result of set difference operation is tuples, which are present in one relation but are not in the second
relation.
Notation − r − s
Finds all the tuples that are present in r but not in s.
∏ author (Books) − ∏ author (Articles)
Output − Provides the name of authors who have written books but not articles.
Cartesian Product (Χ)
Combines information of two different relations into one.
Notation − r Χ s
Where r and s are relations and their output will be
defined as − r Χ s = { q t | q ∈ r and t ∈ s}
σauthor = 'tutorialspoint'(Books Χ Articles)
Output − Yields a relation, which shows all the books and articles written by tutorialspoint.
Rename Operation (ρ)
The results of relational algebra are also relations but without any name. The rename operation allows us
to rename the output relation. 'rename' operation is denoted with small Greek letter rho ρ.
Notation − ρ x (E)
Where the result of expression E is saved with name of x.
Additional operations are −
 Set intersection
 Assignment
 Natural join
5. Consider the given relation schema . ( MAY 2017, NOV 2018 )

Employee(empno,name,office,age)
Books(isbn,title,authors,publisher)
Loan(empno,isbn,date)

Write the following queries in SQL

Find the name of all employees who have borrowed a book published by McGraw-Hill.
Find the name of all employees who have borrowed all book published by McGraw-Hill.
Find the names of employees who have borrowed more than five different books published
by McGraw-Hill.
For each publisher, find the name of employees who have borrowed more than five books of
that publisher.

select name from employee e, books b, loan l where e.empno = l.empno and l.isbn = b.isbn and
b.publisher = ‘McGrawHill’

select name from employee e join loan l on e.empno=l.empno join (select isbn from books where
publisher = 'McGrawHill') x on l.isbn=x.isbn group by e.empno,name having count(*)= (select
count(*) from books where publisher=’McGrawHill’)

select name from employee,loan where employee.empno=loan.empno and isbn in ( select distinct
isbn from books where publisher='McGraw-Hill') group by employee.empno,name having
count(isbn) >=5
 select name from employee,loan,books where employee.empno=loan.empno and
books.isbn=loan.isbn group by employee.empno, name,books.publisher having
count(loan.isbn) >=5
6. Explain about SQL Fundamentals? (JUN 2016) (OR)
State and Explain DDL, DML, DCL with suitable examples. (NOV 2017), (NOV 2019)

SQL FUNDAMENTALS:
SQL is a standard computer language for accessing and manipulating databases.

What is SQL?
 SQL stands for Structured Query Language
 SQL allows you to access a database
 SQL is an ANSI standard computer language
 SQL can execute queries against a database
 SQL can retrieve data from a database
 SQL can insert new records in a database
 SQL can delete records from a database
 SQL can update records in a database
 SQL is easy to learn

SQL is a Standard - BUT....

SQL is an ANSI (American National Standards Institute) standard computer language for accessing and
manipulating database systems. SQL statements are used to retrieve and update data in a database. SQL
works with database programs like MS Access, DB2, Informix, MS SQL Server, Oracle, Sybase,
etc.Unfortunately, there are many different versions of the SQL language, but to be in compliance with the
ANSI standard, they must support the same major keywords in a similar manner (such as SELECT,
UPDATE, DELETE, INSERT, WHERE, and others). Note: Most of the SQL database programs also
have their own proprietary extensions in addition to the SQL standard!
SQL Database Tables
A database most often contains one or more tables. Each table is identified by a name (e.g.
"Customers" or "Orders"). Tables contain records (rows) with data.Below is an example of a table called
"Persons":
LastName FirstName Address City
Hansen Ola Timoteivn 10 Sandnes
Svendson Tove Borgvn 23 Sandnes
Pettersen Kari Storgt 20 Stavanger
The table above contains three records (one for each person) and four columns (LastName, FirstName,
Address, and City).
SQL Queries
With SQL, we can query a database and have a result set
returned. A query like this:
SELECT LastName FROM Persons
Gives a result set like this:
LastName
Hansen
Svendson
Pettersen
Note: Some database systems require a semicolon at the end of the SQL statement. We don't use the
semicolon in our tutorials.

9.Explain the following with examples:

i)DDL

ii)DML
 iii)Embedded SQL (NOV 2014)

Data definition language:

The data definition language is used to specify a database schema by a set of definitions.
The storage structure and access methods used by the database system, is specified by a set of statements
in a special type of DDL called a data storage and definition language. These statements define the
implementation details of the database schemas, which are usually hidden from the users.
The data values stored in the database must satisfy certain constraints. For example, suppose the balance
on an account should not fall below $1100. The DDL provides facilities to specify such constraints. The
database systems check these constraints every time the database is updated.
The various constraints involved in the database is given below:
Domain Constraints:
A domain of possible values must be associated with every attribute (for example, integer types,
character types, date/time types). Declaring an attribute to be of particular domain acts as a constraint on
the values it can take. Domain constraints are tested easily by the system whenever a new data item is
entered into the database.
Referential Integrity:
The referential integrity is used to ensure that a value that appears in one relation for a given set
of attributes also appears for a certain set of attributes in another relation. Database modifications can
cause violations of referential integrity. When a referential integrity constraint is violated, the database
rejects the action that caused the violation.
Assertion:
An assertion is any condition that the database must always satisfy. When an assertion is created,
the system tests it for validity. If the assertion is valid, then any future modification to the database is
allowed only if it does not that assertion to be violated.
Authorization:
Authorization specifies what types of access are permitted for users on various data values in the
database. The authorizations can be categorized as:
Read authorization, allows reading, but not modification of existing data.
Update authorization, allows insertion of new data, but not modification of existing data.
Delete authorization, allows deletion of data.

The DDL gets as input some instructions and generates some output. The output of the DDL is placed in
the data dictionary, which contains metadata- that is data about data. The data dictionary is considered to be
special type of table, which can only be accessed and updated by the database system itself. A database system
consults the data dictionary before reading or modifying actual data.
ii) Data Manipulation Language:
A data manipulation language (DML) is a language that enables users to access or manipulate data
organized by the appropriate data model. The types of access are:
Retrieval of information stored in the database o Insertion of new
information into the database o Deletion of information from the
database
o Modification of information stored in the database
There are basically two types:
Procedural DMLs require a user 3to specify what data are needed and how to get
those data.
Declarative DMLs (also referred to as nonprocedural DMLs) require a user to specify what
data are needed without specifying how to get those data.
A query is a statement requesting the retrieval of information. The portion of a DML that involves
information retrieval is called a query language.

Embedded SQL:
An embedded SQL program must be processed by a special preprocessor prior to compilation. The
preprocessor replaces embedded SQL requests with host-language declarations and procedure calls that
allow run-time execution of the database accesses. Then, the resulting program is compiled by the host
language compiler. To identify embedded SQL requests to the preprocessor, we use the EXEC SQL
 statement. It has the form
EXEC SQL <embedded SQL statement> END-EXEC
The exact syntax for embedded SQL requests depends on the language in which SQL is embedded.
For instance, a semicolon is used instead of END-EXEC when SQL is embedded in C. The java embedding
of SQL called (SQLJ) uses the syntax
#SQL{<embedded SQL statement>}
The statement SQL INCLUDE is placed in the program to identify the place where the preprocessor
should insert the special variables used for communication between the program and the database system.
Variables of the host language can be used within embedded SQL statements, but they must be preceded by
a colon (:) to distinguish them from SQL variables.
Before executing any SQL statements, the program must first connect to the database. This is done
using
EXEC SQL connect to server user user-name END-EXEC

SQL Data Manipulation Language (DML)

SQL (Structured Query Language) is a syntax for executing queries. But the SQL language also includes a
syntax to update, insert, and delete records.
These query and update commands together form the Data Manipulation Language (DML) part of SQL:
 SELECT - extracts data from a database table
 UPDATE - updates data in a database table
 DELETE - deletes data from a database table
 INSERT INTO - inserts new data into a database table

SQL Data Definition Language (DDL)

The Data Definition Language (DDL) part of SQL permits database tables to be created or deleted. We
can also define indexes (keys), specify links between tables, and impose constraints between database tables.
The most important DDL statements in SQL are:
 CREATE TABLE - creates a new database table
 ALTER TABLE - alters (changes) a database table
 DROP TABLE - deletes a database table
 CREATE INDEX - creates an index (search key)
 DROP INDEX - deletes an index
The SQL SELECT Statement
The SELECT statement is used to select data from a table. The tabular result is stored in a result table
(called the result-set).
Syntax
SELECT column_name(s)
FROM table_name
Note: SQL statements are not case sensitive. SELECT is the same as select.

SQL SELECT Example

To select the content of columns named "LastName" and "FirstName", from the database table called
"Persons", use a SELECT statement like this:
SELECT LastName,FirstName FROM Persons
The database table "Persons":
LastName FirstName Address City
Hansen Ola Timoteivn 10 Sandnes
Svendson Tove Borgvn 23 Sandnes
Pettersen Kari Storgt 20 Stavanger
The result
LastName FirstName
Hansen Ola
Svendson Tove
Pettersen Kari
DYNAMIC SQL
The main disadvantage of embedded SQL is that it supports only static SQLs. If we need to build up
queries at run time, then we can use dynamic sql. That means if query changes according to user input,
then it always better to use dynamic SQL. Like we said above, the query when user enters student name
alone and when user enters both student name and address, is different. If we use embedded SQL, one
cannot implement this requirement in the code. In such case dynamic SQL helps the user to develop query
depending on the values entered by him, without making him know which query is being executed. It can
also be used when we do not know which SQL statements like Insert, Delete update or select needs to be
used, when number of host variables is unknown, or when datatypes of host variables are unknown or
when there is direct reference to DB objects like tables, views, indexes are required.
However this will make user requirement simple and easy but it may make query lengthier and complex.
That means depending upon user inputs, the query may grow or shrink making the code flexible enough to
handle all the possibilities. In embedded SQL, compiler knows the query in advance and pre-compiler
compiles the SQL code much before C compiles the code for execution. Hence embedded SQLs will be
faster in execution. But in the case of dynamic SQL, queries are created, compiled and executed only at
the run time. This makes the dynamic SQL little complex, and time consuming.
Since query needs to be prepared at run time, in addition to the structures discussed in embedded SQL, we
have three more clauses in dynamic SQL. These are mainly used to build the query and execute them at
run time.
PREPARE
Since dynamic SQL builds a query at run time, as a first step we need to capture all the inputs from the
user. It will be stored in a string variable. Depending on the inputs received from the user, string variable is
appended with inputs and SQL keywords. These SQL like string statements are then converted into SQL
query. This is done by using PREPARE statement.
For example, below is the small snippet from dynamic SQL. Here sql_stmt is a character variable,
which holds inputs from the users along with SQL commands. But is cannot be considered as SQL query
as it is still a sting value. It needs to be converted into a proper SQL query which is done at the last line
using PREPARE statement. Here sql_query is also a string variable, but it holds the string as a SQL query.
EXECUTE
This statement is used to compile and execute the SQL statements prepared
in DB. EXEC SQL EXECUTE sql_query;
EXECUTE IMMEDIATE
This statement is used to prepare SQL statement as well as execute the SQL statements in DB. It
performs the task of PREPARE and EXECUTE in a single line.
EXEC SQL EXECUTE IMMEDIATE :sql_stmt;
Dynamic SQL will not have any SELECT queries and host variables. But it can be any other SQL
statements like insert, delete, update, grant etc. But when we use insert/ delete/ updates in this type, we
cannot use host variables. All the input values will be hardcoded. Hence the SQL statements can be
directly executed using EXECUTE IMMEDIATE rather than using PREPARE and then EXECUTE.
EXEC SQL EXECUTE IMMEDIATE ‘GRANT SELECT ON STUDENT TO Faculty’;
EXEC SQL EXECUTE IMMEDIATE ‘DELETE FROM STUDENT WHERE STD_ID = 100’;
EXEC SQL EXECUTE IMMEDIATE ‘UPDATE STUDENT SET ADDRESS = ‘Troy’ WHERE STD_ID
=100’;
UNIT II DATABASE DESIGN
Entity-Relationship model – E-R Diagrams – Enhanced-ER Model – ER-to-Relational Mapping –
Functional Dependencies – Non-loss Decomposition – First, Second, Third Normal Forms, Dependency
Preservation – Boyce/Codd Normal Form – Multi-valued Dependencies and Fourth Normal Form –
Join Dependencies and Fifth Normal Form
DATABASE DESIGN
A well-designed database shall:
 Eliminate Data Redundancy: the same piece of data shall not be stored in more than one place. This is
because duplicate data not only waste storage spaces but also easily lead to inconsistencies.
Ensure Data Integrity and Accuracy
Entity-Relationship Data Model
 Classical, popular conceptual data model
 First introduced (mid 70’s) as a (relatively minor) improvement to the relational model: pictorial diagrams
are
easier to read than relational database schemas
 Then evolved as a popular model for the first conceptual representation of data structures in the
process of database design
ER Model: Entity and Entity Set
Considering the above example, Student is an entity, Teacher is an entity, similarly, Class, Subjectetc are
also entities.
An Entity is generally a real-world object which has characteristics and holds relationships in a
DBMS. If a Student is an Entity, then the complete dataset of all the students will be the Entity Set
ER Model: Attributes
If a Student is an Entity, then student's roll no., student's name, student's age, student's gender etc will
be its attributes.
An attribute can be of many types, here are different types of attributes defined in ER database model:
1. Simple attribute: The attributes with values that are atomic and cannot be broken down further are
simple attributes. For example, student's age.
2. Composite attribute: A composite attribute is made up of more than one simple attribute. For
example, student's address will contain, house no., street name, pincode etc.
3. Derived attribute: These are the attributes which are not present in the whole database management
system, but are derived using other attributes. For example, average age of students in a class.
4. Single-valued attribute: As the name suggests, they have a single value.
5. Multi-valued attribute: And, they can have multiple values.

ER Model: Relationships

When an Entity is related to another Entity, they are said to have a relationship. For example, A
ClassEntity is related to Student entity, because students study in classes, hence this is a relationship.
Depending upon the number of entities involved, a degree is assigned to relationships.
For example, if 2 entities are involved, it is said to be Binary relationship, if 3 entities are involved, it is
said to be Ternary relationship, and so on.
Working with ER Diagrams
ER Diagram is a visual representation of data that describes how data is related to each other. In ER Model,
we disintegrate data into entities, attributes and setup relationships between entities, all this can be represented
visually using the ER diagram.
Components of ER Diagram
Entitiy, Attributes, Relationships etc form the components of ER Diagram and there are defined symbols
and shapes to represent each one of them.
Let's see how we can represent these in our ER Diagram.
Entity
Simple rectangular box represents an Entity.

Relationships between Entities - Weak and Strong

Rhombus is used to setup relationships between two or more entities.

Attributes for any Entity

Ellipse is used to represent attributes of any entity. It is connected to the entity.

Weak Entity
A weak Entity is represented using double rectangular boxes. It is generally connected to another entity.

Key Attribute for any Entity

To represent a Key attribute, the attribute name inside the Ellipse is underlined.
Derived Attribute for any Entity
Derived attributes are those which are derived based on other attributes, for example, age can be derived from
date of birth.
To represent a derived attribute, another dotted ellipse is created inside the main ellipse.

Multivalued Attribute for any Entity

Double Ellipse, one inside another, represents the attribute which can have multiple values.

Composite Attribute for any Entity

A composite attribute is the attribute, which also has attributes.

ER Diagram: Entity
An Entity can be any object, place, person or class. In ER Diagram, an entity is represented using rectangles.
Consider an example of an Organisation- Employee, Manager, Department, Product and many more can be
taken as entities in an Organisation.

The yellow rhombus in between represents a relationship.

ER Diagram: Key Attribute
Key attribute represents the main characteristic of an Entity. It is used to represent a Primary key. Ellipse with
the text underlined, represents Key Attribute.
ER Diagram: Binary Relationship
Binary Relationship means relation between two Entities. This is further divided into three types.
One to One Relationship
This type of relationship is rarely seen in real world.

The above example describes that one student can enroll only for one course and a course will also have only one
Student. This is not what you will usually see in real-world relationships.
One to Many Relationship
The below example showcases this relationship, which means that 1 student can opt for many courses, but a
course can only have 1 student. Sounds weird! This is how it is.

Many to One Relationship

It reflects business rule that many entities can be associated with just one entity. For example, Student
enrolls for only one Course but a Course can have many Students.

Many to Many Relationship

The above diagram represents that one student can enroll for more than one courses. And a course can have
more than 1 student enrolled in it.
ER Diagram: Recursive Relationship
When an Entity is related with itself it is known as Recursive Relationship.

ER Diagram: Ternary Relationship

Relationship of degree three is called Ternary relationship.
A Ternary relationship involves three entities. In such relationships we always consider two entites together
and then look upon the third.

For example, in the diagram above, we have three related entities, Company, Product and Sector. To understand
the relationship better or to define rules around the model, we should relate two entities and then derive the third
one.
A Company produces many Products/ each product is produced by exactly one
company. A Company operates in only one Sector / each sector has many companies
operating in it.
Considering the above two rules or relationships, we see that although the complete relationship involves
three entities, but we are looking at two entities at a time.
The Enhanced ER Model
As the complexity of data increased in the late 1980s, it became more and more difficult to use the traditional
ER Model for database modelling. Hence some improvements or enhancements were made to the existing ER
Model to make it able to handle the complex applications better.
Hence, as part of the Enhanced ER Model, along with other improvements, three new concepts were added to
the existing ER Model, they were:
1. Generalization
2. Specialization
3. Aggregration
Generalization
Generalization is a bottom-up approach in which two lower level entities combine to form a higher level
entity. In generalization, the higher level entity can also combine with other lower level entities to make
further higher level entity.
It's more like Superclass and Subclass system, but the only difference is the approach, which is bottom-up.
Hence, entities are combined to form a more generalised entity, in other words, sub-classes are combined to
form a super-
class.

For example, Saving and Current account types entities can be generalised and an entity with name Account
can be created, which covers both.
Specialization
Specialization is opposite to Generalization. It is a top-down approach in which one higher level entity can be
broken down into two lower level entity. In specialization, a higher level entity may not have any lower-level
entity sets, it's possible.

Aggregation
Aggregation is a process when relation between two entities is treated as a single entity.

In the diagram above, the relationship between Center and Course together, is acting as an Entity, which is in
relationship with another entity Visitor. Now in real world, if a Visitor or a Student visits a Coaching Center,
he/she will never enquire about the center only or just about the course, rather he/she will ask enquire about
both.
ER Model to Relational Model
ER Model can be represented using ER Diagrams which is a great way of designing and representing the
database design in more of a flow chart form.
It is very convenient to design the database using the ER Model by creating an ER diagram and later on
converting it into relational model to design your tables.
Not all the ER Model constraints and components can be directly transformed into relational model, but
an approximate schema can be derived.
Few examples of ER diagrams and convert it into relational model schema, hence creating tables in RDBMS.
Entity becomes Table
Entity in ER Model is changed into tables, or we can say for every Entity in ER model, a table is created
in Relational Model.
And the attributes of the Entity gets converted to columns of the table.
And the primary key specified for the entity in the ER model, will become the primary key for the table
in relational model.
For example, for the below ER Diagram in ER Model,

A table with name Student will be created in relational model, which will have
4 columns, id, name, age, address and id will be the primary key for this table.
Table:Student

id name age address

Relationship becomes a Relationship Table

In ER diagram, we use diamond/rhombus to represent a relationship between two entities. In Relational
model we create a relationship table for ER Model relationships too.
In the ER diagram below, we have two entities Teacher and Student with a relationship between them.

As discussd above, entity gets mapped to table, hence we will create table for Teacher and a table for Student
with all the attributes converted into columns.
Now, an additional table will be created for the relationship, for example StudentTeacher or give it any name
you like. This table will hold the primary key for both Student and Teacher, in a tuple to describe the
relationship, which teacher teaches which student.
If there are additional attributes related to this relationship, then they become the columns for this table, like
subject
 name.
Also proper foreign key constraints must be set for all the tables.
Functional Dependency
The functional dependency is a relationship that exists between two attributes. It typically exists between
the primary key and non-key attribute within a table.
X → Y
The left side of FD is known as a determinant, the right side of the production is known as a dependent.
For example:
Assume we have an employee table with attributes: Emp_Id, Emp_Name, Emp_Address.
Here Emp_Id attribute can uniquely identify the Emp_Name attribute of employee table because if we know
the Emp_Id, we can tell that employee name associated with it.
Functional dependency can be written as:
Emp_Id → Emp_Name
Types of Functional dependency

Trivial functional dependency

o A → B has trivial functional dependency if B is a subset of A.
o The following dependencies are also trivial like: A → A, B → B
Example:
1. Consider a table with two columns Employee_Id and Employee_Name.
{Employee_id, Employee_Name} → Employee_Id is a trivial functional dependency as
2. Employee_Id is a subset of {Employee_Id, Employee_Name}.
3. Also, Employee_Id → Employee_Id and Employee_Name → Employee_Name are trivial dependencies
too.

Non-trivial functional dependency

4. A → B has a non-trivial functional dependency if B is not a subset of A.
5. When A intersection B is NULL, then A → B is called as complete non-trivial.
Example:
ID → Name,
Name →
DOB
Normalization of Database
Database Normalization is a technique of organizing the data in the database. Normalization is a systematic
approach of decomposing tables to eliminate data redundancy(repetition) and undesirable characteristics
like Insertion, Update and Deletion anomalies. It is a multi-step process that puts data into tabular form,
removing duplicated data from the relation tables.
Normalization is used for mainly two purposes,

 Eliminating reduntant(useless) data.

 Ensuring data dependencies make sense i.e data is logically stored.

Problems Without Normalization

If a table is not properly normalized and have data redundancy then it will not only eat up extra memory space
but will also make it difficult to handle and update the database, without facing data loss. Insertion, Updation
and Deletion Anomalies are very frequent if database is not normalized. To understand these anomalies let us
take an example of a Student table.

rollno name branch hod office_tel

401 Akon CSE Mr. X 53337

402 Bkon CSE Mr. X 53337

403 Ckon CSE Mr. X 53337

404 Dkon CSE Mr. X 53337

In the table above, we have data of 4 Computer Sci. students. As we can see, data for the fields branch,
hod(Head of Department) and office_tel is repeated for the students who are in the same branch in the college,
this is Data Redundancy.
Insertion Anomaly
Suppose for a new admission, until and unless a student opts for a branch, data of the student cannot be inserted,
or else we will have to set the branch information as NULL.
Also, if we have to insert data of 100 students of same branch, then the branch information will be repeated for
all those 100 students.
These scenarios are nothing but Insertion anomalies.
Updation Anomaly
What if Mr. X leaves the college? or is no longer the HOD of computer science department? In that case all
the student records will have to be updated, and if by mistake we miss any record, it will lead to data
inconsistency. This is Updation anomaly.
Deletion Anomaly
In our Student table, two different informations are kept together, Student information and Branch
information. Hence, at the end of the academic year, if student records are deleted, we will also lose the
branch information. This is Deletion anomaly.
Normalization Rule
Normalization rules are divided into the following normal forms:
1. First Normal Form
2. Second Normal Form
3. Third Normal Form
4. BCNF
5. Fourth Normal Form
6. Fifth Normal Form
First Normal Form (1NF)
For a table to be in the First Normal Form, it should follow the following 4 rules:
1. It should only have single(atomic) valued attributes/columns.
2. Values stored in a column should be of the same domain
3. All the columns in a table should have unique names.
4. And the order in which data is stored, does not matter.
Rules for First Normal Form
The first normal form expects you to follow a few simple rules while designing your database, and they are:
Rule 1: Single Valued Attributes
Each column of your table should be single valued which means they should not contain multiple values. We
will explain this with help of an example later, let's see the other rules for now.
Rule 2: Attribute Domain should not change
This is more of a "Common Sense" rule. In each column the values stored must be of the same kind or type.
For example: If you have a column dob to save date of births of a set of people, then you cannot or you must
not save 'names' of some of them in that column along with 'date of birth' of others in that column. It should
hold only 'date of birth' for all the records/rows.
Rule 3: Unique name for Attributes/Columns
This rule expects that each column in a table should have a unique name. This is to avoid confusion at the time
of retrieving data or performing any other operation on the stored data.
If one or more columns have same name, then the DBMS system will be left confused.
Rule 4: Order doesn't matters
This rule says that the order in which you store the data in your table doesn't matter.

EXAMPLE
Create a table to store student data which will have student's roll no., their name and the name of subjects they
have opted for.
Here is the table, with some sample data added to it.

roll_no name subject

101 Akon OS, CN
103 Ckon Java
102 Bkon C, C++

The table already satisfies 3 rules out of the 4 rules, as all our column names are unique, we have stored data
in the order we wanted to and we have not inter-mixed different type of data in columns.
But out of the 3 different students in our table, 2 have opted for more than 1 subject. And we have stored the
subject names in a single column. But as per the 1st Normal form each column must contain atomic value.
It's very simple, because all we have to do is break the values into atomic values.
Here is our updated table and it now satisfies the First Normal Form.
roll_no name subject
101 Akon OS
101 Akon CN
103 Ckon Java
102 Bkon C
102 Bkon C++

By doing so, although a few values are getting repeated but values for the subject column are now atomic for
each record/row. Using the First Normal Form, data redundancy increases, as there will be many columns with
same data in multiple rows but each row as a whole will be unique.
Second Normal Form (2NF)
For a table to be in the Second Normal Form,
1. It should be in the First Normal form.
2. And, it should not have Partial Dependency.
Dependency
Let's take an example of a Student table with columns student_id, name, reg_no(registration
number), branch and address(student's home address).

student_ reg_n branc addre

name
id o h ss

In this table, student_id is the primary key and will be unique for every row, hence we can use student_id to
fetch any row of data from this table
Even for a case, where student names are same, if we know the student_id we can easily fetch the correct
record.
student_id name reg_no branch address
10 Akon 07-WY CSE Kerala
11 Akon 08-WY IT Gujarat

Hence we can say a Primary Key for a table is the column or a group of columns(composite key) which can
uniquely identify each record in the table.
I can ask from branch name of student with student_id 10, and I can get it. Similarly, if I ask for name of
student with student_id 10 or 11, I will get it. So all I need is student_id and every other column depends on it,
or can be fetched using it.This is Dependency and we also call it Functional Dependency.
Partial Dependency
Now that we know what dependency is, we are in a better state to understand what partial dependency is.
For a simple table like Student, a single column like student_id can uniquely identfy all the records in a table.
But this is not true all the time. So now let's extend our example to see if more than 1 column together can act
as a primary key.
Let's create another table for Subject, which will have subject_id and subject_name fields and subject_id will
be the primary key.
subject_i subject_nam
d e
1 Java
2 C++

www.Notesfree.
3 Php
Now we have a Student table with student information and another table Subject for storing subject
information.
Let's create another table Score, to store the marks obtained by students in the respective subjects. We will also
be saving name of the teacher who teaches that subject along with marks.
subject_i
score_id student_id marks teacher

n
d
1 10 1 70 Java Teacher
2 10 2 75 C++ Teacher
3 11 1 80 Java Teacher
In the score table we are saving the student_id to know which student's marks are these and subject_id to
know for which subject the marks are for.
Together, student_id + subject_id forms a Candidate Key which can be the Primary key.
To get me marks of student with student_id 10, can you get it from this table? No, because you don't know for
which subject. And if I give you subject_id, you would not know for which student. Hence we need student_id
+ subject_id to uniquely identify any row.
But where is Partial Dependency?
Now if you look at the Score table, we have a column names teacher which is only dependent on the subject,
for Java it's Java Teacher and for C++ it's C++ Teacher & so on.
Now as we just discussed that the primary key for this table is a composition of two columns which
is student_id & subject_id but the teacher's name only depends on subject, hence the subject_id, and has
nothing to do with student_id.
This is Partial Dependency, where an attribute in a table depends on only a part of the primary key and not on
the whole key.
How to remove Partial Dependency?
There can be many different solutions for this, but out objective is to remove teacher's name from Score table.
The simplest solution is to remove columns teacher from Score table and add it to the Subject table. Hence, the
Subject table will become:

subject_id subject_name teacher

1 Java Java Teacher
2 C++ C++ Teacher
3 Php Php Teacher
And our Score table is now in the second normal form, with no partial dependency.
score_ student_ subject_ mar
id id id ks
1 10 1 70
2 10 2 75
3 11

Third Normal Form (3NF)

A table is said to be in the Third Normal Form when,
1. It is in the Second Normal form.
2. And, it doesn't have Transitive Dependency.
So let's use the same example, where we have 3 tables, Student, Subject and Score.
Student Table
student_i
d name reg_no branch address
10 Akon 07-WY CSE Kerala
11 Akon 08-WY IT Gujarat
12 Bkon 09-WY IT Rajasthan
Subject Table
subject_id subject_name teacher
1 Java Java Teacher
2 C++ C++ Teacher
3 Php Php Teacher

Score Table
In the Score table, we need to store some more information, which is the exam name and total marks, so let's
add 2 more columns to the Score table.
student_i subject_i
score_id d d marks
1 10 1 70
2 10 2 75
3 11 1 80

Transitive Dependency
With exam_name and total_marks added to our Score table, it saves more data now. Primary key for the Score
table is a composite key, which means it's made up of two attributes or columns → student_id + subject_id.
The new column exam_name depends on both student and subject. For example, a mechanical engineering
student will have Workshop exam but a computer science student won't. And for some subjects you have
Practical exams and for some you don't. So we can say that exam_name is dependent on
both student_id and subject_id.
And what about our second new column total_marks? Does it depend on our Score table's primary key?
Well, the column total_marks depends on exam_name as with exam type the total score changes. For example,
practicals are of less marks while theory exams are of more marks.
But, exam_name is just another column in the score table. It is not a primary key or even a part of the primary
key, and total_marks depends on it.
This is Transitive Dependency. When a non-prime attribute depends on other non-prime attributes rather than
depending upon the prime attributes or primary key.
How to remove Transitive Dependency
Again the solution is very simple. Take out the columns exam_name and total_marks from Score table and put
them in an Exam table and use the exam_id wherever required.
Score Table: In 3rd Normal Form
student_i subject_
score_id d id marks exam_id

The new Exam table

total_mark
exam_id exam_name s
1 Workshop 200
2 Mains 70
3 Practicals 30
Advantage of removing Transitive Dependency
The advantage of removing transitive dependency is,
 Amount of data duplication is reduced.
 Data integrity achieved.
Boyce and Codd Normal Form (BCNF)
Boyce and Codd Normal Form is a higher version of the Third Normal form. This form deals with certain type
of anomaly that is not handled by 3NF. A 3NF table which does not have multiple overlapping candidate keys
is said to be in BCNF. For a table to be in BCNF, following conditions must be satisfied:
 R must be in 3rd Normal Form
 and, for each functional dependency ( X → Y ), X should be a super Key.In simple words, it means, that
for a dependency A → B, A cannot be a non-prime attribute, if B is a prime attribute.
Example
College enrolment table with columns student_id, subject and professor.
student_id subject professor
101 Java P.Java
101 C++ P.Cpp
102 Java P.Java2
103 C# P.Chash
104 Java P.Java
In the table above:
One student can enroll for multiple subjects. For example, student with student_id 101, has opted for subjects -
Java & C++
 For each subject, a professor is assigned to the student.
 And, there can be multiple professors teaching one subject like Java.
What do you think should be the Primary Key?
Well, in the table above student_id, subject together form the primary key, because
using student_id and subject, we can find all the columns of the table.
One more important point to note here is, one professor teaches only one subject, but one subject may have
two different professors.
Hence, there is a dependency between subject and professor here, where subject depends on the professor
name.
This table satisfies the 1st Normal form because all the values are atomic, column names are unique and all the
values stored in a particular column are of same domain.
This table also satisfies the 2nd Normal Form as there is no Partial Dependency.
And, there is no Transitive Dependency, hence the table also satisfies the 3rd Normal Form.
But this table is not in Boyce-Codd Normal Form.
Why this table is not in BCNF?
In the table above, student_id, subject form primary key, which means subject column is a prime attribute.
But, there is one more dependency, professor → subject.
And while subject is a prime attribute, professor is a non-prime attribute, which is not allowed by BCNF.
How to satisfy BCNF?
To make this relation(table) satisfy BCNF, we will decompose this table into two tables, student table
and professor table.
Below we have the structure for both the tables.
Student Table
student_id p_id
101 1
101 2
Professor Table
p_id professor subject
1 P.Java Java
2 P.Cpp C++
And now, this relation satisfy Boyce-Codd Normal Form.
Fourth Normal Form (4NF)
A table is said to be in the Fourth Normal Form when,
1. It is in the Boyce-Codd Normal Form.
2. And, it doesn't have Multi-Valued Dependency.
Multi-valued Dependency
A table is said to have multi-valued dependency, if the following conditions are true,
1. For a dependency A → B, if for a single value of A, multiple value of B exists, then the table may have
multi-valued dependency.
2. Also, a table should have at-least 3 columns for it to have a multi-valued dependency.
3. And, for a relation R(A,B,C), if there is a multi-valued dependency between, A and B, then B and C
should be independent of each other.
If all these conditions are true for any relation(table), it is said to have multi-valued dependency.
Example
Below we have a college enrolment table with columns s_id, course and hobby.
cours
s_id e hobby
Scienc
1 Cricket
e
1 Maths Hockey
2 C# Cricket
2 Php Hockey
From the table above, student with s_id 1 has opted for two courses, Science and Maths, and has two
hobbies, Cricket and Hockey.
You must be thinking what problem this can lead to, right?
Well the two records for student with s_id 1, will give rise to two more records, as shown below, because for
one student, two hobbies exists, hence along with both the courses, these hobbies should be specified.
s_id course hobby
1 Science Cricket
1 Maths Hockey
1 Science Hockey
1 Maths Cricket
And, in the table above, there is no relationship between the columns course and hobby. They are independent
of each other.
So there is multi-value dependency, which leads to un-necessary repetition of data and other anomalies as
well.
How to satisfy 4th Normal Form?
To make the above relation satify the 4th normal form, we can decompose the table into 2 tables.
CourseOpted Table
s_id course
1 Science
1 Maths
2 C#
2 Php
Hobbies Table,
s_id hobby
1 Cricket
1 Hockey
2 Cricket
2 Hockey
Now this relation satisfies the fourth normal form.
A table can also have functional dependency along with multi-valued dependency. In that case, the
functionally dependent columns are moved in a separate table and the multi-valued dependent columns are
moved to separate tables.
Fifth Normal Form (5NF)
A database is said to be in 5NF, if and only if,
1. It's in 4NF
2. If we can decompose table further to eliminate redundancy and anomaly, and when we re-join the
decomposed tables by means of candidate keys, we should not be losing the original data or any new
record set should not arise. In simple words, joining two or more decomposed table should not lose
records nor create new records.
What is Join Dependency
If a table can be recreated by joining multiple tables and each of this table have a subset of the attributes of the
table, then the table is in Join Dependency. It is a generalization of Multivalued DependencyJoin Dependency
can be related to 5NF, wherein a relation is in 5NF, only if it is already in 4NF and it cannot be decomposed
further.
Example
<Employee>
EmpName EmpSkills EmpJob (Assigned Work)
Tom Networking EJ001
Harry Web Development EJ002
Katie Programming EJ002

The above table can be decomposed into the following three tables; therefore it is not in 5NF:

<EmployeeSkills>
EmpName EmpSkills
Tom Networking
Harry Web Development
Katie Programming
<EmployeeJob>

EmpName EmpJob
Tom EJ001
Harry EJ002
<JobSkills> Katie EJ002

Our Join Dependency:

{(EmpName, EmpSkills ), ( EmpName, EmpJob), (EmpSkills, EmpJob)}

The above relations have join dependency, so they are not in 5NF. That would mean that a join relation of the
above three relations is equal to our original relation <Employee>.

FIFTH NORMAL FORM EXAMPLE

Consider an example of different Subjects taught by different lecturers and the lecturers taking classes for
different semesters.
Note: Please consider that Semester 1 has Mathematics, Physics and Chemistry and Semester 2 has only
Mathematics in its academic year!!

In above table, Rose takes both Mathematics and Physics class for Semester 1, but she does not take Physics
class for Semester 2. In this case, combination of all these 3 fields is required to identify a valid data. Imagine
we want to add a new class - Semester3 but do not know which Subject and who will be taking that subject.
We would be simply inserting a new entry with Class as Semester3 and leaving Lecturer and subject as NULL.
As we discussed above, it's not a good to have such entries. Moreover, all the three columns together act as a
primary key, we cannot leave other two columns blank!
Hence we have to decompose the table in such a way that it satisfies all the rules till 4NF and when join them
by using keys, it should yield correct record. Here, we can represent each lecturer's Subject area and their
classes in a better way. We can divide above table into three - (SUBJECT, LECTURER), (LECTURER,
CLASS), (SUBJECT, CLASS)

Now, each of combinations is in three different tables. If we need to identify who is teaching which subject to
which semester, we need join the keys of each table and get the result.
For example, who teaches Physics to Semester 1, we would be selecting Physics and Semester1 from table 3
above, join with table1 using Subject to filter out the lecturer names. Then join with table2 using Lecturer to
get correct lecturer name. That is we joined key columns of each table to get the correct data. Hence there is no
lose or new data - satisfying 5NF condition.
 UNIT III - TRANSACTIONS
Transaction Concepts – ACID Properties – Schedules – Serializability – Concurrency Control – Need
for Concurrency – Locking Protocols – Two Phase Locking – Deadlock – Transaction Recovery - Save
Points – Isolation Levels – SQL Facilities for Concurrency and Recovery

1. TRANSACTION CONCEPTS
What is Transaction?
A set of logically related operations is known as transaction. The main operations of a transaction are:
Read(A): Read operations Read(A) or R(A) reads the value of A from the database and stores it in a buffer
in main memory.
Write (A): Write operation Write(A) or W(A) writes the value back to the database from buffer.
Let us take a debit transaction from an account which consists of following operations:
1.R(A);
2.A=A-1000;
3.W(A);
Assume A’s value before starting of transaction is 5000.
 The first operation reads the value of A from database and stores it in a buffer.
 Second operation will decrease its value by 1000. So buffer will contain 4000.
 Third operation will write the value from buffer to database. So A’s final value will be 4000.
But it may also be possible that transaction may fail after executing some of its operations. The failure can be
because of hardware, software or power etc. For example, if debit transaction discussed above fails after
executing operation 2, the value of A will remain 5000 in the database which is not acceptable by the bank.

To avoid this, Database has two important operations:

Commit: After all instructions of a transaction are successfully executed, the changes made by transaction are
made permanent in the database.
Rollback: If a transaction is not able to execute all operations successfully, all the changes made by
transaction are undone.
Why do you need concurrency in Transactions?
A database is a shared resource accessed. It is used by many users and processes concurrently. For
example, the banking system, railway, and air reservations systems, stock market monitoring, supermarket
inventory, and checkouts, etc.
Not managing concurrent access may create issues like:
 Hardware failure and system crashes
 Concurrent execution of the same transaction, deadlock, or slow performance

States of Transactions

The various states of a Database Transaction are listed below

1
 State Transaction types

Active State A transaction enters into an active state when the execution process begins. During
this state read or write operations can be performed.

Partially A transaction goes into the partially committed state after the end of a transaction.
Committed

Committed When the transaction is committed to state, it has already completed its execution
State successfully. Moreover, all of its changes are recorded to the database permanently.

Failed State A transaction considers failed when any one of the checks fails or if the transaction is
aborted while it is in the active state.

Terminated State of transaction reaches terminated state when certain transactions which are
State leaving the system can't be restarted.

Transition Diagram for a Database Transaction

Let's study a state transition diagram that highlights how a transaction moves between these various states.
1. Once a transaction states execution, it becomes active. It can issue READ or WRITE operation.
2. Once the READ and WRITE operations complete, the transactions becomes partially committed state.
3. Next, some recovery protocols need to ensure that a system failure will not result in an inability to
record changes in the transaction permanently. If this check is a success, the transaction commits and
enters into the committed state.
4. If the check is a fail, the transaction goes to the Failed state.
5. If the transaction is aborted while it's in the active state, it goes to the failed state. The transaction
should be rolled back to undo the effect of its write operations on the database.
6. The terminated state refers to the transaction leaving the system.

2. ACID PROPERTIES

2
 A transaction is a single logical unit of work which accesses and possibly modifies the contents of a
database. Transactions access data using read and write operations.
In order to maintain consistency in a database, before and after transaction, certain properties
are followed. These are called ACID properties.

3
 Atomicity
By this, we mean that either the entire transaction takes place at once or doesn’t happen at all. There is
no midway i.e. transactions do not occur partially. Each transaction is considered as one unit and either
runs to completion or is not executed at all. It involves following two operations.
—Abort: If a transaction aborts, changes made to database are not visible.
—Commit: If a transaction commits, changes made are visible.
Atomicity is also known as the ‘All or nothing rule’.
Consider the following transaction T consisting of T1 and T2: Transfer of 100 from account X to
account Y.

If the transaction fails after completion of T1 but before completion of T2.( say, after write(X) but
before write(Y)), then amount has been deducted from X but not added to Y. This results in an
inconsistent database state. Therefore, the transaction must be executed in entirety in order to ensure
correctness of database state.
Consistency
This means that integrity constraints must be maintained so that the database is consistent before and
after the transaction. It refers to correctness of a database.
Referring to the example above,
The total amount before and after the transaction must be maintained.
Total before T occurs = 500 + 200 = 700.
Total after T occurs = 400 + 300 = 700.
Therefore, database is consistent. Inconsistency occurs in case T1 completes but T2 fails. As a result T is
incomplete.
Isolation
This property ensures that multiple transactions can occur concurrently without leading to
inconsistency of database state. Transactions occur independently without interference. Changes occurring
in a particular transaction will not be visible to any other transaction until that particular change in that
transaction is written to memory or has been committed. This property ensures that the execution of
transactions concurrently will result in a state that is equivalent to a state achieved these were executed
serially in some order.
Let X= 500, Y = 500.
Consider two transactions T and T”.

4
 Suppose T has been executed till Read (Y) and then T’’ starts. As a result , interleaving of
operations takes place due to which T’’ reads correct value of X but incorrect value of Y and sum
computed by
T’’: (X+Y = 50, 000+500=50, 500)
is thus not consistent with the sum at end of transaction:
T: (X+Y = 50, 000 + 450 = 50, 450).
This results in database inconsistency, due to a loss of 50 units. Hence, transactions must take place in
isolation and changes should be visible only after a they have been made to the main memory.
Durability:
This property ensures that once the transaction has completed execution, the updates and
modifications to the database are stored in and written to disk and they persist even if system failure
occurs. These updates now become permanent and are stored in a non-volatile memory. The effects of the
transaction, thus, are never lost.

3. SCHEDULES
1. Serial Schedules
Schedules in which the transactions are executed non-interleaved, i.e., a serial schedule is one in which
no transaction starts until a running transaction has ended are called serial schedules.
Example: Consider the following schedule involving two transactions T1 and T2.
T1 T2

R(A)

W(A)

R(B)

W(B)

R(A)

R(B)

where R(A) denotes that a read operation is performed on some data item ‘A’
This is a serial schedule since the transactions perform serially in the order T1 —> T2
2. Complete Schedules
Schedules in which the last operation of each transaction is either abort (or) commit are called
5
 complete schedules.

6
 Example: Consider the following schedule involving three transactions T1, T2 and T3.
T1 T2 T3

R(A)

W(A)

R(B)

W(B)

commit

commit
abort
This is a complete schedule since the last operation performed under every transaction is either
“commit” or “abort”.
3. Recoverable Schedules
Schedules in which transactions commit only after all transactions whose changes they read commit
are called recoverable schedules. In other words, if some transaction Tj is reading value updated or written
by some other transaction Ti, then the commit of Tj must occur after the commit of Ti.
Example – Consider the following schedule involving two transactions T1 and T2.
T1 T2

R(A)

W(A)

W(A)

R(A)
commi
t
commit

This is a recoverable schedule since T1 commits before T2, that makes the value read by T2 correct.
4. Cascadeless Schedules –
Also called Avoids cascading aborts/rollbacks (ACA). Schedules in which transactions read values
only after all transactions whose changes they are going to read commit are called cascadeless schedules.
Avoids that a single transaction abort leads to a series of transaction rollbacks. A strategy to prevent
cascading aborts is to disallow a transaction from reading uncommitted changes from another transaction
in the same schedule.
In other words, if some transaction Tj wants to read value updated or written by some other transaction Ti,
then the commit of Tj must read it after the commit of Ti.
Example: Consider the following schedule involving two transactions T1 and T2.

7
 T1 T2

R(A)

W(A)

W(A)

commit

R(A)
commit
This schedule is cascadeless. Since the updated value of A is read by T2 only after the updating
transaction i.e. T1 commits.
5. Strict Schedules
A schedule is strict if for any two transactions Ti, Tj, if a write operation of Ti precedes a conflicting
operation of Tj (either read or write), then the commit or abort event of Ti also precedes that conflicting
operation of Tj.
In other words, Tj can read or write updated or written value of Ti only after Ti commits/aborts.
Example: Consider the following schedule involving two transactions T1 and T2.
T1 T2

R(A)

R(A)

W(A)

commit

W(A)

R(A)
commit
This is a strict schedule since T2 reads and writes A which is written by T1 only after the commit of T1.
Note – It can be seen that:
1. Cascadeless schedules are stricter than recoverable schedules or are a subset of recoverable schedules.
2. Strict schedules are stricter than cascadeless schedules or are a subset of cascadeless schedules.
3. Serial schedules satisfy constraints of all recoverable, cascadeless and strict schedules and hence is a
subset of strict schedules.

4. SERIALIZABILITY
When multiple transactions are running concurrently then there is a possibility that the database may
be left in an inconsistent state. Serializability is a concept that helps us to check which schedules are
serializable. A serializable schedule is the one that always leaves the database in consistent state.
What is a serializable schedule?
A serializable schedule always leaves the database in consistent state. A serial schedule is always a
serializable schedule because in serial schedule, a transaction only starts when the other transaction
finished execution. However, a non-serial schedule needs to be checked for Serializability.
Types of Serializability
There are two types of Serializability.
I. Conflict Serializability
II. View Serializability
1. Conflict Serializability
Conflict Serializability is one of the type of Serializability, which can be used to check whether a
non- serial schedule is conflict serializable or not.
What is Conflict Serializability?
A schedule is called conflict serializable if we can convert it into a serial schedule after swapping its
non-conflicting operations.
Conflicting operations
Two operations are said to be in conflict, if they satisfy all the following three conditions:
1. Both the operations should belong to different transactions.
2. Both the operations are working on same data item.
3. At least one of the operations is a write operation.
Let’s see some examples to understand this:
Example 1: Operation W(X) of transaction T1 and operation R(X) of transaction T2 are conflicting
operations, because they satisfy all the three conditions mentioned above. They belong to different
transactions, they are working on same data item X, one of the operations in write operation.
Example 2: Similarly, Operations W(X) of T1 and W(X) of T2 are conflicting operations.
Example 3: Operations W(X) of T1 and W(Y) of T2 are non-conflicting operations because both the
write operations are not working on same data item so these operations don’t satisfy the second condition.
Example 4: Similarly, R(X) of T1 and R(X) of T2 are non-conflicting operations because none of them is
write operation.
Example 5: Similarly, W(X) of T1 and R(X) of T1 are non-conflicting operations because both the
operations belong to same transaction T1.
Conflict Equivalent Schedules
Two schedules are said to be conflict Equivalent if one schedule can be converted into other schedule
after swapping non-conflicting operations.
Conflict Serializable check
Let’s check whether a schedule is conflict serializable or not. If a schedule is conflict Equivalent to its
serial schedule then it is called Conflict Serializable schedule. Let’s take few examples of schedules.
Example of Conflict Serializability
Let’s consider this schedule:
T1 T2

R(A)
R(B)
 R(A)
R(B)
W(B)
W(A)
To convert this schedule into a serial schedule we must have to swap the R(A) operation of transaction
T2 with the W(A) operation of transaction T1. However, we cannot swap these two operations because
they are conflicting operations, thus we can say that this given schedule is not Conflict Serializable.
Let’s take another example:
T1 T2
----- ------
R(A)
R(A)
R(B)
W(B)
R(B)
W(A)
Let’s swap non-conflicting operations:
After swapping R(A) of T1 and R(A) of T2 we get:
T1 T2
----- ------
R(A)
R(A)
R(B)
W(B)
R(B)
W(A)
After swapping R(A) of T1 and R(B) of T2 we get:
T1 T2
----- ------
R(A)
R(B)
R(A)
W(B)
R(B)
W(A)
After swapping R(A) of T1 and W(B) of T2 we get:
T1 T2
----- ------
R(A)
R(B)
W(B)
R(A)
R(B)
W(A)
We finally got a serial schedule after swapping all the non-conflicting operations so we can say that the
given schedule is Conflict Serializable.
2. View Serializability
View Serializability is a process to find out that a given schedule is view serializable or not.
To check whether a given schedule is view serializable, we need to check whether the given schedule
is View Equivalent to its serial schedule. Lets take an example to understand what I mean by that.
Given Schedule:
T1 T2
----- ------
R(X)
W(X)
R(X)
W(X)
R(Y)
W(Y)
R(Y)
W(Y)
Serial Schedule of the above given schedule:
As we know that in Serial schedule a transaction only starts when the current running transaction is
finished. So the serial schedule of the above given schedule would look like this:
T1 T2
----- ------
R(X)
W(X)
R(Y)
W(Y)
R(X)
W(X)
R(Y)
W(Y)
If we can prove that the given schedule is View Equivalent to its serial schedule then the given schedule
is called view Serializable.
Testing for Serializability
5. CONCURRENCY CONTROL
 In the concurrency control, the multiple transactions can be executed simultaneously.
It may affect the transaction result. It is highly important to maintain the order of execution of those
transactions.
6. NEED FOR CONCURRENCY
Problems of concurrency control
Several problems can occur when concurrent transactions are executed in an uncontrolled manner.
Following are the three problems in concurrency control.
  Lost updates
 Dirty read
 Unrepeatable read
1. Lost update problem
When two transactions that access the same database items contain their operations in a way that
makes the value of some database item incorrect, then the lost update problem occurs.
If two transactions T1 and T2 read a record and then update it, then the effect of updating of the first
record will be overwritten by the second update.
Example:

Here,
o At time t2, transaction-X reads A's value.
o At time t3, Transaction-Y reads A's value.
o At time t4, Transactions-X writes A's value on the basis of the value seen at time t2.
o At time t5, Transactions-Y writes A's value on the basis of the value seen at time t3.
o So at time T5, the update of Transaction-X is lost because Transaction y overwrites it
without looking at its current value.
o Such type of problem is known as Lost Update Problem as update made by one transaction
is lost here.
2. Dirty Read
o The dirty read occurs in the case when one transaction updates an item of the database,
and then the transaction fails for some reason. The updated database item is accessed by another
transaction before it is changed back to the original value.
o A transaction T1 updates a record which is read by T2. If T1 aborts then T2 now has
values which have never formed part of the stable database.
Example:

o At time t2, transaction-Y writes A's value.

o At time t3, Transaction-X reads A's value.
 o At time t4, Transactions-Y rollbacks. So, it changes A's value back to that of prior to t1.
o So, Transaction-X now contains a value which has never become part of the stable database.
o Such type of problem is known as Dirty Read Problem, as one transaction reads a dirty
value which has not been committed.
3. Inconsistent Retrievals Problem
o Inconsistent Retrievals Problem is also known as unrepeatable read. When a transaction
calculates some summary function over a set of data while the other transactions are updating the data,
then the Inconsistent Retrievals Problem occurs.
o A transaction T1 reads a record and then does some other processing during which the
transaction T2 updates the record. Now when the transaction T1 reads the record, then the new value
will be inconsistent with the previous value.
Example:
Suppose two transactions operate on three accounts.

o Transaction-X is doing the sum of all balance while transaction-Y is transferring an amount 50
from Account-1 to Account-3.
o Here, transaction-X produces the result of 550 which is incorrect. If we write this produced
result in the database, the database will become an inconsistent state because the actual sum is 600.
o Here, transaction-X has seen an inconsistent state of the database.
Concurrency Control Protocol
Concurrency control protocols ensure atomicity, isolation, and serializability of concurrent
transactions. The concurrency control protocol can be divided into three categories:
1. Lock based protocol
2. Time-stamp protocol

7. LOCKING PROTOCOLS
Lock-Based Protocol
In this type of protocol, any transaction cannot read or write data until it acquires an appropriate lock on it.
There are two types of lock:
1. Shared lock:
o It is also known as a Read-only lock. In a shared lock, the data item can only read by
the transaction.
o It can be shared between the transactions because when the transaction holds a lock, then
it can't update the data on the data item.
2. Exclusive lock:
o In the exclusive lock, the data item can be both reads as well as written by the transaction.
o This lock is exclusive, and in this lock, multiple transactions do not modify the same
data simultaneously.

8. TWO PHASE LOCKING (2PL)

The two-phase locking protocol divides the execution phase of the transaction into three parts.
o In the first part, when the execution of the transaction starts, it seeks permission for the lock
it requires.
o In the second part, the transaction acquires all the locks. The third phase is started as soon as
the transaction releases its first lock.
o In the third phase, the transaction cannot demand any new locks. It only releases the
acquired locks.
 There are two phases of 2PL:
 Growing phase: In the growing phase, a new lock on the data item may be acquired by the
transaction, but none can be released.
 Shrinking phase: In the shrinking phase, existing lock held by the transaction may be
released, but no new locks can be acquired.
In the below example, if lock conversion is allowed then the following phase can happen:
1. Upgrading of lock (from S(a) to X (a)) is allowed in growing phase.
2. Downgrading of lock (from X(a) to S(a)) must be done in shrinking phase.
Example:

The following way shows how unlocking and locking work with 2-PL.
Transaction T1:
o Growing phase: from step 1-3
o Shrinking phase: from step 5-7
o Lock point: at 3
Transaction T2:
o Growing phase: from step 2-6
o Shrinking phase: from step 8-9
o Lock point: at 6
Types of Two Phase Locking (2PL)
1. Strict Two-phase locking (Strict-2PL)
o The first phase of Strict-2PL is similar to 2PL. In the first phase, after acquiring all the locks,
the transaction continues to execute normally.
o The only difference between 2PL and strict 2PL is that Strict-2PL does not release a lock
after using it.
 o Strict-2PL waits until the whole transaction to commit, and then it releases all the locks at
a time.
o Strict-2PL protocol does not have shrinking phase of lock release.

It does not have cascading abort as 2PL does.

2. Rigorous Two-Phase Locking
 Rigorous Two – Phase Locking Protocol avoids cascading rollbacks.
 This protocol requires that all the share and exclusive locks to be held until the transaction
commits.
Timestamp Ordering Protocol
o The Timestamp Ordering Protocol is used to order the transactions based on their Timestamps.
The order of transaction is nothing but the ascending order of the transaction creation.
o The priority of the older transaction is higher that's why it executes first. To determine
the timestamp of the transaction, this protocol uses system time or logical counter.
o The lock-based protocol is used to manage the order between conflicting pairs among
transactions at the execution time. But Timestamp based protocols start working as soon as a
transaction is created.
o Let's assume there are two transactions T1 and T2. Suppose the transaction T1 has entered the
system at 007 times and transaction T2 has entered the system at 009 times. T1 has the higher priority,
so it executes first as it is entered the system first.
o The timestamp ordering protocol also maintains the timestamp of last 'read' and
'write' operation on a data.
Basic Timestamp ordering protocol works as follows:
1. Check the following condition whenever a transaction Ti issues a Read (X) operation:
o If W_TS(X) >TS(Ti) then the operation is rejected.
o If W_TS(X) <= TS(Ti) then the operation is executed.
o Timestamps of all the data items are updated.
2. Check the following condition whenever a transaction Ti issues a Write(X) operation:
o If TS(Ti) < R_TS(X) then the operation is rejected.
o If TS(Ti) < W_TS(X) then the operation is rejected and Ti is rolled back otherwise
the operation is executed.
Where,
TS(TI) denotes the timestamp of the transaction Ti.
R_TS(X) denotes the Read time-stamp of data-item X.
W_TS(X) denotes the Write time-stamp of data-item X.
Thomas write Rule
Thomas Write Rule provides the guarantee of serializability order for the protocol. It improves the
Basic Timestamp Ordering Algorithm.
The basic Thomas write rules are as follows:
o If TS(T) < R_TS(X) then transaction T is aborted and rolled back, and operation is rejected.
o If TS(T) < W_TS(X) then don't execute the W_item(X) operation of the transaction and
continue processing.
o If neither condition 1 nor condition 2 occurs, then allowed to execute the WRITE operation
by transaction Ti and set W_TS(X) to TS(T).

Problems
9. DEADLOCK
A deadlock is a condition wherein two or more tasks are waiting for each other in order to be finished
but none of the task is willing to give up the resources that other task needs. In this situation no task ever gets
finished and is in waiting state forever.
Coffman conditions
Coffman stated four conditions for a deadlock occurrence. A deadlock may occur if all the following
conditions holds true.
 Mutual exclusion condition: There must be at least one resource that cannot be used by more than one
process at a time.
 Hold and wait condition: A process that is holding a resource can request for additional resources that
are being held by other processes in the system.
 No preemption condition: A resource cannot be forcibly taken from a process. Only the process
can release a resource that is being held by it.
 Circular wait condition: A condition where one process is waiting for a resource that is being held
by second process and second process is waiting for third process ….so on and the last process is
waiting for the first process. Thus, making a circular chain of waiting.

For example: In the student table, transaction T1 holds a lock on some rows and needs to update some
rows in the grade table. Simultaneously, transaction T2 holds locks on some rows in the grade table and needs
to update the rows in the Student table held by Transaction T1.
 Now, the main problem arises. Now Transaction T1 is waiting for T2 to release its lock and similarly,
transaction T2 is waiting for T1 to release its lock. All activities come to a halt state and remain at a standstill.
It will remain in a standstill until the DBMS detects the deadlock and aborts one of the transactions.
Deadlock Avoidance
o When a database is stuck in a deadlock state, then it is better to avoid the database rather than aborting

or restating the database. This is a waste of time and resource.

o Deadlock avoidance mechanism is used to detect any deadlock situation in advance. A method like
"wait for graph" is used for detecting the deadlock situation but this method is suitable only for the
smaller database. For the larger database, deadlock prevention method can be used.
Deadlock Detection
In a database, when a transaction waits indefinitely to obtain a lock, then the DBMS should detect
whether the transaction is involved in a deadlock or not. The lock manager maintains a Wait for the graph to
detect the deadlock cycle in the database.
Wait for Graph
o This is the suitable method for deadlock detection. In this method, a graph is created based on the
transaction and their lock. If the created graph has a cycle or closed loop, then there is a deadlock.

o The wait for the graph is maintained by the system for every transaction which is waiting for some
data held by the others. The system keeps checking the graph if there is any cycle in the graph.

The wait for a graph for the above scenario is shown below:
Deadlock Prevention
o Deadlock prevention method is suitable for a large database. If the resources are allocated in such a

way that deadlock never occurs, then the deadlock can be prevented.

o The Database management system analyzes the operations of the transaction whether they can create a
deadlock situation or not. If they do, then the DBMS never allowed that transaction to be executed.

I. Wait-Die scheme
In this scheme, if a transaction requests for a resource which is already held with a conflicting lock by
another transaction then the DBMS simply checks the timestamp of both transactions. It allows the older
transaction to wait until the resource is available for execution.
Let's assume there are two transactions Ti and Tj and let TS(T) is a timestamp of any transaction T. If
T2 holds a lock by some other transaction and T1 is requesting for resources held by T2 then the following
actions are performed by DBMS:
1. Check if TS(Ti) < TS(Tj) - If Ti is the older transaction and Tj has held some resource, then Ti is
allowed to wait until the data-item is available for execution. That means if the older transaction is
waiting for a resource which is locked by the younger transaction, then the older transaction is allowed
to wait for resource until it is available.
2. Check if TS(Ti) < TS(Tj) - If Ti is older transaction and has held some resource and if Tj is waiting
for it, then Tj is killed and restarted later with the random delay but with the same timestamp.
II. Wound wait scheme
o In wound wait scheme, if the older transaction requests for a resource which is held by the younger
transaction, then older transaction forces younger one to kill the transaction and release the
resource. After the minute delay, the younger transaction is restarted but with the same timestamp.
o If the older transaction has held a resource which is requested by the Younger transaction, then
the younger transaction is asked to wait until older releases it.

Here is the table representation of resource allocation for each algorithm. Both of these
algorithms take process age into consideration while determining the best possible way of resource
allocation for deadlock avoidance. One of the famous deadlock avoidance algorithm is Banker’s
algorithm
10. TRANSACTION RECOVERY
UNIT IV IMPLEMENTATION TECHNIQUES
RAID – File Organization – Organization of Records in Files – Indexing and Hashing –Ordered
Indices – B+ tree Index Files – B tree Index Files – Static Hashing – Dynamic Hashing – Query
Processing Overview – Algorithms for SELECT and JOIN operations – Query optimization using
Heuristics and Cost Estimation
RAID
RAID (redundant array of independent disks) originally redundant array of inexpensive disks) is a way of
storing the same data in different places on multiple hard disks to protect data in the case of a drive failure.

www.Notesfree.
RAID: Redundant Arrays of Independent Disks
Disk organization techniques that manage a large numbers of disks, providing a view of a single disk
of high capacity and high speed by using multiple disks in parallel, and high reliability by storing data
redundantly, so that data can be recovered even if a disk fails
Motivation for RAID
 Just as additional memory in form of cache, can improve the system performance, in the same way
additional disks can also improve system performance.

n
 In RAID we can use an array of disks which operates independently since there are many disks,
multiple I/O requests can be handled in parallel if the data required is on separate disks
 A single I/O operation can be handled in parallel if the data required is distributed across multiple
disks.
Benefits of RAID
 Data loss can be very dangerous for an organization
 RAID technology prevents data loss due to disk failure
 RAID technology can be implemented in hardware or software
 Servers make use of RAID Technology
RAID Level 0- Stripping and non-redundant
 RAID level 0 divides data into block units and writes them across a number of disks. As data is
placed
across multiple disks it is also called “data Striping”.
 The advantage of distributing data over disks is that if different I/O requests are pending for two
different blocks of data, then there is a possibility that the requested blocks are on different disks

There is no parity checking of data. So if data in one drive gets corrupted then all the data would be lost.
Thus RAID 0 does not support data recovery Spanning is another term that is used with RAID level 0
because the logical disk will span all the physical drives. RAID 0 implementation requires minimum 2
disks.
Advantages
 I/O performance is greatly improved by spreading the I/O load across many channels & drives.
 Best performance is achieved when data is striped across multiple controllers with only one
driver per controller
Disadvantages
 It is not fault-tolerant, failure of one drive will result in all data in an array being lost
RAID Level 1: Mirroring (or shadowing)
 Also known as disk mirroring, this configuration consists of at least two drives that duplicate the
storage of
 data. There is no striping.
 Read performance is improved since either disk can be read at the same time. Write performance is
the same as for single disk storage.
 Every write is carried out on both disks. If one disk in a pair fails, data still available in the other.
 Data loss would occur only if a disk fails, and its mirror disk also fails before the system is
repaired Probability of combined event is very small.

www.Notesfree.
n
RAID Level 2:
This configuration uses striping across disks, with some disks storing error checking and correcting (ECC)
information. It has no advantage over RAID 3 and is no longer used.

RAID Level 3: Bit-Interleaved Parity

 A single parity bit is enough for error correction, not just detection, since we know which disk has
failed
– When writing data, corresponding parity bits must also be computed and written to a parity
bit disk
– To recover data in a damaged disk, compute XOR of bits from other disks (including parity
bit disk)
 I/O operation addresses all the drives at the same time, RAID 3 cannot overlap I/O. For this reason,
RAID 3 is best for single-user systems with long record applications.
RAID Level 4: Block-Interleaved Parity
 When writing data block, corresponding block of parity bits must also be computed and written
to parity disk
 To find value of a damaged block, compute XOR of bits from corresponding blocks (including
parity block) from other disks.

RAID Level 5:
 RAID 5 uses striping as well as parity for redundancy. It is well suited for heavy read and
low write operations.
 Block-Interleaved Distributed Parity; partitions data and parity among all N + 1 disks, rather
than storing data in N disks and parity in 1 disk.

RAID Level 6:
 This technique is similar to RAID 5, but includes a second parity scheme that is distributed across
the drives in the array. The use of additional parity allows the array to continue to function even if
two disks fail simultaneously. However, this extra protection comes at a cost.
 P+Q Redundancy scheme; similar to Level 5, but stores extra redundant information to guard
against multiple disk failures.
- Better reliability than Level 5 at a higher cost; not used as widely.
 File Organization
 The database is stored as a collection of files.
 Each file is a sequence of records.
 A record is a sequence of fields.
 Classifications of records
– Fixed length record
– Variable length record
 Fixed length record approach:
Assume record size is fixed each file has records of one particular type only different files
are used for different relations
Simple approach
- Record access is
simple Example pseudo code
type account = record
account_number
char(10); branch_name
char(22); balance
numeric(8);
end
Total bytes 40 for a
record

Two
problems - Difficult to delete record from this structure.
- Some record will cross block boundaries, that is part of the record will be stored in one block
and
part in another. It would require two block accesses to read or write
Reuse the free space alternatives:
– move records i + 1, . . ., n to n i, . . . , n – 1
– do not move records, but link all free records
on a free list
– Move the final record to deleted record place.
Free Lists
 Store the address of the first deleted record in the file header.
 Use this first record to store the address of the second deleted record, and so on
Variable-Length Records
Byte string representation
 Attach an end-of-record () control character to the end of each record
 Difficulty with deletion
0 perryridge A-102 400 A-201 900 

www.Notesfree.
1 roundhill A-305 350 

2 mianus A-215 700 

Disadvantage
 It is not easy to reuse space occupied formerly by deleted record.
 There is no space in general for records grows longer
Slotted Page Structure

n
 Slotted page header contains:
– number of record entries
– end of free space in the block
– location and size of each record

Pointer Method

 A variable-length record is represented by a list of fixed-length records, chained together via

pointers.
 Can be used even if the maximum record length is not known.
Disadvantage to pointer structure; space is wasted in all records except the first in a a
chain. Solution is to allow two kinds of block in file:
 Anchor block – contains the first records of chain
 Overflow block – contains records other than those that are the first records of chains.
Organization of Records in Files
• Sequential – store records in sequential order, based on the value of the search key of each record
• Heap – a record can be placed anywhere in the file where there is space
• Hashing – a hash function computed on some attribute of each record; the result specifies in
which block of the file the record should be placed
Sequential File Organization
• Suitable for applications that require sequential processing of the entire file
• The records in the file are ordered by a search-key

Deletion – use pointer chains

Insertion – locate the position where the record is to be inserted
– if there is free space insert there
– if no free space, insert the record in an overflow block
– In either case, pointer chain must be updated

Indexing and Hashing

Basic
Concepts
 Indexing mechanisms used to speed up access to desired data.
– E.g., author catalog in library
 Search Key - attribute to set of attributes used to look up records in
a file. An index file consists of records (called index entries) of the form

Search-key pointer

 Index files are typically much smaller than the original file
 Two basic kinds of indices:
– Ordered indices: search keys are stored in sorted order
– Hash indices: search keys are distributed uniformly across “buckets” and by using a
“hash function” the values are determined.
Ordered Indices
 In an ordered index, index entries are stored sorted on the search key value.
 Primary index: in a sequentially ordered file, the index whose search key specifies the sequential
order of the file.
 Secondary index: an index whose search key specifies an order different from the sequential
order of the file.
Types of Ordered Indices
 Dense index
  Sparse index
Dense Index Files
  Dense index — Index record appears for every search-key value in the file.

www.Notesfree.
Sparse Index Files
 Sparse Index
contains index records for only some search-key values.
 To locate a record with search-key value K we:

n
– Find index record with largest search-key value that is less than or
equal to Search file sequentially starting at the record to which the index record
points

Multilevel Index
 If primary index does not fit in memory, access becomes expensive.
 To reduce number of disk accesses to index records, treat primary index kept on disk as a
sequential file and construct a sparse index on it.
– outer index – a sparse index of primary index
– inner index – the primary index file
 If even outer index is too large to fit in main memory, yet another level of index can be created, and
so on.
Index Update: Deletion
If deleted record was the only record in the file with its particular search-key value, the search-key is
deleted from the index also.
 Single-level index deletion:
– Dense indices – deletion of search-key is similar to file record deletion.
– Sparse indices – if an entry for the search key exists in the index, it is deleted by replacing
the entry in the index with the next search-key value in the file (in search-key order). If the
next search-key value already has an index entry, the entry is deleted instead of being
replaced.
Index Update: Insertion
 Single-level index insertion:
– Perform a lookup using the search-key value appearing in the record to be inserted.
– Dense indices – if the search-key value does not appear in the index, insert it.
– Sparse indices – if index stores an entry for each block of the file, no change needs to be
made to the index unless a new block is created. In this case, the first search-key value
appearing in the new block is inserted into the index.
Secondary Index on balance field of account

Primary and Secondary Indices

 Secondary indices have to be dense.
 Indices offer substantial benefits when searching for records.
 When a file is modified, every index on the file must be updated, Updating indices imposes
overhead on database modification.
 Sequential scan using primary index is efficient, but a sequential scan using a secondary index is
expensive
– each record access may fetch a new block from disk
`
B+-Tree Index Files
Example of a B+-tree : B+-tree for account file (n = 3)
  Disadvantage of indexed-sequential files: performance degrades as file grows, since many
overflow blocks get created. Periodic reorganization of entire file is required.
 Advantage of B+-tree index files: automatically reorganizes itself with small, local, changes, in
the face of insertions and deletions. Reorganization of entire file is not required to maintain
performance.
 Disadvantage of B+-trees: extra insertion and deletion overhead, space overhead.

A B+-tree is a rooted tree satisfying the following properties:

 All paths from root to leaf are of the same length
 Each node that is not a root or a leaf has between [n/2] and n children.
 Special cases:
– If the root is not a leaf, it has at least 2 children.
– If the root is a leaf, it can have between 0 and (n–1) values.
+
B -Tree Node Structure
 Typical node

– Ki are the search-key values

– Pi are pointers to children (for non-leaf nodes) or pointers to records or buckets of records
(for leaf nodes).
 The search-keys in a node are ordered
K1 < K2 < K3 < . . . < Kn–1
Properties of Leaf Nodes
 For i = 1, 2, . . ., n–1, pointer Pi either points to a file record with search-key value Ki, or to a
bucket of pointers to file records, each record having search-key value Ki.
 Pn points to next leaf node in search-key order

Non-Leaf Nodes in B+-Trees

Non leaf nodes form a multi-level sparse index on the leaf nodes. For a non-leaf node with m pointers:
– All the search-keys in the subtree to which P1 points are less than K1.

Example of a B+-tree: B+-tree for account file (n = 3)

B+-tree for account file (n = 5)

 Non-leaf nodes other than root must have between 3 and 5 children ((n/2 and n with n =5).
 Root must have at least 2 children.
Observations about B+-trees
 Since the inter-node connections are done by pointers, “logically” close blocks need not be
“physically”
close.
 The B+-tree contains a relatively small number of levels thus searches can be conducted efficiently.
 Insertions and deletions to the main file can be handled efficiently.
Updates on B+-Trees: Insertion
 Find the leaf node in which the search-key value would appear
 If the search-key value is already there in the leaf node, record is added to file and if necessary a
pointer is inserted into the bucket.
 If the search-key value is not there, then add the record to the main file and create a bucket if
necessary.Then:
– If there is room in the leaf node, insert (key-value, pointer) pair in the leaf node otherwise,
split the node.
Example: B+-Tree before and after insertion of “Clearview”

Updates on B+-Trees: Deletion

• Find the record to be deleted, and remove it from the main file and from the bucket (if present)
• Remove (search-key value, pointer) from the leaf node if there is no bucket or if the bucket has
become empty
• If the node has too few entries due to the removal, and the entries in the node and a sibling fit into
a single node, then
– Insert all the search-key values in the two nodes into a single node (the one on the left), and
delete
 the other node.
– Delete the pair (Ki–1, Pi), where Pi is the pointer to the deleted node, from its parent,
recursively using the above procedure.

Before and after deleting “Downtown”

• The removal of the leaf node containing “Downtown” did not result in its parent having too little
pointers.
So the cascaded deletions stopped with the deleted leaf node’s parent.
Deletion of “Perryridge” from result of previous example

• Node with “Perryridge” becomes empty and merged with its sibling.
• Root node then had only one child, and was deleted and its child became the new root node
B+-Tree File Organization
• The leaf nodes in a B+-tree file organization store records, instead of pointers.
• Since records are larger than pointers, the maximum number of records that can be stored in a
leaf node is less than the number of pointers in a nonleaf node.
• Leaf nodes are still required to be half full.
• Insertion and deletion are handled in the same way as insertion and deletion of entries in a B+-tree index.
B-Tree Index Files
• Similar to B+-tree, but B-tree allows search-key values to appear only once; eliminates redundant
storage of search keys.
• Search keys in nonleaf nodes appear nowhere else in the B-tree; an additional pointer field for
each search key in a nonleaf node must be included.

Generalized B-tree leaf node

Nonleaf node – pointers Bi are the bucket or file record pointers.

B+-tree on same data

Advantages of B-Tree indices:

– May use less tree nodes than a corresponding B+-Tree.
– Sometimes possible to find search-key value before reaching leaf node.
Disadvantages of B-Tree indices:
– Only small fraction of all search-key values are found early
– Non-leaf nodes are larger, so fan-out is reduced (no. of pointers). Thus, B-Trees
typically have greater depth than corresponding B+-Tree
– Insertion and deletion more complicated than in B+-Trees
– Implementation is harder than B+-Trees.

HASHING
• Hashing is an effective technique to calculate the direct location of a data record on the disk
without using index structure.
• Hashing uses hash functions with search keys as parameters to generate the address of a data record.
Hash
Organization
Bucket
A hash file stores data in bucket format. Bucket is considered a unit of storage. A bucket
typically stores one complete disk block, which in turn can store one or more records.
Hash Function
A hash function, h, is a mapping function that maps all the set of search-keys K to the
address where actual records are placed. It is a function from search keys to bucket addresses.
 Worst hash function maps all search-key values to the same bucket.
  An ideal hash function is uniform, i.e., each bucket is assigned the same number of search-key
values from the set of all possible values.
 Ideal hash function is random, so each bucket will have the same number of
records. Types
• Static Hashing
• Dynamic Hashing
Static Hashing
 In static hashing, when a search-key value is provided, the hash function always computes the same
address.
 For example, if mod-4 hash function is used, then it shall generate only 5 values. The output
address shall always be same for that function.
 The number of buckets provided remains unchanged at all times.
Example of Hash File Organization
 There are 10 buckets,
 The hash function returns the sum of the binary representations of the characters modulo 10
– E.g. h(Perryridge) = 5 h(Round Hill) = 3 h(Brighton) = 3

Operation
 Insertion − When a record is required to be entered using static hash, the hash function h
computes the bucket address for search key K, where the record will be stored.
Bucket address = h(K)
 Search − When a record needs to be retrieved, the same hash function can be used to retrieve the
address of
the bucket where the data is stored.
 Delete − This is simply a search followed by a deletion operation.
Handling of Bucket Overflows
 Bucket overflow can occur because of
– Insufficient buckets
– Skew in distribution of records. This can occur due to :
• multiple records have same search-key value
 Although the probability of bucket overflow can be reduced, it cannot be eliminated; it is handled
by using overflow buckets.
 Overflow chaining – the overflow buckets of a given bucket are chained together in a linked list.
 Above scheme is called closed hashing.
– An alternative, called open hashing, which does not use overflow buckets, is not
suitable for database applications.
 www.Notesfree.
Hash Indices

n
• Hashing can be used not only for file organization, but also for index-structure creation.
• A hash index organizes the search keys, with their associated record pointers, into a hash file
structure.
• Hash indices are always secondary indices

Deficiencies of Static Hashing

 In static hashing, function h maps search-key values to a fixed set of B of bucket addresses.
– Databases grow with time. If initial number of buckets is too small, performance will
degrade due to too much overflows.
– If file size at some point in the future is anticipated and number of buckets allocated
accordingly, significant amount of space will be wasted initially.
– If database shrinks, again space will be wasted.
 These problems can be avoided by using techniques that allow the number of buckets to be
modified dynamically.
Dynamic Hashing
• Good for database that grows and shrinks in size
• Allows the hash function to be modified dynamically
• Extendable hashing – one form of dynamic hashing
– Hash function generates values over a large range — typically b-bit integers, with b = 32.
– At any time use only a prefix of the hash function to index into a table of bucket addresses.
– Let the length of the prefix be i bits, 0  i  32.
– Bucket address table size = 2i. Initially i = 0
– Value of i grows and shrinks as the size of the database grows and shrinks.
– Multiple entries in the bucket address table may point to a bucket.
– Thus, actual number of buckets is < 2i
 – The number of buckets also changes dynamically due to coalescing and splitting of
buckets.
General Extendable Hash
In this structure, i2 = i3 = i, whereas i1 = i – 1

www.Notesfree.
n
Insertion in Extendable Hash Structure
To split a bucket j when inserting record with search-key value Kj:
 If i > ij (more than one pointer to bucket j)
– allocate a new bucket z, and set ij = iz = (ij + 1)
– Update the second half of the bucket address table entries originally pointing to j, to point to
z
– remove each record in bucket j and reinsert (in j or z)
– recompute new bucket for Kj and insert record in the bucket (further splitting is
required if the bucket is still full)
 If i = ij (only one pointer to bucket j)
– If i reaches some limit b, or too many splits have happened in this insertion, create an
overflow bucket
 Else
– increment i and double the size of the bucket address table.
– replace each entry in the table by two entries that point to the same bucket.
– recompute new bucket address table entry for Kj
Now i > ij so use the first case above.
Deletion in Extendable Hash Structure
 To delete a key value,
– locate it in its bucket and remove it.
– The bucket itself can be removed if it becomes empty (with appropriate updates to the
bucket address table).
– Coalescing of buckets can be done (can coalesce only with a “buddy” bucket having same
value of ij
and same ij –1 prefix, if it is present)
– Decreasing bucket address table size is also possible
• Note: decreasing bucket address table size is an expensive operation and should
be done only if number of buckets becomes much smaller than the size of the table
Example
Initial Hash structure, bucket size = 2
Hash structure after insertion of one Brighton and two Downtown records

www.Notesfree.
n
Hash structure after insertion of Mianus record

Hash structure after insertion of three Perryridge records

Hash structure after insertion of Redwood and Round Hill records

Use of Extendable Hash Structure

 To locate the bucket containing search-key Kj:
1. Compute h(Kj) = X
2. Use the first i high order bits of X as a displacement into bucket address table, and follow the
pointer to
 appropriate bucket
Updates in Extendable Hash Structure
 To insert a record with search-key value Kj
– follow same procedure as look-up and locate the bucket, say j.
– If there is room in the bucket j insert record in the bucket.
– Overflow buckets used instead in some cases.
 To delete a key value,
– locate it in its bucket and remove it.
– The bucket itself can be removed if it becomes empty
– Coalescing of buckets can be done
– Decreasing bucket address table size is also possible
 Benefits of extendable hashing:
– Hash performance does not degrade with growth of file
– Minimal space overhead
 Disadvantages of extendable hashing
– Extra level of indirection to find desired
record Bucket address table may itself become very big.

QUERY PROCESSING OVERVIEW

1. The scanning, parsing, and validating module produces an internal representation of the query.
2. The query optimizer module devises an execution plan which is the execution strategy to retrieve
the result of the query from the database files. A query typically has many possible execution
strategies differing in performance, and the process of choosing a reasonably efficient one is known
as query optimization. Query optimization is beyond this course. The code generator generates the
code to execute the plan.The runtime database processor runs the generated code to produce the
query result.

Evaluation of SQL Statement

The query is evaluated in a different order.
 The tables in the from clause are combined using Cartesian products.The where predicate is then applied.
 The resulting tuples are grouped according to the group by clause.The having predicate is applied
to each group, possibly eliminating some groups.The aggregates are applied to each remaining
group.The select clause is performed last.
Translating SQL Queries into Relational Algebra
 SQL query is first translated into an equivalent extended relational algebra expression.
 SQL queries are decomposed into query blocks, which form the basic units that can be translated
into the algebraic operators and optimized.
 Query block contains a single SELECT-FROM-WHERE expression, as well as GROUP BY and
HAVING clauses.
  Nested queries within a query are identified as separate query blocks.
Example:
 SELECT LNAME,
FNAME FROM
EMPLOYEE
WHERE SALARY > (SELECT MAX(SALARY)
FROM
EMPLOYEE
WHERE DNO=5);
 The inner block
• (SELECT MAX (SALARY) FROM EMPLOYEE WHERE DNO=5)
– Translated in:
• ℑ MAX SALARY( σDNO=5(EMPLOYEE))
 The Outer block
• SELECT LNAME, FNAME FROM EMPLOYEE WHERE SALARY > C
– Translated in:
• ∏ LNAZME, FNAME ( σSALARY>C(EMPLOYEE))
(C represents the result returned from the inner block.)
 The query optimizer would then choose an execution plan for each block.
 The inner block needs to be evaluated only once. (Uncorrelated nested query).
 It is much harder to optimize the more complex correlated nested queries.
External Sorting
It refers to sorting algorithms that are suitable for large files of records on disk that do not fit entirely in
main memory, such as most database files..
 ORDER BY.
 Sort-merge algorithms for JOIN and other operations (UNION, INTERSECTION). Duplicate
elimination algorithms for the PROJECT operation (DISTINCT). Typical external sorting
algorithm uses a sort-merge strategy: Sort phase: Create sort small sub-files (sorted sub-files are
called runs).
 Merge phase: Then merges the sorted runs. N-way merge uses N memory buffers to buffer input
runs, and 1 block to buffer output. Select the 1st record (in the sort order) among input buffers,
write it to the output buffer and delete it from the input buffer. If output buffer full, write it to disk.
If input buffer empty, read next block from the corresponding run..
E.g. 2-way Sort-Merge

Basic Algorithms for Executing Relational Query

Operations
 An RDBMS must include one or more alternative algorithms that implement each relational algebra
operation (SELECT, JOIN,…) and, in many cases, that implement each combination of these operations.
 Each algorithm may apply only to particular storage structures and access paths (such index,…).
 Only execution strategies that can be implemented by the RDBMS algorithms and that apply to
the particular query and particular database design can be considered by the query optimization
module.
Algorithms for implementing SELECT operation
 These algorithms depend on the file having specific access paths and may apply only to certain
types of selection conditions.
 We will use the following examples of SELECT operations:
– (OP1):σSSN=‘123456789’ (EMPLOYEE)
– (OP2):σ DNUMBER > 5 (DEPARTMENT)
 – (OP3):σDNO=5 (EMPLOYEE)
– (OP4):σ DNO=5 AND SALARY>30000 AND SEX = ‘F’ (EMPLOYEE)
– (OP5):σESSN=‘123456789’ AND PNO=10 (WORKS_ON)
 Many search methods can be used for simple selection: S1 through S6
 S1: Linear Search (brute force) –full scan in Oracle’s terminology-
– Retrieves every record in the file, and test whether its attribute values satisfy the selection
condition: an expensive approach.
– Cost: b/2 if key and b if no key
 S2: Binary Search
– If the selection condition involves an equality comparison on a key attribute on which
the file is ordered.
– σSSN=‘1234567’ (EMPLOYEE), SSN is the ordering attribute.
– Cost: log2b if key.
 S3: Using a Primary Index (hash key)
– An equality comparison on a key attribute with a primary index (or hash key).
– This condition retrieves a single record (at most).
– Cost :primary index : bind/2 + 1(hash key: 1bucket if no collision).
 S4: Using a primary index to retrieve multiple records
– Comparison condition is >, >=, <, or <= on a key field with a primary index
– σDNUMBER >5(DEPARTMENT)
– Use the index to find the record satisfying the corresponding equality condition
(DNUMBER=5), then retrieve all subsequent records in the (ordered) file.
– For the condition (DNUMBER <5), retrieve all the preceding records.
– Method used for range queries too(i.e. queries to retrieve records in certain range)
– Cost: bind/2 + ?. ‘?’ could be known if the number of duplicates known.
 S5: Using a clustering index to retrieve multiple records
– If the selection condition involves an equality comparison on a non-key
attribute with a clustering index.
– σDNO=5(EMPLOYEE)
– Use the index to retrieve all the records satisfying the condition.
– Cost: log2bind + ?. ‘?’ could be known if the number of duplicates known.
 S6: Using a secondary (B+-tree) index on an equality comparison
– The method can be used to retrieve a single record if the indexing field is a key or to retrieve
multiple records if the indexing field is not a key.
– This can also be used for comparisons involving >, >=, <, or <=.
– Method used for range queries too.
– Cost to retrieve: a key= height + 1; a non key= height+1(extra-level)+?, comparison=(height-1)+?
+?
 Many search methods can be used for complex selection which involve a Conjunctive Condition:
S7 through as S9.
– Conjunctive condition: several simple conditions connected with the AND logical connective.
– (OP4): s DNO=5 AND SALARY>30000 AND SEX = ‘F’ (EMPLOYEE).
 S7:Conjunctive selection using an individual index.
– If an attribute involved in any single simple condition in the conjunctive condition has an
access path that permits the use of one of the Methods S2 to S6, use that condition to retrieve
the records.
– Then check whether each retrieved record satisfies the remaining simple conditions in the
conjunctive condition
 S8:Conjunctive selection using a composite index:
– If two or more attributes are involved in equality conditions in the conjunctive
condition and a composite index (or hash structure) exists on the combined fields.
– Example: If an index has been created on the composite key (ESSN, PNO) of the WORKS_ON
file,
 we can use the index directly.
– (OP5):σESSN=‘123456789’ AND PNO=10 (WORKS_ON).
 S9: Conjunctive selection by intersection of record pointers
– If the secondary indexes are available on more than one of the fields involved in simple
conditions in the conjunctive condition, and if the indexes include record pointers (rather than
block pointers), then each index can be used to retrieve the set of record pointers that satisfy
the individual condition.

www.Notesfree.
– The intersection of these sets of record pointers gives the record pointers that satisfy the
conjunctive condition.
– If only some of the conditions have secondary indexes, each retrieval record is further tested
to determine whether it satisfies the remaining conditions.

Algorithms for implementing JOIN Operation

 Join: time-consuming operation. We will consider only natural join operation

n
– Two-way join: join on two files.
– Multiway join: involving more than two files.
 The following examples of two-way JOIN operation (RΘ A=BS) will be used:
– OP6: EMPLOYEE Θ DNO=DNUMBER DEPARTMENT
– OP7: DEPARTMENT Θ MGRSSN=SSN EMPLOYEE
 J1: Nested-loop join (brute force)
– For each record t in R (outer loop), retrieve every record s from S (inner loop) and test
whether the two records satisfy the join condition t[A] = s[B].
 J2: Single-loop join (using an access structure to retrieve the matching records)
– If an index (or hash key) exists for one of the two join attributes (e.g B of S), retrieve each
record t in R, one at a time (single loop), and then use the access structure to retrieve directly
all matching records s from S that satisfy s[B] = t[A]
 J3: Sort-merge join:
– If the records of R and S are physically sorted (ordered) by value of the join attributes A
and B, respectively, we can implement the join in the most efficient way.
– Both files are scanned concurrently in order of the join attributes, matching the records that
have the same values for A and B.
– If the files are not sorted, they may be sorted first by using external sorting.
– Pairs of file blocks are copied into memory buffers in order and records of each file are
scanned only once each for matching with the other file if A & B are key attributes.
– The method is slightly modified in case where A and B are not key attributes.
 J4: Hash-join
– The records of files R and S are both hashed to the same hash file using the same hashing
function on the join attributes A of R and B of S as hash keys.
 Partitioning Phase
– First, a single pass through the file with fewer records (say, R) hashes its records to the
hash file buckets.
– Assumption: The smaller file fits entirely into memory buckets after the first phase.
– (If the above assumption is not satisfied, the method is a more complex one and number of
variations have been proposed to improve efficiency: partition has join and hybrid hash join.)
 Probing Phase
– A single pass through the other file (S) then hashes each of its records to probe appropriate
bucket, and that record is combined with all matching records from R in that bucket.
Heuristic-Based Query Optimization
 1. Break up SELECT operations with conjunctive conditions into a cascade of SELECT operations
2. Using the commutativity of SELECT with other operations, move each SELECT operation as far
down the query tree as is permitted by the attributes involved in the select condition

3. Using commutativity and associativity of binary operations, rearrange the leaf nodes of the tree
4. Combine a CARTESIAN PRODUCT operation with a subsequent SELECT operation in the
tree into a JOIN operation, if the condition represents a join condition
5. Using the cascading of PROJECT and the commuting of PROJECT with other operations, break
down and move lists of projection attributes down the tree as far as possible by creating new
PROJECT operations as needed
6. Identify sub-trees that represent groups of operations that can be executed by a single algorithm
Example
 Query
"Find the last names of employees born after 1957 who work on a project named ‘Aquarius’."
 SQL
SELECT LNAME
FROM EMPLOYEE, WORKS_ON, PROJECT
WHERE PNAME=‘Aquarius’ AND PNUMBER=PNO AND ESSN=SSN AND BDATE.‘1957-12-31’;

Cost Estimation in Query Optimization

The main aim of query optimization is to choose the most efficient way of implementing the relational
algebra operations at the lowest possible cost.
 The query optimizer should not depend solely on heuristic rules, but, it should also estimate
the cost of executing the different strategies and find out the strategy with the minimum cost
estimate.
The cost functions used in query optimization are estimates and not exact cost functions.
 The cost of an operation is heavily dependent on its selectivity, that is, the proportion of select
operation(s) that forms the output.
 In general the different algorithms are suitable for low or high selectivity queries.
 In order for query optimizer to choose suitable algorithm for an operation an estimate of the
cost of executing that algorithm must be provided
The cost of an algorithm depends on cardinality of its input.
 To estimate the cost of different query execution strategies, the query tree is viewed as containing a
series of basic operations which are linked in order to perform the query.
 It is also important to know the expected cardinality of an operation’s output because this forms the
input to
the next operation.
Cost Components of Query Execution
The cost of executing the query includes the following components:
– Access cost to secondary storage.
– Storage cost.
– Computation cost.
– Memory uses cost.
– Communication cost.
Importance of Access cost
Out of the above five cost components, the most important is the secondary storage access cost.
 The emphasis of the cost minimization depends on the size and type of database applications.
 For example in smaller database the emphasis is on the minimizing computing cost as because
most of the data in the files involve in the query can be completely store in the main memory.
 For large database, the main emphasis is on minimizing the access cost to secondary device.
 For distributed database, the communication cost is minimized as because many sites are involved
 for the data transfer.
Cost functions for SELECT
Operation Linear Search:
– [nBlocks(R)/2], if the record is found.
– [nBlocks(R)], if no record satisfied the condition.
Binary Search :
o [log2(nBlocks(R))], if equality condition is on key attribute, because SCA(R) = 1 in this case.
o[log2(nBlocks(R))] + [SCA(R)/bFactor(R)] – 1, otherwise.
Equity condition on Primary key
– [nLevelA(I) + 1]
Equity condition on Non-Primary key
– [nLevelA(I) + 1] + [nBlocks(R)/2]
Cost functions for JOIN Operation
Join operation is the most time consuming operation to process.
 An estimate for the size (number of tuples) of the file that results after the JOIN operation is
required to develop reasonably accurate cost functions for JOIN operations.
 The JOIN operations define the relation containing tuples that satisfy a specific predicate F from
the Cartesian product of two relations R and S.