460-4069/04 – 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 | povinně volitelný typu A |
Ročník | 2 | Semestr | zimní |
| | Jazyk výuky | angličtina |
Rok zavedení | 2022/2023 | Rok zrušení | |
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 bude během cvičení řešit úkoly, v rámci kterých si vyzkouší základní implementaci metod vykonávání dotazů. V průběhu semestru proběhne jeden test týkající se vykonávání dotazů v relačních databázích. Dále bude součástí vypracování projektu na vybrané téma.
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ů, přepisy plánů a optimalizační techniky
2. Cenová optimalizace - statistiky, cenový model
3. Výběr indexu na základě cenové optimalizace
4. Parametrizace a MEMO struktura
5. Jak ovlivňuje algoritmy prostředí, ve kterém je vykonáváme - L2 cache, paralelizace, SIMD, perzistentní
úložiště, distribuce dat
6. Základní problémy grafových databází - nejkratší vzdálenost, hledání trojúhelníků
7. Prostorové dotazy - rozsahové dotazy na nízkých dimenzích
8. Prostorové dotazy - K nejbližších sousedů ve více-rozměrných datech, aproximace (ANN)
9. Slévání seznamů - full-textové vyhledavače, podobnostní vyhledávání
10. Vyhledávání ve stromových datech - větvené dotazy
11. 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. Vliv statistik na plány dotazů
3. Změna plánů při změně fyzické struktury databáze
4. Test ověřující schopnost správně interpretovat plán dotazu
5. Základní typy dotazů v grafových databázích
6. Provádění grafových dotazů
7. ANN
8. Slévání seznamů invertovaného seznamu
9. StackTree algoritmus na stromových datech
10. Aplikace filtru
11. Prezentace projektu na vybrané téma
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í.