Programma

• Introduzione

Caratteristiche generali dei DBMS e loro funzioni: modelli di dati e queries, livelli di astrazione schemi e istanze di un database, indipendenza dei dati. Linguaggi dei DBMS. Architettura di sistema di un database. Classificazione dei principali DBMS.
 

• Basi di dati classiche

Modello Entità/Relazioni e diagrammi relativi.
Modello relazionale: relazioni, attributi, chiavi. Traduzione di un diagramma E/R in modello relazionale.
Algebra relazionale: operazioni sulle relazioni e loro proprietà algebriche; espressione di queries in algebra relazionale; navigazione tra relazioni e problemi di efficienza del join.
Calcolo relazionale su n-ple e su domini: valutazione ridotta e non delle formule, completezza del calcolo relazionale, formule indipendenti dai domini e formule sicure, equivalenza tra algebra relazionale e calcolo relazionale su formule sicure.
Esempi di linguaggi e DBMS relazionali: SQL, Informix.
Progettazione di database relazionali: le principali anomalie; dipendenze funzionali, chiusura di un insieme di dipendenze; assiomi di Armstrong e relative proprietà, chiusura di un insieme di attributi, equivalenza tra insiemi di dipendenze, copertura minima; decomposizione senza perdita di join, decomposizione che preserva le dipendenze; seconda e terza forma normale, forma normale di Boyce-Codd e decomposizioni relative.
Cenni ai modelli reticolare, gerarchico, a oggetti.
 

• Strutture dati e organizzazione fisica dei database

Nozioni preliminari: record fisico, campi, tipi, formato di un record, file, blocchi e costi di accesso al database fisico; organizzazione di un record e di un blocco.
Strutture hash e relativi algoritmi di inserimento.
Alberi bilanciati: alberi di ricerca binaria, B-alberi e varianti principali, i relativi algoritmi di costruzione delle strutture e di ricerca.
Cenni alle organizzazioni di file.
Alberi di ricerca multidimensionali: alberi k-dimensionali e relativi algoritmi.
 
• Information Retrieval (lezioni integrative tenute dal prof. Dario Lucarella)

Strutture dati per IR: architettura di un sistema per la archiviazione ed il reperimento di documenti; metodi di accesso al testo; organizzazione di dizionari.
Modelli di IR: booleano, probabilistico, fuzzy. Valutazione e ottimizzazione della query. Formule di istanza e somiglianza. Strategie di ricerca; strategie di nearest neighbour searching. Indici di valutazione.
Problemi applicativi. Indicizzazione automatica. Esaustività e precisione.
 

• Modelli logici

Datalog: sintassi del linguaggio, base di dati estensionale e intenzionale, regole sicure, interpretazione e modello di un insieme di regole.
Valutazione di regole sicure senza negazione. Valutazione di regole con negazione. Confronto tra datalog e algebra relazionale.
 
• Logiche costruttive e basi di dati (lezioni integrative tenute dal prof. Ugo Moscato)

L'approccio costruttivo al problema dell'informazione incompleta.
Semantica delle logiche costruttive e relativi calcoli; confronto tra il modello relazionale e quello deduttivo.

Testi di riferimento

• Atzeni, Batini, De Antonellis, La teoria relazionale dei dati , Boringhieri, 1985.
• J.D. Ullman, Principles of database and knowledge-based systems, Computer Science Press, 1988.