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 based on home assignments (10 problems, 2 points each), mid-term exam (3 problems, 20 points each), oral exam (up to 3 questions, 20 points each). The number of questions during the oral exam depends on the points collected so far: [0;40] points - 3 questions, (40;60] points - 2 questions, (60;80] points 1 question. Thresholds for the grades are: 50 for 3, 60 for 3.5, 70 for 4, 80 for 4.5, 90 for 5, 100 for 5.5.
The second-try grade is based exclusively on the second-try oral exam, which will include problems and theory questions. Everybody can sit this exam. The new grade is taken into account only if it is better than the first-try grade.
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: