Databases 1000-213bBAD
What is a database?
1. data modelling: tables, trees, graphs
2. query languages: query formulation, expressive power, evaluation
3. meta-data: constraints and dependencies
4. usage and maintenance of views
5. transactions
Relational query languages
1. first-order logic (FO)
2. relational algebra (RA)
3. SQL
4. equivalence of languages
SQL peculiarities: aggregation and NULLs
1. multi-set semantics, aggregation
2. different roles of NULL
3. semantics of NULL in SQL
4. closed-world semantics (*)
5. various joins
Recursion (*)
1. things inexpressible in FO: reachability
2. Datalog
3. RA with iteration (while, inflationary while)
4. a comparison with complexity classes and extensions of FO
5. the limited recursion of SQL
Conceptual data model
1. domain modelling as an analysis of the real world
2. object-oriented domain modelling
3. selected aspects of UML
Logical data model
1. from a domain model to a database design
2. from objects to relations (representing inheritance hierarchies)
3. the role of meta-data (constraints)
4. functional dependencies, keys (PRIMARY KEY, UNIQUE)
5. inclusion dependencies (REFERENCES)
6. other constraints (CONSTRAINT)
7.a note on anomalies, redundancies and Boyce-Codd normal form (BCNF)
Normalization (*)
1. anomalies; what is a redundancy?
2. functional dependencies
3. decomposition by the projection of dependencies
4. BCNF and a decomposition algorithm
5. preservation of information (lossless join)
6. losing functional dependencies during the 3NF decomposition
7. 3NF decomposition
Views and triggers
1. views
2. authorization (grant, revoke)
3. triggers and updates of views
4. materialized views and their maintenance (*)
5. maintenance of the transitive closed without recursion (*)
XML (*)
1. how to model hierarchical data?
2. trees and XML documents
3. schema definition languages: DTD, XML Schema, RelaxNG.
4. query languages: FO vs. XPath, XQuery
Graph databases (*)
1. graphs and query languages with recursion: RPQ
2. RDF and SPARQL
3. LPG and Cypher
Query evaluation
1. algorithm for RA operations (in RAM model)
a. union, projection, selection by the full-scan (linear)
b. join, difference, duplicate elimination and grouping by sorting (linearithmic + the size of the result) or hashing
2. query plan optimization by minimizing intermediate relations: simple heuristics (rewriting, SIP)
3. homomorphism theorem and minimalization of conjunctive queries (*)
4. evaluating XPath queries without comparisons (*)
5. AGM bound and worst-case optimal algorithms for joins (*)
Algorithms in I/O model (*)
1. I/O model: external memory, pages and frames
2. three basic “operations”: scanning, sorting and searching
3. scanning: blocking retrievals
4. sorting in external memory
5. implementation of dictionaries (indices): B+tree, hash tables
Transactions
1. a realistic model: a number of clients, system failures
2. ACID
3. isolation levels
4. implementation of serializability: “conflict-serializable” i 2PL (*)
5. deadlock detection (*)
Distributed databases (*)
1. distributed data models
2. 2PC
(*) – optional topics to be selected by the lecturer
Type of course
Mode
Requirements
Learning outcomes
Knowledge
1. Understands syntax and semantics of first-order queries (K_W01, K_W02).
2. Knows most important properties of the relational algebra (K_W01, K_W02).
3. Knows the theory of functional dependencies and normal forms (K_W01, K_W02).
4. Knows basic properties of the query language SQL (K_W01, K_W02).
5. Knows rules of database design (K_W01, K_W02).
6. Understands the role of transactions in databases (K_W01, K_W02).
Skills
1. Is able to formulate SQL queries (K_U09).
2. Is able to write stored procedures and triggers in at least one database programming language (K_U09).
3. Is able to recognize anomalies in a database design and to transform it into an appropriate normal form
(K_U10).
4. Is able to design and implements a relational database (K_U10).
5. Has basic skills in relational database tuning (K_U10).
Competences
1. Knows the limitations of his/her knowledge and understands the need of further learning, in particular the need to acquire interdisciplinary knowledge (K_K01).
2. Is able to pose precise questions that facilitate extending his/he understanding the given topic or finding missing items in a reasoning (K_K02).
Assessment criteria
Credits:
- microassignments: 10 small assignments, 1 point each = 10 points
- lab project: 0-20 points;
- SQL test (during labs, 90 mins): 5 problem, 4 points each = 20 points;
- modelling test (during lectures, 90 mins): 2 problems, 10 points each = 20 points;
- final written exam (120 mins): 3 problems, 10 points each = 30 points.
The total number of points earned (0-100) translates into the final grade, according to the following thresholds: 50 points for 3, 60 points for 3+, 70 points for 4, 80 points for 4+, 90 for 5.
There is a possibility to replace the final written exam with an oral exam taken before the exam period. This possibility is available only upon obtaining at least 65 points for the microassignments, the lab project and the two tests (in total).
Each of the four ingredients of the final score can be re-taken during the second-try exam period (the second-try grade will be based on the best of the two results). The numbers of points available and the thresholds for each grade will be as for the first try. Re-taking one of the tests or the final written exam is done by returning solutions of problems from the corresponding segment of the second-try exam (taken online, 180 mins). Re-submissions of microassignments and lab projects are regulated directly by lab instructors.
Bibliography
J. Ulmann, J. Widom, A first course in database systems. Third edition. Prentice Hall, 2007.
2. S. Abiteboul, R. Hull, V. Vianu, Foundations of databases , Addison - Wesley 1995
Additional information
Information on level of this course, year of study and semester when the course unit is delivered, types and amount of class hours - can be found in course structure diagrams of apropriate study programmes. This course is related to the following study programmes:
Additional information (registration calendar, class conductors, localization and schedules of classes), might be available in the USOSweb system: