net.sf.bddbddb
Class InferenceRule

java.lang.Object
  net.sf.bddbddb.InferenceRule

All Implemented Interfaces:

IterationElement

Direct Known Subclasses:

BDDInferenceRule, LSInferenceRule, NumberingRule

public abstract class InferenceRule
extends java.lang.Object
implements IterationElement

An InferenceRule represents a single Datalog rule.

Version:

$Id: InferenceRule.java 585 2005-06-10 18:04:11Z joewhaley $

Author:

jwhaley

Nested Class Summary

static class

InferenceRule.DependenceNavigator A navigator that can navigate over rule dependencies.

Field Summary

protected RuleTerm	bottom Head of the rule (i.e.
int	id Unique id number for this rule.
protected java.util.Set	necessaryVariables Set of variables that are necessary.
protected Solver	solver Link to solver.
protected java.util.List	top List of subgoals for the rule (i.e.
protected java.util.Set	unnecessaryVariables Set of variables that are unnecessary.

Constructor Summary

protected	InferenceRule(Solver solver, java.util.List top, RuleTerm bottom) Construct a new inference rule.
protected	InferenceRule(Solver solver, java.util.List top, RuleTerm bottom, int id)

Method Summary

protected java.util.Set	calculateNecessaryVariables() Calculate and return the set of necessary variables for this rule.
Variable	checkUnnecessaryVariables() Checks to see if there are any variables that only appear once.
void	copyOptions(InferenceRule that) Copy the options from another rule into this one.
void	free() Free the memory associated with this rule.
static InferenceRule	fromXMLElement(org.jdom.Element e, Solver s)
java.util.List	generateIR_incremental() Generate and return the IR that implements the incrementalized version of this rule.
java.util.List	generateIR() Generate and return the IR that implements this rule.
Attribute	getAttribute(Variable v) Returns the attribute associated with the given variable.
RuleTerm	getHead() Returns the head term.
java.util.Set	getNecessaryVariables()
static jwutil.collections.MultiMap	getRelationToDefiningRule(java.util.Collection rules) Given a collection of rules, returns a multimap that maps relations to the rules that define that relation.
static jwutil.collections.MultiMap	getRelationToUsingRule(java.util.Collection rules) Given a collection of rules, returns a multimap that maps relations to the rules that use that relation.
java.util.List	getSubgoals() Returns the list of subgoals.
java.util.Set	getUnnecessaryVariables()
Variable	getVariable(java.lang.String name) Returns the variable with the given name, or null if there is none.
java.util.Set	getVariables()
java.util.Map	getVarNameMap()
int	hashCode() The hashCode for rules is deterministic.
int	numberOfVariables()
abstract void	reportStats() Report statistics about this rule.
java.util.Collection	split(int myIndex) Splits a rule into a collection of rules, such that each of the new rules has only two subgoals.
java.lang.String	toString()
org.jdom.Element	toXMLElement()
abstract boolean	update() Update the head relation of this rule based on the subgoal relations.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, notify, notifyAll, wait, wait, wait

Field Detail

solver

protected final Solver solver

Link to solver.

id

public final int id

Unique id number for this rule.

top

protected java.util.List top

List of subgoals for the rule (i.e. the terms on the right hand side). May be empty.

bottom

protected RuleTerm bottom

Head of the rule (i.e. the term on the left hand side).

necessaryVariables

protected java.util.Set necessaryVariables

Set of variables that are necessary. Initialized after calling initialize().

unnecessaryVariables

protected java.util.Set unnecessaryVariables

Set of variables that are unnecessary. Initialized after calling initialize().

Constructor Detail

InferenceRule

protected InferenceRule(Solver solver,
                        java.util.List top,
                        RuleTerm bottom)

Construct a new inference rule.

Parameters:

solver - solver

top - subgoal terms

bottom - head term

InferenceRule

protected InferenceRule(Solver solver,
                        java.util.List top,
                        RuleTerm bottom,
                        int id)

Method Detail

getSubgoals

public java.util.List getSubgoals()

Returns the list of subgoals. Subgoals are the terms to the right of the ":-".

Returns:

list of subgoals

getHead

public RuleTerm getHead()

Returns the head term. That is the term on the left of the ":-".

Returns:

the head term

calculateNecessaryVariables

protected java.util.Set calculateNecessaryVariables()

Calculate and return the set of necessary variables for this rule. Sets the necessaryVariables and unnecessaryVariables fields.

Returns:

set of necessary variables.

checkUnnecessaryVariables

public Variable checkUnnecessaryVariables()

Checks to see if there are any variables that only appear once.

update

public abstract boolean update()

Update the head relation of this rule based on the subgoal relations. Returns true if the head relation changed.

Returns:

true if the head relation changed

reportStats

public abstract void reportStats()

Report statistics about this rule.

free

public void free()

Free the memory associated with this rule. After calling this, the rule can no longer be used.

getRelationToUsingRule

public static jwutil.collections.MultiMap getRelationToUsingRule(java.util.Collection rules)

Given a collection of rules, returns a multimap that maps relations to the rules that use that relation.

Parameters:

rules - collection of rules

Returns:

multimap from relations to rules that use them

getRelationToDefiningRule

public static jwutil.collections.MultiMap getRelationToDefiningRule(java.util.Collection rules)

Given a collection of rules, returns a multimap that maps relations to the rules that define that relation.

Parameters:

rules - collection of rules

Returns:

multimap from relations to rules that define them

split

public java.util.Collection split(int myIndex)

Splits a rule into a collection of rules, such that each of the new rules has only two subgoals. The current rule is simply mutated and not returned in the collection.

Parameters:

myIndex - index number used to name the new rules

Returns:

collection of new inference rules

copyOptions

public void copyOptions(InferenceRule that)

Copy the options from another rule into this one.

Parameters:

that -

generateIR

public java.util.List generateIR()

Generate and return the IR that implements this rule.

Returns:

list of IR instructions

generateIR_incremental

public java.util.List generateIR_incremental()

Generate and return the IR that implements the incrementalized version of this rule.

Returns:

list of IR instructions

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

hashCode

public int hashCode()

The hashCode for rules is deterministic. (We use the unique id number.)

Overrides:

hashCode in class java.lang.Object

See Also:

Object.hashCode()

getVariable

public Variable getVariable(java.lang.String name)

Returns the variable with the given name, or null if there is none.

Parameters:

name - variable name

Returns:

variable

numberOfVariables

public int numberOfVariables()

getNecessaryVariables

public java.util.Set getNecessaryVariables()

getUnnecessaryVariables

public java.util.Set getUnnecessaryVariables()

getVariables

public java.util.Set getVariables()

getVarNameMap

public java.util.Map getVarNameMap()

Returns:

map from names to variables

getAttribute

public Attribute getAttribute(Variable v)

Returns the attribute associated with the given variable.

Parameters:

v - variable

Returns:

attribute

fromXMLElement

public static InferenceRule fromXMLElement(org.jdom.Element e,
                                           Solver s)

toXMLElement

public org.jdom.Element toXMLElement()