Progettazione di basi di dati
distribuite
Marco Mangiacavalli
Matricola: 779291
I miei commenti in rosso CB
Schema della metodologia MS
proposta nel corso
Schema
locale
Operazione
0. presso il
Nodo
1. Visitato
presso il
Frammento
4. Schemi locali
3. alloc. rid.
2. alloc. non rid.
1. Contribuisce a
Frammento
elementare
Caso di studio: sistema di prenotazione
aerea
• Una compagnia aerea deve gestire le
prenotazioni dei suoi aerei. La base dati è
distribuita su tre siti degli Stati Uniti, ad es.
– Denver con codice 1, localizzato nell’area ovest
– New York, codice 2, localizzato nell’area nord
– Atlanta, codice 3, localizzato nell’ area sud
• La base dati rappresenta gli aeroporti dove opera,
gli orari dei voli, le disponibilità, e le prenotazioni.
• Ogni volo, per semplicità, è tra un aeroporto di
partenza e un aeroporto di arrivo.
3
Struttura generale
2. Nord = New York
Rete
1. Ovest = Denver
3. Sud = Atlanta
Passi da eseguire
1) Tradurre lo schema globale di pag. 19 della dispensa ME in uno
schema globale relazionale, producendo anche per ogni
relazione nel modello relazionale il numero di istanze.
2) Esprimere il carico applicativo nella modalità semplificata della
metodologia MS.
3) Condurre la progettazione adottando la metodologia MS.
3.1) Progetto della frammentazione
3.2) Allocazione non ridondante
3.3) Allocazione ridondante
3.4) Ricostruzione degli schemi locali
4) Tradurre gli schemi locali Entità Relazione esito del passo 3 nel
modello relazionale.
5) Nella ipotesi che le due metodologie arrivino a schemi relazionali
diversi, cercare di ragionare sul perchè
1) Traduzione schema globale ER
in Relazionale
Schema globale ER
Volo
Classe
Numero
Data
Gate
Ritardo
Mappa posti
Posti disponibili
Prenotaz.
Check in
Volo
Numero posto
Cod. Bagaglio
Nome
Telefono
Pas
Ora
arrivo
Da
Ora
partenza
Passeggero
A
Aeroporto
Identificatore (Acronimo)
Citta’
Area
Aer
7
Schema globale relazionale
• Aer(idA, città, area) -> 40 istanze
• Volo(numV, dataV, gate, rit, mP, pDisp, idAP,
oraP, idAA, oraA) -> 20.000 istanze
• Pas(noP, tel, numV, dataV, classe, numPo,
codB) -> 1.000.000 istanze
Si assume che un passeggero possa prenotare
e fare check in per un solo volo
Nomi poco espressivi…..
Schema globale relazionale: note
• Nello schema ho evidenziato in grassetto gli attributi
che sono chiave primaria della relazione e in corsivo
le chiavi esterne
• Nella traduzione ME->MS ho cercato di mantenere lo
stesso numero di entità presenti nelle specifiche del
caso ME, quindi ho ottenuto 3 relazioni; un’altra
alternativa poteva essere quella di creare altre 2
relazioni “Prenotazione” e “Check-in”
• Ho assunto che ogni passeggero può fare il check-in
solo se ha prenotato quel determinato volo
Bello!!!
I congiuntivi!
2) Carico applicativo semplificato
Qui avrei inserito la tavola delle
frequenze per operazioni presso i siti
Siti /Operazioni
a
b
c
1
2
3
10.000
20.000
10.000
8.000
12.000
8.000
100
120
100
11
Operazioni
visione per «operazioni»
• a. Prenota passeggero, effettua una
prenotazione, transazione
• b. Check in passeggero, effettua il check in di
un passeggero quando arriva all’aeroporto,
transazione
• c. Partenze dei prossimi trenta voli, fornisce
una report dei prossimi 30 voli che partono da
un aeroporto, interrogazione
12
Operazione a: attributi utilizzati
• Input: Pas = noP, tel; Volo = dataV, idAP, oraP, idAA,
oraA
• Letti: Volo = numV, dataV, pDisp
• Scritti: Volo = pDisp; Pas = classe, numV, dataV
• Dico nome e tel del passeggero che vuole prenotare
il volo + data, ora di part/ar e aeroporto part/ar;
verranno letti num e data del volo e, se ci sono
abbastanza posti disponibili, allora aggiornerà il
campo e assegnerà il volo al passeggero scrivendone
anche la classe
Nella visione “pre web” e’ l’operatore che invoca la transazione
E quindi sa gia’ il codice dell’aeroporto, e non coinvolge la tabella aeroporto
Risparmiando un join.
Operazione b : attributi utilizzati
• Input: Pas = noP, tel; Volo = numV, data
• Letti: Volo = mP; Pas = classe
• Scritti: Volo = mP; Pas = numPo, codB
• Dico nome e tel del passeggero che deve fare il
check-in + num e data del volo da lui prenotato;
verranno letti la classe del passeggero e la mappa dei
posti e, in base a questi, gli verrà assegnato un posto
e un codice del bagaglio
Operazione c: attributi utilizzati
• Input: Volo = dataV, idAP, oraP
• Letti: Volo = numV, dataV, gate, rit, oraP; Pas =
noP, tel, numV, dataV, classe
• Dico data, ora e aeroporto di cui voglio il
report; in output avrò numero, data, gate,
ritardo e ora di partenza dei prossimi 30 voli +
nome, tel e classe dei passeggieri che hanno
prenotato quel volo + città e area
dell’aeroporto di partenza
Carico applicativo
Nodo
Operazione
Fraquenza
1
T1a. Pas prenota volo che parte da aer area 1
10000
1
T1b. Check-in pas in aer area 1
8000
1
Q1c. Report prossimi 30 voli che partono da aer area 1
100
2
T2a. Pas prenota volo che parte da aer area 2
20000
2
T2b. Check-in pas in aer area 2
12000
2
Q2c. Report prossimi 30 voli che partono da aer area 2
120
3
T3a. Pas prenota volo che parte da aer area 3
10000
3
T3b. Check-in pass in aer area 3
8000
3
Q3c. Report prossimi 30 voli che partono da aer area 3
100
I punti . Per separare le migliaia…….
3) Progettazione
3.1) Progetto della
frammentazione
Progetto della frammentazione
• Scopo del passo è quello di individuare i
frammenti elemnetari da allocare in seguito
nei diversi nodi della base di dati distribuita
Individuazione frammenti visitati da Q
e T: T1a
AerArea1
VoliDaAerArea1
?
Pas
?
• AerArea1 = aeroporti area 1
• VoliDaAerArea1 = voli che partono da aeroporto area
1
• Pas = tutti passeggeri possono prenotare un volo
Individuazione frammenti visitati da Q
e T: T1a
• AerArea1 = POP + PV(idA, area)
• VoliDaAerArea1 = POS + PV(numV, dataV,
pDisp, idAP, oraP, idAA, oraA)
• Pas = PV(noP, tel, numV, dataV, classe)
Individuazione frammenti visitati da Q
e T: T1b
AerArea1
VoliDaAerArea1
PasDaAerArea1
• AerArea1 = aeroporti area 1
• VoliDaAerArea1 = voli che partono da aeroporto area
1
• PasDaAerArea1 = passeggeri che partono da
aeroporto area 1
Individuazione frammenti visitati da Q
e T: T1b
• AerArea1 = POP + PV(idA, area)
• VoliDaAerArea1 = POS + PV(numV, dataV, mP,
idAP, oraP)
• PasDaAerArea1 = POS
Individuazione frammenti visitati da Q
e T: Q1c
AerArea1
VoliDaAerArea1
PasDaAerArea1
• AerArea1 = aeroporti area 1
• VoliDaAerArea1 = voli che partono da aeroporto area
1
• PasDaAerArea1 = passeggeri che partono da
aeroporto area 1
Nei requisiti si parlava solo dei voli, non dei passeggeri …
Individuazione frammenti visitati da Q
e T: Q1c
• AerArea1 = POP
• VoliDaAerArea1 = POS + PV(numV, dataV,
gate, rit, idAP, oraP)
• PasDaAerArea1 = POS + PV(noP, tel, numV,
dataV, classe)
Individuazione frammenti visitati da Q
e T: T2a
AerArea2
VoliDaAerArea2
Pas
• AerArea2 = aeroporti area 2
• VoliDaAerArea2 = voli che partono da aeroporto area
2
• Pas = tutti passeggeri possono prenotare un volo
Individuazione frammenti visitati da Q
e T: T2a
• AerArea2 = POP + PV(idA, area)
• VoliDaAerArea2 = POS + PV(numV, dataV,
pDisp, idAP, oraP, idAA, oraA)
• Pas = PV(noP, tel, numV, dataV, classe)
Individuazione frammenti visitati da Q
e T: T2b
AerArea2
VoliDaAerArea2
PasDaAerArea2
• AerArea2 = aeroporti area 2
• VoliDaAerArea1 = voli che partono da aeroporto area
2
• PasDaAerArea2 = passeggeri che partono da
aeroporto area 2
Individuazione frammenti visitati da Q
e T: T2b
• AerArea2 = POP + PV(idA, area)
• VoliDaAerArea2 = POS + PV(numV, dataV, mP,
idAP, oraP)
• PasDaAerArea2 = POS
Individuazione frammenti visitati da Q
e T: Q2c
AerArea2
VoliDaAerArea2
PasDaAerArea2
• AerArea2 = aeroporti area 2
• VoliDaAerArea2 = voli che partono da aeroporto area
2
• PasDaAerArea2 = passeggeri che partono da
aeroporto area 2
Perche’ anche passeggeri? Si chiedeva solo dei voli…
Individuazione frammenti visitati da Q
e T: Q2c
• AerArea2 = POP
• VoliDaAerArea2 = POS + PV(numV, dataV,
gate, rit, idAP, oraP)
• PasDaAerArea2 = POS + PV(noP, tel, numV,
dataV, classe)
Individuazione frammenti visitati da Q
e T: T3a
AerArea3
VoliDaAerArea3
?
Pas
?
• AerArea3 = aeroporti area 3
• VoliDaAerArea3 = voli che partono da aeroporto area
3
• Pas = tutti passeggeri possono prenotare un volo
Individuazione frammenti visitati da Q
e T: T3a
• AerArea3 = POP + PV(idA, area)
• VoliDaAerArea3 = POS + PV(numV, dataV,
pDisp, idAP, oraP, idAA, oraA)
• Pas = PV(noP, tel, numV, dataV, classe)
Individuazione frammenti visitati da Q
e T: T3b
AerArea3
VoliDaAerArea3
PasDaAerArea3
• AerArea3 = aeroporti area 3
• VoliDaAerArea3 = voli che partono da aeroporto area
3
• PasDaAerArea3 = passeggeri che partono da
aeroporto area 3
Individuazione frammenti visitati da Q
e T: T3b
• AerArea3 = POP + PV(idA, area)
• VoliDaAerArea3 = POS + PV(numV, dataV, mP,
idAP, oraP)
• PasDaAerArea3 = POS
Individuazione frammenti visitati da Q
e T: Q3c
AerArea1
VoliDaAerArea1
PasDaAerArea1
• AerArea3 = aeroporti area 3
• VoliDaAerArea3 = voli che partono da aeroporto area
3
• PasDaAerArea3 = passeggeri che partono da
aeroporto area 3
Individuazione frammenti visitati da Q
e T: Q3c
• AerArea3 = POP
• VoliDaAerArea3 = POS + PV(numV, dataV,
gate, rit, idAP, oraP)
• PasDaAerArea3 = POS + PV(noP, tel, numV,
dataV, classe)
Tabella frammenti elementari
visione per operazioni & frammenti
Nodo
Op./Freq
Tipo fram
Rel coinvolte
Fram coinvolti
1
T1a/10000
OP + OS + V
Aer, Volo, Pas
AerArea1, VoliDaAerArea1, Pas
1
T1b/8000
OP + OS + V
Aer, Volo, Pas
AerArea1, VoliDaAerArea1,
PasDaAerArea1
1
Q1c/100
OP + OS + V
Aer, Volo, Pas
AerArea1, VoliDaAerArea1,
PasDaAerArea1
2
T2a/20000
OP + OS + V
Aer, Volo, Pas
AerArea2, VoliDaAerArea2, Pas
2
T2b/12000
OP + OS + V
Aer, Volo, Pas
AerArea2, VoliDaAerArea2,
PasDaAerArea2
2
Q2c/120
OP + OS + V
Aer, Volo, Pas
AerArea2, VoliDaAerArea2,
PasDaAerArea2
3
T3a/10000
OP + OS + V
Aer, Volo, Pas
AerArea3, VoliDaAerArea3, Pas
3
T3b/8000
OP + OS + V
Aer, Volo, Pas
AerArea3, VoliDaAerArea3,
PasDaAerArea3
3
Q3c/100
OP + OS + V
Aer, Volo, Pas
AerArea3, VoliDaAerArea3,
PasDaAerArea3
Frammentazioni un po’ ridondanti!
Frammenti individuati
1.
2.
3.
4.
5.
6.
7.
8.
9.
AerArea1
VoliDaAerArea1
PasDaAerArea1
AerArea1
VoliDaAerArea1
PasDaAerArea1
AerArea1
VoliDaAerArea1
PasDaAerArea1
Non c’e’ P “intera” corretto!
3.2) Allocazione non ridondante
Allocazione non ridondante
• Lo scopo di questa fase è associare ad ogni
nodo i frammenti in modo non ridondante,
basandomi sul carico applicativo
• I frammenti elementari individuati dovranno
essere assegnati al nodo che lo utilizza più
spesso
• In questo mono verranno minimizzati i
trasferimenti tra nodi dovuti a interrogazioni o
transazioni
Assegnazione frammenti ai nodi
qui la «visione» e’ per frammenti
Fr
Op
Nodi
FN1
FN2
FN3
As
AerArea1
T1a, T1b, Q1c
1
18100
-
-
1
VoliDaAerArea1
T1a, T1b, Q1c
1
18100
-
-
1
PasDaAerArea1
T1a, T1b, Q1c, T2a, T3a
1, 2, 3
18100
20000
10000
2
AerArea2
T2a, T2b, Q2c
2
-
32120
-
2
VoliDaAerArea2
T2a, T2b, Q2c
2
-
32120
-
2
PasDaAerArea2
T2a, T2b, Q2c, T1a, T3a
1, 2, 3
10000
32120
10000
2
AerArea3
T3a, T3b, Q3c
3
-
-
18100
3
VoliDaAerArea3
T3a, T3b, Q3c
3
-
-
18100
3
PasDaAerArea3
T3a, T3b, Q3c, T1a, T2a
1, 2, 3
10000
20000
18100
2
Frequenze su passeggero dovute alla scelta precedente di permettere a tutti
I passeggeri di fare prenotazioni da tutti e tre I nodi
NB scelta molto web oriented
Assegnazione frammenti ai nodi
AerArea2
2. Nord = New York
PasDaAerArea1
VoliDaAerArea2
PasDaAerArea2
PasDaAerArea1
PasDaAerArea3
PasDaAerArea2
AerArea1
PasDaAerArea3
VoliDaAerArea1
1. Ovest = Denver
Rete
PasDaAerArea1
PasDaAerArea2
Riportati anche I
potenziali da
Ridondare: bene! 3. Sud = Atlanta
PasDaAerArea3
AerArea3
VoliDaAerArea3
3.3) Allocazione ridondante
Allocazione ridondante
• Lo scopo di questo passo è di duplicare i
frammenti, attualmente presenti in un solo
nodo, anche in altri nodi
• La duplicazione va eseguita solo quando i
risparmi superano i maggiori costi
• Seleziono il nodo i per cui è massima la
differenza: risparmi(i) - costi(i)
Costi - benefici
• Frammenti che potrebbero essere allocati in modo
ridondante: PasDaAerArea1, PasDaAerArea2,
PasDaAerArea3 sui nodi 1 e 3
• Noto che le transazioni sono molte di più rispetto alle
interrogazioni quindi si può dedurre che i costi di
aggiornamento delle varie tabelle distribuite, se si
decidesse di duplicare, sarebbero troppo elevati se si
decidesse di duplicare i dati. Di conseguenza non
conviene replicare i frammenti
Preferirei non dedurre ma calcolare……anche perche’ trasferire
(Interrogazioni) costa di piu’ che aggiornare
Schema finale
AerArea2
2. Nord = New York
VoliDaAerArea2
PasDaAerArea1
PasDaAerArea2
AerArea1
PasDaAerArea3
VoliDaAerArea1
Rete
1. Ovest = Denver
3. Sud = Atlanta
AerArea3
VoliDaAerArea3
3.4) Ricostruzione degli schemi
locali
Ricostruzione degli schemi locali
• Come ultimo passo bisogna ricostruire gli
schemi locali come unione di tutti i frammenti
associati al corrispondente sito ottenuti nei
passi precedenti
VoliDaAerArea1
Check in
A
Da
A3
Prenotaz.
AerArea1
Nodo1
A
VoliDaAerArea1
Prenotaz.
Check in
PasDaAerArea1
PasDaAerArea2
PasDaAerArea3
A
Da
Nodo 2
AerArea2
A
VoliDaAerArea3
Prenotaz.
Check in
Da
A
A3
AerArea3
Nodo 3
50
Schema relazionale
•
•
•
•
AerArea1(idA, città, area)
AerArea2(idA, città, area)
AerArea3(idA, città, area)
VoliDaAerArea1(numV, dataV, gate, rit, mP, pDisp,
idAP, oraP, idAA, oraA)
• VoliDaAerArea2(numV, dataV, gate, rit, mP, pDisp,
idAP, oraP, idAA, oraA)
• VoliDaAerArea3(numV, dataV, gate, rit, mP, pDisp,
idAP, oraP, idAA, oraA)
• Pas(noP, tel, numV, dataV, classe, numPo, codB)
Risultato
• Nello schema ottenuto abbiamo che:
1) Gli aeroporti sono allocati nei 3 nodi in base all’area in cui si
trovano
2) I voli sono distribuiti in base all’area in cui si trova
l’aeroporto di partenza
3) I passeggeri sono tutti allocati nel nodo di New York
• I primi 2 punti rispettano il principio di località, mentre il terzo
no.
• Con questa soluzione le operazioni dei nodi 1 e 3 sui
passeggeri risulteranno meno efficienti, ma se avessi scelto di
duplicare la tabella Passeggeri anche negli altri 2 nodi avrei
avuto notevoli problemi di allineamento dei dati
4) Traduzione schemi locali ER
nel modello relazionale
Prenotaz.
Check in
Volo1
A
Da
A3
Aeroporto1
Passeggero 1u
Passeggero 4u
Passeggero 5u
Passeggero 7
Sito 1
A
Volo2
Prenotaz.
Check in
A
Da
Aeroporto2
Passeggero 2u
Passeggero 4u
Passeggero 6u
Passeggero 7
Sito 2
A
Volo3
Da
A
Prenotaz.
Check in
Passeggero 3u
Passeggero 5u
Passeggero 6u
Passeggero 7
A3
Aeroporto3
Sito 3
54
Schema relazionale
•
•
•
•
•
•
•
•
•
•
•
•
•
Aeroporto1(idA, città, area)
Aeroporto2(idA, città, area)
Aeroporto3(idA, città, area)
Volo1(numV, dataV, gate, rit, mP, pDisp, idAP, oraP, idAA, oraA)
Volo2(numV, dataV, gate, rit, mP, pDisp, idAP, oraP, idAA, oraA)
Volo3(numV, dataV, gate, rit, mP, pDisp, idAP, oraP, idAA, oraA)
Passeggero1(noP, tel, numV, dataV, classe, numPo, codB)
Passeggero2(noP, tel, numV, dataV, classe, numPo, codB)
Passeggero3(noP, tel, numV, dataV, classe, numPo, codB)
Passeggero4(noP, tel, numV, dataV, classe, numPo, codB)
Passeggero5(noP, tel, numV, dataV, classe, numPo, codB)
Passeggero6(noP, tel, numV, dataV, classe, numPo, codB)
Passeggero7(noP, tel, numV, dataV, classe, numPo, codB)