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.refinementoperators;
021
022 import java.util.Map;
023 import java.util.Set;
024 import java.util.SortedSet;
025 import java.util.TreeMap;
026 import java.util.TreeSet;
027
028 import org.dllearner.core.AbstractReasonerComponent;
029 import org.dllearner.core.owl.Description;
030 import org.dllearner.core.owl.Individual;
031 import org.dllearner.core.owl.Intersection;
032 import org.dllearner.core.owl.NamedClass;
033 import org.dllearner.core.owl.Negation;
034 import org.dllearner.core.owl.Nothing;
035 import org.dllearner.core.owl.ObjectProperty;
036 import org.dllearner.core.owl.ClassHierarchy;
037 import org.dllearner.core.owl.Thing;
038 import org.dllearner.utilities.Helper;
039 import org.dllearner.utilities.owl.ConceptComparator;
040
041 import com.jamonapi.Monitor;
042 import com.jamonapi.MonitorFactory;
043
044 /**
045 * Utility methods for constructing refinement operators.
046 *
047 * @author Jens Lehmann
048 *
049 */
050 public final class Utility {
051
052 private AbstractReasonerComponent reasoner;
053 ClassHierarchy sh;
054 private Map<ObjectProperty,Description> opDomains;
055
056 // concept comparator
057 private ConceptComparator conceptComparator = new ConceptComparator();
058
059 // specifies whether to do real disjoint tests or check that
060 // two named classes do not have common instances
061 private boolean instanceBasedDisjoints = true;
062
063 // cache for reasoner queries
064 private Map<Description,Map<Description,Boolean>> cachedDisjoints = new TreeMap<Description,Map<Description,Boolean>>(conceptComparator);
065
066 // cache for applicaple object properties
067 private Map<Description, SortedSet<ObjectProperty>> appOPCache = new TreeMap<Description, SortedSet<ObjectProperty>>(conceptComparator);
068
069 public Utility(AbstractReasonerComponent rs) {
070 throw new Error("not implemented yet");
071 }
072
073 public Utility(AbstractReasonerComponent rs, Map<ObjectProperty,Description> opDomains, boolean instanceBasedDisjoints) {
074 this.reasoner = rs;
075 sh = rs.getClassHierarchy();
076 // we cache object property domains
077 this.opDomains = opDomains;
078 this.instanceBasedDisjoints = instanceBasedDisjoints;
079 }
080
081 /**
082 * Compute the set of applicable object properties for a
083 * given description.
084 *
085 * @param index The index is a description which determines
086 * which of the properties are applicable. Exactly those which
087 * where the index and property domain are not disjoint are
088 * applicable, where disjoint is defined by {@link #isDisjoint(Description, Description)}.
089 *
090 */
091 public SortedSet<ObjectProperty> computeApplicableObjectProperties(Description index) {
092 // use a cache, because large ontologies can have many object properties
093 SortedSet<ObjectProperty> applicableObjectProperties = appOPCache.get(index);
094 if(applicableObjectProperties == null) {
095 Set<ObjectProperty> objectProperties = reasoner.getObjectProperties();
096 applicableObjectProperties = new TreeSet<ObjectProperty>();
097 for(ObjectProperty op : objectProperties) {
098 Description domain = opDomains.get(op);
099 if(!isDisjoint(index,domain)) {
100 applicableObjectProperties.add(op);
101 }
102 }
103 appOPCache.put(index, applicableObjectProperties);
104 }
105 return applicableObjectProperties;
106 }
107
108 /**
109 * Given a set of applicable object properties, this method returns
110 * the most general ones, i.e. those where more general ones do not
111 * exist in the set of applicable properties. Due to the definition
112 * of "applicable", the returned set is just the intersection of the most
113 * general object properties and the applicable properties. (A non-applicable
114 * property cannot have applicable subproperties, because subproperties
115 * can only restrict, but not broaden their domain.)
116 *
117 * @param applicableObjectProperties The set of applicable properties.
118 * @return The most general applicable properties.
119 */
120 public SortedSet<ObjectProperty> computeMgr(SortedSet<ObjectProperty> applicableObjectProperties) {
121 return Helper.intersection(reasoner.getMostGeneralProperties(), applicableObjectProperties);
122 }
123
124 public Set<NamedClass> getClassCandidates(Description index, Set<NamedClass> existingClasses) {
125 return getClassCandidatesRecursive(index, existingClasses, Thing.instance);
126 }
127
128 private Set<NamedClass> getClassCandidatesRecursive(Description index, Set<NamedClass> existingClasses, Description upperClass) {
129 Set<NamedClass> candidates = new TreeSet<NamedClass>();
130
131 // we descend the subsumption hierarchy to ensure that we get
132 // the most general concepts satisfying the criteria
133 // there are 4 checks a class has to satisfy to get into the set;
134 // for 2 of them we can stop further traversal in the subsumption
135 // hierarchy
136 for(Description d : sh.getSubClasses(upperClass)) {
137 // System.out.println("d: " + d);
138 // owl:Nothing is never a candidate (not in EL)
139 if(!(d instanceof Nothing)) {
140 NamedClass candidate = (NamedClass) d;
141 // we first do those checks where we know that we do not
142 // need to traverse the subsumption hierarchy if they are
143 // not satisfied
144 // check1: disjointness with index
145 // check3: no superclass exists already
146 // check5: disjointness
147 if(!isDisjoint(candidate,index) && checkSubClasses(existingClasses,candidate) && checkDisjoints(existingClasses,candidate)) {
148 // check whether the class is meaningful, i.e. adds something to the index
149 // to do this, we need to make sure that the class is not a superclass of the
150 // index (otherwise we get nothing new)
151 if(!isDisjoint(new Negation(candidate),index) && checkSuperClasses(existingClasses,candidate)) {
152 // candidate went successfully through all checks
153 candidates.add(candidate);
154 } else {
155 // System.out.println("k32: " + candidate + " index " + index + " cond1 " + isDisjoint(new Negation(candidate),index) + " cond2 " + checkSuperClasses(existingClasses,candidate));
156 // descend subsumption hierarchy to find candidates
157 candidates.addAll(getClassCandidatesRecursive(index, existingClasses, candidate));
158 }
159 }
160 }
161 }
162 return candidates;
163 }
164
165 // returns true if the candidate is not subclass of an existing class,
166 // false otherwise (check 3)
167 private boolean checkSubClasses(Set<NamedClass> existingClasses, NamedClass candidate) {
168 for(NamedClass nc : existingClasses) {
169 // System.out.println("csc: " + nc + candidate);
170 if(sh.isSubclassOf(candidate, nc)) {
171 return false;
172 }
173 }
174 return true;
175 }
176
177 // returns true if the candidate is not superclass of an existing class,
178 // false otherwise (check 4)
179 private boolean checkSuperClasses(Set<NamedClass> existingClasses, NamedClass candidate) {
180 for(NamedClass nc : existingClasses) {
181 if(sh.isSubclassOf(nc, candidate))
182 return false;
183 }
184 return true;
185 }
186
187 // returns false if any of the classes is disjoint with the new one; true otherwise
188 private boolean checkDisjoints(Set<NamedClass> existingClasses, NamedClass candidate) {
189 for(NamedClass nc : existingClasses) {
190 if(isDisjoint(nc, candidate))
191 return false;
192 }
193 return true;
194 }
195
196
197 public boolean isDisjoint(Description d1, Description d2) {
198 // System.out.println("d1: " + d1);
199 // System.out.println("d2: " + d2);
200 // System.out.println("cache: " + cachedDisjoints);
201
202 // check whether we have cached this query
203 Map<Description,Boolean> tmp = cachedDisjoints.get(d1);
204 Boolean tmp2 = null;
205 if(tmp != null)
206 tmp2 = tmp.get(d2);
207
208 if(tmp2==null) {
209 Boolean result;
210 if(instanceBasedDisjoints) {
211 result = isDisjointInstanceBased(d1,d2);
212 } else {
213 Description d = new Intersection(d1, d2);
214 Monitor mon = MonitorFactory.start("disjointness reasoning");
215 result = reasoner.isSuperClassOf(new Nothing(), d);
216 mon.stop();
217 }
218 // add the result to the cache (we add it twice such that
219 // the order of access does not matter)
220
221 // create new entries if necessary
222 Map<Description,Boolean> map1 = new TreeMap<Description,Boolean>(conceptComparator);
223 Map<Description,Boolean> map2 = new TreeMap<Description,Boolean>(conceptComparator);
224 if(tmp == null)
225 cachedDisjoints.put(d1, map1);
226 if(!cachedDisjoints.containsKey(d2))
227 cachedDisjoints.put(d2, map2);
228
229 // add result symmetrically in the description matrix
230 cachedDisjoints.get(d1).put(d2, result);
231 cachedDisjoints.get(d2).put(d1, result);
232 return result;
233 } else {
234 return tmp2;
235 }
236 }
237
238 private boolean isDisjointInstanceBased(Description d1, Description d2) {
239 SortedSet<Individual> d1Instances = reasoner.getIndividuals(d1);
240 SortedSet<Individual> d2Instances = reasoner.getIndividuals(d2);
241 for(Individual d1Instance : d1Instances) {
242 if(d2Instances.contains(d1Instance))
243 return false;
244 }
245 return true;
246 }
247
248 }