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

        ParseError: KaTeX parse error: Undefined control sequence: \and at position 9: ∃x(R(x) \̲a̲n̲d̲ ̲φ(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í

      ParseError: KaTeX parse error: Undefined control sequence: \and at position 6: R(x) \̲a̲n̲d̲ ̲φ(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

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

   obsahuje stejné volné proměnné

   • ( $\varphi_1 \Rightarrow \varphi_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í), $φ \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á

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í), $φ \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é

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

}}

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