Dependencia generadora de tuplas

En la teoría de bases de datos relacionales , una dependencia generadora de tuplas (TGD) es un tipo de restricción en una base de datos relacional . Es una subclase de la clase de dependencias integradas (ED).

Un algoritmo conocido como 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), genera como salida una instancia que sí satisface los TGD.

Definición

Una dependencia generadora de tuplas es una oración 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})}$

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

Fragmentos

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 equivalentes a 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]}

• En los TGD con protección de frontera (FGTGD), todas las variables compartidas por el cuerpo y la cabeza de una regla (llamadas variables de frontera ) deben aparecer juntas en algún átomo;
• Los TGD protegidos (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 está formado por un solo átomo;
• Las dependencias de inclusión (IND) son LTGD particulares donde en ambos lados de la regla hay solo un átomo relacional. ^[4]

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

Referencias

1. Fagin, Ronald (2009). "Dependencias generadoras de tuplas". En LIU, LING ; ÖZSU, M. TAMER (eds.). Enciclopedia de sistemas de bases de datos . Springer US. págs. 3201–3202. doi :10.1007/978-0-387-39940-9_1274. ISBN . 9780387355443.
2. Benedikt, Michael; Bourhis, Pierre; Jachiet, Louis; Thomazo, Michaël (agosto de 2019). Razonamiento sobre la divulgación en la integración de datos en presencia de restricciones de origen . IJCAI 2019 - 28.ª Conferencia conjunta internacional sobre inteligencia artificial. Macao, China. págs. 1551–1557. arXiv : 1906.00624 . doi :10.24963/ijcai.2019/215.
3. Console, Marco; Kolaitis, Phokion G.; Pieris, Andreas (junio de 2021). Caracterizaciones teóricas de modelos de ontologías basadas en reglas . Simposio sobre principios de sistemas de bases de datos. PODS'21: Actas del 40.º Simposio ACM SIGMOD-SIGACT-SIGAI sobre principios de sistemas de bases de datos . Evento virtual, China. págs. 416–428. doi : 10.1145/3452021.3458310 . hdl : 11573/1568516 .
4. Kolaitis, Phokion G. "Un tutorial sobre las dependencias de bases de datos" (PDF) . Universidad de California Santa Cruz e IBM Research - Almadén . Consultado el 10 de diciembre de 2021 . ^{[ enlace muerto ]}

Lectura adicional

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