Systeemarchitecturen en opslag van gegevens
Deel 2: organisatie van gestructureerde gegevens
Dr. Wilfried Lemahieu
[email protected]
Organisatie van gestructureerde gegevens
• Record-organisatie • Bestandsorganisatie • Database-organisatie
1
Record-organisatie • Record-organisatie betreft de organisatie van data items in stored records. • Methoden: – Relative location – Embedded identification – Gebruik van pointers en lists
Relative location • Er worden enkel attribuutwaarden opgeslagen. • De data items die hiertoe worden gebruikt en die waarden beschrijven van de respectieve attributen van een entiteit, worden geïmplementeerd door middel van adressequentiële data directe opslagstructuren. • De naam van het attribuut waarvan een waarde is geregistreerd, is impliciet bepaald door de relatieve volgorde waaronder die waarde in de verzameling waarden voorkomt. • Zo wordt ieder data item geïdentificeerd aan de hand van zijn relatieve locatie.
2
Relative location 155-9211351-47 Smith R. Charlotte Street 117 London WC1 Data item dat de attribuutwaarde voor het attribuut Social security number voorstelt
Data item dat de attribuutwaarde voor het attribuut Employee name voorstelt
Data item dat de attribuutwaarde voor het attribuut Employee address voorstelt
Create table Employee (SSNR … Employee name … Employee address … … );
Embedded identification • Er worden zowel attribuutnamen als attribuutwaarden opgeslagen (waarbij de naam telkens voorafgaat aan de waarde). • De data items die hiertoe worden gebruikt en die namen en waarden beschrijven van de respectieve attributen van een entiteit, worden geïmplementeerd door middel van adressequentiële data directe opslagstructuren. • De naam van het attribuut waarvan een waarde is geregistreerd is expliciet aanwezig.
3
Embedded identification
SSNR 155-9211351-47 Name Smith R. Address Charlotte Street 117…
Pointers en lists • Er worden enkel attribuutwaarden opgeslagen. • De data items die hiertoe worden gebruikt en die waarden beschrijven van de respectieve attributen van een entiteit, worden geïmplementeerd door middel van pointersequentiële data directe opslagstructuren.
4
Pointers en lists 155-9211351-47 Smith R. Adres 1 160-3514692-18 Gallup S. Adres 1 …
Adres 2 Adres 2 Adres 3
Vaste - variabele woordlengte records • •
Indien ieder record in de file dezelfde woordlengte bezit, spreken we van een bestand met vaste woordlengte. Variabele woordlengte records kunnen het gevolg zijn van: – Het bestaan van variabele woordlengte data items, bijvoorbeeld van het type varchar – Het bestaan van een onbepaald aantal waarden voor een attribuut van een entiteit, waardoor zich een herhalende groep vormt binnen het record, waarvan de woordlengte bepaald wordt door de aantallen waarden in die groep – Het bestaan van attributen die slechts toepasselijk zijn bij een subset van de entiteiten van een entiteittype
•
Het is uiteraard mogelijk om een bestand dat logischerwijze variabele woordlengte records zou bevatten, te implementeren d.m.v. vaste woordlengte records.
5
Vaste - variabele woordlengte records Vaste woordlengte:
Variabele woordlengte:
F1
F2
F3
F4
L1
L2
L3
L4
F1 $
F2
$ F3 $
F4 ($ = delimiter)
F1
F2
F3
F4
Bestandsorganisatie Bestandsorganisatie betreft het organiseren van stored records in physical files of data sets. We maken een onderscheid tussen twee categorieën van bestandsorganisatiemethoden: – Methoden die enkel gebruik maken van de primaire sleutel om gegevens te localiseren – Methoden die gebruik maken van één of meer secundaire sleutels om (een) record(s) te localiseren, gedefinieerd in een query
6
Primary key, secondary key en non-key • Primary key: data item dat op unieke wijze één bepaald stored record identificeert. Er bestaan geen twee records met gelijke primary key waarden in een bestand. • Secondary key: data item dat kan gebruikt worden als toegang (index) naar records, zonder dat het hen uniek identificeert (omdat dezelfde waarde voor meer dan één record kan voorkomen). • Non-key: data item dat niet als primaire, noch als secundaire sleutel gebruikt wordt voor het zoeken naar records.
Record access-methoden gebaseerd op de primaire sleutel •
•
Scanning: de exacte locatie van het gezochte record is niet gekend. De enige mogelijkheid is dan (een deel van) het bestand te scannen tot men het betrokken record tegenkomt. Hierbij wordt telkens de primaire sleutel van het gezochte record vergeleken met de sleutels van de records in het bestand, tot men een "match" heeft. Addressing: gaat uit van de veronderstelling dat er één of ander verband bestaat tussen het record en diens locatie. Deze techniek is dan ook enkel bruikbaar als de data op een DASD zijn opgeslagen. Er bestaan drie basistechnieken: – Direct addressing – Indexed addressing – Key transformation (hashing)
7
Addressing • • •
Direct addressing: de primaire sleutel is het adres. Indexed addressing: maakt gebruik van een index van (primary key, adres) koppels. Key transformation (hashing): hierbij wordt de primary key op één of andere wijze getransformeerd tot een adres, waarop dan het record wordt opgeslagen. Merk op: soms levert een addresseringstechniek niet het exacte adres van een stored record op, maar slechts van een "gebied" waar een groep records is opgeslagen. Dergelijk gebied met records die samen geaddresseerd worden noemen we een bucket. Dergelijke bucket bestaat dan uit één of meer stored record slots.
Sequential file organisation •
Concept: In een sequentiële file, worden records één na één opgeslagen op een opslagdevice, volgens stijgende of dalende volgorde van de primary key.
•
Parameters: – NBLK = (NR / EBF) – EBF =
•
( BKS − BOVHD ) × LF SRS
Verwerking van sequentiële files: – PBA (get unique, seq search) = (1 + NBLK)/2 sba – PBA (get unique, binary search) = log 2
NBLK rba 2
– PBA (get all) = NBLK sba
8
Sequential file organisation: een voorbeeld •
Gegeven: – – – – –
•
NR = 30.000 BKS = 1024 bytes SRS = 100 bytes BOVHD is verwaarloosbaar LF is 100 %
Dan: – EBF = (1024/100) = 10 – NBLK = (NR/EBF) = 3000 – PBAseq= (1 + 3000)/2 = 1500 sba – PBAbin= (log2 1500) = 11 rba
Random file organisation • •
•
• •
Bij random file organisation krijgt men directe toegang tot een record, gebruikmakend van de (primaire) sleutel van dat record. In random files wordt hashing gebruikt om uit de (primaire) sleutel van een record het adres te berekenen van dat record. Daartoe wordt gebruik gemaakt van een sleutel-adres transformatiemethode. Doel is de sleutels (en bijgevolg de records) zo uniform mogelijk te spreiden over de beschikbare adressen. Enkel mogelijk bij opslag op een DASD. Als een hashing-schema voor twee sleutels tot hetzelfde disk adres leidt (synoniemen), spreekt men van een collision.
9
Functie van een hashing routine Primary key value of the record (symbolic address) Key-to-address transformation Relative block address OS address transformation Absolute block address
Streven naar een uniforme verdeling van records over de adresruimte • De term "random" organisatiemethode is misleidend. De doelstelling is niet de records volgens de principes van een random verdelingsfunctie te spreiden (waarbij elk record dezelfde kans heeft om aan gelijk welk adres te worden toegewezen), wel volgens een uniforme verdelingsfunctie. • Maar de verdeling die men met de methoden uit de praktijk kan bereiken benadert veel dichter wat men volgens een theoretisch random distributie kan bereiken dan de uniforme distributie waar men in feite naar streeft. Vandaar de naam "random" organisatiemethode.
10
Gevolg van synoniemen en collisions • NR: aantal records in de file of aantal te registeren records • M: aantal beschikbare adressen voor het opbergen van de records • TM: aantal verschillende adressen dat bij transformatie van de sleutels naar adressen wordt gegenereerd (stel bucket size is 1) • Ideaal: TM = NR = M • Praktijk: TM < NR < M wegens synoniemen
Key-to-address transformation Primary key value of the record (symbolic address) Conversion into numeric form Numeric form primary key value of the record Key-to-address algorithm Key-to-address algorithm block (bucket address) Fitting of block address in function of precise range of available addresses Relative block address
11
Factoren die het resultaat van een sleutel-adres transformatie beïnvloeden • • • •
De key set distributie De bucket size De loading factor De overflow handling techniek
Overflow handling Record
bucket adres ?
Synoniemen Als bucket reeds vol
overflowrecord
…
Open addressing: plaats overflowrecord in eerstvolgende bucket dat nog een vrij slot bevat
12
Performantiemaatstaven
• Verwachte percentage overflowrecords • Verwachte aantal bucket accesses om een record op te halen zet om naar verwachte aantal block accesses
Performantiemaatstaven 0
20
160
2
42
22
3
53
43
4
14
1 ID = 35 ID mod 10
LF = 0,45 5 Bucket size = 4 Open addressing 6 BF = 2
12
95
125
15
76
36
35
8
98
108
9
19
Retrieval accesses voor record met ID 35: 7 record slots 2 buckets 4 blocks (1 rba + 3 sba)
25
7
Record slot Block
Bucket
13
Key-to-address transformation algorithms • • • •
Division Digit analysis Mid-square Folding – Fold-boundary – Fold-shifting
• Base transformation
Division
• De primary key wordt gedeeld door een positief geheel getal, meestal een priemgetal. De rest na deling vormt het adres voor het record.
14
Reeks 1
Reeks 2
Record key Deling door Deling door Record key Deling door Deling door 20 23 20 23 3000 3001 3002 3003 3004 3005 3006 3007 3008 3009 3010 3011 3012 3013 3014 3015 3016 3017 3018 3019
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19
10 11 12 13 14 15 16 17 18 19 20 21 22 00 01 02 03 04 05 06
3000 3025 3050 3075 3100 3125 3150 3175 3200 3225 3250 3275 3300 3325 3350 3375 3400 3425 3450 3475
00 05 10 15 00 05 10 15 00 05 10 15 00 05 10 15 00 05 10 15
10 12 14 16 18 20 22 01 03 05 07 09 11 13 15 17 19 21 00 02
Digit analysis • De verdeling van elke cijferpositie in de primaire sleutel wordt geanalyseerd. De posities met de meeste "skew" worden weggelaten, todat het overige aantal cijfers past in de beschikbare adresruimte. Het criterium om de beste cijferposities voor addressering te zoeken is gebaseerd op de mate waarin de cijfers op die positie overheen alle primaire sleutelwaarden een uniforme verdeling vertonen.
15
Totaal aantal records: 16.045, te mappen naar adressen tussen 0 en 19.999
1 0
2
3
16045
1
4
Cijferpositie 5 6
7
8
9
10
11
1852
5168
1807
1738
1574
1597
1579
87 235
4408
3147
5638
2120
1748
1652
1651
1599
2
2198
3792
1174
4958
1745
1743
1587
1569
1604
334
3
576
2231
2724
281
1684
1610
1620
1576
1603
9371
Cijfer 4 5
1195
2459
1194
1378
1617
1647
1652
1619
3164
12076
3155
1267
1647
1688
1580
1605
1645
1939
6
1243
1560
1606
1538
1611
1625
565
7
1228
1329
1450
1560
1598
1557
253
8
1227
1415
1411
1630
1618
1622
76
9
989
1360
1434
1657
1568
1592
21
Gebruik posities 7, 8, 9 en 10. Bijvoorbeeld: de sleutelwaarde 05282412983 wordt gemapt naar adres 01298
Evaluatie van de verschillende technieken •
•
•
•
Alle transformatietechnieken vertonen dezelfde trend: het verwachte aantal bucket accesses nodig om een record op te halen en het verwachte percentage overflowrecords stijgen wanneer de loading factor stijgt en dalen wanneer de bucket size stijgt. Overflowrecords in de prime area zijn zeer inefficiënt bij een lage bucket size. Het kan wel efficiënt zijn om overflowrecords in de prime area te bewaren bij een hoge bucket size. De "eenvoudige" division methode geeft de beste gemiddelde resultaten. Ze geeft (zelfs) licht betere resultaten dan random transformation, maar sluit er dicht bij aan. Algemeen gezien zal het gedrag van "goede" transformatie algoritmes op werkelijke bestanden lichtjes beter zijn dan, maar zeer nauw aansluiten bij, een perfecte random transformatie. Een systeemontwerper die een bestand ontwerpt, kan de random transformatie-berekeningen dan ook als zeer accurate vuistregel gebruiken om het percentage overflowrecords te schatten.
16
Verwachte waarden op basis van een random mapping Assumptie: volmaakt random mapping van NR records naar NB buckets −
pk =
e
NR NB
NR k ) NB k! (
met k = 0, 1, 2, ... ∞
•
Verwachte aantal buckets in overflow: NB ∑ pk k =b +1
∞
•
Verwachte aantal overflowrecords: NB ∑ pk (k − b) k =b +1
•
Verwachte percentage overflowrecords:
100 NB ∞ ∑ pk ( k − b ) NR k =b +1
Voorbeeld •
Gegeven: – – – –
NR = 40.000 NB = 5.000 b = 10 Addressering per track, volgens een volmaakt random transformatie
• • •
NR/NB = 8 LF = NR/(b x NB) 0,8 p0 = 0,0003; p1 = 0,0027; … p11 = 0,0722; p12 = 0,0481; …
•
Verwacht aantal buckets/tracks in overflow: 5000 x (0,0722+0,0481+0,0296+…) = 920 Verwacht percentage tracks in overflow: 18,4 Verwacht aantal overflowrecords: 5000 x [(0,0722 x 1) + (0,0481 x 2) + (0,0296 x 3) +…] = 2.127 Verwacht percentage overflowrecords = 5,32
• • •
17
Random file ontwerp in de praktijk • • • •
De sleutel-adres transformatie techniek is veelal een gegeven (inherent aan de software). De methode voor het opbergen van overflowrecords is veelal een gegeven (inherent aan de software). De bucket size is veelal indirect bepaald door track-capaciteit en woordlengte van de records. Bijgevolg bestaat de enige vrijheidsgraad die er veelal voorkomt in het bewerken van de load factor. – Lage LF: • Gering aantal verwachte bucket toegangen voor het ophalen van een record en dus lage consultatiekosten. • Minder goede benutting van de opslagcapaciteit en dus hoge opslagkosten
– Hoge LF: • Groter verwacht aantal bucket toegangen voor het ophalen van een record en dus hogere consultatiekosten • Betere benutting van de opslagcapaciteit en dus lagere opslagkosten
•
Conclusie: bereken de optimale LF die de totaalkosten minimaliseert !
Dynamic hashing •
Probleem: de adresruimte met de reeks van adressen die bij toewijzing mogen worden gebruikt moet initieel worden bepaald. Wanneer na verloop van tijd veel meer adressen nodig blijken (veel toevoegingen) of wanneer een veel geringer aantal adressen zou volstaan (veel verwijderingen), moet de sleutel-adres transformatie-methode worden aangepast, hetgeen aanleiding zal geven tot het opnieuw moeten laden van de file.
•
Oplossing: dynamic hashing – Extensible hashing – Linear hashing
18
Indexed sequentiële bestandsorganisatie • •
•
De indexed sequentiële bestandsorganisatie vormt een compromis tussen sequentiële en directe toegang. De records zijn één na één opgeslagen in stijgende (of dalende) volgorde van hun primaire sleutel. Daarnaast zijn de records echter ook geïndexeerd. Hiertoe wordt het bestand opgedeeld in een aantal intervallen of partities. Voor elke partitie wordt bijgehouden: – De sleutel van het laatste record – De eerste record locatie die een record bevat dat tot de partitie behoort
•
Beide bovenstaande elementen worden opgeslagen in een index entry Het informatiesysteem laat zowel sequentiële als random-verwerking toe.
Simple index method • Bij de simple index method bestaat slechts een one-level index. Om een record op te halen uit het bestand, moet de index doorzocht worden om het interval te vinden waarin het record thuishoort. • Het overeenkomstige interval wordt dan gelezen en het record kan worden opgehaald. • De index entries bestaan uit de hoogste sleutel in een interval en het adres van het eerste data record in dit interval.
19
Address 00 Interval
01 02 03
02 05 06 07 11 13 17 19
Index Key
Addr
19 37
00 04
59 78 98
08 12 16
... 04 ... 07
37
... 08 ... 11
59
... 12 ... 15
78
... 16 ... 19
98
Berekeningen 1 + NRi • Get unique: PBA = ( NIL + 1) rba + ∑ ( 2 i =1 EBFi n
− 1) sba
NIL= number of index levels n = NIL+1 NRi = number of data or index entry records at level i
• Get all: PBA = NBLK sba
20
Voorbeeld simple index • Indexed sequential: 1+ 5 1+ 8 = (1 + 1) rba + ( 2 − 1) + ( 2 − 1) sba 50 2
PBA
= 2 rba + 2 sba • Sequential: PBA
= (1+NBLK)/2 = 10,5 sba
Multiple index method
• Wanneer de index zeer groot wordt, kan het nuttig zijn om een “index tot de index” te maken: een tweede, hogereniveau index. • In de praktijk kunnen tot 5 indexniveaus voorkomen.
21
50
0105
51
0212
52
0307
50
53
0414
53
54
0638
55
1215
56
1312
57
1725
58
1869
59
59
1935
62
60
2001
61
2041
62
2142
63
2677
64
2895
68
65
2933
71
66
3413
67
3572
68
3591
69
3617
70
3688
Index 10
0307 1215 1869
56
Index 00
1869 3572 5432
10
20
20
2041 2895
30
3572
30
3688 4237 5432
65
74
...
Voorbeeld multiple index levels
PBA
=
1+ 3 1+ 3 1+ 3 2 2 2 − 1) + ( − 1) + ( − 1) sba (2 + 1) rba + ( 50 50 1
= 3 rba + 1 sba
22
Implementaties van de indexsequentiële bestandsorganisatiemethode in de praktijk • ISAM (Index Sequential Access Method) • VSAM (Virtual Storage Access Method)
ISAM (Index Sequential Access Method) • De records worden gegroepeerd (en de indexen worden ontworpen) om te passen op tracks en cylinders van een disk unit. • ISAM files bestaan uit drie areas: – Prime area: bevat de eigenlijke records – Overflow area: bevat nieuw toegevoegde records, die niet meer pasten in de prime area – Indexes: bestaan uit 2 of 3 niveaus: • Track index • Cylinder index • Master index
23
Cylinder index 00610 0000
03975 0200
05432 0300
…
Normal
Overflow
Normal
Overflow
00014 0001
00014 0001
00027 0002
00027 0002
01500 0100
DUM MY
Track index 0000
COCR
…
…
Normal
Overflow
00610 0040
00610 0040
Normal
Overflow
DUM MY
Prime data area 00011
00014
00020
… …
00025
00027
00598
…
00605
00610
0001
00001
00003
00004
00006
0002
00016
00017
00019
00591
00594
00597
… 0040
Overflow • Nieuw toe te voegen records worden naar de overflow area(s) geschreven wanneer niet voldoende ruimte beschikbaar is op de prime data track. • Er worden twee types overflow area gebruikt: – Cylinder overflow area (locale overflow area) Als een cylinder overflow area is gespecificeerd, wordt het eerste record van de track index gebruikt als Cylinder Overflow Control Record (COCR). Hierin wordt het laaste overflowrecord in de cylinder aangegeven en het aantal bytes dat beschikbaar blijft in de cylinder overflow area. – Independent overflow area (globale overflow area)
24
Keuze van het type overflow area • Enkel independent overflow area: de verwerking is voornamelijk transactie-georiënteerd en het aantal toevoegingen is laag en sterk geclusterd op een klein deel van het bestand. • Enkel cylinder overflow area: wanneer de toevoegingen gelijkmatig verdeeld zijn overheen het gehele bestand. • Zowel independent overflow area als cylinder overflow area: – Als middel om te bepalen wanneer reorganisatie vereist is – Als een middel om al te frequente reorganisaties tegen te gaan wanneer er veel toevoegingen zijn in het bestand en wanneer de verdeling van de toevoegingen verre van gelijkmatig is
Overflow records Normal entry
Overflow entry
Highest key on track
Track address
Highest key in overflow
Address of first overflowrecord
Key area
Data area
Key area
Data area
25
Cylinder index 00610 0000
03975 0200
05432 0300
…
Normal
Overflow
Normal
Overflow
00011 0001
00014 00431
00027 0002
00027 0002
01500 0100
DUM MY
Track index 0000
COCR
…
Prime data area 0001
00001
00003
00004
00006
0002
00016
00017
00019
00020
…
00009
…
00010
00011
00025
00027
Overflow area 00411
…
0041 00431 00014 0001
0043
…
00441
00442
00443
…
0044
Cylinder index 00610 0000
01500 0100
03975 0200
…
05432 0300
DUM
MY
Track index 0000
COCR
Normal
Overflow
Normal
Overflow
00011 0001
00014 00443
00027 0002
00027 0002
…
Prime data area 0001
00001
00003
00004
00006
0002
00016
00017
00019
00020
…
00009
…
00010
00011
00025
00027
Overflow area 00411
…
0041
0043
00431 00014 0001 00441
0044
… 00442
00443 00013 0431
…
26
Verwerken van ISAM-files • • • • • • • • • • •
Doorzoek de cylinder index om de cylinder te zoeken die het record bevat (verwaarloosbaar als de cylinder index zich in het werkgeheugen bevindt). Plaats de R/W head op de juiste cylinder (één armbeweging). Wacht tot het beginpunt van de track index zich onder de leeskop bevindt (gemiddeld 1/2 omwenteling). Lees de track index van het eerste track (transfer-tijd van track index). Zoek in de track index naar het track dat het record bevat (verwaarloosbaar). Selecteer het gewenste track (verwaarloosbaar) en wacht tot het gewenste block zich onder de leeskop bevindt (gemiddeld 1/2 omwenteling). Lees het block dat het gezochte record bevat (transfer-tijd van één block). Update het record in het werkgeheugen (en herpositioneer eventueel de arm als deze intussen verplaatst was). Wacht tot de juiste positie onder de schrijfkop komt (gemiddeld 1/2 omwenteling). Schrijf het block terug naar zijn oorspronkelijke positie op de schijf (transfer-tijd van één block). Wacht een volledige omwenteling om het resultaat te herlezen voor een “write check” (1 omwenteling).
Totaal: 1 armbeweging + 2,5 omwentelingen + transfer-tijd voor 2 data blocks + transfer-tijd voor track index
VSAM (Virtual Storage Access Method) VSAM biedt net als ISAM een index-sequentiële bestandsorganisatiemethode. Ze vertoont echter volgende verschillen tegenover ISAM: – Hardware-onafhankelijk (de indexering is gebaseerd op control areas en control intervals in plaats van op cylinders en tracks) – Meer efficiënte behandeling van insertions en deletions dankzij de mogelijkheid om control areas en control intervals op te splitsen
27
List data-organisatiemethodes • Voor het realiseren van sequentiële datastructuren – One-way linked list – Two-way linked list
• Voor het realiseren van boom-datastructuren – Contiguous list – One-way linked list – Two-way linked list
• Voor het realiseren van plex-datastructuren – Contiguous list – Linked list
List data-organisatiemethodes • Definitie van list: “een geordende verzameling van elementen” • Linear list: geordende verzameling van elementen waarbij ieder element exact één volgende element bezit – Sequentiële datastructuren
• Non-linear list: elke andere list die niet voldoet aan bovenstaande eigenschap – Boom-datastructuren – Plex-datastructuren
28
Linear lists • Een linear list vormt een sequentiële datastructuur • Opslaan met behulp van – Adres-sequentiële opslagstructuur (physical contiguous list) sequentiële organisatiemethode – Pointer-sequentiële opslagstructuur (linked list) one-way linked list organisatiemethode two-way linked list organisatiemethode
One-way linked list organisatiemethode Embedded pointers
10 B
14 A
11 15
E
15 10
C
12 12
F
16 16
D
13 13
G
17 11
H
17
18 18
I
*
29
One-way linked list organisatiemethode Directory pointers 10
11
12
13
B
E
F
G
14
15
16
17
18
A
C
D
H
I
14 10 15 16 11 12 13 17 18
*
Directory
One-way linked list organisatiemethode Gecombineerd met indexed addressing
10 B
14 A
Address
C F I
14 16 13
11 15
E
15 10
Key
C
12 12
F
16 16
D
13 13
G
17 11
H
17
18 18
I
*
30
Verwerken van one-way linked lists • •
PBA(get all) = NR rba PBA (get unique) = (1+NR)/2 rba
•
(1 + NRi ) Met index: n 2 PBA(get unique) = n rba + ∑ − 1 rba i =1 EBFi NIL = number of index levels n = NIL+1 NRi = Number of data or index entry records at level i
•
Let op: allemaal rba !!!
Toevoegen van records 14 A
15 10 15
C
16 16
D
10 B
15
1. Lokaliseren van het record dat logisch volgt op het in te voegen record (C in het voorbeeld). Verwacht aantal zoekpogingen: (1+NR)/2 rba. 2. Indien het record in hetzelfde block zou kunnen worden opgeborgen als het block waar ook C in voorkomt is er geen probleem. Meestal zal het nieuw toe te voegen record echter in een apart nieuw block moeten opgeborgen worden (in het voorbeeld op adres 10), wat 1 random write vraagt. 3. Het nieuwe record wordt op het nieuwe adres geregistreerd en het adres van het record dat er logisch op volgt (dit adres is intussen gekend: 15) wordt in het pointerveld van het nieuwe record opgenomen. 4. Overigens moet nu nog het adres van het record dat logisch voorafgaat aan B bekend zijn om het adres van B in zijn pointerveld te kopiëren (10 i.p.v. 15).
31
Verwijderen van records 1. 2.
3.
4.
Lokaliseren van het record dat verwijderd moet worden. Verwacht aantal zoekpogingen: (1+NR)/2 rba. Indien de delete-opdracht er enkel in bestaat om het te verwijderen record te merken als zijnde logisch geschrapt, dan volstaat een rewrite van het block waarin dit record voorkomt (anders: …). Adres vinden van het record dat logisch voorafgaat aan het te schrappen record. Pointer in het te schrappen record kopiëren naar pointerveld van dat record. Fysisch schrappen van betreffende record. Merk op: als pointerbeschadiging optreedt, gaat de logische volgorde van de records verloren.
Two-way linked list organisatiemethode 10
11
14 B
14 18 A
15
12
16 E
15 10
10 C
12
13
11 F
16 16
15 D
13
12 G
17 11
13 H
17
18 18
17 I
14
32
Toevoegen van records 14 18 A
15 10 15
16
10 14 C
16
15 D
11
10 14 B
1. 2.
3.
4.
15
Lokaliseren van het record dat logisch volgt op het in te voegen record. Verwacht aantal zoekpogingen: (1+NR)/2 rba. Indien het in te voegen record in hetzelfde block zou kunnen worden opgeborgen als het block waar ook het record voorkomt dat er logisch op volgt is er geen probleem. Meestal zal het nieuw toe te voegen record echter in een apart nieuw block moeten opgeborgen worden. Stel: het in te voegen record (B) wordt opgeslagen in een nieuw block op adres 10. Dit vraagt 1 random write. De prior pointer uit C kopiëren in het "terugwaarts" verwijzingsveld van B (14) en de next pointer uit A (waarvan het adres reeds bekend is) kopiëren in het "voorwaarts" verwijzingsveld van B (15). Het record B registreren vraagt 1 random write. Het adres van het nieuwe record (10) kopiëren in het "voorwaarts" verwijzingsveld van A en in het "terugwaarts" verwijzingsveld van C vraagt 1 random read en 1 sequential write (voor A) en nog eens 1 random read en 1 sequential write (voor C).
Verwijderen van records 1. Lokaliseren van het record dat verwijderd moet worden. Verwacht aantal zoekpogingen: (1+NR)/2 rba. 2. Indien de delete-opdracht er enkel in bestaat om het te verwijderen record te markeren als zijnde logisch geschrapt, dan volstaat een rewrite van het block waarin dit record voorkomt (anders: …). 3. De records vinden die logisch voorafgaan aan en volgen op het te schrappen record. De prior pointer in het te schrappen record kopiëren naar het "terugwaarts" verwijzingsveld van het record dat logisch op dat record volgt. De next pointer in het te schrappen record kopiëren naar het "voorwaarts" verwijzingsveld van het record dat logisch aan dat record voorafgaat (telkens 1 rba en 1 sba). 4. Eventueel fysisch schrappen van betreffende record. Als pointerbeschadiging optreedt (bv. in het "voorwaarts" verwijzingsveld), dan kan het volgorde-verband gerecupereerd worden dankzij de pointers in de andere richting.
33
Boomdatastructuren (tree data structures) Een boomdatastructuur is een verzameling van knooppunten (nodes) en verbindingen (branches, edges) met volgende kenmerken: – Er is 1 speciaal knooppunt dat we het root-knooppunt noemen. – Ieder knooppunt (met uitzondering van het root-knooppunt) heeft 1 parent knooppunt. Ieder knooppunt heeft 0, 1 of meer child-knooppunten. – Een knooppunt dat zelf geen child-knooppunten heeft is een leaf node. – De knooppunten zijn verdeeld over een aantal niveaus (levels). Het niveau van het root-knooppunt is 0. Het niveau van een ander willekeurig knooppunt is 1 hoger dan dit van zijn parent.
Boomdatastructuren (vervolg) – Een subboom (subtree) bestaat uit een knooppunt tesamen met al zijn afstammelingen (descendants); dat zijn zijn child nodes, de child nodes van zijn child nodes enz. – Een verzameling van knooppunten die allen dezelfde parent delen zijn twins of siblings. – De in-degree van een knooppunt is het aantal verbindingen dat in dit knooppunt eindigt (de in-degree van een child knooppunt is 1). – De out-degree van een knooppunt is het aantal verbindingen dat uit dat knooppunt ontspringt (de out-degree van een parent knooppunt is n).
34
Binaire boomstructuur • Een belangrijke klasse van boomdatastructuren is de binaire boomstructuur. • Een binaire boomstructuur is een eindige verzameling van knooppunten die – Ofwel leeg is – Ofwel 2 disjuncte binaire bomen omvat die zijn linker- en rechter- subtrees worden genoemd
• De maximale out-degree van eender welk knooppunt is gelijk aan 2.
Toepassingsgebieden van boomdatastructuren • Toepassingen op logisch vlak: de objecten zelf zijn boomgestructureerd. – De objecten die van de verzameling deel uitmaken behoren tot dezelfde klasse (vb.: hiërarchische verantwoordelijkheden van werknemers binnen een organisatie) – De objecten die van de verzameling deel uitmaken komen uit meerdere klassen (vb.: hiërarchische verbanden tussen leveranciers en aankooporders)
• Toepassingen op fysiek vlak: hier gaat het over implementaties van boomdatastructuren die enkel bedoeld zijn om het zoeken naar bepaalde objecten te kunnen versnellen (vb.: gebruik van B-tree voor het zoeken naar een werknemer-object uit een verzameling werknemers).
35
De representatie van boomdatastructuren • Door middel van contiguous lists contiguous physical positioning method • Door middel van linked lists one-way linked list method two-way linked list method (= child-and-twin pointer method)
Contiguous physical positioning method A B
D
E
F
J
A
0
C
B
1
1
G
C
G
K
D
2
2
H
H L
E
2
2
L
M
J
3
I
3
M
K
3
3
I
F
2
2
36
One-way linked list method A B
D
E J
F
C
G
K
H L
I M
05 A
1
06 B
12 1
07 D
08 0
08 E
11 1
09 J
10 0
10 K
0
11 F
0
12 C
1
13 G
14 0
14 H
17 1
16 M
0
15 L
16 0
17 I
0
Two-way linked list method • Child en twin-pointers
• Child en twin-pointer techniek uitgebreid met parent pointers
37
Methoden voor het ophalen van gegevens op basis van secundaire sleutels
Definitie van secundaire sleutel “Gegevenselement binnen een record waarvan de waarde door meerdere records kan worden gedeeld terwijl opvraging van records op basis van zo’n waarde mogelijk is.” Het opvragen van zo’n gegevens zal typisch gebeuren met een query language. Dé belangrijkste query language is SQL (Structured Query Language). Algemeen formaat van SQLopdrachten: SELECT … FROM … WHERE ...
38
Voorbeeld van een SQL-query Select naam, adres from werknemer where woonplaats = “Leuven”
Qualification part van een query •
< Atomic conditions (AC): attribuutnaam Zijn van de vorm: attribuutnaam = >
waarde
•
Item conditions (IC): – Disjunctie van atomic conditions: AC1 or AC2 or … ACp, waarbij elke ACi naar hetzelfde attribuut refereert, maar met een verschillende waarde – Anderzijds kan een item condition ook bestaan uit de verzameling van attribuutwaarden in een interval: Salaris = 1000 - 1999 is equivalent met Salaris = 1000 or salaris = 1001 or … salaris = 1999
•
Record conditions (RC) Bestaan uit een conjunctie van item conditions: IC1 and IC2 and … ICq
•
Query condition (QC) Bestaat uit een disjunctie van record conditions: RC1 or RC2 or … RCp
39
Qualification part van een query: voorbeeld Select naam, adres from werknemer where (woonplaats = “Leuven” and bruto-salaris between 150.000 and 200.000) or (woonplaats = “Brussel” and bruto-salaris between 100.000 and 150.000)
Secondary index organisation • Algemeen gezien halen query' seen variabel aantal records op. Omdat data normaal gezien niet geordend zijn volgens secundaire sleutels, zijn de zoekmechanismen die gebaseerd waren op de primaire sleutel hier niet efficiënt. • Alle methoden voor het ophalen van gegevens op basis van secundaire sleutels hebben als gemeenschappelijk kenmerk dat ze gebruik maken van “secondary index files” (zo genoemd omdat ze secundaire sleutels indexeren), eventueel aangevuld met hulpdata in de records.
40
Single-key (separate) indexing
Multilist file organisation method •
Concept: de multilist file organisation method definieert een verzameling van linked sequentiële structuren (linked lists), waarbij elke linked list records met elkaar verbindt die dezelfde waarde voor een bepaald data item type bevatten. De lists zijn geïndexeerd om snellere toegang tot de records met dezelfde secondary key waarden mogelijk te maken.
•
De multilist file organisation method heeft twee belangrijke eigenschappen: – De functie van de lowest level secondary index is een record bestaande uit het volgende triplet: sec. key value code / head of list address / list length. – Alle records die voldoen aan dezelfde secondary key waarde (voor een bepaald data item type) worden aan elkaar gelinkt met behulp van pointers.
Voorbeeldbestand: een werknemersbestand • 3 secundaire sleutels K1, K2, K3 • Met volgende waarden: K1: K11, K12, K13, … K2: K21, K22, K23, … K3: K31, K32, K33, … • Voorbeeld: – K1: departementsnummer – K2: diplomacode – K3: salaris
K11: 119 K21: AD K31: 1000 - 1500 EUR
41
Voorbeeld van de multilist file organisation method • K11: departement = 119 • K21: diplomacode = AD • K31: salaris = 1000-1500 K11/A01/12
K21/A04/3
01
0
22
2
04 16
17
1
14
05 11 12
24 31
3
K31/A05/3
34
37
Verwerking van een multilist file • •
•
•
Query met 1 IC: de records van de list, aangeduid door de laagsteniveau index entry, voldoen allen volledig. Vb.: K11. Query met meer dan 1 IC (1 RC): de zoekstrategie komt er op neer om elke laagste-niveau index entry te localiseren die geassocieerd is met een item condition. Daarna wordt bepaald welke lijst de kortste is. Enkel deze laatste wordt doorzocht. Elk record in deze lijst wordt opgehaald en in het werkgeheugen onderzocht voor een correcte conjunctie van item conditions, en wordt ofwel “onthouden” ( als het aan de gehele RC voldoet) ofwel “vergeten”. Vb.: K 11 and K31. Query met meer dan 1 RC: de zoekstrategie bestaat erin om de set met target records voor elke RC te bepalen en dan de lijsten te “mergen” in de volgorde waarin de resultaten best getoond worden. Dubbels worden verwijderd tijdens het mergen. Vb.: K11 or K21. Query met negatie-termen: uit de lijst met adressen van records die voldoen aan de non-negated key worden de records verwijderd die voldoen aan de negated key. Vb.: K11 and not K31.
42
Retrieval time bij multilist file organisation •
Om de retrieval time te evalueren, moeten we een onderscheid maken tussen – De benodigde tijd om de higher-level indexen te decoderen – De benodigde tijd om de lower-level indexen te doorzoeken – De benodigde tijd om de target records op te halen
•
Assumpties: – Indexen worden sequentieel doorzocht, ze worden verondersteld geordend te zijn – Higher-level indexen worden verondersteld zeer klein te zijn, zodat ze passen in één block
Parameters • • • • •
PBA: physical block accesses, rba of sba TRBA, TSBA NIV: gemiddelde aantal mogelijke waarden per sleutel NRIV: verwachte aantal records dat een bepaald sleutelwaarde bevat (= gemiddelde list-lengte voor een multilist) EBF: effective blocking factor ( BKS − BOVHD ) × LF stored record size BKS − BOVHD) × LF ( • EBF2 = index entry size • EBF1 =
43
Retrieval time bij multilist file organisation •
Single atomic condition 1 rba
higher level index search
NIV + 1 + 1 rba + − 1 sba lowest level index scan 2EBF2 + NRIV rba data record search
•
Single item condition with p atomic conditions
EBF2
[1 rba ]+ 1 rba + (NIV - p + 1) + 1 − 1 sba + ( p − 1) sba + ∑ NRIVi rba •
2EBF2
p
i =1
where p ≥ 1
Multiple (q) item conditions with multiple (p) atomic conditions PBA(q IC, p AC/IC) = q
j =1
pj (NIVj - p j + 1) + 1 ( p j − 1) (∑ NRIVij ) rba − 1 sba + sba + min 2EBF2 EBF2 j i =1
[1 rba]+ ∑ 1 rba +
Single atomic condition I 1 rba
II
NIV + 1 ba 2 EBF2 ... of NIV + 1 1 rba + ( − 1) sba 2 EBF2
III NRIV rba
44
Single item condition met p atomic conditions •
•
Om de eerste index entry te vinden die zich kwalificeert in verband met de vraag moet uiteindelijk gezocht worden in een verzameling van NIV - (p - 1) waarden (of ranges van waarden). Bij sequentieel zoeken daarbinnen wordt het verwachte aantal zoekpogingen voor het vinden van die eerste entry als volgt bepaald: ( NIV − p + 1) + 1 ( NIV − p + 1) + 1 of in block accesses : 2 2 EBF 2 of, rekening houdende met de aard van de vereiste block - accesses :
•
•
( NIV - p + 1) + 1 1 rba + ( − 1) sba 2 EBF 2 Hieraan moet nu nog een aantal sba worden toegevoegd voor het terugvinden van de andere p-1 index entries die zich kwalificeren: ( p − 1) sba EBF2 Aldus verkrijgen we de "head of list adressen" van p lists met records die zich allemaal kwalificeren: p
∑ NRIV
i
i =1
rba
Single item condition met p atomic conditions: resultaat 1 rba (NIV - p + 1) + 1 ( p − 1) + 1 rba + − 1 sba + sba 2EBF2 EBF2 p
+ ∑ NRIVi rba
met p ≥ 1
i =1
45
Single item condition met p atomic conditions: voorbeeld Select …from …where 1500 < salary <= 1800 Stel dat er 10 salary ranges zijn onderkend, telkens met een grootte van 100 EUR 1000 < salary <= 1100 1100 < salary <= 1200 1200 < salary <= 1300 1300 < salary <= 1400 1400 < salary <= 1500 1500 < salary <= 1600 1600 < salary <= 1700 1700 < salary <= 1800 1800 < salary <= 1900 1900 < salary <= 2000
Select …from … where 1500 < salary <= 1600 or 1600 < salary <= 1700 or 1700 < salary <= 1800 Query opgebouwd uit 1 item condition, samengesteld uit een disjunctie van p (3) atomic conditions
Multiple item conditions met één atomic condition • • •
PBA (q IC, 1 AC/IC) Voorbeeld: department = 119 and skillcode = "PL" Oplossing: – Zoeken in hogere-niveau indexen: 1 rba – Zoeken in lagere-niveau indexen:
q
j =1
(NIVj + 1) − 1 sba 2EBF 2
∑ 1 rba +
waarbij q het in de query gerefereerde aantal IC' s voorstelt enNIVj het verwachte aantal item values voor het item type j aanduidt. – Zoeken in de data file, alleen de records op de kortste lijst moeten worden onderzocht:
min (NRIV j ) rba j waarbij NRIVj = aantal records aanwezig in lijst j
46
Multiple item conditions met multiple atomic conditions • • •
PBA (q IC, p AC/IC) Voorbeeld: 1500 < Salary <= 1800 and department = 119 Oplossing: – Zoeken in hogere-niveau indexen: 1 rba – Zoeken in laagste-niveau indexen: bestaat uit een aantal fysieke block accesses om de eerste index entry voor een bepaalde item value te vinden, vermeerderd met de benodigde block accessen om de pj-1 volgende index entries van gewenste waarden voor ditzelfde item terug te vinden (pj duidt het aantal AC' s aan waaruit de IC j is samengesteld) q
j =1
(NIV j - p j + 1) + 1 ( p j − 1) − 1 sba + sba 2EBF EBF 2 2
∑ 1 rba +
– Zoeken in de data file: bestaat uit een aantal block accesses voor de records die voorkomen op lijsten voor deze IC waarvoor de som van de aantallen records die voldoen aan de bijbehorende AC' s het kleinst is pj ( ∑ NRIV ij ) rba min j i =1
Multiple record conditions • •
PBA (r RC) Voorbeeld:
•
Oplossing: r – PBA (r RC) = ∑ PBA (q IC , p AC / IC ) j
(1500 < salary <= 1800 and department = 119) or (2200 < salary <= 2500 and department = 220)
j =1
r – Sorteren en verwijderen van dubbels: PBA sort ∑ NTR j j1 = met NTRj = het aantal target records dat voldoet voor een RC j. – Bij gebruik van een "r-way" meng-sorteringsproces is dit aantal fysieke block accesses gelijk aan: r ∑ NTR j r j 1 PBA sort ∑ NTR j = 2 × NBLK × (1 + X min ) waarbij NBLK = = BF j =1 het aantal blocks voorstelt dat nodig is om het bestand van zich kwalificerende records te herbergen (bestand dat moet worden gesorteerd) BF is de hierbij veronderstelde blocking factor Xmin is de minimum waarde van X die voldoet aan rx >= NBLK
47
Werknemersbestand: kenmerken • • • • • • •
NR = 100.000 SRS = 200 bytes BS = 2000 bytes Overhead = 0 LF = 1
2000 = 10 EBF1 = 200
EBF2: Stel: key size = 6 bytes; pointer size = 4 bytes; length indicator = 5 bytes
2000 Index entry size = 15 bytes en EBF2 = = 133 15 • •
Stel: 3 secundaire sleutel data items department, skill code en salary Aantal verschillende sleutelwaarden voor ieder secundair sleutel data item: NIV(department) = 100 NIV (skillcode) = 50 NIV (salary) = 25*
* Bestaande uit intervallen van 100, in een gebied dat gaat van 1000 tot 3500
Voorbeeldquery 1 • •
Select … from … where skillcode = "PL" and department = 119 PBA (q IC, 1 AC/IC) q (NIVj + 1) 1 rba + ∑ 1 rba + ( NRIV j ) rba − 1 sba + min j j=1 2EBF2
• •
NRIV1 = NRIV(IC1) = NRIV(skillcode) = 100000/50 = 2000 NRIV2 = NRIV(IC2) = NRIV(department) = 100000/100 = 1000
•
Retrieval cost: (50 + 1) (100 + 1) 1 rba + 1 rba + − 1 sba + 1 rba + 2 × 133 − 1 sba + 1000 rba × 2 133 of 1003 rba
48
Voorbeeldquery 2 •
Select …from …where (department = 119 and skillcode = "PL") or (1500 <= salary < 1750 and skillcode = "PE")
•
PBA (2 RC) + PBA(sort) r
• PBA(r RC) = PBA(q IC, p AC/IC) ∑ j j=1
• • •
r = aantal record conditions q = aantal item conditions/record condition p = aantal atomic conditions/item condition
•
r PBA (sort) = PBA sort ∑ NTR j j=1
Voorbeeldquery 2 (vervolg) •
Het kwalificatie-gedeelte van de eerste RC komt overeen met de kwalificatie van de query condition van de voorgaande query 1. Wij concentreren ons op de oplossing van de tweede RC (1500 <= salary < 1750 and skillcode = "PE") en van de globale QC.
• • • •
NIV(skillcode) = 50 NRIV2 = NRIV(IC2) = NRIV(skillcode) = 100.000/50 = 2000 NIV(salary) = 25 3 100.000 = 12.000 NRIV1 = NRIV(IC1) = NRIVi = 3×
∑ i =1
•
25
Het verwachte aantal target records voor: RC1 = 1000 / 50 = 20 RC 2 =
2000 × 3 = 240 25
Totaal = 260
49
Voorbeeldquery 2 (vervolg) PBA(RC2) = PBA(q IC, p AC/IC) pj q (NIVj − p j + 1) + 1 p j − 1 1 rba + ∑ 1 rba + (∑ NRIVij ) rba − 1 sba + EBF sba + min j 2EBF2 i =1 j=1 2
(25 − 3 + 1) + 1 (50 + 1) 3 − 1 1 rba + 1 rba + − 1 sba + 133 sba + 1 rba + 2 ×133 − 1 sba + 2000 rba × 2 133
= 2003 rba + 1 sba PBA(RC1) = 1003 rba (zie query 1)
Voorbeeldquery 2 (vervolg) • • • •
•
Sorteren van de beide lijsten met zich kwalificerende records ten behoeve van het elimineren van mogelijke duplicaten Aantal target records: 240+20 = 260 r BF target records (assumptie) = 20 NTR j j =1 PBA(sort) = 2 x NBLK x (1+Xmin) waarbij NBLK =
∑
260 NBLK = = 13 20 2 X ≥ 13 ⇒ X min = 4
BF
• •
PBA(sort) = 2 x 13 x (1+4) = 130 sba I/O totaal = 1003 rba + 2003 rba + 1 sba + 130 sba = 3006 rba + 131 sba = …
•
Bij sequentiële organisatiemethode: PBA = (100.000/10) = 10000 sba = …
50
Inverted list file organisation method Het grote nadeel van de multilist-benadering is de noodzaak om, bij een RC bestaande uit multiple IC, alle records aan te spreken in de kortste lijst, zelfs als slechts een kleine subset van de records in deze lijst aan de totale RC zal blijken te voldoen. De inverted list file organisation method lost dit probleem op door alle links uit de eigenlijke data records te verwijderen en de volledige lijst van pointers in pointer arrays te plaatsen, m.a.w. inverted lists te creëren. Het aantal pointers is hetzelfde, maar hun plaatsing is geclusterd in deze pointer arrays, ook accession lists genoemd.
Inverted list file organisation method: voorbeeld K11/X99/12
K21/Y99/3 Y99
X99
01 17 22 31
Z99 A04, A11, A14
A01, A04, A05, A12, A14, A16, A17, A22, A24, A31, A34, A37
K31/Z99/3 A05, A12, A24
04 14
16
05 12
24 34
Voorbeeld: query with 2 item conditions (K11 and K31)
37
A05, A12, A24
51
Evaluatie van de inverted list organisatiemethode • • •
•
EBF2 = Effective blocking factor van de index entries (cfr. multilist organisatiemethode) EBF3 = Effective blocking factor voor de accession list met pointers (dus het aantal record-adressen dat per block kan worden opgeslagen) NTR = "Number of Target Records"; het aantal records dat uiteindelijk voldoet aan de gevraagde kwalificaties Volgende aspecten komen aan bod bij het schatten van het benodigde aantal block accesses: -
Doorzoeken van higher-level indexen Doorzoeken van de lowest-level index Doorzoeken van de accession list(s) Ophalen van de eigenlijke data records
Evaluatie van de inverted list organisatiemethode (vervolg) •
Query met single atomic condition:
2 EBF2
NRIV sba + 1 rba + − 1 sba + [NRIV rba ] EBF3
[1 rba ]+ 1 rba + NIV + 1 − 1
•
Query met q item conditions met maar één atomic condition: q
j =1
q NRIV j NIV j + 1 − 1 sba + ∑ 1 rba + − 1 sba + [NTR rba ] EBF EBF 2 2 3 j =1
[1 rba ]+ ∑ 1 rba +
52
Evaluatie van de inverted list organisatiemethode: voorbeeld •
Algemeen: – – – – –
•
NR = 100.000 Block size: 2000 bytes Load factor = 1 Overhead = 0 NIV(department) = 100; NIV (skillcode) = 50; NIV (salary) = 25
Index: – Index entry size: 10 bytes – Key size: 6 bytes – Pointer size: 4 bytes
2000
= 200 – EBF2 = 10
•
Accession list: – Accession list entry size = 4 bytes – Pointer size = 4 bytes
2000
= 500 – EBF3 = 4
Evaluatie van de inverted list organisatiemethode: voorbeeld (vervolg) • Select …from … where skillcode = "PL" and department = 119 50 + 1 100 + 1 − 1 sba + 1 rba + − 1 sba 1 rba + 1 rba + × × 2 200 2 200 2000 1000 + 1 rba + − 1 sba + 1 rba + − 1 sba + 20 rba 500 500 = 25 rba + 4 sba
53
Toepasselijke bestandsorganisatiemethoden: overzicht • Single-key methoden – Multilistmethode (mét varianten) – Inverted list methode
• Multi-key methoden – Methoden van "Lum" (mét varianten)
Multi-key methoden Methode van Lum: het gebruik van "compound secondary index files" •
•
•
De methode van Lum heeft tot doel het aantal accesses op secundaire indexen te minimaliseren. Daarom wordt een index file gebouwd over de combinatie van data items die als secundaire sleutelelementen fungeren in de records. De ingangen in de index file bevatten de adressen van de records die voldoen aan een conjunctie van sleutelwaarden voor de betreffende secundaire sleutelelementen. Voor een query met in zijn kwalificatie-deel een RC bestaande uit een conjunctie van N waarden voor N respectieve secundaire sleutelelementen volstaat 1 block access (op de index file) om alle adressen van zich kwalificerende records te kennen.
54
De methode van Lum • •
N = maximum aantal secundaire sleutel data items per record (genummerd als item 1, 2, …N) N Item i heeft NIVi verschillende waarden K i1 , K i 2 , K i 3 , ..., K iNIVi en NIVi = K
∑ i =1
•
Lum stelt compound secondary index files voor om een zeer snelle toegang te verkrijgen tot records die voldoen aan een query conjunction. Elke compound secondary index file bestaat uit een aantal buckets die elk record accession numbers of pointers bevatten die voldoen aan een N-tupel secondary key waarden.
• •
Stel het volgende N-tupel: K11, K21, K31, …K N1 waarbij Kiji ∈ {Ki1, Ki2, Ki3, …K iNIVi} Met behulp van een compound secondary index, is slechts één toegang nodig om alle accession numbers te localiseren voor records die voldoen aan de query conjunctie K11 and K21 and …K N1.
•
Wanneer de accession numbers van alle records die voldoen aan een N-tupel van sleutelwaarden kunnen worden opgeslagen in één bucket, is het totale aantal benodigde buckets in een index file gelijk aan NIV1 x NIV2 x NIV3 x …NIV N Bij de inverted list methode zou dit slechts NIV1 + NIV2 + NIV3 + …NIV N zijn, maar het aantal recordadressen dat zich per ingang van een index kwalificeert kan natuurlijk veel kleiner zijn bij gebruik van de methode van LUM.
•
Voorbeeld van een compound secondary index file K1
K2
K3
1.
119
AD
1000
2.
119
AD
1500
3.
119
AD
1750
4.
119
AD
2000
5.
119
AD
2250
6.
119
AD
2500
7.
119
AD
3000
8.
119
FI
1000
9.
119
FI
1500
…
…
…
…
Adressen
Totaal: 3 x 6 x 7 = 126 ingangen
55
Aanmaken van compound secondary index files Beschouw een index file waarvoor de volgorde waarin secondary key values worden in aanmerking genomen de volgende is: 1, 2, 3, 4, …N. Dergelijke index wordt als volgt geconstrueerd: – Stap 1: Houd de item values voor items 1, 2, …N -1 constant en laat item N alle mogelijke secondary key waarden in stijgende volgorde aannemen. – Stap 2: Houd de eerste N-2 waarden constant en laat item N-1 zijn volgende hogere waarde aannemen, als die bestaat. Herhaal in dat geval stap 1. – Stap 3: Wanneer alle waarden voor item N-1 verwerkt zijn, neemt item N2 zijn volgende hogere waarde aan, enz. Dit proces wordt herhaald voor (N-3, N-4, …, 2, 1) todat een bucket werd toegewezen voor alle waarden in alle items.
Minder dan N items zijn gespecificeerd •
•
•
•
Stel dat er N secundaire sleutelelementen zijn per record. De methode van Lum werkt uitstekend indien in het kwalificerende gedeelte van de query naar elk sleutelelement door middel van een waard wordt gerefereerd. De methode heeft echter een probleem wanneer slechts k < N items zijn gespecificeerd in een query conjunction. In dat laatste geval gaan er zich meerdere ingangen in de index file kwalificeren. Deze ingangen kunnen willekeuring fysiek gespreid zijn over de index file, waardoor er meerdere rba' s nodig zijn en de methode dus aan waarde inboet. Stel dat slechts k waarden worden gerefereerd, met k < N. Bijvoorbeeld: stel dat geen waarden zijn gespecificeerd voor de secondary key data items 1, 2, 3, …N -k. Bij gebruik van een compound secondary index file wordt het aantal vereiste toegangen om alle pertinente record accession numbers op te halen gelijk aan NIV1 x NIV2 x …NIV N-k. Om aan dit probleem te verhelpen wordt een mate van redundantie toegestaan en worden meerdere (in principe dezelfde) secondary index files gebouwd.
•
Het totale aantal secondary index files is dan:
•
Het totale aantal ingangen is:
•
De mate van redundantie is:
N s
N N met s = 2 s
N
∏ i =1
NIVi
N s
56
Voorbeeld van redundante index files •
Index file 1 119 AD 119 AD … K1 K2
•
1000 1500 K3
Index file 2 AD 1000 AD 1000 … K2 K3
•
119 210 K1
Index file 3 1000 119 1000 119 … K3 K1
AD FI K2
Voorbeeld: werknemersbestand N=3 K1: deptnr
K2: bekwaamheidscode
NIV(K1) = 3 NIV(K2) = 6 NIV(K3) = 7
(119, 210, 220) (AD, FI, FO, MA, PL, SE) (1000, 1500, 1750, 2000, 2250, 2500, 3000)
K3: salaris
N 3 Vereiste aantal "compound secondary index files": = = 3 s 2 N
Aantal ingangen (
∏ NIV
blokken) per index file:
Totaal aantal ingangen (
n blokken): s
i
= 3 × 6 × 7 = 126
i =1
n
∏ NIV
i
= 3 ×126 = 378
i =1
n Redundantie: = 3 s
57
Beschouw volgende query' s •
Select …from employee where deptnr = 210 and bekwaamheidscode = "AD" and salaris = 1000 index file 1 (K1 K2 K3) consulteren Er is 1 ingang die zich kwalificeert 1 rba
•
Select …from employee where bekwaamheidscode = "AD" and salaris = 1000 index file 2 (K2 K3 K1) consulteren Het aantal ingangen dat zich kwalificeert is 3 1 rba + 2 sba
•
Select … from employee where salaris = 1000 index file 3 (K3 K1 K2) consulteren Het aantal ingangen dat zich kwalificeert is 3 x 6 = 18
1 rba + 17 sba
Berekening van het blokadres binnen een index file Sleutelelementen:
K1 K2 …K n
Bloknummer:
p1 p2 …p n
Blok adres:
[(p1-1) (NIV2 x NIV3 x …NIV n) + (p2-1) (NIV3 x NIV4 x …NIV n) + … (pn-1)] + [eventuele offset]
58
Berekening van blokadres: een voorbeeld • Select …from employee where deptnr = 210 and bekwaamheidscode = "AD" and salaris = 1000 K1 K2 K3 p1 = 2 p2 = 1 p3 = 1 Bucket nummer: p1 p2 p3 = 211 Bucket adres: [(2 - 1) x (6) x (7) + (1 - 1) x (7) + (1 - 1)] + [11] = 53 1 acces op adres 53 van index file 1 • Select …from employee where salaris = 1500 K3 K1 K2 2 1 1 Bucket adres: [(2-1) x (3) x (6) + (1-1) x (6) + (1-1)] + [270] = 288 18 adressen vanaf 288 in index file 3
Conclusies •
Evaluatie voor werknemersbestand, gegeven: – NR = 100.000 records – NIV(department) = 100 – NIV(skill code) = 50 – NIV(salary) = 25
•
Query:
•
De methode van Lum laat toe om zeer snel records op te halen die voldoen aan een query met meerdere item conditions. Deze flexibiliteit gaat echter ten koste van opslagcapaciteit en maintenance time.
select …from employee where department = 119 and skillcode = "PL" 1 rba aangenomen dat er één block is met overhead informatie. Dit betekent dat alle informatie nodig om de correcte index file te vinden en het adres in de index te berekenen opgeslagen is in één block. + [1 rba + 24 sba] direct access naar de index + 20 rba ophalen van target records Totaal: 22 rba + 24 sba
59
Inverted list versus LUM • Op het laagste niveau van de indexen is het aantal secondary index files: – Bij inverted list: N – Bij LUM: 1 (+ eventueel redundante indexen)
• Aantal ingangen voor de secondary index file(s): – Bij inverted list: NIVi – Bij LUM: NIV1 x NIV2 x…NIV n
• Totaal aantal ingangen overheen alle secondary index files: – Bij inverted list: NIV1 + NIV2 + …NIV n – Bij LUM: NIV1 x NIV2 x …NIV n
Database-organisatie
60
Database-organisatie • Betreft de organisatie van verbanden tussen (fysieke) bestanden. • Maakt gebruik van: – Methoden voor record-organisatie – Methoden voor bestandsorganisatie
• Voegt methoden toe voor de koppeling van records behorende tot verschillende bestanden. • Database-organisatiemethoden zijn geïmplementeerd in database software (Database Management Systems, DBMS' en).
Soorten databasesystemen •
•
Afhankelijk van het logische datamodel dat zij moeten implementeren, zien de oplossingen in het interne of fysieke databasemodel van deze systemen er totaal anders uit. Het is dus vanzelfsprekend om de verschillen in logische modellen die aan de basis liggen van DBMS' en als criterium te gebruiken bij de bespreking van database organisatiemethoden. We maken een onderscheid tussen: – Hiërarchische DBMS'en: IMS (IBM), DL1 (IBM) – CODASYL DBMS'en: CA-IDMS (Computer Associates), UDS (Siemens Nixdorf) – Relationele DBMS'en: Universal DB2 (IBM), Oracle 9i (Oracle Corporation), Universal database server (Informix), Sybase 11 (Sybase), SQL Anywhere (Sybase), SQLServer 6.5 (Microsoft) – Object-georiënteerde DBMS'en: O2 (O2 Technology), ObjectStore (Object Design), Gemstone (Gemstone Corporation), Jasmine (Computer Associates)
•
In wat volgt zullen wij ons beperken tot relationele databasemanagementsystemen, en dus de database-organisatiemethoden in relationele systemen bespreken.
61
Database-organisatiemethoden in relationele systemen • • •
•
Logisch bezien bestaat een relationele database uit een verzameling van tabellen die voorstellingen zijn van genormaliseerde relaties. De vraag is hoe de gegevens uit deze tabellen fysisch kunnen worden georganiseerd, m.a.w. hoe het fysieke databasemodel er uitziet. De commissies die zich bezighouden met standaardisatie van talen in een relationele database-omgeving doen geen uitspraken over het fysieke databasemodel. Het is implementor-defined. Het gevolg is dat de wijze waarop de fysieke organisatie van de opslag van gegevens uit een relationele database is geregeld verschilt van DBMS tot DBMS. Wij veronderstellen dat het gebruikte DBMS DB2 Universal Database van IBM is.
Logisch databasemodel voor relationeel databasesysteem Tabeldefinities: Docenten (Personeelsnr., Voornaam, Familienaam, Werkadres) Vakken (Vaknr, Vaknaam, Aantal_studiepunten, Docent)
Voorbeelden van rijen in de tabellen: Docenten: (03197, "Jacques", "Vandenbulcke", "Naamsestraat 69, 3000 Leuven") (06286, "Wilfried", "Lemahieu", "Naamsestraat 69, 3000 Leuven") Vakken: ("D237", "Database management I", 5, 03197) ("D295", "Systeemarchitecturen en opslag van gegevens", 3, 06286)
62
Van database tot tablespace(s) •
•
•
•
•
Storage group: groep van fysieke DASD volumes. Deze volumes kunnen ofwel door het operating systeem worden beheerd, ofwel rechtstreeks door DB2. Alle volumes in een storage group moeten van hetzelfde (device-)type zijn. Database: benoemde verzameling data, die verscheidene soorten objecten bevat zoals tabellen, indexen, …het is de logische eenheid waarmee een toepassingsprogramma interageert. Tablespace: de fysieke opslagruimte binnen een database bestaat uit een verzameling tablespaces. Dit zijn VSAM-bestanden die zich over één of meer storage groups kunnen uitstrekken. Index space: tablespaces kunnen eventueel met index spaces zijn geassocieerd, dit zijn ook VSAM-bestanden die versnelde toegang tot de data in de tablespace mogelijk maken. Stored table: elke tabel wordt toegekend aan een tablespace, die de "primary data" van de tabel bevat. We spreken dan van een stored table. Een tabel beslaat een aantal pagina' s(bv. van 4K grootte) in de tablespace. Eventueel kan een tabel zijn indexen in een aparte index space stockeren.
Toewijzen van logische eenheden aan fysieke eenheden •
•
•
Voor de inrichting van het fysieke databasemodel onder DB2 moeten volgende zaken geregeld worden: – Bepalen van storage groups – Bepalen van databases – Bepalen van tablespaces en index spaces – Toewijzen van • Databases aan storage groups • Index- en tablespaces aan databases • Stored tables aan table spaces • Indexes aan index spaces Een database vormt zo dus een collectie van tablespaces en index spaces. Behalve de indexen die vanzelf door het systeem worden gegenereerd kunnen dan nog allerlei extra indexen overwogen worden. Uiteindelijk moet de consistentie van de genomen beslissingen worden onderzocht.
63
Toewijzen van logische eenheden aan fysieke eenheden (vervolg) Stored table
User database
User database
System database
Tablespaces
…
…
Index
Index spaces
Toewijzen van logische eenheden aan fysieke eenheden (vervolg) Stored table
User database
Table spaces
User database
System database
Storage group 2
Storage group 1
…
…
Index
Index spaces
64
Indexing in een relationele database-omgeving • Een index kan worden gedefinieerd over eender welke (combinatie van) kolom(men) van een tabel. Deze kolommen worden gebruikt als sleutelattributen voor de index. • Indexen hebben tot doel: – Sneller vinden van rijen met een bepaalde (combinatie van) sleutelwaarde(n). – Afdwingen van uniciteit over (combinaties van) kolomwaarden. – Een logische volgorde definiëren overheen de rijen in een tabel. – Een "clustering property" aanbieden voor een tabel, zodat rijen fysiek worden opgeslagen in de volgorde van hun waarden voor de sleutelattributen van de index.
Soorten indexes Indexes kunnen volgens een aantal criteria worden ingedeeld: • • • •
Unique versus non-unique indexes Single column versus multi column indexes Clustering versus non-clustering indexes Gewone indexes versus B-trees
65
Unique versus non-unique indexes • Indien een unique index overheen een kolom van een tabel (of een verzameling van kolommen van een tabel) is gedefinieerd, dan zal het systeem geen duplicate sleutelwaarden voor die kolom toestaan. • Bijgevolg: door een unique index te declareren over de primary key van een tabel kan je voorkomen dat er rijen met duplicate primaire sleutelwaarden zouden binnensluipen in de tabel.
Single column versus multicolumn indexes Een index over meerdere kolommen kan nuttig zijn: – Om een rij uniek te identificeren – Om het totale aantal indexen te reduceren – Om index-only processing mogelijk te maken voor bepaalde query' s – Om query' s met AND -predicaten overheen de geïndexeerde kolommen efficiënter uit te voeren
66
Clustering versus non-clustering indexes • Wanneer een stored table zo is geïmplementeerd dat de volgorde van de records dezelfde is als de volgorde van de ingangen in de index die naar deze records verwijzen, dan spreken wij over een clustering index. • Dus de volgorde die in de index is bepaald is dezelfde als de volgorde van de rijen die hierdoor worden geïndexeerd. • Het voordeel van een clustering index is dat, bij het doorlopen van de index, een pagina met data records altijd slechts eenmaal zal moeten worden opgehaald, onafhankelijk van het aantal data records dat zich kwalificeert en in deze pagina voorkomt.
Clustering index Index
Kolomwaarde 1 2 3
Stored table werknemer
Pointer
DNR 1 1 2 2 2 3 3 3
WNR 100 101 102 103 104 105 106 107
WNAAM
67
Non-clustering index Index
Kolomwaarde 1 2 3
Stored table werknemer
Pointer
DNR 1 1 3 3 3 2 2 2
WNR 100 101 105 106 107 102 103 104
WNAAM
Gewone indexen versus B-trees •
•
•
•
De meest eenvoudige index heeft een ingang en een geassocieerde pointer voor iedere rij uit de geïndexeerde tabel. De index-ingangen kunnen in een sequentieel oplopende of afdalende volgorde worden gehouden. Bij gebruik worden de index-ingangen sequentieel gescand totdat de toepasselijke ingang(en) is (zijn) gevonden, en vandaar de adressen van de pagina' s of data blokken met de zich kwalificerende recor d(s) of rij(en) kunnen worden afgelezen. Deze werkwijze is soms nogal inefficiënt. Bij tabellen die uit een groot aantal rijen bestaan, resulteert ze in zeer grote indexen en dus in tijdrovende zoek-opdrachten op het niveau van de index. Een efficiënter alternatief zijn de boomgestructureerde zoekalgoritmes, waarvan de B-tree de meestgebruikte vertegenwoordiger is.
68
Boomgestructureerde zoekalgoritmes: enkele definities •
•
• •
Boomgestructureerde zoekmethodes maken gebruik van een search tree, waarbij de boomstructuur wordt geïmplementeerd door middel van de linked list bestandsorganisatiemethode. Het niveau (level) Li van een gewoon knooppunt of van een bladknooppunt i wordt bepaald door de lengte van het pad van de root tot het toepasselijke knooppunt i. Daarbij wordt verondersteld dat de root zich op niveau 0 bevindt. De hoogte van een boom wordt bepaald door het maximaal aantal niveaus overheen al zijn knooppunten. Een boom wordt een balanced tree genoemd wanneer het verschil in hoogte tussen de root en ongeacht welke twee bladknooppunten gelijk is aan ten hoogste 1.
Balanced tree
Unbalanced tree
Boomgestructureerde zoekalgoritmes: binary search trees Algemeen principe: – Zoekalgoritme start in knooppunt dat als "root" fungeert – K ↔ Kµ K = Kµ: gevonden ! K < Kµ: zoekalgoritme wordt recursief verder gezet in linker subtree van de root K > Kµ: zoekalgoritme wordt recursief verdergezet in rechter subtree van de root 21 10 5
52 16
24
8
88 41
30
67 45
95 69
69
Boomgestructureerde zoekalgoritmes: B-trees •
•
•
•
B-trees vormen een veralgemening van binary trees, waarbij de outdegree van een knooppunt nu ook groter dan 2 mag zijn en in elk knooppunt meerdere sleutelelementen kunnen voorkomen. Hierdoor zal het aantal niveaus van een B-tree meestal lager zijn dan voor een binary tree. Een B-tree is daarenboven ook balanced, zodat de afstand tussen de root en eender welk leaf knooppunt steeds gelijk is voor een bepaalde boom. Een B-tree vormt een boomgestructureerde verzameling van gekoppelde index-pagina' s, zo ingericht dat met een lager niveau telkens beperktere intervallen van waarden worden aangeduid. Er wordt steeds een onderscheid gemaakt tussen de root page, de nonleaf pages en de leaf pages.
Definitie van een B-tree van orde k •
•
• •
•
• • •
Elk non-leaf knooppunt is van de vorm
, P1, , …, Pq>, met q ≤ 2k. Elke Pi is een tree-pointer: een pointer naar een ander knooppunt in de boom. Elke Pri is een data-pointer: een pointer naar het record waarvan de sleutelwaarde gelijk is aan Ki (of de pagina die dit record bevat). Elk pad van de root naar een leaf node heeft dezelfde lengte, NR, wat ook de hoogte van de B-tree wordt genoemd. Alle leaf nodes zitten dus op hetzelfde niveau. Leaf nodes hebben dezelfde structuur als non-leaf nodes, behalve dat hun tree pointers Pi allemaal null zijn. Binnen elk knooppunt geldt dat K1 < K2 < …< K q Voor alle sleutelwaarden X in de subtree waarnaar door Pi verwezen wordt, geldt dat • Ki < X < Ki+1 voor 0 < i < q • X < Ki voor i = 0 • Ki < X voor i = q Het root-knooppunt kan een aantal tree-pointers (en dus child-knooppunten) hebben dat varieert van 2 tot 2k+1 en een aantal data-pointers (en dus sleutelwaarden) dat varieert van 1 tot 2k. Elk "gewoon" knooppunt, (dus geen root of leaf), heeft een aantal tree-pointers tussen k+1 en 2k+1 en een aantal data-pointers dat varieert van k tot 2k. Elk leaf-knooppunt heeft een aantal data-pointers dat varieert van k tot 2k en uiteraard geen tree-pointers. In het algemeen geldt: eender welk nonleaf-knooppunt met q data-pointers (of dus sleutelwaarden) moet q+1 tree-pointers (en dus child-knooppunten) hebben.
70
Voorbeeld van een B-tree knooppunt met q sleutelwaarden
Pr2 P2 … Pq-1 Kq
P0 K1 Pr1 P1 K2
Prq
Pq
B-tree configurations for a 12-key file 20
Order 1 (h = 3):
8 3
7
11 12
16
28 24 26
17
12
30
24
Order 2 (h = 2): 3
7
8
11
16 17 20
26 28 30
17
Order 3 (h = 2): 3
7
8
11 12 16
20 24 26 28 30
71
B+-trees •
De meeste DBMS-implementaties maken gebruik van een variant van B-trees, namelijk B+-trees. In een B+-tree bevatten enkel de leaf nodes van de tree data pointers. De leaf nodes hebben een entry voor elke (combinatie van) waarde(n) van de geïndexeerde kolom(men), samen met een data pointer naar de pagina(s) met rijen die deze waarde hebben voor de betrokken index key.
•
De leaf-knooppunten van de B+-tree worden meestal door middel van bijkomende pointers in volgorde gehouden, om sequentiële toegang in volgorde van de index key(s) efficiënter te maken. Deze leaf nodes zijn vergelijkbaar met het laagste niveau van een multilevel index.
Voorbeeld van een B+-tree 1000 NL1 2000 NL2 3000 NL3 NL 1
Root page Level 0
NL 2
100 L1 200 L2 300 L3 …
1100 L10 1200 L11 1300 L12 …
NL 3 Non-leaf pages Level 1
L3
L1 10 D1 12 D1 20 D2 … 99 D10
L2 100 D10 102 D10 103 D11 … 200 D23
To data pages
To data pages
L (N)
Leaf pages Level 2
72
Bepalen van de orde van een B+tree • •
Criterium: kies een zo hoog mogelijke orde (waardoor de hoogte van de boom zo laag mogelijk blijft), waarbij een knooppunt toch nog in één block past. Voorbeeld: – Block size = BS = 512 bytes – Key field size KS = 9 bytes – Record pointer size PrS = 7 bytes – Tree pointer size PS = 6 bytes Bepalen van de orde van non-leaf nodes kn: ((2kn+1) x PS) + (2kn x KS) <= BS ((2kn+1) x 6) + (2kn x 9) <= 512 30kn + 6 <= 512 kies kn = 16 Bepalen van de orde van leaf nodes kl: 2kn x (KS + PrS) + PS <= BS 2kn x (9 + 7) + 6 <= 512 32kn + 6 <= 512 kies kn = 15
Syntax voor het definiëren van een index CREATE INDEX indexnaam [UNIQUE] ON tabelnaam (naam of namen van kolommen waarover index wordt gedefinieerd) [CLUSTER] CREATE UNIQUE INDEX LEVNRINDEX ON LEVERANCIER (LEVNR, ASC)
73
Index design • Criteria voor het al dan niet definiëren van een index ? – – – –
Eén of meer tabellen per tablespace Grootte van table Frequentie van gebruik van bepaalde zoekargumenten Verhouding retrieval/update operaties
• Attributen waarover men kan overwegen een index te definiëren: – – – –
Primary key Foreign keys Eventuele andere attributen die vaak in zoekargumenten worden gebruikt Vermijd gebruik van indexen over kolommen met grote woordlengte en over varchar kolommen
Database-organisatiemethoden: accessmethoden •
• •
Relationele DBMS' en zijnnon-navigational: een SQL-query specificeert enkel welke gegevens moeten worden opgehaald, niet hoe ze worden opgehaald. Er zijn dan ook vaak meerdere mogelijkheden om dezelfde query uit te voeren. Elke mogelijkheid komt overeen met een access plan. Het is de rol van de optimizer om uit alle mogelijkheden het meest efficiënte access plan te selecteren, gegeven een bepaalde query. Een cost based optimizer berekent het optimale access plan aan de hand van een aantal ingebouwde cost-formules en op basis van gegevens zoals: - Welke tabellen door de query worden aangesproken - Welke indexen er voor deze tabellen bestaan - De statistische eigenschappen van de data in de tabellen
74
Uitvoering van een programma met embedded SQL-query' s Programma met embedded SQL
Preprocessor
Modified source code
Database request module
Compilatie
Bind
Programma object code
Applicatieplan
Optimizer
Statistische informatie aanwezig in de database Volgende statistische gegevens worden door het databasesysteem bijgehouden en kunnen door de optimizer worden gebruikt om het optimale access plan te berekenen: – Tabellen: • Aantal rijen • Aantal fysieke pagina' s ingenomen door de tabel • Aantal overflowrecords behorende tot de tabel – Kolommen: • Aantal verschillende waarden • Informatie over de verdeling van de waarden – Indexen: • Aantal verschillende waarden voor index sleutels en subsets van de sleutels die in de index aan bod komen • Aantal fysieke pages ingenomen door de index • Mate waarin de index geclusterd is – Tablespaces: • Device-specifieke I/O eigenschappen voor het device waarop de tablespace zich bevindt
75
Filterfactor en cardinaliteiten • De filterfactor (FF) voor een predicaat geeft de fractie aan van het aantal rijen in een tabel dat aan het toepasselijke predicaat zal voldoen. M.a.w., de FF geeft de waarschijnlijkheid dat een rij in een tabel ten aanzien van een toepasselijk predicaat zal worden uitgeselecteerd. • Assumptie: query over één tabel. Query-cardinaliteit = tabel-cardinaliteit x het product van de filterfactoren van de item conditions van de query • Kolom-cardinaliteit filterfactor query-cardinaliteit
Filterfactor en cardinaliteiten: een voorbeeld •
Query:
•
Gegeven:
select …from leverancier where levstatus = 20 and levplaats = "Amsterdam"
– Tabelcardinaliteit: – Kolom-kardinaliteiten:
TC(Leverancier) = 10.000 Colcard(IC1) = 50 Colcard (IC2) = 10 FF(IC1) = 1/50 = 0,02 FF(IC2) = 1/10 = 0,1
– Filterfactoren:
•
QC = TC x (FF1 x FF2) = 10000 x (0,02) x (0,1) = 20
•
Conclusie: via redenering
toegangspad kiezen
Fysiek databasemodel
76
Keuze van toegangspaden • Index scan – Matching index scan Select * from table T1 where C2 = v1 (index op C2) – Non-matching index scan Select * from table T1 where C1 = v1 (index op C2)
• • • •
Tablespace scan Multiple index access Index only access Implementaties van de join
Matching index scan Een matching index scan wordt gebruik als het query-predicaat overeenkomt met de eerste kolom(men) van de gebruikte index. De predicaten zorgen voor een filtering, zodat enkel welbepaalde indexen data pages worden opgehaald. •
• •
Vertrekkende vanuit de root-pagina van de index: zoek naar de entries die overeenkomen met sleutelwaarden die voldoen aan het querypredicaat. Volg de pointer(s) naar (het) tussenliggende niveau(s) van non-leaf pagina' s. Eens de eerste leaf-pagina is gevonden, doorzoek verder de opeenvolgende leaf pages naar entries die voldoen aan het querypredicaat. Volg de pointers naar de overeenkomstige data page(s) (indien nodig), totdat er geen entries meer zijn die voldoen.
77
Matching index scan: voorbeeld 1
1000 NL1 2000 NL2 3000 NL3
NL 1 100 L1 200 L2 300 L3 …
Root page Level 0
NL 3
NL 2 1100 L10 1200 L11 1300 L12 …
2
L3
L1 10 D1 12 D1 20 D2 … 99 D10
L2 100 D10 102 D10 103 D11 … 200 D23
To data pages
To data pages
Non-leaf pages Level 1
3
L (N)
Leaf pages Level 2
Non-matching index scan Een non-matchin index scan wordt gebruikt als het query-predicaat met geen enkele kolom in de index overeenstemt. Deze scan kan niet gebruikt worden om de data te filteren, maar is wel nuttig wanneer meerdere tabellen bestaan in dezelfde tablespace. •
•
Vertrekkende vanuit de eerste leaf page van de index, zoek naar de eerste index entry die overeenkomt met een (combinatie van) sleutelwaarde(n) die voldoet aan het query-predicaat. Volg hierbij de pointers naar de opeenvolgende leaf pages. Eens de eerste gepaste entry gevonden is, volg de pointer naar de overeenkomstige data page(s) (indien nodig). Doorzoek verder de leaf pages naar entries die overeenkomen met sleutelwaarden die voldoen aan het query-predicaat. Volg telkens de pointer naar de overeenkomstige data page(s) (indien nodig), totdat er geen qualifying entries meer zijn.
78
Non-matching index scan: voorbeeld 1000 NL1 2000 NL2 3000 NL3 NL 1
Root page Level 0
NL 3
NL 2
100 L1 200 L2 300 L3 …
1100 L10 1200 L11 1300 L12 …
1
L3
L1 10 D1 12 D1 20 D2 … 99 D10
L2 100 D10 102 D10 103 D11 … 200 D23
To data pages
To data pages
Non-leaf pages Level 1
2
L (N)
Leaf pages Level 2
Tablespace scan • Indien geen gepaste indexen voorhanden zijn, moet de tablespace met de eigenlijke data-pages gescand worden naar rijen die aan het query-predicaat voldoen. • Alle pagina' s in de tablespace worden opgehaald. Dit zal minder efficiënt zijn dan een index scan, zeker in het geval de tablespace rijen van meer dan één tabel bevat.
79
Tablespace scan en index scan: schatten van aantal toegangen Gegeven: Query: Select …from leverancier where levplaats = "Amsterdam" Tabelcardinaliteit: TCLeverancier = 10.000 Kolom-kardinaliteit: Colcard (IC) = 10 FF = 1/10 = 0,1 Capaciteit van de tablespace die (naast andere tabellen) de leverancierstabel bevat: CTS = 500 pagina' s van 4K Grootte van 1 rij uit de leverancierstabel: RSLeverancier = 0,1 K
• • • • •
Verwachte aantal pagina-toegangen (PA): • •
Tablespace scan: PA = CTS = 500 Non-matching index scan op non-clustering index: PA = TCLeverancier + IA = 10.000 + IA Non-matching index scan op clustering index: PA = TCLeverancier x RSLeverancier /4K + IA = 250 + IA Matching index scan op non-clustering index: PA = FF x TCLeverancier + IA = 1000 + IA Matching index scan op clustering index: PA = FF x TCLeverancier x RSLeverancier /4K + IA = 25 + IA
• • •
Multiple index access •
Bij multiple index access wordt meer dan één index gebruikt voor de data access. Row ID (RID) lists worden geconstrueerd op basis van de respectieve indexen. Unies van RID lists leiden tot een lijst van qualified RID' s om de rijen op te halen.
•
Beschouw de query: Select * from werknemers where departement = 119 and salaris = 1000 Stel: we maken gebruik van twee indexen, één over departement en een over salaris
•
Werkwijze: – Doorloop de departement-index (matching index scan) en lees alle RID' s van rijen die voldoen aan departement = 119. Sorteer deze RID' sin stijgende volgorde. – Doorloop de salaris-index (matching index scan) en lees alle RID' s (Row ID' s) van rijen die voldoen aan salaris = 1000. Sorteer deze RID ' s in stijgende volgorde. – Bij AND predicaten (zoals het voorbeeld): bereken de unie van de twee lijsten met RID' s en verwijder dubbels. Bij OR predicaten: berek en de doorsnede van de twee lijsten met RID' s. – Haal de eigenlijke data pages op (indien nodig) aan de hand van deze RID' s.
80
Index only access • Index only access komt voor wanneer geen eigenlijke datapagina' s moeten opgehaald worden om op de gestelde query te antwoorden, aangezien alle predicaten (en gezochte kolommen) in de index(en) te vinden zij. • Uiteraard is deze situatie erg voordelig op gebied van performantie.
Implementatie van de join • Wanneer gegevens uit meerdere tabellen moeten gecombineerd worden, voert het DBMS een join uit, deze wordt gespecificeerd aan de hand van een join-operator. • Algemene vorm van een join over de tabellen R en S: de theta-join R S r(a) θ s(b)
join conditie • De θ-operator bepaalt de voorwaarde waaraan – in verband met de waarden van de kolommen a en b in respectievelijk R en S – voldaan moet zijn, opdat toepasselijke rijen zouden mogen worden samengevoegd.
81
Implementatie van de join (vervolg) Tabel R Employee payscale Cooper 1 Jones 2 O' Donnell 1 Smith 2
Tabel S Payscale 1 2 3
Pay 10000 20000 30000
R S r(payscale) = s(payscale) Employee Cooper Jones O' Donnell Smith
• •
payscale 1 2 1 2
pay 10000 20000 10000 20000
Een join tussen n tabellen wordt normaal uitgevoerd als een opeenvolging van (n-1) joins tussen telkens 2 tabellen Technieken voor de implementatie van de join: nested-loop join, sort-merge join, hash join
Nested-loop join •
•
•
Eén van de tabellen die het voorwerp vormt van de join, wordt als inner-table aangewezen, en de andere als outer-table. Voor iedere rij van de outer-table worden alle rijen van de inner-table gelezen en vergeleken met de betreffende rij uit de outer-table. Wanneer aan de join-conditie is voldaan, worden de twee rijen samengevoegd en in een output-buffer geplaatst. De inner-table wordt dus zo dikwijls doorlopen als er rijen zijn in de outertable. R
S
r(a) θ q(b)
Stel: S outer-table Voor iedere rij s doe het volgende {voor iedere rij r doe het volgende {indien r(a) θ s(b) dan voeg r en s samen en plaats in uitvoerbuffer Q}}
82
Sort-merge join •
Vooreerst worden de beide tabellen op basis van de join-kolommen gesorteerd. Vervolgens worden beide tabellen in de verkregen volgorde doorlopen en worden rijen die aan de join-conditie voldoen samengevoegd en in de uitvoerlijst geplaatst.
•
R
S
r(a) θ q(b)
Stage 1: sorteer R op r(a) sorteer S op s(b) Stage 2: lees eerste rij voor R lees eerste rij voor S voor iedere rij r doe {zolang s(b) < r(b) lees volgende rij van S indien r(a) = s(b) dan voeg r en s samen en plaats op uitvoerlijst Q}
Hash join •
•
•
Er wordt een hashing algoritme toegepast op de join-kolomwaarden van de eerste tabel. Op basis van de verkregen hash value worden de rijen in een hash table geplaatst. Het is natuurlijk mogelijk dat er verschillende rijen aan eenzelfde bucket van de hash table worden toegewezen. Vervolgens wordt hetzelfde hashing algoritme toegepast op de joinkolomwaarden van de tweede tabel. Indien die waarden worden omgezet naar een niet-ledige bucket in de hash table, worden de rijen in de betreffende hashtable bucket vergeleken met de toepasselijke rij van de tweede tabel. Als aan de join-conditie is voldaan, worden ze samengevoegd. De performantie hangt ondermeer af van de grootte van de hash table. Voordeligst is uiteraard wanneer deze volledig in het interne geheugen kan bijgehouden worden.
83
Te kennen uit het boek “File organization & search techniques” Legende:
TK = te kennen NK = niet kennen, mag overgeslagen worden L = te lezen als achtergrondinformatie, voor een goed begrip van de rest van de materie. Niet in detail te kennen Algemene opmerking: complexe formules moet men kunnen toepassen en verklaren, maar niet van buiten kennen. Part 1: factors which affect the organization of data p. 1 – 45 (het volledige deel dus): TK Part 2: data organization methods p. 46 – 67: TK p. 68 – halfweg p. 69: NK p. 69 (tweede helft) – halfweg p. 74: TK p. 74 (tweede helft) – p. 80: NK p. 81 – 101: TK p. 102 – 109: L p. 110 – 133: TK p. 134 – 137: NK p. 138 – 157: TK p. 158 – 170 : NK p. 171 – 175: TK p. 176 – 179: enkel formules kunnen toepassen die op slides staan p. 180 – 185: NK p. 186 (onderaan) – 197: TK p. 198 – 229: NK
Part 3: data search techniques p. 230 – 257: NK p. 258 – 260: TK p. 261 – 262: NK p. 263 – 264: L p. 265 – 267: NK p. 268 – 271: TK p. 272 – 278: L p. 279 – 281: TK p. 282 – 284: NK
84
