460-4069/03 – 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 | Choice-compulsory type A |
| Year | 2 | Semester | winter |
| | Study language | Czech |
| Year of introduction | 2022/2023 | Year of cancellation | |
| 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
The student will solve tasks during the exercise, which will test the basic implementation of selected query execution methods. There will be one test concerning the execution of queries in relational databases. Moreover, students will create a home project on a selected topic.
E-learning
Other requirements
Students have to have knowledge taught in the subject Database Systems II.
Prerequisities
Subject has no prerequisities.
Co-requisities
Subject has no co-requisities.
Subject syllabus:
Lectures:
1. Relational data processing principles - query plan, plan rewritings, and optimization techniques
2. Cost-based optimization - statistics, cost-model
3. Index selection based on cost optimization
4. Query parameterization and MEMO structure
5. Environment - main-memory/persistent environment, L2 cache, SIMD operation, parallelization
6. Graph databases - shortest distance, centrality index computation
7. Spatial queries - range query and k nearest neighbors query in low dimensions
8. Spatial queries - k nearest neighbors in high dimension, approximate nearest neighbors (ANN)
9. Set merging - full-text, similarity search
10. Semi-structured data - twig query pattern
11. Filters
Exercises will be held in a PC lab.
Exercises:
1. Query plans in relational databases - display and operator meaning
2. Influence of statistics on a query plan
3. Change of query plans with respect to physical structure change
4. Test of knowledge related to query plans
5. Basic types of queries in graph databases
6. Graph query processing
7. ANN
8. Inverted list merging
9. StackTree algorithm on a tree data
10. Filter
11. Presentation of a project
Conditions for subject completion
Occurrence in study plans
Occurrence in special blocks
Assessment of instruction