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

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_A,x_B,4), S(4,x_D,x_E)
  • u = <A:x_A, B:x_B>
  • 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
Inductive Models of User Preferences for Semantic Web Dotazování s preferencemi, zápisky z přednášek a cvičení