102
operations.Theonlyconstraintactuallyenforcedbyasystemisthatbeforecheckinginthe
newversiontheuserwhocreatedanewerversionatleasthadtheopportunitytolookat
(andedit)itspredecessors.Inpractice,ofcourse,succeedingversionsusuallyusuallyarethe
resultofeditingthepreviousversion,andsystemstakeadvantageofthisfact,usingdiff
algorithmstooptimizethestorageofversions.
5.1.1 RepresentingtraditionalversiongraphsinPalimpsest
APalimpsestmodeloftraditionalsoftwareengineering-styleversioningapproacheslike
thosein,e.g.(Rochkind1975;Tichy1985;Cohen,Sonietal.1988).Considerabranching
systemwithoutmerge.APalimpsestmodelofthissystemuseschangesetstorepresenteach
nodeintheversiongraph.Eachchangesetcorrespondingtoanodewouldbeasupersetof
thechangesetrepresentingitsparentnode,correspondingtothefactthatitwasderivedby
addingchangestoitsparent.
Addingmergetosuchasystempotentiallyintroducesproblems,inthecasethatcompo-
nentchangesconflict.Whennoconflictsarepresent,amergeresultisobtainedsimplyby
takingtheunionofthetwoparents.Thisresultwouldthenserveasthebaseforanyuser
correctionstotheresultofthemerge,intheformofadditionalchangestothemergedver-
sion.Inthepresenceofconflicts,therearetwopossibilities.Thesimplestistoeliminate
conflictsbyamendingtheaddressorderingasdiscussedinSection4.3.2.Thissimplepossi-
bility,howeverisratherdifferentfromthepoliciesofthesystemsthatwearetryingto
emulate.
Analternativeapporachisthecreateaninitialmergeresultrepresentingaconflict-free
unionofthechangesinthetwoparentversions.Theconflictingchangeswouldbestoredin
aseparatechangesetforhandinterventionbytheuser,operation-by-operation.Inthis
case,themechanicalmergerwouldserveasastartingpointfortheusertocreateafinal
mergeresult.Thisisessentiallysimilartothemergefacilitiesinmostsoftwareconfiguration
managementsystems,whichdetectdifferences,andthenoffertheusertheopportunityto

103
acceptthemormakeotherchangestotheresult.Inthemergeprocess,theexactuser
changesthatledtoconflictswouldallbeaccessibleandlinkedtotheprecisecontextin
whichtheyoccurred.
APalimpsest-basedmodelencodesmuchmoreinformationabouttheprecisechanges
contributingtoaversionandtheirrelationships,butabranchingsystemdoesnotneedmost
ofthecapabilitiesofaPalimpsest-basedmodel.Forabranchingsystemwithoutmerge,the
versiongraphisisomorphictothesubsetrelationshipsamongthechangesetsrepresenting
theversions,withsuccessorrelationscorrespondingtodescendingchainsunderthesubset
relationbetweenchangesets.Oncemergeoperationsandconflictresolutionareadded,this
isomorphismbetweentheversiongraphandthesubsetrelationonchangesetsceasesto
hold,sinceadescendantofaversionmaylacksomeconflict-producingchangesofitspar-
ent(s).
Onespecialcaseoftree-structuredversioningsystemsisevenmorerestrictive.Somesys-
tems(ofwhichtheearliestwasAugment/NLS(Engelbart,Watsonetal.1973;Engelbart
1984))constraintheversiongraphtobeasimplesequenceofhistoricallyrelatedrevisions.
Thesesystemscanbemodeledinthesamewayastree-structuredsystems.Inthiscase,a
seriesofversionscorrespondstoachainofchangesetsunderthesubsetrelation.
5.1.2 Trackingstatesandpersistentaddressing
Likeanychange-orientedrepresentation,thePalimpsestmodelallowsamuchlarger
numberofpotentialconfigurationstobeeasilydescribedandrelatedthanstate-oriented
systemscan.Anycausally(orminimally)consistentsetofchangesdefinedaP-sequence
thathasawell-definedstate.Anytwoversionsrepresentedbychangesetscanbemeaning-
fullycomparedinanumberofways:
• ThedifferencesbetweentwochangesetsAandBcanbedeterminedbyexaminingthe
setsA –B,B – A,andA ˙ B.