001: /*
002: * (c) Copyright 2002, 2003, 2004, 2005, 2006, 2007, 2008 Hewlett-Packard Development Company, LP
003: * [see end of file]
004: */
005:
006: package com.hp.hpl.jena.db.impl;
007:
008: import java.util.ArrayList;
009: import java.util.List;
010:
011: import com.hp.hpl.jena.db.RDFRDBException;
012: import com.hp.hpl.jena.graph.Node;
013: import com.hp.hpl.jena.graph.Node_Variable;
014: import com.hp.hpl.jena.graph.Triple;
015: import com.hp.hpl.jena.graph.query.Bound;
016: import com.hp.hpl.jena.graph.query.Domain;
017: import com.hp.hpl.jena.graph.query.Element;
018: import com.hp.hpl.jena.graph.query.Fixed;
019: import com.hp.hpl.jena.graph.query.Mapping;
020: import com.hp.hpl.jena.graph.query.Query;
021: import com.hp.hpl.jena.shared.BrokenException;
022:
023: public class DBPattern {
024: final Triple pattern;
025: final Element S;
026: final Element P;
027: final Element O;
028:
029: private int Scost, Pcost, Ocost;
030:
031: private boolean isBusy;
032:
033: private boolean isConnected; // pattern can be joined to previously staged pattern for this query.
034:
035: private boolean isStmt; // pattern is over only asserted statement tables (no reified)
036: private boolean isReif; // pattern is over only reified statement tables (no asserted)
037:
038: private List sources; // specialized graphs with triples for this pattern
039:
040: private char subsumed;
041:
042: public DBPattern(Triple pat, Mapping varMap) {
043: pattern = pat;
044: sources = new ArrayList();
045: isBusy = false;
046: isConnected = false;
047: isStmt = isReif = false;
048: S = nodeToElement(pattern.getSubject(), varMap);
049: P = nodeToElement(pattern.getPredicate(), varMap);
050: O = nodeToElement(pattern.getObject(), varMap);
051: Scost = elementCost(S);
052: Pcost = elementCost(P);
053: Ocost = elementCost(O);
054: }
055:
056: public void setBusy() { // pro tem, in case the old `isStaged` actually still meant something
057: if (isBusy)
058: throw new BrokenException(
059: "a DBPattern can be made busy at most once");
060: isBusy = true;
061: }
062:
063: public boolean isConnected() {
064: return isConnected;
065: }
066:
067: /**
068: this nodeToElement is pretty much identical to that of
069: graph.query.patternstagecompiler.compile.
070: */
071: private Element nodeToElement(Node X, Mapping map) {
072: if (X.equals(Query.ANY))
073: return Element.ANY;
074: if (X.isVariable()) {
075: if (map.hasBound(X))
076: return new Bound(map.indexOf(X));
077: else {
078: freeVarCnt++;
079: return new Free(X);
080: }
081: }
082: return new Fixed(X);
083: }
084:
085: public void sourceAdd(SpecializedGraph sg, char sub) {
086: if (sources.isEmpty()) {
087: subsumed = sub;
088: if (sg instanceof SpecializedGraphReifier_RDB)
089: isReif = true;
090: else
091: isStmt = true;
092: } else {
093: if (subsumed != sub)
094: throw new RDFRDBException(
095: "Specialized graphs incorrectly subsume pattern");
096: if (sg instanceof SpecializedGraphReifier_RDB)
097: isStmt = false;
098: else
099: isReif = false;
100: }
101: sources.add(sg);
102: }
103:
104: public boolean hasSource() {
105: return sources.size() > 0;
106: }
107:
108: /**
109: Answer true iff this pattern [currently] is associated with exactly one source.
110: */
111: public boolean isSingleSource() {
112: return sources.size() == 1;
113: }
114:
115: public SpecializedGraph singleSource() {
116: return (SpecializedGraph) sources.get(0);
117: }
118:
119: protected void addFreeVars(List varList) {
120: if (freeVarCnt > 0) {
121: if (S instanceof Free)
122: addVar(varList, (Free) S);
123: if (P instanceof Free)
124: addVar(varList, (Free) P);
125: if (O instanceof Free)
126: addVar(varList, (Free) O);
127: }
128: }
129:
130: private int findVar(List varList, Node_Variable var) {
131: for (int i = 0; i < varList.size(); i += 1) {
132: Node_Variable v = ((VarDesc) varList.get(i)).var;
133: if (var.equals(v))
134: return i;
135: }
136: return -1;
137: }
138:
139: private void addVar(List varList, Free var) {
140: int i = findVar(varList, var.var());
141: if (i < 0) {
142: i = varList.size();
143: VarDesc vx;
144: if (var.isArg()) {
145: vx = new VarDesc(var.var(), var.getMapping(), i);
146: } else {
147: vx = new VarDesc(var.var(), i);
148: }
149: varList.add(vx);
150: }
151: var.setListing(i);
152: }
153:
154: /**
155: currently, we can only join over the same table, and, in general, we
156: can't join if the pattern has a predicate variable -- but, if we are only
157: querying asserted stmts and the pattern is over asserted stmts, we can
158: do the join.
159: */
160: public boolean joinsWith(DBPattern other, List varList,
161: boolean onlyStmt, boolean onlyReif, boolean implicitJoin) {
162: boolean includesSource = other.isSingleSource()
163: && sources.contains(other.sources.get(0));
164: boolean newSourceTest = sources.containsAll(other.sources);
165: // if (includesSource != newSourceTest) System.err.println( ">> old source test: " + includesSource + ", but new source test: " + newSourceTest );
166: if (includesSource
167: && (!(P instanceof Free) || (onlyStmt && isStmt))) { // other has same source. See if there's a join variable.
168: return appearsIn(S, varList) || appearsIn(O, varList)
169: || (onlyStmt && isStmt && appearsIn(P, varList))
170: || (implicitJoin && shareFixedSubject(other));
171: }
172: return false;
173: }
174:
175: private boolean shareFixedSubject(DBPattern other) { // Yukk.
176: boolean originalDefinition = S instanceof Fixed
177: && other.S instanceof Fixed
178: && S.match((Domain) null, other.S
179: .asNodeMatch((Domain) null));
180: return originalDefinition;
181: }
182:
183: /**
184: Answer true iff <code>e</code> is a free variable that appears in
185: <code>varList</code>.
186: */
187: private boolean appearsIn(Element e, List varList) {
188: return e instanceof Free
189: && findVar(varList, ((Free) e).var()) >= 0;
190: }
191:
192: /**
193: * Return the relative cost of evaluating the pattern with the current.
194: * @return the relative cost.
195: */
196:
197: public int cost(Mapping varMap) {
198: if (costInit) {
199: costInit = false;
200: costCur = costCalc();
201: } else if (freeVarCnt > 0) {
202: // only recompute cost if there's a chance it changed.
203: if (anyBound(varMap)) {
204: costCur = costCalc();
205: }
206: }
207: return costCur;
208: }
209:
210: static final int costMax = 100;
211: static final int costMin = 1;
212: int costCur;
213:
214: private boolean costInit = true;
215: private int freeVarCnt = 0;
216:
217: protected boolean isArgCheck(Free v, Mapping map) {
218: int ix = map.lookUp(v.var());
219: if (ix >= 0) {
220: v.setIsArg(ix);
221: isConnected = true;
222: freeVarCnt -= 1;
223: return true;
224: } else
225: return false;
226: }
227:
228: protected boolean anyBound(Mapping map) {
229: boolean res = false;
230: if (S instanceof Free)
231: if (isArgCheck((Free) S, map)) {
232: Scost = elementCost(S);
233: res = true;
234: }
235: if (P instanceof Free)
236: if (isArgCheck((Free) P, map)) {
237: Pcost = elementCost(P);
238: res = true;
239: }
240: if (O instanceof Free)
241: if (isArgCheck((Free) O, map)) {
242: Ocost = elementCost(O);
243: res = true;
244: }
245: return res;
246: }
247:
248: private int fixedCost = 0;
249: private int boundCost = 0;
250: private int unboundCost = 4;
251:
252: // private int unboundPredFactor = 4;
253:
254: private int elementCost(Element x) {
255: if (x instanceof Fixed)
256: return fixedCost;
257: else if (x instanceof Bound)
258: return boundCost;
259: else if ((x instanceof Free) && ((Free) x).isArg())
260: return boundCost;
261: else
262: return unboundCost;
263: }
264:
265: /*
266: * compute the "estimated cost" to evaluate the pattern. in fact,
267: * it is just a relative ranking that favors patterns with bound
268: * nodes (FIXED or bound variables) over unbound nodes (unbound
269: * variables and ANY).
270: * @return int The estimated cost in the range [costmin,costMax).
271: */
272:
273: private int costCalc() {
274: return Scost + Pcost + Ocost;
275: }
276: }
277:
278: /*
279: * (c) Copyright 2002, 2003, 2004, 2005, 2006, 2007, 2008 Hewlett-Packard Development Company, LP
280: * All rights reserved.
281: *
282: * Redistribution and use in source and binary forms, with or without
283: * modification, are permitted provided that the following conditions
284: * are met:
285: * 1. Redistributions of source code must retain the above copyright
286: * notice, this list of conditions and the following disclaimer.
287: * 2. Redistributions in binary form must reproduce the above copyright
288: * notice, this list of conditions and the following disclaimer in the
289: * documentation and/or other materials provided with the distribution.
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: */
|