What Is a Candidate Key?

If the value of an attribute or attribute group in a relationship can uniquely identify a tuple, and its true subset cannot uniquely identify a tuple, this attribute or attribute group is called a candidate code.

Candidate code

Right!

If the value of an attribute or attribute group in a relationship uniquely identifies an

If the value of an attribute or attribute group in the relationship can uniquely identify one

Candidate code steps

Step 1. Find the minimum functional dependency set F of the relational pattern R <U, F>

Step 2. Calculate UL, UR, and UB respectively according to the definitions above (UL represents the set of attributes that appear only on the left side of each dependency expression in the function dependency set; UR means that the attributes appear only on the right side of each dependency expression in the function dependency set A collection of attributes; also note UB = U-UL-UR)

Step 3. If UL , calculate the closure of UL. If UL + = U, then UL is the only candidate code for R, and the algorithm ends. If UL + U, go to step 4. If UL = , go to 5 steps.

Step 4. Combine the UL with the attributes in the UB in turn, and use the definition 4 above to determine whether the combined attribute is a candidate code. After finding all candidate codes, the algorithm ends.

In step 5, the attributes and attribute combinations in UB are judged in order using the above definition 4; after all candidate codes are found, the algorithm ends.

In short: take the minimum dependency set and calculate the UL closure. If the UL closure contains all attributes, then UL is the only candidate code. If it does not, then combine it with the UB attributes in order to find whether the closure contains all attributes.

(When UL is empty, directly take UB and then combine to find the closure)

Candidate code multiple attribute dependency set candidate code solution

Input: Relational pattern R and its functional dependency set F.

Output: all candidate codes of R.

Specific steps:

1) Divide all attributes of R into L, R, N, and LR, and let X represent L, N, and Y represent LR.

2) Find X +. If X + contains all the attributes of R, then X is the only candidate code for R, go to ; otherwise, go to .

3) Take an attribute A in Y and find (XA) +, if it contains all the attributes of R, go to ; otherwise, repeat the process by changing one attribute until you have tried all the attributes in Y.

4) If all candidate codes have been found, the switch ; otherwise, turn to two in Y, three ...... find their properties closures, closure until it contains all of the attributes R.

5) Stop and output the result.

In short: take an X attribute (X is L, N class) for the closure, if it contains all R attributes, it is a code, otherwise take an LR class Y attribute A, find the XA closure, and do not include the full R attributes. Then swap A, including all attributes of R and ending when all codes are found, otherwise take 2, 3 in turn.

Candidate Code Recursion

Specific method: Given a relational pattern R and the corresponding function dependency set F, after preliminary judgment, there are no attributes belonging to L in the function dependency set, and all attributes belong to the LR class. At this time, you can find out in the function dependency set As the determining factor, the attribute that appears most frequently in the left part, such as X, finds the X closure. If its closure includes all attributes in R, then X is a candidate code for R; and then find the attributes that can determine X, For example, Y X, find the closure of Y. If Y's closure contains all the attributes in R, then Y is a candidate code for R, and it will be searched in turn until all the functional dependencies are found out; After finding it, find the combination of the two attributes. Note: At this time, the original candidate codes should not be combined again (the general solution method can be used).

If a relational pattern R (A, B, C, D, E) is set, and the function dependency set F = {A BC, CD E, B D, E A}, find all candidates for R code.

According to the above method, the specific solution steps are as follows: after singularizing the right part of F, F = {A B, A C, CD E, B D, E A}; according to the judgment, A is the determining factor on the left The highest frequency of occurrence, find A + = ABCDE, and then E A, find E + = ABCDE and CD E, and (CD) + = ABCDE. You can get the attributes A, E, and CD as candidate codes; remove A and E In addition to CD, according to the general solution method to obtain the closure of the combination of two attributes, we can get (BC) + = ABCDE. Finally, we can calculate the candidate code of R: A, E, CD, BC.

In short: without L, all attributes belong to LR. Take the attribute X that appears most frequently on the left and find X +. If all attributes in R are included, X is a candidate code. Find the property Y that can determine X, find Y +, and say that Y + contains all the properties in R, then Y is the same. Find a combination of two after each single, and so on. (Candidate code does not participate in combination)

Candidate code algorithm

It is known that the attribute set of the relation pattern R (U) is the functional dependency set F of A1A2 ... An and R, and find a candidate code for R (U).

algorithm:

KEY (X, F)

K = A1A2 ... An;

For i = 1 to n

{Find the attribute closure of K-Ai relative to F (K-Ai) F +;

if (K-Ai) F + = U then K = K-Ai

else then K = K;}

return K;

When using this algorithm to find R (U) candidate codes, only one can be found, and it is not guaranteed to find all the codes. But the same method can be used to adjust the deletion order of attributes and solve all candidate codes.

In this way, let the relationship R (ABCD) and the functional dependency set established on R be F, F = {AB C, C D, D A}, and find all codes of R.

The specific steps according to the above algorithm are as follows:

Let K = {ABCD}, when K = BCD, since KF + = ABCD, A can be deleted according to the algorithm;

K = CD, because KF + = ACD and because KF + is not equal to ABCD, according to the algorithm, B cannot be deleted;

K = BD, because KF + = ABCD and KF + = AB-CD, it can be deleted according to algorithm C;

K = B, because KF + = B and because KF + is not equal to ABCD,

Therefore, according to the algorithm, D cannot be deleted; finally, KEY = BD can be obtained, and the deletion order of the attributes can be adjusted in the same way, and another candidate code AB can be obtained, so the code of R can be BD and AB.

The general solution algorithm is applicable when it is judged that all the attributes belong to the left and right parts of the function dependency and the latter several algorithms are not suitable.

In short: algorithm overview-there are N attributes, looping from 1 to N. K is initially all attributes, and the Nth attribute is subtracted each time. If KF + includes all attributes, the value of K is re-attached to the value of K minus the Nth attribute; otherwise, K is still the value after the last loop. Value. (The algorithm is suitable for all attributes that are of LR type and other algorithms are not suitable. In the actual calculation, the order of deletion must be changed after repeated calculations.)

Method for quickly finding candidate codes from candidate codes

First, for a given relational pattern R (U) and functional dependency set F, its attributes can be divided into 4 categories:

Class L functions that appear only in F depend on the properties of the left part.

Class R, functions that appear only in F depend on the properties on the right.

In the N class, the function in F depends on attributes that do not appear on the left and right.

For the LR class, the functions in F depend on attributes that appear in both the left and right parts.

Candidate codes are solved according to the following theorems and inferences.

Theorem 1: For a given relational pattern R and its functional dependency set F, if X (XR) is a class L attribute, then X must be a member of any candidate code of R.

Corollary 1: For a given relational pattern R and its functional dependency set F, if X (XR) is an L-type attribute and X + contains all the attributes of R, then X must be the only candidate code for R.

Theorem 2: For a given relational pattern R and its functional dependency set F, if X (XR) is an R-type attribute, then X is not in any candidate code.

Theorem 3: There is a relational pattern R and its functional dependency set F. If X is an N-type attribute of R, then X must be included in any candidate code of R.

Corollary 2: For a given relational pattern R and its functional dependency set F, if X is an attribute set consisting of N and L classes of R, and X + contains all the attributes of R, then X is the only candidate code for R.

Example: If a relational pattern R (U) is set, its functional dependency set is F, where:

U = {A, B, C, D, E}, F = {A C, C A, B AC, D AC}

Find the candidate code of R.

Solution: According to the function dependency, we can get:

Attributes B and D are L and E are N. Therefore, attributes B, D, and E must be members of candidate codes, and the closure of these three attributes: B + = ABC, (BD) + = ABCD, (BDE) + = ABCDE, according to inference 2, BDE is the only candidate code for R. So the candidate code of R is BDE.

If the attribute E in the relation pattern R (U) in the example problem is removed, and then the candidate code of R is obtained, the unique candidate code of BD as R can be obtained according to inference 1.

The fast solution method is suitable for determining whether an attribute belongs to L, N, or one of them. If there are L-type and N-type attributes, the candidate code is very fast.

In short: L, R, N, LR classes. According to the theorem, the L and N categories must be one of the candidate codes. If L + contains all R, then L is the only candidate. Class R is not in any candidate code. L + N type and (L + N) + contains all R, then L + N is the only candidate. (Suitable when there is at least one of L and N types.)

Candidate code graph theory judgment method

On the left is a graph theory judgment method for candidate code members of a single attribute functional dependency set.

Algorithm 2: Single-attribute dependency set graph theory solution.

Input: The single-attribute function dependency set F of the relation pattern R, R.

Output: all candidate codes of R.

step:

Find the minimum functional dependency set of F;

Constructor dependency graph FDG;

Find the key attribute set X from the figure (X can be empty);

Check if there is an independent loop in G. If not, output X is the only candidate code for R, go to 6); if there is, go to 5);

Take the attributes corresponding to a node from each independent circuit and combine them into a candidate code with X, and repeat this process to take all possible combinations, that is, all candidate codes for R;

End.

If a relational pattern R (U) is known, its functional dependency set is F, where:

R = {A, B, C, D, E, F}, F = {A B, C D, D E, E F, F C}, find all candidate codes of R.

According to the algorithm, the specific steps are as follows:

Find the minimum function dependency set Fm, Fm = {A B, C D, D E, E F, F C};

Constructor dependency graph.

The key attributes are: A

It can be seen in Figure 1 that there is an independent loop CDFE, so M = 4, so there are 4 candidate codes in total, and each candidate code has N = 1 + 1 = 2 attributes.

Finally, the candidate codes of R are: AC, AD, AE, AF.

This method is suitable for the case where the left part is a single attribute function dependent candidate code, and if the fast solution method is not used to quickly get the candidate code.