Java > Open Source Codes > org > objectweb > medor > optim > rdb > GroupSameDBRule


1 /**
2  * MEDOR: Middleware Enabling Distributed Object Requests
3  *
4  * Copyright (C) 2001-2003 France Telecom R&D
5  * Contact: alexandre.lefebvre@rd.francetelecom.com
6  *
7  * This library is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU Lesser General Public
9  * License as published by the Free Software Foundation; either
10  * version 2.1 of the License, or (at your option) any later version.
11  *
12  * This library is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15  * Lesser General Public License for more details.
16  *
17  * You should have received a copy of the GNU Lesser General Public
18  * License along with this library; if not, write to the Free Software
19  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
20  *
21  * Initial developers: M. Alia, S. Chassande-Barrioz, A. Lefebvre
22  */
23
24 package org.objectweb.medor.optim.rdb;
25
26 import org.objectweb.medor.api.Field;
27 import org.objectweb.medor.api.MedorException;
28 import org.objectweb.medor.api.TupleStructure;
29 import org.objectweb.medor.datasource.api.DataStore;
30 import org.objectweb.medor.expression.api.Expression;
31 import org.objectweb.medor.expression.api.Operator;
32 import org.objectweb.medor.expression.api.Operand;
33 import org.objectweb.medor.expression.lib.And;
34 import org.objectweb.medor.filter.api.FieldOperand;
35 import org.objectweb.medor.filter.jorm.lib.CompositePName;
36 import org.objectweb.medor.filter.jorm.lib.SinglePName;
37 import org.objectweb.medor.filter.lib.MemberOf;
38 import org.objectweb.medor.optim.api.RewriteRule;
39 import org.objectweb.medor.optim.lib.BasicRule;
40 import org.objectweb.medor.query.api.CalculatedField;
41 import org.objectweb.medor.query.api.FilteredQueryTree;
42 import org.objectweb.medor.query.api.NestedField;
43 import org.objectweb.medor.query.api.PropagatedField;
44 import org.objectweb.medor.query.api.QueryLeaf;
45 import org.objectweb.medor.query.api.QueryNode;
46 import org.objectweb.medor.query.api.QueryTree;
47 import org.objectweb.medor.query.api.QueryTreeField;
48 import org.objectweb.medor.query.rdb.api.QualifiedTable;
49 import org.objectweb.medor.query.rdb.api.RdbExpField;
50 import org.objectweb.medor.query.rdb.api.RdbExpQueryLeaf;
51 import org.objectweb.medor.query.rdb.lib.BasicQualifiedTable;
52 import org.objectweb.medor.query.rdb.lib.BasicRdbExpQueryLeaf;
53
54 import java.util.ArrayList ;
55
56 /**
57  * This class groups together as a single RbdExpQueryLeaf the RdbQueryLeaves
58  * working on the same data store.
59  * TODO: Known limitation : This rule does not reorganize a QueryTree
60  * Another rule should be developed to put close together leaves working on the
61  * same data store.
62  */
63 public class GroupSameDBRule extends BasicRule implements RewriteRule {
64     /**
65      * The RdbQuery class represents the result of rewriting a QueryTree.
66      * It has an array of RdbExpFields (its fields), an array of QualifiedTables
67      * (its tables), an Expression working on those Fields, an associated
68      * DataStore and a boolean indicating whether it is a query leaf, or whether
69      * it is the result of merging several QueryLeaves.
70      */
71     protected class RdbQuery {
72         public ArrayList fields;
73         public ArrayList tables;
74         public Expression exp;
75         public DataStore ds;
76         /**
77          * tableIds is the current list of table names (without alias) and
78          * table alias names.
79          */
80         public ArrayList tableIds;
81         public boolean hasSubQuery;
82         public ArrayList subQueries;
83     }
84
85     /**
86      * This class represents the result of splitting the children of
87      * a given QueryTree qt in presence of MemberOf operators
88      * in qt's query filter.
89      * <p>The splitting process is performed by the splitQueries and
90      * recurseSplit methods.
91      */
92     private class SplitQueries {
93         /**
94          * An ArrayList of QueryTrees corresponding to the left part of the
95          * MemberOf.
96          */
97         public ArrayList outerQts;
98         /**
99          * Inner QueryTree: it is an ArrayList of ArrayLists.
100          * <p>There is one such ArrayList for each subquery. Indeed, if there
101          * are several MemberOf operators in the QueryTree's filter, MEDOR has
102          * to generate as many subqueries as there are MemberOf operators. Each
103          * such ArrayList may contain several QueryTrees, namely in case of a
104          * multiple MemberOf. For example, if we have (a, b) MemberOf (c, d),
105          * and c and d are FieldOperands of different QueryTrees, then there
106          * will be an ArrayList containing the two QueryTrees for c and d.s
107          */
108         public ArrayList subQts;
109     }
110
111     /**
112      * Implementation of the RewriteRule interface.
113      * <p>It groups together the RdbQueryLeaves if they are on the same data
114      * store.
115      * @param qt the QueryTree to be rewritten by this rule.
116      * @return the rewritten QueryTree
117      * @throws MedorException if all RdbQueryLeaves are not on the same data
118      * store.
119      * @see RewriteRule
120      */
121     public QueryTree rewrite(QueryTree qt, QueryNode parent)
122             throws MedorException {
123         //TODO propagate the distinct and order by clauses
124 RdbQuery rq = recurseRewrite(qt);
125         debug("end of recurse");
126         if (rq != null) {
127             debug("building RdbLeaf");
128             return buildRdbLeaf(rq, qt);
129         }
130         else
131             return qt;
132     }
133
134     /**
135      * Performs the transformation of a QueryTree.
136      * <p>It performs recursive calls on the QueryTree's schildren.
137      * @param qt is the QueryTree to rewrite.
138      * @return an RdbQuery corresponding to the rewriting.
139      */
140     private RdbQuery recurseRewrite(QueryTree qt) throws MedorException {
141         //debug(qt.getName());
142 if (qt instanceof RdbExpQueryLeaf) {
143             //builds the RdbQuery associated to the Queryleaf
144 debug("RdbExpQueryLeaf: START " + qt.getName());
145             RdbQuery rq = new RdbQuery();
146             Field[] lf = qt.getTupleStructure().getFields();
147             rq.fields = new ArrayList (lf.length);
148             for (int i = 0; i < lf.length; i++) {
149                 rq.fields.add(lf[i]);
150             }
151             QualifiedTable[] lqt = ((RdbExpQueryLeaf) qt).getQualifiedTables();
152             rq.tables = new ArrayList (lqt.length);
153             rq.tableIds = new ArrayList (lqt.length);
154             for (int i = 0; i < lqt.length; i++) {
155                 rq.tables.add(lqt[i]);
156                 if (lqt[i].getAliasName() != null)
157                     rq.tableIds.add(lqt[i].getAliasName());
158                 else
159                     rq.tableIds.add(lqt[i].getTableName());
160             }
161             rq.exp = ((RdbExpQueryLeaf) qt).getQueryFilter();
162             rq.ds = ((RdbExpQueryLeaf) qt).getDataStore();
163             debug("RdbExpQueryLeaf: END " + qt.getName());
164             return rq;
165         }
166         else if (qt instanceof QueryLeaf) {
167             debug("QueryLeaf: " + qt);
168             return null;
169         }
170         //else, it is a QueryNode
171 else if (memberOfInExpression(((QueryNode) qt).getQueryFilter())) {
172             //qt is a QueryNode with memberOf
173 debug("QueryNode with MemberOf: " + qt);
174             SplitQueries split = splitQueries(qt);
175             debug("splitQueries done");
176             debug("Structure of split: "
177                 + "Left: " + split.outerQts.size()
178                 + " Right: " + split.subQts.size()
179             );
180             //deal with the top QueryTree
181 RdbQuery workRq =
182                 exploreQueryTrees((QueryTree[]) split.outerQts.toArray(
183                     new QueryTree[0])
184                 );
185             debug("recursive exploreQueryTrees done");
186             workRq.hasSubQuery = true;
187             if (noCalculation(qt)) {
188                 debug("noCalculation: => continue");
189                 //add exp of current node to the workRq
190 if (workRq.exp == null) {
191                     workRq.exp = ((QueryNode) qt).getQueryFilter();
192                 }
193                 else {
194                     workRq.exp =
195                         new And(workRq.exp, ((QueryNode) qt).getQueryFilter());
196                 }
197                 //construct subqueries
198 workRq.subQueries = new ArrayList ();
199                 debug("number of subqueries: " + split.subQts.size());
200                 for (int i = 0; i < split.subQts.size(); i++) {
201                     RdbQuery innerRq =
202                         exploreQueryTrees((QueryTree[])
203                         ((ArrayList ) split.subQts.get(i)).toArray(
204                             new QueryTree[0])
205                         );
206                     workRq.subQueries.add(innerRq);
207                 }
208
209             }
210             else {
211                 createLeafAndUpdateLinks(workRq, qt);
212                 workRq = null;
213             }
214             return workRq;
215         }
216         else {
217             //qt is a QueryNode without memberOf
218 debug("QueryNode without MemberOf: " + qt);
219             QueryTree[] children = ((QueryNode) qt).getChildren();
220             //recurse on the Children
221 RdbQuery workRq = exploreQueryTrees(children);
222             if (noCalculation(qt)) {
223                 debug("noCalculation: => continue");
224                 //add exp of current node to the workRq
225 if (workRq.exp == null) {
226                     workRq.exp = ((QueryNode) qt).getQueryFilter();
227                 }
228                 else {
229                     workRq.exp =
230                         new And(workRq.exp, ((QueryNode) qt).getQueryFilter());
231                 }
232             }
233             else {
234                 createLeafAndUpdateLinks(workRq, qt);
235                 workRq = null;
236             }
237             debug("QueryNode: END");
238             return workRq;
239         }
240     }
241
242     /**
243      * Breaks the recursion when the QueryTree has calculated fields.
244      * <p>In this case, build a RdbExpQueryLeaf for the children, but not for
245      * the top QueryTree which remains as it is, and for which the links to the
246      * fields are updated to that of the newly created QueryLeaf.
247      * @param workRq the RdbQuery structure containing the children
248      * @param qt the top QueryTree
249      * @throws MedorException in the case of a NestedField.
250      */
251     private void createLeafAndUpdateLinks(RdbQuery workRq, QueryTree qt)
252         throws MedorException {
253         debug("Has calculated field: => stop, create RdbExpQL and link");
254         RdbExpQueryLeaf ql = buildRdbLeaf(workRq, qt);
255         // Upgrade the link between qt and the workRq
256
257         //update fields
258 Field[] fs = qt.getTupleStructure().getFields();
259         TupleStructure ts = ql.getTupleStructure();
260         for (int i = 0; i < fs.length; i++) {
261             if (fs[i] instanceof PropagatedField) {
262                 if (ts.contains(fs[i].getName())) {
263                     debug("Replace in the PropagatedField " + fs[i].getName());
264                     ((QueryNode) qt).updatePropagatedField(
265                         fs[i].getName(),
266                         new QueryTreeField[]{
267                             (QueryTreeField) ts.getField(
268                                 fs[i].getName())});
269                 }
270                 else
271                     debug("Do not replace in the PropagatedField " + fs[i].getName());
272             }
273             else if (fs[i] instanceof CalculatedField) {
274                 debug("Try to replace in the CalculatedField " + fs[i].getName());
275                 Expression e =
276                     ((CalculatedField) fs[i]).getExpression();
277                 if (replaceInFilter(e, ts))
278                     ((QueryNode) qt).updateCalculatedField(
279                         fs[i].getName(), e);
280             }
281             else if (fs[i] instanceof NestedField) {
282                 debug("Replace in the NestedField " + fs[i].getName());
283                 throw new MedorException("Unmanaged Nested Field");
284             }
285         }
286         //update filter
287 if (qt instanceof FilteredQueryTree) {
288             debug("Try to replace in the filter ");
289             Expression e = ((FilteredQueryTree) qt).getQueryFilter();
290             if (replaceInFilter(e, ts))
291                 ((FilteredQueryTree) qt).setQueryFilter(e);
292         }
293     }
294
295     /**
296      * Constructs an RdbQuery corresponding to the recursive exploration and
297      * merging of a given list of QueryTrees.
298      * @param qts the input list of QueryTrees to be explored
299      * @return the RdbQuery constructed by exploring and merging the QueryTrees.
300      * @throws MedorException if some QueryTrees are not on the same data store.
301      */
302     private RdbQuery exploreQueryTrees(QueryTree[] qts) throws MedorException {
303         boolean first = true;
304         RdbQuery workRq = null;
305         for (int i = 0; i < qts.length; i++) {
306             RdbQuery currentRq = recurseRewrite(qts[i]);
307             if (first) {
308                 debug("first");
309                 workRq = currentRq;
310                 first = false;
311             }
312             else if (workRq.ds != null &&
313                 workRq.ds.isSameAs(currentRq.ds)) { //same datastore
314 debug("Same store => merging");
315                 mergeRdbQueries(workRq, currentRq);
316             }
317             else {
318                 throw new MedorException(
319                     "Impossible to group two nodes with different data stores");
320             }
321         }
322         return workRq;
323     }
324
325     /**
326      * Replaces the fields referenced in the expression by the fields of the
327      * tuple structure. This the field name that is used to match the fields
328      * @param e is the expression where the Field referenced by FieldOperand
329      * must be replaced.
330      * @param ts is the tuple structure that contains the fields that replace
331      * the expression fields.
332      * @return true if the expression was modified, otherwise false.
333      * @throws MedorException when the data structure is wrong.
334      */
335     private boolean replaceInFilter(Expression e, TupleStructure ts)
336         throws MedorException {
337         ArrayList al = new ArrayList ();
338         al.add(e);
339         boolean isModified = false;
340         while (!al.isEmpty()) {
341             Expression ex = (Expression) al.remove(0);
342             if (ex instanceof Operator) {
343                 for (int i = 0; i < ((Operator) ex).getOperandNumber(); i++) {
344                     al.add(((Operator) ex).getExpression(i));
345                 }
346             }
347             else if (ex instanceof FieldOperand) {
348                 FieldOperand fo = (FieldOperand) ex;
349                 if (ts.contains(fo.getField().getName())) {
350                     debug("Replace in the FieldOperand: " + fo.getField().getName());
351                     fo.setField(ts.getField(fo.getField().getName()));
352                     isModified = true;
353                 }
354                 else
355                     debug("Do not replace in the FieldOperand: " + fo.getField().getName());
356             }
357         }
358         return isModified;
359     }
360
361     /**
362      * Checks whether a QueryTree contains calculated fields.
363      * <p>
364      * A QueryTree is elligible for being rewritten as an RdbQueryLeaf if all
365      * its children have been rewritten, and if it does not have any calculated
366      * fields.
367      * @param qt the QueryTree for verification
368      * @return true if the QueryTree does not contain calculated fields.
369      */
370     private boolean noCalculation(QueryTree qt) {
371         debug("Testing for calculated fields: ");
372         Field[] qtf = qt.getTupleStructure().getFields();
373         for (int i = 0; i < qtf.length; i++) {
374             if (qtf[i] instanceof CalculatedField) {
375                 debug("found");
376                 return false;
377             }
378         }
379         debug("not found");
380         return true;
381     }
382
383     /**
384      * Merges two RdbQueries.
385      * <p>It has to rename the QualifiedTables if they have the same name.
386      * @param into the RdbQuery into which to merge the other RdbQuery
387      * @param other the RdbQuery to be merged into the first RdbQuery (into
388      * parameter).
389      */
390     private void mergeRdbQueries(RdbQuery into, RdbQuery other) {
391         for (int i = 0; i < other.fields.size(); i++) {
392             into.fields.add(other.fields.get(i));
393         }
394         QualifiedTable qt;
395         for (int i = 0; i < other.tables.size(); i++) {
396             qt = (QualifiedTable) other.tables.get(i);
397             if (into.tables.contains(qt)) {
398                 //The actual same object is used in another query tree. It needs
399 //to be replaced, and all references to qt in the fields
400 QualifiedTable qt1 =
401                     new BasicQualifiedTable(qt.getTableName(),
402                         qt.getAliasName());
403                 for (int j = 0; j < other.fields.size(); j++) {
404                     if (((RdbExpField) other.fields.get(j)).getTable() == qt)
405                         ((RdbExpField) other.fields.get(j)).setTable(qt1);
406                 }
407                 qt = qt1;
408             }
409             //checks aliases: if it has an alias, that alias must not already
410 //exist
411 if (qt.getAliasName() != null) {
412                 if (into.tableIds.contains(qt.getAliasName()))
413                     qt.setAliasName(generateAlias(into.tableIds,
414                         qt.getAliasName()));
415             }
416             else if (into.tableIds.contains(qt.getTableName()))
417                 qt.setAliasName(generateAlias(into.tableIds,
418                     qt.getTableName()));
419             into.tables.add(qt);
420         }
421         if (into.exp == null) //into.exp is null. Take other.exp
422 into.exp = other.exp;
423         else if (other.exp != null) //into.ext and other.exp are not null
424 into.exp = new And(into.exp, other.exp);
425     }
426
427     /**
428      * Generates an alias from a root name given existing table identifiers.
429      * <p>The generated alias is new, i.e., it should not already be in the
430      * existing table identifiers.
431      * <p>The new alias is added to the existing table identifiers.
432      * @param tableIds the existing table identifiers.
433      * @param root the String root for building the new identifier.
434      * @return an new alias based on root.
435      */
436     private String generateAlias(ArrayList tableIds, String root) {
437         root += "_";
438         int i = 1;
439         while (tableIds.contains(root + i)) {
440             i++;
441         }
442         root += i;
443         tableIds.add(root);
444         return root;
445     }
446
447     /**
448      * Parses an Expression to detect the presence of a MemberOf operator.
449      * @param e is the Expression to be parsed.
450      * @return true if the Expression contains a MemberOf, NotMemberof, IsEmpty
451      * or IsNotEmpty operator.
452      */
453     private boolean memberOfInExpression(Expression e) {
454         debug("entering memberOfInExpression");
455         if (e instanceof MemberOf)
456             return true;
457         else if (e instanceof Operator) {
458             Operator op = (Operator) e;
459             boolean found = false;
460             for (int i = 0; i < op.getOperandNumber(); i++) {
461                 if (memberOfInExpression(op.getExpression(i))) {
462                     found = true;
463                     break;
464                 }
465             }
466             return found;
467         }
468         return false;
469     }
470
471     /**
472      * Constructs an RdbExpQueryLeaf from the result of grouping
473      * the RdbExpQueryLeaves of a QueryTree, expressed as an RdbQuery.
474      * @param rq is the RdbQuery representation of the QueryTree for which the
475      * RdbExpQueryLeaves have to be grouped.
476      * @return the RdbExpQueryLeaf obtained when grouping the RdbExpQueryLeaves
477      * of the original QueryTree
478      */
479     private RdbExpQueryLeaf buildRdbLeaf(RdbQuery rq, QueryTree qt)
480         throws MedorException {
481         RdbExpQueryLeaf ql;
482         if (rq.hasSubQuery) {
483             ql = new BasicRdbExpQueryLeaf(
484                 rq.ds,
485                 (QualifiedTable[]) rq.tables.toArray(new QualifiedTable[0]),
486                 qt.getName()
487             );
488             ql.setQueryFilter(rq.exp);
489             for (int i = 0; i < rq.fields.size(); i++) {
490                 ql.addRdbField((RdbExpField) rq.fields.get(i));
491             }
492             for (int i = 0; i < rq.subQueries.size(); i++) {
493                 BasicRdbExpQueryLeaf subql = new BasicRdbExpQueryLeaf(
494                     rq.ds,
495                     (QualifiedTable[])
496                     ((RdbQuery) rq.subQueries.get(i)).tables.toArray(
497                         new QualifiedTable[0]),
498                     qt.getName());
499                 replaceInFilter(ql.getQueryFilter(), subql.getTupleStructure());
500             }
501         }
502         else {
503             ql = new BasicRdbExpQueryLeaf(
504                 rq.ds,
505                 (QualifiedTable[]) rq.tables.toArray(new QualifiedTable[0]),
506                 qt.getName());
507             //System.out.println(ExpressionPrinter.e2str(rq.exp));
508 ql.setQueryFilter(rq.exp);
509             for (int i = 0; i < rq.fields.size(); i++) {
510                 ql.addRdbField((RdbExpField) rq.fields.get(i));
511             }
512         }
513
514         return ql;
515     }
516
517     /**
518      * For a given QueryTree with an identified MemberOf operator in its query
519      * filter, constructs a SplitQueries.
520      * @param qt the QueryTree to be split
521      * @return the new SplitQueries
522      * @see SplitQueries
523      */
524     private SplitQueries splitQueries(QueryTree qt) {
525         SplitQueries split = new SplitQueries();
526         split.outerQts = new ArrayList ();
527         split.subQts = new ArrayList ();
528         Expression e = ((QueryNode) qt).getQueryFilter();
529         return recurseSplit(split, e);
530     }
531
532     /**
533      * Performs the actual work of splitting a QueryTree starting from its
534      * expression.
535      * @param split the input SplitQueries object
536      * @param e the Expression from which to build the SplitQueries
537      * @return the SplitQueries object constructed from the Expression
538      * @see SplitQueries
539      */
540     private SplitQueries recurseSplit(SplitQueries split, Expression e) {
541         if (e instanceof FieldOperand) {
542             QueryTreeField f = (QueryTreeField) ((FieldOperand) e).getField();
543             QueryTree qtf = f.getQueryTree();
544             if (!split.outerQts.contains(qtf))
545                 split.outerQts.add(qtf);
546         }
547         else if ((e instanceof CompositePName) ||
548             (e instanceof SinglePName) ||
549             (e instanceof Operand)) {
550             return split;
551         }
552         else if (e instanceof MemberOf) {
553             debug("splitting MemberOf");
554             MemberOf mo = (MemberOf) e;
555             int moSize = mo.getOperandNumber() / 2;
556             //iterate on all pairs of Fields
557 for (int i = 0; i < moSize; i++) {
558                 if (((MemberOf) e).getExpression(i) instanceof FieldOperand) {
559                     QueryTreeField fLeft =
560                         (QueryTreeField)
561                         ((FieldOperand)
562                         ((MemberOf) e).getExpression(i)).getField();
563                     QueryTree qtfLeft = fLeft.getQueryTree();
564                     debug("Left node is " + qtfLeft.getName());
565                     if (!split.outerQts.contains(qtfLeft))
566                         split.outerQts.add(qtfLeft);
567                 }
568             }
569             ArrayList newSub = null;
570             for (int i = 0; i < moSize; i++) {
571                 QueryTreeField fRight =
572                     (QueryTreeField)
573                     ((FieldOperand)
574                     ((MemberOf) e).getExpression(i + moSize)).getField();
575                 QueryTree qtfRight = fRight.getQueryTree();
576                 debug("Right node is " + qtfRight.getName());
577                 //remove the right QT from outer QT if it is in it
578 if (split.outerQts.contains(qtfRight))
579                     split.outerQts.remove(qtfRight);
580                 //search whether right QT already in subQts or not
581 //if not, add it
582 boolean isInSub = false;
583                 for (int j = 0; j < split.subQts.size(); j++) {
584                     if (((ArrayList ) split.subQts.get(j)).contains(qtfRight)) {
585                         isInSub = true;
586                         break;
587                     }
588                 }
589                 debug("found in subqueries:" + isInSub);
590                 if (!isInSub) {
591                     if (newSub == null)
592                         newSub = new ArrayList (1);
593                     newSub.add(qtfRight);
594                 }
595             }
596             if (newSub != null)
597                 split.subQts.add(newSub);
598             return split;
599         }
600         else if (e instanceof Operator) {
601             Operator op = (Operator) e;
602             for (int i = 0; i < op.getOperandNumber(); i++) {
603                 split = recurseSplit(split, op.getExpression(i));
604             }
605             return split;
606         }
607
608         return split;
609     }
610
611     private static final void debug(String msg) {
612         //System.out.println(msg);
613 }
614 }
615

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags