15 files changed, 1584 insertions, 0 deletions
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/planning/IOperationCompiler.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/planning/IOperationCompiler.java
new file mode 100644
index 00000000..c9f4b305
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/planning/IOperationCompiler.java
@@ -0,0 +1,108 @@
+/*******************************************************************************
+ * Copyright (c) 2004-2008 Gabor Bergmann and Daniel Varro
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v. 2.0 which is available at
+ * http://www.eclipse.org/legal/epl-v20.html.
+ * 
+ * SPDX-License-Identifier: EPL-2.0
+ *******************************************************************************/
+package tools.refinery.viatra.runtime.matchers.planning;
+import java.util.Map;
+import tools.refinery.viatra.runtime.matchers.ViatraQueryRuntimeException;
+import tools.refinery.viatra.runtime.matchers.psystem.IExpressionEvaluator;
+import tools.refinery.viatra.runtime.matchers.psystem.queries.PQuery;
+import tools.refinery.viatra.runtime.matchers.tuple.Tuple;
+import tools.refinery.viatra.runtime.matchers.tuple.TupleMask;
+/**
+ * 
+ * An implicit common parameter is the "effort" PatternDescription. This
+ * indicates that the build request is part of an effort to build the matcher of
+ * the given pattern; it it important to record this during code generation so
+ * that the generated code can be separated according to patterns.
+ * 
+ * @param <Collector>
+ *            the handle of a receiver-like RETE ending to which plans can be
+ *            connected
+ * @author Gabor Bergmann
+ * @noimplement This interface is not intended to be implemented by clients.
+ */
+public interface IOperationCompiler<Collector> {
+    /**
+     * @throws ViatraQueryRuntimeException
+     */
+    public Collector patternCollector(PQuery pattern);
+ 
+    public void buildConnection(SubPlan parentPlan, Collector collector);
+    
+    /**
+     * @since 0.9
+     */
+    public void patternFinished(PQuery pattern, Collector collector);
+    
+    /**
+     * @throws ViatraQueryRuntimeException
+     */
+    public SubPlan patternCallPlan(Tuple nodes, PQuery supplierKey);
+    public SubPlan transitiveInstantiationPlan(Tuple nodes);
+    public SubPlan directInstantiationPlan(Tuple nodes);
+    public SubPlan transitiveGeneralizationPlan(Tuple nodes);
+    public SubPlan directGeneralizationPlan(Tuple nodes);
+    public SubPlan transitiveContainmentPlan(Tuple nodes);
+    public SubPlan directContainmentPlan(Tuple nodes);
+    public SubPlan binaryEdgeTypePlan(Tuple nodes, Object supplierKey);
+    public SubPlan ternaryEdgeTypePlan(Tuple nodes, Object supplierKey);
+    public SubPlan unaryTypePlan(Tuple nodes, Object supplierKey);
+    public SubPlan buildStartingPlan(Object[] constantValues, Object[] constantNames);
+    public SubPlan buildEqualityChecker(SubPlan parentPlan, int[] indices);
+    public SubPlan buildInjectivityChecker(SubPlan parentPlan, int subject, int[] inequalIndices);
+    public SubPlan buildTransitiveClosure(SubPlan parentPlan);
+    public SubPlan buildTrimmer(SubPlan parentPlan, TupleMask trimMask, boolean enforceUniqueness);
+    public SubPlan buildBetaNode(SubPlan primaryPlan, SubPlan sidePlan,
+            TupleMask primaryMask, TupleMask sideMask, TupleMask complementer, boolean negative);
+    public SubPlan buildCounterBetaNode(SubPlan primaryPlan, SubPlan sidePlan,
+            TupleMask primaryMask, TupleMask originalSideMask, TupleMask complementer,
+            Object aggregateResultCalibrationElement);
+    public SubPlan buildCountCheckBetaNode(SubPlan primaryPlan, SubPlan sidePlan,
+            TupleMask primaryMask, TupleMask originalSideMask, int resultPositionInSignature);
+    public SubPlan buildPredicateChecker(IExpressionEvaluator evaluator, Map<String, Integer> tupleNameMap,
+            SubPlan parentPlan);
+    public SubPlan buildFunctionEvaluator(IExpressionEvaluator evaluator, Map<String, Integer> tupleNameMap,
+            SubPlan parentPlan, Object computedResultCalibrationElement);
+    
+    /**
+     * @return an operation compiler that potentially acts on a separate container
+     */
+    public IOperationCompiler<Collector> getNextContainer();
+    /**
+     * @return an operation compiler that puts build actions on the tab of the given pattern
+     * @since 0.9
+     */
+    public IOperationCompiler<Collector> putOnTab(PQuery effort /*, IPatternMatcherContext context*/);
+    public void reinitialize();
+}
+\ No newline at end of file
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/planning/IQueryPlannerStrategy.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/planning/IQueryPlannerStrategy.java
new file mode 100644
index 00000000..6ce9d91b
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/planning/IQueryPlannerStrategy.java
@@ -0,0 +1,29 @@
+/*******************************************************************************
+ * Copyright (c) 2004-2010 Gabor Bergmann and Daniel Varro
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v. 2.0 which is available at
+ * http://www.eclipse.org/legal/epl-v20.html.
+ * 
+ * SPDX-License-Identifier: EPL-2.0
+ *******************************************************************************/
+package tools.refinery.viatra.runtime.matchers.planning;
+import org.apache.log4j.Logger;
+import tools.refinery.viatra.runtime.matchers.ViatraQueryRuntimeException;
+import tools.refinery.viatra.runtime.matchers.context.IQueryMetaContext;
+import tools.refinery.viatra.runtime.matchers.psystem.PBody;
+/**
+ * An algorithm that builds a query plan based on a PSystem representation of a body of constraints. This interface is
+ * for internal use of the various query backends.
+ * 
+ * @author Gabor Bergmann
+ */
+public interface IQueryPlannerStrategy {
+    
+    /**
+     * @throws ViatraQueryRuntimeException
+     */
+    public SubPlan plan(PBody pSystem, Logger logger, IQueryMetaContext context);
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/planning/QueryProcessingException.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/planning/QueryProcessingException.java
new file mode 100644
index 00000000..501ddf73
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/planning/QueryProcessingException.java
@@ -0,0 +1,102 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2013, Zoltan Ujhelyi, Istvan Rath and Daniel Varro
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v. 2.0 which is available at
+ * http://www.eclipse.org/legal/epl-v20.html.
+ * 
+ * SPDX-License-Identifier: EPL-2.0
+ *******************************************************************************/
+package tools.refinery.viatra.runtime.matchers.planning;
+import tools.refinery.viatra.runtime.matchers.ViatraQueryRuntimeException;
+/**
+ * @author Zoltan Ujhelyi
+ * @since 0.9
+ */
+public class QueryProcessingException extends ViatraQueryRuntimeException {
+    private static final long serialVersionUID = -8272290113656867086L;
+    /**
+     * Binding the '{n}' (n = 1..N) strings to contextual conditions in 'context'
+     * 
+     * @param context
+     *            : array of context-sensitive Strings
+     */
+    protected static String bind(String message, String[] context) {
+        if (context == null) 
+            return message;
+    
+        String internal = message;
+        for (int i = 0; i < context.length; i++) {
+            internal = internal.replace("{" + (i + 1) + "}", context[i] != null ? context[i] : "<<null>>");
+        }
+        return internal;
+    }
+    
+    private Object patternDescription;
+    private String shortMessage;
+    /**
+     * @param message
+     *            The template of the exception message
+     * @param context
+     *            The data elements to be used to instantiate the template. Can be null if no context parameter is
+     *            defined
+     * @param patternDescription
+     *            the PatternDescription where the exception occurred
+     * @since 2.0
+     */
+    public QueryProcessingException(String message, Object patternDescription) {
+        super(message);
+        initializeFields(message, patternDescription);
+    }
+    
+    /**
+     * @param message
+     *            The template of the exception message
+     * @param context
+     *            The data elements to be used to instantiate the template. Can be null if no context parameter is
+     *            defined
+     * @param patternDescription
+     *            the PatternDescription where the exception occurred
+     */
+    public QueryProcessingException(String message, String[] context, String shortMessage, Object patternDescription) {
+        super(bind(message, context));
+        initializeFields(shortMessage, patternDescription);
+    }
+    /**
+     * @param message
+     *            The template of the exception message
+     * @param context
+     *            The data elements to be used to instantiate the template. Can be null if no context parameter is
+     *            defined
+     * @param patternDescription
+     *            the PatternDescription where the exception occurred
+     */
+    public QueryProcessingException(String message, String[] context, String shortMessage, Object patternDescription,
+            Throwable cause) {
+        super(bind(message, context), cause);
+        initializeFields(shortMessage, patternDescription);
+    }
+    
+    public Object getPatternDescription() {
+        return patternDescription;
+    }
+    public String getShortMessage() {
+        return shortMessage;
+    }
+    private void initializeFields(String shortMessage, Object patternDescription) {
+        this.patternDescription = patternDescription;
+        this.shortMessage = shortMessage;
+    }
+    
+    public void setPatternDescription(Object patternDescription) {
+        this.patternDescription = patternDescription;
+    }
+}
+\ No newline at end of file
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/planning/SubPlan.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/planning/SubPlan.java
new file mode 100644
index 00000000..1998df9d
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/planning/SubPlan.java
@@ -0,0 +1,240 @@
+/*******************************************************************************
+ * Copyright (c) 2004-2008 Gabor Bergmann and Daniel Varro
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v. 2.0 which is available at
+ * http://www.eclipse.org/legal/epl-v20.html.
+ * 
+ * SPDX-License-Identifier: EPL-2.0
+ *******************************************************************************/
+package tools.refinery.viatra.runtime.matchers.planning;
+import java.util.Arrays;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Set;
+import java.util.WeakHashMap;
+import java.util.stream.Collectors;
+import tools.refinery.viatra.runtime.matchers.context.IQueryMetaContext;
+import tools.refinery.viatra.runtime.matchers.planning.helpers.TypeHelper;
+import tools.refinery.viatra.runtime.matchers.planning.operations.POperation;
+import tools.refinery.viatra.runtime.matchers.planning.operations.PProject;
+import tools.refinery.viatra.runtime.matchers.planning.operations.PStart;
+import tools.refinery.viatra.runtime.matchers.psystem.PBody;
+import tools.refinery.viatra.runtime.matchers.psystem.PConstraint;
+import tools.refinery.viatra.runtime.matchers.psystem.PVariable;
+import tools.refinery.viatra.runtime.matchers.psystem.TypeJudgement;
+/**
+ * A plan representing a subset of (or possibly all the) constraints evaluated. A SubPlan instance is responsible for
+ * representing a state of the plan; but after it is initialized it is expected be immutable 
+ *  (exception: inferred constraints, see {@link #inferConstraint(PConstraint)}).
+ * 
+ * <p> A SubPlan is constructed by applying a {@link POperation} on zero or more parent SubPlans. 
+ * Important maintained information: <ul>
+ * <li>set of <b>variables</b> whose values are known when the runtime evaluation is at this stage,
+ * <li>set of <b>constraints</b> that are known to hold true at this point.
+ * </ul>
+ * 
+ * <p> Recommended to instantiate via a {@link SubPlanFactory} or subclasses, 
+ * so that query planners can subclass SubPlan if needed. 
+ * 
+ * @author Gabor Bergmann
+ * 
+ */
+public class SubPlan {
+    private PBody body;
+    private List<? extends SubPlan> parentPlans;
+    private POperation operation;
+    private final Set<PVariable> visibleVariables; 
+    private final Set<PVariable> allVariables; 
+    private final Set<PVariable> introducedVariables; // delta compared to first parent
+    private Set<PConstraint> allConstraints;
+    private Set<PConstraint> deltaConstraints; // delta compared to all parents
+    private Set<PConstraint> externallyInferredConstraints; // inferred in addition to direct consequences of the operation and parents 
+    
+    
+    
+    
+    /**
+     * A SubPlan is constructed by applying a {@link POperation} on zero or more parent SubPlans.
+     */
+    public SubPlan(PBody body, POperation operation, SubPlan... parentPlans) {
+        this(body, operation, Arrays.asList(parentPlans));
+    }
+    /**
+     * A SubPlan is constructed by applying a {@link POperation} on zero or more parent SubPlans.
+     */
+    public SubPlan(PBody body, POperation operation, List<? extends SubPlan> parentPlans) {
+        super();
+        this.body = body;
+        this.parentPlans = parentPlans;
+        this.operation = operation;
+        
+        this.externallyInferredConstraints = new HashSet<PConstraint>();
+        this.deltaConstraints = new HashSet<PConstraint>(operation.getDeltaConstraints());
+        
+        this.allVariables = new HashSet<PVariable>();
+        for (PConstraint constraint: deltaConstraints) {
+            this.allVariables.addAll(constraint.getDeducedVariables());
+        }
+        this.allConstraints = new HashSet<PConstraint>(deltaConstraints);
+        for (SubPlan parentPlan: parentPlans) {
+            this.allConstraints.addAll(parentPlan.getAllEnforcedConstraints());
+            this.allVariables.addAll(parentPlan.getAllDeducedVariables());
+        }     
+        
+        // TODO this is ugly a bit
+        if (operation instanceof PStart) {
+            this.visibleVariables = new HashSet<PVariable>(((PStart) operation).getAPrioriVariables());
+            this.allVariables.addAll(visibleVariables);
+        } else if (operation instanceof PProject) { 
+            this.visibleVariables = new HashSet<PVariable>(((PProject) operation).getToVariables());
+        } else {
+            this.visibleVariables = new HashSet<PVariable>();
+            for (SubPlan parentPlan: parentPlans)
+                this.visibleVariables.addAll(parentPlan.getVisibleVariables());
+            for (PConstraint constraint: deltaConstraints)
+                this.visibleVariables.addAll(constraint.getDeducedVariables());
+        } 
+        
+        this.introducedVariables = new HashSet<PVariable>(this.visibleVariables);
+        if (!parentPlans.isEmpty()) 
+            introducedVariables.removeAll(parentPlans.get(0).getVisibleVariables());
+        
+        operation.checkConsistency(this);
+    }
+    
+    
+    @Override
+    public String toString() {
+        return toLongString();
+    }
+    public String toShortString() {
+        return String.format("Plan{%s}:%s", 
+                visibleVariables.stream().map(PVariable::getName).collect(Collectors.joining(",")),
+                operation.getShortName());
+    }
+    public String toLongString() {
+        return String.format("%s<%s>", 
+                toShortString(),
+                parentPlans.stream().map(Object::toString).collect(Collectors.joining("; ")));
+    }
+    /**
+     * All constraints that are known to hold at this point
+     */
+    public Set<PConstraint> getAllEnforcedConstraints() {
+        return allConstraints;
+    }
+    /**
+     * The new constraints enforced at this stage of plan, that aren't yet enforced at parents
+     * (results are also included in {@link SubPlan#getAllEnforcedConstraints()})
+     */
+    public Set<PConstraint> getDeltaEnforcedConstraints() {
+        return deltaConstraints;
+    }
+    /**
+     * Indicate that a given constraint was found to be automatically satisfied at this point 
+     *   without additional operations. 
+     * (results are also included in {@link SubPlan#getDeltaEnforcedConstraints()})
+     *   
+     * <p>Warning: not propagated automatically to child plans, 
+     *  so best to invoke before constructing further SubPlans. </p>
+     */
+    public void inferConstraint(PConstraint constraint) {
+        externallyInferredConstraints.add(constraint);
+        deltaConstraints.add(constraint);
+        allConstraints.add(constraint);
+    }
+    
+    public PBody getBody() {
+        return body;
+    }
+    
+    /**
+     * Variables which are assigned a value at this point 
+     * (results are also included in {@link SubPlan#getAllDeducedVariables()})
+     */
+    public Set<PVariable> getVisibleVariables() {
+        return visibleVariables;
+    }
+    /**
+     * Variables which have been assigned a value; 
+     * includes visible variables (see {@link #getVisibleVariables()}) 
+     *   and additionally any variables hidden by a projection (see {@link PProject}). 
+     */
+    public Set<PVariable> getAllDeducedVariables() {
+        return allVariables;
+    }
+    /**
+     * Delta compared to first parent: variables that are visible here but were not visible at the first parent.
+     */
+    public Set<PVariable> getIntroducedVariables() {
+        return introducedVariables;
+    }
+    public List<? extends SubPlan> getParentPlans() {
+        return parentPlans;
+    }
+    public POperation getOperation() {
+        return operation;
+    }
+    
+    
+    /**
+     * The closure of all type judgments of enforced constraints at this point.
+     * <p> No subsumption applied.
+     */
+    public Set<TypeJudgement> getAllImpliedTypeJudgements(IQueryMetaContext context) {
+        Set<TypeJudgement> impliedJudgements = allImpliedTypeJudgements.get(context);
+        if (impliedJudgements == null) {
+            Set<TypeJudgement> equivalentJudgements = TypeHelper.getDirectJudgements(getAllEnforcedConstraints(), context);
+            impliedJudgements = TypeHelper.typeClosure(equivalentJudgements, context);
+            allImpliedTypeJudgements.put(context, impliedJudgements);
+        }
+        return impliedJudgements;
+    }
+    private WeakHashMap<IQueryMetaContext, Set<TypeJudgement>> allImpliedTypeJudgements = new WeakHashMap<IQueryMetaContext, Set<TypeJudgement>>();   
+    
+    
+    @Override
+    public int hashCode() {
+        final int prime = 31;
+        int result = 1;
+        result = prime * result
+                + ((operation == null) ? 0 : operation.hashCode());
+        result = prime * result
+                + ((parentPlans == null) ? 0 : parentPlans.hashCode());
+        return result;
+    }
+    @Override
+    public boolean equals(Object obj) {
+        if (this == obj)
+            return true;
+        if (obj == null)
+            return false;
+        if (!(obj instanceof SubPlan))
+            return false;
+        SubPlan other = (SubPlan) obj;
+        if (operation == null) {
+            if (other.operation != null)
+                return false;
+        } else if (!operation.equals(other.operation))
+            return false;
+        if (parentPlans == null) {
+            if (other.parentPlans != null)
+                return false;
+        } else if (!parentPlans.equals(other.parentPlans))
+            return false;
+        return true;
+    }
+    
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/planning/SubPlanFactory.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/planning/SubPlanFactory.java
new file mode 100644
index 00000000..d0df5fac
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/planning/SubPlanFactory.java
@@ -0,0 +1,33 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2014, Bergmann Gabor, Istvan Rath and Daniel Varro
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v. 2.0 which is available at
+ * http://www.eclipse.org/legal/epl-v20.html.
+ * 
+ * SPDX-License-Identifier: EPL-2.0
+ *******************************************************************************/
+package tools.refinery.viatra.runtime.matchers.planning;
+import tools.refinery.viatra.runtime.matchers.planning.operations.POperation;
+import tools.refinery.viatra.runtime.matchers.psystem.PBody;
+/**
+ * Single entry point for creating subplans.
+ * Can be subclassed by query planner to provide specialized SubPlans.
+ * @author Bergmann Gabor
+ *
+ */
+public class SubPlanFactory {
+    protected PBody body;
+    public SubPlanFactory(PBody body) {
+        super();
+        this.body = body;
+    }
+    
+    public SubPlan createSubPlan(POperation operation, SubPlan... parentPlans) {
+        return new SubPlan(body, operation, parentPlans);               
+    }
+    
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/planning/helpers/BuildHelper.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/planning/helpers/BuildHelper.java
new file mode 100644
index 00000000..ed5d1cbb
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/planning/helpers/BuildHelper.java
@@ -0,0 +1,165 @@
+/*******************************************************************************
+ * Copyright (c) 2004-2010 Gabor Bergmann and Daniel Varro
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v. 2.0 which is available at
+ * http://www.eclipse.org/legal/epl-v20.html.
+ * 
+ * SPDX-License-Identifier: EPL-2.0
+ *******************************************************************************/
+package tools.refinery.viatra.runtime.matchers.planning.helpers;
+import java.util.Collection;
+import java.util.HashSet;
+import java.util.Map;
+import java.util.Set;
+import tools.refinery.viatra.runtime.matchers.ViatraQueryRuntimeException;
+import tools.refinery.viatra.runtime.matchers.context.IQueryMetaContext;
+import tools.refinery.viatra.runtime.matchers.planning.QueryProcessingException;
+import tools.refinery.viatra.runtime.matchers.planning.SubPlan;
+import tools.refinery.viatra.runtime.matchers.planning.SubPlanFactory;
+import tools.refinery.viatra.runtime.matchers.planning.operations.PProject;
+import tools.refinery.viatra.runtime.matchers.psystem.PBody;
+import tools.refinery.viatra.runtime.matchers.psystem.PConstraint;
+import tools.refinery.viatra.runtime.matchers.psystem.PVariable;
+import tools.refinery.viatra.runtime.matchers.psystem.analysis.QueryAnalyzer;
+import tools.refinery.viatra.runtime.matchers.psystem.basicdeferred.ExportedParameter;
+/**
+ * @author Gabor Bergmann
+ * 
+ */
+public class BuildHelper {
+    private BuildHelper() {
+        // Hiding constructor for utility class
+    }
+//    public static SubPlan naturalJoin(IOperationCompiler buildable,
+//            SubPlan primaryPlan, SubPlan secondaryPlan) {
+//        JoinHelper joinHelper = new JoinHelper(primaryPlan, secondaryPlan);
+//        return buildable.buildBetaNode(primaryPlan, secondaryPlan, joinHelper.getPrimaryMask(),
+//                joinHelper.getSecondaryMask(), joinHelper.getComplementerMask(), false);
+//    }
+    
+    
+    /**
+     * Reduces the number of tuples by trimming (existentially quantifying) the set of variables that <ul>
+     * <li> are visible in the subplan, 
+     * <li> are not exported parameters, 
+     * <li> have all their constraints already enforced in the subplan,
+     * </ul> and thus will not be needed anymore.
+     * 
+     * @param onlyIfNotDetermined if true, no trimming performed unless there is at least one variable that is not functionally determined
+     * @return the plan after the trimming (possibly the original)
+     * @since 1.5
+     */
+    public static SubPlan trimUnneccessaryVariables(SubPlanFactory planFactory, /*IOperationCompiler buildable,*/
+            SubPlan plan, boolean onlyIfNotDetermined, QueryAnalyzer analyzer) {
+        Set<PVariable> canBeTrimmed = new HashSet<PVariable>();
+        Set<PVariable> variablesInPlan = plan.getVisibleVariables();
+        for (PVariable trimCandidate : variablesInPlan) {
+            if (trimCandidate.getReferringConstraintsOfType(ExportedParameter.class).isEmpty()) {
+                if (plan.getAllEnforcedConstraints().containsAll(trimCandidate.getReferringConstraints()))
+                    canBeTrimmed.add(trimCandidate);
+            }
+        }
+        final Set<PVariable> retainedVars = setMinus(variablesInPlan, canBeTrimmed);    
+        if (!canBeTrimmed.isEmpty() && !(onlyIfNotDetermined && areVariablesDetermined(plan, retainedVars, canBeTrimmed, analyzer, false))) {
+            // TODO add smart ordering? 
+            plan = planFactory.createSubPlan(new PProject(retainedVars), plan);
+        }
+        return plan;
+    }
+    
+    /**
+     * @return true iff a set of given variables functionally determine all visible variables in the subplan according to the subplan's constraints
+     * @param strict if true, only "hard" dependencies are taken into account that are strictly enforced by the model representation; 
+     *  if false, user-provided soft dependencies are included as well, that are anticipated but not guaranteed by the storage mechanism;
+     *  use true if superfluous dependencies may taint the correctness of a computation, false if they would merely impact performance
+     * @since 1.5
+     */
+    public static boolean areAllVariablesDetermined(SubPlan plan, Collection<PVariable> determining, QueryAnalyzer analyzer, boolean strict) {
+        return areVariablesDetermined(plan, determining, plan.getVisibleVariables(), analyzer, strict);
+    }
+    
+    /**
+     * @return true iff one set of given variables functionally determine the other set according to the subplan's constraints
+     * @param strict if true, only "hard" dependencies are taken into account that are strictly enforced by the model representation; 
+     *  if false, user-provided soft dependencies are included as well, that are anticipated but not guaranteed by the storage mechanism;
+     *  use true if superfluous dependencies may taint the correctness of a computation, false if they would merely impact performance
+     * @since 1.5
+     */
+    public static boolean areVariablesDetermined(SubPlan plan, Collection<PVariable> determining, Collection<PVariable> determined, 
+            QueryAnalyzer analyzer, boolean strict) {
+        Map<Set<PVariable>, Set<PVariable>> dependencies = analyzer.getFunctionalDependencies(plan.getAllEnforcedConstraints(), strict);
+        final Set<PVariable> closure = FunctionalDependencyHelper.closureOf(determining, dependencies);
+        final boolean isDetermined = closure.containsAll(determined);
+        return isDetermined;
+    }
+    private static <T> Set<T> setMinus(Set<T> a, Set<T> b) {
+        Set<T> difference = new HashSet<T>(a);
+        difference.removeAll(b);
+        return difference;
+    }
+    
+    /**
+     * Finds an arbitrary constraint that is not enforced at the given plan.
+     * 
+     * @param pSystem
+     * @param plan
+     * @return a PConstraint that is not enforced, if any, or null if all are enforced
+     */
+    public static PConstraint getAnyUnenforcedConstraint(PBody pSystem,
+            SubPlan plan) {
+        Set<PConstraint> allEnforcedConstraints = plan.getAllEnforcedConstraints();
+        Set<PConstraint> constraints = pSystem.getConstraints();
+        for (PConstraint pConstraint : constraints) {
+            if (!allEnforcedConstraints.contains(pConstraint))
+                return pConstraint;
+        }
+        return null;
+    }
+    
+    /**
+     * Skips the last few steps, if any, that are projections, so that a custom projection can be added instead.
+     * Useful for connecting body final plans into the production node.
+     * 
+     * @since 2.1
+     */
+    public static SubPlan eliminateTrailingProjections(SubPlan plan) {
+        while (plan.getOperation() instanceof PProject)
+            plan = plan.getParentPlans().get(0);
+        return plan;
+    }
+    /**
+     * Verifies whether all constraints are enforced and exported parameters are present.
+     * 
+     * @param pSystem
+     * @param plan
+     * @throws ViatraQueryRuntimeException
+     */
+    public static void finalCheck(final PBody pSystem, SubPlan plan, IQueryMetaContext context) {
+        PConstraint unenforcedConstraint = getAnyUnenforcedConstraint(pSystem, plan);
+        if (unenforcedConstraint != null) {
+            throw new QueryProcessingException(
+                    "Pattern matcher construction terminated without successfully enforcing constraint {1}."
+                            + " Could be caused if the value of some variables can not be deduced, e.g. by circularity of pattern constraints.",
+                    new String[] { unenforcedConstraint.toString() }, "Could not enforce a pattern constraint", null);
+        }
+        for (ExportedParameter export : pSystem
+                .getConstraintsOfType(ExportedParameter.class)) {
+            if (!export.isReadyAt(plan, context)) {
+                throw new QueryProcessingException(
+                        "Exported pattern parameter {1} could not be deduced during pattern matcher construction."
+                                + " A pattern constraint is required to positively deduce its value.",
+                        new String[] { export.getParameterName() }, "Could not calculate pattern parameter",
+                        null);
+            }
+        }
+    }    
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/planning/helpers/FunctionalDependencyHelper.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/planning/helpers/FunctionalDependencyHelper.java
new file mode 100644
index 00000000..40835f52
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/planning/helpers/FunctionalDependencyHelper.java
@@ -0,0 +1,143 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2013, Adam Dudas, Istvan Rath and Daniel Varro
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v. 2.0 which is available at
+ * http://www.eclipse.org/legal/epl-v20.html.
+ * 
+ * SPDX-License-Identifier: EPL-2.0
+ *******************************************************************************/
+package tools.refinery.viatra.runtime.matchers.planning.helpers;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Map;
+import java.util.Map.Entry;
+import java.util.Set;
+import tools.refinery.viatra.runtime.matchers.util.Sets;
+/**
+ * Helper utility class for functional dependency analysis.
+ * 
+ * Throughout this class attribute sets are represented as generic sets and functional dependencies as maps from
+ * attribute set (generic sets) to attribute set (generic sets)
+ * 
+ * @author Adam Dudas
+ * 
+ */
+public class FunctionalDependencyHelper {
+    
+    private FunctionalDependencyHelper() {
+        // Hiding constructor for utility class
+    }
+    
+    /**
+     * Get the closure of the specified attribute set relative to the specified functional dependencies.
+     * 
+     * @param attributes
+     *            The attributes to get the closure of.
+     * @param dependencies
+     *            The functional dependencies of which the closure operation is relative to.
+     * @return The closure of the specified attribute set relative to the specified functional dependencies.
+     */
+    public static <A> Set<A> closureOf(Collection<A> attributes, Map<Set<A>, Set<A>> dependencies) {
+        Set<A> closureSet = new HashSet<A>();
+        for (Set<A> closureSet1 = new HashSet<A>(attributes); closureSet.addAll(closureSet1);) {
+            closureSet1 = new HashSet<A>();
+            for (Entry<Set<A>, Set<A>> dependency : dependencies.entrySet()) {
+                if (closureSet.containsAll(dependency.getKey()))
+                    closureSet1.addAll(dependency.getValue());
+            }
+        }
+        return closureSet;
+    }
+    
+    /**
+     * @return true if the dependency from the left set to the right set is trivial
+     * @since 1.5
+     */
+    public static <A> boolean isTrivial(Set<A> left, Set<A> right) {
+        return left.containsAll(right);
+    }
+    
+    /***
+     * Returns the dependency set over attributes in {@link targetAttributes} that are implied by a given source dependency set.
+     * <p> Note: exponential in the size of the target attribute set.
+     * <p> Note: minimality of the returned dependency set is currently not guaranteed.
+     * @param originalDependencies all dependencies that are known to hold on a wider set of attributes
+     * @param targetAttributes the set of attributes we are interested in
+     * @since 1.5
+     */
+    public static <A> Map<Set<A>, Set<A>> projectDependencies(Map<Set<A>, Set<A>> originalDependencies, Set<A> targetAttributes) {
+        // only those attributes are considered as left-hand-side candidates that occur at least once in dependencies
+        Set<A> leftCandidates = new HashSet<A>(); 
+        for (Entry<Set<A>, Set<A>> dependency : originalDependencies.entrySet()) {
+            if (!isTrivial(dependency.getKey(), dependency.getValue())) // only if non-trivial
+                leftCandidates.addAll(Sets.intersection(dependency.getKey(), targetAttributes));
+        }
+        
+        // Compute an initial list of nontrivial projected dependencies - it does not have to be minimal yet
+        Map<Set<A>, Set<A>> initialDependencies = new HashMap<Set<A>, Set<A>>();
+        for (Set<A> leftSet : Sets.powerSet(leftCandidates)) {
+            Set<A> rightSet = Sets.intersection(closureOf(leftSet, originalDependencies), targetAttributes);
+            if (!isTrivial(leftSet, rightSet)) {
+                initialDependencies.put(leftSet, rightSet);
+            }
+        }
+        // Don't forget to include constants!
+        Set<A> constants = Sets.intersection(closureOf(Collections.<A>emptySet(), originalDependencies), targetAttributes);
+        if (! constants.isEmpty()) {
+            initialDependencies.put(Collections.<A>emptySet(), constants);
+        }
+        
+        // Omit those dependencies where the LHS has superfluous attributes
+        Map<Set<A>, Set<A>> solidDependencies = new HashMap<Set<A>, Set<A>>();
+        for (Entry<Set<A>, Set<A>> dependency : initialDependencies.entrySet()) {
+            Set<A> leftSet = dependency.getKey();
+            Set<A> rightSet = dependency.getValue();
+            boolean solid = true;
+            for (A skipped : leftSet) { // what if we skip one attribute from the left set?
+                Set<A> singleton = Collections.singleton(skipped);
+                Set<A> candidate = Sets.difference(leftSet, singleton);
+                Set<A> rightCandidate = initialDependencies.get(candidate);
+                if (rightCandidate != null) {
+                    if (Sets.union(rightCandidate, singleton).containsAll(rightSet)) {
+                        solid = false;
+                        break;
+                    }
+                }
+            }
+            if (solid) {
+                solidDependencies.put(leftSet, rightSet);
+            }
+        }
+        
+        // TODO perform proper minimization, 
+        // see e.g. page 45 in http://www.cs.ubc.ca/~hkhosrav/db/slides/03.design%20theory.pdf
+        
+        return Collections.unmodifiableMap(solidDependencies);
+    }
+    
+    /**
+     * Adds a given dependency to a mutable accumulator.
+     * @since 1.5
+     */
+    public static <A> void includeDependency(Map<Set<A>, Set<A>> accumulator, Set<A> left, Set<A> right) {
+        Set<A> accumulatorRights = accumulator.computeIfAbsent(left, l -> new HashSet<>());
+        accumulatorRights.addAll(right);
+    }    
+    
+    /**
+     * Adds all given dependencies to a mutable accumulator.
+     * @since 1.5
+     */
+    public static <A> void includeDependencies(Map<Set<A>, Set<A>> accumulator, Map<Set<A>, Set<A>> additionalDependencies) {
+        for (Entry<Set<A>, Set<A>> entry : additionalDependencies.entrySet()) {
+            includeDependency(accumulator, entry.getKey(), entry.getValue());
+        }
+    }
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/planning/helpers/StatisticsHelper.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/planning/helpers/StatisticsHelper.java
new file mode 100644
index 00000000..b4f848a7
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/planning/helpers/StatisticsHelper.java
@@ -0,0 +1,62 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2018, Gabor Bergmann, IncQuery Labs Ltd.
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v. 2.0 which is available at
+ * http://www.eclipse.org/legal/epl-v20.html.
+ * 
+ * SPDX-License-Identifier: EPL-2.0
+ *******************************************************************************/
+package tools.refinery.viatra.runtime.matchers.planning.helpers;
+import java.util.Optional;
+import java.util.function.BiFunction;
+import tools.refinery.viatra.runtime.matchers.tuple.TupleMask;
+import tools.refinery.viatra.runtime.matchers.util.Accuracy;
+/**
+ * Helpers dealing with optionally present statistics information 
+ * 
+ * @author Gabor Bergmann
+ * @since 2.1
+ *
+ */
+public class StatisticsHelper {
+    
+    private StatisticsHelper() {
+        // Hidden utility class constructor
+    }
+    
+    public static Optional<Double> estimateAverageBucketSize(TupleMask groupMask, Accuracy requiredAccuracy, 
+            BiFunction<TupleMask, Accuracy, Optional<Long>> estimateCardinality) 
+    {
+        if (groupMask.isIdentity()) return Optional.of(1.0);
+        
+        Accuracy numeratorAccuracy = requiredAccuracy;
+        Accuracy denominatorAccuracy = requiredAccuracy.reciprocal();
+        TupleMask identityMask = TupleMask.identity(groupMask.sourceWidth);
+        
+        Optional<Long> totalCountEstimate  = estimateCardinality.apply(identityMask, numeratorAccuracy);
+        Optional<Long> bucketCountEstimate = estimateCardinality.apply(groupMask,    denominatorAccuracy);
+        return totalCountEstimate.flatMap(matchCount -> 
+            bucketCountEstimate.map(bucketCount -> 
+                bucketCount == 0L ? 0L : ((double) matchCount) / bucketCount
+        ));
+    }
+    public static Optional<Double> min(Optional<Double> a,  Optional<Double> b) {
+        if (b.isPresent()) {
+            if (a.isPresent()) {
+                return Optional.of(Math.min(a.get(), b.get()));
+            } else return b;
+        } else return a;
+    }
+    public static Optional<Double> min(Optional<Double> a, double b) {
+        if (a.isPresent()) {
+            return Optional.of(Math.min(a.get(), b));
+        } else return Optional.of(b);
+    }
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/planning/helpers/TypeHelper.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/planning/helpers/TypeHelper.java
new file mode 100644
index 00000000..926a591f
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/planning/helpers/TypeHelper.java
@@ -0,0 +1,217 @@
+/*******************************************************************************
+ * Copyright (c) 2004-2010 Gabor Bergmann and Daniel Varro
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v. 2.0 which is available at
+ * http://www.eclipse.org/legal/epl-v20.html.
+ * 
+ * SPDX-License-Identifier: EPL-2.0
+ *******************************************************************************/
+package tools.refinery.viatra.runtime.matchers.planning.helpers;
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.LinkedList;
+import java.util.Map;
+import java.util.Map.Entry;
+import java.util.Queue;
+import java.util.Set;
+import java.util.stream.Collectors;
+import tools.refinery.viatra.runtime.matchers.context.IInputKey;
+import tools.refinery.viatra.runtime.matchers.context.IQueryMetaContext;
+import tools.refinery.viatra.runtime.matchers.psystem.ITypeInfoProviderConstraint;
+import tools.refinery.viatra.runtime.matchers.psystem.PConstraint;
+import tools.refinery.viatra.runtime.matchers.psystem.PVariable;
+import tools.refinery.viatra.runtime.matchers.psystem.TypeJudgement;
+/**
+ * @author Gabor Bergmann
+ * @author Tamas Szabo
+ */
+public class TypeHelper {
+    
+    private TypeHelper() {
+        // Hiding constructor for utility class
+    }
+    /**
+     * Collects the type constraints for the specified collection of variables. The type constraints consist of the
+     * constraints directly enforced on the variable itself, plus all of those that the given variable is unified with
+     * through equalities.
+     * 
+     * @param variables
+     *            the variables in question
+     * @param constraints
+     *            the constraints in the pattern body
+     * @param context
+     *            the query meta context
+     * @return the mapping from variable to set of type constraints
+     * @since 1.6
+     */
+    public static Map<PVariable, Set<IInputKey>> inferUnaryTypesFor(Iterable<PVariable> variables,
+            Set<PConstraint> constraints, IQueryMetaContext context) {
+        Map<PVariable, Set<TypeJudgement>> typeMap = TypeHelper.inferUnaryTypes(constraints, context);
+        return inferUnaryTypesFor(variables, typeMap);
+    }
+    /**
+     * Collects the type constraints for the specified collection of variables. The type constraints consist of the
+     * constraints directly enforced on the variable itself, plus all of those that the given variable is unified with
+     * through equalities.
+     * 
+     * The method accepts a type map which is the result of the basic type inference from the
+     * {@link TypeHelper.inferUnaryTypes} method. The purpose of this method is that the type map can be reused across
+     * several calls to this method.
+     * 
+     * @param variables
+     *            the variables in question
+     * @param typeMap
+     *            the type map of inference results
+     * @return the mapping from variable to set of type constraints
+     * @since 1.6
+     */
+    public static Map<PVariable, Set<IInputKey>> inferUnaryTypesFor(Iterable<PVariable> variables,
+            Map<PVariable, Set<TypeJudgement>> typeMap) {
+        Map<PVariable, Set<IInputKey>> result = new HashMap<PVariable, Set<IInputKey>>();
+        for (PVariable original : variables) {
+            // it can happen that the variable was unified into an other one due to equalities
+            Set<IInputKey> keys = new HashSet<IInputKey>();
+            PVariable current = original;
+            while (current != null) {
+                Set<TypeJudgement> judgements = typeMap.get(current);
+                if (judgements != null) {
+                    for (TypeJudgement judgement : judgements) {
+                        keys.add(judgement.getInputKey());
+                    }
+                }
+                current = current.getDirectUnifiedInto();
+            }
+            result.put(original, keys);
+        }
+        return result;
+    }
+    /**
+     * Infers unary type information for variables, based on the given constraints.
+     * 
+     * Subsumptions are not taken into account.
+     * 
+     * @param constraints
+     *            the set of constraints to extract type info from
+     */
+    public static Map<PVariable, Set<TypeJudgement>> inferUnaryTypes(Set<PConstraint> constraints,
+            IQueryMetaContext context) {
+        Set<TypeJudgement> equivalentJudgements = getDirectJudgements(constraints, context);
+        Set<TypeJudgement> impliedJudgements = typeClosure(equivalentJudgements, context);
+        Map<PVariable, Set<TypeJudgement>> results = new HashMap<PVariable, Set<TypeJudgement>>();
+        for (TypeJudgement typeJudgement : impliedJudgements) {
+            final IInputKey inputKey = typeJudgement.getInputKey();
+            if (inputKey.getArity() == 1) {
+                PVariable variable = (PVariable) typeJudgement.getVariablesTuple().get(0);
+                Set<TypeJudgement> inferredTypes = results.computeIfAbsent(variable, v -> new HashSet<>());
+                inferredTypes.add(typeJudgement);
+            }
+        }
+        return results;
+    }
+    /**
+     * Gets direct judgements reported by constraints. No closure is applied yet.
+     */
+    public static Set<TypeJudgement> getDirectJudgements(Set<PConstraint> constraints, IQueryMetaContext context) {
+        Set<TypeJudgement> equivalentJudgements = new HashSet<TypeJudgement>();
+        for (PConstraint pConstraint : constraints) {
+            if (pConstraint instanceof ITypeInfoProviderConstraint) {
+                equivalentJudgements.addAll(((ITypeInfoProviderConstraint) pConstraint).getImpliedJudgements(context));
+            }
+        }
+        return equivalentJudgements;
+    }
+    /**
+     * Calculates the closure of a set of type judgements, with respect to supertyping.
+     * 
+     * @return the set of all type judgements in typesToClose and all their direct and indirect supertypes
+     */
+    public static Set<TypeJudgement> typeClosure(Set<TypeJudgement> typesToClose, IQueryMetaContext context) {
+        return typeClosure(Collections.<TypeJudgement> emptySet(), typesToClose, context);
+    }
+    /**
+     * Calculates the closure of a set of type judgements (with respect to supertyping), where the closure has been
+     * calculated before for a given base set, but not for a separate delta set.
+     * <p>
+     * Precondition: the set (typesToClose MINUS delta) is already closed w.r.t. supertyping.
+     * 
+     * @return the set of all type judgements in typesToClose and all their direct and indirect supertypes
+     * @since 1.6
+     */
+    public static Set<TypeJudgement> typeClosure(Set<TypeJudgement> preclosedBaseSet, Set<TypeJudgement> delta,
+            IQueryMetaContext context) {
+        Queue<TypeJudgement> queue = delta.stream().filter(input -> !preclosedBaseSet.contains(input)).collect(Collectors.toCollection(LinkedList::new)); 
+        if (queue.isEmpty())
+            return preclosedBaseSet;
+        
+        Set<TypeJudgement> closure = new HashSet<TypeJudgement>(preclosedBaseSet);
+        Map<TypeJudgement, Set<TypeJudgement>> conditionalImplications = new HashMap<>();
+        for (TypeJudgement typeJudgement : closure) {
+            conditionalImplications.putAll(typeJudgement.getConditionalImpliedJudgements(context));
+        }
+        do {
+            TypeJudgement deltaType = queue.poll();
+            if (closure.add(deltaType)) {
+                // direct implications
+                queue.addAll(deltaType.getDirectlyImpliedJudgements(context));
+                // conditional implications, source key processed before, this is the condition key
+                final Set<TypeJudgement> implicationSet = conditionalImplications.get(deltaType);
+                if (implicationSet != null) {
+                     queue.addAll(implicationSet);
+                }
+                // conditional implications, this is the source key
+                Map<TypeJudgement, Set<TypeJudgement>> deltaConditionalImplications = deltaType
+                        .getConditionalImpliedJudgements(context);
+                for (Entry<TypeJudgement, Set<TypeJudgement>> entry : deltaConditionalImplications.entrySet()) {
+                    if (closure.contains(entry.getKey())) {
+                        // condition processed before
+                        queue.addAll(entry.getValue());
+                    } else {
+                        // condition not processed yet
+                        conditionalImplications.computeIfAbsent(entry.getKey(), key -> new HashSet<>())
+                                .addAll(entry.getValue());
+                    }
+                }
+            }
+        } while (!queue.isEmpty());
+        return closure;
+    }
+    /**
+     * Calculates a remainder set of types from a larger set, that are not subsumed by a given set of subsuming types.
+     * 
+     * @param subsumableTypes
+     *            a set of types from which some may be implied by the subsuming types
+     * @param subsumingTypes
+     *            a set of types that may imply some of the subsuming types
+     * @return the collection of types in subsumableTypes that are NOT identical to or supertypes of any type in
+     *         subsumingTypes.
+     */
+    public static Set<TypeJudgement> subsumeTypes(Set<TypeJudgement> subsumableTypes, Set<TypeJudgement> subsumingTypes,
+            IQueryMetaContext context) {
+        Set<TypeJudgement> closure = typeClosure(subsumingTypes, context);
+        Set<TypeJudgement> subsumed = new HashSet<TypeJudgement>(subsumableTypes);
+        subsumed.removeAll(closure);
+        return subsumed;
+    }
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/planning/operations/PApply.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/planning/operations/PApply.java
new file mode 100644
index 00000000..2c285b54
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/planning/operations/PApply.java
@@ -0,0 +1,94 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2014, Bergmann Gabor, Istvan Rath and Daniel Varro
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v. 2.0 which is available at
+ * http://www.eclipse.org/legal/epl-v20.html.
+ * 
+ * SPDX-License-Identifier: EPL-2.0
+ *******************************************************************************/
+package tools.refinery.viatra.runtime.matchers.planning.operations;
+import java.util.Collections;
+import java.util.Set;
+import tools.refinery.viatra.runtime.matchers.planning.SubPlan;
+import tools.refinery.viatra.runtime.matchers.psystem.PConstraint;
+import tools.refinery.viatra.runtime.matchers.util.Preconditions;
+/**
+ * Represents a constraint application on a single parent SubPlan. 
+ * <p> Either a "selection" filter operation according to a deferred PConstraint (or transform in case of eval/aggregate), or
+ * alternatively a shorthand for PJoin + a PEnumerate on the right input for an enumerable PConstraint.
+ * 
+ * <p> <b>WARNING</b>: if there are coinciding variables in the variable tuple of the enumerable constraint, 
+ *   it is the responsibility of the compiler to check them for equality.
+ * 
+ * @author Bergmann Gabor
+ *
+ */
+public class PApply extends POperation {
+    
+    private PConstraint pConstraint;
+    public PApply(PConstraint pConstraint) {
+        super();
+        this.pConstraint = pConstraint;
+    }
+    public PConstraint getPConstraint() {
+        return pConstraint;
+    }
+    @Override
+    public String getShortName() {
+        return String.format("APPLY_%s", pConstraint.toString());
+    }
+    
+    @Override
+    public Set<? extends PConstraint> getDeltaConstraints() {
+        return Collections.singleton(pConstraint);
+    }
+    
+    @Override
+    public int numParentSubPlans() {
+        return 1;
+    }
+    
+    @Override
+    public void checkConsistency(SubPlan subPlan) {
+        super.checkConsistency(subPlan);
+        for (SubPlan parentPlan : subPlan.getParentPlans())
+            Preconditions.checkArgument(!parentPlan.getAllEnforcedConstraints().contains(pConstraint),
+                    "Double-checking constraint %s", pConstraint);              
+        // TODO obtain context?
+        //if (pConstraint instanceof DeferredPConstraint)
+        //      Preconditions.checkArgument(((DeferredPConstraint) pConstraint).isReadyAt(subPlan, context))
+    }
+    
+    @Override
+    public int hashCode() {
+        final int prime = 31;
+        int result = 1;
+        result = prime
+                * result
+                + ((pConstraint == null) ? 0 : pConstraint
+                        .hashCode());
+        return result;
+    }
+    @Override
+    public boolean equals(Object obj) {
+        if (this == obj)
+            return true;
+        if (obj == null)
+            return false;
+        if (!(obj instanceof PApply))
+            return false;
+        PApply other = (PApply) obj;
+        if (pConstraint == null) {
+            if (other.pConstraint != null)
+                return false;
+        } else if (!pConstraint.equals(other.pConstraint))
+            return false;
+        return true;
+    }
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/planning/operations/PEnumerate.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/planning/operations/PEnumerate.java
new file mode 100644
index 00000000..a975d50c
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/planning/operations/PEnumerate.java
@@ -0,0 +1,76 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2014, Bergmann Gabor, Istvan Rath and Daniel Varro
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v. 2.0 which is available at
+ * http://www.eclipse.org/legal/epl-v20.html.
+ * 
+ * SPDX-License-Identifier: EPL-2.0
+ *******************************************************************************/
+package tools.refinery.viatra.runtime.matchers.planning.operations;
+import java.util.Collections;
+import java.util.Set;
+import tools.refinery.viatra.runtime.matchers.psystem.EnumerablePConstraint;
+import tools.refinery.viatra.runtime.matchers.psystem.PConstraint;
+/**
+ * Represents a base relation defined by the instance set of an enumerable PConstraint; there are no parent SubPlans.
+ * 
+ * <p> <b>WARNING</b>: if there are coinciding variables in the variable tuple of the enumerable constraint, 
+ *   it is the responsibility of the compiler to check them for equality.
+ * @author Bergmann Gabor
+ *
+ */
+public class PEnumerate extends POperation {
+    EnumerablePConstraint enumerablePConstraint;
+    
+    public PEnumerate(EnumerablePConstraint enumerablePConstraint) {
+        super();
+        this.enumerablePConstraint = enumerablePConstraint;
+    }
+    public EnumerablePConstraint getEnumerablePConstraint() {
+        return enumerablePConstraint;
+    }
+    @Override
+    public Set<? extends PConstraint> getDeltaConstraints() {
+        return Collections.singleton(enumerablePConstraint);
+    }
+    @Override
+    public int numParentSubPlans() {
+        return 0;
+    }
+    @Override
+    public String getShortName() {
+        return enumerablePConstraint.toString();
+    }
+    @Override
+    public int hashCode() {
+        final int prime = 31;
+        int result = 1;
+        result = prime
+                * result
+                + ((enumerablePConstraint == null) ? 0 : enumerablePConstraint
+                        .hashCode());
+        return result;
+    }
+    @Override
+    public boolean equals(Object obj) {
+        if (this == obj)
+            return true;
+        if (obj == null)
+            return false;
+        if (!(obj instanceof PEnumerate))
+            return false;
+        PEnumerate other = (PEnumerate) obj;
+        if (enumerablePConstraint == null) {
+            if (other.enumerablePConstraint != null)
+                return false;
+        } else if (!enumerablePConstraint.equals(other.enumerablePConstraint))
+            return false;
+        return true;
+    }
+    
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/planning/operations/PJoin.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/planning/operations/PJoin.java
new file mode 100644
index 00000000..10e0a85a
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/planning/operations/PJoin.java
@@ -0,0 +1,64 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2014, Bergmann Gabor, Istvan Rath and Daniel Varro
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v. 2.0 which is available at
+ * http://www.eclipse.org/legal/epl-v20.html.
+ * 
+ * SPDX-License-Identifier: EPL-2.0
+ *******************************************************************************/
+package tools.refinery.viatra.runtime.matchers.planning.operations;
+import java.util.Collections;
+import java.util.Set;
+import tools.refinery.viatra.runtime.matchers.psystem.PConstraint;
+/**
+ * Represents a natural join of two parent SubPlans.
+ * @author Bergmann Gabor
+ *
+ */
+public class PJoin extends POperation {
+    
+//      // TODO leave here? is this a problem in equivalnece checking?
+//      private Set<PVariable> onVariables;
+    public PJoin(/*Set<PVariable> onVariables*/) {
+        super();
+        //this.onVariables = new HashSet<PVariable>(onVariables);
+    }
+//      public Set<PVariable> getOnVariables() {
+//              return onVariables;
+//      }
+    @Override
+    public Set<? extends PConstraint> getDeltaConstraints() {
+        return Collections.emptySet();
+    }
+    @Override
+    public int numParentSubPlans() {
+        return 2;
+    }
+    @Override
+    public String getShortName() {
+        return "JOIN"; //String.format("JOIN_{%s}", Joiner.on(",").join(onVariables));
+    }
+    
+    @Override
+    public int hashCode() {
+        return getClass().hashCode();
+    }
+    @Override
+    public boolean equals(Object obj) {
+        if (this == obj)
+            return true;
+        if (obj == null)
+            return false;
+        if (!(obj instanceof PJoin))
+            return false;
+        return true;
+    }
+    
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/planning/operations/POperation.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/planning/operations/POperation.java
new file mode 100644
index 00000000..e71cf217
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/planning/operations/POperation.java
@@ -0,0 +1,52 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2014, Bergmann Gabor, Istvan Rath and Daniel Varro
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v. 2.0 which is available at
+ * http://www.eclipse.org/legal/epl-v20.html.
+ * 
+ * SPDX-License-Identifier: EPL-2.0
+ *******************************************************************************/
+package tools.refinery.viatra.runtime.matchers.planning.operations;
+import java.util.Set;
+import tools.refinery.viatra.runtime.matchers.planning.SubPlan;
+import tools.refinery.viatra.runtime.matchers.psystem.PConstraint;
+import tools.refinery.viatra.runtime.matchers.util.Preconditions;
+/**
+ * Abstract superclass for representing a high-level query evaluation operation.
+ * 
+ *  <p> Subclasses correspond to various POperations modeled after relational algebra.  
+ * 
+ * @author Bergmann Gabor
+ *
+ */
+public abstract class POperation {
+    /**
+     * Newly enforced constraints
+     */
+    public abstract Set<? extends PConstraint> getDeltaConstraints();
+    
+    public abstract String getShortName();
+    
+    /**
+     * @return the number of SubPlans that must be specified as parents
+     */
+    public abstract int numParentSubPlans();
+    
+    /**
+     * Checks whether this constraint can be properly applied at the given SubPlan.
+     */
+    public void checkConsistency(SubPlan subPlan) {
+        Preconditions.checkArgument(this == subPlan.getOperation(), "POperation misalignment");
+        Preconditions.checkArgument(subPlan.getParentPlans().size() == numParentSubPlans(), "Incorrect number of parent SubPlans");
+    }
+        
+    @Override
+    public String toString() {
+        return getShortName();
+    }
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/planning/operations/PProject.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/planning/operations/PProject.java
new file mode 100644
index 00000000..d0539b2c
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/planning/operations/PProject.java
@@ -0,0 +1,109 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2014, Bergmann Gabor, Istvan Rath and Daniel Varro
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v. 2.0 which is available at
+ * http://www.eclipse.org/legal/epl-v20.html.
+ * 
+ * SPDX-License-Identifier: EPL-2.0
+ *******************************************************************************/
+package tools.refinery.viatra.runtime.matchers.planning.operations;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.List;
+import java.util.Set;
+import java.util.stream.Collectors;
+import tools.refinery.viatra.runtime.matchers.planning.SubPlan;
+import tools.refinery.viatra.runtime.matchers.psystem.PConstraint;
+import tools.refinery.viatra.runtime.matchers.psystem.PVariable;
+import tools.refinery.viatra.runtime.matchers.util.Preconditions;
+/**
+ * Represents a projection of a single parent SubPlan onto a limited set of variables.
+ * <p> May optionally prescribe an ordering of variables (List, as opposed to Set).
+ * 
+ * @author Bergmann Gabor
+ *
+ */
+public class PProject extends POperation {
+    private Collection<PVariable> toVariables;
+    private boolean ordered;
+        
+    
+    public PProject(Set<PVariable> toVariables) {
+        super();
+        this.toVariables = toVariables;
+        this.ordered = false;
+    }
+    public PProject(List<PVariable> toVariables) {
+        super();
+        this.toVariables = toVariables;
+        this.ordered = true;
+    }
+    
+    public Collection<PVariable> getToVariables() {
+        return toVariables;
+    }
+    public boolean isOrdered() {                
+        return ordered;
+    }
+    
+    @Override
+    public Set<? extends PConstraint> getDeltaConstraints() {
+        return Collections.emptySet();
+    }
+    @Override
+    public int numParentSubPlans() {
+        return 1;
+    }
+    @Override
+    public void checkConsistency(SubPlan subPlan) {
+        super.checkConsistency(subPlan);
+        final SubPlan parentPlan = subPlan.getParentPlans().get(0);
+        
+        Preconditions.checkArgument(parentPlan.getVisibleVariables().containsAll(toVariables), 
+                () -> toVariables.stream()
+                        .filter(input -> !parentPlan.getVisibleVariables().contains(input)).map(PVariable::getName)
+                        .collect(Collectors.joining(",", "Variables missing from project: ", "")));
+    }
+    @Override
+    public String getShortName() {
+        return String.format("PROJECT%s_{%s}", ordered? "!" : "", 
+                toVariables.stream().map(PVariable::getName).collect(Collectors.joining(",")));
+    }
+    
+    @Override
+    public int hashCode() {
+        final int prime = 31;
+        int result = 1;
+        result = prime * result + (ordered ? 1231 : 1237);
+        result = prime * result
+                + ((toVariables == null) ? 0 : toVariables.hashCode());
+        return result;
+    }
+    @Override
+    public boolean equals(Object obj) {
+        if (this == obj)
+            return true;
+        if (obj == null)
+            return false;
+        if (!(obj instanceof PProject))
+            return false;
+        PProject other = (PProject) obj;
+        if (ordered != other.ordered)
+            return false;
+        if (toVariables == null) {
+            if (other.toVariables != null)
+                return false;
+        } else if (!toVariables.equals(other.toVariables))
+            return false;
+        return true;
+    }
+    
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/planning/operations/PStart.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/planning/operations/PStart.java
new file mode 100644
index 00000000..9e6ea10e
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/planning/operations/PStart.java
@@ -0,0 +1,90 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2014, Bergmann Gabor, Istvan Rath and Daniel Varro
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v. 2.0 which is available at
+ * http://www.eclipse.org/legal/epl-v20.html.
+ * 
+ * SPDX-License-Identifier: EPL-2.0
+ *******************************************************************************/
+package tools.refinery.viatra.runtime.matchers.planning.operations;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.HashSet;
+import java.util.Set;
+import java.util.stream.Collectors;
+import tools.refinery.viatra.runtime.matchers.psystem.PConstraint;
+import tools.refinery.viatra.runtime.matchers.psystem.PVariable;
+/**
+ * No constraints, and no parent SubPlan, just a (possibly empty) set of a priori known (input) variables. Satisfied by a single tuple.
+ * 
+ * <p> Can also be used without a priori variables, 
+ *   e.g. as a "virtual parent" in extreme cases, 
+ *   such as <code>pattern foo(Bar) = {Bar = eval (3*4)} </code> 
+ * 
+ * @author Bergmann Gabor
+ *
+ */
+public class PStart extends POperation {
+    
+    private Set<PVariable> aPrioriVariables;
+    
+    public PStart(Set<PVariable> aPrioriVariables) {
+        super();
+        this.aPrioriVariables = aPrioriVariables;
+    }
+    public PStart(PVariable... aPrioriVariables) {
+        this(new HashSet<PVariable>(Arrays.asList(aPrioriVariables)));
+    }
+    public Set<PVariable> getAPrioriVariables() {
+        return aPrioriVariables;
+    }
+    @Override
+    public String getShortName() {
+        return aPrioriVariables.stream().map(PVariable::getName).collect(Collectors.joining(",", "START_{", "}"));
+    }
+    @Override
+    public int numParentSubPlans() {
+        return 0;
+    }
+    @Override
+    public Set<? extends PConstraint> getDeltaConstraints() {
+        return Collections.emptySet();
+    }
+    @Override
+    public int hashCode() {
+        final int prime = 31;
+        int result = 1;
+        result = prime
+                * result
+                + ((aPrioriVariables == null) ? 0 : aPrioriVariables.hashCode());
+        return result;
+    }
+    @Override
+    public boolean equals(Object obj) {
+        if (this == obj)
+            return true;
+        if (obj == null)
+            return false;
+        if (!(obj instanceof PStart))
+            return false;
+        PStart other = (PStart) obj;
+        if (aPrioriVariables == null) {
+            if (other.aPrioriVariables != null)
+                return false;
+        } else if (!aPrioriVariables.equals(other.aPrioriVariables))
+            return false;
+        return true;
+    }
+    
+    
+}