Tuple-generating Dependencies
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). 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. Definition A tuple-generating dependency is a sentence in first-order logic of the form: :\forall x_1,\ldots, x_n . \phi(x_1, \ldots, x_n) \rightarrow \exists y_1, \ldots, y_m, \psi(x_1, \ldots, x_n, y_1, \ldots, y_m) where \phi is a possibly empty and \psi is a non-empty conjunction of relational atoms. A relational atom has the form R(w_1, \ldots, w_h), where each of the terms w, \ldots, w_h are variables or constants. Fragments Several fragments of TGDs have been defined. For instance, ''full TGDs'' are TGDs which do not use the existential quantifier. Full TGDs ...
[...More Info...]       [...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]   [Amazon]