A rule specifies that certain sentences can be derived from other sentences, for example, how the net present value of a project can be derived from the project's discounted cash flows. A second rule might specify how the discounted cash flows can be derived from the project's cash flows (and a discount rate assumption), a third set of rules how cash flows are generalizations of various types of payments and receipts etc.

Queries can be answered by interpreting all relevant rules and sentences during the execution (of the query) - on the fly. The inference engine starts with the conclusion (the answer to the query) and works backwards through rules and facts (this is known as backward chaining). It is a very processing-intensive task, practically impossible in big knowledge bases (KBs), and impractical in all but small KBs. It is however a permissible approach.

The Summit-model illustrates some aspects of forward and backward chaining.

FORWARD CHAINING SUPER-STRUCTURE

Rather than interpreting all rules on the fly, the normal approach in Pro/3 is to use the forward chaining super-structure whereby all possible sentences are derived once and for all and stored in the KB. Repeated re-derivations will only take place when needed, that is when rules or sentences which affect (are determinants for) a derived sentence have been changed. 

How does Pro/3 whether or not rules should be interpreted on the fly?

One of the fields in a database record is the record type field (see DB internals). The value of this field is an integer which actually incorporates three sub-codes. One of the sub-fields is record status, which is reflected in the sign of the integer, such that a negative value signifies an inactive record, while a positive value signifies an active record.  This sub-code applies to sentence rule records only. Inactive rules are ignored by the inference engine, with the effect that responses to queries are based only active rules. Consequently, a KB where all queries are to be processed on the fly, have all sentence rule records active, while a KB using the foward chaining super-structure normally has all rule records as inactive. It is assumed then, with respect to inactive rules, that all sentences which can be derived from these rules already are stored in the KB.

It is also possible to combine the two approaches by setting the sentence rule record to the appropriate status (see Sentence Rule-window).

The forward chaining super-structure implies some administrative overheads on Pro/3's part, which needs to keep track of all dependencies between sentences and rules, as well as the status of derivations. To carry out this task, Pro/3 maintains a knowledge dependency graph. This graph is directed and acyclic (which imposes some fundamental limitations on the structure of sentence rules discussed under). The direction of the graph signifies the sequence of derivation (the direction is from condition to conclusion - from determinant to dependent).

Derived sentences stored in the KB are known as such by Pro/3 through the record type field (i.e. derived sentences have type 1, while sentences explicitly entered by the KE have type 2). 

KNOWLEDGE DEPENDENCY GRAPH

Consider the simple implication rule INC-EXP|2 (right). This rule specifies how conditionally projected revenue cash flows can be derived from existing car fleets and conditionally projected car rentals. 

 

The INC-EXP|2-rule is reflected as three dependencies (edges) in the graph:
DETERMINANTS   DEPENDENTS   DERIVATION STATUS
car rental is conditionally projected SENTENCE TYPE INC-EXP|2 SENTENCE RULE 0 or 1
car fleet exists SENTENCE TYPE INC-EXP|2 SENTENCE RULE 0 or 1
INC-EXP|2 SENTENCE RULE revenue cash flow is conditionally projected SENTENCE TYPE 0 or 1
Derivation status signifies whether or not the determinant in the dependency has been changed since last time a sentence derivation took place (0=has changed, 1=has not changed).
The sub-graph which terminated in the revenue cash flow is conditionally projected sentence type node, appears as the drawing to right. The three dependencies discussed over correspond to the thick black arrows.

 

Keeping the graph up-to-date

Pro/3 maintains the derivation status field by tracking all changes to sentence type populations, sentence rules, inexact rules and functions (elements in these sets are referred to as knowledge nodes

Note that this tracking ignores changes to derived sentences, as these principally should be only changed (automatically) through the sentence derivation process. However, it is fully possible to perform such changes. On the other hand, the dependency graph is updated if entire population of derived sentences (all derived sentences of the same type) are deleted. 

Subscribed sentence types

Subscribed sentence type represent a potential problem in this context, since changes in the external SQL tables where they are stored, take place outside Pro/3, i.e. without causing a change in the derivation status in the dependency graph. In the present version of Pro/3, the Sentence Derivation-window has an option to refresh all subscriptions. This will trigger the necessary updates to a graph i.e. in situations where a sentence type has changed. The refresh must be done prior to sentence derivation.

Internal representation of the graph

The graph is represented as a set of sentences in the KB:  

the dependency node with node type N and node name AA determines the dependency node with node type M and node name BB with derivation status S!

The table under shows eight dependency sentences. Note that node types as well as the dependency status are represented by integers.

The dependency graph (and the sentence model graph) are loaded into a Pro/3 RAM data structure upon opening of the KB. Changes in the graphs during processing, are only reflected in this data structure while interacting with Pro/3 (i.e. they are not reflected in the KB). The graphs are stored in the KB upon closing.

Queries only consider knowledge in the KB. This means that queries involving the graphs (such as the standard Pro/3 knowledge dependency queries), will not reflect changes which have taken place after the KB was opened. To compensate for this potential problem, a command to update the graph knowledge in the KB has been included the KB-menu. This command can then be used prior to running such queries.

 

Drawing the graph

The dependency graph can be drawn as a tree directly or exported to a graph drawing package.

RECURSIVE FUNCTIONS

Pro/3 permits directly as well as indirectly recursive functions (a function calling itself). However, such cycles can not be represented in the acyclic dependency graph and are ignored (this does not impair the sentence derivation logic). Consider the following example:

Assume the functions funcA, funcB, funcC and func D
funcA calls funcB, funcC and func D
funcB calls itself
funcC calls funcA and funcD
func D calls no functions
This call structure implies the following dependency graph structure:
funcB determines funcA
funcC determines funcA
funcD determines funcA
funcB determines funcB
funcA determines funcC
funcD determines funcC
The cyclic parts, however, are ignored in the actual graph, which only will include:
funcB determines funcA
funcC determines funcA
funcD determines funcA
funcD determines funcC

This way of treating recursive functions do not have any side-effects within Pro/3.

Sentence Derivation Process Steps

Sentence derivation is a four-step process invoked by the KE through the Sentence Derivation-window, which also includes options for (re-)derivation of all sentences in the KB (regardless of derivation status), re-generation of the dependency graph and refresh of subscribed sentence types. There is also a derivation strategy report which shows the required sequence of sentence type derivations (and the sentence rules involved). 

The four steps are as follows:

Step 0: (optional) REFRESHING SUBSCRIBED SENTENCE TYPES

See subscribed sentence types.

Step 1: CREATING THE DERIVATION GRAPH

Before the derivation of sentences starts, Pro/3 needs to know: (i) the sentence types which require (re-)derivation, and (ii) the appropriate sequence of sentence type derivations (sentences are derived type by type). This information is found in the dependency graph, however a slightly different graph, the derivation graph, is generated as the first step in the derivation (the predicate used in the derivation graph is derives (rather than determines). The derivation graph is generated from the dependency graph and has a similar structure, however, with only two node types:

DETERMINANT

DEPENDENT
2 - SENTENCE TYPE 3 - SENTENCE RULE using the sentence type in the condition
3 - SENTENCE RULE 2 - SENTENCE TYPE concluded by the sentence rule

Inexact rules and functions

Inexact rules and functions are not needed in the derivation graph. Dependencies from a sentence type or sentence rule node via inexact rules or functions to another sentence type or sentence rule are added. The dependencies ST->IR and IR->SR, will be represented as one edge in the derivation graph i.e. ST->SR.

Rules with open entity type arguments - derived rules

The other important difference between the two graphs, is that sentence group-nodes are used in the dependency graph, but not used in the derivation graph (these nodes originate from sentence rules with open entity arguments). 

The creation of the derivation graph involves (i) straight duplication of all dependencies not involving sentence groups and (ii) substitution of dependencies involving sentence groups with sets of dependencies using the sentence group's sentence types. This involves introducing new rules derived from the original sentence group rule (one rule for each sentence type - called derived rules). The following example illustrates this process:

Consider the following implication rule:

The rule involves the following dependencies:

  • sentence type business scenario exists determines rule CONDPRO|1|0
  • sentence group is projected determines rule CONDPRO|1|0
  • rule CONDPRO|1|0 determines sentence group is conditionally projected

Pro/3 will check the actual sentence types in the is conditionally projected sentence group. Let's assume that the following four sentence types exist: revenue cash flow is projected, interest payment is projected, repayment is projected and expense cash flow is projected. From the original sentence group rule, Pro/3 will create one new rule corresponding to each of these four sentence types (i.e. by replacing the open entity variable X with the sentence type). The three dependencies in the dependency graph will accordingly be represented by 12 dependencies in the derivation graph:

revenue cash flow is projected derives CONDPRO|1|1
business scenario exists derives CONDPRO|1|1
CONDPRO|1|1 derives revenue cash flow is conditionally projected
interest payment is projected derives CONDPRO|1|2
business scenario exists derives CONDPRO|1|2
CONDPRO|1|2 derives interest payment is conditionally projected
repayment is projected derives CONDPRO|1|3
business scenario exists derives CONDPRO|1|3
CONDPRO|1|3 derives repayment is conditionally projected
expense cash flow is projected derives CONDPRO|1|4
business scenario exists derives CONDPRO|1|4
CONDPRO|1|4 derives expense cash flow is conditionally projected

Rules CONDPRO|1|1..4 are new rules derived from the original rule CONDPRO|1|0. The rule-tree under shows CONDPRO|1|4:

 

Step 2: CASCADING 'UN-DERIVED' STATUSES

Pro/3 keeps track of each dependency's derivation status as records are added, deleted or modified in the KB. However, the status is not cascaded recursively through the graph. The cascading is done in the derivation graph just after its creation, such that the successors of all dependencies with status 0 also are set to 0.
 

Step 3: DERIVING SENTENCE TYPES

Sentence types are derived one by one in determinant-dependent order - a sentence type can be derived after all it's determinant sentence types have been derived. Sentence types without determinants are not derived (they correspond to sentence types defined by explicitly entered sentences only). Only sentence rules can be direct determinants of a sentence type in the derivation graph, and vice versa only sentence types can be direct determinants of sentence rules.

The derivation of one sentence type involves four steps:

  • deletion of derived sentences
  • activation of all sentence rule direct determinants
  • internal execution of derivation query
  • inactivation of rules
  • publication of the sentence type (if such a publication is defined).

The sentence type revenue revenue cash flow is conditionally projected has one determinant rule (INC-EXP|1): 

Derivation of this sentence type involves the steps:

  • Deletion of all revenue cash flow is conditionally projected derived sentences from the KB (i.e. originating from a previous sentence derivation);
  • Changing of the record status of the rule INC-EXP|2 to active;
  • Execution of the derivation query:  which revenue cash flows are conditionally projected?
  • Insertion of all resulting sentences into the KB (as derived sentences);
  • Changing the record status of rule CONDPRO|1|1 to inactive.
Step 4: SETTING DEPENDENCY GRAPH STATUS

The fourth and last step is to set all dependencies as 'derived' in the dependency graph.

 

SENTENCE DERIVATION STATISTICS

Pro/3 logs a few facts of  the most recent derivation of each sentence type (sentence derivation statistics is in the KB-sentences). This includes the number of sentences derived, the derivation time (in seconds) and derivation start- and end-time. The information is displayed in the Sentence Derivation-window and used in the Sentence-report. The information to estimate the time it will take to re-derive all sentence types.

Acyclicity

The dependency graph (and derivation graph) cannot include cycles. This imposes some essential limitations on rules. 

The same sentence type can not appear both in the condition and in the conclusion (directly and indirectly i.e. via other sentence rules)

This means that you cannot type rules of the type:

  1. if person X knows person Y, then person Y knows person X

  2. if person X knows person Y, then person X is familiar with person Y

  3. if  person X is familiar with person Y, then person X knows person Y

(Rule 1 is never acceptable, while Rule 2 and 3 are unacceptable in the same database - they could exist in the same knowledge base in a recursive multi-KB configuration). 

There are different ways of working around this constraint, as illustrated by the following example. 

 

Example

The rule if the cash flow with amount N and currency DEM exists, then the cash flows with amount (N/1.85) and currency US$ exists, is not allowed since the cash flow exists sentence type appear both in the condition and in the conclusion. The rule can be re-structured in different ways:

(1) Introduce two cash flow entity types: DEM cash flow and US$ cash flow. The rule can then be rewritten as:

if the DEM cash flow with amount N exists, then the US$ cash flow with amount (N/1.85) exists.

(2) Keep the cash flow exists sentence type and introduce a generic sentence type US$-equivalent cash flow exists. The existing rule will then be replaced by two rules:

  • if the cash flow with amount N and currency DEM exists, then the US$ equivalent cash flow with amount (N/1.85) exists and

  • if the cash flow with amount N and currency US$ exists, then the US$ equivalent cash flow with amount N exists.
 

Another approach would be to use a multi-KB configuration, since cycles involving two or more of the participating KBs are possible. See cyclic multi-KBs for details.