#Copyright Massachusetts Institute of technology, 1998.
#Written by Eric Prud'hommeaux for the World Wide Web Consortium

# $Id: SqlDB.pm,v 1.146 2007-08-14 22:00:11 eric Exp $

use strict;
require Exporter;

@W3C::Rdf::SqlDB::NoByPredicateException::ISA = qw(W3C::Util::Exception);
@W3C::Rdf::SqlDBAlgae::ISA = qw(W3C::Rdf::Algae);

package W3C::Rdf::SqlDB;
use vars qw($VERSION $REVISION $DSLI @ISA @EXPORT @EXPORT_OK @TODO);
$REVISION = '$Id: SqlDB.pm,v 1.146 2007-08-14 22:00:11 eric Exp $ ';
@ISA = qw(W3C::Rdf::RdfDB Exporter);
@EXPORT = qw();
$VERSION = 0.10;
$DSLI = 'adpO';
@TODO = ('implement processQuerySets to move join work to SQL', 
	 'addStatement sub functions for assertion functionality:',
	 '  - createMappedStatement', 
	 '  - triplesMatchingMappedNode (via expandMappedStatement)', 
	 '  - triplesMatchingMappedNode', 
	 );
my $PRECEDENCE_TABLE = {
    'W3C::Rdf::SqlDB::Conjunction' => 0, 
    'W3C::Rdf::SqlDB::Disjunction' => 1, 
    'W3C::Rdf::SqlDB::Negation' => 2, 
    'W3C::Rdf::SqlDB::Optional' => 3};
use W3C::Util::W3CDebugCGI qw(&escapeName &unescapeName); # for URL escaping
use W3C::Rdf::RdfDB;
use W3C::Util::Exception;
use W3C::Util::Properties;
use W3C::Database::DBIInterface;

# Import and overload names for classic database structure.
use W3C::Database::Structure;
@W3C::Rdf::SqlDB::Class::ISA = ('W3C::Database::Structure::Table');
sub W3C::Rdf::SqlDB::Class::getPropertyByName {return $_[0]->getFieldByName($_[1])}
@W3C::Rdf::SqlDB::Property::ISA = ('W3C::Database::Structure::Field');
@W3C::Rdf::SqlDB::UnknownRelationException::ISA = qw(W3C::Util::Exception);

# Properties coming from a relation/attribute

package W3C::Rdf::SqlDB::SymbolSet;
use W3C::Util::Exception;

sub new {
    my ($proto, $algae, $relay, $sibling) = @_;
    my $class = ref($proto) || $proto;
    my $self = {ALGAE => $algae};
    bless ($self, $class);
    $self->{RELAY} = $relay;
    $self->{SIBLING} = $sibling;
    $self->{SYMBOL_BINDINGS} = {};	# Table alias for a given symbol.
    $self->{ALIAS_INDEXES} = $relay ? {%{$relay->{ALIAS_INDEXES}}} : {};	# Next number for a table alias.
    $self->{TABLE_ALIASES} = [];	# FROM foo AS bar
    return $self;
}

sub _ensureTableAliasForSymbol {
    my ($self, $table, $term, $qp, $binder, $outer, $allowGenericNode, $prefix) = @_;

    # See if there's a table alias already associated with this symbol
    if (my $boundAliasPair = $self->_getTableAliasForSymbol($qp)) {
	return ($boundAliasPair->[0], undef);
    } else {
	my ($boundAlias, $wheres) = $self->_getNewTableAlias($table, $qp, $binder, $outer, $allowGenericNode, $prefix, 0);
	$self->{SYMBOL_BINDINGS}{$qp->symbol} = [$boundAlias, $table];
	return ($boundAlias, $wheres);
    }
}

sub _getTableAliasForSymbol {
    my ($self, $qp) = @_;
    if ($self->{RELAY} && $self->{RELAY}{SYMBOL_BINDINGS}{$qp->symbol}) {
	return $self->{RELAY}{SYMBOL_BINDINGS}{$qp->symbol};
    }
    return $self->{SYMBOL_BINDINGS}{$qp->symbol};
}

sub _getNewTableAlias {
    my ($self, $table, $qp, $binder, $outer, $allowGenericNode, $prefix, $dontConstrain) = @_;

    # Pick up from older and wiser sibling.
    if ($self->{SIBLING} && $self->{SIBLING}->_getTableAliasForSymbol($qp)) {
	$self->{ALIAS_INDEXES}{$table} = $self->{SIBLING}{ALIAS_INDEXES}{$table};
	my ($boundAlias, $wheres) = $self->{SYMBOL_BINDINGS}{$qp->symbol};
	$self->{SYMBOL_BINDINGS}{$qp->symbol} = [$boundAlias, $wheres];
	return [$boundAlias, $wheres];
    }

    # Invent it for ourselves.
    my $maxForTable = $self->{ALIAS_INDEXES}{$table};
    if (!defined $maxForTable) {
	$maxForTable = $self->{ALIAS_INDEXES}{$table} = 0;
    }
    my $boundAlias = "${table}_$maxForTable";
    $self->{ALIAS_INDEXES}{$table}++;
    push (@{$self->{TABLE_ALIASES}}, [$table, $boundAlias]);

    my $wheres;
    if ($dontConstrain) {
	# Some other constraint will bind this table to the static value.
    } else {
	if ($qp->isa('W3C::Rdf::AlgaeCompileTree::Members')) {
	    &throw(new W3C::Util::ProgramFlowException());
	} elsif ($qp->isa('W3C::Rdf::AlgaeCompileTree::StaticPOS')) {
	    $wheres = $self->{ALGAE}->_constrainKey($qp, $boundAlias, $table, $outer, $allowGenericNode);
	} elsif (defined $qp->varIndex) {
	    $self->{ALGAE}->_selectKey($table, $boundAlias, $qp, $binder, $prefix);
	}
    }
    return ($boundAlias, $wheres);
}

sub getAliases {@{$_[0]->{TABLE_ALIASES}}}

sub mergeDisjunction {
    my ($self, $l, $r) = @_;
    my $lAliases = {map {$_->[1], $_->[0]} @{$l->{TABLE_ALIASES}}};
    my $rAliases = {map {$_->[1], $_->[0]} @{$r->{TABLE_ALIASES}}};
    my $lBindings = &_symbols($l);
    my $rBindings = &_symbols($r);
    foreach my $la (keys %$lAliases) {
	if (exists $rAliases->{$la}) {
	    push (@{$self->{TABLE_ALIASES}}, [$lAliases->{$la}, $la]);
	    delete $rAliases->{$la};
	    foreach my $lb (keys %{$lBindings->{$la}}) {
		if ($rBindings->{$la}{$lb}) {
		    $self->_addBinding($la, $lb, $lBindings->{$la}{$lb});
		    print "matched: $la $lb\n";
		    delete $rBindings->{$la}{$lb};
		} else {
		    $self->_addBinding($la, $lb, $lBindings->{$la}{$lb});
		    print "left only2: $la $lb\n";
		}
	    }
	} else {
	    print "left only: $la\n";
	}
    }
    foreach my $ra (keys %$rAliases) {
	print "right only: $ra\n";
    }
    foreach my $rb (keys %$rBindings) {
	foreach my $ra (keys %{$rBindings->{$rb}}) {
	    print "right only2: $rb $ra\n";
	}
    }
}
sub mergeDisjunction {
    my ($self, $l, $r) = @_;
    foreach my $symbol (keys %{$l->{SYMBOL_BINDINGS}}) {
	my ($alias, $table) = @{$l->{SYMBOL_BINDINGS}{$symbol}};
	$self->_addBinding($alias, $symbol, $table);
    }
    foreach my $pair (@{$l->{TABLE_ALIASES}}) {
	push (@{$self->{TABLE_ALIASES}}, [@$pair]);
    }
    foreach my $table (keys %{$l->{ALIAS_INDEXES}}) {
	$self->{ALIAS_INDEXES}{$table} = $l->{ALIAS_INDEXES}{$table};
    }
}
sub _symbols {
    my ($path) = @_;
    my $ret = {};
    foreach my $symbol (keys %{$path->{SYMBOL_BINDINGS}}) {
	my ($alias, $table) = @{$path->{SYMBOL_BINDINGS}{$symbol}};
	$ret->{$alias}{$symbol} = $table;
#	if ($ret->{$alias}) {
#	    push (@{$ret->{$alias}}, [$symbol, $table]);
#	} else {
#	    $ret->{$alias} = [$symbol, $table];
#	}
    }
    return $ret;
}
sub _addBinding {
    my ($self, $alias, $symbol, $table) = @_;
    if ($self->{SYMBOL_BINDINGS}{$symbol}) {
	push (@{$self->{SYMBOL_BINDINGS}{$symbol}}, [$alias, $table]);
    } else {
	$self->{SYMBOL_BINDINGS}{$symbol} = [$alias, $table];
    }
}

sub toString {
    my ($self) = @_;
    my @ret;
    foreach my $table (keys %{$self->{ALIAS_INDEXES}}) {
	push (@ret, "$table: $self->{ALIAS_INDEXES}{$table}\n");
    }
    foreach my $alias (@{$self->{TABLE_ALIASES}}) {
	push (@ret, "$alias->[0], $alias->[1]\n");
    }
    foreach my $symbol (keys %{$self->{SYMBOL_BINDINGS}}) {
	push (@ret, "$symbol: $self->{SYMBOL_BINDINGS}{$symbol}->[0], $self->{SYMBOL_BINDINGS}{$symbol}->[1]\n");
    }
    return wantarray ? @ret :  join("\n", @ret);
}

# Logic for allocating bindings (Literal, Node, Foreign key targets) in SELECT.
package W3C::Rdf::SqlDB::Binder;

sub new {
    my ($proto, $algae) = @_;
    my $class = ref($proto) || $proto;
    my $self = {BINDINGS => []};

    # Variable, table, column state:
    $self->{SYMBOLS} = new W3C::Rdf::SqlDB::SymbolSet($algae, undef, undef);
    $self->{ORDER} = [];

    bless ($self, $class);
    return $self;
}

sub addBinding {
    my ($self, $binding) = @_;
    push (@{$self->{BINDINGS}}, $binding);
}

sub getBindings {
    my ($self) = @_;
    return $self->{BINDINGS};
}

sub getSymbols {
    my ($self) = @_;
    return $self->{SYMBOLS};
}

sub getAliases {
    my ($self) = @_;
    return $self->{SYMBOLS}->getAliases();
}

# Associate a QueryPiece symbol with an entity identified by a primary key in a
# table.

sub _ensureTableAliasForSymbol {
    my ($self, $table, $term, $qp, $binder, $outer, $allowGenericNode, $prefix) = @_;
    return $self->{SYMBOLS}->_ensureTableAliasForSymbol($table, $term, $qp, $binder, $outer, $allowGenericNode, $prefix);
}

sub _getTableAliasForSymbol {
    my ($self, $qp) = @_;
    return $self->{SYMBOLS}->_getTableAliasForSymbol($qp);
}
sub _getNewTableAlias {
    my ($self, $table, $qp, $binder, $outer, $allowGenericNode, $prefix, $dontConstrain) = @_;
    return $self->{SYMBOLS}->_getNewTableAlias($table, $qp, $binder, $outer, $allowGenericNode, $prefix, $dontConstrain);
}

sub toString {
    my ($self) = @_;
    my @ret;
    for (my $i = 0; $i < @{$self->{BINDINGS}}; $i++) {
	my $binding = $self->{BINDINGS}[$i];
	push (@ret, "BINDINGS[$i]:");
	map {push (@ret, "  $_")} $binding->toString;
    }
    push (@ret, "SYMBOLS: $self->{SYMBOLS}");
    map {push (@ret, "  $_")} $self->{SYMBOLS}->toString;
    return wantarray ? @ret :  join("\n", @ret);
}

# Logic for allocating bindings (Literal, Node, Foreign key targets) in SELECT.
package W3C::Rdf::SqlDB::DisjunctionBinder;

sub new {
    my ($proto, $algae, $parent) = @_;
    my $class = ref($proto) || $proto;
    my $self = {PARENT => $parent, ALGAE => $algae};

    # @@@ note new aliases and wheres. !!!!
    $self->{LSymbols} = $self->{SYMBOLS} = new W3C::Rdf::SqlDB::SymbolSet($self->{ALGAE}, $self->{PARENT}->getSymbols(), undef);

    bless ($self, $class);
    return $self;
}
sub reuseMode {
    my ($self) = @_;
    $self->{RSymbols} = $self->{SYMBOLS} = new W3C::Rdf::SqlDB::SymbolSet($self->{ALGAE}, $self->{PARENT}->getSymbols(), undef, $self->{LSymbols});
}
sub addBinding { # just store in the parent's bindings for now.
    my ($self, $binding) = @_;
    $self->{PARENT}->addBinding($binding);
}
sub _ensureTableAliasForSymbol {
    my ($self, $table, $term, $qp, $binder, $outer, $allowGenericNode, $prefix) = @_;
    return $self->{SYMBOLS}->_ensureTableAliasForSymbol($table, $term, $qp, $binder, $outer, $allowGenericNode, $prefix);
}
sub _getTableAliasForSymbol {
    my ($self, $qp) = @_;
    return $self->{SYMBOLS}->_getTableAliasForSymbol($qp);
}
sub _getNewTableAlias {
    my ($self, $table, $qp, $binder, $outer, $allowGenericNode, $prefix, $dontConstrain) = @_;
    return $self->{SYMBOLS}->_getNewTableAlias($table, $qp, $binder, $outer, $allowGenericNode, $prefix, $dontConstrain);
}
sub finishReuse {
    my ($self) = @_;
    $self->{PARENT}->getSymbols()->mergeDisjunction($self->{LSymbols}, $self->{RSymbols});
    return undef;
}

sub toString {
    my ($self) = @_;
    my @ret;
    for (my $i = 0; $i < @{$self->{BINDINGS}}; $i++) {
	my $binding = $self->{BINDINGS}[$i];
	push (@ret, "BINDINGS[$i]:");
	map {push (@ret, "  $_")} $binding->toString;
    }
    push (@ret, "SYMBOLS: $self->{SYMBOLS}");
    map {push (@ret, "  $_")} $self->{SYMBOLS}->toString;
    return wantarray ? @ret :  join("\n", @ret);
}

package W3C::Rdf::SqlDB::Property;
use W3C::Util::Exception;
sub new {
    my ($proto, $table, $name, $default, $type, $size, $requires) = @_;
    my $class = ref($proto) || $proto;
    my $self = $class->SUPER::new($table, $name, $default, $type, $size);
    $self->{Requires} = $requires;
    return $self;
}

sub getObjectDatatype {
    my ($self) = @_;
    return $self->{TYPE} == 10 ? 'http://www.w3.org/2001/XMLSchema#dateTime' : undef;
}
    # The property knows which parts of speach imply bindings of which tables.
    # For instance, the breadfruit [1] property OrderTracking_Orders#product
    # would look for an Orders alias bound to $s. Orders#product has a target
    # for $o so a Products alias will bound to $o and that alias will be
    # constrained $o.primaryKey=$s.product.

    # A flatbread [2] predicate, foo#p1, would look for a __Holds__ alias for
    # $r.  If $r were not set, it would make a new alias for this graph segment.
    # foo#p1 is a FeDeRate normal1 [3] predicate and therefor has targets for $s
    # and $o so __Nodes__ aliass will be bound to both.

    # At the end of the query walk, some variables may be bound to multiple
    # aliases. For instance, a variable may be bound to a breadfruit table and a
    # fruitbread __Holds__ alias. Additional joins are added to connect these
    # tables. For instance, looking for breadfruit and flatbread predicates will
    # add a JOIN with a constraint like:
    #   __Nodes___0.tableName="Orders" AND __Nodes___0.tableRowId=concat("id=", 5)

    # Repeated properties and products of rules require specialize auxilliary
    # many to many tables. These require some rewrite to change the constraints
    # and selects on the nonexistent attribute in the natural entity table [4]
    # to the a JOIN to the corresponding many to many table.

    # [1] 
    # [2] 
    # [3] 
    # [4] , pointer to a description of the natural entity concept
sub toString {$_[0]->{TABLE}->getName.'.'.$_[0]->getName}
sub processAssertion {
    my ($self, $triple, $algae, $attribution) = @_;
    my ($p, $s, $o) = ($triple->getSlot(0), $triple->getSlot(1), $triple->getSlot(2));
    &throw(new W3C::Util::NotImplementedException());
}

sub processMatch {
    my ($self, $term, $binder, $cell, $algae, $disjunction, $negation, $outer, $attribution) = @_;
    my ($p, $s, $o) = ($term->getSlot(0), $term->getSlot(1), $term->getSlot(2));
    my $field = $self->getName;
    my $table = $self->getTable->getName();
    if ($self->{Requires}) {
	&throw(new W3C::Util::Exception(-message => "you need to be \"$self->{Requires}\" to use the predicate $table.$field"));
    }
    my $entityAlias = undef;

    my $cWheres = []; my $tWheres;

    if ($self == $algae->{SUBJECT_PROPERTY}) {
	($entityAlias, $tWheres) = $binder->_ensureTableAliasForSymbol($table, $term, $s, $binder, $outer, 0, undef);
    } else {
	($entityAlias, $tWheres) = $binder->_ensureTableAliasForSymbol($table, $term, $s, $binder, $outer, 0, undef);
    }
    push (@$cWheres, $tWheres);

    if (my $t = $self->getTarget) {
	my $targetAlias;
	($targetAlias, $tWheres) = $binder->_ensureTableAliasForSymbol($t->getTable->getName, $term, $o, $binder, $outer, 0, undef);
	push (@$cWheres, $tWheres);
	push (@$cWheres, $algae->_addWhereField($entityAlias, $field, '=', $targetAlias, $t->getName, $term, $outer));
    } elsif ($o->isa('W3C::Rdf::AlgaeCompileTree::Members')) {
	&throw(new W3C::Util::ProgramFlowException());
    } elsif ($o->isa('W3C::Rdf::AlgaeCompileTree::StaticPOS')) {
	push (@$cWheres, $algae->_addWhereConst($entityAlias, $field, '=', $o->symbol, $term, $outer));
    } else {
	# VariableQueryPiece in a scalar field.
	# Either _addSelect("$entityAlias.$field", $o->symbol."_$field", $o->existential, "\n")
	# or     $objectConstraint = _addWhereField($entityAlias, $field, '=', $firstAlias, $firstField, $o, $outer)
	my $datatype = $self->getObjectDatatype();
	if ($datatype) {
	    $datatype = $algae->{-atomDictionary}->getUri($datatype);
	}
	push (@$cWheres, $algae->_bindFieldToVariable($entityAlias, $field, $datatype, $term, $o, $binder, $outer));
    }
    my $ret;

    foreach my $constraint (@{$term->{CONSTRAINTS}}) {
	$constraint->toSQL($algae, $term, $cWheres, $outer);
    }

    # This gives a nice right-extended tree.
    foreach my $where (reverse @$cWheres) {
	$ret = $ret && $where ? $where->newConjunction($ret) : ($ret || $where);
    }
    return $ret;
}

# Properties which are handled in a generic triple store.
# Every ref to __Holds__,__Nodes__ table must getNewTableAlias (except for ORs).

@W3C::Rdf::SqlDB::HoldsProperty::ISA = ('W3C::Rdf::SqlDB::Property');
package W3C::Rdf::SqlDB::HoldsProperty;
use W3C::Util::Exception;
use Digest::MD5 qw(md5_hex);

# DEBUGGING:
use vars qw($INTEGRITY_CHECK);
$INTEGRITY_CHECK = 1;

use vars qw($CACHE_nodeToDbId $CACHE_dbIdToNode 
	    $CACHE_attributionToDbId $CACHE_dbIdToAttribution 
	    $CACHE_attrListToDbId $CACHE_dbIdToAttrList 
	    $PREFIX_ALIAS);
$PREFIX_ALIAS = 1;

# Variables to describe the hash2node function.  Current implementation uses
# hex() function so check if the size goes above 32 bits. Check with
# `unpack('D', pack('h*', 0xnum))` where num is the largest integer you can
# get. If you get "Invalid type in unpack: 'D'", implement a hex() function.

$CACHE_nodeToDbId = {};
$CACHE_dbIdToNode = {};
$CACHE_attributionToDbId = {};
$CACHE_dbIdToAttribution = {};
$CACHE_attrListToDbId = {};
$CACHE_dbIdToAttrList = {};

sub getObjectDatatype {
    my ($self) = @_;
    return undef;
}

sub ensureNode {
    my ($self, $node, $algae) = @_;
    my $ret = $CACHE_nodeToDbId->{$node};
    if (!$ret) {
	if ($node->isa('W3C::Rdf::Uri') || 
	    $node->isa('W3C::Rdf::AlgaeCompileTree::Url')) {
	    my $uri = $node->isa('W3C::Rdf::Uri') ? $node->getUri : $node->getUrl;
	    eval {
		my $tableStr;
		my $constraints = $algae->_decomposeUniques($uri, undef, \ $tableStr);
		my $value = join(',', $tableStr, @$constraints);
		my $hash = &_hashNode($value);
		my $rows = [];
		my $constraintStr = $algae->escape($value);
		my $libCode = $algae->executeArrayQuery($rows, "SELECT __Nodes__.id
FROM __Nodes__,$tableStr
WHERE __Nodes__.type=\"table\"
  AND __Nodes__.str=$constraintStr
  AND ".join("\n  AND ", map {"$tableStr.$_"} @$constraints));
		if (@$rows == 0) {
		    eval {
			$algae->executeUpdate("INSERT INTO $tableStr SET ".join(',', @$constraints));
		    }; if ($@) {if (my $ex = &catch('W3C::Database::DBIInterface::DuplicateKeyException')) {
			# There already was one, carry on.
		    } else {
			&throw();
		    }}
		    $ret = &_ensureNode2($algae, 'table', $value, $hash);
		} elsif (@$rows == 1) {
		    $ret = $rows->[0][0];
		} else {
		    &throw(new W3C::Util::Exception(-message => "$uri matched @$rows tuples (should be 1 or 0)"));
		}
	    }; if ($@) {if (my $ex = &catch('W3C::Rdf::SqlDB::UnknownRelationException')) {
		$ret = &_ensureNode3($algae, 'uri', $uri);
	    } elsif (my $ex = &catch('W3C::Util::Exception')) {
		&throw($ex);
	    } else {
		&throw();
	    }}
	} elsif ($node->isa('W3C::Rdf::String')) {
	    my ($tnode, $tnodec, $tid);
	    if (my $dt = $node->getDatatype) {
		($tid, $tnode, $tnodec) = $self->ensureNode($node->getDatatype, $algae);
	    }
	    my $string = $tid.($node->getEncoding eq 'XML' ? 'X' : 'P').$node->getLang.':'.$node->getString;
	    $ret = &_ensureNode3($algae, 'literal', $string, $tid);
	} elsif ($node->isa('W3C::Rdf::BNode')) {
	    my $a = $self->_ensureAttribution($node->getAttribution, $algae);

	    # Encoded str is f(nodeId, uri). Could be f($node->getId, $a) instead...
	    my $str = $node->getId.':'.$node->getUri->getUri;
	    my $hash = &_hashNode($str);

	    if ($INTEGRITY_CHECK) {
		# Integrity check: there should be no such existing bnodes.
		my $rows = [];
		my $libCode = $algae->executeArrayQuery($rows, "SELECT __Nodes__.id
FROM __Nodes__
WHERE __Nodes__.type=\"bnode\"
  AND __Nodes__.hash=\"$hash\"");
		if ((my $count = @$rows) != 0) {
		    &throw(new W3C::Util::Exception(-message => "$str matched $count tuples (should be 0)"));
		}
	    }

	    $ret = &_ensureNode2($algae, 'bnode', $str, $hash, $a);
	} else {
	    &throw(new W3C::Util::ProgramFlowException(-state => "$node"));
	}
	$CACHE_nodeToDbId->{$node} = $ret;
	$CACHE_dbIdToNode->{$ret} = $node;
    }
    return $ret;
}

sub _ensureNode3 {
    my ($algae, $type, $str, $attribOrDT) = @_;
    my $hash = &_hashNode($str);
    my $rows = [];
    my $libCode = $algae->executeArrayQuery($rows, "SELECT __Nodes__.id
FROM __Nodes__
WHERE __Nodes__.type=\"$type\"
  AND __Nodes__.hash=\"$hash\"");
    if (@$rows == 0) {
	return &_ensureNode2($algae, $type, $str, $hash, $attribOrDT);
    } elsif (@$rows == 1) {
	return $rows->[0][0];
    } else {
	&throw(new W3C::Util::Exception(-message => "$type \"$str\" matched @$rows tuples (should be 1 or 0)"));
    }
}

sub _ensureNode2 {
    my ($algae, $type, $value, $hash, $attribution) = @_;
    &utf8::decode($value);
    my $valueStr = $algae->escape($value);
    my $nodec = 0;
    my $attribConstraintStr = $attribution ? ", attribOrDT=\"$attribution\"" : '';
    my $BIG_THRESHOLD = 255;
    if (length($value) > $BIG_THRESHOLD) {
	my ($libCode, $big);
	eval {
	    ($libCode, $big) = $algae->executeUpdate("INSERT INTO __Big__ SET hash=\"$hash\", str=$valueStr");
	}; if ($@) {if (my $ex = &catch('W3C::Database::DBIInterface::DuplicateKeyException')) {
	    # There already was one, find it.
	    $big = $algae->executeSingleQuery("SELECT id FROM __Big__ WHERE hash=\"$hash\"");
	} else {
	    &throw();
	}}
	$valueStr = "\"SELECT str FROM __Big__ WHERE id=$big\", big=$big";
    }

    # Do this in a while in case someone else inserts after we select the max(nodec);
    while ($nodec <= 10) { # @@@ tmp retries
	my ($libCode, $id);
	eval {
	    ($libCode, $id) = $algae->executeUpdate("INSERT INTO __Nodes__ SET type=\"$type\", hash=\"$hash\", str=$valueStr$attribConstraintStr");
	    return;
	}; if ($@) {if (my $ex = &catch('W3C::Database::DBIInterface::DuplicateKeyException')) {
	    # There already was one, find the max collision count.
	    my $tmp = $algae->executeSingleQuery("SELECT max(nodec)
FROM __Nodes__
WHERE hash=\"$hash\" AND type=\"$type\"");
	    if (!defined $tmp) {
		&throw($ex);
	    } elsif ($tmp == $nodec) {
		$nodec = $tmp+1
	    } else {
		&throw($ex);
	    }
	} else {
	    &throw();
	}} else {
	    return $id;
	}
    }
    &throw(new W3C::Util::Exception(-message => "out of room to express \"$type\" \"$valueStr\" -- talk about something else!"));
}

sub _ensureAttribution {
    my ($self, $node, $algae) = @_;

    my $ret = $CACHE_attributionToDbId->{$node};
    if ($algae->refreshNode($node) || !$ret) {
	# May have to clear out existing data for this Attribution.
	my $clear = $node->isa('W3C::Rdf::Attribution::GroundFact'); # && !defined $node->getParent;
	my $docId = $self->ensureNode($node->getSource, $algae);
	my ($authConstraintStr, $authInsertStr) = ('', '');
	if ($node->getAuth) {
	    my $authId = $self->ensureNode($node->getAuth, $algae);
	    $authConstraintStr = "
  AND auth=$authId";
	    $authInsertStr = ", auth=$authId";
	}
	my $rows = [];
	my $libCode = $algae->executeArrayQuery($rows, "SELECT __Attributions__.id
FROM __Attributions__
WHERE __Attributions__.doc=$docId$authConstraintStr");
	if (@$rows == 0) {
	    my $type = 'source'; # !!! check type of Attribution
	    ($libCode, $ret) = $algae->executeUpdate("INSERT INTO __Attributions__ SET type=\"$type\", doc=$docId, created=now()$authInsertStr");
	} elsif (@$rows == 1) {
	    $ret = $rows->[0][0];
	    $libCode = $algae->executeUpdate("UPDATE __Attributions__ SET modified=NULL WHERE id=$ret"); # tickle the last modified time
	    if ($clear) {
		$algae->emptyAttribution($ret);
		delete $CACHE_attrListToDbId->{$ret};
	    }
	} else {
	    &throw(new W3C::Util::Exception(-message => $node->getUri." matched @$rows tuples (should be 1 or 0)"));
	}
	$CACHE_attributionToDbId->{$node} = $ret;
	$CACHE_dbIdToAttribution->{$ret} = $node;
    }
    return $ret;
}

# Handle translation from an array to a RDB one-to-many table.
sub _ensureAttributionList {
    my ($self, $attribIds, $algae) = @_;

    my $hashKey = join(',', sort @$attribIds);
    my $ret = $CACHE_attrListToDbId->{$hashKey};
    if (!$ret) {
	my (@aliases, @constraints);
	for (my $i = 0; $i < @$attribIds; $i++) {
	    my $id = $attribIds->[$i];

	    my $constraint = $i == 0 ? "a$i.a=$id" : "a$i.a=$id AND a$i.listId=a0.listId";

	    push (@constraints, $constraint);
	}

	my $cnstStr = join ("\n  AND ", @constraints);

	my $asStr = join (", \n            ", map {"__AttrLists__ AS a$_ WRITE"} (0..@$attribIds-1));
	$algae->executeUpdate('LOCK TABLES '.join (", \n            ", map {"__AttrLists__ AS a$_ WRITE"} (0..@$attribIds-1)));

	# Find listIds that have at least these members.
	my @rows;
	$algae->executeArrayQuery(\@rows, "SELECT a0.listId\n  FROM ".join (", \n       ", map {"__AttrLists__ AS a$_"} (0..@$attribIds-1))." WHERE $cnstStr");

	if (@rows) {
	    # Find one that has the same number of members.
	    $algae->executeArrayQuery(\@rows, "SELECT listId, COUNT(*)\n  FROM __AttrLists__ AS a0\n WHERE listId IN (".join(',', map {$_->[0]} @rows).")\n GROUP BY listId");
	    foreach my $row (@rows) {
		if ($row->[1] = @$attribIds) {
		    $ret = $row->[0];
		    last;
		}
	    }
	}

	# If we didn't find one, we have to create it.
	if (!$ret) {
	    $ret = $algae->executeSingleQuery('SELECT MAX(listId) FROM __AttrLists__ AS a0')+1;
	    for (my $i = 0; $i < @$attribIds; $i++) {
		my $id = $attribIds->[$i];
		$algae->executeUpdate('UNLOCK TABLES'); # !!! This is bogus
		$algae->executeUpdate('LOCK TABLES __AttrLists__ WRITE');
		$algae->executeUpdate("INSERT INTO __AttrLists__ (listId, a) VALUES ($ret, $id)");
	    }
	}

	$algae->executeUpdate('UNLOCK TABLES');
	$CACHE_attrListToDbId->{$hashKey} = $ret;
#	$CACHE_dbIdToAttrList->{$ret} = $list; # !!!
    }
    return $ret;
}

use warnings FATAL => 'overflow'; # Little warning to those who try to increase
				  # the node identifier size without checking
				  # hex() on their system. See above.
sub _hashNode {
    my ($value) = @_;
    &utf8::encode($value);
    my $hash = &md5_hex($value);
    return $hash;
}

sub processAssertion {
    my ($self, $triple, $algae, $attribution) = @_;

    my $pId = $self->ensureNode($triple->getPredicate, $algae);
    my $sId = $self->ensureNode($triple->getSubject, $algae);
    my $oId = $self->ensureNode($triple->getObject, $algae);
    my $attribIds = [$self->_ensureAttribution($attribution, $algae)];

    my @alreadyThere;
    # @@@ cache-able information
    $algae->executeArrayQuery(\@alreadyThere, "
SELECT al.a
  FROM __Holds__ AS t
       INNER JOIN __AttrLists__ AS al ON t.a=al.listId
 WHERE p=$pId AND s=$sId AND o=$oId");
    push (@$attribIds, map {$_->[0]} @alreadyThere);
    my $aInt = $self->_ensureAttributionList($attribIds, $algae);

    $algae->executeUpdate("REPLACE INTO __Holds__ SET p=$pId, s=$sId, o=$oId, a=$aInt");
    return $triple;
}

sub processDeletion {
    my ($self, $triple, $algae, $attribution) = @_;

    my $pId = $self->ensureNode($triple->getPredicate, $algae);
    my $sId = $self->ensureNode($triple->getSubject, $algae);
    my $oId = $self->ensureNode($triple->getObject, $algae);
    my $attribId = $self->_ensureAttribution($attribution, $algae);

    my @alreadyThere;
    # @@@ cache-able information
    $algae->executeArrayQuery(\@alreadyThere, "
SELECT al.a
  FROM __Holds__ AS t
       INNER JOIN __AttrLists__ AS al ON t.a=al.listId
 WHERE p=$pId AND s=$sId AND o=$oId");
    if (@alreadyThere < 1) {
	# Failed to match any triples.
    } elsif (@alreadyThere == 1) {
	# Only one in the DB.
	$algae->executeUpdate("DELETE FROM __Holds__ WHERE p=$pId AND s=$sId AND o=$oId");
    } else {
	# Find a new AttributionList without $attribution in it.
	my $attribIds = [grep {$_ != $attribId} map {$_->[0]} @alreadyThere];
	my $aInt = $self->_ensureAttributionList($attribIds, $algae);

	$algae->executeUpdate("REPLACE INTO __Holds__ SET p=$pId, s=$sId, o=$oId, a=$aInt");
    }
    return $triple;
}

sub processMatch {
    my ($self, $term, $binder, $cell, $algae, $disjunction, $negation, $outer, $attribution) = @_;
    my ($p, $s, $o) = ($term->getSlot(0), $term->getSlot(1), $term->getSlot(2));
    my $sTable = $self->getTable->getName;
    my $field = $self->getName;

    my $cWheres = [];
    my ($statementsAlias, $tWheres) = $binder->_getNewTableAlias('__Holds__', $s, $binder, $outer, 1, $PREFIX_ALIAS, 1);
    push (@$cWheres, $tWheres);
    $algae->_selectAttribution($statementsAlias, $term, $binder);
    $algae->_selectStatementId($statementsAlias, $term, $binder);

    # Always at least need a Statements and two __Nodes__ aliases.
    my ($pAliasIds, $sAliasIds, $oAliasIds);
    ($pAliasIds, $tWheres) = &getNodeAlias($p, $binder, $algae, $term, $outer);
    push (@$cWheres, $tWheres);
    ($sAliasIds, $tWheres) = &getNodeAlias($s, $binder, $algae, $term, $outer);
    push (@$cWheres, $tWheres);
#	($targetAlias, $tWheres) = $binder->_ensureTableAliasForSymbol($t->getTable->getName, $term, $o, $binder, $outer, 0, undef);
    push (@$cWheres, $algae->_addWhereField($statementsAlias, 'p', '=', $pAliasIds, 'id', $term, $outer)); # need to bind multiple fields with only one reaches
    push (@$cWheres, $algae->_addWhereField($statementsAlias, 's', '=', $sAliasIds, 'id', $term, $outer)); # need to bind multiple fields with only one reaches
    if ($o->isa('W3C::Rdf::AlgaeCompileTree::Members')) {
	push (@$cWheres, $tWheres);
	my ($alias1, undef) = $binder->_getNewTableAlias('__Lists__', $o, $binder, $outer, 1, $PREFIX_ALIAS, 1);
	($oAliasIds, $tWheres) = &getNodeAlias($o->{VAR}, $binder, $algae, $term, $outer); # !!! boundries
	my $wheres4 = $algae->_addWhereField($alias1, 'first', '=', $oAliasIds, 'id', $term, $outer);
	push (@$cWheres, $wheres4);
	$oAliasIds = $alias1;
	push (@$cWheres, $algae->_addWhereField($statementsAlias, 'o', '=', $oAliasIds, 'list', $term, $outer)); # need to bind multiple fields with only one reaches
	push (@{$binder->{ORDER}}, "$alias1.g");
    } else {
	($oAliasIds, $tWheres) = &getNodeAlias($o, $binder, $algae, $term, $outer);
	push (@$cWheres, $tWheres);
	push (@$cWheres, $algae->_addWhereField($statementsAlias, 'o', '=', $oAliasIds, 'id', $term, $outer)); # need to bind multiple fields with only one reaches
    }

#    push (@$cWheres, $algae->_bindFieldToVariable($statementsAlias, 'o', $oAliasIds, 'id', $term, $outer)); # need to bind multiple fields with only one reaches
    if ($o->isa('W3C::Rdf::AlgaeCompileTree::Var')) {
	$algae->{SCALAR_REFERENCES}{$o->symbol} = [$oAliasIds, 'str']; # !!! boundries
    }

    if ($attribution) {
	my $wheres4 = $algae->_addWhereField($statementsAlias, 'a', '=', $attribution->[0], 'listId', $term, $outer);
	push (@$cWheres, $wheres4);
	if ($attribution->[1]) {
	    push (@$cWheres, @{$attribution->[1]});
	    $attribution->[1] = undef;
	}
    }

    foreach my $constraint (@{$term->{CONSTRAINTS}}) {
	if ($constraint->{EXPR}->isa('W3C::Rdf::AlgaeCompileTree::Eq')) {
	    my $l = $constraint->{EXPR}{L};
	    my $r = $constraint->{EXPR}{R};
	    if ($l->isa('W3C::Rdf::AlgaeCompileTree::KeyName')) {
		if ($r->isa('W3C::Rdf::AlgaeCompileTree::Url')) {
		    if ($l->{VARNAME} eq 'ATTRIB') {
			my ($alias1, undef) = $binder->_getNewTableAlias('__AttrLists__', $s, $binder, $outer, 1, $PREFIX_ALIAS, 1);
			my $wheres4 = $algae->_addWhereField($statementsAlias, 'a', '=', $alias1, 'listId', $term, $outer);
			push (@$cWheres, $wheres4);
			my ($alias2, undef) = $binder->_getNewTableAlias('__Attributions__', $s, $binder, $outer, 1, $PREFIX_ALIAS, 1);
			my $wheres5 = $algae->_addWhereField($alias1, 'a', '=', $alias2, 'id', $term, $outer);
			push (@$cWheres, $wheres5);
			my ($alias3, $wheres3) = $binder->_getNewTableAlias('__Nodes__', $r, $binder, $outer, 1, $PREFIX_ALIAS, 0);
			push (@$cWheres, $wheres3);
			my $wheres6 = $algae->_addWhereField($alias2, 'doc', '=', $alias3, 'id', $term, $outer);
			push (@$cWheres, $wheres6);
		    } else {
			&throw(new W3C::Util::ProgramFlowException());
		    }
		} else {
		    &throw(new W3C::Util::ProgramFlowException());
		}
	    } else {
		&throw(new W3C::Util::ProgramFlowException());
	    }
	} elsif ($constraint->{EXPR}->isa('W3C::Rdf::AlgaeCompileTree::Assign')) {
	    my $l = $constraint->{EXPR}{L};
	    my $r = $constraint->{EXPR}{R};
	    if ($l->isa('W3C::Rdf::AlgaeCompileTree::Var')) {
		if ($r->isa('W3C::Rdf::AlgaeCompileTree::KeyName')) {
		    if ($r->{VARNAME} eq 'ATTRIB') {
			my ($alias1, undef) = $binder->_getNewTableAlias('__AttrLists__', $s, $binder, $outer, 1, $PREFIX_ALIAS, 1);
			my $wheres4 = $algae->_addWhereField($statementsAlias, 'a', '=', $alias1, 'listId', $term, $outer);
			push (@$cWheres, $wheres4);
			my ($alias2, undef) = $binder->_getNewTableAlias('__Attributions__', $s, $binder, $outer, 1, $PREFIX_ALIAS, 1);
			my $wheres5 = $algae->_addWhereField($alias1, 'a', '=', $alias2, 'id', $term, $outer);
			push (@$cWheres, $wheres5);
			my ($alias3, $wheres3) = $binder->_getNewTableAlias('__Nodes__', $l, $binder, $outer, 1, $PREFIX_ALIAS, 0);
			push (@$cWheres, $wheres3);
			my $wheres6 = $algae->_addWhereField($alias2, 'doc', '=', $alias3, 'id', $term, $outer);
			push (@$cWheres, $wheres6);
		    } else {
			&throw(new W3C::Util::ProgramFlowException());
		    }
		} else {
		    &throw(new W3C::Util::ProgramFlowException());
		}
	    } else {
		&throw(new W3C::Util::ProgramFlowException());
	    }
	} else {
	    &throw(new W3C::Util::ProgramFlowException());
	}
    }

    my $ret;
    # This gives a nice right-extended tree.
    foreach my $where (reverse @$cWheres) {
	$ret = $ret && $where ? $where->newConjunction($ret) : ($ret || $where);
    }
    return $ret;
}

sub getNodeAlias {
    my ($atom, $binder, $algae, $term, $outer, $wheres) = @_;
    my ($atomAliasIds, $atomTable);
    my $wheres;

    # We already know this node is a table entity.
    if (my $atomEntityAliasPair = $binder->_getTableAliasForSymbol($atom)) {
	# Connect to $atomAliasIds.
	($atomAliasIds, $atomTable) = @$atomEntityAliasPair;
	if ($atomTable eq '__Nodes__') {
	    # @@@ I *think* we're already fully constrained here. Think harder?
	} else {
	    my $t;
	    ($t, $wheres) = $binder->_getNewTableAlias('__Nodes__', $atom, $binder, $outer, 0, $PREFIX_ALIAS, 0);
	    $wheres = $algae->_addWhereTable($atomTable, $t, $atomAliasIds, $term, $outer);
	    $atomAliasIds = $t;
	}
	# something about tableName and $atomEntityAliasPair->[1]
    } else {
	($atomAliasIds, $wheres) = $binder->_ensureTableAliasForSymbol('__Nodes__', $term, $atom, $binder, $outer, 1, $PREFIX_ALIAS);
    }
    return ($atomAliasIds, $wheres);
}

sub changeId {
    my ($self, $from, $to, $algae) = @_;
    my $fromId = $self->ensureNode($from, $algae);
    my $toId = $self->ensureNode($to, $algae);
    #$algae->executeUpdate("LOCK TABLES __Nodes__");
    $algae->executeUpdate("UPDATE __Nodes__ SET id=0 WHERE id=$toId");
    $algae->executeUpdate("UPDATE __Nodes__ SET id=$toId WHERE id=$fromId");
    $algae->executeUpdate("UPDATE __Nodes__ SET id=$fromId WHERE id=0");
    #$algae->executeUpdate("UNLOCK TABLES");
    # What about attributions?
}

@W3C::Rdf::SqlDB::WildcardProperty::ISA = ('W3C::Rdf::SqlDB::Property');
package W3C::Rdf::SqlDB::WildcardProperty;

sub new {
    my ($proto, $predicateVar, $tables) = @_;
    my $class = ref($proto) || $proto;
    my $self = {PREDICATE_VAR => $predicateVar, TABLES => $tables};
    bless ($self, $class);
    return $self;    
}
sub getObjectDatatype {
    my ($self) = @_;
    &throw(new W3C::Util::NotImplementedException());
}
sub processAssertion {
    my ($self, $triple, $algae, $attribution) = @_;
    &throw(new W3C::Util::Exception(-message => "attempt to assert ".$triple->toStrgin." into WildcardProperty"))
}
sub processMatch {
    my ($self, $term, $binder, $cell, $algae, $disjunction, $negation, $outer, $attribution) = @_;
    # Create constraints and bindings for each know relation + the __Holds__ predicate.
    my @constraints;
    foreach my $tableName (keys %{$self->{TABLES}}) {
	if ($tableName eq '__Holds__') {
	    push (@constraints, $self->{TABLES}{'__Holds__'}->getPropertyByName('subject')->processMatch($term, $binder, $cell, $algae, $disjunction, $negation, $outer, $attribution)); # !!! will need some UNION instead of an outer join
	} elsif ($tableName eq '__Nodes__') {
	} else {
	    foreach my $propertyName ($self->{TABLES}{$tableName}->getFieldNames) {
# !!!		push (@constraints, $self->{TABLES}{$tableName}->getPropertyByName($propertyName)->processMatch($term, $binder, $cell, $algae, $disjunction, $negation, 1, $attribution));
	    }
	}
    }
    my $ret;
    # This gives a nice right-extended tree.
    foreach my $wheres (@constraints) {
	$ret = $ret && $wheres ? $wheres->newConjunction($ret) : ($ret || $wheres);
    }
    return $ret;
}

@W3C::Rdf::SqlDB::PropertySet::ISA = ('W3C::Database::Structure::Index');
@W3C::Rdf::SqlDB::PrimaryKey::ISA = ('W3C::Database::Structure::PrimaryKey');

package W3C::Rdf::SqlDB::Constraint;
use W3C::Util::Exception;
@W3C::Rdf::SqlDB::AttributeRestriction::ISA = qw(W3C::Rdf::SqlDB::Constraint);
@W3C::Rdf::SqlDB::AttributeDisjunction::ISA = qw(W3C::Rdf::SqlDB::Constraint);
@W3C::Rdf::SqlDB::Binary::ISA = qw(W3C::Rdf::SqlDB::Constraint);
@W3C::Rdf::SqlDB::Conjunction::ISA = qw(W3C::Rdf::SqlDB::Binary);
@W3C::Rdf::SqlDB::Unary::ISA = qw(W3C::Rdf::SqlDB::Constraint);
@W3C::Rdf::SqlDB::Negation::ISA = qw(W3C::Rdf::SqlDB::Unary);
@W3C::Rdf::SqlDB::Optional::ISA = qw(W3C::Rdf::SqlDB::Unary);
@W3C::Rdf::SqlDB::Disjunction::ISA = qw(W3C::Rdf::SqlDB::Binary);
sub new {
    my ($proto, $init, $top) = @_;
    my $class = ref($proto) || $proto;
    my $self = $init;
    bless ($self, $class);
    return $self;
}
sub newConjunction {
    my ($self, $right) = @_;
    my $ret;
    if ($self->isa('W3C::Rdf::SqlDB::Conjunction')) {
	$ret = $self;
	my $last = $self;
	while ($last->getRight->isa('W3C::Rdf::SqlDB::Conjunction')) {
	    $last = $last->getRight;
	}
	$last->setRight(new W3C::Rdf::SqlDB::Conjunction($last->getRight, $right));
    } else {
	$ret = new W3C::Rdf::SqlDB::Conjunction($self, $right);
    }
    return $ret;
}
sub newDisjunction {
    my ($self, $right) = @_;
    my $ret;
    if ($self->isa('W3C::Rdf::SqlDB::Disjunction')) {
	$ret = $self;
	my $last = $self;
	while ($last->getRight->isa('W3C::Rdf::SqlDB::Disjunction')) {
	    $last = $last->getRight;
	}
	$last->setRight(new W3C::Rdf::SqlDB::Disjunction($last->getRight, $right));
    } else {
	$ret = new W3C::Rdf::SqlDB::Disjunction($self, $right);
    }
    return $ret;
}
sub extractConstraintClause {
    my ($self, $reached, $pOuter, $pOns) = @_;
    my $ret = $self;
    my $parent = $self;
    my $parentParent = undef;
    while ($self->isa('W3C::Rdf::SqlDB::Conjunction')) {
	my $where = $self->{LEFT};
	my ($clause, $depends, $outer) = $where->toOldForm;
	if (@$depends > 1) {
	    my $matches = 1;
	    foreach my $depend (@$depends) {
		if (!$reached->{$depend}) {
		    $matches = 0;
		    last;
		}
	    }
	    if ($matches) {
		push (@$pOns, $clause);
		$$pOuter |= $outer;

		# We've used this constraint for a join clause so remove it.
		if ($ret == $self) {
		    $ret = $self->{RIGHT};
		} else {
		    $parent->{RIGHT} = $self->{RIGHT};
		}
	    }
	}
	$parentParent = $parent;
	$parent = $self;
	$self = $self->{RIGHT};
    }
    my $where = $self;
    my ($clause, $depends, $outer) = $where->toOldForm;
    if (@$depends > 1) {
	foreach my $depend (@$depends) {
	    if (!$reached->{$depend}) {
		return $ret;
	    }
	}
	push (@$pOns, $clause);
	$$pOuter |= $outer;

	# We've used this constraint for a join clause so remove it.
	if ($ret == $self) {
	    $ret = undef; # no more constraints.
	} elsif ($ret == $parent) {
	    $ret = $ret->{LEFT};
	} else {
	    $parentParent->{RIGHT} = $parent->{LEFT};
	}
    }
    return $ret;
}
sub prec {
    my ($self, $precTable) = @_;
    my $class = ref $self;
    if (!exists $precTable->{$class}) {
	# Signal to make no assumptions about precedence.
	return -1;
    }
    return $precTable->{$class};
}

package W3C::Rdf::SqlDB::AttributeRestriction;
sub new {
    my ($proto, $condition, $aliases, $outer, @cParms) = @_;
    my $class = ref($proto) || $proto;
    my $self = $class->SUPER::new({CONDITION => $condition, ALIASES => [sort @$aliases], OUTER => $outer}, @cParms);
    return $self;
}
sub deleteConstraint {
    my ($self, $doomed) = @_;
    return $self == $doomed ? undef : $self;
}
sub findCommonClauses {
    my ($self, $holder, $or, $not, $opt) = @_;
    my @cParts;
    # if ($or) {push @cParts, '||'} !!!@@@ not needed, i *think*
    if ($not) {push @cParts, '!'}
    if ($opt) {push @cParts, '~'}
    push (@cParts, $self->{CONDITION});
    my $hashKey = join ('', @cParts);
    if (exists $holder->{$hashKey}) {
	push (@{$holder->{$hashKey}}, $self);
    } else {
	$holder->{$hashKey} = [$self];
    }
}
sub toOldForm {$_[0]->{CONDITION}, [sort @{$_[0]->{ALIASES}}], $_[0]->{OUTER}}
sub toGraph {
    my ($self, $or, $not, $opt) = @_;
    my @cParts;
    if ($or) {push @cParts, '||'}
    if ($not) {push @cParts, '!'}
    if ($opt) {push @cParts, '~'}
    push (@cParts, $self->{CONDITION});
    my $condition = join ('', @cParts);
    $condition =~ s/(\\(?!n)|\"|<|>)/\\$1/gx;
    my @parts;
    for (my $first = 0; $first < @{$self->{ALIASES}}-1; $first++) {
	for (my $second = $first+1; $second < @{$self->{ALIASES}}; $second++) {
	    my $f = $self->{ALIASES}[$first];
	    $f =~ s/(\\(?!n)|\"|<|>)/\\$1/gx;
	    my $s = $self->{ALIASES}[$second];
	    $s =~ s/(\\(?!n)|\"|<|>)/\\$1/gx;
	    push (@parts, "\"$f\" -> \"$s\" [label=\"$condition\"];\n");
	}
    }
    return join ('', @parts)."\n";
}

sub toDot {
    my ($self, $precTable, $parentPrec) = @_;
    my @parts = ($self->{CONDITION});
    if ($self->{ALIASES}) {
	push (@parts, join ('|', @{$self->{ALIASES}}));
    }
    map {s/(\\(?!n)|\"|<|>)/\\$1/gx} @parts;
    return "\"$self\" [shape=record label=\"".join ('|', @parts)."\"];\n";
}

sub toString {
    my ($self, $precTable, $parentPrec) = @_;
    # debugging return "$self->{CONDITION} [".join (' ', @{$self->{ALIASES}})."]\n";
    return $self->{CONDITION};
}

package W3C::Rdf::SqlDB::AttributeDisjunction;
sub new {
    my ($proto, $lset, $rset, $outer, @cParms) = @_;
    my $class = ref($proto) || $proto;
    my $l = [grep {$_} @$lset];
    my $r = [grep {$_} @$rset];
    my $lcond = join (' AND ', map {$_->{CONDITION}} @$l);
    my $rcond = join (' AND ', map {$_->{CONDITION}} @$r);
    my $condition = "(($lcond) OR ($rcond))";
    my $aliases = {};
    foreach my $s (@$l, @$r) {
	foreach my $alias (@{$s->{ALIASES}}) {
	    $aliases->{$alias} = undef;
	}
    }
    my $self = $class->SUPER::new({CONDITION => $condition, ALIASES => [sort keys %$aliases], OUTER => $outer}, @cParms);
    return $self;
}
sub toString {
    my ($self, $precTable, $parentPrec) = @_;
    # debugging return "$self->{CONDITION} [".join (' ', @{$self->{ALIASES}})."]\n";
    return $self->{CONDITION};
}

package W3C::Rdf::SqlDB::Unary;
sub new {
    my ($proto, $term, @cParms) = @_;
    my $class = ref($proto) || $proto;
    my $self = $class->SUPER::new({TERM => $term}, @cParms);
    return $self;
}
sub deleteConstraint {
    my ($self, $doomed) = @_;
    if ($self == $doomed) {
	return undef;
    }
    $self->{TERM} = $self->{TERM}->deleteConstraint($doomed);
    return $self->{TERM} ? $self->{TERM} : undef;
}
sub toDot {
    my ($self, $precTable, $parentPrec) = @_;
    my $opStr = $self->opStr;
    return "\"$self\" [label=\"$opStr\"];
\"$self\" -> \"$self->{DECL}\"
".$self->{TERM}->toDot($precTable, $parentPrec);
}
sub toString {
    my ($self, $precTable, $parentPrec) = @_;
    my $prec = $self->prec($precTable);
    my $str = $self->opStr.$self->{TERM}->toString($precTable, $parentPrec);
    return $prec < 0 || $prec < $parentPrec ? "($str)" : $str;
}


package W3C::Rdf::SqlDB::Negation;
sub findCommonClauses {
    my ($self, $holder, $or, $not, $opt) = @_;
    $self->{TERM}->findCommonClauses($or, !$not, $opt);
}
sub toGraph {
    my ($self, $or, $not, $opt) = @_;
    $self->{TERM}->toGraph($or, !$not, $opt);
}
sub opStr {'!'}

package W3C::Rdf::SqlDB::Optional;
sub findCommonClauses {
    my ($self, $holder, $or, $not, $opt) = @_;
    $self->{TERM}->findCommonClauses($or, $not, 1);
}
sub toGraph {
    my ($self, $or, $not, $opt) = @_;
    $self->{TERM}->toGraph($or, $not, 1);
}
sub opStr {'~'}

package W3C::Rdf::SqlDB::Binary;
sub new {
    my ($proto, $left, $right, @cParms) = @_;
    my $class = ref($proto) || $proto;
    my $self = $class->SUPER::new({LEFT => $left, RIGHT => $right}, @cParms);
    return $self;
}
sub deleteConstraint {
    my ($self, $doomed) = @_;
    if ($self == $doomed) {
	return undef;
    }
    $self->{LEFT} = $self->{LEFT}->deleteConstraint($doomed);
    $self->{RIGHT} = $self->{RIGHT}->deleteConstraint($doomed);
    return $self->{LEFT} ? ($self->{RIGHT} ? $self : $self->{LEFT}) : ($self->{RIGHT} ? $self->{RIGHT} : undef);
}

# Make sure that a new disjunction follows to the left of any conjunction.
sub newDisjunction {
    my ($self, $right, $pNew) = @_;
    my $ret = $self->SUPER::newDisjunction($right);
    if ($pNew) {$$pNew = $ret};
    my $allClauses = {};

    # Make a list of clauses common to all paths of disjunction.
    $ret->findCommonClauses($allClauses, 0, 0, 0);
    # print join ("\n", keys %$allClauses),"\n"; # candiates for removal from OR

    # Move those clauses to be parrents of the proposed return clause.
    foreach my $hashKey (keys %$allClauses) {
	my $aDeletedClause;
	foreach my $clause (@{$allClauses->{$hashKey}}) {
	    $aDeletedClause = $clause;
	    $ret = $ret->deleteConstraint($clause);
	    # !!! use former until we figure out we need the latter
	    # $ret = new W3C::Rdf::SqlDB::Conjunction($clause, $ret);
	}
	$ret = $aDeletedClause->newConjunction($ret);
    }
    return $ret;
}
sub toDot {
    my ($self, $precTable, $parentPrec) = @_;
    my $opStr = $self->opStr;
    $opStr =~ s/(\\(?!n)|\"|<|>)/\\$1/gx;
    $opStr =~ s/\n/\\n/gx;
    return "\"$self\" [label=\"$opStr\"];
\"$self\" -> \"$self->{LEFT}\" [label=\"l\"];
\"$self\" -> \"$self->{RIGHT}\" [label=\"r\"];
".$self->{LEFT}->toDot($precTable, $parentPrec)."
".$self->{RIGHT}->toDot($precTable, $parentPrec);
}
sub toString {
    my ($self, $precTable, $parentPrec) = @_;
    my $prec = $self->prec($precTable);
    my $str = join (' '.$self->opStr.' ', map {$_->toString($precTable, $prec)} ($self->{LEFT}, $self->{RIGHT}));
    return $prec < 0 || $prec > $parentPrec ? "($str)" : $str;
}
sub getRight {$_[0]->{RIGHT}}
sub setRight {$_[0]->{RIGHT} = $_[1]}

package W3C::Rdf::SqlDB::Conjunction;
sub findCommonClauses {
    my ($self, $holder, $or, $not, $opt) = @_;
    $self->{LEFT}->findCommonClauses($holder, $or, $not, $opt);
    $self->{RIGHT}->findCommonClauses($holder, $or, $not, $opt);
}
sub toGraph {
    my ($self, $or, $not, $opt) = @_;
    $self->{LEFT}->toGraph($or, $not, $opt)."\n".$self->{RIGHT}->toGraph($or, $not, $opt)."\n";
}
sub toOldForm {$_[0]->toString, [], $_[0]->{OUTER}} # @@@ can do much better than this
sub opStr {'
  AND '}
package W3C::Rdf::SqlDB::Disjunction;
sub new {
    my ($proto, @parms) = @_;
    my $class = ref($proto) || $proto;
    my $self = $class->SUPER::new(@parms);
#    my ($lWhereStr, $lDepends, $louter) = $self->_makeWheres($self->{LEFT}, 0, 0);
#    my ($rWhereStr, $rDepends, $router) = $self->_makeWheres($self->{RIGHT}, 0, 0);
#    my $condition = "(($lWhereStr) OR ($rWhereStr))";
    return $self; # do someting with it?
}
sub findCommonClauses {
    my ($self, $holder, $or, $not, $opt) = @_;
    my $leftClauses = {};
    $self->{LEFT}->findCommonClauses($leftClauses, 1, $not, $opt);
    my $rightClauses = {};
    $self->{RIGHT}->findCommonClauses($rightClauses, 1, $not, $opt);

    # Find only the subset common to both leftClauses and rightClauses.
    foreach my $hashKey (keys %$leftClauses) {
	if (my $rightList = $rightClauses->{$hashKey}) {
	    my $leftList = $leftClauses->{$hashKey};
	    if (exists $holder->{$hashKey}) {
		push (@{$holder->{$hashKey}}, @$leftList, @$rightList);
	    } else {
		$holder->{$hashKey} = [@$leftList, @$rightList];
	    }
	}
    }
}
sub toGraph {
    my ($self, $or, $not, $opt) = @_;
    $self->{LEFT}->toGraph(1, $not, $opt)."\n".$self->{RIGHT}->toGraph(1, $not, $opt)."\n";
}
sub toOldForm {$_[0]->toString($PRECEDENCE_TABLE, 0), [], $_[0]->{OUTER}}
sub opStr {'
   OR '}

package W3C::Rdf::SqlDB::Binding;
sub new {
    my ($proto, $queryPiece, $cols, $fieldz, $table) = @_;
    my $class = ref($proto) || $proto;
    my $self = {QUERY_PIECE => $queryPiece, COLS => $cols, FIELDZ => $fieldz, TABLE => $table};
    bless ($self, $class);
    return $self;
}
sub constrains {
    my ($self, $row, $algae) = @_;
    return undef;
}
sub constrain {
    my ($self, $row, $algae) = @_;
    return undef;
}
sub preAssimilate {}
sub _typeStr {&throw(new W3C::Util::NotImplementedException())}
sub toString {
    my ($self) = @_;
    my $typeStr = $self->_typeStr;
    my $cols = join (',', @{$self->{COLS}});
    my $fieldzStr = $self->_fieldzString();
    my $qpStr = $self->{QUERY_PIECE}->toString;
    return "$typeStr binding for cols [$cols] to ($qpStr)$fieldzStr";
}
sub _fieldzString {
    my ($self) = @_;
    my $fieldz = join (',', @{$self->{FIELDZ}});
    return " $self->{TABLE}.[$fieldz]";
}

package W3C::Rdf::SqlDB::DisjunctionBinding;
@W3C::Rdf::SqlDB::DisjunctionBinding::ISA = qw(W3C::Rdf::SqlDB::Binding);
use W3C::Rdf::Atoms qw($Value_NULL);
sub _fieldzString {
    my ($self) = @_;
    return '';
}
# Grab literals from the results
sub assimilate {
    my ($self, $answerRow, $newRow, $rowBindings, $db) = @_;
    $rowBindings->{$self->{QUERY_PIECE}} = $answerRow->[$self->{COLS}->[0]];
}
sub _typeStr {'disjunction'}

package W3C::Rdf::SqlDB::AttributionBinding;
@W3C::Rdf::SqlDB::AttributionBinding::ISA = qw(W3C::Rdf::SqlDB::Binding);
use W3C::Rdf::Atoms qw($Value_NULL);
# Grab literals from the results
sub assimilate {
    my ($self, $answerRow, $newRow, $rowBindings, $db) = @_;
    $db->_cacheAttributionList($self->{QUERY_PIECE}, $answerRow->[$self->{COLS}->[0]]);
}
sub _typeStr {'attribution'}

package W3C::Rdf::SqlDB::StatementIdBinding;
@W3C::Rdf::SqlDB::StatementIdBinding::ISA = qw(W3C::Rdf::SqlDB::Binding);
use W3C::Rdf::Atoms qw($Value_NULL);
# Grab literals from the results
sub assimilate {
    my ($self, $answerRow, $newRow, $rowBindings, $db) = @_;
    $db->_cacheStatementIdList($self->{QUERY_PIECE}, $answerRow->[$self->{COLS}->[0]]);
}
sub _typeStr {'statement ID'}

package W3C::Rdf::SqlDB::ColumnBinding;
use W3C::Util::Exception;
@W3C::Rdf::SqlDB::ColumnBinding::ISA = qw(W3C::Rdf::SqlDB::Binding);
sub constrains {
    my ($self) = @_;
    return [[$self->{QUERY_PIECE}->varIndex, $self->{COLS}[0]]];
}
sub constrain {
    my ($self, $row, $algae) = @_;
    my $object = $row->get($self->{QUERY_PIECE}->varIndex);
    if (defined $object) {
	my $objectStr;
	if ($object->isa('W3C::Rdf::Uri')) {
	    $objectStr = $object->getUri;
	} elsif ($object->isa('W3C::Rdf::String')) {
	    $objectStr = $object->getString;
	} else {
	    &throw(new W3C::Util::NotImplementedException(-class => 'W3C::Rdf::SqlDB', 
							  -method => "addTriple object $object"));
	}
	$self->{MATCH} = $objectStr;
	return [$self->{COLS}->[0], $objectStr, $algae->_addWhereConst($self->{TABLE}, $self->{FIELDZ}[0], '=', $objectStr, $self->{QUERY_PIECE}, 0)];
    } else {
	return undef;
    }
}

package W3C::Rdf::SqlDB::ScalarBinding;
@W3C::Rdf::SqlDB::ScalarBinding::ISA = qw(W3C::Rdf::SqlDB::ColumnBinding);
use W3C::Rdf::Atoms qw($Value_NULL);
sub new {
    my ($proto, $queryPiece, $cols, $fieldz, $table, $datatype) = @_;
    my $class = ref($proto) || $proto;
    my $self = $class->SUPER::new($queryPiece, $cols, $fieldz, $table);
    $self->{Datatype} = $datatype;
    return $self;
}

# Grab literals from the results
sub assimilate {
    my ($self, $answerRow, $newRow, $rowBindings, $db) = @_;
    my $value = $answerRow->[$self->{COLS}->[0]];
    # Add mappings from SQL datatype to XSD datatypes here.
    my $datatype = $self->{Datatype};
    if ($datatype) {
	my $dUri = $datatype->getUri();
	if ($dUri eq 'http://www.w3.org/2001/XMLSchema#dateTime') {
	    if ($value =~ m/^(\d+)-(\d+)-(\d+) (\d+):(\d+):(\d+)$/) {
		$value = "$1$2$3T$4:$5:$6Z";
	    } else {
		&throw(new W3C::Util::Exception(-message => "malformed SQL datetime: \"$value\""));
	    }
	}
    }
    my $atom = defined $value ? $db->{-atomDictionary}->getString($value, $datatype, 'PLAIN') : $Value_NULL;
    $self->{QUERY_PIECE}->absorb($atom, $newRow);
    #$nextResults->[-1][$self->{QUERY_PIECE}->varIndex] = $atom;
    $rowBindings->{$self->{QUERY_PIECE}->symbol} = $atom;
}
sub _typeStr {'scalar'}

package W3C::Rdf::SqlDB::ObjectBinding;
@W3C::Rdf::SqlDB::ObjectBinding::ISA = qw(W3C::Rdf::SqlDB::ColumnBinding);
use W3C::Rdf::Atoms qw($Value_NULL);
sub assimilate {
    my ($self, $answerRow, $newRow, $rowBindings, $db) = @_;
    my $valueHash = {};
    my $allNulls = 1;
    for (my $i = 0; $i < @{$self->{COLS}}; $i++) {
	my $col = $self->{COLS}->[$i];
	my $field = $self->{FIELDZ}->[$i];
	my $value = $answerRow->[$col];
	$valueHash->{$field} = $value;
	if (defined $value) {
	    $allNulls = 0;
	}
    }
    my $atom = $allNulls ? $Value_NULL : $db->{-atomDictionary}->getUri($db->_composeUniques($valueHash, $self->{TABLE}));
    $atom = $self->{QUERY_PIECE}->absorb($atom, $newRow);
    #$nextResults->[-1][$queryPiece->varIndex] = $atom;
    $rowBindings->{$self->{QUERY_PIECE}->symbol} = $atom;
}
sub _typeStr {'node'}
sub toString {
    my ($self) = @_;
    my $typeStr = $self->_typeStr;
    my $cols = join (',', @{$self->{COLS}});
    my $qpStr = $self->{QUERY_PIECE}->toString;
    my $fieldzStr = join (',', @{$self->{FIELDZ}});
    return "$typeStr binding for cols $cols to $qpStr from $self->{TABLE}.$fieldzStr";
}

package W3C::Rdf::SqlDB::NodeBinding;
@W3C::Rdf::SqlDB::NodeBinding::ISA = qw(W3C::Rdf::SqlDB::ObjectBinding);
use W3C::Rdf::Atoms qw($Value_NULL);

	# Grab __Nodes__ from the results
	# do in two passes to queue all the items and query them at once
sub preAssimilate {
    my ($self, $answerRow, $db) = @_;
    if (defined $self->{COLS}->[0]) {
	$db->queueResolveNodeId($answerRow->[$self->{COLS}->[0]]);
    }
}
sub assimilate {
    my ($self, $answerRow, $newRow, $rowBindings, $db) = @_;
    my $atom = defined $self->{COLS}->[0] && $answerRow->[$self->{COLS}->[0]] ? 
	$db->resolveNodeId($answerRow->[$self->{COLS}->[0]]) : $Value_NULL;
    $atom = $self->{QUERY_PIECE}->absorb($atom, $newRow);
    #$nextResults->[-1][$self->{QUERY_PIECE}->varIndex] = $atom;
    $rowBindings->{$self->{QUERY_PIECE}->symbol} = $atom;
}
sub _typeStr {'node'}

# RowConstraintHash -- write down which columns and variables identify the
# solution for an existing row in the result set. For instance, the variabels
# ?name and ?number are bound and a new query asks for the ?address for each
# such tuple.
# ResultSet:
#  ?name ?number ?address
#  "bob"  12.34     N/A
#  "sue"  12.34     N/A
#  "bob"  12.34     N/A
# Algae query:
#  ask (?x folks:name ?name; 
#          folks:number ?number; 
#          folks:address ?address)
# SQL query:
#  SELECT folks_0.name, folks_0.number, folks_0.address
#   FROM folks AS folks_0
#  WHERE (folks_0.name="bob" AND folks_0.number=12.34)
#     OR (folks_0.name="sue" AND folks_0.number=12.34)
# SQL results:
#  "bob"  12.34 "elm street"
#  "sue"  12.34 "mel street"
#  "bob"  12.34 "lem street"
# ResultSet:
#  ?name ?number ?address
#  "bob"  12.34 "elm street"
#  "bob"  12.34 "lem street"
#  "sue"  12.34 "mel street"
#  "bob"  12.34 "elm street"
#  "bob"  12.34 "lem street"

package W3C::Rdf::SqlDB::RowConstraintHash;
use W3C::Util::Exception;

# Construct a constraint hash with the set of all bindings. Also informed by
# the first row of the ResultSet (may change).
sub new {
    my ($proto, $firstRow, $bindings) = @_;
    my $class = ref($proto) || $proto;
    my $self = {
	# array of W3C::Rdf::SqlDB::Binding objects
	BINDINGS => $bindings, 
	# disjunction constraining bound variables (WHERE a.name="Bob" stuff)
	BindingConstraints => undef, 
	# Array of SQL columns to check for already bound values
	SQLcols => undef, 
	# mth column in SQL corresponds to nth column in ResultSet
	# @@@ This will need more complex modeling when a single ResultSet
	# binding corresponds to (is gathered from) multiple SQL colums.
	Sql2Rs => {}, 
	# for each set of bound values, which ResultSet rows correspond
	Key2RsRowNos => {}, 
	# for each ResultSet row, which SQL result rows correspond
	RsRowNo2SqlRows => {}};
    my @sqlCols;
    foreach my $binding (@{$self->{BINDINGS}}) {
	if (my $rsAndCols = $binding->constrains()) {
	    foreach my $rsAndCol (@$rsAndCols) {
		my ($rsCol, $sqlCol) = @$rsAndCol;

		# If the first row of the resultSet has a binding for this
		# column, we should use it to constrain our query. @@@ At some
		# point, the ResultSet should probably get it's own idea if
		# which variables are bound (even to NULL), but I haven't
		# thought enough about cases where variables might be bound in
		# one tuple and not in another.
		if (defined $firstRow->get($rsCol)) {
		    push (@sqlCols, $sqlCol);
		    $self->{Sql2Rs}{$sqlCol} = $rsCol;
		}
	    }
	}
    }

    # Sort the SQL columns numerically to make life easier for the person
    # debugging.
    $self->{SQLcols} = [sort @sqlCols];
    bless ($self, $class);
    return $self;
}

sub getObjectStr { # static
    my ($object) = @_;
    my $objectStr;
    if ($object->isa('W3C::Rdf::AlgaeCompileTree::Members')) {
	&throw(new W3C::Util::ProgramFlowException());
    } elsif ($object->isa('W3C::Rdf::AlgaeCompileTree::StaticPOS')) {
	$object = $object->val;
    }
    if ($object->isa('W3C::Rdf::Uri')) {
	$objectStr = $object->getUri;
    } elsif ($object->isa('W3C::Rdf::String')) {
	$objectStr = $object->getString;
    } else {
	&throw(new W3C::Util::NotImplementedException(-class => 'W3C::Rdf::SqlDB', 
						      -method => "addTriple object $object"));
    }
    return $objectStr;
}

# Construct a key unique to ant set of values (used in indexing row
# constraints).
sub _getRowIndexString {
    my ($self, $row) = @_;
    my (@rsValues);
    foreach my $sqlCol (@{$self->{SQLcols}}) {
	if (!defined $self->{Sql2Rs}{$sqlCol}) {&throw()};
	my $rsCol = $self->{Sql2Rs}{$sqlCol};
	my $object = $row->get($rsCol);
	push (@rsValues, &getObjectStr($object));
    }
    return join(' | ', @rsValues);
}

# Index the ResultSet rows by the variables they have already bound.
sub indexResultSetRow {
    my ($self, $row, $rowNo, $algae) = @_;
    my $rsIndex = $self->_getRowIndexString($row);
    if (exists $self->{Key2RsRowNos}{$rsIndex}) {
	push (@{$self->{Key2RsRowNos}{$rsIndex}}, $rowNo);
    } else {
	$self->{Key2RsRowNos}{$rsIndex} = [$rowNo];

	# No constraint option has been constructed to reflect this
	# combination of bindings.
	my $thisConstraint = undef;
	foreach my $binding (@{$self->{BINDINGS}}) {
	    if (my $foo = $binding->constrain($row, $algae)) {
		my ($col, $val, $where) = @$foo;
		$thisConstraint = $thisConstraint ? 
		    new W3C::Rdf::SqlDB::Conjunction($thisConstraint, $where) : 
		    $where;
	    }
	}

	# Construct (maintain) a set of disjunctive constraints that describe
	# the bound values encountered so far.
	if ($thisConstraint) {
	    $self->{BindingConstraints} = $self->{BindingConstraints} ? 
		new W3C::Rdf::SqlDB::Disjunction($self->{BindingConstraints}, $thisConstraint) : 
		$thisConstraint;
	}
    }
}

sub getConstraints {
    my ($self) = @_;
    return $self->{BindingConstraints};
}

# Walk through the SQL query results and correlate them with the ResultSet rows
# with the same bound values.
sub indexSqlRows {
    my ($self, $answerRow) = @_;
    my (@rsValues);
    foreach my $sqlCol (@{$self->{SQLcols}}) {
	push (@rsValues, $answerRow->[$sqlCol]);
    }
    my $rsIndex = join(' | ', @rsValues);
    if (!exists $self->{Key2RsRowNos}{$rsIndex}) {&throw()}
    foreach my $rsRowNo (@{$self->{Key2RsRowNos}{$rsIndex}}) {
	if (exists $self->{RsRowNo2SqlRows}{$rsRowNo}) {
	    push (@{$self->{RsRowNo2SqlRows}{$rsRowNo}}, $answerRow);
	} else {
	    $self->{RsRowNo2SqlRows}{$rsRowNo} = [$answerRow];
	}
    }
}
sub getRelatedSqlRows {
    my ($self, $row, $rsRowNo) = @_;
    return $self->{RsRowNo2SqlRows}{$rsRowNo};
}

package W3C::Rdf::SqlDB;
use W3C::Rdf::Atoms qw($Value_NULL $ATTRIB_GroundFact $ATTRIB_FactRef $ATTRIB_Reification $ATTRIB_RuleRef $ATTRIB_Inference);
use W3C::Rdf::Algae2;
use vars qw($SEP_ATTRIB $SEP_VALUE $SEP_KEY $PREFIX_ALIAS);
$SEP_ATTRIB = '_'; # separate relation from attribute
$SEP_KEY = '&'; # separate multiple attribute/values in a key
$SEP_VALUE = '_'; # separate attribute from value
$PREFIX_ALIAS = 1;
# $selectFields [[$table, $as, $pos, [$fields...]]|[$table, $as, $pos, $field]]


my $SUBST_NONE = 0;
my $SUBST_PRED = 1;
my $SUBST_SUBJ = 2;
my $SUBST_OBJ = 4;
my $TEST = 'test';

sub new {
    my ($proto, @parms) = @_;
    my $class = ref($proto) || $proto;
    my $self = $class->SUPER::new(@parms);
    my $props = $self->{-properties};
    if (!$props) {
	&throw(new W3C::Util::Exception(-message => "SqlDB ctor needs a properties file"));
    }
    bless ($self, $class);
    if (UNIVERSAL::isa($props, 'W3C::Util::Properties')) {
    } elsif (UNIVERSAL::isa($props, 'W3C::Rdf::String')) {
	$props = $self->{-properties} = new W3C::Util::Properties($props->getString);
    } else {
	$props = $self->{-properties} = new W3C::Util::Properties($props);
    }
    $self->{DB} = new W3C::Database::DBIRef($props);
    my @maps = $props->getI('predicateMap');
    foreach my $map (@maps) {
	if ($map =~ m/\s*([^\s\=]+)\s*\=\>\s*([^\.]+)\.(.*)$/) {
	    $self->{PREDICATE_MAP}{$1} = [$2, $3];
	} else {
	    &throw(new W3C::Util::Exception(-message => "malformed predicate map: \"$map\""));
	}
    }
    $self->{BASE_URI} = $props->getI('schemaNS');
    my $pkg = $props->getI('structure');
    if ($pkg) {
	my $structure = undef;
	my $evalMe = "require $pkg; \$structure = \\\%${pkg}::_AllTables;";
	eval $evalMe;
	if ($@) {&throw()}
	if (!%$structure) {
	    &throw(new W3C::Util::Exception(-message => "$pkg does not define \%${pkg}::_AllTables"));
	}
	$self->{TABLES} = $self->_compileStructure($structure);
	if (!$self->{BASE_URI}) {
	    my $propStr = $props->toString;
	    &throw(new W3C::Util::Exception(-message => "schemaNS property not defined in $propStr"));
	}
    } else {
	# I guess we'll just be using the generic triple store.
	# my $propStr = $props->toString;
	# &throw(new W3C::Util::Exception(-message => "structure property not defined in $propStr"));
    }

    my $auth = $props->get('user');
    if ($auth) {
	$auth = $self->{-atomDictionary}->getUri("data:text/plain,$auth");
    }
    $self->{-sourceAttribution} ||= 
	$self->{-atomDictionary}->getGroundFactAttribution(
			 $self->{-atomDictionary}->getUri($self->{BASE_URI}), 
						 undef, $auth, undef);
    $self->{-assertionAttribution} ||= $self->{-sourceAttribution};

    # Build a description of the __Holds__ relations.
    $self->{STATEMENTS_CLASS} = new W3C::Rdf::SqlDB::Class('__Holds__');
    $self->{STATEMENTS_PK} = new W3C::Rdf::SqlDB::Property($self->{STATEMENTS_CLASS}, 'id', undef, undef, undef);
    $self->{STATEMENTS_CLASS}->addIndex(new W3C::Rdf::SqlDB::PrimaryKey($self->{STATEMENTS_CLASS}, 'PRIMARY', [$self->{STATEMENTS_PK}], 1));
    $self->{TABLES}{'__Holds__'} = $self->{STATEMENTS_CLASS};

    $self->{RDFIDS_CLASS} = new W3C::Rdf::SqlDB::Class('__Nodes__');
    $self->{RDFIDS_PK} = new W3C::Rdf::SqlDB::Property($self->{RDFIDS_CLASS}, 'id', undef, undef, undef);
    $self->{RDFIDS_CLASS}->addField($self->{RDFIDS_PK});
    $self->{RDFIDS_CLASS}->addIndex(new W3C::Rdf::SqlDB::PrimaryKey($self->{RDFIDS_CLASS}, 'PRIMARY', [$self->{RDFIDS_PK}], 1));
    $self->{TABLES}{'__Nodes__'} = $self->{RDFIDS_CLASS};
    $self->{SUBJECT_PROPERTY} = new W3C::Rdf::SqlDB::HoldsProperty($self->{STATEMENTS_CLASS}, 'subject', undef, undef, undef);
    $self->{STATEMENTS_CLASS}->addField($self->{SUBJECT_PROPERTY});
    $self->{SUBJECT_PROPERTY}->setTarget($self->{RDFIDS_PK});

    $self->{STATEMENTS_CLASS}->addField($self->{SUBJECT_PROPERTY});
    $self->{CACHE_NODES_IDS} = {};
    $self->{CACHE_NODES_IDS_QUEUE} = [];
    $self->{CACHE_NODES_IDS_QUEUED} = {};

    $self->{CACHE_ATTRIBUTIONS_IDS} = {};	# cache of loaded Attribution lists
    $self->{TERM2ATTRIBUTION} = {};		# mapping from term to a proof

    $self->{CACHE_ATTRLISTS_IDS_QUEUE} = [];
    $self->{CACHE_ATTRLISTS_IDS_QUEUED} = {};

    $self->{CACHE_ATTRIBUTIONS_IDS_QUEUE} = [];
    $self->{CACHE_ATTRIBUTIONS_IDS_QUEUED} = {};

    $self->{NodesToRefresh} = {};
    return $self;
}

sub disconnect {
    my ($self) = @_;
    if ($self->{DB}) {
	$self->{DB}->disconnect;
	delete $self->{DB};
    }
}

sub _compileStructure {
    my ($self, $structure) = @_;
    my $tables = {};

    # First pass through the compiled structure -- create fields.
    foreach my $tableStr (keys %$structure) {
	my $tableDesc = $structure->{$tableStr};
	my $table = new W3C::Rdf::SqlDB::Class($tableStr);
	$tables->{$tableStr} = $table;

	foreach my $fieldName (keys %{$tableDesc->{-fields}}) {
	    my $field = $tableDesc->{-fields}{$fieldName};
	    my $reqAuth = $self->{-properties}->getI("auth.group.$tableStr.$fieldName");
	    my $requires = undef;
	    my $as = $self->{-properties}->getI("auth.calledWith.group");
	    if ($as !~ m/$reqAuth/) {
		$requires = $reqAuth;
	    }
	    $table->addField(new W3C::Rdf::SqlDB::Property($table, $fieldName, 
				   $field->{-default}, $field->{-type}, 
				   $field->{-size}, $requires));
	}
    }

    # Pass through again, setting pointers to the already established fields.
    foreach my $tableStr (keys %$structure) {
	my $tableDesc = $structure->{$tableStr};
	my $table = $tables->{$tableStr};

	# Set up foreign key pointers.
	foreach my $fieldName (keys %{$tableDesc->{-fields}}) {
	    my $field = $tableDesc->{-fields}{$fieldName};
	    my $fieldOb = $table->getFieldByName($fieldName);
	    if (my $target = $field->{-target}) {
		$fieldOb->setTarget($tables->{$target->[0]}->getFieldByName($target->[1]));
	    }
	}

	# Set up index descriptions.
	foreach my $indexName (keys %{$tableDesc->{-index}}) {
	    my $index = $tableDesc->{-index}{$indexName};
	    my $sequence;
	    foreach my $fieldName (@{$index->{-sequence}}) {
		push (@$sequence, $table->getFieldByName($fieldName));
	    }
	    $table->addIndex(new W3C::Rdf::SqlDB::PropertySet($table, $indexName, $sequence, $index->{-unique}));
	}

	# The primary key is a special index.
	if (my $pkStrs = $tableDesc->{-primaryKey}) {
	    if (!(ref $pkStrs eq 'ARRAY')) {
		$pkStrs = [$pkStrs];
	    }
	    my $pk = [];
	    foreach my $fieldName (@$pkStrs) {
		push (@$pk, $table->getFieldByName($fieldName));
	    }
	    $table->addIndex(new W3C::Rdf::SqlDB::PrimaryKey($table, 'PRIMARY', $pk, 1));
	}
	# print $table->toString,"\n";
    }

    return $tables;
}

sub getAlgaeInterface {
    my ($self, @args) = @_;
    return $self;
    my $queryHandler = new W3C::Rdf::SqlDBAlgae(-atomDictionary => $self->{-atomDictionary}, 
						-errorHandler => $self->{-errorHandler}, 
						-db => $self, 
						-duplicateFieldsInQuery => 0, 
						-checkUnderConstraintsBeforeQuery => 1, 
						-checkOverConstraintsOnEmptyResult => 0, @args);
    $queryHandler->addSource($self); # !!! didn't follow API change 20070801
    return $queryHandler;
}

sub _toAlgae {
    my ($pos, $name, $algae2) = @_;
    if (!$pos) {
    } elsif ($pos->isa('W3C::Rdf::Uri')) {
	return NPnew W3C::Rdf::AlgaeCompileTree::Url($pos->getUri(), $algae2);
    } elsif ($pos->isa('W3C::Rdf::String')) {
	my $dt = $pos->getDatatype() ? $pos->getDatatype()->getUri() : undef;
	return NPnew W3C::Rdf::AlgaeCompileTree::Literal($pos->getString(), $dt, $algae2);
    } elsif ($pos->isa('W3C::Rdf::BNode')) {
	&throw(new W3C::Util::Exception(-message => "bNode invalid argument to triplesMatching"));
    } else {
	&throw(new W3C::Util::Exception(-message => "$pos invalid argument to triplesMatching"));
    }
}

# triplesMatching - simple interface to algae query mechanism
sub triplesMatching {
    my ($self, $view, $lookFors, $flags) = @_;

    my $ret = new W3C::Rdf::RdfDB(-atomDictionary => $self->{-atomDictionary});
    foreach my $lookFor (@$lookFors) {
	my ($p, $s, $o) = @$lookFor;

	my $tAlgae = new W3C::Rdf::Algae2(-atomDictionary => $self->{-atomDictionary}, 
					  -namespaceHandler => $self->{-namespaceHandler}, 
					  -sourceAttribution => $self->{-sourceAttribution}, 
					  -rdfDB => $ret);
	my $parts = [&_toAlgae($p, 'pred', $tAlgae), 
		     &_toAlgae($s, 'subj', $tAlgae), 
		     &_toAlgae($o, 'obj', $tAlgae)];
	my $term = NPnew W3C::Rdf::AlgaeCompileTree::Decl($parts, [], $tAlgae);
    }
    return $ret->getTriples();

    my @results;
    foreach my $lookFor (@$lookFors) {
	my ($p, $s, $o, $c, $r, $a) = @$lookFor;

	my $property = $self->_getDBProperty($p);
	my $tableStr = $property->getTable->getName;
	my $fieldStr = $property->getName;
	my $target = $property->getTarget;
	my $targetTable = $target ? $target->getTable->getName : '';
	my $targetField = $target ? $target->getName : '';

	# data structures used to characterize query
	my $constraints = [];
	my $selectFields = [];

	if ($s) {
	    my $subjectStr;
	    if ($s->isa('W3C::Rdf::Uri')) {
		$subjectStr = $s->getUri;
	    } else {
		&throw(new W3C::Util::NotImplementedException(-class => 'W3C::Rdf::SqlDB', 
							      -method => "triplesMatching subject $s"));
	    }
	    push (@$constraints, @{$self->_decomposeUniques($subjectStr, 'subject', $tableStr)});
	} else {
	    push (@$selectFields, [$tableStr, $fieldStr, 'subject', $SUBST_SUBJ, $self->_uniquesFor($tableStr)]);
	}

	if ($o) {
	    my $objectStr;
	    if ($o->isa('W3C::Rdf::String')) {
		$objectStr = $o->getString;
	    } elsif ($o->isa('W3C::Rdf::Uri')) {
		$objectStr = $o->getUri;
	    } else {
		&throw(new W3C::Util::NotImplementedException(-class => 'W3C::Rdf::SqlDB', 
							      -method => "triplesMatching object $o"));
	    }
	    if ($target) {
		push (@$constraints, @{$self->_decomposeUniques($objectStr, 'target', $targetTable)});
	    } else {
		push (@$constraints, "subject.$fieldStr=\"$objectStr\"");
	    }
	} else {
	    if ($target) {
		push (@$selectFields, [$targetTable, $fieldStr, 'target', $SUBST_OBJ, $self->_uniquesFor($targetTable)]);
	    } else {
		push (@$selectFields, [$tableStr, $fieldStr, 'subject', $SUBST_OBJ, $fieldStr]); # @@@ check if these should differ
	    }
	}

	if (!@$selectFields) {
	    # We were supplied with p s o so we are only testing truth.
	    push (@$selectFields, [$tableStr, $fieldStr, 'subject', $SUBST_NONE, \$TEST]);
	}

	if ($target) {
	    push (@$constraints, "subject.$fieldStr=target.$targetField");
	}

	if (!@$constraints) {
	    push (@$constraints, "1");
	}

	my $fromStr = $target ? "$tableStr AS subject,$targetTable AS target" : "$tableStr AS subject";
	my $whereStr = join (' AND ', @$constraints);
	my $selectStr = &_selectStr($selectFields);

	# silly debugging stuff
	my $selectSpelling = 'SELECT';
	if ($s && $o) {
	    if ($target) { # joined,semiAcls
		$selectSpelling = 'Select'; # literal
	    } else { # disjoint,semiIds
		$selectSpelling = 'sElect'; # literal
	    }
	} elsif ($s) {
	    if ($target) { # joined,semiIds,semiAcls
		$selectSpelling = 'seLect';
	    } else { # disjoint,semiIds,semiAcls
		$selectSpelling = 'selEct'; # literal
	    }
	} elsif ($o) {
	    if ($target) { # disjoint,joined,semiIds,semiAcls
		$selectSpelling = 'seleCt';
	    } else { # disjoint,joined,semiIds,semiAcls
		$selectSpelling = 'selecT';
	    }
	}

	# query and grab results
	my $query = "$selectSpelling $selectStr FROM $fromStr WHERE $whereStr";
	my @queryRes;
	$self->{DB}->executeArrayQuery(\@queryRes, $query);
	foreach my $answerRow (@queryRes) {
	    my $col = 0;

	    # note: We tromp over $p $s $o to do the triple substitution but
	    #       we should be done with them by now anyways. Each row will
	    #       inherit the tromped values from before, but will replace
	    #       them with its own values before creating a new statement.
	    foreach my $fieldInfo (@$selectFields) {
		($p, $s, $o) = $self->_answerRowToTriple($fieldInfo, $answerRow, \$col, $p, $s, $o);
	    }
	    my $statement = new W3C::Rdf::MappedTriple($self, $p, $s, $o, $self->{-sourceAttribution});
	    push (@results, $statement);
	}
    }
    return @results;
}

sub clearAttribution {
    my ($self, $attribution) = @_;
    $self->{NodesToRefresh}{$attribution} = $attribution;
}

sub refreshNode {
    my ($self, $node) = @_;
    return delete $self->{NodesToRefresh}{$node};
}

sub addTriple {
    my ($self, $triple, $attribution) = @_;
    my $property = $self->_getDBProperty($triple->getPredicate);
    my $tableStr = $property->getTable->getName;
    my $fieldStr = $property->getName;
	my $property = $self->_getDBProperty($triple->getPredicate);
	return $property->processAssertion($triple, $self, $attribution);
    my $constraints = $self->_decomposeUniques($triple->getSubject->getUri, $tableStr, $tableStr);
    my $object = $triple->getObject;
    my $objectStr;
    if ($object->isa('W3C::Rdf::Uri')) {
	$objectStr = $object->getUri;
    } elsif ($object->isa('W3C::Rdf::String')) {
	$objectStr = $object->getString;
    } else {
	&throw(new W3C::Util::NotImplementedException(-class => 'W3C::Rdf::SqlDB', 
						      -method => "addTriple object $object"));
    }
    $objectStr = $self->{DB}->escape($objectStr);
    my $query = "UPDATE $tableStr SET $fieldStr=$objectStr WHERE ".join (" AND ", @$constraints);
    $self->{DB}->executeUpdate($query);
    return $self->SUPER::addTriple($triple);
}

# Dreadfully oversimplified. Doesn't handle moving an ID from fruitbread to breadfruit.
sub changeId {
    my ($self, $view, $from, $to) = @_;
    my $property = $self->_getDBProperty($from);
    $property->changeId($from, $to, $self);
#    return SUPER::changeId($view, $from, $to);
    return $to;
}

sub _answerRowToTriple {
    my ($self, $fieldInfo, $answerRow, $pCol, $p, $s, $o) = @_;
    my ($table, $field, $as, $pos, $fieldz) = @$fieldInfo;
    if (ref $fieldz eq 'ARRAY') {
	my $valueHash = {};
	for (my $i = 0; $i < @$fieldz; $i++) {
	    $valueHash->{$fieldz->[$i]} = $answerRow->[$$pCol + $i];
	}
	my $uri = $self->{-atomDictionary}->getUri($self->_composeUniques($valueHash, $table));
	if ($pos & $SUBST_PRED) {$p = $uri} 
	if ($pos & $SUBST_SUBJ) {$s = $uri} 
	if ($pos & $SUBST_OBJ) {$o = $uri} 
	$$pCol += @$fieldz;
    } else {
	if ($pos != $SUBST_NONE) {
	    # @@@ add mappings from SQL datatype to XSD datatypes here!
	    my $str = $self->{-atomDictionary}->getString($answerRow->[$$pCol], undef, 'PLAIN');
	    if ($pos & $SUBST_PRED) {$p = $str} 
	    if ($pos & $SUBST_SUBJ) {$s = $str} 
	    if ($pos & $SUBST_OBJ) {$o = $str} 
	}
	$$pCol++;
    }
    return ($p, $s, $o);
}

sub _getDBProperty {
    my ($self, $p, $s) = @_;

    # get table info based on predicate
    if (!defined $p) {
	&throw(new W3C::Util::NotImplementedException(-class => 'W3C::Rdf::SqlDB', 
						      -method => "_getDBProperty(undef)"));
    }
    if (ref $p eq 'SCALAR') {
	return new W3C::Rdf::SqlDB::WildcardProperty($p, $self->{TABLES});
    }
    my $predicate = $p->getUri;
    my ($table, $field);

    # First look for predicate maps for this URI.
    if (my $mapping = $self->{PREDICATE_MAP}{$predicate}) {
	($table, $field) = @$mapping;

    # Fall back to URI deconstruction.
    } else {
	if ($predicate !~ m/\A$self->{BASE_URI}(\w+)\Q$SEP_ATTRIB\E(\w+)\Z/) {
	    return $self->{TABLES}{'__Holds__'}->getPropertyByName('subject');
	    # &throw(new W3C::Util::Exception(-message => "unknown predicate \"$predicate\""));
	}
	($table, $field) = ($1, $2);
    }

    # The property object is a function of the table and field names.
    if (!exists $self->{TABLES}{$table}) {
	&throw(new W3C::Util::Exception(-message => "nothing known about table \"$table\""));
    }

    my $property = $self->{TABLES}{$table}->getPropertyByName($field);
    if (!$property) {
	&throw(new W3C::Util::Exception(-message => "field \"$field\" unknown for table \"$table\""));
	# return $self->{TABLES}{'__Holds__'}->getPropertyByName('subject');
    }
    return $property;
}

sub _selectStr {
    my ($selects) = @_;
    my @ret;
    foreach my $select (@$selects) {
	my ($table, $field, $as, $pos, $fieldz) = @$select;
	if (ref $fieldz eq 'ARRAY') {
	    push (@ret, map {"$as.$_"} @$fieldz);
	} elsif ($fieldz == \$TEST) {
	    push (@ret, 1);
	} elsif (ref $fieldz) {
	    &throw(new W3C::Util::ProgramFlowException());
	} else {
	    push (@ret, "$as.$fieldz");
	}
    }
    return join (',', @ret);
}

sub _uniquesFor {
    my ($self, $table) = @_;
    return map {$_->getName} @{$self->{TABLES}{$table}->getPrimaryKey->getSequence};
}

sub _composeUniques {
    my ($self, $values, $table) = @_;
    return "$self->{BASE_URI}$table$SEP_ATTRIB".$self->_composeUniqueSuffix($values, $table, $SEP_KEY);
}

sub _composeUniqueSuffix {
    my ($self, $values, $table, $separator) = @_;
    my $segments = [];
    my $pk = [$self->_uniquesFor($table)];
    if (!$pk) {
	&throw(new W3C::Util::Exception(-message => "no primary key for table $table"));
    }
    foreach my $field (@$pk) {
	if (ref $values eq 'HASH') { # values is a hash of key values.
	    if (exists $values->{$field}) {
		my $lvalue = &CGI::escape($field);
		my $rvalue = &CGI::escape($values->{$field});
		push (@$segments, "$lvalue$SEP_VALUE$rvalue");
	    } else {
		&throw(new W3C::Util::Exception(-message => "no value for $field"));
	    }
	} else { # values is a table alias.
	    push (@$segments, "\"$field=\", $values.$field");
	}
    }
    return join ($separator, @$segments);
}

# $uri - row id for a table
# $tableAs - how table should be known in constraints
# $table - real name of table (for checking against uri id)
sub _decomposeUniques {
    my ($self, $uri, $tableAs, $table) = @_;
    my $pTable = undef;
    if (ref $table eq 'SCALAR') {
	$pTable = $table;
	$table = $$pTable ? $$pTable : undef;
    }
    if ($uri !~ m/\A$self->{BASE_URI}(\w+?)\Q$SEP_ATTRIB\E([\w\d\%\Q$SEP_VALUE\E\&]+)\Z/ || 
	(defined $table && $1 ne $table)) { #  && $table ne '__Holds__' && $table ne '__Nodes__'
	&throw(new W3C::Rdf::SqlDB::UnknownRelationException(-message => "\"$uri\" not based on $self->{BASE_URI}$table"));
    }
    if ($pTable) {
	$$pTable = $1;
    }
    my $tablePrefix = $tableAs ? ".$tableAs" : '';
    my $recordId = &CGI::unescape($2);
    my @specifiers = split('&', $recordId);
    my $constraints = [];
    foreach my $specifier (@specifiers) {
	my ($field, $value) = split ($SEP_VALUE, $specifier);
	$field = &unescapeName($field);
	$field = &unescapeName($field);
	push (@$constraints, "$tablePrefix$field=\"$value\"");
    }
    return $constraints;
}

sub _constrainKey {
    my ($self, $qp, $tableAs, $table, $outer, $allowGenericNode) = @_;
    my $uri = $qp->symbol;
    my $pTable = undef;
    if (ref $table eq 'SCALAR') {
	$pTable = $table;
	$table = $$pTable ? $$pTable : undef;
    }
    my ($foundTable, $ret);
    if ($uri =~ m/\A$self->{BASE_URI}(\w+?)\Q$SEP_ATTRIB\E([\w\d\%\Q$SEP_VALUE\E\&]+)\Z/ && (!defined $table || $1 eq $table)) {
	$foundTable = $1;
	my $recordId = &CGI::unescape($2);
	foreach my $specifier (split($SEP_KEY, $recordId)) {
	    my ($field, $value) = split ($SEP_VALUE, $specifier);
	    $field = &unescapeName($field);
	    $value = &unescapeName($value);
	    $ret = $self->_addWhereConst($tableAs, $field, '=', $value, $qp, $outer);
	}
    } elsif ($allowGenericNode) {
	my $hash = &W3C::Rdf::SqlDB::HoldsProperty::_hashNode($uri);
	$ret = $self->_addWhereConst($tableAs, 'hash', '=', $hash, $qp, $outer);
    } else {
	&throw(new W3C::Util::Exception(-message => "\"$uri\" not based on $self->{BASE_URI}$table"));
    }
    if ($pTable) {
	$$pTable = $foundTable;
    }
    return $ret;
}

################################################################################
################################################################################
################################################################################
################################################################################
################################################################################
################################################################################

# Optimize by making lookfor(var, resultSet, row) 
# into lookfor(var, resultSet) return a col number instead of a value.
# Then walk the results
#   for (my $e = $resultSet->elements; $e->hasMoreElements;) {
#	my $row = $e->nextElement;
#	my $query = $self->_buildQuery($these, $those, $thats, $row);
#	...

sub dbEvaluateQTerm {
    my ($self, $resultSet, $exprs, $dbSpec) = @_;
    # SQL query components:
    $self->{SELECTS} = [];		# Tables and aliases to SELECT.

    $self->{BINDER} = new W3C::Rdf::SqlDB::Binder($self);
    $self->{DISJUNCTION_BOUND} = {};	# Which OR clauses are in SELECT.

    $self->{SELECTED_ALIASES} = {};	# Which alias.fields are in SELECT.
    $self->{SCALAR_REFERENCES} = {};	# Where scalar variables were used.

    # Keeping track of [under]constraints
    $self->{CONSTRAINT_REACHES} = {};	# Transitive closure of all aliases
					# constrained with other aliases.
    $self->{CONSTRAINT_HINTS} = {};	# Aliases constrained in some but not
					# all paths of an OR. Handy diagnostic.
    $self->{OVER_CONSTRAINTS} = {};	# Redundent constraints between aliases.

    $self->{TERM2ATTRIBUTION} = {};	# Proofs for each term solution.

    $self->{TERM2STATEMENTID} = {};
    $self->{STATEMENT2ID} = {};

    if ($resultSet->elements()->hasMoreElements()) {
	$self->_processQueries($exprs, $resultSet);
    }
    # $exprs->evaluateQTerm($resultSet, $self);
}

sub dbEvaluateAssertion {
    my ($self, $resultSet, $exprs, $dbSpec, $visited, $trigger, $attribution) = @_;
    my $insertions = [];

    push (@$insertions, $exprs->evaluateAssertion($resultSet, $self, {}, undef, $attribution)); # $self->{-assertionAttribution}

    foreach my $insertion (@$insertions) {
	my ($triple, $reified) = @$insertion;
	my $property = $self->_getDBProperty($triple->getPredicate);
	push (@$insertion, $property);
    }

    # @@@ Walk lists predicates and see if any need to be grouped.
    # Gather those with the same relation together so they can represent
    # a new state that passes integrity constraints.
    # Order by least unmeetable dependencies on NON NULLs.
    # Calculate path through foreign keys to start with bottom of the tree.
    # Write a thesis. Write an application. Make a bundle. Move off the grid.

    # Process remaining ones (either relations or holds).
##    foreach my $insertion (@$insertions) {
##	my ($triple, $reified, $property) = @$insertion;
###	foreach my $attribution ($triple->getAttributionList()->getAllDirect()) {
##	    my @reified = $property->processAssertion($triple, $self, $attribution);
###	}
##	#my $statement = $self->applyRules(\@reified, $triple);
##    }
    return @$insertions;
}

sub dbEvaluateDeletion {
    my ($self, $resultSet, $exprs, $dbSpec, $visited, $trigger, $attribution) = @_;
    my $insertions = [];

    push (@$insertions, $exprs->evaluateDeletion($resultSet, $self, {}, undef, $attribution)); # $self->{-deletionAttribution}

    foreach my $insertion (@$insertions) {
	my ($triple, $reified) = @$insertion;
	my $property = $self->_getDBProperty($triple->getPredicate);
	push (@$insertion, $property);
    }

    # @@@ Walk lists predicates and see if any need to be grouped.
    # Gather those with the same relation together so they can represent
    # a new state that passes integrity constraints.
    # Order by least unmeetable dependencies on NON NULLs.
    # Calculate path through foreign keys to start with bottom of the tree.
    # Write a thesis. Write an application. Make a bundle. Move off the grid.

    # Process remaining ones (either relations or holds).
    foreach my $insertion (@$insertions) {
	my ($triple, $reified, $property) = @$insertion;
	my @reified = $property->processDeletion($triple, $self);
	#my $statement = $self->applyRules(\@reified, $triple);
    }
}

sub executeArrayQuery {$_[0]->{DB}->executeArrayQuery(@_[1..@_-1])}
sub executeWideQuery {$_[0]->{DB}->executeWideQuery(@_[1..@_-1])}
sub executeSingleQuery {$_[0]->{DB}->executeSingleQuery(@_[1..@_-1])}
sub executeUpdate {$_[0]->{DB}->executeUpdate(@_[1..@_-1])}
sub escape {$_[0]->{DB}->escape(@_[1..@_-1])}

sub _processQueries {
    my ($self, $querySets, $resultSet) = @_;

    # find SQL query elements by their statements position
    my $wheres = undef;
    eval {
	my $cell = undef;
	$wheres = $self->_walkQuery($querySets, $self->{BINDER}, $cell, 0, 0, 0, undef);
    }; if ($@) {
	# Handy early return on queries with empty result sets:
	if (my $ex = &catch('W3C::Database::NoCreateException')) {
	    return;
	} else {&throw()}
    }

    if (1) { # @@@calling $self->{-checkUnderConstraintsBeforeQuery}) { # see other underconstraint check
	$self->_checkForUnderConstraint();
    }

    $querySets->{ALGAE2}->dumpStuff('Compiled', $self, $wheres);
    $querySets->{ALGAE2}->dumpStuff('CompiledGraph', $self, $wheres);
    $self->{ONS} = {};

    # SCALAR CONSTRAINT ITERATION:

    # We have a set of bindings from earlier asks. We substitute those bindings
    # into the queries to further constrain the queries. For efficiency, the
    # constraints from each solution are aggregated in a larger disjunction
    # which is executed. _buildResults uses $rowConstraints to associate the
    # results with the constraints from each solution.

    my $firstRow = $resultSet->elements()->nextElement();
    my $rowConstraints = new W3C::Rdf::SqlDB::RowConstraintHash($firstRow, $self->{BINDER}->getBindings());

    # Efficiency hack: count on resultSet not changing until we iterate through
    # the results (specfically, the nth row now will represent the same tuple as
    # the nth row during _buildResults). Thus, the number each row in the
    # binding iteration will correspond to a row in this iteration.

    for (my ($e, $rowNo) = ($resultSet->elements, 0); $rowNo++, $e->hasMoreElements;) {
	my $row = $e->nextElement;
	$rowConstraints->indexResultSetRow($row, $rowNo, $self);
    }

    my $bindingConstraints = $rowConstraints->getConstraints();
    my $query = $self->_buildQuery($querySets, $bindingConstraints, $wheres, 0, 0);
    $resultSet->addMessage("SQL Query: $query");

    my $queryRes = [];
    $self->{DB}->executeArrayQuery($queryRes, $query);
    if (!@$queryRes && $self->{-checkOverConstraintsOnEmptyResult}) {
	$self->_checkForOverConstraint;
    }
    foreach my $answerRow (@$queryRes) {
	$rowConstraints->indexSqlRows($answerRow);
    }

    for (my ($e, $rowNo) = ($resultSet->elements, 0); $rowNo++, $e->hasMoreElements;) {
	my $row = $e->nextElement;

	my $rows = $rowConstraints->getRelatedSqlRows($row, $rowNo);
	$self->_buildResults($rows, $querySets, $row);

	# By contract with the ResultSet enumerator, we eliminate the (probably
	# duplicated) row. BUT, don't eliminate the row if our first term was an
	# optional triple and we didn't get any results.
	if (!($querySets->isa('W3C::Rdf::AlgaeCompileTree::Option') && 
	      !@$queryRes)) {
	    $row->eliminate;
	}
    }
}

sub _walkQuery {
    my ($self, $term, $binder, $cell, $disjunction, $negation, $outer, $attribution) = @_;
    my $ret;
    if ($term->isa('W3C::Rdf::AlgaeCompileTree::Decl')) {
	# Process simple term by looking in app-optimized DB or in __Holds__.
	my $property = $self->_getDBProperty($term->getSlot(0)->lookfor, $term->getSlot(1)->lookfor);
	$ret = $property->processMatch($term, $binder, $cell, $self, $disjunction, $negation, $outer, $attribution);
    } elsif ($term->isa('W3C::Rdf::AlgaeCompileTree::Constraint')) {
	# Process simple term by looking in app-optimized DB or in __Holds__.
	my $cWheres = [];
	$term->toSQL($self, $term, $cWheres, $outer);
	$ret = $cWheres->[0];
    } elsif ($term->isa('W3C::Rdf::AlgaeCompileTree::Conjunction')) {
	my $l = $self->_walkQuery($term->getLeft, $binder, $cell, $disjunction, $negation, $outer, $attribution);
	my $r = $self->_walkQuery($term->getRight, $binder, $cell, $disjunction, $negation, $outer, $attribution);
	if ($l && $r) {
	    $ret = $l->newConjunction($r);
	} else {
	    $ret = ($l || $r);
	}
    } elsif ($term->isa('W3C::Rdf::AlgaeCompileTree::ShortcutDisjunction')) {

	my $disjunctionBinder = new W3C::Rdf::SqlDB::DisjunctionBinder($self, $binder);
	my $l = $self->_walkQuery($term->getLeft(), $disjunctionBinder, $cell, 0, $negation, $outer, $attribution);
	$disjunctionBinder->reuseMode();
	my $r = $self->_walkQuery($term->getRight(), $disjunctionBinder, $cell, 0, $negation, $outer, $attribution);
	my $reuseDisjunctions = $disjunctionBinder->finishReuse();

	# set aliases to max of either l or r.
	# create new constraint based on l and r subconstraints.

	if ($l && $r) {
	    my $new;
	    $ret = $l->newDisjunction($r, \ $new);
	    $self->_selectDisjunction($term->getLeft, $binder, $new->{LEFT});
	    $self->_selectDisjunction($term->getRight, $binder, $new->getRight);
	} else {
	    $ret = ($l || $r);
	}

	if ($reuseDisjunctions) {
	    my $new;
	    $ret = $ret ? $ret->newDisjunction($reuseDisjunctions, \ $new) : 
		$reuseDisjunctions;
	}

    } elsif ($term->isa('W3C::Rdf::AlgaeCompileTree::Negation')) {
	$ret = $self->_walkQuery($term->getDecl(), $binder, $cell, $disjunction, !$negation, $outer, $attribution);
    } elsif ($term->isa('W3C::Rdf::AlgaeCompileTree::Option')) {
	$ret = $self->_walkQuery($term->getDecl(), $binder, $cell, $disjunction, $negation, 1, $attribution);
    } elsif ($term->isa('W3C::Rdf::AlgaeCompileTree::Ask')) {
	my $url = $term->{ALGAE2}->getNameBySource($term->getDB);
	my $cWheres = [];
	my $algae = $self;
	my $r = NPnew W3C::Rdf::AlgaeCompileTree::Url($url, $term->{ALGAE2});
	my $s = $r;
			my ($alias1, undef) = $binder->_getNewTableAlias('__AttrLists__', $s, $binder, $outer, 1, $PREFIX_ALIAS, 1);
			#my $wheres4 = $algae->_addWhereField($statementsAlias, 'a', '=', $alias1, 'listId', $term, $outer);
			#push (@$cWheres, $wheres4);
			my ($alias2, undef) = $binder->_getNewTableAlias('__Attributions__', $s, $binder, $outer, 1, $PREFIX_ALIAS, 1);
			my $wheres5 = $algae->_addWhereField($alias1, 'a', '=', $alias2, 'id', $term, $outer);
			push (@$cWheres, $wheres5);
			my ($alias3, $wheres3) = $binder->_getNewTableAlias('__Nodes__', $r, $binder, $outer, 1, $PREFIX_ALIAS, 0);
			push (@$cWheres, $wheres3);
			my $wheres6 = $algae->_addWhereField($alias2, 'doc', '=', $alias3, 'id', $term, $outer);
			push (@$cWheres, $wheres6);
	$attribution = [$alias1, $cWheres];
	$ret = $self->_walkQuery($term->{DECLS}, $binder, $cell, $disjunction, $negation, $outer, $attribution);
    } else {
	my $ref = ref $term;
	&throw(new W3C::Util::Exception(-message => "unable to compile $ref into SQL"));
    }
    if (0 && @{$term->{CONSTRAINTS}}) { # !!!
	my $strs = join("/n", map {$_->toString()} @{$term->{CONSTRAINTS}});
	&throw(new W3C::Util::Exception(-message => "can't enforce $strs"));
    }
    return $ret;
}

sub queueResolveNodeId {
    my ($self, $id) = @_;
    if (defined $id && !$W3C::Rdf::SqlDB::HoldsProperty::CACHE_dbIdToNode->{$id} && !$self->{CACHE_NODES_IDS_QUEUED}{$id}) {
	push (@{$self->{CACHE_NODES_IDS_QUEUE}}, $id);
	$self->{CACHE_NODES_IDS_QUEUED}{$id} = $id;
    }
}
sub resolveNodeId {
    my ($self, $id) = @_;
    $self->queueResolveNodeId($id);
    my @a;

    if (@{$self->{CACHE_NODES_IDS_QUEUE}}) {
	#    $self->{DB}->executeWideQuery(\@a, "
	#SELECT type,str,big,attribOrDT
	#FROM __Nodes__
	#WHERE id=$id");
	#    my ($type, $str, $big, $attribOrDt) = @a;
	$self->{DB}->executeArrayQuery(\@a, "
SELECT __Nodes__.id,__Nodes__.type,__Nodes__.str,__Nodes__.big,
       __Attributions__.type,__Attributions__.auth,__Attributions__.modified,__Attributions__.created,
       DT.id,DT.str,
       doc.str
  FROM __Nodes__ 
       LEFT OUTER JOIN __Attributions__ ON __Nodes__.attribOrDt=__Attributions__.id
       LEFT OUTER JOIN __Nodes__ AS DT ON __Nodes__.attribOrDt=DT.id
       LEFT OUTER JOIN __Nodes__ AS doc ON __Attributions__.doc=doc.id
 WHERE __Nodes__.id IN (".join (',', @{$self->{CACHE_NODES_IDS_QUEUE}}).")");
	foreach my $row (@a) {
	    $self->internNode(@$row);
	}
	$self->{CACHE_NODES_IDS_QUEUE} = [];
	$self->{CACHE_NODES_IDS_QUEUED} = {};
    }
    return $W3C::Rdf::SqlDB::HoldsProperty::CACHE_dbIdToNode->{$id};
}
sub internNode {
    my ($self, 
	$id, $type, $str, $big, 
	$attribType, $auth, $modified, $created,
	$dtId, $dtUri, 
	$doc) = @_;

    if ($big) {
	$str = $self->{DB}->executeSingleQuery("
SELECT str
FROM __Big__
WHERE id=$big");
    }
    &utf8::decode($str);

    my $atom;
    if ($type eq 'uri') {
	$atom = $self->{-atomDictionary}->getUri($str);
    } elsif ($type eq 'literal') {
	if ($str !~ m/^(\d+)?([PX])(.*?):(.*)$/s) {
	    &throw(new W3C::Util::Exception(-message => "invalid literal encoding \"$str\""));
	}
	my ($dt1, $encoding, $lang, $string) = ($1, $2, $3, $4);
	my $encoding = $encoding eq 'X' ? 'XML' : $encoding eq 'P' ? 'PLAIN' : &throw(new W3C::Util::ProgramFlowException());
	my $dtAtom = undef;
	if (defined $dtId) {
	    $dtAtom = $W3C::Rdf::SqlDB::HoldsProperty::CACHE_dbIdToNode->{$dtId};
	    if (!$dtAtom) {
		$dtAtom = $self->{-atomDictionary}->getUri($dtUri);
		$W3C::Rdf::SqlDB::HoldsProperty::CACHE_dbIdToNode->{$dtId} = $dtAtom;
	    }
	}
	$atom = $self->{-atomDictionary}->getString($string, $dtAtom, $encoding);
	if ($lang) {
	    $lang = $self->{-atomDictionary}->getString($lang, undef, 'PLAIN');
	    $atom->setLang($lang);
	}
    } elsif ($type eq 'table') {
	if ($str !~ m/^([^,]+)/gc) {
	    &throw(new W3C::Util::Exception(-message => "invalid table specifier at start of \"$str\""));
	}
	my $table = $1;
	my @valuePairs = $str =~ m/(?:,([^=]+)=\"([^\"]+)\")/gc;
	if (!@valuePairs || $str =~ /(.)/gc) {
	    &throw(new W3C::Util::Exception(-message => "invalid key/value encoding $1 at \"".substr($str, pos $str)."\""));
	}
	my @keyValues;
	while (@valuePairs) {
	    push (@keyValues, shift (@valuePairs).$SEP_VALUE.shift (@valuePairs));
	}
	my $keySpecifier = join ($SEP_KEY, @keyValues);
	$atom = $self->{-atomDictionary}->getUri("$self->{BASE_URI}$table$SEP_ATTRIB$keySpecifier");
    } elsif ($type eq 'bnode') {
	$doc = $self->{-atomDictionary}->getUri($doc);
	$auth = $auth ? $self->{-atomDictionary}->getUri($auth) : undef;
	my $attribution = $attribType eq 'source' ? 
	    $self->{-atomDictionary}->getGroundFactAttribution($doc, undef, $auth, undef) : 
	    $attribType eq 'generated' ? 
	    $self->{-atomDictionary}->getInferenceAttribution(undef, undef) : 
	    $attribType eq 'reified' ? &throw(new W3C::Util::NotImplementedException()) : 
	    &throw(new W3C::Util::ParameterException(-parameter => 'attribType', -value => $attribType));
	$atom = $self->{-atomDictionary}->createBNode($attribution);
    } else {
	&throw(new W3C::Util::ProgramFlowException());
    }
    $W3C::Rdf::SqlDB::HoldsProperty::CACHE_dbIdToNode->{$id} = $atom;
    return $atom;
}

# Load AttributionLists by id.
sub _queueResolveAttrListId {
    my ($self, $id) = @_;
    if (defined $id && !$W3C::Rdf::SqlDB::HoldsProperty::CACHE_dbIdToAttrList->{$id} && !$self->{CACHE_ATTRLISTS_IDS_QUEUED}{$id}) {
	push (@{$self->{CACHE_ATTRLISTS_IDS_QUEUE}}, $id);
	$self->{CACHE_ATTRLISTS_IDS_QUEUED}{$id} = $id;
    }
}
sub _resolveAttrListId {
    my ($self, $listId) = @_;
    if (@{$self->{CACHE_ATTRLISTS_IDS_QUEUE}}) {
	my $valueStr = join (',', sort @{$self->{CACHE_ATTRLISTS_IDS_QUEUE}});
	my $query = "SELECT listId,a FROM __AttrLists__ WHERE listId IN ($valueStr)";
	my @a;
	my $lists = {};
	my $libRet = $self->executeArrayQuery(\@a, $query);
	foreach my $row (@a) {
	    my ($listId, $a) = @$row;
	    $self->_queueResolveAttributionId($row->[1]);
	    if (exists $lists->{$listId}) {
		push (@{$lists->{$listId}}, $a);
	    } else {
		$lists->{$listId} = [$a];
	    }
	}
	foreach my $id (keys %$lists) {
	    my @attrs;
	    foreach my $a (@{$lists->{$id}}) {
		push (@attrs, $self->_resolveAttributionId($a))
	    }
	    my $attrList = $self->{-atomDictionary}->getAttributionList(@attrs);
	    $W3C::Rdf::SqlDB::HoldsProperty::CACHE_dbIdToAttrList->{$id} = $attrList;
	    $W3C::Rdf::SqlDB::HoldsProperty::CACHE_attrListToDbId->{$valueStr} = $id;
	}
    }
    return $W3C::Rdf::SqlDB::HoldsProperty::CACHE_dbIdToAttrList->{$listId};
}

# Load Attributions by id.
sub _queueResolveAttributionId {
    my ($self, $id) = @_;
    if (defined $id && !$W3C::Rdf::SqlDB::HoldsProperty::CACHE_dbIdToAttribution->{$id} && !$self->{CACHE_ATTRIBUTIONS_IDS_QUEUED}{$id}) {
	push (@{$self->{CACHE_ATTRIBUTIONS_IDS_QUEUE}}, $id);
	$self->{CACHE_ATTRIBUTIONS_IDS_QUEUED}{$id} = $id;
    }
}
sub _resolveAttributionId {
    my ($self, $attrId) = @_;
    if (@{$self->{CACHE_ATTRIBUTIONS_IDS_QUEUE}}) {
	$self->_loadAttributions($self->{CACHE_ATTRIBUTIONS_IDS_QUEUE});
    }
    return $W3C::Rdf::SqlDB::HoldsProperty::CACHE_dbIdToAttribution->{$attrId};
}

sub _bindFieldToVariable {
    my ($self, $constraintAlias, $constraintField, $datatype, $term, $qp, $binder, $outer) = @_;
    my $scalarReference = $self->{SCALAR_REFERENCES}{$qp->symbol};
    my $ret = undef;
    if ($scalarReference) {
	my ($firstAlias, $firstField) = @$scalarReference;
	$ret = $self->_addWhereField($constraintAlias, $constraintField, '=', 
				     $firstAlias, $firstField, $term, $outer);
    } else {
	$self->_selectVariable($constraintAlias, $constraintField, $datatype, $qp, $binder);
	$self->{SCALAR_REFERENCES}{$qp->symbol} = [$constraintAlias, $constraintField];
    }
    return $ret;
}

sub _getFieldForVariable {
    my ($self, $term, $qp) = @_;
    return @{$self->{SCALAR_REFERENCES}{$qp->symbol}};
}

sub _buildQuery {
    my ($self, $implQuerySets, $bindingConstraints, $wheres, $disjunction, $not) = @_;

    # assemble the query
    my $segments = [];

    push (@$segments, "\nSELECT STRAIGHT_JOIN\n       ");
    my ($selectStr, $groupByStr) = $self->_compileSelects();
    push (@$segments, $selectStr);
    push (@$segments, "\nFROM ");

    # change structure of wheres
    my @froms;
    my @aliases = $self->{BINDER}->getAliases;

    # Walk through aliases finding constriants that bind them to already
    # bound aliases. The first alias is considered bound. Remaining aliases
    # are all bound back to this first alias. This approach depends upon the
    # order of the introduction of terms in the query. For instance, if
    # three terms join A to B, B to C, C to D and we pessimally re-order
    # them (AB CD BC), this algorithm will fail on the CD term. We need to
    # work out a nice algorithm for taking all the aliases constrained by
    # non-optional constraints and re-ordering them optimally. Some day.

    my $firstAlias = shift (@aliases);
    my ($table, $alias) = @$firstAlias;
    push (@froms, "$table AS $alias");
    my $reached = {$alias => 1};		# first alias considered bound
    foreach my $aliasPair (@aliases) {
	my ($table, $alias) = @$aliasPair;
	$reached->{$alias} = 1;
	my $outer = 0;
	# constraint extraction may change the root of the $wheres
	if (!exists $self->{ONS}{$alias}) {
	    $self->{ONS}{$alias} = [];
	    $wheres = $wheres->extractConstraintClause($reached, \$outer, $self->{ONS}{$alias});
	    if (!@{$self->{ONS}{$alias}}) { # see other underconstraint check
		warn "$alias not reached, going for cross product\n";
		push (@{$self->{ONS}{$alias}}, 1);
	    }
	}
	my $onStr = join (' AND ', @{$self->{ONS}{$alias}});
	my $joinType = $outer ? "LEFT OUTER" : "INNER";
	push (@froms, "\n     $joinType JOIN $table AS $alias ON $onStr");
    }
    push (@$segments, @froms);

    if ($bindingConstraints) {
	$wheres = $wheres ? 
	    new W3C::Rdf::SqlDB::Conjunction($wheres, $bindingConstraints) : 
	    $bindingConstraints;
    }

    if ($wheres) {
	my $whereStr = $wheres->toString($PRECEDENCE_TABLE, 0);
	push (@$segments, "\nWHERE ");
	push (@$segments, $whereStr);
    }

    if ($groupByStr) {
	push (@$segments, "\nGROUP BY $groupByStr");
    }

    if (@{$self->{BINDER}{ORDER}}) {
	push (@$segments, sprintf("\nORDER BY %s", join(', ', @{$self->{BINDER}{ORDER}})));
    }
#    if ($flags->{-uniqueResults}) {
#	push (@$segments, ' GROUP BY ');
#	push (@$segments, CORE::join (',', @{$self->{LABELS}}));
#    } elsif (my $groupBy = $flags->{-groupBy}) {
#	if (@$groupBy) {
#	    push (@$segments, ' GROUP BY ');
#	    push (@$segments, CORE::join (',', @$groupBy));
#	}
#    }
    return CORE::join('', @$segments);
}

sub _buildResults {
    my ($self, $rows, $implQuerySets, $row) = @_;
    my $uniqueStatementsCheat = {};
    foreach my $answerRow (@$rows) {
	foreach my $binding (@{$self->{BINDER}->getBindings()}) {
	    $binding->preAssimilate($answerRow, $self);
	}
    }
    foreach my $answerRow (@$rows) {

	my $col = 0;
	my $newRow = $row->duplicate;

	# Grab the selected variables ...
#     (a::uris.uri ?uri0 http://www.w3.org/Member/Overview.html)
#     (a::uris.acl ?uri0 ?t1)
#     (a::acls.acl ?acl0 ?t1)
#     (a::ids.value ?id0 "eric")
#     (a::idInclusions.id ?idInc0 ?id0)
#     (a::acls.id ?acl0 ?t0)
#     (a::idInclusions.groupId ?idInc0 ?t0)
#+----------+---------+-------------+---------+--------+-----+-----------+----------------+----+---+
#| acl0_acl | acl0_id | acl0_access | uri0_id | id0_id | t0  | idInc0_id | idInc0_groupId | t1 | 1 |
#+----------+---------+-------------+---------+--------+-----+-----------+----------------+----+---+
#|        6 |     100 |        3122 |     810 |   2112 | 100 |      2112 |            100 |  6 | 1 |
#|        6 |     102 |        3955 |     810 |   2112 | 102 |      2112 |            102 |  6 | 1 |
#+----------+---------+-------------+---------+--------+-----+-----------+----------------+----+---+
# =>
#   row 0:
#     (a::uris.uri ...uris?id=810 http://www.w3.org/Member/Overview.html)
#     (a::uris.acl ...uris?id=810 6)
#     (a::acls.acl ...acls?acl=6&id=100&access=3122 6)
#     (a::ids.value ...ids?id=2112 "eric")
#     (a::idInclusions.id ...idInclusions?id=2112&groupId=100 ...ids?id=2112)
#     (a::acls.id ...acls?acl=6&id=100&access=3122 100)
#     (a::idInclusions.groupId ...idInclusions?id=2112&groupId=100 100)
#   row 1:
#     (a::uris.uri ...uris?id=810 http://www.w3.org/Member/Overview.html)
#     (a::uris.acl ...uris?id=810 6)
#     (a::acls.acl ...acls?acl=6&id=102&access=3955 6)
#     (a::ids.value ...ids?id=2112 "eric")
#     (a::idInclusions.id ...idInclusions?id=2112&groupId=102 ...ids?id=2112)
#     (a::acls.id ...acls?acl=6&id=102&access=3955 100)
#     (a::idInclusions.groupId ...idInclusions?id=2112&groupId=102 100)

	# fill in resultSet
	my $rowBindings = {};
	my $iSelect = 0;
	eval {
	    # Grab objects from the results
	    foreach my $binding (@{$self->{BINDER}->getBindings()}) {
		$binding->assimilate($answerRow, $newRow, $rowBindings, $self);
	    };

	    # ... and the supporting statements.
	    my @proofs = $self->_bindingsToStatements($implQuerySets, $rowBindings, $uniqueStatementsCheat, 0, 0);
	    $newRow->addProofs(\@proofs);
	    #push (@{$nextStatements->[-1]}, $self->_bindingsToStatements($implQuerySets, $rowBindings, $uniqueStatementsCheat));
	    foreach my $s (@proofs) {
		$self->applyClosureRules({}, $s, $self->{-sourceAttribution});
	    }
	}; if ($@) {
	    if ((my $ex = &catch('W3C::Util::Exception')) && 
		$self->{-errorHandler}) {
		$self->{-errorHandler}->error($ex);
		$row->unduplicate($newRow);
	    } else {
		&throw();
	    }
	}
    }
}

sub deleteAttributionNUKE {
    my ($self, $attribution) = @_;
    my $uriStr = $attribution->getSource->getUri;
    my $ret = $self->executeSingleQuery("
SELECT __Attributions__.id FROM __Attributions__ 
       INNER JOIN __Nodes__ ON __Attributions__.doc=__Nodes__.id
 WHERE __Nodes__.type=\"uri\" 
   AND __Nodes__.str=\"$uriStr\"");
    $self->emptyAttribution($ret);
}

sub emptyAttribution {
    my ($self, $attrId) = @_;
    my $containingLists = [];
    my $libCode = $self->executeArrayQuery($containingLists, 
					   "SELECT listId, COUNT(*) FROM __AttrLists__ WHERE a=$attrId GROUP BY listId");

    foreach my $doomed (@$containingLists) {
	if ($doomed->[1] == 1) {
	    # Remove attribution lists that contain ONLY the doomed attribution.
	    $libCode = $self->executeUpdate("DELETE FROM __Holds__ WHERE a=$doomed->[0]");
	    $libCode = $self->executeUpdate("DELETE FROM __AttrLists__ WHERE listId=$doomed->[0]");
	    $libCode = $self->executeUpdate("DELETE FROM __Nodes__ WHERE type=\"bnode\" AND attribOrDT=$attrId");
	} else { warn "doomed: $doomed->[1] != 1\n";
	    # Ensure an attribution list, identical, but without the $attrId in it.
	    &throw(new W3C::Util::NotImplementedException());# !!! my $aInt = $self->_ensureAttributionList($attribIds, $algae);...
	}
    }
}

my $CHEAT_CACHE_Attrib = {};
sub _cacheAttributionList { # @@@ should be in the __Holds__ predicate.
    my ($self, $term, $listId) = @_;
    if ($listId) {
	if (!exists $CHEAT_CACHE_Attrib->{$listId}) {
	    $self->_queueResolveAttrListId($listId);
	    $CHEAT_CACHE_Attrib->{$listId} = [$self->_resolveAttrListId($listId)->getAllDirect()];
	}
	$self->{TERM2ATTRIBUTION}{$term} = $CHEAT_CACHE_Attrib->{$listId};
    } else {
	$self->{TERM2ATTRIBUTION}{$term} = "$self->{TERM2ATTRIBUTION}{$term} = NULL";
    }
}
sub getAttributionId {
    my ($self, $attribution) = @_;
    return $W3C::Rdf::SqlDB::HoldsProperty::CACHE_attributionToDbId->{$attribution};
}

sub _loadAttributions { # @@@ should be in the __Holds__ predicate.
    my ($self, $listIds) = @_;
    my $valueStr = join (', ', @$listIds);
    my @a;
    $self->{DB}->executeArrayQuery(\@a, "
SELECT SoughtAttrib.id, SoughtAttrib.type, SoughtAttrib.modified, SoughtAttrib.created, 

       Doc.id,Doc.type,Doc.str,Doc.big,
       DocAttrib.type,DocAttrib.auth,DocAttrib.modified,DocAttrib.created,
       DocDT.id,DocDT.str,
       DocDoc.str, 

       Auth.id,Auth.type,Auth.str,Auth.big,
       AuthAttrib.type,AuthAttrib.auth,AuthAttrib.modified,AuthAttrib.created,
       AuthDT.id,AuthDT.str,
       AuthAuth.str
  FROM __Attributions__ AS SoughtAttrib  

       INNER JOIN __Nodes__ AS Doc ON SoughtAttrib.doc=Doc.id 
       LEFT OUTER JOIN __Attributions__ AS DocAttrib ON Doc.attribOrDt=DocAttrib.id
       LEFT OUTER JOIN __Nodes__ AS DocDT ON Doc.attribOrDt=DocDT.id
       LEFT OUTER JOIN __Nodes__ AS DocDoc ON DocAttrib.doc=DocDoc.id

       LEFT OUTER JOIN __Nodes__ AS Auth ON SoughtAttrib.auth=Auth.id 
       LEFT OUTER JOIN __Attributions__ AS AuthAttrib ON Auth.attribOrDt=AuthAttrib.id
       LEFT OUTER JOIN __Nodes__ AS AuthDT ON Auth.attribOrDt=AuthDT.id
       LEFT OUTER JOIN __Nodes__ AS AuthAuth ON AuthAttrib.doc=AuthAuth.id

 WHERE SoughtAttrib.id IN ($valueStr)");
    foreach my $row (@a) {
	my ($id, $type, $modified, $created) = @$row[0..3];
	my $doc = $self->internNode(@$row[4..14]);
	my $auth = $row->[15] ? $self->internNode(@$row[15..25]) : undef;
	my $attribution = $self->{-atomDictionary}->getGroundFactAttribution($doc, undef, $auth, undef);
	$W3C::Rdf::SqlDB::HoldsProperty::CACHE_dbIdToAttribution->{$id} = $attribution;
	$W3C::Rdf::SqlDB::HoldsProperty::CACHE_attributionToDbId->{$attribution} = $id;
    }
}

sub _cacheStatementIdList { # @@@ should be in the __Holds__ predicate.
    my ($self, $term, $listId) = @_;
    if ($listId) {
	$self->{TERM2STATEMENTID}{$term} = $listId;
    } else {
	$self->{TERM2STATEMENTID}{$term} = "$self->{TERM2STATEMENTID}{$term} = NULL";
    }
}
sub getStatementId {
    my ($self, $statement) = @_;
    return $self->{STATEMENT2ID}{$statement};
}
sub getStatementsById {
    my ($self, $field, $values) = @_;
    my $valueStr = join (', ', @$values);
    if ($field eq 'a') {
	my $closure = "SELECT listId FROM __AttrLists__ WHERE a IN ($valueStr)";
	my @t;
	$self->{DB}->executeArrayQuery(\@t, $closure);
	my @attrLists;
	foreach my $row (@t) {
	    push (@attrLists, $row->[0]);
	}
	$valueStr = join (', ', @attrLists);
    }
    my $query = "SELECT id, p, s, o, a FROM __Holds__ WHERE $field IN ($valueStr)";
    my @a;
    $self->{DB}->executeArrayQuery(\@a, $query);
    foreach my $row (@a) {
	my ($id, $p, $s, $o, $a) = @$row;
	$self->queueResolveNodeId($p);
	$self->queueResolveNodeId($s);
	$self->queueResolveNodeId($o);
	$self->_queueResolveAttrListId($a);
    }
    my @ret;
#    my $uniqueStatementsCheat = {};
    foreach my $row (@a) {
	my ($id, $p, $s, $o, $a) = @$row;
	my $pred = $self->resolveNodeId($p);
	my $subj = $self->resolveNodeId($s);
	my $obj = $self->resolveNodeId($o);
	my $list = $self->_resolveAttrListId($a);
	my $statement = $self->{-atomDictionary}->getStatement($pred, $subj, $obj, undef, $list); # @@@ no reifeidAs right now
	$self->{STATEMENT2ID}{$statement} = $id;
	push (@ret, $statement);
    }
    return @ret;
}

sub _bindingsToStatements {
    my ($self, $term, $rowBindings, $uniqueStatementsCheat, $disjunction, $negation) = @_;
    if ($term->isa('W3C::Rdf::AlgaeCompileTree::Negation')) {
	# Need to propogate downward because we might have a double negative.
	return $self->_bindingsToStatements($term->getDecl(), $rowBindings, $uniqueStatementsCheat, $disjunction, !$negation);
    } elsif ($term->isa('W3C::Rdf::AlgaeCompileTree::ShortcutDisjunction')) {
	return ($self->_bindingsToStatements($term->getLeft(), $rowBindings, $uniqueStatementsCheat, 1, $negation), 
		$self->_bindingsToStatements($term->getRight(), $rowBindings, $uniqueStatementsCheat, 1, $negation));
    } elsif ($term->isa('W3C::Rdf::AlgaeCompileTree::Option')) {
	return $self->_bindingsToStatements($term->getDecl(), $rowBindings, $uniqueStatementsCheat, $disjunction, $negation);
    } elsif ($term->isa('W3C::Rdf::AlgaeCompileTree::Conjunction')) {
	return ($self->_bindingsToStatements($term->getLeft(), $rowBindings, $uniqueStatementsCheat, $disjunction, $negation), 
		$self->_bindingsToStatements($term->getRight(), $rowBindings, $uniqueStatementsCheat, $disjunction, $negation));
    } elsif ($term->isa('W3C::Rdf::AlgaeCompileTree::Ask')) {
	return $self->_bindingsToStatements($term->{DECLS}, $rowBindings, $uniqueStatementsCheat, $disjunction, $negation);
    } elsif ($term->isa('W3C::Rdf::AlgaeCompileTree::Constraint')) {
	return ();
    }
    if ($negation) {
	return ();
    }
    if ($disjunction && exists $self->{DISJUNCTION_BOUND}{$term} && !$rowBindings->{$term}) {
	return ();
    }
    my ($p, $s, $o) = ($term->getSlot(0), $term->getSlot(1), $term->getSlot(2));

    my $pred = $p->isa('W3C::Rdf::AlgaeCompileTree::StaticPOS') ? $p->lookfor : $rowBindings->{$p->symbol};
    my $subj = $s->isa('W3C::Rdf::AlgaeCompileTree::StaticPOS') ? $s->lookfor : $rowBindings->{$s->symbol};
    my $obj = 
	#$o->isa('W3C::Rdf::AlgaeCompileTree::Members') ? # will need something special for proofs of n'th element in list
	#$rowBindings->{$o->{VAR}->symbol} : 
	$o->isa('W3C::Rdf::AlgaeCompileTree::StaticPOS') ? $o->lookfor : $rowBindings->{$o->symbol};
    if ($pred != $Value_NULL && $subj != $Value_NULL && $obj != $Value_NULL) {
	my $statement = $uniqueStatementsCheat->{$pred}{$subj}{$obj};
	if (!$statement) {
	    $statement = $self->{-atomDictionary}->getStatement($pred, $subj, $obj, 
		undef, # @@@ no reifeidAs right now
		$self->{-assertionAttribution}); # stopgap until we add attrlists to each join on holds. !!! missing functionality
	    $self->{STATEMENT2ID}{$statement} = $self->{TERM2STATEMENTID}{$term};
	    foreach my $attribution (@{$self->{TERM2ATTRIBUTION}{$term}}) {
		$statement->getAttributionList->ensureDirectAttribution($attribution);
	    }
	    $uniqueStatementsCheat->{$pred}{$subj}{$obj} = $statement;
	}
	return $statement;
    }
    return ();
}

###############################################################################
# Selects
#####

sub _selectKey {
    my ($self, $table, $alias, $qp, $binder, $prefix) = @_;
    $prefix = "${alias}_" if (defined $prefix);
    my $pk = [$self->_uniquesFor($table)];
    if (!$pk) {
	&throw(new W3C::Util::Exception(-message => "no primary key for table $table"));
    }
    my $cols = [];
    my $fieldz = [];
    for (my $iField = 0; $iField < @$pk; $iField++) {
	my $field = $pk->[$iField];
	my $punct = $iField == @$pk-1 ? "\n       " : ' ';
	my $symbol = $qp->symbol;
	$symbol =~ s/_:_/_genid/;
	my $col = $self->_addSelect("$alias.$field", $prefix.$symbol."_$field", $qp->existential, $punct);
	push (@$cols, $col);
	push (@$fieldz, $field);
    }
    if ($table eq '__Holds__') {
    } elsif ($table eq '__Nodes__') {
	$binder->addBinding(new W3C::Rdf::SqlDB::NodeBinding($qp, $cols, $fieldz, $table));
    } else {
	$binder->addBinding(new W3C::Rdf::SqlDB::ObjectBinding($qp, $cols, $fieldz, $table));
    }
}

sub _selectVariable {
    my ($self, $constraintAlias, $constraintField, $datatype, $qp, $binder) = @_;
    my $col = $self->_addSelect("$constraintAlias.$constraintField", $qp->symbol."_$constraintField", $qp->existential, "\n");
    $binder->addBinding(new W3C::Rdf::SqlDB::ScalarBinding($qp, [$col], [$constraintField], $constraintAlias, $datatype));
}

sub _selectDisjunction {
    my ($self, $term, $binder, $sql) = @_;
    # Could use $term->toString as the select label but maybe that's not guaranteed unique.
    my $col = $self->_addSelect($sql->toString($PRECEDENCE_TABLE, 0), '"'.$term->toString.'"', 1, "\n       ");
    $binder->addBinding(new W3C::Rdf::SqlDB::DisjunctionBinding($term, [$col], undef, undef));
    $self->{DISJUNCTION_BOUND}{$term} = 1;
}

sub _selectAttribution {
    my ($self, $alias, $term, $binder) = @_;
    my $col = $self->_addSelect("$alias.a", "${alias}_a", 1, "\n       ");
    $binder->addBinding(new W3C::Rdf::SqlDB::AttributionBinding($term, [$col], ['a'], $alias));
    $self->{TERM2ATTRIBUTION}{$term} = $alias;	# @@@ note for debugging. should be reassigned.
}

sub _selectStatementId {
    my ($self, $alias, $term, $binder) = @_;
    my $col = $self->_addSelect("$alias.id", "${alias}_id", 1, "\n       ");
    $binder->addBinding(new W3C::Rdf::SqlDB::StatementIdBinding($term, [$col], ['id'], $alias));
    $self->{TERM2STATEMENTID}{$term} = $alias;	# @@@ note for debugging. should be reassigned.
}

sub _addSelect {
    my ($self, $name, $label, $existential, $punct) = @_;
    my $ret = $self->{SELECTED_ALIASES}{$name};
    if (!defined $ret || $self->{-duplicateFieldsInQuery}) {
	# name:		SELECT foo
	# label:	           AS bar
	# existential:	GROUP BY foo
	# punch:	pretty printing
	push (@{$self->{SELECTS}}, [$name, $label, $punct, $existential]);
	$self->{SELECTED_ALIASES}{$name} = $ret = @{$self->{SELECTS}}-1;
    }
    return $ret;
}

sub _compileSelects {
    my ($self) = @_;
    my (@groupBy, @sel);
    for (my $i = 0; $i < @{$self->{SELECTS}}; $i++) {
	if ($self->{SELECTS}[$i]) {
	    my ($name, $label, $punct, $existential) = @{$self->{SELECTS}[$i]};
	    # Note, the " AS $self->{LABELS}[$i]" is just gravy -- nice in logs.
	    my $comma = $i == @{$self->{SELECTS}} - 1 ? '' : ',';
	    my $asStr = defined $label ? " AS $label" : '';
	    my $punctStr = $i == @{$self->{SELECTS}} ? '' : $punct;
	    push (@sel, "$name$asStr$comma$punctStr");
	    if (!$existential) {
		push (@groupBy, defined $label ? $label : $name);
	    }
	} else {
	    $self->{-errorHandler}->warning(new W3C::Util::ParameterException(-parameter => '?'.$self->{LABELS}[$i]));
	    # remove ith element
	    splice (@{$self->{SELECTS}}, $i, 1);
	    $i--;
	}
    }
    return (join ('', @sel), join (',', @groupBy))
}

#####
# end Selects
###############################################################################

###############################################################################
# Constraints
#####

sub _addWhereField {
    my ($self, $alias1, $field1, $op, $alias2, $field2, $term, $outer) = @_;
    my $opaque = "$op$alias2.$field2";
    return $self->_addWhereOpaque($alias1, $field1, $opaque, 
				  $term, $outer, [$alias2]);
}

sub _addWhereTable {
    my ($self, $atomTable, $nodeAlias, $atomAliasIds, $term, $outer) = @_;
    my @fields;
    foreach my $field (@{$self->{TABLES}{$atomTable}{PRIMARY_KEY}{SEQUENCE}}) {
	my $name = $field->getName;
	push (@fields, "$name=\\\"\",$atomAliasIds.$name,\"\\\"");
    }
    my $opaque = '=concat("'.join (',', $atomTable, @fields).'")';
    return $self->_addWhereOpaque($nodeAlias, 'str', $opaque, 
				  $term, $outer, [$atomAliasIds]);
}

sub _addWhereConst {
    my ($self, $alias1, $field1, $op, $constant, $term, $outer) = @_;
    my $opaque = "$op\"$constant\"";
    return $self->_addWhereOpaque($alias1, $field1, $opaque, 
				  $term, $outer, []);
}

sub _addWhereOpaque {
    my ($self, $alias1, $field1, $opaque, $term, $outer, $reaches) = @_;
    my $condition = "$alias1.$field1$opaque";
    foreach my $reach (@$reaches) {	# !!! may be in disjunction -- need to return in a tree
	$self->_addReaches($alias1, $reach, $term);
    }
    return new W3C::Rdf::SqlDB::AttributeRestriction($condition, [$alias1, @$reaches], $outer);
}

sub _addWhereDisjunction {
    my ($self, $l, $r, $outer) = @_;
    return new W3C::Rdf::SqlDB::AttributeDisjunction($l, $r, $outer);
}

#####
# end Constraints
###############################################################################

###############################################################################
# Constraint Reaches - set of checks to see what tables are constrained against
# each other.
#####

sub _addReaches {
    my ($self, $from, $to, $term) = @_;
    # Entries are a list of paths (lists) that connect $from to $to and visa
    # versa. The first path is the first way the tables were constrained.
    # Additional paths represent over-constraints.
    $self->_fromReachesToAndEverythingToReaches($from, $to, [$term]);
    foreach my $fromFrom (keys %{$self->{CONSTRAINT_REACHES}{$from}}) {
	if ($fromFrom ne $to) {
	    $self->_fromReachesToAndEverythingToReaches($fromFrom, $to, [@{$self->{CONSTRAINT_REACHES}{$from}{$fromFrom}}, $term]);
	}
    }
}

sub _fromReachesToAndEverythingToReaches {
    my ($self, $from, $to, $path) = @_;
    if (exists $self->{CONSTRAINT_REACHES}{$from}{$to}) {
	push (@{$self->{OVER_CONSTRAINTS}{$from}{$to}}, $path);
    } else {
#	print "  ${c}-${g}->${p}\n";
	foreach my $toTo (keys %{$self->{CONSTRAINT_REACHES}{$to}}) {
	    my $toPath = [@{$self->{CONSTRAINT_REACHES}{$to}{$toTo}}, @$path];
	    if (exists $self->{CONSTRAINT_REACHES}{$from}{$toTo}) {
		push (@{$self->{OVER_CONSTRAINTS}{$from}{$toTo}}, $path);
	    } else {
		$self->{CONSTRAINT_REACHES}{$from}{$toTo} = $toPath;
		$self->{CONSTRAINT_REACHES}{$toTo}{$from} = $toPath;
#		print "  ${c}-${gP}->${parent}\n";
#	    } else {
#		print "xx${c}-${gP}->${parent}\n";
	    }
	}
	$self->{CONSTRAINT_REACHES}{$from}{$to} = $path;
	$self->{CONSTRAINT_REACHES}{$to}{$from} = $path;
#    } else {
#	print "xx${c}-${g}->${p}\n";
    }
}

sub _showConstraintsNUKE {
    my ($self) = @_;
    my @ret;
    foreach my $from (keys %{$self->{CONSTRAINT_REACHES}}) {
	foreach my $to (keys %{$self->{CONSTRAINT_REACHES}{$from}}) {
	    push (@ret, $self->_showConstraint($from, $to));
	}
    }
    return join ("\n", @ret);
}

sub _showConstraintNUKE {
    my ($self, $from, $to) = @_;
    my $pathStr = join (' - ', map {$_->toString({-brief => 1})} @{$self->{CONSTRAINT_REACHES}{$from}{$to}});
    return "$from:$to: $pathStr";
}

sub _mergeCommonConstraintsNUKE {
    my ($self, $reachesSoFar, $term, $subTerm) = @_;
    foreach my $fromTable (keys %{$self->{CONSTRAINT_REACHES}}) {
	if (!$reachesSoFar->{$fromTable}) {
	    if (!$self->{CONSTRAINT_HINTS}{$fromTable}) {
		$self->{CONSTRAINT_HINTS}{$fromTable} = {};
	    }
#			    push (@{$self->{CONSTRAINT_HINTS}{$fromTable}}, "for $fromTable");
	}
	foreach my $toTable (keys %{$self->{CONSTRAINT_REACHES}{$fromTable}}) {
	    if (!exists $reachesSoFar->{$fromTable}{$toTable}) {
		push (@{$self->{CONSTRAINT_HINTS}{$fromTable}{$toTable}}, [$term, $subTerm]);
		push (@{$self->{CONSTRAINT_HINTS}{$toTable}{$fromTable}}, [$term, $subTerm]);
	    }
	}
    }
    foreach my $fromTable (keys %$reachesSoFar) {
	if (!$self->{CONSTRAINT_REACHES}{$fromTable}) {
	    if (!$self->{CONSTRAINT_HINTS}{$fromTable}) {
		$self->{CONSTRAINT_HINTS}{$fromTable} = {};
	    }
#			    push (@{$self->{CONSTRAINT_HINTS}{$fromTable}}, "for $fromTable");
	}
	foreach my $toTable (keys %{$reachesSoFar->{$fromTable}}) {
	    if (!exists $self->{CONSTRAINT_REACHES}{$fromTable}{$toTable}) {
		delete $reachesSoFar->{$fromTable}{$toTable};
		delete $reachesSoFar->{$toTable}{$fromTable};
		push (@{$self->{CONSTRAINT_HINTS}{$fromTable}{$toTable}}, [$term, $subTerm]);
		push (@{$self->{CONSTRAINT_HINTS}{$toTable}{$fromTable}}, [$term, $subTerm]);
	    }
	}
    }
}

sub _checkForUnderConstraint {
    my ($self) = @_;
    my @allAliases = $self->{BINDER}->getAliases;
    my $firstAlias = $allAliases[0][1];
    my @messages;
    for (my $iAliasSet = 1; $iAliasSet < @allAliases; $iAliasSet++) {
	my ($table, $alias) = @{$allAliases[$iAliasSet]};
	if (!exists $self->{CONSTRAINT_REACHES}{$firstAlias}{$alias}) {
	    push (@messages, "  $firstAlias not constrained against $alias");
	    foreach my $reaches (keys %{$self->{CONSTRAINT_REACHES}{$firstAlias}}) {
		push (@messages, "    $firstAlias reaches $reaches");
	    }
	    foreach my $reaches (keys %{$self->{CONSTRAINT_REACHES}{$alias}}) {
		push (@messages, "    $alias reaches $reaches");
	    }
	    foreach my $terms (@{$self->{CONSTRAINT_HINTS}{$firstAlias}{$alias}}) {
		my $constrainedByStr = $terms->[1]->toString({-brief => 1});
		my $constrainedInStr = $terms->[0]->toString({-brief => 1});
		push (@messages, "    partially constrained by '$constrainedByStr' in '$constrainedInStr'");
	    }
	}
    }
    if (@messages) {
	&throw(new W3C::Util::Exception(-message => "underconstraints exception:\n".join ("\n", @messages)));
    }
}

sub _checkForOverConstraint {
    my ($self) = @_;
    my @messages;
    my %done;
    foreach my $from (sort keys %{$self->{OVER_CONSTRAINTS}}) {
	next if ($done{$from});
	$done{$from} = 1;
	foreach my $to (sort keys %{$self->{OVER_CONSTRAINTS}{$from}}) {
	    next if ($done{$to});
	    if ($to ne $from) {
		push (@messages, "  $from over-constrained against $to".&_showPath($self->{CONSTRAINT_REACHES}{$from}{$to}));
		foreach my $path (@{$self->{OVER_CONSTRAINTS}{$from}{$to}}) {
		    push (@messages, '    '.&_showPath($path));
		}
	    }
	}
    }
    if (@messages) {
	&throw(new W3C::Util::Exception(-message => "overconstraints exception:\n".join ("\n", @messages)));
    }
}

sub _showPath { # static
    my ($path) = @_;
    my @pathStrs;
    foreach my $term (@$path) {
	push (@pathStrs, $term->toString({-brief => 1}));
    }
    return join (' - ', @pathStrs);
}

#####
# end Constraint Reaches
###############################################################################

################################################################################
################################################################################
################################################################################
################################################################################
################################################################################
################################################################################

sub toString {
    my ($self) = @_;
    my @ret;

    push (@ret, "SELECT:");
    
    push (@ret, "WHERE:");

    
    push (@ret, "=>");
    return join ("\n", @ret);
}

# custom exceptions

sub main::showWheres {
    my ($wheres) = @_;
    my @ret;
    foreach my $where (@$wheres) {
	my ($condition, $aliases, $outer) = @$where;
	push (@ret, ($outer ? '  ~' : '  ').$condition.' ['.join(',',@$aliases).']');
    }
    return wantarray ? @ret : join ("\n", @ret);
}

sub serializeString {
    my ($self, $category, $exprs, $precTable, $parentPrec) = @_;
    return $exprs->toString($precTable, $parentPrec);
}
sub serializeDot {
    my ($self, $category, $exprs, $precTable, $parentPrec) = @_;
    my $dot = $category eq 'Compiled' ? $exprs->toDot : $exprs->toGraph;
    return "digraph dotfile{ 
node [fontname=arial,fontsize=10,color=Black,fontcolor=Blue];
edge [fontname=arial,fontsize=10,color=Darkgreen,fontcolor=Red];
rankdir=TB;

$dot
}

";
}

package W3C::Rdf::SqlDB::NoByPredicateException;
use W3C::Util::Exception;

sub new {
    my ($proto, @parms) = @_;
    my $class = ref($proto) || $proto;
    my $self = $class->SUPER::new(@parms);
    $self->missingParm('-predicate') if (!$self->{-predicate});
    $self->fillInStackTrace;
    return $self;
}
sub getSpecificMessage {return 'No record for predicate "'.$_[0]->{-predicate}.'"';}
sub getPredicate {return $_[0]->{-predicate};}

# custom algae interface to overload (optimize) processQuerySets

1;

__END__

=head1 NAME

W3C::Rdf::SqlDB - RdfDB interface to SQL tables

=head1 SYNOPSIS

  use W3C::Rdf::Atoms;
  use W3C::Rdf::SqlDB;
  ues W3C::Util::NamespaceHandler;
  use W3C::Rdf::Algae2;

  my $atoms = new W3C::Rdf::Atoms();
  my $db = new W3C::Rdf::SqlDB(-atomDictionary => $atoms, 
			       -properties => 'db.prop');
  my $nsh = new W3C::Util::NamespaceHandler();
  my $url = $atoms->getUri(new_abs URI($0, 'file://localhost/some/path'));
  $attrib = $atoms->getGroundFactAttribution($url, undef, undef, undef);
  my $queryHandler = new W3C::Rdf::Algae2($atoms
					  $nsh, 
					  {'' => $self}, $self, 
					  $attrib, 
					  {-uniqueResults => 1}, 
					  -rdfDB => $db);
  my ($nodes, $selects, $messages, $proofs) = 
      $queryHandler->interpret('ask (...)', $self->{-location}, $QL_ALGAE);

=head1 DESCRIPTION

C<SqlDB> implements the C<RdfDB> interface and provides persistent storage for
RDF triples. It is tailored to address SQL databases with application-specific
schemas. Included is an example OrderTracking database which has conventional
tables for storing Orders, Products, Customers, and Addresses. In addition, it
has a generic triple store which C<SqlDB> uses to store or query data that does
not fit in the OrderTracking schema.

This module is part of the W3C::Rdf CPAN module.

=head1 CONSTRUCTOR ( ATOMS, PROPERTIES [, FLAGS ]* )

The C<W3C::Rdf::SqlDB> constructor requires a C<W3C::Rdf::AtomDictionary> and
the name of a file containing properties describing how to access the SQL
database. This properties file identifies a data structure that describes the
application-specific schemas of the database. C<SqlDB> uses this to transform
Algae queries into an SQL query.

=head2 FLAGS

  -duplicateFieldsInQuery -- A field for a given table may be referenced more than once in the SELECT. SqlDBAlgae keeps a list of which response columns hold values for which variables. The same field may be referenced more than once if it is the object of a requested property and a component in a row identifier (primary key). If this flag is true, it tells SqlDBAlgae to repeat the SELECT clause for each reference to a field so an observer can see where each value comes from the SQL response.

=head1 AUTHOR

Eric Prud'hommeaux <eric@w3.org>

=head1 SEE ALSO

L<W3C::Rdf::RdfDB>
L<W3C::Rdf::Algae2>

=head1 COPYRIGHT

Copyright Massachusetts Institute of technology, 1998.

THIS SOFTWARE AND DOCUMENTATION IS PROVIDED "AS IS," AND COPYRIGHT HOLDERS MAKE NO REPRESENTATIONS
OR WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO, WARRANTIES OF MERCHANTABILITY OR
FITNESS FOR ANY PARTICULAR PURPOSE OR THAT THE USE OF THE SOFTWARE OR DOCUMENTATION WILL NOT INFRINGE
ANY THIRD PARTY PATENTS, COPYRIGHTS, TRADEMARKS OR OTHER RIGHTS. 

COPYRIGHT HOLDERS WILL NOT BE LIABLE FOR ANY DIRECT, INDIRECT, SPECIAL OR CONSEQUENTIAL DAMAGES ARISING
OUT OF ANY USE OF THE SOFTWARE OR DOCUMENTATION. 

The name and trademarks of copyright holders may NOT be used in advertising or publicity pertaining 
to the software without specific, written prior permission. Title to copyright in this software and 
any associated documentation will at all times remain with copyright holders. 

=cut

