Melvina H. (Melvina Hani) Tarazi.

Object sharing in a multi-user hypertext system online

. (page 1 of 8)
Online LibraryMelvina H. (Melvina Hani) TaraziObject sharing in a multi-user hypertext system → online text (page 1 of 8)
Font size
QR-code for this ebook

V^'^^'^ o' T^^


no .3131-


[DEC 20 1990 J




M.S. Thesis

Melvina H. Tarazi

CCSTR ^ 101





Massachusetts Institute of Technology

Sloan School of Management

Cambridge, Massachusetts


M.S. Thesis

Melvina H. Tarazi

CCS TR^ 101 ^^^f^3l5^


\ ^l^"




McK-ma H Tarazi

S P Co'-r-uie: Sc:e-ct and Engineering

Massa;.". jsens insurjte of Technoiog>







a; ihs


Ccp>Tigh: (ci 1985 - Me!'. -j-.a H Tarazi

Tr.t 2_'_-.r: nereby grar/.s MTI perrrussior. to reproduce and to distnbute
cones of iT-s ihes:s document in whole or v. rar..

Simanirc of AuLhor

E>eparmcnt of Eiectncal Engineenng and Computer Science

J'onc 20. 1989

Cenified b%

\M^jgy% mI—

Professor Tnomas W. Malone
Tnesis Supcr^•lsor

Accepted b)

Professor .Ajiniir C. Srmin
Chairman, Comrruoee on Graduaxe Students



MeivLTiE K Tarazi

Subrrjne-d tc the of E!emcal EngLneerinc and Computer

Science or. J jr.: 2C. ]9^'^ ir. rar.ia] fj-I:TLimen: of the requiremen*^ for the

decT&e of Masier of Science.


Obieci-onenied da-^ba^es 2.-ic r.\-penex! sysier-.s are emergir.g ir. response :o a demand by
appiiactior, developers for Lncreased. less sn - crkired modelir.g power m database systems.
Such sy5;err.5 succeed l'-. prcMdir.e the necessary tools and facmues for building
coopera::\e v.ork arr'.ications bu: are luTuted ui providing the appropnate object sharing

'V^'e propose to adcL'^ss the object sharj^g requirements for one such system - Obiec: Lens
Object Ler.b ir.:erra-.e> fearjres z: r.;.T^r.ex: system.s. object-oriented systems and ruie-
based agents.

We evaluate various approaches tc object sharing (includL-.g message passing, centralized
object server and dismr^ted objec: servers and various scnemes for concurrency conrrol
and update propagation (lockiLng. timestampung > with respect to the charaaenstics desired
m Object Lens (e g.. speciaLzatior hierarchy, user-mterface. object linking, version control
and combination of long Lnteract;\e transactions and short automatic ransacuons).

We propose a nev. scheme for ■j'jtiating object sharing through the exchange of electronic
mail messages. Object protecticr. is achieved by a hybnd scheme oi access control lists and
capability systems.

Analysis of the transacuons in Object Lens reveals rwo sets of transactions; (1) interactive
transactions that require relatively weak consistency requirements and relatively flexible
concurrency control, ^.d. ;I; automate transactions that require stna concurrency control
requirements. Vv"e propose a hybnd locking and version control concurrency control
scheme that accomodates the two types of transacuons.

Thesis Superv'isor: Profes. or Thomas W. Malone

Title: Panck J McGovem Professor of Inform.aaon Systems


To My Parents


I vi.o_id Il^s tc tharik my thesis super\isor. Professor Tnomas MaJone. for his ir.s:gr.:.
guidance, and suppon His ide^. o?ser\'aao.i5, and suggesuons have deeply contributed to
the success of mis uo.-i..

I V. culd als: iixe to 'S.zr^. Nl: Kf % l-. Crowston for reading several drar.s cf iiis vk'ork.
His sugges:;?r.s. cnucues ar.d comments v.ere exremeiy helpful

M> parents. Reine and Kar„. deserve more than I can express for being nere when I
needed ne— . ar.c for ell -jr.^s .:.r. affecrion. guidance and encouragemen; throughou; my
life. Ma> 'j-js i-.esis be i. rir..i^ c:~.pensation to them for beLng away from home

Special thanks go to m.> bro'-her. Ram^i. for listening to m> gnpes and complaints
throughou: m.> s:a> a: Ml 7

Fmall) . I uould like to acknowledge Ibrahim Saad, Nazhiri Zarghamec, Ala Alry^es.
Emar. Hashem and Ahjnad Tabari for their constant friendship throughout my s'^ay ai M J.T.

Table of Contents

Abstract 2

Dedication 3

AcknowiedgemenLs 4

Table of Contents 5

List of Figures 7

List of Tables 8

1. Introduction 9

1.1 Object Sharing in Object-Onented Databases and H\-pcncxt Systems 10

1.2 The Proposed Objea Sharing Scheme 1 1

1.3 Objec: Lens 11

1 .4 Thesis Afjproach 1 3

1.5 Thesis Oauine 14

2. Architectures for Object Sharing 15

2.1 Message Based Object Sharing 17

2.1.1 Advantages of .Approach P

2.1.2 Disad\an;ages o: Approach 18

2.2 Cenc-alized Object Shanng 18

2.2.1 Adsantages of .Apjproach 19

2.2.2 Disadvantages of Approach 20

2.2.3 Improved Performance using Caching 20

2.2.4 Lmpicmentanon of Ccntrai Data Ser-er 23 Central Database Sever 23 CentraJ Objea Sever 24

2.3 Distributed Object Shanng 25

2.3.1 Ad\antagcs of Approach 26

2.3.2 Disadvantages of Approach 26

2.3.3 Imolcmcntauon of a Distributed Data Server 28 Distributed Objea Server 29 Objea Server and Manager ai each Workstailon 32 E>istnbuted Relanonal Database Systems 33

3. Object Sharing Features in a Distributed Environment 35

3.1 Replication 35

3.2 Consistency and Update Propagation 36

3.3 Concurrency Control 37

3.3.1 Synchronization Techniques Based on Two-Phase Locking 40 Basic 2PL Implcmentanon 40

3.3. 1 .2 Pnmarv Copy 2PL 41 Voting 2PL 41 Centralized 2PL 42 Granulann, of Locking 42 Deadlock betecuon 42

3.3.2 S>Tichroruzauon Techniques Based on Timestamp Ordering 44


3.3 2 ; Basi: TLTiestamp Ordenrc a^

3,3.2 2 MultiN ersior. Tunes'.arr.p Orderj^z ^5 Conser^atlve Tunesiamr Oraenng 46

3.3.3 S\T.:rjor.:zuUor. Techniques Bas&d on Qptimisnc Cor.roi 4b

3 3.3.; Ma'cr.r\ Cons-er.s'-!; 46

3 3.3 2 Dismbuiec Cenificaucn 48

3.3.- Ccrnz;a-~-^on cf the Tnree MeihcKJologies 4f

3.3.5 OLher ConcurrcncN Control Schemes 49

3.4 Secur.p> and Protecuor. 49

3.4.1 Capabi]ir\ Sys'^rr.s 50

3.4.2 .Access Conro! List System 50

4. Literature Surve% 52

4.1 Distributed Reiat;ona; Database Systems 52

4.2 ODiec:-Oner.ted DataDS-se Systems 55

4.3 Mui-j-use: H\7>ertext Systems 59

5. Object Lens Re\isiled 64

5.1 Objec: Lens as a Hv-penex! S\-s:em 64

5.2 Objec: Lens as an ODjeci-Onented Database System 65

5.3 Obtec: Lens Specific Features 65

5 4 Using Object Len^ 66

5.5 Objer. Lens Axchitecrurs 69

5.6 An example 70

6. Multi-user Object Lens 72

6.1 Early Desipr. Decisions '"3

6.2 TemiLTolop 74

6.3 ObieriS in Distnbuted Obiect Lens 75

6.3.1 Shared vs. Personal Obieas 75

6.3.2 PnNate \s Public Objects 76

6.3.3 Local vs. Remote Objects 77

6 4 Creation of a Shared Object 77

6.5 Deletion of a Snared Object 81

6.6 Protection cf a Shared Oc^^?:: 81
6.'' Modification of a Shared Objea 85

6.'.1 Transactions in Object Lens 87 Interaaive transacuons 88

6.7. L2 Automatic Transacpons 90

6.7.2 Concurrency Control ^ 92 Time-St^mp Ordering 92 Optirmsuc Concurrency 93 Two-Phase Locking 94 Version Control 96 Proposed S>Tichroni2ation Technique: Hybrid of Locking and 97

7. Conclusion 106

7.1 Summan- of Work 106

7.2 The Proposed Distributed Object Lens 1 1 1

7.3 Direcuon of Future Vvork 113

List of Figures

Figure 2-1: Ccr.ralized Orjec: Server 19

Figure 2-2: Dismbuied Object Scr\er 29

Figure 2-3: Objec: Ser^■cr and Manager ai each Wortcstaiion 33

Figure 2-4: Distributed Relauonai Database 3-i

Figure 3-1: Example of Conflias in transarjons 39

Figure 3-2: Deadlock Siruation 41

Figure 3-3: Wait -for Graph 45

Figure 5-1: Person object in Object Lens 67

Figure 5-2: Aichitecrure of Object Lens 69

Figure 6-1: Object DefiniDons 75

Figure 6-2: Two-user Dismbuted Object Lens 76

Figure 6-3: System W;de L'ruque Object ID ''9

Figure 6-4: Interactjve Transacnons 88

Figure 6-5: Rule execunon transacuons 91

Figure 6-6: L-.terleaving of Rules 92

Figure 6-7: Resoi'. L".g Modif>-.Modif\- Conflict using Hybnd Im.plementauon 99

Figure 6-8: Resolving a Rcad-Modif\' Conflict using the Hybnd 100


Figure 6-9: Rule Execution Deadlock 101

Figure 7-1: Distnbuted Ooject Lens 111

List of Tables

Table 4-1; Dis-j-.ruiec Database Featjres

Tablt 4-11: Fearures of ODier:-Oner.:ec Dauiascs

Table 4-III: H\-?er.ex; Features


Chapter 1

Conventional record-onented rclauonal daxabases are rescricted in the i^-id of mformanor.
they car. manage. The\ proMce da;a modeiing and cransacuon management capabii:i:c>
thai are wcli suited to business daia processing but which are not adequate for compuier-

supponed coopera:;Ne \«-ork appucations Sjch L-.creasingI> important apphcanons include
ccmputer-ajded desirr.. sofrAare developmen:. documema:ion authonng, and anif.cial
intelligence knov. ledge bases. Tnese applicauons are T.teracnve l-. narjre and deal wi±
Lmstructured objects and comp:ex relauonships among daia, people and scned'ules.

Object-oriented databases and hvper.ext systems anempt to provide the platform to support
the semantic and data models requL'ed for these applicauons. Object Lcjis [Lai 88. Maione
89] IS one such system. It integrates fearurcs of hvTxrtext and objea-onented system.s to
provide a system that may be used to v^xite specific appLicanons for retnevmg and browsing
complex information such as meeting scheduling, project management and document

However, the current implemcmauon of Object Lens fails to suppon a key fearure of
cooperative applications; Object Sharing. Object Lens is currently a single-user system.
Our goal is to propose an object sharing scheme that accommodates the key characteristics
of Object Lens (long interactive transactions combined with short rule-based transactions,
complex objeas, naive users, and version maintenance).


1.1 Object Sharing in Object-Oriented Databases and Hypertext Svstems

Object ar.c ir.fomanor. sharjig s-. orjsc.-onented daubases and h>-pcncx; systems implies:

• Multiple jser.- snc-l:: dc airie ;c access documents and destrr.s created :?\ oihe:

• CoUaboratL-.e u?e:s should be able to viev. modi5iCaiions made tc anv cf Lbe
shared docjmer.t^ c: desirns (update p:opagat;or. ,

• D^'fere-.". useri- uorkir.: ccr.currer.'jy should not be able to mterfere each
others work (.concurrenc> conirol;.

To surpor. ob'ect shar_-.c these systems need tc have a concurrency control scheme, an
update propagator, sc.-.err.e and ar. object protection scheme. Unforronately object-oncmed
databases and r.-.-ptr.tx: s\stem> car. not\ adopt the concurrenc\ conrrol schemes
(such as locidng and timestampmg ■ and update propagation schemes proposed and
implemented fcr dtsr-.butec databases The major problem^s are the different narure of the
transactions Ti^nc \s shon, and the dif'^'"rnt nature of Lhe objects (complex vs. simple)
supported b> these s> stems anc traditional database systems. Hov.e\er these schemes can
be used as the basis for m.ore adequate schemes for object-onented databases and hv-pertext

Many object-onented database? prototypes [Purdy 87. Fishman 8". Homick 87] adopt
variations of locking for concurrency control. Some systems use a checkin-checkout
protocol to disallcv. m.Jttple users from accessing an object concurrently. Existing
distributed h\-pcnext systems use either locking or version control to resolve possible
conflicts from, concurrent users. Most of these systems do not support replication (multiple
copies of an obiect; or version maintenance.


1.2 The Proposed Object Sharing Scheme

V,e a-'fjc thai ihc cradiuona] concurrency concrol schemes as v^eli as ihcLj vananis
proposed for obiect-onenisd databases are not adequate for systerr^s v.hert (I use:
fnendliness is of major imponance, and (2) modificanon may be made to the object
nteractne!) o: automatically.

User fnendliness implies that (ai redoing user performed modificaiions to an object is
intolerable. Cb'i disallowing users to access objects for long pcnods oi iimc is again

We propose a concurrency control scheme thai is a hybrid of locking and version control.
This scheme makes no restncnons on replication, i.e.. objects m.ay be repLicaied and the
scheme would sell be applicable. It also accommodates the existence of different versions
of an object.

We feel that this scheme is suitable for object-onented and hypenext applications that
emphasize user friendliness and that combine interactive modiiicauons through editing of
an object form and automate modifications through the execution of ruie-bastd

1.3 Object Lens

Objea Lens is an mtegraied (hypertext, object-oriented daiabase, rule-based) environment
for developing coopcraiive work applications. It combines the fomial representation of
knowledge (using strucrures such as frames, inheritance networks and production rules) in
knowledge-based systems with the informal representation of infomiation (unstructure text
or graphics) in hypenext systems to present a scmiformal middleground. Object Lens adds
scmanuc structure to hypenext nodes that allows the ease of summanzanon of objea


ccr.:e.-.:> anc rs.a:;or.>r.:r> ar.c 2u:?rr.a:;: search ar.d n-.ampjlatior. of a coliecjor, of
objerts I: r-.a> ^e LS-rc :? de^e.?r sr>er:f;c applicanor.s lo: L'lformatior. shanr.c. rer-.f-L".:
a.-:"' brrv. 5L-.L cf ccmr'.ex irj'rr-r.a:!??.. meet'-nc schedding. projec: management and
documeniatior. de\ (r:>T>er.ex: .. by including CTpiici: knowledge on various
objects such as difiertr:. —.essaze types, pecp'.e. task, mcedngs. produr^ and companies.

Tne basic primitives a\ ailabie lo die programjner to build his applicauons are:

1. Facilities i?: creatine object instances and object types Lirough a tem.plate-
basec jser interlace -

2- Facilities tc modi-f> objects by editLte the window display corresponding tc
the object

3. Facilities tr create r_e-t:2sed agents 'Jiat automaucaliy process Lnfomianon
on behalf cf the user.

4. Facilities tc collect objects toge-ner into folders. The folders m.a> be
autom.aticall;. maintained by an agent.

Featti'''*^ C*^ ar' c*e"" ^T r c* O'^'er* I_en^

We feel that tne follcv. j-.g charactenst^cs of Object Lens liighly in£uencc our choice of an
object sharjig scheme

• Naive Users Orject Lens is geared toward non-programjming users. Tms
makes user-ir.tsrt'ace a m.ajor component of the system.. Tne uscr-intenace
model u'iiuences what aspects of object sharing air exposed to the user.

• Combination of .>\utomatic ancT Interactive Modifications of Objects

Objects may ei'jier be m.odtfied automancally by "rule-based agents" or

interactively by a user edimg a display wLndow corresponding to the object.

• \ersJon .Maintenance As a tool for unplemcntL-.g coopcradvc work
applicauons, Ob'ect Lens shodd supp>on the Maintenance of different versions
of objects.

D:s?:bu:ed Ob'?:: Lgr.s

Dismbuted Object Lens should suppon object sharjig bcnveen various users on the
ncrwork. 1: should suppon locanon rransparency, rephcauon traiispar;r.c\ . concurrenc>
trar.sparcncv' and possibly access transparency Users any where in :he ncrwork sho'uJd be
able to reference and dereference objecis located elsewhere in the nerwork. It should
provide a mechanism for object protecuon. It sho'uld guard against or resolve possible
conflicts that anse because of concurrent access tc ar. object by a number of users.

1.4 Thesis Approach

In this thesis, our main concern 15 exp'.onng the different issues mvohed in object sharing
and the possible solutions to these issues. We are concerned with sharjig object
"instances" in Object Lens. V.'e v.-ii assume all users have the same object hierarchies and
object r\-pc defjiitions, i.e. the PERSON objec: universally means the same Lhuig. We will
not be concemed with object type coercion. [Lee 88] explores the various ways of doing
type translation.

We explore a large number of dismbuted systems (distributed relational daiabases,
distributed h\pcnext systems and distributed object-oriented systems) to examine how
objea sharing is achieved. Most of these systems are prototypes and exjxnmental. Our
emphasis is on Lhe architecture configuration of the distributed systems (centralized or
distributed), the concurrency control schemes used, the protection schemes used and the
upxiaie propagation schemes adopted.

We specify the requirements and fearures of Distributed Object Lens and then study the

suitability of the various techniques for the Object Lens environment.

\^e fL^.a^i) S' the Lradeoffs betueer. the difieren; techr.iqjes ir. the cor.:t>.: of
Obiec: Lens ar.c recommend the most appropriate aesigr, for Distributed Obiec: Lens.

1.5 Thesis Outline

Chapter 2 examines the var,o-js arch:tecnires for objea sharing in a distributed environmien:
in the frameuork of the SerNer-Chen: Model.

Chapter 3 descnDe> vanou> features of a dismbuted system-. I; surveys the vanous
aJgcr/Jrris and schemes to acme\Lng object sharing in a distributed envuonmen:. The
reieN ar.: fearjres are conc-rrenc;. conrrol. update propagation and protection.

Chap'^r -i preser.-.s a bterar^re s'jr%e> of various distributed systems from relarional
databases to objec:-onentec datar^ises to h\penext systems. Tne emphasis m the surve\ is
on the conc'jrrenc;. conrro! adopted, the propagation methods useJ and the
version control schemes explored.

Chapter 5 describes the fear^res and characteristics of Object Lens.

Chapter 6 describes the requirements for Distributed Obiect Lens. It descnbes object
shanng and protection in the context of the Object Lens envTronment. It defines the
possible transactions in Objea Lens and accordmgly examines the different techniques for
concurrency control describing the tradeoffs. A hybrid scherrie best suitable for Distributed
Object Lens is proposed.

Chapter 7 summarizes the key tradeoffs between the various choices and schemes and then
presents Lhe best appropriate approach for Distributed Object Lens.


Chapter 2
Architectures for Object Sharing

Users of centralized systems such as maLiframes are accustomed with, the idea of being able
to share da*^ and objects w-ith oLher users of the system. With the ad\ent of personal
computers, workstaiions and nerworts, Lhe essential schemes and algorithms to suppon
fcamres of object shanng needed to 'c>e revised to v».ork ir. such dismbuted environments

The essential features to object sharing in a distributed system are:

1. Allow muluple users a: various sues tc access objects created b\ any one user
in lhe system (Shared Access i. The access allowed to these objects may
differ from one user to another {Read, Wnte. Delete ) CProtection').

2. Multiple copies of an object may exist in the system. The system need to
ensure that all copies of the object are consistent (i.e., the same") at any point
in time. Consistency is achieved by propagating changes made to one copy of
Lhe objea to all other copies (UpHJate Propagaiion).

3 Perrrut users to access object in a multi-programmed fashion while preserving
the illusion that the user is executing on a dedicated system. To attain this
goal, the system should prevent modifications made by one user from
interfering with reads or updates performed by another (Concurrency
Control). The concurrency control problem is exacerbated in a distributed
system because: (a) users may simultaneously access objects stored a: many
different sites in a distributed system and (b) a concurrency control
mechanism ai one site cannot mstantaneously know about interaction at
another sue.


Tne.T aj-f three approache;; ic cb;ec: sharing l". a dismbuted environmer.: Tr.? three
approacnes are :Tie5sace-ba5ed, centraiizec shared object space and distributed snared
object space \^'e focus oii: anention or the locauon and maintenance of shared obiects
V.'t assume tr.i- perscni! object> are located a: the local site for pjcrsonal use only.

A message-based approach suggests Lha: object sharing could be done through the exchange
of specialized electronic mail messages. To a large extent in distributed systems
information sharing is done thjough the use of electronic mail. The suggestion is that this
could be extended to incorporate exchange and sharing of objects.

Tne cenral_zed approach suggests Lhat shared objects be located at a central sue ir. the
nerworx. Lniv;dual v-ori^staticns nttd to direct shared object access to the centra] sue.
Tr.2S approach is h:gbJ> dependent on the availability of the central site.

The distributed approach suggests that shared objects be distributed at different sites m the
nerw.o:k Users at different sues snouid 'oe able to access objects located at each sue.

Vv'e present the centralized and distributed approach to objea sharing in framework of a
Serv'er-Cltent Model The ser\'er provides the required object m.anagement and objects.
The client is locate at each woritstation to direct object requests. In the centralized
approach, one object server exists in the distributed system. Object caches may be provided
a: the client sue to improve object access. In the distributed approach several objea servers
exist Tnesc may be dedicated machines as in the central approach, in which case object
caches ai the client workstation may improve performance. Another option is to locate both
the scr\'er and the client processes at the workstation. This eliminates the need for a cache.

We examine in this chapter the various possible implementations of each of these schemes
in the context of an object-oriented, knowledge -based, hypertext systems similar to Object
Lens. O'ur sur\e\ is a SNTithesis of ^preaches adopted by different systems. The major
fearures to keep in mind about these systems arc:

• Complix and scrru-s3'jc:ured objects.

• Maiupulanor. ofobiecis perr'ormed ihrough rjie execuuon or use: inie:aci;or

• Triggers :hai activaic processes uhen stored objects are modified.

• A rr.ixtiire of long ar.d shor. irar.sac'.ions

Tne next chapter is reser.ed to cxammng vanojs aigonthLTis and schemes p'c>posed for
concurrency control, up>da:c propaganon and protection. Chapter 4 presents a survey of
dismbuted systems indjcanng v. hat object sharing approach they use, and '-he concurrency
control and update propagation schemes adopted

2.1 Message Based Object Sharing

This approach suggests that objects are shared ber*een different users by embedding them
in electromc m.ail messages that are then mailed through the ner*'ork. Tne objects could be
either literally embedded into the message or embedded li link form. The first method
requires that the receiving end extraa the object descnpuon and the unique objea identifier
suprphed by the underlying system, and buCd a local copy of the object with the appropnaic
unique object id. The second method implies that Lhe sender insens only a reference in the
message tc the objea he uishes to share. It is up to the receiving end to dereference the
objea by explicitly asking for ii if decrr»ed useful. The question is once the objea is
mailed, who 15 responsible for maintaining consistency of the different objea copies.
Seoion 4.3 gives a clearer account of this method.

2.1.1 Advantages or Approach

T7)e advantages of the message-based approach are the following:

• Fits well with distributed culture


Fo: sys-^m? C-.i: are ee2_-ec -.ruardv na:%e users a-nc L-a: make extensr.e use of messages to
share L"jrrma:.or.. u?L-g m.esiages :c sr.are objects seem.s tc be a narura^ evoiuuon.
Moreover. na:\ e users may fee' more comfonible wuh explicit (exposed shanng of objects
•L-har. V.VJ: c-ar. sparer,: snaTiT.t

2.1.2 Disadvantages of Approach

The disadvar.tages of the messagr-based approach are the following:
• Lirr^ted tc L^jna-.i-.g object shanng

Limited 'c :r.::iar.ri ^ ~ ec' shs'':r£

Tnis approach rr.^irl) focuses or. Liitiating object shanng. i.e., making an objea accessible
to omers 1: does nc: address the maintenance of the shared objea. Once there are several
copies cf ihe oDjec; a; CLfr'eren: sites, the problem arises of maintaining and updatr.g these
objects Tr^^ evol'-es l-.:: me i?— hutec approach to object sharing

2.2 Centralized Object Sharing

This approach dictates tha: 2II utformauon (objects) deemed sharabie. (i.e.. accessible by

1 3 4 5 6 7 8

Online LibraryMelvina H. (Melvina Hani) TaraziObject sharing in a multi-user hypertext system → online text (page 1 of 8)