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

В теория реляционных баз данных, зависимость, порождающая равенство (EGD) - это определенный вид ограничения данных. Это подкласс класса встроенные зависимости (ED). ED - это предложение в логике первого порядка вида: ∀x1 ... xn, P (x1, ..., xn) → ∃z1, ..., zk, Q (y1, ..., ym ), где {z1, ..., zk} = {y1, ..., ym} {x1, ..., xn}, и P - возможно, пусто, а Q - непустая конъюнкция атомов равенства. Атом равенства n имеет вид wi = wj, где каждый из w, ..., wh, wi, wj является переменными или константами. Алгоритм, известный как погоня принимает в качестве входных данных экземпляр, который может или не может удовлетворять набору EGD (или, в более общем смысле, набору ED), и, если он завершается (что априори неразрешимо), выводит экземпляр, который действительно удовлетворяет EGD.

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

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