460-4069/04 – 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íPovinnostpovinně volitelný typu A
Ročník2Semestrzimní
Jazyk výukyangličtina
Rok zavedení2022/2023Rok zrušení
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 18+0

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

Prezenční forma (platnost od: 2022/2023 zimní 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: Většina bodů bude získána za bodované úkoly na cvičení. Student se tedy musí účastnit cvičení, aby tyto úkoly vypracoval. Na jednom cvičení dále proběhne test ověřující teoretické znalosti.

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
2024/2025 (N0613A140035) Informatika DS P angličtina Ostrava 2 povinně volitelný typu A stu. plán
2023/2024 (N0613A140035) Informatika DS P angličtina Ostrava 2 povinně volitelný typu A stu. plán
2023/2024 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P angličtina Ostrava 2 volitelný odborný stu. plán
2022/2023 (N0613A140035) Informatika DS P angličtina Ostrava 2 povinně volitelný typu A stu. plán
2022/2023 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P 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í.