DATA BASE MANAGEMENT SYSTEM

DBMSUnit1
DatabaseSystemApplications
AHistoricalPerspective
Early1960s:Hierarchicalandnavigationaldatamodelsused,inefficientanddifficulttomanage.
Late1960s:CharlesBachmaninventsthefirstgeneral-purposeDBMS(Integrated Data Store)
using the network model.
Late1970s:EdgarCoddproposestherelationalmodel,usingtablesforeasierdata storage and
retrieval.
Late1980s:IBMdevelopsSQLforrelationaldatabases,allowingmanagementoflarge datasets.
1980s:Introductionofuser-friendlyDBMSproductslikeOracle,Sybase,andMicrosoft SQL Server.
1990s:Object-orientedDBMS(OODBMS)emergeforcomplexdatastructures,but adoption is
limited commercially.
1991: Microsoft releases MSAccess, dominating the personal DBMS market.
1997: XMLintegration into DBMS products begins.
2000s:RiseofwebapplicationsandcloudcomputingleadstonewDBMSsystemslike NoSQL
databases.
Today:DBMScontinuestoevolve,focusingonscalability,performance,andcloud support.
Popular options include Oracle, SQL Server, MySQL, PostgreSQL, and MongoDB.

Database SystemApplications
AHistoricalPerspective
File Systems versus a DBMS
The Data Model
Levels ofAbstraction in a DBMS
Data Independence
Structure of a DBMS

IntroductiontoDatabaseDesign
Database Design and ER Diagrams
Entities,Attributes, and Entity Sets
Relationships and Relationship Sets

1 page
DATA BASE MANAGEMENT SYSTEM

Additional Features of the ER Model

Conceptual Design With the ER Model

AHistoricalPerspective

Data collection and storage challenges

Evolution from hierarchical to relational models
Contributions of Charles Bachman and Edgar Codd
Emergence of SQLand relational databases
Evolution into object-oriented and NoSQLdatabases
Contemporary trends towards cloud-based applications

IntroductiontoDatabaseManagementSystem(DBMS)

Definition of data, database, and DBMS

Role of DBMS in managing data
Importance in various sectors like banking, education, etc.
Distinction between data and information
Significance of metadata in database management

DatabaseSystemApplications

1. Banking
2. Universities
3. Airlines
4. Railways

2 page
 DATA BASE MANAGEMENT SYSTEM

5. Sales
6. Manufacturing
7. Telecommunication
8. Human Resources

AdvantagesofDatabaseManagementSystem

1. Efficientdatastorageandretrieval
2. Data independence
3. Backup and recovery facilities
4. Consistent and updated information
5. Enhanced data security
6. Centralized data administration
7. Representation of complex data relationships

ComponentsofDBMS

1. Hardware
Importance of hardware in DBMS
Examples of hardware components

3 page
 DATA BASE MANAGEMENT SYSTEM
2. Software

4 page
 DATA BASE MANAGEMENT SYSTEM

RoleandtypesofsoftwareinDBMS
Examples of DBMS software
3. Data
NatureandimportanceofdatainDBMS
Types of data and metadata
4. People
Rolesofdatabaseadministrator,softwaredeveloper,andenduser
Classification of database users

[Link]
WhatisaFileSystem?
Techniqueforarrangingfilesinstoragemediumslikeharddisks,pendrives,DVDs,etc.
Organizes data for easy retrieval.
Consists of various file types (e.g., mp3, mp4, txt, doc) grouped into directories.
Installed directly into the computer's operating system (e.g., Windows, Linux).

WhatisDBMS?
Software for storing and retrieving user data with security measures.
Consists of programs manipulating the database.
AcceptsdatarequestsfromapplicationsandprovidesspecificdataviatheDBMS engine.
Facilitatesdatastorageandretrievalforusersandthird-partysoftwareinlarge systems.

DifferencebetweenFileSystemandDBMS:

Feature File System DBMS

Purpose Used to manage and Asoftwaretostoreandretrieve the
organisethefilesstoredintheharddisk user's data
of the computer
Redundant data Present No presence of redundant data
Query processing Not so efficient Efficient
efficiency

Data consistency Low High (due to normalization)

5 page
 DATA BASE MANAGEMENT SYSTEM

Feature File System DBMS

Complexity Lesscomplex,doesnotsupport Morecomplexityinmanaging data,
complicated transactions supports complicated transactions
easier
Security Less Supportsmoresecuritymechanisms

Cost LessexpensivecomparedtoDBMS Higher cost than file system

Crash recovery Does not support crash recovery Highlysupportedcrashrecoverymechani

sm

FeaturesofFileSystem
Stores data in groups of files.
Data dependency among files.
Designed using languages like C/C++ and COBOL.
Supports shared file systems.
Enables fast file system recovery.

FeaturesofDBMS
User-accessible catalog of data.
Transactionsupport.
Concurrency control with recovery services.
Authorization services.
Ensures consistent data value across all locations.
Offersdatacommunicationsupport.
Provides independent utility services.
Allows simultaneous file sharing among multiple users.

TheDataModel
DatamodelsinDBMShelpinunderstandingdatabasedesignatconceptual,physical,and logical levels,
providing clarity for developers in creating physical databases.

HierarchicalModel
Organizes data into a tree-like structure with a single root.
Each child node has only one parent node.
Efficientlyrepresentsone-to-many relationships(e.g., indexofabook, recipes).

6 page
 DATA BASE MANAGEMENT SYSTEM

NetworkModel
An extension of the Hierarchical model.
Organizes data more like a graph, allowing nodes to have more than one parent.
Establishes multiple relationships, facilitating easier and faster data access.

Entity-relationship Model(E-RModel)
Divides objects of interest into entities and attributes.
Establishes relationships between entities using relationships.
Represents relationships in pictorial form for better understanding.

7 page
 DATA BASE MANAGEMENT SYSTEM

Example:ASchoolDatabasewithentitieslikeStudentandAddress,andtheir attributes.

RelationalModel
Organizes data in two-dimensional tables.
Maintains relationships by storing a common field.
IntroducedbyE.F.Coddin1970,it'sthemostwidelyusedmodel globally.

8 page
 DATA BASE MANAGEMENT SYSTEM

Tablesarealsoknownasrelationsinthismodel.

Object-Oriented DataModel
Combines object-oriented programming and relational data model.
Represents data and relationships in a single structure called an object.
Facilitates storage of complex data types like audio, video, images.

9 page
 DATA BASE MANAGEMENT SYSTEM

LevelsofAbstractioninaDBMS
DataabstractioninDBMSinvolveshidingunimportantdatabasedetailsfromendusersto facilitate easy and
secure data access.

Purpose
Hide irrelevant data from users and provide a focused view of relevant data.
Simplifydata access for users, improving system efficiency.

Example
Analogy:Turningonafanwithoutneedingtounderstandelectricalconnections.
Dataabstractionhidesbackgrounddetails,allowinguserstoperformtaskswithout complexities.

LevelsofDataAbstractions
1. Physical or Internal Level:
Defines how data is stored in the database.
Complex data structures are detailed at this level.
ManagedbyDataAdministrators(DBAs)whohandledatastorageandorganization
.
2. Logical or Conceptual Level:

10 page
 DATA BASE MANAGEMENT SYSTEM

Describes stored data and their relationships.

Represents data structure using tables.
Less complex than the physical level.
Helps DBAs abstract data from the physical level.
3. VieworExternalLevel:
Definesdifferentviewsoftheoveralldatabasedata.
Allows end-user interaction.
Users access data based on queries.

Advantages
Easy data access based on user queries.
Enhanced data security.
Improved database system efficiency.

DataIndependence
DataindependenceinDBMSallowsalteringtheschemaofadatabaseatonelevelwithout affecting the
schema definition at the next higher level, improving data quality and minimizing the need for
modifications in application programs.

11 page
 DATA BASE MANAGEMENT SYSTEM

TypesofDataIndependence
1. Logical Data Independence

Alterstheschemaat the conceptuallevelwithoutaffecting the externalor user view.

Changesinthelogicalstructureofthedatabasenecessitatemodificationsatthelogical level.
Examples:
Breaking existing records into multiple records.
Combining multiple records into one.
Modifying, deleting, or inserting attributes.

2. Physical Data Independence

Alterstheschemaat the internalorphysicallevel without affectingthe conceptual level.

Changesinstoragesizeorphysical structure donotaffectthe conceptual view.

12 page
 DATA BASE MANAGEMENT SYSTEM

Achievable more easily compared to logical data independence.

Examples:
Modifying indexes in the database system.
Modifying the data structure used for storage.

Data independence enhances flexibility and maintenance of database systems by allowing

changesatdifferentlevelswithoutdisrupting higher-levelschemasorapplicationprograms.

StructureofaDBMS
DBMS (Database Management System) serves as an interface between users and
databases,facilitatingvariousoperationslikeinsertion,deletion,updating,andretrievalof data. It
comprises three essential components: Query Processor, Storage Manager, and Disk Storage, each
playing a crucial role in managing databases effectively.

ComponentsofDBMSStructure

1. Query Processor
Responsible for executing user queries, the query processor translates application program-
[Link]:

DDLInterpreter:InterpretsDataDefinitionLanguage(DDL)statementsforschema definitions.
DMLCompiler:ConvertsDataManipulationLanguage(DML)statementsinto
executable code and optimizes queries.
EmbeddedDMLPre-compiler:ConvertsembeddedDMLcommandsinapplication programs
into standard procedural calls.
QueryOptimizer:Analyzes and executes query evaluation plans efficiently.

13 page
 DATA BASE MANAGEMENT SYSTEM

2. Storage Manager
Actsasabridgebetweenqueriesanddatabasedata,maintainingconsistencyand integrity. Its components
include:

Integrity Manager: Manages integrity constraints in the database.

AuthorizationManager:Verifiesuserauthenticationforspecificqueriesorrequests.
File Manager: Manages database files and data structures.
TransactionManager:Ensuresdatabaseconsistencybeforeandaftertransactions and controls
concurrent processes.
BufferManager:Transfersdatabetweenprimaryandmainmemoryandmanages cache
memory.

3. Disk Storage
[Link] include:

Data Dictionary: Stores metadata about database objects'structures.

Data Files: Stores data in files.
Indices:Enablesfastandefficientdataaccessandretrieval.

ThestructuredorganizationofDBMScomponentsensuresefficientdatamanagementand access, providing

users with seamless interaction with databases.

Characteristics ofDBMS:
1. SupportforMultipleViewsofData:
Adatabasesupportsmultipleviewsofdata,allowingdifferentusersorgroupsof users to
access subsets of the database tailored to their needs.
2. Sharing of Data and Multiuser System:
Moderndatabasesystemssupportmultipleusersaccessingthesamedatabase simultaneously,
facilitated by concurrency control strategies to maintain data integrity.
3. Control of Data Redundancy:
DBMSaimstominimizedataredundancybystoringeachdataiteminonlyone
place,althoughsomeredundancymaybeintroducedforperformancereasons, controlled by
the application programming.
4. Data Sharing:
Integrationofdatawithinadatabasesystemallowsforeasierdatasharingamong employees and
users, enabling the generation of more information from the available data.
5. Enforcement of Integrity Constraints:
DBMS must enforce integrity constraints to ensure data validity and integrity,
includingconstraintsrelatedtodatatype,uniqueness,andotherrulesdefinedby

14 page
 DATA BASE MANAGEMENT SYSTEM

the user.
6. Restriction of UnauthorizedAccess:
SecuritysubsystemsinaDBMSrestrictunauthorizedaccessbydefiningdifferent
useraccountswithvaryinglevelsofaccessprivileges,suchasread-onlyorread-write access.
7. Data Independence:
DBMSallowsfordataindependencebyseparatingdatadescriptions(metadata) from
application programs, enabling changes to the data structure without impacting the
application programs.
8. TransactionProcessing:
DBMS includes concurrency control subsystems to ensure data consistency and
validityduringtransactionprocessing,evenwhenmultipleusersareupdatingthe same
information simultaneously.
9. Backup and Recovery Facilities:
Databasesystemsprovidebackupandrecoveryfacilitiestoprotectdatafromloss due to
hardware failures or other issues, ensuring data integrity and availability even in the event
of system failures.
[Link]:
DBMSinherentlypermitsmultipleuserstoaccessitsdatabasesimultaneously, with users
being unaware of the underlying storage and organization of data.

IntroductiontoDatabaseDesignDatabase
Design and ER Diagrams Database Design
Database Design in DBMS involves a series of processes aimed at creating efficient and
[Link] to produce
logical and physical models of the proposed database system, focusing on data requirements, storage,
and organization. One common tool used in database design is the Entity-Relationship (ER)
Diagram, which visually represents the relationships between entities stored in the database. This
diagram helps to explain the logical structure of the database and is based on the concepts of entities,
attributes, and relationships.

Entity-Relationship (ER)Diagram:

15 page
 DATA BASE MANAGEMENT SYSTEM

Entities:Representedbyrectangles,entitiesaretheobjectsorconceptsaboutwhich data is stored in

the database. Examples of entities include customers, products, employees, etc.
Attributes:Representedbyellipses,attributesarethecharacteristicsorpropertiesof entities. Each
entity has a set of attributes that describe it. For example, a customer entity may have
attributes such as name, address, and phone number.
Relationships:Representedbydiamondshapes,relationshipsdefinehowentitiesare related to each
other. They indicate how data from one entity is linked to data in
[Link]-to-one,one-to-many,ormany-to-many.
Lines: Lines connecting entities and attributes represent the connections or
[Link] parts of the
database.
DoubleEllipses:Usedtorepresentmulti-valuedattributes,whichareattributesthat can have
multiple values for a single entity.
DoubleRectangles:Representweakentities,whichareentitiesthatcannotbe uniquely
identified by their attributes alone and depend on a related entity for identification.

Entities,Attributes,andEntitySets
ComponentsofanERDiagram:

16 page
 DATA BASE MANAGEMENT SYSTEM

[Link]

1. Entities:
An entity represents a real-world object or concept that can be identified and
[Link].
Example:Inauniversitydatabase,entitiescouldincludeStudent,Course, Professor,
and Department.

2. WeakEntity:
Aweakentityisanentitythatcannotbeuniquelyidentifiedbyitsattributesalone and relies on a
related entity for identification. It is represented as a double rectangle in an ER diagram.
Example:Inalibrarydatabase,aBookCopyentitymightbeweakbecauseit depends on
the Book entity for identification.

3. Attributes:
[Link] entity's
properties.
Attributes are depicted as ovals connected to their respective entity rectangles.

17 page
 DATA BASE MANAGEMENT SYSTEM

Example:AttributesofaStudententitymightincludeStudentID,Name,
DateOfBirth, etc.

4. KeyAttribute:
[Link] an ER
diagram.
Example:InaCustomerentity,theCustomerIDmightbeakeyattribute.

5. CompositeAttribute:
[Link] represented
as an oval connected to other ovals.
Example:AnAddressattributemightbecomposedofStreet,City,State,andZip Code.

6. MultivaluedAttribute:
[Link] represented
as a double oval.

18 page
 DATA BASE MANAGEMENT SYSTEM

Example:InaProductentity,theColorattributemightbemultivaluedifaproduct can come in

multiple colors.

7. DerivedAttribute:
Aderivedattributeisanattributewhosevaluecanbederivedfromotherattributes of the entity. It
is represented by a dashed oval.
Example:AgecanbeaderivedattributeifitiscalculatedbasedontheDateOfBirth
attribute.

RelationshipsandRelationshipSets
RelationshipsinanERDiagram:

1. One-to-One Relationship:

19 page
 [Link] | [Link] | [Link]

Inaone-to-onerelationship,eachrecordinthefirstentity(A)isassociatedwith exactly one

record in the second entity (B), and vice versa.
Representedbyalineconnectingthetwoentities,withthecardinalitynotation"1" on one side of
the line and "1" on the other side.
Example:AStudententitymaybeassociatedwithexactlyoneAddressentity,and vice versa.

2. One-to-Many Relationship:
Inaone-to-manyrelationship,eachrecordinthefirstentity(A)canbeassociated with many
records in the second entity (B), but each record in the second entity
(B) is associated with at most one record in the first entity (A).
Representedbyalineconnectingthetwoentities,withthecardinalitynotation"1" on one side of
the line and "N" (or "M") on the other side.
Example:ADepartmententitymayhavemanyEmployees,buteachEmployeeis associated
with only one Department.

3. Many-to-One Relationship:
In a many-to-one relationship, many records in the first entity (A) can be
associatedwithonerecordinthesecondentity(B),buteachrecordinthesecond entity (B) is
associated with at most one record in the first entity (A).
Representedbyalineconnectingthetwoentities,withthecardinalitynotation"N" (or "M") on
one side of the line and "1" on the other side.
Example:ManyOrderscanbeplacedbyoneCustomer,buteachOrderis associated
with only one Customer.

4. Many-to-Many Relationship:
Inamany-to-manyrelationship,eachrecordinthefirstentity(A)canbe associated
with many records in the second entity (B), and vice versa.
Representedbyalineconnectingthetwoentities,withthecardinalitynotation"N" (or "M") on
both sides of the line.

Database Management Systems

 [Link] | [Link] | [Link]

Example:ManyStudentscanenrollinmanyCourses,andeachCoursecanhave many Students.

AdditionalFeaturesoftheERModel
FeaturesofERModel:
1. ER Diagram:
ERdiagramsillustratethelogicalstructureofdatabasesbydepictingentities, attributes,
and relationships between them.
2. Database Design:
TheEntity-Relationshipmodelfacilitatesthedesignofdatabasesinasimpleand conceptual
manner, aiding database designers in building effective database structures.
3. Graphical Representation for Better Understanding:
ERdiagramsprovideagraphicalrepresentationthatiseasytounderstand, enabling
developers to communicate database designs effectively with stakeholders.
4. Easy to Build:
ERmodelsarestraightforwardtoconstruct,makingthemaccessiblefordatabase designers of
varying levels of expertise.
5. Extended E-R Features:
TheERmodelincludesadditionalfeaturessuchasspecialization,inheritance, aggregation,
and generalization, which enhance its expressive power and flexibility.
6. Integration:
TheERmodelcanbeseamlesslyintegratedintoacommonrelationalmodel, serving as a
valuable tool for database designers in communicating and implementing database
structures.
7. Simplicity and Versatility:
ER diagrams provide a blueprint for implementing data in specific software
applications,offeringapreviewoftableconnectionsandfields,whichcontributes to their
simplicity and versatility in various applications.

Database Management Systems

 [Link] | [Link] | [Link]

ParticipationConstraintinERDiagrams:
1. TotalParticipation:
In total participation, each entity in the entity set must participate in the
[Link] with at least
one instance of the related entity set.
RepresentedbyadoublelineconnectingtheentitytotherelationshipintheER diagram.
Example:Ifeverystudentmustbeenrolledinatleastonecourse,thenthe participation of
students in the "Enrolled in" relationship is total.
2. Partial Participation:
Inpartialparticipation,entitiesintheentitysetmayormaynotparticipateinthe relationship.
This means that some instances of the entity set may not be associated with any
instances of the related entity set.
RepresentedbyasinglelineconnectingtheentitytotherelationshipintheER diagram.
Example:Ifsomecoursesmaynothaveanystudentsenrolled,thenthe participation
of courses in the "Enrolled in" relationship is partial.

ConceptualDesignWiththeERModel
ConceptualdesignusingtheEntity-Relationship(ER)modelinvolvescreatingahigh-level representation of
the data requirements and relationships in the system.

Database Management Systems

 [Link] | [Link] | [Link]

1. IdentifyEntities:Determinemainobjectsorconceptstobestoredasentities(e.g., Student,
Course).
2. DefineAttributes:Specifypropertiesforeachentity(e.g.,StudentID,Namefor Student).
3. EstablishRelationships:Identifyconnectionsbetweenentities(e.g.,Enrollment between
Student and Course).
4. RefineCardinalityandParticipation:Determinehowmanyinstancesofoneentity relate to
another and if participation is mandatory or optional.
5. ValidatetheModel:Reviewtoensureaccuracyandalignmentwithrequirements.
6. Iterate and Refine: Make adjustments as needed based on feedback and changes.
7. DocumenttheERModel:Creatediagramsanddescriptionstocommunicatethe database
structure.

Database Management Systems

 UNIT-2
IntroductiontotheRelationalModel
Relational Model(RM) represents the database as a collection of relations. A relation is nothing
but a table of values. Every row in the table represents a collection of related data values. These
rows in the table denote a real-world entity or relationship.
The table name and column names are helpful to interpret the meaning of values in each [Link]
data are represented as a set of relations. In the relational model, data are stored as tables.
However, the physical storage of the data is independent of the way the data are logically
organized.

RelationalModelConceptsinDBMS
1. Attribute: Each column in a Table. Attributes are the properties which define a relation.
e.g., Student_Rollno, NAME,etc.
2. Tables– In the Relational model the, relations are saved in the table format. It is stored
along with its entities. A table has two properties rows and columns. Rows represent
records and columns represent attributes.
3. Tuple–Itisnothingbutasinglerowofatable,whichcontainsasinglerecord.
4. RelationSchema: Arelationschemarepresentsthenameoftherelationwithitsattributes.
5. Degree: Thetotalnumberofattributeswhichintherelationiscalledthedegreeoftherelation.
6. Cardinality:TotalnumberofrowspresentintheTable.
7. Column:Thecolumnrepresentsthesetofvaluesforaspecific attribute.
8. Relationinstance–RelationinstanceisafinitesetoftuplesintheRDBMSsystem. Relation
instances never have duplicate tuples.
9. Relationkey–Everyrowhasone,twoormultipleattributes,whichiscalledrelationkey.
 10. Attribute domain– Everyattributehassome pre-defined value and scope which isknown as
attribute domain
AdvantagesofRealationModel
 Structural Independence: Structural independence is an ability that allows us to make
changes in one database structure without affecting other. The relational model have
structuralindependence. Hence making required changes inthe database is convenient in
relational database model.
 Conceptual Simplicity: The relational model allows the designer to simply focus on
logical design and not on physical design. Hence relational models are conceptually
simple to understand.
 Query Capability: Using simple query language (such as SQL) user can get information
from the database or designer can manipulate the database structure.
 Easy design,maintenance and usage: The relational models can be designed logically
hence they are easy to maintain and use.

 KeysinDBMS
KEYS in DBMS is an attribute or set of attributes which helps you to identify a row(tuple) in a
relation(table). They allow you to find the relation between two tables. Keys help you uniquely
identify a row in a table bya combination of one or more columns in that table.

In the above-given example, employee ID is a primary key because it uniquely identifies an

employee record. In this table, no other employee can have the same employee ID.

TypesofKeysinDBMS
TherearesevendifferenttypesofKeysinDBMSandeachkeyhasit’sdifferentfunctionality:
1. Super Key
2. PrimaryKey
3. CandidateKey
4. Alternate Key
5. Foreign Key
6. CompositeKey
7. SurrogateKey
 Superkey:

• A superkey is a group of single or multiple keys which identifies rows in a table.

SuperKey is a superset of Candidate key.

• Allofthe following sets ofsuperkeyare able to uniquely identify a rowofthe employee

table.
• {Emp_SSN}
• {Emp_Number}
• {Emp_SSN,Emp_Number}
• {Emp_SSN,Emp_Name}
• {Emp_SSN,Emp_Number,Emp_Name}
• {Emp_Number,Emp_Name}

CandidateKey:

CANDIDATE KEY in SQL is a set of attributes that uniquely identify tuples in a table. Candidate
Key is a super key with no repeated attributes. The Primary key should be selected fromthe
candidate keys. Everytable must have at least a single candidate key. A table can have multiple
candidate keys but only a single primary key.

Superkeysare:
 • Thecandidatekeyswehaveselectedare:
• {Emp_Id}
• {Emp_Number}

Aprimarykey is selected fromthesetofcandidate keys. That means we caneither have Emp_Id or

Emp_Number as primary key. The decision is made by DBA.

Primary Key:

PRIMARY KEY inDBMS is a column or group of columns in a table that uniquely identify
every row in that table. The Primary Key can’t be a duplicate meaning the same value can’t
appear more than once in the table. A table cannot have more than one primarykey.

Inthefollowingexample,StudIDisaprimarykey.

Foreignkey:

FOREIGN KEY is a column that creates a relationship between two tables. The purpose of
Foreign keys is to maintain data integrity and allow navigation between two different instancesof
an entity. It acts as a cross-reference between two tables as it references the primary key of
another table.

CompositeKey:
Sometimes, a table might not have a single column/attribute that uniquely identifies all the
[Link],acombinationoftwoormore
columns/[Link],weneedtofindthe
optimal setof attributes thatcanuniquelyidentify rows ina table.
 Itactsasaprimarykeyifthereisnoprimarykeyinatable
 Twoormoreattributesareusedtogethertomakeacompositekey.
 Differentcombinationsofattributesmaygivedifferentaccuracyintermsofidentifying the rows
uniquely.

AlternateKey:

Thecandidatekeyotherthantheprimarykeyiscalledanalternatekey.
 Allthekeyswhicharenotprimarykeysarecalledalternatekeys.
 Itisasecondarykey.
 Itcontainstwoormorefieldstoidentifytwoormorerecords.
 Thesevaluesarerepeated.

Surrogatekey:

SURROGATE KEYS is Anartificialkeywhichaims to uniquely identifyeachrecord is called a

surrogate key. This kind of partial key in dbms is unique because it is created when you don’t
have any natural primary key.

 IntegrityConstraintsinDBMS
Indatabase management systems(DBMS) there is a certain set of rules which are used tomaintain
the quality and consistency of data in the database. Every time there is an
insertion,deletion,orupdatingofdatainthedatabaseitistheresponsibilityofthese integrityconstraintsto
maintain the integrity of data and thus help to prevent accidental damage to thedatabase.
Therearefourtypesofintegrityconstraintsin DBMS:
DomainConstraint
EntityConstraint
ReferentialIntegrityConstraint
KeyConstraint

[Link]
1. Every domain must contain atomic values(smallest indivisible units) which meanscomposite
and multi-valued attributes are not allowed.
2. Weperform a datatypecheckhere,whichmeanswhen we assign adata type to a column we
limitthe values thatitcan contain. Eg. If we assign the datatype of attribute age as int, we
can’t give it values other than int datatype.
Example:
EID Name Phone

123456789
01 BikashDutta
234456678

Explanation: In theaboverelation,NameisacompositeattributeandPhoneisamulti-values attribute,

so it is violating domain constraint.
 [Link]

EntityIntegrityConstraintisused to ensure that the primarykeycannot be null. Aprimarykey is

used to identify individual records in a table andif the primary key has a null value,then we
can't identify those records. There can be null values anywhere in the table except the primary
key column.

Example:
EID Name Phone

01 Bikash 9000900099

02 Paul 600000009

NULL Sony 9234567892

Explanation: Intheaboverelation,EIDismadetheprimarykey,andtheprimarykeycan’t take NULL

valuesbutin the third tuple, the primary key isnull,soitisviolatingEntity Integrity constraints.

[Link]
ensures that there must always exist a valid relationship between two relational database tables. This valid relatio

In the Referential integrity constraints,ifaforeign key in Table 1 refers to the Primary Key
ofTable 2, then every value ofthe Foreign Key in Table 1 must be null or be available in Table 2.
NOT NULL:
4. Key constraints:
NOT NULL constraint makes sure that a column does not hold NULL value. When we don’t
Keysare the set ofentities that are used to identifyanentitywithin its entityset uniquely. There
provide value for a particular column while inserting a record into a table, it takes NULL value
could be multiple keys in a single entityset, but out of these multiple keys, onlyonekeywill be
by default. By specifying NULL constraint, we can be sure that a particular column(s) cannot
the primary key. A primary key can only contain unique and not null values in the relational
have NULL values.
database table.

Example:
CREATETABLESTUDENT(
ID INT NOT NULL,
NAMEVARCHAR(35)NOTNULL,
AGE INT NOT NULL,
PRIMARYKEY(ID)
);
UNIQUE:

[Link] a unique
constraint, it means that particular column cannot have duplicate values in a table.

CHECK:

This constraint is used for specifying range of values for a particular column of a table.
Whenthisconstraintisbeingsetonacolumn, itensuresthatthespecifiedcolumn must have the value
falling in the specified range.
DEFAULT:
TheDEFAULTconstraintprovidesadefaultvaluetoacolumnwhenthereisnovalue provided while
inserting a record into a table.

PRIMARYKEY:
Primary keyuniquely identifies each record in a table. It must have unique values and cannot
contain nulls. The primary key has automatically UNIQUE and NOT NULL constraints
appliedto it. It is usually used to index the table or uniquely identify each tuple in the table.
Wecansaythat:
PRIMARYKEYCONSTRAINT=UNIQUECONSTRAINT+NOTNULLCONSTRAINT
 FOREIGNKEYConstraint:
Foreign keys are the columns of a table that points to the primary key of another table. They act
as a cross-reference between [Link] prevents operations that
candestroy the link between the [Link] used in situations where we donotwantthe
deletion of data from one table to hamper the data in the other table.
Oneimportantthingtonotehereisthat- theForeignKey of
onetablepointstoorreferencesthePrimaryKeyof the second table. So, when we delete data from
the main table that points todata in the other table, we will be shown the error - Record in child
table exists.
QueryingRelationalDatainDBMS
Arelationaldatabasequeryisaquestionaboutthedata,andtheanswerconsistsofanewrelation
containing the result. For example, we might want to find all students AGE less than 18 or all
students enrolled in perticular course.
TheSELECTstatement is used to fetch the data froma database table which returns this data in
the form of a result table. These result tables are called result-sets.
Ifyouwanttoselectallthefieldsavailableinthetable,usethefollowing syntax:
Syntax:
SELECT *FROMtable_name;
Thesymbol´*´meansthatweretainallfieldsofselectedtuplesintheresult.

We canretrieverowscorresponding to studentswho are younger than18 withthe following SQL

query:
The conditionage< 18 in the WHERE clause specifies that we want to select only tuples in which
SELECT*
the age field FROMStudentsWHEREage<18;
has a value less than 18.

In addition to selecting a subset of tuples, a query can extract a subset of the fields of each
selected tuple. we can compute the student_id and First_name of students who are younger than
18 with the following query:

SELECTID,FirstNameFROMStudentsWHEREage<18;
SQL Aliases

[Link] the AS keyword.

AliasColumnSyntax:

SELECTcolumn_nameASalias_nameFROMtable_name;
AliasTable Syntax:

Example:
SELECTcolumn_name(s)FROMtable_nameASalias_name;

SELECTstudentIDASID,FROMstudentsASS;
Aliasescanbeusefulwhen:

 Therearemorethanonetableinvolvedina query
 Functionsareusedinthequery
 Columnnamesarebigornotveryreadable
 Twoormorecolumnsarecombinedtogeth

SELECTdatafromMultipleTables:
Wecanalsocombineinformationfrommultipletables.
Syntax:

Example:
SELECTtable1.column1,table2.column2
FROM table1, table2
WHEREtable1.column1=table2.column1;
[Link],[Link]
FROM StudentsASS,Enrolled AS E
WHERE [Link]=[Link];
ViewsinDBMS:
• Writing Complex queries and Securing Database access is very challenging for any
Database Developer and Database Administrator.
• Sometimes SQL queries get very complicated by joins, Group By clauses, and other
referential dependencies, So those Types of queries can be simplified to proxy data or
virtual data which simplifies the queries.
• Suppose, the user needs only2 columns of data, so instead of giving him access to the
whole table in the database, the Database Administrator can easily create a virtual tableof
2 columns that the user needs using the views.
• This will not givefull access to the table and the useris only seeing the projection of only
2 columns and it keeps the database secure.
• View isavirtualtablethatcontainsrowsandcolumns,justlikearealtable.
• Itis usedtohidecomplexityofqueryfromuser.
• Avirtualtabledoes not exist physically, it iscreatedbyaSQLstatementthatjoinsoneor more
tables.
• Views in DBMS can be visualized as virtual tables that are formed by original tablesfrom
the database.
CreatingViews:
• Database views are created using the CREATE VIEWstatement. Views can be created
from a single table, multiple tables or another view.
• To create a view, a user must have the appropriate system privilege according to the
specific implementation.
Syntax:
• CREATE VIEW view_name AS SELECT column1, column2..... FROM table_name
WHERE [condition];

CreatingViewfrommultipletables:
• ViewfrommultipletablescanbecreatedbysimplyincludemultipletablesintheSELECTstatem
ent.
Syntax:
• CREATEVIEWMarksViewASSELECTStudent_Detail.NAME,Student_Detail.ADDRES
S,St udent_Marks.MARKSFROMStudent_Detail, Student_MarkWHERE
Student_Detail.NA ME = Student_Marks.NAME;
DeletingView
AviewcanbedeletedusingtheDropViewstatement.
Syntax
DROPVIEWview_name;
Example:
IfwewanttodeletetheViewMarksView,wecandothisas:
DROPVIEWMarksView;

InsertingaRowinaView:
• Insertingarowintheviewtakesthesamesyntaxasweusetoinsertarowinasimpletable.

Syntax:
• INSERTINTOViewName(column1, column2,..)VALUES(value1, value2,..);

DeletingaRowinaView:
• Deletingarowintheviewtakesthesamesyntaxasweusetodeletearowinasimpletable.
Syntax:

• DELETEFROMViewNameWHEREcondition;
UPDATINGVIEWS:
There are certain conditions needed to be satisfied to update a view. If any one of
theseconditionsisnotmet, then we will notbe allowed to update the view.
1. The SELECT statement which is used to create the viewshould not include GROUP BY
clause or ORDER BY clause.
2. TheSELECTstatementshouldnothavetheDISTINCTkeyword.
3. TheViewshouldhaveallNOTNULLvalues.
4. Theviewshouldnotbecreatedusingnestedqueriesorcomplexqueries.
5. The view should be created from a single table. If the view is created using multiple
tablesthen we will not be allowed to update the view.

We can use the CREATE OR REPLACE VIEW statement to add or remove fields from a view.

Syntax:

CREATE OR REPLACE VIEW view_name AS SELECT column1,column2,.. FROM table_name

WHERE condition;

For example, if we want to update the viewMarksViewand add the field AGE to this View from
StudentMarksTable, we can do this as:

CREATE OR REPLACE VIEW MarksView AS SELECT [Link],

[Link], [Link], [Link] FROM StudentDetails,
StudentMarks WHERE [Link] = [Link];

WITHCHECKOPTION:

The WITH CHECK OPTION clause in SQL is a very useful clause for views. It is applicable to
an updatable view. If the view is not updatable, then there is no meaning of including this
clause in the CREATE VIEW statement.
 The WITH CHECK OPTION clause is used to prevent the insertion of rows in the view
where the condition in the WHERE clause in CREATE VIEW statement is not satisfied.
 If we have used the WITH CHECK OPTION clause in the CREATE VIEW statement, and
if the UPDATE or INSERT clause does not satisfy the conditions then they will return an
error.

Example: In the below example we are creating a View SampleView from StudentDetails Table
with WITH CHECK OPTION clause.

CREATE VIEW SampleView AS SELECT S_ID, NAME FROMStudentDetails WHERE NAME IS NOT NULL
WITH CHECK OPTION;
In this View if we now tryto insert a new row with null value in the NAME column then it
will give an error because the view is created withthe condition for NAME column as NOT
NULL.

RelationalAlgebrainDBMS
• Relational algebra refers to a procedural query language that takes relation instances
asinput and returns relation instances as output.
• Queriesin relational algebra are performed using operators. A binary orunary operator can
be used.
• Aprogrammer/user hastomentiontwothings,"WhattoDo"and "HowtoDo".
• Relationalalgebraisfollowsaparticularsyntaxwiththehelpofwhich,datacanbe accessed and
retrieved very easily from single as well as multiple table/data sources.

Select(σ):

• SelectoperationisdonebySelectionOperatorwhichisrepresentedby"sigma"(σ).

• Itisusedtoretrievetuples(rows)fromthetablewherethegivenconditionissatisfied.
• Itisaunaryoperatormeansitrequiresonlyone operand.
• WhereσisusedtorepresentSELECTION,RisusedtorepresentRELATION

Example:
QueryUsed:
σNameandAge>21(Student_Details)

Ex 2:

Query:

σCustomer_City="Agra"(CUSTOMER)

Project(∏):

• ProjectoperationisdonebyProjectionOperatorwhichisrepresentedby"pi"(∏).
• Usingprojectoperationonecansimplyfetchallthetuplescorrespondingtoasingle attribute or
multiple attributes.
 • [Link] a unary
operator.

Example:

QueryUsed:
πMarks(Student_Details)

Example2:

Query:
∏Customer_Name,Customer_City(CUSTOMER)

Output
Union(∪):
Unionoperationisdone by UnionOperatorwhichisrepresentedby"union"(∪).
It is the same as the union operator from set theory, i.e., it selects all tuples from both relations
but with the exception that for the union of two relations/tables both relations must have thesame
set of Attributes.
• Itisabinaryoperatorasitrequirestwooperands.
• Also,twothingsneedtokeepinmindwhileapplyingunionoperationare:
 Boththerelationscompulsorytohavesamenumberofattributes.
 Boththerelationscompulsorytohavesamedomainforattributes.
Consider the two tables with relations X1(Name, Age) and X2(Name, Age).
• Ifwewishtoapplytheunionoperation,thenitcanbedoneby

SetDifference(-):
SetDifferenceasitsnameindicatesisthedifferencebetweentworelations(R-S).
It is denoted by a "Hyphen"(-) and it returns all the tuples(rows) which are in relation R but
notin relation S. It is also a binary operator.

Example:
Query:

∏Student_Name(STUDENT)-∏Student_Name(COURSE)

Cartesianproduct(X):
Cartesian product is denoted by the "X" symbol. Let's say we have two relations R and S.
Cartesianproductwillcombineeverytuples(row) fromRwithallthe tuples fromS. It combines the
information of two or more relations in one single relation.
Notation:RXS
WhereRisthefirstrelation,Sisthesecond relation

Example:

Query:

LetsfindthecartesianproductoftableRandS. R X

S
IntersectionOperator(∩):
Intersectionoperatorisdenotedby∩symbolanditisusedto select commonrows(tuples) from two
tables (relations).
SyntaxofIntersectionOperator(∩)
table_name1∩table_name2

Query:

∏Student_Name(COURSE)∩∏Student_Name(STUDENT)
JOINSinDBMS
Databases usually have more than one table. JOINsare an SQL construction used to join data
from two or more tables. When you want to use columns from two tables in a result table, the
easiest way to do it is to write a JOINquery. JOINKeyword is used in SQL queries for joining
two or more tables.

ThesyntaxofanSQLJOINis:
TypesofJOIN
SELECT*FROMtable1JOINtable2ON table1.id1=table2.id2
FollowingarethetypesofJOINthatwecanuseinSQL:
 InnerJoin
 Outer Join
o LeftouterJoin
o Right OuterJoin
o FullOuterJoin

InnerJoin:
This is a simple JOIN in which the result is based on matched data as per the equality condition
specified in the SQL query.
Inner JoinSyntaxis,

SELECTcolumn-name-listFROMtable-name1INNERJOINtable-name2WHEREtable-
Example;
[Link]-name = [Link]-name;

InnerJOINquerywillbe,

SELECT*fromclassINNERJOINclass_infowhereclass.id=class_info.id;
NaturalJOIN

NaturalJoinisatypeofInnerjoinwhichisbasedoncolumnhavingsamenameandsame datatype present

in both the tables to be joined.
ThesyntaxforNaturalJoinis,

SELECT*FROMtable-name 1 NATURALJOINtable-name 2;

Example:

Naturaljoinquerywillbe,

SELECT * from class NATURAL JOIN class_info;

Output:

OUTERJOIN
[Link],
1. LeftOuterJoin
 2. RightOuterJoin
3. FullOuterJoin
LEFTOuterJoin
The left outerjoinreturnsaresultsettablewiththematcheddatafromthetwotablesandthen the remaining
rows of the left table and null from the right table's columns.
Syntax:

[Link]-name=
Table: song Table: Artist
[Link]-name;

Query:
SELECT*FROMsongLEFTJOINartistONsong.artist_id=artist.artist_id

RIGHTOuterJoin

The right outer join returns a resultset table with the matched data fromthe two tables being
joined,thentheremainingrowsoftherighttableandnullfortheremaininglefttable'scolumns. Syntax
for Right Outer Join is,

[Link]-name=
[Link]-name;
Query:
SELECT*FROMsongRIGHTJOINartistONsong.artist_id=artist.artist_idOutput:

FullOuterJoin

The fullouterjoinreturnsaresultsettablewiththematcheddataoftwotablethenremaining rows of

both left table and then the right table.

Syntax:

[Link]-name=
[Link]-name;
Query:
SELECT*FROMsongFULLJOINartistONsong.artist_id=artist.artist_idOutput:

RelationalCalculus
Procedural Language - Those Languages which clearly define how to get the required
resultsfrom the Database are called Procedural Language.
RelationalalgebraisaProceduralLanguage.
Declarative Language- Those Language that only cares aboutWhattogetfrom the database
without getting into how to get the results are called Declarative Language.
RelationalCalculusisaDeclarativeLanguage.
Relationalcalculusisanon-proceduralquerylanguage,andinsteadofalgebra,ituses mathematical predicate
calculus.
Relational Calculus in database management system (DBMS) is all about "What you want ?".
RelationalcalculusdoesnottellushowtogettheresultsfromtheDatabase,butitjustcares about what we
want.
Therelationalcalculustellswhattodobutneverexplainshowtodo.
RelationalCalculusisofTwoTypes:
• TupleRelationalCalculus(TRC)
• DomainRelationalCalculus(DRC)
TupleRelationalCalculus (TRC):
• Tuple Relational Calculus (TRC) is a non-proceduralquery language used in relational
database management systems (RDBMS) to retrieve data from tables.
• TRCisadeclarativelanguage,meaningthatitspecifieswhatdataisrequiredfrom the database,
rather than how to retrieve it.
• Tuple Relational Calculus in DBMS uses a tuple variable (t) that goes to each row of the
table and checks if the predicate is true or false for the given row.
• Dependingonthegivenpredicatecondition,itreturnstheroworpartoftherow.

• Table:Student

First_Name Last_Name Age

Ajeet Singh 30
Chaitanya Singh 31
Rajeev Bhatia 27
Carl Pratap 28
• Querytodisplaythelastnameofthosestudentswhereageisgreaterthan30

• Inthe above queryyoucansee two partsseparated by| symbol. The second part iswhere we
• define
{t.Last_Name|Student(t)[Link]> 30} we specify the fields which we want to display
the condition and in the first part
for the selected tuples.
• Theresultoftheabovequerywouldbe:

Last_Name

Singh
• QuerytodisplayallthedetailsofstudentswhereLastnameis‘Singh’

Output:
• {t|Student(t) ANDt.Last_Name='Singh'}

First_Name Last_Name Age

 Ajeet Singh 30
Chaitanya Singh 31

2. DomainRelationalCalculus(DRC)
• [Link] take
the same table to understand how DRC works.
Table:Student

First_Name Last_Name Age

Ajeet Singh 30
Chaitanya Singh 31
Rajeev Bhatia 27
Carl Pratap 28
• Querytofindthefirstnameandageofstudentswherestudentageisgreaterthan 27

{<First_Name,Age>| ∈Student ∧Age>27}

Note:
Thesymbolsusedforlogicaloperatorsare:∧forAND,∨forORand┓for NOT.
• Output:

First_NameAge

Ajeet Chaitanya30
Carl
31
28
 UNIT– III
SQL:QUERIES,CONSTRAINTS,TRIGGERS:formofbasicSQLquery,UNION,INTERSECT,
and EXCEPT, Nested Queries, aggregation operators, NULL values, complex integrity constraints in
SQL, triggers and active databases. Schema Refinement: Problems caused by redundancy,
decompositions, problems related to decomposition, reasoning about functional dependencies, FIRST,
SECOND, THIRD normal forms, BCNF, lossless join decomposition, multi-valued dependencies,
FOURTH normal form, FIFTH normal form.

1. SQLCOMMANDS
Structured Query Language (SQL) is the database language used to create a database and
to perform operations on the existing database. SQL commands are instructions used to
communicate with the database to perform specific tasks and queries with data. These SQL
commands are categorized into five categories as:

i. DDL:DataDefinitionLanguage
ii. DML:DataManipulationLanguage
iii. DQL:DataQueryLanguage
iv. DCL: Data ControlLanguage
v. TCL: Transaction ControlLanguage.

SQLcommands

DDL DML DQL DCL TCL

DataManipulationLanguageDataQueryLanguage DataControlLanguage
DataDefinitionLanguage Transaction ControlLanguage

CREATE INSERT GRANT COMMIT

SELECT

ALTER DELETE REVOKE ROLLBACK

DROP SAVEPOINT
UPDATE

TRUNCATE

i. DDL(Data Definition Language) :DDL or Data Definition Language consists of the

SQL commands that can be used to define the database schema. It simply deals with
descriptions of the database schema and is used to create and modify the structure ofdatabase
objects in the database. The DQL commands are:
  CREATE:Itisusedtocreatethedatabaseoritsobjects(liketable,index,function, views,
store procedure and triggers).
 DROP: Itisusedtodeleteobjectsfromthe database.
 ALTER:Itisusedtoalterthestructureofthedatabase.
 TRUNCATE:Itisusedtoremoveallrecordsfromatable,includingallspaces
allocated for the records are removed.
ii. DQL (Data Query Language):DML statements are used for performing queries on the
data within schema objects. The purpose of DQL Command is to get data from some schema
relation based on the query passed to [Link] DQL commands are:
 SELECT–is usedtoretrievedatafromthedatabase.

iii. DML (Data Manipulation Language):The SQL commands that deals with the
manipulation of data present in the database belong to DML or Data Manipulation Language
and this includes most of the SQL statements. The DML commands are:

 INSERT–is usedtoinsertdataintoatable.
 UPDATE– isusedtoupdateexistingdatawithin a table.
 DELETE–is usedtodeleterecordsfromadatabasetable.
iv. DCL(DataControlLanguage):DCLincludescommandswhichmainlydealwiththe rights,
permissions and other controls of the database system. The DCL commands are:
 GRANT-givesuser’saccessprivilegesto database.
 REVOKE-withdrawuser’saccessprivilegesgivenbyusingtheGRANTcommand.
v. TCL(transactionControlLanguage):TCLcommandsdealswiththetransactionwithin the
database. The TCL commands are:
 COMMIT–commitsaTransaction.
 ROLLBACK–rollbacksatransactionincaseofanyerroroccurs.
 SAVEPOINT–setsasavepointwithinatransaction.

2. DDLCOMMANDS
DDLor Data Definition Language consists of theSQLcommands that can be used to define the
database schema. It simplydeals with descriptions of the database schema and is used to
createandmodifythestructureofdatabaseobjects in [Link]:
i. CREATE:Itisusedtocreatethedatabaseoritsobjectsliketable,index,function,views, store
procedure and triggers.

a) The‘CREATEDATABASE’Statement: Thisstatementisusedtocreate a database.

Syntax:CREATEDATABASEDatabase_Name;
Example: CREATEDATABASEEmployee;

ItcreatesEmployeedatabase.

b) The‘CREATETABLE’Statement:Thisstatementisusedtocreateatable.
Syntax:
CREATETABLETableName(
Column1datatype(size)[column_constraint],
Column2datatype(size)[column_constraint],
....
ColumnNdatatype(size)[column_constraint],
[table_constraint]
[,table_constraint]
);
Note:[Link],youcanskipit.

Columnconstraints

o PRIMARYKEY //Useonly,Ifonecolumnnameasprimarykey.
o NOTNULL //ItdoesnotacceptNULLvalueinthatcolumn.
o DEFAULTvalue //Itstoredefaultvalueinthatcolumn,ifnovalueisinserted
o UNIQUE //Itallowstostoreonlyuniquevaluesinthecolumn

Tableconstraints

o PRIMARYKEY(column_name1,column_name2,…)
Useit,Ifonecolumnnameormultiplecolumnnamesactsasprimarykey.
o UNIQUE(column_name1,column_name2,…)
Useit,ifonecolumnnameormultiplecolumnnamesshouldcontainuniquevalues.
Ifmultiplecolumnnamesareused, thenforeachrow,itconsidervaluesfromallthecolumns mentioned to
decide the uniqueness, but not column wise.
o FOREIGNKEY(column_name1)REFERENCESother_table_name(column_name2) It
is used to link data from one table to other table.
o CHECK(condition)
It does not allow inserting value(s), if the condition is not satisfied. The condition may
alsocontain multiple column names.
Example1:Creatingtablewithoutanyconstraints
CREATETABLEEmployee_Info(
EmployeeID int,
EmployeeNamevarchar(20),
PhoneNumber numeric(10), City
varchar(20),
Countryvarchar(20)
);
Example2:UsingPRIMARYKEYandNOTNULLascolumnconstraints
CREATETABLEDepartments(
DeptID int PRIMARY KEY,
DeptNamevarchar(20)NOTNULL, Hod
varchar(20),
Locationvarchar(20)
);
Example 3: Using PRIMARY KEY, NOT NULL, UNIQUE and DEFAULT as column constraints and FOREIGN
KEY as table constraint.
CREATETABLEStudents_Info(
HallTicketNointPRIMARYKEY, Name
varchar(20)NOT NULL,
Mobilenumeric(10)NOTNULLUNIQUE,
DepartmentID int,
Cityvarchar(20)DEFAULT‘Hyderabad’,
FOREIGNKEY(DepartmentID)REFERENCESDepartments(DeptID)
);

Example4:UsingNOTNULL,UNIQUEascolumnconstraintsandPRIMARYKEYandCHECKastable constraints.
CREATETABLEVoter_list(
VoterIDnumeric(10),
AdhaarNonumeric(12)NOTNULLUNIQUE, Name
varchar(20)NOT NULL,
Age int,
Mobilenumeric(10)UNIQUE, City
varchar(20),
PRIMARYKEY(VoterID),
CHECK(AGE>18)
);

c) The‘CREATETABLEAS’Statement:Youcanalsocreateatablefromanother existing
table. The newly created table also contains data of existing table.
Syntax:
CREATETABLENewTableNameAS(SELECTColumn1,column2,...,ColumnNFR
OMExistingTableName
WHERE[condition]);
Example:CREATETABLEExampleTableAS(SELECTEmployeeName,PhoneNumber
FROMEmployee_Info);
 ii. DROP:Thisstatementisusedtodropanexistingtableora database.
a) The ‘DROP DATABASE’ Statement: This statement is used to drop an existing
database. When you use this statement, complete information present in the database will
be lost.
Syntax: DROPDATABASEDatabaseName;

Example: DROPDATABASEEmployee;

b) The‘DROPTABLE’Statement:[Link] you use

this statement, complete information present in the table will be lost.
Syntax: DROPTABLETableName;

Example: DROPTABLEEmployee;

iii. TRUNCATE: This command is used to delete the information present in the table but
does not delete the table. So, once you use this command, your information will be lost, but
not the table.
Syntax: TRUNCATETABLETableName;
Example: TRUNCATETABLEEmployee_Info;

iv. ALTER: This command is used to add, delete or modifycolumn(s) in an existing table. It
can also be used to rename the existing table and also to rename the existing column name.
a) The‘ALTERTABLE’withADDcolumn:Youcanusethiscommandtoaddanew column to
the existing table.
Syntax: ALTER TABLE TableNameADDColumnNameDatatype;

Example:AddingBloodGroupcolumntotheEmployee_Infotable
ALTER TABLE Employee_Info
ADDBloodGroupvarchar(10);
b) The ‘ALTER TABLE’ withDROP column: You can use this command to remove
acolumn from the existing table.
Syntax: ALTERTABLETableName DROP ColumnName;

Example:RemovingBloodGroupcolumnfromtheEmployee_Infotable
ALTERTABLEEmployee_Info DROP
BloodGroup;
 c) The ‘ALTER TABLE’ withMODIFY COLUMN: Thisstatementisusedtochange the
data type or size of data type of an existing column in a table.

Syntax: ALTERTABLETableName
MODIFYCOLUMNColumnNameDatatype;

Example 1: Changing the size of column ‘EmployeeName’ in table ‘Employee_info’ from

20 to 30.

ALTERTABLEEmployee_InfoMODIFYEmpl
oyeeNamevarchar(30);

Example 2: Changing the data type of column ‘EmployeeID’ in the table ‘Employee_info’
from int to char(10).

ALTER TABLE Employee_Info

MODIFYEmployeeIDchar(10);

d) The‘ALTERTABLE’withCHANGEcolumnname:Thisstatementisusedtochange the
column name of an existing column in a table.

Syntax: ALTERTABLETableName
CHANGECOLUMNOldColumnNameNewColumnName;

Example1:Changingthecolumnname‘EmployeeName’to‘EmpName’intable ‘Employee_info’.

ALTERTABLEEmployee_Info
CHANGECOLUMNEmployeeNameEmpName;

e) The ‘ALTER TABLE’ with RENAME table name: This statement is used to change
the table name in the database.

Syntax: ALTERTABLEOldTableNameRENAMETONewTableName;

Example:Changingthetablenamefrom‘Employee_Info’to ‘Employee_Data’.

ALTERTABLEEmployee_InfoRENAMETO
Employee_Data;

3. DML COMMANDS: The SQL commands that deals with the manipulation of data
present in the database belong to DML or Data Manipulation Language and this includes
most of the SQL statements. The DML commands are:
i. INSERT:Thisstatementisusedtoinsertnewrecord(row)intothetable.
 Syntax: INSERTINTOTableName[(Column1,Column2,...,ColumnN)] VALUES (value1, value2,...,

Example1:
INSERTINTOEmployee_Info(EmployeeID,EmployeeName,PhoneNumber,City,Country) VALUES ('06', 'Sanjana',
'9921321141', 'Chennai', 'India');

Example2:Wheninsertingallcolumnvaluesaspertheirorderinthetable, youcanomit column

names.
INSERTINTOEmployee_Info
VALUES('07','Sayantini','9934567654','Pune','India');

ii. DELETE:Thisstatementisusedtodeletetheexistingrecordsinatable.

Syntax:DELETEFROMTableName
Example: WHERE Condition;
DELETE FROM Employee_Info
WHEREEmployeeName='Preeti';

Note: If whereconditionisnotusedinDELETEcommand,[Link] only rows

which satisfies the condition are deleted.

iii. UPDATE:Thisstatementisusedtomodifytherecordvaluesalreadypresentinthetable.

Syntax: UPDATETableName
SETColumn1=Value1,Column2=Value2,... [WHERE Condition];

Example:

UPDATEEmployee_Info
SETEmployeeName='Jhon',City='Ahmedabad' WHERE EmployeeID =
1;

Note:If where condition is not used in UPDATE command, then in all the rows Employee Name changes to
'Jhon' and City name changes to 'Ahmedabad'.Ifusedonly rows which satisfies the condition are
updated.

4. DQLCOMMAND:ThepurposeofDQLCommandistogetdatafromoneormore tables
based on the query passed to it.
i. SELECT: This statement is used to select data from a database and the data returned
isstored in a result table, called the result-set.
 Syntax: SELECT[DISTINCT]*/Column1,Column2,...ColumN FROM TableName
[WHEREsearch_condition] [GROUP BY column_names
[HAVINGsearch_condition_for_GROUP_BY] [ORDER BY column_name ASC/DESC] ;

Example1:SELECT*FROMtable_name;

Example2:
SELECTEmployeeID,EmployeeName FROM
Employee_Info;

The ‘SELECT with DISTINCT’ Statement: This statement is used to display only
different unique values. It mean it will not display duplicate values.

Example:SELECTDISTINCTPhoneNumberFROMEmployee_Info;

The ‘ORDER BY’ Statement: The ‘ORDER BY’ statement is used to sort the required
results in ascending or descending order. The results are sorted in ascending order by
default. Yet, if you wish to get the required results in descending order, you have to use
the DESC keyword.

Example

/*Selectallemployeesfromthe'Employee_Info'tablesortedby City*/

SELECT*FROMEmployee_Info ORDER
BY City;

/*Selectallemployeesfromthe'Employee_Info'tablesortedby City in Descending order */

SELECT*FROMEmployee_Info ORDER
BY City DESC;

/*Selectallemployeesfromthe'Employee_Info'tablesortedby City and EmployeeName. First it

sort the rows as per city, then sort by employee name */

SELECT * FROM Employee_Info

ORDERBYCity,EmployeeName;

/*Selectallemployeesfromthe'Employee_Info'tablesortedby
CityinDescendingorderandEmployeeNameinAscendingorder:*/

SELECT*FROMEmployee_Info
ORDERBYCityASC,EmployeeNameDESC;
AGGREGATEFUNCTIONS:
The SQL allows summarizing data through a set of functions called aggregate
functions. The commonly used aggregate functions are: MIN(), MAX(), COUNT(),
SUM(),AVG().

MIN() Function: The MIN function returns the smallest value of the selected column in
a table.

Syntax:SELECTMIN(ColumnName)
FROM
TableNameWHERECondi
tion;

Example: SELECTMIN(EmployeeID)
FROM Employee_Info;

MAX( ) Function:TheMAXfunction returns thelargestvalueoftheselectedcolumn in a

table.

Syntax:SELECTMAX(ColumnName)
FROM
TableNameWHERECondi
tion;
Example:
SELECTMAX(Salary)ASLargestFees FROM
Employee_Salary;

COUNT()Function:TheCOUNTfunctionreturnsthenumberofrowswhichmatchthe specified
criteria.

Syntax: SELECTCOUNT(ColumnName)
FROM TableName
WHERECondition;
Example:
SELECTCOUNT(EmployeeID) FROM
Employee_Info;

SUM() Function:TheSUMfunctionreturnsthetotalsumofanumericcolumnthat you choose.

Syntax: SELECTSUM(ColumnName)
FROM
TableNameWHERECondit
ion;
Example:
SELECTSUM(Salary)
FROMEmployee_Salary;
 AVG() Function:TheAVGfunctionreturnstheaveragevalueofanumericcolumnthat you
choose.

Syntax: SELECTAVG(ColumnName)
FROM TableName
WHERECondition;
Example:
SELECTAVG(Salary)
FROMEmployee_Salary;

The‘GROUPBY’Statement:This‘GROUPBY’statementisusedwiththeaggregatefunctions to
group the result-set by one or more columns.

Example:

--Tolistthenumberofemployeesfromeachcity.

SELECTCOUNT(EmployeeID),City FROM
Employee_Info
GROUPBYCity;

The‘HAVING’Clause:The‘HAVING’clausemustbeusedSQLalongwithGROUPBY clause only.

It is similar to the WHERE clause.

Example

/*&nbsp;&nbsp;To list the number of employees in each city. The employees

shouldbesortedhightolowandonlythosecitiesmustbeincludedwhohave more than 5 employees:*/

SELECTCOUNT(EmployeeID),City FROM
Employee_Info
GROUPBY City
HAVINGCOUNT(EmployeeID)>2;

OperatorsinSQL:

ThedifferentsetofoperatorsavailableinSQLare as follows:

 Arithmetic operators
 Bitwiseoperators
 Comparison operator
 Compound operator
 Logicaloperator

Letus look intoeachoneofthem, one byone.

ArithmeticOperators:
Operator Description
% Modulus [A %B]
/ Division [A /B]
* Multiplication[A * B]
– Subtraction[A– B]
+ Addition [A +B]

BitwiseOperators:
Operator Description
^ BitwiseExclusiveOR(XOR) [A^ B]
| BitwiseOR [A|B]
& BitwiseAND[A &B]

ComparisonOperators:
Operator Description
<> NotEqual to [A <>B]
<= Lessthan or equalto [A<= B]
>= Greaterthanorequalto[A>= B]
< Lessthan [A<B]
> Greaterthan[A>B]
= Equalto [A =B]

CompoundOperators:
Operator Description
|*= BitwiseORequals [A |*=B]
^-= BitwiseExclusiveequals [A^-=B]
&= BitwiseAND equals[A&= B]
%= Moduloequals [A%=B]
/= Divideequals [A /=B]
*= Multiplyequals[A*= B]
-= Subtractequals[A-= B]
+= Addequals[A+= B]

LogicalOperators:TheLogicaloperatorspresentinSQLareasfollows:AND,OR,NOT, BETWEEN, LIKE, IN,

EXISTS, ALL, ANY.
AND Operator: This operator is used to filter records that rely on more than one condition. This
operator displays the records, which satisfy all the conditions separated by AND, and give the
output TRUE.
Syntax:

SELECTColumn1,Column2,...,ColumnN FROM
TableName
WHERECondition1ANDCondition2ANDCondition3...;

Example:

SELECT*FROMEmployee_Info
WHERECity='Mumbai'ANDCity='Hyderabad';</pre>

OR Operator: This operator displays all those records which satisfy any of the conditions
separated by OR and give the output TRUE.

Syntax:SELECTColumn1,Column2,...,ColumnNFROM TableName
WHERECondition1ORCondition2ORCondition3...;

Example:

SELECT*FROMEmployee_Info
WHERECity='Mumbai'ORCity='Hyderabad';

NOT Operator: The NOT operator is used, when you want to display the records which do not
satisfy a condition.

Syntax: SELECTColumn1,Column2,...,ColumnN FROM

TableName
WHERENOTCondition;

Example:

SELECT*FROMEmployee_Info WHERE
NOT City='Mumbai';

NOTE:Youcanalsocombinetheabovethreeoperatorsandwriteaqueryasfollows:
SELECT*FROMEmployee_Info
WHERENOTCountry='India'AND(City='Bangalore'ORCity='Hyderabad');

BETWEEN Operator: The BETWEEN operator is used, when you want to select values within a
given range. Since this is an inclusive operator, both the starting and ending values are
considered.

Syntax: SELECTColumnName(s)
FROM TableName
WHEREColumnNameBETWEENValue1ANDValue2;

Example:
 SELECT*FROMEmployee_Salary
WHERESalaryBETWEEN40000AND50000;

LIKEOperator

The LIKE operator is used in a WHERE clause to search for a specified pattern in a column of a
table. There are mainly two wildcards that are used in conjunction with the LIKE operator:

 % :Itisusedtomatches 0ormorecharacter.
 _:Itis usedtomatchesexactlyonecharacter.
Syntax

SELECTColumnName(s) FROM
TableName
WHEREColumnNameLIKEpattern;

RefertothefollowingtableforthevariouspatternsthatyoucanmentionwiththeLIKEoperator.

LikeOperatorCondition Description
WHERECustomerNameLIKE‘v% Findsanyvaluesthatstartwith“v”
WHERECustomerNameLIKE‘%v’ Findsanyvaluesthatendwith“v”
WHERECustomerNameLIKE‘%and%’ Findsanyvaluesthathave“and”in any position
Findsanyvaluesthathave“q”inthesecondpositio
WHERECustomerNameLIKE‘_q%’
n.
Findsanyvaluesthatstartwith“u”andareat least 3
WHERECustomerNameLIKE‘u_%_%’
characters in length
Findsanyvaluesthatstartwith“m”andend with
WHEREContactNameLIKE‘m%a’
“a”

Example:
SELECT * FROM Employee_Info
WHEREEmployeeNameLIKE'S%';

INOperator:[Link] multiple values in a

WHERE clause.

Syntax: SELECTColumnName(s)
FROM TableName
WHEREColumnNameIN(Value1,Value2...);

Example:

SELECT*FROMEmployee_Info
WHERECityIN('Mumbai','Bangalore','Hyderabad');
NOTE:YoucanalsouseINwhilewritingNestedQueries.

EXISTSOperator: TheEXISTSoperatorisusedtotestifarecordexistsornot.
Syntax: SELECTColumnName(s)
FROM TableName WHERE
EXISTS
(SELECTColumnNameFROMTableNameWHEREcondition);

Example:

SELECTCity
FROMEmployee_Info
WHEREEXISTS(SELECTCity
FROMEmployee_Info
WHEREEmployeeId=05ANDCity='Kolkata');

ALL Operator: The ALL operator is used with a WHERE or HAVING clause and returns
TRUEif all of the subquery values meet the condition.

Syntax: SELECTColumnName(s)
FROM TableName
WHEREColumnNameoperatorALL
(SELECTColumnNameFROMTableNameWHEREcondition);

Example:

SELECTEmployeeName FROM
Employee_Info
WHEREEmployeeID=ALL(SELECTEmployeeID
FROMEmployee_Info
WHERECity='Hyderabad');

ANYOperator:SimilartotheALLoperator,theANYoperatorisalsousedwithaWHEREor HAVING
clause and returns true if any of the subquery values meet the condition.

Syntax: SELECTColumnName(s)
FROM TableName
WHEREColumnNameoperatorANY
(SELECTColumnNameFROMTableNameWHEREcondition);

Example:

SELECTEmployeeName FROM
Employee_Info
WHEREEmployeeID=ANY(SELECTEmployeeID
FROMEmployee_Info
WHERECity='Hyderabad'ORCity='Kolkata');

AliasesStatement:Aliasesareusedtogiveacolumn /tableatemporarynameandonly exists for

duration of the query.

Syntax:/*[Link] used in the table, it display alias

name. */

SELECTColumnNameASAliasName FROM
TableName;
 Example:

SELECTEmployeeIDASID,EmployeeNameASEmpName FROM
Employee_Info;

5. NESTEDQUERIES
[Link], basically, the
subquery is a query which is nested within another query.

OUTERQUERY SUBQUERYorINNERQUERY

SELECTEmployeeName,PhoneNumber FROM Employee_Info

WHERECityIN( SELECTCity
FROMOffice
WHERECounty=‘INDIA’);

Firsttheinnerquerygetsexecutedandthe result willbeusedtoexecutetheouter query.

6. SETOPERATIONS:UNION,INTERSECT,EXCEPT
Therearemainlythreesetoperations:UNION, INTERSECT,[Link] image below
to understand the set operations in SQL.

i. UNION:Thisoperatorisusedtocombinetheresult-setoftwoormoreSELECTstatements.
Syntax: SELECTColumnName(s)FROMTable1WHEREcondition UNION
SELECTColumnName(s)FROMTable2WHEREcondition;

ii. INTERSECT:ThisclauseusedtocombinetwoSELECTstatementsandreturnthe intersection

of the data-sets of both the SELECT statements.
 Syntax: SELECTColumnName(s)FROMTable1WHEREcondition INTERSECT
SELECTColumnName(s)FROMTable2WHEREcondition;

iii. EXCEPT:ThisoperatorreturnsthosetuplesthatarereturnedbythefirstSELECT operation, and

are not returned by the second SELECT operation.

Syntax: SELECTColumnName(s)FROMTable1WHEREcondition EXCEPT

SELECTColumnName(s)FROMTable2WHEREcondition;

Note: UNION, INTERSECT or EXCEPT operations are possible if and only if first SELECT
query and second SELECT query produces same no of columns in same order, same
column names and data type. Otherwise it gives an error.

7. JOINS
JOINS are used to combine rows from two or more tables, based on a related column betweenthose
tables. The following are the types of joins:

 INNER JOIN:This join returns those records which have matching values in both
thetables.
 FULL JOIN:This join returns all those records which either have a match in the left or
the right table.
 LEFT JOIN:This join returns records from the left table, and also those records which
satisfy the condition from the right table.
 RIGHTJOIN:Thisjoinreturnsrecordsfromtherighttable,andalsothoserecords which
satisfy the condition from the left table.

Refertotheimage below.
Let’sconsider the below Technologiesand the Employee_Infotable, to understand the syntax of joins.

Employee_Info
EmployeeID EmployeeName PhoneNumber City Country
01 Shravya 9898765612 Mumbai India
02 Vijay 9432156783 Delhi India
03 Preeti 9764234519 Bangalore India
04 Vijay 9966442211 Hyderabad India
05 Manasa 9543176246 Kolkata India

Technologies
TechID EmpID TechName ProjectStartDate
1 01 DevOps 04-01-2019
2 03 Blockchain 06-07-2019
3 04 Python 01-03-2019
4 06 Java 10-10-2019

INNER JOIN or EQUI JOIN: This is a simple JOIN in which the result is based on matched
data as per the equality condition specified in the SQL query. This join is used mostly.
NATURAL JOIN is a type INNER JOIN. We can also use it. It also gives same result.
Syntax

SELECTColumnName(s) FROM
Table1
[Link]=[Link];

Example

[Link],[Link],[Link] FROM
Technologies T
INNERJOINEmployee_InfoEONT.EmpID=[Link];

TechID EmployeeID EmployeeName

1 01 Shravya
2 03 Preeti
3 04 Vijay
FULL OUTER JOIN: The full outer join returns a result-set table with the matched data of
two table then remaining rows of both left table and right table with missing values are filled
with NULL values.

Syntax
SELECTColumnName(s) FROM
Table1
[Link]=[Link];

Example

[Link],[Link],[Link] FROM
Employee_Info E
[Link]=[Link];

EmployeeID EmployeeName TechID

01 Shravya 1
02 Vijay NULL
03 Preeti 2
04 Vijay 3
05 Manasa NULL
06 NULL 4

LEFT JOIN: The left outer join returns a result-set table with the matched data from the two
tables and then the remaining rows of the left table with null for the right table's columns.
Syntax:
SELECTColumnName(s) FROM
Table1
[Link]=[Link];

Example:
[Link],[Link],[Link] FROM
Employee_Info E
[Link]=[Link];

EmployeeID EmployeeName TechID

01 Shravya 1
02 Vijay NULL
03 Preeti 2
04 Vijay 3
05 Manasa NULL
RIGHT JOIN: The right outer join returns a result-set table with the matched data from the
two tables being joined, then the remaining rows of the right table and null for the remaining left
table's columns.
Syntax:
SELECTColumnName(s) FROM
Table1
[Link]=[Link];

Example:
[Link],[Link],[Link] FROM
Employee_Info E
[Link]=[Link];

EmployeeID EmployeeName TechID

01 Shravya 1
03 Preeti 2
04 Vijay 3
NULL NULL 4

8. TRIGGERS
Atriggerisastoredprocedureindatabasewhichautomaticallyinvokeswheneveraspecialevent in the
database occurs. For example, a trigger can be invoked when a row is inserted into a specified
table or when certain table columns are being updated. So, a trigger can be invoked either
BEFORE or AFTER the data is changed byINSERT, UPDATE or DELETEstatement. Refer
to the image below.
Syntax:
CREATETRIGGER[TriggerName] [BEFORE |
AFTER]
{INSERT|UPDATE|DELETE}
on[TableName]
[FOREACHROW]
[TriggerBody]

Explanationofsyntax:

 createtrigger[trigger_name]:Createsorreplacesanexistingtriggerwiththe
trigger_name.
 [before|after]:Thisspecifieswhenthetriggerwillbeexecuted.
 {insert|update|delete}: This specifies theDMLoperation.
 on[table_name]:This specifiesthenameofthetableassociatedwiththetrigger.
 [foreachrow]:Thisspecifiesarow-leveltrigger,i.e.,thetriggerwillbeexecutedfor each
row being affected.
 [trigger_body]:Thisprovidestheoperationtobeperformedastriggerisfired.

BEFOREandAFTERofTrigger:
BEFOREtriggersrunthetriggeractionbeforethetriggeringstatementisrun. AFTER
triggers run the trigger action after the triggering statement is run.

EXAMPLE:

CREATE TRIGGER nb BEFORE INSERT ON accounts FOR EACH ROW /*Event*/ Begin
IF:[Link]<0THEN /*Condition*/
DBMS_OUTPUT.PUT_LINE('BALANCE IS NAGATIVE..'); /*Action*/
END IF;
End;

A trigger called ‘nb’ is created to alert the user when inserting account details with negative
balance value in to accounts table. Before inserting, the trigger is activated if the condition istrue.
When a trigger activated, the action part of the trigger is get executed.

9. NORMALIZATION
 Normalizationistheprocessofminimizingtheredundancyfromarelationorsetof relations.
 ItisusedtoeliminatetheInsertion,UpdateandDeletionAnomalies.
 Normalizationdividesthelargertableintothesmallertableandlinksthemusing relationship.
 Normalizationisdonewiththehelpofdifferentnormalform.
 The inventor of the relational model Edgar Codd proposed the theory of normalization with
the introduction of the First Normal Form, and he continued to extend theory with Second and
Third Normal Form. Later he joined Raymond F. Boyce to develop the theory of Boyce-Codd
Normal [Link] software industry, they are using only up to third normal form and sometimes
Boyce-Codd Normal Form.

TheProblemofredundancy

[Link] when a
database is not normalized. Redundancy leads the following problems.

 WastageofMemory:Diskspaceis wasted duetostoringsamecopymultipletimes.

 Storage cost increases: When multiple copies of same data is stored, need more disk
space and storage cost increases.
 Update anomaly: When Address of student is stored at several places; a change in the
address must be made in all the places. Changing the address at some places and leaving
other places leads to inconsistency problem.
 Insertion Anomaly: The nature of a database may be such that it is not possible to add a
required piece of data unless another piece of unavailable data is also added. Forexample,
a librarydatabase cannot store the details of a new student until that student has taken
atleast one book from the library.
 Deletion Anomaly: When some data is deleted, it also deletes other data automatically.
For example, deleting a book details from a library database, it also delete the student
details who have taken the book previously.

10. 1NF(FIRSTNORMALFORM)
Arelation (table)is said tobeinfirstnormalformifand only if:

 Eachtablecellcontainsonlyatomic values(singlevalue).
 Each recordneedstobeuniquelyidentifiedbytheprimary key.
1NF Example:

HTNO FIRSTNAME LASTNAME MOBILE

9999988888
501 Jhansi Rani
7777799999
8888888881
502 Ajay Kumar
7897897897
503 Priya Verma 9898989898

Theabovetableis not in 1NFbecause 501 and 502 is havingtwovaluesinmobilecolumn. If we add a

new column as alternative mobile number to the above table, then for 503 alternative mobile
number is [Link], if a student has ‘n’ mobile numbers, then adding ‘n’ extra column is
meaningless. It is better to add extra rows. If we add extra row for each 501 and 502 then the
table looks like

HTNO FIRSTNAME LASTNAME MOBILE

501 Jhansi Rani 9999988888
501 Jhansi Rani 7777799999
502 Ajay Kumar 8888888881
502 Ajay Kumar 7897897897
503 Priya Verma 9898989898

But the above table violates primary key constraint. Therefore instead of adding either columns or
rows, the best solution is to split the table into two tables as shown below. If we do as shown
below, if a student having ‘n’ number of mobile numbers also can be added.

HTNO FIRST LAST HTNO MOBILE

NAME NAME 501 9999988888
501 Jhansi Rani 501 7777799999
502 8888888881
502 Ajay Kumar
502 7897897897
503 Priya Verma 503 9898989898

11. 2NF(SECONDNORMALFORM)

Arelation is said to bein 2-NFifand only if

 Itshouldbein 1-NF(FirstNormalForm)
 Thereshouldnotbeanypartialfunctionaldependencies

2NFExample:
 HTNO Name DOB DeptNo DeptName Location
501 Jhansi 30-10-1998 05 CSE A-Block
502 Ajay 24-12-1999 05 CSE A-Block
410 Priya 12-03-2000 04 ECE B-Block
120 Rahul 30-10-1998 01 CIVIL C-Block
415 Smitha 18-06-1999 04 ECE B-Block

The above table is not in 2NF because there exist partial function dependencies. HTNO is a
key attribute in the above table. If every non-key attribute fully dependent on key attribute,
then we say it is fully functional dependent. Consider the below diagram. {Name, DOB,
DeptNo, DeptName, Location} depends on HTNO. But {DeptName, Location} also depends
on DeptNo.

Name

DOB DeptName

DeptNo DeptNo

HTNO Location
DeptName

Location

It is clear that DeptNameand Location not only depends upon HTNO but also on DeptNo.
So, there exists partial function dependency. This partial functional dependency can be
removed by splitting the above table into two tables as follows.

HTNO Name DOB DeptNo DeptNo DeptName Location

12. 3NF(THIRDNORMALFORM)
501 Jhansi 30-10-1998 05 05 CSE A-Block
502 Ajay 24-12-1999 05
410
Arelation Priya in thirdnormal
(table)is 12-03-2000 form 04
04 ifandonlyif it satisfiesthe ECE B-Block
following conditions:
120 Rahul 30-10-1998 01 01 CIVIL C-Block
415 Smitha 18-06-1999
 Itisinsecondnormalform 04
 Thereisnotransitivefunctionaldependency

Transitive functional dependency means, we have the following relationships in the table: A
is functionallydependent on B (A→B), and Bis functionallydependent on C (B→C). In this
case, C is transitively dependent on A via B (A→B and B→C mean A→B→C implies
A→C).
 3NFExample:

Considerthefollowingbookdetails table example:

BOOK_DETAILS
BookID GenreID GenreType Price
1 1 Gardening 250.00
2 2 Sports 149.00
3 1 Gardening 100.00
4 3 Travel 160.00
5 2 Sports 320.00

Theabovetableisnot in3NFbecausethereexist [Link],

BookIDdeterminesGenreID {BookID→GenreID}
GenreIDdeterminesGenreType. {GenreID→GenreType}
BookIDdeterminesGenreTypeviaGenreID. {BookID→GenreType}
Itimpliesthattransitivefunctionaldependencyisexistingandthestructuredoesnotsatisfy
[Link],wesplitthetableintotwoasfollows:
BOOK_DETAILS
BookID GenreID Price
1 1 250.00 GENRE_DETAILS
2 2 149.00 GenreID GenreType
3 1 100.00 1 Gardening
4 3 160.00 2 Sports
5 2 320.00 3 Travel

13. BOYCECODDNORMALFORM(BCNF)

Arelation (table) is said to beintheBCNFifandonlyif it satisfythefollowingconditions:

 ItshouldbeintheThirdNormalForm.
 ForanyfunctionaldependencyA→B, Ashouldbeasuperkey.
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:[Link] go tohospitalmany times to

take treatment. On a single day many patients can take treatment.
Name
P EmailID AdmittedDate Drug Quntity

Ram
1 ram@[Link] 30/10/1998 A-10 10

Jhon
1 jho@[Link] 30/10/1998 X-90 10

Ram
1 ram@[Link] 10/06/2001 X-90 20

Sowmya
1 sam@[Link] 05/03/2002 Y-30 15

Jhon
1 jho@[Link] 05/03/2002 A-10 15

Intheabovetable,{PateintID,AdmittedDate}[Link]
EmailIDvalue, wecan find PatientIDvalue.

ThatisEmailID→ PatientID.

In the above dependency, EmailIdis non-prime attribute and PatientIDis a primeattribute.

Therefore the above table is not in BCNF. In order to bring the table into BCNF, we split it
into two tables as shown below.

PatientID Name AdmittedDate Drug Quntity PatientID EmailID

In 101
other wordsRamwe can also define
30/10/1998 BCNF as
A-10 10there should not
101be any overlapping between candidate
ram@[Link]
102
keys. If youJhon
consider30/10/1998 X-90
the original table 10 splitting), we
(before 102can get twojho@[Link]
candidate keys {PateintID,
101 Ram 10/06/2001 X-90 20 103 sam@[Link]
AdmittedDate}
103 and{EmailID,
Sowmya 05/03/2002AdmittedDate}.
Y-30 15
102 Jhon 05/03/2002 A-10 15

Asthereexistoverlappinginthecandidatekeys,thetableisnotinBCNF. Tobringitinto BCNF, we split into

two tables as shown above.
14. 4-NF(FOURTHNORMALFORM)
Arelation is said to be in 4-NFif and onlyif it satisfies the followingconditions

 ItshouldbeintheThirdNormalForm.
 Thetableshould not haveanyMulti-valuedDependency.

WhatisMulti-valuedDependency?
Atable is said tohavemulti-valued dependency, if thefollowingthreeconditionsaretrue.

i. Atableshould haveat-least 3 columns forit to haveamulti-valueddependency.

ii. ForanydependencyA→B,ifthereexistsmultiplevalueofBforasinglevalueofA, then the
table may have multi-valued dependency. It is represented as A →→ B.
iii. InarelationR(A,B,C),ifthereisamulti-valueddependencybetweenA and B,thenB
andCshouldbeindependentofeachother.

If all these three conditions are true for any relation (table), then it contains multi-valued
[Link]-valueddependencycanbeexplainedwithanexample. LettheRelationR
containing three columns A, B, C and four rows s, t, u, v.

A B C
s a1 b1 c1
t a1 b1 c2
u a1 b2 c1
v a1 b2 c2
If s(A)=t(A)=u(A)=v(A)
s(B)=t(B) ands(B) =v(B)
s(C)=u(C)andt(C)=v(C), then thereexist multi-valueddependency.

Example:ConsiderthebelowcollegeenrolmenttablewithcolumnsHTNO,Subjectand
Hobby.

Subject Python
Subject Java
C# Android
501 502
Hobby Cricket Hobb Chess
y
Dancin Singing
g
Department of CSE(AIML) MRCET
MRCET

Asshownin the above figure, if501 opted forsubjectslikeJavaand C# and hobbies of

501 are Cricket and Dancing. Similarly, If 502 opted for subjects like Python andAndroid
and hobbies of 501 are Chess and Singing, then it can be written into a table with three
columns as follows:
HTNO Subject Hobby
501 Java Cricket
501 Java Dancing
501 C# Cricket
501 C# Dancing
502 Python Chess
502 Python Singing
502 Android Chess
502 Android Singing

Asthereexistmultivalueddependency,theabovetableisdecomposedintotwotablessuch that

HTNO Subject HTNO Hobby

Nowthesetables(relations)satisfythefourthnormalform.
501 Java 501 Cricket
501 C# 501 Dancing
15. 5NF502 Python 502 Chess
502 Android 502 Singing
Arelation is said to be in 5-NFif and onlyif it satisfies the followingconditions

 ItshouldbeintheFourthNormalForm.
 Thetableshould not haveanyjoinDependencyandjoiningshouldbelossless.

5NFisalso knownasProject-join normalform(PJ/NF).

A table is decomposed into multiple small tables to eliminate redundancy, and when
we re-join the decomposed tables, there should not be any loss in the original data or
shold not create any new data. In simple words, joining two or more decomposed table
should not lose records nor create new records.

Database Management Systems Page 78

Department of CSE(AIML) MRCET
MRCET

Example:ConsideratablewhichcontainsarecordofSubject,ProfessorandSemesterin three
columns. The primarykeyis the combination of all three columns. No column itself is not a
candidate key or a super key.

Inthetable,DBMSistaughtbyRavindarandUmaRaniinsemester4,DSby Sindhushaand Venu in sem 3.

In this case, the combination of all these fields required to identify valid data.

Sotomakethetableinto 5NF,we candecompose it intothreerelations,

Subject Professor Semester

C Srilatha 2
DBMS Ravindar 4
DS Sindhusha 3
DBMS UmaRani 4
CN Srikanth 5
DS Venu 3
WT Srinivas 5

Theabovetableisdecomposedintothreetablesasfollows to bringit into 5-NF.

Subject Professor Semester Professor Semester Subject

16.
C LOSSLESSJOINDECOMPOSITION
Srilatha 2 Srilatha 2 C
DBMS Ravindar 3 Ravindar 4 DBMS
Decomposition of a relation R into R1 and R2 is lossless-join decomposition if at least one of
DS Sindhusha 5 Sindhusha 3 DS
the following
DBMS UmaRani functional dependencies are
3 in F+ (Closure
UmaRani of functional dependencies)
5 CN
CN Srikanth 5 Srikanth
R1∩R2→R1 OR 5 WT
DS Venu 2 R1∩R2→R2
Venu
WT Srinivas 5 Srinivas
 ConsiderarelationRwhichisdecomposedinto subrelationsR1 and R2.
 ThisdecompositioniscalledlosslessjoindecompositionwhenwejoinR1andR2and if we

 Forlosslessjoindecomposition, wealways have:R1⋈R2

get the same relation R that was decomposed.

Database Management Systems Page 79

Example 1:Consider the following relation R( A , B , C ). Let this relationis decomposed
into two sub relations R1( A , B ) and R2( B , C )

R R1 R2
A B C A B B C
1 2 1 decompose→ 1 2 and 2 1
2 5 3 2 5 5 3
3 3 3 3 3 3 3

we must have:R1⋈R2 = R .Now, if we perform the natural join ( ⋈) of the sub relations R 1 and
Now, let us check whether this decomposition is lossless or not. For lossless decomposition,

R2 , we get
A B C
1 2 1 ThisrelationissameastheoriginalrelationR.
2 5 3
3 3 3

Thus, we conclude that the above decomposition is lossless join decomposition. This is
because the resultant relation after joining the sub relations is same as the decomposed
relation. No extraneous tuples (rows) appear after joining of the sub-relations.

Example 2:Considerthe following relation R( A , B , C ). Let this relation is decomposed

into two sub relations R1( A , C ) and R2( B , C )

R R1 R2
A B C A C B C
1 2 1 decompose→ 1 1 and 2 1
2 5 3 2 3 5 3
3 3 3 3 3 3 3

we must have:R1⋈R2 = R .Now, if we perform the natural join ( ⋈) of the sub relations R 1 and
Now, let us check whether this decomposition is lossless or not. For lossless decomposition,

R2 , we get
A B C
1 2 1 ThisrelationisnotsameastheoriginalrelationR.
2 5 3
2 3 3
3 5 3
3 3 3

Thus, we conclude that the above decomposition is not lossless join decomposition. This is
because the resultant relation after joining the sub relations is not same as the decomposed
relation. Extraneous tuples (rows) appear after joining of the sub-relations.
 PROBLEMS
ConsiderarelationRisdecomposedintotwo sub relationsR1andR2.

 Ifall the followingconditions satisfy, thenthedecomposition is lossless.

 If anyoftheseconditionsfail,thenthedecomposition is lossy.

Condition-01:Unionofboththesubrelationsmustcontainalltheattributesthatarepresent in the
original relation R.
R1∪R2= R
Condition-02:Intersectionofboththesubrelationsmustnotbenull. Inotherwords,there must be
some common attribute which is present in both the sub relations.
R1∩R2 ≠∅
Condition-03:IntersectionofboththesubrelationsmustbeasuperkeyofeitherR1orR2or both.

************************************************************************

Problem-01:ConsiderarelationschemaR(A,B,C,D)withthefunctionaldependencies A → B
and C → D. Determine whether the decomposition of R into R1 ( A , B ) and R2 ( C , D ) is
lossless or lossy.

Solution:To determine whether the decomposition is lossless or lossy, we will check all the
conditions one by one. If any of the conditions fail, then the decomposition is lossy otherwise
lossless.
Condition-01:Accordingto condition-01,union ofboththesubrelations must containallthe
attributes of relation R. So, we have:
R1( A, B)∪R2( C , D ) = R(A , B, C , D )
Clearly, union of the sub relations contains all the attributes of relation R. Thus, condition-01
satisfies.
Condition-02:According to condition-02, intersection of both the sub relations must not be
null. So, we have-
R1( A, B)∩R2( C , D ) = Φ
Clearly, intersection of the sub relations is [Link], condition-02 fails. Thus, we conclude that
the decomposition is lossy.

************************************************************************
Problem-02:ConsiderarelationschemaR(A,B,C,D)withthefollowingfunctional dependencies
A→ B B→ C C→D D→ B
Determinewhetherthedecompositionof RintoR1( A , B ), R2(B , C) and R3(B ,D )is lossless or
lossy.
Solution:

StrategytoSolve:Whenagivenrelationisdecomposedintomorethantwosubrelations, then
ConsidertheoriginalrelationRwasdecomposedintothegivensubrelationsasshown:
 Consideranyonepossiblewaysinwhichtherelationmighthavebeendecomposed into
those sub relations.
 First,dividethegivenrelationintotwosubrelations.
 Then,dividethesubrelationsaccordingtothesubrelationsgiveninthequestion. As a
thumb rule, remember-
Anyrelation can bedecomposedonlyinto two sub relations at a time.

Decomposition ofR(A,B, C,D) intoR'(A, B, C)and R3(B,D)-

Todeterminewhetherthedecompositionislosslessorlossy,
 Wewill check all the conditions onebyone.
 Ifanyoftheconditionsfail,thenthedecompositionislossyotherwiselossless.

Condition-01:According to condition-01, union of both the sub relations must contain all the
attributes of relation R. So, we have
R‘( A, B, C )∪R3( B, D ) = R (A , B, C , D )
Clearly, union of the sub relations contains all the attributes of relation R. Thus, condition-01
satisfies.

Condition-02:According to condition-02, intersection of both the sub relations must not

benull. So, we have
R‘( A, B, C )∩R3(B,D ) = B
Clearly,intersectionofthesubrelations [Link],condition-02 satisfies.

Condition-03:According to condition-03, intersection of both the sub relations must be

thesuper key of one of the two sub relations or both. So, we have-
R‘( A, B, C )∩R3(B,D ) = B
Now, the closure of attribute B is: B+={B,C,D} So,
 Attribute‘B’cannotdetermineattribute‘A’ofsubrelationR’.
 Thus,itisnotasuperkeyofthe sub relation R’.
 Attribute‘B’ candeterminealltheattributesofsubrelationR3.
 Thus,it is a super keyofthe sub relation R3.

Clearly,intersectionofthesubrelationsisasuperkeyofoneofthesubrelations. So,
condition-03 satisfies. Thus, we conclude that the decomposition is lossless.

Decomposition of R'(A, B,C) intoR1(A, B)andR2(B,C)-

Todeterminewhetherthedecompositionislosslessorlossy,
 Wewill check all the conditions onebyone.
 Ifanyof the conditions fail, then thedecomposition is lossyotherwiselossless.

Condition-01: According to condition-01, union of both the sub relations must contain all the
attributes of relation R’. So, we have
R1( A, B)∪R2( B, C ) = R’(A, B, C )
Clearly, union of the sub relations contain all the attributes of relation R’. Thus, condition-01
satisfies.
Condition-02: According to condition-02, intersection of both the sub relations must not
benull.
So, wehave
R1( A, B)∩R2( B, C) = B
Clearly,intersectionofthesubrelations [Link],condition-02 satisfies.

Condition-03: According to condition-03, intersection of both the sub relations must be

thesuper key of one of the two sub relations or both. So, we have
R1( A, B)∩R2( B, C) = B
+
Now, the closure of attribute B is: B ={B,C,D} So,
 Attribute‘B’cannotdetermineattribute‘A’ofsubrelationR1.
 Thus,itis nota superkeyofthe sub relation R1.
 Attribute‘B’ candeterminealltheattributesofsubrelationR2.
 Thus,it is a super keyofthesubrelationR2.

Clearly,[Link], condition-03
satisfies. Thus, we conclude that the decomposition is lossless.
17. CLOSUREOFANATTRIBUTESET:

The set of all those attributes which can be functionally determined from an attribute
set is called as a closure of that attribute set. Closure of attribute set {X} is denoted as {X} +.
StepstoFindClosureofanAttributeSet:Followingstepsarefollowedtofindthe closure of an
attribute set:
Step-01:Addtheattributescontainedintheattributesetforwhichclosureisbeing calculated to the
result set.
Step-02:Recursivelyaddtheattributestotheresultsetwhichcanbefunctionallydetermined from the
attributes already contained in the result set.

Question1: ConsiderarelationR(A,B,C,D,E,F,G)withthefunctionaldependencies
A→ BC, BC→DE, D→ F, CF→ G
Findtheclosureof{A}, {D} and{B,C}attributesandattributesets
Solution:
ClosureofattributeA:
A+= { A }
={ A , B, C } (UsingA→BC)
={ A , B, C , D , E} (UsingBC →DE)
={ A , B, C , D , E,F} (UsingD→F)
={ A , B, C , D , E,F,G } (UsingCF→ G)
Thus,
A+={A , B , C , D, E ,F,G}
ClosureofattributeD:
+
D={D}
={ D , F}( UsingD→ F)
WecannotdetermineanyotherattributeusingattributesDandFcontainedintheresultset. Thus,
D+= {D ,F}
Closureofattributeset{B, C}
+
{ B, C } ={ B, C}
={ B, C , D , E} (UsingBC→DE)
={ B, C , D , E,F} (UsingD→F)
={ B, C , D , E,F, G } ( UsingCF→ G)
Thus,
{B , C }+= {B , C , D,E , F,G}
Question2:Considerthegivenfunctionaldependencies
AB→ CD AF→ D DE→F C→G F→ E G→ A
Findtheclosureof {A,B}, {A, F},{B, G}and {C, F}

Solution:
Closureof {A, B}:
{AB}+={ A ,B }
={ A , B, C , D } (UsingAB→ CD)
={ A , B, C , D ,G } (UsingC→ G)
Thus,{AB}+={ A , B, C , D , G}

Closureof {C, F}:

+
{CF} ={ C , F }
={ C , F, G } (UsingC→ G)
={ C , E , F, G } (Using F→ E )
={ A , C , E , E , F} (UsingG→A)
={ A , C , D , E , F,G } (UsingAF→ D)
Thus,{ CF}+={ A, C , D , E, F,G }

Closureof {B, G}:

+
{BG } ={B, G }
={ A , B,G } (UsingG→A)
={ A , B, C , D ,G } (UsingAB→ CD)
+
Thus,{ BG } ={ A,B , C , D , G}

Closureof {B, G}:

+
{AF} ={ A ,F }
={ A , D, F} (UsingAF→ D )
={ A , D, E ,F} (Using F→ E )
+
Thus,{ AF} ={ A ,D , E, F}

18. FINDINGTHEKEYSUSINGCLOSURE

Super Key:
Iftheclosureresultofanattributesetcontainsalltheattributesoftherelation, then that attribute set is
called as a super key of that relation.
 Thus,wecansay,“Theclosureofasuperkeyistheentirerelationschema.”
Example:In the above example (Question 1),
 Theclosureof attribute A is theentirerelationschema.
 Thus,attributeA is asuperkeyfor that relation.
CandidateKey:
If there exists no subset of an attribute set whose closure contains all the attributes of
the relation, then that attribute set is called as a candidate key of that relation.
Example:Intheaboveexample(Question1),
 NosubsetofattributeA contains alltheattributesofthe relation.
 Thus,attributeA is also a candidatekeyfor that relation.

FindingCandidateKeysFromaRelation:
Wecandeterminethecandidatekeysofagivenrelationusingthefollowingsteps-

Step-01:Determineallessentialattributesofthegiven relation

 EssentialattributesarethoseattributeswhicharenotpresentonRHSofanyfunctional
dependency.
 [Link] cannot
be determined by other attributes.

Example:LetR(A,B,C,D,E,F)bearelationschemewiththefollowingfunctional dependencies:
A → B,C → DandD → E.

The RHS of all the above functional dependencies contain only B, D and E. The
attributeswhicharenotpresentonRHSofanyfunctionaldependencyareA,CandF. So,
essential attributes are: A, C and F.

Step-02:Determiningallnon-essentialattributesusingessentialattributes

 [Link] can be
determined by using essential attributes.
 Now,followingtwocasesarepossible-
 Case-01:Ifallessentialattributestogethercandetermineallremainingnon-essential
attributes, then
o Thecombinationofessentialattributesisthecandidatekey.
o Itis the onlypossiblecandidatekey.
 Case-02:Ifallessentialattributestogethercannotdetermineallremainingnon-
essential attributes, then-

 Thesetofessentialattributesandsomenon-essentialattributeswillbethecandidate key(s).
 Inthiscase,multiplecandidatekeysarepossible.
 Tofindthecandidatekeys,wecheckdifferentcombinationsofessentialandnon-
essential attributes.

.
 PROBLEMSONFINDINGCANDIDATEKEYS

Problem-
01:LetR=(A,B,C,D,E,F)bearelationschemewiththefollowingdependencies:C→F,E→A
,EC→DandA→B. [Link], determine the total number of candidate
keys and super keys.

Solution:Wewillfindcandidatekeysofthegivenrelationinthefollowingsteps-
Step-01:Determineallessentialattributesofthegiven relation.

 Essentialattributesoftherelationare: C andE.
 So,attributes C and Ewilldefinitelybeapartofeverycandidatekey.

Step-02:Now,wewillcheckiftheessentialattributestogethercandetermineallremaining non-
essential attributes. To check, we find the closure of CE. So,

{ CE }+ ={ C , E }
={ C, E , F} (UsingC→F)
={ A , C , E , F} (UsingE→A)
={ A , C , D , E , F} (UsingEC→ D)
={ A , B, C , D , E,F} (UsingA→B)
[Link],CEistheonly possible
candidate key of the relation.

TotalNumberofSuper Keys-

Therearetotal6attributes inthegivenrelationofwhich-

 Thereare2essentialattributes-Cand E.
 Remaining4 attributesarenon-essential attributes.
 Essential attributes will be definitelypresent in every key.
 Non-essential attributesmayormaynotbepresentineverysuperkey.

C E ABDF

Essential attributes Non-Essentialattributes

So,numberofsuperkeyspossible=2x 2x 2x 2=[Link],totalnumberofsuperkeys possible = 16.

Problem-02:ConsidertherelationschemeR(E,F,G,H,I,J,K,L,M,N)andtheset
offunctionaldependencies: {E, F} → { G}, { F} → {I, J}, { E, H} → { K,L},
{ K} → { M} and {L}→ {N}.Determine thecandidatekey(s).
Solution:Wewillfindcandidatekeysofthegivenrelationinthe following steps-
Step-01:Determineallessentialattributesofthegiven relation.

 Essentialattributesof the relationare-E,FandH.

 So,attributes E, Fand Hwilldefinitelybeapart of everycandidatekey.

Step-02:

 Wewillcheckiftheessentialattributestogethercandetermineallremainingnon-
essential attributes.
 Tocheck,wefindtheclosureofEFH. So,

we have-

{EFH }+={E , F,H}

={ E , F, G ,H } (UsingEF → G)
={ E , F, G ,H ,I, J} (UsingF→IJ)
={ E , F, G ,H ,I, J, K ,L} (UsingEH→ KL)
={ E , F, G ,H ,I, J, K ,L, M } (Using K→ M)
={ E , F, G,H,I, J,K,L, M, N}( UsingL→ N)
WeconcludethatEFHcandeterminealltheattributesofthegivenrelation. So,EFHisthe only
possible candidate key of the relation.

*****************************ALLTHE BEST *******************************

Ravindar.M,[Link],CSEDept,JITS-KNR
 UNIT– IV
Transaction Management: Transaction Concept, Transaction State, Implementation of Atomicity and
Durability, Concurrent Executions, Serializability, Recoverability, Implementation of Isolation, Testing for
serializability, Lock Based Protocols, Timestamp Based Protocols, Validation- Based Protocols, Multiple
Granularity, Recovery and Atomicity, Log–Based Recovery, Recovery with Concurrent Transactions.

1. TRANSACTION
Definition: Atransactionisasinglelogicalunitconsistingofoneormoredatabaseaccess operation.
Example:Withdrawing1000 rupeesfromATM.
Thefollowingsetofoperationsareperformedtowithdraw1000rupeesfromdatabase

ReadcurrentbalancefromDatabase (Let say 5000 rupees) (5000 – 1000 =4000)

Deduct1000fromcurrentbalance (4000rupees) oneTransaction
UpdatecurrentbalanceinDatabase

 Everytransactionisexecutedasasingleunit.
 If the database operations do not update the database but only retrieve data, this type
oftransaction is called a read-only transaction.
 Asuccessfultransactioncanchangethedatabasefromoneconsistentstatetoanother
consistentstate.
 DBMStransactionsmustsatisfyACIDproperties(atomic,consistent,isolatedand durable).

2. ACIDPROPERTIES
ACID propertiesareusedformaintainingtheintegrityofdatabaseduringtransactionprocessing. ACID
stands for Atomicity, Consistency, Isolation, and Durability.

 Atomicity: This property ensure that either all of the tasks of a transaction are performed or
none of them. In simple words it is referred as “all or nothing rule”.

Each transaction is said to be atomic if when one part of the transaction fails, the entire
transaction fails. When all parts of the transaction completed successfully, then the transaction
said to be success. (“all or nothing rule” )

Example:Transferring $100from accountAtoaccountB.

(Assumeinitially, accountAbalance =$400andaccountBbalance=700$.)
 Transferring$100from accountAtoaccountBhastwooperations
a) Debiting100$fromA’s balance ($400-$100 =$300)
b) Crediting100$to B’sbalance ($700+$100= $800)
Let’s say first operation (a) passed successfully while second (b) failed, in this case A’s balance
would be300$ while B would behaving700$ instead of 800$. This is unacceptableinabanking
[Link]
process both the operations. TheAtomicitypropertyensuresthat.

ii. Consistency: The consistency property ensures that the database must be in consistent state
before and after the transaction. There must not be any possibility that some data is incorrectly
affected by the execution of a transaction.
For example, transfering funds from one account to another, the consistency property ensures
that the total values of funds in both the accounts is the same before and end of the transaction.
i.e., Assume initially, A balance = $400 and B balance = 700$.
ThetotalbalanceofA+B =1100$(Beforetransferring100$fromA toB) The total
balance of A + B = 1100$(After transferring 100$ from A to B)
iii. Isolation:Foreverypairoftransactions,oneofthetransactionsshouldnotstartexecution
before the other transaction execution completed, if they use some common data variable. That
is, if the transaction T1 is executing and using the data item X, then transaction T2 should not
start until the transaction T1 ends, if T2 also use same data item X.
Forexample,TransactionT1: Transfer 100$from accountAtoaccountB
TransactionT2:Transfer150$ fromaccountBtoaccountC
Assumeinitially,Abalance=Bbalance=Cbalance=$1000

TransactionT1 TransactionT2
10:00AM ReadA’sbalance ($1000) ReadB’s balance ($1000)
10:01AM Abalance=ABalance –100$ (1000-100=900$) Bbalance=B Balance –150$ (1000-150= 850$)
10:02AM ReadB’s balance ($1000) ReadC’sbalance ($1000)
10:03AM Bbalance=B Balance+100$ (1000+100= 1100$) Cbalance=C Balance+150$ (1000+150=1150$)
10:04AM WriteA’sbalance (900$) WriteB’sbalance (850$)
10:05AM WriteB’sbalance (1100$) WriteC’sbalance (1150$)
10:06AM COMMIT COMMIT
 AftercompletionofTransactionT1andT2,Abalance=900$,Bbalance=1100$,Cbalance
=1150$. But B balance should be 950$. The B balance is wrong due to execution of T1 and T2
parallel and in both the transactions, Account B is common. The last write in account B is at
10:05 AM, so that B balance is 1100$ (write in account B at 10:04 AM is overwritten).

iv. Durability: Once a transaction completes successfully, the changes it has made into the
database should be permanent even if there is a system failure. The recovery-management
[Link],assume
account A balance = 1000$. If A withdraw 100$ today, then the A balance = 900$. After two
days or a month, A balance should be 900$, if no other transactions done on A.

3. STATESOFTRANSACTION
[Link] as
transaction states. They are:

ActiveState:
 Thisis the firststate in the lifecycleof a transaction.
 Oncethetransactionstartsexecuting,thenitissaidtobeinactivestate.
 During this state it performs operations like READ and WRITE on some data items. All
the changes made by the transaction are now stored in the buffer in main memory. They
are not updated in database.
 From active state, a transaction can go into either a partially committed state or a failed
state.
 PartiallyCommittedState:
 Whenthetransactionexecutesitslaststatement,thenthetransactionissaidtobein partially
committed state.
 Still,allthechangesmadebythetransactionarestoredinthebufferinmainmemory,but they are
not updated in the database.
 From partially committed state, a transaction can go into one of two states, a committed
state or a failed state.

CommittedState:
 After all the changes made by the transaction have been successfully updated in the
database, it enters into a committed state and the transaction is considered to be fully
committed.
 After a transaction has entered the committed state, it is not possible to roll back (undo)
the transaction. This is because the system is updated into a new consistent state and the
changes are made permanent.
 Theonlywaytoundothechangesisbycarryingoutanothertransactioncalled as compensating
transaction that performs the reverse operations.

FailedState:
 When a transaction is getting executed in the active state or partiallycommitted state and
some failure occurs due to which it becomes impossible to continue the execution, it
enters into a failed state.

Aborted State:
 After the transaction has failed and entered into a failed state, all the changes made by it
have to be undone.
 Toundothechangesmadebythetransaction,itbecomesnecessarytorollbackthe transaction.
 Afterthetransactionhasrolledbackcompletely,itentersintoanabortedstate.

TerminatedState:
 Thisisthelast state inthelifecycleof a transaction.
 Afterenteringthecommittedstateorabortedstate,thetransactionfinallyentersintoa
terminatedstatewhereits lifecycle finallycomes to an end.
 4. TYPESOFSCHEDULES–SERIALIZABILITY
In DBMS,schedulesmaybeclassifiedas

i. SerialSchedules:
 Allthetransactionsexecuteseriallyoneafter the other.
 Whenonetransactionexecutes,noothertransactionisallowedtoexecute.
Examples:
Schedule-1 Schedule-2
T1 T2 T1 T2
In schedule 1, afterRead(A)
T1 completes its execution, transaction T2 executes. So, schedule-1 is a
Read(A)
A=A+500 transaction T1
A=A-100 in schedule-2, after T2 completes its execution,
Serial Schedule. Similarly,
Write(A) Write(A)
executes. So, schedule -2 is also an example of a Serial Schedule.
Read(B) COMMIT
B=B+100 Read(A)
Write(B) A=A-100
ii. Non-SerialSchedules:
COMMIT Write(A)
 Innon-serialschedules,multipletransactionsexecuteconcurrently.
Read(A) Read(B)
A=A+500 B=B+100
 Operationsofall/someofthetransactionsareinter-leaved
Write(A)
ormixedwitheachother.
Write(B)
 Somenon-serialschedulesmayleadtoinconsistencyofthedatabaseandmayproduce
COMMIT COMMIT wrong
results.
 Examples:
Schedule-1 Schedule-2
T1 T2 T1 T2 operations of T1
Inschedule-1andschedule-2,[Link]
Read(A) Read(A)
and T2 are interleaved. So, these schedules are Non-Serial Schedule.
A=A-100 Read(A)
Write(A) A=A-100
Read(A) Write(A)
iii. SerializableSchedules:
A=A+500 A=A+500
Read(B) Read(B)
 A non-serial schedule of ‘n’ transactions is equivalent to some serial schedule of ‘n’
B=B+100 B=B+100
transactions,Write(B)
then it is called as a serializable schedule.
Write(B)
COMMIT COMMIT
 In other words, the results produced bythe transactions in a serial
Write(A)
schedule areequal to
Write(A)
theresultproducedbythesametransactionsinsomenon-serialschedule,thenthatnon-serial
COMMIT COMMIT

schedule is called as serializability.

 Serializableschedulesbehaveexactlysameas serial schedules.
 Even though, Serial Schedule and Serializable Schedule produce same result, there are
some differences they are
Serial Schedules SerializableSchedules
Concurrency is not allowed. Thus, all the
[Link],multiple
transactionsnecessarily execute serially one
transactions can execute concurrently.
after the other.
It leads to less resource utilization and CPU Itimprovesbothresourceutilizationand CPU
throughput. throughput.
Serial Schedules are less efficient SerializableSchedulesarealwaysbetter
as than serial
compared to serializable schedules. schedules.

Serializabilityismainlyoftwotypes. They are:

 ConflictSerializability
 ViewSerializability
Conflict Serializability:If a given non-serial schedule can be converted into a serial schedule by
swapping its non-conflicting operations, then it is called as a conflict serializable schedule.
Twooperationsarecalledasconflictingoperationsifallthefollowingconditionsholdtrue
(1) Boththeoperationsbelongtodifferenttransactions
(2) Boththeoperationsareon the samedataitem
(3) Atleastoneofthetwooperationsisawriteoperation

Schedule–1 Schedule–2 Schedule- 3 Schedule- 4

T1 T2 T1 T2 T1 T2 T1 T2
Read(A) Read(A) Write(B) Write(B)
Read(A) Write(A) Read(A) Write(B)

InSchedule-1,onlyrule(1)&(2)aretrue,butrule(3)[Link],theoperationsarenotconflict. In Schedule -2,

rule (1), (2) & (3) are true. So, the operations are conflict.
InSchedule-3,onlyrule(1)&(3)aretrue,butrule(2)[Link],theoperationsarenotconflict. In Schedule -4,
rule (1), (2) & (3) are true. So, the operations are conflict.

Testing of Conflict Serializability:Precedence Graph is used to test the Conflict

Serializability of a schedule. The algorithm to draw precedence graph is
(1) Draw anodeforeachtransactioninScheduleS.
(2) IfTareadsXvaluewrittenbyTb, thendrawarrowfrom Tb → Ta.
(3) If TbwritesXvalueafterithasbeenreadbyTa,thendrawarrowfromTa→Tb.
(4) IfTawritesXafterTbwritesX,thendraw arrow from Tb →Ta.
Iftheprecedencegraphhasnocycle,[Link] precedence graph
contains a cycle, then S is not conflict serializable.

Problem-01:Checkwhetherthe givenscheduleSisconflictserializableornot.
S:R1(A),R2(A),R1(B),R2(B),R3(B),W1(A),W2(B)
Solution
:
Giventhat S: R1(A), R2(A) ,R1(B) , R2(B),R3(B) ,W1(A) ,W2(B).
Theschedulefortheaboveoperationsis
Schedule-1
T1 T2 T3
Read(A)
Read(A)
Read(B)
Read(B)
Read(B)
Write(A)
Write(B)
Listall the conflictingoperations and determinethedependencybetween the transactions
(Thumbruletofindconflictoperations:ForeachWrite(X)inTa,makeapairwitheachRead(X)andWrite(X)inTb.
Theorderisimportantineachpairi.e.,forexample,Read after WriteonXorwriteafterreadonX in thegivenschedule.)

 R2(A), W1(A) (T2→T1)

 R1(B), W2(B) (T1→T2)
 R3(B), W2(B) (T3→T2)
Drawtheprecedencegraph:

Thereexistsacycleinthe above [Link],thescheduleSisnotconflictserializable.

Problem-02:CheckwhetherthegivenscheduleSisconflictserializableschedule.
Schedule– S
T1 T2 T3 T4
Read(X)
Write(X)
COMMIT
Write(X)
COMMIT
Write(Y)
Read(Z)
COMMIT
Read(X)
Read(Y)
COMMIT

Solution:Listalltheconflictingoperationstodeterminethedependencybetween transactions.

R2(X),W3(X) (T2→T3)
W3(X),W1(X) (T3→T1)
W3(X),R4(X) (T3→T4)
R2(X),W1(X) (T2→T1)
W1(X),R4(X) (T1→T4)
W2(Y), R4(Y) (T2→T4)

Drawtheprecedencegraph:

[Link],thescheduleSisconflictserializable.
 ViewSerializability:TwoschedulesS1andS2aresaidtobeviewequivalentifbothof them satisfy the
following three rules:

(1) InitialRead:Thefirst read operationon each data item inboththeschedulemustbesame.

 ForeachdataitemX,IffirstreadonXisdonebytransactionTainscheduleS1,thenin schedule2 also the
first read on X must be done by transaction Ta only.
(2) UpdatedRead:Itshouldbesameinboththeschedules.
 IfRead(X)ofTafollowedby Write(X)ofTbin scheduleS1,thenin scheduleS2also,Read(X) of Ta must
follow Write(X) of Tb ..
(3) Finalwrite:Thefinalwriteoperationon each dataiteminboththeschedulemustbesame.
 ForeachdataitemX,ifXhasbeenupdatedatlastbytransaction T iinscheduleS1,thenin schedule S2 also,
X must be updated at last by transaction Ti.

ViewSerializabilityDefinition:Ifagivenscheduleisviewequivalenttosomeserial
schedule,thenitiscalledasaviewserializableschedule.
Note:Everyconflictserializablescheduleis also viewserializableschedulebut not vice-versa

Problem03:Checkwhetherthe givenscheduleSisviewserializableornot
Schedule–1
T1 T2
Read(A)
Write(A)
Read(A)
Write(A)
Read(B)
Write(B)
Read(B)
Write(B)

Solution:

Forthe givenschedule-1,theserialschedulecanbeschedule-2
Schedule-1(S1) Schedule-2(S2)
T1 T2 T1 T2
Read(A) Read(A)
Write(A) Write(A)
Read(A) Read(B)
Write(A) Write(B)
Read(B) Read(A)
Write(B) Write(A)
Read(B) Read(B)
Write(B) Write(B)
 Nowlet us check whether thethreerules of view-equivalent satisfyornot.
Schedule-1(S1) Schedule-2(S2)
T1 T2 T1 T2
1
Read(A) Read(A) Write(A)
1 Read(B) Write(B)
Write(A)
2 Read(A) 1
3
Write(A)
Read(B) 1 2 Read(A) Write(A) Read(B) Write(B)
3
Write(B)
2 Read(B) Write(B) 2
3 3

Rule1: Initial Read

FirstRead(A)isbyT1inS1andinS2alsothefirstRead(A) isbyT1only.
FirstRead(B)isbyT1in S1andinS2alsothefirstRead(B) isbyT1only.
Rule2:UpdatedRead
Write(A)ofT1isreadbyT2inS1 andinS2alsoWrite(A)ofT1isreadbyT2 Write(A)of T1 is
read byT2 in S1and in S2alsoWrite(A)of T1 is read byT2
Rule3:Final Write
Thefinal Write(A)is byT2in S1andin S2 alsothefinal Write(A)is byT2 only
The final Write(B) is by T2 in S1 and in S2 also the final Write(B) is by T2 only
Conclusion: Hence, all the threerules are satisfied in this example, which means Schedule S1and
S2 are view equivalent. Also, it is proved that schedule S2 is the serial schedule of S1. Thus we
can say that the S1 schedule is a view serializable schedule.

Note:Other way of solving it is, if weare able to prove that S1 is conflict serializable, then S1 isalso view serializable. (Refer
conflict serializable problems. Every conflict serializable schedule is also view serializable but not vice-versa.)

5. IMPLEMENTATIONOFATOMICITYANDDURABILITY
The recovery-management component of a DBMS supports atomicityanddurabilitybya variety of
schemes. The simplest scheme to implement it is Shadow copy.

Shadowcopy: Inshadow-copyscheme,
 Atransactionthatwantstoupdatethedatabasefirstcreatesacompletecopyofthe database.
 Allupdatesaredoneonthenewdatabasecopy,leavingtheoriginalcopy,untouched.
 If at any point the transaction has to be aborted, the system simply deletes the new copy.
The old copy of the database has not been affected.
  If the transaction complete successfully, then the database system updates the pointer db-
pointer to point to the new copy of the database; the new copy then becomes the original
copy of the database. The old copy of the database is then deleted. Figure below depicts
the scheme, showing the database state before and after the update.

Figure:Shadowcopytechniqueforatomicityand durability

6. RECOVERABILITY
During execution, if any of the transaction in a schedule is aborted, then this may leads
the database into inconsistence state. If anything goes wrong, then the completed operations in
the schedule needs to be undone. Sometimes, these undone operations may not possible. The
recoverability of schedule depends on undone operations.

If a transaction
Irrecoverable readsIna data
Schedule: value that
a schedule, if isa updated by anT auncommitted
transaction performs a transaction,
dirty read operation
fromothertransactionT andTisacommitsbeforeT
thenthis type of bread called as a dirtybthensuchascheduleisknownas
read. an Irrecoverable
Schedule.
Example:Considerthefollowingschedule
T1 T2
Read(A)
Write(A)
|
| Read(A) //DirtyRead
| Write(A)
| COMMIT
|
ROLLBACK
Here,
 T2performsa dirtyreadoperation.
  T2commitsbeforeT1.
 T1failslaterandrollbacks.
 Thevalue that T2 read now stands to beincorrect.
 T2cannot recoversinceithasalreadycommitted.

Recoverable Schedules:In a schedule, if a transaction Taperforms a dirty read operation

from other transaction TbandTacommit operation delayed till Tbcommit, then such a schedule is
known as an Irrecoverable Schedule.

Example:Considerthefollowingschedule-

T1 T2
Read(A)
Write(A)
|
| Read(A) //DirtyRead
| Write(A)
|
COMMIT

COMMIT//Delayed

Here,
 T2performsa dirtyreadoperation.
 Thecommitoperationof T2is delayedtillT1commitsorroll backs.
 T1commitslater.
 T2isnow allowedtocommit.
 Incase,T1wouldhavefailed,T2hasachancetorecoverbyrollingback.

Checking Whether a Schedule is Recoverable or

Irrecoverable:Check if there exists any dirty read operation.
 Iftheredoes not exist anydirtyread operation, then theschedule is surelyrecoverable.
 Ifthereexistsanydirtyread operation, then
 If the commit operation of thetransactionperformingthedirtyread occurs before
thecommitorabortoperationofthetransactionwhichupdatedthevalue,thenthe
schedule is irrecoverable.
 If the commit operation of the transaction performing the dirty read is delayed till
the commit or abort operation of the transaction which updated the value, then the
schedule is recoverable.
 7. IMPLEMENTATIONOFISOLATION
Isolation determines how transactions integrityis visible to otherusers and systems. It means
that a transaction should take place in a system in such a way that it is the only one transaction
that is accessing the resources in a database system.

Isolation level defines the degree to which a transaction must be isolated from the data
modifications made by any other transactions in the database system. The phenomena’s used to
define levels of isolation are:

a) Dirty Read
b) Non-repeatableRead
c) PhantomRead

Dirty Read: If a transaction reads a data value updated by an uncommitted transaction, then this
type of read is called as dirty read.

T1 T2
Read(A)
Write(A)
|
| Read(A) //DirtyRead
| Write(A)
| COMMIT
|
ROLLBACK

As T1 aborted, the results produced by T2 become wrong. This is because T2 read A (Dirty Read)
which is updated by T1.
Non-RepeatableRead:Nonrepeatableread occurs when atransaction read same data value twice
and get a different value each time. It happens when a transaction reads once before and once
after committed UPDATES from another transaction.
TableinDatabase
T1 T2
ReadA=10
Read(A)
A
WriteA=20
Write(A)
ReadA=20
Read(A)
First,T1readsdataitemAandgetA=10 Next, T2
writes data item A as A = 20
Last,T1readsdataitemAandgetA=20
 OtherexampleforNon-repeatable read:
Table:STUDENT_DATAbeforeT2 Table:STUDENT_DATAafter T2
A B C A B C
100 5 10 100 5 15
101 5 20 101 5 20
102 6 30 102 6 30

T1:SELECTSUM(C)FROMSTUDENT_DATAWHEREB=5; Answeris(10+20)=30
T2: UPDATE STUDENT_DATA SET C = 15 WHEREA=100; Answer,inFirstrowCchangesto15 T1:
SELECT SUM(C ) FROM STUDENT_DATA WHEREB=5; Answer is (15+20) = 35

Phantomreads: Phantom reads occurs when atransaction read same datavaluetwiceand get a
different value each time. It happens when a transaction reads once before and once after
committed INSERTS and/or DELETES from another transaction.
Non-repeatableread Phantomread
WhenT1performsecondread,thereisno WhenT1performsecondread,thenoofrows
changeinnoofrowsinthegiventable eitherincreaseordecrease.
T2performUPDATEoperationonthe T2 perform INSERT and/or DELETE
giventable operationonthegiventable

ExampleforPhantomread:
Table:STUDENT_DATAbeforeT2 Table:STUDENT_DATAafter T2
A B C A B C
100 5 10
100 5 10 101 5 20
101 5 20 102 6 30
103 5 25

T1:SELECTSUM(C)FROMSTUDENT_DATAWHEREB=5; Answeris(10+20)=30
T2:INSERT INTOSTUDENT_DATAVALUES(103,5,25); Answer,inFirstrowCchangesto15
T1:SELECTSUM(C)FROMSTUDENT_DATAWHEREB=5; Answeris(10+20+25)=55

Basedonthesethreephenomena, [Link]:
(1) Read uncommitted: This is the lowest level of [Link] this level, one transaction
mayreadthedataitemmodifiedbyothertransactionwhichisnotcommitted. Itmeandirty read is
allowed. In this level, transactions are not isolated from each other.
 (2) Read Committed: This isolation level guarantees that any data read is committed at the
moment it is read. Thus, it does not allow dirty read. The transaction holds a read/write lock
on the data object, and thus prevents other transactions from reading, updating or deleting it.
(3) Repeatable Read: This is the most restrictive isolation level. The transaction holds read
locks on all rows it references and writes locks on all rows it inserts, updates, or deletes.
Since other transaction cannot read, update or delete these rows, consequently it avoids non-
repeatable read. So other transactions cannot read, update or delete these data items.
(4) Serializable: This is the highest isolation level. A serializable execution is guaranteed to
be a serial schedule. Serializable execution is defined to be an execution of operations in
which concurrently executing transactions appears to be serially executing.
The table given below clearly depicts the relationship between isolation levels and the read
phenomena and locks.
Isolation Level DirtyRead Non-repeatableread PhantomRead
ReadUncommitted Mayoccur Mayoccur Mayoccur
ReadCommitted Don’toccur Mayoccur Mayoccur
RepeatableRead Don’toccur Don’toccur Mayoccur
Serializable Don’toccur Don’toccur Don’toccur
Fromtheabovetable, itisclearthatserializableisolationlevelisbetterthanothers.

8. CONCURRENCYCONTROL
 Concurrencyistheabilityofadatabasetoexecutemultiple transactions simultaneously.
 Concurrency controlisamechanismtomanagethesimultaneouslyexecutingmultiple
transactions such that no transaction interfere with other transaction.
 Executingmultipletransactionsconcurrentlyimprovesthesystemperformance.
 Concurrencycontrolincreasesthethroughputand reduces waitingtimeoftransactions.
 If Concurrency Control is not done, then it may leads to problems like lost updates, dirty
read, non-repeatable read, phantom read etc. (Refer section7 for more details)
 Lost Updates: It occur when two transactions update same data item at thesame time. In
this the first write is lost and only the second write is visible.
ConcurrencycontrolProtocols:
Theconcurrencycan be controlled with thehelpofthefollowingProtocols
(1) Lock-BasedProtocol
(2) Timestamp-BasedProtocol
(3) Validation-BasedProtocol
9. LOCK-BASEDPROTOCOL
 Lock assures that one transaction should not retrieve or update a record which another
transaction is updating.
 For example, traffic at junction, there aresignals which indicate stop and go. When one side
signal is green (vehicles allowed passing), then other side signals are red (locked. Vehicles
not allowed passing). Similarly, in database transaction when one transaction operations are
under execution, the other transactions are locked.
 If at a junction, green signal is given to more than one side, then there may be chances of
accidents. Similarly, in database transactions, if the lockingis not done properly, then it will
display the inconsistent and corrupt data.
Therearetwolockmodes: (1).SharedLock (2).ExclusiveLock
[Link],thenTi
can only read A but not write into A. Shared lock is requested using lock-S
[Link] represented by X. If a transaction Tiapply exclusive lock on data
item A,[Link]-X instruction.

LockCompatibilityMatrix:
 LockCompatibilityMatrixcontrolswhethermultipletransactionscanacquirelockson the
same resource at the same time.
TransactionTiapplied
Shared Exclusive
TransactionTj Shared √ X
request for Exclusive X X
 If a transaction Tiapplied shared lock on data item A, then Tjcan also be allowed to apply
shared lock on A.
 If a transaction Tiapplied shared lock on data item A, then Tjis not allowed to apply
exclusive lock on A.
 If a transaction Tiapplied exclusive lock on data item A, then Tjis not allowed to apply
shared lock on A.
 If a transaction Tiapplied exclusive lock on data item A, then Tjis not allowed to apply
exclusive lock on it.
 Any number of transactions can hold shared locks on a data item, but if any transaction
holdsanexclusivelockonadataitem,thenothertransactionsarenotallowedtoholdany lock on
that data item.
  Whenever a transaction wants to read a data item, it should applyshared lock and when a
transaction wants to write it should apply exclusive lock. If the lock is not applied, then
the transaction is not allowed to perform the operation.

[Link]:

(1) Simplisticlockprotocol

 Itisthesimplestlockingprotocol.
 Itconsiderseachread/writeoperationofatransactionasindividual.
 Itallowstransactionstoperformwrite/readoperationonadataitemonlyafterobtaining a lock
on that data item.
 Transactionsunlockthedataitemimmediatelyaftercompletingthewrite/read operation.
 When atransaction needs to perform manyread and writeoperations, foreach operation
lockisappliedbeforeperformingitandreleasethelockimmediatelyaftercompletionof the
operation.
(2) Pre-claimingLockProtocol
 Inpre-claimingLockProtocol,foreachtransactionalistispreparedconsistingofthe data items
and type of lock required on each of the data item.
 Beforeinitiatinganexecutionofthetransaction,itrequestsDBMStoissuealltherequired locks
as per the list.
 [Link] transaction
is completed then it releases all the lock.
 If all the locks are not granted then this protocol allows the transaction to rolls back and
waits until all the locks are granted.
Nooflock

Beginof Endof
Transaction Transaction

(3) Two-phaselocking(2PL)protocol
 Everytransaction execution starts byacquiringfew locks or zero locks. Duringexecution it
acquire all other required locks one after the other.
  When a transaction releases any of the acquired locks then it cannot acquire any more
newlocks. But,itcanonlyreleasetheacquiredlocksoneaftertheotherduringremaining
execution of that transaction.

Nooflock
GrowingPhase ShrinkingPhase

Beginof Endof
Transaction Transaction

TheTwoPhaseLocking(2PL)[Link]:
Growingphase:Inthegrowingphase,anewlockonthedataitemmaybeacquiredbythe transaction, but
none can be released.(Only get new locks but no release of locks).

Shrinkingphase:Intheshrinkingphase,existinglockheldbythetransactionmaybereleased, but no new

locks can be acquired. (Only release locks but no more getting new locks).

Example:
Time T1 T2
0 LOCK-S(A)
1 LOCK-S(A)
2 Read(A)
3 Read(A)
4 LOCK-X(B)
5 --
6 Read(B)
7 B=B +100
8 Write(B)
9 UNLOCK(A)
10 LOCK-X(C)
11 UNLOCK(B) --
12 Read(C)
13 C=C+500
14 Write(C)
15 COMMIT
16 UNLOCK(A)
17 UNLOCK(C)
18 COMMIT

Thefollowingwayshowshow unlockingandlockingworkwith2-PL.
TransactionT1:
 Growingphase:fromstep1-5 (Afterfirstlockonwards)
TransactionT2:
 Shrinkingphase:fromstep10-12(Afterfirstunlockonwards)  Growingphase:fromstep2-11 (Afterfirstlockonwards)
 Lockpoint:at5 (Nomorenewlocks)  Shrinkingphase:fromstep17-18(Afterfirstunlockonwards)
 Lockpoint:at11 (Nomorenewlocks)
 (4) StrictTwo-phaselocking(Strict-2PL)protocol
 The firstphase of Strict-2PL issimilar [Link] the firstphase,after acquiring allthe locks,
the transaction continues to execute normally.
 The onlydifference between 2PL and strict 2PL is that Strict-2PL does not release a lock
after using it.
 Strict-2PLwaitsuntilthewholetransactionto commit,andthenitreleasesallthelocksat a time.
 Strict-2PLprotocol doesnothaveshrinkingphaseoflockrelease.
Nooflock

GrowingPhase
BeginofTransaction
Endof
Transaction

Strict-2PLdoes not havecascadingabort as 2PLdoes.

10. TIMESTAMPBASEDPROTOCOL
 Atimestampisissuedtoeachtransactionwhenitentersintothesystem.
 Ituseseithersystemtimeorlogicalcounterasatimestamp.
 Itis most commonlyusedconcurrencyprotocol.
 Thetimestampoftransaction Tis denotedasTS(T).
 The system order the transactions based on their arrival time. For example, let the arrival
timesoftransactionsT1,T2andT3be9:00AM,9:01AMand9:[Link] TS(T1)
< TS(T2) < TS(T3).(9:00AM < 9:01AM < 9:02AM)
 Byusingtimestamp, thesystempreparestheserializabilityorder.i.e., T1→T2→T3
 Thereadtimestampofdata item XisdenotedbyR–timestamp(X).
 R–timestamp(X):Itisthe time stamp of theyoungesttransaction that performedread
operation on X.

T1:Read(X)
X T2: Read(X) R-Timestamp(X)=TS(T3)

T3:Read(X)
  Thewritetimestampofdata item X is denoted byW–timestamp(X).
 W–timestamp(X): It is the time stamp of the youngest transaction that performed write
operation on X.
T1:Write(X)

X R-Timestamp(X)=TS(T2)
T2:Write(X)

There aremainlytwo Timestamp OrderingAlgorithmsin DBMS. Theyare:

 BasicTimestampOrdering
 ThomasWriterule

(1). BasicTimestampOrdering
 CheckthefollowingconditionwheneveratransactionTiissuesaRead(X)operation:
o IfW_timestamp(X)>TS(Ti)thentheoperationisrejected.
o IfW_timestamp(X)<= TS(Ti)thentheoperationisexecuted.
(ReadisnotallowedbyTi, ifanyyoungertransactionsthanTiwriteX)

 CheckthefollowingconditionwheneveratransactionTiissuesaWrite(X)operation:
o IfTS(Ti)<R_timestamp(X)thentheoperationisrejected.(WriteisnotallowedbyTi,if any
younger transactions than Ti read X)

o If TS(Ti) < W_ timestamp(X) then the operation is rejected and Ti is rolled back
otherwisetheoperationisexecuted.(WriteisnotallowedbyTi,ifanyyoungertransactionsthan Ti write
X and also Ti should be rolled back and restarted later)

(2) Thomas'sWriteRule
ThomasWriteRuleisatimestamp-basedconcurrencycontrolprotocolwhichignores outdated writes.
It follows the following steps:

(i). IfR_TS(X)>TS(Ta),thenabortandrollbackTaandrejectthe operation.

Transaction:T1 Transaction:T2 VariableA
Arrival=9:00 AM Arrival=9:02AM InitialA=100
TS(T1)=9:00 AM TS(T1)=9:02AM
| |
| Read(A)(A=100) A=100 (R_TS(A)=9:02AM)
| | :
Write(A) (A=200) | (A=100) A=200100

RejectandRollbackT1
 (ii). If W_TS(X)>TS(Ta), thendon’texecutetheWriteOperationofTabutcontinueTa
[Link].
Transaction:T1 Transaction:T2 VariableA
Arrival=9:00 AM Arrival=9:02AM InitialA=100
TS(T1)=9:00 AM TS(T1)=9:02AM
| |
| Write(A)(A=400) A=400 (W_TS(A)=9:02AM)
| | :
Write(A) (A=500) | (A=400) A=500 (Outdatedwrite)
|
RejectbutcontinueT1 |
| |

(iii). Iftheconditionin(i)or(ii)isnotsatisfied,thenexecuteWrite(X)ofTaandset W_TS(X) to

TS(Ta).
OutdatedwritesarerejectedbutthetransactioniscontinuedinThomasWriteRulebutinBasic TO
protocol will reject write operation and terminate such a Transaction.

11. VALIDATIONBASEDPROTOCOL
In this technique, no concurrency control checking is done while the transaction is under
execution. After transaction execution is completed, then only whether concurrency violated or
not is [Link] is based on timestamp based protocol. Validation Based Protocol has three
phases:
1. Readphase: Inthisphase,thetransactionTareadthevalueofvariousdata items thatare
required by Taand stores them in temporary local variables. It can perform all the write
operations on temporary variables without an update to the actual database.
1. Validation phase: After Transaction Taexecution completed, Taperform a validation test
to determine whether it can copy the temporary local variable values to actual database
without causing a violation of serializability.
2. Write phase: If the validation of the transaction is successful (valid), then the temporary
results are written to the database. Otherwise the temporary local variable values of Tais
ignored and Tais rolled back.

To perform the validation test, we need to know when the various phases of transaction Tatook
place. We shall therefore associate three different timestamps with transaction Ta.
(i). Start(Ta): thetimewhenTa,started its execution.
(ii). Validation (Ta): the time when Tafinished its execution and started its
validation phase.
 (iii). Finish (Ta):thetimewhenTafinisheditswritephase.
TheserializabilityorderisdeterminedbychangingthetimestampofTas TS(T)=Validation(T). Hence the
serializability is determined at the validation process and cannot be decided in advance.
Therefore it ensures greater degree of concurrency while executing the transactions.

12. MULTIPLEGRANULARITY
[Link] levels in the
DBMS. They are:
 Database
 Table
 Record/row
 Cell/field value

TableA TableB TableD

RecordR2
RecordR4

TableE
TableC
Cell/FieldValue

Cell/FieldValue

A database contains multiple tables. Each table contains multiple records. Each record contains
multiple field values. It is shown in the above figure. For example, consider Table D and Record
R2. These two are not mutually exclusive. R2 is a part of D. So granularity means
differentlevelsofdatawhere as smallerlevelsarenestedinsidethehigherlevels.
Insidedatabasewehave tables. Inside table we have records. Inside record we have field values.
This can be represented with a tree as shown below.

DB

A B C D Tables

. . ... .. . . . ..
r1r2 r3 r4 Records

. .. Data values
d1d2 d3d4 . . ... .. . .
A lock can be applied at a node, if and only if there does not exist any locks on the decedents
(childs and grand childs) of that node. Otherwise lock cannot be applied. If lock is applied on
table A, it implies that the lack is also applicable to sub-tree from node A. If lock is applied on
database (at root node), it implies the lack is also applicable to all the nodes in the tree.

The larger the object size on which lock is applied, the lower the degree of concurrency
permitted. Onthe other hand, thesmallerthe object sizeon which lockis applied, thesystem has to
maintain larger number of locks. More locks cause a higher overhead and needs more disk space.
So, what is the best object size on which lock can be applied? It depends on the types of
transactions involved. If a typical transaction accesses data values from a record, it is
advantageous to have the lock to that one record. On the other hand, if a transaction typically
accesses many records in the same table, it may be better to have lock at that table.

Locking at higher levels needs lock details at lower levels. This information is provided by
additional types of locks called intention locks. The idea behind intention locks is for a
transaction to indicate, along the path from the root to the desired node, what type of lock(shared
or exclusive) it will require from one of the node’s descendants. There are three types of
intention locks:
(1) Intention-shared(IS):Itindicatesthatoneormoresharedlockswillberequestedon some
descendant node(s).
(2) Intention-exclusive (IX): It indicates that one or more exclusive locks will be requested
on some descendant node(s).
(3) Shared-intention-exclusive (SIX): It indicates that the current node is locked in shared
modebutthatoneormoreexclusivelockswillberequestedonsomedescendantnode(s).
The compatibility table of the three intention locks, the shared and exclusive locks, is shown in
Figure.
Mode IS IX S SIX X
IS Yes Yes Yes Yes No
IX Yes Yes No No No
S Yes No Yes No No
SIX Yes No No No No
X No No No No No

It uses the intention lock modes to ensure serializability. It requires that if a transaction attempts
to lock a node, then that node must follow these protocols:
  TransactionT1shouldfollowthelock-compatibilitymatrix.
 TransactionT1 [Link] in anymode.
 IfT1currentlyhastheparentofthenodelockedineitherIXorISmode,thenthe transaction T1
will lock a node in S or IS mode only.
 IfT1currentlyhastheparentofthenodelockedineitherIXorSIXmodes,thenthe transaction T1
will lock a node in X, SIX, or IX mode only.
 IfT1hasnotpreviouslyunlockedanynodeonly,thentheTransactionT1canlocka node.
 If T1currentlyhasnoneof thechildrenofthenode-lockedonly,thenTransactionT1will unlock
a node.
Note:Inmultiple-granularity,thelocksareacquiredintop-downorder,andlocksmustbe released in
bottom-up order.

13. RECOVERYANDATOMICITY
Databaseneedstoberecovered, whenthefollowingfailuresoccur.
(1) Transactionfailure
(2) System crash
(3) Disk failure
 Transaction failure: During transaction execution, if it cannot proceed further, then it needs
to abort. This is known as transaction failure. A single transaction failure may influencemany
transactions or processes. The reasons for transaction failure are:
 Logicalerrors:Itoccursduetosomecodeerrororaninternalconditionerror.
 Systemerror: ItoccurswhentheDBMSitselfterminatesanactivetransactiondueto
deadlock or resource unavailability.
 System crash: The system may crash due to the external factors such as interruptions in
power supply, hardware or software failure. Example:Operating System errors.
 Disk failure: In early days of technology evolution, hard-disk drives or storage drives usedto
fail frequently. Disk failure occurs due to the formation of bad sectors, disk head crash,un-
reachable to the disk or any other failure which destroys all or part of disk storage.

When a system crashes, it may have many transactions being executed and many files may be
opened for them. When a DBMS recovers from a crash, it must maintain the following:
 Itmustcheckthestatesofallthetransactionsthatwerebeingexecuted.
  Few transactions may be within the middle of some operation; the DBMS should
makesure the atomicity of the transaction during this case.
 Itmustcheck foreach transactionwhetheritsexecutionacceptedortoberolledback.
 Notransactionisallowedtobeinaninconsistentstate.

The following techniques facilitate a DBMS in recovering as well as maintaining the atomicityof a
transaction:
 Logbasedrecovery
 Check point
 Shadowpaging

14. LOGBASEDRECOVERY
The log file contains information about the start and end of each transaction and any updates done by
the transaction on database items. The log file is saved onto some stable storage so that if any failure
occurs, then it can be used to recover the database. The results of all the operation of transaction are first
saved in the log and latter updated on the database. The log information is used to recover from system
failures.

[Link].
 WhenatransactionTistartsexecution, thelogstores:<Ti, Start>
 WhenatransactionTimodifiesanitemXfromoldvalueV1tonewvalueV2,thelog stores:<Ti,
X, V1, V2>
 WhenthetransactionTiexecutioncompleted, thelogstores: <Ti,commit>
 WhenthetransactionTiexecutionaborted,thelogstores:<Ti,abort>
RecoveryusingLogrecords
Whenthesystemiscrashed,thentheDBMSchecksthelogtofindwhichtransactionsneedsto be undo and
which need to be redo. There are two major techniques for recovery from non-catastrophic
transaction failures. They are deferred updates and immediate updates.
i. Deferred database modification:In this technique, all the changes done by the
transaction are saved in the system log without modifying the actual [Link] the
transaction committed, then onlythe changes are updated in the database. If a transaction
failsbeforereachingitscommitpoint,ithasnotchangedthedatabaseinanywayso
 UNDO is not needed. It may be necessary to REDO the effect of the operations that are
recorded in the system log, because their effect not yet written in the database.
ii. Immediate database modification: In this technique, the database is modified
immediately after every operation. However, these operations are recorded in the log file
before they are applied to the database, making recovery still possible. If a transaction
fails to reach its commit point, the effect of its operation must be undone i.e. the
transaction must be rolled back hence we require both undo and redo.

15. CHECKPOINT–(RecoverywithConcurrentTransactions)
 Inordertorecoverdatabasefromsystemcrashes, allthetransactionoperationsarefirstsaved in the
log file and latter updated on the database. The log file is saved in remote location so that it
can be used to recover the database. As time passes, the entries in the log file maygrow too
[Link] the time of recovery, searching the entire log file is very time consuming and an
inefficient method. To ease this situation, the concept of 'checkpoint' is introduced.
 Checkpoint is a mechanism where all the previous log entries are removed from the log file
and their results are updated in the database. The checkpoint is like a bookmark.
 During the execution of the transactions, after executing few operations, a check point is
created and saved in the log file. Now the log file contains only entries after checkpoint
related to new step of transaction till next checkpoint and so on.
 Thecheckpoint is used to declare apoint before which theDBMS was in theconsistent state,
and all transactions were committed.
RecoveryusingCheckpoint
Inthefollowingmanner, arecoverysystemrecoversthedatabasefromthisfailure:
Checkpoint Failure

T1

T2
T3
T4
Time
 Therecoverysystem reads thelogs backwards from theend to thelastcheckpoint.
 Itmaintainstwolists,anundo-listandaredo-list.
  If the recovery system sees a log with <Ti, Start> and <Ti, Commit> or just <Ti,
Commit>, it puts the transaction Tiin the redo-list.
Forexample: Inthelogfile,transactionT1haveonly<Ti,commit>andthetransactions T2 and T3
have <Ti, Start> and <Ti, Commit>. Therefore T1, T2 and T3 transaction are added to the
redo list.
 If the recovery system finds a log with <Ti, Start> but no commit or abort, then it putsthe
transaction Tiin undo-list.
For example: Transaction T4 will have <Ti, Start>. So T4 will be put into undo listsince this
transaction is not yet complete and failed in the middle.
 Allthetransactionsintheundo-list arethenundoneandtheirlogsareremoved.
 All the transactions in the redo-list and their previous logs are removed and then redone
before saving their logs.

16. ARIES ALGORITHM (Algorithm for Recovery and Isolation Exploiting Semantics)
AlgorithmforRecoveryandIsolationExploitingSemantics(ARIES)isoneofthelogbased recovery
method. It uses the Write Ahead Log (WAL) protocol.

Write-ahead logging (WAL): In computer science, write-ahead logging (WAL) is a family of

techniques for providing atomicity and durability (two of the ACID properties) in database
systems. The change done by the transactions are first recorded in the log file and written to
stable storage at remote location, before the changes are written to the database.
TherecoveryprocessofARIESalgorithmhas 3 phases. Theyare:
(1) Analysisphase
(2) RedoPhase
(3) Undo Phase

Startofoldestin-progress
SmallestLSNassociated
transaction with dirty page Lastcheckpoint EndofLog Log Time

AnalysisPhase
Redo Phase

Undophase
 (1) Analysis phase: The recovery subsystem scans the log file forward from the last checkpoint
up to the end. The purpose of the scan is to obtain information about the following:
 Thestartingpointfromwheretheredopassshouldstart.
 Thelistoftransactionstoberolledbackintheundopass.
 Thelistofdirtypages.
(2) Redo: In this phase, the log file is read forward starting from smallest LSN of a dirtypage to
the end and each update found in the log file is redone. The purpose of this redo pass is to
repeat the historyto reconstruct the database to the state present at the time of system failure.
(3) Undo:[Link] ‘loser
transaction’ updates are rolled back in reverse chronological order. If any of the aborted
transaction operations are undone, then skip them, no need to undo once again.

17. DATABASEBACKUP
The process of creating duplicate copy of database is called database backup. Backup
helps to recover against failure of media, hardware or software failures or any other kind of
failures that cause a serious data crash.

Database copy is created and stored in the remote area with the help of network. This
database is periodically updated with the current database so that it will be in sync with data and
other details. This remote database can be updated manually called offline backup. It can be
backed up online where the data is updated at current and remote database simultaneously. Inthis
case, as soon as there is a failure of current database, system automatically switches to the
remote database and starts functioning. The user will not know that there was a failure.

Primarysite Backup
Network
Someofthebackuptechniquesareasfollows:

 Full backup or Normal backup: Full backup is also known as Normal backup. In this,
an exact duplicate copy of the original database is created and stored every time the
backup made. The advantage of this type of backup is that restoring the lost data is very
fast as compared to other. The disadvantage of this method is that it takes more time to
backup.
 Incremental Backup:Instead of backup entire database every time, backup only the
files that have been updated since the last full [Link] this at least weekly once
normal backup has to be done. While incremental database backups do run faster, the
recovery process is a bit more complicated.
 Differential backup: Differential is similar to incremental backup but the difference is
that the recovery process is simplified by not clear the archive bit. So a file that isupdated
after a normal backup will be archived every time a differential backup is run until the
next normal backup runs and clears the archive bit.
 UNIT– V
Data on External Storage, File Organization and Indexing, Cluster Indexes, Primary and Secondary Indexes, Index data Structures,
Hash Based Indexing, Tree base Indexing, Comparison of File Organizations, Indexes and Performance Tuning, Intuitions for
tree Indexes, Indexed Sequential Access Methods (ISAM), B+ Trees: A Dynamic Index Structure.

1. DATAONEXTERNALSTORAGE
Primarymemoryhaslimitedstoragecapacityand is volatile. Toovercomethis limitation,
secondary memory is also termed as external storage devices are used. External storage devices
such as disks and tapes are used to store data permanently.

The Secondary storage devices can be fixed or removable. Fixed Storage device is an
internal storage device like hard disk that is fixed inside the computer. Storage devices that are
portable and can be taken outside the computer are termed as removable storage devices such as
CD, DVD, external hard disk, etc.

Magnetic/opticalDisk:[Link].
MagneticTapes:[Link].
In DBMS, processing a queryand getting output need accessing random pages. So, disks
are preferable than magnetic tapes.

2. FILEORGANIZATION
The database is stored as a collection of files. Each file contains a set of records. Each record
is a collection of fields. For example, a student table (or file) contains many records and each
record belongs to one student with fields (attributes) such as Name, Date of birth, class,
department, address, etc.

Fileorganizationdefineshowfilerecordsaremappedontodiskblocks.

The records of a file are stored in the disk blocks because a block is the unit of data transfer
between disk and memory. When the block size is larger than the record size, each block will
contain more than one record. Sometimes, some of the files may have large records that
[Link],wecanstorepartofarecordononeblockandthereston another. A
pointer at the end of the first block points to the block containing the remainder of the record.

Thedifferenttypesoffileorganizationaregivenbelow:
 HeapFile SequentialFile
Organization Organization

File
Organization

Hash File ClusteredFile

Organization Organization

Heap File Organization: When a file is created using Heap File Organization mechanism, the
records are stored in the file in the order in which they are inserted. So the new records are
inserted at the end of the file. In this type of organization inserting new records is more efficient.
It uses linear search to search records.

Sequential File Organization: When a file is created using Sequential File Organization
mechanism, all the records are ordered (sorted) as per the primary key value and placed in the
file. In this type of organization inserting new records is more difficult because the records need
to be sorted after inserting every new [Link] uses binary search to search records.

Hash File Organization: When a file is created using Hash File Organization mechanism, ahash
function is applied on some field of the records to calculate hash value. Based on the hash value,
the corresponding record is placed in the file.

Clustered File Organization: Clustered file organization is not considered good for large
databases. In this mechanism, related records from one or more relations are kept in a same disk
block, that is, the ordering of records is not based on primary key or search key.

3. INDEXING
If the records in the file are in sorted order, then searching will become very fast. But, in
most of the cases, records are placed in the file in the order in which they are inserted, so new
records are inserted at the end of the file. It indicates, the records are not in sorted order. In
order to make searching faster in the files with unsorted records, indexing is used.

Indexing is a data structure technique which allows you to quickly retrieve records from a
database file. An Index is a small table having only two columns. The first column contains a
copy of the primary or candidate key of a table. The second column contains a set of disk block
addresses where the record with that specific key value stored.
 IndexinginDBMScan be ofthefollowingtypes:

Indexing

PrimaryIndexing SecondaryIndexing ClusteringIndexing

Dense Indexing SparseIndexing

i. PrimaryIndex
 If the index is created by using the primary key of the table, then it is known as primary
indexing.
 Asprimarykeysareuniqueandarestoredinasortedmanner,theperformanceofthe searching
operation is quite efficient.
 Theprimaryindexcanbeclassifiedintotwo types: denseindexandsparseindex.

Denseindex
 If every record in the table has one index entry in the index table, then it is called
denseindex.
 In this, the number of records (rows) in the index table is same as the number of records
(rows) in the main table.
 Aseveryrecordhasoneindexentry, searchingbecomesfaster.

TS TS Hyderabad KCR
AP AP Amaravathi Jagan
TN TN Madras PalaniSwamy
MH MH Bombay Thackray

Sparse index
 Ifonlyfewrecordsinthetablehaveindexentriesintheindextable,thenitiscalled sparse index.
 In this, the number of records (rows) in the index table is less than the number of records
(rows) in the main table.
 Asnotalltherecordhaveindexentries,searchingbecomesslowforrecordsthatdoesnot have
index entries.
 TS TS Hyderabad KCR
TN AP Amaravathi Jagan
MH TN Madras PalaniSwamy
MH Bombay Thackray

ii. Secondary Index

When the sizeofthe main table grows, then sizeofindextablealso grows. If theindextablesize grows
then fetching the address itself becomes slower. To overcome this problem, secondary indexing
is introduced.

 Insecondaryindexing, toreducethesizeofmapping, another levelofindexingisintroduced.

 Itcontainstwolevels. Inthefirstleveleachrecordinthemaintablehasoneentryinthefirst-level index
table.
 The index entries in the fisrt level index table are divided into different groups. For each
group, one index entry is created and added in the second level index table.

Multi-levelIndex:Whenthemaintablesizebecomestoolarge,creatingsecondarylevelindex improves
the search [Link] if the search process is slow; we can add one more level of indexing and
so on. This type of indexing is called multi-level index.
iii. ClusteringIndex
 Sometimestheindexiscreatedonnon-primarykeycolumnswhichmaynotbeunique for
each record.
 Inthiscase,toidentifytherecordfaster,wewillgrouptwoormorecolumnstogetthe unique
value and create index out of them. This method is called a clustering index.
 Therecordswhichhavesimilarcharacteristicsaregrouped,andindexesare createdfor these
group.

Example:Consideracollegecontainsmanystudentsineachdepartment. Allthestudentsbelong to the

same Dept_ID are grouped together and treated as a single cluster. One index pointers point to
the one cluster as a whole. The idex pointer points to the first record in each cluster.HereDept_ID
is a non-unique key.

IndexFile Recordsoftableinmemory
CSE 501 Ajay BCD
ECE 502 Ramya BCA
EEE … … …
… 560 Fathima BCE
401 VijayReddy OC
… … …
460 Mallesh ST
201 Jhon SC
… … …
260 Sowmya BCC
… … …
… … …

In above diagram we can see that, indexes are created for each department in the index
file. In the data block, the students of each department are grouped together to form the cluster.
The address in the index file points to the beginning of each cluster.

4. HASHBASEDINDEXING
Hashing is a technique to directly search the location of desired data on the disk without
using index structure. Hash function is a function which takes a piece of data ( key) as input and
produces a hash valueas output which maps the data to a particular location in the hash table.
 Theconcept of hashingandhash table is showninthebelowfigure

There aremainlytwotypesof hashing methods:

i. Static Hashing
ii. DynamicHashing
 Extendedhashing
 Linearhashing

5. STATICHASHING
Instatichashing,[Link] example
consider the hash function
f(x)= x mod 7
Foranyvalueofx, theabovefunctionproducesoneofthehashvaluefrom{0,1,2, 3,4, 5,6}. It means
static hashing maps search-key values to a fixed set of bucket addresses.

Example:Inserting10,21,16and12inhash table.

HashValue DataRecord
f(10)=10 mod7=3
0 21*
f(21)=21 mod7=0 1
f(16)=16mod 7=2 2 16*
f(12)=12 mod7=5 3 10*
4
5 12*
6

Figure5.1:Statichashing
 Suppose, latter if we want to insert 23, it produce hash value as 2 ( 23 mod 7 = 2 ). But, in the
above hash table, the location with hash value 2 is not empty (it contains 16*). So, a collision
occurs. To resolve this collision, the following techniques are used.
o Open addressing
o SeparateChainingorClosedaddressing

i. Open Addressing:

Openaddressingisacollisionresolvingtechniquewhichstoresallthekeysinsidethe hash table. No

key is stored outside the hash table. Techniques used for open addressing are:

o LinearProbing
o QuadraticProbing
o DoubleHashing

 LinearProbing:

In linear probing, when there is a collision, we scan forwards for the next empty slot to
fill the key’s record. If you reach last slot, then start from beginning.

Example: Consider figure 1. When we try to insert 23, its hash value is 2. But the slotwith
2 is not empty. Then move to next slot (hash value 3), even it is also full, then move once
again to next slot with hash value 4. As it is empty store 23 there. This is shown in the
below diagram.

HashValue DataRecord

0 21*

f(23)=23 mod7=2 2 16*

3 10*

4 23*

5 12*

Figure5.2:LinearProbing
 QuadraticProbing:

In quadratic probing, when collision occurs, it compute new hash value by taking the
original hash value and adding successive values of quadratic polynomial until an open
slot is found. If here is a collision, it use the following hash function: h(x) = ( f(x) + i 2 )
mod n ,where I = 1, 2, 3, 4,….. and f(x) is initial hash value.

Example: Consider figure 1. When we try to insert 23, its hash value is 2. But the slot
with hash value 2 is not empty. Then compute new hash value as (2 +1 2) mod 7 =3, even
it is also full, and then once again compute new hash value as (2 +2 2) mod 7 = 6. As it is
empty store 23 there. This is shown in the below diagram.

Hash
DataRecord
Value

0 21*

f(23)=23 mod7=2 2 16*

3 10*

5 12*

6 23*

Figure5.3:Quadratic Probing

 DoubleHashing

In double hashing, there are two hash functions. The second hash function is used to
provide an offset value in case the first function causes a collision. The followingfunction
is an example of double hashing: (firstHash(key) + i * secondHash(key)) % tableSize.
Use i = 1, 2, 3, …

Apopularsecondhashfunctionis: secondHash(key)=PRIME–(key%PRIME)
wherePRIMEisaprimesmallerthantheTABLE_SIZE.
 Example:[Link] toinsert23,[Link] with hash
value 2 is not empty. Then compute double hashing value as
secondHash (key)=PRIME–(key%PRIME)→ secondHash(23)=5–(23 %5)=2
Doublehashing:(firstHash(key)+i*secondHash(key))%tableSize→ (2+1*2))%7 =4
Astheslotwithhashvalue4isempty,[Link] diagram.
HashValue DataRecord
0 21*
1
f(23)=23 mod7=2 2 16*
3 10*
4 23*
5 12*
6

Figure5.4:Double Probing

ii. SeparateChainingorClosedaddressing:
To handle the collision, This technique creates a linked list to the slot for which collision
occurs. The new key is then inserted in the linked list. These linked lists to the slots appear like
chains. So, this technique is called as separate chaining. It is also called as closed addressing.

Example:Inserting10, 21,16, 12, 23,19, 28, 30in hash table.

HashValue DataRecord
f(10)=10 mod7=3 0 21*

f(21)=21 mod7=0 1

f(16)=16mod 7=2 2 16* 23* 30*

f(12)=12 mod7=5 3 10*

f(23)=23 mod7=2 4

f(19)=19 mod7=5 5 12* 19*

f(30)=30 mod7=2 6

Figure5.5:Separatechainingexample
 6. DYNAMICHASHING
The problem with static hashing is that it does not expand or shrink dynamically as the
size of the database grows or shrinks. Dynamic hashing provides a mechanism in which data
buckets are added and removed dynamically and on-demand. Dynamic hashing can be
implemented using two techniques. They are:

o Extendedhashing
o LinearHashing

i. Extendablehashing
In extendable hashing, a separate directory of pointers to buckets is used. The number
bitsusedindirectoryiscalledglobaldepth(gd)andnumberentriesindirectory=[Link] bits used
for locating the record in the buckets is called local depth(ld) and each bucket canstores up to 2ld
entries. The hash function use last few binarybits of the keyto find the bucket. If
abucketoverflows,itsplits,andiflocaldepthgreaterthanglobaldepth,thenthetabledoublesin size. It is
one form of dynamic hashing.
Example: Let global depth (gd) = 2. It means the directory contains four entries. Let the local
depth (ld) of each bucket = 2. It means each bucket need two bits to perform search operation.
Let each Bucket capacity is four. Let us insert 21, 15, 28, 17, 16, 13, 19, 12, 10, 24, 25 and 11.
21 = 10101 19 = 10011
15 = 01111 12 = 01100
28 = 11100 10 = 01010
17 = 10001 24 = 11000
16 = 10000 25 = 11101
13 = 01101 11 = 01011

Local depth 2
Globaldepth Bucket A
28* 16* 12* 24*
2 2
21* 17* 25* 13* Bucket B
00
01 2
10 BucketC
11 10*
2
Directory BucketD
15* 19* 11*
Figure6.1:Extendible hashing example
Now, let us consider insertion of data entry 20* (binary 10100). Looking at directory
element00,weareledtobucketA,[Link],wehavetosplitthebucketby
allocating a new bucket and redistributing the contents (including the new entry to be inserted)
across the old bucket and its 'split image (new bucket). To redistribute entries across the old
bucket and its split image, we consider the last three bits; the last two bits are 00, indicating a
data entrythat belongs to one of these two buckets, and the third bit discriminates between these
buckets. That is if a key’s last three bits are 000, then it belongs to bucket A and if the last three
bits are 100, then the key belongs to Bucket [Link] we are using three bits for A and A2, so the
local depth of these buckets becomes 3. This is illustrated in the below Figure 6.2.

Local depth 3
16* 24* BucketA
Globaldepth 3
28* Bucket A2
2 12* 20*
2
00 21*
01 2 Bucket B
17* 25*13*
10 10*
11 BucketC

Directory 2
BucketD
15*19*11*
Figure6.2:Afterinserting20andsplittingBucket A

Aftersplit, BucketAandA2havelocaldepthgreaterthanglobaldepth(3>2),so double the

directory and use three bits as global depth. As Bucket A and A2 has local depth 3, so they have
separate pointers from the directory. But, Buckets B, C and D use only local depth 2, so they
have two pointers each. This is shown in the below diagram.

Local depth 3
16* 24* BucketA
Globaldepth 3
28* BucketA2
12* 20*
3
000 BucketB
2
001
010 21*17*25*13*
011
100 2 BucketC
101 10*
110
111 2 BucketD
15*19*11*
Directory

Figure6.3: After inserting 20and doubling the directory

 An important point that arises is whether splitting a bucket necessitates a directory
doubling. Consider our example, as shown in Figure 6.3. If we now insert 9* (01001), it belongs
inbucketB;[Link] and using
directory elements 001 and 101to point to the bucket and its split image. This is shown in the
below diagram. As Bucket B and its split image now have local depth three and it is not
greaterthan global depth. Hence, abucket split does not necessarilyrequireadirectorydoubling.
However, if either bucket A or A2 grows full and an insert then forces a bucket split, we are
forced to double the directory once again.
Local depth 3
16* 24* BucketA
Globaldepth 3
28* BucketA2
3 12* 20*
000 3
001 BucketB
010 17* 9*
3
011
100 21* BucketB2
101 25* 13*
110 2
111 BucketC
10*

2 BucketD
Directory 15*19*11*
Figure6.4:Afterinserting 9

KeyObservations:
 ABucketwillhavemorethanonepointerspointingtoitifitslocaldepthislessthan the global
depth.
 Whenoverflowconditionoccursinabucket,alltheentriesinthebucketarerehashed with a
new local depth.
 IfnewLocalDepthoftheoverflowingbucketisequaltotheglobaldepth,onlythenthe
directories are doubled and the global depth is incremented by 1.
 Thesizeofabucketcannotbechangedafterthedatainsertionprocessbegins.

ii. LinearHashing
Linear hashing is a dynamic hashing technique that linearly grows or shrinks number of
buckets in a hash file without a directory as used in Extendible Hashing. It uses a family of hash
functions instead of single hash function.
 This scheme utilizes a family of hash functions h0, h1,h2, ... , with the property that each
function's range is twice that of its predecessor. That is, if himaps a data entry into one of N
buckets, hi+1 maps a data entry into one of 2N buckets. One example of such hash functionfamily
can be obtained by: where N is the initial number of
hi+1(key)=keymod (2iN)
buckets and i = 0,1,2,….
Initiallyit use N buckets labelled 0 through N–1 and an initial hashingfunction h 0(key) =
key% N is used to map anykeyinto one of the N [Link] each overflow bucket, one of the
buckets in serial order will be splited and its content is redistributed between it and its split
image. That is, for first time overflow in any bucket, bucket 0 will be splited, for second time
overflow in any bucket; bucket 1 will be splited and so on. When number of buckets becomes
2N, then this marks the end of splitting round [Link] function h0 is no longer needed as all 2N
buckets can be addressed by hashing function h 1. In new round namely splitting-round 1,
[Link] repeated
when the hash file grows.

Example: Let N = 4, so we use 4 buckets and hash function h 0(key) = key % 4 is used to map
any key into one of the four buckets. Let us initially insert 4, 13, 19, 25, 14, 24, 15, 18, 23, 11,
16, 12 and [Link] is shown in the below figure.

Bucket#h1h0 Primarypages Overflowpages

0 000 00 4* 24* 16* 12*

1 001 01 13* 25*

2 010 10 14* 18* 10*

3 011 11 19* 15* 23* 11*

Next,when27isinserted,[Link],bucket0(firstbucket)issplited
anditscontentisdistributedbetweenbucket 0andnew bucket. This isshowninbelowfigure.

Bucket#h1h0 Primarypages Overflowpages

0 000 00 24* 16*

1 001 01 13* 25*

2 010 10 14* 18* 10*

3 011 11 19* 15* 23* 11* 27*

4 100 00 4* 12*
Next,when30,31and34isinserted,[Link],bucket1issplited and its content
is distributed between bucket 1 and new bucket. This is shown in below figure.
Bucket# h1 h0 Primarypages Overflowpages
0 000 00 24* 16*
1 001 01 13*
2 010 10 14* 18* 10* 30* 34*
3 011 11 19* 15* 23* 11* 27* 31*
4 100 00 4* 12*
5 101 01 25*

When32,35,40and48isinserted,[Link],bucket2issplited andits content is

distributed between bucket 2 and new [Link] is shown in below figure.
Bucket# h1 h0 Primarypages Overflowpages
0 000 00 24* 16* 32* 40* 48*
1 001 01 13*
2 010 10 18* 10* 34*
3 011 11 19* 15* 23* 11* 27* 31* 35*
4 100 00 4* 12*
5 101 01 25*
6 110 10 14* 30*

When26,20and42isinserted,[Link],bucket3issplited andits content is

distributed between bucket 3 and new [Link] is shown in below figure.
Bucket# h1 h0 Primarypages Overflowpages
0 000 00 24* 16* 32* 40* 48*

1 001 01 13*

2 010 10 18* 10* 34* 26* 42

3 011 11 19* 11* 27* 35*

4 100 00 4* 12* 20*

5 101 01 25*

6 110 10 14* 30*

7 111 11 15* 23* 31*

 This marks the end of splitting [Link] function h0is no longer needed as all 2N
buckets can be addressed by hashing function h1. In new round namely splitting-round 1, bucket
split once again starts from bucket 0. A new hash function h2will be [Link] process is
repeated.

7. INTUITIONSFORTREEINDEXES
We can use tree-like structures as index as well. For example, a binary search tree can
also be used as an index. If we want to find out a particular record from a binary search tree, we
have the added advantage of binary search procedure, that makes searching be performed even
faster. A binary tree can be considered as a 2-way Search Tree, because it has two pointers in
each of its nodes, thereby it can guide you to two distinct ways. Remember that for every node
storing 2 pointers, the number of value to be stored in each node is one less than the number of
pointers, i.e. each node would contain 1 value each.

The abovementioned concept can be further expanded with the notion of the m-Way
Search Tree, where m represents the number of pointers in a particular node. If m = 3, then each
nodeofthesearchtreecontains3pointers,[Link] use mainly two
tree structure indexes in DBMS. They are:

 IndexedSequentialAccessMethods(ISAM)
 B+Tree

8. INDEXEDSEQUENTIALACCESSMETHODS(ISAM)
ISAMisatreestructuredatathatallowstheDBMStolocateparticularrecordusingindex without
having to search the entire data set.
 Therecords in a filearesortedaccordingtotheprimarykeyand saved in the disk.
 Foreachprimarykey,[Link] index is
nothing but the address of record.
 Asorted data file accordingtoprimaryindexiscalledanindexed sequential file.
 TheprocessofaccessingindexedsequentialfileiscalledISAM.
 [Link] primary key
has to be selected to make ISAM efficient.
  ISAM gives flexibility to generate index on other fields also in addition to primary
keyfields.
ISAMcontainthreetypesofnodes:
 Non-leafnodes: Theystorethe search indexkeyvalues.
 Leafnodes: Theystoretheindexofrecords.
 Overflownodes: Theyalsostoretheindexofrecordsbutaftertheleafnodeisfull.

OnISAM, wecanperformsearch,insertionanddeletionoperations.
Search Operation: It follows binarysearch process. The record to be searched will be available in
the leaf nodes or in overflow nodes only. The non-leaf nodes are used to search the value.
Insertion operation: First locate a leaf node where the insertion to be take place (use binary search).
After finding leaf node, insert it in that leaf node if space is available, else create an overflow
node and insert the record index in it, and link the overflow node to the leaf node.
Deletion operation: First locate a leaf node where the deletion to be take place (use binary search).
After finding leaf node, if the value to be deleted is in leaf node or in overflow node, remove it.
If the overflow node is empty after removing the deleted value, then delete overflow node also.
Example: Insert10, 23, 31, 20,68, 35,42,61, 27,71, 46and 59
31

23 68 42 59

7 6
10 20 23 27 68 31 35 42 46 59
 Afterinserting24, 33, 36, and 39 in theabovetree, it looks like

31

23 68 42 59

7 6
10 20 23 27 68 31 35 42 46 59
3
24 33
Deletion:Fromtheabovefigure,afterdeleting42, 71,24and 36

31 39

23 68 42 59

6
10 20 23 27 68 31 35 46 59

33

39

9. B+ TREE
B+ Tree is an extension of Binary Tree which allows efficient insertion, deletion and search
operations. It is used to implement indexing in DBMS. In B+ tree, data can be stored onlyon the
leaf nodes while internal nodes can store the search key values.

1. B+treeof anordermcanstoremaxm-1valuesateach node.

2. Eachnodecanhaveamaximumofmchildrenandatleastm/2children(except root).
3. Thevaluesineachnodeareinsortedorder.
4. Allthenodesmustcontainatleasthalffullexcepttherootnode.
5. Onlyleafnodescontainvaluesandnon-leaf nodescontainsearchkeys.
B+ Search:
SearchingforavalueintheB+-Treealwaysstartsattherootnodeandmovesdownwards until it
reaches a leaf node. The search procedure follows binary tree search procedure.

1. [Link].
2. Startthesearchprocessfromrootnode
3. Ateachnon-leafnode(includingrootnode),
a. Ifallthevaluesinthenon-leafnodearegreaterthanX, thenmovetoits first child
b. Ifallthevaluesinthenon-leafnodearelessthanorequaltoX,thenmovetoits last child
c. Ifforanytwoconsecutivevaluesinthenon-leafnode,leftvalueislessandright value
greaterthan or equal to X, then moveto the child nodewhosepointer is in between
these two consecutive values.
4. Repeatstep-3untilaleaf nodereaches.
5. Atleafnodecomparethekeywiththevaluesinthatnodefromlefttoright. Ifthekey value is
found then display found. Otherwise display it is not found.

Example:Searchingfor35in thebelowgiven B+ tree. Thesearchpathisshowninredcolor.

18

11 31 64

8 15 23 42 59 68

2 5 8 9 11 12 15 16 18 20 23 27 31 35 42 46 59 61 64 66 68 7
B+ Insertion:

1. Applysearch operation on B+treeandfindaleafnodewherethenew value has to insert.

2. Iftheleafnodeisnotfull, theninsertthevalueintheleafnode.
3. Iftheleafnodeisfull, then
 a. Split that leaf node including newly inserted value into two nodes such that each
contains half of the values (In case of odd, 2nd node contains extra value).
b. Insertsmallestvaluefromnewrightleafnode(2ndnode)intotheparentnode. Add
pointers from these new leaf nodes to their parent node.
c. If theparent is full, split it too. Addthemiddlekey(In caseof even,1stvaluefrom 2nd
part)of this parent node to its parent node.
d. Repeatuntilaparentisfoundthatneednotsplit.
4. If therootsplits, createanewrootwhichhasonekeyandtwopointers.

Example:Insert1,5,3,7,9,2,4,6,8,10intoB+treeofanorder4.

B+treeoforder4indicatestherearemaximum3valuesinanode. Initially

Afterinserting1
1

Afterinserting5

Afterinserting3

5
Afterinserting7
1 3 5 7
1 3 5 7
Afterinserting9
5

1 3 5 7 9
Afterinserting2
5

1 2 3 5 7 9
Afterinserting4
5 3 5

1 2 3 4 5 7 9 1 2 3 4 5 7 9
Afterinserting6
3 5

1 2 3 4 5 7 9 6

3 5 7

1 2 3 4 56 7 9

Afterinserting8
3 5 7

1 2 3 4 56 7 8 9

Afterinserting10
3 5 7

56
1 2 3 4 7 8 9 10

3 5 79

1 2 3 4 5 6 7 8 9 10

3 5 9

9 10

1 2 3 4 5 6 7 8
B+Deletion

 Identifythe leaf nodeLfromwheredeletion should takeplace.

 RemovethedatavaluetobedeletedfromtheleafnodeL
 IfLmeetsthe"halffull"criteria, thenitsdone.
 IfLdoesnotmeetsthe "halffull"criteria,then
o If L's right sibling can give a data value, then move smallest value in right sibling
to L (After giving a data value, the right sibling should satisfy the half fullcriteria.
Otherwise it should not give)
o Else, if L's left sibling can give a data value, then move largest value in leftsibling
to L (After giving a data value, the left sibling should satisfy the half full criteria.
Otherwise it does not give)
o Else,mergeLandasibling
o If any internal nodes (including root) contain key value same as deleted value,
then delete those values and replace with it successor. This deletion may
propagate up to root. (If the changes propagate up to root then tree height
decreases).

Example:Considerthegivenbelowtree anddelete19,
19

5 14 24 33

2 3 5 7 14 16 19 20 22 24 27 29 33 34 38 39
Delete19:Half fullcriteriaissatisfiedevenafter deleting19,so justdelete19 fromleafnode

19

5 14 24 33

2 3 5 7 14 16 20 22 24 27 29 33 34 38 39
Delete 20: Half full criteria is not satisfied after deleting 20, so bring 24 from its right siblingand
change key values in the internal nodes.
19

5 14 27 33

2 3 5 7 14 16 22 24 27 29 33 34 38 39
Delete 24: Half full criteria is not satisfied after deleting 24, bringing a value from its siblings
also not possible. Therefore merge it with its right sibling and change key values in the internal
nodes.
19

5 14 33

2 3 5 7 14 16 22 27 29 33 34 38 39
Delete 5: Half full criteria is not satisfied after deleting 5, bringing a value from its siblings also
not possible. Therefore merge it with its left sibling (you can also merge with right) and change
key values in the internal nodes.
19

14 33

2 3 7 14 16 22 27 29 33 34 38 39
Delete7:Halffullcriteriaissatisfiedevenafterdeleting7,sojustdelete7fromleafnode.
17

14 33

2 3 14 16 22 27 29 33 34 38 39
 Delete 2: Half full criteria is not satisfied after deleting 2, bringing a value from its siblings also
not possible. Therefore merge it with its right sibling and change key values in the internalnodes.
22 33

3 14 16 22 27 29 33 34 38 39
9. INDEXESANDPERFORMANCETUNING
Indexing is very important to execute DBMS query more efficiently. Adding indexes to
important tables is a regular part of performance tuning. When we identify a frequently executed
querythat is scanningatableorcausinganexpensivekeylookup, then first consideration is ifan index
can solve this problem. If yes add index for that table.

While indexes can improve query execution speed, the price we pay is on index
maintenance. Update and insert operations need to update the index with new data. This means
that writes will slow down slightly with each index we add to a table. We also need to monitor
index usage and identify when an existing index is no longer needed. This allows us to keep our
indexing relevant and trim enough to ensure that we don’t waste disk space and I/O on write
[Link],weneedtodo the
following:

 Identifytheunusedindexesandremovethem.
 Identifytheminimallyusedindexesand remove them.
 An index that is scanned more frequently, but rarely findsthe required answer. Modifythe
index to reach the answer.
 Identifytheindexes that are verysimilarandcombinethem.

-oO0Oo–

BestofLuck–Ravindar Mogili