460-4069/01 – 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 | češ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 - 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
Výskyt ve studijních plánech
Výskyt ve speciálních blocích
Hodnocení Výuky