001: package org.mandarax.reference;
002:
003: /*
004: * Copyright (C) 1999-2004 <A href="http://www-ist.massey.ac.nz/JBDietrich" target="_top"> Jens
005: * Dietrich </a>
006: *
007: * This library is free software; you can redistribute it and/or modify it
008: * under the terms of the GNU Lesser General Public License as published by the
009: * Free Software Foundation; either version 2 of the License, or (at your
010: * option) any later version.
011: *
012: * This library is distributed in the hope that it will be useful, but WITHOUT
013: * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
014: * FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License
015: * for more details.
016: *
017: * You should have received a copy of the GNU Lesser General Public License
018: * along with this library; if not, write to the Free Software Foundation,
019: * Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
020: */
021: import java.util.*;
022: import org.mandarax.kernel.*;
023: import org.mandarax.util.ClauseIterator;
024:
025: /**
026: * Implementation of an inference engine returning many results.
027: * @author <A href="http://www-ist.massey.ac.nz/JBDietrich" target="_top">Jens Dietrich</A>
028: * @version 3.4 <7 March 05>
029: * @since 1.7.2
030: */
031: public final class ResolutionInferenceEngine2 extends
032: AbstractResolutionInferenceEngine {
033:
034: /**
035: * Constructor.
036: */
037: public ResolutionInferenceEngine2() {
038: super ();
039: }
040:
041: /**
042: * Get the feature descriptions.
043: *
044: * @return the feature descriptions
045: */
046: public InferenceEngineFeatureDescriptions getFeatureDescriptions() {
047: if (featureDescriptions == null) {
048: featureDescriptions = new InferenceEngineFeatureDescriptions() {
049: protected void initialize() {
050: super .initialize();
051: this .supported
052: .add(InferenceEngineFeatureDescriptions.MULTIPLE_RESULTS);
053: this .supported
054: .add(InferenceEngineFeatureDescriptions.LOOP_CHECKS);
055: this .supported
056: .add(InferenceEngineFeatureDescriptions.DERIVATION_EVENT_LISTENERS);
057: }
058:
059: };
060: }
061: return featureDescriptions;
062: }
063:
064: /**
065: * Try to proof a goal.
066: *
067: * @return a derivation node
068: * @param goal -
069: * the goal that has to be proved
070: * @param constraintPool -
071: * a list of constraints
072: * @param queryVariables -
073: * a list of query variables
074: * @param kb -
075: * the knowledge base used
076: * @param counter -
077: * the proof step counter
078: * @param renameVariables
079: * a variable renaming
080: * @param logEnabled -
081: * indicates whether we must log this proof step
082: * @param results -
083: * the list collecting the results
084: * @param appliedClauses -
085: * a list of all clauses applied so far (used to detect loops)
086: * @param exceptionHandlingStrategy -
087: * an integer decoding the exception handling strategy when
088: * fetching and resolving ClauseSetExceptions
089: * @param cardinalityConstraint -
090: * the cardinality constraint specifying the number of results
091: * we are looking for
092: * @param listeners
093: * derivation listeners
094: * @param session
095: * a session
096: * @throws InferenceException
097: */
098: private DerivationNodeImpl proof(Clause goal, List constraintPool,
099: DerivationStepCounter counter,
100: VariableRenaming renameVariables, boolean logEnabled,
101: List appliedClauses, List results, SessionImpl session)
102: throws InferenceException {
103:
104: int exceptionHandlingStrategy = session
105: .getExceptionHandlingStrategy();
106: int cardinalityConstraint = session.getCardinalityContraint();
107: org.mandarax.kernel.KnowledgeBase kb = session
108: .getKnowledgeBase();
109:
110: // make sure that the session is uptodate
111: session.update(renameVariables.getAllRenamings(),
112: constraintPool);
113:
114: // for performance reasons we want to minimize checks whether log is
115: // enabled. On the other hand, we would like to switch log on / off
116: // during a proof (e.g., to analyse a long proof). This implementation
117: // checks the respective log category every 10 steps
118: boolean logOn = (counter.count % 10 == 0) ? LOG_IE_STEP
119: .isDebugEnabled() : logEnabled;
120: DerivationNodeImpl node = new DerivationNodeImpl();
121: node.setId(counter.next());
122: // node.supportedSolution = results.size();
123: DerivationNodeImpl nextNode = null;
124:
125: if (logOn) {
126: LOG_IE_STEP.debug("PROOF STEP "
127: + String.valueOf(counter.count));
128: LOG_IE_STEP.debug("Goal : " + goal.toString());
129: }
130:
131: // try to remove clauses using the object semantics
132: goal = performSemanticalEvaluation(goal, session, logOn);
133:
134: if (goal == null) {
135: node.setFailed(true);
136: return node;
137: }
138:
139: // check whether the max proof length has been reached
140: if (counter.count >= MAXSTEPS) {
141: if (logOn) {
142: LOG_IE_STEP
143: .debug("Maximum number of steps reached, stop here !");
144: }
145:
146: return node;
147: }
148:
149: // if the goal is the empty clause, return success
150: if (goal.isEmpty()) {
151: if (logOn) {
152: LOG_IE_STEP.debug("Derivation successful !");
153: }
154: results.add(node);
155: // new in 3.2: notify listener
156: notifyListenersOnResult(session, logOn);
157:
158: node.setResultNode(true);
159: node.setSupported(results.size() - 1);
160: if (logOn) {
161: LOG_IE_STEP.debug("Set result node supporting result "
162: + (results.size() - 1) + ": " + node);
163: }
164: node.setFailed(false);
165: // check whether we have enough results
166: if (cardinalityConstraint != ALL) {
167: node
168: .setLastNode((results.size() >= cardinalityConstraint));
169: }
170: return node;
171: }
172:
173: // check for the next clause to continue. Try resolution.
174: try {
175: ClauseIterator e = kb.clauses(goal, null);
176: boolean useClause = true;
177: while (e.hasMoreClauses()
178: && (cardinalityConstraint == ALL || results.size() < cardinalityConstraint)) {
179: useClause = true;
180: Resolution r = null;
181: Clause c = null;
182: Clause workCopy = null;
183: try {
184: c = e.nextClause();
185: workCopy = renameVariables.cloneAndRenameVars(c);
186: } catch (ClauseSetException x) {
187: String msg = "Exception fetching clause from iterator for "
188: + goal;
189: LOG_IE_STEP.error(msg, x);
190: // depending on the exception handling strategy we forward
191: // the exception or carry on
192: if (exceptionHandlingStrategy == BUBBLE_EXCEPTIONS)
193: throw new InferenceException(msg, x);
194: useClause = false;
195: }
196: if (useClause
197: && (r = Resolution.resolve(workCopy, goal,
198: unificationAlgorithm, selectionPolicy,
199: session)) != null) {
200: appliedClauses.add(c);
201: if (loopCheckingAlgorithm
202: .isInfiniteLoop(appliedClauses)) {
203: if (logOn) {
204: LOG_IE_STEP
205: .debug("LoopChecking Algorithm "
206: + loopCheckingAlgorithm
207: + " has detected a loop! Try to continue with next clause");
208: }
209: } else {
210: // log
211: if (logOn) {
212: LOG_IE_STEP
213: .debug("Can apply the following rule:");
214: LOG_IE_STEP.debug("Clause : "
215: + c.toString());
216: LOG_IE_STEP.debug("Clause (rn): "
217: + workCopy.toString());
218:
219: // log unification
220: Replacement nextReplacement = null;
221: for (Iterator er = r.unification.replacements
222: .iterator(); er.hasNext();) {
223: nextReplacement = (Replacement) er
224: .next();
225: LOG_IE_STEP.debug("unify : "
226: + nextReplacement.original
227: .toString()
228: + " -> "
229: + nextReplacement.replacement
230: .toString());
231: }
232: }
233:
234: // build a new subgoal
235: Clause nextGoal = getNextGoal(workCopy, goal, r);
236:
237: // build a new constraint pool for the next step
238: List nextConstraintPool = getNextConstraintPool(
239: constraintPool, r);
240:
241: // apply constraints
242: nextGoal = nextGoal.apply(nextConstraintPool);
243:
244: // rename variables in the subgoal
245: nextGoal = renameVariables
246: .cloneAndRenameVars(nextGoal);
247:
248: // keep the renamed var here, otherwise they get
249: // overridden in the recursion
250: Hashtable renamed = renameVariables
251: .getRecentRenamings();
252:
253: // log renamings
254: if (logOn) {
255: Object nextRenaming = null;
256:
257: for (Enumeration er = renamed.keys(); er
258: .hasMoreElements();) {
259: nextRenaming = er.nextElement();
260: LOG_IE_STEP.debug("rename : "
261: + nextRenaming.toString()
262: + " -> "
263: + renamed.get(nextRenaming)
264: .toString());
265: }
266: }
267:
268: // proof the new subgoal
269: nextNode = proof(nextGoal, nextConstraintPool,
270: counter, renameVariables, logOn,
271: appliedClauses, results, session);
272:
273: nextNode.setQuery(goal);
274: nextNode.setAppliedClause(c);
275:
276: // register the subnode
277: node.addSubNode(nextNode);
278:
279: if (!nextNode.isFailed()) {
280: // add renamings and unification
281: nextNode.varRenamings = renamed;
282: nextNode.setUnification(r.unification);
283: }
284: }
285: } else {
286: if (logOn) {
287: LOG_IE_STEP
288: .debug("Cannot apply the following rule:");
289: LOG_IE_STEP.debug("Clause : "
290: + c.toString());
291: LOG_IE_STEP.debug("Clause (rn): "
292: + workCopy.toString());
293: }
294: }
295: }
296: // new in 2.0 - release resources!
297: e.close();
298: } catch (ClauseSetException x) {
299: String msg = "Exception getting clause iterator for "
300: + goal;
301: LOG_IE_STEP.error(msg, x);
302: if (exceptionHandlingStrategy == BUBBLE_EXCEPTIONS)
303: throw new InferenceException(msg, x);
304: }
305: if ((nextNode == null) || nextNode.isFailed()) {
306: List l = node.getSubNodes();
307: int n = l.size();
308: boolean result = true;
309: for (int i = 0; i < n; i++) {
310: result = result
311: && ((DerivationNodeImpl) l.get(i)).isFailed();
312: node.setFailed(result);
313: }
314: // new in 1.9.2
315: node.setFailed(result);
316: }
317: return node;
318: }
319:
320: /**
321: * Answer a query, retrieve (multiple different) result. The cardinality
322: * contraints describe how many results should be computed. It is either
323: * <ol>
324: * <li><code>ONE</code>- indicating that only one answer is expected
325: * <li><code>ALL</code>- indicating that all answers should be computed
326: * <li><code>an integer value greater than 0 indicating that this number of results expected
327: * </ol>
328: * @see #ONE
329: * @see #ALL
330: * @return the result set of the query
331: * @param query the query clause
332: * @param kb the knowledge base used to answer the query
333: * @param aCardinalityConstraint the number of results expected
334: * @param exceptionHandlingPolicy one of the constants definied in this class (BUBBLE_EXCEPTIONS,TRY_NEXT)
335: * @throws an InferenceException
336: */
337: public ResultSet query(Query query,
338: org.mandarax.kernel.KnowledgeBase kb,
339: int aCardinalityConstraint, int exceptionHandlingPolicy)
340: throws InferenceException {
341: Clause firstGoal = getGoal(query);
342: VariableRenaming renameVariables = new VariableRenaming();
343: List resultNodes = new ArrayList();
344: SessionImpl session = new SessionImpl(kb, this , query,
345: exceptionHandlingPolicy, aCardinalityConstraint);
346: notifyListenersOnDerivationStart(session, LOG_IE_STEP
347: .isDebugEnabled());
348:
349: // proof
350: DerivationNodeImpl linResult = proof(firstGoal,
351: new ArrayList(), new DerivationStepCounter(),
352: renameVariables, LOG_IE_STEP.isDebugEnabled(),
353: new ArrayList(MAXSTEPS), resultNodes, session);
354: for (int i = 0; i < resultNodes.size(); i++)
355: ((DerivationNodeImpl) resultNodes.get(i))
356: .propagateSupportedSolutions();
357: linResult
358: .setSemanticEvaluationPolicy(getSemanticEvaluationPolicy());
359: return new ResultSetImpl2(linResult, resultNodes, firstGoal);
360:
361: }
362: }
|