| Course Unit Code | 460-4069/01 |
|---|
| Number of ECTS Credits Allocated | 4 ECTS credits |
|---|
| Type of Course Unit * | Optional |
|---|
| Level of Course Unit * | Second Cycle |
|---|
| Year of Study * | Second Year |
|---|
| Semester when the Course Unit is delivered | Winter Semester |
|---|
| Mode of Delivery | Face-to-face |
|---|
| Language of Instruction | Czech |
|---|
| Prerequisites and Co-Requisites | Course succeeds to compulsory courses of previous semester |
|---|
| Name of Lecturer(s) | Personal ID | Name |
|---|
| BAC027 | doc. Ing. Radim Bača, Ph.D. |
| 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. |
| Learning Outcomes of the Course Unit |
|---|
| 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. |
| Course Contents |
|---|
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 |
| Recommended or Required Reading |
|---|
| Required Reading: |
|---|
[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 |
[1] M.Krátký, R.Bača. Databázové systémy, https://dbedu.cs.vsb.cz/
[2] G.Fritchey. SQL Server Execution Plans. Simple Talk Publishing, 2012, ISBN: 978-1-906434-92-2
[3] B. Nevarez. Inside the SQL Server Query Optimizer. Simple Talk Publishing, 2010, ISBN: 978-1-906434-57-1 |
| Recommended Reading: |
|---|
| [1] H.Garcia-Molina, J.D.Ullman, J.D.Widom. Database Systems: The Complete Book, Prentice Hall, ISBN 0-13-031995-3, 2002. |
[1] J.Pokorný, M.Valenta. Databázové systémy, ČVUT, ISBN 978-80-01-05212-9, 2013.
[2] H.Garcia-Molina, J.D.Ullman, J.D.Widom. Database Systems: The Complete Book, Prentice Hall, ISBN 0-13-031995-3, 2002. |
| Planned learning activities and teaching methods |
|---|
| Lectures, Tutorials |
| Assesment methods and criteria |
|---|
| Task Title | Task Type | Maximum Number of Points
(Act. for Subtasks) | Minimum Number of Points for Task Passing |
|---|
| Graded credit | Graded credit | 100 (100) | 51 |
| SQL Select | Written test | 40 | 15 |
| Vytvoření jednoduchého XML procesoru | Project | 30 | 0 |
| Implementace vybraného úkolu | Project | 30 | 15 |