Unit 2 contents

• Distributed DBMS Architecture:

• -ANSI/SPARC
• -Centralized DBMS Architecture
• -Architectural Models for Distributed DBMS
• Distributed Database Design:
• -Top Down Design process
• -Distribution Design issues
• -Fragmentation
• -Allocation

Distributed © M. T. Özsu & P.

Ch.3/1
Architecture
• Defines the structure of the system
● components identified
● functions of each component defined
● interrelationships and interactions between components defined

Distributed © M. T. Özsu & P.

Ch.3/2
ANSI/SPARC Architecture

User
s

Extern Extern Extern Extern

al al al al
Schem view view view
a

Concept Conceptu
al
ual view
Schema

Intern Internal
al view
Sche
Distributed ma © M. T. Özsu & P.
Ch.3/3
Generic DBMS Architecture

Distributed © M. T. Özsu & P.

Ch.3/4
DBMS Implementation Alternatives

Distributed © M. T. Özsu & P.

Ch.3/5
Dimensions of the Problem
• Distribution
● Whether the components of the system are located on the same
machine or not
• Heterogeneity
● Various levels (hardware, communications, operating system)
● DBMS important one
● data model, query language,transaction management algorithms
• Autonomy
● Not well understood and most troublesome
● Various versions
● Design autonomy: Ability of a component DBMS to decide on issues
related to its own design.
● Communication autonomy: Ability of a component DBMS to decide
whether and how to communicate with other DBMSs.
● Execution autonomy: Ability of a component DBMS to execute local
operations in any manner it wants to.
Distributed © M. T. Özsu & P.
Ch.3/6
Client/Server Architecture

Distributed © M. T. Özsu & P.

Ch.3/7
Advantages of Client-Server
Architectures
• Horizontal and vertical scaling of resources
• Better price/performance on client machines
• Ability to use familiar tools on client machines
• Client access to remote data (via standards)
• Full DBMS functionality provided to client workstations
• Overall better system price/performance

Distributed © M. T. Özsu & P.

Ch.3/8
Database Server

Distributed © M. T. Özsu & P.

Ch.3/9
Distributed Database Servers

Distributed © M. T. Özsu & P.

Ch.3/10
 Peer-to-Peer Component
Architecture
USER DATA
PROCESSOR PROCESSOR
Global Local Syste Local
Extern
Concept Concept m Intern
al ual GD/ ual Log al
Schem Schema D Schema Sche
User a ma
reques Databa
Controller

ts
Interface

Semantic

Processor
Optimizer se

Recovery
Handler

Manager
Monitor

Process
Executi

Runtim

Suppor
Global
Global

Query
Query
User

Data

Local
Local
on

or
USER

t
System
response
s

Distributed © M. T. Özsu & P.

Ch.3/11
Datalogical Distributed DBMS
Architecture
ES ES .. ES
1 2
. n

GCS

LCS LCS .. LCS

1 2 . n

LIS LIS .. LIS

1 2
. n

Distributed © M. T. Özsu & P.

Ch.3/12
Datalogical Multi-DBMS
Architecture
GES GES .. GES
1 2
. n

LES1 … LES1 GCS LESn … LESn

1 n 1 m

LCS LCS … LCS

1 2 n

LIS LIS … LIS

1 2 n

Distributed © M. T. Özsu & P.

Ch.3/13
DBMS Components & Execution
Global
User
Reque
st

Local Local
User Multi- User
Reque DBMS Reque
st Global LayerGlobal Global st
Subreque Subreque Subreque
st st st

DBMS DBMS DBMS

1 2 3

Distributed © M. T. Özsu & P.

Ch.3/14
Mediator/Wrapper Architecture

Distributed © M. T. Özsu & P.

Ch.3/15
Design Problem
• In the general setting :
Making decisions about the placement of data and programs
across the sites of a computer network as well as possibly
designing the network itself.

• In Distributed DBMS, the placement of applications

entails
● placement of the distributed DBMS software; and
● placement of the applications that run on the database

Distributed © M. T. Özsu & P.

Ch.3/16
Distribution Design
• Top-down

● mostly in designing systems from scratch

● More suitable for tightly integrated, homogeneous distributed
DBMS
systems

• Bottom-up
● when the databases already exist at a number of sites
● Suitable for applications where database already exists
● Starting point is individual conceptual schemas
● Exists primarily in the context of heterogeneous database.

Distributed © M. T. Özsu & P.

Ch.3/17
Top-Down Design
Requireme
nts
Analysis

Objectives
User
Conceptual Input View
View Design
Design
Integration

Access
GCS Information ES’s

Distributio
n User
Design Input

LCS’s

Physical
Design

LIS’s
Distributed © M. T. Özsu & P.
Ch.3/18
Top down Design Process
● Suitable for applications where database needs to be
build from scratch

● Activity begins with requirement analysis that defines

the environment of the system and “elicits both the
data and processing needs of all potential DB users”

● This study also specifies where the final system is

expected to stand w.r.to the objectives of DDBS

● These objectives are defined w.r.to performance,

reliability and availability

Distributed © M. T. Özsu & P.

Ch.3/19
cont…

● Requirement document is input to two parallel

activities:

● view design activity, deals with defining the interfaces for

end users

● conceptual design, process by which enterprise is examined

to

determine entity types and relationships

✓ Can be further divided into 2 related activity

groups
● Entity analyses, concerned with determining the
entities, attributes and the relationship between
Distributed
them © M. T. Özsu & P.
Ch.3/20
Cont..
• There is a relationship between the conceptual design and view
design

• Conceptual design is an integration of user views

• View integration should be used to ensure that entity and

relationship requirements for all the views are covered in the view
design

• From the conceptual design step comes the definition of GCS

• The GCS and Access pattern information collected as a result of

View design
Distributed © M. T. Özsu & P.
Ch.3/21
Cont..
• The objective of this stage is to define LCS

• Distributed design activity consists of two steps

✓ Fragmentation
✓ Allocation

Distributed © M. T. Özsu & P.

Ch.3/22
Distribution Design Issues
❶ Why fragment at all?

❷ How to fragment?

❸ How much to fragment?

❹ How to test correctness?

❺ How to allocate?

❻ Information requirements?

Distributed © M. T. Özsu & P.

Ch.3/23
Reasons for Fragmentation
• distribution is performed on the basis of entire files.
• What is a reasonable unit of distribution?
● A relation is not a suitable unit
• Because views are subsets of relations . Therefore the locality of
accesses of applications is defined not on entire relations but on
their subsets.
• views defined on a given relation reside at different sites, two
alternatives with the entire relation being the unit of distribution .
• i) Either the relation is not replicated and is stored at only one
site, it results in an unnecessarily high volume of remote data
accesses

Distributed © M. T. Özsu & P.

Ch.3/24
Cont…
• ii)or it is replicated at all or some of the sites where the
applications reside. It has unnecessary replication, which causes
problems in executing updates and may not be desirable if
storage is limited.

• the decomposition of a relation into fragments, each being

treated as
a unit, permits a number of transactions to execute concurrently.

• Fragmentation typically increases the level of concurrency and

therefore the system throughput.
• Minimizing distributed joins is a fundamental fragmentation issue.
• The second problem is related to semantic data control,
specifically to integrity checking.
Distributed © M. T. Özsu & P.
Ch.3/25
 Fragmentation Alternatives –
Horizontal
PROJ
PROJ1 : projects with budgets less PNO PNAME BUDGE LOC
T
than $200,000 P Instrumentati 1500 Montre
P
1 Database
on 1350
00 New
al
PROJ2 : projects with budgets greater P2 CAD/CAM
Develop. 2500
00 New
York
3P Maintenan 3100
00 Pari
York
than or equal to $200,000 P
4 CAD/CAM
ce 5000
00 Bosto
s
5 00 n

PROJ1 PROJ2

PNO PNAME BUDGE LOC PNO PNAME BUDGE LOC

P Instrumentati T
15000 Montre P CAD/CAM T
2500 New
1 on 0 al 3 00 York
P Database 1350 New P Maintenan 3100 Pari
2 Develop. 00 York 4 ce 00 s
P CAD/CAM 5000 Bosto
5 00 n

Distributed © M. T. Özsu & P.

Ch.3/26
Fragmentation Alternatives –
Vertical
PROJ
PROJ1: information about project PNO PNAME BUDGE LOC
T
budgets P Instrumentati 1500 Montre
P
1 Database
on 1350
00 New
al
PROJ2: information about project P
2 CAD/CAM
Develop. 2500
00 New
York
P
3 Maintenan 3100
00 Pari
York
names and locations P
4 CAD/CAM
ce 5000
00 Bosto
s
5 00 n

PROJ1 PROJ2
PNO BUDGE PNO PNAME LOC
T
P 1500 P Instrumentati Montre
P
1 1350
00 P
1 Database
on New
al
P
2 2500
00 P
2 CAD/CAM
Develop. New
York
P
3 3100
00 P
3 Maintenan Pari
York
P
4 5000
00 P
4 CAD/CAM
ce Bosto
s
5 00 5 n

Distributed © M. T. Özsu & P.

Ch.3/27
Degree of Fragmentation

• The extent to which the database should be fragmented is an

important decision that affects the performance of query
execution.

• The degree of fragmentation goes from one extreme, that is,

• not to fragment at all, to the other extreme, to fragment to the

level of individual tuples (in the case of horizontal fragmentation)
or to the level of individual attributes (in the case of vertical
fragmentation).

Distributed © M. T. Özsu & P.

Ch.3/28
Cont…

finite number of
alternatives

tuples relation
or s
attribut
es

Finding the suitable level of partitioning within

this range

Distributed © M. T. Özsu & P.

Ch.3/29
Correctness of Fragmentation
• Completeness
● Decomposition of relation R into fragments R1, R2, ..., Rn is complete
if and only if each data item in R can also be found in some Ri
• Reconstruction
● If relation R is decomposed into fragments R1, R2, ..., Rn, then there
should exist some relational operator ∇ such that
R = ∇1≤i≤nRi
• Disjointness
● If relation R is decomposed into fragments R1, R2, ..., Rn, and data
item di is in Rj, then di should not be in any other fragment Rk (k ≠
j ).

Distributed © M. T. Özsu & P.

Ch.3/30
Allocation Alternatives
• Non-replicated
● Partitioned Database : each fragment resides at only one site
• Replicated
• fully replicated : Entire database exists at each site
• partially replicated : copies of a fragment may reside in multiple
sites

• The reasons for replication are reliability and efficiency of read-

only queries.

Distributed © M. T. Özsu & P.

Ch.3/31
Comparison of Replication
Alternatives
Full- Partial- Partitionin
replication replication g
QUERY Same
Eas
y Difficulty
PROCESSING

DIRECTORY Easy or Same

MANAGEMENT Non- Difficulty
existant
CONCURRENCY
Moderat Difficult Eas
CONTROL
e y

RELIABILITY Very High Low

high

Possible Possible
REALITY Realisti
applicatio applicatio
c
Distributed
n © M. T. Özsu & P.
n
Ch.3/32
Information Requirements
• Four categories:
● Database information
● Application information
● Communication network information
● Computer system information

• The latter two categories are completely quantitative in nature

and are used in allocation models rather than in fragmentation
algorithms.

Distributed © M. T. Özsu & P.

Ch.3/33
Fragmentation
• Horizontal Fragmentation (HF) :horizontal
fragmentation partitions a relation along its tuples.
i)Primary Horizontal Fragmentation (PHF) :
● Primary horizontal fragmentation of a relation is
performed using predicates that are defined on that
relation.
ii) Derived Horizontal Fragmentation (DHF):
● is the partitioning of a relation that results from
predicates being defined on another relation.
• Vertical Fragmentation (VF)
• Hybrid Fragmentation (HF)
Distributed © M. T. Özsu & P.
Ch.3/34
Information Requirements of Horizontal Fragmentation

• I) Database Information.
- The database information concerns the global conceptual
schema. In this context it is important to note how the database
relations are connected to one another, especially with joins.

-In the relational model, these relationships are also depicted as

relations.

-entity-relationship (E–R) model , these relationships between

database objects are depicted explicitly
-directed links are drawn between relations that are related to
each other by an equijoin operation.
-The relation at the tail of a link is called the owner of the link
and the relation at the head is ©called
Distributed
the member
M. T. Özsu & P.
Ch.3/35
Cont…

• Database Information
● relationship
SKILL
TITLE, SAL

L1
EMP PROJ
ENO, ENAME, TITLE PNO, PNAME, BUDGET,
LOC

ASG
ENO, PNO, RESP,
DUR
● cardinality of each relation: card(R)

Distributed © M. T. Özsu & P.

Ch.3/36
Cont…
• II) Application Information
- both qualitative and quantitative information is required
about applications.
- The qualitative information guides the fragmentation activity,
whereas the quantitative information is incorporated primarily into
the allocation models.

• Thumb rule:
- most active 20% of user queries account for 80% of the total
data accesses.
- This “80/20 rule” may be used as a guideline in carrying out this
analysis

Distributed © M. T. Özsu & P.

Ch.3/37
Cont…
● simple predicates : Given R[A1, A2, …, An], a simple predicate pj is
pj : Ai θValue
where θ ∈ {=,<,≤,>,≥,≠}, Value ∈ Di and Di is the domain of Ai.
For relation R we define Pr = {p1, p2, …,pm}
Example :
PNAME = "Maintenance"
BUDGET ≤ 200000
● minterm predicates : Given R and Pr = {p1, p2, …,pm}
define M = {m1,m2,…,mr} as

M = { mi | mi = ∧ pj∈Pr pj* }, 1≤j≤m, 1≤i≤z

where pj* = pj or pj* = ¬(pj).

Distributed © M. T. Özsu & P.

Ch.3/38
Cont…
• Consider relation PAY .
The following are some of the possible simple predicates that can
be defined on PAY.

p1: TITLE = “Elect. Eng.”

p2: TITLE = “Syst. Anal.”
p3: TITLE = “Mech. Eng.”
p4: TITLE = “Programmer”
p5: SAL ≥ 30000

Distributed © M. T. Özsu & P.

Ch.3/39
Cont…
• ExampleThe following are some of the minterm predicates
that can be defined based on these simple predicates.

m1: TITLE = “Elect. Eng.” ^ SAL <= 30000

m2: TITLE = “Elect. Eng.” ^ SAL > 30000
m3: :(TITLE = “Elect. Eng.”) ^ SAL ≥ 30000
m4: :(TITLE = “Elect. Eng.”) ^ SAL > 30000
m5: TITLE = “Programmer” ^ SAL 30000
m6: TITLE = “Programmer” ^ SAL > 30000

Distributed © M. T. Özsu & P.

Ch.3/40
Cont…
• The minterm definition requires each predicate to be in a minterm
in either
its natural or its negated form.

Thus, m1, for example, should be written as

m1: TITLE = “Elect. Eng.” ^ TITLE 6= “Syst. Anal.” ^ TITLE 6=

“Mech. Eng.” ^ TITLE 6= “Programmer” ^ SAL <= 30000

we use the simplified form. For example m3 can also be rewritten

as

m3: TITLE 6= “Elect. Eng.” ^ SAL ≥ 30000

Distributed © M. T. Özsu & P.
Ch.3/41
Cont…
• Application Information
● minterm selectivities: sel(mi)
● The number of tuples of the relation that would be accessed by a user
query which is specified according to a given minterm predicate mi.
● We denote the selectivity of a minterm m as sel(m ). i i

● Access frequencies: acc(qi)

● The frequency with which a user application qi accesses data.
● Access frequency for a minterm predicate can also be defined.
- If Q = {q1,q2…..qq} is a set of user queries, acc(q ) indicates the access
i

frequency of query q in a given period.

i

- minterm access frequencies can be determined from the query

frequencies.
- We refer to the access frequency of a minterm m as acc(m ). i i

Distributed © M. T. Özsu & P.

Ch.3/42
Primary Horizontal Fragmentation
• Definition: A primary horizontal fragmentation is defined by a
selection operation on the owner relations of a database schema.
Ri = σFi(R), 1 ≤ j ≤ w
where Fi is a selection formula used to obtain fragment Ri , which is
(preferably) a minterm predicate(mi).
Therefore,
A horizontal fragment Ri of relation R consists of all the tuples of R
which satisfy a minterm predicate mi.

Given a set of minterm predicates M, there are as many horizontal

fragments of relation R as there are minterm predicates.

Set of horizontal fragments ©also

Distributed
referred to as minterm fragments.
M. T. Özsu & P.
Ch.3/43
Cont…
•

Distributed © M. T. Özsu & P.

Ch.3/44
Cont…

Distributed © M. T. Özsu & P.

Ch.3/45
PHF – Algorithm
Given: A relation R, the set of simple predicates Pr
Output: The set of fragments of R = {R1, R2,…,Rw} which obey the
fragmentation rules.

Preliminaries :

Pr should be complete
Pr should be minimal :

Distributed © M. T. Özsu & P.

Ch.3/46
Completeness of Simple Predicates

• A set of simple predicates Pr is said to be complete if and only if

the accesses to the tuples of the minterm fragments( horizontal
fragmentation) defined on Pr requires that two tuples of the same
minterm fragment have the same probability of being accessed
by any application.

• Example :
● Assume PROJ[PNO,PNAME,BUDGET,LOC] has two applications
defined on it.
● Find the budgets of projects at each location. (1)
● Find projects with budgets less than $200000. (2)

Distributed © M. T. Özsu & P.

Ch.3/47
Cont…
According to EX(1) ie Find the budgets of projects at each location
Pr={LOC=“Montreal”,LOC=“New York”,LOC=“Paris”}
which is not complete with respect to (2).

Modify above query as

Pr ={LOC=“Montreal”,LOC=“New York”,LOC=“Paris”,
BUDGET≤200000,BUDGET>200000}
which is complete.

Distributed © M. T. Özsu & P.

Ch.3/48
Minimality of Simple Predicates

• If a predicate influences how fragmentation is performed, (i.e.,

causes a fragment f to be further fragmented into, say, fi and fj)
then there should be at least one application/query that accesses
fi and fj differently.

• In other words, the simple predicate should be relevant in

determining a fragmentation.

• If all the predicates of a set Pr are relevant, then Pr is minimal.

Distributed © M. T. Özsu & P.

Ch.3/49
Cont…
Example : Find the budgets of projects at each location
Pr ={LOC=“Montreal”,LOC=“New York”, LOC=“Paris”,
BUDGET≤200000,BUDGET>200000}

is minimal (in addition to being complete).

However, if we add PNAME = “Instrumentation”

then Pr is not minimal.

Distributed © M. T. Özsu & P.

Ch.3/50
COM_MIN Algorithm
Given: a relation R and a set of simple predicates Pr
Output: a complete and minimal set of simple predicates
Pr' for Pr

Rule 1: each fragment is accessed differently by at least

one application.

Distributed © M. T. Özsu & P.

Ch.3/51
Cont…

Distributed © M. T. Özsu & P.

Ch.3/52
COM_MIN Algorithm
❶ Initialization :
● find a pi ∈ Pr such that pi partitions R according to Rule 1
● set Pr' = pi ;
● Pr ←Pr – {pi} ;
● F ← {fi}
❷ Iteratively add predicates to Pr' until it is complete
● find a pj ∈ Pr such that pj partitions some fk defined according to
minterm predicate over Pr' according to Rule 1
● set Pr' = Pr' ∪ {pj};
● Pr ←Pr – {pj}; F ← F ∪ {fj}
● if ∃pk ∈ Pr' which is non relevant then
Pr' ← Pr'– {pi}
Distributed © M. T. Özsu & P.
Ch.3/53
Cont…
• The algorithm begins by finding a predicate that is relevant and
that partitions the input relation.

• The repeat-until loop iteratively adds predicates to this set,

ensuring
minimality at each step. Therefore, at the end the set Pr' is both
minimal and
complete.

• The second step in the primary horizontal design process is to

derive the set of minterm predicates that can be defined on the
predicates in set Pr'.

• Distributed
These minterm predicates determine
© M. T. Özsu & P. the fragments that are used
Ch.3/54
Cont…
• reducing the number of minterm predicates that need to be
considered in fragmentation.

• This reduction can be achieved by eliminating some of the

minterm fragments that may be meaningless

• This elimination is performed by identifying those minterms that

might be contradictory to a set of implications I.

Distributed © M. T. Özsu & P.

Ch.3/55
Cont…
• For example, if Pr' = {p1,p2} where
p1 : att = value 1 and p2 : att = value 2
• and the domain of att is {value 1,value 2}, it is obvious that I
contains two implications:
i1 : (att = value 1))=> ¬(att = value 2)
i2 : ¬ (att = value1))=>(att = value 2)
• The following four minterm predicates are defined according to
Pr' :
m1 : (att = value 1)^(att = value 2)
m2 : (att = value 1)^¬ (att = value 2)
m3 : ¬ (att = value 1)^(att = value 2)
m4 : ¬ (att = value 1)^¬ (att = value 2)
In this case the minterm predicates m1 and m4 are contradictory to the implications I and can therefore
beDistributed
eliminated from M. © M. T. Özsu & P.
Ch.3/56
PHORIZONTAL Algorithm
Makes use of COM_MIN to perform fragmentation.
Input: a relation R and a set of simple predicates Pr
Output: a set of minterm predicates M according to which relation
R is to be fragmented

❶ Pr' ← COM_MIN (R,Pr)

❷ determine the set M of minterm predicates
❸ determine the set I of implications among pi ∈ Pr
❹ eliminate the contradictory minterms from M

Distributed © M. T. Özsu & P.

Ch.3/57
PHF – Example
• Two candidate relations : PAY and PROJ.
• Fragmentation of relation PAY
● Application: Check the salary info and determine raise.
● Employee records kept at two sites  application run at two sites
● Simple predicates
p1 : SAL ≤ 30000
p2 : SAL > 30000
Pr = {p1,p2} which is complete and minimal Pr'=Pr
● Minterm predicates
m1 : (SAL ≤ 30000)
m2 : NOT(SAL ≤ 30000) = (SAL > 30000)

Distributed © M. T. Özsu & P.

Ch.3/58
PHF – Example

PAY1 PAY2
TITLE SAL TITLE SAL
Mech. 270 Elect. 400
Eng.
Programm 00
240 Eng.
Syst. 00
340
er 00 Anal. 00

Distributed © M. T. Özsu & P.

Ch.3/59
PHF – Example
• Fragmentation of relation PROJ
● Applications:
● Find the name and budget of projects given their no.
✓ Issued at three sites
● Access project information according to budget
✓ one site accesses ≤200000 other accesses >200000
● Simple predicates
● For application (1)
p1 : LOC = “Montreal”
p2 : LOC = “New York”
p3 : LOC = “Paris”
● For application (2)
p4 : BUDGET ≤ 200000
p5 : BUDGET > 200000
● Pr = Pr' = {p1,p2,p3,p4,p5}
Distributed © M. T. Özsu & P.
Ch.3/60
PHF – Example
• Fragmentation of relation PROJ continued
● Minterm fragments left after elimination
m1 : (LOC = “Montreal”) ∧ (BUDGET ≤ 200000)
m2 : (LOC = “Montreal”) ∧ (BUDGET > 200000)
m3 : (LOC = “New York”) ∧ (BUDGET ≤ 200000)
m4 : (LOC = “New York”) ∧ (BUDGET > 200000)
m5 : (LOC = “Paris”) ∧ (BUDGET ≤ 200000)
m6 : (LOC = “Paris”) ∧ (BUDGET > 200000)

Distributed © M. T. Özsu & P.

Ch.3/61
PHF – Example

PROJ1 PROJ2

PNO PNAME BUDGE LOC PNO PNAME BUDGE LOC

T T
Databa
P Instrumentati 1500 Montrea P 1350 New
se
1 on 00 l 2 00 York
Develo
PROJ4 PROJ6 p.

PNO PNAME BUDGE LOC PNO PNAME BUDGE LOC

T T
P CAD/CAM 2500 New P Maintenan 3100 Pari
3 00 York 4 ce 00 s

Distributed © M. T. Özsu & P.

Ch.3/62
PHF – Correctness
• Completeness
● Since Pr' is complete and minimal, the selection predicates are
complete
• Reconstruction
● If relation R is fragmented into FR = {R1,R2,…,Rr}

R = ∪∀Ri ∈FR Ri
• Disjointness
● Minterm predicates that form the basis of fragmentation should be
mutually exclusive.

Distributed © M. T. Özsu & P.

Ch.3/63
Derived Horizontal Fragmentation
• Defined on a member relation of a link according to a selection
operation specified on its owner.
● Each link is an equijoin.
● Equijoin can be implemented by means of semijoins.
SKILL
TITLE, SAL

L1
EMP PROJ
ENO, ENAME, TITLE PNO, PNAME, BUDGET, LOC

L2 L3
ASG
ENO, RESP,
PNO, DUR

Distributed © M. T. Özsu & P.

Ch.3/64
DHF – Definition
Given a link L where owner(L)=S and member(L)=R, the derived
horizontal fragments of R are defined as

Ri = R ⋉Si, 1≤i≤w
where w is the maximum number of fragments that will be defined
on R and

Si = σFi (S)
where Fi is the formula according to which the primary horizontal
fragment Si is defined.

Distributed © M. T. Özsu & P.

Ch.3/65
DHF – Example
Given link L1 where owner(L1)=SKILL and member(L1)=EMP
EMP1 = EMP ⋉ SKILL1
EMP2 = EMP ⋉ SKILL2
where
SKILL1 = σSAL≤30000(SKILL)
SKILL2 = σSAL>30000(SKILL)

EMP1 EMP2
ENO ENAME TITLE ENO ENAME TITLE

E A. Mech. E J. Elect.
3
E Lee
J. Eng.
Programm 1
E DoeM. Eng.
Syst.
4
E Miller
R. er
Mech. 2
E Smith
B. Anal.
Syst.
7 Davis Eng. 5
E Casey
L. Anal.
Elect.
6
E ChuJ. Eng.
Syst.
Distributed © M. T. Özsu & P.
8 Jones Anal.
Ch.3/66
Cont…
• To carryout a derived horizontal fragmentation , 3
inputs are needed.

• 1)the set of partitions of the owner relation,

• 2)the member relation
• 3)the set of semijoin predicates between the
owner and the member

Distributed © M. T. Özsu & P.

Ch.3/67
Cont…
• In a database schema . It is common that there are more than
two links into a relation R.

• for ex: ASG has two incoming links.

• In this case there is more than one possible derived
fragmentation of R.

• The choice of candidate fragmentation is based on two criteria:

• 1.The fragmentation with better join characteristics –

performance is more
• 2.The fragmentation used in more applications- performance is
less
Distributed © M. T. Özsu & P.
Ch.3/68
DHF – Correctness
• Completeness
● Referential integrity
● Let R be the member relation of a link whose owner is relation S
which is fragmented as FS = {S1, S2, ..., Sn}. Furthermore, let A be
the join attribute between R and S. Then, for each tuple t of R, there
should be a tuple t' of S such that
t[A] = t' [A]
• Reconstruction
Reconstruction of a global relation from its fragments is
performed by the union operator in both the primary and the
derived horizontal fragmentation.
• Disjointness
● Simple join graphs between the owner and the member fragments.
Distributed © M. T. Özsu & P.
Ch.3/69
Vertical Fragmentation
• A vertical fragmentation of a relation R produces fragments
R1,R2,…,Rr, each of which contains a subset of R’s attributes as
well as the primary key of R.

• The objective of vertical fragmentation is to partition a relation

into a set of
smaller relations so that many of the user applications will run
on only
one fragment.

• An “optimal” fragmentation is one that produces a fragmentation

scheme which minimizes the execution time of user applications
that run
on these fragments.
Distributed © M. T. Özsu & P.
Ch.3/70
cont.
•

Distributed © M. T. Özsu & P.

Ch.3/71
Cont…
• There are two approaches exist for the vertical fragmentation of
global relations
• 1. Grouping: starts by assigning each attribute to one fragment,
and at each step, joins some of the fragments until some criteria
is satisfied.

• 2. Splitting: starts with a relation and decides on beneficial

partitionings based on the access behavior of applications to the
attributes.

• We focus only on splitting technique, since it fits more naturally

within the top-down design methodology, since the “optimal”
solution is probably closer to the full relation than to a set of
fragments each of which consists of a single attribute
Distributed © M. T. Özsu & P.
Ch.3/72
Vertical Fragmentation
• splitting generates non-overlapping fragments
• whereas grouping typically results in overlapping fragments.
• We prefer non-overlapping fragments for disjointness. Of course,
non-overlapping refers only to non-primary key
Advantage:
Easier to enforce functional dependencies
(for integrity checking etc.)
• If we now design the database so that the key attributes are part
of one fragment that is allocated to one site, and the implied
attributes are
part of another fragment that is allocated to a second site, every
update request that causes an integrity check will necessitate
communication among sites.
Distributed © M. T. Özsu & P.
Ch.3/73
VF – Information Requirements
• Application Information
• vertical partitioning places the attributes in one fragment
which are usually accessed together. To measure the
togetherness of attribues we need
● Attribute affinities
● a measure that indicates how closely related the attributes are
● This is obtained from more primitive data
● Attribute usage values
- Given a set of queries Q = {q1, q2,…, qq} that will run on
the relation R[A1, A2,…, An], for each query q and each attribute
i

A , we associate an attribute usage value use(qi,Aj)

j

⎧ 1 if attribute A is referenced by
use(qi,Aj) ⎨ j
⎩ 0 query qi
= otherwise
Distributed © M. T. Özsu & P.
Ch.3/74
VF – Attribute Usage Matrix
Consider the following 4 queries for relation PROJ
q 1: SELECT BUDGET q2: SELECT PNAME,BUDGET
FROM PROJ FROM PROJ
WHERE PNO=Value
q 3: SELECT PNAME q4: SELECT SUM(BUDGET)
FROM PROJ FROM PROJ
WHERE LOC=Value WHERE LOC=Value
Let A1= PNO, A2= PNAME, A3= BUDGET, A4= LOC.
A1 A2 A3 A4
Attribute Usage matrixq 1 0 1 0
use(qi, Aj )= 1
q 0 1 1 0
q2 0 1 0 1
3
q 0 0 1 1
Distributed 4 © M. T. Özsu & P.
Ch.3/75
VF – Affinity Measure aff(Ai,Aj)
• The frequency measure can be included in the definition of the
attribute affinity measure aff (Ai,Aj ).
The attribute affinity measure between two attributes Ai and Aj of a
relation R[A1, A2, …, An] with respect to the set of applications Q =
(q1, q2, …, qq) is defined as follows :

where re fl(qk) is the number of accesses to attributes (A ,A ) for each execution of

i j

application qk at site Sl and accl(qk) is the application access frequencies at different sites.

The result of this computation is an nn matrix, each element of which is one of the measures
defined above. We call this matrix the attribute affinity matrix (AA).
Distributed © M. T. Özsu & P.
Ch.3/76
Attribute Affinity Matrix

Distributed © M. T. Özsu & P.

Ch.3/77
VF – Calculation of aff(Ai, Aj)

Assume each query in the previous example accesses the attributes

once during each execution.
Also assume the access frequencies S1 S2 S3
q1 1 2 1
q2 5 0 0
5 0 0
q3 2 2 2
q4 5 5 5
3 0 0
Then A2 A3
A1 A4
aff(A1, A3) = 15*1 + 20*1+10*1 A1 4 0 4 0
= 45 A2 50 8 55 7
and the attribute affinity matrix AA is A3 4 05 5 53
A4 50 7 33 7
5 8
Distributed © M. T. Özsu & P.
Ch.3/78
Cont…
• The attribute affinity matrix will be used to guide the
fragmentation effort.

• The process involves first clustering together the attributes with

high affinity for each other, and then splitting the relation
accordingly.

Distributed © M. T. Özsu & P.

Ch.3/79
VF – Clustering Algorithm
• The fundamental task in designing a vertical fragmentation
algorithm is to find some means of grouping the attributes of a
relation based on the attribute affinity values in AA.
• In the year 1972, It has been suggested by McCormick et al., the
Bond Energy Algorithm should be used for this purpose
• Reasons: 1. it clusters the attributes with larger affinity values
together, and the ones with smaller values together
• 2. The final groupings are insensitive to the order in which items
are presented to the algorithm
• 3.The computation time of the algorithm is reasonable: O(n2),
where n is the
number of attributes.
• 4.Secondary interrelationships between clustered attribute groups
are identifiable.
Distributed © M. T. Özsu & P.
Ch.3/80
Cont…

• Take the attribute affinity matrix AA and reorganize the attribute

orders to form clusters where the attributes in each cluster
demonstrate high affinity to one another.
• Bond Energy Algorithm (BEA) has been used for clustering of
entities. BEA finds an ordering of entities (in our case attributes)
such that the global affinity measure is maximized.

AM
=
∑∑ (affinity of Ai and Aj with their
i j neighbors)

Distributed © M. T. Özsu & P.

Ch.3/81
Bond Energy Algorithm
Input: The AA matrix(Attribute Affinity matrix)
Output: The clustered affinity matrix CA which is a permutation
of AA

❶ Initialization: Place and fix one of the columns of AA in CA.

❷ Iteration: Place the remaining n-i columns in the remaining i+1

positions in the CA matrix. For each column, choose the
placement that makes the most contribution to the global affinity
measure.

❸ Row order: Order the rows according to the column ordering.

Distributed © M. T. Özsu & P.

Ch.3/82
Cont…

Distributed © M. T. Özsu & P.

Ch.3/83
Cont…

Distributed © M. T. Özsu & P.

Ch.3/84
Cont…

Distributed © M. T. Özsu & P.

Ch.3/85
Bond Energy Algorithm
“Best” placement? Define contribution of a placement:

cont(Ai, Ak, Aj) = 2bond(Ai, Ak)+2bond(Ak, Aj) –2bond(Ai, Aj)

where

n
bond(Ax,Ay) aff(Az,Ax)aff(Az,
= z Ay)
∑ =1

Distributed © M. T. Özsu & P.

Ch.3/86
Cont…

cont(A1,A4,A2) =2∗135+2∗11865−2∗225 =23550

Distributed © M. T. Özsu & P.
Ch.3/87
Cont…
• We consider the clustering of the PROJ relation attributes
and use the attribute affinity matrix AA of Figure 3.16.
• According to the initialization step, we copy columns 1
and 2 of the AA matrix to theCA matrix (Figure 3.17a)
and start with column 3 (i.e., attribute A3).
• There are three alternative places where column 3 can be
placed: to the left of column 1, resulting in the ordering
(3-1-2), in between columns 1 and 2, giving (1-3-2), and
to the right of 2, resulting in (1-2-3). Note that to
compute the contribution of the last ordering we have to
compute cont(A2,A3,A4) rather than cont(A1,A2,A3).
Furthermore, in this context A4 refers to the fourth index
position in the CA matrix, which is empty (Figure 3.17b),
not to the attribute column A4 of the AA matrix. Let us
calculate the contribution to the global affinity measure
Distributed © M. T. Özsu & P.
Ch.3/88
Cont…

Ordering (0-3-1) : 2bond(A0 , A3)+2bond(A3 , A1)–2bond(A0 ,

A1)
= 2* 0 + 2* 4410 – 2*0 = 8820
Thus cont(A0,A3,A1)=8820

Distributed © M. T. Özsu & P.

Ch.3/89
Cont…

Distributed © M. T. Özsu & P.

Ch.3/90
Cont…

Thus cont(A2,A3,A4)=1780

Distributed © M. T. Özsu & P.

Ch.3/91
Cont…
• Since the contribution of the ordering (1-3-2) is the
largest, we select to place A3 to the right of A1 .
• Similar calculations for A4 indicate that it should be
placed to the right of A2
• the rows are organized in the same order as the columns
and the result is shown in fig(d)
• we see the creation of two clusters: one is in the upper
left corner and contains the smaller affinity values and
the other is in the lower right corner and contains the
larger affinity values. This clustering indicates how the
attributes of relation PROJ should be split.

Distributed © M. T. Özsu & P.

Ch.3/92
BEA – Example
Consider the following AA matrix and the corresponding CA matrix
where A1 and A2 have been placed. Place A3:

Ordering (0-3-1) :
cont(A0,A3,A1) = 2bond(A0 , A3)+2bond(A3 , A1)–2bond(A0 , A1)
= 2* 0 + 2* 4410 – 2*0 = 8820
Ordering (1-3-2) :
cont(A1,A3,A2) = 2bond(A1 , A3)+2bond(A3 , A2)–2bond(A1,A2)
= 2* 4410 + 2* 890 – 2*225 = 10150
Ordering (2-3-4) :
cont (A2,A3,A4) = 1780
Distributed © M. T. Özsu & P.
Ch.3/93
BEA – Example
• Therefore, the CA matrix has the form A1 A3 A2

4 4
5 5 0
8
0 5 0
4 5
5 3 5
7
0 3 5
• When A is placed, the final form of the CA matrix (after row
4

organization) is A1 A3 A2 A4
A1 4 4
5 5 0 0
A3 4 5
5 3 5 3
A2 8 7
0 5 0 5
A4 7 7
Distributed © M. T. Özsu & P.
0 3 5 8
Ch.3/94
VF – Partitioning ALgorithm
• The objective of the splitting activity is to find sets
of attributes that are accessed solely, or for the
most part, by distinct sets of applications.
• For example, if it is possible to identify two
attributes,A1 andA2,which are accessed only by
application q1, and attributes A3 and A4, which are
accessed by, say, two applications q2 and q3, it
would be quite straightforward to decide on the
fragments.
• The task lies in finding an algorithmic method of
identifying these groups.
Distributed © M. T. Özsu & P.
Ch.3/95
Cont…
How can you divide a set of clustered attributes {A1, A2,
…, An} into two (or more) sets {A1, A2, …, Ai} and {Ai, …,
An} such that there are no (or minimal) applications that
access both (or more than one) of the sets.

A1 A2 A3 … Ai Ai+1 . .Am
A1 .
A2
TA
..
.

Ai

Ai+1
BA
..
.

Am

Distributed © M. T. Özsu & P.

Ch.3/96
Cont…
• Consider the clustered attribute matrix of Figure3.18. If a
point along the diagonal is fixed, two sets of attributes
are identified.
• One set{A1,A2,...,Ai}is at the upper left-hand corner and
the second set{Ai+1,...,An}is to the right and to the
bottom of this point.
• We call the former set top and the latter set bottom and
denote the attribute sets as TA and BA, respectively.
• We now turn to the set of applications Q ={q1,q2,...,qq}
and define the set of applications that access only TA,
only BA, or both. These sets are defined as follows:

Distributed © M. T. Özsu & P.

Ch.3/97
Cont…
Define
TQ = set of applications that access only TA
BQ = set of applications that access only BA
OQ = set of applications that access both TA and BA
and
CTQ = total number of accesses to attributes by applications
that access only TA
CBQ = total number of accesses to attributes by applications
that access only BA
COQ = total number of accesses to attributes by applications
that access both TA and BA
Then find the point along the diagonal that maximizes

CTQ*CBQ−CO
Q2

Distributed © M. T. Özsu & P.

Ch.3/98
Cont…

Distributed © M. T. Özsu & P.

Ch.3/99
Cont…

Distributed © M. T. Özsu & P.

Ch.3/100
Cont…

Distributed © M. T. Özsu & P.

Ch.3/101
Cont…

Distributed © M. T. Özsu & P.

Ch.3/102
Cont…
Two problems :
● Cluster forming in the middle of the CA matrix
● Shift a row up and a column left and apply the algorithm to find the
“best” partitioning point
● Do this for all possible shifts
● Cost O(m2)
● More than two clusters
● m-way partitioning
● try 1, 2, …, m–1 split points along diagonal and try to find the best
point for each of these
● Cost O(2m)

Distributed © M. T. Özsu & P.

Ch.3/103
VF – Correctness
A relation R, defined over attribute set A and key K, generates the
vertical partitioning FR = {R1, R2, …, Rr}.
• Completeness
● The following should be true for A:
A= ∪ ARi
• Reconstruction
● Reconstruction can be achieved by

R= ⋈K Ri, ∀Ri ∈ FR

• Disjointness
● TID's are not considered to be overlapping since they are
maintained by the system
● Duplicated keys are not considered to be overlapping
Distributed © M. T. Özsu & P.
Ch.3/104
Hybrid Fragmentation
R
HF HF

R1 R2
VF VF VF VF VF

R1 R12 R21 R22 R23

1

Distributed © M. T. Özsu & P.

Ch.3/105
 Fragment Allocation
• Problem Statement
Given
F = {F1, F2, …, Fn} fragments
S ={S1, S2, …, Sm} network sites
Q = {q1, q2,…, qq} applications
Find the "optimal" distribution of F to S.
• Optimality
● Minimal cost
● Communication + storage + processing (read & update)
● Cost in terms of time (usually)
● Performance
Response time and/or throughput
● Constraints
● Per site constraints (storage & processing)

Distributed © M. T. Özsu & P.

Ch.3/106
Cont…
• We make a number of assumptions and definitions that will
enable us to model the allocation problem.
• 1. Assume that Q can be modified so that it is possible to identify
the update and the retrieval-only queries, and to define the
following for a single fragment Fk:
• T = {t1, t2,………, tm}
where ti is the read-only traffic generated at site Si for Fk, and
• U = {u1,u2,………,um}
where ui is the update traffic generated at site Si for Fk.
• 2. Assume that the communication cost between any two pair of
sites Si and Sj is fixed for a unit of transmission. Furthermore,
assume that it is different for updates and retrievals in order that
the following can be defined:
Distributed © M. T. Özsu & P.
Ch.3/107
Cont…

Distributed © M. T. Özsu & P.

Ch.3/108
Cont…
• The second term of the objective function calculates the total cost
of storing all
• the The second term of the objective function calculates the total
cost of storing all
• the duThe second term of the objective function calculates the
total cost of storing all
• the duplicate copies of the fragment.licate copies of the
fragment.opies of the fragment.

Distributed © M. T. Özsu & P.

Ch.3/109
Cont…
• The second term of the objective function calculates the total cost
of storing all the duplicate copies of the fragment.

• The first term, on the other hand, corresponds to the cost of

transmitting the updates to all the sites that hold the replicas of
the fragment, and to the cost of executing the retrieval-only
requests at the site, which will result in minimal data transmission
cost.

Distributed © M. T. Özsu & P.

Ch.3/110
Cont…
• There are a number of reasons why simplistic formulations such
as the one we have discussed are not suitable for distributed
database design.

• 1. One cannot treat fragments as individual files that can be

allocated one at a time, in isolation.

• 2. The access to data by applications is modeled very simply.

• 3. These models do not take into consideration the cost of
integrity enforcement, yet locating two fragments involved in the
same integrity constraint at two different sites can be costly.
• 4. Similarly, the cost of enforcing concurrency control
mechanisms should be considered
Distributed © M. T. Özsu & P.
Ch.3/111
Information Requirements
• Database information
● selectivity of fragments
● size of a fragment
• Application information
● access types and numbers
● access localities
• Communication network information
● unit cost of storing data at a site
● unit cost of processing at a site
• Computer system information
● bandwidth
● latency
● communication overhead

Distributed © M. T. Özsu & P.

Ch.3/112
Database information

Distributed © M. T. Özsu & P.

Ch.3/113
Application information

Distributed © M. T. Özsu & P.

Ch.3/114
Allocation
File Allocation (FAP) vs Database Allocation (DAP):
● Fragments are not individual files
● relationships have to be maintained
● Access to databases is more complicated
● remote file access model not applicable
● relationship between allocation and query processing
● Cost of integrity enforcement should be considered
● Cost of concurrency control should be considered

Distributed © M. T. Özsu & P.

Ch.3/115
Allocation – Information
Requirements
• Database Information
● selectivity of fragments
● size of a fragment
• Application Information
● number of read accesses of a query to a fragment
● number of update accesses of query to a fragment
● A matrix indicating which queries updates which fragments
● A similar matrix for retrievals
● originating site of each query
• Site Information
● unit cost of storing data at a site
● unit cost of processing at a site
• Network Information
● communication cost/frame between two sites
● frame size

Distributed © M. T. Özsu & P.

Ch.3/116
Allocation Model
General Form
min(Total Cost)
subject to
response time constraint
storage constraint
processing constraint

Decision Variable

1 if fragment Fi is stored at
xij
0 site Sj
=
otherwise
Distributed © M. T. Özsu & P.
Ch.3/117
Allocation Model
• Total Cost

∑ query processing
cost +
all
queries
∑ ∑ cost of storing a fragment at
a site
all all
• Storage Costsites fragments
(of fragment Fj at Sk)

(unit storage cost at Sk) * (size of Fj)

* xone
• Query Processing Cost (for jk query)
processing component + transmission component

Distributed © M. T. Özsu & P.

Ch.3/118
Allocation Model
• Query Processing Cost
Processing component
access cost + integrity enforcement cost + concurrency control cost
● Access cost
∑ ∑ (no. of update accesses+ no. of read
all all accesses) *
sites fragments xij * local processing cost at
a site

● Integrity enforcement and concurrency control costs

● Can be similarly calculated

Distributed © M. T. Özsu & P.

Ch.3/119
Allocation Model
• Query Processing Cost
Transmission component
cost of processing updates + cost of processing retrievals
● Cost of updates

∑ ∑ update message
cost +
all all
sites ∑
fragments ∑ acknowledgment
cost
all all
sites fragments
● Retrieval Cost

∑ mi
n
all
sites
(cost of retrieval
command +
all cost of sending back the
fragments result)

Distributed © M. T. Özsu & P.

Ch.3/120
Allocation Model
• Constraints
● Response Time
execution time of query ≤ max. allowable response time for that query

● Storage Constraint (for a site)

∑ storage requirement of a fragment at that
storage site ≤ at that
capacity
all
fragments site

● Processing constraint (for a site)

∑ processing load of a query at that

site ≤ capacity of that
all processing
queries site
Distributed © M. T. Özsu & P.
Ch.3/121
Allocation Model
• Solution Methods
● FAP is NP-complete
● DAP also NP-complete
• Heuristics based on
● single commodity warehouse location (for FAP)
● knapsack problem
● branch and bound techniques
● network flow

Distributed © M. T. Özsu & P.

Ch.3/122
Allocation Model
• Attempts to reduce the solution space
● assume all candidate partitionings known; select the “best”
partitioning

● ignore replication at first

● sliding window on fragments

Distributed © M. T. Özsu & P.

Ch.3/123