{{zarovka |

  • 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é

| bezpečné fle }}

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)

{{Collapse|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

{{zarovka| 1 =

  • ¬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ý

| 2 = př: bezpečná pravidla DRK }}

{{zarovka |

  • pomoci ¬: {S | ¬(S ∈ Sailors)}

  • pozn.: RA neobsahuje nebezpecna pravidla (nema ¬) a je doménově nezávislá

| př: nebezpečná pravidla NRK }}

  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∧...∧φ_rmá všechny volné proměnné omezené, **tj. platí pro ni alespoň 1 z podmínek:

#:(a) proměnná je volná v \varphi_ico není negace ani binární porovnání #:(b) ∃\varphi_i\equiv x=a, kde a je konstanta nebo omezená proměnná

  1. ¬ smí být pouze v konjunkcích z bodu 3

{{Zdroje|1 =

}}

Bezpečné (safe) formule NRK

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

  1. nemají ∀

  2. každá disjunkce \varphi_1 \or \varphi_2obsahuje pouze 1 stejnou volnou proměnnou

  3. každá **konjunkce (maximální), φ \equiv φ_1∧...∧φ_rmá 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 xv ni volnou ⇒ každá komponenta x je omezená) #:(b) \varphi_i\equiv x.A=a, kde a je konstanta nebo komponenta omezené proměnné

  1. ¬ smí být pouze v konjunkcích z bodu 3

}}

{{: Formální_základy_databázové_technologie/Bezpečné_výrazy_Datalog}}