jackrabbit-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Michael Dürig <mdue...@apache.org>
Subject Re: [jr3 microkernel] Change log consolidation
Date Tue, 07 Feb 2012 18:16:25 GMT
>>>> Let m = p:q, n = r:s with p, q, r, s != NIL be valid moves with m != ID
>>>> and
>>>> n != ID. Then the following reduction and commutation rules apply:
>>>>
>>>> 1.  p!~ r:  m * n = n * m
>>>> 2.  p<    r:  illegal (since this implies q<= r which implies p ~ q
and
>>>>             thus m invalid)
>>>> 3.  p = r:  illegal (since this implies q<= r which implies p ~ q and
>>>>             this m invalid)
>>>> 4.  p>    r:  does not commute if q<    s. Otherwise m * n = n * [r
->    s]m
>>>> 5.  p!~ s:  m * n = n * m
>>>> 6.  p<    s:  illegal (since this implies p ~ q and thus m invalid)
>>>> 7.  p = s:  does not commute
>>>> 8.  p>    s:  illegal (since p>    s implies there is an s already
which
>>>>             will conflict with r:s)
>>>> 9.  q!~ r:  m * n = n * m
>>>> 10. q<    r:  m * n = [q ->    p]n * m
>>>> 11. q = r:  m * n = p:s (transitivity of moves)
>>>> 12. q>    r:  m * n = n * [r ->    s]m
>>>> 13. q!~ s:  m * n = n * m
>>>> 14. q<    s:  does not commute if p>    r. Otherwise m * n = [q ->
   p]n * m
>>>> 15. q = s:  illegal (since s conflicts with r:s)
>>>> 16. q>    s:  illegal (since s conflicts with r:s)
>>>>
>>>> Allowing add node and remove node operations the following additional
>>>> conditions apply:
>>>>
>>>> Let m = p:q, n = r:s be valid moves with m != ID and n != ID. Then the
>>>> reduction and commutations rules 1. to 16. apply with extra conditions on
>>>> 4., 10., 12. and 14.:
>>>>
>>>> 4'.  if s = NIL and q = NIL then m * n = -r. Otherwise if s = NIL then
>>>>      m, n do not commute.
>>>> 10'. illegal if p = NIL
>>>> 12'. if s = NIL then m * n = -r * -p
>>>> 14'. illegal if p = NIL
>>>
>>
>>> could you please provide a simple example?
>>

Here are simple examples for each of the above cases and its respective 
special cases. Note that I refined 14'. to

14'. if p = NIL: does not commute if the parent of s is q. Illegal otherwise

1.   >/a:/b >/c:/d     =  >/c:/d >/a:b
2.   >/a:/b >/a/b:/c      illegal
3.   >/a:/b >/a:/c        illegal
4.   >/a/b:/c >/a:/d   =  >/a:/d >/d/b:/c
4.   >/a/b:/c >/a:/c/d    does not commute  (q < s)
4'.  -/a/b -/a         =  -/a               (s = NIL and q = NIL)
4'.  >/a/b:/c -/a      =  does not commute  (s = NIL)
5.   >/a:/b >/c:/d     =  >/c:/d >/a:b
6.   >/a:/b >/c:/a/d      illegal
7.   >/a:/b >/c:/a        does not commute
8.   >/a/d:/b >/c:/a      illegal
9.   >/a:/b >/c:/d     =  >/c:/d >/a:b
10.  >/a:/b >/b/c:/d   =  >/a/c:/d >/a:/b
10'. +/b:{} >/b/c:/       illegal
11.  >/a:/b >/b:/c     =  >/a:/c
12.  >/a:/b/c >/b:/d   =  >/b:/d >/a:/d/c
12'. >/a:/b/c -/b      =  -/b -/a
13:  >/a:/b >/c:/d     =  >/c:/d >/a:b
14.  >/a:/b >/c:/b/d   =  >/c:/a/d >/a:/b
14.  >/a/b:/b >/a:/b/d    does not commute  (p > r)
14'. +/b:{} >/c:/b/c      does not commute  (parent of s = q and p = NIL)
14'. +/b:{} >/c:/b/c/d    illegal           (p = NIL)
15.  >/a:/b >/c:/b        illegal
16.  >/a:/b/d >/c:/b      illegal

Have fun ;-)

Michael

Mime
View raw message