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

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

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
Principles of Database and Knowledge-base Systems (Jeffrey D. Ullman) - zdarma ke stažení na google books

Bezpečné (safe) formule NRK

syntaktická pravidla pro bezpečné výrazy v NRK (nebylo na přednášce)

nemají ∀ každá disjunkce $ \varphi_1 \or \varphi_2 $obsahuje pouze 1 stejnou volnou proměnnou 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é ¬ 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

• 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