001 /**
002 * Copyright (C) 2007-2011, Jens Lehmann
003 *
004 * This file is part of DL-Learner.
005 *
006 * DL-Learner is free software; you can redistribute it and/or modify
007 * it under the terms of the GNU General Public License as published by
008 * the Free Software Foundation; either version 3 of the License, or
009 * (at your option) any later version.
010 *
011 * DL-Learner 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
014 * GNU General Public License for more details.
015 *
016 * You should have received a copy of the GNU General Public License
017 * along with this program. If not, see <http://www.gnu.org/licenses/>.
018 */
019
020 package org.dllearner.utilities.owl;
021
022 import java.util.List;
023 import java.util.Map;
024 import java.util.TreeMap;
025
026 import org.dllearner.core.AbstractReasonerComponent;
027 import org.dllearner.core.owl.Description;
028 import org.dllearner.core.owl.Intersection;
029 import org.dllearner.core.owl.Negation;
030 import org.dllearner.core.owl.Nothing;
031 import org.dllearner.core.owl.ObjectAllRestriction;
032 import org.dllearner.core.owl.ObjectMaxCardinalityRestriction;
033 import org.dllearner.core.owl.ObjectMinCardinalityRestriction;
034 import org.dllearner.core.owl.ObjectProperty;
035 import org.dllearner.core.owl.ObjectSomeRestriction;
036 import org.dllearner.core.owl.Thing;
037 import org.dllearner.core.owl.Union;
038
039 /**
040 * Rewrites a description to an equivalent shorter description. Note that
041 * minimizing is not a trivial operation and requires reasoning. The class
042 * keeps an internal cache on reasoning results, i.e. if similar descriptions
043 * are passed to the minimizer, then its performance will improve over time.
044 *
045 * @author Jens Lehmann
046 *
047 */
048 public class DescriptionMinimizer {
049
050 private AbstractReasonerComponent reasoner;
051 private ConceptComparator conceptComparator = new ConceptComparator();
052 private Map<Description,Map<Description,Boolean>> cachedSubclassOf = new TreeMap<Description,Map<Description,Boolean>>(conceptComparator);
053
054 private boolean beautify = true;
055
056 public DescriptionMinimizer(AbstractReasonerComponent reasoner) {
057 this.reasoner = reasoner;
058 }
059
060 /**
061 * Method which minimzes the input description. The algorithm does not
062 * replace subdescriptions with named classes, e.g.
063 * if the description "male \sqcap \exists hasChild.\top" is passed to the
064 * algorithm and a class "father" is defined in the obvious way
065 * in the background knowledge, then
066 * it will intentionally not return father. Instead, it preserves the
067 * existing structure of the description, but tries to detect and delete
068 * redundant parts within it. For instance, the description "male \sqcap
069 * father" is minimized to "father".
070 *
071 * @param description The description to minimize.
072 * @return Minimized description.
073 */
074 public Description minimizeClone(Description description) {
075 Description descriptionToMinimize = description.clone();
076 return minimize(descriptionToMinimize);
077 }
078
079 /**
080 * Same as {@link #minimizeClone(Description)}, but with no guarantee that
081 * the input description remains unmodified.
082 * @see #minimizeClone(Description)
083 * @param description The description to minimize.
084 * @return Minimized description.
085 */
086 public Description minimize(Description description) {
087 // minimize all children of the description
088 List<Description> children = description.getChildren();
089 for(int i=0; i<children.size(); i++) {
090 description.replaceChild(i, minimize(children.get(i)));
091 }
092 // make a case distinction based on the structure of the description
093 // (note that we do not have to do anything for a number of cases:
094 // a named class, Thing, Nothing, hasValue restrictions, boolean
095 // value restrictions, double value restrictions)
096 if(children.size()==0) {
097 return description;
098 } else if(description instanceof ObjectSomeRestriction) {
099 // \exists r.\bot \equiv \bot
100 if(description.getChild(0) instanceof Nothing) {
101 return Nothing.instance;
102 }
103 return description;
104 } else if(description instanceof ObjectAllRestriction) {
105 // \forall r.\top \equiv \top
106 if(description.getChild(0) instanceof Thing) {
107 return Thing.instance;
108 }
109 // we rewrite \forall r.\bot to \neg \exists r.\top
110 // which is longer but easier to understand for humans
111 if(beautify && description.getChild(0) instanceof Nothing) {
112 ObjectProperty p = (ObjectProperty)((ObjectAllRestriction)description).getRole();
113 return new Negation(new ObjectSomeRestriction(p, Thing.instance));
114 }
115 return description;
116 } else if(description instanceof Negation) {
117 // \neg \bot \equiv \top
118 if(description.getChild(0) instanceof Nothing) {
119 return Thing.instance;
120 // \neg \top \equiv \bot
121 } else if(description.getChild(0) instanceof Thing) {
122 return Nothing.instance;
123 }
124 return description;
125 } else if(description instanceof ObjectMaxCardinalityRestriction) {
126 // <= n r.\bot \equiv \top
127 if(description.getChild(0) instanceof Nothing) {
128 return Thing.instance;
129 }
130 // we rewrite <= 0 r C to \neg \exists r C - easier to read for humans
131 if(((ObjectMaxCardinalityRestriction)description).getCardinality() == 0) {
132 ObjectProperty p = (ObjectProperty)((ObjectMaxCardinalityRestriction)description).getRole();
133 return new Negation(new ObjectSomeRestriction(p, description.getChild(0)));
134 }
135 return description;
136 } else if(description instanceof ObjectMinCardinalityRestriction) {
137 // >= 0 r.C \equiv \top
138 int number = ((ObjectMinCardinalityRestriction)description).getNumber();
139 if(number == 0) {
140 return Thing.instance;
141 }
142 // >= n r.\bot \equiv \bot if n != 0
143 if(description.getChild(0) instanceof Nothing) {
144 return Nothing.instance;
145 }
146 return description;
147 } else if(description instanceof Intersection || description instanceof Union) {
148
149 if(description instanceof Intersection) {
150 for(int i=0; i<children.size(); i++) {
151 for(int j=0; j<children.size(); j++) {
152 if(i != j && isSubclassOf(children.get(j), children.get(i))) {
153 // remove element because it is super class of another element
154 children.remove(i);
155 // we apply the minimization procedure again after removal of the element
156 // (this is not the fastest implementation but avoids bugs as in the previous code)
157 if(children.size()==1) {
158 return minimize(children.get(0));
159 } else {
160 return minimize(description);
161 }
162 }
163 }
164 }
165 } else {
166 for(int i=0; i<children.size(); i++) {
167 for(int j=0; j<children.size(); j++) {
168 if(i != j && isSubclassOf(children.get(i), children.get(j))) {
169 children.remove(i);
170 if(children.size()==1) {
171 return minimize(children.get(0));
172 } else {
173 return minimize(description);
174 }
175 }
176 }
177 }
178 }
179
180 // no subclass relationships => description is already minimal
181 return description;
182
183 // the code below is buggy because in "A AND A AND C", it removes both As
184
185 // List<Integer> toRemove = new LinkedList<Integer>();
186 // // intersection
187 // if(description instanceof Intersection) {
188 // // in an intersection, we have that D1 \sqcap D2 \equiv D1 if
189 // // D1 \sqsubseteq D2; this means we first check whether the
190 // // first element in an intersection is subclass of any other element in the
191 // // intersection; if yes, then we delete it and proceed to the next element
192 // for(int i=0; i<children.size(); i++) {
193 // for(int j=0; j<children.size(); j++) {
194 // if(i!=j)
195 // System.out.println(children.get(i) + " -- " + children.get(j));
196 // if(i != j && isSubclassOf(children.get(j), children.get(i))) {
197 // System.out.println("sub");
198 // toRemove.add(i-toRemove.size());
199 // break;
200 // }
201 // }
202 // }
203 // // union
204 // } else {
205 // // in a union, we have that D1 \sqcup D2 \equiv D2 if
206 // // D1 \sqsubseteq D2; this means we first check whether the
207 // // first element in a union is subclass of any other element in the
208 // // union; if yes, then we delete it and proceed to the next element
209 // // (note the difference to intersection)
210 // for(int i=0; i<children.size(); i++) {
211 // for(int j=0; j<children.size(); j++) {
212 // if(i != j && isSubclassOf(children.get(i), children.get(j))) {
213 // toRemove.add(i-toRemove.size());
214 // break;
215 // }
216 // }
217 // }
218 // }
219 //
220 // System.out.println("to remove: " + toRemove);
221 //
222 // // if all elements are superfluous wrt. another element, then we need
223 // // to keep at least one
224 // if(toRemove.size() == children.size()) {
225 // return children.get(0);
226 // } else {
227 // // remove all elements according to remove list
228 // for(int pos : toRemove) {
229 // children.remove(pos);
230 // }
231 // // dissolve intersection with only one element
232 // if(children.size()==1) {
233 // return children.get(0);
234 // }
235 // return description;
236 // }
237 } else {
238 throw new Error("Cannot minimize description " + description + ".");
239 }
240 }
241
242 private boolean isSubclassOf(Description d1, Description d2) {
243 // check whether we have cached this query
244 Map<Description,Boolean> tmp = cachedSubclassOf.get(d1);
245 Boolean tmp2 = null;
246 if(tmp != null)
247 tmp2 = tmp.get(d2);
248
249 if(tmp2==null) {
250 Boolean result = reasoner.isSuperClassOf(d2, d1);
251
252 // create new entry if necessary
253 Map<Description,Boolean> map1 = new TreeMap<Description,Boolean>(conceptComparator);
254 if(tmp == null)
255 cachedSubclassOf.put(d1, map1);
256
257 cachedSubclassOf.get(d1).put(d2, result);
258 return result;
259 } else {
260 return tmp2;
261 }
262 }
263 }