Dependencia generadora de tuplas

En la teoría de bases de datos relacionales , una dependencia generadora de tuplas (TGD, por sus siglas en inglés) es un tipo específico de restricción en una base de datos relacional . Es una subclase de la clase de dependencias incrustadas (ED, por sus siglas en inglés).

Un algoritmo conocido como " la persecución" toma como entrada una instancia que puede o no satisfacer un conjunto de TGD (o, más generalmente, ED) y, si termina (lo cual es a priori indecidible), produce una instancia que sí satisface los TGD.

Una dependencia generadora de tuplas es una sentencia en lógica de primer orden de la forma: ^{[ 1 ]}

${\displaystyle \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})}$

dónde${\displaystyle \phi }$es posiblemente vacío y${\displaystyle \psi }$es una conjunción no vacía de átomos relacionales . Un átomo relacional tiene la forma${\displaystyle R(w_{1},\ldots ,w_{h})}$donde cada uno de los términos${\displaystyle w,\ldots,w_{h}}$son variables o constantes.

Se han definido varios fragmentos de TGD. Por ejemplo, los TGD completos son aquellos que no utilizan el cuantificador existencial. Los TGD completos pueden considerarse, de forma equivalente, como programas en el lenguaje de consulta Datalog .

También hay algunos fragmentos de TGD que pueden expresarse en lógica protegida , en particular: ^{[ 2 ] [ 3 ] [ 4 ]}

• En los TGD con frontera protegida (FGTGD), todas las variables compartidas por el cuerpo y la cabeza de una regla (llamadas variables frontera ) deben aparecer juntas en algún átomo;
• Las TGD protegidas (GTGD) son FGTGD particulares donde todas las variables utilizadas en el cuerpo de una regla deben aparecer juntas en algún átomo;
• Los TGD lineales (LTGD) son GTGD particulares cuyo cuerpo consta de un solo átomo;
• Las dependencias de inclusión (IND) son LTD particulares donde en ambos lados de la regla hay solo un átomo relacional. ^{[ 5 ]}

El poder expresivo de estos fragmentos y TGD se ha estudiado en profundidad. Por ejemplo, Heng Zhang et al. ^{[ 3 ]} , así como Marco Console y Phokion G. Kolaitis ^{[ 4 ]} , han desarrollado una serie de caracterizaciones basadas en la teoría de modelos para estos lenguajes. Además, Heng Zhang y Guifei Jiang han proporcionado caracterizaciones del poder expresivo de los TGD, varias de sus extensiones y los TGD lineales, específicamente en el contexto de la respuesta a consultas ^{[ 6 ] .}

En SQL , las dependencias de inclusión se expresan típicamente mediante una restricción más fuerte llamada clave foránea , que obliga a las variables frontera a ser una clave candidata en la tabla correspondiente al átomo relacional de${\displaystyle \psi }$.

• Abiteboul, Serge ; Hull, Richard B .; Vianu, Victor (1995). Fundamentos de las bases de datos . Addison-Wesley. ISBN 0-201-53771-0.
• Alin Deutsch, FOL Modeling of Integrity Constraints, https://web.archive.org/web/20140912044956/http://db.ucsd.edu/pubsFileFolder/305.pdf