Lecture Notes Unit3 chapter21 - parallel databases

Description:
Welcome to the comprehensive guide on Relational Database Management System (RDBMS) concepts, tailored for final year B.Sc. Computer Science students affiliated with Alagappa University. This document covers fundamental principles and advanced topics in RDBMS, offering a structured approach to understanding databases in the context of modern computing. PDF content is prepared from the text book databse system concepts by siberschatz, Korth and sudharsan

Key Topics Covered:

Main Topic : Parallel Databases
Sub-Topic :
Introduction - IO Parallelism - Partitioning techniques - comparision of partioning techniques - handlings of skew - Inter-query parallelism - intra-query parallelism
Target Audience:
Final year B.Sc. Computer Science students at Alagappa University seeking a solid foundation in RDBMS principles for academic and practical applications.

URL for previous slides
Unit 3: https://www.slideshare.net/slideshow/lecture-notes-unit3-chapter20-database-system-architectures/272417221
Unit 2:
https://www.slideshare.net/slideshow/lecture-notes-unit2-chapter7-relationaldatabasedesign/271859844
Unit I:
Chapter 6 : Database Design and ER Model https://www.slideshare.net/slideshow/lecture-notes-unit-1-chapter-6-e-r-model/271813542
Chapter 1 : Introduction to DBMS
https://www.slideshare.net/slideshow/lecture-notes-unit1-chapter1-introduction/271392881

Unit V
Chapter 20:
https://www.slideshare.net/slideshow/lecture-notes-unit5-chapter20-transaction/270998760
Chapter 19:
https://www.slideshare.net/slideshow/lecture-notes-unit5-chapter19-cursor-in-pl-sql/270998251
Chapter 18: https://www.slideshare.net/slideshow/lecture-notes-unit5-chapter18-packages-pdf/270845026
Chapter 17: https://www.slideshare.net/slideshow/lecture-notes-unit5-chapter17-stored-procedures-and-functions/270844763
Chapter 16 : https://www.slideshare.net/slideshow/lecture-notes-unit5-chapter16-trigger-creation/270631080
Chapter 15 : https://www.slideshare.net/slideshow/lecture-notes-unit5-chapter-15-pl-sql-programming/270383949

Unit IV

Chapter 14 Synonym : https://www.slideshare.net/slideshow/lecture_notes_unit4_chapter14_synonyms-pdf/270327685
Chapter 13 Users, Privileges : https://www.slideshare.net/slideshow/lecture-notes-unit4-chapter13-users-roles-and-privileges/270304806
Chapter 12 View : https://www.slideshare.net/slideshow/rdbms-lecture-notes-unit4-chapter12-view/270199683
Chapter 11 Sequence: https://www.slideshare.net/slideshow/sequnces-lecture_notes_unit4_chapter11_sequence/270134792
chapter 8,9 and 10 : https://www.slideshare.net/slideshow/lecture_notes_unit4_chapter_8_9_10_rdbms-for-the-students-affiliated-by-alagappa-university/270123800

About the Author:
Dr. S. Murugan is Associate Professor at Alagappa Government Arts College, Karaikudi. With 23 years of teaching experience in the field of Computer Science, Dr. S. Murugan has a passion for simplifying complex concepts in database management.

Disclaimer:
This document is intended for educational pu

1. RDBMS -Unit III
Chapter 21
Parallel Databases
Prepared By
Dr.S.Murugan, Associate Professor
Department of Computer Science,
AlagappaGovernmentArts College, Karaikudi.
(Affiliated by AlagappaUniversity)
Mailid: [email protected]
Reference Book:
Database System Concepts by Abraham Silberschatz, Henry
F.Korth, S. Sudharshan

2. 21.1 Introduction
➢Alargenumberofcomputersusedbytheorganization.
➢Organizationsareusinglargevolumesofdata-suchas
dataaboutwhatitemspeoplebuy,whatWeblinks
usersclickon,andwhenpeoplemaketelephonecalls-
toplantheiractivitiesandpricing.
➢Asmicroprocessorshavebecomecheap,parallel
machineshavebecomecommonandrelatively
inexpensive

3. 21.2 lOParallelism
➢I/Oparallelismreferstoreducingthetimerequiredto
retrieverelationsfromdiskbypartitioningthe
relationsonmultipledisks.
➢Themostcommonformofdatapartitioningis
horizontalpartitioning.
➢Inhorizontalpartitioning,thetuplesofarelationare
divided(ordeclustered)amongmanydisks.

4. 21.2.1 Partitioning Techniques
➢Therearethreebasicdata-partitioningstrategiesare
discussedhere.Assumethattherearendisks,Do,D
1,.
..,D
n-1,acrosswhichthedataaretobepartitioned.
➢Round-robin.Thisstrategyscanstherelationinany
orderandsendsthei
th
tupletodisknumberD
imodn.
Eachdiskhasapproximatelythesamenumberof
tuplesastheothers.(Numberofrecordsdividedwith
modfunction)

5. 21.2.1 Partitioning Techniques
Round-robin:
Records
Mod
FunctionDisk Block
1 1 mod 3 1
2 2 mod 3 2
3 3 mod 3 0
4 4 mod 3 1
5 5 mod 3 2
6 6 mod 3 0
7 7 mod 3 1
8 8 mod 3 2
9 9 mod 3 0
Disk BlockRecords
0 3,6,9
1 1,4,7
2 2,5,8

6. 21.2.1 Partitioning Techniques
➢Hashpartitioning.Thisdeclusteringstrategy
designatesoneormoreattributesfromthegiven
relation'sschemaasthepartitioningattributes.Ahash
functionischosenwhoserangeis{0,1,...,n-1}.
Numberofattributesdivided.
➢Forex,Assumethatthetablecontains9Attributes
with100records.Disk0maycontains100records
withfirst3attribute;Disk1maycontains100records
withnext3attribute;Disk2maycontains100records
withlast3attribute;

7. 21.2.1 Partitioning Techniques
➢Rangepartitioning.Thisstrategydistributes
contiguousattribute-valuerangestoeachdisk.
➢Forexample,rangepartitioningwiththreedisks
numbered0,1,and2mayassigntupleswithvalues
lessthan5todisk0,valuesbetween5and40todisk
1,andvaluesgreaterthan40todisk2.(Numberof
recordsdividedwithrangefunction)

8. 21.2.2 Comparison of Partitioning Techniques
➢Oncearelationhasbeenpartitionedamongseveral
disks,wecanretrieveitinparallel,usingallthedisks.
➢Similarly,whenarelationisbeingpartitioned,itcan
bewrittentomultipledisksinparallel.
➢Thetransferratesforreadingorwritinganentire
relationaremuchfasterwithI/Oparallelism.
➢Readinganentirerelation,orscanningarelation,is
onlyonekindofaccesstodata.

9. 21.2.2 Comparison of Partitioning Techniques
➢Accesstodatacanbeclassifiedasfollows:
1.Scanningtheentirerelation
2.Locatingatupleassociatively(forexample,
employee_nam=e"Campbell");
thesequeries,calledpointqueries,seektuplesthat
haveaspecifiedvalueforaspecificattribute.
3.Locatingalltuplesforwhichthevalueofagiven
attributelieswithinaspecifiedrange(forexample,
10000Isalary<20000);thesequeriesarecalled
rangequeries

10. 21.2.3 Handling of Skew
➢Whenarelationispartitioned(byatechniqueother
thanround-robin),theremaybeaskewinthe
distributionoftuples,withahighpercentageoftuples
placedinsomepartitionsandfewertuplesinother
partitions.
➢Theskewmaybeclassifiedas:
➢Attribute-valueskew
➢Partitionskew

11. 21.2.3 Handling of Skew
➢Attribute-valueskewreferstothefactthatsome
valuesappearinthepartitioningattributesofmany
tuples.
➢Partitionskewreferstothefactthattheremaybe
loadimbalanceinthepartitioning.

12. 21.2.3 Handling of Skew
➢Abalancedrange-partitioningvectorcanbe
constructedbysorting:
➢Therelationisfirstsortedonthepartitioning
attributes.
➢Therelationisthenscannedinsortedorder.
➢Afterevery1/noftherelationhasbeenread,thevalue
ofthepartitioningattributeofthenexttupleisadded
tothepartitionvector.Here,ndenotesthenumberof
partitionstobeconstructed.

13. 21.2.3 Handling of Skew
➢Incasetherearemanytupleswiththesamevalueforthe
partitioningattribute,thetechniquecanstillresultin
someskew.
➢ThemaindisadvantageofthismethodistheextraI/O
overheadincurredindoingtheinitialsort.
➢TheI/Ooverheadforconstructingbalancedrange-
partitionvectorscanbereducedbyconstructingand
storingafrequencytable,orhistogram,oftheattribute
valuesforeachattributeofeachrelation.
➢Figure21.1showsanexampleofahistogramforan
integer-valuedattributethattakesvaluesintherange1
to25.

14. 21.2.3 Handling of Skew

15. 21.2.3 Handling of Skew
➢Incasetherearemanytupleswiththesamevalueforthe
partitioningattribute,thetechniquecanstillresultin
someskew.
➢ThemaindisadvantageofthismethodistheextraI/O
overheadincurredindoingtheinitialsort.
➢TheI/Ooverheadforconstructingbalancedrange-
partitionvectorscanbereducedbyconstructingand
storingafrequencytable,orhistogram,oftheattribute
valuesforeachattributeofeachrelation.
➢Figure21.1showsanexampleofahistogramforan
integer-valuedattributethattakesvaluesintherange1
to25.

16. 21.3 InterqueryParallelism
➢Ininterqueryparallelism,differentqueriesor
transactionsexecuteinparallelwithoneanother.
➢Transactionthroughputandscaleupcanbeincreased
bythisformofparallelism.
➢Interqueryparallelismistheeasiestformof
parallelismtosupportinadatabasesystem-
particularlyinashared-memoryparallelsystem.Lock
tablesandLoginformationaremaintainedinthesame
memory.
➢Supportinginterqueryparallelismismorecomplicated
inashared-diskorsharednothingarchitecture.

17. 21.3 InterqueryParallelism
➢Processorshavetoperformsometasks,suchas
lockingandlogging,inacoordinatedfashion,andthat
requiresthattheypassmessagestoeachother.
➢Aparalleldatabasesystemmustalsoensurethattwo
processorsdonotupdatethesamedataindependently
atthesametime.
➢Whenaprocessoraccessesorupdatesdata,the
databasesystemmustensurethattheprocessorhasthe
latestversionofthedatainitsbufferpool.The
problemofensuringthattheversionisthelatestis
knownasthecache-coherencyproblem.

18. 21.4 IntraqueryParallelism
ItistheformofparallelismwhereSingleQueryis
executedinparallelonmanyprocessors.
Advantages
➢Tospeedupasinglecomplexlongrunningqueries.
➢Bestsuitedforcomplexscientificcalculations
(queries).
SupportedParallelDatabaseArchitectures
SharedMemory,SharedDiskandSharedNothingparallel
architecturesaresupported.
Weneednotworryaboutlockingandloggingasbecause
itinvolvesparallelizingsinglequery.

19. 21.4 IntraqueryParallelism
Types
Intra-operationparallelism–theprocessofspeedingupa
querythroughparallelizingtheexecutionofindividual
operations.
TheoperationswhichcanbeparallelizedareSort,Join,
Projection,Selectionandsoon.
Inter-operationparallelism–theprocessofspeedingupa
querythroughparallelizingvariousoperationswhicharepart
ofthequery.
Forexample,aquerywhichinvolvesjoinof4tablescanbe
executedinparallelintwoprocessorsinsuchawaythateach
processorshalljointworelationslocallyandtheresult1and
result2canbejoinedfurthertoproducethefinalresult.