Dependencia incrustada

En la teoría de bases de datos relacionales , una dependencia incrustada (DE) es un tipo específico de restricción en una base de datos relacional . Es el tipo de restricción más general utilizado en la práctica, e incluye tanto dependencias que generan tuplas como dependencias que generan igualdad . Las dependencias incrustadas pueden expresar dependencias funcionales, dependencias de unión, dependencias multivaluadas , dependencias de inclusión, dependencias de clave externa y muchas más.

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

Una dependencia incrustada (DE) es una oración en lógica de primer orden de la forma:

${\displaystyle \forall x_{1},\ldots ,x_{n}.\phi (x_{1},\ldots ,x_{n})\rightarrow \exists z_{1},\ldots ,z_{k}.\psi (y_{1},\ldots ,y_{m})}$

dónde${\displaystyle \{z_{1},\ldots ,z_{k}\}=\{y_{1},\ldots ,y_{m}\}\setminus \{x_{1},\ldots ,x_{n}\}}$y${\displaystyle \phi }$y${\displaystyle \psi }$son conjunciones de átomos relacionales y de igualdad. ^{[ 1 ]} Un átomo relacional tiene la forma${\displaystyle R(w_{1},\ldots ,w_{h})}$y un átomo de igualdad tiene la forma${\displaystyle w_{i}=w_{j}}$donde cada uno de los términos${\displaystyle w,...,w_{h},w_{i},w_{j}}$son variables o constantes.

En realidad, se pueden eliminar todos los átomos de igualdad del cuerpo de la dependencia sin pérdida de generalidad . ^{[ 2 ]} Por ejemplo, si el cuerpo consiste en la conjunción${\displaystyle A(x,y)\land B(y,z,w)\land y=3\land z=w}$, entonces puede ser reemplazado por${\displaystyle A(x,3)\land B(3,z,z)}$(reemplazando análogamente las posibles ocurrencias de las variables)${\displaystyle y}$y${\displaystyle w}$en la cabeza). Análogamente, se pueden reemplazar las variables existenciales que aparecen en la cabeza si aparecen en algún átomo de igualdad. ^{[ 2 ]}

En la literatura existen muchas restricciones comunes sobre las dependencias incrustadas, entre ellas: ^{[ 1 ] [ 3 ]}

• dependencias completas (o universales ) , que son aquellas sin variables cuantificadas existencialmente (${\displaystyle \exists z_{i}}$)
• dependencias generadoras de tuplas (TGD)
• dependencias generadoras de igualdad (EGD)
• dependencias de una sola cabeza (o de 1 cabeza ) , que tienen solo un átomo en la cabeza
• dependencias no relacionales , en las que solo aparece un símbolo de relación.

Cuando todos los átomos en${\displaystyle \psi }$son igualdades, el ED es un EGD y, cuando todos los átomos en${\displaystyle \psi }$son relacionales, el ED es un TGD. Cada ED es equivalente a un EGD y a un TGD.

Una extensión común de las dependencias incrustadas son las dependencias incrustadas disyuntivas (DED), ^{[ 4 ]} que se pueden definir de la siguiente manera:

${\displaystyle \forall x_{1},\ldots ,x_{n}.\phi (x_{1},\ldots ,x_{n})\rightarrow \bigvee _{i=1}^{\ell }\exists z_{1}^{i},\ldots ,z_{k}^{i}.\psi (y_{1}^{i},\ldots ,y_{m}^{i})}$

dónde${\displaystyle \{z_{1}^{i},\ldots ,z_{k}^{i}\}=\{y_{1}^{i},\ldots ,y_{m}^{i}\}\setminus \{x_{1},\ldots ,x_{n}\}}$y${\displaystyle \phi }$y${\displaystyle \psi }$son conjunciones de átomos relacionales y de igualdad.

Las dependencias incrustadas disyuntivas son más expresivas que las dependencias incrustadas simples, porque las DED en general no se pueden simular usando una o más ED. Una extensión adicional es la dependencia incrustada disyuntiva con desigualdades (indicada con DED).${\displaystyle ^{\neq }}$), en el que cada${\displaystyle \psi }$También puede contener átomos de desigualdad. ^{[ 4 ]} Sin embargo, es importante señalar que esta extensión no mejora el poder expresivo, ya que los DED ya son expresivamente completos para la respuesta a consultas booleanas recursivamente enumerables. ^{[ 5 ] [ 6 ] [ 7 ]}

Todas las restricciones anteriores también se pueden aplicar a las dependencias incrustadas disyuntivas. Además, las DED también pueden considerarse una generalización de las dependencias generadoras de tuplas disyuntivas (DTGD). ^{[ 8 ]}

A diferencia de la relación entre DED y ED, al considerar la respuesta a consultas con consultas conjuntivas (CQ), los DTGD siempre pueden reescribirse de forma equivalente como TGD. ^{[ 7 ]} Sin embargo, si se permiten uniones de consultas conjuntivas (UCQ) en la respuesta a consultas, el poder expresivo de los DTGD sigue siendo estrictamente superior al de los TGD. ^{[ 7 ]} Además, cabe destacar que los DED son estrictamente más expresivos que los DTGD. ^{[ 7 ]}

• Kanellakis, Paris C. (1990). «Elementos de la teoría de bases de datos relacionales» . Manual de informática teórica, volumen B: modelos formales y semática . Ámsterdam: Elsevier. pp. 1073–1156 . doi : 10.1016/b978-0-444-88074-1.50022-6 . ISBN  978-0-444-88074-1.
• Abiteboul, Serge ; Hull, Richard B .; Vianu, Victor (1995). Fundamentos de las bases de datos . Addison-Wesley. ISBN 0-201-53771-0.
• Deutsch, Alin (2009). "Modelado FOL de restricciones de integridad (dependencias)". Enciclopedia de sistemas de bases de datos . Boston, MA: Springer US. pp. 1155–1161 . doi : 10.1007/978-0-387-39940-9_980 . ISBN  978-0-387-39940-9.