     III 

       

            , ,  
   .     
 :          
   ?  ,   , 
        .  
     . 
         ,   . 
          ,      ,  
  .    ,      
 ,     . ,   
,    . 
            
.  ,  ""      
    (.. ) ,     
         
,  . 
             , 
       .  , , 
   ,        
   .       
  . 
     ,     ,     
         
.  ,        
    "    
".   ,         
        
, ..      .  
,       "   ". 

    9      

       ,    ,       
,           
  .  ,      
       ,   
          
  (, ),   . 
           ,    
  ,   . ,   
    ,       
 .         
,       .   
           
 .        , 
   ,         
  ,        
 .  ,       
 ,   , ,    . 
          
,       
  .  ,    ,   12     
 ,  ,  . 
          ,    . 
              
   ,     
   . 
             
.  ,    ,   ,   
.     ,    
         
 .  , ,    , 
..         (.. 
     )   .  
  (    ),   
 , ..   ,    
 ,  , ,  , 
  ..  ,    ,   
         
 . 
         ,       
,  ,         
.      ,   
 .          
 ,       . 
      9    ,    10, 11  
   ,     
       .    
12    /  ,    
     " " (   
      ). 

     9 

      

    9.1.  

           (functional 
dependency  FD),   "  ,     
".          , 
,  ,    ,    10. 
     ,   (      
  )    --  
    . ,   
 SP       
{S#, P#}  {QTY}, ..     S#-P#  
   QTY (       
. 3.8). 
            
,         
    .    ,   
        ,  
     ,   
    .        
         .  
    . 
    .         , 
   ,      
 ,      .   
    ,      , 
      . 

    9.2.   

            
   ,       
S#, P#  QTY     CITY,   
 .       
   SCP.       . 9.1. 

    SCP 

    s#	CITY	P#	QTY 

    SI	London	PI	100 
    SI	London	P2	100 
    S2	Paris	PI	200 
    S2	Paris	P2	200 
    S3	Paris	P2	300 
    S4	London	P2	400 
    S4	London	P4	400 
    S4	London	P5	400 
    
    . 9.1.   SCP 
    
     9.   259 

      : )    (..  
 )    ; )    
,    ()     
  (     4).    
     (),     (). 
       R   ,  X  Y    
  R.      X,   
    
    X -> Y 
    (    "^  ",   "X  
"),    ,     X  R 
       Y  R.  , 
    R    X,      
 Y. ,   SCP (. . 9.1)  
   ,     
SCP     S#     CITY. 

    {   S#   }  ->  {  CITY } 

            : 

    { s#, # } -> { OTY } { s#, # } - { CITY } 
    {	S#, P# } -> {	CITY, QTY } 
    {	S#, P# } ~ {	S# } 
    {	S#, P# } -> {	Sf, P#, CITY, QTY } 
    {	S# } -> { QTY	} 
    {	CTY } -> { S#	} 

    (.    .) 
            
      .  
  ,       
.      ,   
 ,        

    S# -> CITY 

       ,      " 
    ()", ..    .    
 ,   ,    
        
 ,   ,    
   . ,    SCP 
  

    S# - CITY 

         SCP,     
       ;  , 
    SCP             
         . 
 ,      
"" (..     SCP),   
   SCP,      
    . 
            
    () (   ,    (),  
 ). 

    260	 III.    

        R   ,  Y  
    R.  Y   
 X,       
    X ->  Y 
    (    "X   ",   "X  
"),    ,       R 
  X       . 
     ,      R,    
  R     X,      
 . ,   " "  
       (  
  ). 
           
    SCP: 

    {	S#, # } - QTY 
    {	S#, # } -> CITY 
    {	S#, # } -> { CITY, QTY } {	S#, P# } -> S# 
    {	S#, P# } -> { S#, P#, CITY, QTY } 
    {	S# } -> CITY 

     ,  ,   ,  
    . 9.1,    "": 

    S# -> QTY QTY -> S# 

     , ,  ,  "    
   ",      . 
9.1,          SCP. 
     ,   X     R, 
 X   ,      R  
     X (    
 ).     , , , 
   

    # -> ( #, PNAME, COLOR, WEIGHT, CITY } 

    ,   R     - 
      ,  R    
. ,    SCP   ,   
     ,     ( 
   . 9.1).        10. 
    ,      , 
  "",   , 
          
  ,      SCP. (. 
        
SCP.)          
       . 
        ?      , ,   
,     , 
           . 
,      S 
    ,  (  )   
  

     9.  	261 

    ,   5,     S     
   7".       
,           ,    
 5   .    
      . 

    9.3.     

    ,      " "  
     "",  "  
"   "  "  .. 
             
 , .. ,     .  
       SCP   : 

    {   S#,   #   }   -> S# 

          ,    
      (  
 )  . 
       ,      
    ,     , 
   ""  .   
        
 . 

    9.4.    

       ,      . , 
   

    {  S#,   #  }  ->  {  CITY,   CTY } 

      : 

    {   S#,   #   }  - CITY {   S#,   P#   }   -> QTY 

            R   
 ,   ,       >  
  > .     ,     
 > ,     , ..  
     . 
      ,      
 S,   S    S'.  
   ,      
    S'   S.     
    (Armstrong) [9.1],     
       (  
   ).     
,       . 
         .      ,   
ї       R, a 
       . 
    1.	:     ,   > . 
    2.	:   > ,   > . 
    3.	:   >    > , ->. 
              
   (        

    262	 III,    

     ).  ,       
,       S  
 ,     S,     S  
  .    ,   
      (.. ,    
  5).  ,      
   S . 
             
  S     . ( D   
     R.) 
    4.	:  -> . 
    5.	:   - ,   -    - . 
    6.	:   >   -^ ,   > . 
    1.	:   >     D,   > BD. 
     ,  (Darwen)    [9.6]   
,     : 
    8.     ->    - D,    (- ) > BD (  ""  
 ,   "-"   ). 
     "  "   ,   
          
 [9.6]. 
    .     R   , , , D, E, F  
 : 

     ->  
     -  CD -> EF 

     ,      (   
): ,    ,      
,         ,      
 . 
    .  ,       
,  :    ,    , ї   
()  , D   ,   
 (     ),   
 , F ,     . 
      ,   AD  F    R 
       . 

    1.	 -> 	(  } 
    2.	  	(  1   ) 
    3.	AD > CD	(  2   ) 
    4.	CD - EF	(  ) 
    5.	AD > EF	(  3  4   ) 
    6.	AD -> F	(  5   ) 


    9.5.    

                
  S      S,  
    ,       
 .         
.   R      R, 
    

     9.  	263 

    ,     ,    
  . (  "",  , 
      " ".)  
,  ,      R    
     R,    
 ->        R. 
     ,    ,    
,       .  
      (.. 
   ).  , ,   
    ,     
   ,     . 
       ,      R 
  ,    .  ,  
   S,     R, 
        R, 
    , ..      
  S.        . 9.2.  
 . . ,    . 

    CLOSURE [, S] :=  ; 
    do "forever" ; /*   */ 
    for each ED X -> Y in S   /*    X ->   S */ do ; 
    if X is subset of CLOSURE[K, S]  /*    */ 
    then CLOSURE [, S] := CLOSURE [, S] UNION Y ; end ; 
    if CLOSURE[K, S] did not change on this iteration then leave loop ; /* 
      , 
      */ end ; 

    . 9.2.   (    S 

    . ,    R   , , , D,   F  
 : 

     ->   - CF  ->  
    CD -> EF 

       {, }+   {, }   
 . 
    1.     CLOSURE[A", 5]     {, }. 
    2.       ,      
.    (   - )  ,   
     CLOSURE[A", S];  
,        .  CLOSURE[A", 5] 
    {, , }. 
    3.     (  ?-CF)  ,   
        , 
,  ,  . 

    264	 III.    

    4.     (   > )  ?  
   CLOSURE[/v, S\,      {, , , }. 
    5.     (  CD > EF)  CLOSURE[/C, 
5]  . 
    6.         .   
   ,       {, , , 
, F},         . 
    7.  ,        
CLOSUREfA", S]          
 {, , , , F}+={A, , , , F}.  ,  {, }  
  (, ,  ). 
           :   
   S   ,    
 X -> Y   S,       
,  Y    X*  X   
 5.  ,      
,     X > /  
 5*  S. 

    9.6.    

     S1  52    .   ,  
   S1,     52, 
..  5/+   52+,  52    5/. 
(    ""    
.)  ,        
  52,         
   5/. 
    ,  52    5/,  5/    52, .. 
 S1+-S2+,  57  52 . ,   5/  52   
       52,   
       5/,  
   . 
           ,  
   . 
    1.   ( )    5   
  (..   ). 
    2.    ()    5  , 
..            
 5* (   5   ,  
  5).       . 
    3.        5      5  
  5* (..    5   
,    5). 
              
 : 

    # ->  PNAME # -> COLOR # -> WEIGHT # -> CITY 

     ,      :   
     ,  , , 
 ,  ,         
    (..    ).  
,       . 

     9.  	265 

    1. # - ( PNAME, COLOR ) :      # > 
WEIGHT	  # -> CITY 
    2. ( #, PNAME ) -> COLOR :     
    # - PNAME	  PNAME   # - WEIGHT           
    # -> CITY 
    3. # -> #	:     
    # > PNAME	    # -> COLOR # -> WEIGHT # 
-> CITY 

       ,      , 
  ,   ,   . 
      .   
   S,      
   ,      S  
  .     /   S 
       /   S   
,         / 
,     .      
 S /  S  S -/,  / 
 S.       S  
     S. 
    .    R   , , , D   : 

     ->   ->    ->   ->    ->  D 

         ,   . 
    1.       ,     
   : 

     ->  
     ->   -   -   ->  
     - D 

     ,    >   ,     
  . 

    2.            ї>  
    >         > 
,       > D     
   > D\  ,        
> D  . 
    3.    ,    >    , 
    ->         -> 
,      > . 
    4.  ,   -     ->    
-> ,       .    
  : 

    266  III.    

     -*   ->  
     -> D 
      /,      
   S,     
S.  ,          
 S       /.  
 ,         
   (    ). 

    9.7.  

          --  
    .    R 
  >  (        
 )    R    ,    
  R        . 
      ,   
"", ..       (  
""      " ").  
      
;        , 
   ( )     (). 
        .    
 S   5"*    , 
   S.  S   
   5*.    
      5*  S,   
   (    )  
  . 
           R   
 S,     /?,  +  
  S        R,  
  ->     5*".   +   
   R,      R ( 
    ).      
      +     S , 
,  ,     A" Y  
 S (X> Y    S    ,  Y 
   Jf). 
       S1  S2     , 
      , .. S1+-S2+.   
       .  
   ,     
    ,       
      ,     
            
 . 
       ,      
      ,    
 . , , :   
  ;    
 ;   ,   
,      ;  
,         (.. 
    

     9.  	267 

       ),   
  ;     
       . 
        
      ,    
  .       
       ,    
  (MVD, JD  IND),      
 .   , ,     
    ,   . 

     

    9.1.  R    .    
  ( ,   ),  
   R? 
    9.2.  ,       ? 
    9.3.   ,     
    . 
    9.4. ,       
, ,   . 
    9.5.  "  ",  . 
        ?  
        ? 
    9.6.   : )   ; )   
    . 
    9.7.    ,     
  SP. 
    9.8.       R{A, , , D, E, F, G}: 
     ->   -> DE AEF -> G 
      {, }+   .   
 ACF > DG  ? 
    9.9.        
 S1  52? 
    9.10.      ? 
    9.11. ,         
 R{A,B, , D, E}. 
    1.     -> 	 ->                D -> AC                 D ->  
    2.     -> 	D -  
    9.12.         
 R{A, , , D, E, F}. 
     ->   -   -> D ACD ->  BE ->  

    268	 III.    

     -CF  D -. 
     FA  BD EF 
    9.13.   TIMETABLE    . 
D	  (1-5)                    (1-8)         
                        L                
     {D:d, P:p, :, T:t, L:l]      
  ,   /   t       
{D:d,P:p}. ,        
,  ,    ,     
   .      ?  
     ? 
    9.14.    NADDR   : NAME 
( ), STREET (), CITY (), STATE ()  ZIP (), 
        ,   , 
      .   
    .      
 ? 
    9.15.    R   , , , D, E, F, G, , /, J  
   . 

    ABD ->  
     - G  -> F  -> J CJ- I G ->  

        ?    
   ? 

      

    9.1. Armstrong W. W. Dependency Structures of Data Base Relationships // 
Proc. IFIP Congress.  Stockholm, Sweden, 1974. 
         (..    
 " ")-     
 . 
    9.2. Casanova M.A., Fagin R., Papadimitriou C.H. Inclusion Dependencies 
and Their Interaction with Functional Dependencies // Proc. 1st ACM 
SIGACT-SIGMOD Symposium on Principles of Database Systems.  Los Angeles, 
Calif, 1982. 
      (inclusion dependencies  INDs)   
  . ,    
    SP.S#  S.S# 
    (      , 
,     ) ,   
  SP.S#    (  

     9.   269 

     )    S.S#. , , 
   ,       
      ,     
 ,    . .   
    ,      
  --. 
             
,    (   )   
 : 
    1.    >  
    2.     > CD,  >   > D. 
    3.    >> Q  > 
    9.3. Casey R.G., Delobel . Decomposition of a Data Base and the Theory of 
Boolean Switching Functions // IBM J. R&D.  1973.  17,  5. 
      ,       (   
   )     " 
 ".  , ,      
 ,         
 ( ) ,        
    ,      
           . 
,   ""    
        " 
   "   ,   
    . ,     
      ,     
    . 
        ,     
     .    
 [9.8]   ,      
 . 
    9.4. Codd E.F. Further Normalization of the Data Base Relational Model // 
Data Base Systems, Courant Computer Science Symposia Series 6.  Englewood 
Cliffs, N.J.: Prentice-Hall, 1972. 
        .  
" " ("Further Normalization"),   , 
       , 
   10 (      
        ). 
,        
   .         
      . 
    9.5. Codd E.F. Normalized Data Base Structure: A Brief Tutorial // Proc. 
1971 ACM SIGFIDET Workshop on Data Description, Access, and Control.  San 
Diego, Calif, 1971. 
      ,   [9.4]. 
    9.6. Darwen H. The Role of Functional Dependence in Query Decomposition // 
C.J. Date and H. Darwen. Relational Database Writings 1989-1991. Reading, 
Mass.: Addison-Wesley, 1992. 

    270	 III.    

          ,  
          
        ( 
),     .    
         
  .      
   ,     6  
" ".   ,       
        
 ,     . 
    9.7. Darwen H. Observations of a Relational Bigot // Presentation to BCS 
Special Interest Group on Format Aspects of Computing Science.  London, UK, 1990. 
    9.8. Fagin R. Functional Dependencies in a Relational Database and 
Propositional Logic // IBM J.R&D.  1977.  21,  6. 
    ,  " " [9.1]    
    .  ,  
       ,   , 
   /     
 S    ,  ,  f, 
    ,  
 S. 
    9.9. Lucchesi C.L., Osborn S.L. Candidate Keys for Relations // J. . 
and Sys. Sciences. 1978. 17, 2. 
         ,   
 ,    . 
        
    9.1.        ,     
     R.   
    2"  , aAuB  2"  
 , ,     2"". 
    9.5. 1.  -> 	() 
    2.  -> D	() 
    3.  >  \ 	( , 1) 
    4.  -  ->  - 	() 
    5.  (  -  ) -> (    )  (  -  ) (, 3, 4) 
    6.   (  -  ) > 	(, 5) 
    7.   (  -  ) -> D	(, 6, 2) 
    8.  (  -  ) -   D	(, 1, 7) 
     . 
          .  
  ,      : 
, ,   .     
     : 
       ->    - ,   -> . 

     9.  	271 

    9.7.     , .. ,  SP. 

    { S#,	P#,	QTY	}	-> {	S#, P#, QTY } 
    { S#,	P#,	QTY	}	-> {	S#, P# } 
    { S#,	P#,	QTY	}	- {	#, QTY } 
    { S#,	P#,	QTY	}	-> {	S#, QTY } 
    { S#,	P#,	QTY	}	-> {	S# } 
    { S#,	P#,	GTY	}	-> {	P# } 
    { S#,	P#,	QTY	}	-> {	QTY } 
    { S#,	P#,	QTY	}	-> {	} 
    { S#,	P# } ->	{ S#, PI, QTY } 
    { S#,	P# } ->	{ S#, PI } 
    { S#,	P# } ->	{ P#, QTY } 
    { S#,	P# } ->	{ S#, QTY } 
    { S#,	P# } ->	{ S# } 
    { S#,	P# } ->	{ P# } 
    
    { S#,	P# } ->	{ QTY } 
    { S#,	P# } ->	{ } 
    {	P#,	QTY }	-> {	P#, QTY } 
    {	P#,	QTY }	-> {	P# } 
    {	P#,	QTY }	-> {	QTY } 
    {	P#,	QTY }	-* {	} 
    {	S#,	QTY	}	->	{	S#, QTY } 
    {	S#,	QTY	}	->	{	S# } 
    {	S#,	QTY	}	->	{	QTY } 
    {	S#,	QTY	}	->	{	} 
    { S# } - { S# } { S# } - { } 
    { P# } -> { Ptt } { P# ) -> { } 
    {  QTY#  }  ->  {  QTY#   } {  QTY#  }  ->  {   } 
    {   }  ->  {   } 
    9.8. {A, C}+ = {, , , D, ?}.       
 . 
    9.11.  .        : 
    1.  -  
    2.  -  
    3. D ->  
    4. D -> ? 

    272	 III.    

           : 
    3.0--> 
              : 
    2.  -  
        ->    - ;     
  -> ;         
 : 
    3. D ->  
     ,       : 
     ->	 
     -	 
    D ->	 
    D ->	 
        , ,   
 : 
     -  D ->  
     ,    . 
    9.12.  ,     ,   
    : 
    1.  ->  
    2.  ->  
    3.  -> D 
    4. ACD ->  
    5. ? ->  
    6. ? -  
    7.  -> F 
    8. CF ->  
    9. CF -> D 
    10.D-. ? 1 1.D -> F 
     
      2   6,   6  ; 
      8  CF ->  ( ),    
 3  CF ->  ( ),    9  ; 
      8  ACF ->  ( ),   11 
 ACD - ( ),  ACD - ( )  
ACD ->  ( ).  ,  4  . 
             . 
     ->   ->   -> D BE ->  

     9.   273 

     -> F CF->  D -> ? 
    D -> F 
       : 
      2  CD -> ACD ( ),    4 
  ->  ( ),    4   
  -> , 
      2   6,    6   (  ); 
      2  9  CF -> AD ( ),  
 CF -  ( ),     4 
 CF ->  ( ).  ,  8  . 
             : 
     ->  
     ->   -> D CD -  
    BE  
     
     -> F CF -> D D -> ? D -> F 
     ,         
   . 
    9.13.    L, DPC  DPT. 
    9.14.    N, R, ,   Z   NAME, 
STREET, CITY, STATE  ZIP ,    : 
    N -> RCT        RCT -> Z        Z ->  
    ,      : 
    N -> R        W-C        W-T         - ?        Z-C        ^ 
        N. 
    9.15.        ,   
     . -, , ,  
 ,    -> j  cj-> i   -> I. 
-,     {, , , D, G, J} (.. 
  ,      ).   
   J,   -> J,     G, 
  -> G       , , , D    
    ,  {, , , D}   . 

    274  III.    

