460-4069/02 – 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ýukyanglič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 - datové struktury 7. XML databáze - větvené dotazy a dotazy cest 8. XML databáze - holistické spojení pro větvené dotazy 9. Grafové databáze - nejkratší vzdálenost, index centrality 10. Jak ovlivňuje algoritmy prostředí ve které je vykonáváme - L2 cache, paralelizace 11. Jak ovlivňuje algoritmy prostředí ve které je vykonáváme - perzistentní úložiště, podpora ACID 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. Test ověřující schopnost správně interpretovat plán dotazu 6. Provádění prostorových dotazů 7. Indexy a algoritmy pro XML databáze 8. Základní typy dotazů v grafových databázích 9. Aproximace dotazů na index centrality 10. Optimalizace předchozích typů dotazů s ohledem na prostředí 11. Zapojení bloom filtrů do úkolů řešených v předchozích cvičeních 12. Test ověřující znalosti ohleně provádění nerelačních typů dotazů

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

Prezenční 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  51 3
Rozsah povinné účasti: Účast na cvičeních je povinná a je kontrolována. S rozsahem povinné účastí seznámí studenty garant předmětu na začátku semestru.

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 anglič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 anglič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 anglič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 anglič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 anglič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 anglič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 anglič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 anglič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 anglič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 anglič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 anglič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 anglič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

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