Distributed Database Design

Objectives Distributed Database Design

• Definition of Distributed Database

• Motivation for Distributed Database
• Advantage of Distributed Database
• Disadvantages of Distributed Database
• Transactions Management in a Distributed Database environment
• Design of the Distributed Database environment

2
Definition Distributed Database Design

• Distributed database management system (DDBMS)

– Distributed Database: A logically interrelated collection of shared data, physically distributed
over a computer network

– Distributed DBMS (DDBMS): Software system that permits the management of the
distributed database and makes the distribution transparent to users

• Governs storage and processing of logically related data over interconnected computer systems
in which both data and processing functions are distributed among several sites

3
Motivation for Distributed Database Distributed Database Design

• The development of computer network promotes de-centralization

• In a company, the database organization might reflect the organizational structure, which
is distributed into units. Each unit maintains its own database
• Sharing of data can be achieved by developing a distributed database system which:
– Makes data accessible by all units
– Stores data close to where it is most frequently used

4
 Distributed Database Design

Distributed Processing Environment

5
 Distributed Database Design

Distributed Database Management System

6
DDBMS Advantages Distributed Database Design

• Data are located near “greatest demand” site

• Faster data access
• Faster data processing
• Growth facilitation
• Improved communications
• Reduced operating costs
• User-friendly interface
• Less danger of a single-point failure
• Processor independence

7
DDBMS Disadvantages Distributed Database Design

• Complexity of management and control

• Security
• Lack of standards
• Increased storage requirements
• Greater difficulty in managing the data environment
• Increased training cost

8
 Distributed Database Design

Characteristics of Distributed Management

Systems
• Collection of logically-related shared data
• Data split into fragments
• Fragments may be replicated
• Fragments/replicas allocated to sites
• Sites linked by a communications network
• Data at each site is under control of a DBMS
• DBMSs handle local applications autonomously
• Each DBMS participates in at least one global application

9
Characteristics of Distributed Management Systems
Distributed Database Design

• Must perform all the functions of a centralized DBMS

• Must handle all necessary functions imposed by the distribution of data and
processing

• Must perform these additional functions transparently to the end user

10
DDBMS Components Distributed Database Design

• Must include (at least) the following components:

– Computer workstations
– Network hardware and software
– Communications media
– Transaction processor (or, application processor, or transaction manager)
• Software component found in each computer that requests data
– Data processor or data manager
• Software component residing on each computer that stores and retrieves data located at
the site

11
Single-Site Processing, Single-Site Data Distributed
(SPSD) Database Design

• All processing is done on single CPU or host computer (mainframe,

midrange, or PC)
• All data are stored on host computer’s local disk
• Processing cannot be done on end user’s side of the system
• Typical of most mainframe and midrange computer DBMSs
• DBMS is located on the host computer, which is accessed by dumb
terminals connected to it
• Also typical of the first generation of single-user microcomputer databases

12
Multiple-Site Processing, Single-Site Data (MPSD)
Distributed Database Design

• Multiple processes run on different computers sharing a single data repository

• MPSD scenario requires a network file server running conventional
applications that are accessed through a LAN
• Many multi-user accounting applications, running under a personal computer
network, fit such a description

13
Multiple-Site Processing, Distributed Database Design
Multiple-Site Data (MPMD)

• Fully distributed database management system with support for multiple

data processors and transaction processors at multiple sites
• Classified as either homogeneous or heterogeneous
• Homogeneous DDBMSs
– Integrate only one type of centralized DBMS over a network

14
 Distributed Database Design

Homogeneous Distributed Database

15
Multiple-Site Processing, Distributed Database Design
Multiple-Site Data (MPMD)

• Heterogeneous DDBMSs
– Integrate different types of centralized DBMSs over a network
• Fully heterogeneous DDBMS
– Support different DBMSs that may even support different data models
(relational, hierarchical, or network) running under different computer systems,
such as mainframes and microcomputers

16
Distributed Database Distributed Database Design
Transparency Features

• Allow end user to feel like database’s only user

• Features include:
– Distribution transparency
– Transaction transparency
– Failure transparency
– Performance transparency
– Heterogeneity transparency

17
Distribution Transparency Distributed Database Design

• Allows management of a physically dispersed database as though it

were a centralized database
• Three levels of distribution transparency are recognized:
– Fragmentation transparency
– Location transparency
– Local mapping transparency

18
Reference Architecture of DDBMS Distributed Database Design

• Due to diversity, no accepted architecture equivalent to ANSI/SPARC 3-level architecture

for DBMSs.
• • A possible reference architecture consists of:
– Set of global external schemas.
– Global conceptual schema (GCS).
– Fragmentation schema and allocation schema.
– Set of schemas for each local DBMS conforming to 3-level ANSI/SPARC .
– Some levels may be missing, depending on levels of transparency supported.

19
 Distributed Database Design

Reference Architecture of DDBMS

20
Reference Architecture of DDBMS Distributed Database Design

• Global Conceptual Schema is the logical description of the DB as if it were not

distributed. It contains definitions of entities, relationships, constraints, security, and
integrity information
• Fragmentation and Allocation Schemas describe how data are logically partitioned, and
where they are located, taking replication into account
• Local Schemas are the logical descriptions of the local DBs.

21
Transaction Transparency Distributed Database Design

• Ensures database transactions will maintain distributed database’s integrity

and consistency

22
 Distributed Database Design

Distributed Requests and Distributed Transactions

• Distributed transaction
– Can update or request data from several different remote sites on a network
• Remote request
– Lets a single SQL statement access data to be processed by a single
remote database processor
• Remote transaction
– Accesses data at a single remote site

23
 Distributed Database Design

Distributed Queries and Distributed Transactions

• Distributed Queries
– Lets a single SQL statement reference data located at several different local or
remote DB sites

• Distributed transaction
– Allows a transaction to reference several different (local or remote) DB sites

24
Distributed Query Distributed Database Design

25
Distributed Transaction Distributed Database Design

26
Distributed Concurrency Control Distributed Database Design

• Multisite, multiple-process operations are much more likely to create data

inconsistencies and deadlocked transactions than are single-site systems

27
Issues in Distributed Database Design Distributed Database Design

Three key issues we have to consider:

• Data Allocation: where are data placed?
Data should be stored at site with "optimal" distribution.
• Fragmentation: relation may be divided into a number of sub-relations (called
fragments) , which are stored in different sites.
• Replication: copy of fragment may be maintained at several sites

28
Issues in Distributed Database Design Distributed Database Design

• Definition and allocation of fragments carried out

strategically to achieve:
– Locality of Reference
– Improved Reliability and Availability
– Improved Performance
– Balanced Storage Capacities and Costs
– Minimal Communication Costs.
• Involves analyzing most important transactions, based on quantitative/qualitative
information.

29
Data Allocation Distributed Database Design

• Four strategies regarding placement of data:

• Centralized
• Partitioned (or Fragmented)
• Complete Replication
• Selective Replication

30
 Distributed Database Design
Data Allocation
• Centralized: Consists of single database stored at one site with users distributed across
the network (This is not a DDB but distributed processing!)
• Partitioned: Database partitioned into disjoint fragments, each fragment assigned to one
site.
• Complete Replication: Consists of maintaining complete copy of database at each site.
• Selective Replication: Combination of partitioning,
replication, and centralization.

31
Fragment Locations Distributed Database Design

32
Why Fragment? Distributed Database Design

• Usage
– Applications work with partition rather than entire relations
• Efficiency
– Data is stored close to where it is most frequently used
– Data that is not needed by local applications is not stored
• Parallelism
– With fragments as unit of distribution, transaction can be divided into several sub-queries that operate
on fragments
• Security
– Data not required by local applications is not stored and so not available to unauthorized users

33
Design Consideration for FragmentationsDistributed Database Design
• Quantitative information may include:
– frequency with which a transaction is run;
– site from which a transaction is run;
– performance criteria for transactions.
• Qualitative information may include transactions that are executed such as:
– type of access (read or write);
– predicates of read operations.

34
Fragmentation Distributed Database Design

• A relation R is divided into fragments r1, r2, …rn, which contain enough information to
allow reconstruction of R
• Example:
We have a relation Sells (pub, address, price, type)
Type is “small” or “large”. We can split Sells into two different fragments:
• • Sellssmall= σtype = “small”(Sells)
• • SellsLage= σtype = “large”(Sells)

35
Comparison of Strategies for Data Distribution Distributed Database Design

36
Types of Fragmentation Distributed Database Design

• Four types of fragmentation:

– Horizontal
– Vertical
– Mixed
– Derived
• Other possibility is no fragmentation:
– If relation is small and not updated frequently, may be better not to fragment
relation.

37
Horizontal and Vertical Fragmentation Distributed Database Design

38
Horizontal Fragmentation Distributed Database Design

• Each fragment consists of a subset of the tuples of a relation R.

• Defined using Selection operation of relational algebra: σp(R)
• Example:
Relation: Sells(pub, address,price,type)
Fragments:
– SellsBitter= σtype = “bitter”(Sells)
– SellsLager= σtype = “lager”(Sells)

39
Horizontal Fragmentation Distributed Database Design

• This strategy is determined by looking at predicates used by transactions.

• Involves finding set of minimal (complete and relevant) predicates.
• Set of predicates is complete, if and only if, any two
tuples in same fragment are referenced with same
probability by any application.
• Predicate is relevant if there is at least one application that accesses fragments
differently

40
Vertical Fragmentation Distributed Database Design

• Each fragment consists of a subset of attributes of a relation R.

• Defined using projection operation of relational algebra: Πa1,…an(R)
• Determined by establishing affinity of one attribute to another.
• Example:
• Relation:
– Bars (name, address, licence, employees, owner)
• Fragments:
– » Πname,address,licence (Bars)
– » Πname,address,employees,owner(Bars)

41
Mixed Fragmentation Distributed Database Design

42
Example - Mixed Fragmentation Distributed Database Design

• S1 = ΠstaffNo, position, sex, DOB, salary(Staff)

• S2 = ΠstaffNo, fName, lName, branchNo(Staff)
• S21 = σ branchNo=‘B003’(S2)
• S22 = σ branchNo=‘B005’(S2)
• S23 = σ branchNo=‘B007’(S2)

43
Derived Horizontal Fragmentation Distributed Database Design

• A horizontal fragment that is based on horizontal fragmentation of a parent

relation.
• Ensures that fragments that are frequently joined together are at same site.
• Defined using Semijoin operation of relational algebra:
• Ri = R >F Si, 1 ≤ i ≤ w

44
Derived Horizontal Fragmentation Distributed Database Design

• S3 = σ branchNo=‘B003’(Staff)
• S4 = σ branchNo=‘B005’(Staff)
• S5 = σ branchNo=‘B007’(Staff)
• Could use derived fragmentation for Property:
Pi = PropertyForRent >branchNo Si, 3 ≤ i ≤ 5

45
Derived Horizontal Fragmentation Distributed Database Design

• If relation contains more than one foreign key, need to select one as parent.
• Choice can be based on fragmentation used most frequently or fragmentation
with better join characteristics.

46
Correctness of Fragmentation Distributed Database Design

• In defining fragments we have to be very careful.

• Three correctness rules:
– Completeness
– Reconstruction
– Disjointness.

47
Completeness of Fragmentation Distributed Database Design

• Completeness: If relation R is decomposed into fragments r1, r2, …rn, each

data item that can be found in R must appear in at least one fragment. This
ensures no loss of data during fragmentation

48
Reconstruction of Fragmentation Distributed Database Design

• Reconstruction: we must be able to reconstruct the entire R from fragments.

• For horizontal fragmentation is union operation.
– R = r1 ∪ r2 ∪ … ∪ rn,
• For vertical fragmentation is natural join operation.
– R = r1 >< r2 >< … >< rn,
• To ensure reconstruction we have to include primary key attributes in all fragments.

49
Disjointness of Fragmentation Distributed Database Design

• Disjointness: if data item x appears in fragment ri, then it should not appear in any other
fragment.
– Exception: vertical fragmentation, where primary key
attributes must be repeated to allow reconstruction.
• For horizontal fragmentation, data item is a tuple
• For vertical fragmentation, data item is an attribute.

50
Correctness of Horizontal Fragment Distributed Database Design

• Relation: Sells(pub, address,price,type) type={Bitter, Lager}

• Fragments:
• • SellsBitter= σtype = “bitter”(Sells)
• • SellsLager= σtype = “lager”(Sells)
• Correctness rules
– Completeness: Each tuple in the relation appears either in
– SellsBitter, or in SellsLager
– Reconstruction: The Sells relation can be reconstructed from the fragments Sells = SellsBitter ∪
SellsLager
– Disjointness: The two fragments are disjoint, there can be no beer that is both “Lager” and “Bitter”

51
Correctness of Vertical Fragment Distributed Database Design

• Relation: Bars(name,address,licence,employees,owner)
• Fragments:
• • r1 =Πname,address,licence (Bars)
• • r2 = Πname,address,employees,owner(Bars)
• Correctness rules
• • Completeness: Each attribute in the Bars relation appears either in
• r1 or in r2
• • Reconstruction: The Bars relation can be reconstructed from the
• fragments
• Bars = r1 >< r2
• • Disjointness: The two fragments are disjoint, except for the primary
• key, name, which is necessary for reconstruction

52
Transparency in Distributed databases Distributed Database Design

• Distribution Transparency
• Transaction Transparency
• Performance Transparency
• DBMS Transparency

53
Distribution Transparency Distributed Database Design

• The user has to perceive the DDB as a single, logical entity

• Fragmentation Transparency: the user does not need to know that data is fragmented
• Location Transparency: the user does not need to know the location of data items
• Replication Transparency: the user is unaware of replication of data.
• Naming transparency: items in a database must have a unique name, but users don’t
need to worry about it.

54
Naming Transparency Distributed Database Design

• Each item in a DDB must have a unique name.

• DDBMS must ensure that no two sites create a database object with same name.
• Solution 1: create central name server.
• Disadvantages:
– loss of some local autonomy;
– central site may become a bottleneck;
– low availability; if the central site fails, remaining sites cannot create any new objects.

55
Naming Transparency Distributed Database Design

• Solution 2: prefix object with identifier of site that created it

• Example: Beer created at site S1 might be named [Link]
• Disadvantage: loss of distribution transparency

56
Transaction Transparency Distributed Database Design

• Ensures that all distributed transactions maintain distributed database’s integrity and
consistency.
• Distributed transaction accesses data stored at more than one location.
• Each transaction is divided into number of sub transactions, one for each site that has to
be accessed.
• DDBMS must ensure the indivisibility of both the global transaction and each sub-
transactions.
• Must ensure both concurrency transparency, and failure transparency

57
Concurrency Transparency Distributed Database Design

• logically consistent with results obtained if transactions executed one at a time, in some
arbitrary serial order. Same fundamental principles as for centralized DBMS
• DDBMS must ensure both global and local transactions do not interfere with each other
• Similarly, DDBMS must ensure consistency of all sub transactions of global transaction.
• Techniques for concurrency control. Usually different from the ones for DBMS.

58
Concurrency Transparency Distributed Database Design

• Replication makes concurrency more complex. If a copy of a replicated data

item is updated, update must be propagated to all copies.
• Could propagate changes as part of original transaction, making it an atomic
operation.
• However, if one site holding copy is not reachable, then transaction is delayed
until site is reachable.

59
Concurrency Transparency Distributed Database Design

• Could limit update propagation to only those sites currently available.

Remaining sites updated when they become available again.
• Could allow updates to copies to happen asynchronously, sometime after the
original update.
• Delay in regaining consistency may range from a few seconds to several
hours.

60
Failure Transparency Distributed Database Design

• DDBMS must ensure atomicity and durability of global transaction.

• Means ensuring that sub-transactions of global transaction either all commit or all abort.
• Thus, DDBMS must synchronize global transaction to ensure that all sub-transactions
have completed successfully before recording a final COMMIT for global transaction.
• Must do this in presence of site and network failures.

61
Performance Transparency Distributed Database Design

• DDBMS must perform as if it were a centralized DBMS:

• DDBMS should not suffer any performance degradation due to distributed
architecture.
• DDBMS should determine most cost-effective strategy to execute a request.

62
Performance Transparency Distributed Database Design

• Distributed Query Processor (DQP) maps data request into ordered sequence
of operations on local databases.
• It must consider fragmentation, replication, and allocation schemas.
• DQP has to decide:
– which fragment to access;
– which copy of a fragment to use;
– which location to use.

63
Performance Transparency Distributed Database Design

• DQP produces execution strategy optimized with respect to some cost

function.
• Typically, costs associated with a distributed request include:
– I/O cost;
– CPU cost;
– Communication cost.

64
Performance Transparency - Example Distributed Database Design

• Property(Pno, City) 10000 records in London

• Renter(Rno,Max_Price) 100000 records in Glasgow
• Viewing(Pno, Rno) 1000000 records in London
SELECT [Link]
FROM property p INNER JOIN
(renter r INNER JOIN viewing v ON [Link] = [Link])
ON [Link] = [Link]
WHERE [Link]=‘Aberdeen’ AND r.max_price > 200000;

65
Performance Transparency - Example Distributed Database Design

• Assume: Each tuple in each relation is 100 characters long

• 10 renters with maximum price greater than £200,000.
• 100 000 viewings for properties in Aberdeen.
• Computation time negligible compared to communication time.

66
Performance Transparency - Example Distributed Database Design

67
Distribution Transaction Management Distributed Database Design

• DDBMS must ensure:

– synchronization of sub-transactions with other local transactions executing concurrently at a site;
– synchronization of sub-transactions with global
transactions running simultaneously at same of
different sites.
• Global transaction manager (transaction coordinator) at each site, to coordinate global
and local transactions initiated at that site.

68
Distribution Transaction Management Distributed Database Design

• Techniques for Distributed Concurrency Control must ensure distributed

serializability
• Locking protocols (2PL protocol)
• Timestamping methods (extend the definition of timestamp so that it includes
a site identifier)

69
Two-Phase Commit Protocol Distributed Database Design

• Distributed databases make it possible for a transaction to access data

at several sites
• Final COMMIT must not be issued until all sites have committed their
parts of the transaction
• Two-phase commit protocol requires each individual DP’s transaction
log entry be written before the database fragment is actually updated

70
Two-Phase Commit Protocol Distributed Database Design

• All participating nodes in a distributed transaction should perform the same

action:
• They should either all commit or all perform a rollback of the transaction. The
database
• Automatically controls and monitors the commit or rollback of a distributed
transaction and maintains the integrity of the global database (the collection of
databases participating in the transaction) using the two-phase commit
mechanism
• The commit mechanism has the following distinct phases
– Prepare Phase
– Commit Phase
– Forget Phase

71
Two-phase commit Distributed Database Design

• Commit occurs in two phases

– Voting phase
– Actual commit
• Commit controlled by TP system
– Distributed Transaction Coordinator (DTC)

72
Two-phase commit – Prepare Phase Distributed Database Design

• The initiating node, called the global coordinator, asks participating nodes
other than the commit point site to promise to commit or roll back the
transaction, even if there is a failure. If any node cannot prepare, the
transaction is rolled back

73
Two-phase commit – Commit Phase Distributed Database Design

• Participants must write transaction temporarily to durable storage

• If all participants respond to the coordinator that they are prepared, then the
coordinator asks the commit point site to commit. After it commits, the
coordinator asks all other nodes to commit the transaction.
• The global coordinator forgets about the transaction in Forget Phase.

74
Two-phase commit – Other possibility Distributed Database Design

• Three possibilities
– All participants reply positive within time-out interval
• Commit transaction
– One or more participants reply negative
• Abort transaction
– One or more participants do not reply within time-out interval
• Abort transaction

75
Two-phase Commit – Actual commit Distributed Database Design

• Commit transaction
– DTC sends Commit OK message to all participants
– All participants commit
• Write from temporary durable storage to permanent durable storage

76
Two-phase Commit – Abort commit Distributed Database Design

• Abort transaction
– When at least one participant not ready to commit or timeout
– DTC sends Abort message to all participants
• All participants rollback
• Removed from temporary durable storage

77
Distributed Lock Management Distributed Database Design

• Normal locking strategies hold

– Locking done using local lock manager
– Local deadlocks can be prevented and/or resolved
– Distributed deadlocks can happen
• No reliable low cost algorithms for deadlock avoidance and prevention exist today

78
 Query Optimization Distributed Database Design

• Objective of query optimization routine is to minimize total cost associated with

the execution of a request
• Costs associated with a request are a function of the:
– Access time (I/O) cost
– Communication cost
– CPU time cost

79
Query Optimization Distributed Database Design

• Must provide distribution transparency as well as replica transparency

• Replica transparency:
– DDBMS’s ability to hide the existence of multiple copies of data from the user
• Query optimization techniques:
– Manual or automatic
– Static or dynamic
– Statistically based or rule-based algorithms

80
 Distributed Database Design

C. J. Date’s Twelve Commandments for

Distributed Databases
• Fundamental Principle: To the user, a distributed system should look exactly like a
non-distributed system.
1. Local site independence
2. Central site independence
3. Failure independence
4. Location transparency
5. Fragmentation transparency
6. Replication transparency
7. Distributed query processing
8. Distributed transaction processing
9. Hardware independence
10. Operating system independence
11. Network independence
12. Database independence

81
Summary Distributed Database Design

• Distributed database stores logically related data in two or more

physically independent sites connected via a computer network
• Database is divided into fragments
• Distributed databases require distributed processing
• Main components of a DDBMS are the transaction processor and the
data processor

82
 Distributed Database Design

Summary
• Current database systems can be classified by extent to which they
support processing and data distribution
• DDBMS characteristics are best described as a set of transparencies
• A transaction is formed by one or more database requests
• A database can be replicated over several different sites on a computer
network

83
Reference Distributed Database Design

• [Link]
• M. Tamer Ozsu, Patrick Valduriez – Principle of Distributed Database Systems, Prentice
Hall
• Oracle® Database Administrator's Guide 10g Release 2 (10.2)
• David Bell, Jane Grimson – Distributed Database Systems, Addison-Wesley
• [Link]
• [Link]

84
 Distributed Database Design

Thank You!

85