Dependency Graph

The nodes of a dependency graph represent rules and the directed links indicate the direction of dependency.  In an acyclic dependency graph, a rule engine can fire all rules for which either are not dependent on any other rules or which are dependent only on rules that have already been fired.  All other rules can be ignored.  After each set of currently independent rules have been fired, then other rules dependent on them may become eligible to be fired.  The depency graph avoids having to establish a conflict set after each rule fires and enables the rule engine to ignore all rules dependent directly or indifrectly on any rule that does not fire.  The use of dependency graphs is efficient in conditions where facts are frequently being asserted to or retracted from fact bases.