KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > com > hp > hpl > jena > db > impl > DBPattern


1 /*
2  * (c) Copyright 2002, 2003, 2004, 2005 Hewlett-Packard Development Company, LP
3  * [see end of file]
4  */
5
6 package com.hp.hpl.jena.db.impl;
7
8 import java.util.ArrayList JavaDoc;
9 import java.util.List JavaDoc;
10
11 import com.hp.hpl.jena.db.RDFRDBException;
12 import com.hp.hpl.jena.graph.Node;
13 import com.hp.hpl.jena.graph.Node_Variable;
14 import com.hp.hpl.jena.graph.Triple;
15 import com.hp.hpl.jena.graph.query.Bound;
16 import com.hp.hpl.jena.graph.query.Domain;
17 import com.hp.hpl.jena.graph.query.Element;
18 import com.hp.hpl.jena.graph.query.Fixed;
19 import com.hp.hpl.jena.graph.query.Mapping;
20 import com.hp.hpl.jena.graph.query.Query;
21
22
23 public class DBPattern {
24     Triple pattern;
25     Element S;
26     Element P;
27     Element O;
28     int Scost, Pcost, Ocost;
29     boolean isStaged;
30     boolean isConnected; // pattern can be joined to previously staged pattern for this query.
31 boolean isSingleSource; // pattern has just one data source (specialized graph)
32 boolean isStmt; // pattern is over only asserted statement tables (no reified)
33 boolean isReif; // pattern is over only reified statement tables (no asserted)
34 List JavaDoc source; // specialized graphs with triples for this pattern
35 char subsumed;
36     
37     public DBPattern ( Triple pat, Mapping varMap ) {
38         pattern = pat;
39         source = new ArrayList JavaDoc();
40         isStaged = false;
41         isConnected = false;
42         isSingleSource = false;
43         isStmt = isReif = false;
44         S = nodeToElement(pattern.getSubject(), varMap);
45         P = nodeToElement(pattern.getPredicate(), varMap);
46         O = nodeToElement(pattern.getObject(), varMap);
47         Scost = elementCost(S);
48         Pcost = elementCost(P);
49         Ocost = elementCost(O);
50     }
51     
52     /**
53         this nodeToElement is pretty much identical to that of
54         graph.query.patternstagecompiler.compile.
55     */
56     private Element nodeToElement( Node X, Mapping map )
57         {
58         if (X.equals( Query.ANY )) return Element.ANY;
59         if (X.isVariable()) {
60             if (map.hasBound(X))
61                 return new Bound (map.indexOf(X));
62             else {
63                 freeVarCnt++;
64                 return new Free( X );
65             }
66         }
67         return new Fixed( X );
68         }
69
70     
71     public void sourceAdd ( SpecializedGraph sg, char sub ) {
72         if ( source.isEmpty() ) {
73             subsumed = sub;
74             isSingleSource = true;
75             if ( sg instanceof SpecializedGraphReifier_RDB ) isReif = true;
76             else isStmt = true;
77         } else {
78             if ( subsumed != sub )
79                 throw new RDFRDBException("Specialized graphs incorrectly subsume pattern");
80             isSingleSource = false;
81             if ( sg instanceof SpecializedGraphReifier_RDB ) isStmt = false;
82             else isReif = false;
83         }
84         source.add(sg);
85     }
86     
87     public boolean hasSource() { return !source.isEmpty(); }
88     public boolean isSingleSource() { return isSingleSource; }
89     public SpecializedGraph singleSource() { return (SpecializedGraph) source.get(0); }
90
91     protected void addFreeVars ( List JavaDoc varList ) {
92         if (freeVarCnt > 0) {
93             if (S instanceof Free)
94                 addVar(varList, (Free) S);
95             if (P instanceof Free)
96                 addVar(varList, (Free) P);
97             if (O instanceof Free)
98                 addVar(varList, (Free) O);
99         }
100     }
101     
102     private int findVar ( List JavaDoc varList, Node_Variable var ) {
103         int i;
104         for ( i=0; i<varList.size(); i++ ) {
105             Node_Variable v = ((VarDesc) varList.get(i)).var;
106             if ( var.equals(v) )
107                 return i;
108         }
109         return -1;
110     }
111
112     private void addVar ( List JavaDoc varList, Free var ) {
113         int i = findVar(varList,var.var());
114         if ( i < 0 ) {
115             i = varList.size();
116             VarDesc vx;
117             if ( var.isArg() ) {
118                 vx = new VarDesc (var.var(), var.getMapping(), i);
119             } else {
120                 vx = new VarDesc (var.var(), i);
121             }
122             varList.add(vx);
123         }
124         var.setListing(i);
125     }
126     
127     public boolean joinsWith ( DBPattern jsrc, List JavaDoc varList, boolean onlyStmt, boolean onlyReif, boolean implJoin ) {
128         // currently, we can only join over the same table.
129 // and, in general, we can't join if the pattern has a predicate variable.
130 // but, if we are only querying asserted stmts and the pattern is
131 // over asserted stmts, we can do the join.
132 if ( jsrc.isSingleSource() && source.contains(jsrc.source.get(0)) &&
133             ( !(P instanceof Free) || (onlyStmt && isStmt) ) ) {
134             // jsrc has same source. look for a join variables
135 if ( (S instanceof Free) && (findVar(varList,((Free)S).var()) >= 0) )
136                     return true;
137             if ( (O instanceof Free) && (findVar(varList,((Free)O).var()) >= 0) )
138                     return true;
139             if ( onlyStmt && isStmt && (P instanceof Free) &&
140                     (findVar(varList,((Free)P).var()) >= 0) )
141                         return true;
142             if ( implJoin && (S instanceof Fixed) && (jsrc.S instanceof Fixed)
143                     && S.match((Domain)null,jsrc.S.asNodeMatch((Domain)null) ) )
144                 return true;
145         }
146         return false;
147     }
148     
149     
150     /**
151      * Return the relative cost of evaluating the pattern with the current.
152      * @return the relative cost.
153      */
154     
155     public int cost ( Mapping varMap ) {
156         if ( costInit ) {
157             costInit = false;
158             costCur = costCalc();
159         } else if ( freeVarCnt > 0 ) {
160             // only recompute cost if there's a chance it changed.
161 if ( anyBound(varMap) ) {
162                 costCur = costCalc();
163             }
164         }
165         return costCur;
166     }
167     
168     static final int costMax = 100;
169     static final int costMin = 1;
170     int costCur;
171     
172     private boolean costInit = true;
173     private int freeVarCnt = 0;
174     
175     protected boolean isArgCheck ( Free v, Mapping map ) {
176         int ix;
177         ix = map.lookUp(v.var());
178         if ( ix >= 0 ) {
179             v.setIsArg(ix);
180             isConnected = true;
181             freeVarCnt--;
182             return true;
183         } else
184             return false;
185     }
186
187     protected boolean anyBound(Mapping map) {
188         boolean res = false;
189         if ( S instanceof Free )
190             if ( isArgCheck((Free)S,map) ) {
191                 Scost = elementCost(S);
192                 res = true;
193             }
194         if ( P instanceof Free )
195             if ( isArgCheck((Free)P,map) ) {
196                 Pcost = elementCost(P);
197                 res = true;
198             }
199         if ( O instanceof Free )
200             if ( isArgCheck((Free)O,map) ) {
201                 Ocost = elementCost(O);
202                 res = true;
203             }
204         return res;
205     }
206     
207     private int fixedCost = 0;
208     private int boundCost = 0;
209     private int unboundCost = 4;
210     private int unboundPredFactor = 4;
211
212     private int elementCost ( Element x ) {
213         if ( x instanceof Fixed )
214             return fixedCost;
215         else if ( x instanceof Bound )
216             return boundCost;
217         else if ( (x instanceof Free) && ((Free)x).isArg() )
218             return boundCost;
219         else
220             return unboundCost;
221     }
222
223     /*
224      * compute the "estimated cost" to evaluate the pattern. in fact,
225      * it is just a relative ranking that favors patterns with bound
226      * nodes (FIXED or bound variables) over unbound nodes (unbound
227      * variables and ANY).
228      * @return int The estimated cost in the range [costmin,costMax).
229      */
230      
231     private int costCalc() {
232         return Scost+Pcost+Ocost;
233     }
234
235 }
236
237 /*
238  * (c) Copyright 2002, 2003, 2004, 2005 Hewlett-Packard Development Company, LP
239  * All rights reserved.
240  *
241  * Redistribution and use in source and binary forms, with or without
242  * modification, are permitted provided that the following conditions
243  * are met:
244  * 1. Redistributions of source code must retain the above copyright
245  * notice, this list of conditions and the following disclaimer.
246  * 2. Redistributions in binary form must reproduce the above copyright
247  * notice, this list of conditions and the following disclaimer in the
248  * documentation and/or other materials provided with the distribution.
249  * 3. The name of the author may not be used to endorse or promote products
250  * derived from this software without specific prior written permission.
251  *
252  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
253  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
254  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
255  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
256  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
257  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
258  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
259  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
260  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
261  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
262  */
263
Popular Tags