| package org.apache.rya.indexing.pcj.matching; |
| |
| /* |
| * Licensed to the Apache Software Foundation (ASF) under one |
| * or more contributor license agreements. See the NOTICE file |
| * distributed with this work for additional information |
| * regarding copyright ownership. The ASF licenses this file |
| * to you under the Apache License, Version 2.0 (the |
| * "License"); you may not use this file except in compliance |
| * with the License. You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, |
| * software distributed under the License is distributed on an |
| * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY |
| * KIND, either express or implied. See the License for the |
| * specific language governing permissions and limitations |
| * under the License. |
| */ |
| import java.util.ArrayList; |
| import java.util.Collections; |
| import java.util.Comparator; |
| import java.util.HashMap; |
| import java.util.List; |
| import java.util.Map; |
| import java.util.Set; |
| import java.util.TreeMap; |
| |
| import org.apache.rya.api.domain.VarNameUtils; |
| import org.eclipse.rdf4j.model.Value; |
| import org.eclipse.rdf4j.query.algebra.Filter; |
| import org.eclipse.rdf4j.query.algebra.NAryValueOperator; |
| import org.eclipse.rdf4j.query.algebra.ProjectionElem; |
| import org.eclipse.rdf4j.query.algebra.ProjectionElemList; |
| import org.eclipse.rdf4j.query.algebra.QueryModelNode; |
| import org.eclipse.rdf4j.query.algebra.StatementPattern; |
| import org.eclipse.rdf4j.query.algebra.TupleExpr; |
| import org.eclipse.rdf4j.query.algebra.ValueConstant; |
| import org.eclipse.rdf4j.query.algebra.ValueExpr; |
| import org.eclipse.rdf4j.query.algebra.Var; |
| import org.eclipse.rdf4j.query.algebra.helpers.AbstractQueryModelVisitor; |
| |
| import com.google.common.collect.Lists; |
| import com.google.common.collect.Maps; |
| |
| public class QueryVariableNormalizer { |
| |
| |
| /** |
| * @param tuple1 |
| * tuple expression from a parsed query |
| * @param tuple2 |
| * tuple expression from a parsed query (the proposed index whose |
| * variables are to be relabeled) |
| * @return list of all possible tuples obtained by substituting the |
| * variables of proposed index with the variables from query |
| * @throws Exception |
| * @throws IllegalArgumentException |
| */ |
| public static List<TupleExpr> getNormalizedIndex(TupleExpr tuple1, TupleExpr tuple2) throws Exception { |
| |
| List<QueryModelNode> nodes1, nodes2; |
| TreeMap<String, List<QueryModelNode>> queryMap1, indexMap1; |
| List<HashMap<String, String>> varChanges = new ArrayList<HashMap<String, String>>(); |
| List<TupleExpr> tupleList = new ArrayList<TupleExpr>(); |
| |
| |
| |
| // if tuples are equal, no need to do anything |
| if (tuple1.equals(tuple2)) { |
| tupleList.add(tuple1.clone()); |
| return tupleList; |
| } |
| |
| |
| NormalizeQueryVisitor tupNVis = new NormalizeQueryVisitor(false); |
| NormalizeQueryVisitor indexNVis = new NormalizeQueryVisitor(true); |
| tuple1.visit(tupNVis); |
| tuple2.visit(indexNVis); |
| |
| |
| TupleExpr tuple; |
| queryMap1 = tupNVis.getMap(); |
| indexMap1 = indexNVis.getMap(); |
| |
| // TreeMaps that used for comparators |
| TreeMap<String, Integer>[] trees = (TreeMap<String, Integer>[]) new TreeMap[4]; |
| for (int i = 0; i < 4; i++) { |
| trees[i] = new TreeMap<String, Integer>(); |
| } |
| |
| trees[0] = tupNVis.getKeyMap(); // query tuple variable count |
| trees[2] = indexNVis.getKeyMap(); // index tuple variable count |
| |
| |
| // if query does not contain as many constant Vars as index, |
| // normalization not possible. |
| // if (!(trees[0].keySet().size() >= trees[2].keySet().size())) { |
| // System.out.println("In here:1"); |
| // return tupleList; |
| // } |
| |
| // sort keys according to size of associated StatementPattern list |
| // this optimization ensures that initial list of HashMaps (possible |
| // variable substitutions) |
| // is as small as possible |
| // Maybe add additional criteria to comparator taking into account size |
| // of query bin lists |
| Set<String> keys = indexMap1.keySet(); |
| List<String> keyList = new ArrayList<String>(keys); |
| Collections.sort(keyList, new ConstantKeyComp(indexMap1, queryMap1)); |
| |
| // iterate through constant values associated with smaller tuple, |
| // check that larger tuple constants these constants, and use lists |
| // of associated statement patterns to begin to construct variable |
| // substitutions |
| // that are consistent |
| |
| for (String s : keyList) { |
| if (queryMap1.containsKey(s)) { |
| nodes1 = queryMap1.get(s); |
| nodes2 = indexMap1.get(s); |
| |
| |
| if (!(nodes1.size() >= nodes2.size())) { |
| // System.out.println("In here: 2"); |
| // System.out.println("Node lists are " + nodes1 + " and " + |
| // nodes2); |
| return tupleList; |
| } |
| |
| trees[1] = getListVarCnt(nodes1, tupNVis.getVariableMap()); // query |
| // list |
| // variable |
| // count |
| trees[3] = getListVarCnt(nodes2, indexNVis.getVariableMap()); // index |
| // list |
| // variable |
| // count |
| Collections.sort(nodes1, new CountComp(trees[1], trees[0])); |
| Collections.sort(nodes2, new CountComp(trees[3], trees[2])); |
| |
| varChanges = statementCompare(nodes1, nodes2, varChanges, trees); |
| |
| if (varChanges.size() == 0) { |
| return tupleList; |
| } |
| } |
| |
| else { |
| return tupleList; |
| } |
| |
| } |
| |
| List<QueryModelNode> filters2 = indexNVis.getFilters(); |
| // determine if index contains filters whose variables need to be relabeled |
| if (filters2.size() != 0) { |
| List<QueryModelNode> filters1 = tupNVis.getFilters(); |
| // only attempt to normalize variables if query contains more filters than index |
| if (filters1.size() >= filters2.size()) { |
| Collections.sort(filters1, new FilterComp()); |
| Collections.sort(filters2, new FilterComp()); |
| |
| varChanges = statementCompare(filters1, filters2, varChanges, trees); |
| |
| } |
| } |
| |
| List<HashMap<String, String>> varChangeSet = new ArrayList<HashMap<String, String>>(); |
| |
| for (HashMap<String, String> s : varChanges) { |
| if (!varChangeSet.contains(s)) { |
| varChangeSet.add(s); |
| } |
| |
| } |
| |
| |
| ValueMapVisitor valMapVis = new ValueMapVisitor(); |
| tuple1.visit(valMapVis); |
| Map<String, Value> valMap = valMapVis.getValueMap(); |
| |
| |
| for (HashMap<String, String> s : varChangeSet) { |
| //System.out.println(s); |
| tuple = tuple2.clone(); |
| replaceTupleVariables(s, tuple, valMap); |
| tupleList.add(tuple); |
| } |
| |
| return tupleList; |
| |
| } |
| |
| /** |
| * Produces a list of all possible substitutions stored in HashMaps that are |
| * consistent with the two lists of statement patterns |
| * |
| * @param qArray |
| * list of Statement nodes from query tuple |
| * @param iArray |
| * list of Statement nodes from index tuple |
| * @param hMaps |
| * HashMap containing variable substitutions |
| * @param trees |
| * TreeMaps used for statement pattern node ordering |
| * @return |
| */ |
| private static List<HashMap<String, String>> statementCompare(List<QueryModelNode> qArray, |
| List<QueryModelNode> iArray, List<HashMap<String, String>> hMaps, TreeMap<String, Integer>[] trees) { |
| |
| if (hMaps.size() == 0) { |
| HashMap<HashMap<String, String>, Boolean> mapConsistent = new HashMap<HashMap<String, String>, Boolean>(); |
| HashMap<String, String> hMap = new HashMap<String, String>(); |
| mapConsistent.put(hMap, false); |
| evaluateMap(qArray, iArray, hMap, hMaps, mapConsistent, trees); |
| |
| return hMaps; |
| } |
| |
| else { |
| |
| ArrayList<HashMap<String, String>> tempMaps = Lists.newArrayList(hMaps); |
| HashMap<HashMap<String, String>, Boolean> mapConsistent = new HashMap<HashMap<String, String>, Boolean>(); |
| for (HashMap<String, String> s : hMaps) { |
| mapConsistent.put(s, false); |
| } |
| for (HashMap<String, String> s : hMaps) { |
| evaluateMap(qArray, iArray, s, tempMaps, mapConsistent, trees); |
| } |
| |
| return tempMaps; |
| |
| } |
| } |
| |
| |
| /** |
| * Adds or removes HashMap substitution schemes to the list of substitutions |
| * schemes depending on whether or not they are consistent with the two |
| * lists of statement patterns |
| * |
| * @param qArray |
| * List of StatementPatterns associated with query array |
| * @param iArray |
| * List of StatementPatterns associated with index array |
| * @param hMap |
| * HashMap of substitutions to be analyzed for consistent and |
| * added or removed |
| * @param hMaps |
| * List of HashMaps containing substitution schemes |
| * @param trees |
| * Array of TreeMaps used for comparison of StatementPattern |
| * nodes |
| */ |
| private static void evaluateMap(List<QueryModelNode> qArray, List<QueryModelNode> iArray, |
| HashMap<String, String> hMap, List<HashMap<String, String>> hMaps, |
| HashMap<HashMap<String, String>, Boolean> mapConsistent, TreeMap<String, Integer>[] trees) throws IllegalArgumentException { |
| |
| // if all nodes in indexArray have been exhausted, add map of substitutions to |
| // list of possible substitution schemes. |
| if (iArray.size() == 0) { |
| if (!hMaps.contains(hMap)) { |
| hMaps.add(hMap); |
| } |
| mapConsistent.put(hMap, true); |
| return; |
| } |
| |
| // for a given constant key, iterate through possible combinations of statement pattern nodes contained in associated query list and |
| // index list to generate all possible substitution schemes. |
| for (int i = 0; i < iArray.size(); i++) { |
| for (int j = 0; j < qArray.size(); j++) { |
| //System.out.println("Query list is " + qArray+ " and index list is " + iArray); |
| |
| QueryModelNode node1 = qArray.get(j); |
| QueryModelNode node2 = iArray.get(i); |
| // if lists contain statement patterns, check to see if two given statement patterns have same structure |
| // independent of variables names (same constants in same place, non constant Vars in same place) |
| if ((node1 instanceof StatementPattern) && (node2 instanceof StatementPattern)) { |
| if (genConstantCompare((StatementPattern) node1, (StatementPattern) node2)) { |
| |
| List<Var> variables1 = ((StatementPattern)node1).getVarList(); |
| List<Var> variables2 = ((StatementPattern)node2).getVarList(); |
| |
| List<List<String>> vars = genGetCommonVars(variables1, variables2); |
| List<String> vars1 = vars.get(0); |
| List<String> vars2 = vars.get(1); |
| |
| if (listConsistent(vars1, vars2, hMap)) { |
| |
| HashMap<String, String> hashMap = Maps.newHashMap(hMap); |
| putVars(vars1, vars2, hashMap); |
| |
| List<QueryModelNode> queryArray = Lists.newArrayList(qArray); |
| List<QueryModelNode> indexArray = Lists.newArrayList(iArray); |
| |
| indexArray.remove(i); |
| queryArray.remove(j); |
| |
| evaluateMap(queryArray, indexArray, hashMap, hMaps, mapConsistent, trees); |
| } |
| } |
| } // if lists contain filters, see if filters have same structure independent of variables names |
| //(check that conditions are same independent of variable names). |
| else if ((node1 instanceof Filter) && (node2 instanceof Filter)) { |
| try { |
| if (filterCompare((Filter) node1, (Filter) node2)) { |
| |
| List<QueryModelNode> variables1 = FilterVarValueCollector.process(((Filter) node1).getCondition()); |
| List<QueryModelNode> variables2 = FilterVarValueCollector.process(((Filter) node2).getCondition()); |
| |
| List<List<String>> vars = filterCommonVars(variables1, variables2); |
| List<String> vars1 = vars.get(0); |
| List<String> vars2 = vars.get(1); |
| |
| if (listConsistent(vars1, vars2, hMap)) { |
| |
| HashMap<String, String> hashMap = Maps.newHashMap(hMap); |
| putVars(vars1, vars2, hashMap); |
| |
| List<QueryModelNode> queryArray = Lists.newArrayList(qArray); |
| List<QueryModelNode> indexArray = Lists.newArrayList(iArray); |
| |
| indexArray.remove(i); |
| queryArray.remove(j); |
| |
| evaluateMap(queryArray, indexArray, hashMap, hMaps, mapConsistent, trees); |
| } |
| |
| } |
| } catch (Exception e) { |
| System.out.println("Invalid Filter! " + e); |
| } |
| |
| } else { |
| throw new IllegalArgumentException("Invalid query tree."); |
| } |
| |
| } |
| } |
| if (mapConsistent.containsKey(hMap)) |
| if (mapConsistent.get(hMap) == false) { |
| hMaps.remove(hMap); |
| } |
| return; |
| |
| } |
| |
| |
| |
| |
| private static List<List<String>> genGetCommonVars(List<Var> vars1, List<Var> vars2) { |
| |
| |
| List<List<String>> varList = Lists.newArrayList(); |
| List<String> varList1 = Lists.newArrayList(); |
| List<String> varList2 = Lists.newArrayList(); |
| |
| |
| |
| for (int i = 0; i < vars1.size(); i++) { |
| |
| if (!vars1.get(i).isConstant() && !vars2.get(i).isConstant()) { |
| |
| varList1.add(vars1.get(i).getName()); |
| varList2.add(vars2.get(i).getName()); |
| |
| } else if(vars1.get(i).isConstant() && !vars2.get(i).isConstant()) { |
| varList1.add(vars1.get(i).getName()); |
| varList2.add(vars2.get(i).getName()); |
| } |
| |
| } |
| |
| varList.add(varList1); |
| varList.add(varList2); |
| |
| return varList; |
| } |
| |
| |
| private static List<List<String>> filterCommonVars(List<QueryModelNode> vars1, List<QueryModelNode> vars2) { |
| |
| |
| List<List<String>> varList = Lists.newArrayList(); |
| List<String> varList1 = Lists.newArrayList(); |
| List<String> varList2 = Lists.newArrayList(); |
| |
| |
| |
| for (int i = 0; i < vars1.size(); i++) { |
| |
| if ((vars1.get(i) instanceof ValueConstant) && (vars2.get(i) instanceof Var)) { |
| |
| ValueConstant vc = (ValueConstant) vars1.get(i); |
| final String s = VarNameUtils.createUniqueConstVarName(vc.getValue()); |
| varList1.add(s); |
| varList2.add(((Var)vars2.get(i)).getName()); |
| } else if(!(vars1.get(i) instanceof ValueConstant)){ |
| if (!((Var) vars1.get(i)).isConstant() && (vars2.get(i) instanceof Var) |
| && !((Var) vars2.get(i)).isConstant()) { |
| varList1.add(((Var) vars1.get(i)).getName()); |
| varList2.add(((Var) vars2.get(i)).getName()); |
| } else if (((Var) vars1.get(i)).isConstant() && (vars2.get(i) instanceof Var) |
| && !((Var) vars2.get(i)).isConstant()) { |
| varList1.add(((Var) vars1.get(i)).getName()); |
| varList2.add(((Var) vars2.get(i)).getName()); |
| } |
| } |
| |
| } |
| |
| varList.add(varList1); |
| varList.add(varList2); |
| |
| return varList; |
| } |
| |
| |
| |
| private static boolean genConstantCompare(StatementPattern queryNode, StatementPattern indexNode) { |
| |
| |
| |
| ArrayList<Var> vars1 = (ArrayList<Var>) queryNode.getVarList(); |
| ArrayList<Var> vars2 = (ArrayList<Var>) indexNode.getVarList(); |
| |
| |
| for (int i = 0; i < vars1.size(); i++) { |
| |
| if (vars1.get(i).isConstant() && vars2.get(i).isConstant()) { |
| |
| if (!vars1.get(i).equals(vars2.get(i))) { |
| return false; |
| |
| } |
| |
| } else if(!vars1.get(i).isConstant() && vars2.get(i).isConstant() ) { |
| return false; |
| } |
| |
| } |
| |
| return true; |
| |
| } |
| |
| |
| |
| |
| /** |
| * Method checks that substituting val for key is consistent with |
| * substitutions in hMap |
| * |
| * @param val |
| * substituting variable |
| * @param key |
| * variable to be substituted for |
| * @param hMap |
| * HashMap containing the substitutions to be made |
| * @return true if the proposed substitution is consistent with hMap, and |
| * false otherwise |
| */ |
| private static boolean checkVariables(String val, String key, HashMap<String, String> hMap) { |
| |
| if (!hMap.containsKey(key) && !hMap.containsValue(val)) { |
| |
| return true; |
| } else if (!hMap.containsKey(key) && hMap.containsValue(val) || hMap.containsKey(key) |
| && !hMap.containsValue(val)) { |
| |
| return false; |
| } else { |
| |
| return hMap.get(key).equals(val); |
| |
| } |
| |
| } |
| |
| |
| |
| |
| |
| |
| // given two lists of variables and a HashMap, checks to see if substituting variable names in varList1 |
| // for variable names in varList2 is consistent with map. |
| private static boolean listConsistent(List<String> varList1, List<String> varList2, HashMap<String, String> hMap) { |
| |
| for (int k = 0; k < varList1.size(); k++) { |
| |
| String s1 = varList1.get(k); |
| String s2 = varList2.get(k); |
| if (!checkVariables(s1, s2, hMap)) { |
| return false; |
| } |
| } |
| return true; |
| |
| } |
| |
| |
| // given two lists of variables and a HashMap, substitutes variable names in varList1 |
| // for variable names in varList2 by updating map. |
| private static void putVars(List<String> varList1, List<String> varList2, HashMap<String, String> hashMap) { |
| |
| for (int k = 0; k < varList1.size(); k++) { |
| String s1 = varList1.get(k); |
| String s2 = varList2.get(k); |
| if (!hashMap.containsKey(s2)) { |
| |
| hashMap.put(s2, s1); |
| } |
| } |
| |
| } |
| |
| |
| /** |
| * @param filter1 |
| * @param filter2 |
| * @return true if filter2 is equal to filter1 once variables in filter2 are replaced with variables and constants |
| * occurring in same position in filter1 (allows filter1 to contain constants where filter2 contains variables) |
| * @throws Exception |
| */ |
| private static boolean filterCompare(Filter filter1, Filter filter2) throws Exception { |
| |
| NodeCollector nc1 = new NodeCollector(); |
| NodeCollector nc2 = new NodeCollector(); |
| |
| filter1.getCondition().visit(nc1); |
| filter2.getCondition().visit(nc2); |
| |
| List<QueryModelNode> nodeList1 = nc1.getNodes(); |
| List<QueryModelNode> nodeList2 = nc2.getNodes(); |
| |
| if (nodeList1.size() != nodeList2.size()) { |
| return false; |
| } |
| |
| for (int i = 0; i < nodeList1.size(); i++) { |
| if ((nodeList1.get(i) instanceof ValueConstant) && (nodeList2.get(i) instanceof Var)) { |
| continue; |
| } else { |
| if (nodeList1.get(i).getClass() != nodeList2.get(i).getClass()) { |
| return false; |
| } |
| } |
| } |
| |
| return true; |
| |
| } |
| |
| /** |
| * Given a HashMap containing variable substitutions and a tuple, this |
| * method uses a visitor to iterate through the tuple and make the necessary |
| * substitutions |
| * |
| * @param varChanges |
| * @param tuple |
| * @throws Exception |
| */ |
| private static void replaceTupleVariables(HashMap<String, String> varChanges, TupleExpr tuple, Map<String,Value> valMap) throws Exception { |
| |
| TupleVarRenamer visitor = new TupleVarRenamer(varChanges, valMap); |
| tuple.visit(visitor); |
| } |
| |
| /** |
| * Given a list of StatementPattern nodes and a TreeMap containing the |
| * variables in the tuple, this method counts the number of occurrences of |
| * each variable in the given list |
| * |
| * @param list |
| * List of StatementPattern nodes |
| * @param cnt |
| * TreeMap whose keys are tuple variables and whose value is 0 |
| * @return TreeMap whose keys are tuple variables and whose value is the |
| * number of times variable appears in list |
| */ |
| private static TreeMap<String, Integer> getListVarCnt(List<QueryModelNode> list, TreeMap<String, Integer> cnt) { |
| |
| int count = 0; |
| |
| for (QueryModelNode qNode : list) { |
| List<String> vars = VarCollector.process(qNode); |
| for (String s : vars) { |
| count = cnt.get(s); |
| count++; |
| cnt.put(s, count); |
| } |
| |
| } |
| |
| return cnt; |
| |
| } |
| |
| /** |
| * Given a StatementPattern and two TreeMaps containing the variable counts |
| * associated with an associated list and tuple, this method assigns a |
| * number to the StatementPattern node which is determined by the number of |
| * times its variables (non-constant Vars) appear in the list and throughout |
| * the tuple |
| * |
| * @param sp |
| * StatementPattern node |
| * @param listCount |
| * TreeMap with variable count info associated with list |
| * @param tupCount |
| * TreeMap with variable count info associated with tuple |
| * @return count info associated with StatementPattern node |
| */ |
| private static int getSpCount(QueryModelNode sp, TreeMap<String, Integer> listCount, |
| TreeMap<String, Integer> tupCount) { |
| |
| int spCount = 0; |
| |
| List<String> vars = VarCollector.process(sp); |
| for (String var : vars) { |
| spCount = spCount + listCount.get(var) + tupCount.get(var); |
| } |
| return spCount; |
| |
| } |
| |
| /** |
| * @return NormalizedQueryVisitor |
| */ |
| public static NormalizeQueryVisitor getVisitor(boolean isIndex) { |
| return new NormalizeQueryVisitor(isIndex); |
| |
| } |
| |
| |
| // ********************Definition of Comparators**************** |
| // ************************************************************* |
| public static class CountComp implements Comparator<QueryModelNode> { |
| |
| private TreeMap<String, Integer> lCount, tupleCount; |
| |
| public CountComp(TreeMap<String, Integer> lCount, TreeMap<String, Integer> tupleCount) { |
| |
| this.lCount = lCount; |
| this.tupleCount = tupleCount; |
| } |
| |
| // compares StatementPattern nodes based on frequency at which their |
| // variables appear in other StatementPattern nodes in associated |
| // tuple and list |
| |
| public int compare(QueryModelNode sp1, QueryModelNode sp2) { |
| |
| return -(getSpCount(sp1, lCount, tupleCount) - getSpCount(sp2, lCount, tupleCount)); |
| } |
| |
| } |
| |
| // comparator to sort constant key list according to size of associated |
| // StatementPattern array |
| public static class ConstantKeyComp implements Comparator<String> { |
| |
| private TreeMap<String, List<QueryModelNode>> indexMap, queryMap; |
| |
| public ConstantKeyComp(TreeMap<String, List<QueryModelNode>> indexMap, |
| TreeMap<String, List<QueryModelNode>> queryMap) { |
| |
| this.indexMap = indexMap; |
| this.queryMap = queryMap; |
| |
| } |
| |
| // Compare method to sort keys of HashMap<String, |
| // ArrayList<StatementPattern> |
| // for index based on whether key also appears in query Map--if key does |
| // not appear |
| // in query map, key is given value 0 so it is moved to front when key |
| // list is sorted. |
| // If key appears in query map, key is assigned value that is the sum of |
| // the size of the associated |
| // lists in index map and query map. |
| |
| public int compare(String key1, String key2) { |
| |
| int len1 = 0; |
| int len2 = 0; |
| |
| if (queryMap.containsKey(key1) && indexMap.containsKey(key1)) |
| len1 = indexMap.get(key1).size() + queryMap.get(key1).size(); |
| if (queryMap.containsKey(key2) && indexMap.containsKey(key2)) |
| len2 = indexMap.get(key2).size() + queryMap.get(key2).size(); |
| |
| return (len1 - len2); |
| |
| } |
| |
| } |
| |
| public static class FilterComp implements Comparator<QueryModelNode> { |
| |
| public int compare(QueryModelNode q1, QueryModelNode q2) { |
| |
| int size1 = VarCollector.process(q1).size(); |
| int size2 = VarCollector.process(q2).size(); |
| |
| return size1 - size2; |
| |
| } |
| |
| } |
| |
| // ******************** Definition of Visitors***************** |
| // ************************************************************ |
| |
| |
| |
| public static class ValueMapVisitor extends AbstractQueryModelVisitor<Exception> { |
| |
| |
| private Map<String, Value> valMap = Maps.newHashMap(); |
| |
| |
| |
| public Map<String, Value> getValueMap() { |
| return valMap; |
| } |
| |
| public void meet(Var var) { |
| if (var.isConstant()) { |
| valMap.put(var.getName(),var.getValue()); |
| } |
| |
| |
| } |
| |
| public void meet(ValueConstant val) { |
| |
| final String s = VarNameUtils.createUniqueConstVarName(val.getValue()); |
| valMap.put(s, val.getValue()); |
| } |
| |
| } |
| |
| |
| |
| |
| |
| |
| |
| public static class NodeCollector extends AbstractQueryModelVisitor<Exception> { |
| |
| |
| private List<QueryModelNode> nodes = Lists.newArrayList(); |
| |
| public List<QueryModelNode> getNodes() { |
| return nodes; |
| } |
| |
| @Override |
| public void meetNode(QueryModelNode node) throws Exception { |
| nodes.add(node); |
| super.meetNode(node); |
| } |
| |
| } |
| |
| public static class SpVarReNamer extends AbstractQueryModelVisitor<RuntimeException> { |
| |
| private final HashMap<String, String> hMap; |
| private Map<String, Value> valMap; |
| |
| public SpVarReNamer(HashMap<String, String> hMap, Map<String, Value> valMap) { |
| this.valMap = valMap; |
| this.hMap = hMap; |
| } |
| |
| public void meet(Var var) { |
| if (!var.isConstant() && hMap.containsKey(var.getName())) { |
| String val = hMap.get(var.getName()); |
| if (VarNameUtils.isConstant(val)) { |
| var.setName(val); |
| var.setValue(valMap.get(val)); |
| var.setAnonymous(true); //TODO this might be a hack -- when are Vars not anonymous? |
| } else { |
| var.setName(val); |
| } |
| } |
| } |
| |
| } |
| |
| |
| |
| |
| public static class FilterVarReNamer extends AbstractQueryModelVisitor<RuntimeException> { |
| |
| private final HashMap<String, String> hMap; |
| private Map<String, Value> valMap; |
| |
| public FilterVarReNamer(HashMap<String, String> hMap, Map<String, Value> valMap) { |
| this.valMap = valMap; |
| this.hMap = hMap; |
| } |
| |
| @Override |
| public void meet(Var var) { |
| |
| if (!(var.getParentNode() instanceof NAryValueOperator)) { |
| if (!var.isConstant() && hMap.containsKey(var.getName())) { |
| String val = hMap.get(var.getName()); |
| if (VarNameUtils.isConstant(val)) { |
| var.replaceWith(new ValueConstant(valMap.get(val))); |
| } else { |
| var.setName(val); |
| } |
| } |
| } |
| } |
| |
| |
| |
| @Override |
| public void meetNAryValueOperator(NAryValueOperator node) { |
| |
| List<ValueExpr> oldValues = node.getArguments(); |
| List<ValueExpr> newValues = Lists.newArrayList(); |
| |
| for (ValueExpr v : oldValues) { |
| if (v instanceof Var) { |
| Var var = (Var) v; |
| if (!(var.isConstant() && hMap.containsKey(var.getName()))) { |
| String val = hMap.get(var.getName()); |
| if (VarNameUtils.isConstant(val)) { |
| newValues.add(new ValueConstant(valMap.get(val))); |
| } else { |
| var.setName(val); |
| newValues.add(var); |
| } |
| } |
| } else { |
| newValues.add(v); |
| } |
| } |
| |
| node.setArguments(newValues); |
| |
| } |
| |
| |
| } |
| |
| |
| |
| |
| public static class TupleVarRenamer extends AbstractQueryModelVisitor<RuntimeException> { |
| |
| private final HashMap<String, String> varChanges; |
| private Map<String, Value> valMap; |
| |
| public TupleVarRenamer(HashMap<String, String> varChanges, Map<String, Value> valMap) { |
| this.varChanges = varChanges; |
| this.valMap = valMap; |
| } |
| |
| @Override |
| public void meet(ProjectionElemList node) { |
| List<ProjectionElem> proj = node.getElements(); |
| for (ProjectionElem s : proj) { |
| if (varChanges.containsKey(s.getSourceName())) { |
| String name = s.getSourceName(); |
| s.setSourceName(varChanges.get(name)); |
| s.setTargetName(varChanges.get(name)); |
| |
| } |
| } |
| |
| } |
| |
| |
| @Override |
| public void meet(StatementPattern node) { |
| SpVarReNamer spv = new SpVarReNamer(varChanges, valMap); |
| node.visit(spv); |
| } |
| |
| |
| @Override |
| public void meet(Filter node) { |
| FilterVarReNamer fvr = new FilterVarReNamer(varChanges, valMap); |
| node.getCondition().visit(fvr); |
| node.getArg().visit(this); |
| |
| } |
| |
| |
| |
| } |
| |
| public static class VarCollector extends AbstractQueryModelVisitor<RuntimeException> { |
| |
| public static List<String> process(QueryModelNode node) { |
| VarCollector collector = new VarCollector(); |
| node.visit(collector); |
| return collector.getVarNames(); |
| } |
| |
| public static List<Var> processVar(QueryModelNode node) { |
| VarCollector collector = new VarCollector(); |
| node.visit(collector); |
| return collector.getVars(); |
| } |
| |
| private List<String> varNames = new ArrayList<String>(); |
| private List<Var> vars = Lists.newArrayList(); |
| |
| public List<String> getVarNames() { |
| return varNames; |
| } |
| |
| public List<Var> getVars() { |
| return vars; |
| } |
| |
| @Override |
| public void meet(Var var) { |
| if (!var.hasValue()) { |
| varNames.add(var.getName()); |
| } |
| vars.add(var); |
| } |
| } |
| |
| public static class FilterVarValueCollector extends AbstractQueryModelVisitor<RuntimeException> { |
| |
| public static List<QueryModelNode> process(QueryModelNode node) { |
| FilterVarValueCollector collector = new FilterVarValueCollector(); |
| node.visit(collector); |
| return collector.getVars(); |
| } |
| |
| |
| |
| private List<QueryModelNode> vars = Lists.newArrayList(); |
| |
| |
| public List<QueryModelNode> getVars() { |
| return vars; |
| } |
| |
| @Override |
| public void meet(Var node) { |
| vars.add(node); |
| } |
| |
| @Override |
| public void meet(ValueConstant node) { |
| vars.add(node); |
| } |
| |
| |
| |
| } |
| |
| |
| |
| |
| public static class NormalizeQueryVisitor extends AbstractQueryModelVisitor<Exception> { |
| |
| private TreeMap<String, List<QueryModelNode>> map = new TreeMap<String, List<QueryModelNode>>(); |
| private TreeMap<String, Integer> varMap = new TreeMap<String, Integer>(); |
| private TreeMap<String, Integer> emptyVarMap = new TreeMap<String, Integer>(); |
| private List<StatementPattern> statementList = new ArrayList<StatementPattern>(); |
| private List<QueryModelNode> filters = new ArrayList<QueryModelNode>(); |
| private boolean isIndex; |
| |
| |
| |
| public NormalizeQueryVisitor(boolean isIndex) { |
| this.isIndex = isIndex; |
| } |
| |
| |
| |
| private TreeMap<String, List<QueryModelNode>> getMap() { |
| |
| return map; |
| |
| } |
| |
| |
| private TreeMap<String, Integer> getKeyMap() { |
| |
| return varMap; |
| } |
| |
| private TreeMap<String, Integer> getVariableMap() { |
| return emptyVarMap; |
| } |
| |
| public List<StatementPattern> getStatementPatterns() { |
| return statementList; |
| } |
| |
| |
| private List<QueryModelNode> getFilters() { |
| |
| return filters; |
| } |
| |
| @Override |
| public void meet(StatementPattern node) throws Exception { |
| |
| statementList.add(node); |
| |
| String s = ""; |
| String t = ""; |
| |
| Var node1 = node.getSubjectVar(); |
| Var node2 = node.getObjectVar(); |
| Var node3 = node.getPredicateVar(); |
| Var node4 = node.getContextVar(); |
| |
| String s1 = ""; |
| String s2 = ""; |
| String s3 = ""; |
| String s4 = ""; |
| |
| |
| if (node1.isConstant()) |
| s1 = node1.getName().substring(7); |
| |
| if (node2.isConstant()) |
| s2 = node2.getName().substring(7); |
| |
| if (node3.isConstant()) |
| s3 = node3.getName().substring(7); |
| |
| if (node4 != null) { |
| if (node4.isConstant()) |
| s4 = node4.getName().substring(7); |
| } |
| |
| if ((s1+s2+s3).length() == 0) { |
| s = "Nonconstant nodes have no variables."; |
| } |
| |
| List<QueryModelNode> nodes; |
| |
| |
| if (s.length() > 0) { |
| |
| if (map.containsKey(s)) { |
| nodes = map.get(s); |
| nodes.add(node); |
| } else { |
| nodes = new ArrayList<QueryModelNode>(); |
| nodes.add(node); |
| } |
| |
| map.put(s, nodes); |
| |
| } else { |
| |
| if (isIndex) { |
| |
| t = s1 + s2 + s3 + s4; |
| |
| if (map.containsKey(t)) { |
| nodes = map.get(t); |
| nodes.add(node); |
| } else { |
| nodes = new ArrayList<QueryModelNode>(); |
| nodes.add(node); |
| } |
| |
| map.put(t, nodes); |
| |
| } else { |
| |
| String[] comps = new String[4]; |
| comps[0] = s1; |
| comps[1] = s2; |
| comps[2] = s3; |
| comps[3] = s4; |
| |
| for (int i = 0; i < 3; i++) { |
| if (comps[i].length() != 0) { |
| if (map.containsKey(comps[i] + comps[3])) { |
| nodes = map.get(comps[i] + comps[3]); |
| nodes.add(node); |
| } else { |
| nodes = new ArrayList<QueryModelNode>(); |
| nodes.add(node); |
| } |
| |
| map.put(comps[i] + comps[3], nodes); |
| |
| for (int j = i + 1; j < 3; j++) { |
| if (comps[j].length() != 0) { |
| if (map.containsKey(comps[i] + comps[j] + comps[3])) { |
| nodes = map.get(comps[i] + comps[j] + comps[3]); |
| nodes.add(node); |
| } else { |
| nodes = new ArrayList<QueryModelNode>(); |
| nodes.add(node); |
| } |
| map.put(comps[i] + comps[j] + comps[3], nodes); |
| } |
| |
| } |
| } |
| } |
| |
| if (s1.length() != 0 && s2.length() != 0 && s3.length() != 0) { |
| if (map.containsKey(s1 + s2 + s3 + s4)) { |
| nodes = map.get(s1 + s2 + s3 + s4); |
| nodes.add(node); |
| } else { |
| nodes = new ArrayList<QueryModelNode>(); |
| nodes.add(node); |
| } |
| map.put(s1 + s2 + s3 + s4, nodes); |
| } |
| } |
| } |
| |
| super.meet(node); |
| |
| } |
| |
| @Override |
| public void meet(Var node) throws Exception { |
| |
| int count = 1; |
| |
| if (!node.isConstant()) { |
| if (varMap.containsKey(node.getName())) { |
| count = varMap.get(node.getName()); |
| count++; |
| varMap.put(node.getName(), count); |
| } else |
| varMap.put(node.getName(), 1); |
| |
| if (!emptyVarMap.containsKey(node.getName())) |
| emptyVarMap.put(node.getName(), 0); |
| |
| } |
| super.meet(node); |
| } |
| |
| public void meet(Filter filter) throws Exception { |
| filters.add(filter); |
| super.meet(filter); |
| } |
| |
| } |
| |
| } |
