Formální základy databázové technologie/Bezpečné výrazy

Z ωικι.matfyz.cz
Verze z 28. 5. 2015, 22:00, kterou vytvořil PeterBlack (diskuse | příspěvky)

(rozdíl) ← Starší verze | zobrazit aktuální verzi (rozdíl) | Novější verze → (rozdíl)
Přejít na: navigace, hledání
bezpečné fle
  • každá bezpečná fle je doménově nezávislá
  • dá se rychle zjistit zda ze daná fle bezpečná
  • N/DRK fle vyjádřitelné realnými DJ jsou bezpečné

volne proměnné - nejsou v zadnem kvantif. (např R(x)), vázané - jsou v nejakem kvantifikátoru (např: ∃xR(x))

Definujeme: výrazy dotazu $ \{x_1,...,x_k | A(x_1,...,x_k )\} $, $ A $ je formule DRK, databáze $ R* $, dom je doména pro $ R $, aktuální doména formule $ A $ $ adom(A) $ je množina hodnot z relací v $ A $ a konstant v $ A $.

Problém RK jsou nekonečné domény, které je potřeba omezit (aktuální doménou - adom), aby nedocházelo k nežádoucím jevům:

  • Nekonečná odpověď v případě nekonečné $ dom $ (např. $ \{ x,y | x=y \} $ )
  • situace, kdy TRUE ohodnocení volných proměnných není v DB (např. $ \{ x | ¬Employee(Name: x)\} $ )
  • nekonečný výpočet (impl. vyhodnoceni kvantifikace na nekonečné $ dom $) (např. $ \{ x | ∀y R(x,...,y) \} $ kde y má nekon.doménu )

řešením jsou doménově nezávislé (definitní, určité) dotazy $ DRK^{ind} $

  • tj.: nejsou definitní pokud pod ruznymi $ dom $ davaji ruzne vysledky
  • bezpečná formule ⇒ je také doménově nezávislá (opačně to neplatí, dom.nezávislé jsou nadmnožinou bezpečných)
další info  

další sémantiky (stejně silné), které uvedené problémy řeší:

  • neomezená interpretace s omezeným výstupem $ DRK^{out} $ (výsledek je definová jako průnik s $ adom^k $)
  • omezená interpretace $ DRK^{lim} $ (vyhodnocení dotazu probíhá pouze přes hodnoty z $ adom $)
    • každou proměnnou (volné i vázanou) omezíme doménu - přidáme $ R(x) $ a tím omezíme doménu $ x $ na $ adom(R) $ vzhledem k relaci $ R* $
    • konkrétněji:
      • Omezené kvantifikátory:
        • místo $ ∃x(φ(x)) $ se používá $ ∃x(R(x) \and φ(x)) $ - tedy $ (∃x ∈ R) φ(x) $
        • místo $ ∀x(φ(x)) $ se používá $ ∀x(R(x) ⇒ φ(x)) $ - tedy $ (∀x ∈ R) φ(x) $
      • volné proměnné ve φ(x) můžeme také omezit – konjunkcí $ R(x) \and φ(x) $

$ DRK^{out}≅DRK^{lim}≅DRK^{ind} $

zjistit, zda je DRK výraz dom.nezávislý je nerozhodnutelný problém (∄program co zjisti jestli je dom.nezávislý) a tedy $ DRK^{ind} $ není rek.spočetný jazyk

máme ale jednoduchá syntaktická pravidla (třídu) která nám určují bezpečné formule (jsou podmnožinou dom.nezávislých):

Bezpečné formule DRK[editovat | editovat zdroj]

př: bezpečná pravidla DRK:
  • ¬R(x,y) NENÍ bezpečný (dle 3.a)
  • x = y NENÍ bezpečný (3.a)
  • x = y ∨ R(x,y) NENÍ bezpečný (2,3.a)
  • x = y ∧ R(x,y) JE bezpečný
př: nebezpečná pravidla NRK
  • pomoci ¬: {S $ | $ ¬(S ∈ Sailors)}
  • pozn.: RA neobsahuje nebezpecna pravidla (nema ¬) a je doménově nezávislá
  1. nemají ∀
    • ( $ ∀x~ φ(x) $ můžeme nahradit $ ¬∃x (¬φ(x)) $ )
  2. každá disjunkce $ \varphi_1 \or \varphi_2 \or ... $obsahuje stejné volné proměnné
    • ( $ \varphi_1 \Rightarrow \varphi_2 $ tranformujeme na $ ¬\varphi_1\or\varphi_2 $ )
  3. každá konjunkce (maximální), $ φ \equiv φ_1∧...∧φ_r $má všechny volné proměnné omezené, tj. platí pro ni alespoň 1 z podmínek:
    (a) proměnná je volná v $ \varphi_i $co není negace ani binární porovnání
    (b) ∃$ \varphi_i\equiv x=a $, kde $ a $ je konstanta nebo omezená proměnná
  4. ¬ smí být pouze v konjunkcích z bodu 3
další zdroje  
Bezpečné (safe) formule NRK[editovat | editovat zdroj]
syntaktická pravidla pro bezpečné výrazy v NRK (nebylo na přednášce)  
  1. nemají ∀
  2. každá disjunkce $ \varphi_1 \or \varphi_2 $obsahuje pouze 1 stejnou volnou proměnnou
  3. každá konjunkce (maximální), $ φ \equiv φ_1∧...∧φ_r $má všechny volné proměnné omezené, tj. platí pro ni alespoň 1 z podmínek:
    (a) $ \varphi_i $ není negace ani binární porovnání ( $ \varphi_i $ obsahuje $ x $v ni volnou ⇒ každá komponenta $ x $ je omezená)
    (b) $ \varphi_i\equiv x.A=a $, kde $ a $ je konstanta nebo komponenta omezené proměnné
  4. ¬ smí být pouze v konjunkcích z bodu 3
př: nebezpečná pravidla Datalog

z přednášky:

  • GREATER(x,y) :- x > y (není bezpečné)
  • FRIEND(x,y) :- M(x) (není bezpečné)
  • S1(y,w) :- F(x,y), F(x,w), y ≠ w (je bezpečné, ≠ se bere jako =)

z media:Datalog-unsafe_rules.PNG:

  • s(X) :- r(Y) (není bezpečné)
  • s(X) :- r(Y) AND NOT r(X) (není bezpečné)
  • s(X) :- r(Y) AND X < Y (není bezpečné)

(ve všech připadech nekonečnost X splni pravidlo i když je R konečná relace)

Bezpečné pravidla v Datalogu[editovat | editovat zdroj]

  • Omezená proměnná x v Datalogu je taková, která se vyskytuje v těle literálu L a pro jehož tělo platí:
    • L je dán pravým predikátem, nebo
      • pravý predikát - jméno zákl.db relace nebo jméno virtuální relace (prakticky EDB nebo levá strana IDB pravidla)
    • L je x = a nebo a = x , kde a je konstanta nebo omezená proměnná

Pravidlo je bezpečné pokud jsou ∀proměnné omezené.

Datalog má povolená pouze bezpečná pravidla a dále platí, že v hlavách jsou pouze jména virtuálních relací

💡 (ktere nejsou v EDB), tzn odvozováním nevytvářím další základní data