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<sub>B>
zápist T tabulkou:
| R | A | B | C |
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:
Statická analýza - Složitosti