DDBMS (1).pptanmhfvnmbjk bjhjjjhkjkhjkjk

vvnm,nm

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

3. 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

4. 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.

5. 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

6. 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

7. 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).

8. 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.

9. 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.

10. 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.

11. 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.

12. 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.

13. 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.

14. 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.

15. 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.

16. 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 .

17. 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

18. 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.

19. 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.

20. 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)]).

21. 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)]).

22. 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)]).

23. 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

24. 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

25. 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

26. 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

27. 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.

28. 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).

29. 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

30. 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.

31. 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)

32. 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.

33. 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)

34. 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.

35. 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.

36. 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.

37. 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.

38. 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.

39. 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.

40. 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

41. 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

42. 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

43. 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.

44. 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.

45. 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

46. 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.

47. 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.

48. 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

49. 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.

50. 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.