== Tableau dotazy - statická analýza a optimalizace relačních dotazovacích jazyků. ==
{{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, …
== Tableau dotazy (konjunktivní dotazy) ==
umí jen selekci, projekci a kartezsky součin (tedy i join) - používají se k ilustraci principů optimalizace (na matfyzu :P)
tableau query = tabulkové dotazy ≈ konjunktivní dotazy DRK ≈ QBE - query by example
'''Věta:''' 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).
;Příklad:
:Relace: R(A,B,C), S(C,D,E) RA dotaz: (R*S)(C=4)[A,B]
:Tablo dotaz:
*q = (T,u)
**T = R(x<sub>A</sub>,x<sub>B</sub>,4), S(4,x<sub>D</sub>,x<sub>E</sub>)
**u = <A:x<sub>A</sub>, B:x<sub>B</sub>>
===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 ''q'' a ''<nowiki>q'</nowiki>'' 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) ==
Hledání optimalizované na preference uživatele ( pomáháme uživateli najít to co opravdu chce, nebo co si myslíme že by se mu mohlo líbit ).
* 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
