Database and algorithms
Database and algorithms
Academic year 2020/2021
- Course ID
- Teaching staff
- Prof.ssa Rosa Meo
Prof. Rossano Schifanella
- 1st year
- Teaching period
- Second semester
- D.M. 270 TAF C - Related or integrative
- Course disciplinary sector (SSD)
- INF/01 - informatica
- Formal authority
- Type of examination
- Knowledge on programming.
- Propedeutic for
- Complex networks, Introduction to Data Mining
Sommario del corso
The objectives are formalized for each of the two parts of the course.
As regards the “Knowledge and understanding” goal, this course will teach:
- the fundamentals of relational theory,
- SQL language and its relationships with relational algebra,
- design of data in relational databases by means of the conceptual and logical design of databases.
- basic notions of NoSQL databases, important for the new generation of databases and the management of big data.
During the laboratory, students will be able to learn to interact with a real database management system in some practical work sessions in which they apply the learnt concepts and solve the proposed exercises. This learning by practice allows students to make choices, find strategies to solve problems, recognize their own mistakes by following the logical reasoning after the interactions with the system.
After their interaction with a real database management system (Mysql Workbench) students will learn new skills of assisted design of a database, design of new SQL queries for solving given requests, understanding about a given database schema and database content. Finally, students will learn to analyse a set of requirements about a real case problem and learn to be creative in the design of a new database, suitable to solve a given set of requirements.
In the laboratory, the students will learn to work with a practical database management system (Mysql Workbench).
The course aims at providing the theoretical and practical tools to solve a computational problem through the design, analysis and implementation of appropriate algorithms and data structures.
Results of learning outcomes
As regards “Applying knowledge and understanding” goal, during the course the teacher will offer exercizes on query languages and database design that will allow students to apply the learnt methodology to practical cases and understanding the fundamental concepts learnt in theory.
As regards the ability of “Making judgements”, during the sessions dedicated to the solution to exercizes on database design, students learn to follow a well structured design strategy and learn to make judgements about their suitability in different contexts. Similar ability will be acquired about making judgements about the correctness and completeness of the results of their own design methodology.
By solving these exercizes and applying the normalisation theory to the obtained database schema, the students will learn to judge if the result of the database design methodology is well structured. Finally, students will judge about the relevance of a set of requirements that the business client could propose as input on a business application running on a database.
As regards the query languages, the exercizes and examples provided during the course are proposed in an order of increasing complexity and on a given database instance so that students will be able to test them on a real system and reason about their correctness.
As regards the “Learning skills”, they consist in the ability to follow the well-structured methodology of design of a database, and the ability to write queries in SQL that correspond to a request formulated in natural language. Finally students learn to interact, use and manage the different tools offered by a real database management system.
As regards the “Communication skills”, students will be able to learn them during the interactions with other students working in a team for the solution of exercises (both in the laboratory sessions and in the database design classes). Students will be able to ask questions and explain and propose their own solutions. Finally, students will learn to communicate and exchange information on the content of a database, by producing and interpreting the documentation of a data model by the relational data modeling and design languages.
Knowledge and understanding
Students will learn the fundamentals of algorithm design, analysis, and implementation using Python to explore some of the fundamental data structures (e.g., graphs, arrays, trees, hash tables).
Applying knowledge and understanding
The course will provide a framework to experiment with the main concepts through homework and programming assignments that cover the main topics of the course. The students will have also the possibility to apply their knowledge to the solution of a real problem during the preparation of a final project.
This course aims at providing a solid methodological background for the analysis of algorithms in terms of their correctness, complexity (in time and space), and tractability. These are solid conceptual tools that will guide them during the choices of the correct algorithmic solutions for solving problems in real professional life.
Students will be able to use appropriate, formal language in all the steps that involve the design, analysis, and implementation of an algorithmic solution. They will improve both their written and oral skills via the interactions and collaborations with the other students and the teacher during the practical sessions. The final exam will strengthen the students' ability to communicate the results of their analysis and the implementation of the corresponding algorithms and to summarize and discuss the pros and cons of a solution in an oral presentation.
This course consists of two parts: the former is on Databases and the latter is on Algorithms.
Due to the Covid-19 emergency the course will be delivered in the form of video lectures alternated with interactive meetings on a digital platform. Practical assignments and questionnaires of self-evaluation will complement the theoretical part with exercises. During the interactive meetings, question answering and discussion on exercizes solutions will occur. Personal training on the assigned exercises on both the theory and practice modules is fundamental to successfully pass the final exam.
Due to the Covid-19 emergency the course will be delivered in the form of video lectures alternated with interactive classes on a digital platform. Practical assignments and homework will complement the theoretical part with exercises. Personal training on the assigned exercises on both the theory and practice modules is fundamental to successfully pass the final exam.
Learning assessment methods
The final exam will consist of a written test and a following oral discussion. In the written test the candidate will be asked to solve a data design problem, write in SQL a data retrieval request. Due to COVID-19 emergency, the exams will be done in smart-working, on Web-ex with the camera of their PC showing their face.
During the following, oral exam (which is planned some days after the written part) the student will be asked to discuss the presented solution in the written part.
Optionally, the students might accept to answer additional questions on the theoretical part of the course not included in the written test (on normalisation theory, transactions and concurrency control). This oral (optional) part will account for 2 scores on the Database score.
Students are required to pass the written test before they are admitted to the oral part.
The final exam consists of an oral discussion of a project in which the students are asked to select a problem of interest, define a set of algorithmic solutions, compare them in terms of complexity and test their implementation within the framework of a real use case. Propaedeutic to the oral discussion is the submission of an essay that describes in details the projects main building blocks. The oral exam will also have a part with questions to attest the knowledge of the theoretical concepts presented during the course.
During the Covid-19 emergency the oral exam will take place using the Webex video conference system. The rest of the modality will remain unchanged.
The online modality via Webex for the Algorithms oral discussion is confirmed also for the September 2020 exams session.
In the end, both the tests on the two parts of the course (Databases and Algorithms) must be satisfactory to allow the student to overcome the overall examination.
The two parts can be overcome in different exam sessions, but in the same academic year.
As regards the overall score, the two parts weigh equally in the final score, computed as the average of the scores of the two parts (Database and Algorithms): for the final score the average is rounded to the nearest integer.
The laboratory will consist of assignments that will be solved by means of practical activities at the computer that will support the theoretical notions learnt during the course.
In addition, the practical laboratory sessions will support the students to learn the usage and the working of a real database management system (Mysql) and the assisted design of a database schema (Mysql Workbench).
- Introduction to databases;
- database management systems;
- data models;
- database languages;
- the relational model;
- integrity constraints;
- relational algebra;
- Database design methodologies and models;
- the database design process;
- the Entity-Relationship model;
- conceptual design;
- requirement collection and analysis;
- general data modelling criteria;
- design strategies;
- qualities of a conceptual schema;
- a general methodology for database design;
- CASE tools for database design;
- logical design;
- translation towards the relational model;
- Normalization theory for database design;
- redundancies and anomalies;
- functional dependencies;
- Boyce- Codd normal form;
- qualities of decompositions;
- third normal form;
- normalization and the design process
- hints on indexes
- an overview of concurrency control
- basic notions of NoSQL databases (if time allows)
- Use of a real DBMS for database design and creation and queries with SQL (Mysql Workbench)
- Problems and algorithms: solvability, correctness, complexity.
- Termination and non-termination.
- Unsolvable problems: undecidability of the halting problem.
- Correctness of algorithms.
- Mathematical induction principles: simple induction, complete induction, structural induction.
- Analysis of algorithms.
- Complexity (in time and in space) of algorithms.
- Complexity of problems.
- Tractable vs. intractable problems and algorithms.
- Data structures,
- Abstract Data Types (ADT),
- structure invariants.
- Sequences, arrays, linked lists, stacks, queues, trees, dictionaries, hash tables.
- Graph representation and primitives.
- Sorting and selection.
Suggested readings and bibliography
Database Systems - Concepts, Languages and Architectures
Author: Paolo Atzeni, Stefano Ceri, Stefano Paraboschi and Riccardo Torlone
Url: http:// http://dbbook.dia.uniroma3.it
Introduction to Algorithms
Author: T Cormen, C Leiserson, R Rivest, C SteinEdition: Third Edition
Publisher: MIT Press