Details

      Description

      SPARQL defines evaluation bottom-up while bigdata performed vectored pipelined evaluation. In general, pipelined evaluation, which is close to top-down evaluation, does not conflict with bottom up evaluation. However, conflicts in the evaluation semantics can appear in cases where an intermediate join group does not provide a shared variable. A difference in semantics can also appear when a variable would not be visible in bottom up evaluation, but is already bound in pipelined evaluation. For queries where bottom-up and top-down evaluation differ, the query is often incorrect (it will not do what the user intends) and some platforms reject such queries out of hand.

      Static analysis of join groups can determine when top-down evaluation would have different semantics. As indicated above, this breaks down into two cases:

      (A) bottom up evaluation is required;

      (B) bottom up evaluation can be mimicked by hiding variable bindings.

      To address this issue:

      1. Write a method which performs the static analysis and determines whether the two evaluation strategies would produce different results.

      2. For cases which require bottom-up evaluation, perform bottom-up evaluation rather than pipelined evaluation.

      3. As a special case, FILTERs may be unable to observe variables whose bindings are already known to a piplined evaluation strategy. This case can be handled by utilizing LET operators and anonymous variable names or "masking off" certain variables in order to "hide" the variable binding from the FILTER in a particular scope.

      See "The Semantics and Complexity of SPARQL" by J Perez [1], Section 4.3 "Well-designed patterns and normalization"

      [1] http://www.dcc.uchile.cl/~cgutierr/papers/sparql.pdf

        Activity

        Hide
        bryanthompson bryanthompson added a comment -

        Nested Optionals
        - 1 (I need to look at how to handle the double optional)

        SELECT *
        { 
            :x1 :p ?v .
            OPTIONAL
            {
              :x3 :q ?w .
              OPTIONAL { :x2 :p ?v }
            }
        }
        

        The problem with this query is that the inner group is an optional. When it is lifted into a named subquery we also need to mark the INCLUDE as an optional. INCLUDE does not yet support optional join semantics so I have to fix that as well.

        Show
        bryanthompson bryanthompson added a comment - Nested Optionals - 1 (I need to look at how to handle the double optional) SELECT * { :x1 :p ?v . OPTIONAL { :x3 :q ?w . OPTIONAL { :x2 :p ?v } } } The problem with this query is that the inner group is an optional. When it is lifted into a named subquery we also need to mark the INCLUDE as an optional. INCLUDE does not yet support optional join semantics so I have to fix that as well.
        Hide
        bryanthompson bryanthompson added a comment -

        There is one more TCK "bottom up" test which is failing.

             * Optional-filter - 1
             * 
             * <pre>
             * PREFIX :    <http://example/>
             * 
             * SELECT *
             * { 
             *   ?x :p ?v .
             *   OPTIONAL
             *   { 
             *     ?y :q ?w .
             *     FILTER(?v=2)
             *   }
             * }
        

        Reading [1], it appears "SELECT *"

        SELECT * { P }	v is in-scope in P
        

        Thus, we need to handle v as if it were an exogenous variable for this query, which is to say that we would just execute it normally

        [1] http://www.w3.org/TR/sparql11-query/#variableScope

        Show
        bryanthompson bryanthompson added a comment - There is one more TCK "bottom up" test which is failing. * Optional-filter - 1 * * <pre> * PREFIX : <http://example/> * * SELECT * * { * ?x :p ?v . * OPTIONAL * { * ?y :q ?w . * FILTER(?v=2) * } * } Reading [1] , it appears "SELECT *" SELECT * { P } v is in-scope in P Thus, we need to handle v as if it were an exogenous variable for this query, which is to say that we would just execute it normally [1] http://www.w3.org/TR/sparql11-query/#variableScope
        Hide
        bryanthompson bryanthompson added a comment -

        Well, consulting the manifest it turns out that

        A FILTER inside an OPTIONAL can reference a variable bound in the required part of the OPTIONAL
        

        So, there is the answer.

        Show
        bryanthompson bryanthompson added a comment - Well, consulting the manifest it turns out that A FILTER inside an OPTIONAL can reference a variable bound in the required part of the OPTIONAL So, there is the answer.
        Hide
        bryanthompson bryanthompson added a comment -

        Fix for

             * Optional-filter - 1
             * 
             * <pre>
             * PREFIX :    <http://example/>
             * 
             * SELECT *
             * { 
             *   ?x :p ?v .
             *   OPTIONAL
             *   { 
             *     ?y :q ?w .
             *     FILTER(?v=2)
             *   }
             * }
        

        "A FILTER inside an OPTIONAL can reference a variable bound in the required part of the OPTIONAL."

        Note: This is ONLY true when the [group] is OPTIONAL. Otherwise the variables in the parent are not visible.

        Committed revision r5203.

        Show
        bryanthompson bryanthompson added a comment - Fix for * Optional-filter - 1 * * <pre> * PREFIX : <http://example/> * * SELECT * * { * ?x :p ?v . * OPTIONAL * { * ?y :q ?w . * FILTER(?v=2) * } * } "A FILTER inside an OPTIONAL can reference a variable bound in the required part of the OPTIONAL." Note: This is ONLY true when the [group] is OPTIONAL. Otherwise the variables in the parent are not visible. Committed revision r5203.
        Hide
        bryanthompson bryanthompson added a comment -

        Nested Optionals
        - 1

        SELECT *
        { 
            :x1 :p ?v .
            OPTIONAL
            {
              :x3 :q ?w .
              OPTIONAL { :x2 :p ?v }
            }
        

        As noted above, the problem with lifting out the named subquery is that INCLUDE does not currently support OPTIONAL (that is, the NamedSubqueryIncludeOp does not currently support optional).

        As a workaround the INCLUDE is stuffed into an OPTIONAL group.

        Nested Optionals
        - 1 now runs correctly.

        Committed revision r5204.

        Show
        bryanthompson bryanthompson added a comment - Nested Optionals - 1 SELECT * { :x1 :p ?v . OPTIONAL { :x3 :q ?w . OPTIONAL { :x2 :p ?v } } As noted above, the problem with lifting out the named subquery is that INCLUDE does not currently support OPTIONAL (that is, the NamedSubqueryIncludeOp does not currently support optional). As a workaround the INCLUDE is stuffed into an OPTIONAL group. Nested Optionals - 1 now runs correctly. Committed revision r5204.

          People

          • Assignee:
            mikepersonick mikepersonick
            Reporter:
            bryanthompson bryanthompson
          • Votes:
            0 Vote for this issue
            Watchers:
            3 Start watching this issue

            Dates

            • Created:
              Updated:
              Resolved: