1. Granularity of Locks and Degrees of Consistency in a Shared Database - Gray

 

G ra nu la ri ty of

L o c k s a n d D eg re es o f i n a S h a r e d Data Base J N R A

G.B.

I L

Co nsis tenc y

Gray Lorie Putzolu Traiqer

IBlY SaR n eJsoe saer ,c h C La al bi foor ra nt oi ar y

In the f i r s t p a r t o f t h e p ap er t h e p r ob l en o f ch oo sin g granularity size) of l o c k a b l e o b j e c t s s i n tr o du c ed a n d t h e r e l a t e d t r a d e o f f b e t ween c o n c u r r e n c y a n d o v er h ea d s discussed. A locking p r o t o c o l which a l l o w s s i m u l ta n e o u s l o c k i n g a t various u r a n u l a r i t i e s by d i f f e r e n t t r a n s a c t i o n s s p r e s z n t e d . It s b sed on th introduction of add itio nal lock modes besid es th e c o n v e n t i o n a l s h a r e mode a n d e x c l u s i v e m o d e . A proof s given of ABSTRACT:

t h e

t h o e q u i v a l e n c e of t h i s p r o t o c o l t o a c o n v e n t i o n a l o n e. In tho s3cond p a r t of th e paper t h e issue i n a of c o n s i s t e n c y s h a r e d a nv i ro n m e n t disc ussion motivated y s a n al y ze d . T h i s s r e a l i z a t i o n t h a t s o m e e x i s t i n g d a t a base s y s t e m s u s e a u t o m a t i c t h l o c k p r o t o c o l s w hic h i n s u r e p r o t e c t i o n o n l y f ro m c e r t a i n t y p e s of inc onsistenc ie s for instance those arisin g fr om t r a n s a c ti o n b ac k up ) , th ereb y automa tically providin g a limi ted d e g ree of consistsn cy. F ou r d e q r e e s of c m s i s t e n ~ r~ e introduced. T hey c a n be r o u g h l y c h a r a c t e r i z e d a s f o l lo w s : d t g r e e 0 p r o t e c t s o t h e r s from y o u r u p d a t e s , d e g r e e 1 a d d i t i o n a l l y p r o v i d e s p r o t e c t i o n from lo si cg u p d at es , d e g r e e 2 a d d i t o n a 117 p r o v i d z s p r o t e c t i o n from r ea d in g i n c o r r e c t d a t a items, a n d d e g r e e 3 a d d i t i o n a l l y p r o v i d a s p r o t e c t i o n f ro m d a t a items reading i n c o r r e c t r e l a t i o n s h i p s a m o ng po rf o t et hc et i o n f) o . ur r e il .a ? t i .o n ts oh it pa sl d e gdr iesecsu s s ti oo n l o cf ko il nl og w s p r oo nt o c otlhs e, c o n c u r r ~ n c ~ ,v ,v e r h e a d , r e c o v e r y a n d t r a n s a c t i o n st ru ct ur e. Lastly, systems.

these i d e a s

are

related

t o existing

data

management

 

G Y A N U L A R I TY

2

3P

L

CKS:

Pin i m p o r t a n t problem m an ag e m en t s y s t s a is a g gr eg a te s which a r e E xa mp le s o f l o c k a b l e f i e l d v a l ue s , i n t e r v a

which arises i n th e d es ig n o f a d a t a b as e c h oo s in g t h e l o c k a b l e u n i t s , i e. th e data a t o m i c a ll y l oc ke d t o insure c~ nsist ency. u n i t s a r e areas indiv lOu al records, files l s of f i e l d v a l u e s , e ts.

T loov ce kr ha eb al de , u w n ih ti cs h p ir s e s e rn et ls a t a c oh ne z u cr hr eoni cc ye oa nf d e d tt roa d et ho ef f s bi ze tew e eo nr q r a n u l a r i t y o f t h e u n i t s t h em s e lv e s. On t h e o n e h a n d , c o n c u r r e n c y is i n c r e a s e d if a fine lockable unit for ex am ple a record or field) c h o s e n. Such u ni t is appropriate for a tlsimplen is t r a n s a c t i o n w hi c h accesses f ew r e c o r d s . n t h e o t h e r h and a f i n e u n i t o f l o c k i n g w o ul d b e c o s t l y f o r a g lc o m pl e x a g r a n s a c t i o n w h i c h S u c h a t r a n s a c t i o n w ou ld h a v e accesses a l a r g e n um ber o f r e c o r d s . t o setlreset a larg e n um be r of l o c k s , hence in cu rri ng t o o m any times t h e c o m p u t a t io n a l ov e r h e a d o f a c c e s s i n g t h e l o c k su bs ys te m , a n d t h e s t o r a g e o ve rh ea d o f r e p r e s en t i n g a lock i c memory. coarse lockable un it f o r e xa mp le a f i l e ) is p r o b a b l y c o n v e n i e n t f o r a t r a n s a c t i o n w h i c h a c c e s s e s m an an y r e c o r d s . B o w ev e r, su ch a c o a r s e u n i t d is c r ii n in a t es a g a i n a t t r a n s a c t i o n s w hich o n l y w an t t o l o c k o n e member o f t h e f i l e . From t h i s d i s c u s s i o n t f ol lo w s t h a t i t would be desirable t o h ave l o ck ab le un its of differen t g r a n u l a r i t i e s c o e x i s t i n g i n t h e same s y s t e m . In th e

f o l lo w i n g a l o c k p r o to c o l sa tis fying the se r e q u ir e m e nt s be described. Related i m p l em e n t a ti o n issu es of s c h l d u l in g , g r a n ti n g and converting l o ck requests a re no t I] d i s c u s s e d . T h e y were c o v e r e d i n a c o m p a n i o n p a p e r w i l l

~ i e r a r c h i c a l ocks: t h e set of ra sourc e s t o be loc ke d is Note t h a t t h e c o n c e p t o r g a ni z ed o f h i e r a r c h y is used i n t h e c o n t e x t o f a collection o f r e s o u r c e s a nd h as n o t h i n o t o dow ith the d a ta m o d e l used i n a d a ta b a s es y s te m . The hierarchy of F i g u r e 1 m ay b e suggestive. adop t th e not atio n a t h a t e ac h l e v e l o f t h e h i e r a rc h y is given n o d e t y p e w h ic h is a g e n e r i c name f o r a l l t h e no de i n s t a n c e s of t h a t t yp e. F or e xa m pl e, t h e da ta base has n o d es of t y p e area a s its immediate descendants, e a c h area i n t u rn h a s nodes o f ty pe fi le a s its i m m e di a te d t s z e n d a n t s e a c h f i l e h a s n o d e s o f t y p e r ec or d a s and a its i m me di at e d e s c e n d a n t s i n t h e h i e r a r ch y . Since t is h i e r a r c h y e ac h n o de h a s a u n i q u e p a r e n t . e

w

l l

assume t h a t in a hierarchy.

first

 

BASE

DATA 1

AR

EAS

FI L RECORDS

F i g u r e 1.

A

s a m pl e l o c k h i e r a r c hy .

E ac h n od e o f t h e hierar chy can be l o c ke d . If one requests e x c l u s i v e a c c e s s (X) t o a p a r t i c u l a r n od e, t h e n w hen t h e r e q u e s t is g r a nt e d, t h e r e q u e s t o r h a s e x c l u s iv e access t o that n o d e nd I f o ne implicit& e a c h of descendants. r e q u e s t s s h a re d c c e s s (S) t o a p a r t i c u l a r n od e , t h e n w whh e n t h e r e q u e s t i s g r a n t e d , a c c e s s the requestor has shared t o tha t n o d e nd i m p l i c i t l ~ o each descendant of that node. T h e s e two a c c e s s m oodd e s l o c k a n e n t i r e s u b t re e r o ~ t e d t t h e r eq ue st ed n ode.

I

Our go al is t o fin d s o m e t e c h n i q u e f o r im~llitly l o c k i n g an I n e n t i r e s u b tr e e. o r d e r t o l oc k s u b tr a e r oo te d a t node in share o r exclusive mode it is i m po rt an t t o p re v en t share o r e x c l u s i v e l o c k s on t h e a n c e s t o r s o f R w h i c h w o ul d i m p l i c i t l y l o c k f and its descend ants. H en ce a new a c c e s s m ode, i n t e n t i o n _one I) is introdu ced. I n t e n t i o n m ode i s u s e d t o V a g q l ( l o c k ) a l l a n c e s t o r s o f a n o d e t o b e l o c k e d i n s h a r e or e x c l u s i v e m ode, These tags s i g n a l t h e f a c t t h a t l o c k i n g i s b e i n g d o n e a t a f in er w l ev e l a nd p re v en t i m p l i c i t o r e x p l i c i t e x c l u s iv e or s h a r e l o ck s o n t h e ancestors. The p r o t o c ol t s h a r e m oodd e i s l o c k n o de R i Figure 1, t o

o l o c k a s u b t r e e r o o te d a t node R i n e x cl us iv e o r t o l oc k a l l a n ce s to rs o f R i n i n t e n t i o n mode a n d t o n e x c l u s i v e o r s h a r e m ode. S o f o r e x a m p le u s i n g a lo ck particular f i l e one s h ou l d o b t ain i n t en t i o n

ar ec qc ue es ss t t eo x tc hl ue s id va et a b( ao sr e , s ht oa r et h) e aac rc ee ass c to on t a ti nh ien gf i tl he e fi ti sl ee l fa n d T t hheins i m p l i c i t ly l o ck s a l l r e c o r d s o f t h e f i l e i n e x c l u s iv e (or s h a r e ) mode.

W s a y t h a t tw o l o c k r e q u e s t s f o r t h e sa me n od e by tw o d i f f e r e n t t r an sact i o n ar e co r n p ati u s if they can be g r a n t e d c o n c u r r e n tl y . T h e m ode o f t h e r e q u e s t d e t e r m i n e s i t s c o m p a t i b i l i t y w i t h r e q u e s t s by o t h e r The X S made transactions. t h r e e m oodd e s : and I are incompatible

ui th

o ne

g r a n t ed t o g s t h s r and d i The

Share

co m pa tib ili tie s mode allows

another st in ct I

but

distinct

S

re qu es ts

may

be

r e q u e s t s may b e g r a n t e d t o g e t h e r .

am ong m oodd e s d e r i v e read ing but no t

f r om their semantics. m o d i f i c a ti o n of th e

 

corresponding resource by the requestor and by othe r tr an sa ct io ns . T he s e m a n t i c s o f e x c l u s i v e m ode i s t h a t t h e g r a n t e e m ay r ~ a d n d m o d i f y t h e r e s o u r c e a n d n o o t h e r t r a n s a c t i o n n a y r e a d or m od ify t h e r e s o u r c e w h i le the exclusive lock The i s set. resson fo r d i ch o to m i zi n g s h a r e a nd exclusive access that is sev eral share requests can be g ra n te d c o n c u rr e n tl y are c o m p a t i b l e ) wh er ea s an ex clu siv e req ue st c o mp a t i b l e w i t h is n o t a ny ot he r request. I n t e n t i o n mode was i n t r o d u c e d t o be i n c o m p a t i b l e w i th s h a r e a n d e x c l u s i v e mode ( t o p r e v e n t s h a r e a n d e ~ c l u s i v e locks). How ever, intent ion n od e i s c o m p a t i b l e with it se lf since t w o t r a n s a c t i o n s h a v in g i n t e n t i o n access t o n ~ d e a S o r mode a n d w i l l s x p l i c i t l y lo ck d es ce nd an ts o f t h e node i n X, thereby w i l l eit h er be c o m p a t ib l e w ith o ne a n o t h e r o r w i l l be s ch e d u l e d on t h e b a s i s o f t h e i r r e q u e s t s at t h e f i n e r l ev e l. For e x a m p l e , two t r a n s a c t i o n s c a n b e c o n c u r r a n t l y g r a n t e d t h e data b a s e a n 3 so me area a nd so m e f i l e i n i n t e n t i o n mods. I n t h i s case the ir e x p l i c it l oc ks o n r ec or ds i n the f i le w i l l reso lve any c o n f l i c t s am o ng t h em . T he n o t i o n o f i n t e n t i o n m od od e i s r e f i n e d t o jg_tggion s h a r e n ~ d e a nd in te nt io n exc lus ive m ode IX) f o r t wo r ea so n s: th e IS) i n t e n t i o n s h a r e mo mo de o n l y r e q u e s t s share or intention share locks n o d es o f t h e tree r e q u e s t s an e x c l u s i v e a t t h e l o w er i.e. n e v e r l o c k be lo w t h s i n t e n t i o n s h a r e n o d e ) . S i n c e r e a d - o n l y i s a common form of acce ss t w i l l be prof i t a b l e t o d i s ti n g u is h t h i s for g r e a t e r c o n cu r re n cy . S e c on d ly , i f a t r a n s a c t i o n h a s an i n t e n t i o n sh arc lock on a n o d e t h i s t o t c an c on ve rt a share lock at a l a t e r time, b u t o n e c a n n o t c o n v e r t a n i n t e n t i o n e x c l u si v e l o c k t o a share l o c k o n a n ~ d e see [ f o r a d i s cu s s i o n o f t h i s p o i nt ).

_ani one fu rth e r refin em ent of modes, n am e ly W reco gniz s i n t e n t i o n e x c l u s i v e m ode ( S I X ) . S u pp o se one tra ns ac tio n wants t o e ad a n sn tire subtree and t o u p d a te p a r t i c u l a r n od es o f th at su btr ee. U s i ng t h e m od e s p r o v i d e d so f a r w ou l d h a v e t h e t optio ns of: a) r e q u e s t i n g e x c l u s i v e access t o t h e r o ot of the s u b t r e e a n d d o in g n o f u r t h e r l o c k in g o r (b) r e q u es t in g i n t e n t i o n exclusive cce ss t o t h e root o f t h e s u b t r e e a n d e x p l i c i t l y l o c k i n g th e l ow e r n od es in intention, share o r exclusive mode. A l t e r n a t i v e (a) h a s lo w c o n c u r re n c y . If o n l y a small f r a c t i o n o f t h e r e a d n od es a r e u p da te d t h e n a l t e r n a t i w b) ha s high locking overhead. The c o r r e c t acces s m od e w o ul d b e s h a r e access to the s u h t r e e t h er e by a ll o w in g t h e t r a n s a c t i o n t o r e a d a l l n o de s o f t h e s u b t r e e w i th o ut f u r t h e r l o c k in g i n t e n i o n e x c l u s i v e access t o t h e s ubtr ee t h er e by a l lo w i n g t h e t r a n s a c t i o n t o set exclusive l o c k s on t h o s e n o d es i n t h e s u b t r e e which a r e t o b e u p da te d a nd I X or SIX l o c k s o n t h e i n t e r v e n i n g n od es . S i n ce t h i s is such a c o mm m m on on c a s e , S I X i nnoo ddee i s i n tr o d u c ed fo r t h i s p ur po se. is It com patible with si nc e other t r a n s a c t i o n s r e q u es t i ng IS I S m ode mode w i l l e x p l i c i t l y l o ck l ow er n od es i n I S o r S mode t h e r e b y X m od e) avoiding any updates IX o r p r o d u c e d by the S X mode tr a n s ac ti o n . H ow ev er S IX mode i s n o t c o m p a t i b l e w i t h I X , S, SIX o r mode re q ue st s. An e q u i v a l e n t a p p r o a c h w o u l d be t o c o ns i de r IS,IX,S,X) o n l y f o u r m od ss b ut t o a ss um e t h a t a t r a n s a c t i o n c a n r e q u e s t b o t h S a n d IX l o c k p r i v i l e g e s on a r e s o u r c e .

 

Table 1 gives th e comp atibility of t h e r e q u e s t modes, w here f o r c o m p l e t e n e s s we h a v e a l s o i n t r o d u c e d t h s ~III mode NL) which represents th e a b s e n c e of req ue sts of a resource y a transaction.

T a b l e 1.

C o m p a t i b i l i t i e s am ong access modes.

T o s u m m 3 r i z z , we r e c o g n i z e s i x m o d e s o f a c c e s s t o a r e s o u r c e : NL:

G iv es n o a c c ess t o a n o d e i. e. request of a resource.

IS:

G i v s s i n t e n t i o n s h a r e access t o t h e r e q u es t e d n od e a nd a ll o w s th e requestor t o l o c k d esce nd an t n od ss i n S or IS m ~ d e . It d o e s o i m p l i c i t l o ck i ng . )

I X :

Givss i n t e n t i o n e x c l u s i ~ ~ c c e ss t o t h e r e q u e s t e d a ll ow s t h e r e q u e s t o r t o e x p l i c i L l p l o ck d es ce nd an ts SIX, I X o r I S mode. i m p l i c i t l oc k in g .) It d o e s

S:

r e p r e s e n t s t h e a bs en c e

of a

n od e a nd in X S

G iv es s h a r e a c c e s s t o t h e r e q u es t e d no de and t o a l l d e s c e n d a n t s of t h e r e q u est e d n od e w i th o u t se tti ng fu rth er l o c k s. It i m p l i c i t l y sets S l o c k s on t h e r e q u e st e d a l l d e s c e n d a n t s of node.)

SIX:

G i v es s h a r s a n d j~~r~ggtion e x c l u g i v g a z c e s s t o the requested node. In p a r t i c u l a r it i m p l i c i t l y l o c k s 3 d e s c en d a n t s o f t h e n o d s i n s h a r e mode a n d a ll ow s t h e r e q u e s t o r t o e x p l i c i t l y l o c k d e sc e nd a nt n od es i n X SIX o r I X mode.

X:

G iv 2s e x c l u s i v ~ a c c e s s t o t h e r eq ue st ed node and t o all descendants of t h e r e q u es t e d node w i t h ou t s e t t i n g fur the r locks. It implicitly sets X locks on all descendants.) L oc k in g l o w e r n o d e s i n S o r I S m ode w ou ld g iv e n3 in cr ea se d access.

mode i s t h e w e a k e s t n o n - n u l l f or m of a c c e s s t o a r e s o u r c e . It carries f ew er p r i v i l e g e s t h a n IX o r S modes. mode a l l ~ w s S . I X IX S S I X a n d X ms e l o c k s t o be s e t o n d a s c e n d a n t n o d e s w h i l e S allows r e a d only access t o mode a l l descen dants of t h e n od e I S

SIX

S w t o fd ue r t h eh er n lc oe c tk hi ne g n. am m )o .d e c Xa r m r ioed se ti h o fi t hI oX u m am e S I X s e t hp re i v iml oe sgt e ps r oi vf i l e ga en dd f o r m o f access a nd a l l o w s r e a d i n g a nd w r i t i n g of a l l d e s c e n d a n t s

 

of a node withou t fu rth e r locking. in the pa rtial order l a t t i c e ) of Y ote tha t t i s not to ta l a incomparable.

H e n c e t h e m o d e s can b e r a n k e d p r i v i l e g e s show n i n F i gu r e 2 o rd er since a ~ d a re I X

SIX

F i g u r e 2.

The p a r t i a l o r d e r i n g o f m odes by t h e i r p r i v i l e g e s .

The i m p l i z i t l o c k i n g o f n o d es w i l l n o t w o rk i f t r a n s a c t i o n s are a ll ow ed t o le ap in to t h e m i d dl e o f t h e t r e e a nd begin locking nodes at r a n do m . T he im pl ic it locking im p lie d by the S and X n o d e s d e p n d s on a l l t r a n s a c t i o n s o b e y i n g t h e f o l l o w i n g p r o t o c o l: a) E e f o r e r e q u e s t i n g a n S o r IS lock on a node, all ancestor n o d e s of t h e r e q u e s t e d node m u st b e h e l d i n I X o r I S mode y t h e r e q u e st o r .

b) B e f o r e r e q u e s t i n g a n X SIX o r I X l o c k a n a n o d e , a l l a n c e s t o r n o d e s o f t h e r e q u e s t e d n o d e m u s t b e h e l d i n S I X o r IX m o d e by the r e q u e s t o r . c) L o c k s s h o u l d b e r e l e in any o rd er ) o r locks are not held a lo we r l o c k a f t e r

ased ei th e r a t t h e end o f t h e tr a n s a c t io n i n lea f t o r o o t o rd er . I n p a rt ic u la r, i f t o e nd o f t r a n s a c t io n , o n e s h ou ld n o t h ol d releasing its ancestor.

requested root t Lgqf, released To paraphrase t h i s , locks leaf t o r oo t. N o ti ce t h a t leaf nodes are never requested in i n t e n t i o n mode s i n c e t h e y h a v e n o d e s c e n d a n t . ~ . S e v e r a l e x am p ls s : t

ma7

be

instructive t o

g iv e

a few

e x2 mp lo s o f

hie rarchi cal

 

r e q u e s t s sq u e n c a s: To l o c k r e c o r d R f o r r e a d : l o c k d a t a - b as e w i t h m od od e IS l o c k a r s a c o n t a in i n g R w i t h mode IS lock f i l e c o n t a i n i n g R w i t h mode I S l o c k r e c or d R w i t h mode S D on t p a n i c , t h e t r a n s a c t i o n p r ob ab ly a l r e a d y h a s

t h e d a t a b ase ,

f i l e

ar ea and lock. To l o c k r e c o r d R f o r w r i t e - e x c l u s i v e a c c e s s : I X l o c k d a ta - b a se w i t h mode I X lock area containing R with mode I X lock file containing R w i t h mod2 X lock record R w i t h mode N ote t h a t i f t h e records of t h i s and t h e p r s v i o u s e xa m ple a r e d i s t i n c t , e ac h r e q u e s t ca n be g r a nt e d s i m u lt an e ou s ly t o d i f f e r e n t t r a n s a c t i o n s e v e n t h o u g h b o t h r e f e r t o t h e s am e f i f e . To l o c k a f i l e F f o r r e a d a n d write a c c e s s : l o c k d a t a -b a s e I X with mode loc k ar ea co nta inin g F w i t h m ode I X l oc k f i l z P with mode X S i n c e t h i s r e s e r v e s e x c l u s i v e a c c e s s t o tht f i l e , u s e s t h e sam e f i l e as t h e p r e v i o u s t w o e x a m p le s t r a n s a c t i o n s w i l l have t o wait.

i f t

t h i s request

or

the other

T o l o c k a f i l e F f o r c o m p l e t e s c a n a nd o c c a s i o n a l u p d a te : lock data-base I X w i t h mode lock area containing F I X with mode lock fils F w i t h m oodd e S IX IX Th er eaf ter , p ar t i cu l a r records in F can bs l o c k e d f o r u p d a t e by l o ck i ng r e c or d s i n X mo d e. Notice th at ( u nl ik e t h e p r e vi o us e xa m ple ) t h i s t r a n s a c t i o n i s c o m p a t i b l e w ith t h e first example. T h i s i s t h e r e a s o n f o r i n t r o d u c i n g S IIX X m ode. To

quiesce

data

t h e

base

X.

lNooct ek dt ha 3t at tb ha is es lwoi ct hk sm eo dv ee r y o n e D i r e c t e d p~q

i

else

out.

q r a p h ~ f locks:

The n o t i o n s s o f a r i n t r o d u c e d c an be g e n e r a l i z e d t o w ork f o r DAG) directed a c y c l i c g ra p hs of r e s o u r c ? ~ r a t h e r t ha n s im p ly A a h i e r a r c h i 2 s of r e s o u r c e s . tree is s i m p l e DAG. The key l o c k o b s e r v a t i o n is t h a t t o im p l i c it l y o r e x pl i, -i tl y a node, one s h o u ld l o c k l l t h e p a r e n ts of t h e node i n the DAG an d so by i n d u c t i o n l o c k 311 a n c e s t o r s o f t h node. I n p a r t i c u l a r , t o l oc k a s ub gra ph o ne must i z p l i c i t l y o r e x p l i c i t l y l o c k a l l a n c e st o rs o f t h e s u b g r a p h i n t h e a p p r o p r i z t e mods ( f o r a t r e e t h e r e i s o n l y o n e structure paren t). To g i v e a n e x a n p l e of a n o n - h i e r a r c h i c a l im a gin e t h e

locks a r e oiganized

as

i n F ig ur e

3

 

D

T

BASE

AREAS

---I- -FILES

F i g u r e 3.

I INDICES

non-hierarchical

l o c k g ra p h .

t h a t areas a r e f lp h ys ic al l* n o t i o n s a n d t h a t f i l e s We p o s t u l a t e ind ices and r e c o r d s T he d a t a base is a are l o g i c a l n o t io n s . collec tion o f areas. Each area i s a c o l . l e c ti o n o f f i l e s and in di ce s. E ach i nd e x i n t h e f i l e h a s a c o rr e sp o n di n g same a r e a . E ac h r e c o r d b e l o n g s t o soma f i l e a n d t o its corresponding index. r s c o r d i s c om p ri se d o f f i e l d v a l u e s a n d some f i e l d i s i n d e x e d b y a sso c i a t ed u i t h th e f ile c o n t ai n i ng t h e r ec or d. T he the i nd ex f i l e g iv es a s e q u e n t i a l access p a t h t o t h e r e c o r d s and t h e i n d e x g i v e s an a s s o c i a t i v e access p ath t o t h e r e c o rd s b as ed on f i e l d v al ue s. S in ce individual fi el ds are never locked, they do not a p pe a r i n t h e l o c k g ra ph . T o writ? a r e c o r d R i n f i l e with index I: lock data base w i t h mode I X lock area containing F w i t h mode I X l oc k f i l e P with node I X l o c k i n de x w i t h mode I X l o c k r e c o rd R w i t h mode X N o t e t h a t 212

p a t h s t o r ec or d R are

could lock F and I i n i n e x c l u s i v e m od od e .

l oc k ed .

Altern altive ly,

one

e x c l u s i v e mode t h e r e b y i m p l i c i t l y l o c k i n g

To g i v e a m o r e c o m p l e t e e x p l a n a t i o n we o b s e r v e l oc ke d e x ~ l i c i z _ l p by r e q u e s t i n g i t o r implici e x p l i c i t l o c k s o n t h e a n c e s t o r s of t h e n o d e ) i n SIX, X However, t h e de finitio n of IS IX S t h e p r ot o co l s f o r s e t t i n g e x p l i c i t l o c ks h av e follows:

R

t h a t a n o d e ca n be t l y (by a p p r o p r i a t e o n e o f f i v e m od od e s : i m p l i c i t l o c k s a nd t o be e xte nde d a s

node q r a n t d ig S mode t o a transaction if a t is j w i c i t l y l e a s t one o f its p a r e n t s is i m p l i c i tl y o r e x p l i c i t l y ) g ra nt ed t 3 ---the t r a n s a c ti o n in S y induction th t means t h a t S I X o r X mcde. a n c e s t o r s m us t b e explicitly g r a n t e d i n a t l e a s t o n 2 o f t h e node s S , S I X o r X mode t o t h e t r a n s a c t i o n . nods i s i m p l i c i t l ~ g r a n t e d A

X

mode i f

222

of i t s p a r e n t s are

 

(i s p l i c i t l y o r e x p l i c it l y ) g ra nt ed t o t h e t.r an sa ctio n i n X node. tha t a l l nodes ey i n d u z ti o n , t h i s i s e q u iv a l en t t o t h e c o nd i ti o n i n s om e c u t set o f t h e c o l l e c t i o n of a l l p a t h s l e a d i n g fro m t h e node t o th l m o t s of t h e g ra p h a re e x p l i c i t l y g ra ct ed t o t h e transaction i m o d e a n d a n c e s t o r s n o i e s i n t h e c u t set X all of a r e e x p l i c i t l y g r a n t e d i n I X o r S I X m od od e . From F i g u r e 2 , g r a n t e d i n I S mode a node is i m p l i c i t l y i f it i s i m p l i c i t l y g r a n t e d i n S mode, a n d a no de is i m p l i c i t l y g r a n t e d i n I S , I X , S a n d SIX mode i f i t i s i m p l i c i t l y g r a n t e d i n X mode.

( a)

Before req ue sti ng an S or IS lock on a n o d e, o n e should request at least one par en t ( an d by i n d u c t i o n a p a t h t a r o o t ) i n I S ( o r g r e a t e r ) m ode. A s a consequen ce none of t h e ancestors along th is p a th c an g ra nt ed t o a n o th e r be t r a n s a c t i o n i n a m ode i n c o m ~ a t i b l e i t h I S .

(b)

F ef or e r~ qu es tin g X, S IX o r mods a c c e s s t o a n o d e, o n e s h o u ld r e q u e s t i n IX (or greater) all parents of t h e n od e mode. s a consequence a l l a n c e s t o r s w i l l b e h el d i n I X (or g r s a t e r m ode) a n d c a n n o t b e h e l d by o t h e r tra ns ac tio ns i n a m o d 2 incompatible w i t h I X

(i.e.

SIX,

S,

X

a t t h e end o f t h e t r a n s a c t i o n c) L o c ks s h o u l d b e r e l e a s e d e i t h e r ( in a ny o r de r ) o r i n leaf t o r o o t o rd er . I n pa rticula r, if locks are not held t o th e end of t r a n s a c t i o n , o n2 s h o u l d n o t h ol d a l o we r l o c k a f t e r r e l e a s i n g its a n c e s t o r s .

giv e an e xa m pl e using Figure se q u en t ia l s ca n o f a l l 3, a r e c o r d s i n f i l e F n ee d n o t u s e a n i n d e x so o ne c a n g e t an i s p l i c i t s h a r e l o c k o n ea c h r e c o r d i n t h e f i l e by:

To

lock data base lock area containing F lock file P

w i t h m od e w i t h mode w i t h mode

IS

=

IS

=

S

=

This gives im pli ci t S mode access t o r ec or ds i n F. a11 C o nv er se ly , t o r e a d a r e co rd i n a f i l e v i a t h e i n de x I f o r f i l e F o n e n e e d n o t g e t a n i m p l i c i t o r e x p l i c i t l o c k o n f i l e F: lock data base lock area containing lock index I

R

wit h mode w i t h mode w i t h mode

= = =

IS

IS S

This again give s im pl ic it m ode a c c e s s t o a l l r e c o r d s i n i n d ? x I (in file F locked f y I n b o th t h e s e cases, _only p t readinu. E ut t o i n se r t , d e l e t e o r update a record R i n f i l e F with index on m u s t g e t a n i m p l i c i t ar s x p l i c i t l o c k o n a l l a n c e s t o r s of R . how T h e f i r s t e x a m p l e o f t h i s s e c t i o n s h o v e d ho

an ex pl ic it

X

I

lock on

 

a rr5cor3 i s o b t a in e d . To g e t an i m p l i c i t X l o c k o n a l l r e c o r d s i n a file one can s i m p ly l o c k t h e i n d e x a nd f i l e i n X m od e , o r l ~ c k th e are a i n r od ?. The l a t t e r e x am p le s a ll o w h u l k l c a d o r u p d a t e of a s i n c e a11 r e c o r d s i n th e file f i l e w i th o u t f u r t h e r l o c k in g a r a i m p l i c i t l y g r a n t e d i n X mode. Proof

of

~ g u i v a l e n c ? of t h e l o c k p r o t o c o l .

W w i l l now p r ov e t h a t t h e d e s c r i b e d l o c k protocol is equivalent to a c o n v e n t i o n a l o n e w hic h u s e s o n l y two m o d e s ( S a n d X aod w hi c h l o c k s o n l y a t o m i c r e s o u r c e s ( l e a v e s o f a t r e e o r a d i r e c t e d graph)

L e t G = N,A) b e a f i n i t e ( d i r e c t e d ) grr~_h w h e r e N i s t h e s e t o f s t o f nodes and A is t h e arcs. G i s ss s um e d t o be withaut circuits i.e. t h e r e i s no n o n - n u ll p a t h l e a d i n g f r om a n od e n t o itself). n o d e p i s a p a r e n t of a n o d e n a nd n i s a c h i 1 2 of p A i t h e r e i s ari a r c f r o a p t o n . A node n i s a s p u r c e ( s in k ) i f n has no parents ( no c h i l d r e n ) . Let SI be th e set o f sinks of G An _ a n _ c , ~ _ s r ~fx n o d e n i s a n y n o de ( i n c 1 ud i r .g n) i n a p a t h f ro m a s ou r c e t o n. A n o d e - s l i c e o f a s i n k n i s a c o l l e c t i o n of n o d e s s uc h t h a t o a ch p a t h f ro m a s o u r c e t o n c o n t a i n s a t least one of t h e s e n o de s.

= {NL,IS,IX,S,SIX,X] and C t h e c o m p a t i b i li t y m a t r ix MxM->{YES, N O d e s c r ib e d i n T a b l e 1. W e : mxm->{YES,NO) the restriction of t o m = w i l l call c C {NL,S,X]. We a l s o i n t r o d u c e t h e s e t o f l o c k m o d e s

A

M

l o c k - q g g ~ h i s a m a p p i n g L : N >M s u c h t h a t : if n) {IS ,S t he n e i t h e r n is a so u rc e o r t h s r e e x i s t s a pa re a t p of n s uc h t h a t By i n d u c t i o n L (p) € {IS, IX, S, SIX,X] t h e r e o x i s t s a p a t h f ro m a s o u r c e t o n s u c h t h a t L t a k e s o n l y v a l u e s i n (IS,IX,S,SIX,x) o n it Equivalently L is not equal t o NL o n t h e p a t h . b) i f L n) € {IX,SIX,X) t he n e i t h e r n i s a r o o t D r f o r all 3)

€ pi na dr eu nc tt si o pn l . L. . p tka ko ef s n owe n l yh a v ve a L l u( pe si ) i n an cs sto rs of n.

{IX,SIX,X]

{IX ,SIX ,X )

1

on

k

a) l l.

t hBye

m ap o f t h e The i n t e r p r e t a t i o n o f a l o c k - g r a p h i s t h a t it g i v e s a p a r t i c u l a r t r an s a ct i o n o b se r vi n g t h e s i x e x p l i c i t l o c k s h e l d by a s t a t e l o c k p r o t o c 3 1 d e s c r i b e d a b o ve . T he n o t i o n o f p r o j e c t i o n o f a l o c k - g r a p h i s now i n t r o d u c e d t o m o d e l t h n s e t o f i m p l i c i t l o c k s o n a to m i c r e s o u r c e s c o r r e s p o n d i n g l y a c q u i r e d by a t r a n s a c t i o n . T h e ~~o~_e_ce g o f a l o c k - g r ap h L is the m ap pi n g c on st ru ct 2d a s f o l l ~ w s : i there e x i s t a a) 1 n ) = X n o d e - s l i c e { nl s ) o f 11 i=l L(ni)=X ns) b) 1 n)=S i f a) ail i s n o t sntisf e d a n d t h e r e exist o f n s u c h t h a t L ( a) € (S,SIX,X]. b) a re n o t s a t i s f i e d . c) 1 n ) =NL i f a) and

.

..

1:

SI->m

s u ch t h a t

ancestor a

 

Two l o c k - g r a p h s L1 an d L2 a e s ai d t o compatible be C L l n ), L2 n) )= Y E S f o r a l l n € S i m i l a r l y tw o prajections N. a n d 1 2 a r e c o m p a t i b l e i f c 1 l n ) , 1 2 n ) ) = Y E S f o r a l l n € SI We a r e n o w

i n a position t o prove t h e foll ow ing

if

11

T h e o re m :

t w o l o c k - g r a p h s L 1 a n d L2 a r e c o m p a t i b l e t h e n t h e i r p r o j e c t i o n s 1 2 a r e c o m p a t i b l e . I n o t h e r w o rd s i f t h ? e x p l i c i t l o c k s s e t b y tw o t r a n s a c t i o n s ar e n o t c o n f l i c t i n g t h e n a l s o t h e t h re e -s t a t e l o c k s i m p l i c i t e l y a c qu i re d are n o t c o n f l i c t i n g f

11 a n d

P r o o f : A ss ss u m e t h a t 11 a nd 1 2 a r e i n c o m p a t i b l e . W want t o p r ~ v e t h a t L 1 and L2 are i n co m p a ti b le . By d e f i n i t i o n o f c o a p a t i b i l i t y t h e r e m us t e x i s t a s i n k n s u c h t h a t 1 1 n ) =X a n d 1 2 n ) € {S X or vice vsrsa) By definit ion of projection there m ust e x i s t a nod e-sl ice { nl s) of th at Ll nl)= ns) =X. n s uc h =Ll A 1so t h e r e m u s t e x i s t a n a n c e s t o r n o o f n s u c h t h a t L2 L2 n 0 ) € { S , S I X , X ) . From t h e d ~ f i n i t i o n f l o c k - g r a p h t h e r e i s p a t h P1 fr o m a s o u r c e t o n o o n w h i c h L 2 d o e s n o t t a k e t h e v a l u e NL,. PI inter se cts incompatible sinc e If

n u ll

v a l u s o f L2

ni)

th e n o d e- s li c e L l n i ) = X w hi c h

at n i then L1 an d L2 w i th t h e is incompatible

a re n on

H en ce t h e t h e o re m i s p r o v e d .

A l t e r n a t iv e l y t h e r e is a p a t h P2 fr om n o t o the sink n w hich intersects th e no d e- sl ic e ni. From th e definitio n of at lock-graph L t a k e s a v a lu e i n { IIX X ,S , S IX I X ,X ,X ) o n a l l a n c e s t o r s o f n i . In partic ular L l n 3 ) € { IX ,S IX ,X ) . S in ce L2 n0) € { S , S I X , X ) we hav e C Ll nO),L2 nO))=NO. Q. E . D.

Thus we have p re t e n d ed t h a t the lack g r a ~ h s static. far H o w ev ev e r , e x a m i n a t i o n o f F i g u r e su gg es ts otherwise. Areas, f i l e s a n d indices a r e dynamically created and destroy ed, a nd o f c o u r s e are

dr ea ct ao r bd as s e all.)

If

c o on nt li yn u ar lel ay d , i nt hs ee nr t e dt h, e ur pe d iast e d n, a a n de e d e l ef toe rd .l o c k i n g t ha et is

lock p r o to c o l f o r s u c h o p e r a t i o n s is n i c e l y d e m o n s t ra t e d b y t h e i m pl em e nt at io n of index in te rv al locks. Rather than being f o rc e d t o lock en tire indices or individual r ec or ds , we w o u l d l i k e t o be a ble t o lo ck a l l = c o r d s w it h ce rt ai n i n d e x v a l u e; f o r exam ple, l oc k a l l r e c o rd s i n t h e bank a c co u n t f i l e w i th t h e l o c a t i o n f i e l d e q u a l t o Napa. T h e r e f o r e , t h e i n d e x is p a r t i t i o n e d i n t o l o c k a b le kay valu e int erv als . E ac h i n d e x e d r e c o r d belong s t o a p a r t i c u l a r in de x i n t e r v a l and a l l r ec or ds i n a f i l e w it h t h e sam e f i e 1 3 v a l u e on a n i n d e x ed f i e l d w i l l b e lo n g t o t h e sa ne key v a l ue i n t e rv a l N ap ap a a c c o u n t s w i l l b e l o n g t3 t h e same e . a intsrval). This now s t r u c t u r e i s d e p i c t e d i n F i g u r e 4 . The

l

DATA

BASE

 

  AR

EA S

-

FILE I

I N

DICES

INDEX V L U E INTERVALS

U N

I N

DEXED

FIELDS Figure

ir

I

INDEXED FIELDS

The l o c k g r ap h w i t h k e y i n t e r v a l l o c k s .

T he only subtle aspect of Figure 4 s th e dichotosy b etw ee n indlxed a n3 u n- in de xe d fie ld s and th e fact that a k ey value interval s t h paren t of both t h e r e c o r d s . n d ts i n d e x e d f i e l d s . S i n z s t h e f i e l d v a l u e a n d r e c o r d i d e n t i f i e r ( d a t a b a s e k ey ) a p p e a r in t h e in se x, o ne c a n r e a d the fie ld dir ec tly i.e. u i t h ~ u t touching th e rscor d) H en ce a k e y v a l u e i n t e r v a l s a paren t of t h e c o r r es p o n d in g f i e l d v a l ue s . On th e othe r h a n d, t h e index l q p o i n t s f l v i a r e c o r d i d e n t i f i e r s t o a l l r e c o r d s w i t h t h a t value a n d so s a p a r e n t o f a l l r e c o r d s w i th t h a t f i e l d v alu e. DAG, cS ai nn c be e F ui sg eu dr e t o dl oe cf ki n et hs e a n o d e s to hf e t hp er o gt or ac pohl . o f Htohwee vperr e, v ii to u ss h os eu cl dt i ob ne e x t en d e d a s f o l l o n s . W hen a n i n d e x e d f i e l d s u p d a t e d , i t a n d t s parent record move f r o m one index int erv al t o another. So f o r e x a m p l e w he h e n a N ap ap a a c c o u n t H e le na br a nc h , t h e s moved t o t h e S t . a c c o u nt r e c o r d a n d t h e Napa i n t e r v a l o f t s l o c a t i o n f i e l d Itleave th e loc ati on index and j o in tq t h e S t . H e le na i n d e x i n t e r v a l . W hen a new record l * jo in su t h e i n t e r v a l co nt ai ~i ng he s i n s e r t e d it new f i e l d v a l u e a n d a ls o it w j o i n s ll t h e file. D e l e t i o n r em o v es t h e r e c o r d f r o m t h e i n d e x i n t e r v a l a n d from t h e f i l e .

The l o c k p r o t o c o l f o r ch a ng i ng t h e p a r e n t s o f a n o d e ( d)

Befor e

n o de i n th e lo i m p l i c i t l y o r explicitly g r a n t e d t s new p o s i t i o n i n t h e g r a p h . m ov ov e d i n s u c h a w ay a s t o c r e a t e moviny

a

ck

graph, t h i n X mode i n Further, t h e a cycle i n th

is

e n od e inust be both ts o l d and n o d e m u s t not b e e g ra p h .

 

So t o c a r r y o u t t h e e x am p le o f t h i s s e c t i o n t o m o v e a N aapp a b a n k a cco un t t o t h e S t H e l e n a b r a n c h o n e w o u ld : lock data base n modo X l o c k a r e a c o n t a i n g a c c o u n t s i n m ode X l o c k a c co u n ts f i l e i n m ode X l o c k l o c a t i o n i n de x i n m ode X l o c k N apa i n t e r v a l i n mode I X l o c k St H elena i n t e r v a l i n mode X I X loc k record i n mode lock fi eld i n m ode X could get an implicit l oc k on the fie ld Alternatively on2 y r e q u es t in g e xplicit mode on the r e c o rd and index X locks intervals.

 

The data base consists of e n ti ti es which t o be are k mw n s t r u c t u r s d i n c e r t a i n ways. This structure i s b e s t th o u g h t of a s a s s e r t i o n s a b o ut t h e d a t a . E xa m ple s o f su ch a s s e r t i o n s a r e : Names i s a n i n d e x f o r T e l e p h o n e - n u m b e r s . 'T h e valu e of C o u nt - o f- x g i v e s t h e n um be r of employees i n department x. The dat a b a s e is s a i d t o be mnp tent if t s a t i s f i e s all its assertions [2] I n some th e d at a bas e must b ecom e cases t e m p o ra r il y i n c o n s i s t e n t i n order t o t ra n sf o rm t o a new t c onsiste nt state. F o r e x a m p le , add ing a new e m p l o y e e in vo lv es s e v e r a l a t o m i c a c t i o n s a n d t h e u p d a t i n g of' s e v e r a l fields. The d a t a b a s e m ay b e i n c o n s i s t e n t u n t i l a l l t h e s e u p d a t e s h a v e b e en completed. To c o p e w i t h t h e s e t e m p o r ar y i n c o n s i s t e n c i e s , s e q u e n c e s o f a to m i c action s are g r o up ed t o fo rm Transactions t r a n sa c tio g s. are t h e u n it s of consistency. T he y a r e l a r g e r a to m ic a c t i o n s on t h e d a t a ba se w hic h tran sfo rm t from o ne c o n s is t e nt sta te t o a new consistsnt Transa ctions preserve consistency. some state. f action of transaction fails then th e e nt ire transa ction is 'u nd on eq t h e r e b y return ing th e data b a s e t.o a consistent state. T hu s t r a n s a c t i o n s a ls o t h e u nits of' re c o v e ry . H ar dw ar e are f a i l u r e , s y s t e m e r r o r , d e a d lo c k , p r o t e c t i o n v i o l a t i o c s a n d p ro g ra m e r r o r a r e e ac h a source of such fa ilur e. The s y st e m Bay e n f o r c e th e consistency ass ertion s a n d undo a t r a n s a c t i o n w hich t r i e s t o l e a v e t h e d a t a b a se i n a n i n c o n s i s t e n t state. I f t r a n s a c t i o n s a r e r u n o n e a t a time t h e n e a ch t r a n s a c t i o n w l l see t h e c o n s is t e nt s t a t e l e f t b e h i n d by ts pre dec ess or. Bu t i f se v e r a l t r a n sa c ti a n s are sc he dule d concurre ntly then locking is required insure th at the inputs to 2ach t r a n sa c ti o n t o are consistent. Responsibility for r e q u e s t i n g and rele sing locks can be e i t h e r a s s u m e d by by t h e use r o r delegated t o th e s ys te m. User c o n t r o l l e d l oc ki ng results i n potentially d ue t o th e user's fewer l o c k s k no wle dg e o f t h e seman tics of th e data. o t h e r h an d, u s e r On t h e c o n t r o l l ed l o ck i ng r e q u i r e s d i f f i c u l t a nd potentially unreliable a p p l i c a t i o n p ro gr a m m in g. H en ce t h e a p p r o a s h tak en by sorne d a t a base systems is to use automatic lock p r o t o c o l s w hic h ins ure prote ction from g e n e r a l type s of i n c o n s i . s t en c i e s , w h i l e still r e l y i n g on h im s el f a g a i n s t o t h e r so u rce s o f the user t o protect inco nsis tenc ies. F o r e x am p le , a s y s t e m m ay a u t o m a t i c a l l y l s ck u p d3 te d r 2 c o r 3 s bu t no t r e c o r d s w h ic h a r e r e a d . S u ch a system p r e v en t s l o s t u p d a te s a r i s i n g from t r a n s a c t i o n backup. Sti ll , t he u s e r s ho uld e x p l i c i t l y l o ck r e c o rd s i n a r e a d -u p d a t e s e q u en c e t o insure that th e r e a d v a l ue d o es n o t c ha ng e b e f o re t h e actua l u p d at e . I n o t h e r w or ds , a u s e r i s g u ar a nt e ed a l i m i t e d a u t o m a t i c _ c g r ? s i st s t ,p ,p q c p . r h i s degree of c o n s i s t e n c y degree ~ m y be system w iidd ? o r t h e s y s t a a m a y p r o v i d e opti ons t o select it ( f o r i n st a n c e a lock p r o t o c o l n ay b e a s s o c i a t e d w ith a t r a n s a c t i o n o r with an

 

entity). now p r e s e n t s e v e r a l e q u i v a l e n t degrees

tile

defin iti un s of

f o u r c o n si s t en c y

Rn o u tp u t of transaction c o m m i t t e d when the write) a is t r a n s a c t i o n a b d i c a t e s t h e r i g h t t o * u n d o 1 t h e write t h e r e b y m a k in g t h e new v a l ue a v a i l a b l e t o a l l o t h e r t r a n s a c t io n s . 3 u t p u t s are s a i d t o b e u n co rn n it t e d r d i r t y i f t h e y a r s n o t y e t c o m m i t t e d by th e writer. C o n cu r re n t e x e c ut i o n raises t h e p ro ble m t h a t r e a d i n g o r w r i ti n g o t h o r t r a n s a c t i o n s 1 d i r t y d a t a m ay yield inconsistent data. U si ng t h i s n o t i o n o f defined as:

dir ty

data,

t h e d e g r e e s o f c o n s i s t e n c y may b e

Definition 1 D e g r e e 3 : T r a n s a c t i o n T sees d w r e e c on si st en cy i f : ( a) d o e s n o t o v e r w r i t e d i r t y d a ta o f o t h e r t r a n s a c t i 3 n s . t d o e s n ~ to m m i t a n y writes until completes a l l its writes i s . u n t i l t h e e n d of t r a n s a c t i o n EOT)). c) T d o e s n o t r e a d d i r t y d a t a f ro m o t h e r t r a n s a c t i o n s . (d) O t h er t r a n s a c t i o n s do n o t d i r t y any d a t a r e a d b y T b e f o r e T completes

b)

Degree (a) T (b) T c) T

2 : T r a n s a c t i o n T s e e s d-qree 2 cgng&ztency i f : d o e s n o t o v e r w r i te d i r t y d at a o f o t h e r t r a n s a c ti a n s . d o s s n o t c o m m i t a n y w r i t e s b e f o r e POT. d o es no t r e a d d i r t y d a t a o f o t h e r t r a n s a c t i o n s .

D e g r e e 1 : T r a n s a c t i o n T Sews dgqreg o n pi gt en cp i f : a) T d o e s n o t o v e r w r i t e d i r t y d a t a o f o t h u r t r a n s a c ti o n s . b ) T d o s s n o t c o m m i t a n y w r i t e s b e f o r e EO'I . D e g r e e 0: T r a n s a c t i o n T sees degree Q c o n s i s t e n c p i f : a) T d o e s n o t o v e r w r i t e d i r t y d a t a o f o t h e r t r a n s a c t i o n s . N o t e t h a t i f a t r a n s a c t i o n sees a h i g h d e g re e o f c o n s i s t e n c y t h e n t a l s o sees a l l t h e l o w e r d e g r e e s . T he se de fin iti on s hav e i m p l i c a t i o n s fo r transaction r ec ov er y. Trans3ctions ar e d i ch o to m i ze d a s recoverable tra ns ac tio ns w hich can undone without af fe ct in g oth er trans actio ns, and be u n r e c ov e r a b le t r s n s a c t_ i o_ n s w h i c h c a n n o t bt u nd on e b e c a u s e th ey h a v e c om m it te d d a t a t o o t h e r t ra ns ac ti on :; and t o the ext ern al w o rl d. Unre coverab le tr an sa ct io ns cannot: without be undone c a sc a d i n g t r a n s a c t i o n b ac k up t o other trznsactions zr?d t o th e is external worlii e. g 'unprintingl a message usually is t o impossible). If t h e s ys te m undo i n d i v i d u a l transactions w i t h o ut c a sc a di n g b ac k u p t o o t h e r t r a n s a c t i o n s t h e n none of th e

 

transaction s c an b e c om m i tt ed befo re t h e e nd of th e writes t r a n s 3 c t i on . Otherwise some o t h e r t r a n s a c t i o n c o uld further update the e nt ity thereby m ak i n g impossible t o p er fo rm t t r a n s a c t i o n b ac k up w i th o u t p r o p a g at i ng b ac ku p t o t h e s u b s e qu e n t t r a n s a c t io n . D eg re e c o n s i st sn t t r a n s a c t i o n s are unrecoverable c om m it o u t p u t s b e f o r e t h e en d of t r a n s a c t i o n . If a l l degree con siste ncy , then any tra nsact see at least a t le as t d s gr e? 1 c o n s i s t e n t is r e c o v e r a b l e b e ca u se c o m m i t w r i t e s b e f o r e t h e e n d of t h e t r a n s a c t i o n . For all transactions m any d a t a b a s e s y s t e m s r e q u i r e t h a t degree 1 c o ns i st en c y i n o r d e r t o g u ar an te e th at all are recoverable.

b e c a u se t h e y transactions i o a w hic h i s t does not t h i s r e as o n, see a t l e a s t transacti~ns

Degree 2 c o n s is t e nc y i s o l a t e s a t r a n s a c t i o n f r o m t h e u nc om m it t e d data of oth er transactions. W ith d e gr e e consistency a 1 t r a n s a c t i o n m ig h t r e a d u n co m m it te d v a l u e s w h ic h are subsequently u p d at ed o r are undone. Degree 3 c o n s is t e nc y is ola te s the transaction from dirty r e l a t i o n s h i p s am ong e n t i t i e s . F or e xa m pl e, a degree 2 consistent t r a n s a c t i o n m ay r e a d t w o d i f f e r e n t ( co m m i tt ed ) v a l u e s i f t r e a d s ths same e n t i t y twice. This is because a tra nsaction w hi c h u p d a t e s t h e e n t i t y c o u l d b e g i n , u p d at e a n d end i c t h e i n t e r v a l o f t i a a be tw ee n t h e tw o r e a d s . M or or e e l a b c r a t e k i n d s o f a n o m a i i e s d u e t o c o n c u rr en c y a r e p o s s i b l e i f o ne u p d a t e s s n e n t i t y a f t e r r e ad ir ig t o r i f m or s t h a n one e n t i t y is involved see e x a m p l e b e l o w ) . D e g re e consistenc y completely is o la te s the trans action f ro m i n c o n s i s t 2 n c i . e ~d ~d u e t o c o n c u r r e n c y . give a n e xa mp le w hich d e m o n s t r a t e s t h e a p p l i c a t i o n of these se ve ra l degrees of c o n s i s t e n c y , i m ag in e a p r o c g s s c o n t r o l s ys te rn i n w hich some t r a n s a c t i o n is d e d i c a t e d t reading a gauge and periodically writing b a t c h e s of v a l u e s in to a list E a ch g a u g e rea3ing is an i n d i v i d u a l e n t i t y . F o r p er fo rm a nc e reasons, t h i s transaction degree consisten cy, c o m m i tt in g gauge s s all r e a d i n g s a s so o n a s t h e y e n t e r t h e d a t a b a s e . This transaction is ~ te c o v e r a b l e is run ( c a n t b e u n d o ne ) . s ec on d t r a n s a c t i o n p e r i o d i c a l l y w hich r e a d s a l l t h e r e c e n t g au ge r e a d i n g s , c om p u te s a m ean a n d v a r i a n c e a n d w r i t e s t h e s e c om p u te d v a l u e s a s e n t i t i e s i n b z se . S i n c e we w a n t t h e s e two v a l u e s t o be consistent the da ta w i th o n e a n o t h e r , t h e y m ust b e c o m m i tt e d t o g e t h e r i . e . o r?e c a n n o t com mit t h e first before t h e s ec on d i s written). T h is a l lo w s t r a n s a c t i o n u nd o i n t h e c a s e t h a t t a b o r t s a f t e r w r it in g o n ly o n e o f t h e tw o v al ue s. Hence t h i s s t a t i s t i c a l s u m m arp t r a n s a c t i o n s h o u l d see d e g r e e 1 t h i r d t r a n s a c t i o n which r e a d s t h e mean and t on a display w i l l n o t writes 2 consistency. It sees d e g r e e read m e a n w h i c h m i g h t b e u n d o n e b y b a c k u p . Another a a transaction which r e a d s b o t h t h e m ean and t h e variance m us t see degree 3 consistency t o i n s u r e t h a t t h e mean a nd v a r i a n c e d e r i v e f r o m t h s s am e c o m p u t a t i o n ea n i.e. t h e same r u n w h i c h w r o t e t h e m ea To

a l s o w r o te t h e v a r i a n c e ) .

 

Y h eth er a n i n s t a n t i a t i o n o f a t r a n s a c t i o n s e e s d e gr e e 0 1, 2 o r 3 consistzncy d ep en d s on th e action s of oth er concurrent trans action s. L oc k p r o t o c o l s are used by a transaction t o guarantee its s lf a cer tain degree of consistenc y i n de p en d en t o f t h e b e h a v i o r o f o t h e r t r a n s a c t i o n s ( s o l o n g a s 311 t r a n s a c t i o n s a t least obslrve t h e degree 0 protocol) The d e g r e s s

of consisten cy c an b e o p e r a t i o n a l l y d e f i n e d by t h e l o c k p r o t o c o l s w hic h p r o du c e them . tra nsaction lo ck s its inputs t o g u a r an t e s t h e i r c o n s i s t e n c y and l o c k s it s o u t p u t s t o m a rk t h em as d i r t y ( u n c o m m i tt e d ) Degrees 0 1 and 2 ars i m p o r t a n t b e c a u s e o f t h e e f f i c i e n c i e s i m p l i c i t i n t h e s e p ro to co ls . O bv io u sl y , i t i s c he ap er t o l o c k less. L o c k s a r e d i c h o t o m i z e d a s s h a r e go J_o_c i which a l h w multiple r e a d e r s o f t h e same e n t i t y a n d e x c l u s i v e ~ .2.k~ w h i c h r e s e r v e exclu sive access t o an en tit y. L o c k s m ay a l . s o b e c h a r a c t e r i z e d b y t h e i r d ur s ti o n : l o c k s h el d f o r t h e d u ra t io n o f a s i n g l e a c ti o n a r e called short d u r a t i o n locks w h i l e l o c k s h el d t o t h e end of th e t r a n s a c t i o n a r e c a l l e d h q q duyau og lockg S h o r t d u ra t i o n l o c k s a r e u se d t o mark o r o f an test f o r d i r t y d a t a f o r t h e d ur at io n action rather

,an

fo r th e duration of t h e transaction.

T he l o c k p r o t o c o l s a r e : Definition 2

:

transaction T obserpes &gre s oc p r o t o c o l i f : a) T s e t s a l o n g e x c l u s i v e l o c k o n a n y d a t a i t d i r t i e s . b ) T s e t s a l o n g s h a r e l o c k on a n y d a t a it r e a d s .

Degree

3:

D e g r e e 2 : t r a n s a c t i o n T @ s e r v es deqree ock pro toc ol if: (a) s e t s a l o n g e x c l u s i v e l o c k o n a n y d a t a it d i r t i e s . b) T sets a ( p o s i b l y s h o r t ) s h a r e l o c k o n a n y d a t a i t r e a d s . t r a n s a c t i o n T o b g 2 r v e s dgqyr~ lock p q t o c o l i f : a) T s e t s a l o n g e x c l u s i v e l o c k on a n y d a t a it d i r t i e s .

Degree

1:

D e g r e e 0 : t r a n s a c t i o n T o b s ~ r v e s egree 2 &gck ~ r o t o c o l f : (a) a (possibly short) exclusive l o c k on an y d a t a T sets dirties.

it

The l o c k p r o t o c o l d e f i n i t i o n s c an b e s t a t e d m ore t e r s l y w i t h t h e i n tr o du c ti on o f t k e f ol lo w in g n o ta ti o n. tr an sa c ti ~ n s well f o--rmed w ith res-p e c t writes ( r e a d s ) i f it a l v a y s l o c k s an e n t i t y ---in excl usive (shared o r e x c l u s i v e ) m ode b e £ o r e writing (reading) it transaction is formed with Th2 w ell f o r z e d i f it is w e l l r e s p e c t t o r s a d s a nd w r i te s . transaction

si ot m de o ee ns t i tn yo .t

is

x

~ h a s e with

r e s u e c t to r e a d s

o r updates)

i f

( s h a trwe o o pr h ea xs ec l ut rsai nv se a) c t il oo nc k h aa ns e n t gi rt oy w i na gf t ep hr a us en l do cu kr ii nn g?

 

which it

acqu ires loc ks

rslsases locks.

and a

s h r i n k i n g p h a ss

d u r i n g w hic h

it

D 3 f i n i t i o n 2 i s t 3 o r e s t r i c t i v e i n t h e s e n s e t h a t c o n s i s t e n c y will n o t r e q u i r o t h a t a t r a n s a c t i o n h o l d a l l 1oc.t.s t o t h e Y T i.e. t h e is EOT t h e s h r in k i n g p ha se ; rather the constraint th at the On t r a n s a c t i o n be t wo p h a s e is a d aq u at e t o i n s u r e c o n s is t e nc y . t h e o t h e r h an d, o n c e a t r a n s a c t i o n u nl o ck s a n u p d at e d e n t i t y , i t has c om mitte d th at en ti ty a nd s o c a n n z ~ t b e u rd o nc w i t h o ut c a s c a d i n g b a c k u p t o a n y t r a n s a c t i o n s w hi c h m ay have subsequ ently r e ad t h e e n t i t y . F o r t h a t r e as o n, t h e s h r i n k i n g p h as e is u s u a l l y d e fe r re d t o t h e end o f t h e t r a n s a c ti o n s o t h a t t h e tr a n sa c t io n is a lw 3 .y ~ r s c o v e r a b l e an d s o th at a l l u p da te s a r e c o mm it t e d together. T he . l o c k p r o t o c o l s c a n b e r e d e fi n e d a s : Definition 2 Degree Degree

I

: T i s well f o r s e d a n d T is t w o p h a s e .

2:

and

T i s well f o r i n e 6 is t w o p h a s e w i t h

r e s p e c t t o writes

Degree 1: is w e l l f o rm ed w i t h r e s p e c t t o w rits s a n d T i s tw o p h a s s w i t h r e s p e c t t o w r i t e s . Degres

O

T is

well

form ed w i t h r e s p e c t t o writes

transactions ar e r e q u ir e d t o o b se rv e t h e d e gr e e l o ck i ng p r o to c o l s o t h a t t h e y zo n o t u p d a t e t h e u nc om m it te d updates of 2 and o t hers. D e gr ee s 1 , provid e i n c r e a s i n g s y s te m - g u a ra n t e ed c o n s i s t ? nc y A

ncy

of

schedules

T h e d e f i n i t i o n o f what i t means f o r a t r a n s a c t i o n t o see a d e g r e e o f c o n s is t en c y was o r i g i n a l l y g i ve n i n t er m s o f d i r t y d a t a. I n o r d e r t o m ake t h e n o t i o n o f d i r t y dat a e x p l i c i t t i s n e c e s sa r y t o c o n s i d e r th e e x e cu ti on o f a t r a n s a c t i o n i n t h e c o n t e x t o f a set of c o n c u rr e n tl y e x e c ut i n g t r a n s a c t i o n s . T o d o t h i s we i n t r 2 d u c e t h e notion of a schedule fo r a s e t o f t r a n sa e i o n s. P schedule ca n be t h o u g h t o f a s a h i s t o r y or a u d i t t r a i l o f t h e a c t i o n s p e r f o r m e d by set the of tr an sa ct io ns . Gven a s c h e d u l e t h e notion of a is particular entity b ei ng d i r t i e d by a p a r t i c u l a r t r a n s a c ti o n m3ds s x p l i c i t a n d h e n c e t h e n o t i o n o f s e e i n g a c e r t a i n d e g r e e of consistency is forma lized. T h es e n o t i o n s m ay t h e n be ussd t o c o n n e ct ths various de fin iti on s of c o n s is t e nc y an d s ho u th ei r equivalence. The s y s t3 n d i r s c t l y s u p p o r t s pti iss a n 2 actjoqs A c ti 3 cs a r e cat e g i o r i z e d as b q i n actions, n_C actions, s h a r e l c ck actions, e x c l u s i v e ock actions, unloci actions, ~s a dc t i o n s , a n d gi t e ac ti on s. An e n d a c t i o n i s p re s u m e d t o unlock any lo ck s h e l d by

 

t h e t r a n sa c t i on but not explicitly u n lo ck e d b y the transactisn. F o r t h e p u r p o se s o f t h e f o ll o wi n g d e f i n i t i o n s , s h a r e l ~ c k c t i ~ n s a nd t h e i r c o r r e s p o ~ d l n g n lo ck a c t i o n s are a d d i t i o n a l l y c o n s id 2 r e d t o be read actio ns an d e x c l u s iv e l oc k a c t i o n s an d t h e i r c o r r s s p o n d i n q u nl oc k a c t i o n s are a d d i t i o n a l l y c o ns id e re d t o be write a c t i o n s . transaction i s a n y s e qu e nc e o f a c t i o n s b e g in n i ag v i t h a b eg in ac tio n and e n di n g with a n e n d a c t i o n a n d not containing other b e g i n o r o nd a c t i o n s . A ny s e qu e nc e p r e s e r v i n g ) m er gi ng o f t ra n sac t i o ns i n t o a s i n g l e s eq ue nc e i set of transactions.

s

t h e ac tio ns of a s e t of called a sc h ed u l e f o r t h e

s c h e d u l s i s a h i s t o r y o f t h e o r d e r i n w hi c h a c t i o n s a r e e x e c u t e d it d o e s n o t r e c o r d a c t i o n s w h ic h a r e u n do n e d u e t o b a c k up ) . T he s i m p l e s t s c h e d u l e s ru n a l l a c t i o n s o f o n e t r a n s a ct i o n and th e n a l l a sti o n s of another transaction ,. Such o n e - tr a n sa c t io n - a t- a -t i m e s c h e d u l e s a r e c a l l e d gggiri b e c a u s e t h e y h a v e n o c o n c u r r e n c y a m on on g transactions. C l e a r ly , a s e r i a l s c he d ul a ha s n o c o nc u rr en c y i n d u c z d i n c o n s i s t s n c y a n d n o t r a n s a c t i o n sses d i r t y d a t a . L oc k in g c o n s t r a i n s t h e s e t o f a l l o w e d s c h e d u l e s . In particular, a s c h e d u l e is l s q a l o n ly i f i t d o e s n o t s c h ed u l e a l o c k a c t i o n o n an e n t i t y f o r o n e t r a n s a c t i o n w hen t h a t e n t i t y i s a l r e a d y l o c k e d by s o m e o t h e r t r a n s a c t i o n i n a c o n f l i c t i n g mode a schedule An i n i t i a l state and c o m p l et e ly d e f i n e t h e s y s t e m 1s behavior. e a ch ste p of th e s c h ed u l e one can d e d u c e vh ich t e n t i t y v a l u z s ha v e be en c om m it te d a n d w h ic h are d i r t y : i f l o c k i n g is u se d, u p d a te d d a t a i s d i r t y u n t i l i t i s unlocked.

S i n c e a s c h e d u l e makes t h e d e f i n i t i o n o f d i r t y d a t a e x p l i c i t , c a n a p p l y D e f i n i t io n 1 t o d e f i n e c o n s i s t e n t s ch ed ul es :

o ne

Definition transaction Elus T sees d e g re e

S i f f

a l l

at

transactions

schedule sch -e -d -u-l -e .

S

then S

is

1) c o n s i s t e n c y dgq~gg sc h ed u l e 1, ( 1 , 2 o r 3) c o n s i s t e n c ; ~ n S . o r 3) run a t degree (1, 2 consistency n said t o be a _deqre_e 1, 2 or 2 onsistent

G i v e n t h e s e d e f i n i t i o n s one c a n s ho w :

AsszgZ oz 1: (a)

f e ac h t r a n s a c t i o n o b s e r v e s t h e d e g re e 0 (1, 2 o r 3) l o c k protocol D e f i n i t i o n 2) t h e n a ny l e g a l s c h e d u l e i s d e g re e 3 1, 2 o r 3) co ns is ten t D e f ir ii ti o n 3) e , a ch t r a n s a c t i o n d e g r e e 2 o r 3 ) c o n s i s t : : n c y i n of sees (1, the s e n s t

Definition

b)

1)

I

U ck p rnol te os cs o tl r at nh es na c it ito ni s p o os bs si be rl ve e tso dt he fe i nd ee gar ne oe t h e r t2r a no sr z c3)t i o nl o I

 

w h i c h d o e s o b s e r v e t h e d e g r e e 1 2 o r 3) lock protocol such t h a t T and T have a l e g a l s c h e d u le S b u t T does n3t run at degree (2 o r 3) c o n s i s t e n c y i n S Assertion 1 s ay s t h a t if a t r a n s a c t i o n o b se r ve s t h e l o ck p r o to c o l d e f i n i t i o n o f . c o n s i s t en c y ( D e f i n i t i o n 2) t h a n i t i s a s s u r e d of t h e i n fo r m a l d e f i n i t i o n o f c o n s is t e nc y b as ed o n c o s m i t t e d and d i r t y data ( ~ e f i n i t i o n ). U n l e s s a t r a n s a c t i o n a c t u l l l y s e t s th o l o c k s tprr aons sc ar ic bt ie od n b ym i xde es g ar ne ed 1 s c h( e2 dou rl e s 3)w hci co hn s wi si t l eln cc ya u s oe n e t hc ae n t r ac no sn as ct rt iuoc nt t o run a t see) a lover dagree of consistancy. Z ~ w e v e r , ic p a r t i c u l a r c a s e s s u c h t r a n s a c t i o n m i x e s ma m ay n e v e r o c c u r d u e t o t h e s t r u c t u r e o r u s e o f t h e s ys te m . I n th e s e c a s e s a n a p p a r e n tl y low d e g r e e o f l o c k i n g may a c t u a l l y prov ide degree consistency. or example, a data bas e reorg anizatio n usually n ee d do no l o c k i n g it since i s r u n a s an of f -l in e utilit y which is never run c o n c ur r en t ly v i t h o t h e r t r a n s a c t i o n s . Assertion : I f e a c h t r a n s a c t i o n i n a s e t of t r a n s a c t i o n s a t l e a s t o b s e r v e s t h e t r a n s a c t i o n T o b s e r v e s t h e d e gr ee 1 degree 3 lock proto col and i f (2 or 3) l o ck p r o t o c o l then T r u n s at. d e g r e e 1 (2 or 3) c o n s i s t a n c y ( D 9 f i n i ti o n s 1, 3) i n an y le gal. s c h e d u l e f o r t h e set of

transactions.

A s s e r t i o n 2 s a p s t h a t e a ch tr a n s a c t i o n c an c ho os e i t s degrre of c o n s i s t ? n c y s o lo n g as a l l t r a n s a c t i o n s o bs er ve a t l e a s t d eg re e 0 protocols. O f course the outputs of d e gr e s 9 1 cr 2 c ~nsiste nt 1 i. . transactions may be degree 0 o r 2 cocsistent inc ons iste nt) b e c su s e t h e y w er e c o m pu te d with po ten tia lly inconsistent inputs. One c a n i m ag in e t ha t. e a ch d a t z e n ti ty is t a g ge d w it h th e degree of consistency of its writer. A t r a n s a c t i o n m ust b ew are o f r e a d i n g e n t i t i s s t a g ge d w it h d e g re e s l o we r t ha n t h e d e g r e e o f t h e t r a n s a c t i o n .

i s s a i d t: One t r a n s a c t i o n d e p en d on an ot he r i f t h e first takes some of i t s i n p u t s from t h e s e co n d . T he n o t i o n of d e p e n d e n c y i s defined diffe re ntly fo r each d e g re e of c o n s i s t e n cy . T h es e d e p ~ n d e n c y e l a t i o n s are completely defin ed by a s c h e d u l e a nd c a n b e u s e f u l i n d i s c u s s i n g c o n s i s t e n c y a nd r e c ov e ry .

F ac h s c h e d u le transa ctions action a on transaction T t h s s c h ed u la .

<<<

T

<< T

T

d ? f i n e s t h r e e ye_l_at_i_o_n_s: a s f o ll o ws . Suppose th at entity e at so m e ste p in perforns action a1 on enti F u r t h e r s up po se t h a t T d o es

<<: ar,d

<<< o n

t h e set o f

transa ction I performs the s c h e d u l e and that ty e a t a later step in n o t e q u a l T1. Then:

or

or

a i s a write a c t i o n a n d a a is a write a c t i o n a n d a a is a r sa d a c t i o n and a

is a write action i s a rlad action i s a write a c t i o n

if

a is a w r i t e a c t i 9 n a n d a

is

i f

write a c t i o n

 

<

T

T1

or

a i s a write a c t i o n a n d a

is a read

if

a is a

is a

write ac tio n and a'

T he f o l l o w i n g t a b l e i s t h e s e iilf i n i i o n s :

m ea nin g t h a t l a t e r r e a d Ei) l a t e r w r i tt en Let

a notationa lly

for example) T <<< by T o r w r i t t e n A) 8) by T 1 .

<*

b e t h e t r a n s i t i v e c l o s u re o f T q <* T) BEFORE1 (T) = I T 1 A F T E R 1 (T) =

{TI

T

<*

T1)

action

write a c t i o n

c o n v e n i e n t way

i f C writes by T s o r T r e a d s T

of seeing

W) R)

something something

<, t h e n d e f i n e :

.

The sats BEF3R E2, BFTER 2, a n a l o g o u s l y f o r << a n d <<<.

BEF FO ORE E33

and

AFTER3

are

defined

The o b vi ou s interp retatio n fo r th is is thiit each BEF3RE set is t h e set of transactions which c o n t r i b u t e inpu ts t o T and each AFTEI s s t i s t h e s e t o f t r a n s a c t i o n s w hic h t a k e t h e i r i n p u t s f r om T ( wh er e t h e o r d e r i n g o n l y c o n s i d e r s d e p e n de n c i es i n du c ed y t h e corresponding consisten cy degree). some t r a n s a c t i o n i s b o t h b e f o r e T then no could give serial schedule

a n d a f t e r T i n s om e s c h s d u l e s uc h re su lts . In t h i s case on urrent y has introduce d inconsistency. On t h e o t h e r h an d, i f t r a n s a c ti o n s a r e e i t h e r b ef or o or after : (but not a l l r e le v a n t both) then T w i l l see a c o n s i s t e n t s t a t e (o f the corresponding degree). I f a l l t r a n s a c t i o n s d ic ho to m iz e o t h e r s i n t h i s way t h e n the relation < * <<* o r <<<*) w i l l b e a p a r t i a l o r d e r a n d t h e w h o l e s c h e d u l e w i l l g i v e d e g r e e 1 ( 2 o r 3) c o n s i s t e n c y . This can be strsngthened to:

If

A s s e r t i o n 2- : ---------

s c h e d u l s i s d e g r e e 1 ( 2 o r 3 ) c o n s i s t e n t i.f a n d o n l y t h e r e l a t i o n <* ( o r * ) s a pa rti a l order. A

if

T h e <, << a n d < << r e l a t i o n s a r e v a r i a n t s o f t h e d e p e n d s n c y s e t s i n tr o du c ed i n [ 21. I n t h a t p a pe r o n l y d s g r ee 3 consistsncy is introduce d a nd Assertion was p ro ve d for th at case. I n particular such a s c h e d u l e is e q ui v al en t t o t h e ss ri a l sch ed ul e obtains: b y r u n n in g t h e t r a n s a c t i o n s o n e a t a time i n <<< o r d e r . T he p r o o f s o f h an d le a s s e r t i o n 1 [ 2 ] g e n e r a l i z e f 3 .i r l y e a s i l y t o i n the case o f 3 2 g r e e 1 o r 2 c o n s i s t e n c y . C o n s i d e r t h e f o l l o w i n g e x am p le : LOCK '

 

READ UNLOCK LOCK XFITE LOCK BRITE UNLOCK UXLOCK LOCK WRITE UNLOCIC

I n t h i s s ch ed uls T 2 g i v e s E t o T I and T2 u p d a t e s a f t e r TI r e a d s s o T 2 < T 1 , T 2 < < T 1 , T 2 < < <T 1 a n d T 1 < < < T 2 . The schedule is degree 2 consistent but n o t d e gr ee 3 c o n s i s t e n t . I t runs T I a t d e gr e e 2 c o n s i s t 3 n c y a nd T 2 a t d e g r e e 3 c o n s i t e n c y . w ou l d b e n i c e t o d e f i n e a t r a a s a c t i o n t o see d e g r e e 2 o r 3 B E F O R E a n d APTEX s e t s are d i s j o i c t c o n s i s t e n c y i f a nd o n l y i f t h e i n so me s c h e d u l e . H o w ev er , t h i s i s n o t r e s t r i c t i v e e n o u g h , r a t h e r o n 2 must r e q u ir a t h a t t h e b ef o re and a f t e r s e t s be d i s j ~ i n t n s cn e du ls s in order t o state Definition in terns of 1 d s pe n ii en c ie s . F u r t h e r , t h e r e seems t o b e n a n a t u r a l wa way t o d e f i n e It

9

at hp ep ldi ecpaetni d~e nn cf i e tsh e o f d de pe eg nr de ee n c y dc oe nf si ni si tt ei no cny .i s a H s a n ac e p tr ho oe f a nd f o r d i s c u s s i n g s c h e d u l e s an d r E c o v er y is s u o s . ae la ti onsh b

t r a n s a c t i o n b a c k q p =gd systs

pt er ci hn nc ii qp ua el

recovery:

m e n t i on e d p r e v i o u s l y , s y s t e m w i de d e g r e e 1 c o n s i s t e n c y a l lo w s tra nsac tio n b ac ku p a nd s y st em r e c o v e r y w F t h o u t lo s t u p d a te s . i. w it h ou t a f f e c t i n g updates of tran saction s w hic h a r e c o t bs lng b a ck e d up) T he t r a n s a c t i o n is u n re c ov e ra b le a f t e r i t s f i r s t com mit o f a n u p d a te u n lo c k) a nd s o a l t h o u g h degree 1 does n o t r e q u i r e it t h e s h r i n k i n g p h as e is u s u a l ly d e f e r r e d t o t h e e nd of t r a n s ac t io n s o t h a t t h e t r a n s a c t i o n is recoverable. s

G iv en a ny c u r r e n t s t a t e a n d a time o r d e r e d l o g o f t h e u p d a t e s of t r a n sa c t io n s , on e c an r e t u r n t o a c o n s i s t e n t s t a t e by u n-d oing any incomplete tra ns ac tio ns u nc om m itte d upd ates). G i ve n a c h e c k p o i n t a t t i m e TO a n d a lo g w h ic h r e c o r d s o l d a n d new v a l u e s of s n t i t i ? s u p t 3 time TO e, o n e c an c o n s t r u c t t h e m ost r e c e n t consistent s ta te by u nd oin g a l l up da te s w h i c h were nade before t i n s TO b u t w er e n o t y e t c o m m i t t e d a t time TO+e; a n d by r e d o i n g all updates u h i c h were m a d e a n d i n t h e i n t e r v al committed TO t o If th s schedule l o g) is d e gr e e consistent then the TO =. ac t on s can be r e - d o n ? LOG o r d e r ski pp ing u n co m m it te d u p d a t e s ) I f t h e s c h ed u l e l o g ) is d o g r e e 1 c o n s i s t e n t t h e n t h e a c t i ~ n s an b s o r t s d by t r a n s a c t i o n i n < o r d e r a n d r e c o v e r y p er fo r m ed w i t h the s o r t e d l o g. T h e o utc o me of t h i s process w i l l be a sta te by rsfle ctinq a l l th e c ha ng es made a l l transac tions which c o n p l e t e d b e f o r e t h e l o g s to p p e d . H o w ev e r ,

d2 gr ee

1

c ~ n s i s t e n t ran sacti on s

m ap. r e a d

u nc om m itte d

 

  di rt y) data. Tr ansactio n and s y s te m rsc overy m ay u nd o u n c o m m i t t ed u p d a t s s . So i f t h e d e g re e 1 c o n s i s t e n t t r a n s a c ti o n s re-run i. r e -o x z cu t ad b y t h e s ys te m) i n th e a b se n c e o f th e u nd on e t r a n s a c t i o n s t may p r o d u c e e n t i r e l y d i f f e r e n t r e s u l t s t h a n woula b e obtainxl i f th t r a n s a c t i o n were b l i n d l y re d on e fron th e u p da te s r ec or de d i n t h e log . If t h e s ys te m s d e a r e n 2 co ns ist 3n t thsn n3 t r a n s a c t i o n r e a d s uncornrnitted d a t a . S o if tho c or np ls te d t r a n s a c t i o n s a r a r e- do ne i n l o g o r d e r b u t i n t h absence o f some u nd on e incomplete) tr an sa ct io ns the y w l l give exactly the sane r e s u l t s a s wers o b t a i n c d i n t h e p r e s en c e o f t h e u n do ne transactions. I n particular, i f t h e t r a n s a c t i o n s w2re re-run i c t h e order specified by t h e l o g b u t i n t h e a b s z n c e of t h e undone t r a n s a c t i o n s t h e sams c o n s i s t e n t s t a t e w o u ld r e s u l t .

 

 able

2

u r n m a r y of c o n s i s t e n c j r d e g r e e s

 

IM S/V S w i t h t h e p r o g r a m i s o l a t i o n f e a t u r e [ 3 ] h a s a t w o l e v e l l ~ c k s e t s o f r e c o r d s ) , a nd s eg me nt i n s t a n c e s hierarchy: s eg m en t t y p e s records) w i t h i n a s eg m on t t y p e . S e g m e n t t y p e s may be lccke d i n EXCLUSIVE E) n o d e ( wh ic h c o r r e s p o n d s t o o u r ?xclusive X) mode) or i n EXPRESS R E A D (R) RZTRIEVE (G), o r U P D A T E (TJ) ( ~ a c h f which correspond to our n o t i o n of intention mo3e r 3 page I) 3. 7 8 - 3 . 2 7 3 .

S e gn e nt i n s t a n c e s c a n b e l o ck e d i n s h a r e o r e k c l u s i v e mode. S eg m s~ t ype locks are requested at t r a n s a c t i o n i n i t i a t i o n , u s u a l l y i n i n t e n t i o n mode. S eg me nt i n s t a n c 2 l o c k s a r a d y n a m i c a l l y s e t as the tra nsac tio n proceeds. I n a d d i t i o n IM S /V S ha s us er c o n t r o l l e d s h a r e l o c k s o n s eg me nt i n s t a n c e s ( t h e *Q o p t i o n ) w h ic h a l l o w o t h e r r ea d r e q u e s t s b u t n o t o t h e r =Q o r e x c l u s i v e r e q u e s ts . S o r SIX I?IS/V S h a s no n o t i o n of l o c k s on s e g m e nt t y p e s ( w hi ch a l l m em be rs w o u ld a l l o w a scan of o f a s s gm e n t ty ps concurrent readers b u t with other without t h e o v e r h e a d of locking each segment ins tance) S i n c e IH S/V S does not su pp or t 5 m3de on s sg m en t t y p e s o n e n ee d n o t d i s t i n g u i s h t h e t w o i n t e n t i o n modes I S and I X see t h e s e c t i o n i n tr o d u c i n g I S a nd I X modes) I n g e n e r a l, a n ~ t i o n f inten tion I N S/ S/ V S h a s mode a nd d oe s implicit locking but does n o t r e co g n iz e a l l t h e m od e s d e s c r i b e d h e r e . It uses a s t a t i c tw o l e v e l l o c k tree.

.

IM S/V S w it h th e p ro gra m i s o h t i o n f ea tu rs b asica lly provides d e g r e e 2 c o n s i s t s n c y . H ov ev er d e g r o e cons istenc y ca n be obtained o n a se gm en t t y p e b a s i s i n a PCB ( v i e w ) b y s p e c i f y i n g t h e E X P R E S S RE AD o p t i o n f o r t h a t s eg me nt . S i m i l a rl y d e g re e 3 c o n s i s t e n c y c a n e o b t a i n e d y specifying the also has E X C L U S IV E o p t i o n . IM S /V S the user c o n t r o ll e d s h a r e locks d i s c u s s a d a b o v e w hi ch a program to obtain c3n reque st on sele cted s eg m en t i n s t a n c e s additio nal c o n s i s t e n c y o v er t h e d e g re e 1 or 2 c o n s i s t e n c y p r ov i de d by t h e system. IM S /V S without the p r og ra m is ola ti on fe.ature (and a l s o the pr ev io us ve rs io n o f IM S n am e ly IM S/ 2 ) do es n t have a lock h i e r a r c h y s i n c e l o c k i ng is d o n e o n l y o n a s e gm e n t typ e basis. I t pf or or v ai d se es g m d ee gn rt e e t y1p ce o in ns i sat evni ce pw. wy sh p de ec gi rf ey ei n 3g c to hn es i E sX t eCnLcUyS I V oE b t oa pi nt iaobnl .e Uszr c o n t r o l l e d l o c k i n g is a l s o p r o v id e d o n a l i m i t e d b a s i s v i a t h e HO HOLD o p t i o o . DMS 11013 h a s a two l e v e l l oc k h i e r a rc h y [4]: areas and pages Areas m ay b e l o c k e d i n o n e of s e v e n m o d e s irhen t h e y within arzas. a r e O P E N e d : E X C L U S IV E RET9IEV A L ( w h i c h c o r r e s p o n d s t o o u r n o ti o n of s x c l u s i v e m o ds ) PROTECTED U PDATE ( u h i c h co r r t s p o n d s t o o u r c o t i o n o f s h a r e a n d i n t e n t i o n e x c l u s i v e m o d ? ) , PROTSCTED R E T R IE V A L (which ws c a l l s har e m od e ) , UPDATE ( wh ic h corres ponds t o our i n t e n t i o n exclusive mode), a n d RETRIEVAL uhich is our i n t e n t i o n s h a r e

maze

Givei?

th is . tra ns lit era tio n,

th e

compatibility

matrix

d i sp l a ye d i n Table 1 is i d e n t i c a l t o t h e c o m p a t i b i l i t y m a t r i x of DYS 1 1 0 0 s e t s DMS 1 1 0 0 [ 4 , p a g e 3 5 9 1 However, only exclusive l o c k s on p a q e s w i t h i r, areas ( s h o r t term s h a r e l o c k s a r e i n v i s i b l y

 

set d u r in g in te rn al p o i n t e r f o ll o w i ng ) . Further, even i f a t r a n s a z t i o n l o c k s a n a r e a i n e x c l u s i v e m o d e , DMS 1 1 9 0 c o n t i n u e s t o set e x c l u s i v e l o c k s (and i n t e r n a l s h a r e lo c ks ) o n t h e p ag es i n t h e a r e a , d e s p i t e t h e f a c t t h a t an e x c l u s i v e l o c k on a n area p r e c l u d e s reads o r u p d at es of t h e area by o t h e r t r a n s a c t io n s . Similar o b s s r v a t i o n s a p p ly t the 1193 i m p l e m e n t a t i o n cf S and SIX DMS m od es . In a e n e r a l , D?lS 1 1 0 0 r e c o g n i z e s al.1 t h e m o d es d e s c r i b e d h er e and u se s i n t s n ti o n a od es t o d e t ec t :;o nf lic ts b u t d oes n ~ It u s e s a s t a t i c tw o l e v e l lo c k tree. u t i l i z s i m p l i c i t l oc ki ng .

D tlS 1 1 0 0 p r o v i d e s l e v e l 2 c o n s i s t e n c y by s e t t i n g e x c l u si v e l o c k s OR t h e on th e nodifisd p a g es and and a t e m po r :~ r y l o c k p ag e c o r r es p o n d in g t o t h e page w hi ch is l lc u rr e rl t o f r u n u n i t " . The t e m p o ra r y l o c k is r e l e a s e d when th e " c u r r s n t of run unit t1 is moved. I n ad di tio n a r u n- u ni t c an obtain add itio na l locks via an e x p l i c i t KF P com m and. T h e i d e a s p r e s e n t s d were d e v e l o p e d i n t h e p r o c e s s o f d e s i g n i n g a n d a t t h e I H S a n Jose i m pl em e nt in g a n e x p o r i n e n t a l d a t a b a s e s y s t em We w i s h t o e m p h a s i z e Fesearch Laboratory. t h a t t h i s s ys te m is a vzhicl e f o r research in d a t a b a se a r c h i t ec t u r e , and d o e s n o t indicate plans fo r future I M produ cts.) subsystem w h i ch p r o v i d e s t h e modes of lock s herein described, plu s the necesszry logic t o s c h e d ul e r e q u e s t s an d c o n v e rs i o n s, a n d a nd to de te ct re so lv e deadlocks h a s b e en i mp le m en te d a s o ne c om po ne nt of t h e d a t a manager. T h e l ~ c k u bs y s t e m is i n tu rn u s e d by t h e data m an ag er t o automatically loc k t h e n o d e s of its l o c k graph see Figure 5). of th es e lock p r o t o c o l s beyond Ussrs c a n b e u n a w a r e t h e v e r b s " b e g i n t r a n s a c t i o n 1 I a n d Ifend tr a n s a c t i o n " . T he d a t a base is b ro ke n i n t o s e v e r a l s t o r a g e areas. Each a r e a contains a set of relations files), th ei r i n d ic e s , a nd th eir t u p l e s ( r e c c r d s ) a l o n g w i t h a c a t a l o g of t h e area. Each t u p l e h a s a u niq ue tu ple id en ti fi er (data b a s e k ey ) w hic h c a n b e used t o q u i c k l y ( d ir e c t l y ) a d d r e s s t h e t u p l e . Ea c h t u p l e id en tif ier naps set l l t o of f i e l d v a lu e s. t u p l e s are s t o r e d t o g e th e r i n an area-wide he3p to allow physical c luster ing of tup les f ro m differe nt relatio ns. The unused sl o ts i n t h is h ea p are 1.e . rspresen ted by an a r ea - wi d e p o o l o f free t u p l e i d e n t i f i e r s i d e n t i f i e r s no t a l l o c a te d t o a ny r e la t io n ) . E ac h t u p l e " b e l o n g s f 1 t o a u n iq u e r e l a t i o n , and a l l tuples in a relatio n h a v e t h e sa me n u m be r a n d ty pe af fields. One m ay c o n s t r u c t an index on any s ub se t o f t h e f i e l d s of a relation. T up le id en tif ie rs give fast acc2ss t o d i r s c t t u p le s , w h il e indic es give fast associative a cc es s t o f i e l d v a l u e s and t o t h e i r c o r re s p o n d in g tuples. Each a lockable object i n order to solve k e y v a l u ~ n a n i n d e x is made t h e p ro b le m o f 'lp ha nto ms u 1 without lock ing th e e n tir e index. We d o n o t s x p l i c i t l y l oc k i n d i v i d u a l f i e l d s o r w ho le indices so tho se n od es a p p ea r i n Figure 5 on ly for: p e d a g o g i c a l reasons. Figure giv es only t h e l ll o gi c al l* l o c k g ra ph , th er e is also a g ra ph f o r p h y s i c a l p ag e l o c k s a nd f o r o t h e r lo w l e v e l r e s o u rc e s .

As c a n b e s e e n , F i g u r e a tree. is n o t t e ch n iq u es m e~tio ned i n sectio n t he

Hf avy u s e

on

l o c k i ng

is

nade o f DBG1s.

t h e For

t

 

e xs m pl e, ono c an r e ad via tu pl e i d e n t i f i e r w i t h o ut s e t t i n g a ny inc?ex l o c k s b u t t o l oc k a f i e l d f o r u p d at e its t u p l e i entifier a n d t h e o l d a n d new i n d e x k ey v a l u e s c o v e r i n g t h e u pd at ed f i e l d m ode. Fu rther , t h e t r e e is n o t s t a t i c , s i n c e must b e l o c k e d i n data b as e k ey s a r e d y na m ic al ly a l l o c a t e d t o relations; field v 3 l u e s d y n a m i c al l y e n t e r , no v e a ro u nd i n , a nd l e a v e index value in te rv al s when rocords are ins erted, u p da te d a nd deleted; r z l s t i o n s a n d i n d i c e s a r e d y n a m i c a l l y c r e il t ed a nd d e s t r o y e d w i t h i n Th? i m p l e m o n t at i o n o f a r e a s ; a nd a r e a s a r e d y n am i ca ll y a l l o c a t e d . s u ch opera tions o b s e r v es t h e lock protocol presented n th s e c ti o n on d y n a m i c g r a p h s : W hen a n od e ch3.ngss p a r e n t s , a l l old and new pa ren ts m u st explicitly or i m p l i c i tl y ) i n be h e l d i n t e n t i o n e x c l u s i v e mode a n d t h e n o d e t o ov e d m u s t b e h e l d i n b s m ov e x c l u s i v e m od od e .

d e s c r i b e d s y st em s u p p o r t s c o n c u r r e n t l y c o n s i s t e n c y d e g r e e s 1 2 and w h i ch c a n be s p e c i f i e d on a t r a n s a c t i o n basis. I n addition s h a r e l o c k s on i n d i v i d u a l t u p l e s c a n b e a c q u i re d by t h e u s e r .

The

 

D

BASE

T

S

RE

I

RELATIONS

I

I

I

I N D

CI:ES

I I

i

I

INDEX

I

KEY

INTERVALS

I I

I

-

4

I I

I I

f

II

ALLOCATSD

FREE

TUPLE

TUPLE

I D EN T I F I E R S

IDENTIFIER S

I -

I

i I US

NDEXED

INDEXED

FIELDS

aigurs

FIELDS

5

lock

graph

 

a ck no w f e d q e many h e l p £ ul how l o ?3cri, J i m Ne hl and 9 r a d Vads on s y s t e m s a n d how t h e s e r e s u l t s ; n ig ht b e b e e s ~ e c i a l l yndebted E c J o ne s i n t h i ~ P a u l   e

[I

1

g ra te fu ll p

J. N . G r a y , a Shared

P u t z o lu , 1 8 G r a n u l a ri t y o f L o ck s i n Data P ro c ee d in g s of the Intern ational Baserf1 C o n f 2 r s n c s o n V e r y L a r g e D a t a B a s e s , B o s t o n , Mass., S e p t e m b e r R

A

Lorie,

discussions uith Phil c k i ~ g o r k s i n existing rte r p re se n te d . je re s r e ga rd .

G

li

1975.

[

]

K.P. E s w a r a n , J. N Gray, Not i o n s o f C o n s i s t e n c y a n d RJ

[

1

[ 4 ]

1487

Lorie, I L Traiger, On t h e P r e d i c a t e Locks, T e c h n i c a l R e p ~ r t IBil Research Laboratory, San Jos e, Ca., Nov. 1 9 7 4 . R.

A

Info rma tion f l a n ag em en t System Syste m A pp li ca ti o n D e s i gr ? G u i d e , C o r p . , 1975.

.

V ir tu al Storag e I a S //V V S) F o r m No. SH2C -3 3 2 5 - 2 , IBM

.

UNIVAC 1700 S e r i e s D a t a P l a n a c j e m e n t S y s t e m DMS 1 1 0 0 ANSI COBOL F i e l d Data M a n i p u l a t i o n L a n g u a g e . O r d e r No. U P 7 9 0 8 - 2 , S p e r r y B an a n d C o r p . , H ay ay 1 9 7 3 .