001: /******************************************************************
002: * File: LPRuleStore.java
003: * Created by: Dave Reynolds
004: * Created on: 18-Jul-2003
005: *
006: * (c) Copyright 2003, 2004, 2005, 2006, 2007, 2008 Hewlett-Packard Development Company, LP
007: * [See end of file]
008: * $Id: LPRuleStore.java,v 1.7 2008/01/02 12:06:16 andy_seaborne Exp $
009: *****************************************************************/package com.hp.hpl.jena.reasoner.rulesys.impl;
010:
011: import com.hp.hpl.jena.reasoner.TriplePattern;
012: import com.hp.hpl.jena.reasoner.rulesys.*;
013: import com.hp.hpl.jena.graph.*;
014:
015: import java.util.*;
016:
017: /**
018: * Holds the set of backward rules used by an LPEngine. Is responsible
019: * for compile the rules into internal byte codes before use.
020: *
021: * @author <a href="mailto:der@hplb.hpl.hp.com">Dave Reynolds</a>
022: * @version $Revision: 1.7 $ on $Date: 2008/01/02 12:06:16 $
023: */
024: public class LPRuleStore extends RuleStore {
025:
026: /** Flag to indicate whether the rules have been compiled into code objects */
027: protected boolean isCompiled = false;
028:
029: /** A map from predicate to a list of RuleClauseCode objects for that predicate.
030: * Uses Node_RuleVariable.WILD for wildcard predicates.
031: */
032: protected Map predicateToCodeMap;
033:
034: /** The list of all RuleClauseCode objects, used to implement wildcard queries */
035: protected ArrayList allRuleClauseCodes;
036:
037: /** Two level index map - index on predicate then on object */
038: protected Map indexPredicateToCodeMap;
039:
040: /** Set of predicates which should be tabled */
041: protected HashSet tabledPredicates = new HashSet();
042:
043: /** Threshold for number of rule entries in a predicate bucket before second level indexing kicks in */
044: private static final int INDEX_THRESHOLD = 20;
045:
046: /** True if all goals should be treated as tabled */
047: protected boolean allTabled = false;
048:
049: /**
050: * Construct a rule store containing the given rules.
051: * @param rules the rules to initialize the store with.
052: */
053: public LPRuleStore(List rules) {
054: super (rules);
055: }
056:
057: /**
058: * Construct an empty rule store
059: */
060: public LPRuleStore() {
061: super ();
062: }
063:
064: /**
065: * Add all the rules and tabling instructions from an existing rulestore into this one.
066: */
067: public void addAll(LPRuleStore store) {
068: super .addAll(store);
069: tabledPredicates.addAll(store.tabledPredicates);
070: allTabled = tabledPredicates.contains(Node.ANY);
071: }
072:
073: /**
074: * Register an RDF predicate as one whose presence in a goal should force
075: * the goal to be tabled.
076: */
077: public synchronized void tablePredicate(Node predicate) {
078: tabledPredicates.add(predicate);
079: if (predicate == Node.ANY)
080: allTabled = true;
081: }
082:
083: /**
084: * Return an ordered list of RuleClauseCode objects to implement the given
085: * predicate.
086: * @param predicate the predicate node or Node_RuleVariable.WILD for wildcards.
087: */
088: public List codeFor(Node predicate) {
089: if (!isCompiled) {
090: compileAll();
091: }
092: if (predicate.isVariable()) {
093: return allRuleClauseCodes;
094: } else {
095: List codeList = (List) predicateToCodeMap.get(predicate);
096: if (codeList == null) {
097: // Uknown predicate, so only the wildcard rules apply
098: codeList = (List) predicateToCodeMap
099: .get(Node_RuleVariable.WILD);
100: }
101: return codeList;
102: }
103: }
104:
105: /**
106: * Return an ordered list of RuleClauseCode objects to implement the given
107: * query pattern. This may use indexing to narrow the rule set more that the predicate-only case.
108: * @param goal the triple pattern that makes up the query
109: */
110: public List codeFor(TriplePattern goal) {
111: List allRules = codeFor(goal.getPredicate());
112: if (allRules == null) {
113: return allRules;
114: }
115: Map indexedCodeTable = (Map) indexPredicateToCodeMap.get(goal
116: .getPredicate());
117: if (indexedCodeTable != null) {
118: List indexedCode = (List) indexedCodeTable.get(goal
119: .getObject());
120: if (indexedCode != null) {
121: return indexedCode;
122: }
123: }
124: return allRules;
125: }
126:
127: /**
128: * Return true if the given predicate is indexed.
129: */
130: public boolean isIndexedPredicate(Node predicate) {
131: return (indexPredicateToCodeMap.get(predicate) != null);
132: }
133:
134: /**
135: * Return true if the given goal is tabled, currently this is true if the
136: * predicate is a tabled predicate or the predicate is a wildcard and some
137: * tabled predictes exist.
138: */
139: public boolean isTabled(TriplePattern goal) {
140: return isTabled(goal.getPredicate());
141: }
142:
143: /**
144: * Return true if the given predicated is tabled, currently this is true if the
145: * predicate is a tabled predicate or the predicate is a wildcard and some
146: * tabled predictes exist.
147: */
148: public boolean isTabled(Node predicate) {
149: if (allTabled)
150: return true;
151: if (predicate.isVariable() && !tabledPredicates.isEmpty()) {
152: return true;
153: } else {
154: return tabledPredicates.contains(predicate);
155: }
156: }
157:
158: /**
159: * Compile all the rules in a table. initially just indexed on predicate but want to
160: * add better indexing for the particular cases of wildcard rules and type rules.
161: */
162: protected void compileAll() {
163: isCompiled = true;
164:
165: predicateToCodeMap = new HashMap();
166: allRuleClauseCodes = new ArrayList();
167: indexPredicateToCodeMap = new HashMap();
168: for (Iterator ri = getAllRules().iterator(); ri.hasNext();) {
169: Rule r = (Rule) ri.next();
170: ClauseEntry term = r.getHeadElement(0);
171: if (term instanceof TriplePattern) {
172: RuleClauseCode code = new RuleClauseCode(r);
173: allRuleClauseCodes.add(code);
174: Node predicate = ((TriplePattern) term).getPredicate();
175: if (predicate.isVariable()) {
176: predicate = Node_RuleVariable.WILD;
177: }
178: List predicateCode = (List) predicateToCodeMap
179: .get(predicate);
180: if (predicateCode == null) {
181: predicateCode = new ArrayList();
182: predicateToCodeMap.put(predicate, predicateCode);
183: }
184: predicateCode.add(code);
185: if (predicateCode.size() > INDEX_THRESHOLD) {
186: indexPredicateToCodeMap.put(predicate,
187: new HashMap());
188: }
189: }
190: }
191:
192: // Now add the wild card rules into the list for each non-wild predicate)
193: List wildRules = (List) predicateToCodeMap
194: .get(Node_RuleVariable.WILD);
195: if (wildRules != null) {
196: for (Iterator i = predicateToCodeMap.entrySet().iterator(); i
197: .hasNext();) {
198: Map.Entry entry = (Map.Entry) i.next();
199: Node predicate = (Node) entry.getKey();
200: List predicateCode = (List) entry.getValue();
201: if (predicate != Node_RuleVariable.WILD) {
202: predicateCode.addAll(wildRules);
203: }
204: }
205: }
206: indexPredicateToCodeMap.put(Node_RuleVariable.WILD,
207: new HashMap());
208:
209: // Now built any required two level indices
210: for (Iterator i = indexPredicateToCodeMap.entrySet().iterator(); i
211: .hasNext();) {
212: Map.Entry entry = (Map.Entry) i.next();
213: Node predicate = (Node) entry.getKey();
214: HashMap predicateMap = (HashMap) entry.getValue();
215: List wildRulesForPredicate = new ArrayList();
216: List allRulesForPredicate = predicate.isVariable() ? allRuleClauseCodes
217: : (List) predicateToCodeMap.get(predicate);
218: for (Iterator j = allRulesForPredicate.iterator(); j
219: .hasNext();) {
220: RuleClauseCode code = (RuleClauseCode) j.next();
221: ClauseEntry head = code.getRule().getHeadElement(0);
222: boolean indexed = false;
223: if (head instanceof TriplePattern) {
224: Node objectPattern = ((TriplePattern) head)
225: .getObject();
226: if (!objectPattern.isVariable()
227: && !Functor.isFunctor(objectPattern)) {
228: // Index against object
229: List indexedCode = (List) predicateMap
230: .get(objectPattern);
231: if (indexedCode == null) {
232: indexedCode = new ArrayList();
233: predicateMap
234: .put(objectPattern, indexedCode);
235: }
236: indexedCode.add(code);
237: indexed = true;
238: }
239: }
240: if (!indexed) {
241: wildRulesForPredicate.add(code);
242: }
243: }
244: // Now fold the rules that apply to any index entry into all the indexed entries
245: for (Iterator k = predicateMap.entrySet().iterator(); k
246: .hasNext();) {
247: Map.Entry ent = (Map.Entry) k.next();
248: Node pred = (Node) ent.getKey();
249: List predicateCode = (List) ent.getValue();
250: predicateCode.addAll(wildRulesForPredicate);
251: }
252: }
253:
254: // Now compile all the clauses
255: for (Iterator i = allRuleClauseCodes.iterator(); i.hasNext();) {
256: RuleClauseCode code = (RuleClauseCode) i.next();
257: code.compile(this );
258: }
259: }
260:
261: /**
262: * Add/remove a single rule from the store.
263: * Overridden in order to reset the "isCompiled" flag.
264: *
265: * @param rule the rule, single headed only
266: * @param isAdd true to add, false to remove
267: */
268: protected void doAddRemoveRule(Rule rule, boolean isAdd) {
269: isCompiled = false;
270: super .doAddRemoveRule(rule, isAdd);
271: }
272:
273: }
274:
275: /*
276: (c) Copyright 2003, 2004, 2005, 2006, 2007, 2008 Hewlett-Packard Development Company, LP
277: All rights reserved.
278:
279: Redistribution and use in source and binary forms, with or without
280: modification, are permitted provided that the following conditions
281: are met:
282:
283: 1. Redistributions of source code must retain the above copyright
284: notice, this list of conditions and the following disclaimer.
285:
286: 2. Redistributions in binary form must reproduce the above copyright
287: notice, this list of conditions and the following disclaimer in the
288: documentation and/or other materials provided with the distribution.
289:
290: 3. The name of the author may not be used to endorse or promote products
291: derived from this software without specific prior written permission.
292:
293: THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
294: IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
295: OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
296: IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
297: INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
298: NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
299: DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
300: THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
301: (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
302: THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
303: */
|