Brought to you by EarthWeb
IT Library Logo

Click Here!
Click Here!

Search the site:
 
EXPERT SEARCH -----
Programming Languages
Databases
Security
Web Services
Network Services
Middleware
Components
Operating Systems
User Interfaces
Groupware & Collaboration
Content Management
Productivity Applications
Hardware
Fun & Games

EarthWeb Direct EarthWeb Direct Fatbrain Auctions Support Source Answers

EarthWeb sites
Crossnodes
Datamation
Developer.com
DICE
EarthWeb.com
EarthWeb Direct
ERP Hub
Gamelan
GoCertify.com
HTMLGoodies
Intranet Journal
IT Knowledge
IT Library
JavaGoodies
JARS
JavaScripts.com
open source IT
RoadCoders
Y2K Info

Previous Table of Contents Next


2.2.3. Implicit Cross-Subsumption

This type of subsumption can cause propagation anomalies, including unnecessary input role, unreachable goals, and circular inference structure. Such kinds of anomalies do not necessarily produce errors, but do affect the performance of the system.

Unnecessary Input Role. This type of cross-subsumption occurs when an inference step s produces an output role produced by no other inference step, and which is consumed by another inference step s’. In addition there is a subtyping relation between the input roles of the two inference steps. In such situation, the subsuming role becomes an unnecessary input role. An input role of the inference step s’ becomes unnecessary iff

An example is given in Figure 8, where the subsuming knowledge role y’ is unnecessary input role for the inference step s’, as there is the following subtyping relation: y [inverted y] y’. In other words, any substitution for y that satisfies the inference step s, also satisfies s’.

The counterpart anomaly in rule bases can occur when an action in a rule is propagated to another rule as a condition and results in at least one subsumption relationship between a pair of literals in the condition clause. For example:


FIGURE 8 Unnecessary input role caused by implicit cross-subsumption.

p(x, a11) [wedge] q(x, a21) —> r(x, b1)

p(x, a1’) [wedge] r(x, b1) —> s(x)

After forward chaining, the condition in the second rule becomes:

p(x, a11) [wedge] q(x, a21) —> p(x, a1’)

where the third subcondition subsumes the first one. Depending on the context, the two rules may be combined into one, or remove the unnecessary condition in the second rule.

Unreachable Goal. This type of cross-subsumption occurs when an inference step s produces an output role produced by no other inference step, and which is consumed by another inference step s’. In addition, the input roles of the two inference steps are subtypes of the same supertype. In such a situation, either of the two inference steps are unsatisfiable, and there the output goal becomes unreachable, unless the variables of supertypes are allowed to have multiple values. Mutual exclusiveness of objects instantiated makes a certain goal unreachable. The output role of an inference step s’ is unreachable in the structure I iff

An example is given in Figure 9. If there exists a supertype ys, such y’ [inverted y] ys and y [inverted y] ys does not allow multivalues, than the two inference steps are mutually exclusive. In any case, i.e., either the value is of type y’ or y’’, the goal w of the inference step s’ is unreachable.

The counterpart anomaly in rule bases is shown in the following example:

p(x, a11) [wedge] q(x, a21) —> r(x, b1)

p(x, a12) [wedge] r(x, b1) —> s(x)


FIGURE 9 Unreachable goal role caused by implicit cross-subsumption.

As p(x, a11) and p(x, a12) cannot be satisfied simultaneously, s(x) is unreachable goal.

2.2.4. Circular Inference Structure

In rule bases, a set of rules is circular if the chaining of those rules in the set forms a cycle. Circular rules causes that the system will enter an infinite chain at run time. The rules are connected so that at least one literal in action statements is syntactially matched with at least one literal in condition statements. However, syntactic match cannot cover the implicit relationships between literals. An example is the following:

p(x, a1’) —> q(x, a21)

q(x, a2’) —> r(x, a31)

r(x, a3’) —> p(x, a11)

In the case of inference structures, we say that an inference step s initiates a cycle iff

An example is given in Figure 10.

2.2.5. Conclusions

Many vendors offer today software development tools that include both objects and rules and provide rapid development platforms for expert systems. However, most of these tools that are used for building hybrid systems do not provide support for analysis of subsumption relations that may cause anomalies. Consequently, the burden of maintaining the object structure and subsumption relations among literals in rules is left to developers. The perspective put forward in this section was that performing V&V activities might be easier at the level of conceptual model, rather than the level of implemented system. Good practices in software engineering, such as type checking, may help in automating the analysis of subsumption relations and detect anomalies.


FIGURE 10 Circular inference structure caused by implicit cross-subsumption.


Previous Table of Contents Next

footer nav
Use of this site is subject certain Terms & Conditions.
Copyright (c) 1996-1999 EarthWeb, Inc.. All rights reserved. Reproduction in whole or in part in any form or medium without express written permission of EarthWeb is prohibited. Please read our privacy policy for details.