001: package org.mandarax.reference;
002:
003: /*
004: * Copyright (C) 1999-2004 <A href="http://www-ist.massey.ac.nz/JBDietrich" target="_top">Jens Dietrich</a>
005: *
006: * This library is free software; you can redistribute it and/or
007: * modify it under the terms of the GNU Lesser General Public
008: * License as published by the Free Software Foundation; either
009: * version 2 of the License, or (at your option) any later version.
010: *
011: * This library is distributed in the hope that it will be useful,
012: * but WITHOUT ANY WARRANTY; without even the implied warranty of
013: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
014: * Lesser General Public License for more details.
015: *
016: * You should have received a copy of the GNU Lesser General Public
017: * License along with this library; if not, write to the Free Software
018: * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
019: */
020: import java.util.*;
021: import org.mandarax.kernel.*;
022: import org.mandarax.util.ClauseIterator;
023:
024: /**
025: * Implementation of an inference engine returning only one result.
026: * @author <A href="http://www-ist.massey.ac.nz/JBDietrich" target="_top">Jens Dietrich</A>
027: * @version 3.4 <7 March 05>
028: * @since 1.0
029: */
030: public final class ResolutionInferenceEngine extends
031: AbstractResolutionInferenceEngine {
032:
033: private static final DerivationTreeBuilder derivationTreeBuilder = new DerivationTreeBuilder();
034:
035: /**
036: * Constructor.
037: */
038: public ResolutionInferenceEngine() {
039: super ();
040: }
041:
042: /**
043: * Get the feature descriptions.
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.LOOP_CHECKS);
053: }
054:
055: };
056: }
057:
058: return featureDescriptions;
059: }
060:
061: /**
062: * Try to proof a goal.
063: * @return a derivation node
064: * @param goal - the goal that has to be proved
065: * @param constraintPool - a list of constraints
066: * @param count - the proof step count
067: * @param renameVariables a variable renaming
068: * @param logEnabled - indicates whether we must log this proof step
069: * @param appliedClauses - a list of all clauses applied so far (used to detect loops)
070: * @param session a session
071: * @throws InferenceException
072: */
073: private DerivationNodeImpl proof(Clause goal, List constraintPool,
074: DerivationStepCounter counter,
075: VariableRenaming renameVariables, boolean logEnabled,
076: List appliedClauses, SessionImpl session)
077: throws InferenceException {
078:
079: org.mandarax.kernel.KnowledgeBase kb = session
080: .getKnowledgeBase();
081:
082: // make sure that the session is uptodate
083: session.update(renameVariables.getAllRenamings(),
084: constraintPool);
085:
086: // for performance reasons we want to minimize checks whether log is
087: // enabled. On the other hand, we would like to switch log on / off
088: // during a proof (e.g., to analyse a long proof). This implementation
089: // checks the respective log category every 10 steps
090: boolean logOn = (counter.count % 10 == 0) ? LOG_IE_STEP
091: .isDebugEnabled() : logEnabled;
092: DerivationNodeImpl node = new DerivationNodeImpl();
093: node.setId(counter.next());
094: DerivationNodeImpl nextNode = null;
095:
096: if (logOn) {
097: LOG_IE_STEP.debug("PROOF STEP "
098: + String.valueOf(counter.count));
099: LOG_IE_STEP.debug("Goal : " + goal.toString());
100: }
101:
102: // try to remove clauses using the object semantics
103: goal = performSemanticalEvaluation(goal, null, logOn);
104:
105: if (goal == null) {
106: node.setFailed(true);
107: return node;
108: }
109:
110: // check whether the max proof length has been reached
111: if (counter.count >= MAXSTEPS) {
112: if (logOn) {
113: LOG_IE_STEP
114: .debug("Maximum number of steps reached, stop here !");
115: }
116: return node;
117: }
118:
119: // if the goal is the empty clause, return success
120: if (goal.isEmpty()) {
121: if (logOn) {
122: LOG_IE_STEP.debug("Derivation successful !");
123: }
124:
125: node.setFailed(false);
126: node.setResultNode(true);
127:
128: return node;
129: }
130:
131: // check for the next clause to continue. Try resolution.
132:
133: try {
134: ClauseIterator e = kb.clauses(goal, null);
135: boolean useClause = true;
136: while (e.hasMoreClauses()
137: && ((nextNode == null) || nextNode.isFailed())) {
138: useClause = true;
139: Resolution r = null;
140: Clause c = null;
141: Clause workCopy = null;
142: try {
143: c = e.nextClause();
144: workCopy = renameVariables.cloneAndRenameVars(c);
145: } catch (ClauseSetException x) {
146: String msg = "Exception fetching clause from iterator for "
147: + goal;
148: LOG_IE_STEP.error(msg, x);
149: // depending on the exception handling strategy we forward the exception or carry on
150: if (session.getExceptionHandlingStrategy() == BUBBLE_EXCEPTIONS)
151: throw new InferenceException(msg, x);
152: useClause = false;
153: }
154: if (useClause
155: && (r = Resolution.resolve(workCopy, goal,
156: unificationAlgorithm, selectionPolicy,
157: session)) != null) {
158: appliedClauses.add(c);
159:
160: if (loopCheckingAlgorithm
161: .isInfiniteLoop(appliedClauses)) {
162: if (logOn) {
163: LOG_IE_STEP
164: .debug("LoopChecking Algorithm "
165: + loopCheckingAlgorithm
166: + " has detected a loop! Try to continue with next clause");
167: }
168: } else {
169: // log
170: if (logOn) {
171: LOG_IE_STEP
172: .debug("Can apply the following rule:");
173: LOG_IE_STEP.debug("Clause : "
174: + c.toString());
175: LOG_IE_STEP.debug("Clause (rn): "
176: + workCopy.toString());
177:
178: // log unification
179: Replacement nextReplacement = null;
180:
181: for (Iterator er = r.unification.replacements
182: .iterator(); er.hasNext();) {
183: nextReplacement = (Replacement) er
184: .next();
185: LOG_IE_STEP.debug("unify : "
186: + nextReplacement.original
187: .toString()
188: + " -> "
189: + nextReplacement.replacement
190: .toString());
191: }
192: }
193:
194: // build a new subgoal
195: Clause nextGoal = getNextGoal(workCopy, goal, r);
196:
197: // build a new constraint pool for the next step
198: List nextConstraintPool = getNextConstraintPool(
199: constraintPool, r);
200:
201: // apply constraints
202: nextGoal = nextGoal.apply(nextConstraintPool);
203:
204: // rename variables in the subgoal
205: nextGoal = renameVariables
206: .cloneAndRenameVars(nextGoal);
207:
208: // keep the renamed var here, otherwise they get overridden in the recursion
209: Hashtable renamed = renameVariables
210: .getRecentRenamings();
211:
212: // log renamings
213: if (logOn) {
214: Object nextRenaming = null;
215:
216: for (Enumeration er = renamed.keys(); er
217: .hasMoreElements();) {
218: nextRenaming = er.nextElement();
219: LOG_IE_STEP.debug("rename : "
220: + nextRenaming.toString()
221: + " -> "
222: + renamed.get(nextRenaming)
223: .toString());
224: }
225: }
226:
227: // proof the new subgoal
228: nextNode = proof(nextGoal, nextConstraintPool,
229: counter, renameVariables, logOn,
230: appliedClauses, session);
231:
232: nextNode.setQuery(goal);
233: nextNode.setAppliedClause(c);
234:
235: // register the subnode
236: node.addSubNode(nextNode);
237:
238: if (!nextNode.isFailed()) {
239:
240: // add renamings and unification
241: nextNode.varRenamings = renamed;
242: nextNode.setUnification(r.unification);
243: }
244: }
245: } else {
246: if (logOn) {
247: LOG_IE_STEP
248: .debug("Cannot apply the following rule:");
249: LOG_IE_STEP.debug("Clause : "
250: + c.toString());
251: LOG_IE_STEP.debug("Clause (rn): "
252: + workCopy.toString());
253: }
254: }
255: }
256: // new in 2.0 - release resources!
257: e.close();
258: } catch (ClauseSetException x) {
259: String msg = "Exception getting clause iterator for "
260: + goal;
261: LOG_IE_STEP.error(msg, x);
262: if (session.getExceptionHandlingStrategy() == BUBBLE_EXCEPTIONS)
263: throw new InferenceException(msg, x);
264: }
265:
266: if ((nextNode == null) || nextNode.isFailed()) {
267: node.setFailed(true);
268: }
269:
270: return node;
271: }
272:
273: /**
274: * Answer a query, retrieve (multiple different) result.
275: * The cardinality contraints describe how many results should be computed. It is either
276: * <ol>
277: * <li> <code>ONE</code> - indicating that only one answer is expected
278: * <li> <code>ALL</code> - indicating that all answers should be computed
279: * <li> <code>an integer value greater than 0 indicating that this number of results expected
280: * </ol>
281: * This inference engines does not support retrieving multiple answers!
282: * If requested, a runtime exception (<code>java.lang.IllegalArgumentException</code>)
283: * is thrown indicating that the parameter (e.g. <code>ALL</code>) is not valid.
284: * @see #ONE
285: * @see #ALL
286: * @return the result set of the query
287: * @param query the query
288: * @param kb the knowledge base used to answer the query
289: * @param aCardinalityConstraint the number of results expected
290: * @param exceptionHandlingPolicy one of the constants definied in this class (BUBBLE_EXCEPTIONS,TRY_NEXT)
291: * @throws an InferenceException
292: */
293: public ResultSet query(final Query query,
294: org.mandarax.kernel.KnowledgeBase kb,
295: int aCardinalityConstraint, int exceptionHandlingPolicy)
296: throws InferenceException {
297: final Clause firstGoal = getGoal(query);
298: VariableRenaming renameVariables = new VariableRenaming();
299: DerivationNodeImpl linResult = proof(firstGoal,
300: new ArrayList(), new DerivationStepCounter(),
301: renameVariables, LOG_IE_STEP.isDebugEnabled(),
302: new ArrayList(MAXSTEPS), new SessionImpl(kb, this ,
303: query, exceptionHandlingPolicy,
304: InferenceEngine.ONE));
305: linResult
306: .setSemanticEvaluationPolicy(getSemanticEvaluationPolicy());
307: Replacement[] replacements = IEUtils.getReplacements(linResult,
308: firstGoal);
309: DerivationNodeImpl root = derivationTreeBuilder
310: .buildTree(linResult);
311: final Result result = root.isFailed() ? null : new Result(
312: new Derivation(root, 0), replacements);
313: ResultSet rs = new ResultSet() {
314: private int pos = -1;
315: private List vars = null;
316:
317: /**
318: * Moves the cursor to the first row in this ResultSet object.
319: * @return true if the cursor is on a valid row; false if there are no rows in the result set
320: */
321: public boolean first() {
322: pos = 0;
323: return result != null;
324: }
325:
326: /**
327: * Moves the cursor to the last row in this ResultSet object.
328: * @return true if the cursor is on a valid row; false if there are no rows in the result s
329: */
330: public boolean last() {
331: pos = 0;
332: return result != null;
333: }
334:
335: /**
336: * Retrieves the current result number. Numbering starts with 1.
337: * @return a number
338: */
339: public int getResultNumber() {
340: return pos == 0 ? 1 : -1;
341: }
342:
343: /**
344: * Moves the cursor down one row from its current position. A ResultSet cursor is initially positioned
345: * before the first row; the first call to the method next makes the first row the current row;
346: * the second call makes the second row the current row, and so on.
347: * @return true if the new current row is valid; false if there are no more rows
348: */
349: public boolean next() {
350: pos = pos + 1;
351: return result != null && pos == 0;
352: }
353:
354: /**
355: * Moves the cursor to the previous row in this ResultSet object.
356: * @return true if the cursor is on a valid row; false if it is off the result set
357: */
358: public boolean previous() {
359: return false;
360: };
361:
362: /**
363: * Get the current position of the cursor.
364: * @return an integer
365: */
366: public int getCursorPosition() {
367: return pos;
368: }
369:
370: /**
371: * Releases this ResultSet resources.
372: */
373: public void close() {
374: }
375:
376: /**
377: * Get the derivation of the current result.
378: * Throw an exception if the cursor is not positioned at a result.
379: * @return the proof (derivation)
380: */
381: public Derivation getProof() throws InferenceException {
382: if (pos != 0)
383: throw new InferenceException(
384: "Illegal cursor position " + pos
385: + " in result set.");
386: return result.getProof();
387: }
388:
389: /**
390: * Get the object that replaces the variable with the given name and type.
391: * If there is no such object, return null.
392: * Throw an exception if the cursor is not positioned at a result.
393: * @return the object that replaced the variable
394: * @param type the type of the variable
395: * @param name the name of the variable
396: * @exception an inference exception
397: */
398: public Object getResult(Class type, String name)
399: throws InferenceException {
400: if (pos != 0)
401: throw new InferenceException(
402: "Illegal cursor position " + pos
403: + " in result set.");
404: return result.getResult(type, name);
405: }
406:
407: /**
408: * Get the object that replaces the variable.
409: * If there is no such object, return null.
410: * Throw an exception if the cursor is not positioned at a result.
411: * @return the object that replaced the variable
412: * @param term the variable term that is (perhaps) replaced
413: * @exception an inference exception
414: */
415: public Object getResult(VariableTerm term)
416: throws InferenceException {
417: if (pos != 0)
418: throw new InferenceException(
419: "Illegal cursor position " + pos
420: + " in result set.");
421: return result.getResult(term);
422: }
423:
424: /**
425: * Get a list of all variable terms in the query.
426: * @return a list of variable terms
427: */
428: public List getQueryVariables() {
429: if (vars == null)
430: vars = IEUtils.getVars(firstGoal);
431: return vars;
432: }
433:
434: /**
435: * Indicates whether the cursor is at the first position.
436: * @return a boolean
437: */
438: public boolean isFirst() {
439: return result != null && pos == 0;
440: }
441:
442: /**
443: * Indicates whether the cursor is at the last position.
444: * @return a boolean
445: */
446: public boolean isLast() {
447: return result != null && pos == 0;
448: }
449:
450: /**
451: * Moves the cursor a relative number of results, either positive or negative.
452: * @param offset the number of results
453: * @return true if the cursor is on the result set; false otherwise.
454: */
455: public boolean relative(int offset) {
456: pos = pos + offset;
457: return pos == 0;
458: }
459:
460: /**
461: * Moves the cursor to the given result number.
462: * @param resultNo the number of results.
463: * @return true if the cursor is on the result set; false otherwise
464: */
465: public boolean absolute(int resultNo) {
466: pos = resultNo - 1; // like in JDBC - the number of the first result is 1, not 0 !
467: return pos == 0;
468: }
469:
470: /**
471: * Moves the cursor to the front of this ResultSet object, just before the first row.
472: * This method has no effect if the result set contains no rows.
473: */
474: public void beforeFirst() {
475: pos = -1;
476: }
477:
478: /**
479: * Moves the cursor to the end of this ResultSet object, just after the last row.
480: * This method has no effect if the result set contains no rows.
481: */
482: public void afterLast() {
483: pos = 2;
484: }
485:
486: /**
487: * Retrieves whether the cursor is before the first row in this ResultSet object.
488: * @return true if the cursor is before the first row; false if the cursor is at any other position or the result set contains no rows
489: */
490: public boolean isBeforeFirst() throws InferenceException {
491: return pos == -1;
492: }
493:
494: /**
495: * Retrieves whether the cursor is after the last result in this ResultSet object.
496: * @return true if the cursor is after the last result; false if the cursor is at any other position or the result set contains no results
497: */
498: public boolean isAfterLast() throws InferenceException {
499: return pos == 2;
500: }
501:
502: /**
503: * Get the results as map.
504: * @return a map
505: */
506: public Map getResults() throws InferenceException {
507: if (pos != 0)
508: throw new InferenceException(
509: "Illegal cursor position " + pos
510: + " in result set.");
511: return result.getResults();
512: }
513:
514: };
515: return rs;
516:
517: }
518: }
|