okruhy 14/15: ''Relacní kalkuly, relacní algebry, deduktivní databáze. Relacní úplnost. Bezpecné výrazy, ekvivalence relacních dotazovacích jazyku. Veta o tranzitivním uzáveru relace. Sémantika SQL. Datalog, 3 sémantiky a jejich ekvivalence. Datalog s negací, stratifikace. Deduktivní databáze. Rekurze v SQL. Tablo dotazy - statická analýza a optimalizace relacních dotazovacích jazyku. Modelování preferencí, dotazování s preferencemi.''
Podle Majklových zápisků: [http://ttnz.cz/statnice/statnice/] čepičky (🎓) udávají pravděpodobnou důležitost okruhu u státnic.
== Relacní kalkuly, relacní algebry. Relacní úplnost. Bezpecné výrazy, ekvivalence relacních dotazovacích jazyku. (🎓🎓🎓🎓🎓🎓🎓🎓🎓🎓🎓🎓) ==
{{:Formální_základy_databázové_technologie/Relace}}
== Datalog (🎓🎓🎓🎓🎓🎓🎓) ==
{{:Formální_základy_databázové_technologie/Datalog}}
[[Soubor:Cse670235x.png|right|thumb|374px|'''kořeny SQL''' [http://web.cse.ohio-state.edu/~gurari/course/cse670/html/cse670Ch15.html zdroj]]]
== Sémantika SQL ==
''viz [[Databázové_modely_a_jazyky#SQL_a_jeho_standardy|to samé v jiném okruhu]]''
== Rekurze v SQL. (🎓) ==
''viz [[Databázové_modely_a_jazyky#Rekurze v SQL.|přesunuto vedle do SQL]]''
== Tablo dotazy - statická analýza a optimalizace relačních dotazovacích jazyků. () ==
{{Zkazky|
* '''SQL + vyhodnocovanie a optimalizácia dotazov (Richta)''' - bol super, dokonca mu nevadilo, že som zabudol popísať optimalizáciu, stačilo len 3 vetami vysvetliť, o čo ide
}}
{{TODO|projit a doplnit}}
* Statická analýza (relačních dotazovacích jazyků RDJ) chápeme ve smyslu statické analýzy programovacích jazyků PJ (viz Static code analysis) - analýza (kódu) dotazů bez vykonávání programů z nich vytvořených (bez dynamické analýzy). Lze ji vykonat automatizovaným nástrojem ale také formálními metodami které dokazují vlastnosti dotazů.
* Obvyklé cíle statické analýzy PJ (a tedy i RDJ):
** odhalení chyb
** Optimalizace jako součást kompilace
** Odhad složitosti úloh
** Bezpečnost, …
'''Veta:''' Pro každý omezený relační výraz E (selekce, projekce, přirozené spojení s disjunktními proměnnými) existuje T-dotaz q = (T; u) tak, že pro každou instanci I platí E(I) = q(I).
===Lokální optimalizace dotazů===
===Globální optimalizace===
====Homomorfismus tableau dotazů====
Nechť q1 = (T1, u1) a q2 = (T2, u2) jsou dva tablo dotazy. '''Homomorfismus''' z q2 na q1 je substituce θ taková, že θ(T2) ⊆ T1 a θ(u2) ⊆ u1.
'''Věta:''' q1 ⊆ q2 ⇔ existuje homomorfismus z q2 na q1.
Řekneme, že tablo dotaz (T, u) je '''minimální''', když neexistuje dotaz (S, v) ekvivalentní s (T, u) a |S|<|T| (tedy ostře méně spojení).
===Složitosti===
:co-r.e. ... co-rekursivne spocetne
:¬r. ... neni rekurzivni
{| class="wikitable"
|-
!
! inkluze
! splnitelnost
|-
! T-dotazy
| NP úplné
| ano
|-
! DRK
| co-r.e. a ¬r.
| r.e. a ¬r.
|-
! Datalog
| ¬r.
| r.
|}
'''Veta''': Necht <math>q</math> a <math>q'</math> jsou T-dotazy. Pak nasledujici jsou NP-uplne problemy:
:(a) <math>q ⊆ q'</math> (problém existence homomorfismu)
:(b) <math>q ≡ q'</math>
'''Veta (Datalog)''': Splnitelnost idb relace r programem P je rozhodnutelna.
== Modelování preferencí, dotazování s preferencemi. (nové od 2011) ==
{{TODO|projit}}
* Modely preferencí a jejich učení - Model založený na atributech, kolaborativní filtrování, preferenční relace, hybridní modely
* Vyjádření preference - preferenční relace (porovnání x je lepší než y) vs. hodnotící funkce (x je dobrý na 5 hvězdiček, palec nahoru...).
* Implicitní vyjádření (vědomá akce) vs Explicitní vyjádření (chování se např. v eshopu - otevření detailů, prohlížení fotek, ...)
* Model preferencí umožňuje zjistit, jak je některý objekt preferovaný. Vytváří se z chování uživatele
* ''Model založený na atributech''
** Využívá atributů hodnocených položek
** Učení se sestává ze dvou kroků - lokální preference (normalizace hodnot atributů), globální preference (agregace ohodnocení a projekce vektorů do [0, 1])
* ''Kolaborativní filtrování''
** Najdu si množinu V uživatelů podobných uživateli U, kterým se líbí stejné věci
** „Zákazníci, kteří si koupili x si také koupili y“
** K výpočtu vzdáleností se používáji váhy sousedů, počítá se kosinova míra, pearsonova korelace ....
** Implementace - inmemory, bayesovy sítě, predikční modely...
* ''Preferenční relace''
** Užívané v ekonomii
** Porovnání objektů – x je lepší než y
** Neumožňuje jednoduché setřídění objektů podle aktuální vhodnosti
** Vytvořeno podle lidského uvažování - Přirozené pro uživatele, ale možná moc složité
** P(x,y) - mám radši y než x, R(x,y) - y je alespoň tak dobrá jako x, I(x,y) - mezi x a y nedokážu rozlišit, jsou stejně dobré
** CP-sítě Conditional probability networks
{{Statnice_I2}}
