Docente

Prof. Nicola Vitacolonna

Indirizzo e-mail

nicola.vitacolonna@uniud.it

Indirizzo Pagina Web Personale

http://sole.dimi.uniud.it/~nicola.vitacolonna/

Crediti

6 CFU

Finalità

Il corso ha lo scopo di far acquisire allo studente una conoscenza approfondita  dei metodi per la progettazione e l'implementazione di basi di dati relazionali. Il corso mira dunque a fornire adeguate competenze tecniche inerenti alle funzionalità avanzate dei Sistemi di Gestione di Basi di Dati (DBMS, DataBase Management System) attualmente in uso. Ulteriore obiettivo è presentare le tendenze più recenti nell'ambito della tecnologia delle basi di dati. Alla fine del corso lo studente sarà in grado di gestire la progettazione di una base di dati nell'intero ciclo di vita, dall'analisi dei requisiti alla manutenzione; sarà in grado di valutare le prestazioni di una basi di dati e attuare misure di correzione, nonché di realizzare adeguatamente le opportune politiche di sicurezza e privatezza dei dati; avrà inoltre assimilato i concetti e le metodologie fondamentali per la configurazione di sistemi per basi di dati distribuite e per l'analisi di dati spaziali e temporali.

Programma

• Progettazione logica di basi di dati: Dipendenze funzionali e forme normali. Insiemi canonici. Terza forma normale e forma normale di Boyce-Codd. Forme normali superiori. Tecniche di decomposizione di schemi relazionali per la rimozione di anomalie e ridondanze. Esempi di progettazione logica di basi di dati.

• Tecniche avanzate di progettazione fisica: Catalogo e statistiche della base di dati. Fattori di selettività e stime dei costi delle interrogazioni. Analisi dei piani d'esecuzione. Ottimizzazione di interrogazioni. Partizionamento dei dati. Viste materializzate. Clustering multidimensionale.

• SQL e linguaggi di programmazione: Approcci alla programmazione per basi di dati. Funzioni definite dall'utente e trigger nel linguaggio PL/pgSQL. SQL embedded statico (interrogazioni semplici e complesse, l'utilizzo dei cursori) e dinamico (esecuzione immediata ed esecuzione in due fasi). Utilizzo di librerie di funzioni: SQL/CLI (Call Level Interface), ODBC e JDBC. Realizzazione di una base di dati per un'applicazione web.

• Basi di dati spaziali: Introduzione ai GIS e dati geografici/territoriali. Rilevamento dei dati geografici e livelli di astrazione: livello concettuale (visione a campi e visione ad oggetti), livello di rappresentazione, livello di implementazione (formato raster e formato vettoriale). DBMS come componente di un GIS: approccio “naïve”, accoppiamento debole e approccio integrato. Metodi d'indicizzazione di dati spaziali: ordinamento totale vs prossimità/inclusione di oggetti, campi di ricerca e metodologia, indici space-driven e indici data-driven. Interfacciamento delle basi di dati con i GIS (QGIS). Sistemi WebGIS e standard OCG. SQL spaziale. PostGIS, estensione spaziale di PostgreSQL: tipi di dati spaziali, tabelle spaziali, creazione indici, inserimento istanze, funzioni spaziali e interrogazioni.

• Sicurezza: problematiche inerenti alla sicurezza nelle basi di dati e misure di controllo. Controllo degli accessi discrezionale (DAC). Controllo degli accessi vincolato (MAC). Controllo degli accessi basato sui ruoli (RBAC). Supporto di SQL alla sicurezza: istruzioni grant, revoke, create role. Audit trail. Caso di studio: sicurezza in MySQL, PostgreSQL e Oracle.

• Basi di dati distribuite: Sistemi shared-nothing. Speedup e scaleup. Fattori limitanti alla scalabilità: costo di startup, interferenza, asimmetria (skew) dei dati. Memorizzazione distribuita dei dati: replicazione e frammentazione. Partizionamento orizzontale dei dati: round-robin, hash e range partitioning. Elaborazione delle interrogazioni in basi di dati distribuite. Controllo della concorrenza e dell’affidabilità. Cloud computing e tecnologie recenti per la gestione distribuita dei dati. Teorema CAP. Consistenza eventuale. Sistemi BASE vs ACID. Caratteristiche generali dei software NoSQL e NewSQL. Il modello di programmazione MapReduce e una sua implementazione open-source (Hadoop). Implementazione di operatori dell'algebra relazionale in MapReduce.

Attività di Laboratorio

Sono previste almeno 10 ore di attività pratiche al calcolatore, in cui lo studente avrà modo di sperimentare le tecniche di analisi e ottimizzazione delle interrogazioni, l'uso di interfacce di programmazione per le basi di dati, nonché implementare semplici basi di dati spaziali, temporali e distribuite.

Prerequisiti

Il corso di Basi di Dati è un prerequisito fondamentale di questo corso. Inoltre, sebbene non sia obbligatorio, è raccomandabile aver frequentato, o frequentare contestualmente, un corso di algoritmi, un corso di programmazione, un corso di logica e un corso di sistemi distribuiti.

Bibliografia

Testo di riferimento

Avi Silberschatz, Henry F. Korth, S. Sudarshan, Database System Concepts, sesta edizione, McGraw-Hill, 2010.

Testi per la consultazione

Jeffrey D. Ullman, Principles of Database and Knowledge-Base Systems, Vol. 1, Computer Science Press, 1988.

Serge Abiteboul, Richard Hull, Victor Vianu, Foundations of Databases, Addison-Wesley, 1995 (http://webdam.inria.fr/Alice/).

David Maier, The Theory of Relational Databases, Computer Science Press, 1983 (http://web.cecs.pdx.edu/~maier/TheoryBook/TRD.html).

Chris Date, An Introduction to Database Systems, ottava edizione, Addison-Wesley, 2004.

Anand Rajaraman, Jeffrey D. Ullman, Jure Leskovec, Mining of Massive Datasets, Cambridge University Press, 2013 (http://infolab.stanford.edu/~ullman/mmds.html).

Durante il corso sono inoltre forniti articoli di approfondimento e dispense del docente.

Tutti i testi usati nel corso sono disponibili in biblioteca ovvero accessibili gratuitamente online.

Modalità d'esame

L'esame consiste in un progetto individuale, che ha l'obiettivo di approfondire alcuni temi studiati durante il corso. Tale progetto è valutato attraverso la compilazione di un form online e una successiva presentazione orale di circa venti minuti.

Orario di ricevimento

Martedì, ore 15:00–17:00, o su appuntamento.

*********************************************************************************************

Aims

The overall aim of the course is to acquire an in-depth knowledge on the methods for the logical and physical design of relational databases. The main goal is to receive adequate technical competences about some advanced features of current database management systems (DBMSs). Another goal is to gain a thorough understanding of state-of-the-art database technologies and recent trends. At the end of the course, the student will be able to manage the whole life cycle of a database, from requirement analysis to maintenance. Besides, the student will be able to evaluate and tune the performance of a database, will have built up the ability to correctly implement suitable security and privacy policies, and will have learned the concepts and methodologies for the development of distributed systems and for the analysis of spatial and temporal data.

Program

• Logical Database Design: Functional dependencies and normal forms. Canonical sets of functional dependencies. Third normal form and Boyce-Codd normal form. Higher normal forms. Techniques for the decomposition of relational schemas to eliminate update anomalies and redundancy. Examples of database logical designs.

• Advanced Physical Database Design: Catalog and statistics of the database. Selectivity factors. Cost estimation. Analysis of query plans. Query optimization. Data partitioning. Materialized views. Multidimensional clustering.

• SQL and Programming Languages: Approaches to the database programming. User-defined functions and triggers in PL/pgSQL. Static embedded SQL (simple and complex queries, the use of cursors), dynamic embedded SQL (immediate execution and two-phase execution). Database programming with function calls: SQL/CLI (Call Level Interface), ODBC e JDBC. Development of a database for a web application.

• Spatial databases: Introduction to GIS and geographical data. Acquisition of geographical data and abstraction levels: conceptual level, representation level, implementation level. A DBMS as a component of a GIS system: “naïve” approach, weak coupling and integrated approach. Indexing of spatial data:

total ordering vs object proximity/inclusion, search fields, space-driven and

data-driven indexes. Interfaces between DBMSs and GIS systems (QGIS). WebGIS and

the OCG standard. Spatial SQL. PostGIS, a spatial extension of PostgreSQL: data types for spatial data, spatial tables, creation of indexes, data insertion, spatial functions and queries.

• Security: database security issues and control measures. Discretionary Access Control (DAC). Mandatory Access Control (MAC). Role-Based Access Control (RBAC). SQL's support to security: grant, revoke, create role. Audit trail. Case study: security in MySQL, PostgreSQL and Oracle.

• Distributed Databases: Shared-nothing architectures. Speedup and scaleup. Limiting factors to scalability: startup cost, interference, data skew. Physical organization of distributed data: replication and fragmentation. Horizontal partitioning of data: round-robin partitioning, hash partitioning and range partitioning. Query processing in distributed databases. Concurrency and reliability control. Cloud computing and recent technologies for distributed data management. CAP Theorem. Eventual consistency. BASE vs ACID. General features of NoSQL and NewSQL software. The MapReduce programming model and an open-source implementation (Hadoop). Implementation of relational algebra using MapReduce.

Practice

The course includes at least 10 hours of training activities to carry on at the computer. The students will practice with the analysis and optimization of database queries and with database programming interfaces. They will also implement simple spatial, temporal and distributed databases.

Prerequisites

 An introductory database course covering relational algebra, SQL, transactions, conceptual and basic logical design is a prerequisite for this course. Some background in algorithmic theory, programming, logic and distributed systems is also recommended, although not mandatory.

Bibliography

Textbook

Avi Silberschatz, Henry F. Korth, S. Sudarshan, Database System Concepts, sixth edition, McGraw-Hill, 2010.

 Recommended reading

Jeffrey D. Ullman, Principles of Database and Knowledge-Base Systems, Vol. 1, Computer Science Press, 1988.

Serge Abiteboul, Richard Hull, Victor Vianu, Foundations of Databases, Addison-Wesley, 1995 (http://webdam.inria.fr/Alice/).

David Maier, The Theory of Relational Databases, Computer Science Press, 1983 (http://web.cecs.pdx.edu/~maier/TheoryBook/TRD.html).

Chris Date, An Introduction to Database Systems, eighth edition, Addison-Wesley, 2004.

Anand Rajaraman, Jeffrey D. Ullman, Jure Leskovec, Mining of Massive Datasets, Cambridge University Press, 2013 (http://infolab.stanford.edu/~ullman/mmds.html).

During the course, additional research articles and course notes will be provided.

All the texts used in the course are freely available at our library or online.

Exam

The students are required to complete an individual project, whose purpose is to further develop some of the topics discussed during the course. The projects will be evaluated through an online form, which the students will be asked to fill out, and a twenty-minute presentation of their work.

Office hours

By appointment.

Information for Erasmus students

The course will be held in English upon request. The project can be prepared in English, Spanish, or Italian.