a more general optional arcs implementation

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&content-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.