49
tomanageifchangemanagementispartofasystemmodel.Undofacilitiescanremove
changesthatpropagateinanundesirableway,andqueryfacilitiescanhelpausertofind
thosechangesthataffectaproblematicregionoftheshareddata.Thenotionofdynamic
changeismoreinclusivethaninsertanddelete(andevenmoveandcopy).Foritsgenerali-
zations,thenotionoffrozenchangesisessentiallyuselessforanythingmorethanversion-
completeness.
ForsymmetryandcompletenessIalsocategorizefrozenversionsoftheexamplesofdy-
namicoperationsinthesamewayastheirdynamicversions.Onereasonisthatitissome-
timesnecessarytosimulatetheeffectsofdynamicoperationsinasystemthatonlyhasdi-
rectsupportforfrozenoperations.Forinstance,asmartclientofarepositorysupporting
onlyfrozenoperationscouldsupportdynamicoperationsbyannotatingtherepository’sfro-
zenoperationswiththedynamicoperationsfromwhichtheyarefrozen.Theclientcould
performmergesandotheroperationsintermsoftheirdynamicdefinitionsonrequest,but
onlythefrozenoperationswouldbestoredontheserverandavailabletoothers.Suchaso-
lutionisnotchange-completeontheserverside,butcanbechange-completeattheclient
side.Therearepracticalobstaclestosuchastrategy,asalargenumberofstaticoperations
maybeneededtostaticallyrecordtheeffectsofadynamicoperation.
ContentDependent
Content
Independent
Permutational

LimitedScope GlobalScope
Static
Operations
Insert,Delete
[essential]
FrozenMove,FrozenCopy,
FrozenTranspose
[usefultooptimizespacein
version-completesystems]
FrozenSort,FrozenFilter
[rarelyuseful,evenfor
version-completeness]
FrozenGlobalChange,Fro-
zenSpellingCorrection
[veryrarelyuseful,evenfor
version-completeness]
Dynamic
Operations
Multi-context
Insert,Multi-
contextdelete
[essential]
Move,Clone/Copy,Transpose
[widelyusedineditingsys-
tems]
Sort,Filter(arbitrarylocal
constraints)
[notcommonlyprovided]
GlobalChange,SpellingVali-
dation(arbitraryglobal
constraints)
[notcommonlyprovided]
T T T Ta a a ab b b b lll le e e e 2222....1111:::: TTTTaaaaxxxxoooonnnnoooommmmyyyy ooooffff ooooppppeeeerrrraaaattttiiiioooonnnnssss
50
Perhapsthemostcriticalfacttonoticeisthatthefrozenvariationsofdynamicopera-
tionsarenotactuallyuseful.Thereissomesmallutilityinfrozenmoveandcopy,butfor
morecomplexoperations,thefrozenversionsarenotveryinteresting.Furthermore,unless
youconsiderdynamicoperations,allthefrozenoperationscanbesimulatedbyappropriate
compositionsofsimpleinsertionanddeletionoperations.Evenmoveandcopyonlychange
thespaceefficiencyofhistories,buthavenoactualeffectontheexpressivepowerofthose
histories.Andofcourse,aswejustnoted,whileversion-completenessissatisfiedbyanyset
offrozenoperations,change-completenessisonlyavailablewhendynamicoperationscanbe
represented.
2.6 Typesofdynamicoperation
Fortheforegoingreasons,differentiationisreallyonlyfoundinthedynamicoperations.
Howeverthereareanumberofinterestingdistinctionswithinthedynamicoperations,and
theseaffectthepotentialconflictsbetweenoperations.Thedistinctionsbetweencontent-
independent,permutationalandcontent-dependentoperationsseparatedthembytheextent
towhichtheydependontheactualcontentofthedatathattheyaffect.
Contentindependentoperationshaveaneffectthatisalwaysthesame,whateverthe
contentsofthesequenceare.Insertanddeletearenoteditingoperationswhoseopera-
tioninanysensedependsontheactualdatainthesequence;deletionsarenotcondi-
tionalonthestateoftheregionslatedfordestruction,norareinsertionsdependenton
thecontentsneartheinsertionpoint.
Permutationaloperationslikemoveandcopy(sometimescalledclone)rearrangeexisting
portionsofasequence.Theexactstringinsertedbyacopyoperationchangeswiththe
contentofthesourceregion,butinaminimalway,sincethatcontentissimplydupli-
catesatanotherlocation.Anykindofoperationthatsimplypermutesorduplicatesthe
elementsofasequencewithoutlookingatthecontentsofthatsequence,isrepre-
Previous Page Next Page