BASI DI DATI II, 12 aprile 2021 (Svolto a distanza) Domanda 1 (15 minuti) Considerare una tabella T appena creata (vuota), con le seguenti ipotesi - T ha due campi, A di a = 18 byte e B di lunghezza variabile, massimo b = 20 byte; - T ha struttura heap, con memorizzazione a lunghezza variabile (con 2 ulteriori byte per la memorizzazione; quindi un record occupa fra 20 e 40 byte) - gli spazi dei record eliminati sono marcati come liberi e non sono riutilizzati per successivi inserimenti (se non dopo una riorganizzazione che ricompatti i blocchi); poiché la lunghezza è variabile, se, in caso di modifica, la lunghezza del campo variabile aumenta, allora l'operazione viene gestita come un'eliminazione seguita da un inserimento - il sistema utilizza blocchi di dimensione D = 400 byte In tale contesto, supporre che vengano eseguite le seguenti operazioni 1. inserimento di L = 1000 ennuple con il campo B di lunghezza nulla 2. aggiornamento di L/10 = 100 ennuple, con modifica del valore di B costituito questa volta di una stringa b = 20 byte, 3. riorganizzazione del file con ricompattazione dei blocchi Indicare, nello spazio sottostante, il numero di blocchi occupati dalla relazione, dopo ciascuna delle serie di operazioni. Riportare la risposta su tre righe, una per ciascuna serie. Aggiungere, dopo queste tre righe, un breve commento esplicativo. Possibile soluzione 1. (L * (a+2))/D = (1000*20)/400 = 50 2. [risp 1.] + (L/10 * (a+b+2))/D = 50 + 100 * 40 / 400 = 60 3. ((L*9/10 * (a+2)) + (L/10 * (a+b+2)) ) / D =(900*20 + 100*40)/ 400 = 55 Domanda 2 (20 minuti) Si considerino due relazioni R1(A,C,D,E,F), R2(A,G,H,I,L), in cui gli attributi hanno tutti la stessa dimensione L = 10 byte, molto più piccola della dimensione del blocco pari a B = 8000 byte. Si supponga che - l'attributo A sia chiave per entrambe le relazioni, - i valori per A nelle due relazioni siano gli stessi - le relazioni abbiano entrambe N = 1.000.000 ennuple - ciascuna relazione abbia un indice primario su A (e quindi sia ordinata su A) e che le operazioni più frequenti su di essa siano le seguenti: - o1: join delle due relazioni su A, con frequenza f1 = 10.000; - o2: scansione dell’intera relazione R1, con frequenza f2 = 100 Valutare le due seguenti alternative di memorizzazione, calcolando il costo complessivo (riportare la formula che indica il numero di accessi nell’unità di tempo, in base alle variabili sopra citate, e poi il valore numerico): - A: memorizzazione separata delle due relazioni - B: memorizzazione delle due relazioni in un cluster plurirelazionale Rispondere a video, commentando brevemente la soluzione. Spiegare anche, senza entrare nei dettagli, come cambierebbe la situazione se le frequenze fossero diverse, con f2 molto maggiore di f1 (anziché molto minore). Risposta Caso A o1 un merge join di relazioni ordinate, equivale alla scansione delle due 2*N*L*5/B=2*1.000.000*10/8000= 12.500 blocchi o2 scansione di R2 = N*L*5/B=6.250 blocchi Caso B o1 come sopra, 12.500 o2 scansione dei blocchi che contengono entrambe le relazioni, 12.500 Conviene comunque la memorizzazione separata, nel caso proposto di poco, nel secondo caso di molto Domanda 3 (25 minuti) Si considerino tre relazioni, tutte disordinate e con indice sulla chiave primaria, in un sistema che utilizza blocchi di Q=1000 byte e con una disponibilità di P=500 pagine di buffer - R1(A,B,C), con N1=1.000.000 ennuple, di L1=10 byte ciascuna, con 100 valori diversi su B, compresi fra 1 e 100, uniformemente distibuiti e con vincolo di integrità referenziale fra C e R2(D) - R2(D,E,F), con N2=2.000.000 ennuple, di L2=10 byte ciascuna, con vincolo di integrità referenziale fra F e R3(G) - R3(G,H,L), con N3=1.000.000 ennuple, di L3=10 byte ciascuna Indicare, per ciascuna delle tre seguenti operazioni, il piano di esecuzione (specificandolo a parole, ma in modo non ambiguo) e il costo. Supporre che gli indici abbiano tutti profondità I=4 e che il sistema possa scegliere fra hash-join e nested-loop join con indice. 1. SELECT * FROM R1, R2 WHERE C=D AND B<50 2. SELECT * FROM R1, R2 WHERE C=D AND B=20 3. SELECT * FROM R1, R2, R3 WHERE C=D AND F=G AND A=20 Risposta Sia B1=N1/(Q/L1) = 10.000 B2=N2/(Q/L2) = 20.000 1. selezione su R1 e poi hash join, costo B1+2*B1/2 + 3*B2 = ca 80.000 (con nested loop costerebbe B1+N1/2*4, quindi molto di più) 2. selezione su R1 e poi nested loop con accesso diretto (basta una sola scansione su R1), costo B1+N1/100 * (I-2+1) = ca 40.000 (con hash join costerebbe di più, perché servirebbero due passate, con 60.000 solo su R2) 3. selezione su R1 (con indice) e poi due accessi diretti: I + 1 + I + 1 + I + 1 = 15 Domanda 4 (20 minuti) Si considerino un sistema con blocchi di dimensione B = 1000 byte e una relazione R(A,C, ....) con L = 1.000.000 ennuple, di e = 100 byte e campo chiave A di tipo intero e campo C di tipo stringa (ad esempio un nome). Supporre che il sistema offra • strutture primarie disordinate e ordinate (rispetto ad un indice denso di tipo B-tree), ma con ordinamento non mantenuto (quindi eventuali inserimenti vengono effettuati in coda al file) • indici secondari di tipo B-tree Considerare un carico applicativo che preveda una pausa notturna (utilizzabile per riorganizzare le strutture fisiche) e le seguenti operazioni 1. inserimento di una ennupla (con verifica del vincolo di chiave), con frequenza giornaliera f1 = 10; 2. ricerca di una ennupla sulla base del valore della chiave A, con frequenza giornaliera f2 = 1000; 3. ricerca di una ennupla sulla base del valore parziale (una sottostringa iniziale) dell’attributo C, con frequenza giornaliera f3 = 10.000; supporre che il valore parziale sia abbastanza selettivo e porti alla identificazione, in media, di s = 5 ennuple. Progettare l’organizzazione fisica della relazione, (i) scegliendo la struttura primaria (disordinata o ordinata, indicando in questo caso su quale attributo) e (ii) individuando gli eventuali indici. Ragionare in termini di numero di accessi a memoria secondaria, assumendo che gli indici abbiano profondità p = 4, con due livelli mediamente mantenuti nel buffer, e che lettura e scrittura abbiano lo stesso costo. Inoltre, qualora si scelga una struttura ordinata, si assuma che la riorganizzazione sia eseguita tutte le notti e considerare un numero medio di record disordinati in coda pari a metà degli inserimenti di una giornata. Proporre almeno due alternative (quelle che intuitivamente si ritengono migliori) e valutarne il costo. Non è necessario considerare il costo della eventuale riorganizzazione. Risposta Per la struttura primaria, che dal testo può essere ordinata o disordinata (non si parla di hash), l'unico ordinamento utile è quello su C. Poiché su A ci sono operazioni di verifica di chiave e di ricerca (entrambe frequenti) e su C ci sono operazioni di ricerca, pure frequenti, sembrano comunque utili indici sia su A sia su C. Se mancasse uno solo degli indici, servirebbe una scansione sequenziale, che richiederebbe L/(B/e)=100.000 accessi (con frequenze 1000 o 10.000). Quindi emergono solo due alternative: (a) struttura disordinata con indice su A e C (b) struttura ordinata su C (con riorganizzazione notturna) e indice su A Costi per la soluzione (a) Op 1: (p-2)+(p-2)+1+2+1 (accesso ai due indici e al record, scrittura delle due foglie e del blocco dati) costo unitario 8 Op 2: (p-2)+1 (accesso all'indice e al record) costo unitario 3 Op 3: (p-2)+5 (accesso all'indice e ai cinque record, in blocchi diversi) Costo totale 8 * 10 + 3 * 1000 + 7 * 10.000 = ca 73.000 Costi per la soluzione (b) Op 1: simile al caso (a), costo unitario 8 Op 2: come nel caso (a), costo unitario 3 Op 3: (p-2)+1 (accesso all'indice e al blocco con i cinque record; si può trascurare il piccolo disordine, perché l'indice viene mantenuto e i record non ordinati sono mediamente 5 su 1.000.000) Costo totale 8 * 10 + 3 * 1000 + 3 * 10.000 = ca 33.000