Engineering in Computer Science and Artificial Intelligence

DOMENICO LEMBO
ANTONELLA POGGI

General objectives:

The goal of the course is the investigation on the basic concepts of Data Management systems, emphasizing both the relational model and various NoSQL models. Several major
issues related to the theory and the design of relational data management systems are covered, including concurrency control, recovery, file and index organizations, query processing, OLAP and OLTP. A good knowledge of the fundamentals of Programming Structures, Programming Languages, and Databases (SQL, relational data model,
Entity-Relationship data model, conceptual and logical database design) is required.

Knowledge and understanding:
The student will have a good knowledge on how a Data Management System, even a NoSL one, works, how it is structured, and how it is designed. Also, the student will acquire knowledge of the architecture of a database management system and of its main modules (transaction manager, recovery manager, query evaluator). The student will also acquire a good understanding of how to design the physical organization of relations (files and indices), and how the query optimizer of a Data Management system works.

Applying knowledge and understanding:
The students will be able to design her/his own Data Management system, including the concurrence control module, the recovery module, the access file method, and the query optimizer.

Making judgements:
The student will be able to evaluate various kinds of Data Management systems, including NoSQL ones, and will be able to choose the right technique for concurrency, recovery, and query processing in specific application contexts.

Communication skills:
The students will acquire a good knowledge on how to illustrate the algorithms and the techniques at the basis of a modern Data Manager.

Learning skills:
The student will be able to understand any new architecture and approach to Data Management that will become popular in the future.

Excellent knowledge on Data Management systems. Skill on working with NoSQL systems and Data Warehouse Systems.

A good knowledge of the fundamentals of Programming Structures (algorithms and data structures), Programming Languages, Databases (SQL, relational data model, Entity-Relationship data model, conceptual and logical database design), Theoretical Computer Science (computational complexity, computability) is required.

1. Recap on databases and SQL
2. Data warehousing: architectures, multidimensional modeling, OLAP
3. Data Warehouse design methodologies; The DFM model; The logical models for DW: the star schema, the snowflake schema
4. NoSQL data models and systems: the case of graph databases; The Neo4j system
5. The notion of Knowledge Graph; RDFS Knowledge Graphs:syntax, semantics, inference
6. NoSQL data models and systems: the case of Document databases; The MongoDB system
7. The structure of a Data Management System (DBMS)
8. Buffer management: buffer pool, replacement strategies, operations on the buffer
9. Concurrency management: The concept of transaction; The notion of serializability; Concurrency management strategies; Concurrency control in SQL and PostgreSQL; Recovery: Crash management; Classification of failures; Recovery strategies
10. Physical structures for data management: Record and page organizations, Simple file organizations, Indexed file organizations
11. Query processing: evaluation of relational algebra operators

* Lecture notes distributed by the lecturers;
* R. Ramakrishnan, J. Gehrke. Database Management Systems. McGraw-Hill, 2004;
* M. Golfarelli, S. Rizzi. Data Warehouse Design: Modern Pronciples and Methodologies. McGraw-Hill, 2009,
* Additional optional material on concurrency control:
- http://research.microsoft.com/en-us/people/philbe/ccontrol.aspx
- Gerhard Weikum, Gottfried Vossen, "Transactional Information Systems: Theory,
Algorithms, and the Practice of Concurrency Control and Recovery", The Morgan Kaufmann
Series in Data Management Systems.

Gerhard Weikum, Gottfried Vossen, "Transactional Information Systems: Theory, Algorithms, and the Practice of Concurrency Control and Recovery", The Morgan Kaufmann Series in Data Management Systems.

Face-to-face lectures with exercises and hands-on sessions

Attendance is strongly recommended but not mandatory.

Each student may choose between two options:
OPTION 1:Take the written exam only. In this case, the written exam covers the entire syllabus, and the final grade ranges from **18 to 30 cum laude**.
OPTION 2:Take both the written exam and the project. In this case, the written exam is shorter than in **OPTION 1**. The maximum score for the written exam is **24**, and the minimum passing score is **15**. The maximum score for the project is **8**, and the minimum passing score is **4**. The final grade is the sum of the two scores. Any total score above **30** will be recorded as **30 cum laude**.

1) We refer to a setting with both shared and exclusive locks. A transaction T is called cautious if all its lock requests appear before every other action of T. A schedule is called cautious if it is legal and all its transactions are both well-formed and cautious. A lock-based, active scheduler with both shared and exclusive locks is called heedful if it
not accept schedules that are not cautious (where we adopt the usual definition of an active 2PL scheduler “accepting” a schedule). Prove or disprove the following sentences. “accepting” a schedule). Prove or disprove the following sentences.
1.1 Every cautious schedule is a 2PL schedule.
1.2 Every cautious schedule is conflict serializable.
1.3 Every heedful scheduler can avoid to deal with deadlock management.

2) Consider the following transactions: T1 : r1(A)w1(C); T2 : r2(B)w2(A); T3 : r3(C)w3(D);
T4 : w4(D) r4(B) and answer the following questions, providing a detailed justification for each answer.
2.1 How many non-serializable schedules do exist on T1, T2, T3, T4?
2.2 Prove or disprove that all serializable schedules on T1, T2, T3, T4 are accepted by the 2PL scheduler with both shared and exclusive locks.

3) Given the table R(A,B,C) with 1000 tuples stored in a heap with 100 pages and given 80
frames in the buffer, we want to answer the query:
SELECT A, COUNT(*)
FROM R
GROUP BY A
HAVING COUNT(*) > 10
3.1 Illustrate in detail a multi-pass algorithm to solve the problem, and tell which is its cost.
3.2 Tell whether the block-nested loop technique is suitable for answering the query.
3.2.1 If the answer is positive, then illustrate the algorithm and tell which is its cost.
3.2.2 If the answer is negative, consider the following question: can we build and use an index during the application of the block-nested loop algorithm in such a way that the modified block-nested loop algorithm is able to produce the result of the query? If the answer to the question is negative, then motivate the answer in detail; if the answer is positive, provide a detailed description of the new algorithm and tell which is its cost.

4) We refer to a setting where the data manager has 3 buffer frames available, we have a table R(A,B,C,D) with 4.000 tuples stored in a heap with 200 pages and we want to compute the relation obtained from R by eliminating duplicates.
4.1 Illustrate in detail a multipass algorithm for solving the problem in the above mentioned setting and tell which is its cost.
4.2 Making use of a hash-based index, design an index-based algorithm for solving the problem in the above mentioned setting, provide a detailed description of such algorithm and tell which is its cost.
4.3 Making use of a B*-tree-based index, design an index-based algorithm for solving the problem in the above mentioned setting, provide a detailed description of such algorithm and tell which is its cost.

5) (only for students who do not do the project)
Consider the relations Drone(num,model,date) with 1.000 pages and 30.000 tuples, and
Mission(code,num,model,date) with 4.000 pages and an associated index on Mission with search key ⟨model,date⟩, for which we know that the cost of retrieving the records with a specific value of attribute model is 6 page accesses. Assume a buffer with 100 frames, and consider the two queries shown below.
Query Q1:
select num, model from Drone
except all – – not removing duplicates
select num, model from Mission
Query Q2:
select model, date from Drone
except all – – not removing duplicates
select model, date from Mission
where “except all” denotes bag difference. For both queries Q1 and Q2, tell (i) whether it is possible to process the query by using a block-nested loop algorithm, and (ii) whether it is possible to process the query by an index-based algorithm using the above-mentioned index on Mission. In all four cases, if the answer is positive, then describe the algorithm and tell which is its cost. If the answer is negative, then motivate the answer in detail.

6) (only for students who do not do the project)
Let B be a relational database with relations Agency(id,nation), Travel(tcode,agencyid,duration), Visit(tcode,citycode), Participate(tcode,person), Likes(person,citycdode), where (i) each travel agency is located in a nation, (ii) each travel is offered by an agency, has a duration, includes a set of at most 10 cities to visit (relation Visit) and accepts at most 50 participants (relation Participate); (iii)
each person likes a set of at most 20 cities (relation Likes).
6.1 Describe how would you organize a property graph database G in order to represent the relational database B. In particular, (i) specify how nodes, edges, labels, etc. of G are used in order to capture the information stored in the tables of B and (ii) choose a few tuples for the relations in B, and show the specific property graph database G obtained by applying the chosen representation method.
6.2 Consider the query Q on the property graph database that, given the tcode of a specific travel T, returns each person who participates to T and likes at least one city visited by T. Choose one of the following questions and answer it. (i) Assuming the graph database organized as decided for point (6.1), formulate the query on such graph database using a Cypher-like syntax. (ii) Assuming that every page of our system contains 1.000 values and there are 10 free buffer frames, illustrate a possible algorithm that the graph database system can use to answer the query and tell which is its cost in terms of number of page accesses.

• Recap on databases and SQL
  • Books: Lecture notes distributed by the lecturers


• Data warehousing: architectures, multidimensional modeling, OLAP
  • Books: M. Golfarelli, S. Rizzi. Data Warehouse Design: Modern Pronciples and Methodologies. McGraw-Hill, 2009


• Data Warehouse design methodologies; The DFM model; The logical models for DW: the star schema, the snowflake schema
  • Books: M. Golfarelli, S. Rizzi. Data Warehouse Design: Modern Pronciples and Methodologies. McGraw-Hill, 2009


• NoSQL data models and systems: the case of graph databases; The Neo4j system
  • Books: Lecture notes distributed by the lecturers


• The notion of Knowledge Graph; RDFS Knowledge Graphs:syntax, semantics, inference
  • Books: Lecture notes distributed by the lecturers


• The structure of a Data Management System (DBMS). Buffer management: buffer pool, replacement strategies, operations on the buffer
  • Books: R. Ramakrishnan, J. Gehrke. Database Management Systems. McGraw-Hill, 2004


• Concurrency management: The concept of transaction; The notion of serializability; Concurrency management strategies; Concurrency control in SQL and PostgreSQL; Recovery: Crash management; Classification of failures; Recovery strategies
  • Books: R. Ramakrishnan, J. Gehrke. Database Management Systems. McGraw-Hill, 2004


• Physical structures for data management: Record and page organizations, Simple file organizations, Indexed file organizations
  • Books: R. Ramakrishnan, J. Gehrke. Database Management Systems. McGraw-Hill, 2004


• Query processing: evaluation of relational algebra operators
  • Books: R. Ramakrishnan, J. Gehrke. Database Management Systems. McGraw-Hill, 2004