Clau candidata

En el model relacional de bases de senyes, una clau candidata (o clau candidata) d'una relació és una mínima súper clau d'eixa relació; és dir, un conjunt d'atributs tals que:

1. La relació no té dos distintes tuplas (és dir, files o registres en el llenguage de base de senyes comuna) en els mateixos valors per a estos atributs (lo que significa que el conjunt d'atributs és una súper clau).
2. No hi ha un subconjunt propi d'estos atributs per als que es complix la condició anterior (lo que significa que el conjunt és minimal).

Els atributs que la componen es diuen atributs principals. A l'inversa, un atribut que no ocorre en qualsevol clau candidata es diu un atribut no principal.

Ya que una relació conté tuplas no duplicades, el conjunt de tots els seus atributs és una súper clau si no s'utilisen valors nuls. D'això es desprén que cada relació tindrà a lo manco una clau candidata.

Les claus candidates d'una relació nos diuen totes les possibles formes en que podem identificar les seues tuplas. Com a tals, són un concepte important per al disseny d'esquemes de bases de senyes.

Eixemple

La definició de claus candidates es pot ilustrar en el següent eixemple abstracte. Considere's una variable de relació (relvar) R en atributs {A, B, C, D} que solament té els següents dos valors llegals R1 i R2:

r1

A ! B	C	D
a1	b1	c1	d1
a1	b2	c2	d1
a2	b1	c2	d1

r2

A ! B	C	D
a1	b1	c1	d1
a1	b2	c2	d1
a1	b1	c2	d2

Ací, r2 es diferencia de r1 solament en els valors d'i D de l'última tupla.

Per a r1, els següents conjunts tenen la propietat d'unicitat (és dir, no hi ha dos tuplas distintes en l'instància en els mateixos valors per als atributs del conjunt):

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

Per a r2 la propietat d'unicitat és vàlida per als següents conjunts:

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

Degut a que les súper claus d'un relvar són aquells conjunts d'atributs que tenen la propietat d'unicitat per a tots els valors llegals d'eixe relvar, i perque suponem que R1 i R2 són tots els valors llegals que R pot prendre, podem determinar el conjunt de súper claus de R prenent l'intersecció de les dos llistes:

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

Per últim tenim que seleccionar els conjunts per als quals no hi ha subconjunt apropiat en la llista, que són en este cas:

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

Estes són, de fet, les claus candidates del relvar R.

Tenim que considerar totes les relacions que podrien ser assignades a un relvar per a determinar si un cert conjunt d'atributs és una clau candidata. Per eixemple, si haguérem considerat solament r1, hauríem aplegat a la conclusió de que {A, B} és una clau candidata, lo que és incorrecte. No obstant, podríem aplegar a la conclusió a partir d'eixa relació que un cert conjunt no és una clau candidata, perque eixe conjunt no té la propietat d'unicitat (per eixemple, {A, D} per a r1). Deu tindre's en conte que l'existència d'un subconjunt propi d'un conjunt que té la propietat d'unicitat no pot en general ser utilisada com a prova de que el superconjunto no és una clau candidata. En particular, cal destacar que en el cas d'una relació buida, cada subconjunt de la partida té la propietat d'unicitat, incloent el conjunt buit.

Determinació de claus candidates

El conjunt de totes les claus candidates pot ser calculat, per eixemple, a partir del conjunt de dependències funcionals. Per a això, és necessari definir la clausura d'atributs ${\alpha }^{+}$ per a un conjunt d'atributs $\alpha$. El conjunt ${\alpha }^{+}$ conté tots els atributs que estan funcionalment implicats per $\alpha$.

És prou fàcil trobar una sola clau candidata. Escomencem en un conjunt $\alpha$ d'atributs i tractem d'eliminar successivament cada atribut. Si despuix d'eliminar un atribut la clausura permaneix igual, llavors este atribut no és necessari i es pot eliminar de forma permanent. Al resultat ho cridem $\text{minimize}(\alpha )$. Si $\alpha$ és el conjunt de tots els atributs, llavors $\text{minimize}(\alpha )$ és una clau candidata.

De fet, podem detectar cada clau candidata en este procediment, simplement provant totes les possibles maneres d'eliminar estos. No obstant, hi ha moltes més permutació d'atributs ($n!$) que subconjunts ($2^n$). És dir, molts órdens d'atributs conduiran a la mateixa clau candidata. Hi ha una dificultat fonamental per a generar algoritmes eficients per a la computació de claus candidates: Certs tipos de dependències funcionals produïxen moltes claus candidates de forma exponencial. Considere les $2\cdot n$ dependències funcionals $\{A_i\to B_i:i\in \{1,\dots ,n\}\}\cup \{B_i\to A_i:i\in \{1,\dots ,n\}\}$ que produïxen $2^n$ claus candidates: $\{A_1,B_1\}\times \dots \times \{A_n,B_n\}$.

És dir, lo millor que podem esperar és un algoritme que és eficient sobre el número de claus candidates.

El següent algoritme s'eixecuta en temps polinomial en el número de claus candidates i dependències funcionals:

 K [0]:= minimize (A); /* A és el conjunt de tots els atributs */
 n:= 1;  /* Número de claus conegudes fins al moment */
 i:= 0;  /* Clau actualment processada */
 mentres i <n faça
   per a cada α → β ∈ F faça
     S:= α ∪ (K [i] - β);
    found:= false;
     per a j:= 0 fins a n-1 fer
       si K [j] ⊆ S llavors found:= true;
     si not(found) llavors
       K [n]: = minimize(S);
       n: = n + 1;

L'idea darrere de l'algoritme és que, donada una clau candidata $K_i$ i una dependència funcional $\alpha \to \beta$, L'aplicació inversa de la dependència funcional produïx el conjunt $\alpha \cup (K_i\setminus \beta )$, que també és una clau. No obstant, pot ser cobert per atres claus candidates ya conegudes (l'algoritme comprova este cas utilisant la variable "found"). Si no és aixina, llavors minimisar la nova clau produïx una nova clau candidata. L'idea clau és que totes les claus candidates poden crear-se d'esta manera.