Chapter four

Distributed Database Systems

5/13/2022 ADBS(Software Engineering) 1

Objective
At the end of this chapter students will be able to…
• Identify concepts of Distributed Databases
• Describe distributed Database Design
• Explain distributed Query Processing and
• Distributed Transaction Management and Recovery

5/13/2022 ADBS(Software Engineering) 2

Distributed Database Concepts

• A transaction can be executed by multiple networked computers in a

unified manner.
• A distributed database (DDB) processes is a unit of execution (a
transaction) in a distributed manner.
• A distributed database (DDB) can be defined as:
• A collection of multiple logically related databases distributed over a computer
network, and a distributed database management system(DDBMS) as a
software system that manages a distributed database while making the
distribution transparent to the user.

5/13/2022 ADBS(Software Engineering) 3

Distributed Database System
• The concept of transparency extends the general idea of hiding implementation
details from end users (making the distribution invisible to users).
• Advantages
• Management of distributed data with different levels of transparency:
• This refers to the physical placement of data which is not known to the user (distribution
transparency).

5/13/2022 ADBS(Software Engineering) 4

Cont’d…
• Advantages (transparency, contd.)
• Distribution or Network transparency:
• This refers to freedom for the user from the operational details of the
network and the placement of the data in the distributed system.
• It may be divided into location transparency and naming
transparency.
• There is Location transparency, which refers to freedom of issuing command
from any location without affecting it’s working.
• Then there is Naming transparency, which allows access to any names object
(files, relations, etc.) from any location.

5/13/2022 ADBS(Software Engineering) 5

Cont’d…

• Advantages (transparency, contd.)

• Replication transparency:
• copies of the same data objects may be stored at multiple sites for better availability,
performance and reliability.
• This is done to minimize access time to the required data.
• Fragmentation transparency:
• Allows to fragment a relation horizontally (create a subset of tuples of a relation) or
vertically (create a subset of columns of a relation).
• Fragmentation transparency makes the user unaware of the existence of
fragments.

5/13/2022 ADBS(Software Engineering) 6

Cont..
• Other Advantages of (DDBMS)
• Increased reliability and availability:
• Reliability- Because data may be replicated so that it exists at more than one site, the failure of a
node or a communication link does not necessarily make the data inaccessible.
• Availability- is the probability that the system is continuously available (usable or accessible) during a
time interval.
• In a centralized DBMS, a computer failure terminates the operations of the DBMS.
However, a failure at one site of a DDBMS or a failure of a communication link making
some sites inaccessible does not make the entire system inoperable.
• A distributed database system has multiple nodes (computers) and if one fails then
others are available to do the job.

5/13/2022 ADBS(Software Engineering) 7

Cont’d…

• Other Advantages (contd.)

• Improved performance:
• A distributed DBMS fragments the database to keep data closer to where it is needed most.
• This reduces data management (access and modification) time significantly.
• Easier expansion (scalability):
• Allows new nodes (computers) to be added anytime without chaining the entire
configuration.

5/13/2022 ADBS(Software Engineering) 8

Data Fragmentation, Replication and Allocation

Data Fragmentation
• Split a relation into logically related and correct parts.
• A relation can be fragmented in two ways:
• Horizontal Fragmentation
• Vertical Fragmentation

5/13/2022 ADBS(Software Engineering) 9

Cont’d…
• Horizontal fragmentation
• It is a horizontal subset of a relation which contain those tuples which satisfy
selection conditions.
• Consider the Employee relation with selection condition (DNO = 5). All tuples
satisfy this condition will create a subset which will be a horizontal fragment of
Employee relation.
• A selection condition may be composed of several conditions connected by
AND or OR.
• Derived horizontal fragmentation: It is the partitioning of a primary relation to
other secondary relations which are related with Foreign keys.

5/13/2022 ADBS(Software Engineering) 10

Cont’d…
• Vertical fragmentation
• It is a subset of a relation which is created by a subset of columns. Thus a
vertical fragment of a relation will contain values of selected columns.
• There is no selection condition used in vertical fragmentation.
• Consider the Employee relation. A vertical fragment of can be created by
keeping the values of Name, Bdate, Sex, and Address.
• Because there is no condition for creating a vertical fragment, each fragment
must include the primary key attribute of the parent relation Employee. In this
way all vertical fragments of a relation are connected.

5/13/2022 ADBS(Software Engineering) 11

Cont’d…
Data Replication
• Replication refers to the distribution of whole or part of the data to a number of sites
• Useful in improving availability of data
• Improve performance of global queries since the result of such query can be obtained
from any one site
• In full replication, the entire database is replicated and in partial replication some
selected part is replicated to some of the sites
• The disadvantage of full replication is that it can slow down update operation since a
single logical update must be performed on every copy of the database to keep the
copies consistent
• Data Distribution (Data Allocation)
• This is relevant only in the case of partial replication or partition.
• The selected portion of the database is distributed to the database sites.
5/13/2022 ADBS(Software Engineering) 12
Types of Distributed Database Systems
• Homogeneous
• All sites of the database system have Window
identical setup, i.e., same database Site 5 Unix
system software. Oracle Site 1
• The underlying operating system may Oracle
be different. Window
• For example, all sites run Oracle or Site 4 Communications
DB2, or Sybase or some other database network
system.
• The underlying operating systems can Oracle
be a mixture of Linux, Window, Unix,
etc. Site 3 Site 2
Linux Oracle Linux Oracle

5/13/2022 ADBS(Software Engineering) 13

Types of Distributed Database Systems
• Heterogeneous
• Federated: Each site may run different database system but the data access is managed
through a single conceptual schema.
• This implies that the degree of local autonomy is minimum. Each site must adhere to a
centralized access policy. There may be a global schema.
• Multi-database: There is no one conceptual global schema. For data access a schema is
constructed dynamically as needed by the application software.

Object Unix Relational

Oriented Site 5 Unix
Site 1
Hierarchical
Window
Site 4 Communications
network

Network
Object DBMS
Oriented Site 3 Site 2 Relational
Linux Linux

5/13/2022 ADBS(Software Engineering) 14

Cont’d…

• Federated Database Management Systems Issues

• Differences in data models:
• Relational, Objected oriented, hierarchical, network, etc.
• Differences in constraints:
• Each site may have their own data accessing and processing constraints.
• Differences in query language:
• Some site may use SQL, some may use SQL-89, some may use SQL-92, and so on.

5/13/2022 ADBS(Software Engineering) 15

Query Processing in Distributed Databases

• Issues
• Cost of transferring data (files and results) over the network.
• This cost is usually high. So, some optimization is necessary.
• Example: Suppose we have the Employee relation at site 1 and Department relation at Site
2
Employee at site 1. 10,000 rows(records). Row size = 100 bytes(each record is 100
bytes long).
• This means, table size = (10,000*100) 106 bytes.
• Department at Site 2. 100 rows(records). Row size = 35 bytes(each record is 35
bytes long).
• This means, table size = (100*3) 3,500 bytes.

5/13/2022 ADBS(Software Engineering) 16

Query Processing in Distributed Databases
• Issues (cont’d…)
• Query Q : For each employee, retrieve employee name and department name
Where the employee works.

• Q: Fname,Lname,Dname (Employee Dno = Dnumber Department)

Employee

Department

• The result of this query will include 10,000 records, assuming that every
employee is related to a department.

5/13/2022 ADBS(Software Engineering) 17

Cont’d…
• Result
• Suppose that Employee and Department relations are not present at site 3(see the figure
shown below)
• Suppose that each result tuple is 40 bytes long. The query is submitted at site 3 and the result
is sent to this site
• If every employee is related to a department, the result of this query will have 10,000 tuples
• The query is submitted at a distinct site 3, which is called the result site because
the query result is needed there. Neither the EMPLOYEE nor the DEPARTMENT
relations reside at site 3. There are three simple strategies for executing this
distributed query:

5/13/2022 ADBS(Software Engineering) 18

Cont’d…
• Strategies:
1. Transfer Employee and Department to site 3 and perform the join there.
• Total transfer bytes = 1,000,000 + 3500 = 1,003,500 bytes.
2. Transfer Employee to site 2, execute join at site 2 and send the result to site 3.
• Query result size = 40 * 10,000 = 400,000 bytes. Total transfer size = 400,000 + 1,000,000
= 1,400,000 bytes.
3. Transfer Department relation to site 1, execute the join at site 1, and send the result
to site 3.
• Total bytes transferred = 400,000 + 3500 = 403,500 bytes.
• Optimization criteria: minimizing data transfer.
Preferred approach: strategy 3.

5/13/2022 ADBS(Software Engineering) 19

Concurrency Control and Recovery
• Distributed Databases encounter a number of concurrency control and
recovery problems which are not present in centralized databases.
Some of them are listed below.
• Dealing with multiple copies of data items
• Failure of individual sites
• Communication link failure
• Distributed commit
• Distributed deadlock

5/13/2022 ADBS(Software Engineering) 20

Cont’d…
• Details
• Dealing with multiple copies of data items:
• The concurrency control must maintain global consistency. Likewise the recovery
mechanism must recover all copies and maintain consistency after recovery.
• Failure of individual sites:
• Database availability must not be affected due to the failure of one or two sites and the
recovery scheme must recover them before they are available for use.

5/13/2022 ADBS(Software Engineering) 21

Cont’d…
• Details (contd.)
• Communication link failure:
• This failure may create network partition which would affect database availability even
though all database sites may be running.
• Distributed commit:
• A transaction may be fragmented and they may be executed by a number of sites. This
require a two or three-phase commit approach for transaction commit.
• Distributed deadlock:
• Since transactions are processed at multiple sites, two or more sites may get involved in
deadlock. This must be resolved in a distributed manner.

5/13/2022 ADBS(Software Engineering) 22

Cont’d…
• Distributed Concurrency control based on a Distinguished copy of a
data item
• Primary site technique:
• In this method, a single primary site is designated to be the
coordinator site for all database items. Hence, all locks are kept at
that site, and all requests for locking or unlocking are sent there. This
method is thus an extension of the centralized locking approach.
Primary site
Site 5
Site 1

Site 4 Communications neteork

Site 3 Site 2
5/13/2022 ADBS(Software Engineering) 23
Cont’d…

• (primary site technique)Transaction management(cont’d… )

• Concurrency control and commit are managed by this site.
• In two phase locking, this site manages locking and releasing data items. If
all transactions follow two-phase policy at all sites, then serializability is
guaranteed.

5/13/2022 ADBS(Software Engineering) 24

Cont’d….
• Transaction Management
• Advantages:
• An extension to the centralized two phase locking so implementation and management is
simple.
• Data items are locked only at one site but they can be accessed at any site.
• Disadvantages:
• All transaction management activities go to primary site which is likely to overload the site.
• If the primary site fails, the entire system is inaccessible.
• To aid recovery a backup site is designated which behaves as a shadow
of primary site. In case of primary site failure, backup site can act as
primary site.

5/13/2022 ADBS(Software Engineering) 25

Cont’d…
Primary Copy Technique:
• In this approach, instead of a site, a data item partition is designated as primary copy.
To lock a data item just the primary copy of the data item is locked.
• Advantages:
• Since primary copies are distributed at various sites, a single site is not overloaded with
locking and unlocking requests.
• Disadvantages:
• Identification of a primary copy is complex. A distributed directory must be maintained,
possibly at all sites.

5/13/2022 ADBS(Software Engineering) 26

Cont’d…
Recovery from a coordinator failure
• In both approaches a coordinator site or copy may become unavailable. This will
require the selection of a new coordinator.
• Primary site approach with no backup site:
• Aborts and restarts all active transactions at all sites. Elects a new coordinator
and initiates transaction processing.
• Primary site approach with backup site:
• Suspends all active transactions, designates the backup site as the primary site
and identifies a new back up site. Primary site receives all transaction
management information to resume processing.
• Primary and backup sites fail or no backup site:
• Use election process to select a new coordinator site.

5/13/2022 ADBS(Software Engineering) 27

Cont’d…
• Concurrency control based on voting:
• There is no primary copy of coordinator.
• Send lock request to sites that have data item.
• If majority of sites grant lock then the requesting transaction gets the data
item.
• Locking information (grant or denied) is sent to all these sites.
• To avoid unacceptably long wait, a time-out period is defined. If the
requesting transaction does not get any vote information then the
transaction is aborted.

5/13/2022 ADBS(Software Engineering) 28

 • Therefore a DDBMS has the following characteristics:
• a collection of logically related shared data;
• the data is split into a number of fragments;
• fragments may be replicated;
• fragments/replicas are allocated to sites;
• the sites are linked by a communications network;
• the data at each site is under the control of a DBMS;
• the DBMS at each site can handle local applications, autonomously;
• each DBMS participates in at least one global application.

5/13/2022 ADBS(Software Engineering) 29

Client-Server Database Architecture…

• It consists of clients running client software, a set of servers which

provide all database functionalities and a reliable communication
infrastructure.
Server 1 Client 1

Client 2

Server 2 Client 3

Server n Client n
5/13/2022 ADBS(Software Engineering) 30
Client-Server Database Architecture

• The server software is responsible for local data management at a

site, much like centralized DBMS software.
• The client software is responsible for most of the distribution
function.
• The communication software manages communication among
clients and servers.

5/13/2022 ADBS(Software Engineering) 31

Cont’d…

• The processing of a SQL queries goes as follows:

• Client parses a user query and decomposes it into a number of independent
sub-queries. Each subquery is sent to appropriate site for execution.
• Each server processes its query and sends the result to the client.
• The client combines the results of subqueries and produces the final result.

5/13/2022 ADBS(Software Engineering) 32

 END

5/13/2022 ADBS(Software Engineering) 33