Tuple-generating dependency

In relational database theory, a tuple-generating dependency (TGD) is a certain kind of constraint on a relational database. It is a subclass of the class of embedded dependencies (EDs). A TGD is a sentence in first-order logic of the form: ∀x1 ... xn, P(x1, ..., xn) → ∃z1, ..., zk, Q(y1, ..., ym) where {z1, ..., zk} = {y1, ..., ym} \ {x1, ..., xn}, and P is a possibly empty and Q is a non-empty conjunction of relational atoms. A relational atom has the form R(w1, ..., wh) where each of the w, ..., wh, wi, wj, are variables or constants. An algorithm known as the chase takes as input an instance that may or may not satisfy a set of TGDs (or more generally EDs), and, if it terminates (which is a priori undecidable), outputs an instance that does satisfy the TGDs.

References

    This article is issued from Wikipedia - version of the Saturday, October 11, 2014. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.