Query Processing Algorithms 1000-2M25APZ
1. Relational algebra basics: complexity and expressive power.
2. Query evaluation paradigms: testing, computing, counting, aggregating,
enumerating, and sampling of answers.
3. Cost models and classical optimization methods used in database engines.
4. Yannakakis’s algorithm for acyclic queries
5. Algorithms based on query decomposition (treewidth, etc.)
6. Worst-case optimal joins: AGM bound, leapfrog trie-join algorithm
7. Fagin’s Algorithm (FA) and Threshold Algorithm (TA)
8. MPC and HyperCube
9. Evaluating recursive queries: recursion in SQL, evaluating Datalog (naive,
seminaive, top-down, magic set)
10. Static analysis: satisfiability, equivalence, containment, undecidability for the
relational algebra, conjunctive query minimization (*)
11. Other architectures: column stores, factorized databases (*)
12. Other data models: graph and semi-structured databases (*)
Type of course
Requirements
Prerequisites
Course coordinators
Assessment criteria
The final grade is determined by the total number of points earned for home
assignments, mid-term exam, and exam.
Bibliography
S. Abiteboul, R. Hull, V. Vianu, Foundations of Databases (available online).
M. Arenas, P. Barcelo, L. Libkin, W. Martens, A. Pieris, Database Theory: Querying
Data (early version available online).
Selected research papers.
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:
- Bachelor's degree, first cycle programme, Computer Science
- Master's degree, second cycle programme, Computer Science
Additional information (registration calendar, class conductors, localization and schedules of classes), might be available in the USOSweb system: