- 2020-07-29 06:36
*views 3*- Algorithm design and analysis
- Candidate code solving
- database
- Data dependence
- Pattern decomposition

A set of basic methods for solving candidate codes

One , Specific steps of basic algorithm for solving candidate codes .

The first 1 step , Relationship model R < U , F > Minimum functional dependency set of F

The first 2 step , As defined above , Calculated separately UL ,UR , UB （UL Represents a collection of properties that appear only to the left of each dependency in a functional dependency set ; UR Represents a collection of properties that appear only to the right of each dependency in a functional dependency set ; Another note UB = U - UL - UR ）

The first 3 step , if UL ≠Φ, calculation UL Closure of , if UL+ = U , be UL by R The unique candidate code of , End of algorithm . if UL+ ≠U , Transfer to 4 step . if UL = Φ, Transfer to 5 step .

The first 4 step , take UL And in turn UB Attribute combination in , Using the above definition 4 Determine whether the combination attribute is a candidate code ; After finding all the candidate codes , End of algorithm .

The first 5 step , Yes UB Attributes and combinations of attributes in the 4 Judge in turn ; After finding all the candidate codes , End of algorithm .

In short ： Minimum dependency set , calculation UL closure , If UL Closure contains all attributes , be UL Is the only candidate code , If not included , Then, in turn, the UB After the combination of attributes, we can find whether the closure contains all attributes .

（UL Empty time , Take directly UB Find closure by combination in turn ）

Two , Candidate code solving method for multiple attribute dependency sets

input : Relational model R And its functional dependency set F.

output :R All candidate codes for .

Specific steps :

1) hold R All attributes of are divided into L,R,N and LR Four categories , And order X representative L,N class ,Y representative LR class .

2) seek X+, If X+ Contains R All properties of , be X by R Unique candidate code of , turn (5); otherwise , turn (3).

3) stay Y Take one of the properties A, seek (XA)+, If it contains R All properties of , Then turn (4); otherwise , This process is repeated by swapping an attribute , Until you've tried everything Y Properties in .

4) If all the candidate codes have been found , Then turn (5); Otherwise, in the Y Two in turn , Three …… Find their attribute closures , Until it's closed R All properties of .

5) stop it , Output results .

In short ： Take one X attribute （X by L,N class ） Seeking closure , If included R All attributes are codes , Otherwise, take one LR Class Y attribute A, seek XA closure , Not included R All attributes are exchanged A, contain R All attributes and all codes are found , Otherwise, take it in turn 2,3 individual .

Three , Sequential recurrence method

Specific methods : Give a relational pattern R And the corresponding function dependency set F, After preliminary judgment , Does not belong to in the function dependency set L Properties of , All properties belong to LR Class , At this time, we can find the most frequent attribute in the left part of the function dependency set , as X, seek X closure , If it contains R All properties in , be X by R A candidate code for ; Be sure to find out X Properties of , as Y→X, seek Y Closure of , if Y The closure of contains R All properties in , be Y by R A candidate code for , Look down in turn , Until all the functional dependencies are found ; After finding a single attribute, find the combination of two attributes , be careful : At this time, the original candidate codes should not be combined ( The general solution method can be used ).

If there is a relationship model R(A,B,C,D,E), The set of functional dependencies on it F={A→BC,CD→E,B→D,E→A}, reach R All candidate codes for .

According to the above method , The specific solving steps are as follows : hold F After simplification of the right part F={ A→B,A→C,CD→E,B→D,E→A }; According to judgment ,A As a determining factor, it appears most frequently in the left , seek A+=ABCDE, There are E→A, seek E+=ABCDE and CD→E, seek (CD)+=ABCDE, You can get the property A,E,CD Is the candidate code ; except A,E,CD External , Finding the closure of two attribute combination by general solving method , You can get it (BC)+=ABCDE, Finally, it can be calculated R The candidate code of is :A,E,CD,BC.

In short ： No, L, All attributes belong to LR, Take the most frequent attribute on the left X, seek X+, If included R All properties in , be X Is the candidate code . Find a way to decide X Properties of Y, seek Y+, say Y+ contain R All properties in , be Y So is it . After a single, find a couple to combine , And so on .（ Candidate code does not participate in the combination ）

Four , A general algorithm for finding candidate codes

Known relational patterns R(U) The property set is A1A2...An and R Function dependency set of F, seek R(U) A candidate code for .

algorithm ：

KEY(X,F)

K=A1A2…An;

For i=1 to n

{ seek K-Ai be relative to F Property closure of (K-Ai)F+;

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

else then K=K; }

return K;

Using this algorithm R(U) When the candidate code of , Only one can be found , There is no guarantee that all codes will be found . But we can use the same method to adjust the deletion order of attributes to solve all candidate codes .

This is the question of the relationship R(ABCD) and R The set of functional dependencies on is F,F={AB→C,C→D,D→A}, seek R All codes of .

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

set up K={ABCD}, When K=BCD Time , because KF+=ABCD, So it can be deleted according to the algorithm A;

K=CD, because KF+=ACD Because KF+ Not equal to ABCD, So according to the algorithm ,B Cannot be deleted ;

K=BD, because KF+=ABCD And because KF+=AB-CD, So according to the algorithm C Can be deleted ;

K=B, because KF+=B Because KF+ Not equal to ABCD,

So according to the algorithm ,D Cannot be deleted ; Finally, we can find out KEY=BD, Adjust the deletion order of attributes in the same way , Another candidate code can be obtained AB, So in the end, we can get R The code is BD and AB.

The general solution algorithm is suitable for the case that all the attributes are in the left and right parts of the function dependency, and the following algorithms are not suitable .

In short ： Overview of algorithms —— Yes N Properties , from 1 reach N loop .K Initially all attributes , Subtract the first step from each cycle N Properties , If KF+ Include all attributes , be K The value of the K Minus para N Value after attributes ; otherwise K Is still the value since the last cycle .（ The algorithm is suitable for all attributes LR Class and other algorithms are not appropriate , The actual calculation should be repeated after changing the deletion order ）

Five , A fast method for finding candidate codes

First, for a given R(U) And functional dependency sets F, Its properties can be divided into 4 class :

* L class , Only appears in F The function depends on the property on the left .

* R class , Only appears in F The function depends on the right property of .

* N class , stay F The function of depends on properties that are not present on the left and right sides of .

* LR class , stay F The function of depends on the properties that appear in both the left and right parts .

The candidate codes are solved according to the following theorems and corollaries .

* theorem 1: For a given relational schema R And its functional dependency set F, if X(X∈R) yes L Class properties , be X Must be R Member of any candidate code of .

* inference 1: For a given relational schema R And its functional dependency set F, if X(X∈R) yes L Class properties , And X+ Contains R All properties of , be X Must be R Unique candidate code of .

* theorem 2: For a given relational schema R And its functional dependency set F, if X(X∈R) yes R Class properties , be X Not in any candidate code .

* theorem 3: There is a relational model R And its functional dependency set F, If X yes R Of N Class properties , be X Must be included in R In any candidate code of .

* inference 2: For a given relational schema R And its functional dependency set F, If X yes R Of N Class and L The set of properties made up of classes , And X+ Contains R Has attributes , be X yes R Unique candidate code of .

example ：

If there is a relationship model R(U), Its function dependency set is F, among :U={A,B,C,D,E}, F={A→C,C→A,B→AC,D→AC} seek R Candidate code of .

solution :

According to the functional dependence, the :

attribute B,D by L class ,E by N class , So attribute B,D,E Must be a candidate code ,

And the closure of these three properties :B+=ABC,(BD)+=ABCD,(BDE)+=ABCDE, According to inference 2 Available BDE yes R Unique candidate code of .

therefore R The candidate code of is BDE.

If you put the relation pattern in the example R(U) Properties in E Remove , Then ask again R We can infer from the candidate code 1 obtain BD by R Unique candidate code of .

The fast solution method is suitable for judging whether the attribute belongs to L class ,N Class or one of them . If so L Class and N Properties of the class , The speed of solving candidate codes is very fast .

In short ：

L,R,N,LR class . According to the theorem ,L,N Class must be one of the candidate codes , If L+ Include all R, be L As the only candidate .R Class is not in any candidate code .

L+N Class and （L+N）+ Include all R, be L+N As the only candidate .（ Suitable for L,N Class at least one case .）

Example ：

There is a relational model R(A,B,C,D,E), Its function dependency set F={A→BC,CD→E,B→D,E→A}, seek R All candidate codes for .

solution ：

(1)Fm={A→B, A→C,CD→E,B→D,E→A}

(2)A,B,C,D,E Five attributes in F The right and left sides of each function dependency in the , So the candidate code may contain A,B,C,D,E.

(3)A+=ABCDE, Namely A→U, therefore A It's a candidate code B+,C+,D+→U, therefore B,C,D Not a candidate code

E+=ABCDE, Namely E→U, So it is E It's a candidate code

(4) except A,E Two candidate codes , stay B,C,D Find candidate codes for two attributes in (BC)+=ABCDE, Namely BC→U, therefore BC It's a candidate code

(BD)+=BD, Namely BC→U, therefore BD Not a candidate code (CD)+=ABCDE, Namely CD→U, therefore CD It's a candidate code

The candidate codes are ：A,E,BC,CD

Six , Graph theory method for determining candidate code members of functional dependency sets with single attribute on the left

algorithm 2: The solution of single attribute dependent set graph theory .

input : Relational model R,R Single attribute functional dependency set of F.

output :R All candidate codes for .

step :

1, seek F Minimum functional dependency set of ;

2, Constructor dependency graph FDG;

3, Find the key attribute set from the graph X(X Can be empty );

4, see G Is there an independent circuit in , If not, output X mean R Unique candidate code of , turn 6); If so, turn to 5);

5, From each independent loop, the corresponding attribute and X Combined into a candidate code , And repeat the process , Take all possible combinations , mean R All candidate codes of ;

6, end .

If a relational pattern is known R(U), Its function dependency set is F, among ：

R={A,B,C,D,E,F}, F={A→B,C→D,D→E,E→F,F→C}, seek R All candidate codes for .

According to the algorithm , The specific steps are as follows ：

Finding the minimal set of functional dependencies Fm,Fm={ A→B,C→D,D→E,E→F,F→C };

Constructor dependency graph .

The key attributes are :A

In the figure 1 You can see that there is a separate circuit in CDFE, therefore M=4, So it's shared 4 Candidate codes , Each candidate code has N=1+1=2 Properties .

In the end R The candidate code of is :AC,AD,AE,AF.

This method is suitable for solving candidate codes with single attribute on the left , Moreover, if the fast solution method is used, the candidate codes can not be solved quickly .

example ： There is a relational model R(O,B,I,S,Q,D), Its function dependency set F={S→D,D→S,I→B,B→I ,B→O, O→B}, seek R All candidate codes for .

solution ：

(1)FM=F= {S→D,D→S,I→B,B→I ,B→O, O→B}

(2) Constructor dependency graph , As shown in the figure on the right ：

(3) Key attribute set ：{Q}

(4) share 2 Circuits ,SD,IBO, So the number of candidate codes is 2*3=6, The number of attributes for each candidate code is 1+2=3.

therefore R Is not unique , All candidate codes are ：QSI,QDI,QSB,QDB,QSO,QDO

example ： There is a relational model R(X,Y,Z,W), Its function dependency set F={W→Y,Y→W,X→WY,Z→WY ,XZ→W}, seek R All candidate codes for .

solution ：

(1)FM= {W→Y,Y→W,X→Y,Z→W}

(2) Constructor dependency graph , As shown in the figure on the right ：

(3) Key attribute set ：{X,Z}

(4) No independent circuit

therefore ,R There are only unique candidates XZ

Technology

- Java393 articles
- Python205 articles
- Linux112 articles
- Vue98 articles
- MySQL85 articles
- SpringBoot70 articles
- javascript65 articles
- Spring63 articles
- more...

Daily Recommendation

views 2

©2019-2020 Toolsou All rights reserved,

Non preemptive static priority scheduling algorithm for operating system （C language ）Go Language learning notes （GUI programming ）XCTF Attack and defense world web Advanced practice _ 2_lottery What's the difference between computer major and training background ?python realization vlookup_ Dry goods I ： Why python It's inside vlookup Bubble sort primary springboot2 Separation of front and rear platforms ,token Put in header Pit for verification Python Case conversion of letters （ Two methods ）javascript event （ Detailed explanation of zero basis ）Unity2019 UIElement note （ ten ） Simple exercise 2