460-4069/01 – Algoritmy vykonávání dotazů (AVD)

Garantující katedraKatedra informatikyKredity4
Garant předmětudoc. Ing. Radim Bača, Ph.D.Garant verze předmětudoc. Ing. Radim Bača, Ph.D.
Úroveň studiapregraduální nebo graduálníPovinnostvolitelný odborný
Ročník2Semestrzimní
Jazyk výukyčeština
Rok zavedení2015/2016Rok zrušení2022/2023
Určeno pro fakultyFEIUrčeno pro typy studianavazující magisterské
Výuku zajišťuje
Os. čís.JménoCvičícíPřednášející
BAC027 doc. Ing. Radim Bača, Ph.D.
Rozsah výuky pro formy studia
Forma studiaZp.zak.Rozsah
prezenční Klasifikovaný zápočet 2+2
kombinovaná Klasifikovaný zápočet 0+3

Cíle předmětu vyjádřené dosaženými dovednostmi a kompetencemi

Předmět se bude zaměřovat zejména na algoritmy, které se používají pro řešení určitých typů dotazů v databázích. Jedná se jak o běžné OLTP databáze, tak o specializované databáze jako prostorové, grafové nebo XML databáze. Předmět se bude okrajově věnovat i fyzické reprezentaci dat, jelikož se jedná nedílnou součástí těchto algoritmů.

Vyučovací metody

Přednášky
Cvičení (v učebně)

Anotace

Studenti se v předmětu podrobněji seznámí se způsobem vykonávání dotazů v relačních databázích a i v dalších typech databází. Tyto algoritmy často zůstávají uživatelům skryté, ale jejich vlastnosti mají na vykonávání a optimalizaci dotazů zásadní vliv.

Povinná literatura:

[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

Doporučená literatura:

[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.

Forma způsobu ověření studijních výsledků a další požadavky na studenta

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 má mít zvládnuty znalosti, které se učí v předmětu Databázové a informační systémy 2.

Prerekvizity

Předmět nemá žádné prerekvizity.

Korekvizity

Předmět nemá žádné korekvizity.

Osnova předmětu

Obsah přednášek: 1. Principy vykonávání dotazů v relačních databázích - plány dotazů a přepisy plánů 2. Základní algoritmy v relačních databázích - spojení relací (algoritmy a datové struktury), třídění a vlastnosti těchto algoritmů v relačních databázích 3. Cenová optimalizace - histogramy, cenový model 4. Shrnutí kroků při vykonávání dotazů - komplexní příklady 5. Prostorové dotazy - rozsahové dotazy, top-k nejbližších sousedů 6. Prostorové dotazy - příbližné vyhledání nejbližších sousedů (ANN) 7. XML databáze - větvené dotazy a dotazy cest 8. Množinové operace - Techniky, invertovaný seznam a slévání 9. Grafové databáze - nejkratší vzdálenost, vyhledávání v grafu 10. Grafové databáze - praktická práce 11. Jak ovlivňuje algoritmy prostředí ve které je vykonáváme - L2 cache, paralelizace, perzistentní úložiště, podpora ACID, SIMD 12. Aproximace a Bloom filtry Cvičení budou probíhat na počítačové učebně. Obsah cvičení: 1. Zobrazování a správné čtení plánů dotazů u relační databáze 2. Změna plánů při změně fyzické struktury databáze 3. Vliv statistik na plány dotazů 4. Procvičení komplexnějších příkladů 5. PostGIS 6. ANN knihovny 7. Indexy a algoritmy pro XML databáze 8. SIMD v základní operaci slévání 9. Základní typy dotazů v grafech 10. SQL dotazy nad grafem 11. Zapojení bloom filtrů do úkolů řešených v předchozích cvičeních

Podmínky absolvování předmětu

Kombinovaná forma (platnost od: 2015/2016 zimní semestr, platnost do: 2022/2023 letní semestr)
Název úlohyTyp úlohyMax. počet bodů
(akt. za podúlohy)
Min. počet bodůMax. počet pokusů
Klasifikovaný zápočet Klasifikovaný zápočet 100 (100) 51 3
        Test znalostí k relačním databázím Písemka 40  15
        Práce s více-rozměrnými daty Projekt 30  15
        Vytvoření jednoduchého XML procesoru Projekt 30  0
Rozsah povinné účasti: Úkoly se budou plnit dle pokynů na jednotlivých tutoriálech. Každý ze studentů musí absolvovat test znalostí k relačním databázím a implementovat vybraný úkol k více-rozměrným datům.

Zobrazit historii

Podmínky absolvování předmětu a účast na cvičeních v rámci ISP: Splnění všech povinných úkolů v individuálně dohodnutých termínech.

Zobrazit historii

Výskyt ve studijních plánech

Akademický rokProgramObor/spec.Spec.ZaměřeníFormaJazyk výuky Konz. stř.RočníkZLTyp povinnosti
2021/2022 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 2 volitelný odborný stu. plán
2021/2022 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 2 volitelný odborný stu. plán
2020/2021 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 2 volitelný odborný stu. plán
2020/2021 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 2 volitelný odborný stu. plán
2019/2020 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 2 volitelný odborný stu. plán
2019/2020 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 2 volitelný odborný stu. plán
2018/2019 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 2 volitelný odborný stu. plán
2018/2019 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 2 volitelný odborný stu. plán
2017/2018 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 2 volitelný odborný stu. plán
2017/2018 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 2 volitelný odborný stu. plán
2016/2017 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 2 volitelný odborný stu. plán
2016/2017 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 2 volitelný odborný stu. plán
2015/2016 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 2 volitelný odborný stu. plán
2015/2016 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 2 volitelný odborný stu. plán

Výskyt ve speciálních blocích

Název blokuAkademický rokForma studiaJazyk výuky RočníkZLTyp blokuVlastník bloku

Hodnocení Výuky



2021/2022 zimní
2020/2021 zimní
2017/2018 zimní
2016/2017 zimní
2015/2016 zimní