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</sub>>

  • zápist T tabulkou:

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<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

Veta: Necht q a q' jsou T-dotazy. Pak nasledujici jsou NP-uplne problemy: :(a) q ⊆ q<nowiki/>' (problém existence homomorfismu)

:(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=

}}