Formální základy databázové technologie/Ostatni

Z ωικι.matfyz.cz
Přejít na: navigace, hledání

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(xA,xB,4), S(4,xD,xE)
    • u = <A:xA, B:xB>
    • zápist T tabulkou:
R A B C

xA xB 4
S C D E

4 xD xE

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:
Tablo.jpg
Substituce (homomorfismus) z (b) na (a):

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)

Substituce z (c) na (b):

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)

Substituce z (d) na (c):

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
inkluze splnitelnost
T-dotazy NP úplné ano
DRK co-r.e. a ¬r. r.e. a ¬r.
Datalog ¬r. r.

Veta: Necht q a q' jsou T-dotazy. Pak nasledujici jsou NP-uplne problemy:

(a) qq' (problém existence homomorfismu)
(b) qq'

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


další zdroje