DDBMS (1).pptanmhfvnmbjk bjhjjjhkjkhjkjk

SireeshaRM 22 views 50 slides May 10, 2024
Slide 1
Slide 1 of 50
Slide 1
1
Slide 2
2
Slide 3
3
Slide 4
4
Slide 5
5
Slide 6
6
Slide 7
7
Slide 8
8
Slide 9
9
Slide 10
10
Slide 11
11
Slide 12
12
Slide 13
13
Slide 14
14
Slide 15
15
Slide 16
16
Slide 17
17
Slide 18
18
Slide 19
19
Slide 20
20
Slide 21
21
Slide 22
22
Slide 23
23
Slide 24
24
Slide 25
25
Slide 26
26
Slide 27
27
Slide 28
28
Slide 29
29
Slide 30
30
Slide 31
31
Slide 32
32
Slide 33
33
Slide 34
34
Slide 35
35
Slide 36
36
Slide 37
37
Slide 38
38
Slide 39
39
Slide 40
40
Slide 41
41
Slide 42
42
Slide 43
43
Slide 44
44
Slide 45
45
Slide 46
46
Slide 47
47
Slide 48
48
Slide 49
49
Slide 50
50

About This Presentation

vvnm,nm


Slide Content

Chapter 25
Distributed Databases and
Client-Server Architectures
Copyright © 2004 Pearson Education, Inc.

Copyright © 2004 Ramez Elmasri and Shamkant Navathe
Elmasri/Navathe, Fundamentals of Database Systems, Fourth Edition Chapter 25-3
Chapter 25 Outline
1Distributed Database Concepts
2Data Fragmentation, Replication and Allocation
3Types of Distributed Database Systems
4Query Processing
5Concurrency Control and Recovery
63-Tier Client-Server Architecture

Copyright © 2004 Ramez Elmasri and Shamkant Navathe
Elmasri/Navathe, Fundamentals of Database Systems, Fourth Edition Chapter 25-4
Distributed Database Concepts
ItisasystemtoprocessUnitofexecution(atransaction)in
adistributedmanner.Thatis,atransactioncanbeexecuted
bymultiplenetworkedcomputersinaunifiedmanner.
Itcanbedefinedas
Adistributeddatabase(DDB)isacollectionofmultiple
logicallyrelateddatabasedistributedoveracomputer
network,andadistributeddatabasemanagementsystem
asasoftwaresystemthatmanagesadistributed
databasewhilemakingthedistributiontransparentto
theuser.

Copyright © 2004 Ramez Elmasri and Shamkant Navathe
Elmasri/Navathe, Fundamentals of Database Systems, Fourth Edition Chapter 25-5
Distributed Database System
Advantages
1.Managementofdistributeddatawithdifferent
levelsoftransparency:Thisreferstothephysical
placementofdata(files,relations,etc.)whichisnot
knowntotheuser(distributiontransparency).Communications neteork
Site 5
Site 1
Site 2
Site 4
Site 3

Copyright © 2004 Ramez Elmasri and Shamkant Navathe
Elmasri/Navathe, Fundamentals of Database Systems, Fourth Edition Chapter 25-6
Distributed Database System
Advantages
TheEMPLOYEE,PROJECT,andWORKS_ON tablesmaybe
fragmentedhorizontallyandstoredwithpossiblereplicationasshown
below.Communications neteork
Atlanta
San Francisco
EMPLOYEES - All
PROJECTS - All
WORKS_ON - All
Chicago
(headquarters)
New York
EMPLOYEES - New York
PROJECTS - All
WORKS_ON - New York Employees
EMPLOYEES - San Francisco and LA
PROJECTS - San Francisco
WORKS_ON - San Francisco Employees
Los Angeles
EMPLOYEES - LA
PROJECTS - LA and San Francisco
WORKS_ON - LA Employees
EMPLOYEES - Atlanta
PROJECTS - Atlanta
WORKS_ON - Atlanta Employees

Copyright © 2004 Ramez Elmasri and Shamkant Navathe
Elmasri/Navathe, Fundamentals of Database Systems, Fourth Edition Chapter 25-7
Distributed Database System
Advantages
•DistributionandNetworktransparency:Usersdonothaveto
worryaboutoperationaldetailsofthenetwork.ThereisLocation
transparency,whichreferstofreedomofissuingcommandfrom
anylocationwithoutaffectingitsworking.ThenthereisNaming
transparency,whichallowsaccesstoanynamesobject(files,
relations,etc.)fromanylocation.
•Replicationtransparency:Itallowstostorecopiesofadataat
multiplesitesasshownintheabovediagram.Thisisdoneto
minimizeaccesstimetotherequireddata.
•Fragmentationtransparency:Allowstofragmentarelation
horizontally(createasubsetoftuplesofarelation)orvertically
(createasubsetofcolumnsofarelation).

Copyright © 2004 Ramez Elmasri and Shamkant Navathe
Elmasri/Navathe, Fundamentals of Database Systems, Fourth Edition Chapter 25-8
Distributed Database System
Advantages
2.Increasedreliabilityandavailability:Reliabilityrefersto
systemlivetime,thatis,systemisrunningefficientlymostofthe
time.Availabilityistheprobabilitythatthesystemis
continuouslyavailable(usableoraccessible)duringatime
interval.Adistributeddatabasesystemhasmultiplenodes
(computers)andifonefailsthenothersareavailabletodothe
job.
3.Improvedperformance:AdistributedDBMSfragmentsthe
databasetokeepdataclosertowhereitisneededmost.This
reducesdatamanagement(accessandmodification)time
significantly.
4.Easierexpansion(scalability):Allowsnewnodes(computers)
tobeaddedanytimewithoutchainingtheentireconfiguration.

Copyright © 2004 Ramez Elmasri and Shamkant Navathe
Elmasri/Navathe, Fundamentals of Database Systems, Fourth Edition Chapter 25-9
Data Fragmentation, Replication and
Allocation
Data Fragmentation
Split a relation into logically related and correct parts. A
relation can be fragmented in two ways:
Horizontalfragmentation
Itisahorizontalsubsetofarelationwhichcontainthoseof
tupleswhichsatisfyselectionconditions.
ConsidertheEmployeerelationwithselectioncondition(DNO
=5).Alltuplessatisfythisconditionwillcreateasubsetwhich
willbeahorizontalfragmentofEmployeerelation.
Aselectionconditionmaybecomposedofseveralconditions
connectedbyANDorOR.
Derivedhorizontalfragmentation:Itisthepartitioningofa
primaryrelationtoothersecondaryrelationswhicharerelated
withForeignkeys.

Copyright © 2004 Ramez Elmasri and Shamkant Navathe
Elmasri/Navathe, Fundamentals of Database Systems, Fourth Edition Chapter 25-10
Data Fragmentation, Replication and
Allocation
Verticalfragmentation
Itisasubsetofarelationwhichiscreatedbyasubsetof
columns.Thusaverticalfragmentofarelationwillcontain
valuesofselectedcolumns.Thereisnoselectionconditionused
inverticalfragmentation.
ConsidertheEmployeerelation.Averticalfragmentofcanbe
createdbykeepingthevaluesofName,Bdate,Sex,and
Address.
Becausethereisnoconditionforcreatingaverticalfragment,
eachfragmentmustincludetheprimarykeyattributeofthe
parentrelationEmployee.Inthiswayallverticalfragmentsof
arelationareconnected.

Copyright © 2004 Ramez Elmasri and Shamkant Navathe
Elmasri/Navathe, Fundamentals of Database Systems, Fourth Edition Chapter 25-11
Data Fragmentation, Replication and
Allocation
Representation
Horizontalfragmentation
Eachhorizontalfragmentonarelationcanbespecifiedbyas
Ci
(R)operationintherelationalalgebra.
Completehorizontalfragmentation
AsetofhorizontalfragmentswhoseconditionsC1,C2,…,Cn
includeallthetuplesinR-thatis,everytupleinRsatisfies(C1
ORC2OR…ORCn).
Disjointcompletehorizontalfragmentation:NotupleinR
satisfies(CiANDCj)wherei≠j.
ToreconstructRfromhorizontalfragmentsaUNIONis
applied.

Copyright © 2004 Ramez Elmasri and Shamkant Navathe
Elmasri/Navathe, Fundamentals of Database Systems, Fourth Edition Chapter 25-12
Data Fragmentation, Replication and
Allocation
Representation
Verticalfragmentation
Averticalfragmentonarelationcanbespecifiedbya
Li(R)
operationintherelationalalgebra.
Completeverticalfragmentation
AsetofverticalfragmentswhoseprojectionlistsL1,L2,…,Ln
includealltheattributesinRbutshareonlytheprimarykeyof
R.Inthiscasetheprojectionlistssatisfythefollowingtwo
conditions:
L1L2...Ln=ATTRS(R)
LiLj=PK(R)foranyij,whereATTRS(R)isthesetof
attributesofRandPK(R)istheprimarykeyofR.
ToreconstructRfromcompleteverticalfragmentsaOUTER
UNIONisapplied.

Copyright © 2004 Ramez Elmasri and Shamkant Navathe
Elmasri/Navathe, Fundamentals of Database Systems, Fourth Edition Chapter 25-13
Data Fragmentation, Replication and
Allocation
Mixed(Hybrid)fragmentation
AcombinationofVerticalfragmentationandHorizontal
fragmentation.
ThisisachievedbySELECT-PROJECToperationswhichis
representedby
Li(s
Ci(R)).
IfC=True(Selectalltuples)andL≠ATTRS(R),wegeta
verticalfragment,andifC≠TrueandL≠ATTRS(R),wegeta
mixedfragment.
IfC=TrueandL=ATTRS(R),thenRcanbeconsidereda
fragment.

Copyright © 2004 Ramez Elmasri and Shamkant Navathe
Elmasri/Navathe, Fundamentals of Database Systems, Fourth Edition Chapter 25-14
Data Fragmentation, Replication and
Allocation
Fragmentationschema
Adefinitionofasetoffragments(horizontalorverticalor
horizontalandvertical)thatincludesallattributesandtuples
inthedatabasethatsatisfiestheconditionthatthewhole
databasecanbereconstructedfromthefragmentsbyapplying
somesequenceofUNION(orOUTERJOIN)andUNION
operations.
Allocationschema
Itdescribesthedistributionoffragmentstositesofdistributed
databases.Itcanbefullyorpartiallyreplicatedorcanbe
partitioned.

Copyright © 2004 Ramez Elmasri and Shamkant Navathe
Elmasri/Navathe, Fundamentals of Database Systems, Fourth Edition Chapter 25-15
Data Fragmentation, Replication and
Allocation
DataReplication
Databaseisreplicatedtoallsites.Infullreplicationtheentire
databaseisreplicatedandinpartialreplicationsomeselected
partisreplicatedtosomeofthesites.Datareplicationis
achievedthroughareplicationschema.
DataDistribution(DataAllocation)
Thisisrelevantonlyinthecaseofpartialreplicationor
partition.Theselectedportionofthedatabaseisdistributedto
thedatabasesites.

Copyright © 2004 Ramez Elmasri and Shamkant Navathe
Elmasri/Navathe, Fundamentals of Database Systems, Fourth Edition
Chapter 25-16
Disadvantages of distributed databases
Complexity—
–ExtraworkmustbedonebytheDBAstoensurethatthedistributednatureofthe
systemistransparent.
–Extraworkmustalsobedonetomaintainmultipledisparatesystems,insteadofone
bigone.
–Extradatabasedesignworkmustalsobedonetoaccountforthedisconnectednature
ofthedatabase—forexample,joinsbecomeprohibitivelyexpensivewhenperformed
acrossmultiplesystems.
Economics —increased complexity and a more extensive infrastructure means
extra labourcosts.
Security —remote database fragments must be secured, and they are not
centralized so the remote sites must be secured as well. The infrastructure must
also be secured (eg: by encrypting the network links between remote sites).
Difficult to maintain integrity —in a distributed database enforcing integrity over
a network may require too much networking resources to be feasible.
No reliance on central site .

Copyright © 2004 Ramez Elmasri and Shamkant Navathe
Elmasri/Navathe, Fundamentals of Database Systems, Fourth Edition Chapter 25-17
Additional Functions of
Distributed Databases
Distributedqueryprocessing
Distributedtransactionmanagement(e.g.,two-phasecommit)
Replicationmanagement
Distributeddatabaserecovery
Distributedsecurityissues

Copyright © 2004 Ramez Elmasri and Shamkant Navathe
Elmasri/Navathe, Fundamentals of Database Systems, Fourth Edition
Allocation of fragments to sites.
(a) Relation fragments at site 2
corresponding to department 5.

Copyright © 2004 Ramez Elmasri and Shamkant Navathe
Elmasri/Navathe, Fundamentals of Database Systems, Fourth Edition
Allocation of fragments to sites.
(b) Relation fragments at site 3
corresponding to department 4.

Copyright © 2004 Ramez Elmasri and Shamkant Navathe
Elmasri/Navathe, Fundamentals of Database Systems, Fourth Edition Slide 25-20
FIGURE 25.4
Complete and disjoint fragments of the WORKS_ON relation. (a)
Fragments of WORKS_ON for employees working in department 5
(C=[ESSN IN (SELECT SSN FROM EMPLOYEE WHERE DNO=5)]).

Copyright © 2004 Ramez Elmasri and Shamkant Navathe
Elmasri/Navathe, Fundamentals of Database Systems, Fourth Edition Slide 25-21
FIGURE 25.4 (continued)
Complete and disjoint fragments of the WORKS_ON relation. (b)
Fragments of WORKS_ON for employees working in department 4
(C=[ESSN IN (SELECT SSN FROM EMPLOYEE WHERE DNO=4)]).

Copyright © 2004 Ramez Elmasri and Shamkant Navathe
Elmasri/Navathe, Fundamentals of Database Systems, Fourth Edition Slide 25-22
FIGURE 25.4 (continued)
Complete and disjoint fragments of the WORKS_ON relation. (c)
Fragments of WORKS_ON for employees working in department 1
(C=[ESSN IN (SELECT SSN FROM EMPLOYEE WHERE DNO=1)]).

Copyright © 2004 Ramez Elmasri and Shamkant Navathe
Elmasri/Navathe, Fundamentals of Database Systems, Fourth Edition
Works_ontuplesfor
Employeeswhowork
fordept5
Works_ontuplesfor
Employeeswhowork
fordept4
Projectscontrolledby
dept5
G1,G2,G3,G4,G7
G4,G5,G6,G2,G8
•Union of G1,G2,G3
•Union of G4,G5,G6
•Union of G7,G8,G9
•Union of G1,G4,G7
•Fragments at site2
•Fragments at site 3
Works_ontuplesfor
Employeeswhowork
fordept5
Works_ontuplesfor
Employeeswhowork
fordept4
Works_ontuplesfor
Employeeswhowork
fordept1
Projectscontrolledby
dept5
G1,G2,G3,G4,G7
G4,G5,G6,G2,G8

Copyright © 2004 Ramez Elmasri and Shamkant Navathe
Elmasri/Navathe, Fundamentals of Database Systems, Fourth Edition Chapter 25-24
Types of Distributed Database Systems
Homogeneous
Allsitesofthedatabasesystemhaveidenticalsetup,i.e.,samedatabasesystem
software.Theunderlyingoperatingsystemmaybedifferent.Forexample,all
sitesrunOracleorDB2,orSybaseorsomeotherdatabasesystem.The
underlyingoperatingsystemscanbeamixtureofLinux,Window,Unix,etc.
Theclientsthushavetouseidenticalclientsoftware.Communications
neteork
Site 5
Site 1
Site 2Site 3
Oracle Oracle
Oracle
Oracle
Site 4
Oracle
LinuxLinux
Window
Window
Unix

Copyright © 2004 Ramez Elmasri and Shamkant Navathe
Elmasri/Navathe, Fundamentals of Database Systems, Fourth Edition Chapter 25-25
Types of Distributed Database Systems
Heterogeneous
Federated:Eachsitemayrundifferentdatabasesystembutthedata
accessismanagedthroughasingleconceptualschema.Thisimplies
thatthedegreeoflocalautonomyisminimum.Eachsitemustadhere
toacentralizedaccesspolicy.Theremaybeaglobalschema.
Multidatabase:Thereisnooneconceptualglobalschema.Fordata
accessaschemaisconstructeddynamicallyasneededbythe
applicationsoftware.Communications
network
Site 5
Site 1
Site 2Site 3
Network
DBMS
Relational
Site 4
Object
Oriented
LinuxLinux
Unix
Hierarchical
Object
Oriented
RelationalUnix
Window

Copyright © 2004 Ramez Elmasri and Shamkant Navathe
Elmasri/Navathe, Fundamentals of Database Systems, Fourth Edition Chapter 25-26
Homogeneous vsheterogeneous
–Hardware
–Data model: relational, object, hierarchical
–Brand DBMS
–Version of query language
Level of local autonomy
Local vsglobal schema
–Federated: some global schema
–Multidatabase: no (or limited) global schema
Types of Distributed Database Systems

Copyright © 2004 Ramez Elmasri and Shamkant Navathe
Elmasri/Navathe, Fundamentals of Database Systems, Fourth Edition Chapter 25-27
Five level architecture of FDBS
Inthisonelocalschemaistheconceptualschema
(completedatabasedefinition)ofacomponent
database.
Componentschemaisderivedbytranslatingthelocal
schemaintoacommondatamodelfortheFDBS.
Theexportschemarepresentsthesubsetofthe
componentschemathatisavailabletotheFDBS.
Thefederatedschemaistheglobalschemaorview,
whichistheresultofintegratingalltheshareable
exportschemas.
Theexternalschemadefinetheschemaforauser
grouporanapplication.

Copyright © 2004 Ramez Elmasri and Shamkant Navathe
Elmasri/Navathe, Fundamentals of Database Systems, Fourth Edition Slide 25-28
FIGURE 25.5
The five-level
schema architecture
in a federated
database system
(FDBS). Source:
Adapted from Sheth
and Larson,
Federated Database
Systems for
Managing
Distributed
Heterogeneous
Autonomous
Databases. ACM
Computing Surveys
(Vol. 22: No. 3,
September 1990).

Copyright © 2004 Ramez Elmasri and Shamkant Navathe
Elmasri/Navathe, Fundamentals of Database Systems, Fourth Edition Chapter 25-29
Data Transfer Costs of Distributed Query Processing
Distributed Query Processing Using Semijoin
Query and Update Decomposition
Query Processing in Distributed
Databases

Copyright © 2004 Ramez Elmasri and Shamkant Navathe
Elmasri/Navathe, Fundamentals of Database Systems, Fourth Edition Chapter 25-30
Examples to illustrate volume of data transferred.

Copyright © 2004 Ramez Elmasri and Shamkant Navathe
Elmasri/Navathe, Fundamentals of Database Systems, Fourth Edition Chapter 25-31
Query Processing in Distributed Databases
Costoftransferringdata(filesandresults)overthenetwork.
FnameMinitLnameSSNBdateAddressSexSalarySuperssnDno
Issues
This cost is usually high so some optimization is necessary.
Example relations: Employee at site 1 and Department at Site 2
DnameDnumberMgrssnMgrstartdate
Employee at site 1. 10, 000 rows. Row size = 100 bytes. Table size = 10
6
bytes.
Department at Site 2. 100 rows. Row size = 35 bytes. Table size = 3500 bytes.
Q:Foreachemployee,retrieveemployeenameanddepartment
nameWheretheemployeeworks.
Q:
Fname,Lname,Dname(Employee
Dno=DnumberDepartment)

Copyright © 2004 Ramez Elmasri and Shamkant Navathe
Elmasri/Navathe, Fundamentals of Database Systems, Fourth Edition Chapter 25-32
Query Processing in Distributed Databases
Result
Stretagies:
1.TransferEmployeeandDepartmenttosite3.Totaltransferbytes
=1,000,000+3500=1,003,500bytes.
2.TransferEmployeetosite2,executejoinatsite2andsendthe
resulttosite3.Queryresultsize=40*10,000=400,000bytes.
Totaltransfersize=400,000+1,000,000=1,400,000bytes.
The result of this query will have 10,000 tuples, assuming that every
employee is related to a department.
Suppose each result tuple is 40 bytes long. The query is submitted at
site 3 and the result is sent to this site.
Problem: Employee and Department relations are not present at site 3.

Copyright © 2004 Ramez Elmasri and Shamkant Navathe
Elmasri/Navathe, Fundamentals of Database Systems, Fourth Edition Chapter 25-33
Query Processing in Distributed Databases
Stretagies:
3.TransferDepartmentrelationtosite1,executethejoinatsite1,
andsendtheresulttosite3.Totalbytestransferred=400,000+
3500=403,500bytes.
Optimizationcriteria:minimizingdatatransfer.
Preferredapproach:strategy3.
Considerthequery
Q’:Foreachdepartment,retrievethedepartmentnameandthe
nameofthedepartmentmanager
RelationalAlgebraexpression:

Fname,Lname,Dname(Employee
Mgrssn = SSNDepartment)

Copyright © 2004 Ramez Elmasri and Shamkant Navathe
Elmasri/Navathe, Fundamentals of Database Systems, Fourth Edition Chapter 25-34
Query Processing in Distributed Databases
Theresultofthisquerywillhave100tuples,assumingthatevery
departmenthasamanager,theexecutionstrategiesare:
Stretagies:
1.TransferEmployeeandDepartmenttotheresultsiteandperorm
thejoinatsite3.Totalbytestransferred=1,000,000+3500=
1,003,500bytes.
2.TransferEmployeetosite2,executejoinatsite2andsendthe
resulttosite3.Queryresultsize=40*100=4000bytes.Total
transfersize=4000+1,000,000=1,004,000bytes.
3.TransferDepartmentrelationtosite1,executejoinatsite1and
sendtheresulttosite3.Totaltransfersize=4000+3500=7500
bytes.

Copyright © 2004 Ramez Elmasri and Shamkant Navathe
Elmasri/Navathe, Fundamentals of Database Systems, Fourth Edition Chapter 25-35
Query Processing in Distributed Databases
Preferredstrategy:Chosestrategy3.
Nowsupposetheresultsiteis2.Possiblestrategies:
Possiblestrategies:
1.TransferEmployeerelationtosite2,executethequeryandpresent
theresulttotheuseratsite2.Totaltransfersize=1,000,000bytes
forbothqueriesQandQ’.
2.TransferDepartmentrelationtosite1,executejoinatsite1and
sendtheresultbacktosite2.TotaltransfersizeforQ=400,000+
3500=403,500bytesandforQ’=4000+3500=7500bytes.

Copyright © 2004 Ramez Elmasri and Shamkant Navathe
Elmasri/Navathe, Fundamentals of Database Systems, Fourth Edition Chapter 25-36
Query Processing in Distributed Databases
Semijoin:Objectiveistoreducethenumberoftuplesinarelation
beforetransferringittoanothersite.
ExampleexecutionofQorQ’:
1.ProjectthejoinattributesofDepartmentatsite2,andtransfer
themtosite1.ForQ,4*100=400bytesaretransferredandfor
Q’,9*100=900bytesaretransferred.
2.JointhetransferredfilewiththeEmployeerelationatsite1,and
transfertherequiredattributesfromtheresultingfiletosite2.
ForQ,34*10,000=340,000bytesaretransferredandforQ’,39*
100=3900bytesaretransferred.
3.ExecutethequerybyjoiningthetransferredfilewithDepartment
andpresenttheresulttotheuseratsite2.

Copyright © 2004 Ramez Elmasri and Shamkant Navathe
Elmasri/Navathe, Fundamentals of Database Systems, Fourth Edition Chapter 25-37
Query and Update decomposition
•Forqueries,querydecompositionmodule mustbreakup
ordecomposeaqueryintosubqueriesthatcanbeexecutedatthe
individualsites.
•Astrategymustbethereforcombiningtheresultsofthe
subqueriestoformthequeryresult.
•Particularreplicarelatedtothequerymustbeselected.
•Formakingsuchdecisions,DDBMSmustmaintaincatalog
consistingfragmentation,replicationanddistributionof
information.
•Forverticalfragmentationtheattributelistforeachfragmentis
stored.
•Forhorizontalfragmentation,Guardconditionisstored.
•Formixedbotharestored.

Copyright © 2004 Ramez Elmasri and Shamkant Navathe
Elmasri/Navathe, Fundamentals of Database Systems, Fourth Edition Slide 25-38
FIGURE 25.7
Guard conditions and attributes lists for fragments.
(a) Site 2 fragments.

Copyright © 2004 Ramez Elmasri and Shamkant Navathe
Elmasri/Navathe, Fundamentals of Database Systems, Fourth Edition Slide 25-39
FIGURE 25.7 (continued)
Guard conditions and attributes lists for fragments.
(b) Site 3 fragments.

Copyright © 2004 Ramez Elmasri and Shamkant Navathe
Elmasri/Navathe, Fundamentals of Database Systems, Fourth Edition
User wants to insert a new employee tuple
<‘Alex’, ‘B’, ‘coleman’, ‘345671239’, ‘22-
APR-04’, ‘3306 SAND-STONE’, ‘M’,
33000, ‘957654321’, 4>
Decomposed by the DDBMS into two insert
request.
–Insert the full tuple in employee at site 1.
–Insert the projected tuple <‘Alex’, ‘B’,
‘coleman’, ‘345671239’, 33000, ‘957654321’,
4> in the EMPD4 fragment at site 3.
Chapter 25-40
Query and Update decomposition

Copyright © 2004 Ramez Elmasri and Shamkant Navathe
Elmasri/Navathe, Fundamentals of Database Systems, Fourth Edition
Retrieve the names and hours per week for
each employee who works on some project
controlled by department 5.
Query is submitted at site 2
–SQL : SELECT fname,lname,hours
FROM employee, projects, works_on
WHERE dnum = 5 and pnumber = pno
and essn = ssn;
Chapter 25-41
Query and Update decomposition

Copyright © 2004 Ramez Elmasri and Shamkant Navathe
Elmasri/Navathe, Fundamentals of Database Systems, Fourth Edition
The DDBMS can determine from the guard condition on
projs5 and works_on5 that all tuples satisfying the condition (
dnum = 5 and dnumber = pno ) reside at site2.
Decompose the query
–T1 ∏
ESSN ( PROJS5
PNUMBER=PNOWORKS_ON5)
–T2 ∏
ESSN,FNAME, LNAME ( T1
ESSN=SSNEMPLOYEE)
–RESULT ∏
FNAME, LNAME, HOURS ( T2 * WORKS_ON5 )
EXECUTE USING SEMIJOIN
–Execute T1 in site 2 & send ESSN to site 1
–Execute T2 in site 1 & send result to site 2
–Calculate result at site 2
Chapter 25-42
Query and Update decomposition

Copyright © 2004 Ramez Elmasri and Shamkant Navathe
Elmasri/Navathe, Fundamentals of Database Systems, Fourth Edition Chapter 25-43
Two-phase commit protocol
Aglobalrecoverymanager(orcoordinator)performsthe
two-phasecommitprotocol:
1)Whenallparticipatingdatabasessignalthecoordinatorthat
thepartofthetransactioninvolvingeachhasconcluded,the
coordinatorsendsamessage“prepareforcommit”toeach
participant,
2)Ifallparticipatingdatabasesreply“OK”,thetransactionis
successfulandthecoordinatorsendsa“commit”signaltothe
participatingdatabases;otherwiseitsendsamessage“roll
back”orUNDOthelocaleffectofthetransactiontoeach
participatingdatabase.

Copyright © 2004 Ramez Elmasri and Shamkant Navathe
Elmasri/Navathe, Fundamentals of Database Systems, Fourth Edition Chapter 25-44
Distributed Transactions
TheTwoPhaseCommitprotocol(2PC)
Afterpreparephase:participantsarereadytocommitortoabort;theystill
holdlocks
Ifoneoftheparticipantsdoesnotreplyorisnotabletocommitforsome
reason,theglobaltransactionhastobeaborted.
Problem:ifcoordinatorisunavailableafterthepreparephase,resourcesmay
belockedforalongtime.

Copyright © 2004 Ramez Elmasri and Shamkant Navathe
Elmasri/Navathe, Fundamentals of Database Systems, Fourth Edition
Dealingwithmultiplecopiesofdataitems:Theconcurrencycontrolmust
maintainglobalconsistency.Likewisetherecoverymechanismmustrecoverall
copiesandmaintainconsistencyafterrecovery.
Failureofindividualsites:Databaseavailabilitymustnotbeaffectedduetothe
failureofoneortwositesandtherecoveryschememustrecoverthembefore
theyareavailableforuse.
Communicationlinkfailure:Thisfailuremaycreatenetworkpartitionwhich
wouldaffectdatabaseavailabilityeventhoughalldatabasesitesmayberunning.
Distributedcommit:Atransactionmaybefragmentedandtheymaybe
executedbyanumberofsites.Thisrequireatwo-phasecommitapproachfor
transactioncommit.
Distributeddeadlock:Sincetransactionsareprocessedatmultiplesites,twoor
moresitesmaygetinvolvedindeadlock.Thismustberesolvedinadistributed
manner.
Chapter 25-45
DistributedDatabasesencounteranumberofconcurrencycontroland
recoveryproblemswhicharenotpresentincentralizeddatabases.Someof
themarelistedbelow.
Concurrency Control and Recovery

Copyright © 2004 Ramez Elmasri and Shamkant Navathe
Elmasri/Navathe, Fundamentals of Database Systems, Fourth Edition
Concurrency Control and Recovery
1.DistributedConcurrencycontrolbasedonadistinguishedcopyofadata
itemCommunications neteork
Site 5
Site 1
Site 2
Site 4
Site 3
Primary site
Primarysitetechnique
–Asinglesiteisdesignatedasaprimarysitewhichservesasacoordinatorfor
transactionmanagement.
–Alllocksarekeptatthatsite,andallrequestsforlockingorunlockingaresent
here.

Copyright © 2004 Ramez Elmasri and Shamkant Navathe
Elmasri/Navathe, Fundamentals of Database Systems, Fourth Edition Chapter 25-47
Concurrency Control and Recovery
•Transactionmanagement:
–Concurrencycontrolandcommitaremanagedbythissite.Intwophase
locking,thissitemanageslockingandreleasingdataitems.Ifalltransactions
followtwo-phasepolicyatallsites,thenserializabilityisguaranteed.
•Advantages:
–Anextensiontothecentralizedtwophaselockingsoimplementationand
managementissimple.Dataitemsarelockedonlyatonesitebuttheycanbe
accessedatanysite.
•Disadvantages:
–Alltransactionmanagementactivitiesgotoprimarysitewhichislikelyto
overloadthesite.Iftheprimarysitefails,theentiresystemisinaccessible.
•Toaidrecoveryabackupsiteisdesignatedwhichbehavesasa
shadowofprimarysite.Incaseofprimarysitefailure,backup
sitecanactasprimarysite.

Copyright © 2004 Ramez Elmasri and Shamkant Navathe
Elmasri/Navathe, Fundamentals of Database Systems, Fourth Edition Chapter 25-48
PrimaryCopyTechnique
–Inthisapproach,insteadofasite,adataitempartitionisdesignatedas
primarycopy.Tolockadataitemjusttheprimarycopyofthedataitem
islocked.
•Advantages:
–Sinceprimarycopiesaredistributedatvarioussites,asinglesiteisnot
overloadedwithlockingandunlockingrequests.
•Disadvantages:
–Identificationofaprimarycopyiscomplex.Adistributeddirectory
mustbemaintained,possiblyatallsites.
Recoveryfromacoordinatorfailure
•Inbothapproachesacoordinatorsiteorcopymaybecomeunavailable.
Thiswillrequiretheselectionofanewcoordinator.
•Primarysiteapproachwithnobackupsite:Abortsandrestartsallactive
transactionsatallsites.Electsanewcoordinatorandinitiatestransaction
processing.
•Primarysiteapproachwithbackupsite:Suspendsallactivetransactions,
designatesthebackupsiteastheprimarysiteandidentifiesanewbackup
site.Primarysitereceivesalltransactionmanagementinformationto
resumeprocessing.
•Primaryandbackupsitesfailornobackupsite:Useelectionprocessto
selectanewcoordinatorsite.
Concurrency Control and Recovery

Copyright © 2004 Ramez Elmasri and Shamkant Navathe
Elmasri/Navathe, Fundamentals of Database Systems, Fourth Edition Chapter 25-49
Concurrency Control and Recovery
2.DistributedConcurrencycontrolbasedonvoting:Thereisnoprimary
copyofcoordinator.
•Nodistinguishedcopy.
•Sendlockrequesttositesthathavedataitem.
•Eachcopymaintainsitownlockandcangrantordenythe
request.
•Ifmajorityofsitesgrantlockthentherequestingtransactiongets
thedataitem.
•Lockinginformation(grantordenied)issenttoallthesesites.
•Toavoidunacceptablylongwait,atime-outperiodisdefined.If
therequestingtransactiondoesnotgetanyvoteinformationthen
thetransactionisaborted.

Copyright © 2004 Ramez Elmasri and Shamkant Navathe
Elmasri/Navathe, Fundamentals of Database Systems, Fourth Edition Chapter 25-50
Distributed recovery
The recovery process in DDBMS is quite involved.
It is quite difficult to determine whether a site is down without
exchanging numerous message with other sites.
Example
–Site X sends a message to site Y and expects a response from Y but
does not receive it.
The message was not delivered to Y because of communication failure.
Site Y is down and could not respond.
Site Y is running and sent a response, but the response was not delivered.
Another problem with distributed recovery is distributed
commit.
–When a transaction is updating data at several sites, it cannot commit
until it is sure that the effects of the transaction on every site cannot be
lost.
Tags