Formální základy databázové technologie/Ostatni
Obsah
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:
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) q ⊆ q' (problém existence homomorfismu)
- (b) q ≡ q'
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 |
|---|
