UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Practical concurrency considerations for a student oriented database management system Shamper, Julie Anne 1980

You don't seem to have a PDF reader installed, try download the pdf

Item Metadata

Download

Media
UBC_1980_A6_7 S44_8.pdf [ 5.56MB ]
Metadata
JSON: 1.0051814.json
JSON-LD: 1.0051814+ld.json
RDF/XML (Pretty): 1.0051814.xml
RDF/JSON: 1.0051814+rdf.json
Turtle: 1.0051814+rdf-turtle.txt
N-Triples: 1.0051814+rdf-ntriples.txt
Original Record: 1.0051814 +original-record.json
Full Text
1.0051814.txt
Citation
1.0051814.ris

Full Text

c, /  PRACTICAL CONCUfifiENCY CONSIDERATIONS FOR ORIENTED DATABASE MANAGEMENT  A STUDENT  SYSTEM  by JULIE  ANNE SHAMEEH  B.Sc., The U n i v e r s i t y  of A l b e r t a ,  1975  A THESIS SUBMITTED IN PARTIAL FULFILMENT THE REQUIREMENTS FOR MASTER OF  THE DEGREE OF  SCIENCE  in THE FACULTY  OF GRADUATE  (Department o f Computer  We a c c e p t to  THE  this  thesis  the r e q u i r e d  UNIVERSITY OF  Julie  Science)  as c o n f o r m i n g standard  BRITISH COLUMBIA  September  cj  STUDIES  1980  Anne Shamper,  1980  OF  In p r e s e n t i n g t h i s  thesis  in p a r t i a l  f u l f i l m e n t o f the requirements f o r  an advanced degree at the U n i v e r s i t y of B r i t i s h Columbia, the I  Library shall  make i t  freely available  f u r t h e r agree t h a t p e r m i s s i o n  for  reference and  f o r e x t e n s i v e copying o f  this  that  study. thesis  s c h o l a r l y purposes may be granted by the Head of my Department or  by h i s of  for  I agree  representatives.  this  thesis  It  is understood that copying or p u b l i c a t i o n  f o r f i n a n c i a l gain s h a l l  not be allowed without my  written permission.  Department of The  CJMH\J^IAW  U n i v e r s i t y of B r i t i s h  2075 Wesbrook P l a c e V a n c o u v e r , Canada V6T 1W5  Date  ^ j . . \<\/BQ  ScXpWfc  Columbia  iii  ABSTRACT  The  correctness  when  the  database  independent management is  Data  and  not  approach on  theory  Part  This t h e s i s in  may  (EDBS).  a number o f  of  of  a  the  job  those  provided  guarantee  of  concurrency  out  and i n p r a c t i c e .  to  that  correctness controls  EDBS  in  facilities  correctness.  Several  c a n be g u a r a n t e e d .  implementation  provided.  providing  be a v e r y  database  by t h e E d u c a t i o n a l  whereby c o r r e c t n e s s  and a t t h e same time turns  so t h a t  concurrency  i s s e l e c t e d b a s e d on e a s e o f degree  destroyed  by  I t i s concluded to  be  concurrently  examines  particular  a r e proposed  the  correctness concurrency  accessed  sufficient  alternatives  than  of a database  system i s t o c o n t r o l c o n c u r r e n c y  Base System  are  is  transactions.  guaranteed.  general,  An  (or i n t e g r i t y )  a  difficult  rather  Guaranteeing  high  degree  problem  of  both i n  i v  TABLE OF CONTENTS Chapter  I: Introduction  Chapter  I I : Framework  A. . B a s i c  1 . 6  Concepts  6  B.  Serializable  C.  Locking Protocols  16  D.  Other  26  E.  C u r r e n t Hot R e s e a r c h  Chapter  Schedules  12  Systems Issues  ......42  I I I : Problem  .45  A.  EDBS D e s c r i p t i o n  46  B.  ED BS I m p l e m e n t a t i o n  C. . P r o b l e m Chapter A.  Formulation  I V : Recommendations  Alternatives  B. . S e l e c t e d Chapter  <  54 .75 .87 87  Approach  V: C o n c l u s i o n  REFERENCES  96 ........100 10 3  APPENDICES  . .. 106  A: EDBS O v e r v i e w  106  B: EDBS Commands And U t i l i t i e s  107  C: EDBS F i l e  Usage  103  D: I n t e r f a c e  File  System D e s c r i p t i o n  109  E: I n t e r f a c e  File  System F u n c t i o n s  114  V  LIST OF FIGURES  1.  Serial  Schedules  2.  Interface  File  3.. EDBS O v e r v i e w 4.. EDBS F i l e  Usage  System  ...11 54 106 ...108  vi  ACKNOWLEDGEMENTS  I sincerely their also  careful  careful  in  my s u p e r v i s o r s P a u l  review  and  stages  reading  of  the  computer c e n t e r  staff  g e t t i n g the E d u c a t i o n a l  h i s continued  document.  both  Finally,  for  o f my work.  for his direction  thesis,  of the f i n a l  G i l m o r e and A l Fowler  perceptive c r i t i c i s m  w i s h t o t h a n k Bob G o l d s t e i n  formative  the  thank  during  I  the  s u p p o r t and  I wish t o t h a n k  a t UBC and a t SFU f o r t h e i r  Data Base System o p e r a t i o n a l .  help  1  ChjLEtSE I : I n t r o d u c t i o n  T h i s t h e s i s h a s two m a j o r a s p e c t s : c o n c u r r e n c y and a s t u d e n t oriented The  database  management  student  oriented  system. database  E d u c a t i o n a l D a t a Base System of to  APL w o r k s p a c e s . . perform  provided  various  operations DESTROY,  and  delete EDBS  is  educational manipulate  of a  number  databases..  U t i l i t i e s are  databases.  Other  d a t a from a d a t a b a s e , new d a t a i n t o  a  update  database,  a database.  intended  There a r e a t l e a s t  i s the  from an APL t e r m i n a l  MAINTAIN  i n a database, i n s e r t  d a t a from  system  EDBS c o n s i s t s  on  permit a user to r e t r i e v e  data c o n t a i n e d or  (EDBS)..  Users access t h e system  t o CREATE,  commands  management  for  use  two p o s s i b l e  environment. h i s own  i n teaching  approaches  First,  databases..  each  Second,  database concepts.  to using  EDBS  in  an  s t u d e n t c o u l d c r e a t e and the  instructor  could  c r e a t e a common d a t a b a s e t o be a c c e s s e d by a l l s t u d e n t s . Cone u r g e n c y by  more  than  concurrently, objective while  which  one data  defined  as t h e s i m u l t a n e o u s use o f a s y s t e m  user.  When  in  of concurrency  ensuring  provide  is  a  database  database research  is  used  may become i n c o r r e c t .  The  is  database c o r r e c t n e s s .  a c o n c u r r e n c y component  controls  a  to  system  provide  concurrency  The u s u a l a p p r o a c h  f o r a d a t a b a s e management  c o n c u r r e n c y such t h a t  correctness  i s to system  i s guaranteed.  2  A  «  Motivation  Concurrency installation  became an  of  the  system  EDBS was d e p e n d e n t on system  could  available The  The  the  two f i l e  manner  via  impossible,  access  carefully  the issue  file  system. .  Before  the  to rely  on t h e  data  sharing  a u t h o r i z a t i o n , concurrency c o n t r o l ) . EDBS makes o f  available  It  during  The a v a i l a b l e v e r s i o n o f  primarily i n their  could MTS  however, t o s i m u l a t e  capabilities.  EDBS  system.  authorization  the  to  i t had t o be m o d i f i e d  p a r t i c u l a r demands t h a t  terms of a c c e s s  relation  a t UBC.  systems d i f f e r  (i.e.,  in  CDC/APL  be i n s t a l l e d ,  MTS/APL f i l e  facilities  issue  thus  the  system  in  be met i n a s t r a i g h t f o r w a r d  APL  functions.  required  became  file  It  appeared  concurrency  control  necessary  of concurrency before  to  consider  continuing  very  with  the  implementation.  B»  Proposed  A the the  major  problem.  Work  portion  obtain  First,  information.  required  we  be m o d i f i e d ,  information  review to  the  clarify  working  on t h e in  with  defining  problem  an environment o f difficult  approach  requires  the array  that  EDBS  to  of p r a c t i c a l  should  solutions.  work f o l l o w s : literature basic  are  a b o u t t h e e x i s t i n g EDBS c o n c u r r e n c y  thus l i m i t i n g  A summary o f p r o p o s e d (1)  are  imposed  In p a r t i c u l a r , i t i s very  s o l u t i o n . . Second, our b a s i c not  t h e s i s i s concerned  Two major c o n s t r a i n t s  following:  imperfect  of t h i s  i n t h e area  objectives  of c o n c u r r e n c y  of  concurrency  3  control. (2)  examine  EDBS  concurrency  control  d e t e r m i n e t h e e x t e n t t o which achieves these (3)  examine  f a c i l i t i e s to  the existing  system  objectives.  other  systems  to  determine  usual  solutions. (4)  propose  a  objectives  C.  solution  which  satisfies  the  basic  of concurrency c o n t r o l .  Dimensions  This  thesis  has s e v e r a l  dimensions  which  may be d e s c r i b e d  as  follows:  1. . F i l e  Systems  EDBS  has  dependency CDC/APL  been  previously  on t h e APL*PLUS f i l e  file  system.  on t h e CDC/APL f i l e  available  MTS/APL  they  definition,  developed  file  guarantee  was i n i t i a l l y  CDC/APL file  the existing file  systems,  capabilities.  system. in  system  system.  through  by a d e s i r e  which  system t o a  we examine  motivated  to  to  convert  dependency  from on  a the  Our u n d e r t a k i n g t h e n i s t o c o n v e r t f r o m a  dependency  problem  modified  each  to  to  a  In t h i s  dependency  thesis,  EDBS  concurrency  file  system.  understand  first,  on  as part  the  of our  solutions  as  T h i s approach i s what  correctness  i n t e n d e d f o r EDBS and s e c o n d , t h e e x t e n t  concurrency s o l u t i o n Hence, one major particular  their  i s constrained  by t h e  theme o f t h i s  thesis i s  concurrency  control  4  2.  Data  Models  EDBS  supports  network  databases.  characteristics system  creation  of  o t h e r than  analysis whether  is  In each  EDBS  aimed  of  this  thesis  supports  gaining  solution.  t h e s i s i s data  review  Hence,  the  insight  t h e d a t a model i m p l i e s a need  concurrency  we  hierarchical  a  models, i n p a r t i c u l a r  data  into  model..  their  one Our  the question of  for a particular  second  and  essential  d a t a model and we examine a t l e a s t  which  at  relational,  major  type  of  theme o f t h i s  concurrency  control  requirements.  3. . C o r r e c t n e s s  Concurrency which be  jeopardizes correctness.  of  support  o f database  and most s y s t e m s  thesis  within  the  we a t t e m p t  broader  framework  additional by e a c h  system  procedures and EDBS.  of  of  correctness for  ensuring  checking  provide a s e t  error  to d e a l with t h e i s s u e  may  or software  assertions f o r  r o u t i n e s t o d e t e c t and r e c o v e r from  In t h i s  reviewing  updates  environment  of a database  human e r r o r s ,  Many s y s t e m s p r o v i d e i n t e g r i t y  validity  provided  i n a database  The i n t e g r i t y  d e s t r o y e d due t o h a r d w a r e f a i l u r e s ,  errors. the  i s not the o n l y f a c t o r  in  situations. concurrency g e n e r a l by correctness  5  4.  Trade  In are  offs  this  thesis  particularly  and  performance  in  relation  we a r e i n t e r e s t e d relevant:  C.  t o concurrency  Guide  Chapter  II  Chapter  which  describes  facilities  to  with  related  reflect  an i m p l e m e n t a b l e  by  comparing  systems..  literature  and  p r o v i d e d by a number o f and  those of the  compares  of other EDBS  Finally,  i t s  systems.  concurrency  I V d e s c r i b e s a l t e r n a t i v e s and s e l e c t s Chapter  V  what  we  points  work.  i s advised  was b a s i c a l l y  the  EDBS  with a s t a t e m e n t  f o r further  reader  evidenced  reviews  t o be an optimum a p p r o a c h .  not n e c e s s a r i l y intended  thesis  (1979)  mechanisms and t h e t r a d e o f f  control f a c i l i t i e s  III  control  Chapter  directions The  this  I I I concludes  problem.. believe  of  Chapter  concurrency  control  p r o v i d e d by EDBS and o t h e r  concurrency  systems.  t h e t r a d e o f f between i n f o r m a t i o n  and c o r r e c t n e s s as  solutions  Reader^s  describes  two o f which  a s p o i n t e d o u t by Kung and P a p a d i m i t r i o u  between c o n c u r r e n c y concurrency  i n trade o f f s ,  that  this  to the f i n a l our e x p e r i e n c e  t h e s i s e x a m i n e s many i s s u e s solution. with  a search to determine  solution.  This  t h e EDBS  thesis  is  undertaking,  t h e problem  and  find  6  £ h § £ i £ E LL  Framework  z  This database to  chapter  reviews  concurrency.  base  transactions  which  have  o f such  a  i s  of  concurrency  proposed  thus  f a r have been b a s e d  appears  that  locking  alternative  mechanisms  to  a g r e a t e r degree 1  Section 2  Section  serializability  of  concurrency  Basic  in  of  the  a l l solutions techniques.  tends  guarantee  toward  It  finding  serializability  describes  detail  the  by P a p a d i m i t r i o u  protocols.  solutions  terms  t h e amount o f c o n c u r r e n c y  research  chapter  as p r e s e n t e d  locking  in  The  while  of concurrency.  this  examines  is  concurrent  of t h e database.  locking  restricts  Current  that  Virtually  on  research  component f o r a d a t a  measured  provided.  unduly  which c a n be p r o v i d e d .  view  the area of  c o r r e c t n e s s . . One  guarantees  amount  A.  database  serial  a component  in  of concurrency  while e n s u r i n g  system  will  performance  examines  date  i s t c provide a " s e r i a l i z a b i l i t y "  management  providing  to  The o b j e c t i v e  provide concurrency  approach  research  Finally,  as implemented  basic  concepts.  requirements (1979).  section  i n a number o f  for  Section 3 4  reviews  systems.  Concepts  A database  i s d e f i n e d as a s e t o f e n t i t i e s  has  a name and a v a l u e .  For  the  purpose  assumptions  about  of  Users  our  actions:  execute  analysis  we  where each  entity  a c t i o n s on t h e d a t a b a s e . make  the  following  7  (1)  Actions the  are  other  (i.e.,  concurrency we s a y t h a t (2)  The o n l y and We  executed  Actions  consider  view  world.  Hence,  (hereafter  there  called  must be s a t i s f i e d real the  world. entities  said  zero  In t h i s  sense  read,  write, on  action  entities.  to  temporary  sorts  create  be  some  variables..  of c o m p u t a t i o n s as  a  certain  set  constraints)  of the  of  which  real  assertions necessarily  f o r t h e d a t a b a s e t o be c o r r e c t r e l a t i v e  t o the  our database c o n s i s t s o f  Consistency  constraints  applying  might be t h e f o l l o w i n g : E1  i s e q u a l t o E2  En  i s equal t o n  i s t h e index  is  transform  i t from  t o be c o n s i s t e n t  continuously  undergoing  one s t a t e t o a n o t h e r .  i f i t s current  constraints associated is  o f E3  necessary  t o the database that  state  changes A  as user  database  satisfies  is  the s e t of  with t h e database . but  c o r r e c t n e s s . . F o r example, i f e x a c t l y applies  with  f a c t s a b o u t some p o r t i o n  E 1 , E2,..., En.  Consistency  before  with t h e a c t i o n .  exists  database  consistency  an  these  consistency  E2  actions  are:  F o r example, s u p p o s e t h a t  to the database  A  machine).  only  indivisibly  A database represents  executed  a r e performed  involving  we  and one  are atomic.  types of actions  computation  occurring  are  a serial  actions  not  Rather,  actions  on  destroy. do  indivisibly  not  sufficient  one c o n s i s t e n c y  for  constraint  " E K E 2 " , then i t i s p o s s i b l e  fora  8  user t o e r r o n e o u s l y  update E2 w i t h o u t  constraints.  database  it  The  does n o t a c c u r a t e l y  of t h e r e a l  world  will  reflect  violating  the current  state  to  consistency  constraint.  bank a c c o u n t  to another there  account  This  violates a constraint i s  To  been  constant".  new  of  consistent  portion  each  other  during  by  some  " i n moving money f r o m one  be an  instant  t h e number  during  which  not yet c r e d i t e d .  of  dollars  in  the  1  a t some l e v e l ,  transforms  state.  actions  transactions.  a consistent  by t h e same  A transaction,  database  Hence, a t r a n s a c t i o n  state  serves  into  as a u n i t  consistency. In  this  s e c t i o n , we w i l l  follow  a notation  similar to  presented  by Eswaran e t a l . (1976) f o r r e p r e s e n t i n g  a  entity  given  read  by a p a r t i c u l a r t r a n s a c t i o n .  o f e n t i t y E1 by  (T 1 , r e a d , E 1 ) .  The  transaction transaction  eliminated  i f i t i s clear  performing  the a c t i o n . .  To following one  1  that  of that  inconsistent  and t h e o t h e r  into units called  when e x e c u t e d a l o n e , a  will  debited  guarantee c o r r e c t n e s s  user a r e grouped  to  F o r example,  one  system  has  related  because  represent.  A d a t a b a s e must be a t l e a s t t e m p o r a r i l y which a r e  consistency  be i n c o r r e c t , however,  which i t i s i n t e n d e d  update o f e n t i t i e s  any  This  clearly  from  f i x the  idea  groups of a c t i o n s ,  constraint  applies  passage i s taken  will  be  represented  (T1 i n t h i s  context  which  of  an a c t i o n on  F o r example, t h e  name  case)  suppose  the database: that  as  will  transaction  a transaction  T1 and T2, and  to  from  T1  that  be is  consider the that  only  "E1 i s e q u a l t o  page 624 o f Eswaran e t a l .  (1976).  9  E2". Tl  =  {(read,El),  (read,E2) ,  ( w r i t e , E1) , ( w r i t e , E2) }  T2  =  {(read,E1),  (write El)} r  i  In be  e x a m p l e , 1\  this  a transaction.  T1  would  be  a transaction  i s consistency  but  preserving  T2  since  would  not  i t updates  t  both  E1  and  E2  correctly).  (assuming  Even  inconsistent completion  though  during of  In  Hence, upon c o m p l e t i o n i s violated.  not  a  of  i s not  concurrently  transactions. schedule. a  The  may  i t will T2  are be  be  updated temporarily  consistent  updates  E1  constraint that  consistency  E1  preserving  We  but  upon  not  E2.  i s equal  to  and  of  transaction i n the see  transactions which t h e  is  the  concurrently,  two  therefore  want  actions  the must  from  other  from  of a c t i o n s  have a s c h e d u l e r  within  and  different  whose  restricted  temporary  { (T1, w r i t e , E 1 ) ,  T2  =  {(T2,read,El) ,  concurrently  is  the this  such  that  transactions.  consider  our  "E1  is  with  previous equal  to  E2"..  (T2 , r e a d , E2) } the  following  running  database  (T 1 , w r i t e , E2) }  to  input  inconsistencies  associated  according  a  In  transactions,  =  run  i s called  transactions. be  to  whose o u t p u t  problems  applies that  T1  run  we  isolated  correctness  constraint  suppose t h a t  sequence  transactions  actions  d a t a b a s e by  we  interleaving actions  assume h e r e t h a t  of e x e c u t i o n  To  into transactions  resulting  sequence of a r r i v i n g  induced  are  T1,  the  by  environment i n t e r l e a v i n g of each  of  12  entities  database  contrast,  grouped a c t i o n s  transactions  order  T2  the  transaction. Having  is  the  execution  T1..  E2  that  schedule:  to Now,  10  { (T1,write E1) ,  ( T 2 , r e a d , E 1) ,  r  Note the  that  database  been  the  gives  but n o t E 2 a t the time  intended  different)  schedule  that  transaction  entities  database  (T1, write, E 2 ) }  T 2 an i n c o n s i s t e n t  view o f  T 2 reads E 1 not e q u a l t o E 2 because  (i.e.,  E1  updated  this  (T2,read,E2),  of reading).  T 2 should  update  b a s e d on t h e i n c o n s i s t e n t  would  be  inconsistent  upon  T1  has  Now,  i f i t had  the  same  values  read,  completion  of  (or then the  schedule. Another  correctness  problem" which same  value  for  incremented  the  is  the c l a s s i c  when two c o n c u r r e n t  an  entity  value.  overwrites certainly  occurs  problem  The  first  and  result  then i s  that  i n c o r r e c t i f updates g e t l o s t ,  inconsistent constraint  i f  say  two e n t i t i e s  and an update g e t s l o s t  transactions try  and one i n c r e m e n t  "lost  to the  i s lost.  read  write  the  back an  second  update  A database i s  and f u r t h e r  a r e r e l a t e d by a f o r one e n t i t y  update  i t  may  be  consistency  but  not  the  other. . If other arise. set  i n some o r d e r ) The  our  possible  are run s e q u e n t i a l l y then  schedule  of t r a n s a c t i o n s  given two  transactions  previous serial  (i.e.,  t h e above c o r r e c t n e s s  r e s u l t i n g from  i s called  a serial  transactions, schedules:  p r o b l e m s do  sequential schedule.  one a f t e r t h e  execution For  T 1 and T 2 , t h e r e  not of a  example,  are e x a c t l y  11  SERIAL SCHEDULES { (T 1, w r i t e , E 1 ) , (T1, w r i t e , E 2 ) , (T2,read,E1) , ( T 2 , r e a d , E2) }  i  1  i  .  i  T1  T2  { ( T 2 , r e a d , E 1 ) , (T2 , r e a d ,E2) , (T 1, w r i t e , E1) , (T 1, w r i t e , E2) }  •—-  i i  i  T2  T1 Figure  Serial First,  execution  will  give  This  is  system  s c h e d u l e s have a  each  because  only  one  a  T h i r d , the l o s t  serial  schedule  particular  schedule  of  will  update  because  transaction  s c h e d u l e s do n o t p r o v i d e  (i.e.,  i n t e r l e a v i n g of a c t i o n s usual  Kedem and  approach  serializability. equivalent  from  t o some s e r i a l  their  outcomes  are  the  notion  of serializability  et  i s said  to  consistent  occur  Of  by a  course,  transactions  the  Papadimitriou concurrency notion  t o be s e r i a l i z a b l e  of  i fi t i s  i n t h e sense  same).. The n e x t s e c t i o n as p r e s e n t e d  a  transactions).  providing  schedule(equivalent  with  o f an e n t i t y  a l . .1976,  involves  transaction  a new  indivisibly.  1979)  correctness A schedule  be c o n s i s t e n t  each  cannot  different  database.  be a c t i v e i n t h e  into  and w r i t e  schedule  the  c o n c u r r e n c y between  (Eswaran  Silberschatz  ensuring  read occur  serial  The  problem  any will  because  database  properties.  to a serial  view  transaction  consistent  state.  while  desirable  according  a consistent  of a s e r i a l  transform  1979,  of  a t any one t i m e . . S e c o n d , t h e d a t a b a s e w i l l  upon c o m p l e t i o n will  number  of t r a n s a c t i o n s  transaction  1  that  examines t h e  i n Papadimitriou  (1979)..  12  B. . S e r i a l i z a b l e  Schedules  Papadimitriou correctness  justifies  criterion  the appeal  of s e r i a l i z a b i l i t y  as  a  as f o l l o w s :  "Databases a r e s u p p o s e d t o be f a i t h f u l models o f p a r t s of the r e a l world, and u s e r transactions represent instantaneous changes i n the world. Since such c h a n g e s a r e t o t a l l y o r d e r e d by t e m p o r a l p r i o r i t y , the only acceptable interleavings of atomic steps of d i f f e r e n t t r a n s a c t i o n s are those that are e q u i v a l e n t t o some s e q u e n t i a l e x e c u t i o n of t h e s e t r a n s a c t i o n s . ! 1  In  this  section,  we  describe  Papadimitriou's  t r a n s a c t i o n s and c h a r a c t e r i z a t i o n o f s c h e d u l e reader  is  cautioned  class  of t r a n s a c t i o n s .  two  actions:  transaction for  a  read  followed  understanding  and  comparing  2  will  see  model a g a i n  will  serve  this  We p r e s e n t  consist  a  for  i n Chapter  variables.  followed The r e a d  as  by  exactly  This  simple  philosophies  similar  of  reasons. thesis  We  where i t  characteristics of  variables.  the  update  as a h i s t o r y  and  from  of the values of  of a s e t  the values  of  of a s e t of  page 632 o f P a p a d i m i t r i o u  t r a n s a c t i o n model i s used and Goodman (1977).  views  T r a n s a c t i o n s a r e assumed t o  a c t i o n f o r t r a n s a c t i o n T i i s denoted  T h i s passage i s taken The same and R o t h n i e  narrow  (1979) a s a framework  3 of t h i s  to a schedule  of two a c t i o n s : t h e r e t r i e v a l  variables  The  problem.  refers  entities  of  write.  different  i t here  eguivalence. .  consist  a s a means o f d e s c r i b i n g e s s e n t i a l  EDBS c o n c u r r e n c y  database  that  by  model o f  c o n s i d e r s a very  model i s used i n P a p a d i m i t r i o u  Papadimitriou  2  Namely, t h o s e  serializability.  our  1  that Papadimitriou  1  i n Bernstein et  by R i ,  (1979).. al..(1978)  13  the  write The  action set  set Ti) . the  of  by  Wi.  v a r i a b l e s read  of  the  transaction  S i m i l a r i l y , the write  set  of  uninterpreted S(Wi) = £y} of x and  and  function  of  Then  with  our  are  assumed  values  for  are  i n S(Wi)  represents  transactions  involved  S(E2) = {},  Then h would be  can  view y a s  a  called set  suppose some  and  T2  given  usage o f the  to  be  we  written  Papadimitriou  f r o m T1  as  example,  atomic.  variables  variables  actions  i s viewed  the  transaction  S(Wi), i s  For  previous  Similarily,  S(E1) = £x},  we  called  S (Ei) f o r  variables written,  instantaneously.  the  by  is  of that  function  y = f i ( x , z ) ].  transactions that  (denoted  symbols.  S (Ei) = £x, z} .  z [i.e.,  assume  set  a transaction  T i . . Each t r a n s a c t i o n  Consistent within  by  in  assume  term,  actions  That  is,  S(Ri) that  we  are  read  values  for  instantaneously. a h i s t o r y as  in  history  follows: h  are  TI  S (W1) =s (W2) = {x,y} .  Suppose  are  order  scheduled  i n the  Suppose and  T2  that where  also  that  (R1,B2,W1,W2}.  by  h = R1[x]W1[x,y ] W 2 [ x , y ] i  Papadimitriou's following and in  l e t f (i,j)  V represent be  the  of  the  function  equivalence  set of  of h i s t o r i e s  variables  associated  i n the  with the  jth  is  the  database variable  transaction T i ) : "Two set  1  (Let  notion  h i s t o r i e s , h i and h2, a r e o f J V J domains for the  equivalent i f , given variables, any set  In contrast with P a p a d i m i t r i o u ' s a p p r o a c h we r e a d ( w r i t e ) a c t i o n s f o r which t h e c o r r e s p o n d i n g i s empty.  any of  do not show i n h read(write) set  14  initial values for the variables from the corresponding domains, and furthermore any interpretation of the f u n c t i o n s f ( i , j ) , the values of the v a r i a b l e s are i d e n t i c a l a f t e r execution of both histories. n l  To  understand  history In  equivalence  particular,  "augmented "live"  Papadimitriou's syntactic  transaction  The  some t e r m i n o l o g y must f i r s t  given a h i s t o r y  version  characterization  o f h", t h e  h  we  are  "reads  be i n t r o d u c e d .  concerned  from"  of  relation  with i n h,  the and  a  h' d e r i v e d f r o m  h  i n h.  augmented  version  of h i s the h i s t o r y  by: (1) a p p e n d i n g which  onto t h e f r o n t  writes a l l variables  reading  any  (2) a p p e n d i n g  updating  onto  database  then  h' = Now defined "Ri of For  1  2  W[V]  h' would  the  we  i n the database  end  of  T  without  h, a t r a n s a c t i o n  l e t V be  t h e s e t of  be r e p r e s e n t e d as  { h }  suppose t h a t as  transaction  T'  without  o f them.  if  ...  a  a l l v a r i a b l e s i n the database  any  example,  h,  o f them  which reads  For  of  x  ... S (Ri)..  v a r i a b l e s i n the  follows:  R'[V] A "reads  from"  relation  in h i s  follows:  r e a d s x from Wj i n h i f Wj i s t h e l a t e s t a w r i t e symbol b e f o r e R i i n h such t h a t 1  example,  given the  augmented  version  of  occurrence x£S(Wj)" 2  our  previous  T h i s passage  i s taken  from  page 633  of P a p a d i m i t r i o u  (1979).  T h i s passage  i s taken  from  page 634  of Papadimitriou  (1979).  15  history, h' we The  say  = W [ V ] R l £ x ] W 1 [ x , y ] W 2 [ x , y ] B ' [ V] that  RI  reads  definition (1)  T'  (2)  If  of  a live  i s live for  in  h.  t r a n s a c t i o n i n h i s as  live  from  showed  W in  follows:  h.  some  variable Papadimitriou  x from  Wi  transaction  i n h,  then  Tj  Bj  r  reads  Ti i s also live  a  i n h.  that:  "Two h i s t o r i e s , h i and h2, a r e e q u i v a l e n t i f and only if they have t h e same s e t of l i v e t r a n s a c t i o n s and a l i v e E i r e a d s x from Wj i n h i i f and o n l y i f E i reads x f r o m Wj i n h 2 . n l  Eecall equivalent  that to  problem.  in  histories  of s e r i a l i z a b l e  histories.  of h i s t o r i e s it's  Papadimitriou  also  closest  major  that i s an  scheduler  f o r the into  class the  T h i s passage i s taken  algorithm  closest  an  algorithm  serializable  page 635  of the  history).  exists  result  notions  of set  efficient  which c o n v e r t s  there  of  NP-complete  i s no  for a l l efficiently  histories  (i.e.,  from  that there  is  recoqnizing  f o r various subsets  serializable  shows t h a t  of s e r i a l i z a b l e  history  is  which  notions  A  serializable  suggests  (i.e.,  subclasses  input  literature.  are  one  Various  (1979)  provide  NP-complete r e s u l t  to  is  same p a p e r i t i s shown t h a t p r e v i o u s actually  history  the  that  serializability  serializer  history  history.  Papadimitriou  In t h e  The  1  serial  exist  in  transaction  serializable  some  serializability presented  a  an  input  However, recognizable  an  efficient  which  transforms  history  within  of P a p a d i m i t r i o u  an its  (1979)..  16  class).  In  efficient  C.  the  form  be  system  certain  must  be  to  be  thus  controlling  entities  locking  protocol  follows  approach  is  individually  any  to  a  will  We  considerations  all  locking  reguired  set  locking  i f of  a  the  to  locking  the  of the  SDD-1  this  (i.e.,  section  by  we We  known  discuss then  relating a  a  locking  A run  each  possible aspect  of  transaction of  all  to  the  a number  describe  phase l o c k i n g  i n implementing  any  description be  is  where  each  need not  unlock  protocol.  important  on  protocols.  semaphores and  protocol,  section,  two  solutions  lock  An  all this  transaction  syntactic  history  of  d a t e how  transactions  focuses  detail:  c o n c l u d e the  example,  For  concurrency  serializable.  i n the  in  that  it  In  on  in  a particular locking  same  hence  priori.  protocols  be  that  occur  to  to  other the  and  related  protocol.  these  scheduler  exception  Transactions  guarantees  transaction  schedule  data).  according  with  locking  with  descriptions  notable  a l . 1978)  to  a  i t i s unclear  With t h e  et.  concurrently  scheduler  concerned  (1979).  syntactic  s c h e d u l e d , and  access  transactions  with  f a r have been b a s e d  database  resulting  be  i n designing  Papadimitriou  provided  (Bernstein  issues  by  accomplished.  proposed  this  difficulties  envisioned  transactions might  will  Protocols  There are  scheduler  we  schedulers.  Lockinq  the  next s e c t i o n ,  and  few  the  of two  tree  practical  protocol..  17  The set  reader  i s advised  of t r a n s a c t i o n s  this and  create  and  destroy  of  is  an  e n t i t y ; an  is  be  modified  propose  of t h e s e  a  third  by  shared  first  or  context  [see two  of  In  actions  actions  locking  and  which  a given  assumed  a l l ancestors  to  form  a l . (1979)  which up  to  d-1  transactions  variable  may  a  assume d v a l u e s  0,  entity  (1979) f o r al.  directed  (1975) in  exclusive  resources  in.this  acyclic  graph.)  locking  to  entity  d-1  or  a  node i n i n t e n t i o n -  (Lockable  1,  for  intention locking  the  s h a r e an  access  the  et  shared  of  generalize may  if  Gray  node i n  the  i s intended  Silberschatz  called  in  exclusive  lock  modes].  i n t e n t i o n - e x c l u s i v e mode. are  proposed  i s intended  locking  et  and  d-locking  (i.e., the  a  in  lock  locked  state  with e x c l u s i v e  locks  d-1) . In  the  lock  locking  locks  been  A shared  Kedem  Yannakakis  is  broader  more t h a n two  include  have  made.  exclusive  mode  which a t r a n s a c t i o n mode  we  a  Papadimitriou..  between s h a r e d and  often  reading  definition  by  c o n s i s t of  locking  A distinction  entity  to  may  considering  entities.  modes  literature.  now  Locking  Various  an  are  where o t h e r w i s e i n d i c a t e d  Modes o f  to  we  than that considered  section, transactions except  1•  that  this  section  properties (a)  (b)  of  we  which may  an  e n t i t y may  at  a  be  will be  be  concerned  stated  locked  as  follows:  by  only  one  T i cannot  lock  an  transaction  time  i f a transaction  (because i t i s a l r e a d y  locked  by  entity  some  other  18  transaction Tj  2.  Predicate  Our by  unlocks  d i s c u s s i o n assumes t h a t  However, i n a d a t a b a s e • s y s t e m t o want t o a c c e s s  specifying  a  called  the  for  need  accessing  l o c k s operate  we have a s e t o f e n t i t i e s locked.  value  o f which  satisfies  o f e n t i t i e s by  key  addressing).  subsets  of  entities  of l o g i c a l locking, hereafter  described  C i s taken  Hies  1978).. F u r t h e r  examination  this  We  thesis. "phantom  as f o l l o w s  l o c k i n g has been  (Eswaran e t a l . 1976,  1  subset  (i.e.,  logical  (Schlageter  and  1978): Assume  by p r e d i c a t e C which  Then p r e d i c a t e C i s n o t e d  Predicate  the  accessed  i t would be common f o r a  values  f o r some f o r m  are  predicate locking.  Predicate  be  entities  some l o g i c a l  c o n d i t i o n on t h e i r  requirement  suggests  until  the entity.  transaction  The  T i i s suspended  Locks  previous  name.  Tj) then  down and e a c h e n t i t y t h e  f o r locked.  1  i n v e s t i g a t e d by many Stonebraker  of t h i s  1977,  researchers Schlageter  t o p i c i s beyond t h e s c o p e o f  n o t e o n l y an example  problem" i n t h e context  i s to  o f what h a s been  of p r e d i c a t e  termed  locking.  Schlageter (1978) also, investigates the possibility of identifying t h e e n t i t i e s i n t h e s e t d e f i n e d by P r e d i c a t e C and e x p l i c i t l y l o c k i n g each such e n t i t y . The r e s u l t s a r e g e n e r a l l y negative.  19  A phantom the a  current set  of  should  be  first  i s an  e n t i t y that  database  state.  entities  as g i v e n  added t o t h i s  transaction  entities called  phantoms. of  receiving this,  a  an  The  not  exist  some p r e d i c a t e . t h e n  by  another Thus,  These  may view  the  given  of  result of t h e  entities  until  the of  entities  are  phantoms d u r i n g  in  the  described  the  transaction  database.  as  locks  nonexistence  nonexistent  f o l l o w i n g example  no  transaction  materialization  transaction  the  should  example, i f a t r a n s a c t i o n  by  locked.  inconsistent  consider  For  terminates.  must a l s o be  lifetime  set  really  To  illustrate  by  Schlageter  (1978). "A process P s e a r c h e s the same o b j e c t s e t t w i c e . . The objects searched for in the first pass satisfy P r e d i c a t e A, i n t h e s e c o n d pass P r e d i c a t e A & B. As a r e s u l t o f phantom m a t e r i a l i z a t i o n t h e s e t f o u n d i n t h e second pass may n o t be a s u b s e t of t h e s e t f o u n d i n the f i r s t p a s s . " 1  3.  of  Desirable  Properties  The  performance  the  amount  Papadimitriou's  of a l o c k i n g  of  t e r m s , we  could  schedules that  protocol,  greater  we  larger less  the  consider  a  the  locking  the  say  i s evaluated  that that  it the  possible  input  protocol  to  l a r g e r the  responses  serializable schedule  and  be  in  terms  provides.  amount of c o n c u r r e n c y  c l a s s , of r e c o g n i z a b l e  r e s h u f f l i n g of  are  Protocol  protocol  concurrency  serializable  if  1  of a Locking;  of  class a  a scheduler  fewer  of  locking  provided  schedules  In  (i.e., then  would  a  mean  delays).  T h i s p a s s a g e i s t a k e n from page 267 o f S c h l a g e t e r (1978).. our t e r m i n o l o g y s u b s t i t u t e t h e t e r m s t r a n s a c t i o n f o r p r o c e s s entity for object.  In and  20  Another d e s i r a b l e to  providing  freedom  amount o f  from d e a d l o c k .  Deadlock  each  acquires  only  waits f o r the  other  deadlocks of  i s examined  locking  problem  of  policies  the  i n which e n t i t i e s  unlocked).  protocol  4.  which  a r i s e s when  In  the  a  In  describing  addition  i t ensures  each  entities.  set  are  of  that The  that  and  i t needs issue  the  (b)  a  locking  transaction  accessed  locks  a l l locks  are  (d)  a l l actions  of  not we  on  where  examine a  which i s  exclusive  (except  entities  ( i n c l u d i n g read)  entities  are  accessed  by  they  locking  not.  we  make  the  following  an  e n t i t y i s an  e n t i t y which  action  i s to  be  it  locks  lock  on  Protocol  each  accessing  not  d e a d l o c k depends o n l y (and  protocols  unlocking  p r i o r to  (c)  (e)  or  the  is  assumptions: (a)  of  subclass  transactions  another  Protocol/Tree  two  I t i s shown t h a t  subsection  free  locking  of  locked  next  i s deadlock  Phase L o c k i n g  say  entities  L-policies.  c o m p l e t e , and  Two  the  to unlock  whether  free  order  protocol, in  concurrency, i s that  some o f  called  deciding i s NP  a locking  i n Y a n n a k a k i s e t a l . (1979) f o r a  deadlock  are  of  a large  transactions and  feature  and  name  unlock)  modify  their  21  Further, (Eswaran  we  use  the  following  e t a l . 1976): C o n s t r u c t  (a)  model  a directed  w i t h a node c o r r e s p o n d i n g t o e a c h in  (b)  of  serializability  graph  D(S)  transaction  Ti  Schedule S  with  an  arc  some e n t i t y To c l a r i f y  ( T i , Tj) whenever  by T i s e r v e s  (b) a b o v e ,  l e t A1  i n S the output of  directly and  as i n p u t  to Tj  A2 be a c t i o n s  and  suppose  that S = Then  the a r c  involving proved  {...,  ( T i , A1,  ( T i , T j)  entity  would  E) , be  ( T j , A2, E) , f o u n d i n D (S) i f no  E o c c u r s between A1  (Eswaran  e t a l . . 1976)  ...}  that  and  A2  i f D(S)  in  other  S..  It  i s acyclic  action can  be  then S i s  serializability. Given a h i s t o r y us c o n s t r u c t not  the  arc  (T1,T2)  actions,  Eswaran arc  the f o l l o w i n g hi  will  a r e dead  nodes  in  transactions  (1979) l e t D(h)  would  i n h.  For  i n h = E1[XJR2[X],  but  that  a l l a c t i o n s are  appear i n the d i r e c t e d  R1[X]W2£X]  h2 = W1[X]R2[X] h3 =  The  live  a l . assume  histories: =  i n Papadimitriou  a p p e a r i n D (h) .  et  (T1,T2)  to  T1 and T2  would  used  graph D (h) .  correspond  transactions  Since  of  the d i r e c t e d  necessarily  example,  o f t h e form  W1£X]W2£X]  graph f o r  update each  22  In input R2  both to  T2  reads  al.  X  T1  states not  i s an  T2  {(lock,  T1  =  entity  any  transaction  more e n t i t i e s . and  an  a transaction  (read, E 1 ) ,  E1) ,  because  serializable  in  h2  Eswaran  et some  unlocking  phase. , The  T1  which  is  (read,  (lock,  2PL  and  E2) ,  E2)  (unlock,  E2)}  locks  2PL  because  it  requests  r e l e a s i n g a l o c k on  E1..  Eswaran  i s not  is sufficient  execution  W1  unlocked  it  2PL,  that  transaction  E2)}  2PL  as  Thus, a  (unlock,  after  case  from  has  ( r e a d , E2) ,  T2  serve  2PL:  n e c e s s a r y i n the  two  a  E2) ,  any.  to  by  (lock,  follow  deadlock.  once  proposed  E1)  concurrent  The  protocol  (unlock,  E2  does not  (2PI)  (read, E1),  2PL  also  reads X  E1) ,  have shown t h a t and  E2  {(lock,  is  unlocking  i s said  h i s t o r y i s i t the  l o c k i n g phase  E1),  T1  h2.  example o f  (unlock, T2  in  lock a  X by  Note a l s o t h a t  which i s not  =  o u t p u t of  that  phases:  following another  W1.  i s dead  i t may  two  h3,  phase l o c k  (1976)  has  from T2  two  entity,  and  even t h o u g h i n n e i t h e r  even t h o u g h The  hi  for  sense t h a t  then of  a l l required  there the  entities  ensuring  a et  lock  serializability  some  pair  ( T i , Tj)  protocol  does  not  consider  two  on  al..(1976)  i f a transaction,  exists  before  Tj  may  say  such  Ti, that  produce a  non  schedule. phase l o c k  To  see  this  ensure  transactions  freedom T1  and  T2  from where  T1  =  {(lock,  E l ) , ( l o c k , E2)  (unlock,  E1) ,  (unlock,  E2) }  T2  =  {(lock,  E2) ,  (unlock,  E2) ,  (unlock,  E1)}1  ( l o c k , E1)  23  Note t h a t concurrently in  locking  the  other  b o t h T1  and  such t h a t E2,  to  T2  T1  its  2PL.  Now,  i f T1  succeeds i n l o c k i n g  then each  unlock  are  transaction entity..  will  E1  and and  T2 T2  are  succeeds  wait i n d e f i n i t e l y  Hence,  T1  and  run  T2  will  for be  deadlocked. How  i s i t clear that  deadlock,  i t is clear  possible  schedule  of is  transactions because  entities  before  occur  with  before  Tj  Further, of  i f each  and  arcs  transactions  about  the  i n D (S)  be  organized  have  as  rooted  1  been shown t h a t  trees  and  the  these l o c k i n g  policies  depend c o u l d  i s usual  show o n l y  the  This all its  of  Ti  not entity does.  the  set  then  the  i s e s s e n t i a l l y necessary syntactic  information  lock by  Kedem and Protocol  The  entities.  unlock  protocols  relying  on  Silberschatz for  for  structure  in practice  l o c k and  on  set  order.  protocol  graphs.  physical organization  we  before  is acyclic  DAG  a  could  relation  Tree  acyclic  As  situation  serializability  a  of  lock  relation  only  directed  or  must  system i s a v a i l a b l e , o t h e r  proposed  every  2PL.  a binary  2PL  when  as  logical  execution  entity  about database o r g a n i z a t i o n . .  1979)  organized  an  in a linear  which g u a r a n t e e  for  i n w h i c h T i u p d a t e s an  i f this  embedded  a  Ignoring  acyclic  in T follows  Thus,  represent  S and  transaction  information  be  a transaction  updates  serializability  have been d e r i v e d  (1978,  Tj  in  can  ensuring  that  two . t r a n s a c t i o n s  A l t h o u g h i t has for  will  transaction  r e l e a s i n g any.  does  transactions  D(S)  reguires  say  the  that  ensures s e r i a l i z a b i l i t y ?  r e s u l t i n g from c o n c u r r e n t  T,  2PL  2PL  refer For  steps.  databases databases upon  which  to  some  illustration  24  p u r p o s e s we as  focus  A  transaction  database (b)  the  Tree p r o t o c o l  (c)  w h i c h may  be  stated  is  currently  if  i t  (c)  Kedem  Practical  may  a given the  and  greater other locks.  granule  hand,  unlock  not  freedom  an  entity be  two  the  entity  a  lock  at  any  locked  from  tree  phase  on  the  at  time,  most once  protocol  locked.  may  result  Silberschatz  protocol guarantees  both  deadlock.  for a transaction  more a p p r o p r i a t e of  A granule  a relation,  cost  an  Considerations  some l a r g e r g r a n u l e  small  lock  holding  e n t i t y may  which a r e  i n p r a c t i c e be  a file,  the  same t r a n s a c t i o n .  When i t i s n e c e s s a r y  entities.  may  (1978) have shown t h a t t h i s  serializability  entity in  father.  above i t i s c l e a r t h a t  transactions  first  locked.  only  within  may  be  transaction  A transaction  From  to  s e l e c t the  the  however  and  tree  may  Subsequently,  entity's  5«-  on  follows: (a)  in  here  the  context  a column of  i n managing inhibits  f o r the  might  be  a relation,  a  a greater  locks..  concurrency  but  the  a record,  amount of  A large  entities  transaction to  d a t a b a s e which c o n t a i n s  in this  s i z e allows  to lock  tuple,  minimizes  size,  lock  required a  page,  etc.  concurrency  granule  i t  A at  on  management  a  the of  25  Ries  and  overheads that  involved  a fairly  parameters and  Stonebraker  I/O  was  In  a  granule  parts  i s optimum  Their  conclusion  g r a n u l a r i t y s u c h as study  such  (Ries  i f  the  all  if  then  several  are  fine  These s t u d i e s of  greater  managing  access  procedures. completion  Back  not  be  Back  out  to  locking,  facilitate may  of a t r a n s a c t i o n  in  of  the  be that  any  by  a  transaction  t r a n s a c t i o n as  in  data.  desirable  example,  is  it  small  of  a  Bjork  Uncommitted  data  is is  back  out  constraint  Most s y s t e m s each  upon has  maintain  transaction.  undoing a l l changes  log.. It  (1973) t h a t  transaction  to  ensuring  i f i t i s found  involves i n the  due  the  cost.  some c o n s i s t e n c y  then,  the  preferred..  transaction  d a t a b a s e by  was  preferable.  a d d i t i o n to  necessary  recorded  (1973) and  work c o r r e c t l y i f  the  advantages  this  i f deadlock i s detected.  Davies  uncommitted  that  outweighed  for  out  and  of a l l c h a n g e s made t o t h e  made by out  may  is  been v i o l a t e d o r log  i s high,  motivation  serializability  several  large portions t o be  is  locking.  of i n t e r e s t b e c a u s e t h e y i n d i c a t e t h a t  locks  concurrency  Another  a  are  locking  randomly a c c e s s i n g  granularity  transactions  results  1979)  model showed t h a t  transactions  database  or a r e a  For  such  utilization  page o r r e c o r d  i s more a p p l i c a t i o n d e p e n d e n t .  show  of  these  Stonebraker  the  study  terms  on  file  database then coarse g r a n u l a r i t y i s again  cost  in  based as  and  assumptions i n t h e i r  that  simulation  t h r o u g h o u t , r e s p o n s e t i m e , CPU  to f i n e later  However,  size  by  r e s u l t s of t h i s  granularity  size  of  The  coarse  alternative  found  system  utilization.  preferable  examine  in locking.  large granule  as  that  (1977)  this  is  procedure  permitted data  pointed  to  may  update  which has  been  26  updated  by  backed  a transaction  see  the  transaction  problem  T1  a l s o have t o be A need should  be  for held  technique  propagation locking  will  by  another t r a n s a c t i o n  undo T2's  update.  of  end  a transaction.  i n System R that  the  require  (Astrahan  two  r o l l b a c k due  phase  to  course,  hardware o r  et  be  later  some o n g o i n g  T2.  Then  back  Hence,  T2  will  lock  be  propagation  locks  This  for  protocol  to  "prevents  the  of r o l l b a c k  software errors)  the  Schlageter  Recall that  held  update  i s exactly  al..1976).  deadlock".  that locks  reasons  two end  due  i s possible  phase of  to  the  a  other  with  two  locking.  Other  Systems  This  section  provided  by  System  System system  updated  t o the  does n o t  (i.e.,  data  backout suggests that  Of  1.  may  out.  transaction.  D..  which  "isolated"  out  of  T1  backed  used  (1978) p o i n t s  suppose t h a t  i s u p d a t e d by  of t r a n s a c t i o n  phase  i n progress  out.  To  out  still  a number  R  et  relational  data  of  on  views  external  of  concurrency  control  facilities  systems.  R  is  developed  (Astrahan  describes  an at  experimental prototype database  management  the  Laboratory  a l . 1976).  IBM The  i n t e r f a c e which common  relation  is a  San  system  Research  provides  permits d e f i n i t i o n  underlying view.)  Jose,  data.  (The  a  high  of  a  level  variety  SEQUEL term f o r  an  27  The SEQUEL  principal data  (1974). the  cursor marks  sublanguage  System  host  language f o r i n t e r a c t i n g with described  R accomplishes  a  a  positioned  by  tuple  means  of  p a r a m e t e r s a SEQUEL g u e r y an by  active  concept  name which i d e n t i f i e s  particular  Chamberlin  within the  called  a  R i s the  and  t h e i n t e r f a c e between  l a n g u a g e by means o f a is  in  System  Boyce  SEQUEL and cursor.  A  an a c t i v e s e t o f t u p l e s and this  SEQUEL  and a c u r s o r  set.. A  operator  is  which t a k e s as  The t u p l e s  within  s e t may be r e t r i e v e d one a t a t i m e by a u s e r  program  means o f a FETCH command  name.  cursor  which t a k e s  as an argument a  cursor  name. An  alternative  FETCH-HOLD command command  except  returned. the  until  i t  the holding  R employs  and  recovery  predicates.  a  hold  u s e r s from  The  on  updating  the  tuple  or d e l e t i n g  r e l e a s e d ( by means o f a RELEASE  transaction  sophisticated  including  subsystem,  transaction Integrity  very  i s provided.  t h e same way a s t h e FETCH  acquires  prevents other  database c o r r e c t n e s s and  also  i ti s explicitly  command) o r u n t i l System  o f t h e FETCH command  operates i n exactly  that  A hold  tuple  form  integrity  automatic  has t e r m i n a t e d . facilities  f o r ensuring  assertions,  a  l o c k i n g , deadlock  logging detection  back o u t p r o c e d u r e s . assertions  Assertions  are  specified  may d e s c r i b e  by  means  permissible  t r a n s i t i o n s i n t h e database.  automatically  any  violates  an a c t i v e  checked  at  integrity  data  modification  assertion.  t h e end o f e a c h t r a n s a c t i o n ,  b a c k e d o u t i f some a s s e r t i o n i s v i o l a t e d .  The s y s t e m  command  Assertions  SEQUEL  s t a t e s of the  database o r p e r m i s s i b l e rejects  of  which  are normally  and t h e t r a n s a c t i o n i s If  an  assertion  is  28  specified  as  modification In  remainder  concurrency user defined  (b)  multiple  (c)  locking  user  of  PL/1  commands.  A user  transaction.  may  which  long  system  Thus,  defines  transaction  transactions. during  read  Level users.  containing  three  specify  SEQUEL d a t a save  distinct  data  until  will  not  that  undo  save of  he must s p e c i f y  first  may  point.. consistency. the l e v e l at levels  by a t r a n s a c t i o n  i snot  transaction  backout  in  his  consistency  terminates.  of m o d i f i c a t i o n s  modifications  differences  within  i s a c t i v e the user  At a l l t h r e e  the  i s  manipulation  points  levels  modified  R by means o f  made  consistency  by  by  other  levels  occur  from  other  operations.  this  level  Such a t r a n s a c t i o n values  or  data  which  set  the  inaccurate  the  Such a t r a n s a c t i o n  c r t o any i n t e r m e d i a t e  1 consistency At  on  R:  i n System  operators.  can guarantee  The  focus  o f System  as a t r a n s a c t i o n  guarantees that  t h e system  we  granularities  h i s transaction  by any o t h e r  data  consistency  he w i s h e s i t t o e x e c u t e .  modified  one  of  also  R supports  When a u s e r  subsection  h i s own t r a n s a c t i o n s  backup t o t h e b e g i n n i n g System  each  transactions  program  As  after  transaction.  this  BEGIN-TRANS and END-TRANS a  checked  control features  levels  defines  is  each  at various  basically  the  i t  within  (a)  A the  command  the  following  IMMEDIATE  data  offers the least a transaction  incurs  the r i s k  values values  which i s  gathered  may r e a d  of reading  never e x i s t e d  later by  isolation  a  backed level  uncommitted  data.  inconsistent  data  i f the transaction  out.  The  1 transaction  possibly would be  29  unsuitable  as a b a s i s  commitments for  to the outside  statistical  employ  the  uncommitted Level see  reporting.  HOLD  consistency  uncommitted  data.  level  i ti s possible  commit  that  to  guarantees  is  A single  may  itself  that  however,  explicitly  from  losing  seeing  updates.  a transaction  not guaranteed).  f o r another  does n o t  may n o t s e e t h e  i t terminates.  losing level  reproducibility  transaction  is  transaction  the  only  F o r example, i f a whose  to  salary  Recall  transaction  which  may be used  level falls  will  be  deleting  employee  by a guard  employee  to t h i s  set.. Level  explicit  HOLDs.  The p r o b l e m  read  transaction  not  f o r changes  accesses a l l  a c e r t a i n r a n g e , t h e same  only  from  Concurrent updating  or  s e t b u t a l s o f r o m a d d i n g an  consistency  of l o s t  read  reproducibility  the t r a n s a c t i o n .  this  and  of a  but a l s o t o c o l l e c t i o n s o f  within  within  3  equivalent  i s committed  This  3  prevented from  logical  {except, o f c o u r s e ,  single tuples  occur every time  transactions  the  itself).  tuples.  an  successive  2 transaction.,  operator  read  guaranteed  not  answer w i l l  two  r e p r o d u c i b i l i t y and t o  sees  A l l data  applies  employees  as  HOLD  to ensure read  system.  made by t h e  as soon  consistency  t o m o d i f y an e n t i t y  between  level  (i.e.,  updates. 3  user  interval  The  At t h i s  transaction  t h e e n t i t y by a g i v e n  2 transaction  against  protect  or t o g u a r d a g a i n s t  d a t a becomes c o m m i t t e d  level  1 transaction  t h e change i n t h e of  modifies  A level  making  f o r an e n t i t y e a c h t i m e t h e e n t i t y i s a c c e s s e d  reproducibility  accesses  for  I t may be a d e q u a t e ,  However, t h e t r a n s a c t i o n  read  and  or  world.  operator  modifications 2  same v a l u e  f o r updating t h e database  does  not  require  updates i s e l i m i n a t e d .  30  To sets  guarantee  locks  which  consistency  automatically  granularities.  applied  f o r transactions  coarser  may be  tuples.  The p r o t o c o l  Gray e t a l . System  management,  that of  chosen  of  locks  access lock  for  only  (i.e.,  explicit  are  applied  tuple  a t the l e v e l  locks  HOLDs  To r e d u c e t h e  which i s that  at  locks are  a few t u p l e s ,  transactions  f o r reguestinq  System R  whereas  o f a whole  access  many  described i n  (1976). R employs  r e l a t i o n s and t u p l e s physical  the exception  levels,  F o r example, i n d i v i d u a l  granularity  relation)  various  1 and 2 t r a n s a c t i o n s ) .  f o r lock  various  a  (with  may be s e t by l e v e l  overheads r e q u i r e d  a t these  level,  locking  both  at  the  and a t t h e p h y s i c a l  locking  is  logical  level  level  o f pages.  used t o g u a r d a g a i n s t  of  At t h e  occurrences  such a s t h e f o l l o w i n g : "... a d a t a page may c o n t a i n s e v e r a l t u p l e s with each tuple accessed through i t s t u p l e i d e n t i f i e r , which requires following a pointer within t h e data page. Even i f no logical conflict occurs between two t r a n s a c t i o n s b e c a u s e each i s accessing a different relation or a d i f f e r e n t t u p l e i n t h e same r e l a t i o n , a problem c o u l d occur at t h e p h y s i c a l level i f one transaction f o l l o w s a p o i n t e r t o a t u p l e on some page w h i l e the other t r a n s a c t i o n updates a second t u p l e on the same page and c a u s e s a d a t a c o m p a c t i o n r o u t i n e t o reassign tuple locations." 1  A distinction for tuple  logical  lock  transaction  1  This  locking..  For  and e x c l u s i v e  a l l three  i s t o be i n s e r t e d o r u p d a t e d  exclusive  level  between s h a r e d  i s held  on t h e t u p l e  terminates.  Read  3 transactions  passage  page  consistency a  is  made  levels  i fa  transaction  ( o r some s u p e r s e t )  reproducibility  by m a i n t a i n i n g  i s taken from  by  locks  shared  then  an  u n t i l the  i s achieved f o r  l o c k s on  a l l tuples  124 o f A s t r a h a n e t a l .  (1976).  31  and  index  values  transaction. accesses lock so is  r e q u i r e a shared  then  for  i s enqueued b e h i n d  do n o t have t o  be  duration  2  of reading  committed  For  since  purposes  with except  above.  assertions  for  the concept  checking  a l o g g i n g and r e c o v e r y provided  comparison  with  space  designed.  The l o c k  transactions  e t a l . . 1976) i s a n o t h e r  System E , s u p p o r t s  facilities  address  data.  has been g r a n t e d ,  l o c k s on pages as d e s c r i b e d  (Stonebraker  which, l i k e  provides  requests  '  INGRES  integrity  read Such a  exclusive lock  1 1 1  the  consistency  1 c o n s i s t e n c y , no l o c k s a r e h e l d f o r r e a d  physical  of  immediate d u r a t i o n .  earlier  repeatable.  the  level  r e l e a s e d as soon as t h e r e q u e s t  2- - INGEES  by  those  provided  limitations  by  of  updates,  System  of t h e PDP-11s f o r  are  B, l a r g e l y  in  due t o  INGEES  whereby c o n c u r r e n c y  and  control  limited  which  DBMS  provides  The c o n c u r r e n c y  however,  INGEES p r o v i d e s an o p t i o n  view,  validity  scheme.  INGRES,  of a  relational  was  control  be t u r n e d o f f . The  execute  primary  guery  QUEL s t a t e m e n t s  language supported and o t h e r  a t e r m i n a l , o r INGEES may written  in  QUEL embedded  1  read  l o c k with  that the user i s assured  level  can  are  " F o r t r a n s a c t i o n s with  request  reads  for  that  EQUEL.  EQUEL  be  INGEES u t i l i t i e s  invoked  from  from  i s a special  i n t h e g e n e r a l purpose  This passage i s taken  page  i s QUEL.  directly  within  language  programming  126 o f A s t r a h a n  Users  a  may from  program  consisting of  l a n g u a g e C.  et al..(1976).  32  Integrity  assertions  qualification  clauses.  execution  ANDinq  by  This  possibly  any  support  the  A  specified  user's  appropriate  qualifications. violate  are  has  the  R  request  means  with  that  assertion..  transition  of  QUEL  i s modified  assertions effect  integrity  System  by  no  before  existing  reguest  INGRES  assertions  can  does  or  not  deferred  assertions. The  reader  transaction  differently  transactions Throughout writers An  i s cautioned  are the  not  QUEL  data  designers  defining (a)  a  of  (b)  considered  a collection  (c)  been u s i n g  consistency  this  subsection,  command various  as  one  it.  term  INGRES  preserving.  whenever INGEES  we use t e r m INGRES  defined  the  transaction.  INGEES  command  o r INGEES u t i l i t y ) . . other  alternatives  The for  of  INGRES  commands  with  no  C code o f INGRES commands  w i t h C code but no  calls  (a) i s p e r c e i v e d  by INGRES d e s i g n e r s  of the chosen a l t e r n a t i v e  implement  given  a  generalization  minor  have  use  an a r b i t r a r y EQUEL program  Option extension  writers  including the following:  collection  system  i s  manipulation  intervening  we  transaction  a transaction  INGEES  necessarily  INGRES t r a n s a c t i o n  INGEES  sufficient  system c o m p l e x i t y Defining (c) ]  than  remainder  use t h e term  (i.e.,  that  required  user  minor  Option  (b) i s s e e n  as  (a) n o t worth t h e a d d i t i o n a l  f o r i t s implementation..  an INGEES t r a n s a c t i o n  i s , i n the opinion  a  (one which t h e y p r o m i s e d t o  demand).  of o p t i o n  t o be  as an EQUEL program  o f t h e INGEES d e s i g n e r s ,  [option  impossible  to  33  support. create  Such a t r a n s a c t i o n and  destroy  intermediate designers  system  as  in this  depend  on  is  of  this  afford  type,  that  for  out through  resolution  by  INGRES  calls.  may  Hence, t h e r e i s may  R supports a R designers of  be  statement  transactions  System  say  that deadlock cannot  o f a QUEL  from system two  of backing  to  deadlock. transaction  could  deadlock  better  (i.e.,  R i s an e x t e n d e d  the  version  VM/37 0) . designers  resolve)  entities  allowed  amounts  interrogated  again.)  protocol.  The  This lock  lock  are  i s and  not  a l l  locks. inserted  c l e a r from  exclusive  used  a transaction  accomplished  is  locks a l l  via  requests  a  into  the  LOCK i s not  1  can  physically  I f no l o c k s  conflict LOCK  employed  be  locked  by  and then  relation. and  a v a i l a b l e documentation are  INGRES  An i n t e r a c t i o n  lock  detect  by  for a fixed interval  locks  Locks are r e l e a s e d  An i n t e r a c t i o n may c o n s i s t  is  relation  ( r a t h e r than  protocol  reguests.  unless  forconflicting locks  lock  the i n t e r a c t i o n waits  It  both s h a r e d  The  to r e q u i r i n g t h a t  records  proceed  required  Otherwise,  chosen t o a v o i d  i n one s t e p .  which to  have  deadlock.  granted.(i.e..  1  because e x e c u t i o n  s y s t e m e n v i r o n m e n t f o r System  relation  all  I t i s noted  i n advance t h a t  system c a l l s  deadlock i s seen  p r e s u m a b l y b e c a u s e System  transactions its  case  t h e overheads  INGRES and  to r e s o l v e  i n t e r e s t i n g t o note  operating of  calls  contain  The o v e r h e a d  r e s u l t s obtained  way t o t e l l  It  files.  prohibitive.  avoided  no  could  tries whether  the  lock  a t t h e end o f each i n t e r a c t i o n .  of more t h a n  one INGRES  transaction.  34  It  is  offered locks will  not  clear  what  by t h e INGEES l o c k  are exclusive always output  consistency  locks  preserving  inconsistent  correctness  protocol.  If  schedule  transactions.  the lock  assume  that a l l  protocol  preserving.  when used  protocol  when used by a s e t o f  When  used  may r e s u l t  by a s e t o f  in a  schedule  C l e a r l y , any l o c k  always outputs a s e r i a l  schedule  we  guarantee i s  then i t appears t h a t t h e l o c k  which i s n o t c o n s i s t e n c y one t h a t  of  a serializable  INGEES t r a n s a c t i o n s ,  even  sort  by  schedule  non  protocol  may r e s u l t  consistency  i n an  preserving  transactions. It  appears  no c o n s i s t e n c y that  the  executed  also that preserving  read  and  user  u n i t , then  update  indivisibly.  different  INGRES may l o s e  of  updates.  there  an  I f there i s  i s no way t o  require  e n t i t y by t h e same u s e r be  Hence, an update o f t h e same e n t i t y by  may  get  interleaved  that  some p r o t e c t i o n  such t h a t  an u p d a t e  a  gets  lost. We s p e c u l a t e offered  by INGEES.  of  interaction,  an  carefully  This by  to  Second,  mean  not allowing  that  locks  updates  i t  several  value  lost  a r e held  will  updates  f o r the duration  which that  will INGEES  comprise  read.  variable  and u p d a t e  to  be  i t appears t h a t  however,  as  they  These have  statements not  command.  be a v o i d e d  based  on  a  the f a c i l i t y  commands a s an i n t e r a c t i o n c o u l d  transactions.  his  automatically  update s i t u a t i o n s w i l l a  i s  be p r e v e n t e d i f a u s e r  into a retrieval  t h e update o f  to define  speculative,  appears  some l o s t  and e r r o n e o u s  process  general  lost  any u p d a t e command  would  previous  since  s e l e c t s t h e INGEES commands  interaction.. converts  First,  against  be used i n are  highly  been p o i n t e d  o u t by  35  INGEES  writers.  The a  relation)  large is  granularity  lock  lock  reflecting  table  proposed  provided  of  i s not  in  at  an  is  a  is relatively  an  environment  available.  the  hope t h a t  coarse  (on  where c o r e  A predicate  considerable  acceptable overhead i n lock  domains  storage for  locking  space  a  scheme  concurrency  table  of  may  and  be CPU  time.  3.  IMS  IMS running  primarily  consists  of  means o f  a  mapping  to  program  a  PCB  of  essential features i s referred  in  A database i s defined  tree The  represents definition  and  also  set of  IMS  user  database  the  a  means  a l l occurrences The  following  for further details:  a tree node  structure  (i.e.,  database. one  The  root  may  have any  number  segment t y p e s .  Each  child  have any  number o f  child  a  of the d e f i n i t i o n  exactly  type.  of  h i e r a r c h i c a l d a t a model. .  a segment t y p e i n t h e tree  a  When a  as  record.  1977)  Each  by  IMS.  ordered  by  view  specifies  contains  segment child  also  storage  database  to D a t e (  tree).  which  logical  of t h e  for  databases, each defined  particular  program  physical  definition  (b)  the  external  database.  maintained  between  type  reader (a)  is  a  user's  physical  p h y s i c a l d a t a b a s e i s an  describes The  on  provides f a c i l i t i e s  A  logical  corresponding  operating  communication  one  batch a p p l i c a t i o n s .  program c o n t r o l b l o c k (PCB)  is  Each  DBMS w h i c h  a c o l l e c t i o n of  associated  of  hierarchical  of  the  root  root  segment t y p e s  and  of may so  36  (c)  on  t o any  A  database  the of (d)  number o f  levels.  record  database  c o n s i s t s of  of a s i n g l e  dependent  occurrence  r o o t segment and  a  in  number  segments.  A database r e c o r d f o l l o w s the the  the  definition  one  occurrence  be  zero  or  tree  with  o f any  given  more  template  the  imposed  exception  segment t y p e  occurrences  of  by  that for there  each  may  of  its  children. IMS  provides  maintaining restart  a  as  not  explicitly  pointed  t h a t can  values  (for  multiple enforced  be  by  out  viewed IMS  segments  valued).  example,  routines  including  to  assist  checkpoint  in and  out c h a n g e s made t o  procedures  f o r maintaining  the  provide  i n Date as  a  the  (1977), t h e r e  enforces  the  exist  have  hierarchical  without  segment t y p e  and  t o t h a t of E1,  then  E2". o f E2  are  unigueness of  Second, c e r t a i n  s u p p o s e t h a t E1  assertions. two  mechanisms f o r h a n d l i n g  which  very  integrity  E2  seguence consistency  I f the  segment  hierarchical  d a t a b a s e s t h a t an  cannot e x i s t  without  are  IMS  occurrence  not are  database. and  database that  "E1  database i s organized  g u a r a n t e e d by  i t s parent.  and  field  occurrences  i s s u p e r i o r i n the  C would be  consistency  constraints  s t r u c t u r e of an are  features  seguence  fields  a c o n s i s t e n c y c o n s t r a i n t C a p p l i e s t o the  cannot that  of  f o r backing  program, and  constraints. , First,  that  correctness  procedures  given  does  However,  For  set  log.  IMS  o f IMS  by  complete  database  procedures,  database system  a  the  definition simple  of a dependent  rule  such tree for  segment  37  IMS  provides  facilities. systems the  a  The  we  a  s e t of concurrency  difference  in this  regard  The r e m a i n d e r  control  First,  complete  between  of this  a l l occurrences  exclusive  mode.  o f an IMS  will  program  i f i t s PCB e n t r y c o n f l i c t s  with  i s already executing. t h e EXCLUSIVE  GET  particular places  HOLD  segment  the  occurrence,  (i.e.,  command.  other  not  the  updating  i t .  Third, which  may  be  that  of  program  may  set  program  i f either  type. against  forms  neither  locked GET  ensures  locks  on  lost  retrieve command  a  also  a  in  nor  GETmodify  exclusive  GET-HOLD  t h a t two u s e r s with  the will  the i n t e n t i o n o f  be o v e r w r i t t e n . segment  occurrences  and r e l e a s e d by a u s e r p r o g r a m .  t o t h e number o f  h o l d a t one t i m e ,  a  are provided: a  a GET-HOLD  f o r a segment  shared  are  When a segment i s h e l d by  is  procedure  explicitly  there i s a l i m i t  t o guard  command  Hence, segment u p d a t e s c a n n o t  Although  any  by o t h e r u s e r s b u t n o t v i a  may  value  IMS s u p p o r t s  type  When t h e h o l d i n g u s e r i s s u e s a  users  Note t h a t t h i s same  however  occurrence  segment). read  segment  not l o a d and i n i t i a t e  Both  segment i n h o l d .  segment  program may s p e c i f y an  mechanism  version.  i t may be r e t r i e v e d  retrieval  command mode  GET-HOLD  the retrieved  one u s e r  no  d e s c r i b e s IMS  o p t i o n f o r t h e same segment  Two v e r s i o n s o f e a c h r e t r i e v a l  v e r s i o n and a  (i.e.,  Two PCB e n t r i e s c o n f l i c t  S e c o n d , IMS p r o v i d e s a h o l d updates.  user  section  entire  in  specifies  and' o t h e r  facilities.  locked  which  control  i s t h a t IMS l e a v e s most o f  PCB a s s o c i a t e d w i t h a u s e r  whereby  IMS  f o r l o c k p r o t o c o l s up t o t h e  locking).  concurrency  option  primary  have seen  responsibility  automatic  fairly  this  such  facility  locks  appears  that  a  sufficient  38  to guarantee consistency protocol that  by a l l c o n c u r r e n t  IMS  permits  occurrences given  (assuming  to various  lock  following  a  class  programs). user  lock  may  j u d i c i o u s use  to  a  locking  I t i s i n t e r e s t i n g t o note  delegate  classes.  different  A l l segments  t h e n be u n l o c k e d  i s an example o f s u c h  of  segment within  a  i n one o p e r a t i o n . . The  l o c k i n g and  unlocking:  GU PRESIDENT*QB(NAME= JOHN') 1  DEQ B The  •*Q' i n t h e  retrieved  segment  GET  UNIQUE  should  be  following  t h e *Q i s t h e l o c k  releases  a l l shared  that  a hold  functionally  locks  when a c h e c k p o i n t locks  specifies  i n shared  mode.  the  The 'B'  dequeue  command  (DEQ)  on segments i n l o c k  c l a s s B.  Note  and  The  that  shared  lock  on  a  segment  are  identical.  Exclusive  Shared  locked  class.  locks  on a segment  command  are released  operation  within  are also released  initiated  by  a  program  unlocking  strategy  or  appears  when a program the  program  at these times.  by  the  system.  sufficient  to  terminates or i s  executed.  B a c k o u t may be The  automatic  guarantee i s o l a t e d  backout. Finally, PCB  (called  allowed  IMS p e r m i t s the  BEAD  EXPRESS  t o see uncommitted  programs.  A program  known a s a l e v e l  specification option)  changes  of  an  option  whereby  made  by  a  program i s  other  wiiich u s e s t h e BEAD EXPRESS o p t i o n  1 transaction  i n System  R.  i n the  concurrent would be  39  4.  DBTG  In Task  this  Group  system  section  we  1976).  In  provisions  for specifying  DDL,  and  in  first  briefly  a given  network  set  segment  in the  occurrence  and  t o Date  (1977)  may  term  A set type c o n s i s t s  for further  active  program  specifies  the  area,  1  a l l  occurrence  basic  of  the  table  most r e c e n t l y within record  schema  c o n t r o l . . We  the  than  fundamental  a hierarchy i n  number o f  of one  immediate  each types.  of  An  The  the  of  reader  one  owner  model.  fundamental  notion  t h e DBMS m a i n t a i n s f o r database  key  r e c o r d t y p e , w i t h i n each most r e c e n t l y  within a l l record types  of a  i s referred  values  referenced record occurrence  The  record  occurrence  network d a t a  on t h e  The  and i n c l u d e s owner  occurrence  d e t a i l s on  idea i s that a  i n the  the  r e c o r d f o r segment  more member r e c o r d s .  The  based  concurrency)..  have any  DBTG d a t a s u b l a n g u a g e r e s t s  user  with  Base  number o f i m m e d i a t e d e p e n d e n t s ) .  consists  of c u r r e n c y .  within  model and  o r more member r e c o r d t y p e s .  zero or  in  f o r concurrency  network d a t a  uses t h e  database  record  The  t h e Data  are i n t e r e s t e d  mere g e n e r a l s t r u c t u r e  of a s e t . one  we  constraints  statements  the  is a  approach  and  each  integrity  (as w e l l a s any  concept  type  DML  review  network  superiors  the  the  particular,  o f c u r r e n c y ( n o t t o be c o n f u s e d  A that  p r o p o s a l s made by  (DBTG) f o r m a i n t a i n i n g c o r r e c t n e s s i n a network  (CODASYL,  notion  review  i s called  each which  within  set type  and  referenced record  the c u r r e n t of  run-  unit.  1  The s t o r a g e s p a c e f o r a DBTG d a t a b a s e number o f named a r e a s .  is  partitioned  into  a  40  The the  DBTG p r o p o s e s  form  of p r o c e d u r e  procedure during The or  is  d e c l a r a t i o n s i n t h e schema  automatically  a particular  cf integrity  invoked  operation  s e t . . E x a c t l y when t h e p r o c e d u r e  also  specified  as  may be s p e c i f i e d  which  feature  ranges  those  DBTG f a c i l i t i e s  of  IMS  in  Rather,  i t is left  control  s t r a t e g y based The  concurrency  control  wishes  available  how  he  control  not  of this  primitives:  how wishes  R e t r i e v a l - given - other  (b)  Update  (c)  Protected  execution  data  item.  values or  are similar  to  applied automatically. h i s own  concurrency  concurrency  section  control  d e s c r i b e s two  such  f o r any  area  which  he  two t h i n g s when he s p e c i f i e s a  himself concurrent  usage-modes a r e d e s c r i b e d  (a)  is  usage-mode and m o n i t o r e d - m o d e .  a usage-mode  he  after  a specified  available  A user i n d i c a t e s  usage-mode: F i r s t , Second,  are  the  remainder  must s p e c i f y  to use.  on  invokation  Additional constraints  up t o t h e u s e r t o d e v e l o p  primitives.  A user  they  item  items.  f o r concurrency  that  object.  as w e l l a s  f o r example, t o s p e c i f y  o f values allowed f o r data  The  the  a  o r on e r r o r  be i n v o k e d  are a u t o m a t i c a l l y checked  be u s e d ,  Such  particular  trigger  operation involving  could  DDL.  an a r e a , r e c o r d , d a t a  p a r t o f t h e schema.  a s t o r e or modify  This  a  should  o b j e c t and o p e r a t i o n t h a t s h o u l d  constraintsi n  before, after  affecting  o b j e c t may be t h e schema i t s e l f ,  the  of  specification  wishes  to  use  the  area.  users t o use t h e area.  The  below:  u s e r w i s h e s t o r e a d from t h i s a r e a u s e r s may r e a d o r w r i t e i n t h i s a r e a  •- g i v e n u s e r w i s h e s t o w r i t e i n t h i s - o t h e r u s e r s may r e a d o r w r i t e Retrieval - g i v e n u s e r w i s h e s t o r e a d from t h i s - o t h e r u s e r s may r e a d b u t n o t w r i t e  area  area  41  (d)  Protected  Update - g i v e n user wishes t o w r i t e i n t h i s area - o t h e r u s e r s may r e a d b u t n o t w r i t e  (e) E x c l u s i v e R e t r i e v a l - g i v e n user wishes t o read - o t h e r u s e r s may n e i t h e r r e a d (f)  E x c l u s i v e Update - given.user -  A user  other  i s not a l l o w e d  usage-mode  has  already  wishes t o write i n t h i s  users  may n e i t h e r r e a d  access  t o an a r e a  The f a c i l i t y  f o r ensuring  use  area  be e f f e c t i v e l y  an  correctness.  large  because  which  differs isolating this  i f a  conflicting  the  protected used  mechanism  unit  or  exclusive  t o ensure  severely  of l o c k i n g  by some  database restricts  ( i . e . , an area)  i sa  scheme  from  provide  for  an  any t h a t we have seen  a user  from  mechanism  additional  so f a r i n t h a t , r a t h e r  the a c t i v i t i e s  other  the  basic  idea  of  the  i s as f o l l o w s : A u s e r may e x p l i c i t l y p l a c e a r e c o r d  into  monitored-mode.  user  monitored-mode.  in  by  A  has  the  record  A r e c e i v e s an e r r o r  what t o do n e x t .  the  record  in  monitored-mode  to change t h e r e c o r d w i l l f a i l  changed  User  him t o d e c i d e  criticism  The  I f a u s e r . A, h a s a  attempt  concurrent  users.  notify  concurrent of  of other concurrent  to  of  user  an  attempts  mechanism  a  activities  to  this  DBTG p r o p o s a l s  users,  then  nor write  p o r t i o n o f the database. The  than  might  However,  concurrency  area  been e s t a b l i s h e d f o r t h a t a r e a  other user. of  nor write  literature  since  requested  message and i t i s up  Monitored-mode  (Engles  A  i f some  1971,  has  1977).  received The b a s i c  problems a r e as f o l l o w s : (a)  When a r e q u e s t t o m o d i f y mode f a i l s ,  a  record  in  t h e r e i s no way o f f o r c i n g  monitoredthe user t o  42  handle {h)  No  the s i t u a t i o n protection  uncommitted  is  from  currently (d)  One u s e r  provided  changing  to  data  may t r a n s f e r from  one  (A p o s s i b l e r e s u l t  concurrent  a given  user's  user i s  current  record occurrence  i s that a  user,  unaware  that  himself traversing  scheme.  to  r e p l a c e t h e DBTG n o t i f y  One such  a LOCK s t a t e m e n t  which p e r m i t s  a user  o f r u n - u n i t . . [Some s i m i l a r et  a l . (1S75).]  problems i n c l u d i n g (1976) b a s e d  Current  We c o n c l u d e  A unified  this  has  provides  to e x p l i c i t l y  ideas  lock  solution  a  t o be t h e  were p r o p o s e d  been  a n d the c o n c e p t  Hot R e s e a r c h  p r o t o c o l with a  when t h e r e c o r d c e a s e s  concurrency  on l o c k i n g  Programming  p r o p o s a l made by UNIVAC(1976)  current  Hawley  may  t h e wrong s e t o c c u r r e n c e . ) .  p r o p o s a l s have been made t o t h e CODASYL  Committee  of  t o another.  find  and keep i t l o c k e d even  «  that  another  record  E  prevent  c u r r e n t o f r u n - u n i t h a s been t r a n s f e r r e d ,  Language  by  seeing  his  Several  for  against  w o r k i n g on.  run-unit  locking  offered  changes.  (c) No mechanism i s users  correctly.  earlier  t o s e v e r a l DBTG  proposed  by  Engles  of a c u r s o r .  Issues  chapter  with a l i s t  of c u r r e n t hot r e s e a r c h  issues: 1.  Quantitative scheduler have  been  measures  a r e needed. proposed  Papadimitriou  f o r e v a l u a t i n g the performance o f a To  such  date  only  qualitative  as t h e s e t o f a l l o u t p u t  (1979) s u g g e s t s  one p r o m i s i n g  measures schedules.  direction  which  43  would on  be  to  requests  approximate the  by  counting  the  total number  which c a n n o t e x e c u t e i m m e d i a t e l y 2.  A  basic  assumption  d e s c r i p t i o n of a l l  history  is  known  and  solutions".  One  to  and  This  Bernstein  get  around  retain  t o which  this  (1977).  to  steps  the be  to  this  a  number  locking on  of  can  i n Papadimitriou  focusing  a  available  transactions  R e c a l l that  r e q u i r e m e n t by  of  a  In  remove  have  arriving  in  priori.  wealth to  i s that  occur  a  cl-ear how  approach i s discussed al.  formalism  scheduler  a p p r o a c h wou.'.d  et  transaction  transactions  the  still  prototype transactions matched.  of  imposed  upon;= a r r i v a l .  words " i t i s not  assumption  r  in Papadimitriou•s  syntactic  Papadimitriou's  number o f d e l a y s  be  (1979)  protocols  each i n d i v i d u a l  transaction. 3.  Many o f  the  locking  r e s u l t s presented  strategies  distinguish protocols their  between r e a d  are  can  Weinberger context  be  found  (1 978).  to  A  current  except  discussion  adeguately  write  assuming  related  to  generalized  to  a c t i o n s . " In that  all  set  actions  phase  lock  Lien  and  Kedem  Silberschatz  (1979), i n  shared  lock  protocols  note  and  distributed  for  the  systems  continued are  locks".  discussed  the  database  when t r a n s a c t i o n s  exclusive  choose  for  a requirement  correctness  i s s u e , not  p u r p o s e s we  two and  and  lock  modify  a l . . (1975)  work on  here, i s  general  i n Gray et  "concerning  permitted  thesis  and  d i r e c t e d graphs,  investigation  major  by  not  literature  Some g e n e r a l i z a t i o n o f t h e  of t h e i r  modeled by  4.  stated  entities.  protocol  are  i n the  anywhere e l s e  data  SDD-1  in  management.  system  - a  this For  prototype  44  distributed  database  system  Corporation  o f America.  data  stored  a t a number o f n e t w o r k  with  SDD-1  The SDD-1 s y s t e m  which,  among  many  The c o n c u r r e n c y  of  data  describes  control  mechanism.  the  concurrency  et  a l . 1980,  S h i p man of  their  tree  distribution  the  there  (Bayer  SDD-1  Bernstein Many  by t h e  replication. Database  and  i t s  a l . 1980,  A  Systems  concurrency  correctness  of  (see R o t h n i e  Berstein  have d i s c u s s e d  distributed  i s the issue and  and  extensions  databases(i.e.,  of concurrency  McCreight  B-tree  some  variant)  with  any  database  to  Kwong and Wood  the  problem  the  many r e m a i n i n g  is  concurrent  i n B-trees.  a data  guarantee  efficient  the  system.  usual  i n B-trees  problems.  and  as a  by  specific the  B-  s e t of operations.  (1979, 1980) f o r a s u r v e y  of c o n c u r r e n c y  access.  problems  However,  by t h e s t r u c t u r e imposed f o r a limited  A B-  structure for  on a d a t a b a s e s t o r e d  involves  by a r e g u i r e m e n t  See  1972)  of p r o c e s s e s  a r e suggested  and  on  have  1979, Kedem and S i l b e r s c h a t z 1979).  operation  tree  et  to  Concurrent  solutions  data  system  researchers  a  associated  and  Transactions  organizing  (or  concurrency  i s t h e same a s we  F u r t h e r , an a n a l y s i s o f  results  Papadimitriou  i s s u e here  system  distribution  c o n t r o l mechanism i s p r o v i d e d  1980).  Finally,  interact  that i t i s f u r t h e r complicated  o f p a p e r s i n ACM  {1980)  from  others, include distributed  been d e s c r i b i n g e x c e p t  series  Users  a s i f i t were a n o n - d i s t r i b u t e d d a t a b a s e  SDD-1 h a n d l e s a l l i s s u e s a r i s i n g  problems  i n v o l v e s redundant  sites.  because  control.  5.  under d e v e l o p m e n t by Computer  a  of s o l u t i o n s t o discussion  of  45  Chapter  I I I : Problem  In  general,  follows: the  our  t o ensure  system  i s  EDBS c o n c u r r e n c y  used  concurrently  under  of background m a t e r i a l  the  First,  view and we compare concurrency in  Chapter  concurrency the  file  Second,  control  with  different  three  discussed  Both  constrained  intended by  the  Papadimitriou's  term be  reader  EDBS  used  into  in  terms  implementation  aspects.  of  locking  of  EDBS r e l i e s  reguired been  The e x i s t i n g system.  model  by i t s  CDC/APL,  solution  solution  are  which  may  be  I t i s our hope t o  of p r e v i o u s f i l e control  facilities  as p r e s e n t e d  of key problems  on  implemented  APL*PLUS,  the concurrency  file  systems. using  i n Chapter I I .  related  to  running  MTS.  i s cautioned that  we a r e r e f e r r i n g  t o perform  EDBS  EDBS h a s now  concurrency  we p r o v i d e a l i s t  EDBS c o n c u r r e n t l y under The  the  which i s i n d e p e n d e n t  transaction  understand  and CDC/APL i m p l e m e n t a t i o n s  f o r EDBS. CDC/APL  and  systems {i.e.,  APL*PLUS  we d e s c r i b e EDBS  Finally,  of  file  chapter  the user's point of  general  discuss  mechanism.  the  devise a s o l u t i o n Third,  some  to  when  s y s t e m s which h a v e been d e s c r i b e d  we  to provide insight  was i n i t i a l l y  in  EDBS  This  required  T h i s has s e v e r a l  t o do  concurrency  MTS/APLJ .  to those  control.  system  both  by  MTS.  we d e s c r i b e EDBS from  EDBS  control II.  may be s t a t e d a s  c o r r e c t n e s s of data maintained  provides a host problem.  problem  in this  chapter  when we use t h e  t o a s e t o f APL f u n c t i o n s which  o p e r a t i o n s on  databases.  may  46  Ao  EDBS D e s c r i p t i o n  EDBS r e c o g n i z e s database  modifying  is  EDBS.  maintaining  A common u s e r  i s  and  responsible  a DBA t o a c c e s s EDBS  and  DBAs access  of  three  relational  —  (workspace) intended  available  supported each  t o one o r more  given  of  by  —  data  hierarchical, by  EDBS. .  model.  many  user. One  system  required to for  use  by  commands  (2)  M o d i f i c a t i o n commands  (3)  Buffer  (4)  Control  and system  workspaces  are  t o Appendix A  utilities.  manipulation  Retrieval  separate  i s referred  with t h e d i f f e r e n t  (1)  A  network,  These  similarities  c a t e g o r i e s o f commands a v a i l a b l e  commands  the  (such a s t h o s e  The r e a d e r  has i t s own d a t a  commands  permission  APL w o r k s p a c e s .  required  o f EDBS w o r k s p a c e s and  for interacting  each system four  are  are  responsible  f o r creating, destroying, granting  models  there  is  databases.  f o r common u s e r s .  Although  number  utilities  data  implements  an o v e r v i e w  (DBA)  Other workspaces a r e i n t e n d e d  t o , and m a i n t a i n i n g  system  A DBA may a l s o be a common  a  utilities  A  m a i n t a i n i n g , and  granting access  c a r r y out h i s r o l e  contain  All  for  to  the system).  and  users..  i s one who has been  workspace c o n t a i n s a l l t h e  install  common  for installing,  a database.  comprised  administrator  o f u s e r s : system a d m i n i s t r a t o r s ,  A database a d m i n i s t r a t o r  creating,  databases.. by  types  administrators,  administrator  for  three  with  among t h e commands types  language. each  of  databases, There  system:  are  47  Data  in  Rather, it  may  the  be  read  however  to  systems  data.  or m o d i f i e d  a l l three  data  a hold  to  the user  (System  to advise  closing  provides  a  which  retrieval EDBS  GET-HOLD.  place  i t  control  a  database  user  with  concept  o f a HOLD,  f o r each system.  As i n  two v e r s i o n s o f e a c h versions  a h e l d on t h e d a t a  retrieve retrieved.  p o s s i b l e EDBS r e t u r n s a s t a t u s c o d e later  to hold  the item.  commands: OPEN and CLOSE f o r o p e n i n g and  RELEASE. .  the capability by  means  The  BELEASE  of e x p l i c i t l y of  a  command  releasing  previous  a  GET-HOLD  command. does not p r o v i d e  in  t o recover an  integrity  an  inconsistent  interactive the  state:  database  dialogue  logging  A DUMPLOG u t i l i t y  information.  assertions.  from a s y s t e m  which massages t h e  mechanism i s updates.  the  Both  him t o t r y a g a i n  he h a s a c g u i r e d  are provided  through  is  R, IMS) EDBS s u p p o r t s  i s not immediately  There a r e t h r e e  utility  where  Modification  from t h e b u f f e r and  of h o l d i n g i s d i f f e r e n t  The GET-HOLD a l s o a c q u i r e s  database  by a u s e r .  commands  v i a b u f f e r commands.  systems  command: GET and  If  hold  directly  a buffer via retrieval  new o r u p d a t e d  the unit  retrieval  and  i s not manipulated  database.  Common  other  database  i t i s moved i n t o  commands t a k e in  a  Logged e n t r i e s  of  crash  which may l e a v e  The f i r s t into  with  a the  DBA.  state  The s e c o n d  deletions  f o r printing  may be e r a s e d  the  i s t h e MAINTAIN  consistent  a l l insertions,  i s provided  Two mechanisms  and  the logged  v i a t h e EBASELOG  48  Utility.  1  The r e a d e r  i s referred  EDBS d a t a  manipulation  available The  objectives of this  (1)  to  provide  a  EDBS d i f f e r s in (2)  describe  flavour  1  •  control  facilities  interface  f o r each  EDBS  EDBS  available  (both  control). concurrency  at  the  user  for  the  system. we c h o o s e  System  R  system  EDBS  and DBTG  system.  relational  a full  updating,  following supported  system  provides  and r e t r i e v a l  range  of s t o r a g e  and d e l e t i n g  capabilities  from  simple  more t h a n  retrieval, one r e l a t i o n .  operations are provided f o r  tuples.  Among  other  things,  o f t h e SEQUEL d a t a s u b l a n g u a g e a r e  by t h e EDBS r e l a t i o n a l  DML:  (a)  o r d e r i n g on t u p l e s r e t r i e v e d  (b)  nested  (c)  specification  (d)  i  before  IMS f o r t h e EDBS h i e r a r c h i c a l  retrieval,  addition,  inserting,  not  the  within  B e l a t i o n a 1 System  gualified  the  system,  t h e EDBS network  The  In  system  we have s e e n  detail  As a means o f c o m p a r i s o n  for  are two-fold: o f how e a c h  those  in  of  commands and u t i l i t i e s .  section  from  B f o r a summary  g e n e r a l and i n t e r m s o f c o n c u r r e n c y  to  relational  t o Appendix  mapping o f more t h a n  retrieval  command  explicit  elimination  The MAINTAIN, DUMPLOG i m p l e m e n t e d a t UBC.  and  two  relations  o f d u p l i c a t e s from  ERASELOG  utilities  in  a  a query  have n o t been  49  result. Like operate  SEQUEL, a l l EDBS s t o r a g e o p e r a t i o n s a r e on a s i n g l e  The  EDBS  approach  that  o f System  and  data  of and  R.  to  defining  W i t h System  them when t h e y distinguishes  manipulation..  A  base r e l a t i o n s . destroy  base  The  Only  i s similar  require  the  base  EDBS, on t h e  i s provided user)  and  data  f o r defining  new  may  and  create  to  an  only  of  cursor tuples  APL program  R.  in in  Recall  a  identify  program  buffer.  name.  The  by EDBS  Tuples  are which  relation  name  of a cursor.  system  is  control the  mechanism  HOLD  available  option..  multiple  levels  transaction  definition  facilities  a r e not supported.  option  operates  differently  between  of  w i t h EDBS i s one r e l a t i o n .  of  The  locking,  tuple.  System  a FETCH command..  automatic  R i s a single  that  by means o f b u f f e r commands  of a r e l a t i o n  concurrency  EDBS r e l a t i o n a l  t h e d a t a s u b l a n g u a g e and t h e h o s t  The t u p l e s may be r e a d by a  sets  serves the function  hold  relations  by means o f c u r s o r s which  appropriate  specification  The  definition  definition  (not a common  the interface  maintains a c t i v e available  utility  from  manner by means  new  data  w i t h EDBS and System  s e t s of t u p l e s .  specifying  i n a unified  a r e no l o n g e r needed..  of i n t e r f a c i n g  accomplishes  active  a DBA  f o r data  may c r e a t e  between  differs  relations.  method  language  separate  new r e l a t i o n s  R facilities  t h e SEQUEL o p e r a t o r . . A u s e r destroy  to  a t a time.  manipulation are provided  o t h e r hand,  R  relation  restricted  System  consistency  EDBS and System The u n i t  with the  of hold  The  R and  HOLD  R: The u n i t with  System  50  EDBS e n f o r c e s c e r t a i n be s t a t e d  rules  on u s e o f t h e GET-HOLD w h i c h  may  as f o l l o w s :  (a)  A u s e r must  (b)  A user  (c)  Only  hold a r e l a t i o n  prior  t o updating i t .  may h o l d a t most one r e l a t i o n  buffer  intervene  commands between  a t one t i m e ,  ( o r t h e RELEASE command) the  GET-HOLD  and  may  UPDATE  commands. Prior deletion  use  o f t h e GET-HOLD  of tuples.  i s not required f o r i n s e r t i o n or  EDBS a u t o m a t i c a l l y h o l d s  the  relation  in  for  hierarchical  these i n s t a n c e s .  2-  Hierarchical  System  The  data  EDBS  databases  is  difference  is  description  similar that  to  that  of  EDBS  does  not  v a l u e s o r key v a l u e s c o n s i s t i n g The is  EDBS also  GET  similar  NEXT,  operations by  data  GET  manipulation  In  of  by  described  f o r IMS  PCB  most  notable  sequencing  o f key  one  field  for hierarchical The  GET  value. databases UNIQUE,  T h e s e o p e r a t i o n s may be g u a l i f i e d  and B o o l e a n  concurrency  EDBS.  may h o l d  Recall  support  sublanguage..  o p e r a t o r s which c o m p r i s e  o f an IMS segment s e a r c h  which a u s e r  The  NEXT WITHIN PARENT, INSERT, DELETE, and REPLACE  supported  time.  language  are a l l supported.  terms  IMS.  o f more t h a n  t o t h e IMS d a t a  means o f c o m p a r i s o n  equivalent  language  that  The (see  argument.  control,  HOLD  option  Chapter  II).  mere than  the  o n l y t h e HOLD o p t i o n i s operates  EDBS h a s no f a c i l i t y  one segment  IMS p r o v i d e s t h i s  exactly  occurrence  facility  e x c l u s i v e o p t i o n o r by means o f e x p l i c i t  at  as by one  by means o f t h e  shared  locks.  51  EDBS  enforces  retrieval  the  following  rules  on  use  of  GET-HOLD  operations:  (a)  Except any  segment  held (b)  for  a  r o o t segment, t h e p a r e n t - t o - b e o f  which i s t o be i n s e r t e d  v i a a GET-HOLD r e t r i e v a l  Any segment must  which i s t o be  first  be  held  via  must f i r s t  be  command.  modified a  or  GET-HOLD  deleted retrieval  command. (c)  Only  buffer  intervene and  3.  Network  The  be  EDBS d a t a  is  specified  concerned  in  to  not  occurrence. record  occurrence without  f o r network  the  be  schema  MANUAL.  i s first  EDBS  b e i n g a member  are  That  command  databases i s Many  inserted  not supported  the  database  DBTG o p t i o n s which  may  by EDBS.. F o r  member r e c o r d t y p e  in  EDBS  i s , when an o c c u r r e n c e  of a  as  a  member  class  a l w a y s OPTIONAL.  r e c o r d type  of  of a  c r e a t e d and p l a c e d i n t h e  the removal  i s  o f any member  Other  f o r every  automatically  in  the storage l e v e l  by EDBS.  Furthermore,  type  language  with  the storage c l a s s  assumed  is  retrieval  v e r s i o n o f t h e DBTG schema DDL..  member r e c o r d t y p e it  description  a r e not supported  example,  GET-HOLD  may  System  features  system  between a  ( o r t h e RELEASE command)  any m o d i f i c a t i o n ccmmand.  a rather limited DBTG  commands  may e x i s t  o f any s e t o c c u r r e n c e .  for  database,  of every  any s e t member  T h i s means t h a t an in  the  database  52  EDBS Since no  does n o t m a i n t a i n  a s many c u r r e n c y  i n d i c a t o r s a s DBTG.  an EDBS d a t a b a s e i s n o t d i v i d e d i n t o named a r e a s ,  need  area..  t o maintain  the current  The most i m p o r t a n t  run-unit  --  is  not  implications  in  terms  virtually  every  established  on  currencies  (i.e.,  DBTG.  of  by  the  system  use of h o l d s .  the  use o f h o l d s Five  control  With  This  has o b v i o u s  DMLs. .  With  of run-unit EDBS  DBTG  which i s  operations  bear  no  The r e m a i n d e r  of  (b)  deletion of a record  (c)  inclusion  (d)  removal of a record  (e)  update o f a r e c o r d  the  proposed  by t h e  does not p r o v i d e  subsection  describes  system. are a v a i l a b l e :  i n a s e t occurrence  i n a s e t occurrence c u r r e n t l y i n the database.  apply  t o use o f h o l d s  i n t h e network  system: Before in is (b)  a record  hold.  may be u p d a t e d  Upon c o m p l e t i o n  automatically  i t must be  placed  in  placed  o f t h e update t h e h o l d  removed.  F o r INCLUDE and fiEMOVE t h e r e c o r d be  EDBS  record  of a record  rules  (1971)  this  possible modification actions o f a new  by  t o those  report  i n t h e EDBS n e t w o r k  following  provided  resemblance  insertion  (a)  are  e s t a b l i s h e d by means o f o t h e r  facilities  (a)  The  EDBS,  uses t h e c u r r e n t  R e c a l l t h a t t h e DBTG f i n a l  for  each  o f a l l -- t h e c u r r e n t of  respective  occurrences  within  r e c o r d ox s e t p o i n t e r s ) .  concurrency  network  maintained  operation  segment  occurrence  DBTG c u r r e n c y  v i a t h e FIND o p e r a t i o n .  performed  The  record  there i s  hold..  may  optionally  A RELEASE command  must be  53  issued (c)  to release  For deletion the record in  hold.  The h o l d  completion (dj  A  user  hold There  i s automatically  o f t h e DELETE  certain  users.  existence  of concurrent  (a)  difficulties  The  when d e a l i n g  EDBS  inherent  in  A record  Guide  record  or set pointer that  EDBS  As with  DBTG  advises  users n e c e s s i t a t e s with  the  from t h e a c t i v i t i e s  User's  that  that  caution  may mark t h e p o s i t i o n  record  If  t h e l o c a t i o n r e m a i n s empty and t h e p o i n t e r  prior A  an e r r o r c o n d i t i o n  deletion will  set pointer  record  h a s been d e l e t e d  i s stored  that  occurrence referenced  will  result. location  of  user. is If a the  undetectable.  may mark t h e p o s i t i o n o f a member  has by  by a n o t h e r  i n t h e vacant be  been  another  "the  must be  ways:  a  new r e c o r d  of other  o r s e t p o i n t e r s " . . A user  i n one o f t h e f o l l o w i n g  referenced  (b)  occurrence i n  c o n t r o l scheme f o r network d a t a b a s e s . .  affected  upon  command,  user i s n e t c o m p l e t e l y i s o l a t e d  exercised  placed  released  may have a t most one r e c o r d  concurrent  be  may o p t i o n a l l y be  a t one t i m e .  are  concurrency the  the hold,  removed user.  an e r r o r c o n d i t i o n  from  a  set  I f the pointer i s will  result.  may  54  B..  EDBS  Implementation  EDBS  was  University  of  availability techniques  Computer system  Toronto.  of  the  to  University  the The  of Calgary  CDC/APL  constraint The  system a  installed  EDBS  on  functions  to i n s t a l l of  general  EDBS.  their  itself  major file  file  system  by Y a i r  using  diagram  represents the r e l a t i o n s h i p  file  system  the  available  was t o use  The  an  MTS/APL f i l e  MTS/AFI f u n c t i o n s .  and t h e MTS/APL f i l e  between  CDC/APL  >]  EDBS, t h e  MTS/APL  I  System  Figure 2  <  j File  The file  The f o l l o w i n g  INTEBFACE F I L E SYSTEM  File  major  interface  system.  system.  Interface  i t  Wand, F a c u l t y o f  i s intended to simulate the  system  and t h e  system  system.  EDBS  the  Data  requirement of the  file  interface  Control  s h o u l d n o t be m o d i f i e d .  (suggested  and  The  system.  o f C a l g a r y ) was t o p r o v i d e  between  on  overlay  eliminated  Management, U n i v e r s i t y system  used  The d e c i s i o n  The  at  s m a l l workspace..  were  EDBS a t UBC.  t h e system  approach  and  o f t h e MTS/APL f i l e  was c o n v e r s i o n o f t h e  was t h a t  Group  was dependent  on t h e CDC/APL f i l e  introduction  version  implementation  file into  was c o n v e r t e d t o r e l y  became f e a s i b l e  Research  system  Overlay  the recent  Systems  implementation  APL*PLUS  f i t the  (CDC).  With  the  by  designed  System  interface  55  The exactly calls  functions those  a  available  provided  particular  interface  function  from t h e i n t e r f a c e  by t h e CDC/APL f i l e  CDC/APL which  function  performs the task  p e r f o r m e d by t h e CDC f u n c t i o n exactly  what i t e x p e c t e d  The file  concurrency CDC/APL  file  a straight The logical  system  forward  that  (i.e.,  differ  With t h e s e e x c e p t i o n s , using  the a v a i l a b l e  and  physical  and  relies  exception  on  objects  file  to this i s  the  EDBS  been  to  EDBS  function. i n their  authorization  and  simulation  the  MTS APL f i l e  of  system  was  which  requires  setting  a s r e l a t i o n s , segments and r e c o r d s  on f i l e s .  the  of  an  task.  on such locks  would have  primarily  access  EDBS  calls  returns  EDBS a p p r o a c h t o c o n c u r r e n c y c o n t r o l  locks  version  facilities  control).  actually  when i t c a l l e d t h e CDC systems  system a r e  s y s t e m . . When  and f u r t h e r m o r e  CDC and MTS APL f i l e  sharing  i t  file  EDBS manages i t s own system  tc  relational does  not  logical  set physical system  of  locks  locks.  the  r e l y on t h e f i l e  One  APL*PLUS  system f o r  locking. The  conversion  CDC/APL i n v o l v e d  at University  extensive  modification  used  by t h e r e l a t i o n a l s y s t e m .  and  network  physical  level  University all was  three  systems  of  of l o c k i n g . Calgary  hierarchical  to  rely  Modification  A result  was t h a t similar on  of  of the h i e r a r c h i c a l involving  the locking  strategies  (i.e.,  relational  the  do) .  to  mechanism  .modifications  t h e CDC/APL f i l e  and network s y s t e m s  APL*PLUS  o f the l o c k i n g  was f a r l e s s e x t e n s i v e  s y s t e m s a r e now  modified  o f C a l g a r y from  system  only the made  at  used by system  j u s t as t h e  56  In  this  section  implementation data at  usage  we  describe  the  along  a number o f d i m e n s i o n s .  i n general  by r e v i e w i n g ' E B B S f i l e s  the f i l e  system  level.  Second,  at  consider  major d i f f e r e n c e s EDBS under  First, and  EDBS  we e x a m i n e  authorization  we examine i m p l e m e n t a t i o n o f  c o n c u r r e n c y c o n t r o l i n t h e APL*PLUS v e r s i o n look  existing  o f EDBS.  i n t h e CDC/APL v e r s i o n .  Third,  we  Finally,  we  MTS.  i  1..  EDBS F i l e s This  at by  and  section  the f i l e  files. file  describes  system  EDBS i t s e l f .  utilities  Authorization  level.  EDBL. f i l e s  .ire c r e a t e d  f o r t h e message f . l l e ,  (See A p p e n d i x  reguirements  Access r e s t r i c t i o n s are also  A l l of these f i l e s  except  and a c c e s s  C f o r a graphical  by  imposed  various  DBA l o g f i l e  and b u f f e r  representation  of  usage.) (a)  Message The  File:  message f i l e  various file  EDBS u t i l i t i e s .  to  administrator message  Translation The to  administered translation  i s  permitted  one  used by message  A l l u s e r s have Only  the  read  system  t o modify t h i s f i l e . .  taken  from  the  EDBS  tape. Table  primary provide  file.  is  messages  There ; i s  this  file  distribution (b)  error  p e r EDBS i n s t a l l a t i o n .  access  The  contains  File:  purpose a  of the t r a n s l a t i o n table i s  directory  of  by  DBA..  table  one per DBA.  a l l the There  A l l users  databases is have  DBA  one read  EDBS  57  access  (c)  to  access  to t h i s  Record  Table  The  record All the  The  (e)  table  All  users  The  complete  about  segment t y p e s ,  record table  access t o t h i s  access  to t h i s  contains  per  file.  the and DBA. Only  file.  have  read  information  o f domains,  There i s one  has  field  access  complete a c c e s s  to t h i s  the  fields,  and  per  DBA.  file.  Only  table  to this  on  file.  File: log f i l e  database  i s used  open and  modifications. database. this (f)  has  information  characteristics  items.  DBA  File:  field  data  Log  read  complete  Table  DBA  stores  T h e r e i s one  have  has  physical  the  the  aspects of r e l a t i o n s ,  users  Field  Only  File:  types.  DBA  file.  file.  record table  physical  (d)  this  keep  There  a  is  A l l u s e r s have  log one  of log  read/write  the  database file  per  access  to  File: record  occurrences inverted sharing  file  of  is  (segment  lists,  relation. type,  to  has  file.  Record The  t o keep t r a c k o f who  the There  and  to  occurrences locks  record is  used  used  type, one  access  to t h i s  or to  file.  record tuples),  synchronize  segment  record f i l e  segment t y p e , o r r e l a t i o n .  read/write  store  type per  A l l users  or  record have  58  (gj  Buffer  File:  The  buffer  from  the database.  an  file  OPEN command  This  file  i s used  to hold  The b u f f e r  and d e s t r o y e d  can only  data  file  retrieved  i s created i n  i n a CLOSE  be a c c e s s e d  by  the  command. user  who  owns i t . (h)  DBA Log  File:  The DBA  log f i l e  DBAs a  are.  vector  DBA  i s used t o keep t r a c k  I t c o n s i s t s of e x a c t l y  o f EEA a c c o u n t  log  file  numbers.  have r e a d / w r i t e  access  file  by t h e s y s t e m  different  database  i s created  record  relations,  (i.e., files  database  n record  to t h i s  record  With t h e e x c e p t i o n access  All  users  creating  numbers over for  creating  and one  or  The DBA l o g  where n i s or r e c o r d  log  record  the  number  types i n the  file).  Access  occurrence  any u s e r  access  i s potentially  reguires  that  from  to  has  to  at the level.  read/write  the  vector DBA  o f DBAs i s m a i n t a i n e d  h a s t h e a c c o u n t o f t h e SA w i l l  the  procedure  o f DBA  account  account.  Control  as f o l l o w s :  Utilities  updating  administrator's  t h e DBA l o g f i l e  a DBA and  t h e new  DBA schema t a b l e s and  i n t h e system  A l l users  v i a t h e GRANT ACCESS u t i l i t y  read/write  and u p d a t e d  authorization  stored user  be r e a d  one  files.  have  DBAs  i s  administrator.  of these r e s t r i c t i o n s  b e c a u s e any common u s e r for  files  type l e v e l  t o a l l database  There  file.  segment t y p e s ,  i s restricted  level,  one component,  p e r EDBS i n s t a l l a t i o n .  A database c o n s i s t s of n + 1 f i l e s of  o f who t h e  the  DBA  log are  l i b r a r y . . O n l y i f a common he  be  .able  to  load  the  59  procedure must  required to i n s t a l l  permit  the  who  a r e t o become  2..  Concurrency The  to  The system  files on  with  f o r read  interlock  and  place  access  the  file  file.  In  file,  all  order  network  list  an  interlock  user  must  a time  users  on  a file user  mechanism:  then has  by  the  lock  he an  APL*PLUS  and  unlock  interlock If a  will  be  on t h e  to  on  the  use  file  user  able  interlock  exclusive  interlock  a  out f e a t u r e .  requests.  i s guaranteed  p l a c e an  facilities  r e q u e s t i n g an  order of t h e i r  even t h o u g h a n o t h e r  users  locking  explicitly  Several users  i n the  that a  and  of three  f u n c t i o n i s provided  permits a user to  a r e queued  not  to those  SA  APL*PL0S  f u n c t i o n , a hold  f o r e x c l u s i v e use.  a file  does  control  file  Further, the  DBAs.  t h e h i e r a r c h i c a l and  interlock  file  a p p r o p r i a t e workspace  a DBA.  APL*PLUS v e r s i o n o f EDBS makes use  implement  file  h i m s e l f as  of  a  prior  to  accessing i t . A hold on  a  list  segment  occurrences record first  file  (user  occurrence  of  ID,  identifies u s e r , and  a  f o r the  component The  is a list  logical  the  of type  segment  a  All  A hold  list  file  a hold segment  (i.e.,  the  i s s t o r e d as  the  file.  time  h e l d segment, t h e time  having  type.  a r e s t o r e d i n one  contains zero index,  currently  given  type).  of each r e c o r d  hold.list  the  given  of a l l u s e r s  or  more t r i p l e s  stamp). user  stamp i s the t i m e  ID  The  of  logical  identifies  a t which t h e  the  the  form index  holding  h o l d was  set..  60  When for  the  a  segment  currently to  user  requests  type  h e l d , then  the hold  list.  code i s r e t u r n e d The  being  time.  hold  on  five  segment  minutes. after  in  to  user  i s not  a new  hold  a  an  prevent  triple status  segment  period  of  t o be i n e f f e c t f o r  requests  has e x p i r e d  a  excessive  i s guaranteed  I f another  segment  list  i s not p o s s i b l e .  used for  the hold  by a d d i n g  a hold  i s  a segment  the  i s already  unavailable  the time l i m i t  If  i s granted  feature  from  only  the hold  to indicate that  occurrence  on a segment,  checked.  I f t h e segment  time-out  A  is  a hold  a  hold  on  then t h e p r i o r  the  hold i s  i  removed. " i  During place  a  command users  hold  may s t i l l  segment This  type  type  Since accessing and  t h e segment  actual  a file  other  segment of  t o the user  However,  To a v o i d only  after  to  the  file  other  a segment,  access  to the  performing  the  update.  by p l a c i n g an i n t e r l o c k on t h e ;  must  place  an i n t e r l o c k on a f i l e  take  place  under  unnecessary  delays  a l lprocessing  the  both  complete.  retrievals  protection  of  an  placed  not r e g u i r i n g access  to the  and t h e i n t e r l o c k i s removed is  prior to  the i n t e r l o c k i s  The  by EDBS i s n o t c l e a r f r o m a v a i l a b l e  APL*PLUS v e r s i o n .  may  a t any t i m e .  file.. a l l users  user  and t h u s 'no m o d i f i c a t i o n  may be e x e c u t e d .  i s accomplished  has been c o m p l e t e d  followed  segment  modification  i s restricted  modifications  access  same  no  i t f o r t h e i n t e r l o c k t o be e f f e c t i v e ,  interlock.  the  the  i s i n hold,  r e t r i e v e the held  restriction  segment  file  in  affecting  During  on  t h e t i m e a segment  exact,  as soon  lock  as  protocol  documentation  for  61  As file  an  during  component The  integrity  first  not  measure  modifications.  of each r e c o r d element  locked  EDBS a l s o This  type f i l e  lock  1  i f  i t  occupies  the  and i s a two e l e m e n t  of t h e l o c k vector  and  s e t s i t s own l o c k  i s 0 i f the record  i s . The s e c o n d  element  on a  second vector.  type  is  of the l o c k  i  vector set  i s 0 when no l o c k  when t h e r e c o r d  on e v e r y r e t r i e v a l user  does  not  and t h e t i m e  type i s l o c k e d .  and e v e r y  The l o c k  modification.  interrupt a modification  the lock  vector  the f i r s t  if  modification  a  the  element file  are is the  still printed  will  allowed.  However,  and i s n o t resumed t h e n t h e  remain  set to 1 to indicate  i n an i n c o n s i s t e n t s t a t e . t o the r e c o r d  will  In t h i s event,  type are prevented,  but  that  further  retrievals  I n e i t h e r c a s e an 'INTEGRITY CHECK' message  each time t h e f i l e  i s accessed u n t i l  t h e DBA c o r r e c t s  situation.* The  system the  interrupted  of the lock  is  modifications  i s  i f a  element  be r e s e t t o 0 when t h e m o d i f i c a t i o n c o m p l e t e s .  was  i s checked  Ordinarily,  always  first  APL*PLUS  t o implement  system  itself  a lock vector  1  i s i n effect  version  of  EDBS does  not r e l y  locking i n the r e l a t i o n a l m a i n t a i n s f o r each r e l a t i o n  t o implement  This paragraph i s taken Computer S y s t e m s R e s e a r c h  the l o c k i n g  on t h e f i l e  system.  Rather,  a r e a d e r l i s t and  mechanism.,  from documentation compiled Group, U n i v e r s i t y of T o r o n t o .  i  by  the  62  All (the  t u p l e s from  record  relation file.  file).  reader  users c u r r e n t l y read  vector.  list  relation  element  modification The  lock  vector f o ra  of  with  the  record  IDs f o r those  the  vector  1 i f the r e l a t i o n being  held  which must be e n f o r c e d  (b)  a relation  time  i s  nor  numeric  2  i s being  i f the h e l d and  modified.  that the hold or  may h o l d a r e l a t i o n  a t one t i m e .  when a n o t h e r  user  user  may a c c e s s  a relation  w h i l e one  i s modifying i t .  rules  are enforced  v i a the  reader  list  and  EDBS  waits  as f o l l o w s : For  (b)  reading  (i.e.,  for  the r e l a t i o n  or  in  time  hold  t o be u n l o c k e d  and t h e n  onto the reader  For holds  t h e GET command)  {i-e.,  e n t e r s t h e user  number and  list.  t h e GET-HOLD command)  for  the r e l a t i o n  t o be u n l o c k e d  or  unheld  then  and  f o r modification  enters  EDBS  waits  for modification a  1 into  the lock  vector. (c)  The  are the following:  may n o t be m o d i f i e d  other  user  (a)  that  i t i n hold  no  These  along  file  started.  a t most one u s e r  {c)  lock  two components  the  neither  (a)  has  and  of t h e l o c k v e c t o r i s t h e time  was  rules  modified, is  list  one  A l o c k v e c t o r i s a two e l e m e n t  element o f  i s being  are stored i n  i s a matrix c o n t a i n i n g user  was s t a r t e d .  0 i f the r e l a t i o n  vector  reader  reading the r e l a t i o n  The f i r s t  second  The  a r e s t o r e d i n the f i r s t A  each  t h e same r e l a t i o n  F o r m o d i f i c a t i o n s EDBS w a i t s f o r t h e r e l a t i o n  to  lock  63  be  unlocked  vector To never  ensure  releasing  reads  are  recorded his  will  one u s e r w i l l  not  timed  out  be  after  five  a relation  dropped  Similarily,  may  be  i s not timed  inconsistent printed  modification totally  five  minutes  user r e q u e s t s t o h o l d o r  any row  of  the  reader  minutes o l d .  list  1  command i s i n t e r r u p t e d  the r e l a t i o n  I n s t e a d , an  by  h o l d s and  then the  l o c k e d f o r any l e n g t h o f t i m e .  out because  state.  relation  Thus, i f a user i s  f o r more . t h a n  be i g n o r e d i f i t i s more t h a n f i v e a relation  a  a read, both  minutes.  i f another  the lock  t o be empty.  t i e up  a h o l d or by i n t e r r u p t i n g  will  relation  is  that  the r e l a t i o n .  If  lock  writes a 2 into  and w a i t s f o r t h e r e a d e r l i s t  as h a v i n g h e l d  hold  modify  and u n h e l d ,  file  may  be  'INTEGRITY CHECK' e r r o r  This in  an  message  and n e i t h e r h o l d s n o r m o d i f i c a t i o n s a r e a l l o w e d .  2  i  3.  Concurrency  The  control  CDC/APL  with  CDC/APL  implementation  of l o c k i n g  for hierarchical  and  I  network mainly with  differs  from  i n use o f t h e i n t e r l o c k the  system and  databases  CDC/APL  a r e used  an e r r o r  file  the  function  system).  Two  APL*PLUS (which  implementation 'is unavailable  f e a t u r e s o f t h e CDC/APL  t o accomplish the i n t e r l o c k : a f i l e  t i e function  trapping function. i i  1  and These two paragraphs are taken c o m p i l e d by t h e Systems R e s e a r c h Group at Toronto. 2  from the  f i  documentation University of  64  The of  file  t i e f u n c t i o n (FTIE)  i n t e g e r s and a m a t r i x  prior the  to accessing i t .  user  the  names.  When a f i l e  Thereafter,  number r a t h e r read/modify When indicating mind  When  of f i l e  as a r g u m e n t s A user  i s tied,  w o r k s p a c e and t h e i n t e g e r p r o v i d e d  file.  not  takes  than  by  a  user  ties  user  mode.  a  t h a t he w i s h e s  user t i e s  user  i t s name.  mode c r i n w r i t e  i f another  a  the  i t i s made known t o is  file  in  associated the f i l e may  be  read/modify  t o read t h e f i l e  modifies the f i l e  a file  file  with by i t s  tied  in  1  file  only  vector  must t i e a  references A  a  at  mode  he i s  and t h a t he d o e s the  same  i n w r i t e mode he i s i n d i c a t i n g  time. t h a t he  i i  wishes t o modify to  modify  tied  the f i l e  to  a file  user a t a time user  attempts  message.  a t t h e same t i m e .  may h a v e a f i l e to  tie a system  tied  CDC  error  trapping  i n t h e program  of  a system  t o which  error.  one  second  f o r w r i t e he r e c e i v e s an e r r o r (FUNTIE)  for  trapping  function. t i e and  function a  takes  branch  will'  taken)  by means  The f u n c t i o n o f an i n t e r l o c k error  as an argument a occur  in  the  An u n s u c c e s s f u l t i e f o r w r i t e may be  (and a p p r o p r i a t e a c t i o n  file  Only  i n w r i t e mode., I f a  provides a function  detected  the  u s e r s may be  1  mode a t t h e same t i m e .  file also  Any n u m b e r o f  users  files.  The  event  and t h a t he does n o t want o t h e r  i n read/modify  The f i l e  untieing  location  the f i l e  trapping  of  the  error  i s achieved v i a  functions i n the following  manner:  1  The CDC/APL f i l e s y s t e m a l s o p e r m i t s a f i l e t o be t i e d i n r e a d mode which a l l o w s o t h e r u s e r s t o r e a d ( b u t n o t m o d i f y ) t h e file a t t h e same t i m e . T h i s o p t i o n i s n o t u s e d by EDBS.  65  (a)  A file  i s normally  fact,  the  for (b)  OPEN  tied  i n read/modify'mode.  command  ties  a l l database  In files  read/modify.  Immediately is  untied  in  write  p r i o r t o any w r i t e  and an a t t e m p t  operation  the f i l e  i s made t o t i e t h e  file  mode. i  (c)  I f the t i e f o r write is  performed.  Otherwise,  m i n u t e and t r i e s (d)  again  five  status  write  waits  is  m i n u t e s EDBS g i v e s  operation  file  after  performing  i s untied  and t i e d  a  f o r one  f o r write.  not  possible  up and r e t u r n s a  code t o i n d i c a t e an u n s u c c e s s f u l  Immediately the  EDBS  t o t i e the f i l e  I f a successful t i ef o r within  (e)  succeeds the write  lock. .  write  again  operation  i n read/modify  mode. The version) the  CDC/APL v e r s i o n does r e l y  relational  hierarchical The vector) one  system.  record  user  contains  consists  o f e x a c t l y two e l e m e n t s .  of  user  holds  hold  the hold  vector  i s similar  locking  in  t o that f o r the  functions  (not  a  hold  list  Element  Element  i s (0,0). .  i  reader  a hold  was s t a r t e d . . I f t h e r e l a t i o n  lock  Component  1 i s the user  the r e l a t i o n .  a  (not a  the whcle r e l a t i o n ,  currently holding  a t which t h e h o l d  implement  locking f o r modification.  Since  time  to  trapping  list).  the  a  system  t h e APL*PLUS  systems.  to e f f e c t file  ( i n c o n t r a s t with  The a p p r o a c h  t i e and e r r o r  a r e used  of each  on t h e f i l e  and n e t w o r k  file  o f EDBS  is  vector number  2 i s the not i n  66  avoid  The  following  lost  updates..  command r e a d s  procedure  i s used  (Suppose t h a t  and w r i t e s v a r i a b l e Loop:  an  by a l l t h r e e s y s t e m s t o EDBS  X from  data  file  F) :  Read X from F T i e F f o r WRITE I f t i e f a i l s go t o Wait Write X t o F T i e F f o r READ/MCDIFY Stop D e l a y 1 minute T i e f o r READ/MODIFY  Wait:  manipulation  ;  Go t o Loop This The  read  user  procedure  i s done and t h e n  has  redone.  the  file  at  a time.  hierarchical  record  files.  situation files  lost  before  successfully  that  system  which  The  CDC/APL  updating  be t i e d  updates user  must  tied,  triggers version  to tie for any o f them.  f o r write waits  w r i t e . . Examination  because  a  given  was n o t u p d a t i n g t h e |  lock  more  than  EDBS  and t h e n  deletion  from  of  handles  write  EDBS  one  unties tries  any  again  that  must  modify  this record  I f any o f t h e f i l e s  cannot i t has  t o t i e them a l l  o f EDBS APL code i n d i c a t e s  GRANTACCESS)  several  a l l required  that  an EDBS o p e r a t i o n ( i . e . , GET, UPDATE, INSERT, DELETE, DESTROYDBA,  another  t h e r e a d i s i g n o r e d and  and u p d a t e .  when a u s e r  operations.  As an e x a m p l e , c o n s i d e r t h e DELETE command i n  by a t t e m p t i n g  immediately  for  write,  user's read  There are o c c a s i o n s  the  i f i t i s determined  for  prevents  out o f p r e v i o u s  u p d a t e i s made o n l y i f a n o t h e r  between t h e g i v e n  file  later  tied  The p r o c e d u r e  user's file  amounts t o back  d a t a from  whenever  CREATEDBA,  more t h a n  one  of  are  i  file,  a l l files  are tied  for  write  before  any i  modified.  them  67  I  We the  conclude  CDC f i l e A user  category, file  is  following  access  password, created  and  from  excerpts  to h i s f i l e s mode  APL  from  which  via  the  category  description of  means  of  a  may be s p e c i f i e d  the  CDC  by  FCREATE  file  when t h e  function.  APL r e f e r e n c e manual  i s ordinarily  files  cannot  may,  alternatively,  be a c c e s s e d  or  categories they  and  a brief  The (1978)  facilities.  The f i l e  if  with  authorization f a c i l i t i e s .  semiprivate  (b)  subsection  c o n t r o l s access  describe these (a)  this  by o t h e r  be  A  of  t o access  The f i l e  number under  c a n be g i v e n  these  the f i l e  know t h e p a s s w o r d , t h e name o f t h e  t h e user  file  a category of  Either  users  Private  users.  assigned  public.  allows other  private.  file,  which i t was s t o r e d .  a password.  Only  users  who  type  of  know t h e p a s s w o r d can use t h e f i l e . (c)  The f i l e  mode i s used  operation created  another  by APL  are o r d i n a r i l y the  password  but.are Other file the  user  (including allowed  file  workspaces)  do  For f i l e s other  the f i l e not  users  (assuming  exclude  them)  or destroy the f i l e .  permission t o a l t e r the  t h e WR o p t i o n  i s created.  the  can perform.  to alter  c a n be g i v e n  by s p e c i f y i n g  control  t o read  and c a t e g o r y  not a l l o w e d users  to  ( f o r write)  when  68  A file or  category,  c h a n g e d o u t s i d e t h e APL  category option  and  mode-  i s n o t used  4.. EDBS Under  In  this  details these  control  f o r this  section and  a l l CDC  We c o n c l u d e  facilities  MTS a u t o m a t i c  locking  on  because t h i s  consists  takes into  and  control  mechanism.  file  The p a s s w o r d  copy  his active  functions via  very  description a  state  Among  in  v i a MTS f u n c t i o n s w i t h  little  v i a the  library others,  incurs  correctness.  file  operations  The f i l e  may be e x e c u t e d the  starts  concurrency,  users t o perform  To use  o f i t (from a p u b l i c  a r e p o s s i b l e from  a  —  o u t s i d e t h e APL e n v i r o n m e n t .  workspace.  access  look i n t o the  with  starts  for  We s a y t h a t o u r p r o b l e m  system a l l o w s  w i t h i n an APL f u n c t i o n .  operations  the  which i s p r o v i d e d  o f a s e t o f f u n c t i o n s which  a  section  and j e o p a r d i z e s d a t a b a s e  MTS/APL f i l e stored  this  we  CDC/APL  are a v a i l a b l e  state provides  of deadlock  files  from  to f i l e s .  control  a t which our p r o b l e m  of concurrency  The  uses  purpose.  concurrency  facilities.  the r i s k  EDBS  we examine t h e MTS f a c i l i t i e s  the e x c e p t i o n  here  access  of s i m u l a t i n g t h e c o r r e s p o n d i n g  t h e EDBS s t a t e  which  to  environment..  be r e a s s i g n e d  MTS  authorization  of  p a s s w o r d , and mode may a l s o  from  system  o r t h e SA's the  system APL o r a  user  account)  following  MTS  w i t h i n APL: CREATE, DESTROY, READ,  WRITE, EMPTY, LOCK, UN1K, RENAME,  and RENUMBER.,  69  A subset command  is  command from  of the c a p a i s i l i t i e s provided  available  allows  or write  a user  from  by  integrity  a  of  shared  and  lock  are i n c l u s i v e  modification  users  This  to  read  a v a i l a b l e are b a s i c a l l y  locking.  (1976)  also  locking file:  levels  of l o c k i n g ,  The f o l l o w i n g  and  UBC  are  excerpts  Commands  provided  lock  for  (1977)  i n the  locks  sense  that  use  The locking  i tf o r reading  also locks i t f o r reading  f o r maintaining  reading,'  for destruction.  The r u l e s f o r c o n c u r r e n t tasks  PERMIT  command.  other  which i n c l u d e t h r e e  Devices  classes of  destruction  permit  MTS  facilities:  modification, classes  MTS  and  these  Three  SHARE  control f a c i l i t i e s  l o c k i n g , and e x p l i c i t  UBC F i l e s  describe  the  into h i s f i l e s .  provided  automatic  MTS/APL  to explicitly  The c o n c u r r e n c y those  v i a the  by  lock  three a  locking  file  Any  number  reading has  of  tasks  and m o d i f i c a t i o n .  of  a  file  among  can have a f i l e  a t t h e same t i m e a s l o n g  the  file  locked  separate  for  Only  one  task  modification  or  I  task  can  have  modification  a t one t i m e ,  other  has  task  the  a  and  file  file then  locked  locked only  Only  one  destruction other  task  for  i f no  f o r reading or  destruction. (c)  locked f o r  a s no o t h e r  destruction.. (b)  >  task  can  have  at  one  time,  has  the  file  for  and l o c k i n g a f i l e f o r  are the following: (a)  for  a  file  and open  locked t  then or  only locked  for i f no for  70  reading Piles by  or m o d i f i c a t i o n .  are  implicitly  MTS whenever a u s e r  locking. .  For  subroutine  level,  write  a line  reguests  example,  from  a file,  (or m o d i f i c a t i o n )  manner  until  locking  i s associated  the  use  with  i f  of  a  call  and  file  is  operating  to a subroutine implicitly  and l e a v e  with  the f i l e  user  MTS w i l l  that  locked  s o m e t h i n g o f MTS which  on t h e f i r s t  1  reading  associated  (automatically)  the  unlocked requires  from  the  t o read  or  lock the f i l e f o r  file  locked  in  that  i s complete.. I n g e n e r a l , the  t h e FDUB  (file  or device  and a u t o m a t i c u n l o c k i n g  usage  is  block)  done  when  FDUB i s r e l e a s e d . When  MTS  implicitly  FDUB, i t may r a i s e  2  a  the locking class  it..  F o r example, i f a user  first  writes  a line  same  file,  MTS  will  the f i r s t  write  before  locks  operating  to a f i l e  and t h e n  implicitly and  leave  file  through  but i t from  will  never  the subroutine  reads  a  lock the f i l e i t  a particular  locked  line  lower level  from  the  f o r modification for  modification  thereafter.. If,  while  according  t o the concurrent  reguested, the task however,  attempting  MTS i m p l i c i t l y  t o wait MTS  until  checks  to  lock  a file  MTS d e t e r m i n e s  use r u l e s i t c a n n o t  and a u t o m a t i c a l l y  the f i l e  lock  the f i l e  attempts  c a n be l o c k e d . . B e f o r e  t o ensure t h a t  that  to  as  gueue  doing so,  gueuing t h e job t o wait  on  1  We distinguish between t h e MTS command level and t h e MTS subroutine l e v e l . The f a c i l i t i e s a v a i l a b l e from w i t h i n APL a r e those at t h e subroutine level.  2  Lock f o r d e s t r u c t i o n i s s a i d t o be.at a higher l e v e l than f o r m o d i f i c a t i o n which i s , i n t u r n , a t a h i g h e r l e v e l t h a n for reading.  lock lock  7 1  the as  file well  will  as o t h e r s  respective task  not r e s u l t i n a s i t u a t i o n wherein  queues.  t o wait Files  within  be  deadlocked  can a l s o  be  will  explicitly  cannot  FRELEASE  locks  locks  may  which  will  Explicit command  be also  locks  may  system)  also permits i m p l i c i t  without  closing the f i l e .  description We  and  attention  of the simulated  focus  unlocked  from  I n a d d i t i o n , an be  here  the  on  within  done  i f  explicitly  to  to  Otherwise,  the user leaves  (and n o t p a r t  locks  APL v i a t h e  file..  which a l s o c l o s e s  a v a i l a b l e t o EDBS  our  from  released  concludes our d e s c r i p t i o n  turn  not allow the  no w a i t i n g  closes  be  function  D..  that  remain i n e f f e c t u n t i l  special  now  locked  removed  (or t h e FRELEASE command  This  their  be a c c o m p l i s h e d .  command  implicit  in  task  an e r r o r i n d i c a t i o n .  ( v i a t h e LOCK and UNLK commands).  Implicit  We  return  may be s p e c i f i e d t o r e q u e s t  locking  indefinitely  I f s u c h i s t h e c a s e , MTS w i l l  but i n s t e a d  APL  option  will  the current  be  APL. .  v i a t h e UNLK the f i l e ) . .  o f t h e APL  explicitly  o f t h e MTS/APL f i l e  file  removed  system.  d e t a i l s of the simulation..  functions  the important  i s available i n  A  A  Appendix  o n e s : MTSCREATE, MTSTIE,  MTSUNTIE, and TRAP 1. The The  syntax  MTSCREATE f u n c t i o n  simulates  o f t h e FCREATE f u n c t i o n  t h e CDC FCREATE f u n c t i o n .  i s as f o l l o w s :  •file-name[:password ] [/options]'  FCREATE fnum  j  72  The C,  WE,  list S,  or  semiprivate files  of options  or p u b l i c .  (i.e.,  structured). was  PU t o s p e c i f y  not  remaining (a)  If  of  format  access  and  accomplishes  ithe  following  file  i s created  whose name  file-name.  f o r read  file  are specified  the f i l e i s  or w r i t e r e s p e c t i v e l y  t i e number  of f i l e  file  were n o t  v i a the  SHAEE f u n c t i o n .  inserted  (fnum) i s i n s e r t e d  t i e numbers and t h e  i n t h e same r e l a t i v e  file  position  into a  name  is  i n a table  names.  MTSFTIE f u n c t i o n s i m u l a t e s  t h e CDC F T I E  f u n c t i o n whose  i s the following:  •[•account] The The  direct  access  d o e s n o t use t h e p a s s w o r d o p t i o n , i t  t h e S o r WE o p t i o n s  The  mode,  direct  options  DA,  |  g i v e n by  table  syntax  are  these  automatically  MTSCEEATE  An APL i n t e r n a l  MTS/APL  The  coded, write  functions:  permitted  (c)  are  EDBS  simulated.  is (b)  access,  a r e coded f i l e s ,  files  Since  direct  S i n c e a l l EDBS f i l e s  and no EDBS f i l e s  simulated  c a n i n c l u d e any o f t h e f o l l o w i n g :  file-name  password  list  f o r write —  task.  for  following (a)  file  to  examination.  EM f o r r e a d / m o d i f y , simulate. MTSFTIE  We  and no  leave  accomplishes  tasks:  The a c c o u n t the  -- ED f o r r e a d ,  a r e not easy  further  remaining  fnum  o p t i o n i s n o t used by EDBS and n o t s i m u l a t e d .  of o p t i o n s  option  [:password ] [ / o p t i o n s ] ' F T I E  number i f p r o v i d e d name  account:file-name.  to  produce  i s concatenated the  MTS  to  name  this the  73  (b)  The  file  filename The which  i stied. tables  function  one  simulates  argument,  o f MTSUNTIE i s t o  corresponding  file  i s , the f i l e  are updated.  MTS UNTIE f u n c t i o n  takes  That  names  1  the  a vector delete from  number and  CDC  FUN TIE  of f i l e  the the  t i e numbers.. The  file  file  function  t i e numbers  and  number and f i l e  name  tables respectively. The  MTS TRAP 1 f u n c t i o n  trapping  function.  appear p o s s i b l e from  available  concurrent  locks locks this  the  trapping  o f t h e CDC/APL  interface f i l e  and e r r o r  trapping  expected  CDC  function  error  does.not  gets  called  when  system  file  with  capabilities, EDBS  is  system  the exception the  1  run  are of  following  under MTS i n a  environment:  (a)  very  (h)  l o s s of database  (c)  deadlock  Very  little  little  concurrency correctness  concurrency  a r e not a u t c m a t i c a l l y signs point (a)  1  via  be  error  of the  nothing.  a l l facilities  can  i n place  The MTS TRAP 1 f u n c t i o n  that  CDC l o c k i n g  problems  CDC  t o simulate.  EDBS b u t does Given  the  The  i s used  o f f from  APL,  i s possible released The  f o r the h i e r a r c h i c a l  When  a  because  until  following  MTS  automatic  the user h o l d i n g t h e examples  illustrate  system:  u s e r GET-HOLDs a segment, t h e h o l d  vector  Each u s e r h a s h i s own f i l e number t a b l e and f i l e name table which reside i n h i s a c t i v e workspace t o r e c o r d f i l e s c u r r e n t l y t i e d and w h i c h a r e d e s t r o y e d when he l e a v e s APL. ' i  74  in  the record  file  When t h e h o l d  prevented file (b)  If the  locked other  by  v i a either A  file  i s  are  the  tables the  locked  Within  deadlocked before is  lock  detected  but EDBS  EDBS will  successful. because  the record  from  user  A  cannot  new have  read.  h o l d i n g any leaves  be  APL  locked f o r  vector..  database read APL.  may  file,  for  until a l l  from t h e schema This  not  be  is  because  locked has  MTS  APL e n v i r o n m e n t , i f two u s e r s  for them  waiting  to write  into  f o r the other  the f i l e  read  they  by MTS an e r r o r message w i l l n o t be a b l e  continue  Correctness  an i n t e n d e d  to correctly  operation of  as the  from a  will  t o r e l e a s e h i s shared  f o r m o d i f i c a t i o n c a n be a c c o m p l i s h e d .  will  be  commands.  by t h e DBA i f a common u s e r  both attempt  each  until  o f f from  tables  will  f o r reading.  the  and t h e n  who  have s i g n e d schema  a  modification.  locked  t o update t h e h o l d  users  modification  from  prevented  file  A DBA may n o t c r e a t e concurrent  file  record  file i s  segments from t h e r e c o r d  automatically  segment o f t h e same t y p e  (c)  updated.  users  t h e GET o r GET-HOLD  users  modification  and  for  concurrent  r e a d s a segment  Concurrent  because  MTS  from r e t r i e v i n g  user  checked  v e c t o r i s updated t h e r e c o r d  automatically Thereafter,  must be  be p a s s e d  i f both database  i t .  writes i s  update has n o t b e e n made. .  lock  I f deadlock back t o  interpret  be  not  EDBS  Rather,  had  been  maintained  75  Co  Problem  Formulation  EDBS h a s a l o g i c a l of  locking.  mechanism.  The  level  logical  Physical  level  of locking  level  of  locking i s  that  With t h e CDC/APL i m p l e m e n t a t i o n ,  include  the waiting  file  i s tied At  record  the l o g i c a l  level,  i s t h e GET-HOLD  done  by  physical  the  locking  file would  done by EDBS t o d e t e r m i n e  an e n t i t y i s a  or tuple.  occurrence, record  occurrence  modification  i s  Logical  locking  level data  a  The g r a n u l e or  segment  i fa  r e f e r s only  maintained  by  write,  create  or  occurrence,  f o r read  i s a segment  record  The type  granule or  at  destroy  a  actions  by  as those  contained  logical  level.  entities.  for  relation.  t o databases created  EDBS s u c h  s y s t e m , f o r example, t h e o n l y  segment  relation.  type,  schema t a b l e s a r e n e v e r l o c k e d read,  level  f o r write.  occurrence  Other  physical  locking  system.  and c h e c k i n g  and a  EDBS. i n the Actions  In the r e l a t i o n a l  a r e GET, PUT,  UPDATE  and  DELETE. At is  the physical  a file.  action  is  inserting  a  file  section  system  Second, level  describes  operation  we  examine  for  EDBS c o n c u r r e n c y  concepts  presented  t h e EDBS l o c k  and a t t h e p h y s i c a l  concurrency  and t h e g r a n u l e  maintained  by EDBS.  reading,  An  writing,  level.  Third,  Finally  unit of  facilities II.  First,  consistency.  p r o t o c o l both a t the l o g i c a l  i n terms of l e v e l  provided.  control  i n chapter  an EDBS t r a n s a c t i o n a s o u r b a s i c  EDBS i m p l e m e n t a t i o n s of  are records  records.  terms of the b a s i c  we d e f i n e  entities  a p p l i e s to a l l data  or d e l e t i n g  This in  Locking  level  we compare t h e  of consistency a  list  of  various  and amount  key  problems  76  associated  w i t h r u n n i n g EDBS i n a c o n c u r r e n t MTS e n v i r o n m e n t  is  provided. The referred an  reader to i n this  all file  concurrency  1.  advised  chapter  MTS e n v i r o n m e n t  that  that  t h e MTS/APL  v e r s i o n o f EDBS  i s t h e one which i s  operational i n  as a s i n g l e  system  user  requirements  system.  That  i s , we assume  have been s i m u l a t e d e x c e p t f o r  control.  Iransaction Definition  Recall by  the  options  that  same  consistent  a transaction  user  which  database  into  i s d e f i n e d as a group o f a c t i o n s  when  executed  alone  a new c o n s i s t e n t  state.  were c o n s i d e r e d f o r c h o o s i n g  (a)  APL t e r m i n a l s e s s i o n  (b)  APL program  (c)  group  (d) s i n g l e  Before database, of  is  a  The f o l l o w i n g  an EDBS t r a n s a c t i o n :  c o n t a i n i n g EDBS f u n c t i o n  o f EDBS  transforms  calls  commands  EDBS ccmmand  one o f t h e above o p t i o n s can be s e l e c t e d , t h e  entity,  action  terms  and u s e r must be d e f i n e d i n t h e c o n t e x t  EDBS. EDBS  comprise data  i s  used  to  the record f i l e s .  such  as  the  problem  i s concerned  files (  not  database  create  just  manipulate  In addition,  EDBS  schema t a b l e s and DBA l o g . with  the  as a l l . d a t a  and  databases maintains  maintained  files). by EDBS.  Hence,  other  Our c o n c u r r e n c y  maintaining correctness  record  which  of  a l l EDBS  we must d e f i n e a  77  There a r e t h r e e Only  common  database  users  users (  u s e r s o f EDBS: S A s  or DBAs i.e.,  who  have  users  of  DBAs and common u s e r s .  r  become databases  Since our concurrency  problem i s concerned  we must  a s an EDBS  d e f i n e a user  There For  several  example, an e n t i t y  segment, such be  are  record  as a f i l e  something  value,  field We  level  component.  s m a l l e r than  select  A single  either  a  c r e a t e d by EDBS).  with  a l l  EDBS  for defining  logical  item  data,  an e n t i t y . such  as  c o u l d be a p h y s i c a l  In addition, of these  a record i n a f i l e (the f i l e  system  r e c o r d i s used  data-items  within  occurrence.  Thus, i n c e r t a i n  to  are  items  an e n t i t y such  a  item could  as an i n d e x  value or data-item.  of c o n c e r n  entity  be  o r t u p l e o r an e n t i t y  or f i l e  users  user.  alternatives  could  common  refer  a  a s an e n t i t y  level)  these are the e n t i t i e s .  to store a l l  tuple,  segment  contexts  to a tuple,  because a t our  domains,  fields  occurrence we  will  or  use  or  record  the  term  segment o r r e c o r d o c c u r r e n c e (and  vice versa). Finally, create to  or destroy e n t i t i e s .  occur  indivisibly  individual deleting  file  other  read,  Any o t h e r c o m p u t a t i o n s  some a c t i o n .  operations  a r e two b r o a d  manipulation utilities  creating  with  Actions  write,  a r e assumed  We c h o o s e a s a c t i o n s t h e  f o r reading,  writing,  inserting,  records.  There Data  we must d e f i n e an a c t i o n .  and  databases..  types  commands s u c h such  as those  destroying  Execution  of operations supported  by EDBS:  a s GET, PUT, UPDATE, DELETE f o r creating  databases  and  and  and d e s t r o y i n g DBAs, granting  access  o f each EDBS o p e r a t i o n g e n e r a t e s  to  a certain  78  sequence in  of  actions.  the h i e r a r c h i c a l (a)  Check the  (b)  system  necessary  Check  files  f o r segment t o  a l l descendant  record  actions  system  done by EDBS entity As  associated  because the required  (i.e.,  file  update  the  DBA  include  creation  called  stores  be  file.  (the hold  record  on t h e b u f f e r  only  temporary done by t h e  action.  vector)  create Actions  the  Locking  i n t h e DBA  i s updated.  required schema  associated  o f a number o f e n t i t i e s  o f an e n t i t y  the  Locking an  include  mechanism) does g e n e r a t e an a c t i o n .  to  in  the  log (i.e.,  to create tables  a  and  w i t h CREATEDBA schema  tables  the vector  o f DBA  numbers).  EDBS does n o t p r o v i d e same  file  to  from  operations  example, t h e EDBS u t i l i t y  log  and  DELETE command  deletions  read/write  buffer  the hold  of operations  account  and  not considered  DBA c o n s i s t s  update  the  on a p e r u s e r b a s i s .  i n the record another  with  tables  do n o t c o n s i d e r  i s also  deleted  files.  t h e schema  information  has  segments.  Unlock  We  user  t h e segment i s  be  (e)  t o be a c t i o n s  and  t o ensure t h a t  segment and i t s d e s c e n d a n t s ,  files.  tasks:  rights.  Delete  reads from  An  file  the  {d)  The  command  held.  (c) L o c k r e c o r d for  to ensure t h a t  access  buffer  t h e DELETE  which p e r f o r m s t h e f o l l o w i n g  schema t a b l e s  being  file  F o r example, c o n s i d e r  user  may  be  transactions.  TRANS o p e r a t o r s  a mechanism  grouped  into  whereby  consistency  actions  by  preserving  the units  ( R e c a l l t h e System R BEGIN-TRANS and END-  for this  purpose.)  79  We d e f i n e which  have been  resulting  no  carefully  i s option  current  state  way o f knowing Given  defining support The  that  a  i s that  i t i s  not  support  transaction  for  backout through  of  concurrency.  support read  a problem control  support  with  EDBS i n  mechanism h a s  option  containing  EDBS  INGEES  a r e not a c o n c e r n  begins. (c) f o r  commands.  designers  h e r e b e c a u s e EDBS  Hence,  additional  because  i t would be ,too  F o r example, i f i t  would which  was r e a d  mean  were  o f System that  deemed  unit  restrictive  necessary  to  E, the requirement f o r  another  has b e e n r e a d until  does  i s not expected. I  a transaction  3  when  overheads  (a) ] i s n o t a s u i t a b l e  level  the  preserving.  ends and a n o t h e r  concerned  calls  that  be a m i n o r g e n e r a l i z a t i o n t o  program  backout.  such  [option  entity  the e n t i t y  i t would  system  consistency  an  to  operations  session  reproducibility  modify time  option  APL t e r m i n a l  defining  As n o t e d ,  possible  which  this  user  the concurrency  ( b ) , an APL  considering  for  a  where one t r a n s a c t i o n  difficulties  An  by  i s consistency  (c) a b o v e .  transaction,  option  as a g r o u p o f i E D B S  chosen  seguence o f a c t i o n s  This its  an EDBS t r a n s a c t i o n  user  by a g i v e n  the given  user  could  user from t h e  signs  APL.  not  off  from  1  An because  EDBS  utility  could  i t i s consistency  serve  preserving.  subsection  discusses  why  manipulation  command, c o u l d  option not serve  by i t s e l f The (d) , as a  as a  transaction  remainder  a  single  of  this  EDBS  data  transaction..  80  EDBS  data  manipulation  consistency  preserving.  hierarchical  system  preceding  GET-HOLD  considered  t o be a  occurrence  segment  occurrences,  consistency  2.  Lock i n g  next  that  at  also  a  lock of  protocol  alone  into  c a n n o t be only  one  will  not  transactions  which  transactions  protocol  (i.e.,  will  t h e GET-HOLD  t h e GET-HOLD command  guarantees result  in  mechanism)  is  schedules.  i s restricted  segment o r r e c o r d  occurrence  with t h i s  The major  t o o p e r a t e on a t one  time.  approach c o n s i d e r t h e  example:  database that  exactly "Segment  one c o n s i s t e n c y S1 i s e q u a l  two EDBS t r a n s a c t i o n s ,  S2 a c c o r d i n g {(11,  the  c o n s t r a i n t r e l a t e s two  t o group a c t i o n s  t h e problems a s s o c i a t e d  that  i t updates  t o guarantee s e r i a l i z a b l e  Suppose t h a t the  command  by  schedules.  i s that  see  REPLACE  because  general  obtained  command when e x e c u t e d  execution  EDBS l o c k  following  and  this  most one r e l a t i o n ,  To  The  and i f a c o n s i s t e n c y  i s to provide  sufficient  problem  command.  in  REPLACE command i n t h e  u p d a t e s t h e segment  we a r e a b l e  concurrent  serializable  not  the  not  preserving.  that  step  The  are  Protocol  Given the  Consider  transaction  segment  be  which  commands  to the f o l l o w i n g  constraint  t o Segment S 2 " .  applies to Suppose  T 1 and T 2 , u p d a t e segments schedule:  GET-HOLD, S 1 ) ,  ( T 1 , REPLACE, S 1 ) ,  (T2,  GET-HOLD, S 1 ) ,  ( T 2 , REPLACE, S 1 ) ,  (12,  GET-HOLD, S 2 ) ,  ( T 2 , REPLACE, S 2 ) ,  (T1,  GET-HOLD, S 2 ) ,  ( T 1 , REPLACE,  S2)}  S1  81  As the the  usual,  segment REPLACE The  Eswaran  we do n o t show b u f f e r i n the buffer  commands.  Modification  i s assumed t o o c c u r  indivisibly  with  command. above  schedule  is  not  serializable  according  e t a l . (1976) b e c a u s e T1 u p d a t e s S1 b e f o r e  updates  S2  before  logical  level  is  concurrency  T1 does.. T h u s t h e EDBS l o c k  unsuitable  to maintain  to  as  a  database  EDBS p h y s i c a l l e v e l (a)  of  T2 does and T2 protocol  for  at the  controlling  correctness.  locking  guarantee  mechanism  to  appears t o serve  correctness  of  a  two p u r p o s e s :  single  EDBS  operation (b)  t o implement  This  part  of the l o g i c a l  i s n o t an uncommon  approach.  mechanism i n which p h y s i c a l l o c k s that  operations  results.  With CDC/APL The  to accomplish regard  used  such  we  that  with  to  ensure  give  correct  i s a v a i l a b l e whereby p h y s i c a l  locking  locking.  t o (a) above, t h e o n l y  (Suppose  be l o s t  R e c a l l t h e System R l o c k  on pages a r e  logical  implementation  T2=£R2,W2}, will  an o p t i o n  mechanism f o r d o i n g  example:  locking  at the R e l a t i o n a l Storage I n t e r f a c e  Also,  may be used  level  guarantee  i s that  lost  so  illustrated  is  have  two  made  updates w i l l in  the  be p r e v e n t e d . the  transactions,  following  T1=£R1,W1} and  S(R1) =S(W1)=S (R2)=S (W2) = £x) .)  e i t h e r of the f o l l o w i n g  by  An  update  schedules:  S1= {S1[X ]R2£X ]W1[ X ]W2£X ]} S2= {R1£X]R2£X]W2£X]W1£X]} Recall according  that  these  t o Papadimitriou  schedules  cannot  (1979) b e c a u s e  be  serializable  i n S1, T1 i s dead  and  82  in  S2,  either  T2  is  occur.  t h e r e i s no s e r i a l  In  does n o t a l l o w e i t h e r  either  schedule  t r a n s a c t i o n t o attempt The  serializability  schedules,  schedule  i n which  be dead. o f t h e above  We assume t h a t t i e f o r w r i t e o c c u r s  write.  input  and  t r a n s a c t i o n would CDC/EDBS  second  dead  schedules  indivisibly  to  with the  according to the lock p r o t o c o l the to write w i l l  redo  h i s read.  component o f EDBS w i l l  S1 and S2, i n t o  transform  the r e s p e c t i v e output  the  schedules  51 ( o u t p u t ) = {B1£X]B2[X]W1£X ]B2[ X ]W2£X ]} 52 ( o u t p u t ) = (E1[X ]E2£X ]W2[X ]B1[X ]W1[X ]}  Since output  the reads  schedules  which a r e r e d o n e a r e i g n o r e d  are the s e r i a l  the e f f e c t i v e  schedules  51 ( e f f e c t i v e ) = {E1£ X ]W1[ X ]R2£X ]W2£X ]} 52 ( e f f e c t i v e ) = (B2£ X ] W2£ X ]B 1[ X ]W 1 [ X ]} With r e g a r d t o (b) a b o v e , t h e CDC/APL not  provide  intended  the l e v e l of i s o l a t i o n  for  the  implementation modification user  will  system.  guarantees  command  other  Becall that  involving  from  implementation  that  during  a record  users  does  originally  the  execution  APL*PLDS of  any  (segment, r e l a t i o n )  have e x c l u s i v e use o f t h e r e c o r d t y p e  (segment  the type,  relation). Exclusive never  use o f a f i l e ,  guaranteed  the  CDC/APL l o c k  to  a  file  other  users  type  or  otherwise,  w i t h t h e CDC/APL i m p l e m e n t a t i o n . p r o t o c o l i s such  other  implementation  record  users  does e n s u r e will  be  may  Becall  t h a t when one u s e r i s  read  from  the f i l e . .  from  modifying  that  writing  The CDC/APL  t h a t d u r i n g any m o d i f i c a t i o n  prevented  i s  command  the record  type  83  (segment t y p e , . r e l a t i o n ) .  3-  Level of  The with  System R m u l t i p l e l e v e l s o f c o n s i s t e n c y  the  though  view  a  that  certain  preserving, In will  Consistency  seguence  subsection,  describe  APL*PLUS  consistency  automatic  consistency level  the  and  of  view  System  is  not  CDC/APL  R levels  consistency  of consistency  as  versions  a v a i l a b l e when EBBS r e l i e s  of c o n s i s t e n c y  Even  of the database.  operations  control.  a  means  of  o f EDBS and t o solely  It i s felt  on  MTS  that the  i s u s e f u l , as an i n d i c a t o r o f EDBS  e v e n t h o u g h we a r e a p p l y i n g  this  notion,  not a t  a t r a n s a c t i o n a s i n System R, b u t a t t h e l e v e l  the  o f one  operation. Recall  Level  t h e System R l e v e l s  of consistency:  1 - l e a s t i s o l a t i o n from o t h e r u s e r s - a t r a n s a c t i o n may r e a d uncommitted  data  Level  2 - a t r a n s a c t i o n r e a d s o n l y committed d a t a - read r e p r o d u c i b i l i t y i s not guaranteed  Level  3 - complete i s o l a t i o n frcm other users - a t r a n s a c t i o n r e a d s o n l y committed d a t a - read  The  APL*PLUS  operations  with  reproducibility version  something  Read r e p r o d u c i b i l i t y  an  actions  l o c k i n g f o r concurrency  System R n o t i o n  is  of  be a p p l i e d t o i n d i v i d u a l EDBS the  concerned  t r a n s a c t i o n has o f t h e d a t a b a s e .  i t may have a c o n s i s t e n t  this  comparing  EDBS  a  i s  EDBS  may r e a d  appears  to  between c o n s i s t e n c y  i s guaranteed,  i n t e r l o c k e d a t most once operation  of  i s guaranteed provide  levels  uncommitted  2 and 3,.  assuming t h a t a . given  w i t h i n t h e same o p e r a t i o n . data  EDBS  file  However,  because f i l e i n t e r l o c k s  84  do  n o t a p p e a r t o be h e l d t o t h e end o f an o p e r a t i o n . The  EDBS  consistency. write  into  cannot  operations Since  the f i l e  be  data,  other  from  is  users  the read at  the  guaranteed.  uncommitted  under  again  CDC/APL  achieve  modify t i e permits same  time,  Further,  because  read  an  other  1  users t o  reproducibility  operation  a t i e f o r write  reading ( regardless  level  may  does n o t  o f when t h e t i e  read  prevent  for  write  released) . What l e v e l  locking? locked. All  Every Every  locks w i l l Read  operation  entity  entity  read  only  once an e n t i t y  user  level  3 consistency.  releases  of c o n s i s t e n c y  will  an e n t i t y  read  that  by  an  i s that  be l o c k e d  which  file  Of c o u r s e , very  by  for exclusive  use.  b e c a u s e no f o r read,  other  user  the e n t i t y . paid  concurrency  for will  an  i s not until This i s  this be  other  and  because read  some  containing  little  will  operation.  data  the price  automatic share  i s locked  committed  MTS  be  be g u a r a n t e e d  i s modified  the  with  operation  t o t h e end o f e a c h  reproducibility  will  c a n we e x p e c t  written w i l l  be h e l d  can modify  operation possible  of consistency  level  provided.  4.. Amount o f C o n c u r r e n c y Amount o f c o n c u r r e n c y of a c t i o n s  from  different  r e f e r s t o t h e amount o f i n t e r l e a v i n g transactions.  85  With  EDBS, i n t e r l e a v i n g o f a c t i o n s  restricted  at  Interleaving In  versions (i.e.,  subsection, offered  by  o f EDBS a t t h e  level  CDC/APL  APL*PL0S version  interleaving file,  the level  version  because  whereas  the of  the  relative CDC/APL  individual  from  locking. amounts  and  EDBS  MTS  of APL  operations  operat  supports l e s s concurrency that the  the  CDC/APL  file  permits  by d i f f e r e n t u s e r s t o t h e same  implementation  actions  system  does  by d i f f e r e n t u s e r s  not  permit  involving the  file. To  clarify,  suppose e n t i t i e s  same f i l e  and c o n s i d e r  schedules  S1, S2 and S3:  S1={.  ..  E1[X]E2[Y]E1[Z]  S3={... W1[ X ]W2[ Y ]W1£.Z ] The actions  CDC/APL  X, Y, and Z a r e s t o r e d  the f o l l o w i n g  lock  seguences o f a c t i o n s  of these  would  within  ...}  protocol  not allow  schedules.  the  ...}  would  permit  shown i n s c h e d u l e s S1 a n d S2 b u t n o t S3.  protocol  in  ...}  S2= {. . . . W1[ X ]R2[ Y ]W1[ Z ]  any  GET-HOLD mechanism.  by p h y s i c a l l e v e l  of  APL*PIUS  any  the  APL*PLUS,  o f r e a d s and w r i t e s  interleaving  lock  via  we compare  i n t e r l e a v i n g of actions The  same  logical  i s further restricted  this  concurrency  a  from d i f f e r e n t u s e r s i s  t h e sequence o f The  t h e sequence of a c t i o n s  APL*PLUS shown i n  86  The lies  amount o f c o n c u r r e n c y  somewhere  versions. writes)  between  that  of  by d i f f - e r e n t but  not  schedules  responses  o f t h e MTS/APL l o c k  EDBS  APL*PLUS  under and  MTS  CDC/APL  o f r e a d s ( b u t n o t r e a d s and  users involving  S1  with  the  MTS s u p p o r t s i n t e r l e a v i n g  schedule  5.  expected  t h e same  S2  and  file.  That i s ,  S3 would be p o s s i b l e  protocol.  Key P r o b l e m s This  solved  subsection i d e n t i f i e s  before  EDBS  i s  key  problems  operational  in  which  a  must  concurrent  environment: (a) EDBS d o e s n o t s u p p o r t  a basic  (b)  the  The l o c k p r o t o c o l sufficient  (c)  Very  t o guarantee  little  automatic  of c o n s i s t e n c y .  logical  serializable  concurrency  is  level  i s not  schedules.  p r o v i d e d due t o MTS  locking.  (d) C o r r e c t n e s s situation  at  unit  may  be  should arise  destroyed  i f  at the physical  a  deadlock level.  be MTS  87  Chapter  IV:  In  Recommendations  t h i s chapter  to p e r m i t t i n g System.  objective  correctness  of  TRANS  END-TRANS  defining an  A.  and  several  use  of  of  each  maintained  by  Educational  approach  EDBS.  operators We  the  alternative  are  We  is  Data  to  assume  available  as  supporting  Base  guarantee  that  c o n c l u d e t h i s c h a p t e r by  specifying  approaches  BEGIN-  a means  of  recommending  routines..  Alternatives In  this  Alternatives relying  on  1  transaction  file  2  we  investigate  are  s i m i l a r i n that  system  backout. to  extensive  do  t o do  logical  i n t h e i r proposed  i n terms of  system  require  and  differ  implications  file  section  the  alternatives  in  data  transactions.  approach  present  concurrent  The  and  we  freedom  Alternative logical  three  from  of  locking.  deadlock  and  3 p r o p o s e s not  EDES and  recommend  protocols.  level locking.  modification  they both  level  lock  alternatives.  to  This i s not  The This  the  approach discussed  (a)  protocol  A transaction  i s described has  a locking  as  follows:  phase and  an  unlocking  phase. (b)  The  locking  locking  phase i s p r o v i d e d by  facilities  (i.e.,  Every  the  MTS  entity  automatic read  by  the  here  A l t e r n a t i v e : _1  lock  for  would  detail.  The  has  need  r e l y on  two  a  88  transaction  will  prior  t o the read  will  be l o c k e d  to the write  be  locked  action.  Every  f o r modification  action.  may be r a i s e d  f o r read  within  immediately  entity  written  immediately  prior  The l o c k c l a s s f o r an e n t i t y a  transaction  but  i t  will  n e v e r be l o w e r e d ) . (c)  A l l locks step  are automatically  i n the  unlocking This backout  lock  lock  lock  used  intention The means  work:  System  proposal  transaction  The  not  deadlock f r e e .  the  R  Transaction  f o r deadlock r e s o l u t i o n .  level  f o r deadlock,  serializable  a p p e a r s t o be  a  3  on t h e  the a c t u a l granule record  locks  transactions  the  MTS  schedules.  simplified  type,  file  locked  relation).  system will  The  version  (i.e.,  of  without  containing following  types.  to  be one f i l e  the  locking (i.e.,  transaction  a  locks  the e n t i t y . example i l l u s t r a t e s  how a l t e r n a t i v e 1 might  e a c h o f two t r a n s a c t i o n s Suppose a l s o The  that  following  attempt  GET-HOLD, S 1 ) , GET-HOLD, S2) , GET-HOLD, S 2 ) ,  to  update  segments S1 and S2 a r e o f  seguence  of operations  i n deadlock: {(T1, (T2, (TI,  do  Hence, when we s a y t h a t a  an e n t i t y we mean t h a t  segments S1 and S2.  result  is  ensures  to rely  Suppose t h a t  different  constitutes  locking).  type,  file  protocol  protocol  by  that  segment  the  protocol  a p p r o a c h assumes t h a t , e x c e p t  automatic, proposed  This  as the l a s t  phase o f the t r a n s a c t i o n .  procedures a r e proposed  This  that  transaction.  released  ( T i , REPLACE, S 1) , (T2, REPLACE, S 2 ) , (T2, GET-HOLD, S1)}  will  89  T1 hold  will  be w a i t i n g  vector  to l o c k S1.  record  HOLD  file  transaction  file  exclusive  because  lock  t o read will the  on t h e f i l e ,  Similarly,  the hold  be a b l e other  vector  to  read  the  be w a i t i n g  f o r segment  lock  during  to  T2 w i l l  type  i t s respective  transaction  obtained  detect  this  deadlock  back t o one o f t h e t r a n s a c t i o n s hold  vector) a  h a s been  signal  receives S1  file  is  the  holding  previous  an GET-  operation. MTS w i l l  be  the record  o f segment t y p e S2.  the record  Neither  t o lock  by TI s h o u l d The  procedure  that  backout.  subsection  (of the  message  could  I n o u r example, i f T1 update  f o rtransaction  discusses  of  segment  could  a database  l o g containing  A record  be e a s i l y  implementation  backout:  o f t h e user  i s not c u r r e n t l y maintained.  a record  the read  deadlock  message t h e n t h e p r i o r  modifications.  modification  This  and p a s s a message  be undone.  EDBS m a i n t a i n s  Also,  unsuccessful.  remainder o f t h i s  considerations  database  indicating  f o r transaction  t h e deadlock  situation  modified  a  list  of a l l  who p e r f o r m e d t h e  The e x i s t i n g  to record  this  logging  information.  o f t h e t i m e a t which t h e m o d i f i c a t i o n  was s t a r t e d  would be u s e f u l . Transaction modifications could  record  global becomes  be  as recorded  would  necessary  stored to  recorded  undone s o l o n g  involve  i n the log.  t h e time a t which  variable  modifications  backout  database  The BEGIN-TEANS  operator  t h e t r a n s a c t i o n was s t a r t e d as  i n the user's back  undoing  the  a c t i v e work s p a c e .  transaction  i n the l o g b e l o n g i n g  out, to this  a  If i t  database user  as t h e time a t which t h e m o d i f i c a t i o n  could  was made  90  is  later  than  The  System  necessary. modified until as  R  Hence,  given  a t which t h e t r a n s a c t i o n principle  the  by a g i v e n  the  part  the time  of  lock  isolated  protocol  transaction i s not  operator,  backout  will  must be s u c h t h a t modified  transaction terminates.  o f t h e END-TRANS  was s t a r t e d .  by  I f locks  isolated  any  be data  other  are released  backout  will  be  guaranteed. A  l o g of modifications  contained EDBS  i n the r e c o r d  (i.e.,  be and  handled  like  END-TRANS  (a)  lock  reguired  automatically  locked  (bracketed  could  (i.e.,  then t h e highest A l l locks  transaction  are  mode i n one  of the t r a n s a c t i o n . be  from r e a d  level  locking  are automatically  transaction.  a  i n the reguired  at the beginning  by  raised  within  mode t o w r i t e  the mode)  mode i s r e q u e s t e d .  released  then  by BEGIN-TRANS  as f o l l o w s :  by  I f t h e l o c k i n g mode i s t o  the  and DBA u t i l i t i e s  transactions  protocol i s described  transaction  (c)  maintained  that  schema t a b l e s and t h e DBA l o g ) .  be l o g g e d  A l l entities  step (b)  any o t h e r  to  currently  than  2  —  The  could  i s not  other  operators).  A l t e r n a —t —i— v e :  — — —  files,  modifications  These m o d i f i c a t i o n s  made t o EDBS d a t a ,  a t t h e end o f  91  This backout  alternative  lock  protocol  INGEES d i f f e r i n g  that  INGRES  locks  a l l reguired The  automatically As  be  by r e g u i r i n g t h a t a n i n t e r a c t i o n  before of  proceeding.  the  Similarly, a l l locks  Alternative  identical  lock  lock  protocol  facilities  t h e END-TRANS  held  could  be  as part  of the  operator  could  by t h e t r a n s a c t i o n .  1 the proposal  i s to rely  Hence, t h e a c t u a l g r a n u l e  on t h e  file  locked  will  file.  entities requests  indicate  event  i n which  will  be  messaqe that  time  could  Since  transaction  (a)  return attempt  the  t h e form  a to  run  be p r a c t i c a l l y  the following  at  the  be  to execution  required.  of deadlock.  I f lock  which r e c e i v e s  the  MTS  code t o t h e u s e r t o  his  transaction  by t h e t r a n s a c t i o n  at  a  could  has n o t y e t e x e c u t e d any  be  impossible difficult  beqinning  of  t o implement to  a  determine  transaction.  problems:  The whole t r a n s a c t i o n prior  reguired  i s not r e q u i r e d .  b e c a u s e i t would  requirements  all  status  transaction  backout  2 would  an EDBS c o n t e x t  Consider  in  and a l l l o c k s c u r r e n t l y h e l d  Alternative  locking  realized  he s h o u l d  released.  actions,  a t r a n s a c t i o n cannot lock  deadlock, then the t r a n s a c t i o n  deadlock  in  Recall  phase  release  with  The  be  i n i t s implementation d e t a i l s .  t o do a l l l o c k i n g .  one  later  proposed  deadlock  operator.  transaction  r e s o l u t i o n are not reguired.  v i a MTS/APL e x p l i c i t  BEGIN-TRANS  that  to that  entities  locking  advantage  i s virtually  only  avoids  implemented  system  the  procedures f o r deadlock  The by  has  would have t o  t o determine  be  analyzed  which f i l e s  will  92  (b)  Within  a s i n g l e EDBS d a t a  utility, There by (c)  more t h a n  is  from (d)  It  file  may  be  reguired.  no way t o d e t e r m i n e t h e f i l e s  examining  Similarly,  one  m a n i p u l a t i o n command o r  reguired  t h e name o f t h e command o r u t i l i t y .  t h e mode o f l o c k  c a n n o t be  determined  knowledge o f t h e command o r u t i l i t y . i s  often  impossible  desired  mode  because  these  of  lock  t o determine e i t h e r the or  the  files  depend on t h e r e s u l t s  reguired  of  previous  actions. A s o l u t i o n t o these  p r o b l e m s might  be t o assume  Hence, f o r a l l t r a n s a c t i o n s  composed  by common  assume  to  schema  that  Further,  read  we c o u l d  access  assume t h a t e v e r y  access t o a l l database database  log  schema t a b l e s  the  file  files.  could  could  be l o c k e d  users  tables  transaction  locked  f o r read  we  could  i s reguired.  reguires  Hence, t h e n r e c o r d  be  the worst.  write  files  and t h e  f o r modification  and t h e  at the beginning  of  each  transaction. DBA  utilities  BEGIN-TRANS file  operator  do n o t r e q u i r e specific  and t h e schema t a b l e s Both  because  alternatives  locks  entities.  are  held  provided  f o r DBAs c o u l d  lock  of by  implementation  each  1 and 2 a r e r e s t r i c t i v e on  files  that  rather  a l l locks  transaction.  Alternative  the  DBA  log  f o r e x c l u s i v e use.  2  requirements  i f  be we  on  than  individual  Alternative 1  must be r e q u e s t e d  The  will  of concurrency  than  A l t e r n a t i v e 2 i s more r e s t r i c t i v e  due t o t h e r e q u i r e m e n t beginning  access t o database f i l e s . . A  amount further  choose  of  at  the  concurrency  restricted  by  t o make worst  case  93  assumptions about the advantage  of  transaction  backout  files  reguired  alternative  2  by  over  a transaction.  A  alternative  is  procedures f o r deadlock  1  resolution  major that  are  not  reguired.  Alternative:  3  Alternative do  not  rely  Further, will  on  we  use  the  part  correctness.  a common  We may  of  user  modify a t the existing to  do  with  lock  not  discuss focus  logical  to  here the  only  level  on  we  locking.  locking f a c i l i t i e s  protocol  3 proposes that  holding  simplicity, a  user  a  We  to  approaches i n that  which  ensure  he  database  special facilities  locking  reguirements  for  user.  capability  that  of do  from p r e v i o u s  system the  need.  Alternative  For  file  provide  as  which a DBA  3 differs  a lock must  more t h a n one protocol could  hold  beginning  a l l logical  an  code c o u l d  unsuccessful  c a n n o t be  immediately  protocol  avoids  placed  deadlock  t r a n s a c t i o n backout  user  be  hold  be  and  hence  procedures are  not  item  enforced  be  which  o f the  items  very  deadlock reguired.  to  the time.  states  intends  Consistent  returned  This  with  a t one  i t e m s which he  i f any  i n hold.  provided  logical  of h i s t r a n s a c t i o n .  approach, a s t a t u s  indicate  the  with the  to the user  requested  simple detection  lock and  94  The  facilities  GET-HOLD  mechanism..  restriction logical the  lock  When  logical  being  Since  not  have  enforce  the  most  IMS does n o t user  one  enforce programs  provided.  segment, r e c o r d ,  i n the database  IMS  at  we have p r o p o s e d ,  (i.e.,  the  i t must  be  relation) i s locked  for  (i.e.,  holds)  and r e l i e s  on t h e  file  system  to  f o r modification.  lock  3 delegates  management.  relation list.  A code c o u l d  time  between  a read  stamp) lock  be r e g u i r e d  lock  be added  triple and a  3  after  alternatively, duration  of  operations blocks.  in  write  will  locks  the  maintained  a  single  provides  EDBS  (user  the  hold  list  Recall  that  System  similar  requirements.  E  locks that  or of a  logical  to distinguish procedures  f o r modification. MTS a u t o m a t i c l o c k s  MTS l o c k s  responsible  could  be  be  released  f o r s e t t i n g them o r ,  remain i n e f f e c t f o r t h e  operation. .  Certain  a t l e a s t one m o t i v a t i o n o f each i n d i v i d u a l  physical level  ID,  Additional  procedures t o reorganize  f o r the duration  record  i n the form  each  lock.  time.  segment,  to  require  action  each  automatic l o c k i n g could  may i n i t i a t e This  for  i s already  a t some a p p r o p r i a t e  immediately  a d d i t i o n a l r e s p o n s i b i l i t y t o EDBS  t o s e t and r e l e a s e  Alternative released  A  i n t h e database  index,  file  may  of  With t h e e x i s t i n g a p p r o a c h , EDBS manages i t s own  Alternative  will  a user  those  does  procedures are  item  modified  l o c k s f o r read  hold  which  and b a c k o u t  a  IMS  a t one t i m e .  protocol  modification.  for  that  (as does EDES) t h a t  may d e a d l o c k ,  lock  Eecall  e n t i t y i n hold  simple  actually  proposed a r e b a s i c a l l y  locking  EDBS  inverted  storage list  f o r maintaining EDBS  operation.  was m o t i v a t e d by  95  Alternative alternatives (1)  3 o f f e r s a greater  1 and  2 f o r the  logical rather the  (2)  items than  The  user  which he to  requiring  has can  is  appropriate  lock  may  be  this  in  logical  automatically freeing  the  locking  are  proposed  entities  explicit  lock  protocol  involved hence  in  of  (i.e.,  his  into his  transaction  lock  For  protocol  example, a  an  entity  use  by  user  and  other  he  users.  a l t e r n a t i v e 3 i s that unless  we  have p r o p o s e d  all  First,  users  database  employ  an  lock  1  resolve by  at  i s such t h a t the  transaction  i t .  the  backout  be  not  procedures  do  thus  any  particular  relying  on  protocol.  MTS The  procedures  2 recommends  that  locked  via  a transaction.  The  occurs,  yet  to  a transaction  automatically of  two  to  i t s lock  beginning  make  Second,  for  Alternative  i f deadlock  d e a d l o c k has  system  t r a n s a c t i o n backout  a transaction  locking  file  recommends  phase o f  a d m i t s d e a d l o c k and to  by  responsibility  Alternative f o r the  2  locking.  reguired  the  and  level  a l l entities the  1  on  lock of  a l t e r n a t i v e s which  to r e l y  physical  user  three  Alternatives  and  required  MTS  about  RELEASE i t f o r  as f o l l o w s :  common:  automatic l o c k i n g protocol  locked  locked.  guaranteed  section  protocol.  lock  be  protocol.  summarized  proposals both  not  may  entire f i l e  i s f i n i s h e d with  disadvantage  correctness  In  be  an  information  explicitly  major  segment)  that  than  reasons:  concurrency.  knows when he  A  a  incorporate  increase  may  following  (i.e.,  segment t y p e )  amount of c o n c u r r e n c y  any  e x e c u t e d any are  not  transaction actions  and  reguired.  96  Alternative locking for  3  proposes  logical  lock  items  protocols  Selected  the  beginning  end  of  up  to the user.  level  locking  2 (i.e.,  transaction)  is  of  BEGIN-TRANS  interface  file  users  contain not  The  (2)  Similarly,  with  due  reguired. with  END-TRANS  to  We  and  work s p a c e s  do  solution  part  Common  users  schema  tables.  EDBS d a t a  do  manipulation  utilities  files.  will  The SA i s  f a c i l i t i e s because h i s  expect  and  to  modify  the  him t o be u s i n g  EDBS  users.  makes  not  the  operators  f o r DBAs  o p e r a t o r s f o r DBAs.  not  of  use  of  the  following  a b o u t EDBS:  DBA  i t s  intended f o r  END-TRANS  intended  initially  EBAs and common  as  modify  commands  i n f o r m a t i o n i n the  do  not  require  to  database  a c c e s s t o t h e DBA l o g f i l e . (3)  at  operators are  t h e work s p a c e s  transaction definition  proposed  information (1)  Rather,  i s t o s e t up t h e s y s t e m  concurrently  largely  and  c o n t a i n BEGIN-TRANS  users.  i f  of a l l e n t i t i e s  n o t be s t o r e d  BEGIN-TRANS and END-TRANS  function system  system.  will  provided  locking  simplicity.  types  common  responsibility  Dependence upon t h e f i l e  chosen  These o p e r a t o r s w i l l  for  the  i s contra-indicated.  automatic  proposed.  common  of  o f a t r a n s a c t i o n and r e l e a s e o f a l l l o c k s a t t h e  implementation Two  additional f a c i l i t i e s for  Approach  Alternative  a  provide  and t o l e a v e most  s y s t e m t o do l o g i c a l  B.  to  do n o t r e q u i r e a c c e s s  97  (4)  The  Database f i l e s log)  remain  user  so l o n g  {i.e.,  tied  record  files  when.EDBS r e t u r n s  remainder of t h i s  section  c o n t r o l to the  provides  BEGIN-TBANS and END-TRANS o p e r a t o r s  the  implementation.  DBA  database  as t h e d a t a b a s e i s open.  the  (1)  and  specifications for  and o u t l i n e s d e t a i l s  of  Operators  BEGIN-TR AN S - l o c k t h e schema t a b l e s f o r d e s t r u c t i o n - l o c k t h e DEA l o g f i l e f o r m o d i f i c a t i o n END-TRANS - release  {2)  Operators  a l l locks  held  f o r Common  on schema t a b l e s  and DBA  log f i l e  Users  BEGIN-TRANS - l o c k a l l r e c o r d f i l e s and t h e l o g f i l e (belonging t o t h e c u r r e n t l y open d a t a b a s e ) f o r m o d i f i c a t i o n - l o c k t h e schema t a b l e s f o r r e a d END-TEANS - release tables (3)  a l l locks  Implementation (a)  The  BEGIN-TEANS  destruction.  tables lock  operator  (ZTTABLE, This  modification  utilities  on d a t a b a s e  files  and  Details  schema t a b l e s  than  held  f o r DBAs must ZETABLE,  lock  class  be  locked  for  the  require  write  DBA  is  access  to  that  to i n h i b i t  the the  only  for  rather  one o f t h e DBA  destruction.  mode i s not e x p e c t e d  because  ZFTABLE)  i s chosen  because a t l e a s t  (DESTBOYDBA) r e q u i r e s  lock the  user  schema  the The  schema higher  concurrency who tables  would and  98  lock him  for  from a l s o  read by (b)  destruction writing.  The  log file  operator  BEGIN-TRANS  lock  t h e schema  files  for  from  FNAMES.  Only  the  and  database  system  are  variable  FNAMES  whose  from FNUMS i s g r e a t e r as  tables  will  database  files.  reguire  t h e DBA  number.  procedure  operator  for  recommend  that  function,  files  and t h a t  FRELEASE f u n c t i o n . the f i l e .  unlocking  for  files  conclude  common  file could  they  files.  via  that  here.  the  be u n l o c k e d  FMTS  v i a the  FRELEASE into  are  also  advantages  c l o s i n g them  there  The  a l s o be used  Investigations without  must  names o u t l i n e d f o r  be l o c k e d  Recall  that  users  and d a t a b a s e  locating  BEGIN-TRANS o p e r a t o r  to  read  from  selected  u n l o c k t h e schema t a b l e s  us  We  variable  of d a t a b a s e f i l e s  number  schema  The END-TRANS  closes  for  filenames  15 s h o u l d  account  the lock.  dependent  the i n t e r f a c e f i l e  be  of  The SA's  f o r common u s e r s must  Names  than  LOCK  lock the  spaces.  tables  tie  We  f o r DBAs must  operator  corresponding  account  work  write.  available  Locking  (e)  excluded  s t o r i n g the system  The  reguire  be  f c r modification..  SYSACCNT i n a l l DBA  the  will  must be known t o a c c o m p l i s h  recommend  (d)  u s e r s who  class.  BEGIN-TEANS  number  (c)  Common  would n o t e x c l u d e  a c c e s s t o t h e schema t a b l e s  either locking  DBA  by a DBA  none  has  led  (i.e.,  99  reductions be In  and  we  by n o t c l o s i n g f i l e s  would  insignificant).  this  providing  i n overhead  chapter  we have d e s c r i b e d  concurrent  have  use  selected  implementation.  three  alternatives  of the Educational  an  approach  We c o n c l u d e t h i s  based  Data  on  chapter  with  Base  for  System,  feasibility  of  a summary o f our  recommendations: (1)  BEGIN-TRANS and provided own  {2)  operators  should  be  by means o f which a u s e r may d e f i n e h i s  transactions.  Entities  reguired  automatically operator the (3)  END-TRANS  transaction  as p a r t  and a u t o m a t i c a l l y  should  be  o f t h e BEGIN-TRANS  unlocked  as  part  of  operator.  should  locking  a  locked  END-TRANS  EDBS  by  rely  reguired  on by  the f i l e  s y s t e m t o do a l l  i t s concurrency  control  mechanism. (4)  In  terms  of  assumptions reguired The  amount  should  of  c a n be summed  may r e a d  from  execute  maintained serial  be  made  (2) above, w o r s t concerning  concurrency  provided  up as f o l l o w s :  Any number o f t r a n s a c t i o n s  a t t h e same t i m e .  concurrently  different  fashion.  entities  by o u r recommended  t h e schema t a b l e s  by EDBS.  case  by a t r a n s a c t i o n .  approach  may  implementing  on  Otherwise,  Transactions  databases created  transactions  are executed  and  in  a  100  Chapter  V:  Conclusion  This  thesis  undertaking  has  described  and p r o p o s e d  concurrent  a  our e x p e r i e n c e  with  solution  for  running  clarified  the  basic  EDBS  in  a  EDBS e n v i r o n m e n t .  In  chapter  concurrency examined  2,  we  c o n t r o l which i s t o  one  ensure t h a t  approach  actions  serializable  for  from  ensure  obtaining  transactions  fashion.  Next,  we  objective  correctness. correctness are  concurrency  examined  control f a c i l i t i e s  We  which* i s t o  two l o c k  provided  of then  intermingled  which have been shown t o g u a r a n t e e s e r i a l i z a b i l i t y . reviewed  t h e EDBS  in  a  protocols  Finally,  by a number  we of  systems. In  chapter  3,  we  examined  facilities  and compared them t o  provided  various  including of  analyses  those  of  provided.  MTS  based  further 1.  4,  systems..  existing  lock  we c o m p i l e d EDBS i s  We  protocol and  a list  level o f key  operational  in  a  various we  alternative solutions  recommended  an  approach  areas  reguiring  considerations.  remainder  of t h i s  chapter  identifies  work.  In t h i s write have  we p r o p o s e d  t h e key p r o b l e m s and  on p r a c t i c a l The  other  control  environment.  chapter  which s o l v e d  concurrency  of c o n c u r r e n c y  Finally,  problems r e g u i r i n g r e s o l u t i o n before concurrent  of  the  an i n d i c a t i o n o f t h e amount  consistency  In  EDBS  t h e s i s we have r e s t r i c t e d  actions. not  Those t h a t  been  create  considered  in  our a t t e n t i o n t o read and d e s t r o y detail.  their The  and  entities  notion  of  10 1  serializability whichin  create  chapter  should  must be and  2 and  be  extended  to  account  destroy e n t i t i e s .  the  alternatives  examined  in  terms  The  actions  analyses presented  proposed  of  for  this  in  chapter  3  broader n o t i o n of  serializability. 2.  We  have  logical such  identified  two  level  as  as  records.  entities  which  categories. creates  such  not  entities.  write into This  synchronization and  databases. solution  destroy  The in  problem  the  the  of phantoms has  as g i v e n by prevented  given  predicate,  a  Thus, t h e  as  refers  entities  (i.e.,  clear  how  he he  additional  the  which and  proposed  i n which a DBA  been t h o r o u g h l y  the  entity  terminates.  second  different  to  not  a d d i n g an  non-existence  problem  that  t h e schema t a b l e s  If a transaction  transaction makes a  If  transactions  some p r e d i c a t e t h e n  from  transaction  two  t h e n he h a s c r e a t e d no  for  situation  these  attempts  w h i l e some u s e r has i t open.  t h e c o n t e x t o f EDBS.  must be  items  access  log f i l e .  indicates  reguired  of  a  level  c r e a t e s a database  database  For example, i t i s not would h a n d l e  entities  the  these f i l e s ,  such  at  at a p h y s i c a l  either  when a DBA  and  be  to d e s t r o y a database 3.  to  difficulty may  those  those  some EDBS t r a n s a c t i o n s  belong  example,  the r e c o r d f i l e s  does n o t a l s o  create  segments and However,  may For  t y p e s o f EDBS e n t i t i e s :  relational  t u p l e s ) are r e t r i e v e d  other  to  a  will  set  set  until  i f the on be  same  retrieved.  locked.  system  where  i t also  given  the  must be  and  of  transactions  this  based  s e t of e n t i t i e s o f an e n t i i t y  locks  Otherwise,  retrieval  investigated  This sets  refers  of to  102  the  hierarchical  at a time system, locked  i s retrieved. the  a  F o r example,  non-existence  until  transaction upon  and network s y s t e m s where o n l y one e n t i i t y  the does  first  end not  of  a  so  transaction  and  did  be  i n t e r m s o f how t h e y  might  investigate and  the  problem  written  read  that  instantaneously.  EDBS s u p p o r t s  various  assured  cannot  avoids l o s t  p o s s i b l e t o vary  being  environment  in  between t h e l o s t  are  Given  for  read  that values f o r variables  EDBS  simulate  set  that  the  second 3 should  problems. which  update  to  problem  Papadimitriou's variables  in  instantaneously  i n the  a  and  write  set are  these assumptions,  the only  be s e r i a l i z a b l e  i s i f updates  updates at a l o g i c a l  the concept  a  i n chapter  of ensuring consistency.  way t h a t a h i s t o r y lost.  useful  upon  r e s o l v e phantom  model assumes t h a t v a l u e s  transaction's similarily  a  the r e l a t i o n s h i p  transaction  exist  a l t e r n a t i v e s presented  provide  must be  t h a t t h e segment d i d n o t e x i s t  The  4. . EDBS  hierarchical  segment  retrieval. evaluated  the  of a p a r t i c u l a r  find  retrieval  in  level.  get Given  o f a t r a n s a c t i o n , i t might be  the lock p r o t o c o l at a  physical  level  to  c o n d i t i o n s f o r consistency, a l l the while  that the l o s t  u p d a t e p r o b l e m i s under  control.  103  BEFERENCES  A s t r a h a n , M.M., D.D. B l a s g e n , D.D. C h a m b e r l i n , K.P. Eswaran, J.N. G r a y , P.P. G r i f f i t h s , S.F. K i n g , R.A. L o r i e , P.R. McJones, J.W. M e h l , G. R. P u t z o l u , I. L. T r a i g e r , B.W. Wade, and V. Watson. 1976. System R: R e l a t i o n a l a p p r o a c h t o d a t a b a s e management. ACM T r a n s a c t i o n s on D a t a b a s e Systems 1 (2) : 97-137. B a y e r , R . a n d E. M c C r e i g h t . 1972. O r g a n i z a t i o n and m a i n t e n a n c e of l a r g e o r d e r e d i n d i c e s . A c t a I n f o r m a t i c a 1: 173-189. B e r n s t e i n , P.A., D.W..Shipman, J.B. R o t h n i e , and N. Goodman. 1977. The c o n c u r r e n c y c o n t r o l mechanism o f SDD-1: A s y s t e m f o r d i s t r i b u t e d d a t a b a s e s {the g e n e r a l c a s e ) . Computer C o r p o r a t i o n o f A m e r i c a TR CCA-77-09. Cambridge, Mass. B e r n s t e i n , P.A., D.W. Shipman, and J.B. R o t h n i e . . 1980. Concurrency c o n t r o l i n a system f o r d i s t r i b u t e d database (SDD-1)..ACM T r a n s a c t i o n s on D a t a b a s e Systems 5 ( 1 ) : 18-51. B e r n s t e i n , P.A. and D.W. Shipman.. 1980. The c o r r e c t n e s s o f c o n c u r r e n c y c o n t r o l mechanisms i n a s y s t e m f o r d i s t r i b u t e d d a t a b a s e s (SDD-1)..ACM T r a n s a c t i o n s on D a t a b a s e Systems 5 (1) : 52-68. B j o r k , L.A. 1973. R e c o v e r y P r o c . ACM Annual C o n f .  scenario Atlanta,  f o r a DB/DC s y s t e m . Ga: 142-146.  C h a m b e r l i n , D.D. and R.F..Boyce.. 1974.. SEQUEL: A s t r u c t u r e d E n g l i s h g u e r y l a n g u a g e . P r o c . ACM SIGFIDET Workshop. Ann A r b o r , M i c h i g a n . May: 249-264. CODASYL.. 1971. Data Base ACM, New York. A p r i l .  Task  Group R e p o r t . CODASYL, DBTG,  CODASYL Programming Language Committee. Development. C o n t r o l Data C o r p o r a t i o n . 60454000. .  1978  APL  1976.  Version  COBOL J o u r n a l  2 Reference  of  Manual  Date, C.J. 1977. An i n t r o d u c t i o n t o d a t a b a s e s y s t e m s . Second e d i t i o n . . A d d i s o n - W e s l e y P u b l i s h i n g Company. ISBN 0-20114456-5. D a v i e s , C.T. Proc..ACM  1973. R e c o v e r y s e m a n t i c s f o r a DB/DC A n n u a l C o n f . . A t l a n t a , Ga: 136-141.  system.  E n g l e s , R.W. 1971. An a n a l y s i s o f t h e A p r i l 1971 DBTG R e p o r t a p o s i t i o n paper p r e s e n t e d t o t h e Programming Language Committee by t h e IBM R e p r e s e n t a t i v e t o t h e D a t a Base Task  104  Group.  (Available  from  British  Computer  Society.)  E n g l e s , R.W. 1976. C u r r e n c y and c o n c u r r e n c y i n t h e COBOL Data Base F a c i l i t y . P r o c . . I F I P W o r k i n g C o n f e r e n c e on M o d e l l i n g i n Data B a s e Management S y s t e m s , J a n u a r y . Eswaran, K.D., J.N. G r a y , R.A. L o r i e , and I . L . T r a i g e r . 1976. The n o t i o n s o f c o n s i s t e n c y and p r e d i c a t e l o c k s i n a database system. C o m m u n i c a t i o n s o f t h e ACM 1 9 ( 1 1 ) : 624-633. G r a y , J.N., R.A. L o r i e , G.R. P u t z o l u , and I . L . T r a i g e r . 1976. G r a n u l a r i t y o f l o c k s and d e g r e e s o f c o n s i s t e n c y i n a s h a r e d d a t a b a s e . Pp. 695-723 i n P r o c . I F I P Working C o n f e r e n c e on M o d e l l i n g i n D a t a Base Management S y s t e m s . J a n u a r y . F r e u d e n s t a d t , Germany. Hawley, D.A., J . S . K n o w l e s , and E.E. T o z e r . . 1975. .Database c o n s i s t e n c y and the CODASYL DBTG p r o p o s a l s . Computer J o u r n a l . 18 ( 1 ) : 206-212. IBM  C o r p o r a t i o n . . I n f o r m a t i o n management s y s t e m / v i r t u a l s t o r a g e g e n e r a l i n f o r m a t i o n manual..GH20-1260.  Kedem, Z. and A. S i l b e r s c h a t z . 1979. . C o n t r o l l i n g c o n c u r r e n c y u s i n g l o c k i n g p r o t o c o l s ( p r e l i m i n a r y r e p o r t ) . Proc. IEEE F e b r u a r y : 274-285. Kwong, Y.S. and D. Wood. 1979. Concurrency i n B-trees, S-trees and T - t r e e s . Computer S c i e n c e T e c h n i c a l R e p o r t 79-CS-17, McMaster U n i v e r s i t y . Kwong, Y.S. and D. Wood. 1979. Approaches to concurrency t r e e s . (To a p p e a r i n P r o c . M a t h e m a t i c a l F o u n d a t i o n o f Computer S c i e n c e s , Rydzyna, Poland.) Kung, H.T. and C.H. P a p a d i m i t r i o u . 1979. of c o n c u r r e n c y c o n t r o l f o r d a t a b a s e s . C o n f . B o s t o n , Mass. May.  in  B-  An o p t i m a l i t y t h e o r y P r o c . 1979 SIGMOD  L i e n , Y.E. and P . J . .Weinberger. . 1978. Consistency, c o n c u r r e n c y , and c r a s h r e c o v e r y . ACM-SIGMOD C o n f e r e n c e . P a p a d i m i t r i o u , C.H. 1977.. The s e r i a l i z a b i l i t y d a t a b a s e u p d a t e s . J o u r n a l o f t h e ACM 2 6 ( 4 ) :  of c o n c u r r e n t 631-653.  R i e s , D.R. and M. S t o n e b r a k e r . 1977. Effects of locking g r a n u l a r i t y i n a d a t a b a s e management s y s t e m . ACM T r a n s a c t i o n s on D a t a b a s e Systems 2 (3): 233-246. R i e s , D.R. and M. S t o n e b r a k e r . 1979. Locking granularity r e v i s i t e d . . ACM T r a n s a c t i o n s on D a t a b a s e Systems 4 ( 2 ) : 227. . R o t h n i e , J.B. and N. Goodman. . 1 977. An o v e r v i e w o f t h e p r e l i m i n a r y d e s i g n of SDD-1: a s y s t e m of d i s t r i b u t e d  210-  105  d a t a b a s e s . P r o c . .1977 B e r k e l e y Workshop on D i s t r i b u t e d D a t a Management and Computer Networks. B e r k e l e y , C a l i f o r n i a . May. E o t h n i e , J . B . , P.A. B e r n s t e i n , S. F o x , N. Goodman, M. Hammer, T. A. , L a n d e r s , C. . E e e e v e , D. W. Shipman, and E. Wong.. 1980.. I n t r o d u c t i o n t o a system f o r d i s t r i b u t e d d a t a b a s e s (SDD-1).. ACM T r a n s a c t i o n s on D a t a b a s e Systems 5 ( 1 ) : 1-17. S c h l a g e t e r , G. 1978. P r o c e s s s y n c h r o n i z a t i o n i n d a t a b a s e s y s t e m s . ACM T r a n s a c t i o n s on D a t a b a s e Systems 3 ( 3 ) : 248-271. S i l b e r s c h a t z , A. And Z. Kedem. 1978. C o n s i s t e n c y i n h i e r a r c h i c a l d a t a b a s e s y s t e m s . ( A v a i l a b l e i n JACM.) Simon F r a s e r U n i v e r s i t y . 1978.. MTS/APL f i l e g u i d e . Computing C e n t e r .  system  user's  S t o n e b r a k e r , M., E . Wong, P. K r e p s , and G. H e l d . 1976. The d e s i g n and i m p l e m e n t a t i o n o f INGEES. ACM T r a n s a c t i o n s on D a t a b a s e Systems 1 ( 3 ) : 189-222. U n i v e r s i t y o f B r i t i s h Columbia Computing C e n t r e .  1976.  UBC f i l e s  University of B r i t i s h Centre.  1977.  UBC Commands,  Columbia  and d e v i c e s . Computing  U n i v e r s i t y of C a l g a r y . E d u c a t i o n a l data base system data base a d m i n i s t r a t o r ' s manual. Department o f Computer S e r v i c e s CSEM-009. U n i v e r s i t y of Toronto. 1975. E d u c a t i o n a l d a t a b a s e system m a n i p u l a t i o n f a c i l i t y u s e r ' s manual. Computer Systems E e s e a r c h Group. O c t o b e r .  data  U n i v e r s i t y of Toronto. 1975. E d u c a t i o n a l d a t a b a s e system base a d m i n i s t r a t o r ' s manual. Computer Systems E e s e a r c h Group. December.  data  Y a n n a k a k i s , M., C.H. P a p a d i m i t r i o u , and H.T. Kung. . 1979. L o c k i n g p o l i c i e s : s a f e t y and freedom from d e a d l o c k . P r o c . I E E E . F e b r u a r y : 286-297..  APPENDIX A:  EDBS OVERVIEW  Create • SA  I Create DBA List Databases Grant Access  Create Database List Database Descr.  Relational  Hierarchical QUERY  AND  J  Network  UPDATE FACILITIES  Maintain  I Destroy Database  Destroy DBA *  Figure 3  106  107  APPENDIX  B: EDES Commands and  Relational  System  Utilities  Hierarchical  System  Network  GET  GET  GET HOLD  GET NEXT  PUT  GET NEXT WITHIN  UPDATE  GET HOLD  STORE  DELETE  INSEBT  DELETE  REPLACE  INCLUDE  DELETE  REMOVE  UNIQUE  System  GET RECORD GET SET PABENT  GET HOLD  MODIFY CHANGE TO CURRENT  DBA  Utilities  CREATEDBA  DUMPLOG  DESTEOYDBA  ERASELOG  LISTDATABASES  MAINTAIN  CREATE  MAKEAVAILABLE  DESTROY  MAKUNAVAIL ABLE  GRANTACCESS  LISTACTIVEUSERS  108  APPENDIXC : EDBS FILE USAGE  Figure 4  109  APPENDIX D: I n t e r f a c e F i l e This  System D e s c r i p t i o n  appendix provides a d e s c r i p t i o n  functions  which c o m p r i s e  basically  two c a t e g o r i e s o f f u n c t i o n s which had t o be s i m u l a t e d .  First,  t h e CDC/APL f i l e  system f u n c t i o n s . category file  our i n t e r f a c e  o f t h e major  system  Of p a r t i c u l a r  referred  Our d e s c r i p t i o n  i n part a restatement  There a r e  S e c o n d , a number o f  In t h e f o l l o w i n g , each  briefly  t o t h e CDC APL V e r s i o n  details.  system.  importance i n the l a t e r  function i s described  system f u n c t i o n s a r e o n l y  is  functions.  i s t h e #FI f u n c t i o n .  system  file  in detail.  The  described.  The r e a d e r i s  2 Reference  of t h e simulated o f pages  simulated  simulated  Manual f o r f u r t h e r file  system f u n c t i o n s  10.8 t o 10.10 o f t h e CDC  Manual.  MTSCREATE: The function  'file-name  [ / o p t i o n s ]'MTSCREATE fnum  MTSCREATE f u n c t i o n s i m u l a t e s (FCREATE).  t h e CDC f i l e  MTSCREATE may be used t o c r e a t e a f i l e  specify  o p t i o n s about the type  of f i l e .  created  i t i s tied  number fnum.  t o the f i l e  may i n c l u d e S o r WR t o p e r m i t respectively, the  list  function  t o other  users.  the f i l e  Files  a r e a l w a y s i n t e r n a l I/O f o r m a t  •FILE2/DA  The l i s t  f o r read options created MTS l i n e  S WR*  11  (A f i l e named F I L E a s i t s number)  MTSCREATE 2  of options  or r e a d / w r i t e , specified in by t h e MTSCREATE files.  creation follow:  ' F I L E 1 ' MTSCREATE  and  When t h e f i l e i s  Any o t h e r  of o p t i o n s a r e i g n o r e d . .  Examples o f f i l e  create  1 with  11  (A f i l e named F I L E 2 p e r m i t t e d f o r RW t o others)  110  MTSDEL: MTSDEL fnum [ , rnum] The function fnum. that  MTSDEL f u n c t i o n s i m u l a t e s (FRDEL).  MTSDEL  position  record  d e l e t e s t h e r e c o r d rnum f r o m  I f t h e r e c o r d was a l r e a d y the f i l e  t h e CDC f i l e  changes)  absent,  nothing  delete file  i s done  (except  and nc e r r o r s r e s u l t .  MTSERASE: MTSERASE fnums The applied  a c t i o n o f t h e CDC f i l e  t o CDC d i r e c t  function.  All files  access  erase  files  specified  function  i s simulated  by t h e r i g h t  (FERASE)  when  by t h e MTSERASE  argument a r e  destroyed.  MTSFMMES: r e s u l t The  currently tied.  FNAMES f u n c t i o n . always  I.D.s  MTSFNAMES  MTSFNAMES f u n c t i o n r e t u r n s  I.D.s) o f f i l e s  is  <  13  a matrix  o f names  MTSFNAMES s i m u l a t e s  t h e CDC  The number o f c o l u m n s i n t h e m a t r i x  (i.e.,  three  less  than  with  a r e t h r e e c h a r a c t e r s s h o r t e r than  (and u s e r  returned  CDC b e c a u s e MTS CDC  user I . D . s ) .  user An  example f o l l o w s : MTSFNAMES SAMPLE 1 ALGEBRA *XXAR F I L E 1 MTSFNUM_S_: r e s u l t The for  tied  <  MTSFNUMS  MTSFNUMS f u n c t i o n r e t u r n s a v e c t o r o f numbers i n use files.  The o r d e r i s t h e same a s t h e o r d e r  names i n t h e r e s u l t FNUMS f u n c t i o n .  of f i l e  f r o m MTSFNAMES.. MTSNUMS s i m u l a t e s t h e CDC  111  MTSFTIE:  ' [ * a c c o u n t ] f i l e - n a m e [ / o p t i o n s ]' F T I E fnum  The  MTSFTIE f u n c t i o n s i m u l a t e s  (FTIE). file  having  given, one  MTSFTIE g i v e s  t h e i n d i c a t e d name.  the stored  used  MTSFTIE  file  for signing  provided  t h e number  i s ignored  by t h e MTSFTIE f u n c t i o n .  MTSFUNTIE  MTSFUNTIE file  If  rnum  that  than the  of o p t i o n s i f  Examples  using  (A u s e r t i e s one o f h i s own f i l e s )  MTSFTIE  8  (A u s e r t i e s a belonging to another user)  <  t h e CDC  a l l tied  FUNTIE.  that  t h e CDC  r i g h t argument  use MTSUNTIE MTSFNUMS. .  fnum as  rnum a s i t s r e c o r d  number.  an empty  FREAD  or s c a l e r  f o r which  having  the c u r r e n t  does n o t e x i s t ,  MTSREAD s i m u l a t e s  having  A l lfiles  rnum]  r e a d s from  record  i s not p r o v i d e d ,  record  files,  FREAD fnum [,  MTSREAD f u n c t i o n number  file  fnums  simulates  To u n t i e  MTSREAD: r e s u l t The  7  numbers a p p e a r i n t h e v e c t o r  untied..  file  (I.D.) i s  I.D. r a t h e r  The l i s t  stored  follow:  MTSFUNTIE:  its  t i e function  account  under t h a n  onto the system.  •*XXAR F I L E 1•  are  file  fnum t o t h e p r e v i o u s l y I f a user  i s sought  * F I L E 5 ' MTSFTIE  their  t h e CDC  the f i l e  record  number  numeric v e c t o r  function.  i s used.  If  i s returned.  112  MTSSTAT;  result  MTSSTAT provided returns having  <  FSTATUS fnum  simulates  a very  by t h e CDC f i l e  status  the l a r g e s t record fnum as i t s f i l e  small  subset  function  of the c a p a b i l i t i e s  (FSTATUS).  MTSSTAT  number c u r r e n t l y i n use by t h e f i l e  number.  I f the f i l e  i s empty -1 i s  returned.  MTSWEITE:  array  The  MTSWEITE fnum [,  MTSWEITE f u n c t i o n  having  fnum a s i t s number  record  number.  described  as t h e r e c o r d  ($"FI1,  file  system  file  operations.  a  The f o l l o w i n g  functions  #FI by  the current  t h e CDC FWEITE  describes  use t h e s y s t e m  record  function.  how t h e y  work: The CDC  f u n c t i o n #FI t o p e r f o r m a l l  F o r example, FCEEATE i s d e f i n e d  create..  Each f i l e  number a s t h e f i r s t  function  A #FI  as f o l l o w s :  1,B"  system  element  c a n a c t u a l l y be used  #FI  function c a l l s  i n the r i g h t  directly  should #FI  with  a r g u m e n t . . The  and i s used  directly  EDBS. The  references the  rnum a s i t s  number (1) f o l l o w i n g t h e #FI i n d i c a t e s t h a t  a file  unique  having  $ " F I 2 , $"FI3 and $"FI4)  "A FCEEATE B <1>  perform  argument on t h e f i l e  t h e i n t e r f a c e between EDBS and t h e f u n c t i o n s above.  The  its left  MTSWEITE s i m u l a t e s  $"FI f u n c t i o n s  accomplish  writes  I f rnum i s n o t p r o v i d e d ,  number i s u s e d . The  rnum]  $"FI f u n c t i o n s  simulate  t h e #FI f u n c t i o n .  t o #FI made by EDBS have been  appropriate  $"FI f u n c t i o n .  modified  All  to refer to  113  Our  interface f i l e  functions.. #TEAP.. MTSID  $"TRAP1  replaces  $"LIB1 s i m u l a t e s  and r e v e r s e  facilities  system  MTSID  f o r decoding  includes  t h e CDC  a number o f  error trapping  t h e CDC s y s t e m  function  (REVMTSID) f u n c t i o n s and e n c o d i n g  a user  other function,  #LIB.  replace account  The  EDBS number.  APPENDIX E : I n t e r f a c e F i l e  FUNCTION MTSCREATE MTSFTIE MTSUNTIE $"FI4 $"REVMTSID  VARIABLE FNAMES  <1> <2> <3> <4> <5> <6> <7> <8> <9> <10> <11> <12> <13> <14> <15> <16> <17> <18> <19> <20> <21> <22> <23> <24>  System  Functions  NAMES MTSDEL MTSFUNTIE MTSWRITE $"LIBDELETE $"TRAP1  MTSERASE MTSID $"FI1 $"LIBUPDATE  MTSFNAMES MTSREAD $"FI2  MTSFNUMS MTSSTAT $"FI3 $"LIB1  NAMES FNOMS  " A MTSCREATE B;FNAME;MSG;OPTIONS FNAME= (1+A$. •%•) $TAA $*a)a)a> CREATE F I L E CALLED FNAME 5)5)5) $> (0$EQ$EX3$TAMSG=FMTS 'CREATE •,FNAME)%CREATED MSG $>0 CREATED: OPTIONS= ( {$,FNAME) +1) $DRA $*5)5)5> UPDATE FILENAME LIST 25)5) $'* LIBUPDATE FN AM E $*a)5)5) I F SEMIPRIVATE PERMIT FOR READ TO OTHERS 5)5)5) $> ( ($, OPTIONS) $LTOPTIONS$. !S') %UPDATE $>(0$EQ$EX3$TAMSG=FMTS 'SHARE • , FNAME)#SHARED MSG $>0 $*5)S)5) I F WRITE OPTION PERMIT FOB WRITE TO OTHERS 5)5)5) SHARED:$>( {$ OPTIONS)$LTOPTIONS$.'W')%UPDATE $> (0$EQ$EX3$TAMSG=FMTS 'SHARE ',FNAME,' RW')%UPDATE MSG $>0 $*5)5)5) UPDATE FNAMES AND FNUMS 5)5)5) UPDATE: $> { ($ , FNAMES) $EQ0) % F I E S T FNAMES=FNAMES,<1> FNAME,( 1 6-$, FNAME) $ , ' ' $>TIE FIRST:FNAMES= 1 16 $,FNAME,(16-$,FNAME)$,• • TIE:FNUMS=FNUMS,B r  II  <1> <2> <3> <4> <5> <6> <7> <8> <9> <10> <11> <12> <13> <14> <15> <16> <17> <18> <19> <20>  " MTSDEL B;FNUM;RNUM;MSG;FNAME;M;DATA FNUM=1$TAB FN AME=,FNAMES<(FNUMS$EQFNUM)%$,$,FNUMS;> $*333 SET APL EXTERNAL FORMAT 335) MSG=* EXTERNAL FSETTYPE FNAME $*333 SET DIRECT ACCESS MODIFIER 335) #IO=0 M=32$,0 M<30>=1 MSG=M FSETMODS FNAME #10=1 $ > ( ( $ RNUM=1$DRB)$EQO)%SEQ $*333 FIND LINE NO..FOR DIRECT ACCESS WRITE 333 MSG=(RNUM*1000) FSETLINE FNAME SEQ:$> (0$EQ$EX3$TAMSG=' • FWRITE FNAME) %RESET MSG $>0 RESET: $*333 INCREMENT LINE POINTER 333 M S G = R N U M « FGETLINE FNAME MSG = (RNUM+1000) FSETLINE FNAME 1  r  ,  II  <1> <2> <3> <4> <5> <6> <7> <8> <9> <10> <11> <12> <13> <14>  " MTSERASE A;MSG;FNUM;FNAME;I I=,.1 $> (I$GT$ / , A) %0 FNUMf_1$TAI$TAA FNAME=,FNAMES<(FNUMS$EQFNUM) %$.$,FNUMS;> $*333 UNTIE F I L E S GIVEN BY A 333 MTSUNTIE FNUM $*333 DESTROY F I L E S GIVEN BY A 333 $>(0$EQ$EX3$TAMSG=FMTS 'DESTROY *,F NAME)%DONE MSG $>0 DONE:I=I+1 $*5)33 UPDATE FILENAME LIST 333 $"LIBDELETE FNAME $>2 II  <1> <2> <3> <4> <5> <6> <7> <8> <9> <10> <11>  " R=MTSFNAMES; I I=,1 E= 0 13 $,• • NEXT: $> (I$GT$ ,FNUMS) %Q $>(FNAMES<I;5>$EQ':')%ACC $*333 COMPOSE FNAME I F NO ACCOUNT NO. GIVEN 333 R=R,<1> • •,4$DR,FNAMES<I;> $>OUT $*333 COMPOSE FNAME I F ACCOUNT NO. GIVEN 333 ACC:R=R,<1> «3',(,FNAMES<I;$.4>)•,7$,5$DR,FNAMES<I;> O0T:I=I+1 $>NEXT II  116  " <1>  ii  BESULT=MTSFNUMS EE SULT=FNUM S  A MTSFTIE B;MSG;FNAME;STATUS <1> $*a)33> COMPOSE FNAME I F ACCOUNT NO. GIVEN a)a)a) <2> $> (A<1>$NE« a)') %NOACC <3> FN AM E=A< 2 3 4 5> , : • , ( ( (6$DEA) $NE • •) $. 1) $DB5$DKA <4> FNAME= (1+FNAME$. *%•) $TAFNAME <5> $*a)a)d) COMPOSE FNAME I F NO ACCOUNT NO. GIVEN a)a)a> <6> $>EEECHK <7> NOACC:FNAME= (1 + A$.'%')$TAA <8> EBBCHK:$>(B$EPFNUMS)%E1 <9> $*a)a)3 CHECK THAT F I L E PEEMITTED 3 3 3 <10> $> (0$EQ$EX3$TAMSG=FMTS ('CHKACC • , FNAME) INTO * STATUS ' ) %OK <11> MSG <12> $>0 <13> OK:$>(STATUS$EQO)%E2 <14> $*a>33 UPDATE FNUMS AND FNAMES 333 <15> $> {($,FNAMES)$EQO) % F I E S T <16> FNAMES=FNAMES,<1> FNAME,(16-$,FNAME)$ , ' • <17> $>TIE <18> FIRST:FNAMES= 1 16 $,FNAME, (16-$,FNAME)$,* • <19> TIE:FNUMS=FNUMS,B <20> $>0 <21> E 1 : « T I E NUMBEE IN USE' <22> $>0 <23> E 2 : ' F I L E NOT PEEMITTED' 11  1  II  MTSFUNTIE A;I $*333 UNTIE F I L E S GIVEN BY A 333 I=,1 $> (I$GT$, , A) JtO MTSUNTIE 1$TAI$TAA 1 = 1+1 $>3  <1> <2> <3> <4> <5>  <6> II  Z = MTSID $*333 THIS FUNCTION FINDS THE USEE ID 333 $*333 FOE THE CALLING ACCOUNT a)a)a) Z=,#AV<#IO+ (4$,256)$EN1$TA#AI>  <1> <2> <3> II  " <1> <2> <3> <4> <5> <6> <7> <8> <9> <10> <11> <12> <13> <14> <15> <16> <17> <18> <19> <20> <21> <22> <23> <24> <25>  RESULT-MTSRE&D E;FNUM;BNUM;MSG;FNAME;M;DATA FN UM=1$TAE FN AME = , FNAMES< (FNUMS $EQFNUM) %$.$,FNUMS;> $*333 SET APL INTEENAL FOEMAT 333 MSG='INTEENAL FSETTYPE FNAME $*333 SET DIEECT ACCESS MODIFIES 2)33 #10=0 M=32$,0 M<30>=1 MSG=M FSETMODS FNAME #10=1 $> ( ($,BNUM=1$DBB)$EQ0)%SEQ $*333 FIND LINE NO. FOB DIBECT ACCESS BEAD 333 MSG=(BNUM*1000) FSETLINE FNAME SEQ:$> (0$EQ$EX3$TAMSG='DAT A• FEEA D FNAME) %EESET $>(30$EQ$EX3$TAMSG) %NULL MSG $>0 NULL:DATA=$.0 $>UNLOCK BESET: $*333 INCEEMENT LINE POINTEE 333 MSG= BNUM' FGETLINE FNAME MSG= (BNUM+1000) FSETLINE FNAME $*333 UNLOCK IMPLICIT MTS LOCKING 333 EESULT=DATA 1  1  II  <1> <2> <3> <4> <5> <6> <7>  <1> <2> <3> <4> <5> <6> <7> <8>  " BESULT=MTSSTAT A;MSG;FNAME;LINE;FNUM $*333 FIND LAST LINE IN USE IN F I L E 333 FNAME= FNAMES<(FNUMS$EQA)%$.$,FNUMS;> MSG=FMTS •GETLST •,FNA ME INTO * LINE• $> (12$EQ$EX3$TAMSG) %EOF EESULT=,LINE/1000 $>0 EOF:RESULT-,1 f  it  » MTSUNTIE A;Y;FNAME;MSG $*333 UNTIE F I L E GIVEN BY A 333 $> ( (FNUMS$.A)$GT$,FNUMS)%EREOE FNAME=,FNAMES< (FNUMS$EQA) %$.$,FNUMS;> $*333 UPDATE FNUMS AND FNAMES 333 FNUMS=(Y= FNUMS$EPA)%FNUMS FN AMES=Y$C1FNAMES $>0 EBEOR:•ATTEMPTING TO UNTIE AN UNTIED F I L E * II  118  <1> <2> <3> <4> <5> <6> <7> <8> <9> <10> <11> <12> <13> <14> <15> <16> <17> <18> <19> <20>  " A MTSWEITE B;FNUM;RNUM;MSG;FNAME;M;DATA FN UM = 1 $ TAB FN AME = ,FNAM ES<(FNUMS$EQFNUM)%$.$,FNUMS;> $*333 SET APL INTERNAL FORMAT 333 M S G = « I N T E R N A L ' FSETTYPE FNAME $*333 SET DIRECT ACCESS MODIFIEE 333 #10=0 M=32$ 0 M<30>=1 MSG=M FSETMODS FNAME #10=1 $>({$,ENUM=1$DRB)$EQ0)%SEQ $*333 FIND LINE NO. FOR DIRECT ACCESS WRITE 333 MSG=(RNUM*1000) FSETLINE FNAME SEQ:$> (0$EQ$EX3$TAMSG=A FWRITE FNAME)%RESET MSG $>0 RESET: $*333 INCREMENT LINE POINTER 333 MSG= * RNUM FGETLINE FNAME MSG=(RNUM+1000) FSETLINE FNAME r  1  it  <1> <2> <3> <4> <5> <6> <7> <8> <9> <10> <1 1> <12> <13>  " A $"FI1 B;X X=1$TAB $*333 BRANCH TO FUNCTION GIVEN BY B 333 $> ( (X$EQ1) , (X$EQ2) , (X$EQ4) , (X$EQ9) , (X$EQ10) ) %L 1 L 2 , L4 , L 9 , L 1 • NOT VALID $"FI1 COMMAND' L1:A MTSCREATE 1$DRB $>0 L2:A MTSWRITE 1$DBB $>0 L4:MTSERASE A $>0 L9:MTSFUNTIE A $>0 L10:A MTSFTIE 1$DRB r  II  <1> <2> <3> <4> <5> <6> <7> <8> <9>  '» Z=$"FI2 B;X X=1$TAB $*333 EfiANCH TO FUNCTION GIVEN BY B 333 $> ( (X$EQ3) , (X$EQ7) , (X$EQ8) ) 5 5 1 3 ^ 7 ^ 8 'NOT VALID $"FI2 COMMAND' L3:Z = MT SREAD 1$DEB $>0 L7: Z=MTSFNAMES $>0 L8:Z=MTSFNUMS II  119  <1> <2>  " $"FI3 B $*333 CALL FUNCTION GIVEN BY B 333 MTSDEL 1$DRE II  <1> <2>  " Z=A $"FI4 B $*333 CALL FUNCTION GIVEN BY B 333 Z = MTSSTAT A II  " $"LIBDELETE FNAME;MSG;X <1> $*333 DELETE F I L E NAME FROM LIBNAMES 333 <2> MSG='INTERNAL* FSETTYPE 'LIBNAMES' <3> $>(0$EQ$EX3$TAMSG='X• FREAD 'LIBNAMES')%OK <4> MSG <5> $>OUT <6> OK:X={ (FNAME, (17-$,FNAME) $, • • ) 8 . $EQ$TEX) $C1 X <7> $*333 RESET RECORD NUMBER TO ONE 333 <8> MSG=FRELEASE •LIENAMES' <9> MSG='INTERNAL' FSETTYPE 'LIBNAMES' <10> $>(0$EQ$EX3$TAMSG=X FWRITE 'LIBNAMES')%OUT <11> MSG <12> OUT:MSG=FRELEASE 'LIBNAMES' II  <1> <2> <3> <4> <5> <6> <7> <8> <9> <10> <11> <12> <13> <14> <15>  " $"LIBUPDATE FNAME;STATUS; MSG ; X $*333 CHECK I F LIENAMES ALREADY CREATED 333 $> (0$EQ$EX3$TAMSG=FMTS ('CHKACC LIBNAMES') INTO 'STATUS')%RE $*333 CREATE LIBNAMES AND PERMIT FOR READ 333 MSG=FMTS 'CREATE LIENAMES MSG=FMTS 'SHAEE LIBNAMES' X= 0 17 $,' • $>WEITE BEAD:MSG='INTEEN AL' FSETTYPE 'LIENAMES' MSG='X» FEE AD 'LIENAMES' MSG=FEELEASE 'LIENAMES• $*333 UPDATE LIBNAMES 333 WEITE:X=X,<1> FNAME, (17-$,FNAME)$, • • MSG='INTEENAL' FSETTYPE 'LIBNAMES' MSG=X FWBITE 'LIENAMES' MSG=FBELEASE 'LIENAMES' 1  II  120  " Z=$"LIB1 LIBNO;STATUS;MSG;FNAME <1> $*333 THIS FUNCTION EETUENS A L I S T OF FILENAMES 333 <2> $*333 CONTAINED IN THE ACCOUNT GIVEN BY LIBNO 933 <3> $> (0$EQ$,LIBNO) %NOACC <4> FNAME=(1$DB5$TALIBNO),•:LIBNAMES' <5> $>NEXT <6> NOACC:FN AME='LIBNAMES• <7> NEXT:$>(0$EQ$EX3$TAMSG=FMTS{'CHKACC FNAME) INTO • S T A T U S ) % <8> Z= 0 17 $,• « <9> $>0 <10> READ:MSG='INTERNAL FSETTYPE FNAME <11> M S G = Z « FREAD FNAME <12> MSG=FRELEASE FNAME ,  1  ,  <1> <2> <3>  it z=$"MTSID L I S T $*333 THIS FUNCTION FINDS THE USER ID 333 $*a)33 FOR A L I S T OF USERS 333 Z=#AV<#IO + $TE(4$,256)$EN, LIST> E=$"EEVMTSID USEE $*333 THIS FUNCTION FINDS THE USEE ID 333 $*333 IN ENCODED FOEM FEOM CHAR REPN 333 E=256$DE (#AV$. USER) -#IO $"TRAP1 LABEL $*333 THIS FUNCTION DOES NOTHING..IT I S USED TO REMOVE 333 $*333 THE EEEOE TEAPPING F A C I L I T I E S PEOVIDED BY #TEAP 333  # FNAMES C $,$,$EQ 2; $,$EQ 0 16 # FNUMS N $,$,$EQ  1 ; $,$EQ 0  Tea  ALPHA ALPHABET AND ASSIGN BRACKETS BRANCH CAP CIRCULAR FUNCTIONS COLON COMMA(CATENATION) COMMENT COMPRESSION COlfPRESSIONll~\ CUP DECODE DEFINITION{DEL) DELTA DELTAU DIERESIS DIGITS DIMENSION DIVIDE DROP ENCODE EQUAL ESCAPE EXPANSION EXPANSION(1) EXPONENTIATION EXECUTE FACTORIAL FORMAT GRADE DOWN GRADE UP GREATER OR EQUAL GREATER THAN INDEX  a A--z A-•z A  n s l i t e r a t i oji_T_a b l e  $AL A-Z  -  a-z  A- Z  &  -<-  [  ]  <  >  ->  $> $G0  n  $CA  o  $$  j » A  :  $CI  $* $co  %  X V  $DE $BA  A  .. 0 -•9  P 4+ T  w  \ \  * t  $C1  $cu II  4 > >  < ©  r  MAXIMUM MEMBERSHIP MINIMUM . MINUS MODULUS MULTIPLY  €  L 1 X  $"  $U" $DS 0-9 $, $RH / $DR $D0  V  ~ o  6J  V  PARENTHESES • PERIOD PLUS QUAD QUAD - DIVIDE QUOTE - QUAD QUOTE  $EN $RP $EQ $0UT  $%  $MA $CE $EP $ME $MI $FL $1  *  $TN l $NR $N0 $NE  $: $0M I $0R  ( )  (  +  +  •  # $/ $#  mi 9  • RANDOM ROTATION ROTATIONS RSUB  $X1 0 $EX  $LE $LT $-. $L" $@ $L0 $LN  $N& -  OMEGA OR  )  i  ?  $R0 $RV ©  $R1  $RS  $FA SEMICOLON SUB I SYSTEM  V  Y  <  NAND NEGATION NOR NOT NOT EQUAL NULL  9  / / u  A  $PI  LESS OR EQUAL LESS THAN LINE FEED LOCKED FUNCTION LOGARITHM  $GD $GU $GE $GT $. $10  TAKE TRANSPOSITION $IN  UNDERSCORE  • >.  '  y •  cr:"'  $SU $IB $SY  +  $TA $UP $TR  -  $UN  From UBC  APL  

Cite

Citation Scheme:

    

Usage Statistics

Country Views Downloads
France 6 0
China 5 23
United States 4 0
Saudi Arabia 2 0
Turkey 2 0
Germany 1 0
Canada 1 0
City Views Downloads
Unknown 10 0
Beijing 4 1
Ashburn 3 0
Fuzhou 1 0
Redwood City 1 0
Vancouver 1 0
Roubaix 1 0

{[{ mDataHeader[type] }]} {[{ month[type] }]} {[{ tData[type] }]}
Download Stats

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0051814/manifest

Comment

Related Items