56
Section2.5.Forpermutationaloperationsarangeissubjectonlytoduplication(copying
elsewhere)ordeletion,whileapointcanonlybeaffectedbydatabeinginsertedatit
5
.
Point Range
Point
Conflictifequal;similarforallopera-
tions.
Range
Potentialconflictwhenpointinrange;
variesbyoperation.
Potentialconflictwhenregionsoverlap;var-
iesbyoperation.
etc.
T T T Ta a a ab b b b lll le e e e 3333....1111:::: SSSSttttrrrruuuuccccttttuuuurrrraaaallll ssssiiiittttuuuuaaaattttiiiioooonnnnssss tttthhhhaaaatttt mmmmaaaayyyy iiiinnnnddddiiiiccccaaaatttteeee aaaa ccccoooonnnnfffflllliiiicccctttt....
Inallcasesofinteractingoperations,aconflictispossibleiftheapplication’ssemantics
requireit,however,potentialconflictscanbemeaningfullygroupedbystructuralconfigura-
tion,anumberofwhichcanbehandledidenticallyforalloperations.Formoreextended
operationsets,applicationsmust(inanycase)beabletoexamineoperationsetstolookfor
potentialconflicts.ThegoalofPalimpsest’soperationmodelistogivewelldefined,logically
consistent,andpracticalresultsforasmanycasesaspossible,sothatapplicationsarenot
preventedfromimplementingwhateverpoliciestheyrequirebyaddingrestrictionsonopera-

5
Theotherpossiblepermutationaloperationistotalreplacement.However,thisisnotstrictly
necessary,aswecanmodelreplacementasacoupledpairofdeletionandinsertionoperations.Since
conflictdetectionisextensible(asrequiredtosupportthefullrangeofsensibleapplicationpolicies),
ignoringreplacementwillentailnolossofgenerality.
57
tioncombination.Thereareonlythreestructuralcasestoconsider,givingatriangularma-
trixofpossibilities,allofwhichareinherentlypossibleforanysystemthatallowsdiver-
gence:
Point-pointconflicts.Theseareallessentiallythesame,andtheyallrepresentapotential
conflict.Whenmorethanoneinsertionismadeatthesamepointeitheranapplication
conflictmustbereported,orthetwoitemsmustbeorderedrelativetooneanother—in
suchawaythatthesamepairofoperationswillalwaysbeorderedthesameway.
Point-rangeconflicts.Theseareessentiallyallofasimilarform,withsomedatabeing
insertedinaregionthatisreadoraffectedbyanotheroperation.Iftherangeisonly
read,noconflictshouldoccur,asthetwochangesareindependent;whenbothareac-
tive,theoperationthatreadstherangeshouldreceivearesultincludingtheaddeddata.
Inthecasewheretherangeistobemodifiedbytheoperation,asemanticconflictis
possible,dependingontheeffecttobeperformedontherange.Formostoperations,the
conflictshouldberesolvedinthesamewayasintheread-onlycase.Oneimplicationof
thisisthattheresultsofaninsertionarelostifarangecontainingtheinsertionpointis
deleted.
Range-rangeconflicts.Thesepresentvaryingproblems,dependingonwhethertheopera-
tionschangethepositionofcontentsoftheranges,orwhethertheoperationssimply
readthecontentsoftheranges.Inthecaseofoverlapswherebothoperationsmerely
readthecontentsoftheranges,thereisnoinherentconflict.Butincaseswhereeven
oneoftherangesisaffectedbyoneoftheoperations,aninherentconflictexists.Ifthe
applicationdoesnotdisallowthecombination,thesystemmustbeabletoordertheop-
erationsinordertodeterminewhateffectoccursintheregionoftheoverlap.Evenmore
thaninthecaseofmultipleinsertionsatasinglepoint,thisisastructuralsituation
wherethesystemmustmakeadecisionabouthowtoorderchanges.Furthermore,this
Previous Page Next Page