Clave de candidato

Conjunto de columnas en una base de datos relacional

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 de una clave candidata se denominan atributos principales , ^[3] y una columna que no aparece en ninguna clave candidata se denomina atributo no principal .

Cada relación sin valores NULL tendrá al menos una clave candidata: dado que 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 esta será mínimo.

Existe una dependencia funcional de la clave candidata a 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 .

Ejemplo

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 tiene únicamente los dos valores legales siguientes r1 y r2 :

Aquí r2 difiere de r1 solo 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 legales de ese relvar y debido a que asumimos que r1 y r2 son todos los valores legales 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 cuales no existe un subconjunto propio en la lista, que en este caso son:

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

Éstas son de hecho las claves candidatas de relvar R.

Tenemos que considerar todas las relaciones que podrían asignarse a una variable rel para determinar si un determinado conjunto de atributos es una clave candidata. Por ejemplo, si hubiéramos considerado solo r1 , entonces habríamos concluido que {A,B} es una clave candidata, lo cual es incorrecto. Sin embargo, podríamos concluir a partir de dicha relación que un determinado conjunto no es una clave candidata, porque ese conjunto no tiene la propiedad de unicidad (ejemplo {A,D} para r1 ). Nótese que la existencia de un subconjunto propio de un conjunto que tiene la propiedad de unicidad no puede, en general, usarse como evidencia de que el superconjunto no es una clave candidata. En particular, nótese que en el caso de una relación vacía, cada subconjunto del encabezado tiene la propiedad de unicidad, incluido el conjunto vacío.

Determinación de claves candidatas

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 de atributo para un conjunto de atributos . El conjunto contiene todos los atributos que están implicados funcionalmente por . ${\displaystyle \alpha ^{+}}$ ${\displaystyle \alpha }$ ${\displaystyle \alpha ^{+}}$ ${\displaystyle \alpha }$

Es bastante sencillo encontrar una clave candidata única. Empezamos con un conjunto 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 de forma permanente. Llamamos al resultado . Si es el conjunto de todos los atributos, entonces es una clave candidata. ${\displaystyle \alpha }$ ${\displaystyle {\text{minimize}}(\alpha )}$ ${\displaystyle \alpha }$ ${\displaystyle {\text{minimize}}(\alpha )}$

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 ( ) que de subconjuntos ( ). Es decir, muchos órdenes de atributos conducirán a la misma clave candidata. ${\displaystyle n!}$ ${\displaystyle 2^{n}}$

Existe una dificultad fundamental para los algoritmos eficientes de cálculo de claves candidatas: ciertos conjuntos de dependencias funcionales dan lugar a una cantidad exponencial de claves candidatas. Consideremos las dependencias funcionales que dan lugar a claves candidatas: . Es decir, lo mejor que podemos esperar es un algoritmo que sea eficiente con respecto a la cantidad de claves candidatas. ${\displaystyle 2\cdot n}$ ${\displaystyle \{A_{i}\rightarrow B_{i}:i\in \{1,\dots ,n\}\}\cup \{B_{i}\rightarrow A_{i}:i\in \{1,\dots ,n\}\}}$ ${\displaystyle 2^{n}}$ ${\displaystyle \{A_{1},B_{1}\}\times \dots \times \{A_{n},B_{n}\}}$

El siguiente algoritmo en realidad se ejecuta en tiempo polinomial en el número de claves candidatas y dependencias funcionales: ^[4]

función find_candidate_keys(A, F) /* A es el conjunto de todos los atributos y F es el conjunto de dependencias funcionales */ K[0] := minimizar(A); n := 1; /* Número de claves conocidas hasta el momento */ i := 0; /* Clave procesada actualmente */ mientras i < n hacer  para cada α → β ∈ F hacer /* Construye una nueva clave potencial a partir de la clave conocida previamente y la FD actual */ S := α ∪ (K[i] − β); /* Busca si la nueva clave potencial es parte de las claves ya conocidas */ encontrado := falso; para j := 0 a n-1 hacer  si K[j] ⊆ S entonces encontrado := verdadero; /* Si no, agréguelo */ Si  no se encuentra entonces K[n] := minimizar(S); es:= n+1; yo := yo + 1 devolver K

La idea detrás del algoritmo es que, dada una clave candidata y una dependencia funcional , la aplicación inversa de la dependencia funcional produce el conjunto , que también es una clave. Sin embargo, puede estar cubierto por otras claves candidatas ya conocidas. (El algoritmo verifica este caso utilizando la variable 'found'). Si no es así, entonces al minimizar la nueva clave se obtiene una nueva clave candidata. La idea clave es que todas las claves candidatas se pueden crear de esta manera. ${\displaystyle K_{i}}$ ${\displaystyle \alpha \rightarrow \beta }$ ${\displaystyle \alpha \cup (K_{i}\setminus \beta )}$

Véase también

• Clave alternativa , una clave que no se selecciona como clave principal entre las claves candidatas para una relación
• Clave compuesta
• Normalización de bases de datos
• Clave primaria
• Base de datos relacional
• Superclave
• El implicante primo es la noción correspondiente de una clave candidata en la lógica booleana.

Referencias

1. Date, Christopher (2015). "Codd's First Relational Papers: A Critical Analysis" (PDF) . warwick.ac.uk . Consultado el 4 de enero de 2020 . Nótese que el extracto permite que una "relación" tenga cualquier número de claves primarias y, además, que dichas claves puedan ser "redundantes" (mejor: reducibles ). En otras palabras, lo que el artículo llama una clave primaria es lo que más tarde (y mejor) se conocería como una superclave , y lo que el artículo llama una clave primaria no redundante (mejor: irreducible ) es lo que más tarde se conocería como una clave candidata o (mejor) simplemente una clave .
2. "base de datos - ¿Puede una relación tener claves candidatas con diferentes longitudes?". Desbordamiento de pila . Consultado el 23 de marzo de 2023 .
3. Saiedian, H. (1996-02-01). "Un algoritmo eficiente para calcular las claves candidatas de un esquema de base de datos relacional". The Computer Journal . 39 (2): 124–132. doi :10.1093/comjnl/39.2.124. ISSN  0010-4620.
4. L. Lucchesi, Cláudio; Osborn, Sylvia L. (octubre de 1978). "Claves candidatas para relaciones". Revista de Ciencias de la Computación y de Sistemas . 17 (2): 270–279. doi :10.1016/0022-0000(78)90009-0.

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

Enlaces externos

• 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 el RDBMS (sistema de gestión de bases de datos relacionales).