Compito di Complementi di Basi di Dati
24 giugno 2010
Esercizio 1:
Si supponga che per memorizzare i dati relativi alla gestione delle catene di supermercati presenti in una data regione sia stata usata un’unica tabella SU P ERM ERCAT O con la seguente struttura:
SU P ERM ERCAT O(CodiceSupermercato, DirettoreSupermercato, AziendaP roprietaria, P rovinciaSupermercato, P rovinciaAzienda, Reparto, DirettoreReparto)
Sia dato il seguente insieme di requisiti. Ogni supermercato appartenente ad una data catena di super- mercati di propriet`a di una determinata azienda sia identificato da un numero progressivo (supermercato numero 1 della catena di supermercati di propriet`a dell’azienda XYZ, supermercato numero 2 della catena di supermercati di propriet`a dell’azienda XYZ,, etc.). Di ogni supermercato vogliamo memorizzare il di- rettore e la provincia ove si trova. Si assuma che una stessa persona possa dirigere pi`u supermercati di una stessa catena, ma non supermercati di catene diverse. Ogni azienda proprietaria di una catena di supermercati sia identificata univocamente da un codice e sia caratterizzata dal provincia ove ha sede. Si assuma che ogni azienda possa possedere una sola catena di supermercati. In ogni supermercato siano presenti pi`u reparti, ciascuno identificato da un nome (ossia non vi possano essere reparti diversi con lo stesso nome nello stesso supermercato). Ovviamente, non possiamo escludere che supermercati diversi possano avere reparti con lo stesso nome. Ogni reparto di un dato supermercato sia gestito da un di- rettore di reparto. Si assuma che un direttore di reparto possa dirigere un unico reparto (di un unico supermercato).
(a) Determinare le dipendenze funzionali della relazione SU P ERM ERCAT O.
(b) Determinare le chiavi candidate e gli attributi primi e non primi di SU P ERM ERCAT O.
(c) Stabilire se SU P ERM ERCAT O `e o meno in BCNF.
(d) Stabilire se SU P ERM ERCAT O `e o meno in 2NF.
(e) Stabilire se SU P ERM ERCAT O `e o meno in 3NF.
(f) Nel caso in cui SU P ERM ERCAT O non sia in 3NF, fornire una scomposizione lossless join in 3NF di SU P ERM ERCAT O che conservi le dipendenze.
Esercizio 2:
Mostrare come il metodo 2PL stretto eviti le anomalie di perdita di aggiornamento, lettura sporca e lettura inconsistente. Successivamente, stabilire se i seguenti schedule appartengono o meno a TS, 2PL stretto, 2PL, CSR e VSR.
1. s1: r1(x), w1(t), r2(x), w2(x), r2(z), w4(t), w2(z), r1(y), w3(z), w3(y), w4(z);
2. s2: r1(x), w2(x), r3(y), r2(x), w1(x), r4(y), w2(x), r3(z), w4(z);
3. s3: w1(x), r2(t), r1(y), r2(y), w3(t), r4(y), w2(x), w4(y), w4(x), r1(z), w3(z), r4(t).
1
Esercizio 3:
Determinare i profili dei risultati intermedi e del risultato finale (cardinalit`a e dimensione delle tabelle, numero di valori distinti di ciascuno dei loro attributi) della seguente interrogazione che restituisce, per ogni studente identificato dal suo numero di matricola, le materie/esami superate/i col punteggio 24/30:
π
M atricola(Studenti)1 π
M atricola,M ateria(σ
V oto=24(Esami)), relativa alle tabelle:Studenti(Cognome, M atricola, P rovincia);
Esami(M ateria, M atricola, V oto), aventi i seguenti profili:
CARD(Studenti) = 40, SIZE(Studenti) = 27, CARD(Esami) = 1300, SIZE(Esami) = 22, SIZE(Cognome) = 20, SIZE(M atricola) = 5, SIZE(P rovincia) = 2, SIZE(M ateria) = 15, SIZE(V oto) = 2,
V AL(Cognome) = 38, V AL(M atricola) = 40, V AL(P rovincia) = 40, V AL(M ateria) = 20, V AL(V oto) = 13.
Abbiamo assunto che ogni studente abbia superato almeno un esame.
P.S. Si ricordi che la formula col(n, m, k) che calcola il numero di colori distinti presenti in k oggetti estratti a partire da n oggetti diversi di m colori distinti, distribuiti omogeneamente, ammette la seguente approssimazione:
(a) col(n, m, k) = k se k ≤ m/2;
(b) col(n, m, k) = (k + m)/3 se m/2 ≤ k ≤ 2m;
(c) col(n, m, k) = m se k ≥ 2m.
Esercizio 4:
Data la sequenza di chiavi:
7, 11, 5, 17, 3, 29, 9, 19, 2, 23, 10, 31, 8, si costruisca passo passo un B-albero di ordine p = 4.
Successivamente, con riferimento alla medesima sequenza di chiavi, si costruisca passo passo un B+-albero con ordine dei nodi interni p = 3 e ordine dei nodi foglia pleaf = 3.
Infine, si descriva la sequenza di passi necessaria per l’esecuzione delle seguenti operazioni:
• trovare il record con valore del campo chiave di ricerca pari a 5 (sia per il B-albero che per il B+-albero);
• trovare il record con valore del campo chiave di ricerca pari a 23 (sia per il B-albero che per il B+-albero);
• trovare i record con valore del campo chiave di ricerca compreso tra 5 e 23, estremi inclusi (solo per il B+-albero).
Esercizio 5 (FACOLTATIVO):
Siano date due istanze r, s ∈ R e una scomposizione binaria ρ di R. Stabilire se mρ(r ∩ s) = mρ(r) ∩ mρ(s). In caso di risposta positiva, fornire una dimostrazione; in caso di risposta negativa, fornire un controesempio.
