     14 

     

    14.1.  

          13,    
     ,  
       ,    
.         
.       
           ,     
  .  ,       
       
    .     
   ,    
 . 
          .   
 ,       
 .       
, ..  . 
    .        
   ,  , ,   
  .      , 
   . 
     ,       , 
      .      
  ;       
,       .    
  ,      
     .  
       
,       .  
,         
SQL.  ,      . 
         . 
    1.  -,  ,     ,  
     ,      
- .        , 
     ,     
  . 
    2.  -, ,    ,   
 ,           
 .  ,      ,     
         
   . 

    368	 IV,   

    14.2.    

       ,      
     .   ,  
     ,   
     -    
 . ( ,      
    .      
       . 
    " "     
.)  ,      
(    ) : 
    	   ; 
    	  ', 
    	  . 
        
     ,   . 14.1,   : 
    /?    tl\   
       ?2;    
   (  ,     //)  
  t3;        (  , 
    /2,     ,     
 //)    t4.    , 
  ,  ,     t4   
     ""  ,  
 . 

     		  
      	I tl	
    -	t2 I	 	 
      	t3	
    -	\	
    -	t4	 	 
    -		 

    . 14.1.     t4  ,  
  

       

       ,    
    (,   , ) 
 ,       ,  
    .  ,    , 
   ,      . 
( ,          
     .)      
    ,     (  
,   ""  ).     . 14.2 
 14.3. 
       (. . 14.2)      t2 
    (    
).        (3.  
,   

     14.  369 

        ,      
    (2,         
,      //.     
     .  ,  , 
           , , 
,    . (      
   ,         
  .) 

     		  
    -	I	
    -	tl	 	 
    -	I	
      	t2	 
    -	t3	   
    	4	 

    . 14.2.         
  t2 

     	                  
    	tl                
    I            t2	 
    	t3              
    	J, 

    . 14.3.         
.2,         t3 

     ,   . 14.3,   "" 
.        ,  
    12,      t3  
  ,       
  t3          
  tl.        . 

       

     . 14.4     ,     
  ().      ,   
   10   3   1.    
   110, , ,        
,       .    
,           
    .     
     :       
    ,         
,      3. 

    14.3.  

        ,      
         
 .     :  ,   
   ,    (  

    370  IV.   

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

     1	 2 3 ______________40___________________50___________________30______________ 
    _________ _______________________ ________ _	.  
                  _ 
    I 
       1 :        tl	 sum =40                I           
         
    I 
       2 :        t2	 sum =90                I           
        
    	t3            3 : 
    	t4           3 : I                  30 - 20 
    	I 
    	t5           1 : 
    I 
    	t6            1 : 
    I	40 - 50 I 
    	t7             
    	|                  
    I 
       3 :        t8 sum = 110 (  120)	J, 

    . 14.4.      


         . 
    1.   , ,       
:     ( ), 
 - (X locks  exclusive locks),     
,  S- (S locks  Shared locks). 
    . -  S-       
.  ,  -  S-  
,          . 
 , ,         
" ",          . 
    2.            
(-),           
 . 
    3.            
(S-),  "        - 
  ;         
S-     (..      
     S-). 

     14.  371 

            , 
  . 14.5,     .  
    ,       
   (    S  X, 
    ).  ,   
     ,      
   . 14.5 (       
 " ").      N  
  (        
,        ), a Y  
  (     ). , 
    . 

    II   .|    s			
    X	N	N	Y 
    s	N	Y	Y 
    -	Y	Y	Y 

    . 14.5.    -  S- 

          ,    
    -  S-   
   (    ). 
    1.  ,    ,   
  S-   . 
    2.  ,    ,   
  -   .  , , ,  
   /     
S-,     -. 
    .       : 
,   " "     
S-,    " "    
-  .     "" 
(  )        
  .       , 
     ,     . 
    3.          
-         ,  
     .     
      ,     , 
  . 
    .        
       (  
  ).      
       "   
 ". 
    4.  -       ( 
 " "  " "). S-  
     ,       
 ,       . 

    14.4.    

           ,  
   . 

    372  IV.   

        
    
     . 14.6    ,   . 
14.1,        . 
        t3   , 
       -   , 
       S-,    . 
 ,      .   
          (4.  
        ,   
         .  
   ,      . 

     		  
    _	.	_ 
    I 
      	tl	~ 
    ( S-  )	I	 
    	t2	   
    	I	( S-  ) 
    I 
      	t3	 
    ( -  )	I	 
    	I	 
    	t4	   
    	|	( -  ) 
    	|	 
    	|	 
    	J,	 

    . 14.6.    ,     14 
   

       

     . 14.7  14.8     ,   
 . 14.2  14.3 .     
     .   
     /2 (  . 14.7    . 
14.8)   .   ,       
    ,        
-,    .  ,   
      ,      
  (       ).  
           
.          
 (         
,      ).    
        . 

       

     . 14.9    . 14.4   
       14.3. 
        t6   . 
  ,        -  
  1,        S-,  
  .  , 

     14.  373 

     .     
       /7   .   
,        S-   
 3,        -,   
 .  ,      . 
,        (  
  ),       
 (     ,  
  ). 

    ________ _______________________ __________ 
    _	.                    _ 
    I 
    	tl               
    	I          ( -  ) 
    I 
               t2	 ( S-  )       |     
                               |                             
      t3                          |        
  ( -  ) :           t4 ( 
S-  )        | ____________4-__________________________ 

    . 14.7.        
     t2 

     	                 
    	tl               
    	I          ( -  ) 
      	t2                      
    { -  )	I                     
    	|                     
    	t3               
    	|                   
    	|           ( -  ) 
    :   	t4 
    ( -  )	I 
    4. 

    . 14.8.        
     (2 

    14.5.   

       ,       
 ,     .  
,         
 .       .  . 
14.10     ,   !  2  
  ,     (  
    ),    " ...   
"       (  
),   ,   . 

    374  IV.   

     1                 2                   3 40                    
50                     30                            
 \ \    1 :        tl                    ( 
S-          |                      1)              |  
                    sum =40               |                     
  2 :        t2                     ( S-       
   |                      2)              |                      
sum =90               |                   -                 t3        
   3 :                   |          ( 
S-  -                   |                 3) _         
          1                     _                   t4          
  3 :                    |           ( -  -   
               |                3) 1                   30 -> 20  
t5            1 :                   |          ( 
S-  -                   |                 1) _         
          1                     _                    t6          
  1 :                    |           ( -     
                |                 1)                    |          
            3 :        t7                 
 ( S-          |                   
 3)              |                                   1     
                              J,                  

    . 14.9.    ,    
 17    

                                \ 1  ! 
        tl                                   |             
      -                 t2         2   -               
   |                   2         t3              
                     |                                   |    
               -               t4         1   
               |                                 |      
                           -                 

    . 14.10.    


    375	 IV.   


       ,      
    ,     
       .  . 
14.10   ,   ,   
      ,    
.     System R ,    
           [14.4]. 
    ,        
      .      
     , ..   ", 
     ".    
          
     .  ,    
,       . 
    .          
. ,        
,       ,  
       . 
     ,  -  ""  
 " -  ".    
        , 
 ,     ,   . 
     ,    ,  
   "   -"  
     .     
     .    , 
        . 

    14.6.    

          ,   
   "  ",   
      
.  ,     
  ,   , ..     
   ,        
.      . 
    1.    ,      
        
   ,    13. 
    2.  ,        
    .     " 
 " ,     
  . 
    3.   , ,  , 
     , ..   
 . 
         (. 14.1-14.4),  : 
       ,    
   , ..      
  ,    ,    ,   
 .         

    376	 IV.   

 .  . 14.7  14.8   
    ,    .  . 
14.6  14.9   ,       , 
,      .    
,       
  ,    . 
    .         
(  - )   .  
         
,        
    .    
,        , 
     .  ,   
  (..   ),   
    . 
     ,       
 ,    ,   
  .     
         
  ,      . , 
,      " 1  ",   
  " " (       ).  , 
     10.     
  ,        =22,   
    ,     =2\. 
   ,    ,  
    ,    ,   
 5,    ,    (   
      ). 
           (   
 )  (Eswaran)  [14.5].      
   ',     
  : 
        "  ",   
       . 
        ,   ,  
 . 
    1.    -     (, 
   )     . 
    2.          
 . 
     , ,    , 
  :       . 
    .          
  (  )   . 
,         
     . 
            
   .       
 .      , 

    1         . 

     14. 	377 

    77, 2, ... .    
,   ,    
   S,     ], 72, 
... ,      5.    S  
 .     , S   
, ..        . 
       ӗ     77, 72, ... . 
   , ,    S   
 . ,       
,       .  , 
,        
  .         
  ,   ,    
  ,     , ..   
    ,     
  . (       , 
q, ...           ,  
       ,    
     ,     .) 
,          ,  
        
 ,    ,     ,  
  . 
       ,       
  (..     ), 
       ,   
          
,     .      
    , ,   
        
   ,    "  
" (     )   
 .   ,    
    . ,   
   ,       
       (     
   ). 

    14.7.   

      ,  ,     
       . 
        
,  ,     . 
,       ,     
    ,     
  . 
    .        
.     ,    
              
     .      
        . 
        ,   [14.4]   ,  
[14.9],      SQL,  ,    DB2  IBM 
  .  ,    ,  

    378	 IV.   

   ( ),     ,  
   ( ).     
 ,   DB2,    
    .   
 ()   ;     
   ,      
 (         
,         ). 
   ()   77    : 
    	    /?,1 
    	     , 
    	         , 
    	 -  , 
               
 . 
     ,      72  
   /?     .   
]    /?,    ,   
     .   , ,  
  (   -)    
       . 
    .    ,     
 ,     .  ,  ,  
 ,         
,           
.        
      .   ,     
    ,   (  )   
    .    
   ,        
,     (  ,    ). 
       ,      
       ,    
DB2.  ,    SQL    " 
"     ,    
 .       . 

    14.8.   

          ,    
 .         
     ,   , 
   (  )   
   .      
  [14.8].  ,     
     :    , 
  , 

    '  "  "   ,  
          
 (     ).  ,   
 DB2  77,    ,   
"" (U-),        
(S-). U-   S-,     
U- , ,    X-.     
   . 

     14. 	379 

   ,       
 ,  ,     (.. 
    ). ,   
 -   ,     
-      ,    
     .   ,  
         
       . 
    ,     Jf-   
 R.            
 ,        
R.     ,        
   .       ? 
,     ,     
 R -  ,     - 
  -   R.      
 ,     ,    
,       (,  
,     ),     
 ,     .    
,  ,       
  . 
      , -  S-      
,     .    [14.8, 14.9]  
    ,      
,     :    
   (Intent Shared lock  IS),  
    (Intent exclusive lock  IX),   
       , 
    (Shared Intent exclusive lock  SIX).   
     ( ,  
        R), 
       S-  -. 
      IS 
       S-     R  
,        . 
      IX 
       ,     , 
        R,  
     -.    S 
           R,   
.           
 R. 
       SIX 
          S-  
1-, ..       
 R,   .        
     R,      
 -. 
      X 
             R. 
     ,       
 R. 

    380	 IV.   

             
  . 14.11  ,    
 ,     . 

    		X	SIX	IX	S	IS	
    X		N	N	N	N	N	Y 
    SIX	N	N	N	N	Y	Y 
    IX	N	N	Y	N	Y	Y 
    S		N	N	N	Y	Y	Y 
    IS	N	Y	Y	Y	Y	Y 
    -		Y	Y	Y	Y	Y	Y 

    . 14.11.  ,    

           
 . 
    1.      S-   ,  
  IS-       
,     . 
    2.      -   ,  
  IX-       
,     . 
    (  ,       , 
     [14.8].) 
             
 ,   . 14.12.   L2 
   (..     )  
   L1    ,     
 (N)    L1      
      L2     (. . 
14.11).  ,     ,  
    ,       
   (  ,    
  ,      ,   
    .) 

    X 
    I 
    SIX 
    
    
    I	S             I	X 
    I 
    IS 

    . 14.12.      

     ,  (   )  
      . ,  
       IS-  
 ,     .     

     14.  381 

 , ,   IX-.    
           
 LOCK,         
 S-, -  SIX-    . ,  
    LOCK   DB2 (  
     SQL). 
    ,      ,  
         
         
    .     
, ,       ,  
       . 
,   S-   ,  
IS-   ,    S-  
 .        . 

    14.9.    SQL 

       SQL       
 (,      ).   
,       
   . , ,  
,    77,      
  72       ,     
  77.       
 ,   .    
   ,     . 
    ,     ,    
    READ COMMITTED ( ), 
REPEATABLE READ ( )  SERIALIZABLE (  
).     ,   
  READ UNCOMMITTED ( )   
  " " (    ),    
  READ ONLY (     13). 

      

      13    SET TRANSACTION   SQL, 
        
 .       , 
     (READ COMMITTED), 
  (REPEATABLE READ)     
(SERIALIZABLE).    SERIALIZABLE, ,   
    ,      
,   " "    
: SERIALIZABLE > REPEATABLE READ > READ COMMITTED > READ UNCOMMITTED. 
             
(  ),      
    . ,    
     ,     
    .      
     ,  : 
       . ,   77  
   ,   72   , 
  

    382	 IV.   

  77 .    72 , 
        ,     
 (  77    ). 
        . ,  77   
,  2    ,    77 
  "" .    77   "  
 "     . 
        . ,   77   
 ,     (,   
  ). ,   72   , 
    .   77     
 ,   ,      
   " ". 
             
   ,     
  . 14.13. 
     	 	 
	  

    READ UNCOMMITTED	Y	Y	Y 
    READ COMMITTED	N	Y	Y 
    REPEATABLE READ	N	N	Y 
    SERIALIZABLE	N	N	N 

    . 14.13.    SQL 

        :     
  " "?       
      .     
            
 ,        . 
       ,  
        (..   
    ).     
  [13.11, 14.4]. 
          ,  ,   
 SERIALIZABLE (,  ,    
)    ,      
   .      
    LOCK     
 ,       
.     SQL      
 . 
       ,    REPEATABLE READ  
  SQL    DB2   .    
 REPEATABLE READ   DB2   SERIALIZABLE  
 SQL. 

    14.10.  

          .   
  ,       
   ,  :   
 ,     
.     - ,     
, ..       
    . 

     14.  383 

           
 .     :   
  (S-)      
(-). ]   S-   , 
          S-,  
  -.    -   
,            
  .  ;     
         
 .   S-     
, -     ,    
    .     
    . 
         (  )   
 .       , 
      ,     
 .     ,      
    ,      
   ,      
  .  ,    
      .   
         
-    . 
           
,    .      
      
       , 
        .     
   " ", ..    ( 
  ,    DB2,     SQL 
   READ COMMITTED). 
             
     .    
       , 
    ,      
 ,     ""   
 (..     ,     
).         
 ,  S-  - , ..  .   
     (  ) 
   LOCK      
,   . 
    ,          
 SQL.    SQL      
,         SERIALIZABLE, 
REPEATABLE READ, READ COMMITTED, READ UNCOMMITTED,     
     . 

     

    14.1.      . 
    14.2.      . 
    14.3.    77, 72  ,    : 
    1:   1  , 

    384	 IV.   

    2:  , 
    :    ,       1 
    (       ). 
    ) ,   ], 2    . 
      ,  
    . 
    ) ,   77, 72       . 
    1		2		 
    R1:	    tl	R2:	    t2	R3:	 
  		t3 
    tl := tl + 1		t2 := tZ * 2		  13	  
    U1:	   tl	U2:	   t2	U3:	 		1 
        ,    
  - ? 
    )   -   ,   
   ()    "" ,  
  ? 
    )   -  ,   
 ,     ,     
   ? 
    14.4.        
    77, 72, ..., 772     , 
,..., . 

     tO	........ 
      
     tl         (Tl)	  
     t2          (T2)	  
    -	(1)	  
    -	(4)	 D 
    -	(15)	  
    -	(2)	  
    -	(2)	 ? 
    -	()	 F 
    -	(2)	 F 
    -	(5)	  
    -	(1)	   
    -	(6)	  
    -	(5)	   
    -	()	  
    -	(6)	  
    -	(7)	 G 
    -	(8)	  
    -	(9)	 G 
    -	(9)	 G 
    -	<8)	  

     14.  385 
    13      


    (7) 
    (9) 
    () 
    () 
    (9) 
    (6) 
    (Till 
    (12) 
    (12) 
    (21 
    (Til) 
    (12) 
       
      
     G 
      
      
       
      
     D 
      
     F 
      
      
    	(10)         
    	(12)        D 
    	(4)         G 
    	tn           ........ 

    ,   G  (    ) 
 S-   G,   G (    
)   -   G. ,    
    .      
  tnl 
    14.5.     ,   . 
14.1-14.4.       ,    
     ,     
 ? 
    14.6.        : 
X, S, IX, IS, SIX. (.       .) 
    14.7.        
   . 
    14.8.    ,    
   ? 
    14.9.    SQL    : 
 ,     .  
     ,      
(  ,  ,  )? 

      

         [13.1, 13.9]   [13.11]  
 13. 
    14.1. Bayer R., Heller M., Reiser A. Parallelism and Recovery in Database 
Systems // ACM TODS.  1980.  5,  2. 
         ,  
 ,    ,  
    .    
  ,       
, ..         
        . 

    386	 IV.   

           (  
      ),     
  ,       
   .      
  . 
    1.     72     , 
          77, 
  72       
.      -   ,  
   ,      
 . 
    2.     72     , 
          77, 
  72     ,    
77        (  
   ). 
    ,        
 ,         
  . 
    14.2. Bernstein P.A., Goodman N. Timestamp-Based Algorithms for 
Concurrency Control in Distributed Database Systems // Proc. 6th Intern. Conf. 
on Very Large Data Bases.  Montreal, Canada, 1980. 
          ,  
    ,   :    
      ,   
,         
   (      
).  ,       
,   ,       
  ,    .   
         
.        , 
      .  
          
  (         [14.11]). 
         ,     
     (   
      -  
     ).     
     .  ,  
        
   .     ,  
       ,  
     (     
,     ).    
,       ! 
,  (Gray)  [13.11] ,       
        
[14.11],  ,   ,   . 
    14.3. Blasgen M.W., Gray J.N., Mitoma M., Price T.G. The Convoy Phenomenon 
// ACM Operating Systems Review.  1979.  13,  2. 

     14. 	387 

             
    . ,      
       ;   . 
    .  ""      
    ,    ; , 
  ,        . 
          .   7 
          
  , ..     
,  - ,      .  
    ,    
-    .      
 ,  .   - ,  
     ,   , 
,    ,     
     .      
        . 
        ,     (   ) 
     ,   ,   
     .   
  ,     .  
,     " ",  
     ,   
 -  .      
,     ,    
   ,      "   
 ". 
    14.4. Date C.J. Concurrency // . J. Date. An Introduction to Database 
Systems: Volume II.  Reading. Mass.: Addison-Wesley, 1983. 
             . 
    14.5. Eswaran .P., Gray J.N., Lorie R.A., Traiger I.L. The Notions of 
Consistency and Predicate Locks in a Data Base System // CACM.  1976.  19,  11. 
            . 
    14.6. Franaszek P., Robinson J.T. Limitations on Concurrency in 
Transaction Processing //ACM TODS.  1985. 10,  1. 
       [14.11], 
    14.7. Franaszek P.,  Robinson J.T.,  Thomasian A.  Concurrency Control  
for High Contention Environments // Ibid.  1992.  17,  2. 
       , , ,      
        
,   .       
      .   
 "    [ ]  
  ,       
  ".     
    . 

    388	 IV.   

    14.8. Gray J.N., Lorie R.A., Putzolu G.R. Granularity of Locks in a Large 
Shared Data Base // Proc. 1st Intern. Conf. on Very Large Data Bases.  
Framingham, Mass., 1975. 
          .  
   ,  "  "   
  .   , ,  
   , ,     
     (      
).         
     . 
              
 ,      . 
-,  ,        
  ,   . -,   
         . 
        ,   
     . ,  
       ()   
,   ,  ,    #  .  
         ,  
         
 ,         
  .  ,      
""         ,   "" 
   . 
            . 
       -       
-      . 
    "   S-  SIX-      
 S-      . 
         S-  IS-   , 
   IS- (  )      
   . 
         S-, IX-  SIX-   
,    IX- (  )   
   . 
               
,          . 
            
 ,    ,     
       . 
, IX-, ,         
  .       
,      . 
    14.9. Gray J.N., Lorie R.A., Putzolu G.R., Traiger I.L. Granularity of 
Locks and Degrees of Consistency in a Shared Data Base // Proc. IFIP TC-2 
Working Conf. on Modeling in Data Base Management Systems (ed. G. M. Nijssen). 
 Amsterdam, Netherlands: North-Holland; New York, N.Y.: Elsevier Science, 1976. 

     14. 	389 

           (  " "). 
    14.10. Harder ., Rothermel . Concurrency Control Issues in Nested 
Transactions / VLDB Journal.  1993.  2,  1. 
         13,    ( 
   .       
     . 
    14.11.Kung .., Robinson J.T. On Optimistic Methods for Concurrency Contr 
ACM TODS.  1981.  6,  2. 
          , < 
  (  )  ,   , <  
  ,       
,     .    , 
,     ,    
 .       
 .     !    
    . <    
,          
         , 
          
 . 
     [14.6]   ,      
,      i 
          
  (..    .  
),    . , 41 
          ]  
  . ( [13.11], , yreef ,  
            
 "" , .. ,     
      .    
 ,    i  ,    [14.12].) 
    14.12. O'NeilP.E. The Escrow Transactional Method // Ibid. 1986.  11, 4. 
        . ,    
   ,  "   ",  
,            
     (   
).       , ..  
 ,     .  
,         
  ,         
   .      10  
,         ( ) 
 10 ,          
.          
 .  .   , ,   
       .   
   ,        
   ,     . 
(       ,   
   .) 

    390	 IV.   

         ,  
 , ..      ,   
.           
(, "      ,     
 ").    ,      
,         
    (  ,   
 ,   ,     ). 
        ,      
 .     ,   
  ,    IMS Fast Path 
 IBM.  ,        
    [14.11] ( , 
,    "", ..    
,    ). 
    14.13. Papadimitriou . The Theory of Database Concurrency Control. 
Rockville, Md.: Computer Science Press, 1986. 
     ,       . 
        
    14.3. )    ,   
   : 
    	=	 
    	=	1 
    	=	2 
    	=	1 
    	=	2 
    	=	4 
    	=	3 
      
    1-2- 
    1--2 
    2-1- 
    2--1 
    -1-2 
    -2-1 
    ,      . ,  
    ,      
        . 
    )  90    ,   
     . ( Ri, Rj, Rk 
   Rl, R2, R3,       
. , Up, Uq, Ur    UJ, 
U2, U3,       .) 
    Ri-Rj-Rk-Up-Uq-Ur : 3*2*1*3*2*1 =	36  
    Ri-Rj-lp-Rk-Uq-Ur : 3*2*2*1*2*1 =	24  
    Ri-Rj-Lp-Uj-Rk-Ur : 3*2*2*1*1*1 =	12  
    Ri-Up-Rj-Rk-Uq-Ur =3*1*2*1*2*1 =	12  
    Ri-lp-Rj-Uq-Rk-Ur =3*1*2*1*1*1=	6  
     =	90  
    ) . ,   RJ-R2-R3-U3-U2-U]     
 ()     (),     
    . (. 

     14.  391 

  .)   ,  "" 
        
 ,      0,   -  
.       ,   
   10.        
     ? (     
  ?)  ,    
R1-R2-R3-U3-U2-U1   . 
    ) . ,   R1-R3-U1-U3-R2-U2   
(     1-2-),     
,  ], 72      .  
     R3      
 S-  .   UI   77   
   ,     ,      
    (,     
   77    ). 
           .  
          
     (),   , 
    (),    
    ,   ,     
   ,      
  ( ),      
 (),       
  .      
 (  "<"  ""): 
     <   <  <  
    14.4.    tn         
 !   ,      , 
  72, , 9  8.  ,  4   
  ()    79,  
12     4,   10  11 
    12.      
   . 14.14   ,    
  ,     77   Tj   , 
  77       
 Tj.         
    ,       . 

     
      ( X  ) 
      ( X ) 

    . 14.14,     . 14.4 


    392  IV.   

    14.5.  ,   . 14.1-14.3,   
     ,     
 ( , ,    DB2    
     - ,    DB2  
S-  U-).     
 (. . 14.4),        
  .   ,       
    ,      
  ,     . 
(,     ,     
           
       .   
          
  .) 
    14.9.        ,  : 
   ,    
 . 
       .    SQL , 
 (  )      
 . 
      .       
 . 
      .      
 ,     . 

     14. 	393 

