Logical implication of functional dependence

The logical implication of functional dependence （ turn ）

One 、 Logic implies
  Definition ： There's a relationship model R(U) And its functional dependency set F, If for R Any one of F The relationship between r Function dependency X→Y All set up , said F Logic implies X→Y, Or called X→Y Can be F Introduction .

 

example ： Relationship model R=(A,B,C), Functional dependency set F={A→B,B→C}, F Logic implies A→C.

Prove ： set up u,v by r Any two tuples in ：
      if A→C Don't set up , Then there are u[A]=v[A], and u[C]≠v[C]
      and A→B, B→C, know
      u[A]=v[A], u[B]=v[B], u[C]=v[C],
      I.e u[A]=v[A] be u[C]=v[C], Contradict assumptions .
      so F Logic implies A→C.

Satisfy F All tuples of a dependency set are functionally dependent X→Y（X→Y Do not belong to F Set ）, said F Logic implies X→Y
（X→Y from F All dependencies in the dependency set are inferred ）

 

Two 、Armstrong axiom

 1、 Theorem ： if U For the relationship model R Complete set of properties ,F by U A set of functional dependencies on , set up X、Y、Z、W Are all R Subset , Yes R(U,F) Yes ：

        F1( reflexivity )： if X≥Y( surface X contain Y）, be X→Y by F What it implies ;(F1':X→X)
        F2( Augmentation ): if X→Y by F What it implies , be XZ→YZ by F What it implies ;(F2':XZ→Y)
        F3( Transitivity ): if X→Y,Y→Z by F What it implies , be X→Z by F What it implies ;
        F4( Pseudo increasement )： if X→Y,W≥Z( surface W contain Z） by F What it implies , be XW→YZ by F What it implies ;
        F5( Pseudo transmissibility ): if X→Y,YW→Z by F What it implies , be XW→Z by F What it implies ;

        F6( complexity ): if X→Y,X→Z by F What it implies , be X→YZ by F What it implies ;
        F7( Decomposability ): if X→Y,Z≤Y ( surface Z Included in Y） by F What it implies , be X→Z by F What it implies .

        Functional dependency inference rules F1∽F7 It's all right .

 

2、Armstrong axiom ：

Rules of reasoning F1、F2、F3 combined term Armstrong axiom ;
F4 ∽ F7 May by F1、F2、F3 Push , yes Armstrong The corollary part of an axiom .

 

3、 ... and 、 Functional dependent closures
　 Definition ： if F For the relationship model R(U) The set of functional dependencies for , We put F And all who are F The set of functional dependencies of logical implication is called F The closure of , Write it down as F+.
namely ：F+={X→Y|X→Y∈F∨“ application Armstong Axioms begin with F Any... Exported from X→Y”}

      △ F Included in F+, If F=F+, be F Is a complete set of functional dependencies .
     △ Regulations ： if X by U Subset ,X→Φ Belong to F+.

          example ：R=ABC,F={A→B,B→C}, seek F+

      Explain ： F+={A→Φ,AB→Φ,AC→Φ,ABC→Φ,B→Φ,C→Φ,
               A→A,AB→A,AC→A,ABC→A,B→B,C→C,
                A→B,AB→B,AC→B,ABC→B,B→C,
                A→C,AB→C,AC→C,ABC→C,B→BC,
                A→AB,AB→AB,AC→AB,ABC→AB,BC→Φ,
               A→AC,AB→AC,AC→AC,ABC→AC,BC→B,
               A→BC,AB→BC,AC→BC,ABC→BC,BC→C,
               A→ABC,AB→ABC,AC→ABC,ABC→A,BC→BC}

    

       example ： Known relational patterns R in
           U={A,B,C,D, E, G},
           F={AB→C, C→A, BC→D, ACD→B,D→EG, BE→C, CG→BD, CE→AG}, Judge BD→AC Whether to belong to F+
 
       Explain ： from D→EG know D→E,BD→BE             … ①
           Also know BE→C,C→A therefore BE→A, BE→AC … ②
           from ①、② know ,BD→AC, therefore BD→AC By F What it implies , namely BD→AC Belong to F+
    
       example ： Known relational patterns R in
           U={A,B,C,E, H, P, G},
           F={AC→PE, PG→A, B→CE, A→P,GA→B, GC→A, PAB→G, AE→GB, ABCP→H}, prove BG→HE Belong to F+

        Prove ： from B→CE know B→C,B→E, BG→GC         … ①
            Also know GC→A,A→P therefore BG→A, BG→ABCP … ②
            also ABCP→H, from ①、② know BG→HE, therefore BG→HE By F What it implies ,
            namely BG→HE Belong to F+
 
Four 、 Property set closure
　1、 Definition ： if F For the relationship model R(U) The set of functional dependencies for ,X yes U Subset , By Armstrong Axioms are derived from all X→Ai The resulting attribute set

 

example ： set up R=ABC,F={A→B, B→C} When X Respectively A,B,C Is to seek X+.

Explain ： When X=A when ,X+=ABC
    When X=B when ,X+=BC
    When X=C when ,X+=C

* X The attribute set represented can determine the attribute set （ Including itself ）

 

2、 Theorem ： If and only if Y Belong to X+ when ,X→Y According to Armstron Axiom consists of F export .

Prove ： set up Y=A1,A2,…,An

   ① sufficient condition ： When Y Belong to X+ when , For each i,X→Ai Can be derived from axioms .
               Then use the merge rule to get X→Y.
   ② Necessary condition ： if X→Y Can be derived from axioms , Then according to the decomposition rules ,
               X→Ai(i=1,2,…,n) establish , therefore Y Belong to X+.

 

3、 Calculation X+

(1) Algorithm basis ： if F For the relationship model R(U) The set of functional dependencies for ,X,Z,W yes U Subset , For arbitrary Z→W∈F, if X≥Z（ surface X contain Z）, be X→XW.

 

(2) Algorithm ：
a. Make X+ = X;
b. stay F Find each unmarked function dependency in turn , if “ Left attribute set ” Included in X+ , Then order X+ = X+∪“ Right attribute set ”, Set the access flag for the accessed function dependency .
c. Repeat b until X+ Until no change .

（ Shilling X+ Equal to itself , And then in F+ Find the left contained in X+ Properties of , Add the corresponding attribute on the right to X in ）

 

(3) Algorithm implementation
               Input ： Relationship model R Subset X,R Function dependency set on F.
               Output ：X About F The closure of X+

 

Algorithm pseudo language description ：

 Closure(X,F)
 {
    olds=Φ; news=X; G=F;
    while (olds!=news)
     {
       olds=news;
       for (G Each function in depends on W→Z)
        {
          if (news contain W)
            {
               news=news∪Z;
               from G Remove functional dependencies from W→Z;
             }
         }
     }
   return news;
 }

example ： Known relational patterns R in
U={A,B,C,D,E, G},
F={AB→C, C→A, BC→D, ACD→B, D→EG, BE→C, CG→BD, CE→AG},
seek (BD)+, Judge BD→AC Whether to belong to F+

Explain ：X+=BDEGCA
Conclusion ：(BD)+=ABCDEG,BD→AC May by F export , namely BD→AC Belong to F+

 

example ： Known relational patterns R in
U={A,B,C,E,H, P, G},
F={AC→PE, PG→A, B→CE, A→P, GA→B,GC→A, PAB→G, AE→GB, ABCP→H},
prove BG→HE Belong to F+

Prove ： because ,(BG)+ =ABCEHPG,
therefore BG→HE May by F export , namely BG→HE Belong to F+

 

4、 Conclusion
Determine functional dependencies X→Y Whether it can be determined by F The derived problem , It can be transformed into seeking X+ And judge Y Whether it is X+ Subset problem .
That is, the closure problem can be transformed into the attribute set problem .
Determine the dependency of a given function X→Y Whether it is contained in the set of functional dependencies F Algorithm implementation ：

 

Input ： Functional dependency set F, Function dependency X→Y
Output ： if X→Y∈F+ Output true , Otherwise, the output is false

 

Algorithm pseudo language description ：
number(F,X→Y)
{ if (Y Included in close(X,F))
      return really
  else
      return false
}

 
{Ai|i=1,2,…} be called X about F The closure of , Write it down as X+.

 

 

5、 ... and 、 Equivalence and coverage

　　 Definition ： Relationship model R<U,F> Two dependency sets on F and G, If F+=G+, said F and G It is equivalent. , Remember to do F≡G. if F≡G, said G yes F An overlay of , vice versa . Two equivalent functional dependency sets are identical in expressive ability .

6、 ... and 、 Minimum functional dependency set

　　 Definition ： If the functional dependency set F Meet the following conditions , said F Is the minimum functional dependency set or the minimum covering .

　　① F The right part of any function dependency in contains only one attribute ;
　　② F There is no such functional dependency in X→A, bring F And F-{X→A} Equivalent ;
　　③ F There is no such functional dependency in X→A,X There are real subsets Z bring F-{X→A}∪{Z→A} And F Equivalent .

　　 Algorithm ： Calculate the minimum functional dependency set .

　　 Input A set of functional dependencies

　　 Output F An equivalent minimal functional dependency set of G

　　 step ：① Use the law of decomposition , send F The right part of any function dependency in contains only one attribute ;
　　　　　② Remove redundant functional dependencies ： From the first functional dependency X→Y Start moving it from F Removing the , And then find out in the rest of the functional dependencies X The closure of X+, see X+ Does it include Y, if , Then remove it. X→Y; Otherwise, you can't remove , Do it one by one . Until no redundant functional dependencies are found ;
　　　　　③ Remove the redundant attributes on the left of each dependency . One by one, check the dependencies of non single attributes on the left of the function dependency . for example XY→A, To judge Y Redundant , with X→A Instead of XY→A Is it equivalent ？ if A (X)+, be Y Is a redundant attribute , Can be removed .

　　 give an example ： Known relational patterns R<U,F>,U={A,B,C,D,E,G},F={AB→C,D→EG,C→A,BE→C,BC→D,CG→BD,ACD→B,CE→AG}, seek F The minimum set of functional dependencies .

　　 Explain 1： Solve by algorithm , Make it meet three conditions

　　① Use decomposition rules , Turn all function dependencies into function dependencies with a single attribute on the right , have to F by ：F={AB→C,D→E,D→G,C→A,BE→C,BC→D,CG→B,CG→D,ACD→B,CE→A,CE→G}

　　② Get rid of F Redundant function dependency in

A． set up AB→C For redundant functional dependencies , Then remove it. AB→C, have to ：F1={D→E,D→G,C→A,BE→C,BC→D,CG→B,CG→D,ACD→B,CE→A,CE→G}

　　 Calculation (AB)F1+： set up X(0)=AB

　　 Calculation X(1)： scanning F1 Each function in depends on , Find... On the left AB or AB Functional dependence of subsets , Because no such functional dependency can be found . There are X(1)=X(0)=AB, Algorithm was terminated .

(AB)F1+= AB It doesn't contain C, so AB→C It's not a redundant functional dependency , Cannot from F1 Removing the .

B． set up CG→B For redundant functional dependencies , Then remove it. CG→B, have to ：F2={AB→C,D→E,D→G,C→A,BE→C,BC→D,CG→D,ACD→B,CE→A,CE→G}

　　 Calculation (CG)F2+： set up X(0)=CG

　　 Calculation X(1)： scanning F2 Each function in depends on , Find... On the left CG or CG Functional dependence of subsets , Get one C→A Function dependency . There are X(1)=X(0)∪A=CGA=ACG.

　　 Calculation X(2)： scanning F2 Each function in depends on , Find... On the left ACG or ACG Functional dependence of subsets , Get one CG→D Function dependency . There are X(2)=X(1)∪D=ACDG.

　　 Calculation X(3)： scanning F2 Each function in depends on , Find... On the left ACDG or ACDG Functional dependence of subsets , Get two ACD→B and D→E Function dependency . There are X(3)=X(2)∪BE=ABCDEG, because X(3)=U, Algorithm was terminated .

(CG)F2+=ABCDEG contain B, so CG→B Are redundant functional dependencies , from F2 Removing the .

C． set up CG→D For redundant functional dependencies , Then remove it. CG→D, have to ：F3={AB→C,D→E,D→G,C→A,BE→C,BC→D,ACD→B,CE→A,CE→G}

　　 Calculation (CG)F3+： set up X(0)=CG

　　 Calculation X(1)： scanning F3 Each function in depends on , Find... On the left CG or CG Functional dependence of subsets , Get one C→A Function dependency . There are X(1)=X(0)∪A=CGA=ACG.

　　 Calculation X(2)： scanning F3 Each function in depends on , Find... On the left ACG or ACG Functional dependence of subsets , Because no such functional dependency can be found . There are X(2)=X(1), Algorithm was terminated .(CG)F3+=ACG.

(CG)F3+=ACG It doesn't contain D, so CG→D It's not a redundant functional dependency , Cannot from F3 Removing the .

D． set up CE→A For redundant functional dependencies , Then remove it. CE→A, have to ：F4={AB→C,D→E,D→G,C→A,BE→C,BC→D,CG→D,ACD→B,CE→G}

　　 Calculation (CG)F4+： set up X(0)=CE

　　 Calculation X(1)： scanning F4 Each function in depends on , Find... On the left CE or CE Functional dependence of subsets , Get one C→A Function dependency . There are X(1)=X(0)∪A=CEA=ACE.

　　 Calculation X(2)： scanning F4 Each function in depends on , Find... On the left ACE or ACE Functional dependence of subsets , Get one CE→G Function dependency . There are X(2)=X(1)∪G=ACEG.

　　 Calculation X(3)： scanning F4 Each function in depends on , Find... On the left ACEG or ACEG Functional dependence of subsets , Get one CG→D Function dependency . There are X(3)=X(2)∪D=ACDEG.

　　 Calculation X(4)： scanning F4 Each function in depends on , Find... On the left ACDEG or ACDEG Functional dependence of subsets , Get one ACD→B Function dependency . There are X(4)=X(3)∪B=ABCDEG. because X(4)=U, Algorithm was terminated .

(CE)F4+=ABCDEG contain A, so CE→A Are redundant functional dependencies , from F4 Removing the .

　　③ Get rid of F4 Each function in depends on the redundant properties on the left （ Check only the functional dependencies on the left that are not individual properties ） because C→A, Function dependency ACD→B Properties in A It's redundant , Get rid of A have to CD→B.

　　 So the minimum functional dependency set is ：F={AB→C,D→E,D→G,C→A,BE→C,BC→D,CG→D,CD→B,CE→G}

 

　　 Explain 2： utilize Armstrong The reasoning rules of axiomatic system are solved

　　① hypothesis CG→B For redundant functional dependencies , that , from F It can be removed from the Armstrong The inference rules of axiomatic system are derived .

　　 because CG→D （ It is known that ）

　　 therefore CGA→AD,CGA→ACD （ The law of enlargement ）

　　 because ACD→B （ It is known that ）

　　 therefore CGA→B （ The law of transmission ）

　　 because C→A（ It is known that ）

　　 therefore CG→B （ Pseudo transitive law ）

　　 so CG→B It's redundant .

　　② The same is true ：CE→A It's redundant .

　　③ Because of C→A, We know that the function depends on ACD→B Properties in A It's redundant , Get rid of A have to CD→B.

So the minimum functional dependency set is ：F={AB→C,D→E,D→G,C→A,BE→C,BC→D,CG→D,CD→B,CE→G}

7、 ... and 、 Candidate code algorithm

     Definition 4b.6（ Equivalent definition of candidate code ） set up F It's the relationship model R(U,F) The set of functional dependencies for ,K yes U A subset of attributes of , If K About F The closure of K+=U( meaning ？), and K Any true subset of about F The closures of are not U, be K yes R A candidate code for .

    Definition 4b.6 Inference ： set up F It's the relationship model R(U,F) The set of functional dependencies for , If the attribute subset X Every attribute of does not appear in F To the right of any function dependency set in , Then all candidate codes must have X.

    explain ： By seeking X+ We can see that , If the attribute subset X Every attribute of does not appear in F To the right of any function dependency set in , Then any does not contain X The closure of a subset of attributes of cannot contain X, Of course not U, None of these attribute subsets are R Code of , therefore R There must be... In all the candidate codes of X.

    Algorithm 4b.2（ Have not appeared in F The algorithm for finding candidate codes when any function in depends on the attributes on the right of the set ）

    ① Find out what doesn't appear in F A subset of attributes consisting of all attributes on the right of any function dependency set in X;

    ② seek X+, if X+=U, be X yes R The candidate code for , And R There are no other candidates , The algorithm ends ; Otherwise to ③;

    ③ One by one, check the absence X A property in is merged into X The resulting subset of attributes Yi, if Yi+=U, be Yi Is a candidate code ;

    ④ Take the ones that are not candidate codes in turn Yi , One by one, an attribute that is not in any candidate code is merged into Yi The resulting subset of attributes Zi, if    Zi+=U, be Zi Is a candidate code ;

    ⑤ And so on , Until there is no such attribute subset and attribute , I found out R All the candidates for .

example 4b.2 Set the relational pattern R=(U,F),U={ABCDE},F={AB→C,C→D,BE→A, E→DB}, Find all candidate codes .

    Explain ：E be not in F On the right side of the middle ,R The candidate code of must contain E, E0=E, Yes E→DB, therefore E1=EDB, And find BE→A, therefore E2=EDBA, And find AB→C, therefore E3=EDBAC

therefore E+=EDBAC=U, therefore E yes R The only candidate code for .

example 4b.3 Set the relational pattern R=(U,F),U={ABCDE},F={AB→CD,E→D, D→E,AE→BC,B→E}, Find all candidate codes .

    Explain ：A be not in F On the right side of the middle ,R The candidate code of must contain A,A+=A, therefore A Not a candidate code ;

(AB)0=AB, AB→CD, B→E therefore (AB)1=ABCDE(AB)+=ABCDE=U, therefore ,AB It's a candidate code ;

(AC)+=AC, therefore ,AC Not a candidate code

(AD)0=AD, D→E, therefore (AD)1=ADE, E→D,AE→BC therefore (AD)2=ADEBC

(AD)+=ADEBC=U, therefore ,AD It's a candidate code

(AE)0=AE, AE→BC , E→D,(AE)+=AEDBC=U, therefore ,AE It's a candidate code ;3 With more than attributes A All subsets of contain AB or AD or AE, They are all super codes , Can't be a candidate code . therefore ,R The candidate codes are AB,AD,AE.