CSE 4125: Distributed Database
Systems
Chapter – 3
Levels of Distributed Transparency
Rajon|AUST 1
Reference Architecture for DDB
• Represents the organization of any DDB.
• Not explicitly implemented in all DDBs.
–But conceptually relevant in order to
understand the working mechanism of DDB.
Rajon|AUST 2
Rajon|AUST 3
Components:
[Link] Schema.
[Link] Schema.
[Link] Schema.
[Link] Mapping Schema.
Rajon|AUST 4
Global Schema
Global schema defines all the data which are
contained in the distributed database.
–Conceptual view* of the database.
–As if the database were not distributed at all.
Global schema defines a set of global relations
Rajon|AUST 5
Fragmentation Schema
Each global relation (R) can be split into several non-
overlapping portions which are called fragments.
–Logical portions of R.
Example –
R can be partitioned into R1 ,R2 and R3
Rajon|AUST 6
The mapping between global relations and
fragments is defined in the fragmentation
schema.
Ri indicates i th fragment of global
relation R.
Rajon|AUST 7
Allocation Schema
Allocation schema defines at which site(s) a fragment is
located.
Rajon|AUST 8
Fragments from R creates physical image (R j) of R at
site j.
Rajon|AUST 9
Local Mapping Schema
Mapping physical images to database objects which
are manipulated by local DBMS.
Depends on the types of the local DBMS.
–Example: if local DBMS is Oracle, the physical
images must be mapped so that Oracle can
understand
Rajon|AUST 10
Advantage of Fragmentation
Usage:
–In general, applications work with views (subset of
relation) rather than entire relations.
–In data distribution, it seems appropriate to work with
subsets of relation as the unit of distribution.
Efficiency:
–Data is stored close to where it is most frequently used.
In addition, data that is not needed by local
applications is not stored.
Rajon|AUST 11
Parallelism:
–A transaction can be divided into several sub queries that
operate on fragments. This should increase the degree of
concurrency by allowing transactions to execute in parallel.
Security:
–Data not required by local applications is not stored, and
consequently not available to unauthorized users.
Rajon|AUST 12
Disadvantage of Fragmentation
Performance:
–The performance of global application that requires data
from several fragments located at different sites may be
slower.
Integrity:
–Integrity control may be more difficult if data and functional
dependencies are fragmented and located at different sites.
Rajon|AUST 13
Distribution Transparency
The property of DDB by which the internal
details of the distribution are hidden from the
users (i.e. application programmer).
–A transparent system “hides” the implementation details
from users.
–The advantage of a fully transparent DDB is the high
level of support that it provides for the development of
complex applications.
Rajon|AUST 14
Levels of Distribution Transparency:
–Levels at which an application programmer view
the DDB, depending on how much distribution
transparency is provided by the DDBMS.
Important levels are –
i. Level-1: Fragmentation transparency.
ii. Level-2: Location transparency.
iii. Level-3: Local mapping transparency.
Rajon|AUST 15
Level-1: Fragmentation Transparency:
–Programmer works on global relation.
–Fragmentation information is hidden.
Enables Programmer to query upon any relation as if it
were not fragmented.
Rajon|AUST 16
Level-2: Location Transparency:
- Fragmentation information is provided. Programmer works
on fragments.
–Location (i.e. site name) information is hidden.
Enables Programmer to query upon fragments as if they
were stored locally in the user’s site.
Rajon|AUST 17
Level-3: Local Mapping Transparency:
–Location information is provided. Programmer works on
fragmentation at specific location (site).
–Local DBMS information is hidden.
Enables Programmer to query upon fragments at a site as if the
local DBMS is “known” (i.e. Oracle or MySQL) .
Rajon|AUST 18
Who Should Provide Transparency?
Three layers:
User language (code).
– Compiler, interpreter.
Operating system.
– Distributed environment (Network management)
–Local DBMS.
Rajon|AUST 19
Additional Reading
Copy of a fragment.
Replication transparency.
Rajon|AUST 20
Questions
Rajon|AUST 21
Types of Fragmentation
1. Horizontal fragmentation
2. Vertical fragmentation.
3. Mixed fragmentation.
Rajon|AUST 22
Determining Fragmentation
The following information is used to decide
fragmentation:
Quantitative information:
frequency of queries, site, where query is run,
selectivity (i.e. probability of accessing) of the
queries, etc.
Qualitative information:
types of access of data, read/write, etc.
Rajon|AUST 23
Rules of Fragmentation
Completeness:
–All data in global relation must be mapped into
fragments.
–No data must be left unmapped.
Reconstruction:
–It must be possible to obtain the global relation
from its fragments.
Rajon|AUST 24
Disjointness:
–It is convenient to have disjoint (non-overlapping)
fragments.
–Not strict, can be violated.
Rajon|AUST 25
Horizontal Fragmentation
Partitioning the tuples of a global relation into
subsets.
Example: global relation:
SUPPLIER (SNUM, NAME, CITY)
Apply horizontal fragmentation based on city.
*Question: what relational algebraic operation can
be applied?
Rajon|AUST 26
Global schema:
SUPPLIER (SNUM, NAME, CITY)
Fragmentation Schema:
SUPPLIER1 = SL CITY = “DHK” SUPPLIER
SUPPLIER2 = SL CITY = “CTG” SUPPLIER
Qualification: Predicate which is used in the selection
operation that defines a fragment.
q1: CITY = “DHK”
q2: CITY = “CTG”
Rajon|AUST 27
Discuss:
⁇ Is it complete ?
⁇ How to reconstruct ?
⁇ Is it disjoint ?
Rajon|AUST 28
Discuss:
⁇ Is it complete ?
If DHK and CTG are the only possible values of the
CITY attribute.
⁇ How to reconstruct ?
SUPPLIER = SUPPLIER1 UN SUPPLIER2
⁇ Is it disjoint ?
Yes
Rajon|AUST 29
Derived Horizontal Fragmentation
In some cases, horizontal fragmentation cannot
be based on its own attributes.
Needs to be derived from the horizontal
fragmentation of another relation.
Rajon|AUST 30
Example: global relations:
SUPPLIER (SNUM, NAME, CITY)
SUPPLY (SNUM, PNUM, DEPTNUM, QUAN)
Partition SUPPLY based on a cities.
*Question: What is the relational algebraic formula
to apply this?
Rajon|AUST 31
Global relations:
SUPPLIER (SNUM, NAME, CITY)
SUPPLY (SNUM, PNUM, DEPTNUM, QUAN)
Fragmentation Schema (method-1):
Firstly,
SUPPLIER1 = SL CITY = “DHK” SUPPLIER
SUPPLIER2 = SL CITY = “CTG” SUPPLIER
Finally,
SUPPLY1 = SUPPLY SJ SNUM = SNUM SUPPLIER1
SUPPLY2 = SUPPLY SJ SNUM = SNUM SUPPLIER2
Rajon|AUST 32
Global relations:
SUPPLIER (SNUM, NAME, CITY)
SUPPLY (SNUM, PNUM, DEPTNUM, QUAN)
Fragmentation Schema (method-2):
SUPPLIER1 = SL q1 SUPPLIER
SUPPLIER2 = SL q2 SUPPLIER
Where,
q1: [Link] = [Link] and [Link] = “DHK”
q2: [Link] = [Link] and [Link] = “CTG”
Rajon|AUST 33
Discuss:
⁇ Is it complete ?
⁇ How to reconstruct ?
⁇ Is it disjoint ?
Rajon|AUST 34
Discuss:
⁇ Is it complete ?
Requires that there be no supplier number in the SUPPLY
relation which are not contained also in the SUPPLIER
relation.
⁇ How to reconstruct ?
SUPPLY = SUPPLY1 UN SUPPLY2
⁇ Is it disjoint ?
Yes (supplier numbers are unique key)
Rajon|AUST 35
Vertical Fragmentation
Partitioning the attributes of a global relation
into subsets.
Example: global relation:
EMP (EMPNUM, NAME, SAL, TAX, MGRNUM, DEPTNUM)
Apply vertical fragmentation.
*Question: what relational algebraic operation can be
applied?
Rajon|AUST 36
Global schema:
EMP (EMPNUM, NAME, SAL, TAX, MGRNUM, DEPTNUM)
Fragmentation schema:
EMP1 = PJ EMPNUM, NAME, MGRNUM, DEPTNUM EMP
EMP2 = PJ SAL, TAX EMP
*Question: do you think the fragmentation is
acceptable?
Rajon|AUST 37
NO
Global schema:
EMP (EMPNUM, NAME, SAL, TAX, MGRNUM, DEPTNUM)
Fragmentation schema:
EMP1 = PJ EMPNUM, NAME, MGRNUM, DEPTNUM EMP
EMP2 = PJ EMPNUM, SAL, TAX EMP
Rajon|AUST 38
Discuss:
⁇ Is it complete ?
⁇ How to reconstruct ?
⁇ Is it disjoint ?
Rajon|AUST 39
Discuss:
⁇ Is it complete ?
If each attribute is mapped into at least one attribute of the
fragments.
⁇ How to reconstruct ?
EMP = EMP1 JN EMPNUM=EMPNUM EMP2
*NOT COMPLETE
* EMPNUM TWICE
SOLUTION (Not Considered in Book)
EMP = EMP1 JN EMPNUM=EMPNUM PJ SAL, TAX EMP2
⁇ Is it disjoint ?
Yes (supplier numbers are unique key)
Rajon|AUST 40
Mixed Fragmentation
Horizontal + Vertical.
Can be applied recursively.
Represented by Fragmentation tree.
Rajon|AUST 41
Global Schema:
EMP (EMPNUM, NAME, SAL, TAX, MGRNUM, DEPTNUM)
Fragmentation schema:
EMP1 = SL DEPTNUM ≤ 10 PJ EMPNUM, NAME, MGRNUM, DEPTNUM EMP
EMP2 = SL DEPTNUM > 10 PJ EMPNUM, NAME, MGRNUM, DEPTNUM EMP
EMP3 = PJ EMPNUM, NAME, SAL, TAX EMP
Fragmentation tree:
Rajon|AUST 42
Discuss:
⁇ Is it complete ?
⁇ How to reconstruct ?
⁇ Is it disjoint ?
Rajon|AUST 43
Discuss:
⁇ Is it complete ?
Yes
⁇ How to reconstruct ?
EMP = UN (EMP1 , EMP2) JN EMPNUM=EMPNUM
PJ EMPNUM, SAL, TAX EMP3
⁇ Is it disjoint ?
Yes
Rajon|AUST 44
Degree of Fragmentation
The degree of fragmentation lies between two
extreme situations:
1. Not to fragment at all.
2. 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).
Rajon|AUST 45
Practice Problems/ Questions
Rajon|AUST 46
Distribution transparency for read-only
application.
Rajon|AUST 47
Objective
We analyze with an example the different levels
of distribution transparency:
o Level 1: Fragmentation transparency.
o Level 2: Location transparency.
o Level 3: Local mapping transparency.
For a read-only application.
Rajon|AUST 48
Scenario
Global schema:
SUPPLIER (SNUM, NAME, CITY)
Fragmentation schema:
SUPPLIER1 = SL CITY = “DHK” (SUPPLIER)
SUPPLIER2 = SL CITY = “CTG” (SUPPLIER)
Allocation schema:
SUPPLIER1 @ site 1.
SUPPLIER2 @ site 2, 3.
Rajon|AUST 49
Assume, a application –
Reading a value from terminal and assigning it to a variable:
Query: Get NAME for a given SNUM. Example –
Writing a value of a variable to terminal:
Rajon|AUST 50
Analyzing Level – 1 transparency
Hint:
Use global relation only.
Because fragmentation
information is hidden.
Rajon|AUST 51
Rajon|AUST 52
The DDBMS interprets this primitive by accessing
the databases at any one of the three sites in a way
which is completely determined by the system.
The problem of determining how to access the
database will be discussed in Chapter 5 and 6.
Completely ignore the fact that the database is
distributed.
Rajon|AUST 53
Analyzing Level – 2 transparency
Hint:
Use fragmentation
information.
Rajon|AUST 54
Rajon|AUST 55
This application is clearly independent from changes
in the allocation schema, but not from changes in the
fragmentation schema, because the fragmentation
structure is incorporated in the application.
Location transparency is by itself very useful,
because it allows the application to ignore which
copies exist of each fragment, therefore allowing
copies to be moved from one site to another, and
allowing the creation of new copies without affecting
the application.
Rajon|AUST 56
Analyzing Level – 3 transparency
Hint:
Use fragmentation
information + location
information (i.e. site
numbers) .
Rajon|AUST 57
Rajon|AUST 58
The most important aspects of local mapping
transparency is not this name mapping between
fragment names and local filenames, but the mapping
of the primitives used by the application program into
the primitives used by the local DBMS.
Rajon|AUST 59
Distribution transparency for update
application
Rajon|AUST 60
Update Sub-tree
Example:
EMP1 = SL DEPTNUM ≤ 10 PJ EMPNUM, NAME, MGRNUM, DEPTNUM (EMP)
EMP2 = SL DEPTNUM > 10 PJ EMPNUM, NAME, MGRNUM, DEPTNUM (EMP)
EMP3 = PJ EMPNUM, NAME, SAL, TAX (EMP)
Which part of the tree will be effected
if DEPTNUM is updated?
Rajon|AUST 61
Example:
EMP1 = SL DEPTNUM ≤ 10 PJ EMPNUM, NAME, MGRNUM, DEPTNUM (EMP)
EMP2 = SL DEPTNUM > 10 PJ EMPNUM, NAME, MGRNUM, DEPTNUM (EMP)
EMP3 = PJ EMPNUM, NAME, SAL, TAX (EMP)
Which part of the tree will be effected
if DEPTNUM is updated?
Rajon|AUST 62
Objective
We analyze with an example the different levels
of distribution transparency:
o Level 1: Fragmentation transparency.
o Level 2: Location transparency.
o Level 3: Local mapping transparency.
For an update application.
Rajon|AUST 63
Scenario
Global schema:
EMP (EMPNUM, NAME, SAL, TAX, MGRNUM, DEPTNUM)
Fragmentation schema:
EMP1 = PJ EMPNUM, NAME, SAL, TAX SL DEPTNUM ≤ 10 (EMP)
EMP2 = PJ EMPNUM, MGRNUM, DEPTNUM SL DEPTNUM ≤ 10 (EMP)
EMP3 = PJ EMPNUM, NAME, DEPTNUM SL DEPTNUM > 10 (EMP)
EMP4 = PJ EMPNUM, SAL, TAX, MGRNUM SL DEPTNUM > 10 (EMP)
Allocation schema:
EMP1 @ site 1, 5; EMP2 @ site 2, 6
EMP3 @ site 3, 7; EMP4 @ site 4, 8
Rajon|AUST 64
Assume, a UPDTEMP application:
Updating DEPTNUM to 15 where EMPNUM is 100.
Example:
Rajon|AUST 65
Analyzing Level – 1 transparency
Hint:
Use global relation. No concept of fragments.
Rajon|AUST 66
Rajon|AUST 67
Update as if the database were not distributed.
The application programmer need not to know
whether an attribute is used in the definition of the
fragmentation schema or not.
It is the system’s responsibility to perform all the
operations which are implicitly required by the
fragmentation and allocation schema.
Rajon|AUST 68
Analyzing Level – 2 transparency
Hints:
Use fragments.
–Use the concept of update sub-tree.
–Follow the effect of update.
Rajon|AUST 69
Effect of Update
EMP1 = PJ EMPNUM, NAME, SAL, TAX SL DEPTNUM ≤ 10 (EMP)
EMP2 = PJ EMPNUM, MGRNUM, DEPTNUM SL DEPTNUM ≤ 10 (EMP)
EMP3 = PJ EMPNUM, NAME, DEPTNUM SL DEPTNUM > 10 (EMP)
EMP4 = PJ EMPNUM, SAL, TAX, MGRNUM SL DEPTNUM > 10 (EMP)
Rajon|AUST 70
Effect of Update
EMP1 = PJ EMPNUM, NAME, SAL, TAX SL DEPTNUM ≤ 10 (EMP)
EMP2 = PJ EMPNUM, MGRNUM, DEPTNUM SL DEPTNUM ≤ 10 (EMP)
EMP3 = PJ EMPNUM, NAME, DEPTNUM SL DEPTNUM > 10 (EMP)
EMP4 = PJ EMPNUM, SAL, TAX, MGRNUM SL DEPTNUM > 10 (EMP)
Rajon|AUST 71
Effect of Update
EMP1 = PJ EMPNUM, NAME, SAL, TAX SL DEPTNUM ≤ 10 (EMP)
EMP2 = PJ EMPNUM, MGRNUM, DEPTNUM SL DEPTNUM ≤ 10 (EMP)
EMP3 = PJ EMPNUM, NAME, DEPTNUM SL DEPTNUM > 10 (EMP)
EMP4 = PJ EMPNUM, SAL, TAX, MGRNUM SL DEPTNUM > 10 (EMP)
Rajon|AUST 72
Effect of Update
EMP1 = PJ EMPNUM, NAME, SAL, TAX SL DEPTNUM ≤ 10 (EMP)
EMP2 = PJ EMPNUM, MGRNUM, DEPTNUM SL DEPTNUM ≤ 10 (EMP)
EMP3 = PJ EMPNUM, NAME, DEPTNUM SL DEPTNUM > 10 (EMP)
EMP4 = PJ EMPNUM, SAL, TAX, MGRNUM SL DEPTNUM > 10 (EMP)
Rajon|AUST 73
Effect of Update
EMP1 = PJ EMPNUM, NAME, SAL, TAX SL DEPTNUM ≤ 10 (EMP)
EMP2 = PJ EMPNUM, MGRNUM, DEPTNUM SL DEPTNUM ≤ 10 (EMP)
EMP3 = PJ EMPNUM, NAME, DEPTNUM SL DEPTNUM > 10 (EMP)
EMP4 = PJ EMPNUM, SAL, TAX, MGRNUM SL DEPTNUM > 10 (EMP)
Rajon|AUST 74
Hints: Use fragments. Use the update sub-tree. Follow
the effect of update.
Store the necessary record from EMP1 and EMP2 to temporary
variables.
Insert the records into EMP3 and EMP4 from the temporary
variables.
Delete the records from EMP1 and EMP2.
Rajon|AUST 75
Rajon|AUST 76
Analyzing Level – 3 transparency
Hints: Use fragments + locations. Follow the effect
of update (like previous level), but this time
locations will be considered.
Store the necessary record from EMP1 and EMP2 from any of
the corresponding sites to temporary variables.
Insert the records into EMP3 and EMP4 at corresponding sites
from the temporary variables.
Delete the records from EMP1 and EMP2 at corresponding sites.
Rajon|AUST 77
Rajon|AUST 78
Additional Reading
Level – 4 transparency.
Distribution transparency for a more complex
read-only application.
–Text book section 3.3.2 (page-51)
Rajon|AUST 79
Practice Problems/ Questions
Rajon|AUST 80