94
Definition 4.12:Moved(a
1 , a
2 , S)is true iff$c e S, c =M[a’
1 , a’
2 , d] and
a’
1 £
SA a
1 <
SA a
2 £
SA a’
2 .
Definition 4.13:RecessiveMoves(m, S)is{c = M[a, b, c] e S | c <
chg morc = m}.
Definition 4.14:For a P-sequenceX
S ,andS’ ˝ S,C’(a
1 , a
2 , S’)is defined by the following
cases, listed in order of priority:
1. Ifa
2 <
SA a
1 , C’(a
1 , a
2 , S’)isL.
2. IfDeleted(a
2 , a
2 , S’), C’(a
1 , a
2 , S’)isL.
3. IfI
X (a
1 ) + 1 „ I
X (a
2 ), C’(a
1 , a
2 )is equal toC’(a
1 , P
X (I
X (a
1 ) + 1), S’)C’(P
X (I
X (a
1 ) + 1), a
2 ,
S’).
4. Ifa
2 = (I,
i),andIis the ID of an insertionI[s, d],wheres = v
1 … v
n ,then
C’(a
1 , a
2 ) = v
i–1 .
5. Ifa
1 = (I
1 …I
n , i),a
2 = (I’
1 …I’
n , j),I
1 = I’
1 , and Change(I
1 )is a copy, then
C’(a
1 , a
2 , S) = C’((I
2 …I
n , i), (I’
2 …I’
n , j), S’).
6. Ifa
1 = (I
1 …I
n , i),a
2 = (I’
1 …I’
n , j),I
1 = I’
1 , Change(I
1 )is a move, then
C’(a
1 , a
2 , S’) = C’((I
2 …I
n , i), (I’
2 …I’
n , j), S’ – RecessiveMoves(I
1 , S’)).
7. IfMoved(a
2 , a
2 , S’), C’(a
1 , a
2 , S’)isL.
8. OtherwiseC’(a
1 , a
2 , S’) = L.
We can see a few things about the contents of a sequence and their relationship to the
structure of addresses. All contents in a sequence originally come from some insertion opera-
tion, and the addresses between which contents occur contain the ID of their insertion.
Many pairs of addresses exist between which no data occurs. Whenever something is in-
serted, whether directly or as the result of a move or a copy, new addresses are created be-
fore and after the new data. While the address at an insertion point is no longer available as
the target for other changes (in order to preserve minimal consistency), a new insertion
point is created immediately after it, immediately preceding the new material. Similarly, a
Definition 4.12:Moved(a
1 , a
2 , S)is true iff$c e S, c =M[a’
1 , a’
2 , d] and
a’
1 £
SA a
1 <
SA a
2 £
SA a’
2 .
Definition 4.13:RecessiveMoves(m, S)is{c = M[a, b, c] e S | c <
chg morc = m}.
Definition 4.14:For a P-sequenceX
S ,andS’ ˝ S,C’(a
1 , a
2 , S’)is defined by the following
cases, listed in order of priority:
1. Ifa
2 <
SA a
1 , C’(a
1 , a
2 , S’)isL.
2. IfDeleted(a
2 , a
2 , S’), C’(a
1 , a
2 , S’)isL.
3. IfI
X (a
1 ) + 1 „ I
X (a
2 ), C’(a
1 , a
2 )is equal toC’(a
1 , P
X (I
X (a
1 ) + 1), S’)C’(P
X (I
X (a
1 ) + 1), a
2 ,
S’).
4. Ifa
2 = (I,
i),andIis the ID of an insertionI[s, d],wheres = v
1 … v
n ,then
C’(a
1 , a
2 ) = v
i–1 .
5. Ifa
1 = (I
1 …I
n , i),a
2 = (I’
1 …I’
n , j),I
1 = I’
1 , and Change(I
1 )is a copy, then
C’(a
1 , a
2 , S) = C’((I
2 …I
n , i), (I’
2 …I’
n , j), S’).
6. Ifa
1 = (I
1 …I
n , i),a
2 = (I’
1 …I’
n , j),I
1 = I’
1 , Change(I
1 )is a move, then
C’(a
1 , a
2 , S’) = C’((I
2 …I
n , i), (I’
2 …I’
n , j), S’ – RecessiveMoves(I
1 , S’)).
7. IfMoved(a
2 , a
2 , S’), C’(a
1 , a
2 , S’)isL.
8. OtherwiseC’(a
1 , a
2 , S’) = L.
We can see a few things about the contents of a sequence and their relationship to the
structure of addresses. All contents in a sequence originally come from some insertion opera-
tion, and the addresses between which contents occur contain the ID of their insertion.
Many pairs of addresses exist between which no data occurs. Whenever something is in-
serted, whether directly or as the result of a move or a copy, new addresses are created be-
fore and after the new data. While the address at an insertion point is no longer available as
the target for other changes (in order to preserve minimal consistency), a new insertion
point is created immediately after it, immediately preceding the new material. Similarly, a