http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/11349b11/extras/indexing/src/main/java/org/apache/rya/indexing/external/matching/OptionalJoinSegment.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/org/apache/rya/indexing/external/matching/OptionalJoinSegment.java b/extras/indexing/src/main/java/org/apache/rya/indexing/external/matching/OptionalJoinSegment.java new file mode 100644 index 0000000..6f3d409 --- /dev/null +++ b/extras/indexing/src/main/java/org/apache/rya/indexing/external/matching/OptionalJoinSegment.java @@ -0,0 +1,168 @@ +package org.apache.rya.indexing.external.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.HashMap; +import java.util.List; +import java.util.Map; +import java.util.Set; + +import org.apache.rya.indexing.external.tupleSet.ExternalTupleSet; +import org.apache.rya.rdftriplestore.inference.DoNotExpandSP; +import org.apache.rya.rdftriplestore.utils.FixedStatementPattern; +import org.openrdf.query.algebra.Filter; +import org.openrdf.query.algebra.Join; +import org.openrdf.query.algebra.LeftJoin; +import org.openrdf.query.algebra.QueryModelNode; +import org.openrdf.query.algebra.TupleExpr; +import org.openrdf.query.algebra.ValueExpr; +import org.openrdf.query.algebra.evaluation.impl.ExternalSet; + +import com.google.common.base.Preconditions; +import com.google.common.collect.Sets; + +/** + * An OptionalJoinSegment represents the portion of a {@link TupleExpr} that is + * connected by Filters, LeftJoins, and Joins. All nodes in the portion of the + * TupleExpr that are connected via these node types are gathered into an + * ordered and an unordered list that can easily be compared with + * {@link ExternalTupleSet} nodes for sub-query matching to use with Precomputed + * Joins. + * + */ +public class OptionalJoinSegment<T extends ExternalSet> extends AbstractQuerySegment<T> { + + public OptionalJoinSegment(Join join) { + Preconditions.checkNotNull(join); + createJoinSegment(join); + } + + public OptionalJoinSegment(LeftJoin join) { + Preconditions.checkNotNull(join); + createJoinSegment(join); + } + + public OptionalJoinSegment(Filter filter) { + Preconditions.checkNotNull(filter); + createJoinSegment(filter); + } + + public OptionalJoinSegment(Set<QueryModelNode> unorderedNodes, List<QueryModelNode> orderedNodes, Map<ValueExpr, Filter> filterMap) { + this.unorderedNodes = unorderedNodes; + this.orderedNodes = orderedNodes; + this.conditionMap = filterMap; + } + + private void createJoinSegment(TupleExpr te) { + orderedNodes = getJoinArgs(te, orderedNodes); + unorderedNodes = Sets.newHashSet(orderedNodes); + } + + /** + * This method matches the ordered nodes returned by + * {@link OptionalJoinSegment #getOrderedNodes()} for nodeToReplace with a subset of + * the ordered nodes for this OptionalJoinSegment. The order of the nodes for + * nodeToReplace must match the order of the nodes as a subset of + * orderedNodes + * + * @param segment + * - nodes to be replaced by ExternalSet node + * @param set + * - ExternalSet node that will replace specified query nodes + */ + @Override + public boolean replaceWithExternalSet(QuerySegment<T> segment, T set) { + Preconditions.checkNotNull(segment != null); + Preconditions.checkNotNull(set); + if (!containsQuerySegment(segment)) { + return false; + } + List<QueryModelNode> nodeList = segment.getOrderedNodes(); + int begin = orderedNodes.indexOf(nodeList.get(0)); + // TODO this assumes no duplicate nodes + if (begin < 0 || begin + nodeList.size() > orderedNodes.size() + || !nodeList.equals(orderedNodes.subList(begin, begin + nodeList.size()))) { + return false; + } + orderedNodes.removeAll(nodeList); + orderedNodes.add(begin, set); + unorderedNodes.removeAll(nodeList); + unorderedNodes.add(set); + for (QueryModelNode q : nodeList) { + if (q instanceof ValueExpr) { + conditionMap.remove(q); + } + } + return true; + } + + /** + * + * @param tupleExpr + * - the query object that will be traversed by this method + * @param joinArgs + * - all nodes connected by Joins, LeftJoins, and Filters + * @return - List containing all nodes connected by Joins, LeftJoins, and + * Filters. This List contains the {@link ValueExpr} in place of the + * Filter and a {@link FlattenedOptional} in place of the LeftJoin + * for ease of comparison with PCJ nodes. + */ + private List<QueryModelNode> getJoinArgs(TupleExpr tupleExpr, List<QueryModelNode> joinArgs) { + + if (tupleExpr instanceof Join) { + if (!(((Join) tupleExpr).getLeftArg() instanceof FixedStatementPattern) + && !(((Join) tupleExpr).getRightArg() instanceof DoNotExpandSP)) { + Join join = (Join) tupleExpr; + getJoinArgs(join.getRightArg(), joinArgs); + getJoinArgs(join.getLeftArg(), joinArgs); + } + } else if (tupleExpr instanceof LeftJoin) { + LeftJoin lj = (LeftJoin) tupleExpr; + joinArgs.add(new FlattenedOptional(lj)); + getJoinArgs(lj.getLeftArg(), joinArgs); + } else if (tupleExpr instanceof Filter) { + Filter filter = (Filter) tupleExpr; + joinArgs.add(filter.getCondition()); + conditionMap.put(filter.getCondition(), filter); + getJoinArgs(filter.getArg(), joinArgs); + } else { + joinArgs.add(tupleExpr); + } + return joinArgs; + } + + + @Override + public OptionalJoinSegment<T> clone() { + List<QueryModelNode> order = new ArrayList<>(); + for(QueryModelNode node: orderedNodes) { + order.add(node.clone()); + } + + Set<QueryModelNode> unorder = Sets.newHashSet(order); + + Map<ValueExpr, Filter> map = new HashMap<>(); + for(ValueExpr expr: conditionMap.keySet()) { + map.put(expr.clone(), conditionMap.get(expr).clone()); + } + return new OptionalJoinSegment<T>(unorder, order, map); + } + +}
http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/11349b11/extras/indexing/src/main/java/org/apache/rya/indexing/external/matching/OptionalJoinSegmentMatcher.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/org/apache/rya/indexing/external/matching/OptionalJoinSegmentMatcher.java b/extras/indexing/src/main/java/org/apache/rya/indexing/external/matching/OptionalJoinSegmentMatcher.java new file mode 100644 index 0000000..a359d02 --- /dev/null +++ b/extras/indexing/src/main/java/org/apache/rya/indexing/external/matching/OptionalJoinSegmentMatcher.java @@ -0,0 +1,164 @@ +package org.apache.rya.indexing.external.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.Collection; +import java.util.Iterator; +import java.util.List; + +import org.openrdf.query.algebra.QueryModelNode; +import org.openrdf.query.algebra.evaluation.impl.ExternalSet; + +import com.google.common.base.Optional; +import com.google.common.base.Preconditions; + +/** + * This class matches ExternalSet queries to sub-queries of a given + * {@link OptionalJoinSegment}. A match will occur when the + * {@link QueryModelNode}s of the ExternalSet can be grouped together in the + * OptionalJoinSegment and ordered to match the ExternalSet query. + * + */ + +public class OptionalJoinSegmentMatcher<T extends ExternalSet> extends AbstractExternalSetMatcher<T> { + + private ExternalSetConverter<T> converter; + + public OptionalJoinSegmentMatcher(QuerySegment<T> segment, ExternalSetConverter<T> converter) { + Preconditions.checkNotNull(segment); + Preconditions.checkNotNull(converter); + this.segment = segment; + this.segmentNodeList = new ArrayList<>(segment.getOrderedNodes()); + this.converter = converter; + } + + /** + * @param segment + * - {@link QuerySegment} to be replaced by ExternalSet + * @param set + * - ExternalSet to replace matching QuerySegment + */ + @Override + protected boolean match(QuerySegment<T> nodes, T set) { + + Preconditions.checkNotNull(nodes); + Preconditions.checkNotNull(set); + + if (!segment.containsQuerySegment(nodes)) { + return false; + } + final List<QueryModelNode> consolidatedNodes = groupNodesToMatchExternalSet(getOrderedNodes(), + nodes.getOrderedNodes()); + if (consolidatedNodes.size() == 0) { + return false; + } + + // set segment nodes to the consolidated nodes to match pcj + segment.setNodes(consolidatedNodes); + final boolean nodesReplaced = segment.replaceWithExternalSet(nodes, set); + + // if ExternalSet nodes replaced queryNodes, update nodes + // otherwise restore segment nodes back to original pre-consolidated + // state + if (nodesReplaced) { + updateTupleAndNodes(); + } else { + segment.setNodes(segmentNodeList); + } + + return nodesReplaced; + } + + /** + * + * @param queryNodes + * - query nodes to be compared to pcj for matching + * @param pcjNodes + * - pcj nodes to match to query + * @return - query nodes with pcj nodes grouped together (if possible), + * otherwise return an empty list. + */ + private List<QueryModelNode> groupNodesToMatchExternalSet(final List<QueryModelNode> queryNodes, + final List<QueryModelNode> externalSetNodes) { + final QueryNodeConsolidator pnc = new QueryNodeConsolidator(queryNodes, externalSetNodes); + final boolean canConsolidate = pnc.consolidateNodes(); + if (canConsolidate) { + return pnc.getQueryNodes(); + } + return new ArrayList<QueryModelNode>(); + } + + @Override + public boolean match(T set) { + Preconditions.checkNotNull(set); + QuerySegment<T> segment = converter.setToSegment(set); + return match(segment, set); + } + + @Override + public QuerySegment<T> match(Iterator<List<T>> sets, Optional<QueryNodeListRater> r) { + QueryNodeListRater rater = null; + + if (r.isPresent()) { + rater = r.get(); + } else { + rater = new BasicRater(segmentNodeList); + } + + double min= Double.MAX_VALUE; + double temp = 0; + QuerySegment<T> minSegment = null; + while (sets.hasNext()) { + QuerySegment<T> tempSegment = match(sets.next()); + temp = rater.rateQuerySegment(tempSegment.getOrderedNodes()); + if(temp < min) { + min = temp; + minSegment = tempSegment; + } + } + + return minSegment; + } + + @Override + public QuerySegment<T> match(Collection<T> sets) { + Preconditions.checkNotNull(sets); + QuerySegment<T> copy = ((OptionalJoinSegment<T>) segment).clone(); + for (T set : sets) { + QuerySegment<T> nodes = converter.setToSegment(set); + if (copy.containsQuerySegment(nodes)) { + List<QueryModelNode> consolidatedNodes = groupNodesToMatchExternalSet(copy.getOrderedNodes(), + nodes.getOrderedNodes()); + if (consolidatedNodes.size() == 0) { + return copy; + } + + // set segment nodes to the consolidated nodes to match + copy.setNodes(consolidatedNodes); + copy.replaceWithExternalSet(nodes, set); + } + } + + return copy; + } + + +} http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/11349b11/extras/indexing/src/main/java/org/apache/rya/indexing/external/matching/QueryNodeConsolidator.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/org/apache/rya/indexing/external/matching/QueryNodeConsolidator.java b/extras/indexing/src/main/java/org/apache/rya/indexing/external/matching/QueryNodeConsolidator.java new file mode 100644 index 0000000..9a2d3be --- /dev/null +++ b/extras/indexing/src/main/java/org/apache/rya/indexing/external/matching/QueryNodeConsolidator.java @@ -0,0 +1,618 @@ +package org.apache.rya.indexing.external.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.Comparator; +import java.util.HashSet; +import java.util.Iterator; +import java.util.List; +import java.util.SortedSet; +import java.util.TreeSet; + +import org.openrdf.query.algebra.QueryModelNode; +import org.openrdf.query.algebra.TupleExpr; +import org.openrdf.query.algebra.ValueExpr; + +import com.google.common.base.Preconditions; + +/** + * Given an order List view of an {@link OptionalJoinSegment} taken from a query + * and an OptionalJoinSegment representing an ExternalSet, this class attempts + * to consolidate the {@link QueryModelNode}s of the ExternalSet together within + * the query and order them in a way that is consistent with the ExternalSet. + * This is the key step in matching the ExternalSet to a subset of a query when + * LeftJoins are present. + * + */ +public class QueryNodeConsolidator { + + private TreeSet<PositionNode> leftJoinPosSet = new TreeSet<>(new PositionComparator()); + private TreeSet<PositionNode> extSetPosSet = new TreeSet<>(new PositionComparator()); + + // nonExtSetNodes in query that extSetNodes cannot move past + private TreeSet<PositionNode> lowerBoundSet = new TreeSet<>(new PositionComparator()); + // nonExtSetNodes in query that extSetNodes cannot move past + private TreeSet<PositionNode> upperBoundSet = new TreeSet<>(new PositionComparator()); + private int greatestLowerBound = -1; + private int leastUpperBound = Integer.MAX_VALUE; + + private List<QueryModelNode> queryNodes; + private List<QueryModelNode> extSetNodes; + private boolean consolidateCalled = false; + private boolean returnValConsolidate = false; + + public QueryNodeConsolidator(List<QueryModelNode> queryNodes, List<QueryModelNode> extSetNodes) { + Preconditions.checkArgument( + new HashSet<QueryModelNode>(queryNodes).containsAll(new HashSet<QueryModelNode>(extSetNodes))); + this.queryNodes = new ArrayList<>(queryNodes); + this.extSetNodes = new ArrayList<>(extSetNodes); + int i = 0; + for (QueryModelNode q : queryNodes) { + if (q instanceof FlattenedOptional) { + leftJoinPosSet.add(new PositionNode(q, i)); + } + if (extSetNodes.contains(q)) { + extSetPosSet.add(new PositionNode(q, i)); + } + i++; + } + } + + /** + * This method consolidates the ExternalSet nodes within the query. After + * this method is called, the ExternalSet nodes in the query will be + * completely consolidated if true is returned and will only be partially + * consolidated if false is return + * + * @return - true or false depending on whether nodes could be entirely + * consolidated + */ + public boolean consolidateNodes() { + if (consolidateCalled) { + return returnValConsolidate; + } + consolidateCalled = true; + returnValConsolidate = consolidate() && reOrderExtSetNodes(); + return returnValConsolidate; + } + + /** + * + * @return List of the query's QueryModelNodes + */ + public List<QueryModelNode> getQueryNodes() { + return queryNodes; + } + + // assumes nodes are consolidated -- checks if they can be reordered to + // match ExternalSet node list + private boolean reOrderExtSetNodes() { + int pos = extSetPosSet.last().getPosition(); + for (int j = extSetNodes.size() - 1; j >= 0; j--) { + QueryModelNode node = extSetNodes.get(j); + int i = queryNodes.indexOf(node); + // use ExternalSet node in queryNodes so FlattenedOptional boundVars + // are consistent with query + node = queryNodes.get(i); + if (!moveQueryNode(new PositionNode(node, i), pos)) { + return false; + } + pos--; + } + return true; + } + + private boolean consolidate() { + while (canConsolidate()) { + Move move = getNextMove(); + // if move is empty, then ExternalSet nodes are + // consolidated + if (move.isEmpty) { + return true; + } + moveQueryNode(move.node, move.finalPos); + } + + return false; + } + + private boolean canConsolidate() { + if (greatestLowerBound < leastUpperBound) { + return true; + } + return adjustBounds(); + } + + // if l.u.b < g.l.b, attempt to push g.l.b up + // assume first ExternalSet position node has position less + // than g.l.b. - this should be by design given that + // l.u.b <= g.l.b. and there has to be at least one ExternalSet node + // positioned before l.u.b. + private boolean adjustBounds() { + + int finalPos = extSetPosSet.first().getPosition(); + PositionNode node = lowerBoundSet.last(); + + return moveQueryNode(node, finalPos); + } + + // assumes g.l.b <= l.u.b. + // iterates through ExternalSet nodes in query from lowest position to + // highest looking for a difference in index position greater than + // one. Given the leftmost pair of nodes separated by two or more + // spaces, the leftmost node in the pair is moved so that its final + // position is one position to the left of the rightmost node. For + // example, given nodes at index 1 and index 3, the node at index 1 + // is advanced to index 2. This method returns the suggested Move, + // but does not actually perform the Move. + private Move getNextMove() { + + Iterator<PositionNode> posIterator = extSetPosSet.iterator(); + PositionNode current; + if (posIterator.hasNext()) { + current = posIterator.next(); + } else { + throw new IllegalStateException("PCJ has no nodes!"); + } + PositionNode next; + int pos1 = -1; + int pos2 = -1; + while (posIterator.hasNext()) { + next = posIterator.next(); + pos1 = current.getPosition(); + pos2 = next.getPosition(); + // move nodes are not adjacent + if (pos1 + 1 < pos2) { + if (leastUpperBound > pos2) { + return new Move(current, pos2 - 1); + } + // pos1 < leastUpperBound < pos2 b/c pos1 < leastUpperBound by + // design + else if (greatestLowerBound < pos1) { + return new Move(next, pos1 + 1); + } + // move current to node after greatestLowerBound + else { + return new Move(current, greatestLowerBound); + } + } + + current = next; + } + + return new Move(); + } + + private boolean moveQueryNode(PositionNode node, int position) { + + if (!canMoveNode(node, position)) { + if (upperBoundSet.size() > 0) { + leastUpperBound = upperBoundSet.first().getPosition(); + } + if (lowerBoundSet.size() > 0) { + greatestLowerBound = lowerBoundSet.last().getPosition(); + } + return false; + } + // update QueryModelNodes in leftJoin index so that FlattenedOptional + // var counts are correct + updateLeftJoinNodes(node, position); + // move node in queryNode list + updateNodeList(node, position, queryNodes); + // update bounds + updatePositionNodeSet(node, position, lowerBoundSet); + updatePositionNodeSet(node, position, upperBoundSet); + // update leastUppperBound and greatestLowerBound + if (upperBoundSet.size() > 0) { + leastUpperBound = upperBoundSet.first().getPosition(); + } + if (lowerBoundSet.size() > 0) { + greatestLowerBound = lowerBoundSet.last().getPosition(); + } + // update positions within leftJoin index + updatePositionNodeSet(node, position, leftJoinPosSet); + // no need to update entire set because ExternalSet nodes are not moved + // past one another during consolidation + updatePositionNode(node, position, extSetPosSet); + + return true; + } + + private boolean canMoveNode(PositionNode node, int finalPos) { + PositionNode bound = getBounds(node, finalPos, queryNodes, leftJoinPosSet); + if (bound.isEmpty) { + return true; + } + addBound(bound, node, finalPos); + return false; + + } + + // adds bound to either lowerBoundSet or uppderBoundSet, depending on + // initial and + // final position of move + private void addBound(PositionNode bound, PositionNode node, int finalPos) { + int diff = finalPos - node.getPosition(); + + if (diff == 0) { + return; + } + + if (diff > 0) { + if (upperBoundSet.contains(bound)) { + return; + } else { + upperBoundSet.add(bound); + } + } else { + if (lowerBoundSet.contains(bound)) { + return; + } else { + lowerBoundSet.add(bound); + } + } + } + + // updates nodes in given TreeSet between node.getPosition() and position + private void updatePositionNodeSet(PositionNode node, int position, TreeSet<PositionNode> set) { + + if (set.size() == 0) { + return; + } + + int oldPos = node.getPosition(); + int diff = position - oldPos; + SortedSet<PositionNode> posNodes; + boolean containsNode = false; + + if (diff == 0) { + return; + } + + // remove node before decrementing or incrementing to prevent + // overwriting + if (set.contains(node)) { + containsNode = true; + set.remove(node); + } + + if (diff > 0) { + posNodes = set.subSet(node, false, new PositionNode(position), true); + + List<PositionNode> pNodeList = new ArrayList<>(); + for (PositionNode pos : posNodes) { + pNodeList.add(pos); + } + // decrement posNodes + for (PositionNode pos : pNodeList) { + int p = pos.getPosition() - 1; + updatePositionNode(pos, p, set); + } + } else { + posNodes = set.subSet(new PositionNode(position), true, node, false); + // create list to iterate in reverse order + List<PositionNode> pNodeList = new ArrayList<>(); + for (PositionNode pos : posNodes) { + pNodeList.add(pos); + } + // increment elements of TreeSet in reverse order so + // that no collisions occur - PositionNodes are incremented + // into slot created by removing node + for (int i = pNodeList.size() - 1; i >= 0; i--) { + PositionNode pNode = pNodeList.get(i); + int p = pNode.getPosition() + 1; + updatePositionNode(pNode, p, set); + } + } + + if (containsNode) { + node.setPosition(position); + set.add(node); + } + + } + + // updates the var counts in specified left join index + private void updateLeftJoinNodes(PositionNode node, int finalPos) { + if (node.getNode() instanceof ValueExpr) { + return; + } + + int diff = finalPos - node.getPosition(); + + if (diff == 0) { + return; + } + + if (node.isOptional) { + leftJoinPosSet.remove(node); + FlattenedOptional optional = (FlattenedOptional) node.getNode(); + if (diff < 0) { + for (int i = node.getPosition() - 1; i > finalPos - 1; i--) { + QueryModelNode tempNode = queryNodes.get(i); + if (tempNode instanceof ValueExpr) { + continue; + } + optional.addArg((TupleExpr) tempNode); + } + } else { + for (int i = node.getPosition() + 1; i < finalPos + 1; i++) { + QueryModelNode tempNode = queryNodes.get(i); + if (tempNode instanceof ValueExpr) { + continue; + } + optional.removeArg((TupleExpr) tempNode); + } + } + node.setNode(optional); + // FlattenedOptional equals does not take into account var counts + // The following three lines update the var count in the optional in + // list + int index = queryNodes.indexOf(optional); + queryNodes.remove(optional); + queryNodes.add(index, optional); + leftJoinPosSet.add(node); + + } else { + TupleExpr te = (TupleExpr) node.getNode(); + SortedSet<PositionNode> optionals; + if (diff < 0) { + optionals = leftJoinPosSet.subSet(new PositionNode(finalPos), true, node, false); + for (PositionNode pNode : optionals) { + FlattenedOptional optional = (FlattenedOptional) pNode.getNode(); + optional.removeArg(te); + } + } else { + optionals = leftJoinPosSet.subSet(node, false, new PositionNode(finalPos), true); + for (PositionNode pNode : optionals) { + FlattenedOptional optional = (FlattenedOptional) pNode.getNode(); + optional.addArg(te); + } + } + } + + } + + // works only if moving node to final position does not move it across + // another node in set + private void updatePositionNode(PositionNode node, int position, TreeSet<PositionNode> set) { + set.remove(node); + node.setPosition(position); + set.add(node); + } + + // assumes input data fall within capacity of list + private void updateNodeList(PositionNode node, int finalPos, List<QueryModelNode> list) { + int initialPos = node.getPosition(); + QueryModelNode qNode = list.remove(initialPos); + if (finalPos < list.size()) { + list.add(finalPos, qNode); + } else { + list.add(qNode); + } + } + + /** + * + * @param node + * @param finalPos + * @param list + * @param leftJoinNodes + * @return PositionNode - if node cannot be move to final position, this + * method returns a non-empty PositionNode representing a bound to + * the move. If it can, it returns an empty PositionNode. + */ + // determine if given node can be moved to finalPos + // assumes node.position and finalPos fall within index range of list + private PositionNode getBounds(PositionNode node, int finalPos, List<QueryModelNode> list, + TreeSet<PositionNode> leftJoinNodes) { + + // filters can be moved up and pushed down join segment + // without affecting bound and unbound variables of + // FlattenedOptionals -- Filters can be pushed down as + // far as possible because it is assumed that any variable + // that appears in a Filter also appears in a ExternalSet node + // if Filters can be grouped, then Filter variables will + // automatically be bound + if (node.getNode() instanceof ValueExpr) { + return new PositionNode(); + } + + int diff = finalPos - node.getPosition(); + + if (diff == 0) { + return new PositionNode(); + } + + if (node.isOptional) { + FlattenedOptional optional = ((FlattenedOptional) node.getNode()).clone(); + if (diff < 0) { + for (int i = node.getPosition() - 1; i > finalPos - 1; i--) { + QueryModelNode tempNode = list.get(i); + if (tempNode instanceof ValueExpr) { + continue; + } + + if (!optional.canAddTuple((TupleExpr) tempNode)) { + return new PositionNode(tempNode, i); + } + + if (tempNode instanceof FlattenedOptional) { + FlattenedOptional tempOptional = (FlattenedOptional) tempNode; + if (!tempOptional.canRemoveTuple(optional)) { + return new PositionNode(tempNode, i); + } + + } + optional.addArg((TupleExpr) tempNode); + } + } else { + for (int i = node.getPosition() + 1; i < finalPos + 1; i++) { // TODO + // check + // bounds + QueryModelNode tempNode = list.get(i); + if (tempNode instanceof ValueExpr) { + continue; + } + if (!optional.canRemoveTuple((TupleExpr) tempNode)) { + return new PositionNode(tempNode, i); + } + + if (tempNode instanceof FlattenedOptional) { + FlattenedOptional tempOptional = (FlattenedOptional) tempNode; + if (!tempOptional.canAddTuple(optional)) { + return new PositionNode(tempNode, i); + } + } + optional.removeArg((TupleExpr) tempNode); + } + } + + return new PositionNode(); + + } else { + TupleExpr te = (TupleExpr) node.getNode(); + SortedSet<PositionNode> leftJoins; + if (diff < 0) { + leftJoins = leftJoinNodes.subSet(new PositionNode(finalPos), true, node, false); + + for (PositionNode pNode : leftJoins) { + FlattenedOptional optional = (FlattenedOptional) pNode.getNode(); + if (!optional.canRemoveTuple(te)) { + return new PositionNode(pNode); + } + } + } else { + + leftJoins = leftJoinNodes.subSet(node, false, new PositionNode(finalPos), true); + for (PositionNode pNode : leftJoins) { + FlattenedOptional optional = (FlattenedOptional) pNode.getNode(); + if (!optional.canAddTuple(te)) { + return new PositionNode(pNode); + } + } + } + + return new PositionNode(); + + } + + } + + static class Move { + + PositionNode node; + int finalPos; + boolean isEmpty = true; + + public Move(PositionNode node, int finalPos) { + this.node = node; + this.finalPos = finalPos; + this.isEmpty = false; + } + + public Move() { + } + + } + + static class PositionNode { + + private int position; + private QueryModelNode node; + private boolean isOptional = false; + boolean isEmpty = true; + + public PositionNode(QueryModelNode node, int position) { + this.node = node; + this.position = position; + this.isOptional = node instanceof FlattenedOptional; + isEmpty = false; + } + + public PositionNode(PositionNode node) { + this(node.node, node.position); + } + + public PositionNode(int position) { + this.position = position; + isEmpty = false; + } + + public PositionNode() { + + } + + /** + * @return the position + */ + public int getPosition() { + return position; + } + + /** + * @param position + * the position to set + */ + public void setPosition(int position) { + this.position = position; + } + + /** + * @return the node + */ + public QueryModelNode getNode() { + return node; + } + + public void setNode(QueryModelNode node) { + this.node = node; + } + + public boolean isOptional() { + return isOptional; + } + + @Override + public String toString() { + return "Node: " + node + " Position: " + position; + } + + } + + class PositionComparator implements Comparator<PositionNode> { + + @Override + public int compare(PositionNode node1, PositionNode node2) { + + if (node1.position < node2.position) { + return -1; + } + if (node1.position > node2.position) { + return 1; + } + + return 0; + } + + } + +} http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/11349b11/extras/indexing/src/main/java/org/apache/rya/indexing/external/matching/QueryNodeListRater.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/org/apache/rya/indexing/external/matching/QueryNodeListRater.java b/extras/indexing/src/main/java/org/apache/rya/indexing/external/matching/QueryNodeListRater.java new file mode 100644 index 0000000..115a12b --- /dev/null +++ b/extras/indexing/src/main/java/org/apache/rya/indexing/external/matching/QueryNodeListRater.java @@ -0,0 +1,39 @@ +package org.apache.rya.indexing.external.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.List; + +import org.openrdf.query.algebra.QueryModelNode; + +/** + * Class used for determining an optimal query plan. It assigns a score + * between 0 and 1 to a list of QueryModelNodes. A lower score indicates + * that the List represents a better collection of nodes for building a query + * plan. Usually, the specified List is compared to a base List (original query), + * and the specified List (mutated query) is compared to the original to determine + * if there was any improvement in the query plan. This is meant to be used in conjunction + * with the method {@link ExternalSetMatcher#match(java.util.Iterator, com.google.common.base.Optional)}. + * + */ +public interface QueryNodeListRater { + + public double rateQuerySegment(List<QueryModelNode> eNodes); + +} http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/11349b11/extras/indexing/src/main/java/org/apache/rya/indexing/external/matching/QueryNodesToTupleExpr.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/org/apache/rya/indexing/external/matching/QueryNodesToTupleExpr.java b/extras/indexing/src/main/java/org/apache/rya/indexing/external/matching/QueryNodesToTupleExpr.java new file mode 100644 index 0000000..5bffb63 --- /dev/null +++ b/extras/indexing/src/main/java/org/apache/rya/indexing/external/matching/QueryNodesToTupleExpr.java @@ -0,0 +1,188 @@ +package org.apache.rya.indexing.external.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.HashSet; +import java.util.List; +import java.util.Set; + +import org.openrdf.query.algebra.Filter; +import org.openrdf.query.algebra.Join; +import org.openrdf.query.algebra.LeftJoin; +import org.openrdf.query.algebra.QueryModelNode; +import org.openrdf.query.algebra.TupleExpr; + +import com.google.common.collect.Lists; + +/** + * This class converts a given collection of {@link QueryModelNode}s into a + * {@link TupleExpr}. The primary purpose of this class is to reconstruct a + * TupleExpr representation of a {@link QuerySegment} from its List view. + * + */ +public class QueryNodesToTupleExpr { + + private List<QueryModelNode> queryNodes; + private Set<Filter> filters; + + public QueryNodesToTupleExpr(List<QueryModelNode> queryNodes, Set<Filter> filters) { + this.queryNodes = queryNodes; + this.filters = filters; + } + + /** + * + * @return - a TupleExprAndNodes object that consists of the the TupleExpr + * representation of the List of QueryModelNodes and the nodes used + * to build the TupleExpr. + */ + public TupleExprAndNodes getTupleAndNodes() { + List<QueryModelNode> nodeCopy = new ArrayList<>(); + Set<Filter> setCopy = new HashSet<>(); + for (QueryModelNode q : queryNodes) { + nodeCopy.add(q.clone()); + } + for (Filter f : filters) { + setCopy.add(f.clone()); + } + TupleExpr te = buildQuery(nodeCopy, setCopy); + + return new TupleExprAndNodes(te, nodeCopy, setCopy); + } + + private TupleExpr buildQuery(List<QueryModelNode> queryNodes, Set<Filter> filters) { + List<Filter> chain = getFilterChain(filters); + return getNewJoin(queryNodes, chain); + } + + // chain filters together and return front and back of chain + private static List<Filter> getFilterChain(Set<Filter> filters) { + final List<Filter> filterTopBottom = Lists.newArrayList(); + Filter filterChainTop = null; + Filter filterChainBottom = null; + + for (final Filter filter : filters) { + if (filterChainTop == null) { + filterChainTop = filter; + filter.setParentNode(null); + } else if (filterChainBottom == null) { + filterChainBottom = filter; + filterChainTop.setArg(filterChainBottom); + } else { + filterChainBottom.setArg(filter); + filterChainBottom = filter; + } + } + if (filterChainTop != null) { + filterTopBottom.add(filterChainTop); + } + if (filterChainBottom != null) { + filterTopBottom.add(filterChainBottom); + } + return filterTopBottom; + } + + // build newJoin node given remaining joinArgs and chain of filters + private static TupleExpr getNewJoin(List<QueryModelNode> args, List<Filter> filterChain) { + TupleExpr newJoin; + TupleExpr tempJoin; + final List<TupleExpr> joinArgs = Lists.newArrayList(); + for (QueryModelNode q : args) { + if (q instanceof TupleExpr) { + joinArgs.add(0, (TupleExpr) q); + } else { + throw new IllegalArgumentException("Invalid query node!"); + } + } + + if (joinArgs.size() > 1) { + TupleExpr left = joinArgs.remove(0); + TupleExpr right = joinArgs.remove(0); + tempJoin = getJoin(left, right); + for (int i = joinArgs.size() - 1; i >= 0; i--) { + tempJoin = getJoin(tempJoin, joinArgs.get(i)); + } + if (filterChain.size() == 0) { + newJoin = tempJoin; + } else if (filterChain.size() == 1) { + newJoin = filterChain.get(0); + ((Filter) newJoin).setArg(tempJoin); + } else { + newJoin = filterChain.get(0); + filterChain.get(1).setArg(tempJoin); + } + } else if (joinArgs.size() == 1) { + tempJoin = joinArgs.get(0); + if (filterChain.size() == 0) { + newJoin = tempJoin; + } else if (filterChain.size() == 1) { + newJoin = filterChain.get(0); + ((Filter) newJoin).setArg(tempJoin); + } else { + newJoin = filterChain.get(0); + filterChain.get(1).setArg(tempJoin); + } + } else { + throw new IllegalStateException("JoinArgs size cannot be zero."); + } + return newJoin; + } + + private static TupleExpr getJoin(TupleExpr oldJoin, TupleExpr newArg) { + if (newArg instanceof FlattenedOptional) { + return new LeftJoin(oldJoin, ((FlattenedOptional) newArg).getRightArg()); + } else { + return new Join(oldJoin, newArg); + } + } + + public static class TupleExprAndNodes { + + private TupleExpr te; + private List<QueryModelNode> nodes; + private Set<Filter> filters; + + public TupleExprAndNodes(TupleExpr te, List<QueryModelNode> nodes, Set<Filter> filters) { + this.te = te; + this.nodes = nodes; + this.filters = filters; + } + + public TupleExpr getTupleExpr() { + return te; + } + + public List<QueryModelNode> getNodes() { + return nodes; + } + + public Set<Filter> getFilters() { + return filters; + } + + @Override + public String toString() { + return "Query: " + te + " Nodes: " + nodes; + } + + } + +} http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/11349b11/extras/indexing/src/main/java/org/apache/rya/indexing/external/matching/QuerySegment.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/org/apache/rya/indexing/external/matching/QuerySegment.java b/extras/indexing/src/main/java/org/apache/rya/indexing/external/matching/QuerySegment.java new file mode 100644 index 0000000..8603a68 --- /dev/null +++ b/extras/indexing/src/main/java/org/apache/rya/indexing/external/matching/QuerySegment.java @@ -0,0 +1,85 @@ +package org.apache.rya.indexing.external.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.List; +import java.util.Set; + +import org.apache.rya.indexing.external.matching.QueryNodesToTupleExpr.TupleExprAndNodes; +import org.openrdf.query.algebra.Filter; +import org.openrdf.query.algebra.QueryModelNode; +import org.openrdf.query.algebra.evaluation.impl.ExternalSet; + +/** + * A QuerySegment represents a subset of a query to be compared to PCJs for + * query matching. The QuerySegment is represented as a List, where the order of + * the nodes in the list is determined by a Visitor as it traverses the Segment + * from top down, visiting right children before left. + * + */ +public interface QuerySegment<T extends ExternalSet> extends Cloneable{ + + /** + * + * @return - an unordered view of the {@link QueryModelNode}s in the segment + */ + public Set<QueryModelNode> getUnOrderedNodes(); + + /** + * + * @return - an ordered view of the {@link QueryModelNode}s in the segment. + */ + public List<QueryModelNode> getOrderedNodes(); + + public Set<Filter> getFilters(); + + /** + * + * @param segment + * - this method verifies whether the specified segment is + * contained in this segment + * @return - true if contained and false otherwise + */ + public boolean containsQuerySegment(QuerySegment<T> segment); + + /** + * Sets List of {@link QueryModelNode}s representing this QuerySegment to + * specified list + * + * @param nodes + * - nodes to set + */ + public void setNodes(List<QueryModelNode> nodes); + + /** + * + * @param nodeToReplace + * - QuerySegment representation of ExternalSet T to match with + * subset of this QuerySegment + * @param set + * - ExternalSet to replace matching QuerySegment nodes if match + * occurs + * @return - true if match occurs and false otherwise + */ + public boolean replaceWithExternalSet(QuerySegment<T> nodeToReplace, T set); + + public TupleExprAndNodes getQuery(); + +} http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/11349b11/extras/indexing/src/main/java/org/apache/rya/indexing/external/matching/QuerySegmentFactory.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/org/apache/rya/indexing/external/matching/QuerySegmentFactory.java b/extras/indexing/src/main/java/org/apache/rya/indexing/external/matching/QuerySegmentFactory.java new file mode 100644 index 0000000..4bf1faf --- /dev/null +++ b/extras/indexing/src/main/java/org/apache/rya/indexing/external/matching/QuerySegmentFactory.java @@ -0,0 +1,60 @@ +package org.apache.rya.indexing.external.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 org.openrdf.query.algebra.Filter; +import org.openrdf.query.algebra.Join; +import org.openrdf.query.algebra.LeftJoin; +import org.openrdf.query.algebra.QueryModelNode; +import org.openrdf.query.algebra.evaluation.impl.ExternalSet; + +import com.google.common.base.Preconditions; + +/** + * Factory class for producing {@link QuerySegment}s from {@link QueryModelNode}s. + * + * @param <T> - ExternalSet parameter + */ +public class QuerySegmentFactory<T extends ExternalSet> { + + public QuerySegment<T> getQuerySegment(QueryModelNode node) { + Preconditions.checkNotNull(node); + if(node instanceof Filter) { + Filter filter = (Filter)node; + if(MatcherUtilities.segmentContainsLeftJoins(filter)) { + return new OptionalJoinSegment<T>(filter); + } else { + return new JoinSegment<T>(filter); + } + } else if(node instanceof Join) { + Join join = (Join) node; + if(MatcherUtilities.segmentContainsLeftJoins(join)) { + return new OptionalJoinSegment<T>(join); + } else { + return new JoinSegment<T>(join); + } + } else if (node instanceof LeftJoin) { + return new OptionalJoinSegment<T>((LeftJoin) node); + } else { + throw new IllegalArgumentException("Node must be a Join, Filter, or LeftJoin"); + } + + } + +} http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/11349b11/extras/indexing/src/main/java/org/apache/rya/indexing/external/matching/TopOfQueryFilterRelocator.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/org/apache/rya/indexing/external/matching/TopOfQueryFilterRelocator.java b/extras/indexing/src/main/java/org/apache/rya/indexing/external/matching/TopOfQueryFilterRelocator.java new file mode 100644 index 0000000..6ebbe39 --- /dev/null +++ b/extras/indexing/src/main/java/org/apache/rya/indexing/external/matching/TopOfQueryFilterRelocator.java @@ -0,0 +1,95 @@ +package org.apache.rya.indexing.external.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.HashSet; +import java.util.List; +import java.util.Set; + +import org.openrdf.query.algebra.Filter; +import org.openrdf.query.algebra.Projection; +import org.openrdf.query.algebra.TupleExpr; +import org.openrdf.query.algebra.ValueExpr; +import org.openrdf.query.algebra.helpers.QueryModelVisitorBase; + +/** + * Class consisting of a single utility method for relocating filters. + * + */ +public class TopOfQueryFilterRelocator { + + /** + * + * This method moves the Filters of a specified {@link TupleExpr} to the top + * of the TupleExpr. + * + * @param query + * - query whose filters will be relocated + * @return - TupleExpr with filters relocated to top + */ + public static TupleExpr moveFiltersToTop(TupleExpr query) { + + ProjectionAndFilterGatherer fg = new ProjectionAndFilterGatherer(); + query.visit(fg); + List<ValueExpr> filterCond = new ArrayList<>(fg.filterCond); + Projection projection = fg.projection; + + if (filterCond.size() == 0) { + return query; + } + + Filter first = new Filter(); + first.setCondition(filterCond.remove(0)); + Filter current = first; + for (ValueExpr cond : filterCond) { + Filter filter = new Filter(null, cond); + current.setArg(filter); + current = filter; + } + + TupleExpr te = projection.getArg(); + projection.setArg(first); + current.setArg(te); + + return query; + + } + + static class ProjectionAndFilterGatherer extends QueryModelVisitorBase<RuntimeException> { + + Set<ValueExpr> filterCond = new HashSet<>(); + Projection projection; + + @Override + public void meet(Projection node) { + this.projection = node; + node.getArg().visit(this); + } + + @Override + public void meet(Filter node) { + filterCond.add(node.getCondition()); + node.replaceWith(node.getArg()); + } + + } + +} http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/11349b11/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/AbstractPCJMatcher.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/AbstractPCJMatcher.java b/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/AbstractPCJMatcher.java deleted file mode 100644 index 38e4045..0000000 --- a/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/AbstractPCJMatcher.java +++ /dev/null @@ -1,126 +0,0 @@ -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.Collections; -import java.util.HashSet; -import java.util.List; -import java.util.Set; - -import org.apache.rya.indexing.external.tupleSet.ExternalTupleSet; -import org.apache.rya.indexing.pcj.matching.QueryNodesToTupleExpr.TupleExprAndNodes; - -import org.openrdf.query.algebra.BinaryTupleOperator; -import org.openrdf.query.algebra.Filter; -import org.openrdf.query.algebra.QueryModelNode; -import org.openrdf.query.algebra.TupleExpr; -import org.openrdf.query.algebra.UnaryTupleOperator; - -/** - * This class provides implementations of methods common to all implementations of - * the {@link PCJMatcher} interface. - * - */ -public abstract class AbstractPCJMatcher implements PCJMatcher { - - protected QuerySegment segment; - protected List<QueryModelNode> segmentNodeList; - protected boolean tupleAndNodesUpToDate = false; - protected TupleExpr tuple; - protected Set<TupleExpr> unmatched; - protected PCJToSegment pcjToSegment; - protected Set<Filter> filters; - - /** - * @param - pcj - PremomputedJoin to be matched to a subset of segment - * @return - true if match occurs and false otherwise - */ - @Override - public boolean matchPCJ(ExternalTupleSet pcj) { - QuerySegment sgmnt = pcjToSegment.getSegment(pcj); - if(sgmnt == null) { - throw new IllegalArgumentException("PCJ must contain at east one Join or Left Join"); - } - return matchPCJ(sgmnt, pcj); - } - - /** - * In following method, order is determined by the order in which the - * node appear in the query. - * @return - an ordered view of the QueryModelNodes appearing tuple - * - */ - @Override - public List<QueryModelNode> getOrderedNodes() { - return Collections.unmodifiableList(segmentNodeList); - } - - - @Override - public Set<Filter> getFilters() { - if (!tupleAndNodesUpToDate) { - updateTupleAndNodes(); - } - return filters; - } - - @Override - public TupleExpr getQuery() { - if (!tupleAndNodesUpToDate) { - updateTupleAndNodes(); - } - return tuple; - } - - @Override - public Set<TupleExpr> getUnmatchedArgs() { - if (!tupleAndNodesUpToDate) { - updateTupleAndNodes(); - } - return unmatched; - } - - - private void updateTupleAndNodes() { - TupleExprAndNodes tupAndNodes = segment.getQuery(); - tuple = tupAndNodes.getTupleExpr(); - filters = tupAndNodes.getFilters(); - unmatched = new HashSet<>(); - List<QueryModelNode> nodes = tupAndNodes.getNodes(); - for (QueryModelNode q : nodes) { - if (q instanceof UnaryTupleOperator - || q instanceof BinaryTupleOperator) { - unmatched.add((TupleExpr) q); - } - } - tupleAndNodesUpToDate = true; - } - - - /** - * Interface for converting an {@link ExternalTupleSet} (PCJ) into a - * {@link QuerySegment}. - * - */ - interface PCJToSegment { - public QuerySegment getSegment(ExternalTupleSet pcj); - } - -} http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/11349b11/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/AbstractQuerySegment.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/AbstractQuerySegment.java b/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/AbstractQuerySegment.java deleted file mode 100644 index 75a7098..0000000 --- a/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/AbstractQuerySegment.java +++ /dev/null @@ -1,122 +0,0 @@ -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.Collection; -import java.util.Collections; -import java.util.HashSet; -import java.util.List; -import java.util.Map; -import java.util.Set; - -import org.apache.rya.indexing.pcj.matching.QueryNodesToTupleExpr.TupleExprAndNodes; - -import org.openrdf.query.algebra.Filter; -import org.openrdf.query.algebra.QueryModelNode; -import org.openrdf.query.algebra.ValueExpr; - -import com.google.common.base.Preconditions; -import com.google.common.collect.Maps; -import com.google.common.collect.Sets; - -/** - * This class provides implementations of methods common to implementations - * of the {@link QuerySegment} interface. - * - */ -public abstract class AbstractQuerySegment implements QuerySegment { - - - protected List<QueryModelNode> orderedNodes = new ArrayList<>(); - protected Set<QueryModelNode> unorderedNodes; - protected Map<ValueExpr, Filter> conditionMap = Maps.newHashMap(); - - /** - * Returns set view of nodes contained in the segment - */ - @Override - public Set<QueryModelNode> getUnOrderedNodes() { - return Collections.unmodifiableSet(unorderedNodes); - } - - /** - * Returns a list view of nodes contained in this segment, where order is - * determined by the getJoinArgs method - * - * @param TupleExpr - * from top to bottom. - */ - @Override - public List<QueryModelNode> getOrderedNodes() { - return Collections.unmodifiableList(orderedNodes); - } - - /** - * Allows nodes to be reordered using {@link PCJMatcher} and set - * @param nodes - reordering of orderedNodes - */ - @Override - public void setNodes(List<QueryModelNode> nodes) { - Set<QueryModelNode> nodeSet = Sets.newHashSet(nodes); - Preconditions.checkArgument(nodeSet.equals(unorderedNodes)); - orderedNodes = nodes; - unorderedNodes = nodeSet; - } - - /** - * @param query - * - QuerySegment that this method checks for in this - * JoinSegment - */ - @Override - public boolean containsQuerySegment(QuerySegment query) { - return unorderedNodes.containsAll(query.getUnOrderedNodes()); - } - - /** - * @return - a TupleExpr representing this JoinSegment - */ - @Override - public TupleExprAndNodes getQuery() { - List<QueryModelNode> nodeCopy = new ArrayList<>(); - for (QueryModelNode q : orderedNodes) { - if (!(q instanceof ValueExpr)) { - nodeCopy.add(q.clone()); - } - } - QueryNodesToTupleExpr qnt = new QueryNodesToTupleExpr(nodeCopy, getFilters()); - return qnt.getTupleAndNodes(); - } - - @Override - public Set<Filter> getFilters() { - Collection<Filter> filters = conditionMap.values(); - Set<Filter> filterSet = new HashSet<>(); - for (Filter filter : filters) { - filterSet.add(filter.clone()); - } - - return filterSet; - - } - - -} http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/11349b11/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/AccumuloIndexSetProvider.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/AccumuloIndexSetProvider.java b/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/AccumuloIndexSetProvider.java new file mode 100644 index 0000000..641830b --- /dev/null +++ b/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/AccumuloIndexSetProvider.java @@ -0,0 +1,223 @@ +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 static java.util.Objects.requireNonNull; + +import java.util.ArrayList; +import java.util.Iterator; +import java.util.List; +import java.util.Map; + +import org.apache.accumulo.core.client.AccumuloException; +import org.apache.accumulo.core.client.AccumuloSecurityException; +import org.apache.accumulo.core.client.Connector; +import org.apache.accumulo.core.client.TableNotFoundException; +import org.apache.hadoop.conf.Configuration; +import org.apache.log4j.Logger; +import org.apache.rya.accumulo.instance.AccumuloRyaInstanceDetailsRepository; +import org.apache.rya.api.RdfCloudTripleStoreConfiguration; +import org.apache.rya.api.instance.RyaDetailsRepository; +import org.apache.rya.api.instance.RyaDetailsRepository.RyaDetailsRepositoryException; +import org.apache.rya.indexing.IndexPlanValidator.IndexedExecutionPlanGenerator; +import org.apache.rya.indexing.IndexPlanValidator.ValidIndexCombinationGenerator; +import org.apache.rya.indexing.accumulo.ConfigUtils; +import org.apache.rya.indexing.external.matching.ExternalSetProvider; +import org.apache.rya.indexing.external.matching.QuerySegment; +import org.apache.rya.indexing.external.tupleSet.AccumuloIndexSet; +import org.apache.rya.indexing.external.tupleSet.ExternalTupleSet; +import org.apache.rya.indexing.pcj.storage.PcjException; +import org.apache.rya.indexing.pcj.storage.PrecomputedJoinStorage; +import org.apache.rya.indexing.pcj.storage.accumulo.AccumuloPcjStorage; +import org.apache.rya.indexing.pcj.storage.accumulo.PcjTableNameFactory; +import org.apache.rya.indexing.pcj.storage.accumulo.PcjTables; +import org.openrdf.query.MalformedQueryException; +import org.openrdf.query.QueryEvaluationException; +import org.openrdf.query.algebra.TupleExpr; +import org.openrdf.sail.SailException; + +import com.google.common.collect.Lists; +import com.google.common.collect.Maps; + +import jline.internal.Preconditions; + +/** + * Implementation of {@link ExternalSetProvider} that provides {@link ExternalTupleSet}s. + * This provider uses either user specified Accumulo configuration information or user a specified + * List of ExternalTupleSets to populate an internal cache of ExternalTupleSets. If Accumulo configuration + * is provided, the provider connects to an instance of RyaDetails and populates the cache with + * PCJs registered in RyaDetails. + * + */ +public class AccumuloIndexSetProvider implements ExternalSetProvider<ExternalTupleSet> { + + private static final Logger log = Logger.getLogger(ExternalSetProvider.class); + private static final PCJToSegmentConverter converter = new PCJToSegmentConverter(); + private List<ExternalTupleSet> indexCache; + private Configuration conf; + private boolean init = false; + + public AccumuloIndexSetProvider(Configuration conf) { + Preconditions.checkNotNull(conf); + this.conf = conf; + } + + public AccumuloIndexSetProvider(Configuration conf, List<ExternalTupleSet> indices) { + Preconditions.checkNotNull(conf); + this.conf = conf; + this.indexCache = indices; + init = true; + } + + /** + * + * @return - size of underlying PCJ cache + * @throws Exception + */ + public int size() throws Exception { + if(!init) { + indexCache = PCJOptimizerUtilities.getValidPCJs(getAccIndices()); + init = true; + } + return indexCache.size(); + } + + /** + * @param segment - QuerySegment used to get relevant queries form index cache for matching + * @return List of PCJs for matching + */ + @Override + public List<ExternalTupleSet> getExternalSets(QuerySegment<ExternalTupleSet> segment) { + try { + if(!init) { + indexCache = PCJOptimizerUtilities.getValidPCJs(getAccIndices()); + init = true; + } + TupleExpr query = segment.getQuery().getTupleExpr(); + IndexedExecutionPlanGenerator iep = new IndexedExecutionPlanGenerator(query, indexCache); + List<ExternalTupleSet> pcjs = iep.getNormalizedIndices(); + List<ExternalTupleSet> tuples = new ArrayList<>(); + for (ExternalTupleSet tuple: pcjs) { + QuerySegment<ExternalTupleSet> pcj = converter.setToSegment(tuple); + if (segment.containsQuerySegment(pcj)) { + tuples.add(tuple); + } + } + return tuples; + + } catch (Exception e) { + throw new RuntimeException(e); + } + } + + /** + * @param segment - QuerySegment used to get relevant queries form index cache for matching + * + * @return Iterator of Lists (combos) of PCJs used to build an optimal query plan + */ + @Override + public Iterator<List<ExternalTupleSet>> getExternalSetCombos(QuerySegment<ExternalTupleSet> segment) { + ValidIndexCombinationGenerator comboGen = new ValidIndexCombinationGenerator(segment.getOrderedNodes()); + return comboGen.getValidIndexCombos(getExternalSets(segment)); + } + + /** + * + * + * @param conf + * - client configuration + * + * @return - list of {@link ExternalTupleSet}s or PCJs that are either + * specified by user in Configuration or exist in system. + * + * @throws MalformedQueryException + * @throws SailException + * @throws QueryEvaluationException + * @throws TableNotFoundException + * @throws AccumuloException + * @throws AccumuloSecurityException + * @throws PcjException + */ + private List<ExternalTupleSet> getAccIndices() throws Exception { + + requireNonNull(conf); + final String tablePrefix = requireNonNull(conf.get(RdfCloudTripleStoreConfiguration.CONF_TBL_PREFIX)); + final Connector conn = requireNonNull(ConfigUtils.getConnector(conf)); + List<String> tables = null; + + if (conf instanceof RdfCloudTripleStoreConfiguration) { + tables = ((RdfCloudTripleStoreConfiguration) conf).getPcjTables(); + } + // this maps associates pcj table name with pcj sparql query + final Map<String, String> indexTables = Maps.newLinkedHashMap(); + final PrecomputedJoinStorage storage = new AccumuloPcjStorage(conn, tablePrefix); + final PcjTableNameFactory pcjFactory = new PcjTableNameFactory(); + + final boolean tablesProvided = tables != null && !tables.isEmpty(); + + if (tablesProvided) { + // if tables provided, associate table name with sparql + for (final String table : tables) { + indexTables.put(table, storage.getPcjMetadata(pcjFactory.getPcjId(table)).getSparql()); + } + } else if (hasRyaDetails(tablePrefix, conn)) { + // If this is a newer install of Rya, and it has PCJ Details, then + // use those. + final List<String> ids = storage.listPcjs(); + for (final String id : ids) { + indexTables.put(pcjFactory.makeTableName(tablePrefix, id), storage.getPcjMetadata(id).getSparql()); + } + } else { + // Otherwise figure it out by scanning tables. + final PcjTables pcjTables = new PcjTables(); + for (final String table : conn.tableOperations().list()) { + if (table.startsWith(tablePrefix + "INDEX")) { + indexTables.put(table, pcjTables.getPcjMetadata(conn, table).getSparql()); + } + } + } + + // use table name sparql map (indexTables) to create {@link + // AccumuloIndexSet} + final List<ExternalTupleSet> index = Lists.newArrayList(); + if (indexTables.isEmpty()) { + log.info("No Index found"); + } else { + for (final String table : indexTables.keySet()) { + final String indexSparqlString = indexTables.get(table); + index.add(new AccumuloIndexSet(indexSparqlString, conf, table)); + } + } + + + return index; + } + + private static boolean hasRyaDetails(final String ryaInstanceName, final Connector conn) { + final RyaDetailsRepository detailsRepo = new AccumuloRyaInstanceDetailsRepository(conn, ryaInstanceName); + try { + detailsRepo.getRyaInstanceDetails(); + return true; + } catch (final RyaDetailsRepositoryException e) { + return false; + } + } + + +} http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/11349b11/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/FlattenedOptional.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/FlattenedOptional.java b/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/FlattenedOptional.java deleted file mode 100644 index 934b90a..0000000 --- a/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/FlattenedOptional.java +++ /dev/null @@ -1,331 +0,0 @@ -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.HashMap; -import java.util.HashSet; -import java.util.Map; -import java.util.Set; - -import org.apache.rya.rdftriplestore.inference.DoNotExpandSP; -import org.apache.rya.rdftriplestore.utils.FixedStatementPattern; - -import org.openrdf.query.algebra.Filter; -import org.openrdf.query.algebra.Join; -import org.openrdf.query.algebra.LeftJoin; -import org.openrdf.query.algebra.QueryModelNodeBase; -import org.openrdf.query.algebra.QueryModelVisitor; -import org.openrdf.query.algebra.TupleExpr; -import org.openrdf.query.algebra.ValueExpr; -import org.openrdf.query.algebra.Var; - -import com.google.common.collect.Sets; - -/** - * This class is essentially a wrapper for {@link LeftJoin}. It provides a - * flattened view of a LeftJoin that is useful for matching {@AccumuloIndexSet - * } nodes to sub-queries to use for Precomputed Joins. - * Because LeftJoins cannot automatically be interchanged with {@link Join}s and - * other LeftJoins in the query plan, this class has utility methods to check - * when nodes can be interchanged in the query plan. These methods track which - * variables returned by {@link LeftJoin#getRightArg()} are bound. A variable is - * bound if it also contained in the set returned by - * {@link LeftJoin#getLeftArg()}. Nodes can be interchanged with a LeftJoin (and - * hence a FlattenedOptional) so long as the bound and unbound variables do not - * change. - * - */ -public class FlattenedOptional extends QueryModelNodeBase implements TupleExpr { - - private Set<TupleExpr> rightArgs; - private Set<String> boundVars; - private Set<String> unboundVars; - private Map<String, Integer> leftArgVarCounts = new HashMap<String, Integer>(); - private ValueExpr condition; - private TupleExpr rightArg; - private Set<String> bindingNames; - private Set<String> assuredBindingNames; - - public FlattenedOptional(LeftJoin node) { - rightArgs = getJoinArgs(node.getRightArg(), new HashSet<TupleExpr>()); - boundVars = setWithOutConstants(Sets - .intersection(node.getLeftArg().getAssuredBindingNames(), node - .getRightArg().getBindingNames())); - unboundVars = setWithOutConstants(Sets.difference(node.getRightArg() - .getBindingNames(), boundVars)); - condition = node.getCondition(); - rightArg = node.getRightArg(); - getVarCounts(node); - assuredBindingNames = new HashSet<>(leftArgVarCounts.keySet()); - bindingNames = new HashSet<>(Sets.union(assuredBindingNames, - unboundVars)); - } - - public FlattenedOptional(FlattenedOptional optional) { - this.rightArgs = optional.rightArgs; - this.boundVars = optional.boundVars; - this.unboundVars = optional.unboundVars; - this.condition = optional.condition; - this.rightArg = optional.rightArg; - this.leftArgVarCounts = optional.leftArgVarCounts; - this.bindingNames = optional.bindingNames; - this.assuredBindingNames = optional.assuredBindingNames; - } - - public Set<TupleExpr> getRightArgs() { - return rightArgs; - } - - public TupleExpr getRightArg() { - return rightArg; - } - - /** - * - * @param te - * - TupleExpr to be added to leftarg of {@link LeftJoin} - */ - public void addArg(TupleExpr te) { - if (te instanceof FlattenedOptional) { - return; - } - incrementVarCounts(te.getBindingNames()); - } - - public void removeArg(TupleExpr te) { - if (te instanceof FlattenedOptional) { - return; - } - decrementVarCounts(te.getBindingNames()); - } - - /** - * - * @param te - * - {@link TupleExpr} to be added to leftArg of LeftJoin - * @return - true if adding TupleExpr does not affect unbound variables and - * returns false otherwise - */ - public boolean canAddTuple(TupleExpr te) { - // can only add LeftJoin if rightArg varNames do not intersect - // unbound vars - if (te instanceof FlattenedOptional) { - FlattenedOptional lj = (FlattenedOptional) te; - if (Sets.intersection(lj.rightArg.getBindingNames(), unboundVars) - .size() > 0) { - return false; - } else { - return true; - } - } - - return Sets.intersection(te.getBindingNames(), unboundVars).size() == 0; - } - - /** - * - * @param te - * - {@link TupleExpr} to be removed from leftArg of LeftJoin - * @return - true if removing TupleExpr does not affect bound variables and - * returns false otherwise - */ - public boolean canRemoveTuple(TupleExpr te) { - return canRemove(te); - } - - @Override - public Set<String> getBindingNames() { - return bindingNames; - } - - @Override - public Set<String> getAssuredBindingNames() { - return assuredBindingNames; - } - - public ValueExpr getCondition() { - return condition; - } - - @Override - public boolean equals(Object other) { - if (other instanceof FlattenedOptional) { - FlattenedOptional ljDec = (FlattenedOptional) other; - ValueExpr oCond = ljDec.getCondition(); - return nullEquals(condition, oCond) - && ljDec.getRightArgs().equals(rightArgs); - } - return false; - } - - @Override - public int hashCode() { - final int prime = 31; - int result = prime + (rightArgs == null ? 0 : rightArgs.hashCode()); - result = prime * result - + (condition == null ? 0 : condition.hashCode()); - return result; - } - - /** - * This method is used to retrieve a set view of all descendants of the - * rightArg of the LeftJoin (the optional part) - * - * @param tupleExpr - * - tupleExpr whose args are being retrieved - * @param joinArgs - * - set view of all non-join args that are descendants of - * tupleExpr - * @return joinArgs - */ - private Set<TupleExpr> getJoinArgs(TupleExpr tupleExpr, - Set<TupleExpr> joinArgs) { - if (tupleExpr instanceof Join) { - if (!(((Join) tupleExpr).getLeftArg() instanceof FixedStatementPattern) - && !(((Join) tupleExpr).getRightArg() instanceof DoNotExpandSP)) { - Join join = (Join) tupleExpr; - getJoinArgs(join.getLeftArg(), joinArgs); - getJoinArgs(join.getRightArg(), joinArgs); - } - } else if (tupleExpr instanceof LeftJoin) { // TODO probably not - // necessary if not - // including leftarg - LeftJoin lj = (LeftJoin) tupleExpr; - joinArgs.add(new FlattenedOptional(lj)); - getJoinArgs(lj.getLeftArg(), joinArgs); - } else if (tupleExpr instanceof Filter) { - getJoinArgs(((Filter) tupleExpr).getArg(), joinArgs); - } else { - joinArgs.add(tupleExpr); - } - - return joinArgs; - } - - /** - * This method counts the number of times each variable appears in the - * leftArg of the LeftJoin defining this FlattenedOptional. This information - * is used to whether nodes can be moved out of the leftarg above the - * LeftJoin in the query. - * - * @param tupleExpr - */ - private void getVarCounts(TupleExpr tupleExpr) { - if (tupleExpr instanceof Join) { - Join join = (Join) tupleExpr; - getVarCounts(join.getLeftArg()); - getVarCounts(join.getRightArg()); - } else if (tupleExpr instanceof LeftJoin) { - LeftJoin lj = (LeftJoin) tupleExpr; - getVarCounts(lj.getLeftArg()); - } else if (tupleExpr instanceof Filter) { - getVarCounts(((Filter) tupleExpr).getArg()); - } else { - incrementVarCounts(tupleExpr.getBindingNames()); - } - } - - /** - * - * @param te - * - {@link TupleExpr} to be removed from leftArg of LeftJoin - * @return - true if removing te doesn't affect bounded variables of - * LeftJoin and false otherwise - */ - private boolean canRemove(TupleExpr te) { - // can only remove LeftJoin if right varNames do not intersect - // unbound vars - if (te instanceof FlattenedOptional) { - FlattenedOptional lj = (FlattenedOptional) te; - if (Sets.intersection(lj.getRightArg().getBindingNames(), - unboundVars).size() > 0) { - return false; - } else { - return true; - } - } - Set<String> vars = te.getBindingNames(); - Set<String> intersection = Sets.intersection(vars, boundVars); - if (intersection.size() == 0) { - return true; - } - for (String s : intersection) { - if (leftArgVarCounts.containsKey(s) && leftArgVarCounts.get(s) == 1) { - return false; - } - } - return true; - } - - private void incrementVarCounts(Set<String> vars) { - for (String s : vars) { - if (!s.startsWith("-const-") && leftArgVarCounts.containsKey(s)) { - leftArgVarCounts.put(s, leftArgVarCounts.get(s) + 1); - } else if (!s.startsWith("-const-")) { - leftArgVarCounts.put(s, 1); - } - } - } - - private void decrementVarCounts(Set<String> vars) { - for (String s : vars) { - if (leftArgVarCounts.containsKey(s) && leftArgVarCounts.get(s) > 1) { - leftArgVarCounts.put(s, leftArgVarCounts.get(s) - 1); - } else { - leftArgVarCounts.remove(s); - bindingNames.remove(s); - assuredBindingNames.remove(s); - } - } - } - - /** - * - * @param vars - * - set of {@link Var} names, possibly contained constants - */ - private Set<String> setWithOutConstants(Set<String> vars) { - Set<String> copy = new HashSet<>(); - for (String s : vars) { - if (!s.startsWith("-const-")) { - copy.add(s); - } - } - - return copy; - } - - @Override - public <X extends Exception> void visit(QueryModelVisitor<X> visitor) - throws X { - throw new UnsupportedOperationException(); - } - - @Override - public String toString() { - return "FlattenedOptional: " + rightArgs; - } - - @Override - public FlattenedOptional clone() { - return new FlattenedOptional(this); - } - -}
