RE: a more general optional arcs implementation

> The interface to the solution set is:
> for each row
>   for each new solution
>     duplicate the row
>     add the bindings to the new row
> eliminate the original row

This is roughly what I do except (a) that I avoid the duplication because a
result row can point to a parent result row.  If there are no matching in
the optional the result is the original row (thisis what makes it OPTIONAL).
The saving in memory terms can be quite large.  Also, (b) I don't match
rows, I match large graph patterns as below.

Looking up a variable is cascaded up the tree until a variable with the
right name is found.  The tree depth is equal to the number of stages in the
query - I execute one query operation per graph pattern instance so in:


> ask (
>  ?n p1 B .
>  ?n p2 C .
>  ~?n p3 ?n2 )

SELECT *
WHERE 
  ?n p1 B .
  ?n p2 C .
OPTIONAL
  ?n p3 ?n2

that is two stages (the WHERE and the OPTIONAL clauses - boith full graph
patterns, not just single triples.).  Mutliple OPTIONALs are allowed - I
believe this can be made order independent with the rule that a variable:

1/ must be in the mandatory part (the WHERE) and any number of OPTIONALs
2/ In at most one OPTIONAL part 

(2) means it can't be bound in two separate OPTIONAL clauses.

Downside is that can't optionally query for one or the other as in

OPTIONAL
  (?x  foaf:name ?name)
OPTIONAL
  (?x  vcard:FN ?name)   # "FN" is formatted name

which is a bit like Alberto's

(?x (foaf:name | vcard:FN) ?name) 

except for the fact that Alberto's form implies one or the other must exist.

Rule 2 would means the optional clauses are independent and so can be issued
in any order or even in parallel.

	Andy

-------- Original Message --------
> From: Eric Prud'hommeaux <>
> Date: 29 June 2004 17:49
> 
> Rob, putting all the optional stuff together...:
> 
> From the code [1]:
> package W3C::Rdf::AlgaeCompileTree::Option;
> sub evaluateQTerm {
>     my ($self, $resultSet, $db, $modifier) = @_;
> 
>     for (my $e = $resultSet->elements; $e->hasMoreElements;) {
> 	my $row = $e->nextElement;
> 	my $miniResultSet = $row->makeResultSet;
> 	$self->{DECL}->evaluateQTerm($miniResultSet, $db, $modifier |
$OUTER);
> 	my $empty = 1;
> 	for (my $miniE = $miniResultSet->elements; $miniE->hasMoreElements;)
{
> 	    $empty = 0;
> 	    my $miniRow = $miniE->nextElement;
> 	    my $newRow = $row->duplicate;
> 	    $newRow->assumeNewBindings($miniRow);
> 	}
> 	if ($empty) {
> 	    $self->{DECL}->nullOut($row);
> 	} else {
> 	    $row->eliminate;
> 	}
>     }
> }
> 
> The interface to the solution set is:
> for each row
>   for each new solution
>     duplicate the row
>     add the bindings to the new row
> eliminate the original row
> 
> ala:
> sub evaluateQTerm {
>     for (my $e = $resultSet->elements; $e->hasMoreElements;) {
> 	my $row = $e->nextElement;
> 	for each solution
> 	    my $newRow = $row->duplicate;
> 	    $newRow->assumeNewBindings(solution);
> 	}
> 	$row->eliminate;
>     }
> }
> 
> package W3C::Rdf::AlgaeCompileTree::Decl;
> sub nullOut {
>     my ($self, $row) = @_;
>     for (my $i = 0; $i < $self->arity; $i++) {
> 	my $part = $self->getSlot($i);
> 	if ($part->isa('W3C::Rdf::AlgaeCompileTree::Var') &&
> 	    !defined $row->get($part->varIndex)) {
> 	    $part->absorb($Value_NULL, $row);
> 	}
>     }
> }
> 
> 
> Single Optional Test [2]:
> ns <http://example.org/n#>
> require <http://www.w3.org/2004/06/20-rules/#assert>
> assert (
>  A p1 B .
>  A p2 C .
>  A p3 D .
> 
>  B p1 B .
>  B p2 C )
> 
> ask (
>  ?n p1 B .
>  ?n p2 C .
>  ~?n p3 ?n2 )
> 
> collect (?n ?n2)
> 
> +------------------------+------------------------+
> >                       n|                      n2|
> > ------------------------|------------------------|
> > <http://example.org/n#B>|                    NULL|
> > <http://example.org/n#A>|<http://example.org/n#D>|
> +------------------------+------------------------+
> 
> 
> Order Dependence Test [3]:
> 
> ns <http://example.org/n#>
> require <http://www.w3.org/2004/06/20-rules/#assert>
> assert (
>  A p1 B .
>  A p2 C .
>  A p3 D .
> 
>  D p4 E .
>  E p5 F .
> 
>  D2 p4 E2 .
>  E2 p5 F2 )
> 
> ask (
>  ?n p1 B .
>  ?n p2 C .
>  ?n2 p4 ?n3 .
>  ?n3 p5 ?n4 .
>  ~?n ?po ?n2 )
> 
> collect (?n ?n2 ?po)
> 
>
+------------------------+-------------------------+------------------------
-+
> >                       n|                       n2|                   
> > po|
> >
------------------------|-------------------------|-------------------------
|
> > <http://example.org/n#A>|<http://example.org/n#D2>|                  
> > NULL| <http://example.org/n#A>|
> > <http://example.org/n#D>|<http://example.org/n#p3>|  
>
+------------------------+-------------------------+------------------------
-+
> 
> 
> Nested Optional Test [4]:
> 
> ns <http://example.org/n#>
> require <http://www.w3.org/2004/06/20-rules/#assert>
> assert (
>  A p1 B . # truncates on optional 1 term 1
>  A p2 C .
> # A p3 D .
> 
> # D p4 E .
> # D p5 F .
> # D p6 F .
> 
>  A2 p1 B . # truncates on optional term 2
>  A2 p2 C .
>  A2 p3 D2 .
> 
>  D2 p4 E2 .
> # D2 p5 F2 .
> # D2 p6 F2 .
> 
>  A3 p1 B . # eliminates second optional
>  A3 p2 C .
>  A3 p3 D3 .
> 
>  D3 p4 E3 .
>  D3 p5 F3 .
> # D3 p6 F3 .
> 
>  A4 p1 B . # has all arcs
>  A4 p2 C .
>  A4 p3 D4 .
> 
>  D4 p4 E4 .
>  D4 p5 F4 .
>  D4 p6 F4
> )
> 
> ask (
>  ?n p1 B .
>  ?n p2 C .
>  ~(?n ?p3 ?d .
>    ?d p4 ?e .
>    ?d p5 ?f .
>    ~?d p6 ?g))
> 
> collect (?n ?d ?e ?f ?g)
> 
> +----------...----+-----...----+-----...----+-----...----+------...----+
> >          ...   n|     ...   d|     ...   e|     ...   f|      ...   g|
> > ----------...----|-----...----|-----...----|-----...----|------...----|
> > <http://e...n#A>|     ...NULL|     ...NULL|     ...NULL|      ...NULL|
> > <http://ex...#A2>|     ...NULL|     ...NULL|     ...NULL|     
> > ...NULL| <http://ex...#A3>|<http...#D3>|<http...#E3>|<http...#F3>|   
> > ...NULL|
> > <http://ex...#A4>|<http...#D4>|<http...#E4>|<http...#F4>|<http:...#F4>|
> +----------...----+-----...----+-----...----+-----...----+------...----+
> 
> 
> I'd be keen on a screw case.
> 
> [1]
>
http://dev.w3.org/cvsweb/perl/modules/W3C/Rdf/AlgaeCompileTree.pm?rev=HEAD&c
ontent-type=text/x-cvsweb-markup
> 
> [2]
>
http://dev.w3.org/cvsweb/perl/modules/W3C/Rdf/test/Optional0-alg.sh?rev=HEAD
&content-type=text/x-cvsweb-markup
> 
> [3]
>
http://dev.w3.org/cvsweb/perl/modules/W3C/Rdf/test/Optional1-alg.sh?rev=HEAD
&content-type=text/x-cvsweb-markup
> 
> [4]
>
http://dev.w3.org/cvsweb/perl/modules/W3C/Rdf/test/Optional2-alg.sh?rev=HEAD
&content-type=text/x-cvsweb-markup
> 
> --
> -eric
> 
> office: +81.466.49.1170 W3C, Keio Research Institute at SFC,
>                         Shonan Fujisawa Campus, Keio University,
>                         5322 Endo, Fujisawa, Kanagawa 252-8520
>                         JAPAN
>         +1.617.258.5741 NE43-344, MIT, Cambridge, MA 02144 USA
> cell:   +1.857.222.5741 (does not work in Asia)
> 
> (eric@w3.org)
> Feel free to forward this message to any list for any purpose other than
> email address distribution.

Received on Wednesday, 30 June 2004 08:32:55 UTC