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.reasoning;
021
022 import java.util.Map;
023 import java.util.SortedSet;
024 import java.util.TreeSet;
025
026 import org.dllearner.core.owl.ObjectAllRestriction;
027 import org.dllearner.core.owl.NamedClass;
028 import org.dllearner.core.owl.Nothing;
029 import org.dllearner.core.owl.Description;
030 import org.dllearner.core.owl.ObjectSomeRestriction;
031 import org.dllearner.core.owl.FlatABox;
032 import org.dllearner.core.owl.Intersection;
033 import org.dllearner.core.owl.Union;
034 import org.dllearner.core.owl.Negation;
035 import org.dllearner.core.owl.Thing;
036 import org.dllearner.utilities.Helper;
037 import org.dllearner.utilities.datastructures.SortedSetTuple;
038
039 public class FastRetrieval {
040
041 private FlatABox abox;
042
043 public FastRetrieval(FlatABox abox) {
044 this.abox = abox;
045 }
046
047 public SortedSetTuple<String> calculateSets(Description concept) {
048 return calculateSetsADC(concept, null);
049 }
050
051 // Algorithmus wird ueber Rekursion und
052 // Delegation zur Helper-Klasse implementiert
053 public SortedSetTuple<String> calculateSetsADC(Description concept, SortedSetTuple<String> adcSet) {
054 if(concept instanceof Thing) {
055 return new SortedSetTuple<String>(abox.top,abox.bottom);
056 } else if(concept instanceof Nothing) {
057 return new SortedSetTuple<String>(abox.bottom,abox.top);
058 } else if(concept instanceof NamedClass) {
059 SortedSet<String> pos = abox.getPositiveInstances(((NamedClass)concept).getName());
060 SortedSet<String> neg = abox.getNegativeInstances(((NamedClass)concept).getName());
061 return new SortedSetTuple<String>(pos,neg);
062 } else if(concept instanceof Negation) {
063 return calculateNegationSet(calculateSetsADC(concept.getChild(0), adcSet));
064 } else if(concept instanceof Intersection) {
065 // this should never happen, but it does; we work around the issue
066 if(concept.getChildren().size()==1)
067 return calculateSetsADC(concept.getChild(0),adcSet);
068 SortedSetTuple<String> res =
069 calculateConjunctionSets(calculateSetsADC(concept.getChild(0),adcSet),calculateSetsADC(concept.getChild(1),adcSet));
070 for(int i=2; i < concept.getChildren().size(); i++) {
071 res = calculateConjunctionSets(res,calculateSetsADC(concept.getChild(i),adcSet));
072 }
073 return res;
074 } else if(concept instanceof Union) {
075 // this should never happen, but it does; we work around the issue
076 if(concept.getChildren().size()==1)
077 return calculateSetsADC(concept.getChild(0),adcSet);
078
079 SortedSetTuple<String> res =
080 calculateDisjunctionSets(calculateSetsADC(concept.getChild(0),adcSet),calculateSetsADC(concept.getChild(1),adcSet));
081 for(int i=2; i < concept.getChildren().size(); i++) {
082 res = calculateDisjunctionSets(res,calculateSetsADC(concept.getChild(i),adcSet));
083 }
084 return res;
085 } else if(concept instanceof ObjectAllRestriction) {
086 return calculateAllSet(abox,((ObjectAllRestriction)concept).getRole().getName(),calculateSetsADC(concept.getChild(0),adcSet));
087 } else if(concept instanceof ObjectSomeRestriction) {
088 return calculateExistsSet(abox,((ObjectSomeRestriction)concept).getRole().getName(),calculateSetsADC(concept.getChild(0),adcSet));
089 }
090
091 throw new Error("Unknown concept type " + concept);
092 }
093
094
095 public static SortedSetTuple<String> calculateConjunctionSets(SortedSetTuple<String> child1, SortedSetTuple<String> child2) {
096 return new SortedSetTuple<String>(
097 Helper.intersection(child1.getPosSet(),child2.getPosSet()),
098 Helper.union(child1.getNegSet(),child2.getNegSet()));
099 }
100
101 public static SortedSetTuple<String> calculateDisjunctionSets(SortedSetTuple<String> child1, SortedSetTuple<String> child2) {
102 return new SortedSetTuple<String>(
103 Helper.union(child1.getPosSet(),child2.getPosSet()),
104 Helper.intersection(child1.getNegSet(),child2.getNegSet()));
105 }
106
107 public static SortedSetTuple<String> calculateNegationSet(SortedSetTuple<String> child) {
108 return new SortedSetTuple<String>(child.getNegSet(),child.getPosSet());
109 }
110
111 public static SortedSetTuple<String> calculateExistsSet(FlatABox abox, String roleName, SortedSetTuple<String> child) {
112 // FlatABox abox = FlatABox.getInstance();
113
114 // zu beschreibende Mengen
115 SortedSet<String> posSet = new TreeSet<String>();
116 SortedSet<String> negSet = new TreeSet<String>();
117
118 // Daten zu R+
119 Map<String, SortedSet<String>> rplus = abox.rolesPos.get(roleName);
120 Map<String, SortedSet<String>> rminus = abox.rolesNeg.get(roleName);
121
122 // es wird r(a,b) untersucht und sobald ein b mit b \in C+ gefunden
123 // wird, wird a in posSet aufgenommen
124
125 if(rplus!=null) {
126 for (String a : rplus.keySet()) {
127 if (rplus.containsKey(a) && checkExist(rplus.get(a), child.getPosSet()))
128 posSet.add(a);
129 }
130 }
131
132 // ich muss über die ganze Domain gehen: selbst wenn für ein a gar kein
133 // (a,b) in R- existiert, dann kann so ein a trotzdem die Bedingung erfüllen
134 if(rminus==null) {
135 if(child.getNegSet().equals(abox.domain))
136 negSet = abox.domain;
137 } else {
138 for (String a : abox.domain) {
139 if(!rminus.containsKey(a)) {
140 if(child.getNegSet().equals(abox.domain))
141 negSet.add(a);
142 } else
143 if (checkAll(Helper.difference(abox.domain, rminus.get(a)), child.getNegSet()))
144 negSet.add(a);
145 }
146 }
147
148 return new SortedSetTuple<String>(posSet,negSet);
149 }
150
151 public static SortedSetTuple<String> calculateAllSet(FlatABox abox, String roleName, SortedSetTuple<String> child) {
152 // FlatABox abox = FlatABox.getInstance();
153
154 // zu beschreibende Mengen
155 SortedSet<String> posSet = new TreeSet<String>();
156 SortedSet<String> negSet = new TreeSet<String>();
157
158 // Daten zu R+ und R-
159 Map<String, SortedSet<String>> rplus = abox.rolesPos.get(roleName);
160 Map<String, SortedSet<String>> rminus = abox.rolesNeg.get(roleName);
161
162 // Fallunterscheidungen einbauen, da R+ und R- leer sein können
163 // und es nicht für jedes a der Domain ein (a,b) \in R+ bzw. R- geben muss;
164 // man beachte, dass viele Regeln nur gelten, weil als Domain die Menge aller
165 // Individuen angenommen wird!
166
167 // R- ist leer
168 if(rminus==null) {
169 // falls C die ganze Domain umfasst, dann erüllt jedes Individual
170 // All R.C, ansonsten keines (es muss nichts gemacht werden)
171 if(child.getPosSet().equals(abox.domain))
172 // keine Kopie notwendig, da Domain unveränderlich
173 posSet = abox.domain;
174 } else {
175 for (String a : abox.domain) {
176 if(!rminus.containsKey(a)) {
177 // a erfüllt die Bedingung, falls alle b in C+ sind
178 if(child.getPosSet().equals(abox.domain))
179 posSet.add(a);
180 }
181 else if (checkAll(Helper.difference(abox.domain, rminus.get(a)), child.getPosSet()))
182 posSet.add(a);
183 }
184 }
185
186 // falls R+ leer ist, dann ist Bedingung nie erfüllt
187 if(rplus!=null) {
188 for (String a : rplus.keySet()) {
189 // falls R+ Schlüssel nicht enthält, ist Bedingung nicht erfüllt
190 if (rplus.containsKey(a) && checkExist(rplus.get(a), child.getNegSet()))
191 negSet.add(a);
192 }
193 }
194
195 return new SortedSetTuple<String>(posSet,negSet);
196 }
197
198 // gibt true zurueck, falls es ein b gibt mit b \in s1 und b \in s2,
199 // ansonsten false
200 private static boolean checkExist(SortedSet<String> s1, SortedSet<String> s2) {
201 for (String b : s1) {
202 if (s2.contains(b))
203 return true;
204 }
205 return false;
206 }
207
208 // gibt false zurueck, falls fuer ein b \in s1 gilt b \in s2,
209 // ansonsten true
210 private static boolean checkAll(SortedSet<String> s1, SortedSet<String> s2) {
211 for (String b : s1) {
212 if (!s2.contains(b))
213 return false;
214 }
215 return true;
216 }
217
218 public FlatABox getAbox() {
219 return abox;
220 }
221 }