NSPARQL Jesse Weaver 20080911 Jesse Weaver 2

From Semantic Portal Wiki

• Question is for the Presentation: nSPARQL Jesse Weaver 20080911
• Question is asked by: Jesse Weaver
• The Question is: See the question page.

The conclusion of complexity O(G*exp) is based on the assumption that Label is called k times, where k is the sum of the number of depth-0 expressions, the number of depth-1 expressions, ..., and the number of depth-d expressions. This is true if Label is called once for each of the expressions at every depth.

Consider the counterexample where exp=edge::[node::b/next::a]/next::[node::b/next::a]. In this case, lines 1 and 2 of label will break apart the expression as so:

  edge::[node::b/next::a]/next::[node::b/next::a]
     edge::[node::b/next::a]
        node::b
        next::a
     next::[node::b/next::a]
        node::b
        next::a

As you can see, label is called 7 times, even though k would equal 5 (the number of unique expressions in the tree above). How could this be remedied to avoid the redundant work and thus enforce the assumption of k calls to Label?