Dependencia generadora de igualdad

En la teoría de bases de datos relacionales , una dependencia generadora de igualdad (EGD, por sus siglas en inglés) es un tipo específico de restricción sobre los datos. 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 EGD (o, más generalmente, un conjunto de ED) y, si termina (lo cual es a priori indecidible), produce una instancia que sí satisface los EGD.

Una subclase importante de dependencias generadoras de igualdad son las dependencias funcionales .

Una dependencia generadora de igualdad 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 \psi (y_{1},\ldots ,y_{m})}$

dónde${\displaystyle \{y_{1},\ldots ,y_{m}\}\subseteq \{x_{1},\ldots ,x_{n}\}}$,${\displaystyle \phi }$es una conjunción de átomos relacionales y de igualdad y${\displaystyle \psi }$es una conjunción no vacía de átomos de igualdad. 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. ^{[ 1 ]} 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).

Una definición equivalente es la siguiente: ^{[ 2 ]}

${\displaystyle \forall x_{1},\ldots ,x_{n}.\phi (x_{1},\ldots ,x_{n})\rightarrow x_{i}=x_{j}}$

dónde${\displaystyle i,j\in \{1,\ldots ,n\}}$En efecto, generar una conjunción de igualdades equivale a tener múltiples dependencias que generan una sola igualdad.

• Abiteboul, Serge ; Hull, Richard B .; Vianu, Victor (1995). Fundamentos de 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