TRANSPARENCY

DISTRIBUTION
38 LEVELS OF

defined by applications. The problem of determining,

in
evaluating.
access strategies
between different access strategies
is dealt with Chapters and 6.
5
and choosing application can be
written in many
However, we will show
that the same
can affect the
diferent
the way in which an application is written possible
ways, and that
access strategies.
applications. It shows, first with a
very simel.
Section 3.3 deals with read-only distributis
complex one, the different levels of
application and then with a more 3.3 on undat
3.4 performs the same analysis as Section
transparency. Section access the
Both the above sections are based on applications which
applications.
updating just a single tuple; in this
way We
database for retrieving or probleme
distributed concerned with the
without being
transparency
can discuss distribution Section 3.5 we deal with the latter problem, and
of accessing sets of tuples. In applicstion
highest level of distribution transparency the
show that even at the the DDBM8
power of the primitives which are issued to
programmer can control the and their enforcement in
distributed
integrity constraints
Section 3.6 deals with
databases.

Global
schema

Site
Fragmentation independent
schema schemas

Allocation
schema

(Other sites)

Local Local
mapping
mapping schema 2
schema|

DBMS of
DBMS Of
site 2
site 1

Local
Local database
database
at site 2
at site I
databases.
distributed
architecture for
reference
Flgure 3.1 A
 |3.1) REFERENCE ARCHITECTURE FOR D1STRIBUTED DATABASES 89

3.1 REFERENCE ARCHITECTURE FOR DISTRIBUTED

DATABASES

Figure 3.1 shows a reference architecture for a disributed database. Thisrefefenee

architecture is not explicitly implemented in all distributed databases; however,
its levels are conceptually relevant in order to upderstand the organization of ghy
distributed databaSe. We will therefore analyze and understand athe components
of this reference architecture.
At the top level of Figure 3.1 is the global shemna. The global scherma defines
All the data which are contained in the distributel database as if the database were
not distributed at all. For this reason, the globa schema can be defined exactly in
the same way as in a nondistributed database. However, the data model which is
used for the definition of a global schema shoud be convenient for the definition
of the mapping to the other levels of the distr buted database. We will use the
relational model for this purpose. Using this mdel, the global schema consists of
the definition of a set of global relations.
Each global relation can be split into sevfl nonoverlapping portions which
are called fragments. There are several diffdeht ways in which to perform the
splitting ,eration; theyg deseribed in theest section. The mapping between
glohal relations and fragments is defined in he fragmentation schema. This
mapping is one to many; i.e., several fragmehts cprrespond to one global relation,
but only one global relation corresponds to pn fragment. Fragments are indicated
by aglobal relation name with an index (rderen index); for example, R, indicates
the ith fragnent of global relation R.
Fragments are logical portions of glohal telains which are physically located
at one or several sites of the network. The allochtion schema defines at which
site{s) afragnent is located. Note that the type omapping defined in the allocation
scherna determines whether the distributed dataþase is redundant or nonredun
dant: in the former case the mapping is one to mDy, while in the latter case the
napping is one to one. All the fragments whiçh correspond to the same global
relation R and are located at the same site j donstitute the physical image of
global relation R at site j. There is therefore Aone to one mapping between a
physical image and &pair (global relation, site physical images can be indicated
by a global relation name and a site index. To distinguish them from fragments,
we will use a superscript; for example, R indicaes the physical image of the globa
relation R at site j.
An example of the relationship between the pbject types defined above is shown
in Figure 3.2. A global relation R is split into four fragments Ri, R2, R3, and R4.
These four fragments are allocated redundant|y at the three sites of a computer
network, thus building three physical images R', R, and R.
To complete the terminology, we will refer to a copy of a fragment at a given
site, and denote it using the global relation narhe and two indexes (a fragment index
And a site index). For example, in Figure 3.2 the notation R} indicates the copy
of fragment Ra which is located at site 3.
Finally, note that two physical images dan be identical. In this case we will
 40 LEVELS OF DISTRIBUTIONTRANSPARENCY

(R)
p' (site 1)
R

(R})

R,
(R})
R (site 2)

R,
(R{)

RA

(R}) R (site 3)

(R})

(R})
Global relation Fragments Physical images
Figure 3.2 Fragments and physical images for a global relation.

say that a physical image is a copy of another physical image. For example,
Figure 3.2, R' is a copy of R'. in
Let us now go back to the reference architecture of Figure
3.1. We have
already deseribed the relationships between the objects at the three top
architecture. These three levels are site independent; therefore, they do levels of this
not depend
on the data model of the local DBMSS. At a lower
level, it is necessary to map
the physical images to the objects which are manipulated by
This mapping is called a local mapping schema and the local DBS.
local DBMS; therefore in a heterogeneous system we depends on the type a
mappings at different sites. have different types of loca
This architecture provides a very general conceptual framework
ing distributed databases. The three most inportant for understand
features of this architecture are the separation of data objectives which motivale
the control of redundancy, and the independence fragmentation and allocauo
from local DBMSs.
1. Separating the concept of data fragmentation from
location. This separation allows us só distirguish twothedifferent
conceptlevels
ol daa
of dis-
tribution transparency, namely fragmentation transparency and loca-
tion transpareney. Fragmentation transparency is
the highest de5
 (3.2] TYPES OF DATA FRAGMENTATION 41

transparency and consists of the fact that theuser or application program

mer works on global relations. Location transparency is a lower degree of
transpareney and requires the user or applieation programmer to work on
fragments instad of global relations; however, he or she does not know where
the fragments are located. The separation between the concept of fragmernta
tion and allocation is very convenient in distributed database design, because
the determination of relevant portions of the data is thus distinguished from
the problem of optimal allocation, as willbe shown in the next chapter.
2 Explicit control of redundancy. The reference architecture provides explicit
control of redundancy at the frag1ment level. For example, in Figure 3.2 the
two physical images R and R' are overlapping; i.e., they contain common
data. The definition of disjoint fragments as building blÍcks of physical images
allowsus to refer explicitly to this overlapping part: the replicated fragment
Rg. As we shall see, the explicit control over redundancy is useful in several
aspects of distributed database management.
3 Independence from local DBMSs. This feature, called local mapping trans
parency, allows us to study several problems of distributed database manage
ment without having to take into account the specific data models of lo
cal DBMSs. Clearly, in a homogeneous system it is possible that the site
independent schemata are defined using the same data model as the local
DBMSs, thus reducing the complexity of this mapping.
Another type of transparency which is strictly related to location transparency
is replication transparency. Replication transparency means that the user is
unaware of the replication of fragments. Clearly, replication transparency is implied
by location transparency; however, in certain cases it is possible that the user has
no tocation transparency but has replication transparency (thus, he or she uses one
particular copy, and the system makes appropriate..actions. onthe othercopies).
In this book, we do not further distinguish replication transparency from location
transparency.
As a final remark on the reference architecture, we can say that it performs
the sane function as the ANSI/SPARCarchitecture in traditional DBMSS: it is
not necessarily implemented by the existing systerns, but it shows which levels and
schemata are conceptually relevant.

3.2 TYPES OF DATA FRAGMENTATION

The decomposition of global relations into fragments can be performed by applying

two different types of fragmentation: horizontal fragmentation and vertical
fragmentation. We willârst consider these two types o fragmentation separately
and then consider the more complex fragmentation which can be obtained by
applying a composition of both.
In all types of fragmentation, a fragment can be defined by an expression in
a relational language (we willuse relational algebra) which takes global relations
 42 LEVELS OF DISTRIBUTION TRANSPARENCY

as operands and produces the fragment as result. For example, if a global .

tion contains data about employees, a fragment which econtains only data
employees who work at department D, can be obviously defined by a selecabout
operation on the globaB relation.
There are, howev¿r, some rules which must be followed when defining froc
ments:

Completeness condition All the data of the global relation must be man.
ped ihto the fragments; i.e., it must not happen that a data item which belongs to
a global,relation does not belong to any fragment.
Reconstruction condition It must always be possible to reconstruct each
global relation from its fragments. The necessity of this condition is obvious: in
fact, only fragments are stored in the distributed database, and global relation
have to be built through this reconstruction operation if necessary.
Disjointness condition As we have discussed in the previous section, it
is convenient that fragments be disjoint, so that the replieation of data can be
controlled explicitly at the allocation level. However, this condition is useful mainly
with horizontal fragmentation, while for vertical fragmentation we will sometimes
allow this condition to be violated. The reason for this exception willbe discussed
when dealing with vertical fragmentation.
We can now consider the fragmentation rules.

3.2.1 Horizontal Fragmentation

Horizontal fragmentation consists of partitioning the tuples of a global relation into
subsets; this is clearly useful in distributed databases, where each subset can contain
data which have common geographical properties. It can be defined by expressing
each fragment as a selection operation on the global relation. For example, let a
global relation be
SUPPLIER(SNUM, NAME, CITY)
Then the horizontal fragmentation can be defined in the following way:
SUPPLIER, SLcrrY=«SpSUPPLIER

SUPPLIER, = SLcITY="LA"SUPPLIER
The above fragmentation satisfies the completeness condition if SF" and "LA" are
the only possible values of the CITY attribute; otherwise we would not know to
which fragnent the tuples with other CITY values belong.
The reconstruction condition is easily verified, because it is always possible to
reconstruct the SUPPLIER global relation through the following operation:
SUPPLIER SUPPLIER, UN SUPPLIER2

The disjointness condition is clearly verified.

We will call the predicate which is used in the selection operation which defines
a fragment its qualiication. For instance, in the above example the qualifications
are:
 [3.2) TYPES OF DATA FRAGMENTATION 48

q1 : CITY = "SF"
2: CITY LA"
We can generalize from the above example that in order to satisfy the completeness
condition, the set of qualifications of all fragments must be complete, at least
with respect to the set of allowed values. The reconstruction condition is always
satisfied through the union operation, and the disjointness condition requires that
qualifications be mutually exelusive.

(3.2.2 Derived Horizontal Fragmentation

In some cases, the horizontal fragmentation of a relation cannot be based on a
property of its own attributes, but is derived from the horizontal fragmentation of
another relation. Consider, for example, a global relation

SUPPLY(SNUM, PNUM, DEPTNUM, QUAN)

where SNUM is a supplier number. It is meaningful to partition this relation so
that a fragment contains the tuples for suppliers which are in a given city. However,
city is not an attribute of the SUPPLY relation, it is an attribute of the SUPPLIER
relation considered in the above example. Therefore we need a semi-join operation
in order to determine the tuples of SUPPLY which correspond to the suppliers in
a given city. The derived fragmentation of SUPPLY can be therefore defined as
follows:
SUPPLY SUPPLYSJSNUM=SNUM SUPPLIER,
SUPPLY, = SUPPLY SJSNUM=SNUM SUPPLIER?
The effect of the semi-join operations is to select from SUPPLY the tuples which
satisfy the join condition between SUPPLIER, or SUPPLIER, and SUPPLY, thus
determining those tuples of SUPPLY which refer to suppliers in San Francisco or
Los Angeles, respectively.
The reconstruction of the global relation SUPPLY can be performed through
the union operation as was shown for SUPPLIER.
When a global relation R has a derived fragmentation, the qualifications of its
fragments cannot be expressed as predieates which use attributes from R; rather,
the condition for a tuple t to belong to a given fragment R, of R is the existence,
in some other fragment S; of S, of atuple esuch that t and satisfy the semi-join
specification of the derived fragmentation. Considering the above example, we give
a simple representation of this condition (which should in fact include an existential
quantifier) as follows:
91 : [Link] [Link] AND SUPPLIER. CITY = "SF"
q2 :[Link] = [Link] AND [Link] = "LA"
The meaning of the above qualifications is to state, for any tuple of SUPPLY,
(SUPPLY), the existence of a supplier from San Francisco (Los Angeles) with the
same supplier number.
 44 LEVELS OF DISTRIBUTION TRANSPARENCY

The completeness of the albove fragmentation requires that there be no supDlies

numbers in the SUPPLY relation which are not contained also in the SUPPLIED
relation. This is a typical., and reasonable, integrity constraint for this databas
and usually is called the referential integrity constraint.
The disjointness condition is satisfied if a tuple of the SUPPLY relation does not
correspond to two tuples of the SUPPLIER relation which belong to two different
fragments. In this case this condition is easily verified, because the supplier numbers
are unique keys of the SUPPLIER relation; however, in general it can be difficult
to prove that this condition holds.

3.2.3 Vertical Fragmentation

The vertical fragmentation of a global relation is the subdivision of its attributes
into groups; fragments are obtained by projecting the global relation over each
group. This can be useful in distributed databases where each group of attributes
can contain data which have common geographical properties. The fragmentation
is correct if each attribute is mapped into at least one attribute of the fragments;
moreover, it must be possible to reconstruct the original relation by joining the
fragments together. Consider, for example, a global relation
EMP(EMPNUM, NAME, SAL, TAX, MGRNUM, DEPTNUM)
A vertical fragmentation of this relation can be defined as
EMP =PJsMPNUM, NAME, MGRNUM, DEPTNUM BIMP
EMP2 PJEMPNUM, SAL, TAX EMP
This fragmentation could, for instance, reflect an organization in which salaries and
taxes are managed separately. The reconstruction of relation EMP can be obtained
as

EMP = EMP; JNEMPNUM= EMPNUM EMP2

because EMPNUM is a key of EMP. Ingeneral, the inclusion of a key of the global
relation into each fragment is the most straightforward way tw guarantee that the
reconstruction through a join operation is possible. An alternatiye way to provide
the reconstruction property is to generate tuple identifiers which are used 2s
system-controlled keys. This can be convenientin order to avoid the replication o
large keys; moreover, tuple identifiers cannot be modified by users,
Notice that the above formula for the reconstruction of the global relation EMP
is not complete, because the result of joining EMP, and EMP2 contains the column
EMPNUM twice. This undesired replication can be eliminated by a projection
operation that we omit to indjcate.
Let us finally consider the problem of fragment disjointness. First, we
seen that at least the key should be replicated in all fragments in order to
reconstruction. In general, we can sav that in vertical fragmentation the mi
motivation for having disjoint fragments (i.e., tocontrol replication) isnot as im
portant as in horizontal fragmentation. In fact, if we include the Same attribute in
 (3.2] TYPES OF DATA FRAGMENTATION 46
two different vertical fragments, we know exactly that the replicated data is con
stituted by the column which corresponds to this attribute; if instead we allow two
horizontal fragments to overlap, by permitting nonmutually exclusive qualifications,
then we cannot refer directly to the overlapping portion.
For example,consider the following vertical fragmentation of relation EMP.
EMP, = PJEMPNUM, NA ME, MGRNUM, DEP TNUM EMP

EMP» PJEMPNUM, NA ME, SAL, TAX EMP

The attribute NAME is replicated in both fragments. We can explicitly elininate
this attribute when we reconstruct relation EMP through an additional projection
operation:

EMP = EMP,JNEMPNUM= EMPNUM PJEMPNUM, SAL, TA XEMP2

3.2.4 Mixed Fragmentation

The fragments which are obtained by the above fragmentation operations are
relations themselves, so that it is possible to apply the fragmentation operations
recursively, provided that the correctness conditions are satisfied each time. The
reconstruction can be obtained by applying the reconstruction rules in inverse order.
The expressions which define fragments are more complex in this case; consider,
for example, the same global relation
EMP EMPNUM, NAME, SAL, TAX, MGRNUM, DEPTNUM)

The following is a mixed fragmentation which obtained by applying the vertical

fragmentation of the previous example, followed by a horizontal fragmentation on
DEPTNUM:
EMP; = SLpEPTNUM<10PJ EMPNUM,NA ME, MGRNUM, DEPTNUM EMP
EMP2 = SLj0 DEPTNUM< 20PJ EMPNUM, NA ME, MGRNUM,DEPTNUM EMP
EMP3 = SLpEPTNUM> 20PJ EMPNUM, NA ME, MGRNUM, DEPTNUM EbMP
EMP4 =PJEMPNUM, NAME,SAL, TAX EMP

EMP

EMP,

EMP, EMP, EMP,

Figure 3.3 The fragmentation tree of relation EMP
46 LEVELS OF DISTRIBUTION TRA NSPARENCY

The reconstruction of relat ion EMP is defined by the following expression:

EMP =UN (EMP.EMP2, EMP:)JN BMPNUM-EMPNUM

PJEMPUM,SA L, TAX EMP4

Mixed fragment ation can be conveniently represented by a fragmentation

tree. In a fragmentat ion tree, the root corresponds to aglobal relation, the
leaves correspond to the fragments, and the intermediate nodes correspond te
the intermediate results of the fragment-defining expressions. The set of nodes
which are sons of a given node represent the decomposition of this node by
fragmentation operation (vertical or horizontal). For example, Figure 3.3 shoWA
the fragmentation tree of relation EMP. The root (relation EMP) is vertically
fragmented into two portions: one portion corresponds to a leaf node of the tree
(EMP,): the other portion is horizontally partitioned, thus generating the other
three leaves, corresponding to fragments EMPi, EMP2, and EMP3.
The EXAMPLE_DDB
Figure 3.4shows the global and fragmentation schemata of EXAMPLE_DDB which
will be used in the rest of this book for the development of examples. Most of the
global relations of EXAMPLE_DDB and their fragmentation have been already in
troduced. A DEPT relation, horizontally fragmented into three fragments on the
value of the DEPTNUM attribute, is added. The features of EXAMPLE_ DDB
will be discussed when they will be used to exemplify specific topics. Note, as a

Global schem8

EMP(EMPNUM, NAME, SAL, TAX, MGRNUM, DEPTNUM)

DEPTDEPTNUM, NAME, AREA, MGRNUM)
SUPPLIER(SNUM, NAME, CITY)
SUPPLY(SNUM, PNUM, DEPTNUM, QUAN)
Fragmentation schema
EMP; = SLpEpTNUM<10J EMPNUM, NA ME, MGRNUM, DEPTNUMEMP)
EMP2 = SLË0< DEPTNUM<20PJEMPNUM, NAME, MGRNUM, DEPTNUM(BMP)
EMP3 SLpEpTNUM> 20PJ EMPNUM, NA ME, MGRNUM, DEPTNUMMP)
EMP4 = PJEMPNUM, NAME, SAL, TA X(EMP)
DEPT; SLDEPTNUM< 10(DEPT)
DEPT; = SLj0< DEPTNUM< 20(DEPT)
DEPT3 =8LDEpTNUM> 2o(DEPT)
SUPPLIER, = 8LcrY=4gp (SUPPLIER)
SUPPLIER; = SLcTYLA"(SUPPLIER)
SUPPLY; = SUPPLY 8J gNUM=SNUMSUPPLIER;
SUPPLY2 = SUPPLY SJ SNUM=SNUMSUPPLIER:

Flgure 3.4 The global and fragmentetion schemata of EXAMPLE_DDB.