Databases

GATE (CS/IT) Exam Preparation Notes — ER Model, Relational Model, SQL, Normalization, File
Organization, Indexing, Transactions & Concurrency Control

These notes explain every topic in the Databases syllabus in plain language, with definitions, worked examples, and
comparison tables designed for quick revision. Read each section in order — later topics (normalization, indexing,
concurrency control) build on the relational model concepts introduced early on.

Contents
• 1. ER Model
• 2. Relational Model (Relational Algebra, Tuple Calculus, SQL)
• 3. Integrity Constraints
• 4. Normal Forms
• 5. File Organization
• 6. Indexing (B-Trees and B+ Trees)
• 7. Transactions and Concurrency Control
• Exam Note: System Documentation (high-yield recurring short answer)

1. Entity–Relationship (ER) Model

The ER model is a conceptual (high-level) data model used at the design stage to describe the structure of a database
independent of how it will actually be implemented in a DBMS. It represents the real world as a collection of entities
and the relationships among them, and is usually drawn as an ER diagram before being converted into relational
tables.

1.1 Basic Building Blocks

• Entity: a real-world object or concept that can be distinguished from all other objects, e.g. a particular
student, a particular course.
• Entity Set: a collection of entities of the same type that share the same attributes, e.g. the set of all Student
entities.
• Attribute: a property that describes an entity, e.g. Name, Roll_No, DOB for a Student entity.
• Domain: the set of permitted values for an attribute, e.g. the domain of Age is positive integers.

Types of Attributes
• Simple vs Composite: a simple attribute cannot be divided further (e.g. Roll_No); a composite attribute can
be split into sub-parts (e.g. Name → First_Name + Last_Name).
• Single-valued vs Multi-valued: a single-valued attribute holds one value per entity (e.g. DOB); a multi-valued
attribute can hold several values (e.g. Phone_Numbers), shown in ER diagrams with a double ellipse.
• Stored vs Derived: a stored attribute is saved directly in the database (e.g. DOB); a derived attribute is
computed from another attribute (e.g. Age derived from DOB), shown with a dashed ellipse.
• Key Attribute: an attribute (or set of attributes) whose value uniquely identifies each entity in the entity set;
shown underlined in ER diagrams.

1.2 Relationships
• Relationship: an association between two or more entities, e.g. a Student ENROLLS_IN a Course.
• Relationship Set: a collection of relationships of the same type.
 • Degree of a relationship: the number of entity sets participating: unary (recursive, one entity set, e.g.
Employee SUPERVISES Employee), binary (two entity sets — the most common case), or ternary (three entity
sets).
A relationship set can itself have descriptive attributes. For example, the ENROLLS_IN relationship between Student
and Course might carry an attribute Grade, because the grade only makes sense in the context of a specific student–
course pair, not for the student or course alone.

1.3 Keys
• Super Key: any set of attributes that can uniquely identify a tuple/entity (may contain extra, unnecessary
attributes).
• Candidate Key: a minimal super key — no attribute can be removed from it without losing the uniqueness
property.
• Primary Key: the candidate key chosen by the database designer to identify tuples; cannot be NULL.
• Alternate Key: a candidate key that was not chosen as the primary key.
• 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 tables.

1.4 Mapping Cardinalities and Participation

Mapping cardinality (or cardinality ratio) expresses how many entities of one set can be associated with how many
entities of another set, through a given relationship set.

Cardinality Meaning Example

One entity of A relates to at most one entity of B, and A Person has one Passport; a Passport
One-to-One (1:1)
vice versa. belongs to one Person.
One entity of A relates to many entities of B, but each
One-to-Many (1:N) One Department has many Employees.
B relates to only one A.
Many Employees work in one
Many-to-One (N:1) Many entities of A relate to one entity of B.
Department.
A Student enrolls in many Courses; a
Many-to-Many (M:N) Many entities of A relate to many entities of B.
Course has many Students.

• Total participation: every entity in the entity set must participate in at least one relationship (shown with a
double line in an ER diagram).
• Partial participation: some entities may not participate in the relationship at all (shown with a single line).

1.5 Weak Entities

A weak entity is an entity that does not have enough attributes of its own to form a primary key; it depends on a
strong (owner) entity for its identification. It is linked to its owner through an identifying relationship, and is uniquely
identified only by combining the owner's primary key with its own partial key (called a discriminator).
Example: a Dependent (relative of an employee) may only have a Name, which is not unique on its own. Dependent
becomes a weak entity, identified by (Employee_ID, Dependent_Name), where Employee_ID comes from the
owning strong entity Employee.
Notation: a weak entity set is drawn as a double rectangle, its identifying relationship as a double diamond, and its
discriminator attribute is underlined with a dashed line (partial key) rather than a solid line.

1.6 ER Diagram Notation — Quick Reference

Symbol Represents
Rectangle Entity set
 Symbol Represents
Double Rectangle Weak entity set
Ellipse Attribute
Double Ellipse Multi-valued attribute
Dashed Ellipse Derived attribute
Underlined attribute Key attribute
Diamond Relationship set
Double Diamond Identifying relationship (for a weak entity)
Line Links entities to relationships / attributes
Double Line Total participation

1.7 Extended ER (EER) Features

• Specialization: a top-down process of designating sub-groupings (subclasses) within an entity set based on
distinguishing characteristics, e.g. Employee specialized into Engineer and Manager.
• Generalization: the reverse, bottom-up process — combining several entity sets that share common
attributes into a single higher-level (super-class) entity set, e.g. Car and Truck generalized into Vehicle.
• Attribute inheritance: a lower-level (sub-class) entity inherits all attributes and relationships of the higher-
level (super-class) entity.
• Disjoint vs Overlapping constraint: in disjoint specialization an entity can belong to only one subclass at a
time; in overlapping specialization an entity may belong to more than one subclass simultaneously.
• Total vs Partial specialization: total specialization requires every entity in the super-class to belong to some
subclass; partial specialization allows entities that belong to no subclass.
• Aggregation: a technique that treats a relationship set as a higher-level abstract entity so that it can
participate in relationships with other entity sets. It is used when a relationship needs to be connected to
another relationship.

1.8 Reducing an ER Diagram to Relational Tables

Once the ER diagram is finalized, it is converted into relational schema using the following standard mapping rules —
a favourite source of GATE questions:
1. Strong entity → one table containing all its simple/derived-excluded attributes, with the entity's key as the
table's primary key.
2. Weak entity → one table containing its own attributes plus the primary key of its owner entity (as a foreign
key); the table's primary key is the combination of the owner's key and the weak entity's partial key.
3. Composite attribute → flattened into its constituent simple attributes as separate columns; the composite
attribute itself is not stored as a column.
4. Multi-valued attribute → converted into a brand-new table containing the entity's primary key plus the
multi-valued attribute, since a single column cannot hold multiple values (this avoids violating First Normal
Form — see Section 4).
5. 1:1 relationship → merge by placing the primary key of either entity as a foreign key in the other entity's
table (preferably the entity with total participation), or create a separate table if both sides are optional.
6. 1:N relationship → place the primary key of the "1" side as a foreign key in the table of the "N" side.
7. M:N relationship → create a brand-new table containing the primary keys of both participating entities
(together forming the composite primary key) plus any descriptive attributes of the relationship itself.
2. Relational Model
The relational model represents data as a collection of relations (tables). It was proposed by E. F. Codd and is the
theoretical foundation on which SQL and virtually all traditional DBMSs are built.

2.1 Basic Terminology

Formal term Everyday term
Relation Table
Tuple Row / record
Attribute Column / field
Domain Set of allowed values for an attribute
Degree Number of attributes (columns) in a relation
Cardinality Number of tuples (rows) in a relation instance
Relation Schema The table's structure/name and its attributes, e.g. Student(Roll_No, Name, Dept)
Relation Instance The actual data currently stored in the table at a point in time

Two sample relations are used throughout this section for illustration:
Student(Roll_No, Name, Dept, Age)
Enrollment(Roll_No, Course_Id, Grade)
Course(Course_Id, Title, Credits)

2.2 Relational Algebra

Relational algebra is a procedural query language: a query is expressed as a sequence of operations applied to
relations, where each operation takes one or two relations as input and produces a new relation as output (this
closure property is what allows operations to be composed/nested).

Fundamental (Basic) Operators

• Selection (σ): chooses tuples that satisfy a given condition. σ(condition)(R) filters rows without changing the
columns. Example: σ(Dept='CSE')(Student) — all CSE students.
• Projection (π): chooses specified columns and removes duplicate rows from the result. π(Name,Dept)
(Student) — only the Name and Dept columns, with duplicates eliminated.
• Union (∪): combines tuples from two relations, removing duplicates. Requires union-compatibility: both
relations must have the same number of attributes with matching domains.
• Set Difference (−): R − S returns tuples that are in R but not in S. Also requires union-compatibility.
• Cartesian Product (×): R × S pairs every tuple of R with every tuple of S, producing a relation whose degree is
the sum of the degrees of R and S, and whose cardinality is the product of their cardinalities.
• Rename (ρ): ρ(x)(R) renames the relation R (and optionally its attributes) to x, useful for self-joins and multi-
step expressions.

Derived Operators (built from the fundamental ones)

• Intersection (∩): R ∩ S = R − (R − S); returns tuples common to both relations.
• Theta Join (⋈θ): R ⋈θ S = σθ(R × S); a Cartesian product followed by a selection on some condition θ.
• Equijoin: a theta join where the condition θ uses only the equality (=) operator.
• Natural Join (⋈): an equijoin performed automatically over all attributes with the same name in both
relations, with the duplicate (common) columns appearing only once in the result. Example: Student ⋈
Enrollment joins on the common attribute Roll_No.
 • Outer Joins: preserve unmatched tuples by padding missing attribute values with NULL. Left outer join keeps
all tuples of the left relation, right outer join keeps all tuples of the right relation, and full outer join keeps all
tuples of both.
• Division (÷): R ÷ S returns tuples of R that are associated with every tuple in S. It is the natural operator for
"for all" style queries, e.g. find students who have enrolled in every course offered.

Worked Example (Relational Algebra)

Query: Find the names of students enrolled in the course with Course_Id = 'CS101'.
π(Name) ( σ(Course_Id='CS101') (Student ⋈ Enrollment) )

Reading it inside-out: first join Student and Enrollment on Roll_No (natural join), then select only rows where
Course_Id = 'CS101', then project just the Name column.

2.3 Tuple Relational Calculus (TRC)

Unlike relational algebra, which is procedural (it specifies how to get the result step by step), tuple calculus is a
declarative language — it specifies what result is wanted, using a predicate (condition) that the result tuples must
satisfy, without stating the sequence of operations.
A TRC query has the general form:
{ t | P(t) }

This is read as: "the set of all tuples t such that predicate P(t) is true." Here t is a tuple variable, and P is a formula
that may use logical connectives (∧ AND, ∨ OR, ¬ NOT) and quantifiers:
• Existential quantifier (∃): ∃t(P(t)) is true if there exists at least one tuple t for which P(t) holds.
• Universal quantifier (∀): ∀t(P(t)) is true only if P(t) holds for every possible tuple t.
• Free vs Bound variable: a tuple variable is bound if it is quantified by ∃ or ∀ inside the formula; otherwise it
is free. Only the free variable(s) named before the "|" appear in the final answer.
Worked Example: Find the names of students enrolled in course 'CS101' (same query as above, in TRC):
{ t | ∃ s ∈ Student, ∃ e ∈ Enrollment
( s.Roll_No = e.Roll_No ∧ e.Course_Id = 'CS101' ∧ [Link] = [Link] ) }

This reads: "give me all tuples t (with a Name field) such that there exist a Student tuple s and an Enrollment tuple e
where their Roll_No values match, the enrollment's Course_Id is 'CS101', and t's Name equals s's Name."
A closely related declarative language, Domain Relational Calculus (DRC), expresses the same idea but uses domain
variables that range over single attribute values instead of whole tuples: { <x1, x2, ..., xn> | P(x1, ..., xn) }. Both TRC
and DRC have the same expressive power as relational algebra — a result known as relational completeness.

2.4 SQL (Structured Query Language)

SQL is the standard language for defining, manipulating, and controlling relational databases. It combines DDL, DML,
DCL and TCL sub-languages in a single syntax.

Category Purpose Key commands

DDL — Data Definition Language Defines/modifies the structure of database objects. CREATE, ALTER, DROP, TRUNCATE
DML — Data Manipulation
Manipulates the data stored inside tables. SELECT, INSERT, UPDATE, DELETE
Language
DCL — Data Control Language Controls access/permissions on data. GRANT, REVOKE
TCL — Transaction Control
Manages the effects of transactions. COMMIT, ROLLBACK, SAVEPOINT
Language

Anatomy of a SELECT Statement

SELECT <columns / expressions>
 FROM <table(s)>
WHERE <row-level filter condition>
GROUP BY <grouping columns>
HAVING <group-level filter condition>
ORDER BY <sort columns> [ASC | DESC];

Conceptual order of execution (important for understanding, and frequently tested): FROM → WHERE → GROUP BY
→ HAVING → SELECT → ORDER BY. This is why WHERE cannot refer to an aggregate (it runs before grouping), while
HAVING can.
• WHERE vs HAVING: WHERE filters individual rows before any grouping takes place; HAVING filters entire
groups after aggregate functions (COUNT, SUM, AVG, MIN, MAX) have been computed.

Aggregate Functions
• COUNT(*): counts the number of rows (including rows with NULLs); COUNT(column) counts only non-NULL
values of that column.
• SUM, AVG: total and average of a numeric column (NULLs are ignored).
• MIN, MAX: smallest and largest value of a column.
Example — average marks per department, only for departments with more than 50 students:
SELECT Dept, AVG(Marks) AS Avg_Marks
FROM Student
GROUP BY Dept
HAVING COUNT(*) > 50;

Joins in SQL
Join type Behaviour
INNER JOIN Returns only rows that have matching values in both tables.
LEFT OUTER JOIN All rows of the left table, with NULLs for unmatched right-table columns.
RIGHT OUTER JOIN All rows of the right table, with NULLs for unmatched left-table columns.
FULL OUTER JOIN All rows from both tables, NULLs wherever there is no match on either side.
CROSS JOIN Cartesian product of the two tables — every row of one paired with every row of the other.
NATURAL JOIN An inner join performed automatically over all identically-named columns.
A table joined with itself (using aliases), e.g. to find employees and their managers within one
SELF JOIN
Employee table.

Subqueries
• Nested subquery: a SELECT statement inside another SQL statement's WHERE/FROM/SELECT clause; often
combined with IN, ANY, ALL, or EXISTS.
• Correlated subquery: an inner query that references a column from the outer query, and is therefore re-
evaluated once for every row processed by the outer query.
Example — students who scored more than the department average (correlated subquery):
SELECT Name, Dept, Marks
FROM Student S1
WHERE Marks > (SELECT AVG(Marks)
FROM Student S2
WHERE [Link] = [Link]);

Set Operations
• UNION: combines results of two SELECT statements, removing duplicate rows (requires the same
number/type of columns in both queries).
• UNION ALL: same as UNION but keeps duplicate rows (faster, since no duplicate-elimination pass is needed).
• INTERSECT: returns only rows common to both result sets.
 • EXCEPT / MINUS: returns rows present in the first result set but not in the second.

Views, NULLs, and Constraints in SQL

• View: a virtual table defined by a stored SELECT query; it has no data of its own and is recomputed (or
materialized) when queried, created using CREATE VIEW view_name AS SELECT ...
• NULL handling: NULL represents an unknown/missing value. Comparisons with NULL using =, <, > always
yield UNKNOWN (not TRUE or FALSE); the correct tests are IS NULL and IS NOT NULL. SQL uses three-valued
logic: TRUE, FALSE, UNKNOWN.

3. Integrity Constraints
Integrity constraints are rules that restrict the data that can be stored in a database, ensuring accuracy and
consistency. They can be checked automatically by the DBMS.
• Domain constraint: every attribute value must belong to the declared domain (data type and allowed range)
of that attribute, e.g. Age must be a positive integer.
• Key constraint (uniqueness): no two tuples in a relation may have the same value for the primary key (or
any declared candidate key).
• Entity integrity constraint: no attribute that is part of the primary key may contain a NULL value, since NULL
cannot uniquely identify a tuple.
• Referential integrity constraint: a foreign key value must either match some existing primary key value in
the referenced relation, or be entirely NULL — it can never point to a non-existent tuple.
• NOT NULL constraint: explicitly disallows NULL for a given column, even if that column is not part of the
primary key.
• CHECK constraint: a boolean condition that every row must satisfy, e.g. CHECK (Age >= 18).
• Assertion: a general constraint on the database as a whole (possibly spanning multiple tables), automatically
checked whenever any relevant table is modified, e.g. "the total number of enrolled students in a course
must never exceed its seat capacity."
• Trigger: a stored procedure that is automatically executed ("fires") in response to a specified event (INSERT,
UPDATE, or DELETE) on a specified table, used to enforce complex business rules or maintain derived/audit
data.

Referential Integrity — ON DELETE / ON UPDATE Actions

Action Effect when the referenced (parent) row is deleted/updated
CASCADE Automatically deletes/updates the matching child rows as well.
SET NULL Sets the foreign key of matching child rows to NULL.
RESTRICT / NO ACTION Rejects the delete/update operation if matching child rows exist.
SET DEFAULT Sets the foreign key of matching child rows to a predefined default value.

4. Normal Forms
Normalization is the process of organizing attributes into relations to minimize data redundancy and eliminate
undesirable characteristics called anomalies. Without proper normalization, insertion, deletion and update
anomalies can occur — e.g. deleting the last student from a department in a poorly designed table might
accidentally delete all information about that department too.

4.1 Functional Dependencies (FD)

A functional dependency X → Y ("X determines Y", or "Y is functionally dependent on X") means that whenever two
tuples agree on the values of attribute set X, they must also agree on the values of attribute set Y. FDs express
business rules/constraints inherent to the data, e.g. Roll_No → Name means a Roll_No uniquely determines the
student's Name.
• Trivial FD: X → Y where Y is a subset of X — always holds and adds no information.
• Armstrong's Axioms: a sound and complete set of inference rules for deriving all FDs implied by a given set
F:
◦ Reflexivity: if Y ⊆ X, then X → Y.
◦ Augmentation: if X → Y, then XZ → YZ for any Z.
◦ Transitivity: if X → Y and Y → Z, then X → Z.
• Additional (derived) rules: Union: X→Y and X→Z imply X→YZ. Decomposition: X→YZ implies X→Y and X→Z.
Pseudotransitivity: X→Y and WY→Z imply WX→Z.
• Attribute closure (X+): the set of all attributes that are functionally determined by X, given a set of FDs F.
Computing X+ is the standard technique for finding candidate keys and checking whether a given FD is
implied by F (Y is implied by F if Y ⊆ X+).

Worked Example — Finding Candidate Keys via Closure

Given relation R(A, B, C, D, E) with functional dependencies F = { A → B, BC → D, D → E }, find the candidate key(s).
Step 1: Try AC+ (attributes appearing only on the left side, or not implied
elsewhere, are good starting guesses)
Start: {A, C}
A → B => add B => {A, B, C}
BC → D => add D => {A, B, C, D}
D → E => add E => {A, B, C, D, E} = all attributes
So AC+ = {A,B,C,D,E} --> AC is a super key.

Step 2: Check minimality

A+ = {A,B} (does not contain C, D, E) -> A alone is not enough
C+ = {C} -> C alone is not enough
Since removing either A or C from {A,C} loses the 'determines everything'
property,
AC is minimal => AC is a CANDIDATE KEY.

4.2 Normal Forms Hierarchy

Each normal form is a stricter constraint than the one before it: 1NF ⊃ 2NF ⊃ 3NF ⊃ BCNF ⊃ 4NF (every relation in
BCNF is automatically in 3NF, every relation in 3NF is automatically in 2NF, and so on).

First Normal Form (1NF)

A relation is in 1NF if every attribute contains only atomic (indivisible) values — no repeating groups and no multi-
valued or composite attributes stored directly as a single column value.

Second Normal Form (2NF)

A relation is in 2NF if it is in 1NF and has no partial dependency — i.e., no non-prime attribute (an attribute that is
not part of any candidate key) is functionally dependent on only part of a composite candidate key. 2NF issues can
only arise when the primary key has more than one attribute.

Third Normal Form (3NF)

A relation is in 3NF if it is in 1NF and, for every non-trivial functional dependency X → A, at least one of the following
holds: (a) X is a super key, OR (b) A is a prime attribute (part of some candidate key). Equivalently, 3NF forbids
transitive dependency of a non-prime attribute on a candidate key through another non-prime attribute.

Boyce-Codd Normal Form (BCNF)

A relation is in BCNF if, for every non-trivial functional dependency X → A, X must be a super key — the "OR A is
prime" escape clause of 3NF is removed. BCNF is therefore strictly stronger than 3NF.
Worked Example — 3NF but not BCNF (classic GATE-style question)
Relation R(A, B, C) with FDs: AB → C and C → B.
Candidate keys:
AB+ = {A,B,C} = all attributes -> AB is a candidate key
AC+ = {A,C,B} = all attributes -> AC is also a candidate key
(B alone, C alone do not determine everything)

Prime attributes = attributes appearing in ANY candidate key = {A, B, C} (i.e. ALL
attributes are prime)

3NF check: the only non-trivial FDs are AB->C (AB is a superkey - OK) and C->B (B is
prime - OK)
=> Every FD satisfies the 3NF condition => R IS in 3NF.

BCNF check: for C -> B, is C a super key? C+ = {B,C} (missing A) => C is NOT a
super key
=> R VIOLATES BCNF, even though it is in 3NF.

This example is important because it shows precisely why BCNF is stricter than 3NF: 3NF forgives a violation if the
dependent attribute happens to be prime, while BCNF does not.

Multivalued Dependency (MVD) and Fourth Normal Form (4NF)

A multivalued dependency X →→ Y means that for a given value of X, there is a set of values of Y associated with it,
independent of the other attributes in the relation. MVDs typically arise when two independent multi-valued facts
about the same entity are stored in a single table, causing redundant combinations.
A relation is in 4NF if it is in BCNF and has no non-trivial multivalued dependency X →→ Y unless X is a super key.
Decomposing a relation to remove a harmful MVD (splitting the two independent multi-valued facts into two
separate tables) resolves the redundancy.

4.3 Decomposition Properties

When a relation is split (decomposed) into smaller relations during normalization, two properties should ideally be
preserved:
• Lossless-Join Decomposition: joining the decomposed relations back together (via natural join) must
reproduce exactly the original relation — no spurious (extra, incorrect) tuples should appear, and no
information should be lost. A decomposition of R into R1 and R2 is lossless if and only if the common
attributes (R1 ∩ R2) form a super key of at least one of R1 or R2.
• Dependency-Preserving Decomposition: every functional dependency in the original set F must be
enforceable by examining only one of the decomposed relations, without needing to reconstruct the original
relation via a join. This lets the DBMS check constraints efficiently.
A key GATE fact: it is always possible to decompose a relation into 3NF such that the decomposition is both lossless-
join and dependency-preserving (the "3NF synthesis algorithm" guarantees this). However, it is not always possible
to achieve BCNF while also preserving all dependencies — sometimes BCNF decomposition sacrifices dependency
preservation to guarantee losslessness.

5. File Organization
File organization refers to the way records are physically arranged/stored on secondary storage (disk), which directly
affects how efficiently records can be inserted, deleted, and retrieved.

5.1 Types of File Organization

Organization How it works Strengths / Weaknesses
Very fast insertion; but searching for a
New records are simply appended at the end of the
Heap (Pile) file record requires scanning the entire file on
file, in no particular order.
average (O(n)).
 Organization How it works Strengths / Weaknesses
Fast for range queries and ordered access
(binary search possible); insertion/deletion is
Records are stored in physical order sorted by a key
Sequential file expensive because the file may need
field.
reorganizing to maintain order (often
handled via an overflow area).
Very fast for exact-match/equality search
A hash function maps each record's key to a (O(1) on average); poor for range queries
Hashed file
specific bucket/block address. since sorted order is not maintained; may
suffer from bucket overflow.
Records from one or more related tables that are
Speeds up queries that retrieve many
frequently accessed together are stored physically
Clustered file records sharing a clustering value; but only
close on disk (often ordered by a non-key clustering
one clustering order is possible per file.
field).

5.2 Hashing in Detail

• Static hashing: the number of buckets is fixed at the time the file is created. If data grows beyond the
buckets' capacity, bucket overflow occurs and must be handled using an overflow chain (linked overflow
buckets) or open addressing (probing for the next free slot).
• Dynamic hashing (Extendible hashing): the hash address space can grow or shrink as the file grows or
shrinks, using a directory of pointers to buckets, so the whole file does not need to be reorganized at once —
only the directory (which can double in size) and possibly a single bucket that is split.

6. Indexing
An index is an auxiliary data structure that speeds up retrieval of records from a file, in exchange for some extra
storage space and index-maintenance overhead on insertions/deletions. Without an index, answering a query
requires a full linear scan of the file.

6.1 Types of Ordered Indexes

• Primary index: built on the ordering (sorting) key field of a sequentially ordered file — usually one index
entry per block (sparse), since the file itself is already sorted by this field.
• Clustering index: built on a non-key ordering field of a sequentially ordered file (a field that is not unique,
but the file is still physically sorted on it) — one index entry per distinct value of that field.
• Secondary index: built on a non-ordering field (a field the file is not physically sorted by) — must be dense
(one index entry for every single record), since the underlying data is not sorted by this field.
• Dense index: contains an index entry for every search-key value (and hence every record) in the data file.
• Sparse index: contains an index entry only for some of the search-key values (typically one per disk block),
relying on the file being physically sorted so the rest of the block can be scanned from the nearest earlier
index entry.
• Multilevel index: an index on an index — when even the first-level index becomes too large to search
efficiently (or to fit in memory), a second-level sparse index is built over the first level, and so on, reducing
the number of disk accesses needed for a lookup.

6.2 B-Tree
A B-tree of order m is a balanced, multi-way search tree where:
• Every node has at most m children and at most (m − 1) keys.
• Every internal node (except the root) has at least ⌈m/2⌉ children.
• The root has at least 2 children (unless it is a leaf).
 • All leaf nodes appear at the same depth (the tree is perfectly balanced).
• Keys within each node are stored in sorted order, and each key in an internal node is accompanied by a
data/record pointer stored right there in that node.
Because data pointers are attached to keys at every level (not just the leaves), a search can sometimes terminate
early at an internal node — but this also means internal nodes hold fewer keys for the same block size (since space is
shared between keys and data pointers), making the tree comparatively "bushier"/taller than the equivalent B+ tree.

6.3 B+ Tree
A B+ tree is the variant of the B-tree that is almost universally used in real database indexes. The key structural
difference:
• Internal (non-leaf) nodes: store only key values used purely for navigation/routing — no data/record
pointers. This lets each internal node hold more keys for the same block size, keeping the tree shorter and
reducing the number of disk I/Os per search.
• Leaf nodes: store all the actual key–record-pointer pairs. Every key value in the tree appears at the leaf level
(some keys are duplicated in internal nodes purely as routing signposts).
• Linked leaves: leaf nodes are chained together in sorted order via pointers, so a range query (e.g. "all keys
between 30 and 90") only needs one initial descent to find the starting leaf, followed by simply following the
leaf chain — a major advantage over the plain B-tree for range queries.

Worked Example — Computing the Order of a B+ Tree

Suppose a disk block is 1 KB (1024 bytes), each search-key value takes 9 bytes, and each block pointer takes 6 bytes.
(These are illustrative sizes; an actual GATE question will give you specific numbers to plug into the same formulas.)
Internal node order p (max children):
p * (pointer size) + (p - 1) * (key size) <= block size
6p + 9(p - 1) <= 1024
15p - 9 <= 1024 => 15p <= 1033 => p <= 68.86
=> p = 68 (max 68 children, i.e. max 67 keys per internal node)
=> minimum children per internal node (except root) = ceil(68/2) = 34

Leaf node order p_leaf (assume record pointer size = 7 bytes, plus 1 'next leaf'
block pointer of 6 bytes):
p_leaf * (key size + record pointer size) + block pointer <= block size
p_leaf * (9 + 7) + 6 <= 1024 => 16 p_leaf <= 1018 => p_leaf <= 63.6
=> p_leaf = 63 (max 63 key-record pairs per leaf)

6.4 B-Tree vs B+ Tree — Comparison

Aspect B-Tree B+ Tree
Data pointers Stored at every node (internal + leaf) Stored only at leaf nodes
Leaf-node linking Leaves are not linked to each other All leaves are linked in a sorted chain
Can terminate at an internal node — Always descends all the way to a leaf —
Search for a single key
sometimes faster consistent cost
Range queries Inefficient — no leaf chain to traverse Very efficient — just follow the leaf chain
Keys per node (same block More (internal nodes hold only keys) —
Fewer (space shared with data pointers)
size) shorter, wider tree
The standard index structure used by virtually
Common use Rarely used in practice for DBMS indexing
all commercial DBMSs
7. Transactions and Concurrency Control
7.1 Transactions and the ACID Properties
A transaction is a single logical unit of work — a sequence of one or more database operations (reads and writes)
that must be executed as an indivisible whole. Every transaction, to be reliable, must satisfy the ACID properties:
• Atomicity: a transaction's operations either all complete successfully, or none of them take effect at all ("all
or nothing") — a transaction cannot be left partially executed.
• Consistency: a transaction takes the database from one consistent state to another, preserving all declared
integrity constraints.
• Isolation: the intermediate effects of a transaction must not be visible to other concurrently executing
transactions, even though multiple transactions may physically interleave their operations for efficiency — it
must appear as if transactions ran one at a time.
• Durability: once a transaction commits, its effects must survive permanently, even in the event of a
subsequent system crash.

7.2 Transaction States

A transaction moves through the following states during its lifetime:
8. Active — the initial state; the transaction is executing its operations.
9. Partially Committed — after the final statement has executed, but before all changes are guaranteed to be
permanently saved to disk.
10. Committed — after successful completion, once all changes have been made durable.
11. Failed — reached if the normal execution cannot proceed, e.g. due to a hardware or logical error.
12. Aborted — after the transaction has been rolled back and the database restored to its state prior to the
transaction's start; from here the transaction may either be restarted or killed entirely.

7.3 Schedules and Serializability

When multiple transactions execute concurrently, their individual read/write operations may interleave; the
resulting sequence of operations (from all transactions combined) is called a schedule.
• Serial schedule: transactions are executed one completely after another with no interleaving at all — always
safe/consistent, but offers no concurrency (poor performance).
• Concurrent (non-serial) schedule: operations from different transactions are interleaved to improve
throughput/response time — but this interleaving can introduce inconsistency if not controlled carefully.
• Serializable schedule: a (possibly interleaved) schedule that produces the same final effect on the database
as some serial schedule of the same transactions — this is the correctness criterion that concurrency control
protocols aim to guarantee.

Conflict Serializability
Two operations from different transactions conflict if they operate on the same data item and at least one of them is
a write. There are three conflict types: read-write, write-read, and write-write. A schedule is conflict serializable if it
can be transformed into a serial schedule by swapping only non-conflicting (adjacent) operations.
Testing method — the Precedence Graph: draw one node per transaction; draw an edge Ti → Tj whenever an
operation of Ti conflicts with, and precedes, an operation of Tj on the same data item. The schedule is conflict
serializable if and only if this precedence graph is acyclic (has no cycles); if acyclic, any topological ordering of the
graph gives an equivalent serial order.

Worked Example — Precedence Graph and Cycle Detection

Schedule S: R1(A), R2(A), W1(A), W2(A), R1(B), R2(B), W1(B), W2(B) — where Ri/Wi denotes a read/write by
transaction Ti.
Conflicting pairs on A:
 R2(A) occurs before W1(A) -> conflict (read-write) -> edge T2 -> T1
W1(A) occurs before W2(A) -> conflict (write-write) -> edge T1 -> T2

We already have both T1 -> T2 AND T2 -> T1 => a CYCLE exists

=> Schedule S is NOT conflict serializable.

View Serializability
A broader (less strict) correctness criterion than conflict serializability: two schedules are view equivalent if (a) each
transaction reads the same initial values, (b) each transaction reads the values written by the same transaction in
both schedules, and (c) each data item has the same final writer in both schedules. Every conflict serializable
schedule is also view serializable, but not vice versa — some view serializable schedules exist that are not conflict
serializable (typically involving "blind writes" — writes not preceded by a read of the same item).

Recoverability of Schedules
• Recoverable schedule: a transaction commits only after every transaction from which it read has already
committed — this ensures that a committed transaction's results never depend on an aborted transaction's
changes.
• Cascadeless schedule: stricter still — a transaction may read a value only after the transaction that wrote it
has already committed. This avoids cascading rollback, where the abort of one transaction would force the
rollback of several others that read its uncommitted values.
• Strict schedule: the strictest — a transaction can neither read nor overwrite a data item until the transaction
that last wrote it has committed or aborted. Strict schedules are both cascadeless and recoverable, and are
the easiest to recover from after a crash.

7.4 Concurrency Control Protocols

A concurrency control protocol is the set of rules a DBMS enforces at run time (as transactions execute) to guarantee
that every resulting schedule is serializable, without needing to check the entire schedule after the fact.

Lock-Based Protocols
• Shared lock (S): obtained before reading a data item; multiple transactions may hold a shared lock on the
same item simultaneously.
• Exclusive lock (X): obtained before writing a data item; only one transaction may hold an exclusive lock on a
given item, and no other transaction may simultaneously hold any lock (shared or exclusive) on it.
S (requested) X (requested)
S (held) Compatible (Yes) Not compatible (No)
X (held) Not compatible (No) Not compatible (No)

• Two-Phase Locking (2PL): every transaction is divided into a growing phase (locks may only be acquired,
never released) followed by a shrinking phase (locks may only be released, never acquired again). The point
at which the transaction holds its maximum number of locks — the boundary between the two phases — is
called the lock point. Basic 2PL guarantees conflict serializability, but does not by itself prevent cascading
rollback or deadlock.
• Strict 2PL: all exclusive locks held by a transaction are released only after it commits or aborts (shared locks
may still be released earlier) — this guarantees cascadeless (and hence recoverable) schedules; it is the
protocol most commonly implemented in practice.
• Rigorous 2PL: all locks — both shared and exclusive — are held until the transaction commits or aborts,
guaranteeing strict schedules.

Deadlock Handling
A deadlock is a state where two or more transactions are each waiting for a lock held by another transaction in the
cycle, so none of them can proceed.
 • Deadlock prevention: avoids deadlock before it can occur, typically by ordering transactions using
timestamps: Wait-Die (an older transaction is allowed to wait for a younger one; a younger transaction
requesting a lock held by an older one is aborted/"dies") and Wound-Wait (an older transaction "wounds" —
forcibly aborts — a younger one holding a needed lock; a younger transaction simply waits for an older one).
• Deadlock detection: allows deadlocks to form, then periodically checks for them by building a wait-for graph
(an edge Ti → Tj if Ti is waiting for a lock held by Tj); a cycle in this graph indicates a deadlock, which is
resolved by aborting one or more transactions in the cycle (the "victim").
• Deadlock avoidance vs recovery: prevention/avoidance stops deadlocks from ever forming (at the cost of
potentially unnecessary aborts), while detection-based approaches let deadlocks occur and then recover
from them.

Timestamp-Ordering Protocol
Each transaction Ti is assigned a unique, monotonically increasing timestamp TS(Ti) at the moment it starts. Every
data item Q maintains two timestamps: W-timestamp(Q), the largest timestamp of any transaction that successfully
wrote Q, and R-timestamp(Q), the largest timestamp of any transaction that successfully read Q.
• If a transaction tries to read Q but TS(Ti) < W-timestamp(Q) (i.e., a "future" transaction already overwrote
Q), the read is rejected and Ti is rolled back.
• If a transaction tries to write Q but TS(Ti) < R-timestamp(Q) or TS(Ti) < W-timestamp(Q) (a later transaction
already read or wrote Q), the write is rejected and Ti is rolled back.
• Thomas' Write Rule: an optimization to the basic protocol — if TS(Ti) < W-timestamp(Q), the write can
simply be ignored (rather than rolling back Ti) since a later transaction has already overwritten Q anyway;
this allows some schedules to be accepted that are not conflict serializable, but are still correct.
Timestamp ordering guarantees a schedule equivalent to the serial order defined by the transactions' timestamps,
and is deadlock-free by construction (transactions are never made to wait for one another — they are simply rolled
back and restarted with a new, later timestamp if a conflict is detected).

Validation (Optimistic) Concurrency Control

Optimistic protocols assume conflicts between transactions are rare, so they avoid the overhead of locking
altogether and instead check for conflicts only at the end. Each transaction proceeds through three phases:
13. Read phase — the transaction reads data items (from the database or its own local copies) and performs all
computations, storing tentative updates in a private workspace rather than the database itself.
14. Validation phase — before committing, the transaction is checked against other concurrently validated
transactions to ensure no conflicting/serializability-breaking interleaving has occurred.
15. Write phase — if validation succeeds, the tentative updates are made permanent in the actual database; if
validation fails, the transaction is rolled back and restarted.

Multiversion Concurrency Control (MVCC)

Rather than overwriting a data item on every write, MVCC keeps multiple versions of each data item, each tagged
with the timestamp (or transaction id) that created it. A read request is satisfied by the most recent version that
existed at, or before, the reading transaction's own timestamp — this allows read operations to proceed without
ever waiting for (or being blocked by) write operations, since writers simply create a new version rather than
overwriting the one a reader might need.

Exam Note: System Documentation

📌 High-Yield Recurring Short Answer — System Documentation
This topic was directly examined in the 2023–24 paper, Group B, Q4 (5 marks): "What do you mean by System
Documentation? Classify the different types of System Documentation." It has not repeated in the two papers
since, which makes it a reasonable candidate to resurface. The ready-made 5-mark answer below covers the
definition plus a clean classification.
Definition:
System documentation is the complete collection of written records — diagrams, specifications, manuals, and
reports — that describe how a system was designed, built, and is intended to be used and maintained. It is
prepared at every stage of the system development life cycle and serves as a permanent reference for
developers, users, and maintenance staff long after the original design team has moved on.
Classification of System Documentation:
(A) By location relative to the program:
• Internal documentation: embedded directly inside the program/system itself — comments in source
code, meaningful variable and function names, consistent indentation, and header blocks that describe
each module's purpose. It is read by anyone examining the code directly.
• External documentation: maintained as separate documents outside the program — includes system
manuals, flowcharts, DFDs, ER diagrams, and formal requirement/design specifications.
(B) By audience/purpose:
• User documentation: written for the end users of the system — user manuals, quick-start guides,
tutorials, and FAQs. It explains how to operate the system, not how it works internally.
• Technical documentation: written for developers, testers, and technical maintenance staff — system
design documents, database schemas, API references, and inline source-code documentation. It explains
how the system is built and how it works internally.
• Process documentation: records the process of developing the system itself, rather than the system's
features — project plans, feasibility study reports, test plans, meeting minutes, schedules, and
standards followed during development. It is primarily useful for project management, audits, and
future development teams who need to understand why certain design decisions were made.