Menu
▾
▴
[DL-Learner SVN] SF.net SVN: dl-learner:[1619] trunk/src/dl-learner/org/dllearner
|
From: <jen...@us...> - 2009-02-20 10:56:08
|
Revision: 1619
http://dl-learner.svn.sourceforge.net/dl-learner/?rev=1619&view=rev
Author: jenslehmann
Date: 2009-02-20 10:56:04 +0000 (Fri, 20 Feb 2009)
Log Message:
-----------
- wrote a class which uses reasoning to minimize a given class description
- reasoning results are cached to improve performance over time for many minimize operations
- implementation passes simple unit test
Modified Paths:
--------------
trunk/src/dl-learner/org/dllearner/core/owl/Description.java
trunk/src/dl-learner/org/dllearner/test/junit/TestOntologies.java
Added Paths:
-----------
trunk/src/dl-learner/org/dllearner/test/junit/MinimizeTests.java
trunk/src/dl-learner/org/dllearner/utilities/owl/DescriptionMinimizer.java
Modified: trunk/src/dl-learner/org/dllearner/core/owl/Description.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/core/owl/Description.java 2009-02-19 15:25:44 UTC (rev 1618)
+++ trunk/src/dl-learner/org/dllearner/core/owl/Description.java 2009-02-20 10:56:04 UTC (rev 1619)
@@ -160,6 +160,11 @@
children.remove(child);
}
+ public void replaceChild(int index, Description newChild) {
+ children.remove(index);
+ children.add(index, newChild);
+ }
+
/**
* Tests whether this description is at the root, i.e.
* does not have a parent.
Added: trunk/src/dl-learner/org/dllearner/test/junit/MinimizeTests.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/test/junit/MinimizeTests.java (rev 0)
+++ trunk/src/dl-learner/org/dllearner/test/junit/MinimizeTests.java 2009-02-20 10:56:04 UTC (rev 1619)
@@ -0,0 +1,46 @@
+/**
+ * Copyright (C) 2007-2009, Jens Lehmann
+ *
+ * This file is part of DL-Learner.
+ *
+ * DL-Learner is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * DL-Learner is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ *
+ */
+package org.dllearner.test.junit;
+
+import org.dllearner.core.ReasonerComponent;
+import org.dllearner.core.owl.Description;
+import org.dllearner.parser.KBParser;
+import org.dllearner.parser.ParseException;
+import org.dllearner.test.junit.TestOntologies.TestOntology;
+import org.dllearner.utilities.owl.DescriptionMinimizer;
+import org.junit.Test;
+
+/**
+ * Tests for minimizing class descriptions.
+ *
+ * @author Jens Lehmann
+ *
+ */
+public class MinimizeTests {
+
+ @Test
+ public void minimizeTest1() throws ParseException {
+ ReasonerComponent reasoner = TestOntologies.getTestOntology(TestOntology.FATHER_OE);
+ DescriptionMinimizer minimizer = new DescriptionMinimizer(reasoner);
+ Description d = KBParser.parseConcept("(\"http://example.com/father#male\" AND (\"http://example.com/father#male\" OR EXISTS \"http://example.com/father#hasChild\".TOP))");
+ Description minD = minimizer.minimize(d);
+ assert(minD.toString().equals("http://example.com/father#male"));
+ }
+}
Modified: trunk/src/dl-learner/org/dllearner/test/junit/TestOntologies.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/test/junit/TestOntologies.java 2009-02-19 15:25:44 UTC (rev 1618)
+++ trunk/src/dl-learner/org/dllearner/test/junit/TestOntologies.java 2009-02-20 10:56:04 UTC (rev 1619)
@@ -19,11 +19,16 @@
*/
package org.dllearner.test.junit;
+import java.io.File;
+import java.net.MalformedURLException;
+
import org.dllearner.core.ComponentInitException;
import org.dllearner.core.ComponentManager;
+import org.dllearner.core.KnowledgeSource;
import org.dllearner.core.ReasonerComponent;
import org.dllearner.core.owl.KB;
import org.dllearner.kb.KBFile;
+import org.dllearner.kb.OWLFile;
import org.dllearner.parser.KBParser;
import org.dllearner.parser.ParseException;
import org.dllearner.reasoning.FastInstanceChecker;
@@ -36,10 +41,11 @@
*/
public final class TestOntologies {
- public enum TestOntology { EMPTY, SIMPLE, SIMPLE_NO_DR, SIMPLE_NO_DISJOINT, SIMPLE_NO_DR_DISJOINT, SIMPLE2, SIMPLE3, R1SUBR2, DATA1, FIVE_ROLES };
+ public enum TestOntology { EMPTY, SIMPLE, SIMPLE_NO_DR, SIMPLE_NO_DISJOINT, SIMPLE_NO_DR_DISJOINT, SIMPLE2, SIMPLE3, R1SUBR2, DATA1, FIVE_ROLES, FATHER_OE };
public static ReasonerComponent getTestOntology(TestOntology ont) {
String kbString = "";
+ String owlFile = "";
if(ont.equals(TestOntology.EMPTY)) {
// no background knowledge
@@ -103,22 +109,31 @@
kbString += "r3(a,b).\n";
kbString += "r4(a,b).\n";
kbString += "r5(a,b).\n";
+ } else if(ont.equals(TestOntology.FATHER_OE)) {
+ owlFile = "examples/family/father_oe.owl";
}
try {
- KB kb = KBParser.parseKBFile(kbString);
+ ComponentManager cm = ComponentManager.getInstance();
+ KnowledgeSource source;
- // create reasoner
- ComponentManager cm = ComponentManager.getInstance();
- KBFile source = new KBFile(kb);
+ // parse KB string if one has been specified
+ if(!kbString.isEmpty()) {
+ KB kb = KBParser.parseKBFile(kbString);
+ source = new KBFile(kb);
+ // parse OWL file otherwise
+ } else {
+ source = cm.knowledgeSource(OWLFile.class);
+ try {
+ cm.applyConfigEntry(source, "url", new File(owlFile).toURI().toURL());
+ } catch (MalformedURLException e) {
+ e.printStackTrace();
+ }
+ }
+
ReasonerComponent rc = cm.reasoner(FastInstanceChecker.class, source);
-// ReasonerComponent rs = cm.reasoningService(rc);
source.init();
rc.init();
- // TODO there shouldn't be a need to call this explicitly!
- // (otherwise we get a NullPointerException, because the hierarchy is not created)
-// rs.prepareSubsumptionHierarchy();
-// rs.prepareRoleHierarchy();
return rc;
} catch(ParseException e) {
e.printStackTrace();
Added: trunk/src/dl-learner/org/dllearner/utilities/owl/DescriptionMinimizer.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/utilities/owl/DescriptionMinimizer.java (rev 0)
+++ trunk/src/dl-learner/org/dllearner/utilities/owl/DescriptionMinimizer.java 2009-02-20 10:56:04 UTC (rev 1619)
@@ -0,0 +1,207 @@
+/**
+ * Copyright (C) 2007-2009, Jens Lehmann
+ *
+ * This file is part of DL-Learner.
+ *
+ * DL-Learner is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * DL-Learner is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ *
+ */
+package org.dllearner.utilities.owl;
+
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Map;
+import java.util.TreeMap;
+
+import org.dllearner.core.ReasonerComponent;
+import org.dllearner.core.owl.Description;
+import org.dllearner.core.owl.Intersection;
+import org.dllearner.core.owl.Negation;
+import org.dllearner.core.owl.Nothing;
+import org.dllearner.core.owl.ObjectAllRestriction;
+import org.dllearner.core.owl.ObjectMaxCardinalityRestriction;
+import org.dllearner.core.owl.ObjectMinCardinalityRestriction;
+import org.dllearner.core.owl.ObjectSomeRestriction;
+import org.dllearner.core.owl.Thing;
+import org.dllearner.core.owl.Union;
+
+/**
+ * Rewrites a description to an equivalent shorter description. Note that
+ * minimizing is not a trivial operation and requires reasoning. The class
+ * keeps an internal cache on reasoning results, i.e. if similar descriptions
+ * are passed to the minimizer, then its performance will improve over time.
+ *
+ * @author Jens Lehmann
+ *
+ */
+public class DescriptionMinimizer {
+
+ private ReasonerComponent reasoner;
+ private ConceptComparator conceptComparator = new ConceptComparator();
+ private Map<Description,Map<Description,Boolean>> cachedSubclassOf = new TreeMap<Description,Map<Description,Boolean>>(conceptComparator);
+
+ public DescriptionMinimizer(ReasonerComponent reasoner) {
+ this.reasoner = reasoner;
+ }
+
+ /**
+ * Method which minimzes the input description. The algorithm does not
+ * replace subdescriptions with named classes, e.g.
+ * if the description "male \sqcap \exists hasChild.\top" is passed to the
+ * algorithm and a class "father" is defined in the obvious way
+ * in the background knowledge, then
+ * it will intentionally not return father. Instead, it preserves the
+ * existing structure of the description, but tries to detect and delete
+ * redundant parts within it. For instance, the description "male \sqcap
+ * father" is minimized to "father".
+ *
+ * @param description The description to minimize.
+ * @return Minimized description.
+ */
+ public Description minimizeClone(Description description) {
+ Description descriptionToMinimize = description.clone();
+ return minimize(descriptionToMinimize);
+ }
+
+ /**
+ * Same as {@link #minimizeClone(Description)}, but with no guarantee that
+ * the input description remains unmodified.
+ * @see #minimizeClone(Description)
+ * @param description The description to minimize.
+ * @return Minimized description.
+ */
+ public Description minimize(Description description) {
+ // minimize all children of the description
+ List<Description> children = description.getChildren();
+ for(int i=0; i<children.size(); i++) {
+ description.replaceChild(i, minimize(children.get(i)));
+ }
+ // make a case distinction based on the structure of the description
+ // (note that we do not have to do anything for a number of cases:
+ // a named class, Thing, Nothing, hasValue restrictions, boolean
+ // value restrictions, double value restrictions)
+ if(children.size()==0) {
+ return description;
+ } else if(description instanceof ObjectSomeRestriction) {
+ // \exists r.\bot \equiv \bot
+ if(description.getChild(0) instanceof Nothing) {
+ return Nothing.instance;
+ }
+ return description;
+ } else if(description instanceof ObjectAllRestriction) {
+ // \forall r.\top \equiv \top
+ if(description.getChild(0) instanceof Thing) {
+ return Thing.instance;
+ }
+ return description;
+ } else if(description instanceof Negation) {
+ // \neg \bot \equiv \top
+ if(description.getChild(0) instanceof Nothing) {
+ return Thing.instance;
+ // \neg \top \equiv \bot
+ } else if(description.getChild(0) instanceof Thing) {
+ return Nothing.instance;
+ }
+ return description;
+ } else if(description instanceof ObjectMaxCardinalityRestriction) {
+ // <= n r.\bot \equiv \top
+ if(description.getChild(0) instanceof Nothing) {
+ return Thing.instance;
+ }
+ return description;
+ } else if(description instanceof ObjectMinCardinalityRestriction) {
+ // >= 0 r.C \equiv \top
+ int number = ((ObjectMinCardinalityRestriction)description).getNumber();
+ if(number == 0) {
+ return Thing.instance;
+ }
+ // >= n r.\bot \equiv \bot if n != 0
+ if(description.getChild(0) instanceof Nothing) {
+ return Nothing.instance;
+ }
+ return description;
+ } else if(description instanceof Intersection || description instanceof Union) {
+ List<Integer> toRemove = new LinkedList<Integer>();
+ // intersection
+ if(description instanceof Intersection) {
+ // in an intersection, we have that D1 \sqcap D2 \equiv D1 if
+ // D1 \sqsubseteq D2; this means we first check whether the
+ // first element in a union is superclass of any other element in the
+ // union; if yes, then we delete it and proceed to the next element
+ for(int i=0; i<children.size(); i++) {
+ for(int j=0; j<children.size(); j++) {
+ if(i != j && isSubclassOf(children.get(j), children.get(i))) {
+ toRemove.add(i-toRemove.size());
+ break;
+ }
+ }
+ }
+ // union
+ } else {
+ // in a union, we have that D1 \sqcup D2 \equiv D2 if
+ // D1 \sqsubseteq D2; this means we first check whether the
+ // first element in a union is subclass of any other element in the
+ // union; if yes, then we delete it and proceed to the next element
+ // (note the difference to intersection)
+ for(int i=0; i<children.size(); i++) {
+ for(int j=0; j<children.size(); j++) {
+ if(i != j && isSubclassOf(children.get(i), children.get(j))) {
+ toRemove.add(i-toRemove.size());
+ break;
+ }
+ }
+ }
+ }
+ // if all elements are superfluous wrt. another element, then we need
+ // to keep at least one
+ if(toRemove.size() == children.size()) {
+ return children.get(0);
+ } else {
+ // remove all elements according to remove list
+ for(int pos : toRemove) {
+ children.remove(pos);
+ }
+ // dissolve intersection with only one element
+ if(children.size()==1) {
+ return children.get(0);
+ }
+ return description;
+ }
+ } else {
+ throw new Error("Cannot minimize description " + description + ".");
+ }
+ }
+
+ private boolean isSubclassOf(Description d1, Description d2) {
+ // check whether we have cached this query
+ Map<Description,Boolean> tmp = cachedSubclassOf.get(d1);
+ Boolean tmp2 = null;
+ if(tmp != null)
+ tmp2 = tmp.get(d2);
+
+ if(tmp2==null) {
+ Boolean result = reasoner.isSuperClassOf(d2, d1);
+
+ // create new entry if necessary
+ Map<Description,Boolean> map1 = new TreeMap<Description,Boolean>(conceptComparator);
+ if(tmp == null)
+ cachedSubclassOf.put(d1, map1);
+
+ cachedSubclassOf.get(d1).put(d2, result);
+ return result;
+ } else {
+ return tmp2;
+ }
+ }
+}
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
