DATABASE MANAGEMENT

SYSTEMS
Complete Syllabus Notes & Reference Guide

Covers: DBMS Fundamentals • ER & Relational Modeling • Relational Algebra & Calculus •
SQL • Normalization & Functional Dependencies • Transactions & ACID • Concurrency
Control • Recovery • Indexing & File Organization • Query Processing & Optimization •
Distributed & NoSQL Databases

Prepared for MCA Coursework

NIT Patna
Database Management Systems — Notes

Table of Contents

Introduction to Database Management Systems 5

1.1 Why Not Just Use Files? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.2 Advantages of a DBMS Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.3 Users of a Database System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.4 Database System Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.5 Data Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.6 Schema vs. Instance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.7 Database Languages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

The Entity-Relationship (ER) Model 9

2.1 Basic Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.2 Relationships . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.3 Keys . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.4 Weak Entities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.5 Extended ER (EER) Features . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.6 A Complete Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

The Relational Model 13

3.1 Basic Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

3.2 Properties of Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

3.3 Integrity Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

3.4 Referential Integrity and Foreign Key Actions . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

3.5 Mapping an ER Diagram to Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

Relational Algebra and Relational Calculus 16

4.1 Fundamental (Unary/Binary Set) Operations of Relational Algebra . . . . . . . . . . . . . . . . 16

4.2 Additional (Derived) Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

4.3 Worked Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

4.4 Relational Calculus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

Structured Query Language (SQL) 19

5.1 SQL Sub-Languages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

5.2 Data Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

5.3 Constraints in SQL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2
Database Management Systems — Notes

5.4 Basic Query Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

5.5 Joins in SQL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

5.6 Aggregate Functions and Grouping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

5.7 Subqueries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

5.8 Set Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

5.9 Views . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

5.10 Indexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

5.11 Window Functions (Analytic SQL) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

5.12 Null Handling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

Functional Dependencies and Normalization 23

6.1 Functional Dependencies (FDs) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

6.2 Update Anomalies (the Problem Normalization Solves) . . . . . . . . . . . . . . . . . . . . . . 23

6.3 Normal Forms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

6.4 Worked Normalization Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

6.5 Decomposition Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

Transaction Management and the ACID Properties 26

7.1 The ACID Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

7.2 Transaction States . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

7.3 Schedules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

7.4 Recoverability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

Concurrency Control 29

8.1 Lock-Based Protocols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

8.2 Timestamp-Ordering Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

8.3 Multiversion Concurrency Control (MVCC) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

8.4 Optimistic Concurrency Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

8.5 SQL Isolation Levels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

Database Recovery Techniques 32

9.1 Types of Failure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

9.2 The Log . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

9.3 Deferred vs. Immediate Database Modification . . . . . . . . . . . . . . . . . . . . . . . . . . 32

9.4 Checkpoints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

9.5 ARIES Recovery Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

9.6 Buffer Management Policies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

3
Database Management Systems — Notes

Storage Structures, File Organization, and Indexing 35

10.1 Storage Hierarchy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

10.2 File Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

10.3 Indexing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

10.4 B-Tree and B+-Tree Indexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

10.5 Hash-Based Indexing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

10.6 Bitmap Indexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

Query Processing and Optimization 38

11.1 The Query Processing Pipeline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

11.2 Cost Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

11.3 Algorithms for Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

11.4 Algorithms for Join . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

11.5 Heuristic (Rule-Based) Query Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

11.6 Materialized Views . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

An Introduction to Distributed Databases and NoSQL Systems 41

12.1 Distributed Databases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

12.2 The CAP Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

12.3 BASE vs. ACID . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

12.4 NoSQL Data Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

12.5 SQL vs. NoSQL — Quick Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

4
Database Management Systems — Notes

CHAPTER 1
Introduction to Database Management
Systems
A database is an organized collection of related data stored in a structured form so that it can be
efficiently accessed, managed, and updated. A Database Management System (DBMS) is the
software layer that sits between the physical data and the applications or users that need it. It provides
a systematic way to create, retrieve, update, and manage data while enforcing rules that keep that
data accurate and secure.

1.1 Why Not Just Use Files?

Before DBMSs became common, applications stored data directly in flat files managed by the
operating system. This approach — called the file-processing system — worked for small,
single-purpose programs but broke down as systems grew. The core problems were:

• Data redundancy and inconsistency: the same data (e.g., a customer's address) was often
duplicated across multiple files maintained by different programs, so updating it in one place but
not another left the data inconsistent.
• Difficulty in accessing data: every new question about the data (e.g., 'list all customers in a given
pin code') required a programmer to write a new program, because file systems offer no
general-purpose query capability.
• Data isolation: data was scattered across files in different, often incompatible, formats, making it
hard to write programs that combined data from multiple files.
• Integrity problems: business rules ('an account balance may not go below zero') had to be
hard-coded into every program that touched the data, and were easy to forget.
• Atomicity problems: if a program crashed midway through an operation involving several file
updates (e.g., a funds transfer), the files could be left in a partially updated, inconsistent state.
• Concurrent-access anomalies: when multiple users update the same file simultaneously without
coordination, updates can be lost or the file can become corrupted.
• Security problems: it is hard to give every user exactly the access they need (and no more) when
access control has to be enforced by each individual application.

A DBMS was designed specifically to eliminate or drastically reduce all of these problems by
centralizing data management under one piece of software that every application talks to.

1.2 Advantages of a DBMS Approach

• Controlling redundancy: data is stored once (or redundancy is deliberate and controlled) and
shared by all applications, so updates only need to happen in one place.
• Restricting unauthorized access: the DBMS provides authentication and authorization so only
permitted users can read or write specific data.
• Providing persistent storage for program objects and data structures.

5
Database Management Systems — Notes

• Providing storage structures and search techniques (indexes, hashing) for efficient query
processing.
• Providing backup and recovery so data is not lost due to system or media failure.
• Providing multiple user interfaces: query languages for casual users, APIs for application
programmers, forms and menus for parametric users.
• Representing complex relationships among data using a data model.
• Enforcing integrity constraints that must hold for the data (data types, uniqueness, referential
relationships, business rules).
• Permitting inferencing and actions using rules and triggers (active database capability).

1.3 Users of a Database System

User type Role

Database Administrator (DBA) Has central control over the system: schema definition,
storage structure, access authorization, and coordination
among users.

Database Designer Identifies the data to be stored, chooses appropriate

structures to represent and store this data, before the
database is actually built and populated.

Application Programmers Write application programs that interact with the

database through APIs, embedded SQL, or ORM
frameworks.

Sophisticated/Casual Users Interact with the system by issuing queries and updates
using a query language (e.g., analysts writing SQL).

Naive/Parametric Users Use a permanently coded application (a form or app)

without knowing anything about the database internals
— e.g., a bank teller or an e-commerce buyer.

Specialized Users Write specialized applications that do not fit the

traditional processing framework — e.g., CAD systems,
expert systems, ML pipelines.

1.4 Database System Architecture

A DBMS is commonly described using the ANSI/SPARC three-schema architecture, which separates
the way data is physically stored from the way it is presented to users. This separation is what gives a
DBMS its two most important properties: physical data independence and logical data independence.

6
Database Management Systems — Notes

The three-schema (ANSI/SPARC) architecture

• External level (view level): describes the part of the database that a particular user group is
interested in, hiding the rest. Many external views can exist for one database.
• Conceptual level (logical level): describes what data is stored and the relationships among the data
for the whole database, independent of any particular application.
• Internal level (physical level): describes how the data is actually stored — file organization,
indexes, data structures, and access paths used by the storage engine.

Physical data independence — the capacity to change the internal/physical schema (e.g., add a
new index, switch storage engine) without needing to change the conceptual schema, so application
programs are unaffected.

Logical data independence — the capacity to change the conceptual schema (e.g., add a new
entity or attribute) without having to change existing external schemas or the application programs
written against them.

1.5 Data Models

A data model is a collection of conceptual tools for describing data, data relationships, data semantics,
and consistency constraints. Data models can broadly be grouped into three categories.

Category Description Examples

Object/Record-based (high-level, Provide fairly flexible structuring ER model, Object-oriented model,

conceptual) capabilities, close to how people Semantic models
naturally think about data.

Record-based Used to specify the overall logical Relational model, Network model,
(representational/implementation) structure of the database using Hierarchical model
records of a fixed format.

7
Database Management Systems — Notes

Category Description Examples

Physical (low-level) Describe how data is actually stored File organizations, indexing
on the storage medium. structures

1.6 Schema vs. Instance

The overall design of a database is called the database schema — it is analogous to the type
definition of a variable in a programming language, and normally does not change often. The data
actually stored in the database at a particular moment is called a database instance (or state), which
changes every time a record is inserted, updated, or deleted.

1.7 Database Languages

• Data Definition Language (DDL): used to define the database schema — CREATE, ALTER,
DROP. The compiled result of DDL statements is stored in a special file called the data dictionary
or system catalog, which itself is treated as a mini-database describing the database.
• Data Manipulation Language (DML): used to retrieve, insert, delete, and modify data — SELECT,
INSERT, UPDATE, DELETE. DML can be procedural (the user specifies what data is needed and
how to get it — e.g., relational algebra) or declarative/non-procedural (the user specifies what data
is needed without specifying how — e.g., relational calculus, SQL).
• Data Control Language (DCL): used to control access to data — GRANT, REVOKE.
• Transaction Control Language (TCL): used to manage transactions — COMMIT, ROLLBACK,
SAVEPOINT.

Note: In practice SQL is a single language that bundles DDL, DML, DCL and TCL statements together,
which is why it is often called a comprehensive or universal database language rather than a purely
declarative DML.

8
Database Management Systems — Notes

CHAPTER 2
The Entity-Relationship (ER) Model
The Entity-Relationship model is a high-level conceptual data model that lets a database designer
describe the data of an organization independent of any DBMS software. It views the real world as a
set of basic objects (entities) and the relationships among them, and is typically drawn as an ER
diagram during the database design phase.

2.1 Basic Concepts

Entity — a real-world object that is distinguishable from other objects. An entity has a set of
properties (attributes), and the values of some subset of attributes must uniquely identify it (e.g., a
specific STUDENT with student_id = 2027045).

Entity Set — a collection of entities of the same type sharing the same attributes (e.g., the set of all
STUDENT entities).

Attribute — a property that describes an entity. Attributes are drawn as ellipses in an ER diagram.

Types of attributes
• Simple (atomic) attribute — cannot be divided further, e.g., age.
• Composite attribute — can be divided into sub-parts, e.g., name = {first_name, last_name}.
• Single-valued attribute — has only one value for a given entity, e.g., ssn.
• Multi-valued attribute — can have multiple values, e.g., a person can have several phone numbers;
drawn as a double ellipse.
• Derived attribute — its value can be calculated/derived from other attributes, e.g., age can be
derived from date_of_birth; drawn as a dashed ellipse.
• Key attribute — uniquely identifies each entity in the entity set; underlined in a diagram.

2.2 Relationships
A relationship is an association among two or more entities. A relationship set is a collection of
relationships of the same type, and is drawn as a diamond connected to the participating entity sets.

Degree of a relationship
• Unary (recursive) — relates an entity to itself, e.g., an EMPLOYEE 'supervises' another
EMPLOYEE.
• Binary — relates two entity sets, by far the most common, e.g., STUDENT enrolls-in COURSE.
• Ternary — relates three entity sets, e.g., SUPPLIER supplies PART to PROJECT.

9
Database Management Systems — Notes

Mapping cardinality (cardinality ratio)

Cardinality expresses the number of entities to which another entity can be associated via a
relationship set.

Ratio Meaning Example

One-to-One (1:1) An entity in A is associated with at A PERSON has one PASSPORT; a

most one entity in B and vice versa. PASSPORT belongs to one
PERSON.

One-to-Many (1:N) An entity in A can be associated with One DEPARTMENT has many
many entities in B, but an entity in B EMPLOYEEs; each EMPLOYEE
is associated with at most one entity belongs to one DEPARTMENT.
in A.

Many-to-One (N:1) The reverse of one-to-many, viewed Many EMPLOYEEs work in one
from the other side. DEPARTMENT.

Many-to-Many (M:N) Entities on both sides can be A STUDENT enrolls in many

associated with many entities on the COURSEs; a COURSE has many
other side. STUDENTs.

Participation constraints
• Total participation: every entity in the entity set must participate in at least one relationship instance
(drawn as a double line). Example: every EMPLOYEE must work in some DEPARTMENT.
• Partial participation: only some entities need to participate (drawn as a single line). Example: not
every EMPLOYEE manages a DEPARTMENT.

2.3 Keys

Key type Definition

Super Key any set of attributes that, taken together, uniquely

identifies an entity in the entity set.

Candidate Key a minimal super key — no proper subset of it is also a

super key. An entity set can have several candidate
keys.

Primary Key the candidate key chosen by the database designer as

the principal means of identifying entities; cannot be
NULL.

Alternate Key a candidate key that was not chosen as the primary key.

Composite Key a primary key made up of two or more attributes.

Foreign Key an attribute (or set of attributes) in one relation that

refers to the primary key of another (or the same)
relation, used to represent relationships between tuples
of two relations.

10
Database Management Systems — Notes

2.4 Weak Entities

A weak entity set is one whose existence depends on another entity set, called the identifying or
owner entity set — a weak entity has no primary key of its own and is instead identified by combining
a partial key (a discriminator) with the primary key of its owner entity. For example, a DEPENDENT of
an EMPLOYEE only makes sense in the context of that employee; DEPENDENT would be identified
by (employee_id, dependent_name). Weak entity sets are drawn with a double rectangle, and the
identifying relationship with a double diamond.

2.5 Extended ER (EER) Features

Specialization and generalization
Specialization is the process of designating subgroupings (subclasses) within an entity set
(superclass) that have distinct attributes or participate in distinct relationships — for example,
PERSON specialized into STUDENT and EMPLOYEE. Generalization is the reverse process:
identifying common features among several entity sets and defining a generalized (super) entity set
that contains them, e.g., CAR and TRUCK generalized into VEHICLE.

Constraints on specialization/generalization
• Disjoint vs. overlapping: in a disjoint constraint an entity can belong to at most one subclass; in an
overlapping constraint it may belong to more than one.
• Total vs. partial: a total specialization requires every superclass entity to belong to some subclass;
a partial specialization allows entities that belong to no subclass.

Aggregation
Aggregation is an abstraction in which relationship sets (along with their entity sets) are treated as
higher-level entity sets, allowing a relationship to participate in another relationship. This is used when
a relationship set itself needs to be associated with another entity — for instance, treating the
relationship 'WORKS_ON(EMPLOYEE, PROJECT)' as a single unit so it can also be associated with
a MANAGER who monitors that assignment.

2.6 A Complete Example

11
Database Management Systems — Notes

ER diagram: STUDENT enrolls in COURSE (M:N relationship with a descriptive attribute 'grade')

In this example, STUDENT and COURSE are entity sets connected through the ENROLLS
relationship set, which is many-to-many (a student can enroll in many courses and a course can have
many students). The attribute grade belongs to the relationship itself, since a grade only makes sense
in the context of a specific student-course pairing, not for the student or course alone.

12
Database Management Systems — Notes

CHAPTER 3
The Relational Model
The relational model, proposed by E. F. Codd in 1970, represents data and relationships among data
as a collection of two-dimensional tables called relations. It remains the dominant data model used by
commercial DBMSs today (MySQL, PostgreSQL, Oracle, SQL Server) because of its simplicity and
strong mathematical foundation.

3.1 Basic Terminology

Relational term Informal equivalent

Relation Table

Tuple Row / record

Attribute Column / field

Degree Number of attributes (columns) in a relation

Cardinality Number of tuples (rows) in a relation

Domain The set of allowable, atomic values for an attribute

Relation schema The name of a relation plus its attributes, e.g.,

Student(sid, name, dept, gpa)

Relation instance The actual set of tuples in a relation at a given point in

time

3.2 Properties of Relations

• Each cell of the relation contains exactly one atomic (single) value — this is the basis of First
Normal Form.
• Attribute names in a relation are distinct, and the order of attributes has no significance.
• Each tuple is distinct — there are no duplicate tuples in a relation (this follows from the relation
being a mathematical set).
• The order of tuples has no significance, theoretically (although a query result can be explicitly
sorted with ORDER BY).

3.3 Integrity Constraints

• Domain constraint: every value of an attribute must be drawn from the attribute's domain (e.g., age
must be a positive integer).
• Key constraint: no two tuples can have identical values for all the primary key attributes;
additionally, a primary key attribute cannot contain a NULL value (entity integrity).
• Entity integrity constraint: the primary key of a relation cannot be null (for base relations) — this
ensures every tuple in a relation is uniquely and validly identifiable.

13
Database Management Systems — Notes

• Referential integrity constraint: a value of a foreign key must either match a value of the primary
key it references in the other relation, or be entirely NULL. This constraint is what actually
implements relationships between tables.
• General/semantic (business rule) constraints: additional rules specified by the database
designer/administrator, e.g., 'an employee's salary may not exceed the salary of their manager'.

3.4 Referential Integrity and Foreign Key Actions

When a row referenced by a foreign key is deleted or its key is updated, the DBMS must decide how
to preserve referential integrity. This behaviour is specified when the foreign key is defined:

Action Effect

CASCADE The delete/update is propagated to the referencing rows

automatically (deleting a DEPARTMENT deletes all its
EMPLOYEEs).

SET NULL The foreign key column in the referencing rows is set to
NULL.

SET DEFAULT The foreign key column in the referencing rows is set to
a predefined default value.

RESTRICT / NO ACTION The delete/update is rejected if any referencing row

exists.

3.5 Mapping an ER Diagram to Relations

Once an ER diagram is finalized, it is systematically converted into a set of relation schemas using
standard mapping rules:

1 Strong entity → becomes a relation with all its simple/simple-composite attributes; the entity's key
becomes the relation's primary key.
2 Weak entity → becomes a relation whose attributes include its own partial key plus the primary key
of its owner entity (as a foreign key); the primary key of the new relation is the combination of both.
3 1:1 relationship → the primary key of one relation is placed as a foreign key in the other (commonly
on the side with total participation), or the two relations can be merged.
4 1:N relationship → the primary key of the 'one' side is placed as a foreign key in the relation on the
'many' side.
5 M:N relationship → a new relation is created, with the primary keys of both participating entities as
foreign keys, together forming the composite primary key of the new relation. Any descriptive
attributes of the relationship (like 'grade') are added to this new relation.
6 Multi-valued attribute → becomes its own relation, with a foreign key referencing the owner entity's
primary key.
7 Specialization/Generalization → can be mapped in one of several ways: (a) one relation per
subclass plus one for the superclass ('one table per subtype + supertype'), (b) one relation per
subclass only (attributes of the superclass are copied into every subclass table), or (c) a single
relation for the whole hierarchy with a 'type' discriminator column and nullable columns for
subclass-specific attributes.

14
Database Management Systems — Notes

15
Database Management Systems — Notes

CHAPTER 4
Relational Algebra and Relational
Calculus
Relational algebra and relational calculus are formal, mathematically precise query languages that
operate on relations and form the theoretical foundation of SQL. Relational algebra is procedural — a
query specifies a sequence of operations to be performed on existing relations to derive the desired
result. Relational calculus is non-procedural — a query describes the desired result without specifying
how to obtain it.

4.1 Fundamental (Unary/Binary Set) Operations of Relational

Algebra

Operator Symbol Purpose

Select sigma (condition)(R) Selects the tuples (rows) of relation

R that satisfy a given predicate.

Project pi (attribute-list)(R) Selects certain columns from R and

removes duplicate rows from the
result.

Union RUS Returns tuples that are in R, in S, or

in both (R and S must be
union-compatible: same degree and
matching domains).

Set Difference R-S Returns tuples that are in R but not

in S.

Cartesian Product RxS Returns every possible combination

of tuples from R with tuples from S;
the result has degree(R) + degree(S)
attributes.

Rename rho (R -> R2) Renames a relation and/or its

attributes, useful for self-joins or
improving readability.

4.2 Additional (Derived) Operations

Operator Symbol Purpose

Set Intersection R∩S Tuples that appear in both R and S;

derivable as R - (R - S).

Theta Join R JOIN(theta) S Combines Cartesian product and a

selection: sigma(theta)(R x S).

16
Database Management Systems — Notes

Operator Symbol Purpose

Equijoin - A theta join where theta is

composed only of equality
comparisons.

Natural Join R |X| S An equijoin over all attributes

common to R and S, with the
duplicate columns automatically
removed from the result — the most
commonly used join.

Outer Join (Left/Right/Full) - Like a natural/theta join, but tuples

from one or both relations that would
otherwise be dropped (because they
have no match) are kept, with
NULLs padded in for the missing
attributes.

Division R/S Returns tuples from R that are

associated with every tuple in S —
classic use case: 'find students who
have taken ALL courses in the
Computer Science department'.

4.3 Worked Examples

Given relations Employee(eid, name, dept, salary) and Department(dno, dname, location):

-- Employees in the 'Sales' department earning more than 50000

sigma(dept='Sales' AND salary>50000)(Employee)

-- Only the names and salaries of all employees

pi(name, salary)(Employee)

-- Employee names together with the department location

pi(name, location)( Employee |X| dept=dno Department )

-- Employees who work in a department located in 'Ranchi'

pi(name)( sigma(location='Ranchi')(Employee |X| dept=dno Department) )

4.4 Relational Calculus

Relational calculus comes in two flavours. Tuple Relational Calculus (TRC) expresses a query as {t |
P(t)} — 'the set of all tuples t such that predicate P(t) is true' — where t ranges over tuples of a
relation. Domain Relational Calculus (DRC) instead uses domain variables that range over individual
attribute values: { | P(x1, ..., xn)}. Both use quantifiers — the existential quantifier (there exists) and
the universal quantifier (for all) — to express conditions such as 'a student who has taken every
course'.

17
Database Management Systems — Notes

Note: Relational algebra, tuple relational calculus, and domain relational calculus (when restricted to safe
expressions) are all provably equivalent in expressive power — this equivalence result is why SQL, which
resembles calculus in its declarative SELECT syntax, can still be evaluated internally by translating it into an
algebra expression that the query optimizer manipulates.

18
Database Management Systems — Notes

CHAPTER 5
Structured Query Language (SQL)
SQL (Structured Query Language) is the standard declarative language used to define, manipulate,
and control data in a relational DBMS. It is declarative in the sense that the user specifies what data is
wanted, and the DBMS's query optimizer determines the most efficient way to retrieve it.

5.1 SQL Sub-Languages

Category Statements Purpose

DDL CREATE, ALTER, DROP, Define and modify the structure of

TRUNCATE database objects (tables, views,
indexes).

DML SELECT, INSERT, UPDATE, Query and manipulate the data

DELETE stored in tables.

DCL GRANT, REVOKE Control access permissions on

database objects.

TCL COMMIT, ROLLBACK, Manage the effects of DML

SAVEPOINT, SET TRANSACTION statements as transactions.

5.2 Data Definition

CREATE TABLE Department (
dno INT PRIMARY KEY,
dname VARCHAR(50) NOT NULL UNIQUE,
location VARCHAR(50)
);

CREATE TABLE Employee (

eid INT PRIMARY KEY,
name VARCHAR(50) NOT NULL,
salary DECIMAL(10,2) CHECK (salary > 0),
dno INT,
FOREIGN KEY (dno) REFERENCES Department(dno)
ON DELETE SET NULL ON UPDATE CASCADE
);

ALTER TABLE Employee ADD COLUMN hire_date DATE;

DROP TABLE Employee;

5.3 Constraints in SQL

• NOT NULL — the column may not contain a NULL value.
• UNIQUE — every value in the column must be distinct (unlike a primary key, multiple NULLs are
usually allowed).
• PRIMARY KEY — combines NOT NULL and UNIQUE; identifies each row.

19
Database Management Systems — Notes

• FOREIGN KEY — enforces referential integrity with another table.

• CHECK — restricts the values that can be placed in a column using a boolean expression.
• DEFAULT — supplies a value automatically when none is specified on insert.

5.4 Basic Query Structure

The general form of a SQL query and the logical order in which its clauses are conceptually evaluated
(which is different from the order they are written in) is:

SELECT [DISTINCT] column-list

FROM table-list
WHERE row-condition
GROUP BY grouping-columns
HAVING group-condition
ORDER BY sort-columns [ASC|DESC];

-- Logical processing order:

-- FROM -> WHERE -> GROUP BY -> HAVING -> SELECT -> ORDER BY

Note: This distinction matters: because WHERE is logically evaluated before SELECT, a WHERE clause
cannot reference a column alias defined in SELECT. Because HAVING is evaluated after GROUP BY,
HAVING can filter on aggregate values, whereas WHERE cannot.

5.5 Joins in SQL

-- Inner join (only matching rows from both tables)
SELECT [Link], [Link]
FROM Employee e JOIN Department d ON [Link] = [Link];

-- Left outer join (keep all Employees, even those with no department)
SELECT [Link], [Link]
FROM Employee e LEFT JOIN Department d ON [Link] = [Link];

-- Self join (find employees who earn more than their manager)
SELECT [Link] AS employee, [Link] AS manager
FROM Employee e1 JOIN Employee e2 ON e1.mgr_id = [Link]
WHERE [Link] > [Link];

5.6 Aggregate Functions and Grouping

-- Average salary per department, only for departments with more than 5 employees
SELECT dno, COUNT(*) AS emp_count, AVG(salary) AS avg_sal
FROM Employee
GROUP BY dno
HAVING COUNT(*) > 5
ORDER BY avg_sal DESC;

Common aggregate functions: COUNT, SUM, AVG, MIN, MAX. COUNT(*) counts all rows including
duplicates and NULLs; COUNT(column) counts only non-NULL values in that column.

5.7 Subqueries

20
Database Management Systems — Notes

-- Employees who earn more than the company average (scalar subquery)
SELECT name FROM Employee
WHERE salary > (SELECT AVG(salary) FROM Employee);

-- Departments that have at least one employee (EXISTS - correlated subquery)

SELECT dname FROM Department d
WHERE EXISTS (SELECT 1 FROM Employee e WHERE [Link] = [Link]);

-- Employees not in the 'HR' department (NOT IN)

SELECT name FROM Employee
WHERE dno NOT IN (SELECT dno FROM Department WHERE dname = 'HR');

Note: A correlated subquery references a column from the outer query and is conceptually re-evaluated
once for every row of the outer query, whereas a non-correlated (simple) subquery is evaluated exactly
once.

5.8 Set Operations

SELECT city FROM Customers
UNION
SELECT city FROM Suppliers; -- duplicates removed

SELECT city FROM Customers

UNION ALL
SELECT city FROM Suppliers; -- duplicates kept

SELECT city FROM Customers

INTERSECT
SELECT city FROM Suppliers;

SELECT city FROM Customers

EXCEPT
SELECT city FROM Suppliers; -- MINUS in Oracle

5.9 Views
A view is a virtual table defined by a stored query; it does not itself store data (unless materialized),
and is recomputed from its base tables every time it is referenced. Views are used to simplify complex
queries, present a restricted/customized window of data to a class of users (a security mechanism),
and provide logical data independence.

CREATE VIEW HighEarners AS

SELECT eid, name, salary, dno
FROM Employee
WHERE salary > 100000;

A view is generally updatable (INSERT/UPDATE/DELETE through it will affect the underlying base
table) only if it is defined on a single table without aggregate functions, DISTINCT, GROUP BY, or set
operations.

5.10 Indexes
CREATE INDEX idx_emp_dno ON Employee(dno);
CREATE UNIQUE INDEX idx_dept_name ON Department(dname);

21
Database Management Systems — Notes

5.11 Window Functions (Analytic SQL)

Window functions perform a calculation across a set of rows related to the current row, without
collapsing the rows into a single output row the way GROUP BY does.

SELECT name, dno, salary,

RANK() OVER (PARTITION BY dno ORDER BY salary DESC) AS dept_rank,
AVG(salary) OVER (PARTITION BY dno) AS dept_avg
FROM Employee;

5.12 Null Handling

NULL represents an unknown or missing value and behaves differently from ordinary values in
comparisons — any arithmetic or comparison operation involving NULL evaluates to UNKNOWN, not
TRUE or FALSE. Because of this, NULL values must be tested with IS NULL / IS NOT NULL rather
than = NULL, and SQL logic effectively becomes three-valued (TRUE/FALSE/UNKNOWN).

22
Database Management Systems — Notes

CHAPTER 6
Functional Dependencies and
Normalization
Normalization is a step-by-step, formal process of organizing the attributes and relations of a database
in order to minimize data redundancy and eliminate undesirable characteristics called update
anomalies. It is driven by the theory of functional dependencies.

6.1 Functional Dependencies (FDs)

Functional Dependency — given a relation R, an attribute (or set of attributes) Y is functionally

dependent on X (written X -> Y, read 'X determines Y') if, for any two tuples that agree on the values
of X, they must also agree on the values of Y. X is called the determinant.

For example, in Employee(eid, name, dno, dname), eid -> name holds (each employee id determines
exactly one name), and dno -> dname holds (each department number determines exactly one
department name).

Armstrong's Axioms (rules for reasoning about FDs)

• Reflexivity: if Y is a subset of X, then X -> Y.
• Augmentation: if X -> Y, then XZ -> YZ for any Z.
• Transitivity: if X -> Y and Y -> Z, then X -> Z.
From these three primary axioms, several useful derived rules follow, including union (X->Y and X->Z
implies X->YZ), decomposition (X->YZ implies X->Y and X->Z), and pseudo-transitivity.

6.2 Update Anomalies (the Problem Normalization Solves)

Consider a single, un-normalized relation Enrollment(student_id, student_name, course_id,
course_name, instructor):

• Insertion anomaly: to record that a new course exists, but no student has enrolled yet, we would be
forced to insert a row with a NULL student_id, which may violate a key constraint.
• Deletion anomaly: if the only student enrolled in a course drops it and that row is deleted, we lose
all information about the course (its name, its instructor) along with the student's row.
• Update anomaly: if an instructor's name changes, every row for every student enrolled in that
instructor's course must be updated; missing even one row leaves the data inconsistent.

6.3 Normal Forms

First Normal Form (1NF)
A relation is in 1NF if every attribute contains only atomic (indivisible) values, and each column
contains values of a single type — i.e., there are no repeating groups or multi-valued/composite

23
Database Management Systems — Notes

attributes stored in a single cell.

Second Normal Form (2NF)

A relation is in 2NF if it is in 1NF and every non-prime attribute (an attribute that is not part of any
candidate key) is fully functionally dependent on the whole of every candidate key — i.e., there is no
partial dependency of a non-prime attribute on just part of a composite primary key. 2NF is only a
meaningful concern for relations with a composite primary key.

Third Normal Form (3NF)

A relation is in 3NF if it is in 2NF and no non-prime attribute is transitively dependent on any candidate
key — i.e., for every FD X -> Y in the relation, either X is a superkey, or Y consists entirely of prime
attributes (attributes that belong to some candidate key).

Boyce-Codd Normal Form (BCNF)

A relation is in BCNF if for every non-trivial functional dependency X -> Y that holds in the relation, X is
a superkey. BCNF is a stricter version of 3NF (it drops the exception that allows Y to be prime) and
eliminates all redundancy that can be detected using functional dependencies alone. Every relation in
BCNF is also in 3NF, but not every 3NF relation is in BCNF.

Higher normal forms

• Fourth Normal Form (4NF): a relation in BCNF has no non-trivial multi-valued dependencies other
than a dependency on a superkey (eliminates redundancy caused by independent multi-valued
facts stored in the same relation, e.g., an employee's skills and their children stored together).
• Fifth Normal Form (5NF / PJNF): a relation has no join dependency that is not implied by its
candidate keys — i.e., the relation cannot be losslessly decomposed into smaller relations that,
when joined back together, might produce spurious extra rows.

6.4 Worked Normalization Example

Consider the un-normalized relation:

Orders(order_id, cust_id, cust_name, cust_city, product_id, product_name, unit_price, quant

ity)

FDs:
order_id, product_id -> quantity
cust_id -> cust_name, cust_city
product_id -> product_name, unit_price
order_id -> cust_id

This relation has cust_name and cust_city transitively dependent on order_id (through cust_id), and
product_name/unit_price transitively dependent on order_id (through product_id) — a clear violation
of 3NF. Decomposing it removes the redundancy:

Customer(cust_id, cust_name, cust_city)

Product(product_id, product_name, unit_price)
Order(order_id, cust_id)
OrderItem(order_id, product_id, quantity)

24
Database Management Systems — Notes

Each customer's name/city is now stored exactly once, each product's name/price is stored exactly
once, and the OrderItem relation records only the facts specific to a particular order line — this is now
free of the insertion, deletion, and update anomalies described above.

6.5 Decomposition Properties

• Lossless-join decomposition: when the decomposed relations are naturally joined back together,
the result must reproduce exactly the original relation — no spurious tuples should appear and no
information should be lost. A decomposition of R into R1 and R2 is guaranteed lossless if the
common attributes (R1 ∩ R2) form a superkey of at least one of R1 or R2.
• Dependency preservation: it should be possible to enforce every functional dependency that held
on the original relation by checking constraints only within the individual decomposed relations,
without needing to join them back together.

Note: It is always possible to decompose a relation into BCNF such that the decomposition is lossless, but
it is not always possible to simultaneously guarantee dependency preservation. 3NF, in contrast, can
always be achieved with both properties satisfied simultaneously — this trade-off is one reason 3NF is often
accepted as 'good enough' in practical database design.

25
Database Management Systems — Notes

CHAPTER 7
Transaction Management and the ACID
Properties
A transaction is a single logical unit of work that accesses and possibly modifies the contents of a
database, typically comprising one or more SQL statements. Transactions are the mechanism by
which a DBMS guarantees that the database moves from one consistent state to another, even in the
presence of concurrent access and system failures.

7.1 The ACID Properties

Property Meaning

Atomicity A transaction is treated as a single indivisible unit —

either all of its operations are reflected in the database,
or none are. If a transaction fails partway through, all of
its effects are undone (rolled back).

Consistency Execution of a transaction, taken alone, must move the

database from one consistent state to another — all
integrity constraints must be preserved before and after
the transaction.

Isolation Even though many transactions may execute

concurrently, each transaction must be unaware of other
transactions executing concurrently, and the net effect
must be as if transactions were executed one after
another (serially).

Durability Once a transaction has committed, its changes must

persist in the database even if there is a subsequent
system crash — this is normally guaranteed by writing
changes to non-volatile storage and maintaining logs.

7.2 Transaction States

A transaction moves through a well-defined sequence of states during its lifetime: Active (the initial
state, while it is executing) -> Partially Committed (after the final statement has executed, but before
all changes are guaranteed durable) -> Committed (after successful completion) or, if something goes
wrong, Failed -> Aborted (after the transaction has been rolled back and the database restored to its
state prior to the transaction's start).

7.3 Schedules
A schedule is a sequence that indicates the chronological order in which instructions of concurrent
transactions are executed. A serial schedule is one in which the transactions are executed one
completely after another with no interleaving — serial schedules are always correct (they trivially
preserve consistency, assuming each transaction individually does) but they offer no concurrency and

26
Database Management Systems — Notes

hence poor performance.

Serializability
A schedule is called serializable if its effect on the database is equivalent to that of some serial
schedule of the same transactions. Since serial schedules are known to be correct, a serializable
schedule is guaranteed to leave the database in a consistent state, while still allowing operations from
different transactions to interleave for better performance.

• Conflict serializability: a schedule is conflict-serializable if it can be transformed into a serial

schedule by successive swaps of non-conflicting operations. Two operations conflict if they belong
to different transactions, access the same data item, and at least one of them is a write.
• View serializability: a weaker, more general notion — a schedule is view-serializable if it is 'view
equivalent' to some serial schedule (same initial reads, same final writes, and the same transaction
reads the same value written by the same writer or the initial database in both schedules). Every
conflict-serializable schedule is view-serializable, but not vice versa. Testing view-serializability is
NP-hard in general, so most practical DBMSs test for (and enforce) the stricter
conflict-serializability instead.

Conflict serializability of a given schedule can be tested efficiently by constructing a precedence graph
(serialization graph): a node for every transaction, and a directed edge Ti -> Tj whenever Ti has an
operation that conflicts with, and precedes, an operation of Tj. The schedule is conflict-serializable if
and only if this graph is acyclic.

7.4 Recoverability
• Recoverable schedule: if a transaction Tj reads a data item previously written by Ti, then the
commit operation of Ti must appear before the commit operation of Tj. This guarantees that the
DBMS is never forced to permanently commit a transaction that read uncommitted ('dirty') data
from a transaction that later aborts.
• Cascadeless (avoids cascading rollback) schedule: a transaction is permitted to read a value
written by another transaction only after that other transaction has committed — this prevents a
single abort from forcing a chain of other transactions to also abort.
• Strict schedule: a transaction can neither read nor overwrite a data item written by another
transaction until that other transaction has committed or aborted — strict schedules simplify
recovery, since undoing a transaction just means restoring the old value.

27
Database Management Systems — Notes

28
Database Management Systems — Notes

CHAPTER 8
Concurrency Control
Concurrency control refers to the protocols a DBMS uses to guarantee that concurrently executing
transactions produce a serializable (and hence correct) outcome, without sacrificing more throughput
than necessary.

8.1 Lock-Based Protocols

The most common approach requires a transaction to acquire an appropriate lock on a data item
before accessing it.

Lock mode Compatible with Purpose

Shared lock (S) Other S locks Held to read a data item; multiple
transactions may hold a shared lock
on the same item simultaneously.

Exclusive lock (X) No other locks Held to write a data item; only one
transaction may hold an exclusive
lock on an item, and no other
transaction may hold any lock on it
at the same time.

Two-Phase Locking (2PL) Protocol

Under 2PL, every transaction is divided into two phases:

1 Growing phase: the transaction may acquire locks, but may not release any lock.
2 Shrinking phase: the transaction may release locks, but may not acquire any new lock.
It is a proven theorem that if every transaction in a schedule follows 2PL, the resulting schedule is
guaranteed to be conflict-serializable. Basic 2PL, however, can still suffer from cascading rollbacks
(because locks can be released before commit). Strict 2PL fixes this by holding all exclusive locks until
the transaction commits or aborts, and Rigorous 2PL (the variant most commercial systems actually
use) holds both shared and exclusive locks until commit/abort, which additionally guarantees
strictness and produces a schedule equivalent to the serial order in which transactions committed.

Deadlock
2PL does not prevent deadlock — a cyclic situation where transaction T1 waits for a lock held by T2,
which in turn waits for a lock held by T1. DBMSs handle deadlock either by prevention (e.g., the
wait-die and wound-wait schemes, which use transaction timestamps to decide whether a transaction
should wait or be forced to abort/restart) or by detection and recovery (periodically building a wait-for
graph and aborting a transaction — the 'victim' — whenever a cycle is found).

8.2 Timestamp-Ordering Protocol

29
Database Management Systems — Notes

Each transaction is assigned a unique timestamp when it begins, and every data item records the
timestamp of the most recent transaction that read it (read_TS) and the most recent one that wrote it
(write_TS). The protocol ensures conflicting operations execute in timestamp order: if a transaction
attempts an operation that would violate this order (e.g., it tries to write a value that a 'younger'
transaction has already read), it is rejected and restarted with a new, later timestamp. This guarantees
conflict-serializability without using locks at all, avoiding deadlock entirely, though at the cost of
potentially restarting transactions.

8.3 Multiversion Concurrency Control (MVCC)

Instead of overwriting a data item, MVCC keeps several versions of it, each tagged with the timestamp
(or transaction id) that created it. A read request is served the most recent version that is consistent
with the requesting transaction's own timestamp/snapshot, which means readers never block writers
and writers never block readers. MVCC is the basis of the concurrency control used by PostgreSQL,
Oracle, and MySQL's InnoDB engine, and underlies the SNAPSHOT ISOLATION level available in
most modern DBMSs.

8.4 Optimistic Concurrency Control

Optimistic protocols assume conflicts are rare, so a transaction proceeds without any locking through
a Read phase (data is read and updates are made only to local copies) and a Validation phase (the
DBMS checks whether the transaction's operations would violate serializability against transactions
that committed in the meantime); if validation succeeds, the transaction enters a Write phase and its
local updates are applied to the database; if it fails, the transaction is aborted and restarted.

8.5 SQL Isolation Levels

The SQL standard defines four isolation levels that trade off strict correctness for concurrency
performance, defined in terms of which anomalies they permit:

Isolation level Dirty Read Non-repeatable Read Phantom Read

READ UNCOMMITTED Possible Possible Possible

READ COMMITTED Not possible Possible Possible

REPEATABLE READ Not possible Not possible Possible

SERIALIZABLE Not possible Not possible Not possible

• Dirty read: a transaction reads a value written by another transaction that has not yet committed
(and might later be rolled back).
• Non-repeatable read: a transaction re-reads a row it read before, and finds that another committed
transaction has modified or deleted it in the meantime.
• Phantom read: a transaction re-executes a query with a search condition, and finds that another
committed transaction has inserted new rows that now satisfy that condition.

30
Database Management Systems — Notes

31
Database Management Systems — Notes

CHAPTER 9
Database Recovery Techniques
Recovery is the process by which a DBMS restores the database to a consistent, correct state after a
failure — whether a transaction failure, a system crash, or a media/disk failure. Recovery techniques
rely heavily on maintaining a log: a sequential record of all updates made to the database.

9.1 Types of Failure

• Transaction failure: caused by logical errors (bad input, a constraint violation) or system errors
(e.g., deadlock, forcing the DBMS to abort the transaction).
• System crash: a hardware or software failure (power outage, OS crash) causes the contents of
volatile (main) memory to be lost, but the contents of non-volatile storage (disk) are assumed to
remain intact.
• Disk/media failure: a disk block loses its content, either through a head crash or a failure during a
data-transfer operation — recovery requires a backup copy of the data.

9.2 The Log

The log is a sequence of log records, each recording one write to the database. A typical update log
record has the form , meaning transaction Ti changed data item X from old_value to new_value. In
addition, the log records , , and markers.

Write-Ahead Logging (WAL) rule — before a data item's value is written to the actual database (on
disk), the corresponding log record describing that update must first be written to stable storage.
This guarantees that if the system crashes after a database write but before the log record makes it
to disk, the update could be lost and undetectable — WAL prevents exactly this scenario, and is the
single most important rule underlying crash recovery.

9.3 Deferred vs. Immediate Database Modification

• Deferred update (deferred modification): all writes of a transaction are recorded in the log but not
applied to the database itself until the transaction commits — so recovery after a crash only ever
needs to REDO the committed transactions' writes; there is never a need to UNDO anything, since
uncommitted changes were never written to the database.
• Immediate update (immediate modification): a transaction's writes are applied to the database as
soon as they occur (even before commit), provided the corresponding log record has already been
written (per WAL). Recovery must then both REDO the writes of committed transactions and
UNDO the writes of transactions that were active (uncommitted) at the time of the crash.

9.4 Checkpoints
Scanning the entire log after a crash to determine which transactions to redo/undo becomes
prohibitively slow as the log grows. A checkpoint periodically (a) forces all log records currently in main

32
Database Management Systems — Notes

memory to stable storage, (b) forces all modified buffer (database) pages to disk, and (c) writes a
record to the log, where L is the list of transactions active at checkpoint time. During recovery, the
DBMS only needs to examine the log starting from the most recent checkpoint, since any transaction
that committed before that point is guaranteed to already be durable on disk.

9.5 ARIES Recovery Algorithm

ARIES (Algorithm for Recovery and Isolation Exploiting Semantics) is the industry-standard recovery
algorithm used (in some variant) by most commercial DBMSs. It performs recovery in three sequential
passes over the log:

1 Analysis pass: scans the log forward from the last checkpoint to identify which transactions were
active (need undoing) and which data pages were 'dirty' at the moment of the crash, and
determines the point in the log at which the REDO pass must begin.
2 Redo pass: scans forward from the point determined by the analysis pass, and redoes every
logged update (regardless of whether the transaction that made it eventually committed or aborted)
to restore the database to exactly the state it was in at the instant of the crash — this is the 'repeat
history' principle central to ARIES.
3 Undo pass: scans the log backward, undoing the writes of every transaction that was still active
(had not committed) at the time of the crash, restoring the database to a consistent,
transaction-atomic state.

A key feature of ARIES is that log records themselves carry a Log Sequence Number (LSN), and each
database page stores the LSN of the last log record that updated it — this allows the redo pass to skip
updates that are already reflected in the page on disk, making recovery idempotent (safe to interrupt
and restart, since a crash during recovery itself simply causes the whole process to run again).

9.6 Buffer Management Policies

Policy Options Impact

Steal Steal / No-Steal 'Steal' allows an uncommitted

transaction's dirty pages to be
written to disk before commit
(needed under memory pressure),
which then requires an UNDO
capability during recovery.

Force Force / No-Force 'Force' requires all of a transaction's

dirty pages to be written to disk at
commit time (guarantees durability
immediately, but hurts performance);
'No-Force' (used by most systems)
defers those writes, relying on
REDO during recovery to
reconstruct them from the log.

33
Database Management Systems — Notes

34
Database Management Systems — Notes

CHAPTER 10
Storage Structures, File Organization, and
Indexing

10.1 Storage Hierarchy

A DBMS deals with several classes of storage media that differ in speed, cost, and volatility: cache
and main memory (fast, volatile, expensive per byte), flash/SSD storage (non-volatile, moderately
fast), magnetic disk (non-volatile, slower, cheap, the primary medium for most databases) and
offline/tertiary storage such as tape (used for backups and archival). Data is transferred between disk
and main memory in fixed-size units called blocks or pages, and minimizing the number of block
transfers ('disk I/Os') is the central concern of physical database design.

10.2 File Organization

File organization refers to the way records of a table are physically arranged on disk within blocks.

Organization Description Best for

Heap (unordered) file Records are placed in the file in no Fast inserts; full table scans; small
particular order, typically in insertion tables.
order.

Sequential (sorted) file Records are physically sorted on a Range queries and ordered retrieval
chosen ordering (search) key. on the sort key; but expensive to
maintain the order on insert/delete.

Hash file Records are placed into buckets Very fast exact-match lookups on
based on applying a hash function to the hash key; poor for range queries.
a chosen hash key.

Clustered file Records from two or more related Speeding up joins that are almost
tables that are frequently joined always executed together.
together are stored physically near
each other.

10.3 Indexing
An index is an auxiliary access structure built on one or more columns of a table, designed to speed
up retrieval of records that satisfy a given search condition, at the cost of extra storage space and the
overhead of maintaining the index whenever the underlying table changes.

35
Database Management Systems — Notes

Index type Definition

Primary index An ordered file whose records have a fixed length with
two fields; the first holds a value of the primary key of the
data file, and the second is a pointer to the
corresponding data block; built only on a data file
ordered on its key field.

Clustering index Similar to a primary index, but built on a non-key

ordering field of the data file (a field whose values are
not necessarily unique) — a table can have at most one
clustering index, since the data file can be physically
sorted in only one way.

Secondary index An ordered file with an entry for every record (not just
every distinct block, as with a primary/clustering index) of
the data file, built on any non-ordering field. A table can
have any number of secondary indexes.

Dense index Has an index entry for every search-key value (and
hence every record) in the data file.

Sparse index Has an index entry only for some of the search-key
values (typically one per block), requiring a subsequent
scan within the block to locate the exact record.

Multilevel index An index built on top of another index (recursively),

reducing the number of disk I/Os needed to search a
very large first-level index.

10.4 B-Tree and B+-Tree Indexes

Almost all commercial relational DBMSs implement their indexes using a B+-tree, a balanced,
self-maintaining, multi-level tree structure specifically designed to minimize disk I/O for both
exact-match and range queries.

A B+-tree index — internal nodes only guide the search; all actual data pointers live in the leaf nodes, which are
chained together for fast range scans.

36
Database Management Systems — Notes

• Internal (non-leaf) nodes contain only search-key values and pointers to child nodes, used purely
to guide the search down the tree; they contain no data pointers themselves.
• Leaf nodes contain every search-key value along with either the actual data record or a pointer to
it, and are linked together in a doubly linked list, so once the search reaches the correct leaf, a
range query can be answered by simply following these leaf-level links sequentially rather than
re-traversing the tree.
• The tree is always kept height-balanced — every path from the root to a leaf has the same length
— which guarantees that lookups, insertions, and deletions all run in O(log n) time even in the
worst case, regardless of the pattern of past insertions/deletions.
• A B-tree (without the '+') differs in that data pointers are also stored in internal nodes, which saves
some space but forecloses the leaf-chaining trick, making B-trees less common than B+-trees in
practice for range-heavy relational workloads.

10.5 Hash-Based Indexing

• Static hashing: the number of buckets is fixed at creation time, so performance degrades as the file
grows and buckets begin to overflow.
• Extendible hashing: uses a directory of pointers to buckets that can dynamically double in size, so
only the affected bucket (and the directory) needs to be reorganized on overflow, avoiding a full-file
reorganization.
• Linear hashing: grows the file by splitting buckets one at a time, in a fixed round-robin order,
avoiding the need for a directory altogether.

10.6 Bitmap Indexes

A bitmap index is built on a column with a small number of distinct values (low cardinality, e.g., gender
or a status flag); it stores one bit vector per distinct value, with a 1 in position i if row i has that value.
Bitmap indexes are extremely compact and support very fast AND/OR/NOT combinations across
multiple conditions using simple bitwise operations, making them popular in data-warehouse and
analytical (OLAP) workloads, though they are poorly suited to columns with high cardinality or to
tables with heavy write traffic.

37
Database Management Systems — Notes

CHAPTER 11
Query Processing and Optimization
Query processing is the sequence of steps a DBMS takes to translate a high-level declarative query
(SQL) into a low-level, efficient sequence of operations on the physical data, and then execute it.

11.1 The Query Processing Pipeline

1 Parsing and translation: the SQL query is checked for correct syntax, verified against the system
catalog (do the referenced tables/columns exist, does the user have permission), and translated
into an internal representation, typically a relational-algebra expression or a query tree/graph.
2 Optimization: the query optimizer examines multiple algebraically equivalent expressions for the
same query, and multiple possible execution plans (which algorithm to use for each join, which
index to use for each selection, in what order to perform the joins), and chooses the plan with the
estimated lowest cost.
3 Evaluation (execution): the query-evaluation engine executes the chosen plan and returns the
result to the user.

11.2 Cost Estimation

The optimizer estimates the cost of a plan primarily in terms of the number of disk block transfers it will
require (since disk I/O dominates total query time), relying on statistics maintained in the system
catalog: the number of tuples and blocks in each relation, the number of distinct values in each
column, and the height/depth of any available indexes.

11.3 Algorithms for Selection

Algorithm When used

Linear (full table) scan Always applicable; examines every block of the file.

Binary search Applicable when the file is physically sorted on the

comparison attribute.

Primary/clustering index lookup Applicable for an equality comparison on the indexed

ordering field.

Secondary index lookup Applicable for an equality comparison on any indexed

field, but can be costly for a large result set since each
matching record may reside in a different block.

11.4 Algorithms for Join

38
Database Management Systems — Notes

Algorithm Basic idea Typical cost driver

Nested-loop join For every tuple in the outer relation, O(|R| x |S|) in the worst case — the
scan the entire inner relation looking simplest but generally the slowest
for matches. algorithm.

Block nested-loop join A refinement that processes the Number of blocks of the outer
inner relation one block at a time relation.
against an entire block of the outer
relation held in memory, reducing
the number of times the inner
relation must be re-scanned.

Index nested-loop join For each tuple of the outer relation, Requires a suitable index on the
use an index on the join attribute of inner relation's join attribute.
the inner relation to directly retrieve
matching tuples, instead of
scanning.

Sort-merge join Both relations are sorted (or already Cost of sorting each relation (if not
ordered via an index) on the join already sorted), then a linear merge
attribute, and then merged in a pass.
single coordinated linear pass,
similar to the merge step of
merge-sort.

Hash join A hash function is applied to the join Very efficient when the smaller
attribute of the smaller ('build') relation's hash table fits in memory;
relation to partition it into an the standard default algorithm in
in-memory hash table; the larger most modern optimizers for
('probe') relation is then scanned equijoins.
once, and each tuple's hash value is
used to find matches directly.

11.5 Heuristic (Rule-Based) Query Optimization

In addition to (or before) cost-based optimization, a query tree can be improved using a set of heuristic
transformation rules that are known to be safe (they never make things worse) and are cheap to apply:

• Push SELECT operations down the query tree as early as possible (perform selections/filters
before joins), since this reduces the number of tuples that later, more expensive operations must
process.
• Push PROJECT operations down the tree similarly, keeping only the attributes actually needed at
each step, to reduce the size of intermediate results.
• Combine a CARTESIAN PRODUCT immediately followed by a SELECT into a single, more
efficient JOIN operation.
• Reorder the sequence of JOIN operations so that the join producing the smallest intermediate
result executes first.
• Perform SELECT and PROJECT operations before any JOIN, so that the relations being joined are
as small as possible.

11.6 Materialized Views

39
Database Management Systems — Notes

Unlike an ordinary view, a materialized view physically stores the result of its defining query, trading
extra storage space and the need for periodic refresh against significantly faster read performance —
a common technique for pre-computing expensive aggregate queries in data-warehouse and reporting
systems.

40
Database Management Systems — Notes

CHAPTER 12
An Introduction to Distributed Databases
and NoSQL Systems

12.1 Distributed Databases

A distributed database is a single logical database whose data is physically stored across multiple,
often geographically separated, sites, each managed by (possibly different) DBMS software, but
which together present a unified view to applications.

• Fragmentation: dividing a relation into smaller pieces distributed across sites. Horizontal
fragmentation splits a relation by rows (each site gets a subset of the tuples, e.g., by region);
vertical fragmentation splits it by columns (each site gets a subset of the attributes, typically
together with the primary key so the pieces can be rejoined).
• Replication: storing copies of the same data at multiple sites, improving availability and read
performance, at the cost of extra work needed to keep the copies synchronized.
• Distributed transactions and the Two-Phase Commit (2PC) protocol: to keep a transaction that
touches multiple sites atomic, a coordinator first asks every participating site to 'prepare' (and
confirm it can commit) in a voting phase, and only issues the actual 'commit' to every site in a
second phase if all sites voted yes — guaranteeing that either every site commits or every site
aborts.

12.2 The CAP Theorem

The CAP theorem states that a distributed data store can provide at most two of the following three
guarantees simultaneously in the presence of a network partition: Consistency (every read receives
the most recent write, or an error), Availability (every request receives a non-error response, without a
guarantee it contains the most recent write), and Partition tolerance (the system continues to operate
despite an arbitrary number of messages being dropped or delayed by the network). Because network
partitions cannot be avoided in a real distributed system, the practical choice most systems face is
between prioritizing consistency (CP systems) or availability (AP systems) whenever a partition
actually occurs.

12.3 BASE vs. ACID

Many distributed NoSQL systems deliberately relax the ACID guarantees in favour of BASE: Basically
Available, Soft state (the state of the system may change over time even without new input, as
replicas converge), and Eventual consistency (if no new updates are made, all replicas will eventually
converge to the same value, though they may be temporarily inconsistent).

12.4 NoSQL Data Models

41
Database Management Systems — Notes

Category Data model Example systems Typical use case

Key-Value stores A simple map from a Redis, DynamoDB, Riak Caching, session storage,
unique key to an opaque simple lookups at very
value/blob. high throughput.

Document stores Semi-structured, MongoDB, CouchDB Content management,

self-describing documents catalogs, flexible/evolving
(typically JSON/BSON), schemas.
where different documents
in the same collection may
have different fields.

Column-family Data organized into rows Apache Cassandra, Very large-scale,

(wide-column) stores with a flexible, dynamically HBase high-write-throughput,
extensible set of columns time-series or log data.
grouped into 'column
families'.

Graph databases Data modeled explicitly as Neo4j, Amazon Neptune Social networks,
nodes and the (typed, recommendation engines,
directed) edges between fraud detection,
them, optimized for knowledge graphs.
traversal.

12.5 SQL vs. NoSQL — Quick Comparison

Aspect Relational (SQL) NoSQL

Schema Fixed, defined in advance Flexible/dynamic, often applied at

(schema-on-write) read time (schema-on-read)

Scaling Traditionally scales vertically (a Designed to scale horizontally (more

bigger machine) machines/shards)

Consistency model Strong consistency, full ACID Often eventual consistency (BASE),
transactions though many modern systems now
offer tunable/strong consistency too

Query language Standardized SQL Varies by product — no single

universal standard

Best fit Structured data with complex Very large, fast-growing, or

relationships and multi-row semi-structured/unstructured
transactional integrity requirements datasets that need horizontal scale

42