001: /*
002: (c) Copyright 2002, 2003, 2004, 2005, 2006, 2007, 2008 Hewlett-Packard Development Company, LP
003: [See end of file]
004: $Id: DBQueryHandler.java,v 1.25 2008/01/02 12:08:22 andy_seaborne Exp $
005: */
006:
007: package com.hp.hpl.jena.db.impl;
008:
009: /**
010: An extension of SimpleQueryHandler for database-graphs.
011: @author wkw et al
012: */
013:
014: import com.hp.hpl.jena.graph.*;
015: import com.hp.hpl.jena.graph.query.*;
016: import com.hp.hpl.jena.db.*;
017: import com.hp.hpl.jena.shared.JenaException;
018:
019: import java.util.*;
020:
021: public class DBQueryHandler extends SimpleQueryHandler {
022:
023: /** the Graph this handler is working for */
024: private GraphRDB graph;
025: boolean queryOnlyStmt; // if true, query only asserted stmt (ignore reification)
026: boolean queryOnlyReif; // if true, query only reified stmt (ignore asserted)
027: boolean queryFullReif; // if true, ignore partially reified statements
028: private boolean doFastpath; // if true, enable fastpath optimization
029: private boolean doImplicitJoin; // if true, optimize (pushdown) implicit joins
030:
031: // e.g., "(ur1 pred1 ?v1) (uri1 pred2 ?v2)" is an implicit join on uri1
032:
033: /** make an instance, remember the graph */
034: public DBQueryHandler(GraphRDB graph) {
035: super (graph);
036: this .graph = graph;
037: if (graph.reificationBehavior() == GraphRDB.OPTIMIZE_ALL_REIFICATIONS_AND_HIDE_NOTHING) {
038: queryFullReif = queryOnlyReif = queryOnlyStmt = false;
039: } else {
040: queryFullReif = queryOnlyReif = false;
041: queryOnlyStmt = true;
042: }
043: doFastpath = true;
044: }
045:
046: public void setDoFastpath(boolean val) {
047: doFastpath = val;
048: }
049:
050: public boolean getDoFastpath() {
051: return doFastpath;
052: }
053:
054: public void setDoImplicitJoin(boolean val) {
055: doImplicitJoin = val;
056: }
057:
058: /**
059: Answer a Stage that covers the given triple patterns. This may be a
060: default stage if pastpath is disabled, or a composite database stage
061: if fastpath is enabled. If we're lucky there will be a single database
062: stage if the entire triple pattern can be translated into a single SQL
063: statement.
064: */
065: public Stage patternStage(Mapping varMap,
066: ExpressionSet constraints, Triple[] givenTriples) {
067: return avoidFastpath(constraints, givenTriples) ? super
068: .patternStage(varMap, constraints, givenTriples)
069: : patternStageWithFullpath(varMap, constraints,
070: givenTriples);
071: }
072:
073: /**
074: Answer true iff we should avoid the fastpath code and instead fall back
075: on the default implementation in SimpleQueryHandler. Cases:
076: <ul>
077: <li>doFastPath is false [obviously]
078: <li>givenTriples is empty [establishes a useful invariant]
079: <li>there's just one givenTriple and the constrains are not Complex
080: </ul>
081: */
082: private boolean avoidFastpath(ExpressionSet constraints,
083: Triple[] givenTriples) {
084: return doFastpath == false
085: || givenTriples.length == 0
086: || (givenTriples.length == 1 && !constraints
087: .isComplex());
088: }
089:
090: /**
091: <code>givenTriples</code> is not empty.
092: */
093: private Stage patternStageWithFullpath(Mapping varMap,
094: ExpressionSet constraints, Triple[] givenTriples) {
095: int i;
096: List stages = new ArrayList();
097: List patternsToDo = new ArrayList();
098: for (i = 0; i < givenTriples.length; i++)
099: patternsToDo.add(new Integer(i));
100: DBPattern[] source = createDBPatterns(varMap, givenTriples);
101: //
102: while (patternsToDo.size() > 0) {
103: DBPattern src = findCheapPattern(varMap, patternsToDo,
104: source);
105:
106: // now we have a pattern for the next stage.
107: List varList = new ArrayList(); // list of VarDesc
108: ExpressionSet evalCons = new ExpressionSet(); // constraints
109: // to eval
110: List queryPatterns = new ArrayList(); // list of DBPattern
111: queryPatterns.add(src);
112: boolean pushQueryIntoSQL = false;
113: // fastpath is only supported for patterns over one table.
114: if (src.isSingleSource()) {
115: src.addFreeVars(varList);
116: boolean didJoin = attemptJoiningOthers(patternsToDo,
117: source, src, varList, queryPatterns);
118: // push down query if (1) there is a join OR if
119: // (2) there is no join but there is a constraint to
120: // eval on a single pattern.
121: // see if any constraints can be pushed down
122: if (didJoin)
123: pushQueryIntoSQL = true;
124: else {
125: for (i = 0; i < varList.size(); i++) {
126: VarDesc vx = (VarDesc) varList.get(i);
127: // see if any constraints on a result var.
128: // if so, push down constraint.
129: /*/ UNCOMMENT THE LINES BELOW TO ENABLE CONSTRAINT EVALUATION WITHIN THE DB. */
130: if ((vx.isArgVar == false)
131: && findConstraints(constraints,
132: evalCons, vx))
133: pushQueryIntoSQL = true;
134: /* UNCOMMENT THE LINES ABOVE TO ENABLE CONSTRAINT EVALUATION WITHIN THE DB. */
135: }
136: }
137: if (pushQueryIntoSQL) {
138: // add result vars to reslist for query
139: for (i = 0; i < varList.size(); i++) {
140: VarDesc vx = (VarDesc) varList.get(i);
141: if (vx.isArgVar == false)
142: vx.bindToVarMap(varMap);
143: }
144: }
145:
146: } else if (!src.hasSource())
147: pushQueryIntoSQL = true;
148: // hack to handle the case when no graphs match the pattern
149: Stage newStage = pushQueryIntoSQL ? new DBQueryStage(graph,
150: src.hasSource() ? src.singleSource() : null,
151: varList, queryPatterns, evalCons) : super
152: .patternStage(varMap, constraints,
153: new Triple[] { src.pattern });
154: // stages[stageCount++] = newStage;
155: stages.add(newStage);
156: }
157: return stages.size() == 1 ? (Stage) stages.get(0)
158: : new StageSequence(stages);
159: }
160:
161: /**
162: @param patternsToDo
163: @param source
164: @param src
165: @param varList
166: @param queryPatterns
167: @return
168: */
169: private boolean attemptJoiningOthers(List patternsToDo,
170: DBPattern[] source, DBPattern src, List varList,
171: List queryPatterns) {
172: boolean didJoin = false;
173: // see if other patterns can join with it.
174: while (true) {
175: boolean foundJoin = false;
176: for (int i = 0; i < patternsToDo.size(); i++) {
177: DBPattern candidate = source[((Integer) patternsToDo
178: .get(i)).intValue()];
179: if (candidate.joinsWith(src, varList, queryOnlyStmt,
180: queryOnlyReif, doImplicitJoin)) {
181: queryPatterns.add(candidate);
182: patternsToDo.remove(i);
183: candidate.addFreeVars(varList);
184: candidate.setBusy();
185: foundJoin = didJoin = true;
186: }
187: }
188: if (foundJoin == false || patternsToDo.size() == 0)
189: break;
190: }
191: // while (foundJoin && patternsToDo.size() > 0);
192: return didJoin;
193: }
194:
195: /**
196: find the minimum cost pattern ... but always choose a connected
197: pattern over a disconnected pattern (to avoid cross-products).
198: There will always be a minimal cost pattern (because <code>sources</code>
199: is never empty).
200: */
201: private DBPattern findCheapPattern(Mapping varMap,
202: List patternsToDo, DBPattern[] sources) {
203: DBPattern cheapSource = null;
204: boolean haveConnectedPattern = false;
205: int minCost = DBPattern.costMax, minConnCost = DBPattern.costMax;
206: int selectedPatternIndex = -1;
207: for (int i = 0; i < patternsToDo.size(); i++) {
208: DBPattern unstaged = sources[((Integer) patternsToDo.get(i))
209: .intValue()];
210: int cost = unstaged.cost(varMap);
211: if (unstaged.isConnected()) {
212: if (cost < minConnCost) {
213: cheapSource = unstaged;
214: minConnCost = cost;
215: haveConnectedPattern = true;
216: selectedPatternIndex = i;
217: }
218: } else if (haveConnectedPattern == false && cost < minCost) {
219: minCost = cost;
220: cheapSource = unstaged;
221: selectedPatternIndex = i;
222: }
223: }
224: if (cheapSource == null)
225: throw new JenaException(
226: "impossible: no cheapest pattern among sources");
227: cheapSource.setBusy();
228: patternsToDo.remove(selectedPatternIndex);
229: return cheapSource;
230: }
231:
232: /**
233: Answer an array of database pattern objects, each associated with
234: the specialised graphs that might contain the triples it's trying to
235: match.
236: */
237: private DBPattern[] createDBPatterns(Mapping varMap,
238: Triple[] givenTriples) {
239: DBPattern[] sources = new DBPattern[givenTriples.length];
240: int reifBehavior = graph.reificationBehavior();
241: for (int i = 0; i < givenTriples.length; i += 1)
242: sources[i] = createInitialPattern(varMap, reifBehavior,
243: givenTriples[i]);
244: return sources;
245: }
246:
247: private DBPattern createInitialPattern(Mapping varMap,
248: int reifBehavior, Triple triple) {
249: DBPattern src = new DBPattern(triple, varMap);
250: associateWithSources(src, triple, reifBehavior);
251: return src;
252: }
253:
254: /**
255: Associate the database pattern <code>src</code> with the sources
256: which might contain triples it would match.
257: */
258: private void associateWithSources(DBPattern src, Triple pat,
259: int reifBehavior) {
260: Iterator it = graph.getSpecializedGraphs();
261: while (it.hasNext()) {
262: SpecializedGraph sg = (SpecializedGraph) it.next();
263: char sub = sg.subsumes(pat, reifBehavior);
264: if (sub != SpecializedGraph.noTriplesForPattern)
265: src.sourceAdd(sg, sub);
266: if (sub == SpecializedGraph.allTriplesForPattern)
267: break;
268: }
269: }
270:
271: // getters/setters for query handler options
272:
273: public void setQueryOnlyAsserted(boolean opt) {
274: if ((opt == true) && (queryOnlyReif == true))
275: throw new JenaException(
276: "QueryOnlyAsserted and QueryOnlyReif cannot both be true");
277: queryOnlyStmt = opt;
278: }
279:
280: public boolean getQueryOnlyAsserted() {
281: return queryOnlyStmt;
282: }
283:
284: public void setQueryOnlyReified(boolean opt) {
285: // System.err.println( ">> setQueryOnlyReified: style of graph is " + graph.getReifier().getStyle() );
286: if (graph.reificationBehavior() != GraphRDB.OPTIMIZE_ALL_REIFICATIONS_AND_HIDE_NOTHING)
287: throw new JenaException(
288: "Reified statements cannot be queried for this model's reification style: "
289: + graph.getReifier().getStyle());
290: if ((opt == true) && (queryOnlyStmt == true))
291: throw new JenaException(
292: "QueryOnlyAsserted and QueryOnlyReif cannot both be true");
293: queryOnlyReif = opt;
294: }
295:
296: public boolean getQueryOnlyReified() {
297: return queryOnlyReif;
298: }
299:
300: public void setQueryFullReified(boolean opt) {
301: if (graph.reificationBehavior() != GraphRDB.OPTIMIZE_ALL_REIFICATIONS_AND_HIDE_NOTHING)
302: throw new JenaException(
303: "Reified statements cannot be queried for this model's reification style");
304: queryFullReif = opt;
305: }
306:
307: public boolean getQueryFullReified() {
308: return queryFullReif;
309: }
310:
311: private boolean findConstraints(ExpressionSet constraints,
312: ExpressionSet evalCons, VarDesc vx) {
313: boolean res = false;
314: Iterator it = constraints.iterator();
315: Expression e;
316: while (it.hasNext()) {
317: e = (Expression) it.next();
318: if (e.isApply() && e.argCount() == 2) {
319: Expression l = e.getArg(0);
320: if (l.isVariable()
321: && vx.var.getName().equals(l.getName())) {
322: String f = e.getFun();
323: if (dbPartiallyHandlesExpression(f)) {
324: evalCons.add(e);
325: // for now, constraints must be reevaluated outside the
326: // db engine since the db engine may not fully evaluate
327: // the constraint.
328: // it.remove();
329: res = true;
330: }
331: }
332: }
333: }
334: return res;
335: }
336:
337: /**
338: Answer true if the database makes at least a partial attempt to evaluate
339: this constraint.
340: */
341: private boolean dbPartiallyHandlesExpression(String f) {
342: return f.equals(ExpressionFunctionURIs.J_startsWith)
343: || f
344: .equals(ExpressionFunctionURIs.J_startsWithInsensitive)
345: || f.equals(ExpressionFunctionURIs.J_contains)
346: || f
347: .equals(ExpressionFunctionURIs.J_containsInsensitive)
348: || f.equals(ExpressionFunctionURIs.J_EndsWith)
349: || f
350: .equals(ExpressionFunctionURIs.J_endsWithInsensitive);
351: }
352:
353: protected static final class StageSequence extends Stage {
354: private final int numStages;
355:
356: private final Stage[] stages;
357:
358: protected StageSequence(List stages) {
359: this .numStages = stages.size();
360: this .stages = (Stage[]) stages
361: .toArray(new Stage[this .numStages]);
362: }
363:
364: public Stage connectFrom(Stage s) {
365: for (int i = 0; i < numStages; i += 1) {
366: stages[i].connectFrom(s);
367: s = stages[i];
368: }
369: return super .connectFrom(s);
370: }
371:
372: public Pipe deliver(Pipe L) {
373: return stages[numStages - 1].deliver(L);
374: }
375: }
376: }
377:
378: /*
379: (c) Copyright 2002, 2002, 2003, 2004, 2005, 2006, 2007, 2008 Hewlett-Packard Development Company, LP
380: All rights reserved.
381:
382: Redistribution and use in source and binary forms, with or without
383: modification, are permitted provided that the following conditions
384: are met:
385:
386: 1. Redistributions of source code must retain the above copyright
387: notice, this list of conditions and the following disclaimer.
388:
389: 2. Redistributions in binary form must reproduce the above copyright
390: notice, this list of conditions and the following disclaimer in the
391: documentation and/or other materials provided with the distribution.
392:
393: 3. The name of the author may not be used to endorse or promote products
394: derived from this software without specific prior written permission.
395:
396: THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
397: IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
398: OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
399: IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
400: INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
401: NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
402: DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
403: THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
404: (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
405: THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
406: */
|