== Tableau dotazy - statická analýza a optimalizace relačních dotazovacích jazyků. ==
'''Statická analýza''' (relačních dotazovacích jazyků) chápeme ve smyslu statické analýzy programovacích jazyků (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 programovacích jazyků (a tedy i relačních dotazovacích jazyků):
** 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ů '''statické analýzy''' (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>>
** zápist T tabulkou:
{| class=wikitable
|R
|A
|B
|C
|-
|<br>
|x<sub>A</sub>
|x<sub>B</sub>
|4
|}
{| class=wikitable
|S
|C
|D
|E
|-
|<br>
|4
|x<sub>D</sub>
|x<sub>E</sub>
|}
===Glogální optimalizace - Homomorfismus tableau dotazů===
Lokální optimalizace - klasická optimalizace třeba SQL přeuspořádáním stromu dotazu.
'''Globální optimalizace''' - vymaže vícero zbytečných spojení.
''q₁'' = (''T₁'', ''u₁'') a ''q₂'' = (''T₂'', ''u₂'') jsou tablo dotazy, '''homomorfismus''' ''q₂'' → ''q₁'' je substituce θ taková, že θ(''T₂'') ⊆ ''T₁'' a θ(''u₂'') ⊆ ''u₁''.
'''Věta:''' ''q₁'' ⊆ ''q₂'' ⇔ existuje homomorfismus ''q₂'' → ''q₁''.
Ř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í).
'''Příklad:'''<br>[[Soubor:Tablo.jpg|frameless|346x346px]]<br><u>Substituce (homomorfismus) z (b) na (a):</u>
:''x₁'' v (b) je to samé jako ''x'' v (a). Stejne tak ''y₁'' v (b) je to samé jako ''y'' v (a).
:''x'',''y'' zůstává.
:Je vidět, že (a) má v sobě všechny podmínky co upravene (b), takže výsledny homomorfismus je podmnožinou (a).
:Tudiz (a) je podmnozinou (b)
<u>Substituce z (c) na (b):</u>
: ''x''₂ v (c) je to samé jako ''x₁'' v (b). Stejne tak ''y''₂ v (c) je to samé jako ''y''₁ v (b).
: ''x'',''x₁'',''y'',''y₁'' zůstává.
: Je vidět, že (b) má v sobě všechny podmínky co upravene (c), takže výsledny homomorfismus je podmnožinou (b).
: Tudiz (a) je podmnozinou (c)
<u>Substituce z (d) na (c):</u>
:''x₁'' v (d) je to samé jako ''x₂'' v (c).
:''x,y,y₁'' zůstává.
:Je vidět, že (c) má v sobě všechny podmínky co má (d), takže výsledek bude podmnožinou výsledku (d)
===Statická analýza - 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) ''q'' ⊆ ''q''<nowiki/><nowiki>' (problém existence homomorfismu)</nowiki>
:(b) ''q'' ≡ ''q''<nowiki/>'
'''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 )
* '''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...).
* '''Explicitní vyjádření''' (vědomá akce) vs '''Implicitní vyjádření''' (chování se např. v eshopu - otevření detailů, prohlížení fotek, ...)
=== Modely preferencí a jejich učení ===
'''Model založený na atributech''', '''kolaborativní filtrování''', '''preferenční relace''', hybridní modely
* 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
{{Zdroje|1=
* [http://ceur-ws.org/Vol-235/paper10.pdf Inductive Models of User Preferences for Semantic Web]
* [http://artax.karlin.mff.cuni.cz/~michelfj/mff/dotazovani/dotazovani-v1.0.pdf Dotazování s preferencemi, zápisky z přednášek a cvičení]
}}
