AlgebraManager


1   /*
2    * This file belongs to the XQuark distribution.
3    * Copyright (C) 2003 Universite de Versailles Saint-Quentin.
4    * 
5    * This program is free software; you can redistribute it and/or
6    * modify it under the terms of the GNU Lesser General Public
7    * License as published by the Free Software Foundation; either
8    * version 2.1 of the License, or (at your option) any later version.
9    * 
10   * This program is distributed in the hope that it will be useful,
11   * but WITHOUT ANY WARRANTY; without even the implied warranty of
12   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13   * Lesser General Public License for more details.
14   * 
15   * You should have received a copy of the GNU Lesser General Public
16   * License along with this program; if not, write to the Free Software
17   * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307.
18   * You can also get it at http://www.gnu.org/licenses/lgpl.html
19   * 
20   * For more information on this software, see http://www.xquark.org.
21   */
22  
23  package org.xquark.mediator.algebra;
24  
25  import java.util.ArrayList  ;
26  import java.util.HashMap  ;
27  import java.util.List  ;
28  
29  import org.xquark.mediator.decomposer.AlgebraStructureVisitor;
30  import org.xquark.mediator.decomposer.GetVariablePathsVisitor;
31  import org.xquark.mediator.plan.ExecutionPlan;
32  import org.xquark.mediator.plan.OpSubQuery;
33  import org.xquark.mediator.plan.Operator;
34  import org.xquark.mediator.runtime.MediatorException;
35  import org.xquark.xquery.metadata.MetaDataImpl;
36  import org.xquark.xquery.parser.*;
37  import org.xquark.xquery.parser.util.Constants;
38  import org.xquark.xquery.typing.*;
39  
40  /**
41   * This class is designed to handle dependancies and reduction
42   * of requests. It identifies sources and is the pre-transformation before
43   * generating the execution plan.
44   * <p>The structure is as follows at initialization :</p>
45   * <ul>
46   *    <li> There is an array of DepNodes where each DepNode is associated to
47   *      one QDB.</li>
48   *    <li> for each DepNode, there is a DepLeaf (that can be a DepVar or
49   *      a DepSource) that is associated to the variables of the
50   *      FLWR expression of the QDB.</li>
51   * </ul>
52   *
53   */
54  public class AlgebraManager {
55      // **********************************************************************
56      // * VERSIONING
57      // **********************************************************************
58      private static final String   RCSRevision = "$Revision: 1.16 $";
59      private static final String   RCSName = "$Name:  $";
60  
61      // **********************************************************************
62      // * CLASS VARIABLES
63      // **********************************************************************
64  
65      private ArrayList   depnodes = null;
66      private TypeVisitor typevisitor = null;
67      private ExecutionPlan plan = null;
68      // make correspondance on variable and DepNode that handle it
69      private HashMap   mapnode = null;
70      private XQueryExpression qmem = null;
71      private boolean isQmemRoot = false;
72      private ArrayList   mainvars = null;
73      private ArrayList   idvars = null;
74      private HashMap   mappath = null;
75      private ArrayList   pathlist = null;
76      private MetaDataImpl metadata = null;
77      //protected HashMap aliases = null;
78      //protected HashMap dependvarmap = null;
79      private AlgFLWR currentDepFLWR = null;
80      private GetVariablePathsVisitor gvpvisitor = null;
81      private ArrayList   scopeVariables = new ArrayList  ();
82  
83      // ******************************************************************
84      // * INITIALISATION
85      // ******************************************************************
86      /**
87       *
88       * @param metadata
89       * @param typevisitor
90       * @param qmem
91       */
92      public AlgebraManager(ExecutionPlan plan, MetaDataImpl metadata, TypeVisitor typevisitor, XQueryExpression qmem, ArrayList   mainvars, ArrayList   idvars) throws MediatorException {
93          this.typevisitor = typevisitor;
94          this.metadata = metadata;
95          this.depnodes = new ArrayList  ();
96          this.mapnode = new HashMap  ();
97          this.plan = plan;
98          this.qmem = qmem;
99          this.isQmemRoot = qmem.getRoot();
100         this.mainvars = mainvars;
101         this.idvars = idvars;
102         mappath = new HashMap  ();
103         pathlist = new ArrayList  ();
104     }
105 
106     // ************************************************************************
107     // * GET/SET METHODS
108     // ************************************************************************
109     public MetaDataImpl getMetaData() {
110         return metadata;
111     }
112     //public XQueryExpression getQMem() { return qmem ; }
113     //public ArrayList getNodes() { return depnodes ; }
114     public TypeVisitor getTypeVisitor() {
115         return typevisitor;
116     }
117     public ArrayList   getIdVars() {
118         return idvars;
119     }
120     public HashMap   getVarPaths() {
121         return mappath;
122     }
123     public ExecutionPlan getPlan() {
124         return plan;
125     }
126 
127     public void addVarsToScope(List   vars) {
128         if (vars == null)
129             return;
130         for (int i = 0; i < vars.size(); i++)
131             addVarToScope((Variable) vars.get(i));
132     }
133 
134     public void removeVarsFromScope(List   vars) {
135         scopeVariables.removeAll(vars);
136     }
137 
138     public void addVarToScope(Variable var) {
139         if (!this.scopeVariables.contains(var))
140             scopeVariables.add(var);
141     }
142 
143     public void removeVarFromScope(Variable var) {
144         scopeVariables.remove(var);
145     }
146 
147     public ArrayList   getScopeVariables() {
148         return scopeVariables;
149     }
150     // ************************************************************************
151     // * CONSTRUCT THE DEPENDENCY TREE (accessed by MediatorStatement)
152     // ************************************************************************
153 
154     /** start <code>AlgebraStructureVisitor</code> to visit all the QDBs
155      */
156     public void generate() throws MediatorException {
157         try {
158             AlgebraStructureVisitor asv = new AlgebraStructureVisitor(this);
159             for (int k = 0; k < mainvars.size(); k++)
160                  ((Variable) mainvars.get(k)).accept(asv);
161         } catch (XQueryException e) {
162             throw new MediatorException("Could not build structure to construct algebra", e);
163         }
164     }
165     /** to be commented ... : fills mappath , modify depnodes */
166 
167     public void computeVarPaths() throws MediatorException, XQueryException {
168         if (gvpvisitor == null)
169             gvpvisitor = new GetVariablePathsVisitor(true, this.mappath, this.pathlist);
170         for (int i = 0; i < depnodes.size(); i++) {
171             Algebra depnode = (Algebra) depnodes.get(i);
172             if (depnode instanceof AlgFLWR) {
173                 if (((AlgFLWR) depnode).isQDB()) {
174                     gvpvisitor.setRootQDB(depnode.isRootQDB());
175                     gvpvisitor.setQDB(depnode.isQDB());
176                     gvpvisitor.setMonoSource(depnode.isMonoSource());
177                     if (depnode.isMonoSource())
178                         gvpvisitor.setCurrentList(((FLWRExpression) depnode.getExpression()).getVariables());
179                     else
180                         gvpvisitor.resetCurrentVarList();
181                     depnode.getExpression().accept(gvpvisitor);
182                 }
183             }
184         }
185         gvpvisitor.setRootQDB(false);
186         gvpvisitor.setQDB(false);
187         gvpvisitor.setMonoSource(false);
188         gvpvisitor.resetCurrentVarList();
189         qmem.accept(gvpvisitor);
190         mappath = gvpvisitor.getVarPaths();
191         pathlist = gvpvisitor.getPathStrList();
192         for (int i = 0; i < depnodes.size(); i++) {
193             Algebra depnode = (Algebra) depnodes.get(i);
194             if (depnode instanceof AlgFLWR && ((AlgFLWR) depnode).isRootQDB())
195                 depnode.setPaths();
196         }
197     }
198 
199     /**
200      * Add a new QDB in the dependency tree. (create a AlgMem)
201      *
202      * @param expression
203      * @param var
204      */
205     public AlgFLWR addQDB(Variable var, boolean islet) throws MediatorException {
206         return addQDB(var.getExpression(), var, islet);
207     }
208     public AlgFLWR addQDB(XQueryExpression expression, Variable var, boolean islet) throws MediatorException {
209         currentDepFLWR = new AlgFLWR(expression, var, this, islet);
210         depnodes.add(currentDepFLWR);
211         addMapNode(var, currentDepFLWR);
212         return currentDepFLWR;
213     }
214 
215     /**
216      * Add a new Variable in the dependency tree. (create a AlgVar)
217      *
218      * @param expression
219      * @param var
220      */
221     public AlgVar addVar(Variable addvar, Variable var, boolean islet) throws MediatorException {
222         AlgVar depvar = new AlgVar(addvar, var, this, islet);
223         depnodes.add(depvar);
224         addMapNode(var, depvar);
225         return depvar;
226     }
227 
228     /**
229      * Add a new Source in the dependency tree. (create a AlgSource)
230      *
231      * @param expression
232      * @param var
233      */
234     public AlgSource addSource(XQueryExpression expression, Variable var, boolean islet) throws MediatorException {
235         ArrayList   variables = null;
236         if (var != null) {
237             variables = new ArrayList  (1);
238             variables.add(var);
239         }
240         if (var == null)
241             return addSource(expression, variables, islet);
242         return addSource(var.getParentFLWRExpression(), variables, islet);
243     }
244     public AlgSource addSource(XQueryExpression expression, ArrayList   variables, boolean islet) throws MediatorException {
245         AlgSource source = null;
246         Variable var = null;
247         if (variables == null || variables.isEmpty()) {
248             try {
249                 var = typevisitor.getStaticContext().createVariable(Constants.FOR_BINDINGTYPE, expression,Variable.DEPMAN_CREATOR);
250                 //var = this.createVariable(Constants.FOR_BINDINGTYPE, expression, this.typevisitor);
251                 ArrayList   vars = new ArrayList  (1);
252                 vars.add(var);
253                 mappath.put(var, vars);
254                 pathlist.add(var.getStringValue());
255                 FLWRExpression tmpFlwr = new FLWRExpression(vars, null, var, null);
256                 tmpFlwr.setParentModule(expression.getParentModule());
257                 source = new AlgSource(tmpFlwr, var, this, islet);
258             } catch (XQueryException e) {
259                 throw new MediatorException("Could not create variable", e);
260             }
261         } else
262             source = new AlgSource(expression, variables, this, islet);
263         depnodes.add(source);
264         if (variables == null || variables.isEmpty())
265             addMapNode(var, source);
266         else
267             for (int i = 0; i < variables.size(); i++)
268                 addMapNode((Variable) variables.get(i), source);
269         return source;
270     }
271 
272     /**
273      * Add a new Eval in the dependency tree. (create a AlgEval)
274      *
275      * @param expression
276      * @param var
277      */
278     public AlgSourceEval addSourceEval(XQueryExpression expression, Variable var, boolean islet) throws MediatorException {
279         ArrayList   variables = null;
280         if (var != null) {
281             variables = new ArrayList  (1);
282             variables.add(var);
283         }
284         if (var == null)
285             return addSourceEval(expression, variables, islet);
286         return addSourceEval(var.getParentFLWRExpression(), variables, islet);
287     }
288     public AlgSourceEval addSourceEval(XQueryExpression expression, ArrayList   variables, boolean islet) throws MediatorException {
289         AlgSourceEval source = null;
290         Variable var = null;
291         if (variables == null || variables.isEmpty()) {
292             try {
293                 var = typevisitor.getStaticContext().createVariable(Constants.FOR_BINDINGTYPE, expression,Variable.DEPMAN_CREATOR);
294                 //var = this.createVariable(Constants.FOR_BINDINGTYPE, expression, this.typevisitor);
295                 ArrayList   vars = new ArrayList  (1);
296                 vars.add(var);
297                 mappath.put(var, vars);
298                 pathlist.add(var.getStringValue());
299                 FLWRExpression tmpFlwr = new FLWRExpression(vars, null, var, null);
300                 tmpFlwr.setParentModule(expression.getParentModule());
301                 source = new AlgSourceEval(tmpFlwr, var, this, islet);
302             } catch (XQueryException e) {
303                 throw new MediatorException("Could not create variable", e);
304             }
305         } else
306             source = new AlgSourceEval(expression, variables, this, islet);
307         depnodes.add(source);
308         if (variables == null || variables.isEmpty())
309             addMapNode(var, source);
310         else
311             for (int i = 0; i < variables.size(); i++)
312                 addMapNode((Variable) variables.get(i), source);
313         return source;
314     }
315 
316     /**
317      * Add a new Sequence in the dependency tree. (create a AlgSequence)
318      *
319      * @param expression
320      * @param var
321      */
322     public AlgSequence addSequence(XQueryExpressionSequence expression, Variable var, boolean islet) throws MediatorException {
323         AlgSequence depsequence = new AlgSequence(expression, var, this, islet);
324         //depfunction.generate(metadata) ;
325         depnodes.add(depsequence);
326         addMapNode(var, depsequence);
327         return depsequence;
328     }
329 
330     /**
331      * Add a new union in the dependency tree. (create a AlgUnion)
332      *
333      * @param expression
334      * @param var
335      */
336     public AlgUnion addUnion(ListOpUNIONExpression expression, Variable var, boolean islet) throws MediatorException {
337         AlgUnion depunion = new AlgUnion(expression, var, this, islet);
338         //depfunction.generate(metadata) ;
339         depnodes.add(depunion);
340         addMapNode(var, depunion);
341         return depunion;
342     }
343 
344     /**
345      * Add a new Function-Source in the dependency tree. (create a AlgFunction)
346      *
347      * @param expression
348      * @param var
349      */
350     public AlgFunction addFunction(XQueryExpression expression, Variable var, boolean islet) throws MediatorException {
351         AlgFunction depfunction = new AlgFunction(expression, var, this, islet);
352         //depfunction.generate(metadata) ;
353         depnodes.add(depfunction);
354         addMapNode(var, depfunction);
355         return depfunction;
356     }
357 
358     /**
359      * Add a new Arith Function-Source in the dependency tree. (create a AlgArithFunction)
360      *
361      * @param expression
362      * @param var
363      */
364     public AlgArithFunction addArithFunction(ListOpArithExpression expression, Variable var, boolean islet) throws MediatorException {
365         AlgArithFunction deparithfunction = new AlgArithFunction(expression, var, this, islet);
366         //depfunction.generate(metadata) ;
367         depnodes.add(deparithfunction);
368         addMapNode(var, deparithfunction);
369         return deparithfunction;
370     }
371 
372     /**
373      * Add a new Value in the dependency tree. (create a AlgValue)
374      *
375      * @param expression
376      * @param var
377      */
378     public AlgValue addValue(XQueryExpression expression, Variable var, boolean islet) throws MediatorException { // fillMapPath(expression) ;
379         AlgValue depvalue = new AlgValue(expression, var, this, islet);
380         depnodes.add(depvalue);
381         addMapNode(var, depvalue);
382         return depvalue;
383     }
384 
385     /**
386      * Add a new Value in the dependency tree. (create a OpValue)
387      *
388      * @param expression
389      * @param var
390      */
391     public AlgEval addEval(XQueryExpression expression, Variable var, boolean islet) throws MediatorException { // fillMapPath(expression) ;
392         AlgEval depeval = new AlgEval(expression, var, this, islet);
393         depnodes.add(depeval);
394         addMapNode(var, depeval);
395         return depeval;
396     }
397 
398     /**
399      * Add a new Value in the dependency tree. (create a AlgFLWR)
400      *
401      * @param expression
402      * @param var
403      */
404     public AlgFLWR addFlwr(XQueryExpression expression, Variable var, boolean islet) throws MediatorException {
405         AlgFLWR depflwr = new AlgFLWR(expression, var, this, islet);
406         depnodes.add(depflwr);
407         addMapNode(var, depflwr);
408         return depflwr;
409     }
410 
411     /**
412      * Add a new Value in the dependency tree. (create a AlgValue)
413      *
414      * @param expression
415      * @param var
416      */
417     public AlgLocated addLocated(LocatedExpression expression, Variable addvar, Variable var, boolean islet) throws MediatorException {
418         AlgLocated deplocated = new AlgLocated(expression, addvar, var, this, islet);
419         depnodes.add(deplocated);
420         addMapNode(var, deplocated);
421         return deplocated;
422     }
423 
424     /**
425      *
426      * @param variable
427      * @param node
428      */
429     private void addMapNode(Variable variable, Algebra node) throws MediatorException {
430         if (variable != null)
431             mapnode.put(variable, node);
432     }
433 
434     /**
435      *
436      * @param variable
437      */
438     public Algebra getMapNode(Variable variable) {
439         Algebra newnode = (Algebra) mapnode.get(variable);
440         //if (newnode == null) throw new MediatorException("DepManager.getMapNode:  no matching node to " + variable) ;
441         return newnode;
442     }
443 
444     /**
445      *
446      * @param var
447      * @return
448      */
449     public ArrayList   getPathsfromVar(Variable var) {
450         return (ArrayList  ) mappath.get(var);
451     }
452 
453     public ArrayList   getPathsList() {
454         return this.pathlist;
455     }
456 
457     /**
458      *
459      * @param var
460      * @return
461      */
462     public GetVariablePathsVisitor getGVPVisitor() {
463         return gvpvisitor;
464     }
465 
466     // ******************************************************************
467     // * OPTIMISATIONS
468     // ******************************************************************
469     /**
470      * Optimising by regrouping by sources if useful.
471      */
472     /*
473     public void optimize() {
474         // TODO start optimising by regrouping by sources if useful.
475     }
476     */
477     // ******************************************************************
478     // MAKING EXECUTION PLAN
479     // ******************************************************************
480     /**
481      * The execution plan is done by identifying the root node(s).
482      * The whole tree come with it (with help of variable referencedBy
483      * defined in DepNode).
484      * @param connection
485      * @return
486      */
487 
488     public ExecutionPlan FillPlan() throws MediatorException {
489         ArrayList   roots = new ArrayList  ();
490         for (int i = 0; i < depnodes.size(); i++) {
491             Algebra depnode = (Algebra) depnodes.get(i);
492             if (depnode instanceof AlgFLWR && ((AlgFLWR) depnode).isRootQDB()) {
493                 Operator tmpalgebra = (Operator) depnode.createOperator(plan);
494                 if (tmpalgebra != null)
495                     if (this.isQmemRoot)
496                         roots.add(tmpalgebra);
497                     else
498                         plan.setRoot(tmpalgebra);
499             }
500         }
501         if (roots.size() == 1)
502             plan.setRoot((Operator) roots.get(0));
503         else if (roots.size() > 1)
504             plan.setRoot(new OpSubQuery(plan, null, (Operator[])roots.toArray(new Operator[0]), false, true));
505         return plan;
506     }
507 
508 //  private int varIndex = 0;
509 //  private Variable createVariable(int bindingType, XQueryExpression expr, TypeVisitor typeVisitor) throws XQueryException {
510 //      if (typeVisitor != null && expr != null)
511 //          expr.accept(typeVisitor);
512 //      Variable var = new Variable(new QName(null, null, "var_depman" + (++varIndex), expr.getParentModule()), expr.getParentModule());
513 //      var.setBindingType(bindingType);
514 //      var.setExpression(expr);
515 //      return var;
516 //  }
517 
518     // ******************************************************************
519     // * DEBUGGING
520     // ******************************************************************
521     /**
522      *
523      * @return
524      */
525     public String   toString() {
526         StringBuffer   buf = new StringBuffer  ();
527         buf.append("<DepManager>\n");
528         for (int i = 0; i < mainvars.size(); i++) {
529             Algebra depnode = (Algebra) mapnode.get(mainvars.get(i));
530             if (depnode instanceof AlgFLWR && ((AlgFLWR) depnode).isQDB())
531                 buf.append(depnode.toCompleteString(1));
532         }
533         //      for (int i = 0; i < depnodes.size(); i++) {
534         //          DepNode depnode = (DepNode) depnodes.get(i);
535         //          if (depnode instanceof DepFLWR && ((DepFLWR) depnode).isQDB())
536         //              buf.append(depnode.toCompleteString(1));
537         //      }
538         buf.append("</DepManager>\n");
539         return buf.toString();
540     }
541 }
542
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags