Chapter6:AlgorithmsforP-sequences
Thischapterdiscussesalgorithmsforchange-orientedmanagementofsequences.Wewill
considertheissuefromadatastructureperspective,examiningwaystoretainadatabaseof
changes,andproducetheresultsofapplyingsubsetsofthosechanges.Thischapterproceeds
incrementallytoafullsolution:firstpresentingalgorithmssufficientformanagingchange
setsincludingonlyinsertanddeleteoperations,andthenextendingthemtohandlemove
andcopyoperations.Thefirststagewillbeginwithanexaminationofthealgorithmsfor
VTMLeditors,andthencontinuewithanexaminationofhowtoimplementthemorecom-
plexmodelprovidedbyPalimpsest.VTMLisachange-orienteddataformattohelpsupport
collaborationovertheWorldWideWeb,whichprovidesaninterestingcontrasttoPalimpsest.
6.1 TheVTMLmodel
ThissectiongivesabriefdescriptionofVTML2.0,(theVersionedTextMarkupLanguage)
asystemsupportingchange-orientedconcurrencycontrolforwebapplications.Theinitial
descriptionofVTML(VTML1.0)waspresentedin(VitaliandDurand1995).VTMLisafile
formatfortheinterchangeofmultiplerevisionsofdocuments,andisintendedasabuilding
blockforprotocolsforcollaborationovertheweb.AVTMLdocumentcanrepresentasetof
updatestobeappliedtoanotherVTMLdocument,oritcanbeaself-containedrepresenta-
tionofmultipleversionsofadocument.VTMLisstillhasversionswhichuseapurebranch-
ingscheme.Italsosupportsadditionalchange-orientedfeatures,whichstoreinformation
abouttheindividualinsertionanddeletionoperationsthatmakeupaversion.Versionscan
explicitlyaddin,orremoveparticularchangesthatwerecreatedinotherversions.

111
6.1.1 Versionsandversionnumbers
Sinceachangeisapplicableinanyversionthatisadescendentoftheversioninwhichit
wasadded,ancestorqueriesareimportantinquicklydeterminingwhetheraparticular
changeispresentinaparticularversion.InVTML,thisproblemissolvedbyusingaversion
numberingscheme.Whileversionscouldbearbitrarilyidentified,structurednamingschemes
areinwideusebecausetheyenableaprogramtodeterminetherelationshipbetweentwo
versionsgivenonlytheirversionnumbers.Inparticular,itisusefultobeabletotellifa
versionisachildofanotherversion,andtocalculatetheversionnumberofthecommon
ancestoroftwoversionsgiventheirversionnumbers.VTMLversionsarerepresentedusing
“L-shaped”versionnumbers.Thisnumberingsystemhasbeen(independently)describedin
(KellerandUllman1995),whichexaminesthemintermsoftheirorderingproperties,for
integratingversionmanagementintotraditionaldatabasesystems.BeforedescribingL-
shapedversionnumbering,wewillbrieflyreviewthetwomostobviousalternatives,and
theircharacteristics.
Thefirstalternativecanbecalledoutlinenumbering.Inthissystem,asinallthefollow-
ingonesweshallexamine,therootversionisalwaysnumber1.Thefirstchildofanode,x,
willhavenumberx.1.Then-thbrotherofx.1willhavenumberx.n.Thismeansthateach
successorversionincreasesthelengthoftheversionnumber.Whilethissystemissimpleto
implement,andwhileancestortestingandcommonancestordeterminationaretrivial,this
schemeisneverused.Thisisbecauseversiontreestendtohavemanylongchains,andout-
linenumbersgrowlinearlyinthelengthofachain.
Thesecondalternativecanbecalledreverseoutlinenumbering.Inthissystem,thefirst
childofanodexwillhavenumberx+1.Thefirstsiblingofx+1willhavenumber(x+1).1.
Undertheserules,furthersiblingswillbenumberedx+1.1.1,andsoon.Inthissystem,suc-
cessorsarenumberedsequentially,solvingtheproblemoflongidentifiers,butanylarge
numberofalternativesrecreatestheproblem.