460-4069/01 – Query Processing Algorithms (AVD)
Gurantor department | Department of Computer Science | Credits | 4 |
Subject guarantor | doc. Ing. Radim Bača, Ph.D. | Subject version guarantor | doc. Ing. Radim Bača, Ph.D. |
Study level | undergraduate or graduate | Requirement | Optional |
Year | 2 | Semester | winter |
| | Study language | Czech |
Year of introduction | 2015/2016 | Year of cancellation | 2022/2023 |
Intended for the faculties | FEI | Intended for study types | Follow-up Master |
Subject aims expressed by acquired skills and competences
The subject focuses on query processing algorithms that are commonly used in databases. We describe different data models and query processing problems. Several different techniques are described for each problem.
Teaching methods
Lectures
Tutorials
Summary
Students learn how are queries processed in a relational databases and also in other types of databases. These algorithms are usually hidden but their features has a significant influence to on a query processing and optimization.
Compulsory literature:
[1] G.Fritchey. SQL Server Execution Plans. Simple Talk Publishing, 2012, ISBN: 978-1-906434-92-2
[2] B. Nevarez. Inside the SQL Server Query Optimizer. Simple Talk Publishing, 2010, ISBN: 978-1-906434-57-1
Recommended literature:
Way of continuous check of knowledge in the course of semester
Student se bude podílet na řešení dílčích úkolů na cvičení v rámci, kterých si vyzkouší základní implementaci vybraných metod vykonávání dotazů. V průběhu semestru proběhnou dvě písmenky: (1) vykonávání dotazů v relačních databázích, (2) vykonávání dotazů v dalších typech databází.
E-learning
Other requirements
Student have to have a knowledge teached in a subject database and information systems 2.
Prerequisities
Subject has no prerequisities.
Co-requisities
Subject has no co-requisities.
Subject syllabus:
Lectures:
1. Relational data processing principles - query plan, plan rewritings
2. Basic algorithms in relational databases - joins (algorithms, data structures)
3. Cost-based optimization - histograms, cost-model
4. Summary - complex examples
5. Spatial queries - range query, top-k nearest neighbor
6. Spatial queries - approximate nearest neighbor (ANN)
7. XML databases - path and twig queries
8. Set operations - inverted list, intersection
9. Graph databases - graph traversal, shortest distance
10. Graph database - practical work
11. Environment - main-memory/persistent environment, ACID support, parallelization, L2 caches
12. Approximation, Bloom filters
Exercises will be held in a PC lab. Exercises:
1. Query plans in relational databases - display and operator meaning
2. Change of query plans with respect to physical structure change
3. Influence of statistics on a query plan
4. Test of knowledge related to query plans
5. PostGIS
6. ANN libraries
7. XML query processing algorithms
8. SIMD merging algorithm
9. Basic graph algorithms
10. SQL queries on graphs
11. Bloom filters combined with the previous problems
Conditions for subject completion
Occurrence in study plans
Occurrence in special blocks
Assessment of instruction