===== 4. domácí úloha: Paralelizace provádění databázových dotazů =====

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ů. V řeči SQL dotazů se tedy jedná (schématicky) o dotazy typu:
<code sql>
select 1
where
  exists (select * from data_table where predicates[0](...)) and
  exists (select * from data_table where predicates[1](...)) and
  exists (select * from data_table where predicates[2](...)) and
  ...
</code>
a
<code sql>
select 1
where
  exists (select * from data_table where predicates[0](...)) or
  exists (select * from data_table where predicates[1](...)) or
  exists (select * from data_table where predicates[2](...)) or
  ...
</code>

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 poddotazu ''exists select * from data_table where predicates[0](...)'' přidělíme jednomu vláknu (tj. každý poddotaz bude zpracovávat právě jedno vlákno sekvenčním přístupem)
  - Zparalelizujeme vyhodnocování každého poddotazu (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?

<note important>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.</note>

Stáhněte si balíček [[https://cw.fel.cvut.cz/wiki/_media/courses/b4b36pdv/tutorials/hw05_database.zip|hw05_database.zip]].
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á.


Zazipovaný soubor ''query.h'' odevzdávejte do systému BRUTE. Před odevzdáním se ujistěte, že jste z kódu odebrali všechny ladící výpisy. **Termín pro odevzdání je 2.4. 23:59.** /* Termíny pro odevzdání jsou **28.3.2019 23:59 CET** (pro středeční cvičení) a **29.3.2019 23:59 CET** (pro čtvrteční cvičení). */

Za úlohu můžete získat maximálně **2 body** v závislosti na rychlosti Vašeho řešení.