net.sourceforge.nite.search.rewriter
Class ConditionDistributorTemplate

java.lang.Object
  net.sourceforge.nite.search.rewriter.ConditionDistributorTemplate

All Implemented Interfaces:

ParserTreeConstants, ConditionDistributor, RewriterConstants

Direct Known Subclasses:

DefaultConditionDistributor

public abstract class ConditionDistributorTemplate
extends java.lang.Object
implements ConditionDistributor, ParserTreeConstants, RewriterConstants

This class provides a template algorithm for the condition distribution process, implementing the features that should be common to any rewriting, while leaving as abstract the core distribution algorithm, which provides a solution to the constraint-satisfaction problem of distributing the remaining conditions.

We know that some variables and conditions must occur together, and for efficiency should occur in particular positions in the ordered subqueries. Concrete implementations of this class should implement distributeRemainingConditions() in order to provide a pluggable algorithm for distributing the remaining conditions and variable declarations according to their own heuristics or algorithms.

This template implementation of the ConditionDistributor works by incrementally creating declarations for different classes of variable/condition. It creates minimal-variable SimpleQueries using the following heuristics (note that the rules are applied only to those variables and conditions which have not already been assigned to a subquery):

• Lone variables: Create a subquery for each variable which appears exclusively in unary conditions (conditions involving only that variable). These queries should be evaluated last, as the variables declared within them are not required anywhere else and therefore merely increase the size of the resulting match set, which is the cross product of the new variable binding and the elements previous match set.
• One-variable conditions: Create a subquery for each variable which is involved in unary conditions. These conditions will tend to restrict the number of matches returned for a variable declaration, by specifying a property which must hold for all of those variables. Therefore queries involving these conditions can be evaluated early to restrict the size of variable bindings which are later combined with other bindings. This also means that other conditions, involving the same variable in binary relationships, have a wider choice of subqueries across which they can be distributed. They can be placed as early or as late in the ordering as is required, subject to the declaration of the other variables involved.
• Single-occurrence variables: Create a subquery for each undeclared variable which appears in only one undistributed condition. This condition must appear with the declaration of the variable. This heuristic is applied repeatedly (using the remaining undeclared variables and undistributed conditions) until it no longer applies.

We are then left with the problem of declaring the remaining variables, distributing the remaining conditions and ordering the resultant simple queries. This final stage is controlled by distributeRemainingConditions() which must be implemented in subclasses.

Author:

nmayo@inf.ed.ac.uk

Field Summary

Fields inherited from interface net.sourceforge.nite.search.ParserTreeConstants

JJTCONDITION, JJTLOGICAL, jjtNodeName, JJTQUERY, JJTSIMPLEQUERY

Fields inherited from interface net.sourceforge.nite.search.rewriter.RewriterConstants

BREAK_LINE, TEST_QUERIES

Constructor Summary

ConditionDistributorTemplate(java.util.List conds, java.util.Hashtable vars)
Initialise the class with a set of MinimalConditions and DeclarableVariables.

Method Summary

void	createSkeletonDeclarations() Create skeleton subqueries for any remaining undeclared variables, without appending conditions.
NodeQuery	distribute(DeclarationOrderingScheme orderingScheme) Distribute the conditions and variable declarations across a new set of SimpleQueries, returning the resultant complex query.
java.util.List	getTypes(java.lang.String varName) Get the types associated with a particular variable.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

ConditionDistributorTemplate

public ConditionDistributorTemplate(java.util.List conds,
                                    java.util.Hashtable vars)

Initialise the class with a set of MinimalConditions and DeclarableVariables.

Parameters:

conds - a List of MinimalCondition objects representing SimpleNodes which should be distributed

vars - a Hashtable mapping each variable name to a DeclarableVariable object

Method Detail

distribute

public final NodeQuery distribute(DeclarationOrderingScheme orderingScheme)

Distribute the conditions and variable declarations across a new set of SimpleQueries, returning the resultant complex query. This is the template method, describing at a high level the steps of the distribution algorithm.

We may wish to add hooks to this algorithm for subclasses to provide actions between stages.

Specified by:

distribute in interface ConditionDistributor

Parameters:

orderingScheme - a DeclarationOrderingScheme to use in ordering subqueries

Returns:

a new query

createSkeletonDeclarations

public void createSkeletonDeclarations()

Create skeleton subqueries for any remaining undeclared variables, without appending conditions.

getTypes

public java.util.List getTypes(java.lang.String varName)

Get the types associated with a particular variable.

Specified by:

getTypes in interface ConditionDistributor

Parameters:

varName - a String naming the variable

Returns:

a List of the types the variable is bound to