4. domácí úloha: Databázové dotazy #
- Předloha: pdv-04database.zip
- Do BRUTE odevzdávejte zip archiv obsahující soubor
query.h.
Vyhodnocování dotazů v databázových systémech často obnáší procházení velkého množství dat. Aby bylo vyhodnocování efektivní, databáze často odhadují jaká posloupnost operací vede k nejrychlejšímu výsledku. V této domácí úloze si zkusíte rozhodnout (a vyzkoušet), jaký přístup k vyhodnocení dotazů je nejvhodnější, přičemž se zaměříme na to, jak vyhodnocování dotazu co možná nejlépe paralelizovat.
Vaším úkolem bude vyhodnotit sadu dotazů na jednu tabulku. U každého dotazu bude Vaším úkolem rozhodnout, zda existuje alespoň jeden záznam v tabulce, pro který námi zadaná podmínka platí. My se Vás budeme ptát na pravdivostní hodnotu konjunkce (respektive disjunkce) těchto dílčích dotazů, tedy následující dva dotazy:
- Existuje pro každý dotaz (=predikát) alespoň jeden záznam v tabulce, pro který predikát platí?
- Existuje alespoň jeden záznam v tabulce, pro který platí některý z predikátů?
V případě, že chceme vyhodnocování takových dotazů paralelizovat, máme k dispozici dva základní dekompoziční přístupy:
- Vyhodnocování jednoho dotazu přidělíme jednomu vláknu (tj. každý dotaz bude zpracovávat právě jedno vlákno sekvenčním přístupem).
- Zparalelizujeme vyhodnocování každého dotazu (tj., vlákna si rozdělí řádky v tabulce, na kterých budou testovat pravdivost predikátu).
Vaším úkolem bude zamyslet se nad tím, který z těchto přístupů bude vhodnější pro který typ dotazu za předpokladu, že konjunkce (respektive disjunkce) je pravdivá. Následující otázky Vám mohou pomoci tento problém vyřešit:
- Je pro daný typ dotazu (a danou očekávanou pravdivostní hodnotu
true) důležité identifikovat alespoň jeden pravdivý dotaz v jedné vybrané tabulce? nebo - Je potřeba prohledávat více tabulek?
V některých situacích byste měli být schopní rozhodnout, jaká je pravdivostní hodnota dotazu bez toho, abyste museli prohledat otestovat všechny predikáty na všech záznamech v tabulce. V takové situaci je vhodné prohledávání ukončit.
Vaším úkolem je doimplementovat těla metod is_satisfied_for_all a is_satisfied_for_any v souboru query.h. Tyto metody mají za úkol rozhodnout, zda konjunkce (respektive disjunkce) dílčích dotazů je splněná.