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.


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).  


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 



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.