should greedy algorithm test value expressions?

Iovka, I have laid out a couple ways greedy can work using your
whiteboard example.
Notation:
  Cₙ identifies triple constraints from the shape <S>.
  tₙ identifies triples.
  <S>, <Tₙ> are shapes.

  t1-t4 are followed by the triple constraints that are tested against.
  The "exhaustive" column includes the succeeding mapping after the '→'.
  t5-t10 are followed by the shape they match and a discriminating
  property path.

      C1          C2         C3               C4
<S> { :a @<T1>*, (:a @<T2> | :b xsd:integer), :b . }
<T1> { :b @<T3> }
<T2> { :b @<T4> }
<T3> { :c . }
<T4> { :d . }
                     exhaustive  greedy1  greedy2
 t1: <x>  :a <x1> .  C1,C2→C1    C1       C1
 t2: <x>  :a <x2> .  C1,C2→C2    C1       C2
 t3: <x>  :a <x3> .  C1,C2→C1    C1       C1
 t4: <x>  :b <x4> .  C3,C4→C3    C3       C3

 t5: <x1> :b <y1> .  <T1>:b/:c
 t6: <x2> :b <y2> .  <T2>:b/:d
 t7: <x3> :b <y3> .  <T1>:b/:c
 t8: <y1> :c 1 .     <T3>:c
 t9: <y2> :d 2 .     <T4>:d
t10: <y3> :c 3 .     <T3>:c

exhaustive -- succeeds with t1:C1, t2:C2, t3:C1, t4:C3
• Map triples to constraints by matching predicate only.
• Examine each combination of assignments for t1-t4 where C1,C2,C1,C3
  is the first that succeed the recursive test of the @<Tₙ> tests.

greedy1 -- fails after trying t1:C1, t2:C1, t3:C3, t4:C3
• Map triples to constraints by matching the predicate only.
• Fails recursive validation because <x2> doesn't match <T1> (no :b/:c)


greedy2 -- succeed with t1:C1, t2:C1, t3:C3, t4:C3
• Map triples to constraints by matching the predicate and value
  expressions. This includes recursive validation of <x1> - <x4>.
• Succeeds on first (only) assignment.

So the big question is whether we should avoid the recursive
validation that made greedy2 assign t2 to C2 instead of C1 as would
happen if we examine only the predicate. Note that "exhaustive" gets
the same result as greedy2 even though it only does the recursive
check after testing the triple expression.
-- 
-ericP

office: +1.617.599.3509
mobile: +33.6.80.80.35.59

(eric@w3.org)
Feel free to forward this message to any list for any purpose other than
email address distribution.

There are subtle nuances encoded in font variation and clever layout
which can only be seen by printing this message on high-clay paper.

Received on Thursday, 21 January 2016 09:58:08 UTC