460-4069/01 – Query Processing Algorithms (AVD)

Gurantor departmentDepartment of Computer ScienceCredits4
Subject guarantordoc. Ing. Radim Bača, Ph.D.Subject version guarantordoc. Ing. Radim Bača, Ph.D.
Study levelundergraduate or graduateRequirementOptional
Year2Semesterwinter
Study languageCzech
Year of introduction2015/2016Year of cancellation2022/2023
Intended for the facultiesFEIIntended for study typesFollow-up Master
Instruction secured by
LoginNameTuitorTeacher giving lectures
BAC027 doc. Ing. Radim Bača, Ph.D.
Extent of instruction for forms of study
Form of studyWay of compl.Extent
Full-time Graded credit 2+2
Part-time Graded credit 0+3

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:

[1] H.Garcia-Molina, J.D.Ullman, J.D.Widom. Database Systems: The Complete Book, Prentice Hall, ISBN 0-13-031995-3, 2002.

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

Full-time form (validity from: 2015/2016 Winter semester, validity until: 2022/2023 Summer semester)
Task nameType of taskMax. number of points
(act. for subtasks)
Min. number of pointsMax. počet pokusů
Graded credit Graded credit 100 (100) 51 3
        SQL Select Written test 40  15
        Vytvoření jednoduchého XML procesoru Project 30  0
        Implementace vybraného úkolu Project 30  15
Mandatory attendence participation: Students have to pass every test/project in the subject.

Show history

Conditions for subject completion and attendance at the exercises within ISP: Completion of all mandatory tasks within individually agreed deadlines.

Show history

Occurrence in study plans

Academic yearProgrammeBranch/spec.Spec.ZaměřeníFormStudy language Tut. centreYearWSType of duty
2021/2022 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P Czech Ostrava 2 Optional study plan
2021/2022 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K Czech Ostrava 2 Optional study plan
2020/2021 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P Czech Ostrava 2 Optional study plan
2020/2021 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K Czech Ostrava 2 Optional study plan
2019/2020 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P Czech Ostrava 2 Optional study plan
2019/2020 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K Czech Ostrava 2 Optional study plan
2018/2019 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P Czech Ostrava 2 Optional study plan
2018/2019 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K Czech Ostrava 2 Optional study plan
2017/2018 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P Czech Ostrava 2 Optional study plan
2017/2018 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K Czech Ostrava 2 Optional study plan
2016/2017 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P Czech Ostrava 2 Optional study plan
2016/2017 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K Czech Ostrava 2 Optional study plan
2015/2016 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P Czech Ostrava 2 Optional study plan
2015/2016 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K Czech Ostrava 2 Optional study plan

Occurrence in special blocks

Block nameAcademic yearForm of studyStudy language YearWSType of blockBlock owner

Assessment of instruction



2021/2022 Winter
2020/2021 Winter
2017/2018 Winter
2016/2017 Winter
2015/2016 Winter