Clave del candidato

Una clave candidata , o simplemente una clave , de una base de datos relacional es cualquier conjunto de columnas que tienen una combinación única de valores en cada fila, con la restricción adicional de que eliminar cualquier columna podría producir combinaciones duplicadas de valores.

Una clave candidata es una superclave mínima , ^{[ 1 ]} es decir, una superclave que no contiene una más pequeña. Por lo tanto, una relación puede tener múltiples claves candidatas, cada una con un número diferente de atributos. ^{[ 2 ]}

Las claves candidatas específicas a veces se denominan claves primarias , claves secundarias o claves alternativas . Las columnas en una clave candidata se denominan atributos primarios , ^{[ 3 ]} y una columna que no aparece en ninguna clave candidata se denomina atributo no primario .

Cada relación sin valores NULL tendrá al menos una clave candidata: como no puede haber filas duplicadas, el conjunto de todas las columnas es una superclave, y si esta no es mínima, algún subconjunto de ella será mínimo.

Existe una dependencia funcional desde la clave candidata hacia todos los atributos de la relación.

Las superclaves de una relación son todas las formas posibles en que podemos identificar una fila. Las claves candidatas son los subconjuntos mínimos de cada superclave y, como tales, son un concepto importante para el diseño del esquema de la base de datos .

La definición de claves candidatas se puede ilustrar con el siguiente ejemplo (abstracto). Consideremos una variable de relación ( relvar ) R con atributos ( A , B , C , D ) que solo tiene los siguientes dos valores válidos r1 y r2 :

Aquí, r2 se diferencia de r1 únicamente en los valores 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 de atributo en el 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 se cumple 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}

Dado que las superclaves de un relvar son aquellos conjuntos de atributos que tienen la propiedad de unicidad para todos los valores válidos de ese relvar y debido a que asumimos que r1 y r2 son todos los valores válidos que R puede tomar, podemos determinar el conjunto de superclaves 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}

Finalmente, necesitamos seleccionar aquellos conjuntos para los que no existe un subconjunto propio en la lista, que en este caso son:

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

Estas son, de hecho, las claves candidatas de relvar R.

Debemos considerar todas las relaciones que podrían asignarse a una relación para determinar si un conjunto de atributos es una clave candidata. Por ejemplo, si solo hubiéramos considerado r1 , habríamos concluido que {A,B} es una clave candidata, lo cual es incorrecto. Sin embargo, a partir de dicha relación, podríamos concluir que un conjunto no es una clave candidata, ya que ese conjunto no posee la propiedad de unicidad (ejemplo: {A,D} para r1 ). Cabe señalar que la existencia de un subconjunto propio de un conjunto que posee la propiedad de unicidad no puede utilizarse, en general, como prueba de que el superconjunto no es una clave candidata. En particular, en el caso de una relación vacía, todo subconjunto del encabezado posee la propiedad de unicidad, incluido el conjunto vacío.

El conjunto de todas las claves candidatas se puede calcular, por ejemplo, a partir del conjunto de dependencias funcionales . Para ello, necesitamos definir el cierre del atributo.${\displaystyle \alpha ^{+}}$para un conjunto de atributos${\displaystyle \alpha }$. El conjunto${\displaystyle \alpha ^{+}}$contiene todos los atributos que están funcionalmente implícitos por${\displaystyle \alpha }$.

Es bastante sencillo encontrar una única clave candidata. Comenzamos con un conjunto${\displaystyle \alpha }$de atributos e intentamos eliminar sucesivamente cada atributo. Si después de eliminar un atributo el cierre del atributo permanece igual, entonces este atributo no es necesario y podemos eliminarlo permanentemente. Llamamos resultado${\displaystyle {\text{minimizar}}(\alpha )}$. Si${\displaystyle \alpha }$es el conjunto de todos los atributos, entonces${\displaystyle {\text{minimizar}}(\alpha )}$es una clave candidata.

En realidad podemos detectar cada clave candidata con este procedimiento simplemente probando cada orden posible de eliminación de atributos. Sin embargo, hay muchas más permutaciones de atributos (${\displaystyle n!}$) que subconjuntos (${\displaystyle 2^{n}}$). Es decir, muchos órdenes de atributos darán como resultado la misma clave candidata.

Existe una dificultad fundamental para los algoritmos eficientes para el cálculo de claves candidatas: ciertos conjuntos de dependencias funcionales conducen a una cantidad exponencial de claves candidatas. Consideremos el${\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\}\}}$ lo cual produce${\displaystyle 2^{n}}$Claves candidatas: ${\displaystyle \{A_{1},B_{1}\}\times \dots \times \{A_{n},B_{n}\}}$Es decir, lo mejor que podemos esperar es un algoritmo que sea eficiente con respecto al número de claves candidatas.

The following algorithm actually runs in polynomial time in the number of candidate keys and functional dependencies:^[4]

function find_candidate_keys(A, F) /* A is the set of all attributes and F is the set of functional dependencies */ K[0] := minimize(A); n := 1; /* Number of Keys known so far */ i := 0; /* Currently processed key */ while i < n dofor each α → β ∈ F do /* Build a new potential key from the previous known key and the current FD */ S := α ∪ (K[i] − β); /* Search whether the new potential key is part of the already known keys */ found := false; for j := 0 to n-1 doif K[j] ⊆ S then found := true; /* If not, add it */ ifnot found then K[n] := minimize(S); n := n + 1; i := i + 1 return K

The idea behind the algorithm is that given a candidate key ${\displaystyle K_{i}}$ and a functional dependency ${\displaystyle \alpha \rightarrow \beta }$, the reverse application of the functional dependency yields the set ${\displaystyle \alpha \cup (K_{i}\setminus \beta )}$, which is a key, too. It may however be covered by other already known candidate keys. (The algorithm checks this case using the 'found' variable.) If not, then minimizing the new key yields a new candidate key. The key insight is that all candidate keys can be created this way.

• Alternate key, a key that is not selected as a primary key among candidate keys for a relationship
• Compound key
• Database normalization
• Primary key
• Relational database
• Superkey
• Prime implicant is the corresponding notion of a candidate key in boolean logic

• Date, Christopher (2003). "5: Integridad". Introducción a los sistemas de bases de datos . Addison-Wesley. pp. 268–276 . ISBN  978-0-321-18956-1.

• Sistemas de gestión de bases de datos relacionales - Diseño de bases de datos - Términos de referencia - Claves : Una descripción general de los diferentes tipos de claves en los SGBDR (Sistemas de gestión de bases de datos relacionales).