Esame Basi di Dati
21 Gennaio 2013
Matricola
Prog. (Sı̀/No)
Cognome
Nome
Istruzioni
• I voti verranno resi disponibili su AlmaEsami. Chi vorrà rifiutare il voto
dovrà comunicarlo tassativamente 5 giorni dalla data della pubblicazione all’indirizzo [email protected]. Passato questo termine, i voti
di coloro che non li hanno esplicitamente rifiutati si intendono accettati, e
il docente provvederà a registrarli successivamente — il momento preciso
in cui avverrà la registrazione non è definito a priori, e può variare da
appello ad appello, l’unico termine fisso è quello dei 5 giorni per rifiutare
il voto. Quanto detto vale per i voti maggiori o uguali a 18.
• Non sarà compilato alcuno statino, e il libretto non verrà firmato. La
registrazione avviene solamente elettronicamente. Pertanto non bisogna
presentarsi fisicamente dal docente per la registrazione.
• Prima di iniziare, scrivere nome, cognome e matricola su tutti i fogli,
in modo leggibile. Nella tabella sopra riportata indicare anche se si deve
sostenere la parte di laboratorio e, in caso positivo, se si è svolto il progetto.
• Scrivere le soluzioni direttamente su questi fogli, e utilizzare i fogli protocollo solo per la brutta: i fogli protocollo verranno ritirati, ma non
verranno corretti. Non è gradito l’uso delle matite: si deve utilizzare una
penna.
• Non si possono utilizzare libri o appunti, né tenere telefoni cellulari o altri
dispositivi di comunicazione, neanche se spenti. Il tempo a disposizione è
di due ore.
• Si consiglia di non dare soltanto le soluzioni, ma anche i ragionamenti
che hanno portato alla soluzione. Questo ci permetterà di valutare anche
risposte parziali o parzialmente false.
Firma per la presa visione delle istruzioni:
1
1
Multiple choice
1. Come viene rappresentata l’associazione uno a molti nel modello logico?
(a) L’identificatore univoco dell’entita’ di arrivo diventa chiave esterna
del’entita’ di partenza associata.
(b) L’identificatore univoco dell’entita’ di partenza diventa chiave esterna
del’entita’ di arrivo associata.
(c) Viene creata una nuova entita’ che contiene le chiavi della prima e
della seconda entita’.
(d) Viene creata una nuova entita’ che contiene solo gli attributi che non
sono chiavi.
2. Cosa si intende con normalizzazione?
(a) E’ una tecnica di verifica dei risultati della progettazione di una base
di dati.
(b) E’ una metodologia di progettazione.
(c) Ambedue le risposte precedenti sono vere.
(d) Nessuna delle risposte precedenti e’ vera.
3. Quando si dice che una transazione rispetta la proprieta’ di durabilita?
(a) Se tutte le operazioni che la compongono sono affidabili.
(b) Se tutte le operazioni che la compongono sono completate, oppure
sono disfatte, come se non fossero mai state eseguite.
(c) Se rende permanenti le modifiche effettuate immediatamente dopo il
termine della transazione.
(d) Se e’ eseguita nel sistema contemporaneamente ad altre transazioni,
come se fosse l’unica ad essere eseguita.
4. In cosa consiste la fase di progettazione logica?
(a) La descrizione verbale di uno problema.
(b) La traduzione di una descrizione verbale verso uno schema E/R.
(c) La traduzione di una schema E/R verso la costruzione di un’elenco
di tabelle.
(d) La traduzione verso SQL.
5. In algebra relazionale, la cardinalità di una differenza tra due relazioni r1
e r2 (|r1 − r2|, assumendo che la differenza sia ben definita) è:
(a) sempre compresa tra 0 e |r1|.
(b) sempre compresa tra 0 e |r2|.
(c) sempre compresa tra min(|r1|,|r2|) e max(|r1|,|r2|).
(d) nessuna delle risposte precedenti.
6. Nella fase di ristrutturazione di uno schema ER, una generalizzazione
senza associazioni:
2
(a) Può essere ristrutturata mantenendo solo l’entità padre solo se la
generalizzazione è esclusiva.
(b) Può sempre essere ristrutturata mantenendo solo l’entità padre.
(c) Può essere ristrutturata mantenendo solo l’entità padre solo se la
generalizzazione è totale.
(d) Non può essere ristrutturata mantenendo solo l’entità padre.
3
2
Query
Si considerino le seguenti tabelle:
Socio
numeroTessera
1111
2222
3333
Prestito
articolo
dvd1
dvd1
dvd2
dvd3
dvd1
Dvd
codice
dvd1
dvd2
dvd3
dvd4
nome
Paolo
Mario
Giovanni
numeroTessera
1111
1111
1111
2222
3333
cognome
Rossi
Verdi
Bianchi
dataInizio
1/1/2013
10/1/2013
1/1/2013
1/1/2013
17/1/2013
titolo
Ultimo dei templari (2011)
Social network (the)
Discorso del re (Il)
Fast and Furious 5
credito
20
15
14.20
dataFine
10/1/2013
15/1/2013
10/1/2013
10/1/2013
22/1/2013
genere
Fantasy
Drammatico
Drammatico
Thriller
(Importante: il contenuto delle tabelle è solamente un esempio; non possono trarsi conclusioni sull’assenza o la completezza dei dati—ad esempio, non
è garantito che non ci siano altri dvd oltre a quelli mostrati qui)
1. Scrivere in SQL una query che restituisce i cognomi dei soci che hanno
preso in presito piu’ di due DVD di genere drammatico.
2. Scrivere in SQL una query che restituische i cognomi dei soci che hanno
preso in prestito un dvd lo stesso giorno.
3. Scrivere in algebra relazionale una query che restituisce i numeri di tessera
dei soci che non hanno mai chiesto una proroga del prestito di un dvd.
4. Scrivere in algebra relazionale una query che restituisce i cognomi dei soci
che hanno piu’ di 10 euro di credito, che non hanno preso in prestito un
dvd in data 10/01/2013.
4
3
Progettazione ER: MUSEO
Progettare lo schema ER relativo ad un museo contenente informazioni su:
1. Le opere (di cui sono rilevanti: il codice dell’opera, nome, periodo storico,
valore).
2. Gli autori (di cui sono rilevanti: nome, cognome, data di nascita).
3. Le sale (di cui sono rilevanti: il nome, altezza, larghezza, lunghezza).
4. Le zone (di cui sono rilevanti: il codice della zona, orario di visita).
5. I custodi (di cui sono rilevanti: il codice del custode, nome, cognome,
numero di cellulare).
Il museo e’ composto da diverse zone, ciascuna comprendente un certo numero
di sale.
Una sala appartiene ad una ed una sola zona.
Ogni zona ha un orario di visita ed e’ custodita giornalmente da uno ed un
solo custode secondo un turno settimanale che resta invariato.
L’orario di visita di una zona e’ sempre lo stesso.
Il turno settimanale definisce per ciascun custode la zona di cui si deve
occupare per ciascun giorno della settimana.
Durante una settimana un custode non puo’ custodire piu’ di una volta la
stessa zona.
Non ci sono autori con stesso nome e cognome.
Non ci sono sale con lo stesso nome.
Ciascuna sala contiene opere d’arte.
Le opere d’arte si dividono in: dipinti e sculture.
5
Laboratorio
Sia dato l’indice B+Tree secondario rappresentato in figura. I primi (n-1)
puntatori di ogni foglia puntano a liste di identificatori di record RID, non
rappresentati in Figura.
Si assuma che l’albero sia utilizzato per indicizzare un file di 12.000 record,
in cui ogni blocco contiene un record. I valori della chiave di ricerca presenti nel
file corrispondono ovviamente ai valori presenti nelle foglie dell’indice. Inoltre,
si assuma che in ogni blocco delle liste di RID siano presenti 100 RID, e che la
radice dell’albero sia mantenuta in memoria centrale.
1. Nel file vengono inseriti alcuni record, tutti con chiave di ricerca 42. Si
disegni l’albero dopo gli inserimenti (senza rappresentare le liste di RID).
2. A partire dal B+tree generato al punto 1, si stimi nel caso medio il numero
di accessi a disco necessari per recuperare i record con chiave di ricerca
32.
3. A partire dal B+tree generato al punto 1, si stimi nel caso medio il numero
di accessi a disco necessari per recuperare i record con chiave di ricerca
41.
Per i punti 2 e 3 si mostrino anche i passaggi intermedi, non solo il risultato
finale.
6
Esame basi di dati 21 Gennaio 2013: Traccia
(1) Multiple choice
1-b; 2-a; 3-c; 4-c; 5-a; 6-b.
(2) Query
1. SELECT cognome
FROM Socio, Prestito, Dvd
WHERE Socio.numeroTessera=Prestito.numeroTessera and
Dvd.genere=’Drammatico’ and
Prestito.articolo=Dvd.codice
GROUP BY Socio.cognome
HAVING COUNT(*) > 2
2. SELECT DISTINCT S.cognome
FROM Prestito AS P1, Prestito AS P2, Socio AS S
WHERE P1.dataInizio = P2.dataInizio and
P1.numeroTessera=S.numeroTessera
and P1.numeroTessera <> P2.numeroTessera
3. πN umeroT essera (P restito) − πN umeroT essera
(P restito ./DataFine=DataInizio∧Articolo=Articolo∧NumeroTessera=NumeroTessera P restito)
4. Il numero di tessera dei soci che hanno piu’ di 10 euro di credito meno il
numero di tessera dei soci che hanno preso in prestito un dvd il 10 Gennaio
2013.
R1=πN umeroT essera (σcredito>10 (Socio))−πN umeroT essera (σDataInizio≥0 10/01/20130 (P restito))
Il risultato in join con Socio per ottenere il cognome dei soci:
πCognome (Socio ./NumeroTessera=NumeroTessera R1)
7
(3) E/R
Poiche’ durante una settimana un custode non puo’ custodire piu’ di una volta la stessa zona, la rappresentazione dei turni puo’ avvenire tramite l’attributo
Giorno dell’associazione custodita da tra le entita’ Custode e Zona.
(4) Laboratorio
1. Il B+tree dopo l’inserimento di 42:
2. 2 accessi, di cui 1 per livello (esclusa la radice). Non essendo presente la
chiave cercata, non vi sono record con valore 32.
3. 2 accessi per ottenere il puntatore alla lista di RID. Abbiamo 12.000 record
e 12 valori distinti, per cui in media 1000 record con valore 41. Per cui
servono 1000/100 =10 accessi per recuperare la lista di RID, e 1000 accessi
al file, essendoci un record per blocco. In tutto, 1012 accessi.
8