DISTRIBUTED DATABASE MANAGEMENT

SYSTEM
Design: Replication & Fragmentation Techniques
Comprehensive Study Notes | Exam Coverage: J-19, J-21, M-23, M-24, M-25

1. Distributed Database Management System (DDBMS)

Exam J-21 (~3 marks) — Explain DDBMD (Distributed DBMS)

1.1 Definition
A Distributed Database Management System (DDBMS) is a software system that manages a
distributed database — a collection of logically interrelated data items that are physically distributed
across multiple sites in a computer network — while making the distribution transparent to the user.

1.2 Key Characteristics

• Physical Distribution: Data stored at geographically separated sites connected by a network.
• Logical Integration: Data appears as a single, unified database to the end user.
• Distribution Transparency: Users need not know where data resides.
• Autonomy: Each site can operate independently to some degree.
• Replication: Copies of data may exist at multiple sites for performance & fault tolerance.

1.3 Advantages of DDBMS

Advantage Description
Improved Performance Local queries processed locally; reduces network load.
Higher Availability Failure of one site does not crash the entire system.
Scalability Nodes can be added easily without redesigning the whole
system.
Reliability Replication ensures data survives hardware failures.
Reflects Org Structure Departments can own their own local data.
Data Sharing Remote sites can still access centrally maintained data.
1.4 Disadvantages of DDBMS
• Increased complexity of design, implementation, and management.
• Harder to maintain consistency across sites (distributed concurrency control).
• Network communication overhead can degrade performance.
• Security is more difficult to enforce across multiple sites.
• Lack of standardised tools compared to centralised DBMS.

1.5 Architecture Overview

A DDBMS typically includes the following components:
• Global Conceptual Schema (GCS): Describes the entire distributed database logically.
• Fragmentation Schema: Specifies how relations are split across sites.
• Allocation Schema: Maps fragments to specific physical sites.
• Local DBMS: Each site has its own DBMS managing local data.
• Communication Manager: Handles inter-site message passing and query routing.
2. Data Fragmentation in Distributed Processing
M-23 (14 marks) — What is data fragmentation? Give different types of
Exam
fragmentation in distributed processing system.

2.1 What is Data Fragmentation?

Data fragmentation is the process of dividing a global relation (table) into smaller logical units called
fragments, each of which can be stored at different sites in the distributed network. Fragmentation is
the first step in DDBMS design after the global schema is defined.

Why To store data close to where it is most frequently used, thereby reducing network
Fragment traffic and improving response time.
?

2.2 Correctness Rules for Fragmentation

1. Completeness: Every data item in the original relation must appear in at least one fragment (no
data is lost).
2. Reconstruction: The original relation must be perfectly reconstructable from its fragments using
relational algebra operations.
3. Disjointness: Each data item should appear in exactly one fragment (no overlap), except for
replication purposes in vertical fragmentation where primary keys may be repeated.

2.3 Types of Fragmentation

Type 1: Horizontal Fragmentation (HF)

Horizontal fragmentation divides a relation into subsets of tuples (rows). Each fragment contains a
subset of rows satisfying a specific predicate.

a) Primary Horizontal Fragmentation

Fragments are defined using selection predicates on the relation itself.

Notation: HFᵢ = σ(predicate)(R)

Example: Employee relation fragmented by department location:

• EMP_DELHI = σ (city = 'Delhi') (EMPLOYEE)
• EMP_MUMBAI = σ (city = 'Mumbai') (EMPLOYEE)
• EMP_CHENNAI = σ (city = 'Chennai') (EMPLOYEE)
Each fragment stored at the city's local site. Reconstruction: EMPLOYEE = EMP_DELHI ∪
EMP_MUMBAI ∪ EMP_CHENNAI

b) Derived Horizontal Fragmentation

A relation is fragmented based on a predicate defined on another (usually owner/parent) relation.
Used when a member relation has a foreign-key relationship with an owner relation.

Notation: DHFᵢ = R ⋈ HFᵢ(S) where S is the owner relation

Example: ORDERS fragmented according to the fragmentation of CUSTOMER:

• ORDERS_DELHI = ORDERS ⋈ CUSTOMER_DELHI
• ORDERS_MUMBAI = ORDERS ⋈ CUSTOMER_MUMBAI

Aspect Details
Operation used Selection (σ)
Reconstruction UNION (∪) of all fragments
Disjointness Each tuple in exactly one fragment
Best for Queries that access rows from specific categories/regions
Example predicate Salary > 50000, Region = 'North'

Type 2: Vertical Fragmentation (VF)

Vertical fragmentation divides a relation into subsets of attributes (columns). Each fragment contains a
subset of columns plus the primary key (for reconstruction).

Notation: VFᵢ = π(attribute list)(R)

Example: EMPLOYEE(EmpID, Name, Address, Salary, Dept) fragmented as:

• VF1 = π(EmpID, Name, Address)(EMPLOYEE) — stored at HR Site
• VF2 = π(EmpID, Salary, Dept)(EMPLOYEE) — stored at Accounts Site

Primary key (EmpID) is repeated in both fragments to enable reconstruction.

Reconstruction: EMPLOYEE = VF1 ⋈ VF2 (Natural Join on EmpID)

Aspect Details
Operation used Projection (π)
Reconstruction JOIN (⋈) of fragments on primary key
Disjointness Primary key appears in all fragments; other attrs disjoint
Best for Queries accessing only specific columns (reduces bandwidth)
Design challenge Grouping attributes so each site's queries are local
Type 3: Mixed (Hybrid) Fragmentation
A combination of both horizontal and vertical fragmentation applied to the same relation. This is the
most flexible and commonly used strategy in real systems.

Case A: Horizontal then Vertical (HV)

• First apply horizontal fragmentation to get row-based fragments.
• Then apply vertical fragmentation on each horizontal fragment.
• Reconstruction: First JOIN (vertical), then UNION (horizontal).

Case B: Vertical then Horizontal (VH)

• First apply vertical fragmentation to get column-based fragments.
• Then apply horizontal fragmentation on each vertical fragment.
• Reconstruction: First UNION (horizontal), then JOIN (vertical).

Example: Fragment EMPLOYEE first by region (horizontal), then split each regional fragment into HR-
columns and Payroll-columns (vertical).

Fragmentation Type Operation Reconstruction Primary Use Case

Horizontal Selection (σ) UNION (∪) Data partitioned by
category/region
Vertical Projection (π) JOIN (⋈) Data partitioned by
attribute usage
Mixed / Hybrid σ then π (or vice JOIN then UNION Complex, real-world
versa) distributed schemas
3. Approaches to Store Relations in Distributed Databases
M-24 (7 marks) — Explain the approaches to store the relation in the distributed
Exam
databases.

Once a relation has been fragmented, the next design decision is how and where to store those
fragments across the distributed network. There are three primary approaches:

3.1 Approach 1: Non-Replicated, Non-Fragmented (Centralised)

The entire relation is stored at exactly one site without any fragmentation or replication.

• All queries involving this relation must access the central site.
• Simple to implement; no consistency issues.
• Single point of failure; poor performance for distributed queries.
• Suitable for small, rarely-accessed, or administrative tables.

3.2 Approach 2: Fragmentation (No Replication)

The relation is divided into fragments (horizontal, vertical, or mixed), and each fragment is stored at
exactly one site. No copies exist anywhere else.

• Each site stores only the data it most frequently uses → good locality.
• Queries spanning multiple sites require inter-site joins/unions.
• No redundancy → lower storage cost, no synchronization needed.
• Failure of one site makes that fragment unavailable.

This is the most common approach for large tables in DDBMS design.

3.3 Approach 3: Replication

One or more copies (replicas) of a relation or its fragments are maintained at multiple sites.

3.3.1 Full Replication

The complete relation is copied at every site in the network.
• Excellent read performance: any query can be answered locally.
• Very high write cost: every update must be propagated to all sites.
• High storage overhead.
• Best when reads are very frequent and writes are rare.
3.3.2 Partial Replication
Each fragment is replicated at selected sites (not all). The number of copies depends on how often the
fragment is accessed.
• Balances performance and storage cost.
• More commonly used in practice than full replication.
• Requires a replication factor decision per fragment.

Approach Fragment Replicate Pros Cons

ed? d?
Centralised No No Simple, no sync Single point of
failure
Fragmentation only Yes No Good locality, low cost Site failure →
data unavailable
Full Replication No/Yes All sites Best read performance Expensive writes,
high storage
Partial Replication Yes Selected Balanced trade-off Complex
sites management

3.4 The Allocation Problem

Given a set of fragments and a set of sites, the allocation problem is to decide which fragment goes to
which site(s), optimizing a cost function (e.g., minimizing total communication cost + local processing
cost).

Objective: Minimize communication cost while keeping each site's processing cost acceptable.
• Fragments frequently accessed together by the same site should be co-located.
• Read-only fragments can be replicated freely; write-heavy fragments should minimise copies.
• The allocation schema is stored in the global directory/catalog.
4. DDBMS Design Techniques
J-19 (~7 marks) + M-25 — Fragmentation Techniques & DDBMS Design
Exam
Techniques

The design of a DDBMS involves a series of systematic steps that transform a global conceptual
schema into a physical distributed implementation. The two main pillars of DDBMS design are
Fragmentation and Replication/Allocation.

4.1 Overview of the Design Process

1. Define the Global Conceptual Schema (GCS): Model the entire database as if it were
centralised.
2. Fragmentation Design: Divide relations into fragments based on access patterns.
3. Allocation Design: Decide which fragments (or replicas) go to which site.
4. Physical Design: Choose indexes, storage structures, and access paths at each site.

4.2 Fragmentation Design — Detailed

(See Section 2 for full fragmentation types. Below are the design guidelines and techniques.)

4.2.1 Information Required for Fragmentation

• Quantitative data: Frequency of each query type (read/write), number of tuples, access sites.
• Qualitative data: Predicates used in WHERE clauses, attribute access frequency.

4.2.2 Horizontal Fragmentation Design Technique

Steps to derive primary horizontal fragments:
5. Collect all simple predicates (minterm predicates) used in queries on the relation.
6. Build a set of complete, minimal predicates.
7. Generate minterms: all logically possible combinations of simple predicates.
8. Eliminate contradictory minterms (those that can never be true).
9. Each non-empty minterm defines one fragment.

Example: Relation EMPLOYEE with predicates p1: city='Delhi', p2: city='Mumbai', p3: salary>50000:
• Minterm M1: city='Delhi' ∧ salary>50000
• Minterm M2: city='Delhi' ∧ salary≤50000
• Minterm M3: city='Mumbai' ∧ salary>50000
• Minterm M4: city='Mumbai' ∧ salary≤50000
4.2.3 Vertical Fragmentation Design Technique
Vertical fragmentation is based on attribute affinity — attributes that are accessed together by the
same queries should be placed in the same fragment.

Steps:
10. Build an Attribute Usage Matrix: rows = queries, columns = attributes, cell = 1 if query uses
attribute.
11. Calculate Attribute Affinity: aff(Ai, Aj) = Σ (queries that use both Ai and Aj) × access frequency
× number of sites.
12. Build Affinity Matrix (AA): symmetric matrix of affinity values.
13. Cluster the matrix: Group highly-affine attributes together using Bond Energy Algorithm (BEA).
14. Split the clustered matrix into vertical fragments at the natural break point.

Bond Energy Algorithm (BEA) — Steps

15. Start with any two attributes and compute the initial affinity.
16. For each remaining attribute, find the position in the current ordering that maximises the global
affinity measure (AM).
17. Place attribute at that position.
18. Repeat until all attributes are placed.
19. Identify natural breaks (low inter-cluster affinity) to define fragment boundaries.

AM formula: AM = Σᵢ Σⱼ aff(Aᵢ,Aⱼ) × adjacent(Aᵢ,Aⱼ) (sum over all adjacent attribute pairs)

4.3 Replication Design — Detailed

4.3.1 What is Replication?

Replication is the process of maintaining copies of data (fragments or entire relations) at more than
one site. The primary motivation is fault tolerance and read performance improvement.

4.3.2 Types of Replication

A. Synchronous (Eager) Replication

All replicas are updated atomically as part of the same transaction that updates the primary copy.
Uses distributed transaction protocols (2-Phase Commit, 2PC).
Property Detail
Consistency All replicas always consistent (strong consistency)
Performance Higher write latency due to 2PC overhead
Availability If one replica site is down, the write transaction may fail
Use case Financial systems, mission-critical OLTP
B. Asynchronous (Lazy) Replication
The primary copy is updated first, and changes are propagated to replicas later (after the transaction
commits). Replicas may be temporarily inconsistent.
Property Detail
Consistency Eventual consistency; temporary divergence possible
Performance Fast writes; network delays absorbed asynchronously
Availability High; writes succeed even if replica sites are down
Use case Read-heavy systems, data warehouses, geographic replication

4.3.3 Replication Strategies

i. Primary Copy (Master-Slave) Strategy

• One designated site holds the primary (master) copy.
• All writes go to the primary; primary propagates to secondary (slave) sites.
• Read operations can be served from any replica.
• Simple conflict resolution: primary always wins.
• Bottleneck: primary site can become a performance/availability bottleneck.

ii. Voting / Quorum-Based Strategy

• Each update requires votes from a quorum (majority) of sites holding a replica.
• Read quorum + Write quorum > total replicas (ensures at least one overlap).
• No single primary site bottleneck; more fault tolerant.
• More complex protocol; requires distributed coordination.

iii. Update Everywhere (Multi-Master) Strategy

• Any site with a replica can accept writes.
• Highest availability but highest conflict risk.
• Requires conflict detection and resolution mechanism.
• Used in cloud-native and geo-distributed systems.

4.4 Allocation Design — Detailed

The allocation problem determines the optimal placement of fragments across sites. It is a cost-
optimization problem.

4.4.1 Cost Function

The total cost to minimize is:
Total Cost = Communication Cost + Local Processing Cost + Storage Cost
 • Communication cost: Cost of transferring data between sites for queries that span multiple
sites.
• Local processing cost: CPU/disk cost to process a query at the local site.
• Storage cost: Cost of storing a fragment/replica at a site.

4.4.2 Allocation Heuristics

• A fragment should be stored where it is most frequently accessed (Best Fit heuristic).
• If a fragment is updated frequently from multiple sites, replicate it to reduce remote updates.
• If a fragment is read-only, replicate freely to improve read performance.
• Co-locate fragments that are frequently joined together.

4.4.3 Formal Allocation Algorithm

20. For each fragment Fᵢ, compute access frequency from each site Sⱼ.
21. For each possible allocation (set of sites for each fragment), calculate total cost.
22. Choose the allocation with minimum total cost.
Note: The exact allocation problem is NP-hard; heuristic algorithms are used in practice.

4.5 Two-Phase Commit Protocol (2PC) in DDBMS

2PC is used to ensure atomicity of distributed transactions (especially important when updating
replicas synchronously).

Phase 1 — Voting Phase (Prepare)

23. Coordinator sends PREPARE message to all participants.
24. Each participant writes a redo/undo log entry and sends VOTE-COMMIT or VOTE-ABORT.
25. If a participant cannot commit (e.g., lock conflict), it sends VOTE-ABORT.

Phase 2 — Decision Phase (Commit/Abort)

26. If all participants voted COMMIT → Coordinator sends GLOBAL-COMMIT.
27. If any participant voted ABORT → Coordinator sends GLOBAL-ABORT.
28. Each participant commits or aborts accordingly and sends ACK.
29. Coordinator completes the transaction.

Blocking: If the Coordinator crashes after Phase 1 but before Phase 2, participants
Problem
are blocked waiting for the global decision.

4.6 Distributed Query Processing

After fragmentation and allocation, queries must be decomposed and optimized across sites.
Query Decomposition Steps
30. Normalization: Transform query into a canonical form.
31. Analysis: Check for semantic errors.
32. Simplification: Remove redundant predicates.
33. Restructuring: Use algebraic equivalences to find cheaper execution plans.

Query Optimization Considerations

• Minimize data transfer: Process data locally as much as possible; only transfer necessary
results.
• Semi-join optimization: Reduce relation size before shipping across network.
• Join ordering: Perform the most selective joins first.
• Site selection: Choose the site with lowest load to execute a query.
5. Quick Revision Summary

Topic Key Points to Remember

DDBMS Definition Logically integrated, physically distributed DB; transparent
to user
Fragmentation — General Completeness + Reconstruction + Disjointness
Horizontal Fragmentation Rows split by σ (selection); reconstructed by ∪ (union)
Vertical Fragmentation Columns split by π (projection); reconstructed by ⋈ (join);
PK repeated
Mixed Fragmentation Combination of HF and VF; most flexible
Derived Horizontal Fragment using join with owner relation's horizontal
fragments
Allocation Approaches Centralised / Fragmentation only / Full replication / Partial
replication
Replication Types Synchronous (2PC, strong consistency) vs Asynchronous
(eventual)
Replication Strategies Primary Copy / Quorum / Multi-Master
2PC Protocol Phase 1 = Vote; Phase 2 = Commit/Abort; Problem =
blocking on coordinator crash
BEA Algorithm Clusters attributes by affinity to define vertical fragment
boundaries
Allocation Problem NP-hard; minimize: communication + processing + storage
cost

End of DDBMS Study Notes