Re: Formal defintion of nested optionals

From: Seaborne, Andy <andy.seaborne@hp.com>
Date: Thu, 13 Apr 2006 15:26:32 +0100
Message-ID: <443E5F98.8030106@hp.com>
To: Jorge Pérez <jperez@utalca.cl>

```

Jorge Pérez wrote:
> Hi!, I try but I cannot find an answer to my question in the mailing
>
> 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

This archive was generated by hypermail 2.3.1 : Tuesday, 6 January 2015 20:52:07 UTC