460-4069/02 – 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 languageEnglish
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 - data structures 7. XML databases - path and twig queries 8. XML databases - twig query holistic joins 9. Graph databases - shortest distance, centrality index computation 10. Environment - paralelization, L2 caches 11. Environment - main-memory/persistent environment, ACID support 12. Approximation, Bloom filters Excercises will be held in a PC lab. Excercises: 1. Query plans in relational databases - display and operator meaning 2. Change of query plans with respect to physical structure change 3. Influence of a statistics on a query plan 4. Test of a knowledge related to query plans 5. Range query processing 6. Indexes and algoithms for XML databases 7. Graph databases 8. Optimalization of queries with repsect to an enviroment 9. Integration of Bloom filters 10. Test

Conditions for subject completion

Part-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  51 3
Mandatory attendence participation: The tasks are completed according to the specification of the lecturer.

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 English Ostrava 2 Optional study plan
2020/2021 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P English Ostrava 2 Optional study plan
2019/2020 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P English Ostrava 2 Optional study plan
2019/2020 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K English Ostrava 2 Optional study plan
2018/2019 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P English Ostrava 2 Optional study plan
2018/2019 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K English Ostrava 2 Optional study plan
2017/2018 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P English Ostrava 2 Optional study plan
2017/2018 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K English Ostrava 2 Optional study plan
2016/2017 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P English Ostrava 2 Optional study plan
2016/2017 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K English Ostrava 2 Optional study plan
2015/2016 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P English Ostrava 2 Optional study plan
2015/2016 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K English Ostrava 2 Optional study plan

Occurrence in special blocks

Block nameAcademic yearForm of studyStudy language YearWSType of blockBlock owner

Assessment of instruction

Předmět neobsahuje žádné hodnocení.