W3C home > Mailing lists > Public > public-rdf-dawg@w3.org > January to March 2005

Re: question about combining patterns

From: Seaborne, Andy <andy.seaborne@hp.com>
Date: Fri, 11 Feb 2005 11:48:36 +0000
Message-ID: <420C9B94.2090701@hp.com>
To: Alberto Reggiori <alberto@asemantics.com>
CC: RDF Data Access Working Group <public-rdf-dawg@w3.org>

Alberto Reggiori wrote:
> On Feb 2, 2005, at 7:34 PM, Seaborne, Andy wrote:
> 
>>>is the following query
>>>
>>>PREFIX  dc:  <http://purl.org/dc/elements/1.1/>
>>>PREFIX  ns:  <http://example.org/ns#>
>>>SELECT  ?title ?price
>>>WHERE
>>>{
>>>    ( ?x dc:title ?title )
>>>    ( ?x ns:price ?price )
>>>}
>>>AND ( ( ?price < 30 ) || ( ?price > 40 ) )
>>>
>>>going to fail accordingly to what stated in
>>>
>>>	http://www.w3.org/2001/sw/DataAccess/rq23/#CombiningPatterns
>>>
>>>?
>>>
>>>I think so - due the above query has two graph-patterns, and that the
>>>constraints by definition do not bind any var - it should fail
>>
>>
>>It should be OK - what about #CombiningPatterns is suggesting this to
>>you?
> 
> 
> to me it is suggesting that a "basic graph pattern" is a set of 
> triple-patterns, which can be combined in 5 possible ways (here called 
> blocks):
> 
> 	-> group pattern (block of blocks)
> 	-> constraints
> 	-> optionals
> 	-> named-graphs
> 	-> alternatives
> 
> Constraints are considered a special kind of block, not part of a basic 
> graph pattern - which do not bind variables and are only used to filter 
> results. A block containing only constraints is a valid block. The 
> first 4 patterns combinations are about a conjunctive combination of 
> their blocks' elements (where a set of patterns must all match); while 
> the last one (alternatives) is about simple disjunction (where two or 
> more possible patterns are tried). Each block contributes to the final 
> result/solution.
> 
> 
>>{
>>    ( ?x dc:title ?title )
>>    ( ?x ns:price ?price )
>>}
>>
>>is a group of patterns that just generates bindings for ?title and
>>?price these go into the cosntraint.
>>
>>Variables are NOT scoped by blocks - they are global to the query.  Is
>>this the reading you are making?
>>
>>There is an outer group containing this inner group (redundantly) and
>>the AND clause.  The AND applies to the outer group "all solutions are
>>such that ?price < 30 || ? price > 40"
> 
> 
> yes this part was clear and taken
> 
> 
>>The example in that section shows that the query can include {} nesting
>>and return the same solutions.  Suggestions for improvement?
> 
> 
> any good reason why constraints could not be part of the "basic graph 
> pattern" definition?

It would be possible to have a design where constraints are part of basic blocks 
- its a different design.

It would have some implications:

{ (?x dc10:title ?title) UNION (?x dc11:title ?title) } AND ?title =~/foo/i

does not have the constraints on a basic pattern block.  It would have to be 
moved into each branch.

An optimizer may well do this - but then an optimizer may well move the 
constrinast inside basic pattern blocks to put the constraint at the best place 
for the query and the data.

If a constraint involves two variables, then it gets harder to
say where they constraint should be.

> 
> Constraints should then be evaluated either on any previous (outer 
> block) result context and on bindings generated in the block itself 
> (i.e. constraints are evaluated in their tree of blocks). This would 
> make its processing more deterministic and logical.

I think there is little burden on implementation because this sort of variable 
liveness analysis is necessary for any rewriting (and ones that don't do that 
aren't focusing on efficiency so don't care anyway).

> 
> 
>>>In other words, in the implementation, while processing the blocks
>>>stack one should execute any "binding graph-pattern" first or fail if
>>>not possible.
>>
>>Not sure about "stack" given that variables are in a flat global space.
> 
> 
> Even if the spec says that the scope of variables is global to the 
> query, in the case of optionals and nested optionals, some sort of 
> block-scoping of variables is required (see 5.6 section).

Section 5.6 is going to be "upgraded".  There will be a requirement that covers 
all the ways that ordering can occur (they all amount to variables being bound 
or unbound if thinking procedurally).  If there is ambiguity (e.g. two optionals 
using same variable) it's wrong.  It's detectable beofe execution.

[cwm seems to do much the same - not sure how it handles some more complex cases]

	Andy

 > This, in a
> way or the other (imagine a scenario of n>3 levels of nesting and 
> several combinations of patterns), it would require to keep track of 
> which variable is used in which block and its binding - and process it 
> accordingly. And order matters - then an implementation needs to 
> process blocks in a certain order to gain the correct answer.
> 
> Similarly, with constraints blocks, due they are meant to filter 
> results and do not bind variables, they are required to be evaluated in 
> certain "result context". Which would make the following query invalid
> 
> 
>>The order issue is a separate matter - I have been working on a
>>generalisation of the optional variables rule that also covers
>>constraints to get consistent answers. I have an action item to report
>>the ordering and optionals issue.
> 
> 
> good to know
> 
> 
>>The rule has to be that for constraints, if a variable is used
>>elsewhere, that part is executed first.  This naturally follows from 
>>the
>>declarative interpretation.
> 
> 
> this was very easy and systematic to do with RDQL, while now is much 
> more tricky due we do have nesting and grouping. And if so, this rule 
> should be clearly stated into the spec.
> 
> cheers
> 
> Alberto
> 
> -
> Alberto Reggiori, @Semantics S.R.L.
> www.asemantics.com
> 
> 
Received on Friday, 11 February 2005 11:48:55 GMT

This archive was generated by hypermail 2.3.1 : Tuesday, 26 March 2013 16:15:22 GMT