Зависимость, порождающая равенство

В теории реляционных баз данных зависимость , генерирующая равенство (EGD), представляет собой определенный вид ограничения на данные. Это подкласс класса встроенных зависимостей (ED).

Алгоритм, известный как погоня, принимает на вход экземпляр, который может удовлетворять или не удовлетворять набору EGD (или, в более общем смысле, набору ED), и, если он завершается (что априори неразрешимо), выводит экземпляр, который действительно удовлетворяет требованиям EGD.

Важным подклассом зависимостей, генерирующих равенство, являются функциональные зависимости .

Определение

Зависимость, порождающая равенство, — это предложение в логике первого порядка вида:

$\forall x_{1},\ldots ,x_{n}.\phi (x_{1},\ldots ,x_{n})\rightarrow \psi (y_{1},\ldots ,y_{m})$

где $\{y_{1},\ldots ,y_{m}\}\subseteq \{x_{1},\ldots ,x_{n}\}$, $\phi$ представляет собой соединение атомов отношения и равенства и $\psi$ является непустой конъюнкцией атомов равенства. Реляционный атом имеет вид $R(w_{1},\ldots ,w_{h})$ а атом равенства имеет вид $w_{i}=w_{j}$, где каждое из слагаемых $w,...,w_{h},w_{i},w_{j}$ являются переменными или константами.

На самом деле, можно удалить все атомы равенства из тела зависимости без потери общности. Например, если тело состоит из союза $A(x,y)\land B(y,z,w)\land y=3\land z=w$, то его можно заменить на $A(x,3)\land B(3,z,z)$ (аналогично заменяя возможные вхождения переменных $y$ и $w$ в голове).

Эквивалентное определение следующее:

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

где $i,j\in \{1,\ldots ,n\}$.Действительно, создание комбинации равенств эквивалентно наличию нескольких зависимостей, которые генерируют только одно равенство.

Дальнейшее чтение

• Абитбул, Серж ; Халл, Ричард Б .; Виану, Виктор (1995). Основы баз данных . Аддисон-Уэсли. ISBN  0-201-53771-0 .
• Алин Дойч, FOL Моделирование ограничений целостности, https://web.archive.org/web/20140912044956/http://db.ucsd.edu/pubsFileFolder/305.pdf