import org.openrdf.query.algebra.Join; //导入依赖的package包/类
@Override
public void meet(final Join node) throws Exception {
    super.meet(node);

    final TupleExpr leftArg = node.getLeftArg();
    final TupleExpr rightArg = node.getRightArg();

    /**
     * if join(join(1, 2), join(3,4))
     * should be:
     * join(join(join(1,2), 3), 4)
     */
    if (leftArg instanceof Join && rightArg instanceof Join) {
        final Join leftJoin = (Join) leftArg;
        final Join rightJoin = (Join) rightArg;
        final TupleExpr right_LeftArg = rightJoin.getLeftArg();
        final TupleExpr right_rightArg = rightJoin.getRightArg();
        final Join inner = new Join(leftJoin, right_LeftArg);
        final Join outer = new Join(inner, right_rightArg);
        node.replaceWith(outer);
    }

}
 

import org.openrdf.query.algebra.Join; //导入依赖的package包/类
@Override
public void meet(final Filter node) throws Exception {
    super.meet(node);

    final ValueExpr condition = node.getCondition();
    final TupleExpr arg = node.getArg();
    if (!(arg instanceof Join)) {
        return;
    }

    final Join join = (Join) arg;
    final TupleExpr leftArg = join.getLeftArg();
    final TupleExpr rightArg = join.getRightArg();

    if (leftArg instanceof StatementPattern && rightArg instanceof StatementPattern) {
        final Filter left = new Filter(leftArg, condition);
        final Filter right = new Filter(rightArg, condition);
        node.replaceWith(new Join(left, right));
    }

}
 

import org.openrdf.query.algebra.Join; //导入依赖的package包/类
@Override
    public void meet(final Join node) {
      node.getLeftArg().visit(this);
      final double leftArgCost = cardinality;
      // System.out.println("Left cardinality is " + cardinality);
      node.getRightArg().visit(this);

      if (node.getLeftArg() instanceof FixedStatementPattern && node.getRightArg() instanceof DoNotExpandSP) {
        return;
      }

      try {
        final double selectivity = selectEvalStatsDAO.getJoinSelect(config, node.getLeftArg(), node.getRightArg());
//        System.out.println("CardCalc: left cost of " + node.getLeftArg() + " is " + leftArgCost + " right cost of "
//        + node.getRightArg() + " is " + cardinality);
//         System.out.println("Right cardinality is " + cardinality);
        cardinality += leftArgCost + leftArgCost * cardinality * selectivity;
//        System.out.println("CardCalc: Cardinality is " + cardinality);
//        System.out.println("CardCalc: Selectivity is " + selectivity);
        // System.out.println("Join cardinality is " + cardinality);

      } catch (final Exception e) {
        e.printStackTrace();
      }

    }
 

import org.openrdf.query.algebra.Join; //导入依赖的package包/类
@Test
public void testNestedJoins() throws Exception {
    StatementPattern isUndergrad = new StatementPattern(new Var("x"), constant(RDF.TYPE), constant(UNDERGRAD));
    StatementPattern isProfessor = new StatementPattern(new Var("y"), constant(RDF.TYPE), constant(PROFESSOR));
    StatementPattern takesCourse = new StatementPattern(new Var("x"), constant(TAKES), new Var("c"));
    StatementPattern teachesCourse = new StatementPattern(new Var("y"), constant(TEACHES), new Var("c"));
    QueryRoot queryTree = new QueryRoot(new Join(
            isProfessor,
            new Join(
                    new Join(isUndergrad, takesCourse),
                    teachesCourse)));
    SparqlToPipelineTransformVisitor visitor = new SparqlToPipelineTransformVisitor(collection);
    queryTree.visit(visitor);
    Assert.assertTrue(queryTree.getArg() instanceof AggregationPipelineQueryNode);
    AggregationPipelineQueryNode pipelineNode = (AggregationPipelineQueryNode) queryTree.getArg();
    Assert.assertEquals(Sets.newHashSet("x", "y", "c"), pipelineNode.getAssuredBindingNames());
}
 

import org.openrdf.query.algebra.Join; //导入依赖的package包/类
@Test
public void testComplexJoin() throws Exception {
    StatementPattern isUndergrad = new StatementPattern(new Var("x"), constant(RDF.TYPE), constant(UNDERGRAD));
    StatementPattern isProfessor = new StatementPattern(new Var("y"), constant(RDF.TYPE), constant(PROFESSOR));
    StatementPattern takesCourse = new StatementPattern(new Var("x"), constant(TAKES), new Var("c"));
    StatementPattern teachesCourse = new StatementPattern(new Var("y"), constant(TEACHES), new Var("c"));
    QueryRoot queryTree = new QueryRoot(new Join(
            new Join(isUndergrad, takesCourse),
            new Join(isProfessor, teachesCourse)));
    SparqlToPipelineTransformVisitor visitor = new SparqlToPipelineTransformVisitor(collection);
    queryTree.visit(visitor);
    Assert.assertTrue(queryTree.getArg() instanceof Join);
    Join topJoin = (Join) queryTree.getArg();
    Assert.assertTrue(topJoin.getLeftArg() instanceof AggregationPipelineQueryNode);
    Assert.assertTrue(topJoin.getRightArg() instanceof AggregationPipelineQueryNode);
    AggregationPipelineQueryNode leftPipeline = (AggregationPipelineQueryNode) topJoin.getLeftArg();
    AggregationPipelineQueryNode rightPipeline = (AggregationPipelineQueryNode) topJoin.getRightArg();
    Assert.assertEquals(Sets.newHashSet("x", "c"), leftPipeline.getAssuredBindingNames());
    Assert.assertEquals(Sets.newHashSet("y", "c"), rightPipeline.getAssuredBindingNames());
}
 

import org.openrdf.query.algebra.Join; //导入依赖的package包/类
@Test
public void testProjection() throws Exception {
    StatementPattern isUndergrad = new StatementPattern(new Var("x"), constant(RDF.TYPE), constant(UNDERGRAD));
    StatementPattern isCourse = new StatementPattern(new Var("course"), constant(RDF.TYPE), constant(COURSE));
    StatementPattern hasEdge = new StatementPattern(new Var("x"), new Var("p"), new Var("course"));
    ProjectionElemList projectionElements = new ProjectionElemList(
            new ProjectionElem("p", "relation"),
            new ProjectionElem("course"));
    QueryRoot queryTree = new QueryRoot(new Projection(
            new Join(new Join(isCourse, hasEdge), isUndergrad),
            projectionElements));
    SparqlToPipelineTransformVisitor visitor = new SparqlToPipelineTransformVisitor(collection);
    queryTree.visit(visitor);
    Assert.assertTrue(queryTree.getArg() instanceof AggregationPipelineQueryNode);
    AggregationPipelineQueryNode pipelineNode = (AggregationPipelineQueryNode) queryTree.getArg();
    Assert.assertEquals(Sets.newHashSet("relation", "course"), pipelineNode.getAssuredBindingNames());
}
 

import org.openrdf.query.algebra.Join; //导入依赖的package包/类
@Test
public void testMultiProjection() throws Exception {
    StatementPattern isUndergrad = new StatementPattern(new Var("x"), constant(RDF.TYPE), constant(UNDERGRAD));
    StatementPattern isCourse = new StatementPattern(new Var("course"), constant(RDF.TYPE), constant(COURSE));
    StatementPattern hasEdge = new StatementPattern(new Var("x"), new Var("p"), new Var("course"));
    ProjectionElemList courseHasRelation = new ProjectionElemList(
            new ProjectionElem("p", "relation"),
            new ProjectionElem("course"));
    ProjectionElemList studentHasRelation = new ProjectionElemList(
            new ProjectionElem("p", "relation"),
            new ProjectionElem("x", "student"));
    QueryRoot queryTree = new QueryRoot(new MultiProjection(
            new Join(new Join(isCourse, hasEdge), isUndergrad),
            Arrays.asList(courseHasRelation, studentHasRelation)));
    SparqlToPipelineTransformVisitor visitor = new SparqlToPipelineTransformVisitor(collection);
    queryTree.visit(visitor);
    Assert.assertTrue(queryTree.getArg() instanceof AggregationPipelineQueryNode);
    AggregationPipelineQueryNode pipelineNode = (AggregationPipelineQueryNode) queryTree.getArg();
    Assert.assertEquals(Sets.newHashSet("relation"), pipelineNode.getAssuredBindingNames());
    Assert.assertEquals(Sets.newHashSet("relation", "course", "student"), pipelineNode.getBindingNames());
}
 

import org.openrdf.query.algebra.Join; //导入依赖的package包/类
@Test
public void testPeriodicNodePlacement() throws MalformedQueryException {
     String query = "prefix function: <http://org.apache.rya/function#> " //n
            + "prefix time: <http://www.w3.org/2006/time#> " //n
            + "prefix fn: <http://www.w3.org/2006/fn#> " //n
            + "select ?obs ?time ?lat where {" //n
            + "Filter(function:periodic(?time, 12.0, 6.0,time:hours)) " //n
            + "Filter(fn:test(?lat, 25)) " //n
            + "?obs <uri:hasTime> ?time. " //n
            + "?obs <uri:hasLattitude> ?lat }"; //n
     
     SPARQLParser parser = new SPARQLParser();
     ParsedQuery pq = parser.parseQuery(query, null);
     TupleExpr te = pq.getTupleExpr();
     te.visit(new PeriodicQueryNodeVisitor());
     
     PeriodicNodeCollector collector = new PeriodicNodeCollector();
     te.visit(collector);
     
     PeriodicQueryNode node2 = new PeriodicQueryNode(12*60*60*1000L, 6*3600*1000L, TimeUnit.MILLISECONDS, "time", new Join());

     Assert.assertEquals(true, periodicNodesEqualIgnoreArg(node2, collector.getPeriodicQueryNode()));
     
}
 

import org.openrdf.query.algebra.Join; //导入依赖的package包/类
private static void getReOrderings(List<Join> joins, Map<Join, List<TupleExpr>> reOrder,
        List<Map<Join, List<TupleExpr>>> reOrderings) {

    if (joins.isEmpty()) {
        reOrderings.add(reOrder);
        return;
    }

    List<Join> joinsCopy = Lists.newArrayList(joins);
    Join join = joinsCopy.remove(0);
    List<List<TupleExpr>> joinArgPerms = joinArgs.get(join);
    for (List<TupleExpr> tupList : joinArgPerms) {
        Map<Join, List<TupleExpr>> newReOrder = Maps.newHashMap(reOrder);
        newReOrder.put(join, tupList);
        getReOrderings(joinsCopy, newReOrder, reOrderings);
    }
    
    return;

}
 

import org.openrdf.query.algebra.Join; //导入依赖的package包/类
@Override
public void meet(Join node) {

    filterList = Lists.newArrayList();
    
    List<TupleExpr> args = Lists.newArrayList();
    args = getJoinArgs(node, args);
    List<List<TupleExpr>> argPerms = Lists.newArrayList(Collections2.permutations(args));
    joinArgs.put(node, argPerms);
    filterArgs.put(node, filterList);

    for (TupleExpr te : args) {
        if (!(te instanceof StatementPattern) && !(te instanceof ExternalTupleSet)) {
            te.visit(this);
        }
    }

}
 

import org.openrdf.query.algebra.Join; //导入依赖的package包/类
private static List<TupleExpr> getJoinArgs(TupleExpr tupleExpr, List<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);
        } // assumes all filter occur above first join of segment --
          // this should be the state
          // after PrecompJoinOptimizer is called
    } else if (tupleExpr instanceof Filter) {
        filterList.add((Filter) tupleExpr);
        getJoinArgs(((Filter) tupleExpr).getArg(), joinArgs);
    } else {
        joinArgs.add(tupleExpr);
    }

    return joinArgs;
}
 

import org.openrdf.query.algebra.Join; //导入依赖的package包/类
private boolean isJoinValid(Join join) {

        Set<String> leftBindingNames = join.getLeftArg().getBindingNames();
        Set<String> rightBindingNames = join.getRightArg().getBindingNames();

        
        //System.out.println("Left binding names are " + leftBindingNames + " and right binding names are " + rightBindingNames);
        
        if (Sets.intersection(leftBindingNames, rightBindingNames).size() == 0) {
            if (omitCrossProd) {
                return false;
            } else {
                return true;
            }

        } else {
            if (join.getRightArg() instanceof ExternalTupleSet) {

                return ((ExternalTupleSet) join.getRightArg()).supportsBindingSet(leftBindingNames);

            } else {
                return true;
            }
        }

    }
 

import org.openrdf.query.algebra.Join; //导入依赖的package包/类
@Override
public void meet(Join node) {

          if (compSet.contains(node.getRightArg())) {
              this.toBeReplaced = node.getRightArg();
              node.replaceChildNode(node.getRightArg(), replacement);
              return;
          } else if (compSet.contains(node.getLeftArg())) {
              this.toBeReplaced = node.getLeftArg();
              node.replaceChildNode(node.getLeftArg(), replacement);
              return;
          } else {
              super.meet(node);
          }

      }
 

import org.openrdf.query.algebra.Join; //导入依赖的package包/类
@Override
public void meet(Join node) {
    try {
        if (node.getLeftArg() instanceof FixedStatementPattern && node.getRightArg() instanceof DoNotExpandSP) {
            return;
        }
        List<TupleExpr> joinArgs = getJoinArgs(node, new ArrayList<TupleExpr>());
        HashMultimap<String, StatementPattern> varMap = getVarBins(joinArgs);
        while (!varMap.keySet().isEmpty()) {
            String s = getHighestPriorityKey(varMap);
            constructTuple(varMap, joinArgs, s);
        }
        List<TupleExpr> filterChain = getFilterChain(joinArgs);

        for (TupleExpr te : joinArgs) {
            if (!(te instanceof StatementPattern) || !(te instanceof EntityTupleSet)) {
                te.visit(this);
            }
        }
        // Replace old join hierarchy
        node.replaceWith(getNewJoin(joinArgs, filterChain));

    } catch (Exception e) {
        e.printStackTrace();
    }
}
 

import org.openrdf.query.algebra.Join; //导入依赖的package包/类
protected <L extends List<TupleExpr>> L getJoinArgs(TupleExpr tupleExpr, L 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 Filter) {
        joinArgs.add(tupleExpr);
        getJoinArgs(((Filter)tupleExpr).getArg(), joinArgs);
    } else {
        joinArgs.add(tupleExpr);
    }

    return joinArgs;
}
 

import org.openrdf.query.algebra.Join; //导入依赖的package包/类
/**
 *
 * @param tupleExpr
 *            - the query object that will be traversed by this method
 * @param joinArgs
 *            - all nodes connected by Joins and Filters
 * @return - List containing all nodes connected by Joins, LeftJoins, and
 *         Filters. This List contains the
 * @param ValueExpr
 *            in place of the Filter
 */
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 Filter) {
        Filter filter = (Filter) tupleExpr;
        joinArgs.add(filter.getCondition());
        conditionMap.put(filter.getCondition(), filter);
        getJoinArgs(filter.getArg(), joinArgs);
    } else {
        joinArgs.add(tupleExpr);
    }
    return joinArgs;
}
 

import org.openrdf.query.algebra.Join; //导入依赖的package包/类
public QuerySegment<T> getQuerySegment(final QueryModelNode node) {
    Preconditions.checkNotNull(node);
    if(node instanceof Filter) {
        final Filter filter = (Filter)node;
        if(MatcherUtilities.segmentContainsLeftJoins(filter)) {
            return new OptionalJoinSegment<T>(filter);
        } else {
            return new JoinSegment<T>(filter);
        }
    } else if(node instanceof Join) {
        final 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");
    }

}
 

import org.openrdf.query.algebra.Join; //导入依赖的package包/类
/**
 *
 * @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;
}
 

import org.openrdf.query.algebra.Join; //导入依赖的package包/类
/**
 * 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;
}
 

import org.openrdf.query.algebra.Join; //导入依赖的package包/类
private void buildQuery(final TupleExpr tupleExpr, final StatementPattern matchStatement) {
    //If our IndexerExpr (to be) is the rhs-child of LeftJoin, we can safely make that a Join:
    //  the IndexerExpr will (currently) not return results that can deliver unbound variables.
    //This optimization should probably be generalized into a LeftJoin -> Join optimizer under certain conditions. Until that
    //  has been done, this code path at least takes care of queries generated by OpenSahara SparqTool that filter on OPTIONAL
    //  projections. E.g. summary~'full text search' (summary is optional). See #379
    if (matchStatement.getParentNode() instanceof LeftJoin) {
        final LeftJoin leftJoin = (LeftJoin)matchStatement.getParentNode();
        if (leftJoin.getRightArg() == matchStatement && leftJoin.getCondition() == null) {
            matchStatement.getParentNode().replaceWith(new Join(leftJoin.getLeftArg(), leftJoin.getRightArg()));
        }
    }
    final FilterFunction fVisitor = new FilterFunction(matchStatement.getObjectVar().getName());
    tupleExpr.visit(fVisitor);
    final List<IndexingExpr> results = Lists.newArrayList();
    for(int i = 0; i < fVisitor.func.size(); i++){
        results.add(new IndexingExpr(fVisitor.func.get(i), matchStatement, fVisitor.args.get(i)));
    }
    removeMatchedPattern(tupleExpr, matchStatement, new IndexerExprReplacer(results));
}