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 cancellation
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
Combined Graded credit 0+3

Subject aims expressed by acquired skills and competences

Subject focuses on a query processing algorithms that are commonly used in databases. Subject deals also with data structurtes since they are inherent part of these algorithms.

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:

G.Fritchey. SQL Server Execution Plans. Simple Talk Publishing, 2012, ISBN: 978-1-906434-92-2

Recommended literature:

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

Další požadavky na studenta

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

Combined form (validity from: 2015/2016 Winter semester)
Task nameType of taskMax. number of points
(act. for subtasks)
Min. number of points
Graded credit Graded credit 100  51
Mandatory attendence parzicipation:

Show history

Occurrence in study plans

Academic yearProgrammeField of studySpec.FormStudy language Tut. centreYearWSType of duty
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