Distributed DBMS Architecture, Fragmentation & Replication

A Distributed DBMS DDBMS consists of software at each site that manages its local data and participates in global query processing.

Distributed DBMS Architecture

A Distributed DBMS (DDBMS) consists of software at each site that manages its local data and participates in global query processing.

	Global Query		Global Schema
	Processor		(data dictionary)
	Local DBMS		Communication
	(handles local data)		Manager

Key Components

Component	Responsibility
Global Schema	Maps logical tables to physical fragments/sites
Query Processor	Decomposes global queries into sub-queries for each site
Communication Manager	Handles network messaging between sites
Local DBMS	Executes sub-queries on local data using standard SQL
Transaction Manager	Coordinates distributed transactions (2PC)

Fragmentation

Fragmentation is the process of dividing a relation into smaller pieces called fragments that are stored at different sites.

Why Fragment?

Without fragmentation: Entire table at one site → all queries go there (bottleneck) With fragmentation: Data stored near where it's used → faster local access

1. Horizontal Fragmentation

Divides a table by rows — each fragment is a subset of tuples satisfying a specific condition.

EmpID	Name	Region
E001	Alice	North
E002	Bob	South
E003	Carol	North
E004	Dave	East

E001	Alice	North
E003	Carol	North

Employee Table (global)

Horizontal Fragments (by Region)

Correctness conditions:

Completeness: Every tuple appears in at least one fragment
Disjointness: Each tuple appears in at most one fragment (usually)
Reconstruction: Original relation recoverable via UNION

2. Vertical Fragmentation

Divides a table by columns — each fragment contains a subset of attributes.

EmpID	Name	Salary	Department
E001	Alice	75000	CS
E002	Bob	62000	Math

E001	Alice	CS
E002	Bob	Math

E001	75000
E002	62000

Employee Table (global)

Vertical Fragments

3. Mixed (Hybrid) Fragmentation

Combines both horizontal and vertical fragmentation.

First apply vertical fragmentation → then horizontal (or vice versa) Employee → V-fragment → then H-fragment each V-fragment Results in grid of fragments, each at a specific site.

Replication

Replication is the process of storing copies of data at multiple sites. Each copy is called a replica.

Types of Replication

Full Replication

The entire database is copied at every site.

Site A	Full copy of all tables
Site B	Full copy of all tables
Site C	Full copy of all tables
Advantage	Maximum availability; any site can serve any query
Disadvantage	Very high update cost (every update must go to all sites)
Best for	Read-heavy systems with rare updates

Partial Replication

Some relations (or fragments) are replicated at selected sites.

Site A (Delhi)	Employee(Delhi), Product(all)
Site B (Mumbai)	Employee(Mumbai), Product(all)
Site C (Central)	Employee(all), Product(all)

No Replication

Each fragment stored at exactly one site.

Advantage: Low update overhead Disadvantage: Site failure makes that data unavailable

Replication Trade-offs

Strategy	Read perf.	Update overhead
Full replication	Excellent	Very high
Partial replication	Good	Moderate
No replication	Site-local	Low

Distributed Query Processing

Challenge

A query may need data from multiple fragments at different sites. The system must:

Decompose the global query into sub-queries
Send sub-queries to relevant sites
Execute sub-queries locally
Combine partial results
Return final result to user

Cost Components

Total Cost = Local Processing Cost + Communication Cost Communication Cost: C = t_msg + t_transfer × data_size Where: t_msg = fixed message overhead (latency) t_transfer = data transfer rate × bytes Goal: Minimize data transferred across network

Semi-Join Optimization

Instead of sending large tables across the network, use semi-joins:

Query	Find employees in CS department (Dept at Site A, Emp at Site B)
Send entire Department table from A to B	expensive if large
1. Send π_{DeptID}(σ_{DeptName='CS'}(Dept)) from A to B	tiny!
2. B computes Emp ⋈ {CS_deptID}	gets matching employees