W3C home > Mailing lists > Public > public-rdf-dawg-comments@w3.org > October 2006

Re: Filter scope and optionals

From: Jorge Pérez <jperez@ing.puc.cl>
Date: Mon, 30 Oct 2006 12:43:02 -0300 (CLST)
Message-ID: <55779.146.155.4.12.1162222982.squirrel@mail.ing.puc.cl>
To: andy.seaborne@hp.com
Cc: public-rdf-dawg-comments@w3.org

Hi Andy,

> If the proposed filter scoping rule is taken naively, there isn't a way to
> get
> value testing conditions into the left join conditions for optional
> (unlike
> the join conditions for a group).
>
> Here's an example:
>
> ---- Data
> @prefix   :         <http://example/> .
>
> :x1 :p 1 .
> :x2 :p 2 .
>
> :x3 :q 3 .
> :x3 :q 4 .
> ---- Data
>
>
> ---- Query
> PREFIX :    <http://example/>
>
> SELECT *
> {
>    ?x :p ?v .
>    OPTIONAL
>    {
>      ?y :q ?w .
>      FILTER(?v=2)
>    }
> }
> ---- Query

I personally think that this kind of queries are interesting from the user
point of view, but because they need a *dynamic scope* evaluation (I
really don't know how to call it, but I think you understand) the language
looses the compositionality. What I mean is that the *expression*

{
  ?y :q ?w .
  FILTER(?v=2)
}

has different meanings depending on where it appears on the query. Here
you are discussing the appearance of it in the right hand side of an
OPTIONAL, but it would appear in a parallel group, in a UNION, inside a
GRAPH, etc. Also here the expression in the filter is very simple but I
think that with bound\!bound things could be more complex.

>
>
> ---- Results 1
> ---------------------
> | x   | v | y   | w |
> =====================
> | :x2 | 2 | :x3 | 4 |
> | :x2 | 2 | :x3 | 3 |
> | :x1 | 1 |     |   |
> ---------------------
>
> ---- Results 2
> -------------------
> | x   | v | y | w |
> ===================
> | :x2 | 2 |   |   |
> | :x1 | 1 |   |   |
> -------------------
>
> Results 1 is what the current doc (declarative form) gets - and would be
> the
> same if the FILTER were part of the left outer join conditions.
>
> Results 2 is what a purely filter-scoped-to-group gets because the
> optional
> part never matches because ?v is an unbound variable.
>
>
> I can't see any way of getting filter into the scope of the left outer
> join.
> The only way I can see of rewriting this query is to use a UNION and
> repeat
> the fixed pattern on each side of the union, one side including the filter
> and
>   optional triple pattern. That query is going to give different answers
> and
> the app will have to post-process the results to find out what went on.

And the following query?

SELECT *
{
   ?x :p ?v .
   OPTIONAL
   {
     ?x :p ?v .
     ?y :q ?w .
     FILTER(?v=2)
   }
}

I think (but I do not have a proof of it), that giving a dinamic scope for
filters in optionals does not increase the expressiveness of the language
compared with the compositional-algebraic-operations approach, and one can
always obtain the same result repeating the pattern inside the optional
(as in the above query).

>
> Intuitively, the scope rule needs to be modified to put the filter just
> outside the group, allowing it to be part of the left outer join, and not
> just
> inside the group.

I think it is not so simple, because you can have patterns like

{ ?x :p ?v
  OPTIONAL {
     ?y :p ?w
     OPTIONAL {
        ?z :q ?u .
        FILTER (?v=2) } } }

and then the problem affect the semantics of nested optionals too.

>
> Any alternatives?
> How do we formalize this?

One approach is to formalize OPTIONAL + FILTER in a navigational way (as
the current spec).
Another approach to formalize the dinamic scoping (without loosing
compositionality) is to think that the filter is *generating bindings*,
for example from

{
  ?y :q ?w .
  FILTER(?v=2)
}

results the solutions for ?y :q ?w defined also in variable ?v but with
fixed value 2 for ?v. What I do not like of this approach is that FILTER
is not filtering, it is *forcing* some bindings, and formal definitions
would become complex in the case of restrictions like ?x = ?y, or
restrictions with negations.

I'm personally in favor of the Results 2 above (filter-scoped-to-group).

- jorge


>
> 	Andy
>
>
Received on Monday, 30 October 2006 15:43:32 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Tuesday, 8 January 2008 14:14:50 GMT