44
quencesandtheirediting,althoughtheissuesapplytoothertypesofaggregatedatastruc-
turesaswell.
Therearetwofundamentalpropertiesthatmightbesatisfiedbyachange-orientedrepre-
sentationofstatechanges.Onepossibilityisasetofoperationsthatisversion-complete.We
willdefinethetermversion-completetorefertoasetofoperationtypesthatsufficestorep-
resentallthepossibledifferencesbetweensignificantstates(versions)ofadataobject.
Whenthegoalistorepresentonlyparticularstatesofdataobjects,withoutconcernfor
combiningormodifyingchangehistories,aversion-completesetofchangesisallthatis
neededtomeetthefunctionalrequirement.
Withaversion-completesetofoperationtypes,anyversiongraphcanberepresentedby
setsofchangesinahistorystructure.Suchrepresentationsareoftenusedasastorageopti-
mizationtechniquetoreducetheoverheadanddataduplicationsofsavingmanydistinct
butsimilarstates.Suchrepresentationsarechosensothatthestoragetoholdallneeded
versionsofanobjectwillbeassmallaspractical.Thepreciseoperationtypesandtheirrep-
resentationarecriticaltosatisfyingasystem’stimeandspaceefficiencygoals,bothinterms
ofthespacerequiredtoholdtypicalhistories,andthetimerequiredtofindtherepresenting
anyparticularhistory.However,theactualoperationsusedarenotimportantinthemselves,
andthereareinfactmanypossibleoperationsets,withfairlysimplesemantics.
Version-completenessisnotaverydifficultpropertytoensure.Moredifficultistofinda
setofbasicoperationsthatischange-complete.Suchasetofoperationsissufficientnotonly
torepresentdifferencesamongarbitraryversions,butisalsochosentobe“natural”forthe
applicationareainquestion.Whilethismayinvolveveryspecializedoperationsofuseonly
inaparticularapplication,thereareinfactmanyusefulgeneralizedoperations,depending
onanapplication’srequirements.Onekeyissueindeterminingthenaturalnessofanopera-
tionsetforanapplication’sneedsiswhethertheoperationsdirectlycorrespondtoauser’s
actionsinusingtheapplication,ortoauser’smodelofwhatisbeingaccomplishedbythose
45
actions.
1
Thisinformation,whileitmaybestrictlyredundantinthesenseofversion-
completeness,canprovecriticalinpreservingusers’editingintentionswhenhistoriesare
modified.Operationslikemergeandselectiveundodependcriticallyontheactualopera-
tionsperformed,andareoneofthereasonsforadoptingchange-completeoperationmodels.
Inaversion-completesystem,theresultofmergingtwootherstatesisnotinitselfspe-
cial:anychangesetisacceptablethatcorrectlyproducesanacceptableresult:representing
thesavedstatesofthesharedstructurewhilemeetingthecomplexityandspacerequire-
mentsoftheapplication.Inatypicaloperation-completesystem,sucharesultstatewould
betheresultofsomekindofmergeoperationperformedontheoperationhistoriesthatcre-
atedthetworelevantversions,anditwouldreflectthecombinedeffectsoftheprimitive
operationsinthosehistories.
2.4 Limitsofthetaxonomy
Inthefollowing,Isummarizesomekeyaspectsofchangeinteractionbyenumerating
typesofinteractionandconflictresolution.Theglobalcontextofoperationtypes,potential
inter-operationinteractions,andpotentialconflictsprovidesaconceptualframeworkforun-
derstandingtheconflictsituationsinChapter3,andthedesigndecisionsinthePalimpsest
modelpresentedinChapter4.
InthistaxonomyIconsiderpropertiesofoperationsthatareindependentofthepolicy
issueswhichariseintheimplementationoffacilitieslikemergeandundo.Thesefacilities
createseriousissuesofchangeconflictthatwewilldiscussinChapter3,inthecontextofa

1
Thesearedistinct,inthatmostuser’smentalmodelsofeditingincludeoperationslike“move,”
buttheiractualactionsinmosteditorsareacombinationof“cut”and“paste”actions.Changerepre-
sentationsorientedtohumanneedsaremoreimportantthanapplication-orientedones,wherethe
distinctionispossible.
Previous Page Next Page