Gelijkheid genererende afhankelijkheid - Equality-generating dependency

In relationele database theorie , een gelijkheid genereren dependency (EGD) is een bepaald soort beperking op de data. Het is een subklasse van de klasse van ingebedde afhankelijkheden (ED). Een ED zin tussen eerste orde logica van de vorm: ∀x1 ... xn, P (x1, ..., xn) → ∃z1, ..., zk, Q (y1, ..., ym ) waarbij {z1, ..., zk} = {y1, ..., ym} \ {x1, ..., xn} en P een mogelijk lege en Q een niet-lege combinatie van gelijke atomen. An gelijkheid atoom heeft de vorm wi = wj waarbij elk van de w, ..., wh, wi, wj, zijn variabelen of constanten. Een algoritme bekend als de jacht neemt als input een instantie die al dan niet een reeks EGDS (of meer algemeen een reeks HO) niet aan en, indien eindigt (die a priori onbeslisbare) uitgang een instantie die wel voldoen de EGDS.

Referenties