Database and algorithms
Database and algorithms
Academic year 2017/2018
- Course ID
- Teaching staff
- Prof. Rosa Meo
Dott. 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.
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. The course will introduce the students to the basic notions of NoSQL databases, important for the new generation of databases and the management of big data. In the laboratory the students will be able to work with a practical database management system.
In this course students will learn several fundamental principles of algorithm design and how to implement some fundamental data structures (e.g., graphs, arrays, trees, hash tables). This course aims at providing a solid methodological background for the analysis of algorithms in terms of their correctness, complexity (in time and in space), and tractability.
Results of learning outcomes
After the course students will be able to design data for relational databases, formulate a query in SQL or relational algebra, interact with a real database management system and will have the basic notions of NoSQL databases.
After the course students will be able to approach a problem through the design, analysis and implementation of appropriate algorithms and data structures.
This course consists in two parts: the former is on Databases and the latter is on Algorithms.
The course will consist of 32 hours of frontal lessons and 16 hours of practical assignments at the computer or at assigned exercises. Personal training on the assigned exercises on both the theory and practice modules is fundamental to successfully pass the final exam.
The course will consist of 32 hours of frontal lessons and 16 hours of practical assignments at the computer. 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 some data design problems, write in SQL a data retrieval request, present and discuss the practical assignments implemented during the course.
During the following, oral exam (planned some days after the written part) the student will be asked to discuss the presented solution in the written part.
Students are required to pass the written test before to be admitted the oral part.
The final exams consists in 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.
At 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 laboratory will consists in assignments that will be solved by means of practical activities at the computer that will support the theorical notions learnt during the course.
Databases; database management systems; data models; database languages; the relational model and its languages; integrity constraints; relational algebra; SQL;
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
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
Paolo Atzeni, Stefano Ceri, Stefano Paraboschi and Riccardo Torlone
Introduction to Algorithms. T Cormen, C Leiserson, R Rivest, C Stein