*This course is not currently conducted!*

*Erasmus code:*11.3

*ISCED code:*0612

*ECTS credits:*unknown

*Language:*Polish

*Organized by:*Faculty of Mathematics, Informatics, and Mechanics

*Related to study programmes:*

# 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: