Computer Science

Activity type

Discipline Informatiche

SSD

INF/01

Year

N/D

Semester

N/D

CFU

6

Hours distribution

36 classroom hours, 24 training hours

Lecturers

Activity type

Discipline Informatiche

SSD

INF/01

Year

N/D

Semester

N/D

CFU

6

Hours distribution

36 classroom hours, 24 training hours

Lecturers

MARIA DE MARSICO

General goals:
To be able to design/evaluate the properties, storage structure and protocols of a database management system.
To introduce students to scalable methodologies for the design and development of database software applications.

Specific goals:
Knowledge of the properties of a database schema and of a decomposition. Ability to retrieve information in a database. Ability to evaluate the cost of data access operations. Knowledge of protocols for concurrency control.
To introduce students to formalised and scalable methodologies for the conceptual analysis and design of database applications, and to standard technologies for the development of relational databases.

Knowledge and understanding:
Fundamentals of relational database design and querying. Main data structures for storage of data on secondary memory. Main techniques for concurrency control.
Students will acquire fundamental methodological skills in the design of medium-large database applications (in particular for what concerns: a) requirements elicitation; b) conceptual analysis; c) design of the relational database and main use-cases), and their development (using relational DBMSs and the SQL language).


Applying knowledge and understanding:
To design relational schemes with “good properties”. To formulate queries in relational algebra. To evaluate costs of basic operations on a file with a given physical organization.
Students will be able to proficiently apply the acquired skills in the actual design of medium-large database applications.

Critical and judgmental skills:
To be able to assess the properties of a relational schema and of a decomposition. To be able to choose an appropriate storage structure for the information in a schema.
Students will be able to take autonomous and rational decisions during the various phases of the design process of an actual database application.

Communication skills:
To be able to communicate/share che qualitative/quantitative characteristics of the relational structure of a database.
Students will be able to interact proficiently with final customers (for what concerns requirements elicitation) and with other designers (for what concerns the design process of medium-large software systems).

Learning skills:
To be able to use the learned concepts in the following module of the course and in a possible advanced course on Databases.
Students will be able to extend their skills in the subjects of this course, by the autonomous reading of technical documentation concerning the design of database applications.

General objectives:
Be able to design/evaluate the properties, storage structure, and protocols of a database management system.

Specific objectives:
Knowledge of the properties of a relational schema and its decomposition. Ability to use relational algebra expressions to search for information in a relational database. Ability to evaluate the costs of data access operations.

Knowledge and understanding:
Theoretical foundations of relational database design and querying (relational algebra). Main data organization structures in secondary storage.

Apply knowledge and understanding:
Design relational schemas with "good properties." Query a database using relational algebra. Evaluate the costs of basic operations on files with different types of physical organization.

Critical and judgment skills:
Be able to evaluate the properties of a relational schema and its decomposition. Be able to choose the most appropriate data structure to store the information in a schema.

Communication skills:
Be able to communicate/share qualitative/quantitative characteristics related to the relational structure of a database.

The course is taught in the first semester of the second year. Knowledge of the basic elements of mathematics and logic, acquired through the courses taught during the first year, is required.
There are no prerequisite courses. However, knowledge of the topics covered in the courses: Mathematical Methods for Computer Science and Introduction to Algorithms is recommended.

Module: Module II
N/D
Module: Module I

Introduction to database management systems (2 hours)
History
Characteristics of database management systems
Model and system evolution

The relational model (30 hours)


Foundamentals: domain, attribute, relation, n-uple, schema
Query languages (relational algebra, relational complete languages)

Normalization theory

Functional dependencies
Key of a relation
Third normal form
Armstrong axioms and closure of a set of dependencies
Closure of a set of attributes
Minimal cover of a set of functional dependencies
Decompositions with a lossless join
Decompositions that preserve dependncies


Physical organization of data (14 hours)

Secondary storage
Physical and logical records
Pointers
Bloks
Heap file
Hash file
Indexed file (dense and sparse indexes).
B-tree

Concurrency control (14 hours)

Transactions
Serial schedule
Serializability
Transaction models and locking protocols
Livelock and deadlock.
Two-phase protocols
Conservative and aggressive protocols
"Dirty" data
Cascade rollback
Timestamp

Module: Module II
N/D
Module: Module I
1. R. A. Elmasri, S. B. Navathe, “Sistemi di basi di dati – Fondamenti”, Pearson – Addison Wesley, IV edizione, 2004.

2. J. D. Ullman, “Principles of database and knowledge-base systems”, vol. I, Computer Science Press, 1988.


Course slides and stuff


Examples of exam exercises

Module: Module II
N/D
Module: Module I
N/D

Face-to-face lectures.

Not mandatory but strongly encouraged.

The written part (about 2 and half hours) consists in a section of multiple choice questions about theori and a section with three exercises about: Relational Algebra, Relational Theory, Physical Organization.

The oral part consists into questions about: Definitions and basics about Relational Theory, Proofs of theorems in Relational Theory, Physical Organization

Write some queries expressed in natural language in relational algebra.

Calculate the keys of a relational schema. Determine whether the schema is in third normal form. If necessary, decompose the schema so that the subschemas satisfy the correctness and efficiency properties of a database (3NF, lossless join, etc.).

Analyze the computational usage and efficiency of a database in relation to the physical organization method used to organize the data.

Module: Module II
N/D
Module: Module I

• Introduction to databases and the relational model (5 hours)
  • Books: Slides 01-02


• Relational Algebra (8 hours)
  • Books: Slides 03-05


• Design of a relational database (3 hours)
  • Books: Slides 06


• Functional dependencies and closure of a set of functional dependencies (8 hours)
  • Books: Slides 07-08


• Third Normal Form (3NF) (8 hours)
  • Books: Slides 09-10


• Closure of an attribute set and schema keys (5 hours)
  • Books: Slides 11-12


• Schema decompositions that preserve dependencies and have a lossless join (7 hours)
  • Books: Slides 13-16


• Minimal cover of a set of functional dependencies and decomposition algorithm (7 hours)
  • Books: Slides 17-20


• Physical organization of data (5 hours)
  • Books: Slides 21-24


• Concurrency control (4 hours)
  • Books: Slides 25, 26, 29, 30