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

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

∀x1 ... xn, P (x1, ..., xn) → ∃z1, ..., zk, Q (y1, ..., ym)

где {z1, ..., zk} = {y1, ..., ym} {x1, ..., xn}, а P - возможно, пустой, а Q - непустая конъюнкция атомов отношения и равенства . Реляционный атом имеет форму R (w1, ..., wh), а атом равенства имеет форму wi = wj, где каждый из w, ..., wh, wi, wj - переменные или константы. Когда все атомы в Q равны, ED является EGD, а когда все атомы в Q являются относительными, ED является TGD. Каждый ED эквивалентен EGD и TGD. Говорят, что TGD заполнен, когда квантор существования пуст. Алгоритм, известный как погоня принимает в качестве входных данных экземпляр, который может или не может удовлетворять набору ED, и, если он завершается (что априори неразрешимо), выводит экземпляр, который действительно удовлетворяет ED.

использованная литература