Dipartimento di Informatica e Scienze dell'Informazione
Corso di Documentazione Automatica
Programma
Testi consigliati
Modalita' di esame
Testo Esercitazione
Generalita'
(Korth e Silberschatz,
Ullman 88)
Aspetti
distintivi. Concetti e termini base. Livelli di
astrazione. Linguaggi di definizione e di manipolazione dei dati. Struttura
di un DBMS.
Modelli tradizionali dei dati
Generalita'.
- Il modello Entity-Relationship.
( Batini et al. 92) Concetti base (entita', relazioni, attributi,
cardinalita').
Diagrammi E-R. Trasformazione di diagrammi
E-R in schemi relazionali. Vincoli di
integrita', chiavi e dipendenze di esistenza. Gerarchie di generalizzazione.
- Il modello relazionale.
(Korth e Silberschatz,
Ullman 88, Date e Darwen 92)
Concetti base (schema, relazione, tupla). Algebra relazionale. Operazioni
derivate (intersezione,
join, divisione). Calcolo
relazionale. Potere espressivo dell'algebra relazionale e del calcolo
relazionale.
Safe relational calculus. Linguaggi "commerciali": SQL
(query language, funzioni di gruppo, DDL e DML, view, modifiche su view,
cataloghi),
Quel, QBE.
- Il modello reticolare.
(Korth e Silberschatz,
Ullman 88) Concetti base (record, link). Diagrammi data-structure.
Trasformazione di diagrammi E-R in diagrammi data-structure. Modello DBTG
(set, owner,
member). Confronto tra modello relazionale e reticolare. Linguaggio di accesso,
operazioni di modifica.
Database deduttivi
(Ullman 88,
Abiteboul et al. 95) Aspetti
introduttivi. Il linguaggio Datalog.
Semantica model-theoretic, di punto fisso, operazionale. Risoluzione SLD.
Differenze tra
Datalog e Prolog. Vincoli di integrita'. Cenni ad aggiornamenti nelle basi
di dati
deduttive ed estensioni del Datalog.
Approccio object
oriented
(Wegner 87, Goldberg e
Robson 83, Meyer 88, Stroustrup 87,
Lippmann 93)
Motivazioni. Classificazione di Wegner (object based, class based, object
oriented).
Nozione di oggetto e confronto con nozione di tipo di dato. Nozione di
classe, object
identity, clientship, object sharing. Inheritance, polimorfismo,
overriding, late
binding, tipo statico e dinamico. Problemi legati ad inheritance e
sottotipazione.
Linguaggio Smalltalk, cenni ad Eiffel, linguaggio C++.
Data base orientati ad oggetti
(Comm. ACM 91)
Motivazioni.
Limiti dei database relazionali.
Caratteristiche generali. Approccio relazionale esteso. Approccio ad
oggetti persistenti
(gestione della persistenza, persistenza per ereditarieta' e riferimento).
Sistema
Gemstone e sistema Ode.
Teoria della normalizzazione
(Ullman 88)
Aspetti introduttivi e
motivazioni.
Dipendenze funzionali, chiusura di un insieme di dipendenze funzionali,
assiomi di Armstrong, regole derivate. Chiusura di uno schema rispetto ad
un insieme di dipendenze
funzionali. Teorema di soundness e completezza degli assiomi di Armstrong.
Algoritmo per il calcolo della chiusura di uno schema e sua correttezza.
Equivalenza tra insiemi di dipendenze. Ricoprimenti minimali. Algoritmo per
trovare
un ricoprimento minimale.
Decomposizioni lossless join. Algoritmo per testare se una decomposizione
e' lossless
join e sua correttezza. Versione per decomposizioni in due schemi.
Decomposizioni che
preservano le dipendenze funzionali. Proiezione di un insieme di
dipendenze. Test
di preservazione delle dipendenze.
Forme normali per schemi di relazioni: forma normale di Boyce-Codd, terza
forma normale.
Motivazioni. Algoritmo per produrre una decomposizione lossless join in
BCNF e sua
correttezza. Versione "efficiente" e sua correttezza. Algoritmo per
produrre una
decomposizione in 3NF che preservi le dipendenze e sua correttezza.
Algoritmo per produrre una
decomposizione lossless join in 3NF che preservi le dipendenze e sua
correttezza.
Architettura di un DBMS
(Ciaccia e Maio 95,
Korth e Silberschatz)
Struttura generale di un DBMS, supporti di memorizzazione, record a
lunghezza fissa
e variabile, organizzazione in blocchi. File sequenziali con indice, indici
densi e sparsi, B-tree, hashing statico e dinamico
(hashing virtuale, hashing estendibile).
Elaborazione di query
(Ciaccia e Maio 95,
Korth e Silberschatz,
Ullman 89)
Equivalenza di espressioni nell'algebra relazionale.
Principi per l'ottimizzazione algebrica. Stima del costo di esecuzione di
una query: fattori di selettivita', stima delle dimensioni dei risultati
intermedi.
Strategie per l'esecuzione del join naturale (iterazione semplice,
iterazione orientata
ai blocchi, merge-join, uso di indici, three-way join). Un esempio:
l'ottimizzatore del System R.
Autorizzazione
Ciaccia e Maio 95,
Korth e Silberschatz)
Politiche di autorizzazione. Modelli discrezionali e mandatori.
Cenni su problemi di controllo del flusso dei dati.
L'autorizzazione nel System R: comandi di Grant e Revoke, struttura dei
cataloghi di autorizzazione e algoritmi di Grant e Revoke,
autorizzazione attraverso le viste.
Crash recovery
(Korth e Silberschatz,
Ullman 88)
Classificazione
delle memorie e delle failure. Operazioni sulla memoria
(input,
output, read, write). Concetto di transazione. Modello a stati della
transazione.
Log incrementale con modifiche rimandate ed immediate, e schemi di recovery
corrispondenti.
Checkpoints. Shadow pages. Failure della memoria non volatile ed implementazione
della memoria stabile.
Controllo della concorrenza
(Papadimitriou 86,
Ullman 88)
Generalita'. Nozione di entita', transazione, schedule, serializzabilita'.
Modello read/write delle transazioni. Interpretazione di una transazione,
di un passo
di uno schedule e di uno schedule. Equivalenza di schedule rispetto allo
stato finale,
computazionale e rispetto ai conflitti e caratterizzazioni di tali
equivalenze come
uguaglianze di grafi. Nozione di dead step. Test di serializzabilita' rispetto
ai conflitti. Casi particolari (Read before Write, modello delle azioni).
Cenni alla
complessita' della serializzabilita' computazionale. Nozione di
scheduler. Modo
dinamico, statico e di dichiarazione. Locking statico a due fasi, dinamico
a due fasi,
a due fasi e relativi protocolli. Locking a due fasi.
Read-write lock.
Modi di lock e matrici di compatibilita'. Timestamp scheduler e sua
implementazione.
Deadlock e livelock. Deadlock detection. Grafo di deadlock. Prevenzione del
deadlock. Trattamento di failure.
Cascading rollback. Locking a due fasi stretto. Protocolli aggressivi e
conservativi.
Database distribuiti
(Ullman 88,
Korth e Silberschatz)
Generalita'. Item e transazioni locali e globali. Vantaggi e svantaggi.
Replicazione
e frammentazione orizzontale e verticale dei dati. Esecuzione di query in
un sistema
distribuito. Locking distribuito: tecniche write-locks-all, majority, k di
n, copia
primaria, token di copia primaria, nodo centrale. Commitment distribuito: blocco
delle transazioni, commit a due fasi. Deadlock in sistemi distribuiti.
Risoluzione
con time-out. Waits-for-graph. Prevenzione basata su timestamp (wait-die e
wound-die).
Database attivi.
(Ceri e Widom 96) Aspetti introduttivi. Il
paradigma E-C-A.
Modelli di esecuzione. Cenni ai linguaggi Starbust e Ode.
- H.F. Korth ed A. Silberschatz.
Database system concepts.
McGraw-Hill.
- J.D. Ullman.
Principles of database and knowledge-base systems (Vol. I).
Computer Science Press, 1988.
- S. Abiteboul, R. Hull e V. Vianu
Foundations of Databases.
Addison-Wesley, 1995.
- C. Batini, S. Ceri ed S.B. Navathe.
Conceptual database design.
Benjamin/Cummings, 1992.
Anche in italiano: La progettazione concettuale dei dati,
editore Franco Angeli.
- C.J. Date e H. Darwen.
A Guide to the SQL Standard.
Addison-Wesley, 1992.
- P. Wegner.
Dimensions of Object Based Language Design.
Proc. OOPSLA '87.
pp.168-182.
- Next-generation database systems.
Comm. ACM, Vol.34, n.10, Ottobre 1991.
- A. Goldberg e D. Robson.
Smalltalk-80: the language and its implementation.
Addison-Wesley, 1983.
- B. Meyer.
Object-oriented software construction.
Prentice Hall, 1988.
- B. Stroustrup.
The C++ Programming Language.
Addison Wesley, 1987.
- S.B. Lippmann.
C++ Primer.
Addison-Wesley, 1993.
- J.D. Ullman.
Principles of database and knowledge-base systems (Vol. II).
Computer Science Press, 1989.
- P. Ciaccia e D. Maio.
Lezioni di basi di dati.
Progetto Leonardo, Bologna, 1995.
- C. Papadimitriou.
The theory of database concurrency control.
Computer Science Press, 1986.
- S. Ceri e J. Widom.
Active Database Systems - Triggers and Rules for Advanced
Database Processing.
Morgan-Kaufmann, 1996.
Esame scritto (3-4 esercizi: ad esempio definizione di uno schema di DB,
scomposizione
in forme normali, formulazione di query, ...) + orale + esercitazione
(progettazione di un database
corrispondente ad una specifica assegnata e prototipazione utilizzando
un DBMS relazionale).
a.a. 1996/97
Il problema
Definire lo schema di una base di dati relativa alla gestione dei fondi di
ricerca
di un dipartimento.
I fondi sono identificati da un tipo,
un anno di riferimento ed un titolare (che e' un professore ordinario del
dipartimento). Ogni fondo ha inoltre un ammontare e una data di scadenza (che
puo' essere precedente o successiva all'ultimo giorno dell'anno di
riferimento).
I membri del personale possono
essere inseriti in uno o piu' fondi di ricerca.
I fondi possono essere utilizzati per rimborsare missioni, per acquistare
materiale
scientifico (ad esempio libri, hardware, software), per pagare prestazioni
d'opera
occasionali a collaboratori, per coprire le spese d'ufficio (telefono,
posta, fotocopie,
cancelleria, ...). I fondi possono essere utilizzati fino al loro
esaurimento, ma
entro la loro data di scadenza.
Per ogni membro del personale del dipartimento si vogliono memorizzare
matricola,
nome, cognome, telefono, qualifica, modalita' di pagamento scelta. Se la
modalita'
di pagamento e' accredito su conto corrente si vogliono memorizzare anche
le coordinate
bancarie del conto corrente (istituto bancario, numero filiale, numero
di conto corrente).
Una missione, effettuata da un certo membro del
dipartimento,
ha una destinazione, un motivo, una data di inizio e una data di fine, un
ammontare complessivo.
Una missione puo' essere rimborsata come rimborso spese, nel qual caso ha
una lista
spese associata, o con diaria, nel qual caso l'ammontare della missione
dipende solo
dalla durata, dalla qualifica del dipendente e dal tipo di fondi su cui e'
rimborsata.
La lista spese associata ad una missione contiene varie voci. Per ogni voce
si vuole memorizzare il tipo (es. viaggio aereo, viaggio
treno, albergo, iscrizione a convegno, ...),
l'ammontare della spesa in valuta estera e in che valuta e' espresso tale
ammontare
(es. 30 DM), la data in cui la spesa e' stata
effettuata (necessaria per determinare il cambio) e l'ammontare della spesa
in lire
italiane.
Una missione e' rimborsata su un fondo di ricerca.
Le missioni effettuate da un certo dipendente possono essere rimborsate
solo su fondi
di ricerca in cui il dipendente e' inserito.
La lista spese di una missione effettuata da un dottorando non puo'
contenere voci
di tipo "pasti".
Per ogni acquisto di materiale scientifico, effettuato da un certo membro
del dipartimento
in una certa data su un certo fondo di ricerca si assegna un codice (numero
di inventario)
e si vuole memorizzare la descrizione del materiale acquistato e il prezzo.
Se l'acquisto
e' effettuato in valuta estera, si vuole memorizzare il prezzo in valuta
estera, in che
valuta e' espresso tale prezzo e l'ammontare della spesa in lire italiane.
Un collaboratore puo' effettuare un lavoro per il dipartimento, ed essere
pagato
su un fondo di ricerca. Solo il titolare del fondo puo' effettuare pagamenti di
prestazioni d'opera occasionali a collaboratori.
Ogni prestazione d'opera ha una data d'inizio e una data di fine, e una
descrizione
del lavoro effettuato.
Per ogni prestazione d'opera si vuole memorizzare su quale fondo e' effettuato
il pagamento, in che data,
in che modo e' effettuato (contanti o bonifico su c/c, e in tal caso quale) e a
quale prestazione d'opera si riferisce.
Per ogni prestazione d'opera si vuole anche memorizzare se
e' stato sviluppato del software e se sono stati prodotti dei rapporti
scientifici.
Ogni prestazione d'opera e' prestata da un collaboratore, che puo' essere
un membro
del dipartimento solo se la sua qualifica e' dottorando. Un dottorando,
comunque,
non puo' percepire come pagamento di prestazioni occasionali piu' di 15
milioni
l'anno. Per ogni collaboratore si memorizza nome, cognome, titolo,
indirizzo, telefono,
e, se ce l'ha, numero di partita IVA.
Ogni membro del dipartimento ha delle spese d'ufficio (telefono, posta, fotocopie,
cancelleria, ...). Tali spese sono coperte dai fondi di ricerca. Per ognuna
di tali
spese (relativa ad un certo membro) si memorizza la descrizione, la data in
cui viene
effettuata e l'ammontare.
La base di dati deve fornire le seguenti possibilita'.
- Per un membro del dipartimento
- Avere una situazione globale delle spese che ha sostenuto, in particolare
avere la
lista delle missioni, degli acquisti di materiali, delle spese d'ufficio
effettuate,
con l'indicazione del fondo su cui sono state addebitate.
Per ogni fondo in cui il membro e' inserito, avere la somma complessiva da
lui spesa
su quel fondo.
- Per il titolare di un fondo di ricerca
- Avere l'ammontare attualmente disponibile sul fondo. Avere la lista e il
totale di tutte
le spese effettuate sul fondo
- per tipo di spesa (cioe': missione, acquisto materiale, prestazione
d'opera,
spese d'ufficio);
- per membro del dipartimento che le ha effettuate.
Cercare il membro del dipartimento che ha speso su quel fondo piu' di ogni
altro
e quello che ha effettuato la spesa di ammontare massimo; determinare la
spesa media
pro-capite dei membri nel fondo per missioni, acquisti, spese d'ufficio;
determinare la missione
e l'acquisto di ammontare massimo effettuate sul fondo.
- Per l'ufficio missioni
- Inserire le missioni effettuate dai membri del dipartimento. Per ogni missione,
visualizzare il totale prelevato dal fondo e, in caso di missione con lista
spese,
il dettaglio delle spese che la compongono.
- Per l'ufficio contabile
- Inserire gli acquisti di materiale, le spese d'ufficio, i pagamenti di
prestazioni occasionali.
Visualizzare tali informazioni. Visualizzare il saldo di ogni fondo.
Cercare (per
avvertire i titolari) i fondi in scadenza e i fondi il cui saldo e'
inferiore al
10% dell'ammontare iniziale.
- Per il direttore del dipartimento
- Per ogni fondo, determinare la spesa percentuale per ogni tipo (missione,
acquisto
materiale, spese ufficio, prestazioni occasionali).
Per ogni fondo, determinare la spesa percentuale per ogni membro che vi e'
inserito.
Determinare, per i collaboratori che hanno effettuato almeno due
prestazioni occasionali
diverse, la durata complessiva e l'ammontare complessivo delle loro prestazioni.
Svolgimento dell'esercitazione
Comprende i seguenti punti.
-
Definizione della struttura del database usando il modello Entity-Relationship.
-
Definizione e formalizzazione dei vincoli di integrita'.
-
Traduzione nel modello relazionale.
-
Implementazione usando Microsoft Access o DB4. In entrambi i casi, si usi SQL
per quanto e' possibile (in particolare, si indichino esplicitamente i comandi
SQL corrispondenti alle varie funzionalita' richieste sopra),
ed i linguaggi di comandi di Access/DB4 per il resto (ad esempio, gestione
di menu, gestione degli errori). Si specifichi e si giustifichi
l'eventuale uso di indici.
-
(Opzionale) Traduzione nel modello degli oggetti e stesura di uno schema di
implementazione, mettendo in evidenza le differenze con il precedente.
E' anche possibile l'implementazione utilizzando
i DBMS ad oggetti ObjectStore o Ode. In tal caso il punto 5 e'
obbligatorio,
mentre il punto 3 diviene opzionale.
I gruppi interessati ad utilizzare tali OODBMS contattino preventivamente
le docenti
per motivi organizzativi.
Consegna e valutazione
La consegna dovra' avvenire entro il 30 settembre 1997 per chi sostiene l'orale
a giugno/luglio, prima di sostenere l'orale per gli altri.
All'esercitazione verra' assegnato un voto in trentesimi; il voto finale
dell'esame
sara' determinato dalla media pesata del voto dell'esercitazione (1/3) e del
voto di scritto e orale (2/3).
Ritorno alla pagina precedente
Per suggerimenti e commenti si prega di scrivere a: Elena Zucca zucca@disi.unige.it
Ultima modifica: 12 Novembre 1997