1 | package tuffy.ground; |
2 | |
3 | import java.util.ArrayList; |
4 | import java.util.HashMap; |
5 | import java.util.HashSet; |
6 | import java.util.Hashtable; |
7 | import java.util.Iterator; |
8 | |
9 | |
10 | import tuffy.mln.Atom; |
11 | import tuffy.mln.Clause; |
12 | import tuffy.mln.Literal; |
13 | import tuffy.mln.MarkovLogicNetwork; |
14 | import tuffy.mln.Predicate; |
15 | import tuffy.mln.Term; |
16 | import tuffy.mln.Tuple; |
17 | import tuffy.util.UIMan; |
18 | |
19 | /** |
20 | * "Syntactic" Knowledge Base Model Constructor. |
21 | * Analyze the query and the MLN rules to identify |
22 | * relevant atoms that need to be grounded to answer the query. |
23 | * Here KBMC only |
24 | * materialize relevant portion of predicate tables, while further refinement |
25 | * of active set of predicates and grounding |
26 | * of clauses are left to class {@link Grounding}. |
27 | */ |
28 | public class KBMC { |
29 | /** |
30 | * MLN used in this KBMC. |
31 | */ |
32 | private MarkovLogicNetwork mln; |
33 | |
34 | /** |
35 | * Constructor of KBMC. |
36 | * @param mln MLN used in this KBMC. |
37 | */ |
38 | public KBMC(MarkovLogicNetwork mln){ |
39 | this.mln = mln; |
40 | } |
41 | |
42 | public HashSet<Clause> allowedClauses = null; |
43 | |
44 | /** |
45 | * Run KBMC to identify and materialize relevant groundings of predicates. |
46 | * |
47 | * Here the relevant atoms needed to be grounded is determined as |
48 | * follows. One atom may be potentially relevant if it is in a clause $c$ |
49 | * that contains a literal $a$ that has the same predicate as another |
50 | * potentially relevant tuple $b$. If $a$ and this predicate $b$ |
51 | * has MGU $m$, substituting this atom with $m$ will obtain tuple that |
52 | * is potentially relevant. Recursively do this until no potentially |
53 | * relevant tuples are generated according current set of potentially |
54 | * relevant tuples. Here $m$'s role is providing restrictions on possible |
55 | * groundings. |
56 | * |
57 | * Only ground a set of tuples, s.t., 1) $\forall$ tuple $a$, $b$ in this |
58 | * set, $a$ does not subsume $b$; and 2) $\forall$ tuple $c$ that is |
59 | * potentially relevant, there exists tuple $a$ in this set, that $a$ |
60 | * subsumes $c$. |
61 | * |
62 | * Note that, grounding both $a$ and $b$ when $a$ subsumes $b$ is not |
63 | * necessary, because the grounding results of $a$ will include $b$. |
64 | * |
65 | */ |
66 | public void run() { |
67 | // atoms to be explored |
68 | Hashtable<Predicate, AtomCutSet> toExp = new |
69 | Hashtable<Predicate, AtomCutSet>(); |
70 | // atoms deemed relevant |
71 | Hashtable<Predicate, AtomCutSet> relAtoms = new |
72 | Hashtable<Predicate, AtomCutSet>(); |
73 | UIMan.verbose(1, ">>> KBMC: Identifying relevant atoms/clauses..."); |
74 | // begin with queries |
75 | for(Predicate qp : mln.getAllPred()) { |
76 | AtomCutSet q = new AtomCutSet(qp); |
77 | if(qp.hasQuery()) { |
78 | for(Atom a : qp.getQueryAtoms()) { |
79 | q.addTuple(a.args); |
80 | //System.out.println(a); |
81 | } |
82 | } |
83 | toExp.put(qp, q); |
84 | |
85 | relAtoms.put(qp, new AtomCutSet(qp)); |
86 | } |
87 | bigloop: |
88 | while(true) { |
89 | // pick next seed |
90 | Predicate pred = null; |
91 | Tuple seed = null; |
92 | for(AtomCutSet aset : toExp.values()) { |
93 | seed = aset.top(); |
94 | if(seed != null) { |
95 | pred = aset.pred; |
96 | break; |
97 | } |
98 | } |
99 | // check if seeds have been exhausted |
100 | if(seed == null) break; |
101 | //System.out.println("SEED - " + pred.getName() + seed); |
102 | |
103 | // search |
104 | for(Clause c : pred.getRelatedClauses()) { |
105 | |
106 | if(allowedClauses != null && !allowedClauses.contains(c)){ |
107 | continue; |
108 | } |
109 | |
110 | //System.out.println("CLAUSE - " + c); |
111 | mln.setClauseAsRelevant(c); |
112 | for(Literal lit : c.getLiteralsOfPredicate(pred)) { |
113 | if(lit.isBuiltIn()) continue; |
114 | // calc mgu |
115 | HashMap<String, Term> vmap = lit.mostGeneralUnification(seed); |
116 | if(vmap == null) continue; |
117 | // apply to other literals |
118 | for(Literal ol : c.getRegLiterals()) { |
119 | if(ol.isBuiltIn()) continue; |
120 | if(ol.equals(lit)) continue; |
121 | Literal sol = ol.substitute(vmap); |
122 | Tuple newa = sol.toTuple(); |
123 | Predicate newp = sol.getPred(); |
124 | if(newp.noNeedToGround()) continue; |
125 | if(toExp.get(newp).subsumes(newa) || |
126 | relAtoms.get(newp).subsumes(newa)) { |
127 | continue; |
128 | } |
129 | //System.out.println("GOT " + newp.name + newa); |
130 | toExp.get(newp).addTuple(newa); |
131 | // short cut |
132 | if(newp.equals(pred) && !toExp.get(pred).contains(seed)) { |
133 | continue bigloop; |
134 | } |
135 | } |
136 | |
137 | } |
138 | } |
139 | toExp.get(pred).removeTuple(seed); |
140 | relAtoms.get(pred).addTuple(seed); |
141 | } |
142 | // fill up tables |
143 | UIMan.verbose(1, ">>> KBMC: Materializing predicates..."); |
144 | for(AtomCutSet as : relAtoms.values()) { |
145 | Predicate p = as.pred; |
146 | |
147 | if(mln.isScoped(p) || p.noNeedToGround()) continue; |
148 | boolean suc = as.collectAll(); |
149 | if(suc) { |
150 | for(Tuple t : as.heap) { |
151 | Atom a = new Atom(p, t); |
152 | if(a.pred.isClosedWorld()){ |
153 | a.truth = false; |
154 | a.type = Atom.AtomType.EVIDENCE; |
155 | } |
156 | UIMan.verbose(1, " " + a.toString() + " - " + UIMan.comma(a.groundSize()) + " tuples"); |
157 | p.groundAndStoreAtom(a); |
158 | } |
159 | } |
160 | } |
161 | } |
162 | |
163 | /** |
164 | * AtomCutSet is set of atoms with the same predicate. |
165 | * These atoms are organized in strata, with each stratum |
166 | * responds to a different degree-of-freedom. Atoms in a AtomCutSet |
167 | * satisfy that $\forall$ atom $a$ in this set, there does not exist atom $b$ |
168 | * in this set that $a$ subsumes $b$. For the definition of ``subsume'', see |
169 | * {@link Tuple#subsumes(Tuple)}. |
170 | * |
171 | */ |
172 | private static class AtomCutSet { |
173 | /** |
174 | * Predicate of this AtomCutSet. |
175 | */ |
176 | Predicate pred; |
177 | |
178 | /** |
179 | * Arity of {@link AtomCutSet#pred}. |
180 | */ |
181 | int arity; |
182 | |
183 | /** |
184 | * Whether this AtomCutSet is complete. Here by ``complete'' |
185 | * it means arbitrary tuple is subsumed by some tuples in this |
186 | * AtomCutSet. For the definition of ``subsume'', see |
187 | * {@link Tuple#subsumes(Tuple)}. |
188 | */ |
189 | boolean complete = false; |
190 | |
191 | /** |
192 | * List of stratum in this AtomCutSet. |
193 | */ |
194 | ArrayList<Stratum> strata = new ArrayList<Stratum>(); |
195 | |
196 | /** |
197 | * Set of all tuples in each stratum. |
198 | */ |
199 | HashSet<Tuple> heap = new HashSet<Tuple>(); |
200 | |
201 | /** |
202 | * Copy all tuples in each stratum to {@link AtomCutSet#heap}. |
203 | * @return true if some of this stratum is not empty. |
204 | */ |
205 | public boolean collectAll() { |
206 | for(Stratum s : strata) { |
207 | heap.addAll(s.tuples); |
208 | } |
209 | return (!heap.isEmpty()); |
210 | } |
211 | |
212 | /** |
213 | * Constructor of AtomCutSet. Given a predicate, |
214 | * initialize a stratum for each number between |
215 | * 0 and this predicate's arity. Each stratum |
216 | * for number $n$ means tuples in this stratum |
217 | * have degree-of-freedom $n$. |
218 | * @param p |
219 | */ |
220 | public AtomCutSet(Predicate p) { |
221 | pred = p; |
222 | arity = p.arity(); |
223 | for(int i=0; i<=p.arity(); i++) { |
224 | strata.add(new Stratum()); |
225 | } |
226 | } |
227 | |
228 | /** |
229 | * Returns the first tuple in the first stratum. |
230 | */ |
231 | public Tuple top() { |
232 | for(int i=arity; i>=0; i--) { |
233 | Stratum s = strata.get(i); |
234 | if(!s.isEmpty()) { |
235 | return s.tuples.iterator().next(); |
236 | } |
237 | } |
238 | return null; |
239 | } |
240 | |
241 | /** |
242 | * Remove the input tuple from corresponding stratum. Here |
243 | * the corresponding stratum is found by the degree-of-freedom |
244 | * of the input tuple. |
245 | * @param t input tuple. |
246 | */ |
247 | public void removeTuple(Tuple t) { |
248 | strata.get(t.dimension).tuples.remove(t); |
249 | } |
250 | |
251 | /** |
252 | * Return true if the input tuple is in the corresponding stratum. |
253 | * Here the corresponding stratum is found by the degree-of-freedom |
254 | * of input tuple. |
255 | * @param t input tuple. |
256 | */ |
257 | public boolean contains(Tuple t) { |
258 | return strata.get(t.dimension).tuples.contains(t); |
259 | } |
260 | |
261 | |
262 | /** |
263 | * Returns true if there exists a tuple in this AtomCutSet |
264 | * that subsumes the input tuple. For the definition of ``subsume'', see |
265 | * {@link Tuple#subsumes(Tuple)}. |
266 | * @param t input tuple. |
267 | */ |
268 | public boolean subsumes(Tuple t) { |
269 | int dim = t.dimension; |
270 | if(complete) return true; |
271 | if(dim == arity) { |
272 | return false; |
273 | } |
274 | for(int i=arity; i>= dim; i--) { |
275 | if(strata.get(i).subsumes(t)) return true; |
276 | } |
277 | return false; |
278 | } |
279 | |
280 | /** |
281 | * Add a tuple to corresponding stratum. Remove all the |
282 | * existing tuples that can be subsumed by the new input |
283 | * tuple. The goal is $\forall$ tuples $a$ and $b$ in |
284 | * a certain stratum, $a$ does not subsume $b$. This function |
285 | * pluses a condition in {@link KBMC#run()} ensure this. |
286 | * |
287 | * @param t input tuple |
288 | */ |
289 | public void addTuple(Tuple t) { |
290 | int dim = t.dimension; |
291 | if(dim == arity) { |
292 | for(Stratum s : strata) { |
293 | s.clear(); |
294 | } |
295 | strata.get(dim).add(t); |
296 | complete = true; |
297 | return ; |
298 | } |
299 | strata.get(dim).add(t); |
300 | for(int i=dim-1; i>=0; i--) { |
301 | strata.get(i).removeTuplesSubsumedBy(t); |
302 | } |
303 | } |
304 | |
305 | /** |
306 | * A stratum is a set of tuples with the same degree-of-freedom. |
307 | */ |
308 | class Stratum{ |
309 | /** |
310 | * Set of tuples in this stratum. |
311 | */ |
312 | HashSet<Tuple> tuples = new HashSet<Tuple>(); |
313 | |
314 | /** |
315 | * Add a tuple to this stratum. |
316 | * @param t Added tuple. |
317 | */ |
318 | public void add(Tuple t) { |
319 | tuples.add(t); |
320 | } |
321 | |
322 | /** |
323 | * Test whether there is a tuple in this stratum |
324 | * subsumes the input tuple. For the definition of |
325 | * ``subsume'', see {@link Tuple#subsumes(Tuple)}. |
326 | * @param t tuple to be tested. |
327 | * @return true if there is a tuple subsumes the input tuple. |
328 | */ |
329 | public boolean subsumes(Tuple t) { |
330 | for(Tuple at : tuples) { |
331 | if(at.subsumes(t)) return true; |
332 | } |
333 | return false; |
334 | } |
335 | |
336 | /** |
337 | * Remove tuples in this stratum that subsumes the input tuple. |
338 | * |
339 | * @param t input tuple. |
340 | * @see Stratum#subsumes(Tuple). |
341 | */ |
342 | public void removeTuplesSubsumedBy(Tuple t) { |
343 | for(Iterator<Tuple> it = tuples.iterator(); it.hasNext();) { |
344 | if(t.subsumes(it.next())) { |
345 | it.remove(); |
346 | } |
347 | } |
348 | } |
349 | |
350 | /** |
351 | * Return true if this stratum is empty. |
352 | */ |
353 | public boolean isEmpty() { |
354 | return tuples.isEmpty(); |
355 | } |
356 | |
357 | /** |
358 | * Empty this stratum. |
359 | */ |
360 | public void clear() { |
361 | tuples.clear(); |
362 | } |
363 | } |
364 | } |
365 | |
366 | } |