Re: Formal defintion of nested optionals

Jorge Pérez wrote:
> Hi!, I try but I cannot find an answer to my question in the mailing
> list, sorry if the question was already answered.
> 
> The right answer for an optional pattern is very clear when there is no
> nesting, i.e. when one can easily read the formal defintion "S is a
> solution of OPT(A,B) if S is a...". I understand that OPT(A, B) refeers
> to
> 
> {
>   A .
>   OPTIONAL { B }
> }
> 
> But when there is a nested optional pattern it appears to be a confusion,
> for:
> 
> {
>   A .
>   OPTIONAL {
>     B .
>     OPTIONAL { C }
>   }
> }
> 
> What is the right answer? I think that there are at least two
> posibilities:
> 
> 1) one is to think in the composition of two binary operations, a
> binary operation between B and C, and a binary operation between
> A and the result of the previous operation, something like
> OPT(A, OPT(B, C)). The formal defintion in this case is clear
> followind the doc: S is a solution of OPT(A, OPT(B,C)) if S is a
> solution of A and of OPT(B, C) otherwise if S is a solution to A
> but not to A and OPT(B, C).

Yes - it's opt(A, opt(B,C)).

and   A OPTIONAL B OPTIONAL C is opt(opt(A,B), C)

> 
> 2) the other posibility is to think of the application of one single
> ternary operation, i.e. somethign like OPT(A, B, C). The formal
> definition here would be: S is a solution of OPT(A, B, C) if S is a
> solution of A and B and C, otherwise if S is a solution of A and B but
> not of C, otherwise if S is a solution to A but not to B.

Surely OPT(A, B, C) == OPT(A, OPT(B, C)) by that definition anyway?

> 
> In the last draft it seems that when defining formally the optional
> matching the editors agree with 1) for nesting when thay say
> "a combination of two patterns...". But when they are informally
> reading the examples of nested optional patterns I think they agree
> with 2). When looking in some implementations (SPARQLer for example)
> they seems to use 2. for evaluation...

SPARQLer (or rather ARQ, for that is the query engine being used) is doing (1) 
almost exactly: ARQ builds soltuion up, rather than consider all possibilities 
and narrow them down.

The in-memory algorithm is roughly:

1/ Calculate A to get an iterator of solutions to A

2/ For each solution to A,
    attempt to do OPTIONAL(Z)
    where Z is B OPTIONAL C
      either output the results of that or the original input solution from A.

3/ In doing Z, it's the same, take the input solution, solve B,
    attempt to solve C given the solution of A and B
    Output either the solution from A fed into B fed into C
    or just A fed into B

	Andy

> 
> What is the right formal definition of nested patterns?
> Thanks...
> 
> --------
> Jorge Pérez R.
> http://ing.utalca.cl/~jperez
> 
> -------------------------------------------------
> Este mensaje fue enviado por: http://webmail.utalca.cl
> 
>

Received on Thursday, 13 April 2006 14:26:57 UTC