Встроенная зависимость

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

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

Определение

Встроенная зависимость (ED) — это предложение в логике первого порядка вида:

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

где $\{z_{1},\ldots ,z_{k}\}=\{y_{1},\ldots ,y_{m}\}\setminus \{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$ в голове). Аналогично можно заменить возникающие в голове экзистенциальные переменные, если они появляются в каком-то атоме равенства.

Ограничения

В литературе существует множество общих ограничений на встроенные зависимости, в том числе:

• полные (или универсальные ) зависимости , которые не содержат экзистенциально-квантифицированных переменных ( $\exists z_{i}$)
• зависимости, генерирующие кортежи (TGD)
• зависимости, генерирующие равенство (EGD)
• одноголовые (или 1-head ) зависимости , которые имеют только один атом в голове
• униреляционные зависимости , в которых встречается только один символ отношения

Когда все атомы в $\psi$ являются равенствами, ED является EGD и, когда все атомы в $\psi$ реляционны, ED является TGD. Каждая ED эквивалентна EGD и TGD.

Расширения

Распространенным расширением встроенных зависимостей являются дизъюнктивные встроенные зависимости (DED). который можно определить следующим образом:

$\forall x_{1},\ldots ,x_{n}.\phi (x_{1},\ldots ,x_{n})\rightarrow \bigvee _{i=1}^{\ell }\exists z_{1}^{i},\ldots ,z_{k}^{i}.\psi (y_{1}^{i},\ldots ,y_{m}^{i})$

где $\{z_{1}^{i},\ldots ,z_{k}^{i}\}=\{y_{1}^{i},\ldots ,y_{m}^{i}\}\setminus \{x_{1},\ldots ,x_{n}\}$ и $\phi$ и $\psi$ представляют собой соединения атомов отношения и равенства.

Дизъюнктивные встроенные зависимости более выразительны, чем простые встроенные зависимости, поскольку DED в целом невозможно смоделировать с использованием одного или нескольких ED.Еще более выразительным ограничением является дизъюнктивная встроенная зависимость с неравенствами (обозначается DED $^{\neq }$), в котором каждый $\psi$ может содержать также атомы неравенства.

Все ограничения, приведенные выше, могут быть применены и к дизъюнктивным встроенным зависимостям. Помимо них, DED также можно рассматривать как обобщение дизъюнктивных зависимостей, генерирующих кортежи (DTGD).

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

• Канеллакис, Пэрис К. (1990). «Элементы теории реляционных баз данных» . Справочник по теоретической информатике, том B: Формальные модели и сематика . Амстердам: Эльзевир. стр. 1073–1156. дои : 10.1016/b978-0-444-88074-1.50022-6 . ISBN  978-0-444-88074-1 .
• Абитбул, Серж ; Халл, Ричард Б .; Виану, Виктор (1995). Основы баз данных . Аддисон-Уэсли. ISBN  0-201-53771-0 .
• Дойч, Алин (2009). «Моделирование ограничений целостности (зависимостей) FOL». Энциклопедия систем баз данных . Бостон, Массачусетс: Springer US. стр. 1155–1161. дои : 10.1007/978-0-387-39940-9_980 . ISBN  978-0-387-39940-9 .