Zależność generująca równość

W teorii relacyjnych baz danych zależność generująca równość (EGD) jest pewnym rodzajem ograniczenia danych. Jest to podklasa klasy osadzonych zależności (ED).

Algorytm znany jako chase przyjmuje jako dane wejściowe instancję, która może, ale nie musi, spełniać zestaw EGD (lub, bardziej ogólnie, zestaw ED), a jeśli się zakończy (co jest a priori nierozstrzygalne), wyprowadza instancję, która spełnia wymagania EGD.

Ważną podklasą zależności generujących równość są zależności funkcjonalne .

Definicja

Zależność generująca równość to zdanie w logice pierwszego rzędu postaci:

{\ Displaystyle \ forall x_ {1}, \ ldots, x_ {n}. \ phi (x_ {1}, \ ldots, x_{n})\strzałka w prawo \psi (y_{1},\ldots,y_{m})}

gdzie $}}$ ${\ Displaystyle \ {y_ {1}, \ ldots, y_ {m} \} \ subseteq \ {x_ {1}, \ ldots ,$ $jest$ $niepustą$ , jest koniunkcją atomów relacyjnych i równościowych, a koniunkcją atomów równości. Atom relacyjny ma postać, a atom równości ma $h$ $\ Displaystyle R (w_ {1}, \ ldots, w_ {$ , gdzie każdy z wyrazów ${j}}$ są zmiennymi lub stałymi.

Równoważna definicja jest następująca:

{\ Displaystyle \ forall x_ {1}, \ ldots, x_ {n}. \ phi (x_ {1}, \ ldots, x_ {n}) \rightarrow x_{i}=x_{j}}

gdzie ${\ Displaystyle i, j \ w \ {1, \ ldots, n \}}$ . Rzeczywiście, generowanie koniunkcji równości jest równoznaczne z posiadaniem wielu zależności, które generują tylko jedną równość.

^ Cali, Andrea; Pieris, Andreas (2011). O zależnościach generujących równość w zapytaniach ontologicznych - raport wstępny (PDF) . Międzynarodowe warsztaty Alberto Mendelzona na temat podstaw zarządzania danymi (AMW 2011).

Dalsza lektura

Serge Abiteboul , Richard B. Hull, Victor Vianu : Podstawy baz danych. Addison-Wesley, 1995.
Alin Deutsch, FOL Modelowanie ograniczeń integralności, https://web.archive.org/web/20140912044956/http://db.ucsd.edu/pubsFileFolder/305.pdf

[1] Cali, Andrea; Pieris, Andreas (2011). O zależnościach generujących równość w zapytaniach ontologicznych - raport wstępny (PDF) . Międzynarodowe warsztaty Alberto Mendelzona na temat podstaw zarządzania danymi (AMW 2011).