Llave candidata

En el modelo relacional de bases de datos, una llave candidata (o clave candidata) de una relación es una mínima súper llave de esa relación; es decir, un conjunto de atributos tales que:

1. La relación no tiene dos distintas tuplas (es decir, filas o registros en el lenguaje de base de datos común) con los mismos valores para estos atributos (lo que significa que el conjunto de atributos es una súper llave).
2. No hay un subconjunto propio de estos atributos para los que se cumple la condición anterior (lo que significa que el conjunto es minimal).

Los atributos que la componen se llaman atributos principales. A la inversa, un atributo que no ocurre en cualquier llave candidata se llama un atributo no principal.

Dado que una relación contiene tuplas no duplicadas, el conjunto de todos sus atributos es una súper llave si no se utilizan valores nulos. De ello se desprende que cada relación tendrá al menos una clave candidata.

Las llaves candidatas de una relación nos dicen todas las posibles formas en que podemos identificar sus tuplas. Como tales, son un concepto importante para el diseño de esquemas de bases de datos.

La definición de llaves candidatas se puede ilustrar con el siguiente ejemplo abstracto. Considérese una variable de relación (relvar) R con atributos {A, B, C, D} que solo tiene los siguientes dos valores legales R1 y R2:

Aquí, r2 se diferencia de r1 solo en los valores de A y D de la última tupla.

Para r1, los siguientes conjuntos tienen la propiedad de unicidad (es decir, no hay dos tuplas distintas en la instancia con los mismos valores para los atributos del conjunto):

{A, B}, {A, C}, {B, C}, {A, B, C}, {A, B, D}, {A, C, D}, {B, C, D}, {A, B, C, D} 

Para r2 la propiedad de unicidad es válida para los siguientes conjuntos:

{B, C}, {B, D}, {C, D}, {A, B, C}, {A, B, D}, {A, C, D}, {B, C, D}, {A, B, C, D} 

Debido a que las súper llaves de un relvar son aquellos conjuntos de atributos que tienen la propiedad de unicidad para todos los valores legales de ese relvar, y porque suponemos que R1 y R2 son todos los valores legales que R puede tomar, podemos determinar el conjunto de súper llaves de R tomando la intersección de las dos listas:

{B, C}, {A, B, C}, {A, B, D}, {A, C, D}, {B, C, D}, {A, B, C, D} 

Por último tenemos que seleccionar los conjuntos para los cuales no hay subconjunto apropiado en la lista, que son en este caso:

{B, C}, {A, B, D}, {A, C, D} 

Estas son, de hecho, las llaves candidatas del relvar R.

Tenemos que considerar todas las relaciones que podrían ser asignadas a un relvar para determinar si un cierto conjunto de atributos es una llave candidata. Por ejemplo, si hubiéramos considerado solo r1, habríamos llegado a la conclusión de que {A, B} es una llave candidata, lo cual es incorrecto. Sin embargo, podríamos llegar a la conclusión a partir de esa relación que un cierto conjunto no es una llave candidata, porque ese conjunto no tiene la propiedad de unicidad (por ejemplo, {A, D} para r1). Debe tenerse en cuenta que la existencia de un subconjunto propio de un conjunto que tiene la propiedad de unicidad no puede en general ser utilizada como prueba de que el súper conjunto no es una llave candidata. En particular, cabe destacar que en el caso de una relación vacía, cada subconjunto de la partida tiene la propiedad de unicidad, incluyendo el conjunto vacío.

El conjunto de todas las llaves candidatas puede ser calculado, por ejemplo, a partir del conjunto de dependencias funcionales. Para ello, es necesario definir la clausura de atributos ${\displaystyle \alpha ^{+}}$ para un conjunto de atributos ${\displaystyle \alpha }$. El conjunto ${\displaystyle \alpha ^{+}}$ contiene todos los atributos que están funcionalmente implicados por ${\displaystyle \alpha }$.

Es bastante fácil encontrar una sola llave candidata. Empezamos con un conjunto ${\displaystyle \alpha }$ de atributos y tratamos de eliminar sucesivamente cada atributo. Si después de eliminar un atributo la clausura permanece igual, entonces este atributo no es necesario y se puede eliminar de forma permanente. Al resultado lo llamamos ${\displaystyle {\text{minimize}}(\alpha )}$. Si ${\displaystyle \alpha }$ es el conjunto de todos los atributos, entonces ${\displaystyle {\text{minimize}}(\alpha )}$ es una llave candidata.

De hecho, podemos detectar cada llave candidata con este procedimiento, simplemente probando todas las posibles maneras de eliminar estos. Sin embargo, hay muchas más permutaciones de atributos (${\displaystyle n!}$) que subconjuntos (${\displaystyle 2^{n}}$). Es decir, muchos órdenes de atributos conducirán a la misma llave candidata. Hay una dificultad fundamental para generar algoritmos eficientes para la computación de llaves candidatas: Ciertos tipos de dependencias funcionales producen muchas llaves candidatas de forma exponencial. Considere las ${\displaystyle 2\cdot n}$ dependencias funcionales ${\displaystyle \{A_{i}\rightarrow B_{i}:i\in \{1,\dots ,n\}\}\cup \{B_{i}\rightarrow A_{i}:i\in \{1,\dots ,n\}\}}$ que producen ${\displaystyle 2^{n}}$ llaves candidatas: ${\displaystyle \{A_{1},B_{1}\}\times \dots \times \{A_{n},B_{n}\}}$.

Es decir, lo mejor que podemos esperar es un algoritmo que es eficiente con respecto al número de llaves candidatas.

El siguiente algoritmo se ejecuta en tiempo polinomial en el número de llaves candidatas y dependencias funcionales:^[1]​

 K [0]:= minimize (A); /* A es el conjunto de todos los atributos */  n:= 1;  /* Número de llaves conocidas hasta el momento */  i:= 0;  /* Llave actualmente procesada */  mientras i <n haga    para cada α → β ∈ F haga      S:= α ∪ (K [i] - β);     found:= false;      para j:= 0 hasta n-1 hacer        si K [j] ⊆ S entonces found:= true;      si not(found) entonces        K [n]: = minimize(S);        n: = n + 1; 

La idea detrás del algoritmo es que, dada una llave candidata ${\displaystyle K_{i}}$ y una dependencia funcional ${\displaystyle \alpha \rightarrow \beta }$, La aplicación inversa de la dependencia funcional produce el conjunto ${\displaystyle \alpha \cup (K_{i}\setminus \beta )}$, que también es una llave. No obstante, puede ser cubierto por otras llaves candidatas ya conocidas (el algoritmo comprueba este caso utilizando la variable "found"). Si no es así, entonces minimizar la nueva llave produce una nueva llave candidata. La idea clave es que todas las llaves candidatas pueden crearse de esta manera.