sal

Distributed Systems
& Distributed Databases

n
The Complete Premium Semester Preparation E-Book

Ka
A Single, Comprehensive Resource Covering:
Full Syllabus Notes · Solved PYQs · Question Bank Solutions
Revision Sheets · Memory Tricks · Architecture Diagrams
Interview Insights · Exam Strategies · MCQs & Long Answers
l
mo

Made by
Anmol Kansal

University: Maulana Abul Kalam Azad University of Technology, WB

An

Programme: [Link], AI & Machine Learning

Subject Code: PEC-IT601B / PECAIML-601C
Semester: 6th
Session: 2024–2025

“This is not just a set of notes — this is a journey from absolute beginner
to deep conceptual mastery in Distributed Systems.”
How to Use This E-Book

sal
Quick Revision
This book is built to be your single, complete resource for the Distributed Systems
/ Distributed Databases paper. You should not need any other notes, photocopies,
YouTube playlists, or PDFs. Everything required for the semester examination, viva,
assignment work, and even interview preparation lives in these pages.

The structure

n
This volume contains Part I — Complete Notes:

Ka
1. Part I — Complete Notes. Every topic of the official MAKAUT syllabus, explained from
the very basics, with diagrams, tables, and worked examples. Read this first, unit by unit.
The companion volumes — Solved PYQs, Question Bank Solutions, and Revision Sheets — are
separate downloads on your device.

The colour-coded boxes

Throughout the book you will see coloured boxes. Each colour means a specific kind of help:

Blue (Definition): formal, university-style definitions you can write directly in answer
scripts.
l
•
mo

Purple (Intuition): the same idea in plain English, with stories or analogies.
•
Green (Why Needed): what problem this concept solves.
•
Brown (Exam Tip): how to score full marks on this topic.
•
Orange (Common Mistake): traps where students lose marks.
•
Pink (Memory Trick): mnemonics and visual hooks.
•
An

Teal (Real-World): where Google, Amazon, or your bank uses this.

•
Gold (Interview Insight): what an interviewer will follow-up with.
•

The 7-Day Exam Plan

You have one week before the exam. Here is how to use this volume, hour by hour, to walk
into the exam hall fully prepared. Each day assumes 4–5 focused hours (you can compress or
expand, but do not skip days).

Made by Anmol Kansal • Page 2

 HOW TO USE THIS E-BOOK

Day Focus What to do

1 Unit 1 + Unit 6 Read Chapter 1 cover-to-cover. Memorise
(lightweight units) the 3 transparencies, P2P & MDBS diagrams,
and “CC SIDE Drift” mnemonic. Then read
Chapter 6 (Advanced Topics). End the day

sal
by writing the end-of-chapter Quick Revision
of each unit in your own hand.
2 Unit 2 Read Chapter 2 fully. The two heavyweight
(fragmentation & design) algorithms are PHorizontal and Bond Energy
— trace each with a fresh example on paper.
Memorise the 8 factors affecting allocation.
Practice drawing the 4-layer query processing
diagram twice from memory.

n
3 Unit 3 — Part A Read Sections 3.1–3.5 (factors, cost model,
(Query optimization) static & dynamic QO, semi-join, idempo-
tency). Practice the semi-join numerical

4 Unit 3 — Part B
Ka
on paper.
mnemonic.
Memorise the CD-SSSN-FT

Read the rest of Chapter 3 (Sections 3.6–3.10).

(Transactions & concur- Master the BTO algorithm: write the 2 Read
rency) rules + 3 Write rules from memory. Memorise
the wait-die / wound-wait table. Draw the
2PL lock-vs- time diagram twice.
5 Unit 4 Read Chapter 4 fully. Master 2PC: coordina-
(Commit & recovery) tor algorithm, participant algorithm, message
diagram, all 4 failure scenarios, all 5 disad-
vantages (BC-Hammer Limited). Draw 2PC
l
and 3PC state diagrams from memory. Un-
derstand the partition limitation of 3PC and
mo

the quorum cure.

6 Unit 5 + final revision Read Chapter 5. Memorise the three architec-
(Parallel DBs + sweep) ture diagrams (SM, SD, SN) and the parallel-
vs-distributed table. Then sweep the Quick
Revision boxes of all 6 chapters. Re-write any
mnemonic you have forgotten.
7 Mock + light review In the morning: attempt one full PYQ (most
recent year) under 3-hour exam conditions,
closed book. In the afternoon: review your
An

answers, fix mistakes. In the evening: read

only the Exam Tip and Common Mistake
boxes throughout the book. Sleep early.

If you have only 3 days

1. Day 1: Units 3 + 4 (these carry ∼60% of every paper).

2. Day 2: Units 1 + 2 (the cheap, high-yield marks).

3. Day 3: Units 5 + 6 + one mock PYQ.

Made by Anmol Kansal • Page 3

Distributed Systems / DDBMS

If you have only 1 day (don’t, but if you must)

Read only: the Quick Revision boxes at the end of every chapter, the Memory Trick boxes,
and every Exam Tip box. Skip the body text. This is the absolute minimum to walk in and
write a coherent paper.

sal
Good luck. You are going to do brilliantly.
— Anmol Kansal

n
l Ka
mo
An

Made by Anmol Kansal • Page 4

Contents

sal
How to Use This E-Book 2

Official Syllabus at a Glance 11

I Complete Notes — Full Syllabus 12

1 Introduction and Distributed DBMS Architecture 13

n
1.1 Distributed Data Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.1.1 From centralised to distributed: a brief evolution . . . . . . . . . . . . . . 14
1.1.2 Why we cannot just keep using one big computer . . . . . . . . . . . . . . 15

Ka
1.2 What is a Distributed Database System (DDBS)? . . . . . . . . . . . .
1.2.1 Three defining properties . . . . . . . . . . . . . . . . . . . . .
1.2.2 DDBS vs. Distributed DBMS (DDBMS): clarification . . . . .
1.2.3 A first picture of a DDBS . . . . . . . . . . . . . . . . . . . . .
1.3 Advantages of a DDBMS . . . . . . . . . . . . . . . . . . . . . . . . .
1.4 Disadvantages of a DDBMS . . . . . . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
15
15
16
16
16
17
1.5 Problem Areas (Functions a DDBMS Must Provide) . . . . . . . . . . . . . . . . 18
1.6 Refresher: Database Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.6.1 The relational model in 90 seconds . . . . . . . . . . . . . . . . . . . . . . 19
1.6.2 ACID — the four pillars of a transaction . . . . . . . . . . . . . . . . . . . 19
1.6.3 Levels of data abstraction (ANSI/SPARC) . . . . . . . . . . . . . . . . . 19
l
1.7 Refresher: Computer Network Concepts . . . . . . . . . . . . . . . . . . . . . . . 20
1.7.1 OSI & TCP/IP layering . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
mo

1.7.2 LAN, MAN, WAN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

1.7.3 Latency vs. bandwidth — the most important distinction . . . . . . . . . 20
1.8 Transparencies in a Distributed DBMS . . . . . . . . . . . . . . . . . . . . . . . . 21
1.8.1 The nine transparencies, formally . . . . . . . . . . . . . . . . . . . . . . . 21
1.8.2 Three nested levels (the diagram MAKAUT loves) . . . . . . . . . . . . . 21
1.8.3 Worked example: a single query at four transparency levels . . . . . . . . 22
1.8.4 Comparison table: transparency, performance, and effort . . . . . . . . . 23
1.9 Distributed DBMS Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
1.9.1 Understanding the Reference Architecture from First Principles . . . . . . 23
An

1.9.2 The five-schema reference architecture . . . . . . . . . . . . . . . . . . . . 25

1.9.3 Three implementation styles . . . . . . . . . . . . . . . . . . . . . . . . . . 27
1.10 Global Directory Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
1.10.1 Four directory storage strategies . . . . . . . . . . . . . . . . . . . . . . . 29
1.10.2 Comparison table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
1.11 End-of-Chapter Summary — Unit 1 . . . . . . . . . . . . . . . . . . . . . . . . . 29
1.11.1 Quick revision sheet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
1.11.2 Most important exam points (from PYQ analysis) . . . . . . . . . . . . . 30
1.11.3 High-probability questions for the next exam . . . . . . . . . . . . . . . . 30
1.11.4 Practice questions (with quick hints) . . . . . . . . . . . . . . . . . . . . . 30

Made by Anmol Kansal • Page 5

Distributed Systems / DDBMS

2 Distributed Database Design, Semantic Data Control & Query Processing

Issues 32
2.1 Alternative Design Strategies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.1.1 Top-down design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.1.2 Bottom-up design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

sal
2.1.3 When to prefer each . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.2 Distributed Design Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.3 Fragmentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.3.1 Correctness rules for any fragmentation . . . . . . . . . . . . . . . . . . . 35
2.3.2 Horizontal fragmentation (HF) . . . . . . . . . . . . . . . . . . . . . . . . 36
2.3.3 Derived horizontal fragmentation . . . . . . . . . . . . . . . . . . . . . . . 38
2.3.4 Vertical fragmentation (VF) . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.3.5 Mixed fragmentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

n
2.4 Data Allocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.4.1 Factors affecting allocation (exam question) . . . . . . . . . . . . . . . . . 39
2.4.2 Non-replicated allocation: best-fit method . . . . . . . . . . . . . . . . . . 40
2.4.3 Replicated vs. non-replicated allocation . . . . . . . . . . . . . . . . . . . 41

Ka
2.5 Semantic Data Control — View Management . . . . . . . . . . . . .
2.5.1 Why views matter even more in a DDBMS . . . . . . . . . .
2.5.2 View resolution: query modification . . . . . . . . . . . . . .
2.5.3 Materialised views & incremental refresh . . . . . . . . . . . .
2.6 Data Security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.6.1 Three dimensions of security . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
41
41
41
42
42
42
2.6.2 Discretionary vs. mandatory access control . . . . . . . . . . . . . . . . . 42
2.6.3 Distributed-DBMS-specific concerns . . . . . . . . . . . . . . . . . . . . . 42
2.7 Semantic Integrity Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.7.1 Types of integrity constraints . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.7.2 Distributed SIC: the hard part . . . . . . . . . . . . . . . . . . . . . . . . 43
l
2.8 Query Processing — Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.9 Characterization of Query Processors . . . . . . . . . . . . . . . . . . . . . . . . . 44
mo

2.10 Layers of Query Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

2.10.1 Layer 1 — Query Decomposition . . . . . . . . . . . . . . . . . . . . . . . 44
2.10.2 Layer 2 — Data Localization . . . . . . . . . . . . . . . . . . . . . . . . . 45
2.10.3 Layers 3 & 4 — Optimization . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.11 Query Decomposition — Worked Example . . . . . . . . . . . . . . . . . . . . . . 46
2.12 Localization of Distributed Data — Worked Example . . . . . . . . . . . . . . . 46
2.13 End-of-Chapter Summary — Unit 2 . . . . . . . . . . . . . . . . . . . . . . . . . 47
2.13.1 Quick revision sheet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
2.13.2 Most important exam points (from PYQ analysis) . . . . . . . . . . . . . 47
2.13.3 High-probability questions for the next exam . . . . . . . . . . . . . . . . 47
An

2.13.4 Practice questions (with quick hints) . . . . . . . . . . . . . . . . . . . . . 48

3 Distributed Query Optimization, Transaction Management & Concurrency

Control 49
3.1 Distributed Query Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.1.1 Factors governing query optimization . . . . . . . . . . . . . . . . . . . . 51
3.1.2 The cost model in detail . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.1.3 Centralized query optimization (background) . . . . . . . . . . . . . . . . 52
3.1.4 Static vs. dynamic query optimization . . . . . . . . . . . . . . . . . . . . 52
3.1.5 Search space & search strategy . . . . . . . . . . . . . . . . . . . . . . . . 54
3.1.6 Linear vs. bushy join trees . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

Made by Anmol Kansal • Page 6

 CONTENTS

3.1.7 Ordering of fragment queries . . . . . . . . . . . . . . . . . . . . . . . . . 55

3.1.8 Distributed query optimization algorithms . . . . . . . . . . . . . . . . . . 55
3.2 Semi-Join Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
3.3 Idempotency Rules for Query Simplification . . . . . . . . . . . . . . . . . . . . . 56
3.3.1 The six classical simplification rules . . . . . . . . . . . . . . . . . . . . . 56

sal
3.3.2 Worked PYQ-2023 simplification . . . . . . . . . . . . . . . . . . . . . . . 57
3.4 Transaction Management . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
3.4.1 What is a transaction? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
3.4.2 Goals of transaction management . . . . . . . . . . . . . . . . . . . . . . . 58
3.4.3 ACID — the four mandatory properties . . . . . . . . . . . . . . . . . . . 58
3.4.4 Characteristics of transactions . . . . . . . . . . . . . . . . . . . . . . . . 58
3.4.5 Taxonomy of transaction models . . . . . . . . . . . . . . . . . . . . . . . 59
3.4.6 Dirty, fuzzy and phantom reads . . . . . . . . . . . . . . . . . . . . . . . . 60

n
3.5 Serializability — The Gold Standard of Correctness . . . . . . . . . . . . . . . . 61
3.6 Concurrency Control in Centralized Databases (Review) . . . . . . . . . . . . . . 61
3.6.1 Lock-based concurrency control . . . . . . . . . . . . . . . . . . . . . . . . 61
3.7 Concurrency Control in Distributed Databases . . . . . . . . . . . . . . . . . . . 62

3.8
Ka
3.7.1 Distributed two-phase locking variants . . . . . . .
3.7.2 Timestamp ordering (TO) . . . . . . . . . . . . . .
3.7.3 Optimistic concurrency control (brief) . . . . . . .
Deadlock Management . . . . . . . . . . . . . . . . . . . .
3.8.1 What is a deadlock? . . . . . . . . . . . . . . . . .
3.8.2 Three strategies . . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
63
63
64
64
64
64
3.8.3 Deadlock detection in distributed DBs . . . . . . . . . . . . . . . . . . . . 65
3.8.4 Deadlock prevention — wait-die and wound-wait . . . . . . . . . . . . . . 65
3.8.5 Granularity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
3.9 End-of-Chapter Summary — Unit 3 . . . . . . . . . . . . . . . . . . . . . . . . . 66
3.9.1 Quick revision sheet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
l
3.9.2 Most important exam points (from PYQ analysis) . . . . . . . . . . . . . 67
3.9.3 High-probability questions for the next exam . . . . . . . . . . . . . . . . 67
mo

3.9.4 Practice questions (with quick hints) . . . . . . . . . . . . . . . . . . . . . 68

4 Reliability, Failures, Commit & Recovery Protocols 69

4.1 Reliability Issues in Distributed Databases . . . . . . . . . . . . . . . . . . . . . . 70
4.1.1 Definitions: reliability vs. availability . . . . . . . . . . . . . . . . . . . . . 70
4.1.2 “High reliability does not ensure correctness” . . . . . . . . . . . . . . . . 70
4.1.3 Who is responsible for correct execution? . . . . . . . . . . . . . . . . . . 71
4.2 Types of Failures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
4.2.1 1. Transaction failure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
4.2.2 2. Site (system) failure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
An

4.2.3 3. Media (disk) failure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

4.2.4 4. Communication failure . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
4.2.5 5. Network partition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
4.2.6 The CAP theorem (preview) . . . . . . . . . . . . . . . . . . . . . . . . . 72
4.3 Reliability Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
4.3.1 1. Redundancy (hardware) . . . . . . . . . . . . . . . . . . . . . . . . . . 72
4.3.2 2. Replication (data) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
4.3.3 3. Logging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
4.3.4 4. Checkpointing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
4.3.5 5. Process pairs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
4.4 Why a Commit Protocol Is Necessary . . . . . . . . . . . . . . . . . . . . . . . . 74

Made by Anmol Kansal • Page 7

Distributed Systems / DDBMS

4.5 Two-Phase Commit (2PC) Protocol . . . . . . . . . . . . . . . . . . . . . . . . . 74

4.5.1 Roles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
4.5.2 The two phases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
4.5.3 Coordinator algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
4.5.4 Participant algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

sal
4.5.5 2PC message diagram and communication structure . . . . . . . . . . . . 75
4.5.6 State transition diagram of 2PC . . . . . . . . . . . . . . . . . . . . . . . 76
4.5.7 Failure scenarios in 2PC . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
4.5.8 Disadvantages of 2PC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
4.5.9 Unilateral abort capability . . . . . . . . . . . . . . . . . . . . . . . . . . 77
4.6 Three-Phase Commit (3PC) Protocol . . . . . . . . . . . . . . . . . . . . . . . . . 78
4.6.1 The three phases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
4.6.2 Why the extra phase makes it non-blocking . . . . . . . . . . . . . . . . . 78

n
4.6.3 State-transition diagram of 3PC . . . . . . . . . . . . . . . . . . . . . . . 78
4.6.4 Termination protocol after coordinator failure . . . . . . . . . . . . . . . . 78
4.6.5 Does 3PC solve everything? — Network partition . . . . . . . . . . . . . 79
4.7 Comparison: 2PC vs 3PC vs Quorum . . . . . . . . . . . . . . . . . . . . . . . . 79

Ka
4.8 Recovery Protocols and Algorithms . . . . . . . . . . . . . . . . . . . . . . .
4.8.1 UNDO / REDO (immediate update, with logging) . . . . . . . . . .
4.8.2 ARIES (Algorithm for Recovery and Isolation Exploiting Semantics)
4.9 End-of-Chapter Summary — Unit 4 . . . . . . . . . . . . . . . . . . . . . .
4.9.1 Quick revision sheet . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.9.2 Most important exam points (from PYQ analysis) . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
80
80
80
81
81
81
4.9.3 High-probability questions for the next exam . . . . . . . . . . . . . . . . 82
4.9.4 Practice questions (with quick hints) . . . . . . . . . . . . . . . . . . . . . 82

5 Parallel Database Systems 83

5.1 What Is a Parallel Database? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
5.1.1 Why parallel databases exist . . . . . . . . . . . . . . . . . . . . . . . . . 84
l
5.1.2 Two performance metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
mo

5.1.3 Goals of using parallel architecture . . . . . . . . . . . . . . . . . . . . . . 85

5.2 Parallel Database vs. Distributed Database . . . . . . . . . . . . . . . . . . . . . 85
5.3 Parallel Architectures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
5.3.1 Shared-Memory (SM) architecture . . . . . . . . . . . . . . . . . . . . . . 86
5.3.2 Shared-Disk (SD) architecture . . . . . . . . . . . . . . . . . . . . . . . . 86
5.3.3 Shared-Nothing (SN) architecture . . . . . . . . . . . . . . . . . . . . . . 87
5.3.4 Hybrid architectures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
5.3.5 Side-by-side comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
5.4 Forms of Parallelism in Query Processing . . . . . . . . . . . . . . . . . . . . . . 88
5.4.1 Inter-query parallelism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
An

5.4.2 Intra-query parallelism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

5.5 Partitioning Strategies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
5.5.1 Round-robin partitioning . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
5.5.2 Hash partitioning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
5.5.3 Range partitioning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
5.5.4 Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
5.6 Parallel Implementations of Relational Operators . . . . . . . . . . . . . . . . . . 90
5.6.1 Parallel scan with selection . . . . . . . . . . . . . . . . . . . . . . . . . . 90
5.6.2 Parallel sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
5.6.3 Parallel join . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
5.6.4 Parallel aggregation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

Made by Anmol Kansal • Page 8

 CONTENTS

5.7 Load Balancing and Data Skew . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

5.8 End-of-Chapter Summary — Unit 5 . . . . . . . . . . . . . . . . . . . . . . . . . 91
5.8.1 Quick revision sheet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
5.8.2 Most important exam points (from PYQ analysis) . . . . . . . . . . . . . 92
5.8.3 High-probability questions for the next exam . . . . . . . . . . . . . . . . 92

sal
5.8.4 Practice questions (with quick hints) . . . . . . . . . . . . . . . . . . . . . 92

6 Advanced Topics: Mobile Databases, Distributed Object Management, Multi-

databases 93
6.1 Mobile Databases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
6.1.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
6.1.2 Why mobile databases exist . . . . . . . . . . . . . . . . . . . . . . . . . . 94
6.1.3 Architecture of a mobile database system . . . . . . . . . . . . . . . . . . 95
6.1.4 Characteristics that make mobile DBs special . . . . . . . . . . . . . . . . 95

n
6.1.5 Mobile transactions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
6.1.6 Purpose of mobile database replication . . . . . . . . . . . . . . . . . . . . 96
6.1.7 Data dissemination via broadcast . . . . . . . . . . . . . . . . . . . . . . . 96
6.2 Distributed Object Management . . . . . . . . . . . . . . . . . . . . . . . . . . . 97

Ka
6.2.1 Why distributed objects matter . . . . . . . . . . . . . . . . . . . .
6.2.2 Reference architecture . . . . . . . . . . . . . . . . . . . . . . . . .
6.2.3 Classic and modern technologies . . . . . . . . . . . . . . . . . . .
6.2.4 Distributed object DBMSs . . . . . . . . . . . . . . . . . . . . . .
6.3 Multi-Database Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.3.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
97
97
97
98
98
98
6.3.2 MDBS vs. Homogeneous DDBMS — the key distinction . . . . . . . . . . 98
6.3.3 Five-level schema architecture of an MDBS . . . . . . . . . . . . . . . . . 98
6.3.4 Three dimensions of MDBS autonomy . . . . . . . . . . . . . . . . . . . . 98
6.3.5 Federated vs. unfederated MDBS . . . . . . . . . . . . . . . . . . . . . . . 99
6.3.6 Auxiliary program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
l
6.3.7 Issues in multi-database query processing . . . . . . . . . . . . . . . . . . 100
6.3.8 Protocol for multiple transactions on different databases . . . . . . . . . . 100
mo

6.4 Data Warehousing, OLAP, and WWW Architecture . . . . . . . . . . . . . . . . 100

6.4.1 OLTP vs. OLAP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
6.4.2 Data warehouse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
6.4.3 WWW as a distributed information system . . . . . . . . . . . . . . . . . 101
6.4.4 Three-tier web application architecture . . . . . . . . . . . . . . . . . . . . 101
6.5 End-of-Chapter Summary — Unit 6 . . . . . . . . . . . . . . . . . . . . . . . . . 101
6.5.1 Quick revision sheet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
6.5.2 Most important exam points (from PYQ analysis) . . . . . . . . . . . . . 102
6.5.3 High-probability questions for the next exam . . . . . . . . . . . . . . . . 102
6.5.4 Practice questions (with quick hints) . . . . . . . . . . . . . . . . . . . . . 102
An

Made by Anmol Kansal • Page 9

Distributed Systems / DDBMS

n sal
l Ka
mo
An

Made by Anmol Kansal • Page 10

Official Syllabus at a Glance

sal
Source: MAKAUT, West Bengal — [Link] AI & ML, Distributed Systems (PEC-IT601B /
PECAIML-601C), effective from session 2020–21. Total contact: 3L. Total scheduled hours: 48.

Unit Topics Covered Hrs

1 Introduction: Distributed data processing; What is a 8
DDBS; Advantages and disadvantages of DDBS; Problem areas;
Overview of database and computer network concepts.
Distributed DBMS Architecture: Transparencies in a dis-

n
tributed DBMS; Distributed DBMS architecture; Global direc-
tory issues.
2 Distributed Database Design: Alternative design strategies; 11
Distributed design issues; Fragmentation; Data allocation.

Ka
Semantics Data Control: View management; Data security;
Semantic Integrity Control.
Query Processing Issues: Objectives of query processing;
Characterization of query processors; Layers of query processing;
Query decomposition; Localization of distributed data.
3 Distributed Query Optimization: Factors governing query 11
optimization; Centralized query optimization; Ordering of frag-
ment queries; Distributed query optimization algorithms.
Transaction Management: The transaction concept; Goals
of transaction management; Characteristics of transactions;
l
Taxonomy of transaction models.
mo

Concurrency Control: Concurrency control in centralized

database systems; Concurrency control in DDBSs; Distributed
concurrency control algorithms; Deadlock management.
4 Reliability: Reliability issues in DDBSs; Types of failures; 8
Reliability techniques; Commit protocols; Recovery protocols &
algorithms.
5 Parallel Database Systems: Parallel architectures; parallel 6
query processing and optimization; load-balancing.
6 Advanced Topics: Mobile Databases; Distributed Object 4
An

Management; Multi-databases.

Made by Anmol Kansal • Page 11

 n sal
Part I
Ka
Complete Notes — Full Syllabus
l
mo
An

Made by Anmol Kansal • Page 12

 Introduction and Distributed DBMS
Chapter 1 ·

Architecture

sal
PYQ Analysis — How Much Did Unit 1 Carry in Recent Exams?
Years analysed: 2023, 2024 and 2025 MAKAUT PEC-IT601B papers.
Year Questions from Unit 1 Count Marks
2023 Group A: Q1(III) Define homogeneous 5 13

n
distributed database [1], Q1(IV) Max
FDs of relation degree n [1], Q1(VI)
What is data dictionary? [1]. Group B:
Q4 Components necessary for building

2024
Ka
a distributed database [5], Q6 What
is DDBMS & its features [5].
Group A: Q1(iii) Define heterogeneous
DDBMS [1], Q1(vi) Logical data in-
dependence [1]. Group B: Q4 Peer-
3 7+

to-peer architecture with diagram [5].

Group C: indirect coverage in many
questions.
2025 Group A: Q1(I) Originating node of 6 18
distributed transaction [1], Q1(II) Ad-
vantage of DDBMS [1], Q1(III) View
l
management [1]. Group B: Q3 Dis-
mo

tributed transparency & 3 levels [5],

Q6 MDBS architecture [5]. Group C:
Q11(a) Discuss multi-database archi-
tecture [5].
Average — ≈5 ≈ 13
Verdict. Unit 1 reliably yields 12–18 marks per paper, mostly in Group A (1-mark
definitions) and Group B (5-mark “with diagram” or “define + features” questions).
Mastering Unit 1 is the cheapest way to bank ∼20% of your paper.
Most repeated Unit-1 topics across all three years:
An

1. DDBMS definition, features, advantages & disadvantages (asked in 2023, 2024 and
2025 in some form — almost guaranteed).
2. Architecture diagrams (P2P 2024, MDBS 2025, components 2023).
3. Transparencies & heterogeneous vs. homogeneous DDBMS (1-markers each year).
4. Data dictionary / global directory (1-marker, 2023).
5. Max no. of FDs on n-attribute relation (the famous 22n MCQ — appeared in 2010
and 2023).

Made by Anmol Kansal • Page 13

Distributed Systems / DDBMS

Quick Revision
What Unit 1 will teach you. By the end of this chapter you will be able to:
• Explain in plain English what a distributed database is, why it exists, and what it
costs you.

sal
• Distinguish a distributed database from a parallel database, from a centralized database,
and from “a bunch of databases that happen to be on different machines”.
• Draw and describe the ANSI/SPARC-extended reference architecture for a
DDBMS (global schema, fragmentation schema, allocation schema, local schema).
• Define and contrast the eight / nine famous transparencies: data independence, net-
work, location, replication, fragmentation, naming, failure, transaction, performance.
• Compare the three architectural styles — client–server, peer-to-peer, and multi-

n
database — and pick the right one for a given problem.
• Discuss the global directory problem and the four ways of storing it (centralized,
fully replicated, partitioned, cached).

Ka
• Quickly recall the underlying database concepts (relation, schema, key, FD, ACID)
and network concepts (OSI layers, LAN/WAN, latency vs. bandwidth) on which
everything else in this book stands.

1.1 Distributed Data Processing

Before we touch the word “database”, let us first understand the broader idea that gives birth
to it: distributed data processing (DDP).
l
Definition
Distributed data processing is a computing paradigm in which work — the storage,
mo

retrieval and manipulation of data — is divided among multiple autonomous but inter-
connected computers, each contributing CPU, memory, and storage resources, so that
the user perceives the collective system as a single processing facility.

Intuition
Imagine a single super-clerk in a bank who knows everything about every customer. He
becomes the bottleneck of the entire branch — slow, prone to mistakes when tired, and a
complete catastrophe when he calls in sick. Now replace him with a team of clerks, each
responsible for a chunk of customers; together they answer queries much faster, and one
An

absent clerk does not stop the bank. That is the spirit of distributed processing. The
team must, however, agree on rules: who handles which customer, what if two clerks
update the same record, how to merge results, and so on. Those rules are exactly what a
distributed DBMS provides.

1.1.1 From centralised to distributed: a brief evolution

The journey of database computing can be summarised by four eras:
1. Mainframe era (1960s). A single big computer with dumb terminals. All data lived in one
place. Centralised DBMS. Easy to design, terrible to scale.

Made by Anmol Kansal • Page 14

 CHAPTER 1. INTRODUCTION AND DISTRIBUTED DBMS ARCHITECTURE

2. Client–server era (late 1980s). The mainframe becomes a database server and personal
computers do the presentation. Still one logical database, but two physical tiers.
3. Distributed era (1990s). Multiple database servers on different physical sites are connected
by a network and appear as one logical database. This is the DDBMS.

sal
4. Cloud / NoSQL era (2000s onwards). Massive distribution, eventual consistency,
geo-replication — the commercial realisation of every theoretical concept in this book.

1.1.2 Why we cannot just keep using one big computer

Why It Is Needed

A single centralized database fails on at least five dimensions: scalability (RAM/CPU

caps out), cost (one mainframe costs more than ten servers of equivalent total power),

n
availability (one machine fails, everyone is offline), geography (a Kolkata user accessing
a New York database pays a 200 ms latency tax per query), and organizational auton-
omy (each department wants control over its own data). Distributed data processing
addresses all five.

Ka
1.2 What is a Distributed Database System (DDBS)?

Definition
A Distributed Database System (DDBS) is a collection of multiple, logically in-
terrelated databases stored at different sites of a computer network, together with the
software — the Distributed Database Management System (DDBMS) — that
manages this distributed data and makes the distribution transparent to its users.
l
The phrase to underline is “logically interrelated”. Three independent databases at three
mo

sites with no logical connection are not a DDBS — they are just three databases. What makes
them one distributed database is that the DDBMS treats them as a single logical whole.

1.2.1 Three defining properties

According to Özsu and Valduriez, a system qualifies as a DDBS if and only if it has all three of
the following:
1. Multiple sites. The data is physically spread over ≥ 2 computers (nodes) connected by a
network.
An

2. Logical interrelation. The data items at different sites are connected by some shared
schema or constraints — e.g. a foreign key at site B referring to a tuple at site A.
3. Transparent access. A user submits a query as if they were talking to one normal centralized
database; the DDBMS hides the distribution. (We will study these “transparencies” formally
in Section 1.8.)

Quiz Trap

“A distributed database is a database stored on a fast network.” False. The defining

ingredient is logical relation plus transparent access, not just network presence. The
exam often slips in this kind of half-truth as an MCQ option.

Made by Anmol Kansal • Page 15

Distributed Systems / DDBMS

1.2.2 DDBS vs. Distributed DBMS (DDBMS): clarification

Students often write “DDBS” and “DDBMS” as if they were synonyms; they are not.
• DDBS = the data that is distributed — the actual rows, columns, files.
• DDBMS = the software that manages a DDBS — it translates user queries into network

sal
operations, ensures transactions are atomic across sites, etc.
Together, DDBS + DDBMS = full distributed database system.

1.2.3 A first picture of a DDBS

One Logical Database (the DDBS)

n
Site A

U1

U2
Ka
Computer Network Site B

Site C

Figure 1.1: A minimum-viable DDBS: three sites, one logical database, users that do not know
l
(and do not care) which site stores what.
mo

Reading the diagram. The dashed rectangle is the most important visual element: even
though there are physically three separate database instances (DB1 , DB2 , DB3 ) sitting on three
machines, the DDBMS software wraps them so that to user U1 it behaves as one unified database.
U1 never writes “SELECT . . . FROM DB2 ”; U1 simply writes “SELECT . . . FROM Customer”
and the DDBMS figures out the location.

1.3 Advantages of a DDBMS

An

This is one of the most frequently asked exam questions. The MAKAUT PYQ 2025 directly
asks “What is the advantage of a DDBMS?”. Memorise at least six of the following so you can
never be caught short.

Advantage Explanation (write this in the exam)

1. Reflects organi- Most enterprises are themselves distributed: a bank has
zational structure branches, a multinational has offices. Putting the data at the
same site as the people who own it matches the real-world
hierarchy.

Made by Anmol Kansal • Page 16

 CHAPTER 1. INTRODUCTION AND DISTRIBUTED DBMS ARCHITECTURE

Advantage Explanation (write this in the exam)

2. Improved local Each site can independently administer its own portion of the
autonomy database: backups, security policies, even minor schema tweaks.
Headquarters does not have to grant permissions for every local
change.

sal
3. Improved reli- Because data is replicated and processing is spread, failure of one
ability & availabil- site need not bring the whole system down. A 5-site DDBMS
ity with per-site 99% uptime can offer system uptime well above
99.99% for read-mostly workloads.
4. Improved per- Queries can be processed in parallel at multiple sites; data is
formance stored close to where it is used, reducing network traffic. The
classic example: a customer in Kolkata reads from the Kolkata

n
branch, not from a Mumbai mainframe.
5. Economical Adding capacity means adding a node — you do not need to
(scalability) throw away last year’s mainframe. Hardware cost grows linearly
while central-machine cost grows as a power law.
6.
growth
Modular
Ka
A new department can join the DDBMS without disturbing
existing sites. Just install the DDBMS software, declare the
local schemata, and update the global directory.
7. Easier expan- When the company opens an office in Berlin, you just spin up
sion across geogra- a Berlin site. Users in Berlin enjoy local latency; the global
phies schema remains untouched.
8. Data shar- A DDBMS can hide differences between an Oracle site, a DB2
ing across hetero- site, and a PostgreSQL site (multi-database systems — Unit 6).
geneous systems The user sees one logical database.
9. Improved data Sensitive data can be stored only at sites authorized to hold
l
integrity & secu- it, while still being queryable (with proper access checks) from
rity anywhere.
mo

Memory Trick

Remember the advantages by the mnemonic “REAL PRIDE”: Reliability, Expansion,

Autonomy, Locality of data, Performance, Reflects org structure, Integrity & security,
Data sharing, Economy/scalability. Nine words, all in “REAL PRIDE”.

1.4 Disadvantages of a DDBMS

An

The flip side. Many students forget that exam questions love “Discuss advantages and disadvan-
tages”; the disadvantages half is often skipped — and 50% of marks are lost.
1. Complexity. The DDBMS software is dramatically more complex than a centralized one —
it must handle network failures, distributed deadlocks, two-phase commits, etc.
2. Higher cost (initial). Although hardware is cheaper, the cost of designing, deploying and
maintaining the DDBMS, plus inter-site networking, is non-trivial.
3. Security. A bigger attack surface: every site becomes an entry point. Inter-site messages
must be encrypted. Authentication is harder when users float across sites.

Made by Anmol Kansal • Page 17

Distributed Systems / DDBMS

4. Integrity control overhead. Enforcing a global constraint (e.g. “the total balance across
all branches must equal X”) requires inter-site messages, slowing updates.
5. Lack of universally accepted standards. Two DDBMS products may not interoperate;
SQL is universal, distributed-transaction protocols are not.

sal
6. Database design is harder. You must decide how to fragment data, how to allocate
fragments, whether to replicate — decisions a centralized designer never has to make.
7. Difficult to test and debug. A bug that depends on the timing of three messages across
two sites is much harder to reproduce in a lab.

Memory Trick

“CC SIDE Drift” — Complexity, Cost, Security, Integrity overhead, Design difficulty,
Experts shortage, Debugging difficulty, plus the lack of Recognized standards. Drift

n
= “no fixed standard”. Pictures help: imagine a self-driving boat (CC = cruise control)
drifting because nobody agreed which side is north.

Ka
1.5 Problem Areas (Functions a DDBMS Must Provide)

Every later unit of this syllabus is, in fact, an answer to a specific “problem area” of distributed
databases. Listing them here gives you a map of the rest of the book.

Problem area Issue Solved in Unit

Distributed DB design How to fragment and allocate data Unit 2
across sites?
Distributed directory Where do we keep the metadata that Unit 1 (this chapter)
management says “fragment R2 lives at site B”?
l
Distributed query pro- How to translate a global query into Units 2 & 3
mo

cessing & optimization local queries cheaply?

Distributed concur- How to keep transactions serializable Unit 3
rency control when locks live on different sites?
Distributed deadlock How to detect a cycle of waits across Unit 3
management sites?
Reliability of dis- What if a site or the network crashes Unit 4 (commit and
tributed DBMSs mid-transaction? recovery protocols)
Replication manage- When to replicate, how to keep replicas Units 2, 4
ment consistent?
An

Operating system sup- Inter-process communication, thread- Pre-requisite

port ing, scheduling.
Heterogeneous What if different sites run different Unit 6 (multi-
database support DBMS products? databases)

1.6 Refresher: Database Concepts

You are expected to remember these from your earlier DBMS course; this section is the absolute
minimum you need to make sense of the rest of the book. If a concept is new, look it up before

Made by Anmol Kansal • Page 18

 CHAPTER 1. INTRODUCTION AND DISTRIBUTED DBMS ARCHITECTURE

sal
proceeding.

1.6.1 The relational model in 90 seconds

• Relation: a table. Mathematically, a subset of the Cartesian product of its attribute domains.
• Tuple: a row. Represents one fact (one customer, one order).
• Attribute: a column.
• Schema: the structure — relation names, attributes, types, constraints.

an
• Instance: the contents at a particular time.
• Primary key (PK): a minimal subset of attributes whose values uniquely identify a tuple.
There is exactly one per relation (by choice of the designer).
• Foreign key (FK): an attribute of relation R that takes values from the PK of relation S,
creating a link.
• Functional Dependency (FD) X → Y : whenever two tuples agree on attributes X, they
must agree on attributes Y . Drives normalization.
• Normalization: re-arranging schemas to eliminate redundancy. 1NF, 2NF, 3NF, BCNF,
lK
4NF in order of strictness.

Remember This
Maximum number of FDs on n attributes. A relation on n attributes has 2n
subsets, so the number of ordered pairs (X, Y ) where X, Y ⊆ attributes is 2n × 2n = 22n .
PYQ-2010 Q1(x) asks exactly this; the answer is 22n (counting both trivial and non-trivial
FDs).

1.6.2 ACID — the four pillars of a transaction

• Atomicity — a transaction is all-or-nothing.
o
• Consistency — it moves the DB from one valid state to another.
• Isolation — concurrent transactions appear to run alone.
• Durability — committed changes survive crashes.
Everything in Units 3 and 4 is about preserving ACID when the database is spread across a
nm

flaky network.

1.6.3 Levels of data abstraction (ANSI/SPARC)

A standard 3-level architecture, central to understanding the DDBMS extended architecture in
Section 1.9.
• External (view) level: different views for different users.
• Conceptual (logical) level: the one global schema of the entire enterprise.
• Internal (physical) level: how the data is stored on disk.
Mappings between these levels give logical data independence (external ↔ conceptual) and
physical data independence (conceptual ↔ internal). The PYQ-2024 Q1(vi) asks “What
is logical data independence in DDBMS?” — the answer is exactly: the ability to change the
conceptual schema without altering any external schema.

Made by Anmol Kansal • Page 19

Distributed Systems / DDBMS

1.7 Refresher: Computer Network Concepts

Distributed databases rest on networks; you must be fluent in three things: the OSI/TCP layers,
the WAN/LAN distinction, and the performance metrics latency & bandwidth.

sal
1.7.1 OSI & TCP/IP layering

Layer OSI name Job (relevant to DDBMS)

7 Application Talks to the user; DDBMS clients live
here.
6 Presentation Marshals/unmarshals data formats (big-

n
endian vs. little-endian floats, JSON vs.
Protobuf).
5 Session Maintains a logical conversation be-
tween client and server.
4

3
2
Transport (TCP/UDP)

Network (IP)
Data link
Ka Reliable byte stream (TCP) or fire-and-
forget datagrams (UDP). DDBMS com-
mit messages run on TCP.
Routes packets between machines.
Frames bits over a single physical hop.
1 Physical Wires, fibre, radio.

1.7.2 LAN, MAN, WAN

• LAN (Local Area Network): a single building/campus, latency < 1 ms, bandwidth Gbps.
l
Intra-cluster DDBMSs.
mo

• MAN (Metropolitan): city scale; latency ∼ few ms.

• WAN (Wide Area Network): country/global; latency 50–400 ms, bandwidth highly
variable. Long-haul DDBMS like global e-commerce systems.

1.7.3 Latency vs. bandwidth — the most important distinction

Intuition
Latency is “how long until the first bit arrives”. Bandwidth is “how many bits per second
An

once data is flowing”. Sending a 1 GB file from Kolkata to New York: a 1 Gbps link with
200 ms latency takes 0.2 s (latency) + 8 s (1 GB at 1 Gbps) ≈ 8.2 s. Now issue 100 small
queries one after another instead: each pays the 200 ms latency, so 100 × 0.2 s = 20 s —
more than twice as slow! Distributed databases are usually latency-bound, not
bandwidth-bound. That is why almost every optimization in this book (semi-joins,
query rewriting, hint queries) is about reducing the number of round trips, not about
reducing the bytes per round trip.

1.8 Transparencies in a Distributed DBMS

Made by Anmol Kansal • Page 20
 CHAPTER 1. INTRODUCTION AND DISTRIBUTED DBMS ARCHITECTURE

Definition
Transparency in the DDBMS context means hiding the distribution-related complexity

sal
from the user. A perfectly transparent DDBMS feels exactly like an ordinary, single-
machine DBMS. The more transparency, the simpler the application code; the less
transparency, the more efficient (but harder to write) applications can be.

The number of transparencies actually defined varies by textbook between 4 and 9. We will
cover nine commonly examined transparencies. The PYQ-2025 Q3 explicitly asks about three
levels of transparency, so memorise the layered picture in Figure 1.2.

n
1.8.1 The nine transparencies, formally
1. Data independence: ability to change the schema (logical or physical) without rewriting
applications. Inherited from centralized DBMSs; described above.

Ka
2. Network transparency: the user does not see the underlying network; query syntax is
identical to a single-site SQL. Sub-divided into:

• Location transparency: the user does not need to specify which site stores the data.
• Naming transparency: every object has a globally unique name; no clashes between sites.

3. Replication transparency: the user is unaware that multiple physical copies exist; the
DDBMS keeps them in sync.

4. Fragmentation transparency: the user is unaware that a relation has been split into
fragments stored at different sites; queries are written against the whole relation.
l
5. Local mapping transparency: the user knows that data is fragmented and replicated, but
does not need to know where; the user names a fragment, the DDBMS finds it.
mo

6. Transaction transparency: a single transaction may execute over many sites, but it still
looks atomic and serializable to the user.

7. Failure transparency: site or link failures are masked; the user perceives “slow” rather
than “broken”.

8. Performance transparency: the user need not write location-aware queries to get good
performance; the optimizer does that.

9. Concurrency transparency: multiple users on different sites do not see each other’s
An

intermediate states.

1.8.2 Three nested levels (the diagram MAKAUT loves)

How to read it. The outermost rectangle is the “highest” or “strongest” transparency: at
this level, the user literally writes the query as if the database were one big table. Inside it, the
next ring exposes a little bit of the implementation: the user can mention fragments but still
not their sites. The innermost ring exposes even more: the user must say which fragment is at
which site, but is shielded only from the local file names. Going outward = more comfort for the
user; going inward = more control & usually better performance.

Made by Anmol Kansal • Page 21

Distributed Systems / DDBMS

Level 1: Fragmentation
Level Transparency
2: Location Transparency
Level
user does
3:notLocal
even
Mapping
see fragments
user sees fragments but not their sites
Transparency
user sees fragments & sites
but not local file names

sal
Figure 1.2: Three levels of transparency, nested from highest (user sees nothing of the distribution)
to lowest (user sees almost everything except local file names). This is the picture you should

n
reproduce on the answer sheet for any “three levels of transparency” question.

Exam Tip

Ka
Two-line trick for the exam: write the diagram, then write: “Higher levels of
transparency hide more details but reduce the user’s ability to optimize; lower levels
expose more details but allow the user to give hints to the optimizer.” That single line
earns you the “critical analysis” mark.

1.8.3 Worked example: a single query at four transparency levels

Consider relations EMP(eno, name, sal, dno) and the query “find all employees in dept 10”.
Level 1 – Fragmentation transparency:
SELECT * FROM EMP WHERE dno = 10;
Level 2 – Location transparency:
l
SELECT * FROM EMP_1 WHERE dno = 10
UNION SELECT * FROM EMP_2 WHERE dno = 10;
mo

(user mentions fragments but not where they live)

Level 3 – Local mapping transparency:
SELECT * FROM EMP_1@SiteA UNION ... EMP_2@SiteB;
(user must locate fragments)
Level 4 – No transparency:
user opens local files /var/db/[Link] on site A and site B, parses them manually.
As you go down, query length increases, but in exchange the user can hand-tune the plan.

Real-World Application
An

MongoDB sharding gives location transparency: you say “insert into collection X”
and a config server routes you to the right shard. But MongoDB does not give full
fragmentation transparency: if you query without the shard key, the system broadcasts
to every shard, and the user is held responsible for choosing a shard-key-friendly query.

Interview Insight

Interview follow-up: “Which transparency is the hardest to implement and why?” —

the canonical answer is failure transparency, because masking a real network partition
(a P in the CAP theorem, Unit 4) forces a fundamental trade-off between C (consistency)

Made by Anmol Kansal • Page 22

 CHAPTER 1. INTRODUCTION AND DISTRIBUTED DBMS ARCHITECTURE

and A (availability). You cannot have all three, so something must be visible to the user,
no matter how cleverly you code it.

1.8.4 Comparison table: transparency, performance, and effort

sal
Transparency User effort Optimizer freedom Typical real-world ex-
ample
Fragmentation Lowest Highest Google Spanner
Location Low High PostgreSQL FDW
Local mapping Med Med Older Oracle distributed
DB

n
None High Low Bare Hadoop file access

1.9 Distributed DBMS Architecture

Ka
We now describe the canonical reference architecture for a DDBMS, which extends the
ANSI/SPARC 3-level model with two new levels: the fragmentation schema and the allocation
schema.

1.9.1 Understanding the Reference Architecture from First Principles

Before memorising the layers of the reference architecture, let us ask a more important question:

Why do we even need so many layers in a distributed database?

Intuition
l
Imagine a university with campuses in Kolkata, Delhi and Bangalore. Every campus
stores student records locally because storing everything on one machine would be slow
mo

and risky. But students and teachers still want the entire university to behave like one
single system. Now several difficult questions appear automatically:
• How do users see one unified database?
• How do we split data across campuses?
• How do we decide which campus stores which data?
• How do we hide all this complexity from users?
The reference architecture is simply the systematic answer to these questions.
An

Step 1 — The user only wants a simple global view. Suppose the university has the
following student table:

StudentID Name Campus

101 Rahul Kolkata
102 Priya Delhi
103 Aman Bangalore

A teacher should simply be able to write:

SELECT * FROM STUDENT;

Made by Anmol Kansal • Page 23

Distributed Systems / DDBMS

The teacher should not need to know where Rahul or Priya are stored physically. Therefore we
create the:

Definition
Global Conceptual Schema (GCS) = the complete logical view of the entire dis-

sal
tributed database, as if everything were stored in one place.

So the GCS answers:

“What does the whole database logically look like?”

Step 2 — The system must physically split the data. Storing all rows everywhere would
waste huge amounts of storage. So the system divides the table. For example:

n
Fragment 1 (Kolkata)
StudentID Name Campus
101 Rahul Kolkata

102
Ka
Fragment 2 (Delhi)
StudentID Name Campus
Priya Delhi
Fragment 3 (Bangalore)
StudentID Name Campus
103 Aman Bangalore

This introduces a new question:

“How exactly was the global table divided?”

l
That answer is stored in the:
mo

Definition
Fragmentation Schema = describes how global relations are split into smaller fragments.

Step 3 — The fragments must now be placed somewhere. After fragmentation, another
question appears:

“Which fragment should be stored at which site?”

An

For example:

Fragment Stored At
STUDENT_KOL Kolkata Server
STUDENT_DEL Delhi Server
STUDENT_BAN Bangalore Server

This information belongs to the:

Definition
Allocation Schema = specifies where each fragment is physically stored.

Made by Anmol Kansal • Page 24

 CHAPTER 1. INTRODUCTION AND DISTRIBUTED DBMS ARCHITECTURE

Step 4 — Each site still needs its own local database. Now look at the Kolkata server
alone. It stores only:

StudentID Name Campus

101 Rahul Kolkata

sal
From Kolkata’s perspective, this is just a small local database. Therefore every site has:
• Local Conceptual Schema (logical local view)
• Local Internal Schema (physical storage details)

The core philosophy behind the architecture

The reference architecture separates concerns layer-by-layer:

n
Layer Main Question Answered
Global Conceptual Schema What does the whole database logically look like?
Fragmentation Schema
Allocation Schema
Local Schemas

Remember This
Ka
How was the database divided?
Where is each fragment stored?
How does each individual site store its local data?

This is the biggest insight students usually miss:

The architecture exists because distribution creates multiple independent

problems.

A centralized DBMS only worries about storing data. A distributed DBMS must addi-
tionally worry about:
l
• dividing data,
mo

• placing data,
• synchronizing data,
• hiding distribution,
• and coordinating many sites together.
That is why extra layers become necessary.

1.9.2 The five-schema reference architecture

An

Schema-by-schema explanation

External Schema (ES)

The view of the database that a particular application or user group sees. Multiple
ESs may exist (one per role). A salesperson sees (customer_id, name, balance);
an auditor sees the full ledger.

Global Conceptual Schema (GCS)

The single enterprise-wide logical view of the entire database. It is the union of
all the data, expressed as ordinary relations, foreign keys, integrity constraints. It
does not say anything about where the data is stored.

Made by Anmol Kansal • Page 25

Distributed Systems / DDBMS

External Schema (ES)

external/global map

Site-independent
Global Conceptual Schema (GCS)
schemata

sal
fragmentation

Fragmentation Schema

allocation

Allocation Schema
local map (1) local map (n)

n
Local Cnc. Schema (Site 1) Local Cnc. Schema (Site n)

Site-specific
schemata
Local Internal Schema (1) Local Internal Schema (n)

Ka
Figure 1.3: Reference architecture of a DDBMS. The top three schemata (ES, GCS, Frag-
mentation) are independent of where data is stored. Below the dashed line, schemata become
site-specific. The “allocation schema” is the crucial bridge that says “fragment Fi lives at site
Sj ”.

Fragmentation Schema
Defines how each global relation is partitioned into fragments. Three flavours (full
details in Chapter 2): horizontal, vertical, and mixed fragmentation.
l
Allocation Schema
Maps each fragment to one or more physical sites. If a fragment is mapped to
mo

multiple sites, it is replicated. PYQ-2024 Q3 asks about “factors affecting allocation”

— those factors live here.

Local Conceptual Schema (LCS)

The view of the data held at one particular site. Conceptually similar to the
conceptual schema of a centralized DBMS, but restricted to that site’s allocated
fragments.

Local Internal Schema (LIS)

How the LCS is physically stored at that site — file organization, indexes, page
An

layout.

Where do the schemata physically live?

A famous MCQ (PYQ-2010 Q1(iv)) asks where the global schema, fragmentation schema, and
allocation schema reside. The answer is (c) all the machines of the DDBMS network —
in the form of a globally replicated directory. Every site needs to know the GCS to validate
queries locally and to know which sites to forward sub-queries to. Caching, partial replication,
and other clever directory schemes are studied in Section 1.10.

Made by Anmol Kansal • Page 26

 CHAPTER 1. INTRODUCTION AND DISTRIBUTED DBMS ARCHITECTURE

1.9.3 Three implementation styles

The reference architecture is abstract. Real DDBMS products implement it in one of three styles.
PYQs from MAKAUT ask about all three.

sal
Client–Server architecture

Client 1 Client 2 Client 3 Client n

Network

n
DB Server 1 DB Server 2 DB Server m

Ka
Figure 1.4: Client–server DDBMS: clients (≤ thin, do presentation) talk to one or more database
servers; the servers may further communicate with each other to honour cross-site queries.

Key idea. Functionality is split into two clearly-typed nodes: clients hold the user interface
and possibly caches; servers hold the data and the DBMS engine. Servers can be single (one big
server, multiple clients) or multiple (several servers in a true DDBMS). When a query spans
servers, one server is chosen as the coordinator and the rest as participants (this is the basis of
two-phase commit in Chapter 4).

Advantages.
• Clear separation of concerns — easy to develop and tune.
l
• Servers can be hardened, secured, and replicated independently.
mo

• Scalable on the read side: add more servers, replicate read-only data.

Disadvantages.
• Server-side may become a bottleneck.
• More moving parts on the network.
• Failure of a server affects all of its clients.
An

Peer-to-Peer (P2P) architecture

Key idea. No special server class. Every node has the full DBMS stack and stores some data.
Clients of a peer are sometimes other peers, sometimes humans.

Architectural components present at every peer:

• User Processor — handles user requests, security, global query parsing.
• Data Processor — accesses the local data, executes the local part of a query.
• Global Directory (or its cache) — knows where every fragment lives.
• Local DBMS — traditional centralized DBMS functionality.

Made by Anmol Kansal • Page 27

Distributed Systems / DDBMS

Peer 1 Peer 2 Peer 3

Site 1 Site 2 Site 3

sal
Peer 4 Peer 5 Peer 6
Site 4 Site 5 Site 6

Figure 1.5: Peer-to-peer DDBMS: every node plays both client and server roles. PYQ-2024 Q4
asks to draw this. Note the fully meshed links — any peer can directly talk to any other.

When is P2P the right answer? When all sites are equal peers — e.g. a federation of
universities sharing research data, or a blockchain-style decentralised ledger. It is not the right

n
answer when one site naturally dominates (e.g. corporate headquarters); for those, client–server
is more honest.

Multi-Database System (MDBS) architecture

Ka
MDBS / Global Layer
(Global schema, query decomposer, transaction monitor)

Oracle DB2 Postgres

DBMS DBMS DBMS

DB1 DB2 DB3

Figure 1.6: Multi-Database System: pre-existing autonomous DBMSs are “wrapped” under one
l
global layer that provides federated access. Each local DBMS retains full local autonomy.
mo

Key difference from ordinary DDBMS. In an MDBS, the local databases pre-exist —
they were designed and built independently. The global layer is bolted on top. In a designed
DDBMS, the entire system is designed top-down from one global conceptual schema. PYQ-2025
Q6 and Q11(a) both ask about MDBS architecture.

1.10 Global Directory Issues

An

The global directory (also called the global system catalog) is the meta-data of the DDBMS: it
stores
1. the GCS itself,

2. the fragmentation schema (which fragments exist),

3. the allocation schema (which sites have which fragments),

4. access rights, statistics for the optimizer, locking information, etc.

The big design question: where do we keep the directory? Four standard answers; each is a
trade-off.

Made by Anmol Kansal • Page 28

 CHAPTER 1. INTRODUCTION AND DISTRIBUTED DBMS ARCHITECTURE

1.10.1 Four directory storage strategies

1. Centralized. One site holds the whole directory. Pros: simple, easy to keep consistent.
Cons: single point of failure; that site becomes a hot spot.
2. Fully replicated. Every site has a full copy. Pros: every site can resolve any name locally;

sal
fast reads. Cons: updates (e.g. a new fragment) are expensive — every site must be informed.
3. Partitioned (distributed). Each site holds the portion of the directory relevant to the
fragments it stores. Pros: updates are local; storage cost is low. Cons: to resolve a name not
stored locally, the site must ask another site — adds inter-site messages.
4. Cached. Combine partitioned + a per-site cache of recently looked-up entries. Pros:
amortises lookup cost over many queries. Cons: cache invalidation problem (a fragment
migration invalidates many caches).

n
Remember This
The MAKAUT exam loves the comparison “centralized vs. replicated vs. partitioned vs.
cached” directory. Write all four in a table; you get the marks. The four words in order

Ka
spell roughly “C R P C” — which you can remember as “Copy Required Per Call” —
a hint at the trade-off each strategy makes.

1.10.2 Comparison table

Property Centralized Replicated Partitioned Cached

Storage cost (total) Low High Low Medium
Read speed Slow Fast Med Fast (on hit)
Update cost Low High Low Medium
Single point of failure Yes No No No
l
Cache-coherence overhead N/A N/A N/A Yes
mo

1.11 End-of-Chapter Summary — Unit 1

1.11.1 Quick revision sheet

Quick Revision
Definitions you must memorise verbatim:
• DDBS, DDBMS, transparency, fragmentation schema, allocation schema, global
An

directory.
Pictures you must be able to draw from memory:
• Reference architecture (Figure 1.3).
• Three nested levels of transparency (Figure 1.2).
• Client–server, P2P, MDBS architectures (Figures 1.4, 1.5, 1.6).
Lists you must be able to spit out:
• 9 advantages (REAL PRIDE), 7 disadvantages (CC SIDE Drift).
• 9 transparencies in order from highest to lowest.

Made by Anmol Kansal • Page 29

Distributed Systems / DDBMS

• 4 directory storage strategies and one trade-off for each.

1.11.2 Most important exam points (from PYQ analysis)

sal
1. “What is the advantage of a DDBMS?” — PYQ-2025 Q1(II), repeatedly examined. Memorise
five out of nine advantages.
2. “What is logical data independence in DDBMS?” — PYQ-2024 Q1(vi). One-liner: change
conceptual schema without breaking external schema.
3. “Distributed transparency at three levels with diagram” — PYQ-2025 Q3.
4. “Peer-to-peer architecture with diagram” — PYQ-2024 Q4. Draw figure 1.5 and label the
User Processor / Data Processor / GD / LDBMS.

n
5. “Heterogeneous distributed database” — PYQ-2024 Q1(iii). Different DBMS products at
different sites; the DDBMS hides the differences (MDBS architecture).
6. “The node where the distributed transaction originates is called the . . . ” — PYQ-2025 Q1(I).

Ka
The canonical answer is coordinator (or “coordinating site”; some books say “root agent”).

1.11.3 High-probability questions for the next exam

Based on three PYQs (2010, 2024, 2025), the following are highly likely to repeat:
• Define DDBS and list its advantages & disadvantages. [5–10 marks]
• Explain three levels of transparency with diagram. [5 marks]
• Describe DDBMS reference architecture. [10–15 marks]
• Compare centralized, replicated, partitioned and cached directory storage. [5 marks]
• Compare client–server vs. peer-to-peer vs. MDBS. [5–10 marks]
l
mo

1.11.4 Practice questions (with quick hints)

MCQ. Global, Fragmentation and Allocation Schema reside in — (a) the coordinator (b) the
system virtually (c) every machine (d) all of these.
Hint: every site needs to know where data is. Answer: (c).
Fill in the blank. The node where a distributed transaction originates is called the .
Answer: coordinator (also called root agent in some references).
One-word. Which transparency hides the existence of multiple physical copies of the same
data? Answer: Replication transparency.
An

Short. “Fragmentation transparency cannot be achieved without location transparency.” True

or false? Justify.
Hint: Think about the nesting in Figure 1.2.
Answer: True. Fragmentation transparency is a stricter guarantee than location transparency,
so it includes location transparency.
Long. Draw and explain the DDBMS reference architecture; explain each schema and the
mappings between them. Hint: reproduce Figure 1.3 and walk through Section 1.9.
Long. Differentiate between distributed databases and parallel databases. Hint: look ahead
to Chapter on parallel databases (Unit 5); the key axes are shared-nothing vs. tightly-coupled,
geographical distribution, autonomy of sites, data autonomy, and network latency.

Made by Anmol Kansal • Page 30

 CHAPTER 1. INTRODUCTION AND DISTRIBUTED DBMS ARCHITECTURE

End of Unit 1 — next chapter: Distributed Database Design & Semantic Data Control.

n sal
l Ka
mo
An

Made by Anmol Kansal • Page 31

 Thank You for Reading!
This was a freely shared demo version of the notes.

Want the Full Exam Preparation Bundle?

Complete Detailed Notes + PYQ Solutions + Question Bank + Revision

Material

Designed specially for Semester Exam Preparation

Purchase at a very affordable student-friendly price

Official Store
[Link]

Join My Telegram Group

[Link]

Contact via Telegram Bot

[Link]
 YouTube Channel
[Link]

Study Smart. Revise Fast. Score Better.

Made by Anmol Kansal