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)