460-4069/02 – Algoritmy vykonávání dotazů (AVD)
Garantující katedra | Katedra informatiky | Kredity | 4 |
Garant předmětu | doc. Ing. Radim Bača, Ph.D. | Garant verze předmětu | doc. Ing. Radim Bača, Ph.D. |
Úroveň studia | pregraduální nebo graduální | Povinnost | volitelný odborný |
Ročník | 2 | Semestr | zimní |
| | Jazyk výuky | angličtina |
Rok zavedení | 2015/2016 | Rok zrušení | 2022/2023 |
Určeno pro fakulty | FEI | Určeno pro typy studia | navazující magisterské |
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:
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
Výskyt ve studijních plánech
Výskyt ve speciálních blocích
Hodnocení Výuky
Předmět neobsahuje žádné hodnocení.