BASI DI DATI

(CFU 9)

Prof. Angelo Montanari



Finalità


Obiettivo fondamentale del corso è l’acquisizione dei concetti, delle metodologie e degli strumenti fondamentali nel campo delle basi di dati, con particolare attenzione ai modelli (concettuale, logico e fisico), ai linguaggi (di definizione, di interrogazione e di aggiornamento) e all’architettura dei sistemi per basi di dati. Vengono descritti in dettaglio i linguaggi per la definizione, l’interrogazione e l’aggiornamento dei dati (algebra relazione, calcolo relazionale, SQL). Vengono, inoltre, forniti elementi di progettazione concettuale (analisi e raccolta dei requisiti, costruzione di modelli Entità/Relazioni), logica (ristrutturazione di schemi concettuali, trasformazione di schemi concettuali in schemi logici, normalizzazione dei dati) e fisica (strutture di indicizzazione) di basi di dati. Infine, viene introdotta la nozione di transazione e vengono analizzate le componenti principali di un DBMS.

Dopo aver superato l’esame si ritiene che lo studente sia in grado di formalizzare in un linguaggio relazionale operazioni di definizione e manipolazione dei dati espresse in linguaggio naturale e di progettare semplici basi di dati a livello concettuale (costruzione di schemi Entità/Relazioni a partire da insiemi di requisiti espressi in linguaggio naturale), logico (trasformazione di schemi Entità/Relazioni in schemi relazionali, normalizzazione di schemi relazionali) e fisico (definizione degli opportuni indici).



Programma 2016/17


Parte 1 - Concetti di base

Ruolo e funzionalità di una base di dati; astrazioni sui dati; modelli concettuali, logici e fisici dei dati; istanze e schemi; indipendenza logica e fisica dei dati; linguaggi per la definizione e la manipolazione dei dati; i sistemi per la gestione delle basi di dati (DBMS); amministratore e utenti di una base di dati; il dizionario dei dati; la struttura generale di una base di dati.


Parte 2 - Il modello Entità/Relazioni (ER)

Metodologie, tecniche e modelli per il progetto di una base di dati: il ciclo di vita dei sistemi informativi e le metodologie di progettazione di basi di dati; i costrutti di base del modello concettuale Entità/Relazioni (ER): tipi e istanze di entità e relazioni, attributi (semplici, composti, a singolo valore, a valore multiplo, opzionali, derivati) e chiavi (identificatori interni ed esterni, le nozioni di entità debole, entità proprietaria, chiave parziale e relazione identificante), dominio di un attributo e utilizzo dei NULL, vincoli associati alle relazioni (partecipazione e rapporto di cardinalità), relazioni ricorsive e ruoli, relazioni di grado superiore al secondo, i diagrammi ER; documentazione di schemi ER: tecniche di documentazione, regole aziendali (vincoli di integrità e regole di derivazione); costrutti avanzati del modello ER: specializzazioni e categorie. Modellazione dei dati in UML: i diagrammi delle classi (classi, associazioni, molteplicità, identificatori, generalizzazioni).


Parte 3 - Il modello relazionale

Nozioni di base, definizione delle relazioni, definizione dei vincoli sulle relazioni (che coinvolgono un'unica relazione o più relazioni), schemi e istanze di una base di dati relazionale, operazioni di aggiornamento delle relazioni, politiche di reazione alle violazioni dei vincoli.


Parte 4 - La progettazione delle basi di dati.

La progettazione concettuale dei dati: raccolta e analisi dei requisiti, criteri generali di rappresentazione, strategie di progetto, qualità di uno schema concettuale, strumenti CASE per la progettazione dei dati; la progettazione logica dei dati: analisi delle prestazioni su schemi ER, ristrutturazione di schemi ER (analisi delle ridondanze, eliminazione delle gerarchie, partizionamento/accorpamento di entità e/o relazioni, scelta degli identificatori principali), traduzione del modello ER nel modello relazionale; cenni alla teoria della progettazione delle basi di dati relazionali: dipendenze funzionali, ragionamento sulle dipendenze funzionali, scomposizione di relazioni, scomposizioni lossless-join, scomposizioni che conservano le dipendenze, forme normali per gli schemi di relazione (1NF, 2NF, 3NF e BCNF), scomposizioni in 3NF che conservano le dipendenze.


Parte 5 - L'algebra relazionale e il calcolo relazionale

L'algebra relazionale: le operazioni di base, interrogazioni in algebra relazionale, operazioni derivate, operazioni addizionali, ottimizzazione algebrica, i limiti dell'algebra relazionale; il calcolo relazionale: nozioni di base, calcolo relazionale su domini, calcolo relazionale su tuple con dichiarazioni di range, confronto tra il calcolo relazionale su domini e il calcolo relazione su tuple con dichiarazione di range, il legame tra calcolo relazionale e algebra relazionale.


Parte 6 - Il linguaggio SQL

La definizione dei dati in SQL; interrogazioni in SQL; istruzioni di aggiornamento in SQL; altre definizioni dei dati in SQL (vincoli di integrità generici, viste, specifica di vincoli di addizionali sotto forma di asserzioni); il DBMS Oracle Express Edition; cenni a SQL e linguaggi di programmazione (trigger, funzioni e procedure).


Parte 7 - XML

Introduzione a XML, gli elementi XML, gli attributi XML, documenti XML, XML parser, applicazioni di XML, XML e basi di dati, il linguaggio DTD, dichiarazioni di tipo di un documento XML, validità di un documento XML e modalità di validazione, DTD e schemi relazionali, DTD e XML Schema, linguaggi di interrogazione XML, XPath e XQuery.


Parte 8 – L'organizzazione fisica dei dati.

Memorizzazione dei record ed organizzazione dei file primari: introduzione, strumenti e tecniche per la gestione della memoria secondaria, memorizzazione di file di record su disco, operazioni sui file, file di record non ordinati, file di record ordinati, tecniche di hashing, altre possibili organizzazioni dei file primari, uso della tecnologia RAID per parallelizzare l’accesso a disco. Strutture di indicizzazione dei file: indici ordinati di singolo livello (primari, di clustering, secondari), indici multilivello statici, indici multilivello dinamici che utilizzano B-alberi e B+-alberi, altri tipi di indice (cenni).


Parte 9 – Tecnologia delle basi di dati centralizzate.

La nozione di transazione: introduzione, proprietà delle transazioni, scheduling e recupero delle transazioni, tecniche di serializzazione, supporto alle transazioni in SQL. Il gestore del buffer: architettura del buffer manager, primitive per la gestione del buffer, politiche di gestione del buffer, relazione tra il gestore del buffer e il file system. Tecniche di controllo della concorrenza: problematiche, architettura, anomalie delle transazioni concorrenti, tecniche basate su viste, conflitti, locking a due fasi (2PL e 2PL stretto) e timestamp, tecniche multiversione, granularità dei dati. Tecniche di controllo dell’affidabilità: concetti di base, architettura del controllore dell’affidabilità, la nozione di memoria stabile, organizzazione del log, gestione delle transazioni, gestione dei guasti. Elaborazione e ottimizzazione delle interrogazioni: i cataloghi di sistema; ottimizzazione delle interrogazioni (rappresentazione interna delle interrogazioni, profili delle relazioni, ottimizzazione basata sui costi); progettazione fisica di una base di dati.


Bibliografia


Testi adottati:

R. Elmasri, S. Navathe, Fundamentals of Database Systems (7th Edition), Pearson International Education / Addison Wesley, 2016. 

P. Atzeni, S. Ceri,  P. Fraternali, S. Paraboschi, R. Torlone, Basi di Dati (quarta edizione), McGraw-Hill, 2014.


Altri testi di riferimento:

A. Silberschatz, H. F. Korth, S. Sudarshan. Database System Concepts (5th Edition), McGraw-Hill, 2005.

A. Albano, G. Ghelli, R. Orsini. Fondamenti di basi di dati,, Zanichelli, 2005.

J.D. Ullman, Principle of Database and Knowledge Base Systems I – II, Computer Science Press, 1989. (Trad. it.

Basi di dati e di conoscenza, Gruppo Editoriale Jackson, 1991.)

S.Abiteboul, R.Hull, V. Vianu. Foundations of Databases, Addison-Wesley, 1995.

C. J. Date. An Introduction to Databases Systems (7th Edition), Addison-Wesley, 2000.



DATABASES

(CFU 9)

Prof. Angelo Montanari


Objectives


The main goal of the course is the acquisition of basic concepts, methodologies, and tools of the database field, with a special attention to models (conceptual, logical, and physical), languages (definition, query, and update languages), and DBMS architectures. The course gives a detailed account of languages for data definition, query, and update (relational algebra, relational calculi, SQL). Moreover, it illustrates the distinctive features of database conceptual design (requirement collection and analysis, synthesis of ER schemas), logical design (conceptual schema reconstruction, mapping of conceptual schema into logical ones, data normalization), and physical design (indexing structures). Finally, it introduces the fundamental notion of transaction and it will provide an in-depth analysis of the main components of a DBMS.

Students that get a pass in databases are expected to be able to formalize in a relational language data definition, query, and update operations expressed in natural language, as well as to be able to design simple databases at conceptual level (design of ER schema starting from a set of requirements in natural language), logical level (mapping of ER conceptual schemas into relational ones, normalization of relational schemas), and physical level (definition of suitable indexes).




Program 2016/17


Part 1 – Basic concepts

Role and functionalities of a database; data abstractions; conceptual, logical, and physical data models; schemas and instances, logical and physical data independence; data definition and data manipulation languages; Database Management Systems (DBMSs); database administrator and database users; data dictionary; the structure and modules of a DBMS.


Part 2 – The Entity/Relationship (ER) model

Methodologies, techniques, and models for database design: the life cycle of an information system; methodologies for database design; the basic constructs of the Entity/Relationship (ER) model: entity types and instances, relation types and instances, attributes (simple, compound, single-valued, multiple-valued, optional, derived), keys (internal and external identifiers, the notions of weak entity, owner entity, partial key and identifying relation); attribute domains and the use of NULL; constraints associated with relations (participation constraints and cardinality ratios); recursive relations and roles; binary relations and relations with arity greater than two; ER diagrams; documentation of ER schemas; documentation techniques; business rules (integrity constraints and derivation rules); advanced ER constructs: specialization and category. UML data modelling: class diagrams (class, association, multiplicity, identifier, generalization).


Part 3 – The relational data model

Basic notions, the definition of relation, the definition of relational model constraints (constraints about a single relation and constraints involving more than one relation), relational database schemas and instances, update operations (insertion, deletion, modification) and possible constraint violations, constraint violation policies.


Pari 4 – Database design

The conceptual design: requirement collection and analysis; general criteria for data representation; design strategies; qualities of a conceptual schema; CASE tools for database design. The logical design: performance analysis on ER schemas; restructuring of ER schemas (redundancy analysis, elimination of specialization hierarchies, partitioning/ merging of entities/relations, the choice of the primary identifier); mapping of ER schemas into relational schemas. The theory of the logical design of relational databases: functional dependencies, reasoning about functional dependencies, relation decomposition, lossless join decompositions, decompositions that preserve functional dependencies, normal forms for relation schemas (1NF, 2NF, 3NF e BCNF), lossless join decomposition in 3NF that preserve functional dependencies.


Part 5 – The relational algebra and the relational calculus

Relational algebra: basic operations, queries in relational algebra, derived operations, additional operations, algebraic optimization, the limitations of relational algebra; the relational calculus: basic notions, domain relational calculus and tuple relational calculus with range specification, the relationships between domain relational calculus and tuple relational calculus with range specification, the relationships between relational calculi and relational algebra.


Part 6 – The SQL language

SQL data definition and data types; queries in SQL; update statements in SQL; additional data definition features (generic integrity constraints, views, specifying constraints as assertions); the DBMS Oracle Express Edition, notes on SQL and programming languages (triggers, procedures, and functions).


Parte 7 – XML

Introduction to XML, XML elements, XML attributes, XML documents, XML parser, XML applications, XML and databases, the DTD language, XML document type declaration, validity of an XML document, validation methodologies, DTD and relational schemas, DTD and XML Schema, XML query languages, XPath e Xquery.


Part 8 – Physical organization of data

The storage of file records and the organization of primary files: introduction, devices and techniques for the management of secondary storage, placing file records on disks, operations on files, files of unordered records (heap files), files of ordered records (sorted files), hashing techniques, other primary file organizations, efficient disk access by means of RAID technology. Indexing structures for files: types of single-level ordered indexes (primary, clustering, secondary), static multilevel indexes, dynamic multilevel indexes using B-trees and B+-trees, other types of indexes.


Part 9 – Database server technology

The notion of transaction: introduction to transaction processing, properties of transactions, transaction scheduling and recovery, serialization techniques, transaction support in SQL. Buffer manager: architecture of the buffer manager, primitives for buffer management, buffer management policies, on the relationships between the buffer manager and the file system. Concurrency control techniques: problems, architecture, anomalies of concurrent transactions, view-based techniques, conflict-based techniques, two-phase locking techniques (2PL and strict 2PL), concurrency control based on timestamp ordering, multiversioning-based techniques, granularity of data items. Database recovery techniques: basic concepts, architecture, the notion of stable memory, organization of the log, transaction processing, fault management. Query processing and optimization: system catalogs, query optimization (query internal representation, relation profiles, cost-based optimization), physical design of databases.


References:


Main references:

Testi adottati:

R. Elmasri, S. Navathe, Fundamentals of Database Systems (7th Edition), Pearson International Education / Addison Wesley, 2016. 

P. Atzeni, S. Ceri,  P. Fraternali, S. Paraboschi, R. Torlone, Basi di Dati (quarta edizione), McGraw-Hill, 2014 (in Italian).


Additional references:

A. Silberschatz, H. F. Korth, S. Sudarshan. Database System Concepts (5th Edition), McGraw-Hill, 2005.

A. Albano, G. Ghelli, R. Orsini. Fondamenti di basi di dati,, Zanichelli, 2005 (in Italian).

J.D. Ullman, Principle of Database and Knowledge Base Systems I – II, Computer Science Press, 1989.

S.Abiteboul, R.Hull, V. Vianu. Foundations of Databases, Addison-Wesley, 1995.

C. J. Date. An Introduction to Databases Systems (7th Edition), Addison-Wesley, 2000.