{{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\ast$, 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|\neg Employee(Name:x)\}$ )

• nekonečný výpočet (impl. vyhodnoceni kvantifikace na nekonečné $dom$) (např. $\{x|\forall yR(x,...,y)\}$ kde y má nekon.doménu )

řešením jsou doménově nezávislé (definitní, určité) dotazy $DR{K}^{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 $DR{K}^{out}$ (výsledek je definová jako průnik s $ado{m}^k$)

• omezená interpretace $DR{K}^{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\ast$

  • konkrétněji:

    • Omezené kvantifikátory:

      • místo $\exists x(\phi (x))$ se používá

        ParseError: KaTeX parse error: Undefined control sequence: \and at position 9: ∃x(R(x) \̲a̲n̲d̲ ̲φ(x))

        - tedy $(\exists x\in R)\phi (x)$

      • místo $\forall x(\phi (x))$ se používá $\forall x(R(x)\Rightarrow \phi (x))$ - tedy $(\forall x\in R)\phi (x)$

    • volné proměnné ve φ(x) můžeme také omezit – konjunkcí

      ParseError: KaTeX parse error: Undefined control sequence: \and at position 6: R(x) \̲a̲n̲d̲ ̲φ(x)

$DR{K}^{out}\cong DR{K}^{lim}\cong DR{K}^{ind}$ }}

zjistit, zda je DRK výraz dom.nezávislý je nerozhodnutelný problém (∄program co zjisti jestli je dom.nezávislý) a tedy $DR{K}^{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í ∀

   • ( $\forall x\phi (x)$ můžeme nahradit $\neg \exists x(\neg \phi (x))$ )

2. každá disjunkce

   ParseError: KaTeX parse error: Undefined control sequence: \or at position 11: \varphi_1 \̲o̲r̲ ̲\varphi_2 \or .…

   obsahuje stejné volné proměnné

   • ( ${\phi }_1\Rightarrow {\phi }_2$ tranformujeme na

     ParseError: KaTeX parse error: Undefined control sequence: \or at position 11: ¬\varphi_1\̲o̲r̲\varphi_2

     )

3. každá **konjunkce (maximální), $\phi \equiv {\phi }_1\wedge ...\wedge {\phi }_r$má všechny volné proměnné omezené, **tj. platí pro ni alespoň 1 z podmínek:

#:(a) proměnná je volná v ${\phi }_i$co není negace ani binární porovnání #:(b) ∃${\phi }_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 =

• Principles of Database and Knowledge-base Systems (Jeffrey D. Ullman) - zdarma ke stažení na google books

}}

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

   ParseError: KaTeX parse error: Undefined control sequence: \or at position 11: \varphi_1 \̲o̲r̲ ̲\varphi_2

   obsahuje pouze 1 stejnou volnou proměnnou

3. každá **konjunkce (maximální), $\phi \equiv {\phi }_1\wedge ...\wedge {\phi }_r$má všechny volné proměnné omezené, **tj. platí pro ni alespoň 1 z podmínek:

#:(a) ${\phi }_i$ není negace ani binární porovnání ( ${\phi }_i$ obsahuje $x$v ni volnou ⇒ každá komponenta $x$ je omezená) #:(b) ${\phi }_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}}