KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > com > hp > hpl > jena > reasoner > rulesys > impl > LPRuleStore


1 /******************************************************************
2  * File: LPRuleStore.java
3  * Created by: Dave Reynolds
4  * Created on: 18-Jul-2003
5  *
6  * (c) Copyright 2003, 2004, 2005 Hewlett-Packard Development Company, LP
7  * [See end of file]
8  * $Id: LPRuleStore.java,v 1.4 2005/02/21 12:17:56 andy_seaborne Exp $
9  *****************************************************************/
10 package com.hp.hpl.jena.reasoner.rulesys.impl;
11
12 import com.hp.hpl.jena.reasoner.TriplePattern;
13 import com.hp.hpl.jena.reasoner.rulesys.*;
14 import com.hp.hpl.jena.graph.*;
15
16 import java.util.*;
17
18 /**
19  * Holds the set of backward rules used by an LPEngine. Is responsible
20  * for compile the rules into internal byte codes before use.
21  *
22  * @author <a HREF="mailto:der@hplb.hpl.hp.com">Dave Reynolds</a>
23  * @version $Revision: 1.4 $ on $Date: 2005/02/21 12:17:56 $
24  */
25 public class LPRuleStore extends RuleStore {
26     
27     /** Flag to indicate whether the rules have been compiled into code objects */
28     protected boolean isCompiled = false;
29     
30     /** A map from predicate to a list of RuleClauseCode objects for that predicate.
31      * Uses Node_RuleVariable.WILD for wildcard predicates.
32      */
33     protected Map predicateToCodeMap;
34     
35     /** The list of all RuleClauseCode objects, used to implement wildcard queries */
36     protected ArrayList allRuleClauseCodes;
37
38     /** Two level index map - index on predicate then on object */
39     protected Map indexPredicateToCodeMap;
40         
41     /** Set of predicates which should be tabled */
42     protected HashSet tabledPredicates = new HashSet();
43         
44     /** Threshold for number of rule entries in a predicate bucket before second level indexing kicks in */
45     private static final int INDEX_THRESHOLD = 20;
46     
47     /** True if all goals should be treated as tabled */
48     protected boolean allTabled = false;
49     
50     /**
51      * Construct a rule store containing the given rules.
52      * @param rules the rules to initialize the store with.
53      */
54     public LPRuleStore(List rules) {
55         super(rules);
56     }
57     
58     /**
59      * Construct an empty rule store
60      */
61     public LPRuleStore() {
62         super();
63     }
64     
65     /**
66      * Add all the rules and tabling instructions from an existing rulestore into this one.
67      */
68     public void addAll(LPRuleStore store) {
69         super.addAll(store);
70         tabledPredicates.addAll(store.tabledPredicates);
71         allTabled = tabledPredicates.contains(Node.ANY);
72     }
73     
74     /**
75      * Register an RDF predicate as one whose presence in a goal should force
76      * the goal to be tabled.
77      */
78     public synchronized void tablePredicate(Node predicate) {
79         tabledPredicates.add(predicate);
80         if (predicate == Node.ANY) allTabled = true;
81     }
82     
83     /**
84      * Return an ordered list of RuleClauseCode objects to implement the given
85      * predicate.
86      * @param predicate the predicate node or Node_RuleVariable.WILD for wildcards.
87      */
88     public List codeFor(Node predicate) {
89         if (!isCompiled) {
90             compileAll();
91         }
92         if (predicate.isVariable()) {
93             return allRuleClauseCodes;
94         } else {
95             List codeList = (List) predicateToCodeMap.get(predicate);
96             if (codeList == null) {
97                 // Uknown predicate, so only the wildcard rules apply
98 codeList = (List) predicateToCodeMap.get(Node_RuleVariable.WILD);
99             }
100             return codeList;
101         }
102     }
103     
104     /**
105      * Return an ordered list of RuleClauseCode objects to implement the given
106      * query pattern. This may use indexing to narrow the rule set more that the predicate-only case.
107      * @param goal the triple pattern that makes up the query
108      */
109     public List codeFor(TriplePattern goal) {
110         List allRules = codeFor(goal.getPredicate());
111         if (allRules == null) {
112             return allRules;
113         }
114         Map indexedCodeTable = (Map) indexPredicateToCodeMap.get(goal.getPredicate());
115         if (indexedCodeTable != null) {
116             List indexedCode = (List) indexedCodeTable.get(goal.getObject());
117             if (indexedCode != null) {
118                 return indexedCode;
119             }
120         }
121         return allRules;
122     }
123     
124     /**
125      * Return true if the given predicate is indexed.
126      */
127     public boolean isIndexedPredicate(Node predicate) {
128         return (indexPredicateToCodeMap.get(predicate) != null);
129     }
130     
131     /**
132      * Return true if the given goal is tabled, currently this is true if the
133      * predicate is a tabled predicate or the predicate is a wildcard and some
134      * tabled predictes exist.
135      */
136     public boolean isTabled(TriplePattern goal) {
137         return isTabled(goal.getPredicate());
138     }
139     
140     /**
141      * Return true if the given predicated is tabled, currently this is true if the
142      * predicate is a tabled predicate or the predicate is a wildcard and some
143      * tabled predictes exist.
144      */
145     public boolean isTabled(Node predicate) {
146         if (allTabled) return true;
147         if (predicate.isVariable() && !tabledPredicates.isEmpty()) {
148             return true;
149         } else {
150             return tabledPredicates.contains(predicate);
151         }
152     }
153     
154     /**
155      * Compile all the rules in a table. initially just indexed on predicate but want to
156      * add better indexing for the particular cases of wildcard rules and type rules.
157      */
158     protected void compileAll() {
159         isCompiled = true;
160         
161         predicateToCodeMap = new HashMap();
162         allRuleClauseCodes = new ArrayList();
163         indexPredicateToCodeMap = new HashMap();
164         for (Iterator ri = getAllRules().iterator(); ri.hasNext(); ) {
165             Rule r = (Rule)ri.next();
166             ClauseEntry term = r.getHeadElement(0);
167             if (term instanceof TriplePattern) {
168                 RuleClauseCode code = new RuleClauseCode(r);
169                 allRuleClauseCodes.add(code);
170                 Node predicate = ((TriplePattern)term).getPredicate();
171                 if (predicate.isVariable()) {
172                     predicate = Node_RuleVariable.WILD;
173                 }
174                 List predicateCode = (List)predicateToCodeMap.get(predicate);
175                 if (predicateCode == null) {
176                     predicateCode = new ArrayList();
177                     predicateToCodeMap.put(predicate, predicateCode);
178                 }
179                 predicateCode.add(code);
180                 if (predicateCode.size() > INDEX_THRESHOLD) {
181                     indexPredicateToCodeMap.put(predicate, new HashMap());
182                 }
183             }
184         }
185
186         // Now add the wild card rules into the list for each non-wild predicate)
187 List wildRules = (List) predicateToCodeMap.get(Node_RuleVariable.WILD);
188         if (wildRules != null) {
189             for (Iterator i = predicateToCodeMap.entrySet().iterator(); i.hasNext(); ) {
190                 Map.Entry entry = (Map.Entry)i.next();
191                 Node predicate = (Node)entry.getKey();
192                 List predicateCode = (List)entry.getValue();
193                 if (predicate != Node_RuleVariable.WILD) {
194                     predicateCode.addAll(wildRules);
195                 }
196             }
197         }
198         indexPredicateToCodeMap.put(Node_RuleVariable.WILD, new HashMap());
199                 
200         // Now built any required two level indices
201 for (Iterator i = indexPredicateToCodeMap.entrySet().iterator(); i.hasNext(); ) {
202             Map.Entry entry = (Map.Entry)i.next();
203             Node predicate = (Node) entry.getKey();
204             HashMap predicateMap = (HashMap) entry.getValue();
205             List wildRulesForPredicate = new ArrayList();
206             List allRulesForPredicate = predicate.isVariable() ? allRuleClauseCodes : (List) predicateToCodeMap.get(predicate);
207             for (Iterator j = allRulesForPredicate.iterator(); j.hasNext(); ) {
208                 RuleClauseCode code = (RuleClauseCode)j.next();
209                 ClauseEntry head = code.getRule().getHeadElement(0);
210                 boolean indexed = false;
211                 if (head instanceof TriplePattern) {
212                     Node objectPattern = ((TriplePattern)head).getObject();
213                     if (!objectPattern.isVariable() && !Functor.isFunctor(objectPattern)) {
214                         // Index against object
215 List indexedCode = (List) predicateMap.get(objectPattern);
216                         if (indexedCode == null) {
217                             indexedCode = new ArrayList();
218                             predicateMap.put(objectPattern, indexedCode);
219                         }
220                         indexedCode.add(code);
221                         indexed = true;
222                     }
223                 }
224                 if (!indexed) {
225                     wildRulesForPredicate.add(code);
226                 }
227             }
228             // Now fold the rules that apply to any index entry into all the indexed entries
229 for (Iterator k = predicateMap.entrySet().iterator(); k.hasNext(); ) {
230                 Map.Entry ent = (Map.Entry)k.next();
231                 Node pred = (Node)ent.getKey();
232                 List predicateCode = (List)ent.getValue();
233                 predicateCode.addAll(wildRulesForPredicate);
234             }
235         }
236         
237         // Now compile all the clauses
238 for (Iterator i = allRuleClauseCodes.iterator(); i.hasNext(); ) {
239             RuleClauseCode code = (RuleClauseCode)i.next();
240             code.compile(this);
241         }
242     }
243     
244     /**
245      * Add/remove a single rule from the store.
246      * Overridden in order to reset the "isCompiled" flag.
247      *
248      * @param rule the rule, single headed only
249      * @param isAdd true to add, false to remove
250      */
251     protected void doAddRemoveRule(Rule rule, boolean isAdd) {
252         isCompiled = false;
253         super.doAddRemoveRule(rule, isAdd);
254     }
255
256 }
257
258
259 /*
260     (c) Copyright 2003, 2004, 2005 Hewlett-Packard Development Company, LP
261     All rights reserved.
262
263     Redistribution and use in source and binary forms, with or without
264     modification, are permitted provided that the following conditions
265     are met:
266
267     1. Redistributions of source code must retain the above copyright
268        notice, this list of conditions and the following disclaimer.
269
270     2. Redistributions in binary form must reproduce the above copyright
271        notice, this list of conditions and the following disclaimer in the
272        documentation and/or other materials provided with the distribution.
273
274     3. The name of the author may not be used to endorse or promote products
275        derived from this software without specific prior written permission.
276
277     THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
278     IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
279     OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
280     IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
281     INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
282     NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
283     DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
284     THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
285     (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
286     THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
287 */
Popular Tags