net.sf.bddbddb
Class InferenceRule

java.lang.Object
  extended by 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()


Copyright © 2004-2008 Stanford SUIF Compiler Group. All Rights Reserved.