76 files changed, 6215 insertions, 0 deletions

diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/BasePConstraint.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/BasePConstraint.java
new file mode 100644
index 00000000..eda4aa25
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/BasePConstraint.java
@@ -0,0 +1,108 @@
+/*******************************************************************************
+ * 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.psystem;
+
+import tools.refinery.viatra.runtime.matchers.context.IQueryMetaContext;
+
+import java.util.Collections;
+import java.util.HashSet;
+import java.util.Map;
+import java.util.Set;
+import java.util.concurrent.atomic.AtomicInteger;
+
+/**
+ * @author Gabor Bergmann
+ *
+ */
+public abstract class BasePConstraint implements PConstraint {
+
+
+    protected PBody pBody;
+    private final Set<PVariable> affectedVariables;
+
+
+    private final int sequentialID = nextID.getAndIncrement();
+
+        // Use a static atomic integer to avoid race conditions when creating new constraints.
+    private static AtomicInteger nextID = new AtomicInteger(0);
+
+    public BasePConstraint(PBody pBody, Set<PVariable> affectedVariables) {
+        super();
+        this.pBody = pBody;
+        this.affectedVariables = new HashSet<PVariable>(affectedVariables);
+
+        for (PVariable pVariable : affectedVariables) {
+            pVariable.refer(this);
+        }
+        pBody.registerConstraint(this);
+    }
+
+    @Override
+    public String toString() {
+        return "PC[" + getClass().getSimpleName() + ":" + toStringRest() + "]";
+    }
+
+    protected abstract String toStringRest();
+
+    @Override
+    public Set<PVariable> getAffectedVariables() {
+        return affectedVariables;
+    }
+
+    @Override
+    public Map<Set<PVariable>, Set<PVariable>> getFunctionalDependencies(IQueryMetaContext context) {
+        return Collections.emptyMap();
+    }
+
+    @Override
+    public void replaceVariable(PVariable obsolete, PVariable replacement) {
+        pBody.checkMutability();
+        if (affectedVariables.remove(obsolete)) {
+            affectedVariables.add(replacement);
+            obsolete.unrefer(this);
+            replacement.refer(this);
+            doReplaceVariable(obsolete, replacement);
+        }
+    }
+
+    protected abstract void doReplaceVariable(PVariable obsolete, PVariable replacement);
+
+    @Override
+    public void delete() {
+        pBody.checkMutability();
+        for (PVariable pVariable : affectedVariables) {
+            pVariable.unrefer(this);
+        }
+        pBody.unregisterConstraint(this);
+    }
+
+    @Override
+    public void checkSanity() {
+    }
+
+    /**
+     * For backwards compatibility. Equivalent to {@link #getBody()}
+     */
+    public PBody getPSystem() {
+        return pBody;
+    }
+    /**
+     * @since 2.1
+     */
+    @Override
+    public PBody getBody() {
+        return pBody;
+    }
+
+    @Override
+    public int getMonotonousID() {
+        return sequentialID;
+    }
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/DeferredPConstraint.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/DeferredPConstraint.java
new file mode 100644
index 00000000..d2bf088c
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/DeferredPConstraint.java
@@ -0,0 +1,31 @@
+/*******************************************************************************
+ * 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.psystem;
+
+import java.util.Set;
+
+import tools.refinery.viatra.runtime.matchers.context.IQueryMetaContext;
+import tools.refinery.viatra.runtime.matchers.planning.SubPlan;
+
+/**
+ * Any constraint that can only be checked on certain SubPlans (e.g. those plans that already contain some variables).
+ * 
+ * @author Gabor Bergmann
+ * 
+ */
+public abstract class DeferredPConstraint extends BasePConstraint {
+
+    public DeferredPConstraint(PBody pBody, Set<PVariable> affectedVariables) {
+        super(pBody, affectedVariables);
+    }
+
+    public abstract boolean isReadyAt(SubPlan plan, IQueryMetaContext context);
+
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/EnumerablePConstraint.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/EnumerablePConstraint.java
new file mode 100644
index 00000000..9129aa47
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/EnumerablePConstraint.java
@@ -0,0 +1,59 @@
+/*******************************************************************************
+ * 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.psystem;
+
+import java.util.Set;
+
+import tools.refinery.viatra.runtime.matchers.tuple.Tuple;
+
+/**
+ * A constraint for which all satisfying tuples of variable values can be enumerated at any point during run-time.
+ * 
+ * @author Gabor Bergmann
+ * 
+ */
+public abstract class EnumerablePConstraint extends BasePConstraint {
+    protected Tuple variablesTuple;
+
+    protected EnumerablePConstraint(PBody pBody, Tuple variablesTuple) {
+        super(pBody, variablesTuple.<PVariable> getDistinctElements());
+        this.variablesTuple = variablesTuple;
+    }
+
+    @Override
+    public void doReplaceVariable(PVariable obsolete, PVariable replacement) {
+        variablesTuple = variablesTuple.replaceAll(obsolete, replacement);
+    }
+
+    @Override
+    protected String toStringRest() {
+        String stringRestRest = toStringRestRest();
+        String tupleString = "@" + variablesTuple.toString();
+        return stringRestRest == null ? tupleString : ":" + stringRestRest + tupleString;
+    }
+
+    protected String toStringRestRest() {
+        return null;
+    }
+
+    public Tuple getVariablesTuple() {
+        return variablesTuple;
+    }
+
+    @Override
+    public Set<PVariable> getDeducedVariables() {
+        return getAffectedVariables();
+    }
+
+    public PVariable getVariableInTuple(int index) {
+        return (PVariable) this.variablesTuple.get(index);
+    }
+
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/IExpressionEvaluator.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/IExpressionEvaluator.java
new file mode 100644
index 00000000..686999f7
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/IExpressionEvaluator.java
@@ -0,0 +1,42 @@
+/*******************************************************************************
+ * 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.psystem;
+
+/**
+ * An expression evaluator is used to execute arbitrary Java code during pattern matching. In order to include the
+ * evaluation in the planning seemlessly it is expected from the evaluator implementors to report all used PVariables by
+ * name.
+ * 
+ * @author Zoltan Ujhelyi
+ * 
+ */
+public interface IExpressionEvaluator {
+
+    /**
+     * A textual description of the expression. Used only for debug purposes, but must not be null.
+     */
+    String getShortDescription();
+
+    /**
+     * All input parameter names should be reported correctly.
+     */
+    Iterable<String> getInputParameterNames();
+
+    /**
+     * The expression evaluator code
+     * 
+     * @param provider
+     *            the value provider is an engine-specific way of reading internal variable tuples to evaluate the
+     *            expression with
+     * @return the result of the expression: in case of predicate evaluation the return value must be true or false;
+     *         otherwise the result can be an arbitrary object. No null values should be returned.
+     * @throws Exception
+     */
+    Object evaluateExpression(IValueProvider provider) throws Exception;
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/IMultiQueryReference.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/IMultiQueryReference.java
new file mode 100644
index 00000000..8f647c64
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/IMultiQueryReference.java
@@ -0,0 +1,26 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2022, Tamas Szabo, GitHub
+ * 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.psystem;
+
+import java.util.Collection;
+
+import tools.refinery.viatra.runtime.matchers.psystem.queries.PQuery;
+
+/**
+ * A {@link PConstraint} that implements this interface refers to a list of PQueries.
+ * 
+ * @author Tamas Szabo
+ * @since 2.8
+ *
+ */
+public interface IMultiQueryReference {
+
+    Collection<PQuery> getReferredQueries();
+
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/IQueryReference.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/IQueryReference.java
new file mode 100644
index 00000000..9ee05b39
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/IQueryReference.java
@@ -0,0 +1,33 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2014, 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.psystem;
+
+import java.util.Collections;
+import java.util.List;
+
+import tools.refinery.viatra.runtime.matchers.psystem.queries.PQuery;
+
+/**
+ * A {@link PConstraint} that implements this interface refers to a {@link PQuery}.
+ * 
+ * @author Zoltan Ujhelyi
+ *
+ */
+public interface IQueryReference extends IMultiQueryReference {
+
+    PQuery getReferredQuery();
+
+    /**
+     * @since 2.8
+     */
+    @Override
+    default List<PQuery> getReferredQueries() {
+        return Collections.singletonList(getReferredQuery());
+    }
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/IRelationEvaluator.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/IRelationEvaluator.java
new file mode 100644
index 00000000..e4c396d8
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/IRelationEvaluator.java
@@ -0,0 +1,47 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2022, Tamas Szabo, GitHub
+ * 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.psystem;
+
+import java.util.List;
+import java.util.Set;
+
+import tools.refinery.viatra.runtime.matchers.tuple.Tuple;
+
+/**
+ * Implementations of this interface take an arbitrary number of input relations with their contents and compute the
+ * tuples of a single output relation.
+ * 
+ * @author Tamas Szabo
+ * @since 2.8
+ *
+ */
+public interface IRelationEvaluator {
+
+    /**
+     * A textual description of the evaluator. Used only for debug purposes, but must not be null.
+     */
+    String getShortDescription();
+
+    /**
+     * The relation evaluator code. For performance reasons, it is expected that the returned set is a mutable
+     * collection, and the caller must be allowed to actually perform mutations!
+     */
+    Set<Tuple> evaluateRelation(List<Set<Tuple>> inputs) throws Exception;
+
+    /**
+     * For each input relation that this evaluator requires, this method returns the expected arities of the relations in order.
+     */
+    List<Integer> getInputArities();
+
+    /**
+     * Returns the arity of the output relation that this evaluator computes.
+     */
+    int getOutputArity();
+
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/ITypeConstraint.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/ITypeConstraint.java
new file mode 100644
index 00000000..b72035a8
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/ITypeConstraint.java
@@ -0,0 +1,65 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2015, 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.psystem;
+
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Map;
+import java.util.Map.Entry;
+
+import tools.refinery.viatra.runtime.matchers.context.IInputKey;
+import tools.refinery.viatra.runtime.matchers.context.IQueryMetaContext;
+import tools.refinery.viatra.runtime.matchers.tuple.Tuple;
+
+import java.util.Set;
+
+/**
+ * Common superinterface of enumerable and deferred type constraints.
+ * @author Bergmann Gabor
+ *
+ */
+public interface ITypeConstraint extends ITypeInfoProviderConstraint {
+
+    public abstract TypeJudgement getEquivalentJudgement();
+    
+    /**
+     * Static internal utility class for implementations of {@link ITypeConstraint}s.
+     * @author Bergmann Gabor
+     */
+    public static class TypeConstraintUtil {
+        
+        private TypeConstraintUtil() {
+            // Hiding constructor for utility class
+        }
+        
+        public static Map<Set<PVariable>, Set<PVariable>> getFunctionalDependencies(IQueryMetaContext context, IInputKey inputKey, Tuple variablesTuple) {
+            final Map<Set<PVariable>, Set<PVariable>> result = new HashMap<Set<PVariable>, Set<PVariable>>();
+            
+            Set<Entry<Set<Integer>, Set<Integer>>> dependencies = context.getFunctionalDependencies(inputKey).entrySet();
+            for (Entry<Set<Integer>, Set<Integer>> dependency : dependencies) {
+                result.put(
+                        transcribeVariables(dependency.getKey(), variablesTuple), 
+                        transcribeVariables(dependency.getValue(), variablesTuple)
+                );
+            }
+
+            return result;
+        }
+
+        private static Set<PVariable> transcribeVariables(Set<Integer> indices, Tuple variablesTuple) {
+            Set<PVariable> result = new HashSet<PVariable>();
+            for (Integer index : indices) {
+                result.add((PVariable) variablesTuple.get(index));
+            }
+            return result;
+        }
+
+    }
+
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/ITypeInfoProviderConstraint.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/ITypeInfoProviderConstraint.java
new file mode 100644
index 00000000..ff127d38
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/ITypeInfoProviderConstraint.java
@@ -0,0 +1,28 @@
+/*******************************************************************************
+ * 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.psystem;
+
+import java.util.Set;
+
+import tools.refinery.viatra.runtime.matchers.context.IQueryMetaContext;
+
+/**
+ * @author Gabor Bergmann
+ * 
+ */
+public interface ITypeInfoProviderConstraint extends PConstraint {
+
+    /**
+     * Returns type information implied by this constraint.
+     * 
+     */
+    public Set<TypeJudgement> getImpliedJudgements(IQueryMetaContext context);
+
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/IValueProvider.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/IValueProvider.java
new file mode 100644
index 00000000..d959adc4
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/IValueProvider.java
@@ -0,0 +1,27 @@
+/*******************************************************************************
+ * 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.psystem;
+
+/**
+ * Helper interface to get values from a tuple of variables. All pattern matching engines are expected to implement this
+ * to handle their internal structures.
+ * 
+ * @author Zoltan Ujhelyi
+ * 
+ */
+public interface IValueProvider {
+
+    /**
+     * Returns the value of the selected variable
+     * @param variableName
+     * @return the value of the variable; never null
+     * @throws IllegalArgumentException if the variable is not defined
+     */
+    Object getValue(String variableName);
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/InitializablePQuery.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/InitializablePQuery.java
new file mode 100644
index 00000000..a82d12ec
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/InitializablePQuery.java
@@ -0,0 +1,56 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2014, 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.psystem;
+
+import java.util.Set;
+
+import tools.refinery.viatra.runtime.matchers.ViatraQueryRuntimeException;
+import tools.refinery.viatra.runtime.matchers.psystem.annotations.PAnnotation;
+import tools.refinery.viatra.runtime.matchers.psystem.queries.PProblem;
+import tools.refinery.viatra.runtime.matchers.psystem.queries.PQuery;
+
+/**
+ * Adds extra methods to the PQuery interface to initialize its contents.
+ *
+ * @author Zoltan Ujhelyi
+ *
+ */
+public interface InitializablePQuery extends PQuery {
+
+    /**
+     * Sets the query status. Only applicable if the pattern is still {@link PQueryStatus#UNINITIALIZED uninitialized}.
+     *
+     * @param status the new status
+     */
+    void setStatus(PQueryStatus status);
+    
+    /**
+     * Adds a detected error. Only applicable if the pattern is still {@link PQueryStatus#UNINITIALIZED uninitialized}.
+     *
+     * @param problem the new problem
+     */
+    void addError(PProblem problem);
+
+    /**
+     * Sets up the bodies of the pattern. Only applicable if the pattern is still {@link PQueryStatus#UNINITIALIZED
+     * uninitialized}.
+     *
+     * @param bodies
+     * @throws ViatraQueryRuntimeException
+     */
+    void initializeBodies(Set<PBody> bodies);
+
+    /**
+     * Adds an annotation to the specification. Only applicable if the pattern is still
+     * {@link PQueryStatus#UNINITIALIZED uninitialized}.
+     *
+     * @param annotation
+     */
+    void addAnnotation(PAnnotation annotation);
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/KeyedEnumerablePConstraint.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/KeyedEnumerablePConstraint.java
new file mode 100644
index 00000000..91eea817
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/KeyedEnumerablePConstraint.java
@@ -0,0 +1,39 @@
+/*******************************************************************************
+ * 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.psystem;
+
+import tools.refinery.viatra.runtime.matchers.tuple.Tuple;
+
+/**
+ * @author Gabor Bergmann
+ * 
+ */
+public abstract class KeyedEnumerablePConstraint<KeyType> extends EnumerablePConstraint {
+
+    protected KeyType supplierKey;
+
+    public KeyedEnumerablePConstraint(PBody pBody, Tuple variablesTuple,
+            KeyType supplierKey) {
+        super(pBody, variablesTuple);
+        this.supplierKey = supplierKey;
+    }
+
+    @Override
+    protected String toStringRestRest() {
+        return supplierKey == null ? "$any(null)" : keyToString();
+    }
+
+    protected abstract String keyToString();
+
+    public KeyType getSupplierKey() {
+        return supplierKey;
+    }
+
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/PBody.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/PBody.java
new file mode 100644
index 00000000..c38dc23a
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/PBody.java
@@ -0,0 +1,289 @@
+/*******************************************************************************
+ * 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.psystem;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.LinkedHashSet;
+import java.util.List;
+import java.util.Map;
+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.psystem.basicdeferred.ExportedParameter;
+import tools.refinery.viatra.runtime.matchers.psystem.basicenumerables.ConstantValue;
+import tools.refinery.viatra.runtime.matchers.psystem.queries.PDisjunction;
+import tools.refinery.viatra.runtime.matchers.psystem.queries.PQuery;
+import tools.refinery.viatra.runtime.matchers.psystem.queries.PQuery.PQueryStatus;
+import tools.refinery.viatra.runtime.matchers.util.Preconditions;
+
+/**
+ * A set of constraints representing a pattern body
+ * 
+ * @author Gabor Bergmann
+ * 
+ */
+public class PBody implements PTraceable {
+    
+    public static final String VIRTUAL_VARIABLE_PREFIX = ".virtual";
+    private static final String VIRTUAL_VARIABLE_PATTERN = VIRTUAL_VARIABLE_PREFIX + "{%d}";
+    
+    private PQuery query;
+
+    /**
+     * If null, then parent query status is reused
+     */
+    private PQueryStatus status = PQueryStatus.UNINITIALIZED;
+
+    private Set<PVariable> allVariables;
+    private Set<PVariable> uniqueVariables;
+    private List<ExportedParameter> symbolicParameters;
+    private Map<Object, PVariable> variablesByName;
+    private Set<PConstraint> constraints;
+    private int nextVirtualNodeID;
+    private PDisjunction containerDisjunction;
+
+    public PBody(PQuery query) {
+        super();
+        this.query = query;
+        allVariables = new LinkedHashSet<>();
+        uniqueVariables = new LinkedHashSet<>();
+        variablesByName = new HashMap<>();
+        constraints = new LinkedHashSet<>();
+    }
+
+    /**
+     * @return whether the submission of the new variable was successful
+     */
+    private boolean addVariable(PVariable var) {
+        checkMutability();
+        Object name = var.getName();
+        if (!variablesByName.containsKey(name)) {
+            allVariables.add(var);
+            if (var.isUnique())
+                uniqueVariables.add(var);
+            variablesByName.put(name, var);
+            return true;
+        } else {
+            return false;
+        }
+    }
+
+    /**
+     * Use this method to add a newly created constraint to the pSystem.
+     * 
+     * @return whether the submission of the new constraint was successful
+     */
+    boolean registerConstraint(PConstraint constraint) {
+        checkMutability();
+        return constraints.add(constraint);
+    }
+
+    /**
+     * Use this method to remove an obsolete constraint from the pSystem.
+     * 
+     * @return whether the removal of the constraint was successful
+     */
+    boolean unregisterConstraint(PConstraint constraint) {
+        checkMutability();
+        return constraints.remove(constraint);
+    }
+
+    @SuppressWarnings("unchecked")
+    public <ConstraintType> Set<ConstraintType> getConstraintsOfType(Class<ConstraintType> constraintClass) {
+        Set<ConstraintType> result = new HashSet<ConstraintType>();
+        for (PConstraint pConstraint : constraints) {
+            if (constraintClass.isInstance(pConstraint))
+                result.add((ConstraintType) pConstraint);
+        }
+        return result;
+    }
+
+    public PVariable newVirtualVariable() {
+        checkMutability();
+        String name;
+        do {
+            
+            name = String.format(VIRTUAL_VARIABLE_PATTERN, nextVirtualNodeID++);
+        } while (variablesByName.containsKey(name));
+        PVariable var = new PVariable(this, name, true);
+        addVariable(var);
+        return var;
+    }
+    
+    public PVariable newVirtualVariable(String name) {
+        checkMutability();
+        Preconditions.checkArgument(!variablesByName.containsKey(name), "ID %s already used for a virtual variable", name);
+        PVariable var = new PVariable(this, name, true);
+        addVariable(var);
+        return var;
+    }
+
+    public PVariable newConstantVariable(Object value) {
+        checkMutability();
+        PVariable virtual = newVirtualVariable();
+        new ConstantValue(this, virtual, value);
+        return virtual;
+    }
+
+    public Set<PVariable> getAllVariables() {
+        return allVariables;
+    }
+
+    public Set<PVariable> getUniqueVariables() {
+        return uniqueVariables;
+    }
+
+    private PVariable getVariableByName(Object name) {
+        return variablesByName.get(name).getUnifiedIntoRoot();
+    }
+
+    /**
+     * Find a PVariable by name
+     * 
+     * @param name
+     * @return the found variable
+     * @throws IllegalArgumentException
+     *             if no PVariable is found with the selected name
+     */
+    public PVariable getVariableByNameChecked(Object name) {
+        if (!variablesByName.containsKey(name))
+            throw new IllegalArgumentException(String.format("Cannot find PVariable %s", name));
+        return getVariableByName(name);
+    }
+
+    /**
+     * Finds and returns a PVariable by name. If no PVariable exists with the name in the body, a new one is created. If
+     * the name of the variable starts with {@value #VIRTUAL_VARIABLE_PREFIX}, the created variable will be considered
+     * virtual.
+     * 
+     * @param name
+     * @return a PVariable with the selected name; never null
+     */
+    public PVariable getOrCreateVariableByName(String name) {
+        checkMutability();
+        if (!variablesByName.containsKey(name)) {
+            addVariable(new PVariable(this, name, name.startsWith(VIRTUAL_VARIABLE_PREFIX)));
+        }
+        return getVariableByName(name);
+    }
+
+    public Set<PConstraint> getConstraints() {
+        return constraints;
+    }
+
+    public PQuery getPattern() {
+        return query;
+    }
+
+    void noLongerUnique(PVariable pVariable) {
+        assert (!pVariable.isUnique());
+        uniqueVariables.remove(pVariable);
+    }
+
+    /**
+     * Returns the symbolic parameters of the body. </p>
+     * 
+     * <p>
+     * <strong>Warning</strong>: if two PVariables are unified, the returned list changes. If you want to have a stable
+     * version, consider using {@link #getSymbolicParameters()}.
+     * 
+     * @return a non-null, but possibly empty list
+     */
+    public List<PVariable> getSymbolicParameterVariables() {
+        return getSymbolicParameters().stream().map(ExportedParameter::getParameterVariable)
+                .collect(Collectors.toList());
+    }
+
+    /**
+     * Returns the exported parameter constraints of the body.
+     * 
+     * @return a non-null, but possibly empty list
+     */
+    public List<ExportedParameter> getSymbolicParameters() {
+        if (symbolicParameters == null) 
+            symbolicParameters = new ArrayList<>();
+        return symbolicParameters;
+    }
+
+    /**
+     * Sets the exported parameter constraints of the body, if this instance is mutable.
+     * @param symbolicParameters the new value
+     */
+    public void setSymbolicParameters(List<ExportedParameter> symbolicParameters) {
+        checkMutability();
+        this.symbolicParameters = new ArrayList<>(symbolicParameters);
+    }
+
+    /**
+     * Sets a specific status for the body. If set, the parent PQuery status will not be checked; if set to null, its corresponding PQuery
+     * status is checked for mutability.
+     * 
+     * @param status
+     *            the status to set
+     */
+    public void setStatus(PQueryStatus status) {
+        this.status = status;
+    }
+
+    public boolean isMutable() {
+        if (status == null) {
+            return query.isMutable();
+        } else {
+            return status.equals(PQueryStatus.UNINITIALIZED);
+        }
+    }
+    
+    void checkMutability() {
+        if (status == null) {
+            query.checkMutability();
+        } else {
+            Preconditions.checkState(status.equals(PQueryStatus.UNINITIALIZED), "Initialized queries are not mutable");
+        }
+    }
+
+    /**
+     * Returns the disjunction the body is contained with. This disjunction may either be the
+     * {@link PQuery#getDisjunctBodies() canonical disjunction of the corresponding query} or something equivalent.
+     * 
+     * @return the container disjunction of the body. Can be null if body is not in a disjunction yet.
+     */
+    public PDisjunction getContainerDisjunction() {
+        return containerDisjunction;
+    }
+
+    /**
+     * @param containerDisjunction the containerDisjunction to set
+     */
+    public void setContainerDisjunction(PDisjunction containerDisjunction) {
+        Preconditions.checkArgument(query.equals(containerDisjunction.getQuery()), "Disjunction of pattern %s incompatible with body %s", containerDisjunction.getQuery().getFullyQualifiedName(), query.getFullyQualifiedName());
+        Preconditions.checkState(this.containerDisjunction == null, "Disjunction is already set.");
+        this.containerDisjunction = containerDisjunction;
+    }
+
+    /**
+     * All unary input keys directly prescribed by constraints, grouped by variable.
+     * <p> to supertype inference or subsumption applied at this point.
+     */
+    public Map<PVariable, Set<TypeJudgement>> getAllUnaryTypeRestrictions(IQueryMetaContext context) {
+        Map<PVariable, Set<TypeJudgement>> currentRestrictions = allUnaryTypeRestrictions.get(context);
+        if (currentRestrictions == null) {
+            currentRestrictions = TypeHelper.inferUnaryTypes(getConstraints(), context);
+            allUnaryTypeRestrictions.put(context, currentRestrictions);
+        }
+        return currentRestrictions;
+    }
+    private WeakHashMap<IQueryMetaContext, Map<PVariable, Set<TypeJudgement>>> allUnaryTypeRestrictions = new WeakHashMap<IQueryMetaContext, Map<PVariable,Set<TypeJudgement>>>();   
+    
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/PConstraint.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/PConstraint.java
new file mode 100644
index 00000000..ae2c4632
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/PConstraint.java
@@ -0,0 +1,70 @@
+/*******************************************************************************
+ * 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.psystem;
+
+import java.util.Comparator;
+import java.util.Map;
+import java.util.Set;
+
+import tools.refinery.viatra.runtime.matchers.context.IQueryMetaContext;
+import tools.refinery.viatra.runtime.matchers.psystem.analysis.QueryAnalyzer;
+
+/**
+ * @author Gabor Bergmann
+ * 
+ */
+public interface PConstraint extends PTraceable {
+
+    /**
+     * @since 2.1
+     * @return the query body this constraint belongs to
+     */
+    public PBody getBody();
+
+    /**
+     * All variables affected by this constraint.
+     */
+    public Set<PVariable> getAffectedVariables();
+
+    /**
+     * The set of variables whose potential values can be enumerated (once all non-deduced variables have known values).  
+     */
+    public Set<PVariable> getDeducedVariables();
+    
+    /**
+     * A (preferably minimal) cover of known functional dependencies between variables.
+     * @noreference Use {@link QueryAnalyzer} instead to properly handle dependencies of pattern calls. 
+     * @return non-trivial functional dependencies in the form of {variables} --> {variables}, where dependencies with the same lhs are unified.   
+     */
+    public Map<Set<PVariable>,Set<PVariable>> getFunctionalDependencies(IQueryMetaContext context);  
+
+    public void replaceVariable(PVariable obsolete, PVariable replacement);
+
+    public void delete();
+
+    public void checkSanity();
+
+    /**
+     * Returns an integer ID that is guaranteed to increase strictly monotonously for constraints within a pBody.
+     */
+    public abstract int getMonotonousID();
+    
+
+    /**
+     * A comparator that orders constraints by their {@link #getMonotonousID() monotonous identifiers}. Should only used
+     * for tiebreaking in other comparators.
+     * 
+     * @since 2.0
+     */
+    public static final Comparator<PConstraint> COMPARE_BY_MONOTONOUS_ID = (arg0, arg1) -> arg0.getMonotonousID() - arg1.getMonotonousID();
+
+    
+    
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/PTraceable.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/PTraceable.java
new file mode 100644
index 00000000..f0241a9c
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/PTraceable.java
@@ -0,0 +1,16 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2017, Dénes Harmath, IncQueryLabs 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.psystem;
+
+/**
+ * Marker interface for PSystem elements that can be traced.
+ * @since 1.6
+ */
+public interface PTraceable {
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/PVariable.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/PVariable.java
new file mode 100644
index 00000000..b6ea4861
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/PVariable.java
@@ -0,0 +1,203 @@
+/*******************************************************************************
+ * 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.psystem;
+
+import java.util.HashSet;
+import java.util.Set;
+
+/**
+ * @author Gabor Bergmann
+ *
+ */
+public class PVariable {
+    private PBody pBody;
+    /**
+     * The name of the pattern variable. This is the unique key of the pattern node.
+     */
+    private String name;
+    /**
+     * virtual pVariables are nodes that do not correspond to actual pattern variables; they represent constants or Term
+     * substitutes
+     */
+    private boolean virtual;
+
+    /**
+     * Set of constraints that mention this variable
+     */
+    private Set<PConstraint> referringConstraints;
+
+    /**
+     * Determines whether there are any constraints that can deduce this variable
+     */
+    private Boolean deducable;
+
+    /**
+     * Another PVariable this variable has been unified into. Please use the other variable instead of this. Null iff
+     * this is still a first-class variable.
+     */
+    private PVariable unifiedInto;
+
+    PVariable(PBody pBody, String name) {
+        this(pBody, name, false);
+    }
+
+    PVariable(PBody pBody, String name, boolean virtual) {
+        super();
+        this.pBody = pBody;
+        this.name = name;
+        this.virtual = virtual;
+        // this.exportedParameter = false;
+        this.referringConstraints = new HashSet<PConstraint>();
+        this.unifiedInto = null;
+        this.deducable = false;
+    }
+
+    /**
+     * Replaces this variable with a given other, resulting in their unification. This variable will no longer be
+     * unique.
+     *
+     * @param replacement
+     */
+    public void unifyInto(PVariable replacement) {
+        pBody.checkMutability();
+        replacementCheck();
+        replacement = replacement.getUnifiedIntoRoot();
+
+        if (this.equals(replacement))
+            return;
+
+        if (!this.isVirtual() && replacement.isVirtual()) {
+            replacement.unifyInto(this);
+        } else {
+            // replacement.referringConstraints.addAll(this.referringConstraints);
+            // replacement.exportedParameter |= this.exportedParameter;
+            replacement.virtual &= this.virtual;
+            if (replacement.deducable != null && this.deducable != null)
+                replacement.deducable |= this.deducable;
+            else
+                replacement.deducable = null;
+            Set<PConstraint> snapshotConstraints = // avoid ConcurrentModificationX
+                    new HashSet<PConstraint>(this.referringConstraints);
+            for (PConstraint constraint : snapshotConstraints) {
+                constraint.replaceVariable(this, replacement);
+            }
+            // replacementCheck() will fail from this point
+            this.unifiedInto = replacement;
+            pBody.noLongerUnique(this);
+        }
+    }
+
+    /**
+     * Determines whether there are any constraints that can deduce this variable
+     */
+    public boolean isDeducable() {
+        replacementCheck();
+        if (deducable == null) {
+            deducable = false;
+            for (PConstraint pConstraint : getReferringConstraints()) {
+                if (pConstraint.getDeducedVariables().contains(this)) {
+                    deducable = true;
+                    break;
+                }
+            }
+        }
+        return deducable;
+    }
+
+    /**
+     * Register that this variable is referred by the given constraint.
+     *
+     * @param constraint
+     */
+    public void refer(PConstraint constraint) {
+        pBody.checkMutability();
+        replacementCheck();
+        deducable = null;
+        referringConstraints.add(constraint);
+    }
+
+    /**
+     * Register that this variable is no longer referred by the given constraint.
+     *
+     * @param constraint
+     */
+    public void unrefer(PConstraint constraint) {
+        pBody.checkMutability();
+        replacementCheck();
+        deducable = null;
+        referringConstraints.remove(constraint);
+    }
+
+    /**
+     * @return the name of the pattern variable. This is the unique key of the pattern node.
+     */
+    public String getName() {
+        replacementCheck();
+        return name;
+    }
+
+    /**
+     * @return the virtual
+     */
+    public boolean isVirtual() {
+        replacementCheck();
+        return virtual;
+    }
+
+    /**
+     * @return the referringConstraints
+     */
+    public Set<PConstraint> getReferringConstraints() {
+        replacementCheck();
+        return referringConstraints;
+    }
+
+    @SuppressWarnings("unchecked")
+    public <ConstraintType> Set<ConstraintType> getReferringConstraintsOfType(Class<ConstraintType> constraintClass) {
+        replacementCheck();
+        Set<ConstraintType> result = new HashSet<ConstraintType>();
+        for (PConstraint pConstraint : referringConstraints) {
+            if (constraintClass.isInstance(pConstraint))
+                result.add((ConstraintType) pConstraint);
+        }
+        return result;
+    }
+
+    @Override
+    public String toString() {
+        // replacementCheck();
+        return name;// + ":PatternNode";
+    }
+
+    public PVariable getDirectUnifiedInto() {
+        return unifiedInto;
+    }
+
+    public PVariable getUnifiedIntoRoot() {
+        PVariable nextUnified = unifiedInto;
+        PVariable oldUnifiedInto = this;
+        while (nextUnified != null) {
+            oldUnifiedInto = nextUnified;
+            nextUnified = oldUnifiedInto.getDirectUnifiedInto();
+        }
+        return oldUnifiedInto; // unifiedInto;
+    }
+
+    public boolean isUnique() {
+        return unifiedInto == null;
+    }
+
+    private void replacementCheck() {
+        if (unifiedInto != null)
+            throw new IllegalStateException("Illegal usage of variable " + name + " which has been replaced with "
+                    + unifiedInto.name);
+    }
+
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/TypeJudgement.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/TypeJudgement.java
new file mode 100644
index 00000000..4447b225
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/TypeJudgement.java
@@ -0,0 +1,153 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2015, 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.psystem;
+
+import java.util.Collection;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Map;
+import java.util.stream.Collectors;
+import java.util.Set;
+
+import tools.refinery.viatra.runtime.matchers.context.IInputKey;
+import tools.refinery.viatra.runtime.matchers.context.IQueryMetaContext;
+import tools.refinery.viatra.runtime.matchers.context.InputKeyImplication;
+import tools.refinery.viatra.runtime.matchers.psystem.basicdeferred.TypeFilterConstraint;
+import tools.refinery.viatra.runtime.matchers.psystem.basicenumerables.TypeConstraint;
+import tools.refinery.viatra.runtime.matchers.tuple.Tuple;
+import tools.refinery.viatra.runtime.matchers.tuple.Tuples;
+
+/**
+ * A judgement that means that the given tuple of variables will represent a tuple of values that is a member of the extensional relation identified by the given input key.
+ * @author Bergmann Gabor
+ *
+ */
+public class TypeJudgement {
+    
+    private IInputKey inputKey;
+    private Tuple variablesTuple;
+    /**
+     * @param inputKey
+     * @param variablesTuple
+     */
+    public TypeJudgement(IInputKey inputKey, Tuple variablesTuple) {
+        super();
+        this.inputKey = inputKey;
+        this.variablesTuple = variablesTuple;
+    }
+    public IInputKey getInputKey() {
+        return inputKey;
+    }
+    public Tuple getVariablesTuple() {
+        return variablesTuple;
+    }
+    @Override
+    public int hashCode() {
+        final int prime = 31;
+        int result = 1;
+        result = prime * result
+                + ((inputKey == null) ? 0 : inputKey.hashCode());
+        result = prime * result
+                + ((variablesTuple == null) ? 0 : variablesTuple.hashCode());
+        return result;
+    }
+    @Override
+    public boolean equals(Object obj) {
+        if (this == obj)
+            return true;
+        if (obj == null)
+            return false;
+        if (!(obj instanceof TypeJudgement))
+            return false;
+        TypeJudgement other = (TypeJudgement) obj;
+        if (inputKey == null) {
+            if (other.inputKey != null)
+                return false;
+        } else if (!inputKey.equals(other.inputKey))
+            return false;
+        if (variablesTuple == null) {
+            if (other.variablesTuple != null)
+                return false;
+        } else if (!variablesTuple.equals(other.variablesTuple))
+            return false;
+        return true;
+    }
+    
+    public Set<TypeJudgement> getDirectlyImpliedJudgements(IQueryMetaContext context) {
+        Set<TypeJudgement> results = new HashSet<TypeJudgement>();
+        results.add(this);
+        
+        Collection<InputKeyImplication> implications = context.getImplications(this.inputKey);
+        for (InputKeyImplication inputKeyImplication : implications) {
+            results.add(
+                transcribeImplication(inputKeyImplication)
+            );
+        }
+        
+        return results;
+    }
+    
+    /**
+     * @since 1.6
+     */
+    public Set<TypeJudgement> getWeakenedAlternativeJudgements(IQueryMetaContext context) {
+        Set<TypeJudgement> results = new HashSet<TypeJudgement>();
+        
+        Collection<InputKeyImplication> implications = context.getWeakenedAlternatives(this.inputKey);
+        for (InputKeyImplication inputKeyImplication : implications) {
+            results.add(
+                transcribeImplication(inputKeyImplication)
+            );
+        }
+        
+        return results;
+    }
+    
+    /**
+     * @since 2.0
+     */
+    public Map<TypeJudgement, Set<TypeJudgement>> getConditionalImpliedJudgements(IQueryMetaContext context) {
+        return context.getConditionalImplications(this.inputKey).entrySet().stream().collect(Collectors.toMap(
+                entry -> transcribeImplication(entry.getKey()),
+                entry -> entry.getValue().stream().map(this::transcribeImplication).collect(Collectors.toSet())));
+    }
+    
+    
+    
+    private TypeJudgement transcribeImplication(InputKeyImplication inputKeyImplication) {
+        return new TypeJudgement(
+                inputKeyImplication.getImpliedKey(), 
+                transcribeVariablesToTuple(inputKeyImplication.getImpliedIndices())
+        );
+    }
+    private Tuple transcribeVariablesToTuple(List<Integer> indices) {
+        Object[] elements = new Object[indices.size()];
+        for (int i = 0; i < indices.size(); ++i)
+            elements[i] = variablesTuple.get(indices.get(i));
+        return Tuples.flatTupleOf(elements);
+    }
+
+    @Override
+    public String toString() {
+        return "TypeJudgement:" + inputKey.getPrettyPrintableName() + "@" + variablesTuple.toString();
+    }
+    
+    /**
+     * Creates this judgement as a direct type constraint in the given PBody under construction.
+     * <p> pre: the variables tuple must be formed of variables of that PBody.
+     * @since 1.6
+     */
+    public PConstraint createConstraintFor(PBody pBody) {
+        if (inputKey.isEnumerable()) {
+            return new TypeConstraint(pBody, variablesTuple, inputKey);
+        } else {
+            return new TypeFilterConstraint(pBody, variablesTuple, inputKey);
+        }
+    }
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/VariableDeferredPConstraint.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/VariableDeferredPConstraint.java
new file mode 100644
index 00000000..8ea6bb93
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/VariableDeferredPConstraint.java
@@ -0,0 +1,40 @@
+/*******************************************************************************
+ * 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.psystem;
+
+import java.util.Set;
+
+import tools.refinery.viatra.runtime.matchers.context.IQueryMetaContext;
+import tools.refinery.viatra.runtime.matchers.planning.SubPlan;
+
+/**
+ * A kind of deferred constraint that can only be checked when a set of deferring variables are all present in a plan.
+ * 
+ * @author Gabor Bergmann
+ * 
+ */
+public abstract class VariableDeferredPConstraint extends DeferredPConstraint {
+
+    public VariableDeferredPConstraint(PBody pBody,
+            Set<PVariable> affectedVariables) {
+        super(pBody, affectedVariables);
+    }
+
+    public abstract Set<PVariable> getDeferringVariables();
+
+    /**
+     * Refine further if needed
+     */
+    @Override
+    public boolean isReadyAt(SubPlan plan, IQueryMetaContext context) {
+        return plan.getVisibleVariables().containsAll(getDeferringVariables());
+    }
+
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/aggregations/AbstractMemorylessAggregationOperator.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/aggregations/AbstractMemorylessAggregationOperator.java
new file mode 100644
index 00000000..63a37bbe
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/aggregations/AbstractMemorylessAggregationOperator.java
@@ -0,0 +1,31 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2016, Gabor Bergmann, IncQueryLabs 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.psystem.aggregations;
+
+/**
+ * 
+ * An aggregation operator that does not store interim results beyond the final aggregated value.
+ * @author Gabor Bergmann
+ * @since 1.4
+ */
+public abstract class AbstractMemorylessAggregationOperator<Domain, AggregateResult> 
+    implements IMultisetAggregationOperator<Domain, AggregateResult, AggregateResult> 
+{
+
+    @Override
+    public AggregateResult getAggregate(AggregateResult result) {
+        return result;
+    }
+
+    @Override
+    public AggregateResult clone(AggregateResult original) {
+        return original;
+    }
+    
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/aggregations/AggregatorType.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/aggregations/AggregatorType.java
new file mode 100644
index 00000000..4cc40a2b
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/aggregations/AggregatorType.java
@@ -0,0 +1,49 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2016, Zoltan Ujhelyi, 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.psystem.aggregations;
+
+import java.lang.annotation.ElementType;
+import java.lang.annotation.Inherited;
+import java.lang.annotation.Retention;
+import java.lang.annotation.RetentionPolicy;
+import java.lang.annotation.Target;
+
+import tools.refinery.viatra.runtime.matchers.aggregators.count;
+
+/**
+ * The aggregator type annotation describes the type constraints for the selected aggregator. In version 1.4, two kinds of
+ * aggregators are supported:
+ * 
+ * <ol>
+ * <li>An aggregator that does not consider any parameter value from the call ({@link count}), just calculates the
+ * number of matches. This is represented by a single {@link Void} and a single corresponding return type.</li>
+ * <li>An aggregator that considers a single parameter from the call, and executes some aggregate operations over it.
+ * Such an aggregate operation can be defined over multiple types, where each possible parameter type has a corresponding return type declared.</li>
+ * </ol>
+ * 
+ * <strong>Important!</strong> The parameterTypes and returnTypes arrays must have
+ * <ul>
+ * <li>The same number of classes defined each.</li>
+ * <li>Items are corresponded by index.</li>
+ * <li>Items should represent data types</li>
+ * </ul>
+ * 
+ * @author Zoltan Ujhelyi
+ * @since 1.4
+ *
+ */
+@Target({ ElementType.TYPE })
+@Retention(RetentionPolicy.RUNTIME)
+@Inherited
+public @interface AggregatorType {
+
+    Class<?>[] parameterTypes();
+
+    Class<?>[] returnTypes();
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/aggregations/BoundAggregator.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/aggregations/BoundAggregator.java
new file mode 100644
index 00000000..e6972544
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/aggregations/BoundAggregator.java
@@ -0,0 +1,61 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2016, Gabor Bergmann, IncQueryLabs 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.psystem.aggregations;
+
+import tools.refinery.viatra.runtime.matchers.context.IInputKey;
+import tools.refinery.viatra.runtime.matchers.context.common.JavaTransitiveInstancesKey;
+
+/**
+ * Augments an aggregator operator with type bindings for the type of values being aggregated and the aggregate result.
+ * <p> In case of <em>count</em>, the operator should be null.
+ * @author Gabor Bergmann
+ * @since 1.4
+ */
+public class BoundAggregator {
+    private final IMultisetAggregationOperator<?, ?, ?> operator;
+    private final Class<?> domainType;
+    private final Class<?> aggregateResultType;
+
+    public BoundAggregator(IMultisetAggregationOperator<?, ?, ?> operator, 
+            Class<?> domainType,
+            Class<?> aggregateResultType) {
+        super();
+        this.operator = operator;
+        this.domainType = domainType;
+        this.aggregateResultType = aggregateResultType;
+    }
+
+    public IMultisetAggregationOperator<?, ?, ?> getOperator() {
+        return operator;
+    }
+
+    public Class<?> getDomainType() {
+        return domainType;
+    }
+
+    public Class<?> getAggregateResultType() {
+        return aggregateResultType;
+    }
+
+    public IInputKey getDomainTypeAsInputKey() {
+        return toJavaInputKey(domainType);
+    }
+
+    public IInputKey getAggregateResultTypeAsInputKey() {
+        return toJavaInputKey(aggregateResultType);
+    }
+
+    private static IInputKey toJavaInputKey(Class<?> type) {
+        if (type==null) {
+            return null;
+        } else { 
+            return new JavaTransitiveInstancesKey(type);
+        }
+    }
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/aggregations/IAggregatorFactory.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/aggregations/IAggregatorFactory.java
new file mode 100644
index 00000000..c970bd6a
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/aggregations/IAggregatorFactory.java
@@ -0,0 +1,40 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2016, Zoltan Ujhelyi, Tamas Szabo, 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.psystem.aggregations;
+
+/**
+ * 
+ * Describes an aggregation operator keyword, potentially with type polymorphism. The actual runtime
+ * {@link IMultisetAggregationOperator} that implements the aggregation logic may depend on the type context.
+ * 
+ * <p>
+ * Implementors are suggested to use lower-case classnames (as it will end up in the language) and are required use the
+ * annotation {@link AggregatorType} to indicate type inference rules.
+ * 
+ * <p>
+ * <strong>Important!</strong> Implemented aggregators must be (1) deterministic (2) pure and (3)support incremental
+ * value updates in the internal operation.
+ * 
+ * @author Zoltan Ujhelyi
+ * @since 1.4
+ */
+
+public interface IAggregatorFactory {
+
+    /**
+     * Given type parameters selected from {@link AggregatorType} annotations, returns a run-time aggregator operator
+     * that is bound to the actual types.
+     * 
+     * @param domainClass
+     *            Java type of the values that are being aggregated
+     * @return the actual run-time aggregator logic, with type bindings
+     */
+    public BoundAggregator getAggregatorLogic(Class<?> domainClass);
+
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/aggregations/IMultisetAggregationOperator.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/aggregations/IMultisetAggregationOperator.java
new file mode 100644
index 00000000..3bc22274
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/aggregations/IMultisetAggregationOperator.java
@@ -0,0 +1,106 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2016, Gabor Bergmann, IncQueryLabs 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.psystem.aggregations;
+
+import java.util.Collection;
+import java.util.stream.Stream;
+
+import tools.refinery.viatra.runtime.matchers.aggregators.ExtremumOperator;
+
+/**
+ * A single column aggregator is used to incrementally compute the aggregate of a multiset of values according to an aggregator operator.
+ * 
+ * <p> The operator provides two methods of computation: <ul>
+ *  <li>Stateless aggregation of an explicit multiset, provided by {@link #aggregateStatelessly(Collection)}.</li>
+ *  <li>Incremental aggregation, provided by {@link #createNeutral()}, {@link #update(Object, Object, boolean)}, {@link #isNeutral(Object)}, {@link #getAggregate(Object)}.    
+ * </ul>
+ * 
+ * <p> In case of incremental computation, the aggregable multiset is conceptual; it is not represented by an explicit Collection<Domain> object, but its update operations are tracked.  
+ * 
+ * <p> In case of incremental computation, internal results, potentially distinct from the final aggregate result, may be stored in a helper data structure called <b>accumulator</b>.
+ * The goal of this distinction is that the final result may not be sufficient for incremental updates (see e.g. {@link ExtremumOperator}).
+ * 
+ * @author Gabor Bergmann
+ *
+ * @param <Domain> the type of elements to be aggregated.
+ * @param <Accumulator> the type used to store the interim results of the aggregate computation, 
+ *  that may be incrementally refreshed upon updates to the multiset, and that can easily yield the final result.
+ * @param <AggregateResult> the type of the final result of the aggregation to be output.
+ * 
+ * @since 1.4
+ */
+public interface IMultisetAggregationOperator<Domain, Accumulator, AggregateResult> {
+    
+    /**
+     * A textual description of the operator.
+     */
+    String getShortDescription();
+    
+    /**
+     * A name or identifier of the operator.
+     */
+    String getName();
+    
+    /**
+     * @return the neutral element, i.e. the interim result of aggregating an empty multiset.
+     */
+    Accumulator createNeutral();
+    
+    /**
+     * @return true if the interim result is equivalent to the neutral element, as if there are no values in the multiset.
+     * Must return true if the multiset is empty.
+     */
+    boolean isNeutral(Accumulator result);
+
+    /**
+     * @return an updated intermediate result, 
+     *  changed to reflect that a given object was added to / removed from the multiset 
+     *      (as indicated by the parameter isInsertion)
+     */
+    Accumulator update(Accumulator oldResult, Domain updateValue, boolean isInsertion);
+    
+    /**
+     * @return the aggregate result obtained from the given intermediate result. 
+     * May be null to indicate that the current multiset cannot be aggregated (e.g. 0 elements have no minimum).
+     */
+    AggregateResult getAggregate(Accumulator result);
+
+    /**
+     * Calculates the aggregate results from a given stream of values; all values are considered as inserted
+     * @return the aggregate result, or null if no result can be calculated (e.g. because of an empty stream)
+     * @since 2.0
+     */
+    AggregateResult aggregateStream(Stream<Domain> stream);
+    
+    /**
+     * Clones the given accumulator (with all its internal contents).
+     */
+    default Accumulator clone(Accumulator original) {
+        throw new UnsupportedOperationException();
+    }
+    
+    /**
+     * Combines the given aggregate result and accumulator into a single aggregate result. 
+     */
+    default AggregateResult combine(AggregateResult left, Accumulator right) {
+        throw new UnsupportedOperationException();
+    }
+    
+    default boolean contains(Domain value, Accumulator accumulator) {
+        throw new UnsupportedOperationException();
+    }
+    
+    /**
+     * Pretty prints the contents of the given accumulator. 
+     */
+    default String prettyPrint(final Accumulator accumulator) {
+        return accumulator.toString();
+    }
+    
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/analysis/QueryAnalyzer.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/analysis/QueryAnalyzer.java
new file mode 100644
index 00000000..e3f28cff
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/analysis/QueryAnalyzer.java
@@ -0,0 +1,194 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2016, Gabor Bergmann, IncQueryLabs 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.psystem.analysis;
+
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Map;
+import java.util.Map.Entry;
+import java.util.Set;
+import java.util.stream.Collectors;
+
+import tools.refinery.viatra.runtime.matchers.context.IQueryBackendContext;
+import tools.refinery.viatra.runtime.matchers.context.IQueryMetaContext;
+import tools.refinery.viatra.runtime.matchers.planning.helpers.FunctionalDependencyHelper;
+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.annotations.PAnnotation;
+import tools.refinery.viatra.runtime.matchers.psystem.annotations.ParameterReference;
+import tools.refinery.viatra.runtime.matchers.psystem.basicdeferred.ExportedParameter;
+import tools.refinery.viatra.runtime.matchers.psystem.basicenumerables.PositivePatternCall;
+import tools.refinery.viatra.runtime.matchers.psystem.queries.PParameter;
+import tools.refinery.viatra.runtime.matchers.psystem.queries.PQuery;
+
+/**
+ * Object responsible for computing and caching static query analysis results.
+ * <p> Any client can instantiate this to statically analyze queries. 
+ * Query backends should share an instance obtained via {@link IQueryBackendContext} to save resources.
+ * <p> Precondition: all involved queries must be initialized.
+ * @noinstantiate Considered unstable API; subject to change in future versions. 
+ * Either use the analyzer provided by {@link IQueryBackendContext}, or anticipate 
+ * potential future breakage when instantiating your own analyzer.
+ * @author Gabor Bergmann
+ * @since 1.5
+ */
+public final class QueryAnalyzer {
+    
+    private IQueryMetaContext metaContext;
+
+    public QueryAnalyzer(IQueryMetaContext metaContext) {
+        this.metaContext = metaContext;
+    }
+
+    // Functional dependencies
+    
+    /**
+     * Maps query and strictness to functional dependencies 
+     */
+    private Map<PQuery, Map<Set<Integer>, Set<Integer>>> strictFunctionalDependencyGuarantees =  
+            new HashMap<>();
+    private Map<PQuery, Map<Set<Integer>, Set<Integer>>> softFunctionalDependencyGuarantees =  
+            new HashMap<>();
+
+    /**
+     * Functional dependency information, expressed on query parameters, that the match set of the query is guaranteed to respect. 
+     * <p> The type dependencies shall be expressed on the <i>parameter index</i> integers, NOT the {@link PParameter} object.
+     * @return a non-null map of functional dependencies on parameters that can be processed by {@link FunctionalDependencyHelper}
+     * @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 (@FunctionalDependency) 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 Map<Set<Integer>, Set<Integer>> getProjectedFunctionalDependencies(PQuery query, boolean strict) {
+        Map<PQuery, Map<Set<Integer>, Set<Integer>>> guaranteeStore =  strict ? strictFunctionalDependencyGuarantees : softFunctionalDependencyGuarantees;
+        Map<Set<Integer>, Set<Integer>> dependencies = guaranteeStore.get(query);
+        //  Why not computeIfAbsent? See Bug 532507
+        //      Invoked method #computeFunctionalDependencies may trigger functional dependency computation for called queries;
+        //      and may thus recurs back into #getProjectedFunctionalDependencies, causing a ConcurrentModificationException
+        //      if the called query has not been previously analyzed.
+        //
+        //      Note: if patterns are recursive, the empty accumulator will be found in the store 
+        //          (this yields a safe lower estimate and guarantees termination for #getProjectedFunctionalDependencies)
+        //          But this case probably will not occur due to recursive queries having a disjunction at some point, 
+        //          and thus ignored by #computeFunctionalDependencies  
+        if (dependencies == null) {
+            dependencies = new HashMap<>(); // accumulator
+            guaranteeStore.put(query, dependencies);
+            computeFunctionalDependencies(dependencies, query, strict);
+        }
+        return dependencies;
+    }
+
+    private void computeFunctionalDependencies(Map<Set<Integer>, Set<Integer>> accumulator, PQuery query, boolean strict) {
+        Set<PBody> bodies = query.getDisjunctBodies().getBodies();            
+        if (bodies.size() == 1) { // no support for recursion or disjunction
+
+            PBody body = bodies.iterator().next();
+            
+            // collect parameter variables
+            Map<PVariable, Integer> parameters = body.getSymbolicParameters().stream()
+                    .collect(Collectors.toMap(ExportedParameter::getParameterVariable,
+                            param -> query.getParameters().indexOf(param.getPatternParameter())));
+            
+            // collect all internal dependencies
+            Map<Set<PVariable>, Set<PVariable>> internalDependencies = 
+                    getFunctionalDependencies(body.getConstraints(), strict);
+            
+            // project onto parameter variables
+            Map<Set<PVariable>, Set<PVariable>> projectedDeps = 
+                    FunctionalDependencyHelper.projectDependencies(internalDependencies, parameters.keySet());
+            
+            // translate into indices
+            for (Entry<Set<PVariable>, Set<PVariable>> entry : projectedDeps.entrySet()) {
+                Set<Integer> left = new HashSet<Integer>();
+                Set<Integer> right = new HashSet<Integer>();
+                for (PVariable pVariable : entry.getKey()) {
+                    left.add(parameters.get(pVariable));
+                }
+                for (PVariable pVariable : entry.getValue()) {
+                    right.add(parameters.get(pVariable));
+                }
+                accumulator.put(left, right);
+            }
+            
+        } else {
+            // Disjunctive case, no dependencies are inferred
+            // TODO: we can still salvage the intersection of dependencies IF 
+            // - all bodies have disjoint match sets
+            // - and we avoid recursion
+        }
+        
+        // add annotation-based soft dependencies (regardless of number of bodies)
+        if (!strict) {
+            outer:
+                for (PAnnotation annotation : query.getAnnotationsByName("FunctionalDependency")) {
+                    Set<Integer> lefts = new HashSet<Integer>();
+                    Set<Integer> rights = new HashSet<Integer>();
+                    
+                    for (Object object : annotation.getAllValues("forEach")) {
+                        ParameterReference parameter = (ParameterReference) object;
+                        Integer position = query.getPositionOfParameter(parameter.getName());
+                        if (position == null) continue outer;
+                        lefts.add(position);
+                    }
+                    for (Object object : annotation.getAllValues("unique")) {
+                        ParameterReference parameter = (ParameterReference) object;
+                        Integer position = query.getPositionOfParameter(parameter.getName());
+                        if (position == null) continue outer;
+                        rights.add(position);
+                    }
+                    
+                    FunctionalDependencyHelper.includeDependency(accumulator, lefts, rights);
+                }
+        }
+    }
+
+    /**
+     * Functional dependency information, expressed on PVariables within a body, that the selected constraints imply. 
+     * @return a non-null map of functional dependencies on PVariables that can be processed by {@link FunctionalDependencyHelper}
+     * @param constraints the set of constraints whose consequences will be analyzed
+     * @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 (@FunctionalDependency) 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 Map<Set<PVariable>, Set<PVariable>> getFunctionalDependencies(Set<? extends PConstraint> constraints, boolean strict) {
+        Map<Set<PVariable>, Set<PVariable>> accumulator = new HashMap<Set<PVariable>, Set<PVariable>>();
+        for (PConstraint pConstraint : constraints){
+            if (pConstraint instanceof PositivePatternCall) {
+                // use query analysis results instead
+                PositivePatternCall call = (PositivePatternCall) pConstraint;
+                PQuery query = call.getSupplierKey();
+                Map<Set<Integer>, Set<Integer>> paramDependencies = getProjectedFunctionalDependencies(query, strict);
+                for (Entry<Set<Integer>, Set<Integer>> entry : paramDependencies.entrySet()) {
+                    Set<PVariable> lefts = new HashSet<PVariable>();
+                    Set<PVariable> rights = new HashSet<PVariable>();
+                    
+                    for (Integer index : entry.getKey()) {
+                        lefts.add(call.getVariableInTuple(index));
+                    }
+                    for (Integer index : entry.getValue()) {
+                        rights.add(call.getVariableInTuple(index));
+                    }
+                    
+                    FunctionalDependencyHelper.includeDependency(accumulator, 
+                            lefts, rights);
+                }
+            } else {
+                // delegate to PConstraint
+                FunctionalDependencyHelper.includeDependencies(accumulator, 
+                        pConstraint.getFunctionalDependencies(metaContext));
+            }
+        }
+        return accumulator;
+    }
+
+
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/annotations/PAnnotation.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/annotations/PAnnotation.java
new file mode 100644
index 00000000..c4fbe0e9
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/annotations/PAnnotation.java
@@ -0,0 +1,94 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2014, 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.psystem.annotations;
+
+import java.util.List;
+import java.util.Optional;
+import java.util.Set;
+import java.util.function.BiConsumer;
+
+import org.eclipse.collections.api.multimap.MutableMultimap;
+import org.eclipse.collections.impl.multimap.list.FastListMultimap;
+
+/**
+ * A container describing query annotations
+ * @author Zoltan Ujhelyi
+ *
+ */
+public class PAnnotation {
+
+    private final String name;
+    private MutableMultimap<String, Object> attributes = FastListMultimap.newMultimap();
+
+    public PAnnotation(String name) {
+        this.name = name;
+
+    }
+
+    /**
+     * Adds an attribute to the annotation
+     * @param attributeName
+     * @param value
+     */
+    public void addAttribute(String attributeName, Object value) {
+        attributes.put(attributeName, value);
+    }
+
+    /**
+     * Return the name of the annotation
+     */
+    public String getName() {
+        return name;
+    }
+
+    /**
+     * Returns the value of the first occurrence of an attribute
+     * @param attributeName
+     * @return the attribute value, or null, if attribute is not available
+     * @since 2.0
+     */
+    public Optional<Object> getFirstValue(String attributeName) {
+        return getAllValues(attributeName).stream().findFirst();
+    }
+    
+    /**
+     * Returns the value of the first occurrence of an attribute
+     * @param attributeName
+     * @return the attribute value, or null, if attribute is not available
+     * @since 2.0
+     */
+    public <T> Optional<T> getFirstValue(String attributeName, Class<T> clazz) {
+        return getAllValues(attributeName).stream().filter(clazz::isInstance).map(clazz::cast).findFirst();
+    }
+
+    /**
+     * Returns all values of a selected attribute
+     * @param attributeName
+     * @return a non-null, but possibly empty list of attributes
+     */
+    public List<Object> getAllValues(String attributeName) {
+        return attributes.get(attributeName).toList();
+    }
+    
+    /**
+     * Executes a consumer over all attributes. A selected attribute name (key) can appear (and thus consumed) multiple times.
+     * @since 2.0
+     */
+    public void forEachValue(BiConsumer<String, Object> consumer) {
+        attributes.forEachKeyValue(consumer::accept);
+    }
+
+    /**
+     * Returns a set of all attribute names used in this annotation
+     * @since 2.1
+     */
+    public Set<String> getAllAttributeNames() {
+        return attributes.keySet().toSet();
+    }
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/annotations/ParameterReference.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/annotations/ParameterReference.java
new file mode 100644
index 00000000..c67e9046
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/annotations/ParameterReference.java
@@ -0,0 +1,30 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2014, 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.psystem.annotations;
+
+/**
+ * An annotation parameter referencing a query parameter by name. Does not check whether the parameter exists.
+ *
+ * @author Zoltan Ujhelyi
+ *
+ */
+public class ParameterReference {
+
+    final String name;
+
+    public ParameterReference(String name) {
+        super();
+        this.name = name;
+    }
+
+    public String getName() {
+        return name;
+    }
+
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/basicdeferred/AggregatorConstraint.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/basicdeferred/AggregatorConstraint.java
new file mode 100644
index 00000000..56f86e89
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/basicdeferred/AggregatorConstraint.java
@@ -0,0 +1,98 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2016, Tamas Szabo, 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.psystem.basicdeferred;
+
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Map;
+import java.util.Set;
+
+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.PBody;
+import tools.refinery.viatra.runtime.matchers.psystem.PVariable;
+import tools.refinery.viatra.runtime.matchers.psystem.TypeJudgement;
+import tools.refinery.viatra.runtime.matchers.psystem.aggregations.BoundAggregator;
+import tools.refinery.viatra.runtime.matchers.psystem.queries.PQuery;
+import tools.refinery.viatra.runtime.matchers.tuple.Tuple;
+import tools.refinery.viatra.runtime.matchers.tuple.Tuples;
+
+/**
+ * The PSystem representation of an aggregation.
+ * 
+ * @author Tamas Szabo
+ * @since 1.4
+ */
+public class AggregatorConstraint extends PatternCallBasedDeferred implements ITypeInfoProviderConstraint {
+
+    protected PVariable resultVariable;
+    private BoundAggregator aggregator;
+    protected int aggregatedColumn;
+
+    public AggregatorConstraint(BoundAggregator aggregator, PBody pBody, Tuple actualParametersTuple, PQuery query,
+            PVariable resultVariable, int aggregatedColumn) {
+        super(pBody, actualParametersTuple, query, Collections.singleton(resultVariable));
+        this.resultVariable = resultVariable;
+        this.aggregatedColumn = aggregatedColumn;
+        this.aggregator = aggregator;
+    }
+
+    public int getAggregatedColumn() {
+        return this.aggregatedColumn;
+    }
+
+    public BoundAggregator getAggregator() {
+        return this.aggregator;
+    }
+
+    @Override
+    public Set<PVariable> getDeducedVariables() {
+        return Collections.singleton(resultVariable);
+    }
+
+    @Override
+    public Map<Set<PVariable>, Set<PVariable>> getFunctionalDependencies(IQueryMetaContext context) {
+        final Map<Set<PVariable>, Set<PVariable>> result = new HashMap<Set<PVariable>, Set<PVariable>>();
+        result.put(getDeferringVariables(), getDeducedVariables());
+        return result;
+    }
+
+    @Override
+    protected void doDoReplaceVariables(PVariable obsolete, PVariable replacement) {
+        if (resultVariable.equals(obsolete))
+            resultVariable = replacement;
+    }
+
+    @Override
+    protected Set<PVariable> getCandidateQuantifiedVariables() {
+        return actualParametersTuple.<PVariable> getDistinctElements();
+    }
+
+    @Override
+    protected String toStringRest() {
+        return query.getFullyQualifiedName() + "@" + actualParametersTuple.toString() + "->"
+                + resultVariable.toString();
+    }
+
+    public PVariable getResultVariable() {
+        return resultVariable;
+    }
+
+    @Override
+    public Set<TypeJudgement> getImpliedJudgements(IQueryMetaContext context) {
+        Set<TypeJudgement> result = new HashSet<TypeJudgement>();
+        IInputKey aggregateResultType = aggregator.getAggregateResultTypeAsInputKey();
+        if (aggregateResultType != null) {
+            result.add(new TypeJudgement(aggregateResultType, Tuples.staticArityFlatTupleOf(resultVariable)));
+        }
+        return result;
+    }
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/basicdeferred/BaseTypeSafeConstraint.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/basicdeferred/BaseTypeSafeConstraint.java
new file mode 100644
index 00000000..7bc949a8
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/basicdeferred/BaseTypeSafeConstraint.java
@@ -0,0 +1,99 @@
+/*******************************************************************************
+ * 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.psystem.basicdeferred;
+
+import java.util.Collections;
+import java.util.Set;
+import java.util.stream.Collectors;
+import java.util.stream.Stream;
+
+import tools.refinery.viatra.runtime.matchers.context.IQueryMetaContext;
+import tools.refinery.viatra.runtime.matchers.planning.SubPlan;
+import tools.refinery.viatra.runtime.matchers.psystem.PBody;
+import tools.refinery.viatra.runtime.matchers.psystem.PVariable;
+import tools.refinery.viatra.runtime.matchers.psystem.TypeJudgement;
+import tools.refinery.viatra.runtime.matchers.psystem.VariableDeferredPConstraint;
+
+/**
+ * @author Gabor Bergmann
+ * 
+ */
+public abstract class BaseTypeSafeConstraint extends
+        VariableDeferredPConstraint {
+    
+    protected Set<PVariable> inputVariables;
+    protected PVariable outputVariable;
+
+    public PVariable getOutputVariable() {
+        return outputVariable;
+    }
+
+    /**
+     * @param pBody
+     * @param inputVariables
+     * @param outputVariable null iff no output (check-only)
+     */
+    public BaseTypeSafeConstraint(PBody pBody,
+            Set<PVariable> inputVariables, final PVariable outputVariable) {
+        super(pBody, 
+                (outputVariable == null) ? 
+                        inputVariables : 
+                            Stream.concat(inputVariables.stream(), Stream.of(outputVariable)).collect(Collectors.toSet())
+                    );
+        this.inputVariables = inputVariables;
+        this.outputVariable = outputVariable;
+    }
+
+    @Override
+    public Set<PVariable> getDeducedVariables() {
+        if (outputVariable == null) 
+            return Collections.emptySet(); 
+        else
+            return Collections.singleton(outputVariable);
+    }
+
+    @Override
+    public Set<PVariable> getDeferringVariables() {
+        return inputVariables;
+    }
+
+    @Override
+    public boolean isReadyAt(SubPlan plan, IQueryMetaContext context) {
+        if (super.isReadyAt(plan, context)) {
+            return checkTypeSafety(plan, context) == null;
+        }
+        return false;
+    }
+
+    /**
+     * Checks whether all type restrictions are already enforced on affected variables.
+     * 
+     * @param plan
+     * @return a variable whose type safety is not enforced yet, or null if the plan is typesafe
+     */
+    public PVariable checkTypeSafety(SubPlan plan, IQueryMetaContext context) {
+        Set<TypeJudgement> impliedJudgements = plan.getAllImpliedTypeJudgements(context);
+        
+        for (PVariable pVariable : inputVariables) {
+            Set<TypeJudgement> allTypeRestrictionsForVariable = pBody.getAllUnaryTypeRestrictions(context).get(pVariable);
+            if (allTypeRestrictionsForVariable != null && !impliedJudgements.containsAll(allTypeRestrictionsForVariable))
+                return pVariable;
+        }
+        return null;
+    }
+    
+    @Override
+    protected void doReplaceVariable(PVariable obsolete, PVariable replacement) {
+        if (inputVariables.remove(obsolete)) 
+            inputVariables.add(replacement);
+        if (outputVariable == obsolete) 
+            outputVariable = replacement;
+    }
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/basicdeferred/Equality.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/basicdeferred/Equality.java
new file mode 100644
index 00000000..b978b62c
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/basicdeferred/Equality.java
@@ -0,0 +1,96 @@
+/*******************************************************************************
+ * 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.psystem.basicdeferred;
+
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Map;
+import java.util.Set;
+
+import tools.refinery.viatra.runtime.matchers.context.IQueryMetaContext;
+import tools.refinery.viatra.runtime.matchers.planning.SubPlan;
+import tools.refinery.viatra.runtime.matchers.psystem.DeferredPConstraint;
+import tools.refinery.viatra.runtime.matchers.psystem.PBody;
+import tools.refinery.viatra.runtime.matchers.psystem.PVariable;
+
+/**
+ * @author Gabor Bergmann
+ * 
+ */
+public class Equality extends DeferredPConstraint {
+
+    private PVariable who;
+    private PVariable withWhom;
+
+    public Equality(PBody pBody, PVariable who, PVariable withWhom) {
+        super(pBody, buildSet(who, withWhom));
+        this.who = who;
+        this.withWhom = withWhom;
+    }
+
+    private static Set<PVariable> buildSet(PVariable who, PVariable withWhom) {
+        Set<PVariable> set = new HashSet<PVariable>();
+        set.add(who);
+        set.add(withWhom);
+        return set;
+    }
+
+    /**
+     * An equality is moot if it compares the a variable with itself.
+     * 
+     * @return true, if the equality is moot
+     */
+    public boolean isMoot() {
+        return who.equals(withWhom);
+    }
+
+    @Override
+    public void doReplaceVariable(PVariable obsolete, PVariable replacement) {
+        if (obsolete.equals(who))
+            who = replacement;
+        if (obsolete.equals(withWhom))
+            withWhom = replacement;
+    }
+
+    @Override
+    protected String toStringRest() {
+        return who.getName() + "=" + withWhom.getName();
+    }
+
+    public PVariable getWho() {
+        return who;
+    }
+
+    public PVariable getWithWhom() {
+        return withWhom;
+    }
+
+    @Override
+    public Set<PVariable> getDeducedVariables() {
+        return Collections.emptySet();
+    }
+    
+    @Override
+    public Map<Set<PVariable>, Set<PVariable>> getFunctionalDependencies(IQueryMetaContext context) {
+        final Map<Set<PVariable>, Set<PVariable>> result = new HashMap<Set<PVariable>, Set<PVariable>>();
+        result.put(Collections.singleton(who), Collections.singleton(withWhom));
+        result.put(Collections.singleton(withWhom), Collections.singleton(who));
+        return result;
+    }
+
+    @Override
+    public boolean isReadyAt(SubPlan plan, IQueryMetaContext context) {
+        return plan.getVisibleVariables().contains(who) && plan.getVisibleVariables().contains(withWhom);
+        // will be replaced by || if copierNode is available;
+        // until then, LayoutHelper.unifyVariablesAlongEqualities(PSystem<PatternDescription, StubHandle, Collector>) is
+        // recommended.
+    }
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/basicdeferred/ExportedParameter.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/basicdeferred/ExportedParameter.java
new file mode 100644
index 00000000..80706792
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/basicdeferred/ExportedParameter.java
@@ -0,0 +1,108 @@
+/*******************************************************************************
+ * 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.psystem.basicdeferred;
+
+import java.util.Collections;
+import java.util.Set;
+
+import tools.refinery.viatra.runtime.matchers.planning.QueryProcessingException;
+import tools.refinery.viatra.runtime.matchers.psystem.PBody;
+import tools.refinery.viatra.runtime.matchers.psystem.PVariable;
+import tools.refinery.viatra.runtime.matchers.psystem.VariableDeferredPConstraint;
+import tools.refinery.viatra.runtime.matchers.psystem.queries.PParameter;
+import tools.refinery.viatra.runtime.matchers.psystem.queries.PQuery;
+
+/**
+ * @author Gabor Bergmann
+ *
+ */
+public class ExportedParameter extends VariableDeferredPConstraint {
+    PVariable parameterVariable;
+    final String parameterName;
+    final PParameter patternParameter;
+
+    /**
+     * @since 1.4
+     */
+    public ExportedParameter(PBody pBody, PVariable parameterVariable, PParameter patternParameter) {
+        super(pBody, Collections.singleton(parameterVariable));
+        this.parameterVariable = parameterVariable;
+        this.patternParameter = patternParameter;
+        parameterName = patternParameter.getName();
+    }
+
+    @Override
+    public void doReplaceVariable(PVariable obsolete, PVariable replacement) {
+        if (obsolete.equals(parameterVariable))
+            parameterVariable = replacement;
+    }
+
+    @Override
+    protected String toStringRest() {
+        Object varName = parameterVariable.getName();
+        return parameterName.equals(varName) ? parameterName : parameterName + "(" + varName + ")";
+    }
+
+    @Override
+    public Set<PVariable> getDeducedVariables() {
+        return Collections.emptySet();
+    }
+
+    /**
+     * The name of the parameter; usually, it is expected that {@link #getParameterVariable()} is more useful, except
+     * maybe for debugging purposes.
+     * 
+     * @return a non-null name of the parameter
+     */
+    public String getParameterName() {
+        return parameterName;
+    }
+
+    public PVariable getParameterVariable() {
+        return parameterVariable;
+    }
+
+    /**
+     * @since 1.4
+     */
+    public PParameter getPatternParameter() {
+        if (patternParameter == null) {
+            PQuery query = pBody.getPattern();
+            Integer index = query.getPositionOfParameter(parameterName);
+            if (index == null) {
+                throw new IllegalStateException(String.format("Pattern %s does not have a parameter named %s",
+                        query.getFullyQualifiedName(), parameterName));
+            }
+            return query.getParameters().get(index);
+        } else {
+            return patternParameter;
+        }
+    }
+
+    @Override
+    public Set<PVariable> getDeferringVariables() {
+        return Collections.singleton(parameterVariable);
+    }
+
+    @Override
+    public void checkSanity() {
+        super.checkSanity();
+        if (!parameterVariable.isDeducable()) {
+            String[] args = { parameterName };
+            String msg = "Impossible to match pattern: "
+                    + "exported pattern variable {1} can not be determined based on the pattern constraints. "
+                    + "HINT: certain constructs (e.g. negative patterns or check expressions) cannot output symbolic parameters.";
+            String shortMsg = "Could not deduce value of parameter";
+            throw new QueryProcessingException(msg, args, shortMsg, null);
+        }
+
+    }
+
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/basicdeferred/ExpressionEvaluation.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/basicdeferred/ExpressionEvaluation.java
new file mode 100644
index 00000000..06688c36
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/basicdeferred/ExpressionEvaluation.java
@@ -0,0 +1,80 @@
+/*******************************************************************************
+ * 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.psystem.basicdeferred;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.LinkedHashSet;
+import java.util.Map;
+import java.util.Set;
+
+import tools.refinery.viatra.runtime.matchers.context.IQueryMetaContext;
+import tools.refinery.viatra.runtime.matchers.psystem.IExpressionEvaluator;
+import tools.refinery.viatra.runtime.matchers.psystem.PBody;
+import tools.refinery.viatra.runtime.matchers.psystem.PVariable;
+import tools.refinery.viatra.runtime.matchers.tuple.Tuples;
+
+/**
+ * @author Zoltan Ujhelyi
+ *
+ */
+public class ExpressionEvaluation extends BaseTypeSafeConstraint {
+
+    private IExpressionEvaluator evaluator;
+    private boolean isUnwinding;
+
+    public ExpressionEvaluation(PBody pBody, IExpressionEvaluator evaluator, PVariable outputVariable) {
+        this(pBody, evaluator, outputVariable, false);
+    }
+
+    /**
+     * @since 2.4
+     */
+    public ExpressionEvaluation(PBody pBody, IExpressionEvaluator evaluator, PVariable outputVariable,
+            boolean isUnwinding) {
+        super(pBody, getPVariablesOfExpression(pBody, evaluator), outputVariable);
+        this.evaluator = evaluator;
+        this.isUnwinding = isUnwinding;
+    }
+
+    /**
+     * @since 2.4
+     */
+    public boolean isUnwinding() {
+        return isUnwinding;
+    }
+
+    public IExpressionEvaluator getEvaluator() {
+        return evaluator;
+    }
+
+    @Override
+    protected String toStringRest() {
+        return Tuples.flatTupleOf(new ArrayList<PVariable>(inputVariables).toArray()).toString() + "|="
+                + evaluator.getShortDescription();
+    }
+
+    @Override
+    public Map<Set<PVariable>, Set<PVariable>> getFunctionalDependencies(IQueryMetaContext context) {
+        if (outputVariable == null)
+            return Collections.emptyMap();
+        else
+            return Collections.singletonMap(inputVariables, Collections.singleton(outputVariable));
+    }
+
+    private static Set<PVariable> getPVariablesOfExpression(PBody pBody, IExpressionEvaluator evaluator) {
+        // use a linked set, so that the variables will come in the order of the parameters
+        Set<PVariable> result = new LinkedHashSet<PVariable>();
+        for (String name : evaluator.getInputParameterNames()) {
+            PVariable variable = pBody.getOrCreateVariableByName(name);
+            result.add(variable);
+        }
+        return result;
+    }
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/basicdeferred/Inequality.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/basicdeferred/Inequality.java
new file mode 100644
index 00000000..5cac33dc
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/basicdeferred/Inequality.java
@@ -0,0 +1,151 @@
+/*******************************************************************************
+ * 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.psystem.basicdeferred;
+
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.HashSet;
+import java.util.Set;
+
+import tools.refinery.viatra.runtime.matchers.psystem.PBody;
+import tools.refinery.viatra.runtime.matchers.psystem.PVariable;
+import tools.refinery.viatra.runtime.matchers.psystem.VariableDeferredPConstraint;
+
+/**
+ * @author Gabor Bergmann
+ * 
+ */
+public class Inequality extends VariableDeferredPConstraint {
+
+    private PVariable who;
+    private PVariable withWhom;
+
+    /**
+     * The inequality constraint is weak if it can be ignored when who is the same as withWhom, or if any if them is
+     * undeducible.
+     */
+    private boolean weak;
+
+    public Inequality(PBody pBody, PVariable who, PVariable withWhom) {
+        this(pBody, who, withWhom, false);
+    }
+
+    public Inequality(PBody pBody, PVariable who, PVariable withWhom,
+            boolean weak) {
+        super(pBody, new HashSet<>(Arrays.asList(who, withWhom) ));
+        this.who = who;
+        this.withWhom = withWhom;
+        this.weak = weak;
+    }
+
+    // private Inequality(
+    // PSystem<PatternDescription, StubHandle, ?> pSystem,
+    // PVariable subject, Set<PVariable> inequals)
+    // {
+    // super(pSystem, include(inequals, subject));
+    // this.subject = subject;
+    // this.inequals = inequals;
+    // }
+
+    // private static HashSet<PVariable> include(Set<PVariable> inequals, PVariable subject) {
+    // HashSet<PVariable> hashSet = new HashSet<PVariable>(inequals);
+    // hashSet.add(subject);
+    // return hashSet;
+    // }
+
+    @Override
+    public Set<PVariable> getDeferringVariables() {
+        return getAffectedVariables();
+    }
+
+    // private static int[] mapIndices(Map<Object, Integer> variablesIndex, Set<PVariable> keys) {
+    // int[] result = new int[keys.size()];
+    // int k = 0;
+    // for (PVariable key : keys) {
+    // result[k++] = variablesIndex.get(key);
+    // }
+    // return result;
+    // }
+
+    // @Override
+    // public IFoldablePConstraint getIncorporator() {
+    // return incorporator;
+    // }
+    //
+    // @Override
+    // public void registerIncorporatationInto(IFoldablePConstraint incorporator) {
+    // this.incorporator = incorporator;
+    // }
+    //
+    // @Override
+    // public boolean incorporate(IFoldablePConstraint other) {
+    // if (other instanceof Inequality<?, ?>) {
+    // Inequality other2 = (Inequality) other;
+    // if (subject.equals(other2.subject)) {
+    // Set<PVariable> newInequals = new HashSet<PVariable>(inequals);
+    // newInequals.addAll(other2.inequals);
+    // return new Inequality<PatternDescription, StubHandle>(buildable, subject, newInequals);
+    // }
+    // } else return false;
+    // }
+
+    @Override
+    protected String toStringRest() {
+        return who.toString() + (isWeak() ? "!=?" : "!=") + withWhom.toString();
+    }
+
+    @Override
+    public void doReplaceVariable(PVariable obsolete, PVariable replacement) {
+        if (obsolete.equals(who))
+            who = replacement;
+        if (obsolete.equals(withWhom))
+            withWhom = replacement;
+    }
+
+    @Override
+    public Set<PVariable> getDeducedVariables() {
+        return Collections.emptySet();
+    }
+
+    /**
+     * The inequality constraint is weak if it can be ignored when who is the same as withWhom, or if any if them is
+     * undeducible.
+     * 
+     * @return the weak
+     */
+    public boolean isWeak() {
+        return weak;
+    }
+
+    /**
+     * A weak inequality constraint is eliminable if who is the same as withWhom, or if any if them is undeducible.
+     */
+    public boolean isEliminable() {
+        return isWeak() && (who.equals(withWhom) || !who.isDeducable() || !withWhom.isDeducable());
+    }
+
+    /**
+     * Eliminates a weak inequality constraint if it can be ignored when who is the same as withWhom, or if any if them
+     * is undeducible.
+     */
+    public void eliminateWeak() {
+        if (isEliminable())
+            delete();
+    }
+
+    public PVariable getWho() {
+        return who;
+    }
+
+    public PVariable getWithWhom() {
+        return withWhom;
+    }
+
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/basicdeferred/NegativePatternCall.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/basicdeferred/NegativePatternCall.java
new file mode 100644
index 00000000..87d9d9fc
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/basicdeferred/NegativePatternCall.java
@@ -0,0 +1,52 @@
+/*******************************************************************************
+ * 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.psystem.basicdeferred;
+
+import java.util.Collections;
+import java.util.Set;
+
+import tools.refinery.viatra.runtime.matchers.psystem.PBody;
+import tools.refinery.viatra.runtime.matchers.psystem.PVariable;
+import tools.refinery.viatra.runtime.matchers.psystem.queries.PQuery;
+import tools.refinery.viatra.runtime.matchers.tuple.Tuple;
+
+/**
+ * @author Gabor Bergmann
+ * 
+ */
+public class NegativePatternCall extends PatternCallBasedDeferred {
+
+    public NegativePatternCall(PBody pBody, Tuple actualParametersTuple, PQuery query) {
+        super(pBody, actualParametersTuple, query);
+    }
+
+    @Override
+    public Set<PVariable> getDeducedVariables() {
+        return Collections.emptySet();
+    }
+
+    /**
+     * @return all variables that may potentially be quantified they are not used anywhere else
+     */
+    @Override
+    protected Set<PVariable> getCandidateQuantifiedVariables() {
+        return getAffectedVariables();
+    }
+
+    @Override
+    protected void doDoReplaceVariables(PVariable obsolete, PVariable replacement) {
+    }
+
+    @Override
+    protected String toStringRest() {
+        return "!" + query.getFullyQualifiedName() + "@" + actualParametersTuple.toString();
+    }
+
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/basicdeferred/PatternCallBasedDeferred.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/basicdeferred/PatternCallBasedDeferred.java
new file mode 100644
index 00000000..93eeffec
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/basicdeferred/PatternCallBasedDeferred.java
@@ -0,0 +1,118 @@
+/*******************************************************************************
+ * 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.psystem.basicdeferred;
+
+import java.util.Collections;
+import java.util.HashSet;
+import java.util.Set;
+
+import tools.refinery.viatra.runtime.matchers.planning.QueryProcessingException;
+import tools.refinery.viatra.runtime.matchers.psystem.IQueryReference;
+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.VariableDeferredPConstraint;
+import tools.refinery.viatra.runtime.matchers.psystem.queries.PQuery;
+import tools.refinery.viatra.runtime.matchers.tuple.Tuple;
+
+/**
+ * @author Gabor Bergmann
+ *
+ */
+public abstract class PatternCallBasedDeferred extends VariableDeferredPConstraint implements IQueryReference {
+
+    protected Tuple actualParametersTuple;
+
+    protected abstract void doDoReplaceVariables(PVariable obsolete, PVariable replacement);
+
+    protected abstract Set<PVariable> getCandidateQuantifiedVariables();
+
+    protected PQuery query;
+    private Set<PVariable> deferringVariables;
+
+    public PatternCallBasedDeferred(PBody pBody, Tuple actualParametersTuple,
+            PQuery pattern, Set<PVariable> additionalAffectedVariables) {
+        super(pBody, union(actualParametersTuple.<PVariable> getDistinctElements(), additionalAffectedVariables));
+        this.actualParametersTuple = actualParametersTuple;
+        this.query = pattern;
+    }
+
+    public PatternCallBasedDeferred(PBody pBody, Tuple actualParametersTuple,
+            PQuery pattern) {
+        this(pBody, actualParametersTuple, pattern, Collections.<PVariable> emptySet());
+    }
+
+    private static Set<PVariable> union(Set<PVariable> a, Set<PVariable> b) {
+        Set<PVariable> result = new HashSet<PVariable>();
+        result.addAll(a);
+        result.addAll(b);
+        return result;
+    }
+
+    @Override
+    public Set<PVariable> getDeferringVariables() {
+        if (deferringVariables == null) {
+            deferringVariables = new HashSet<PVariable>();
+            for (PVariable var : getCandidateQuantifiedVariables()) {
+                if (var.isDeducable())
+                    deferringVariables.add(var);
+            }
+        }
+        return deferringVariables;
+    }
+
+    @Override
+    public void checkSanity() {
+        super.checkSanity();
+        for (Object obj : this.actualParametersTuple.getDistinctElements()) {
+            PVariable var = (PVariable) obj;
+            if (!getDeferringVariables().contains(var)) {
+                // so this is a free variable of the NAC / aggregation?
+                for (PConstraint pConstraint : var.getReferringConstraints()) {
+                    if (pConstraint != this
+                            && !(pConstraint instanceof Equality && ((Equality) pConstraint).isMoot()))
+                        throw new QueryProcessingException (
+                                "Variable {1} of constraint {2} is not a positively determined part of the pattern, yet it is also affected by {3}.",
+                                new String[] { var.toString(), this.toString(), pConstraint.toString() },
+                                "Read-only variable can not be deduced", null);
+                }
+            }
+        }
+
+    }
+
+//    public SubPlan getSidePlan(IOperationCompiler compiler) throws QueryPlannerException {
+//        SubPlan sidePlan = compiler.patternCallPlan(actualParametersTuple, query);
+//        sidePlan = BuildHelper.enforceVariableCoincidences(compiler, sidePlan);
+//        return sidePlan;
+//    }
+
+    @Override
+    protected void doReplaceVariable(PVariable obsolete, PVariable replacement) {
+        if (deferringVariables != null) {
+            // FAIL instead of hopeless attempt to fix
+            // if (deferringVariables.remove(obsolete)) deferringVariables.add(replacement);
+            throw new IllegalStateException("Cannot replace variables on " + this
+                    + " when deferring variables have already been identified.");
+        }
+        actualParametersTuple = actualParametersTuple.replaceAll(obsolete, replacement);
+        doDoReplaceVariables(obsolete, replacement);
+    }
+
+    public Tuple getActualParametersTuple() {
+        return actualParametersTuple;
+    }
+
+    @Override
+    public PQuery getReferredQuery() {
+        return query;
+    }
+
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/basicdeferred/PatternMatchCounter.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/basicdeferred/PatternMatchCounter.java
new file mode 100644
index 00000000..0c40d91e
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/basicdeferred/PatternMatchCounter.java
@@ -0,0 +1,70 @@
+/*******************************************************************************
+ * 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.psystem.basicdeferred;
+
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.Map;
+import java.util.Set;
+
+import tools.refinery.viatra.runtime.matchers.context.IQueryMetaContext;
+import tools.refinery.viatra.runtime.matchers.psystem.PBody;
+import tools.refinery.viatra.runtime.matchers.psystem.PVariable;
+import tools.refinery.viatra.runtime.matchers.psystem.queries.PQuery;
+import tools.refinery.viatra.runtime.matchers.tuple.Tuple;
+
+/**
+ * @author Gabor Bergmann
+ */
+public class PatternMatchCounter extends PatternCallBasedDeferred {
+
+    private PVariable resultVariable;
+
+    public PatternMatchCounter(PBody pBody, Tuple actualParametersTuple,
+            PQuery query, PVariable resultVariable) {
+        super(pBody, actualParametersTuple, query, Collections.singleton(resultVariable));
+        this.resultVariable = resultVariable;
+    }
+
+    @Override
+    public Set<PVariable> getDeducedVariables() {
+        return Collections.singleton(resultVariable);
+    }
+    
+    @Override
+    public Map<Set<PVariable>, Set<PVariable>> getFunctionalDependencies(IQueryMetaContext context) {
+        final Map<Set<PVariable>, Set<PVariable>> result = new HashMap<Set<PVariable>, Set<PVariable>>();
+        result.put(getDeferringVariables(), getDeducedVariables());
+        return result;
+    }
+
+    @Override
+    protected void doDoReplaceVariables(PVariable obsolete, PVariable replacement) {
+        if (resultVariable.equals(obsolete))
+            resultVariable = replacement;
+    }
+
+    @Override
+    protected Set<PVariable> getCandidateQuantifiedVariables() {
+        return actualParametersTuple.<PVariable> getDistinctElements();
+    }
+
+
+    @Override
+    protected String toStringRest() {
+        return query.getFullyQualifiedName() + "@" + actualParametersTuple.toString() + "->"
+                + resultVariable.toString();
+    }
+
+    public PVariable getResultVariable() {
+        return resultVariable;
+    }
+
+}
\ No newline at end of file
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/basicdeferred/RelationEvaluation.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/basicdeferred/RelationEvaluation.java
new file mode 100644
index 00000000..336a83fb
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/basicdeferred/RelationEvaluation.java
@@ -0,0 +1,57 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2022, Tamas Szabo, GitHub
+ * 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.psystem.basicdeferred;
+
+import java.util.List;
+
+import tools.refinery.viatra.runtime.matchers.psystem.EnumerablePConstraint;
+import tools.refinery.viatra.runtime.matchers.psystem.IMultiQueryReference;
+import tools.refinery.viatra.runtime.matchers.psystem.IRelationEvaluator;
+import tools.refinery.viatra.runtime.matchers.psystem.PBody;
+import tools.refinery.viatra.runtime.matchers.psystem.queries.PQuery;
+import tools.refinery.viatra.runtime.matchers.tuple.Tuple;
+
+/**
+ * A constraint which prescribes the evaluation of custom Java logic that takes an arbitrary number of input relations
+ * and produces one output relation. Contrast this to {@link ExpressionEvaluation}, which produces a single output value
+ * given an input tuple.
+ * 
+ * The assumption is that the relation evaluation logic is not incremental, that is, it can only perform from-scratch
+ * computation of the output relation given the complete input relations. To this end, the relation evaluator always
+ * receives the complete input relations with all their contents as input. However, the evaluator engine makes sure that
+ * the output of the relation evaluation is at least "seemingly" incremental. This means that the underlying computation
+ * network computes the delta on the output compared to the previous output and only propagates the delta further.
+ * 
+ * @author Tamas Szabo
+ * 
+ * @since 2.8
+ *
+ */
+public class RelationEvaluation extends EnumerablePConstraint implements IMultiQueryReference {
+
+    private final IRelationEvaluator evaluator;
+    private final List<PQuery> inputQueries;
+
+    public RelationEvaluation(final PBody body, final Tuple variablesTuple, final List<PQuery> inputQueries,
+            final IRelationEvaluator evaluator) {
+        super(body, variablesTuple);
+        this.evaluator = evaluator;
+        this.inputQueries = inputQueries;
+    }
+
+    public IRelationEvaluator getEvaluator() {
+        return this.evaluator;
+    }
+
+    @Override
+    public List<PQuery> getReferredQueries() {
+        return this.inputQueries;
+    }
+
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/basicdeferred/TypeFilterConstraint.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/basicdeferred/TypeFilterConstraint.java
new file mode 100644
index 00000000..8b6e29ef
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/basicdeferred/TypeFilterConstraint.java
@@ -0,0 +1,105 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2015, 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.psystem.basicdeferred;
+
+import java.util.Collections;
+import java.util.Map;
+import java.util.Set;
+
+import tools.refinery.viatra.runtime.matchers.context.IInputKey;
+import tools.refinery.viatra.runtime.matchers.context.IQueryMetaContext;
+import tools.refinery.viatra.runtime.matchers.psystem.ITypeConstraint;
+import tools.refinery.viatra.runtime.matchers.psystem.PBody;
+import tools.refinery.viatra.runtime.matchers.psystem.PVariable;
+import tools.refinery.viatra.runtime.matchers.psystem.TypeJudgement;
+import tools.refinery.viatra.runtime.matchers.psystem.VariableDeferredPConstraint;
+import tools.refinery.viatra.runtime.matchers.psystem.basicenumerables.TypeConstraint;
+import tools.refinery.viatra.runtime.matchers.tuple.Tuple;
+
+/**
+ * Represents a non-enumerable type constraint that asserts that values substituted for the given tuple of variables 
+ *      form a tuple that belongs to a (typically non-enumerable) extensional relation identified by an {@link IInputKey}.
+ * 
+ * <p> The InputKey is typically not enumerable. If it is enumerable, use {@link TypeConstraint} instead, so that the PConstraint carries over the property of enumerability.
+ * 
+ * @author Bergmann Gabor
+ *
+ */
+public class TypeFilterConstraint extends VariableDeferredPConstraint implements
+        ITypeConstraint {
+
+    private Tuple variablesTuple;
+    private IInputKey inputKey;
+    
+    private TypeJudgement equivalentJudgement;
+
+    
+    public TypeFilterConstraint(PBody pBody, Tuple variablesTuple, IInputKey inputKey) {
+        super(pBody, variablesTuple.<PVariable> getDistinctElements());
+        this.equivalentJudgement = new TypeJudgement(inputKey, variablesTuple);
+
+        this.variablesTuple = variablesTuple;
+        this.inputKey = inputKey;
+        
+        if (variablesTuple.getSize() != inputKey.getArity())
+            throw new IllegalArgumentException(
+                    this.getClass().getSimpleName() + 
+                    " applied for variable tuple " + variablesTuple + " having wrong arity for input key " + 
+                            inputKey);
+   }
+
+    
+    
+    public Tuple getVariablesTuple() {
+        return variablesTuple;
+    }
+
+    public IInputKey getInputKey() {
+        return inputKey;
+    }
+
+    @Override
+    public TypeJudgement getEquivalentJudgement() {
+        return equivalentJudgement;
+    }
+
+    @Override
+    protected void doReplaceVariable(PVariable obsolete, PVariable replacement) {
+        variablesTuple = variablesTuple.replaceAll(obsolete, replacement);
+        this.equivalentJudgement = new TypeJudgement(inputKey, variablesTuple);
+    }
+
+    @Override
+    public Set<TypeJudgement> getImpliedJudgements(IQueryMetaContext context) {
+        return Collections.singleton(equivalentJudgement);
+    }
+
+    @Override
+    public Set<PVariable> getDeducedVariables() {
+        return Collections.emptySet();
+    }
+
+    @Override
+    public Set<PVariable> getDeferringVariables() {
+        return getAffectedVariables();
+    }
+
+    @Override
+    protected String toStringRest() {
+        return inputKey.getPrettyPrintableName() + "@" + variablesTuple;
+    }
+    
+    @Override
+    public Map<Set<PVariable>, Set<PVariable>> getFunctionalDependencies(IQueryMetaContext context) {
+        return TypeConstraintUtil.getFunctionalDependencies(context, inputKey, variablesTuple);
+    }
+
+    
+    
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/basicenumerables/AbstractTransitiveClosure.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/basicenumerables/AbstractTransitiveClosure.java
new file mode 100644
index 00000000..7bbf7118
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/basicenumerables/AbstractTransitiveClosure.java
@@ -0,0 +1,44 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2018, Gabor Bergmann, Zoltan Ujhelyi, 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.psystem.basicenumerables;
+
+import java.util.Set;
+
+import tools.refinery.viatra.runtime.matchers.context.IQueryMetaContext;
+import tools.refinery.viatra.runtime.matchers.psystem.IQueryReference;
+import tools.refinery.viatra.runtime.matchers.psystem.ITypeInfoProviderConstraint;
+import tools.refinery.viatra.runtime.matchers.psystem.KeyedEnumerablePConstraint;
+import tools.refinery.viatra.runtime.matchers.psystem.PBody;
+import tools.refinery.viatra.runtime.matchers.psystem.TypeJudgement;
+import tools.refinery.viatra.runtime.matchers.psystem.queries.PQuery;
+import tools.refinery.viatra.runtime.matchers.tuple.Tuple;
+
+/**
+ * @since 2.0
+ */
+public abstract class AbstractTransitiveClosure extends KeyedEnumerablePConstraint<PQuery> implements IQueryReference, ITypeInfoProviderConstraint {
+
+    public AbstractTransitiveClosure(PBody pBody, Tuple variablesTuple, PQuery supplierKey) {
+        super(pBody, variablesTuple, supplierKey);
+    }
+
+    @Override
+    public PQuery getReferredQuery() {
+        return supplierKey;
+    }
+
+    /**
+     * @since 1.3
+     */
+    @Override
+    public Set<TypeJudgement> getImpliedJudgements(IQueryMetaContext context) {
+        return PositivePatternCall.getTypesImpliedByCall(supplierKey, variablesTuple);
+    }
+
+}
\ No newline at end of file
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/basicenumerables/BinaryReflexiveTransitiveClosure.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/basicenumerables/BinaryReflexiveTransitiveClosure.java
new file mode 100644
index 00000000..e3dae240
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/basicenumerables/BinaryReflexiveTransitiveClosure.java
@@ -0,0 +1,57 @@
+/*******************************************************************************
+ * Copyright (c) 2004-2010 Zoltan Ujhelyi, 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.psystem.basicenumerables;
+
+import tools.refinery.viatra.runtime.matchers.context.IInputKey;
+import tools.refinery.viatra.runtime.matchers.planning.QueryProcessingException;
+import tools.refinery.viatra.runtime.matchers.psystem.PBody;
+import tools.refinery.viatra.runtime.matchers.psystem.queries.PQuery;
+import tools.refinery.viatra.runtime.matchers.tuple.Tuple;
+
+/**
+ * For a binary base pattern over an enumerable universe type, computes the reflexive transitive closure (base)*
+ * 
+ * @author Gabor Bergmann, Zoltan Ujhelyi
+ * @since 2.0
+ */
+public class BinaryReflexiveTransitiveClosure extends AbstractTransitiveClosure {
+
+    private final IInputKey universeType;
+
+    public BinaryReflexiveTransitiveClosure(PBody pBody, Tuple variablesTuple,
+            PQuery pattern, IInputKey universeType) {
+        super(pBody, variablesTuple, pattern);
+        this.universeType = universeType;
+    }
+
+    @Override
+    protected String keyToString() {
+        return supplierKey.getFullyQualifiedName() + "*";
+    }
+
+    /**
+     * Returns the type whose instances should be returned as 0-long paths. 
+     * @since 2.0
+     */
+    public IInputKey getUniverseType() {
+        return universeType;
+    }
+
+    @Override
+    public void checkSanity() {
+        if (!universeType.isEnumerable() || universeType.getArity() != 1) {
+            throw new QueryProcessingException(
+                    String.format("Invalid universe type %s - it should be enumerable and must have an arity of 1.",
+                            universeType.getPrettyPrintableName()),
+                    pBody.getPattern());
+        }
+    }
+    
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/basicenumerables/BinaryTransitiveClosure.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/basicenumerables/BinaryTransitiveClosure.java
new file mode 100644
index 00000000..716d043b
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/basicenumerables/BinaryTransitiveClosure.java
@@ -0,0 +1,33 @@
+/*******************************************************************************
+ * 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.psystem.basicenumerables;
+
+import tools.refinery.viatra.runtime.matchers.psystem.PBody;
+import tools.refinery.viatra.runtime.matchers.psystem.queries.PQuery;
+import tools.refinery.viatra.runtime.matchers.tuple.Tuple;
+
+/**
+ * For a binary base pattern, computes the irreflexive transitive closure (base)+
+ * 
+ * @author Gabor Bergmann
+ * 
+ */
+public class BinaryTransitiveClosure extends AbstractTransitiveClosure {
+
+    public BinaryTransitiveClosure(PBody pBody, Tuple variablesTuple,
+            PQuery pattern) {
+        super(pBody, variablesTuple, pattern);
+    }
+
+    @Override
+    protected String keyToString() {
+        return supplierKey.getFullyQualifiedName() + "+";
+    }
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/basicenumerables/Connectivity.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/basicenumerables/Connectivity.java
new file mode 100644
index 00000000..10da2e21
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/basicenumerables/Connectivity.java
@@ -0,0 +1,11 @@
+/*
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.viatra.runtime.matchers.psystem.basicenumerables;
+
+public enum Connectivity {
+        WEAK,
+        STRONG;
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/basicenumerables/ConstantValue.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/basicenumerables/ConstantValue.java
new file mode 100644
index 00000000..251146c8
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/basicenumerables/ConstantValue.java
@@ -0,0 +1,57 @@
+/*******************************************************************************
+ * 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.psystem.basicenumerables;
+
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.Map;
+import java.util.Set;
+
+import tools.refinery.viatra.runtime.matchers.context.IQueryMetaContext;
+import tools.refinery.viatra.runtime.matchers.psystem.KeyedEnumerablePConstraint;
+import tools.refinery.viatra.runtime.matchers.psystem.PBody;
+import tools.refinery.viatra.runtime.matchers.psystem.PVariable;
+import tools.refinery.viatra.runtime.matchers.tuple.Tuples;
+
+/**
+ * @author Gabor Bergmann
+ * 
+ */
+public class ConstantValue extends KeyedEnumerablePConstraint<Object> {
+
+    private PVariable variable;
+
+    public ConstantValue(PBody pBody, PVariable variable, Object value) {
+        super(pBody, Tuples.staticArityFlatTupleOf(variable), value);
+        this.variable = variable;
+    }
+
+    @Override
+    protected String keyToString() {
+        return supplierKey.toString();
+    }
+    
+    /**
+     * @since 1.7
+     */
+    public PVariable getVariable() {
+        return variable;
+    }
+    
+    @Override
+    public Map<Set<PVariable>, Set<PVariable>> getFunctionalDependencies(IQueryMetaContext context) {
+        final Map<Set<PVariable>, Set<PVariable>> result = new HashMap<Set<PVariable>, Set<PVariable>>();
+        final Set<PVariable> emptySet = Collections.emptySet(); // a constant value is functionally determined by everything
+        result.put(emptySet, Collections.singleton(getVariableInTuple(0)));
+        return result;
+    }
+
+
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/basicenumerables/PositivePatternCall.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/basicenumerables/PositivePatternCall.java
new file mode 100644
index 00000000..25ab34b4
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/basicenumerables/PositivePatternCall.java
@@ -0,0 +1,76 @@
+/*******************************************************************************
+ * 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.psystem.basicenumerables;
+
+import java.util.HashSet;
+import java.util.Set;
+
+import tools.refinery.viatra.runtime.matchers.context.IInputKey;
+import tools.refinery.viatra.runtime.matchers.context.IQueryMetaContext;
+import tools.refinery.viatra.runtime.matchers.psystem.IQueryReference;
+import tools.refinery.viatra.runtime.matchers.psystem.ITypeInfoProviderConstraint;
+import tools.refinery.viatra.runtime.matchers.psystem.KeyedEnumerablePConstraint;
+import tools.refinery.viatra.runtime.matchers.psystem.PBody;
+import tools.refinery.viatra.runtime.matchers.psystem.TypeJudgement;
+import tools.refinery.viatra.runtime.matchers.psystem.queries.PQuery;
+import tools.refinery.viatra.runtime.matchers.tuple.Tuple;
+import tools.refinery.viatra.runtime.matchers.tuple.Tuples;
+
+/**
+ * @author Gabor Bergmann
+ *
+ */
+public class PositivePatternCall extends KeyedEnumerablePConstraint<PQuery> implements IQueryReference, ITypeInfoProviderConstraint {
+
+    public PositivePatternCall(PBody pBody, Tuple variablesTuple,
+            PQuery pattern) {
+        super(pBody, variablesTuple, pattern);
+    }
+
+    @Override
+    protected String keyToString() {
+        return supplierKey.getFullyQualifiedName();
+    }
+
+    // Note: #getFunctionalDependencies is intentionally not implemented - use QueryAnalyzer instead!
+//    @Override
+//    public Map<Set<PVariable>, Set<PVariable>> getFunctionalDependencies(IQueryMetaContext context) {
+//        return super.getFunctionalDependencies(context);
+//    }
+
+    @Override
+    public PQuery getReferredQuery() {
+        return supplierKey;
+    }
+
+    @Override
+    public Set<TypeJudgement> getImpliedJudgements(IQueryMetaContext context) {
+        return getTypesImpliedByCall(supplierKey, variablesTuple);
+    }
+
+    /**
+     * @since 1.3
+     */
+    public static Set<TypeJudgement> getTypesImpliedByCall(PQuery calledQuery, Tuple actualParametersTuple) {
+        Set<TypeJudgement> result = new HashSet<TypeJudgement>();
+        for (TypeJudgement parameterJudgement : calledQuery.getTypeGuarantees()) {                      
+            IInputKey inputKey = parameterJudgement.getInputKey();
+            Tuple judgementIndexTuple = parameterJudgement.getVariablesTuple();
+            
+            Object[] judgementVariables = new Object[judgementIndexTuple.getSize()];
+            for (int i=0; i<judgementVariables.length; ++i)
+                judgementVariables[i] = actualParametersTuple.get((int) judgementIndexTuple.get(i));
+            
+            result.add(new TypeJudgement(inputKey, Tuples.flatTupleOf(judgementVariables))); 
+        }
+        return result;
+    }
+
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/basicenumerables/RepresentativeElectionConstraint.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/basicenumerables/RepresentativeElectionConstraint.java
new file mode 100644
index 00000000..b97ff55f
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/basicenumerables/RepresentativeElectionConstraint.java
@@ -0,0 +1,43 @@
+/*
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.viatra.runtime.matchers.psystem.basicenumerables;
+
+import tools.refinery.viatra.runtime.matchers.context.IQueryMetaContext;
+import tools.refinery.viatra.runtime.matchers.psystem.*;
+import tools.refinery.viatra.runtime.matchers.psystem.queries.PQuery;
+import tools.refinery.viatra.runtime.matchers.tuple.Tuple;
+
+import java.util.Set;
+
+public class RepresentativeElectionConstraint extends KeyedEnumerablePConstraint<PQuery>
+                implements IQueryReference, ITypeInfoProviderConstraint {
+        private final Connectivity connectivity;
+
+        public RepresentativeElectionConstraint(PBody pBody, Tuple variablesTuple, PQuery supplierKey,
+                                                                                        Connectivity connectivity) {
+                super(pBody, variablesTuple, supplierKey);
+                this.connectivity = connectivity;
+        }
+
+        public Connectivity getConnectivity() {
+                return connectivity;
+        }
+
+        @Override
+        public PQuery getReferredQuery() {
+                return supplierKey;
+        }
+
+        @Override
+        public Set<TypeJudgement> getImpliedJudgements(IQueryMetaContext context) {
+                return PositivePatternCall.getTypesImpliedByCall(supplierKey, variablesTuple);
+        }
+
+        @Override
+        protected String keyToString() {
+                return supplierKey.getFullyQualifiedName() + "#" + connectivity + "#representative";
+        }
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/basicenumerables/TypeConstraint.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/basicenumerables/TypeConstraint.java
new file mode 100644
index 00000000..2ca54cc0
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/basicenumerables/TypeConstraint.java
@@ -0,0 +1,79 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2014, 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.psystem.basicenumerables;
+
+import java.util.Collections;
+import java.util.Map;
+import java.util.Set;
+
+import tools.refinery.viatra.runtime.matchers.context.IInputKey;
+import tools.refinery.viatra.runtime.matchers.context.IQueryMetaContext;
+import tools.refinery.viatra.runtime.matchers.psystem.ITypeConstraint;
+import tools.refinery.viatra.runtime.matchers.psystem.KeyedEnumerablePConstraint;
+import tools.refinery.viatra.runtime.matchers.psystem.PBody;
+import tools.refinery.viatra.runtime.matchers.psystem.PVariable;
+import tools.refinery.viatra.runtime.matchers.psystem.TypeJudgement;
+import tools.refinery.viatra.runtime.matchers.tuple.Tuple;
+
+/**
+ * Represents an enumerable type constraint that asserts that values substituted for the given tuple of variables 
+ *      form a tuple that belongs to an enumerable extensional relation identified by an {@link IInputKey}.
+ *
+ * <p> The InputKey must be enumerable!
+ *
+ * @author Zoltan Ujhelyi
+ *
+ */
+public class TypeConstraint extends KeyedEnumerablePConstraint<IInputKey> implements ITypeConstraint {
+    
+    private TypeJudgement equivalentJudgement;
+    
+    public TypeConstraint(PBody pBody, Tuple variablesTuple, IInputKey inputKey) {
+        super(pBody, variablesTuple, inputKey);
+        this.equivalentJudgement = new TypeJudgement(inputKey, variablesTuple);
+        
+        if (! inputKey.isEnumerable())
+            throw new IllegalArgumentException(
+                    this.getClass().getSimpleName() + 
+                    " applicable for enumerable input keys only; received instead " + 
+                            inputKey);
+        if (variablesTuple.getSize() != inputKey.getArity())
+            throw new IllegalArgumentException(
+                    this.getClass().getSimpleName() + 
+                    " applied for variable tuple " + variablesTuple + " having wrong arity for input key " + 
+                            inputKey);
+    }
+
+    @Override
+    protected String keyToString() {
+        return supplierKey.getPrettyPrintableName();
+    }
+    
+    @Override
+    public TypeJudgement getEquivalentJudgement() {
+        return equivalentJudgement;
+    }
+
+    @Override
+    public Set<TypeJudgement> getImpliedJudgements(IQueryMetaContext context) {
+        return Collections.singleton(equivalentJudgement);
+        //return equivalentJudgement.getDirectlyImpliedJudgements(context);
+    }
+    
+    @Override
+    public Map<Set<PVariable>, Set<PVariable>> getFunctionalDependencies(IQueryMetaContext context) {
+        return TypeConstraintUtil.getFunctionalDependencies(context, supplierKey, variablesTuple);
+    }
+
+    @Override
+    public void doReplaceVariable(PVariable obsolete, PVariable replacement) {
+        super.doReplaceVariable(obsolete, replacement);
+        this.equivalentJudgement = new TypeJudgement(getSupplierKey(), variablesTuple);
+    }
+}
\ No newline at end of file
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/queries/BasePQuery.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/queries/BasePQuery.java
new file mode 100644
index 00000000..2c03a894
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/queries/BasePQuery.java
@@ -0,0 +1,231 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2015, 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.psystem.queries;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Objects;
+import java.util.Optional;
+import java.util.Set;
+import java.util.stream.Collectors;
+import java.util.stream.Stream;
+
+import tools.refinery.viatra.runtime.matchers.ViatraQueryRuntimeException;
+import tools.refinery.viatra.runtime.matchers.backend.IQueryBackendFactory;
+import tools.refinery.viatra.runtime.matchers.backend.QueryEvaluationHint;
+import tools.refinery.viatra.runtime.matchers.context.IInputKey;
+import tools.refinery.viatra.runtime.matchers.psystem.PBody;
+import tools.refinery.viatra.runtime.matchers.psystem.TypeJudgement;
+import tools.refinery.viatra.runtime.matchers.psystem.annotations.PAnnotation;
+import tools.refinery.viatra.runtime.matchers.tuple.Tuples;
+import tools.refinery.viatra.runtime.matchers.util.Preconditions;
+
+/**
+ * Default implementation of PQuery.
+ * 
+ * @author Bergmann Gabor
+ */
+public abstract class BasePQuery implements PQuery {
+
+        protected PQueryStatus status = PQueryStatus.UNINITIALIZED;
+        /**
+     * @since 2.0
+     */
+        protected final PVisibility visibility;
+        protected List<PProblem> pProblems = new ArrayList<PProblem>();
+        private List<PAnnotation> annotations = new ArrayList<PAnnotation>();
+        private QueryEvaluationHint evaluationHints = new QueryEvaluationHint(null, (IQueryBackendFactory)null);
+        PDisjunction canonicalDisjunction;
+        private List<String> parameterNames = null; // Lazy initialization
+        
+        /** For traceability only. */
+        private List<Object> wrappingQuerySpecifications = new ArrayList<Object>(1);
+
+        @Override
+        public Integer getPositionOfParameter(String parameterName) {
+                ensureInitialized();
+            int index = getParameterNames().indexOf(parameterName);
+            return index != -1 ? index : null;
+        }
+
+        protected void setStatus(PQueryStatus newStatus) {
+            this.status = newStatus;
+        }
+
+        protected void addError(PProblem problem) {
+                status = PQueryStatus.ERROR;
+            pProblems.add(problem);
+        }
+
+        @Override
+        public PQueryStatus getStatus() {
+            return status;
+        }
+
+        @Override
+        public List<PProblem> getPProblems() {
+                return Collections.unmodifiableList(pProblems);
+        }
+
+        @Override
+        public boolean isMutable() {
+            return status.equals(PQueryStatus.UNINITIALIZED) || status.equals(PQueryStatus.INITIALIZING);
+        }
+
+        @Override
+        public void checkMutability() {
+            Preconditions.checkState(isMutable(), "Cannot edit query definition %s", getFullyQualifiedName());
+        }
+
+        /**
+     * @since 1.5
+     */
+        public void setEvaluationHints(QueryEvaluationHint hints) {
+            checkMutability();
+            this.evaluationHints = hints;
+        }
+
+        @Override
+        public QueryEvaluationHint getEvaluationHints() {
+                ensureInitialized();
+                return evaluationHints;
+                // TODO instead of field, compute something from annotations?
+        }
+
+        protected void addAnnotation(PAnnotation annotation) {
+            checkMutability();
+            annotations.add(annotation);
+        }
+
+        @Override
+        public List<PAnnotation> getAllAnnotations() {
+                ensureInitialized();
+            return new ArrayList<>(annotations);
+        }
+
+        private Stream<PAnnotation> getAnnotationStreamByName(final String name) {
+            ensureInitialized();
+        return annotations.stream().filter(Objects::nonNull).filter(annotation -> Objects.equals(name, annotation.getName()));
+        }
+        
+        @Override
+        public List<PAnnotation> getAnnotationsByName(final String annotationName) {
+                return getAnnotationStreamByName(annotationName).collect(Collectors.toList());
+        }
+
+        @Override
+        public Optional<PAnnotation> getFirstAnnotationByName(String annotationName) {
+            return getAnnotationStreamByName(annotationName).findFirst();
+        }
+
+        @Override
+        public List<String> getParameterNames() {
+                ensureInitialized();
+                if (parameterNames == null) {
+                    parameterNames = getParameters().stream().map(PParameter::getName).collect(Collectors.toList()); 
+                }
+            return parameterNames;
+        }
+
+        @Override
+        public Set<PQuery> getDirectReferredQueries() {
+                ensureInitialized();
+            return canonicalDisjunction.getDirectReferredQueries();
+        }
+
+        @Override
+        public Set<PQuery> getAllReferredQueries() {
+            ensureInitialized();
+            return canonicalDisjunction.getAllReferredQueries();
+        }
+
+
+        @Override
+        public List<Object> publishedAs() {
+                return wrappingQuerySpecifications;
+        }
+        
+        @Override
+        public Set<TypeJudgement> getTypeGuarantees() {
+            ensureInitialized();
+                Set<TypeJudgement> result = new HashSet<TypeJudgement>();
+                
+                List<PParameter> parameters = getParameters();
+                for (int i=0; i<parameters.size(); ++i) {
+                        PParameter parameter = parameters.get(i);
+                        IInputKey declaredUnaryType = parameter.getDeclaredUnaryType();
+                        if (declaredUnaryType != null) {
+                                result.add(new TypeJudgement(declaredUnaryType, Tuples.staticArityFlatTupleOf(i)));
+                        }
+                }
+                
+                return result;
+        }
+        
+        /**
+     * @since 2.0
+     */
+        public BasePQuery(PVisibility visibility) {
+                super();
+                this.visibility = visibility;
+        }
+
+        @Override
+        public PDisjunction getDisjunctBodies() {
+                ensureInitialized();
+            Preconditions.checkState(!status.equals(PQueryStatus.ERROR), "Query %s contains errors.", getFullyQualifiedName());
+            return canonicalDisjunction;
+        }
+
+        @Override
+        public final void ensureInitialized() {
+            try {
+            if (status.equals(PQueryStatus.UNINITIALIZED)) {
+                setStatus(PQueryStatus.INITIALIZING);
+                setBodies(doGetContainedBodies());
+                setStatus(PQueryStatus.OK);
+            }
+            } catch (QueryInitializationException e) {
+                addError(new PProblem(e, e.getShortMessage()));
+                throw e;
+            }
+        }
+
+        protected final void setBodies(Set<PBody> bodies) {
+            canonicalDisjunction = new PDisjunction(this, bodies);
+            for (PBody body : canonicalDisjunction.getBodies()) {
+                body.setStatus(null);
+            }
+            setStatus(PQueryStatus.OK);
+        }
+
+        /**
+         * Creates and returns the bodies of the query. If recalled again, a new instance is created.
+         * 
+         * @return
+         * @throws ViatraQueryRuntimeException
+         */
+        protected abstract Set<PBody> doGetContainedBodies();
+
+        @Override
+        public String toString() {
+            return String.format("PQuery<%s>=%s", getFullyQualifiedName(), super.toString());
+        }
+
+    /**
+     * @since 2.0
+     */
+    @Override
+    public PVisibility getVisibility() {
+        return visibility;
+    }
+        
+}
\ No newline at end of file
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/queries/PDisjunction.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/queries/PDisjunction.java
new file mode 100644
index 00000000..eae4eacf
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/queries/PDisjunction.java
@@ -0,0 +1,104 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2014, 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.psystem.queries;
+
+import java.util.Collections;
+import java.util.LinkedHashSet;
+import java.util.Set;
+import java.util.stream.Collectors;
+
+import tools.refinery.viatra.runtime.matchers.psystem.PBody;
+
+/**
+ * 
+ * A disjunction is a set of bodies representing separate conditions. A {@link PQuery} has a single, canonical
+ * PDisjunction, that can be replaced using rewriter
+ * 
+ * @author Zoltan Ujhelyi
+ * 
+ */
+public class PDisjunction {
+
+    private Set<PBody> bodies;
+    private PQuery query;
+
+    public PDisjunction(Set<PBody> bodies) {
+        this(bodies.iterator().next().getPattern(), bodies);
+    }
+
+    public PDisjunction(PQuery query, Set<PBody> bodies) {
+        super();
+        this.query = query;
+        this.bodies = Collections.unmodifiableSet(new LinkedHashSet<>(bodies));
+        this.bodies.forEach(body -> body.setContainerDisjunction(this));
+    }
+
+    /**
+     * Returns an immutable set of bodies that consists of this disjunction
+     * 
+     * @return the bodies
+     */
+    public Set<PBody> getBodies() {
+        return bodies;
+    }
+
+    /**
+     * Returns the corresponding query specification. May be null if not set.
+     */
+    public PQuery getQuery() {
+        return query;
+    }
+
+    /**
+     * Returns all queries directly referred in the constraints. They are all required to evaluate this query
+     * 
+     * @return a non-null, but possibly empty list of query definitions
+     */
+    public Set<PQuery> getDirectReferredQueries() {
+        return this.getBodies().stream().
+                flatMap(PQueries.directlyReferencedQueriesFunction()). // flatten stream of streams
+                collect(Collectors.toCollection(LinkedHashSet::new));
+    }
+
+    /**
+     * Returns all queries required to evaluate this query (transitively).
+     * 
+     * @return a non-null, but possibly empty list of query definitions
+     */
+    public Set<PQuery> getAllReferredQueries() {
+        Set<PQuery> processedQueries = new LinkedHashSet<>();
+        processedQueries.add(this.getQuery());
+        Set<PQuery> foundQueries = getDirectReferredQueries();
+        Set<PQuery> newQueries = new LinkedHashSet<>(foundQueries);
+    
+        while(!processedQueries.containsAll(newQueries)) {
+            PQuery query = newQueries.iterator().next();
+            processedQueries.add(query);
+            newQueries.remove(query);
+            Set<PQuery> referred = query.getDirectReferredQueries();
+            referred.removeAll(processedQueries);
+            foundQueries.addAll(referred);
+            newQueries.addAll(referred);
+        }
+        return foundQueries;
+    }
+    
+    /**
+     * Decides whether a disjunction is mutable. A disjunction is mutable if all its contained bodies are mutable.
+     * 
+     */
+    public boolean isMutable() {
+        for (PBody body : bodies) {
+            if (!body.isMutable()) {
+                return false;
+            }
+        }
+        return true;
+    }
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/queries/PParameter.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/queries/PParameter.java
new file mode 100644
index 00000000..07165aa2
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/queries/PParameter.java
@@ -0,0 +1,105 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2014, 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.psystem.queries;
+
+import java.util.Objects;
+
+import tools.refinery.viatra.runtime.matchers.context.IInputKey;
+
+/**
+ * A descriptor for declared PQuery parameters. A parameter has a name, a declared type and a direction constraint
+ *
+ * @author Zoltan Ujhelyi
+ *
+ */
+public class PParameter {
+
+    private final String name;
+    private final String typeName;
+    private final IInputKey declaredUnaryType;
+    private final PParameterDirection direction;
+
+    public PParameter(String name) {
+        this(name, (String) null);
+    }
+
+    public PParameter(String name, String typeName) {
+        this(name, typeName, (IInputKey) null);
+    }
+
+    public PParameter(String name, String typeName, IInputKey declaredUnaryType) {
+        this(name, typeName, declaredUnaryType, PParameterDirection.INOUT);
+    }
+
+    /**
+     * @since 1.4
+     */
+    public PParameter(String name, String typeName, IInputKey declaredUnaryType, PParameterDirection direction) {
+        super();
+        this.name = name;
+        this.typeName = typeName;
+        this.declaredUnaryType = declaredUnaryType;
+        this.direction = direction;
+
+        if (declaredUnaryType != null && declaredUnaryType.getArity() != 1) {
+            throw new IllegalArgumentException(
+                    "PParameter declared type must be unary instead of " + declaredUnaryType.getPrettyPrintableName());
+        }
+    }
+
+    /**
+     * @return the direction
+     * @since 1.4
+     */
+    public PParameterDirection getDirection() {
+        return direction;
+    }
+
+    /**
+     * @return the name of the parameter
+     */
+    public String getName() {
+        return name;
+    }
+
+    /**
+     * Returns a textual representation of the declared type of the parameter
+     * 
+     * @return the type description, or null if not available
+     */
+    public String getTypeName() {
+        return typeName;
+    }
+
+    /**
+     * Yield an {@link IInputKey} representation of the type declared for this parameter.
+     * 
+     * @return the unary type that was declared on this parameter in the query header, or null if not available
+     */
+    public IInputKey getDeclaredUnaryType() {
+        return declaredUnaryType;
+    }
+
+    @Override
+    public boolean equals(Object obj) {
+        if (obj instanceof PParameter) {
+            return Objects.equals(name, ((PParameter) obj).name)
+                    && Objects.equals(typeName, ((PParameter) obj).typeName)
+                    && Objects.equals(declaredUnaryType, ((PParameter) obj).declaredUnaryType)
+                    && Objects.equals(direction, ((PParameter) obj).direction);
+        }
+        return false;
+    }
+
+    @Override
+    public int hashCode() {
+        return Objects.hash(name, typeName, declaredUnaryType);
+    }
+
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/queries/PParameterDirection.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/queries/PParameterDirection.java
new file mode 100644
index 00000000..c94d4797
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/queries/PParameterDirection.java
@@ -0,0 +1,35 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2016, Grill Balázs, IncQueryLabs
+ * 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.psystem.queries;
+
+/**
+ * Values of this enum describe a constraint to the calling of patterns regarding its parameters.
+ * 
+ * @author Grill Balázs
+ * @since 1.4
+ *
+ */
+public enum PParameterDirection {
+
+    /**
+     * Default value, no additional constraint is applied
+     */
+    INOUT,
+    
+    /**
+     * The parameters marked with this constraints shall be set to a value before calling the pattern
+     */
+    IN,
+    
+    /**
+     * The parameters marked with this constraints shall not be set to a value before calling the pattern
+     */
+    OUT
+    
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/queries/PProblem.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/queries/PProblem.java
new file mode 100644
index 00000000..1fe4f541
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/queries/PProblem.java
@@ -0,0 +1,68 @@
+/*******************************************************************************
+ * 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.psystem.queries;
+
+import tools.refinery.viatra.runtime.matchers.planning.QueryProcessingException;
+
+/**
+ * Represents an error that was detected while the {@link PQuery} object was built from a source.
+ * @author Bergmann Gabor
+ *
+ */
+public class PProblem {
+
+    private final String shortMessage;
+    private final String location; 
+    private final Exception exception;
+
+    public PProblem(String shortMessage) {
+        this(null, shortMessage, null, null);
+    }
+    /**
+     * @since 2.0
+     */
+    public PProblem(String shortMessage, Integer line, Integer column) {
+        this(null, shortMessage, line, column);
+    }
+    public PProblem(QueryProcessingException exception) {
+        this(exception, exception.getShortMessage(), null, null);
+    }
+    public PProblem(Exception exception, String shortMessage) {
+        this(exception, shortMessage, null, null);
+    }
+    
+    /**
+     * @since 2.0
+     */
+    public PProblem(Exception exception, String shortMessage, Integer line, Integer column) {
+        this.shortMessage = shortMessage;
+        this.exception = exception;
+        if (line == null) {
+            location = "Unspecified location";
+        } else if (column == null) {
+            location = String.format("Line %d", line);
+        } else {
+            location = String.format("Line %d Column %d", line, column);
+        }
+    }
+
+    public String getShortMessage() {
+        return shortMessage;
+    }
+    public Exception getException() {
+        return exception;
+    }
+    /**
+     * @since 2.0
+     */
+    public String getLocation() {
+        return location;
+    }
+    
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/queries/PQueries.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/queries/PQueries.java
new file mode 100644
index 00000000..56f8ca76
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/queries/PQueries.java
@@ -0,0 +1,110 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2014, 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.psystem.queries;
+
+import java.util.HashSet;
+import java.util.Set;
+import java.util.function.Function;
+import java.util.function.Predicate;
+import java.util.stream.Stream;
+
+import tools.refinery.viatra.runtime.matchers.context.IInputKey;
+import tools.refinery.viatra.runtime.matchers.psystem.IMultiQueryReference;
+import tools.refinery.viatra.runtime.matchers.psystem.ITypeConstraint;
+import tools.refinery.viatra.runtime.matchers.psystem.PBody;
+import tools.refinery.viatra.runtime.matchers.psystem.PTraceable;
+import tools.refinery.viatra.runtime.matchers.psystem.basicenumerables.TypeConstraint;
+import tools.refinery.viatra.runtime.matchers.psystem.queries.PQuery.PQueryStatus;
+
+/**
+ * Utility class for using PQueries in functional/streaming collection operations effectively
+ *
+ * @author Zoltan Ujhelyi
+ *
+ */
+public final class PQueries {
+
+    /**
+     * Hidden constructor for utility class
+     */
+    private PQueries() {
+    }
+
+    /**
+     * Predicate checking for the status of selected queries
+     *
+     */
+    public static Predicate<PQuery> queryStatusPredicate(final PQueryStatus status) {
+        return query -> query.getStatus().equals(status);
+    }
+
+    /**
+     * Enumerates referred queries (without duplicates) for the given body
+     */
+    public static Function<PBody, Stream<PQuery>> directlyReferencedQueriesFunction() {
+        return body -> (body.getConstraintsOfType(IMultiQueryReference.class).stream()
+                .flatMap(e -> e.getReferredQueries().stream()).distinct());
+    }
+
+    /**
+     * Enumerates directly referred extensional relations (without duplicates) in the canonical form of the given query
+     * 
+     * @param enumerablesOnly
+     *                            only enumerable type constraints are considered
+     * @since 2.0
+     */
+    public static Stream<IInputKey> directlyRequiredTypesOfQuery(PQuery query, boolean enumerablesOnly) {
+        return directlyRequiredTypesOfDisjunction(query.getDisjunctBodies(), enumerablesOnly);
+    }
+
+    /**
+     * Enumerates directly referred extensional relations (without duplicates) for the given formulation of a query.
+     * 
+     * @param enumerablesOnly
+     *                            only enumerable type constraints are considered
+     * @since 2.0
+     */
+    public static Stream<IInputKey> directlyRequiredTypesOfDisjunction(PDisjunction disjunctBodies,
+            boolean enumerablesOnly) {
+        Class<? extends ITypeConstraint> filterClass = enumerablesOnly ? TypeConstraint.class : ITypeConstraint.class;
+        return disjunctBodies.getBodies().stream().flatMap(body -> body.getConstraintsOfType(filterClass).stream())
+                .map(constraint -> constraint.getEquivalentJudgement().getInputKey()).distinct();
+    }
+
+    /**
+     * @since 1.4
+     */
+    public static Predicate<PParameter> parameterDirectionPredicate(final PParameterDirection direction) {
+        return input -> input.getDirection() == direction;
+    }
+
+    /**
+     * Returns all {@link PTraceable}s contained in the given {@link PQuery}: itself, its bodies and their constraints.
+     * 
+     * @since 1.6
+     */
+    public static Set<PTraceable> getTraceables(PQuery query) {
+        final Set<PTraceable> traceables = new HashSet<>();
+        traceables.add(query);
+        query.getDisjunctBodies().getBodies().forEach(body -> {
+            traceables.add(body);
+            body.getConstraints().forEach(traceables::add);
+        });
+        return traceables;
+    }
+
+    /**
+     * Calculates the simple name related from a given qualified name by finding the part after the last '.' character.
+     * 
+     * @since 2.0
+     */
+    public static String calculateSimpleName(String qualifiedName) {
+        return qualifiedName.substring(qualifiedName.lastIndexOf('.') + 1);
+    }
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/queries/PQuery.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/queries/PQuery.java
new file mode 100644
index 00000000..a909c650
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/queries/PQuery.java
@@ -0,0 +1,154 @@
+/*******************************************************************************
+ * 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.psystem.queries;
+
+import java.util.List;
+import java.util.Set;
+
+import tools.refinery.viatra.runtime.matchers.ViatraQueryRuntimeException;
+import tools.refinery.viatra.runtime.matchers.backend.IQueryBackend;
+import tools.refinery.viatra.runtime.matchers.backend.IQueryBackendHintProvider;
+import tools.refinery.viatra.runtime.matchers.backend.QueryEvaluationHint;
+import tools.refinery.viatra.runtime.matchers.psystem.PBody;
+import tools.refinery.viatra.runtime.matchers.psystem.PTraceable;
+import tools.refinery.viatra.runtime.matchers.psystem.TypeJudgement;
+
+/**
+ * Internal representation of a query / graph pattern (using a constraint system formalism), 
+ * to be interpreted by a query evaluator ({@link IQueryBackend}). 
+ * End-users of VIATRA Query should access a query as an IQuerySpecification instead. 
+ * 
+ * <p>
+ * PQuerys are definitions of queries usable inside pattern descriptions. Such description always has (a non-null) name. The query
+ * itself is defined as a (non-empty) set of {@link PBody} instances, the result is the disjunction of the single
+ * {@link PBody} instances. </p>
+ * <p>
+ * A PQuery might be constructed from erroneous patterns or might be uninitialized - this is represented by its status.
+ * 
+ * @author Zoltan Ujhelyi
+ * @since 0.8.0
+ * @noimplement This interface is not intended to be implemented by clients. Use {@link BasePQuery} as a base class instead.
+ */
+public interface PQuery extends PQueryHeader, PTraceable {
+
+    // TODO rewritten as / rewritten from traceability to PDisjunction?
+    
+    /**
+     * @author Zoltan Ujhelyi
+     * 
+     */
+    public enum PQueryStatus {
+        /**
+         * Marks that the query definition is not initialized
+         */
+        UNINITIALIZED,
+        /**
+         * Marks that the query definition is being initialized
+         * @since 1.4
+         */
+        INITIALIZING,
+        /**
+         * The query definition was successfully initialized
+         */
+        OK,
+        /**
+         * The query definition was initialized, but some issues were present
+         */
+        WARNING,
+        /**
+         * The query definition was not successfully initialized because of an error
+         */
+        ERROR
+    }
+
+    /**
+     * Returns all bodies associated with the query in their canonical form. If called multiple times, the same set with
+     * the same contents will be returned.
+     * 
+     */
+    PDisjunction getDisjunctBodies();
+
+    /**
+     * Returns all queries directly referred in the constraints. They are all required to evaluate this query
+     * 
+     * @return a non-null, but possibly empty list of query definitions
+     */
+    Set<PQuery> getDirectReferredQueries();
+
+    /**
+     * Returns all queries required to evaluate this query (transitively).
+     * 
+     * @return a non-null, but possibly empty list of query definitions
+     */
+    Set<PQuery> getAllReferredQueries();
+
+    /**
+     * Returns the initialization status of the definition
+     * 
+     */
+    PQueryStatus getStatus();
+    
+    /**
+     * Returns a list describing the problems that were found in this query.
+     * 
+     * <p> TODO: formulate invariant connecting {@link #getPProblems()} and {@link #getStatus()}.
+     * 
+     * @return a non-null, but possibly empty list of problems
+     */
+    List<PProblem> getPProblems();
+
+    /**
+     * Before a modification operation is executed, a mutability check is performed (via the {@link #getStatus()}
+     * implementation, and in case of problems an {@link IllegalStateException} is thrown.
+     */
+    void checkMutability();
+
+    /**
+     * An option to check mutability of the query. It can be used to avoid getting an {@link IllegalStateException} by
+     * the execution of {@link #checkMutability()}.
+     * 
+     * @return true if the query specification is still editable
+     */
+    boolean isMutable();
+
+    /**
+     * Optional hints regarding the query evaluation strategy, to be interpreted by the query engine.
+     * <p> To ensure the possibility of external overrides, 
+     *  the evaluation engine should not directly consult this field, 
+     *  but use an {@link IQueryBackendHintProvider} instead.
+     */
+    public QueryEvaluationHint getEvaluationHints();
+
+    
+    /**
+     * Type information, expressed on query parameters, that all matches of the query are guaranteed to respect. 
+     * <p> At the very minimum, this should include the declared types of the parameters.
+     * <p> The type judgement tuples shall contain the <i>parameter index</i>, NOT the {@link PParameter} object.
+     * 
+     * @return a non-null set of type judgements that the query guarantees for its matches
+     */
+    public Set<TypeJudgement> getTypeGuarantees();
+
+    /**
+     * If the query definition is uninitialized, initializes it.
+     * @throws ViatraQueryRuntimeException if initialization of query specification fails
+     */
+    public abstract void ensureInitialized();
+    
+    /**
+     * Returns the end-user query specification API objects that wrap this query.
+     * 
+     * <p> Intended for traceability and debug purposes, not part of normal operation. 
+     * Returned list is intended to be appended during query specification construction time.
+     * 
+     * @return a non-null, but possibly empty list of query specification objects;
+     */
+    List<Object> publishedAs();
+
+}
\ No newline at end of file
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/queries/PQueryHeader.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/queries/PQueryHeader.java
new file mode 100644
index 00000000..f3671934
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/queries/PQueryHeader.java
@@ -0,0 +1,101 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2015, 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.psystem.queries;
+
+import java.util.List;
+import java.util.Optional;
+
+import tools.refinery.viatra.runtime.matchers.psystem.annotations.PAnnotation;
+
+/**
+ * Represents header information (metainfo) about a query. 
+ * <p> To be implemented both by IQuerySpecifications intended for end users, 
+ * and the internal query representation {@link PQuery}.
+ * 
+ * 
+ * @author Bergmann Gabor
+ * @since 0.9
+ */
+public interface PQueryHeader {
+
+    /**
+     * Identifies the pattern for which matchers can be instantiated.
+     */
+    public String getFullyQualifiedName();
+
+    /**
+     * Return the list of parameter names
+     * 
+     * @return a non-null, but possibly empty list of parameter names
+     */
+    public List<String> getParameterNames();
+
+    /**
+     * Returns a list of parameter descriptions
+     * 
+     * @return a non-null, but possibly empty list of parameter descriptions
+     */
+    public List<PParameter> getParameters();
+
+    /**
+     * Returns the index of a named parameter
+     * 
+     * @param parameterName
+     * @return the index, or null of no such parameter is available
+     */
+    public Integer getPositionOfParameter(String parameterName);
+
+    /**
+     * Returns a parameter by name if exists
+     * @since 2.1
+     */
+    default Optional<PParameter> getParameter(String parameterName) {
+        return Optional.ofNullable(getPositionOfParameter(parameterName))
+            .map(getParameters()::get);
+    }
+    
+    /**
+     * Returns the list of annotations specified for this query
+     * 
+     * @return a non-null, but possibly empty list of annotations
+     */
+    public List<PAnnotation> getAllAnnotations();
+
+    /**
+     * Returns the list of annotations with a specified name
+     * 
+     * @param annotationName
+     * @return a non-null, but possibly empty list of annotations
+     */
+    public List<PAnnotation> getAnnotationsByName(String annotationName);
+
+    /**
+     * Returns the first annotation with a specified name
+     * 
+     * @since 2.0
+     */
+    public Optional<PAnnotation> getFirstAnnotationByName(String annotationName);
+    
+    /**
+     * Returns the visibility information about the query.
+     * @since 2.0
+     */
+    public PVisibility getVisibility();
+    
+    /**
+     * Returns the non-qualified name of the query. By default this means returning the qualified name after the last
+     * '.' character.
+     * 
+     * @since 2.0
+     */
+    public default String getSimpleName() {
+        return PQueries.calculateSimpleName(getFullyQualifiedName());
+    }
+
+}
\ No newline at end of file
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/queries/PVisibility.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/queries/PVisibility.java
new file mode 100644
index 00000000..7cb312bd
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/queries/PVisibility.java
@@ -0,0 +1,37 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2017, Zoltan Ujhelyi, 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.psystem.queries;
+
+/**
+ * @author Zoltan Ujhelyi
+ * @since 2.0
+ *
+ */
+public enum PVisibility {
+
+    /**
+     * A public (default) visibility means a pattern can be called at any time.
+     */
+    PUBLIC,
+    /**
+     * A private query is not expected to be called directly, only by a different query matcher. 
+     */
+    PRIVATE,
+    /**
+     * A query that is only used inside a single caller query and is not visible outside its container query. Such
+     * patterns must also fulfill the following additional constraints:
+     * 
+     * <ul>
+     * <li>An embedded query must have only a single body.</li>
+     * <li>An embedded query must not be recursice.</li>
+     * </ul>
+     */
+    EMBEDDED
+
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/queries/QueryInitializationException.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/queries/QueryInitializationException.java
new file mode 100644
index 00000000..470d7287
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/queries/QueryInitializationException.java
@@ -0,0 +1,35 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2015, 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.psystem.queries;
+
+import tools.refinery.viatra.runtime.matchers.planning.QueryProcessingException;
+
+/**
+ * Represent an exception that occurred while initializing the specification of a query. 
+ * @author Bergmann Gabor
+ * @since 0.9
+ *
+ */
+public class QueryInitializationException extends QueryProcessingException {
+
+    public QueryInitializationException(String message, String[] context, String shortMessage, Object patternDescription,
+            Throwable cause) {
+        super(message, context, shortMessage, patternDescription, cause);
+    }
+
+    public QueryInitializationException(String message, String[] context, String shortMessage, Object patternDescription) {
+        super(message, context, shortMessage, patternDescription);
+    }
+
+    private static final long serialVersionUID = 9106033062252951489L;
+
+
+    
+    
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/rewriters/AbstractRewriterTraceSource.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/rewriters/AbstractRewriterTraceSource.java
new file mode 100644
index 00000000..276b2b42
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/rewriters/AbstractRewriterTraceSource.java
@@ -0,0 +1,53 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2017, Grill Balázs, IncQueryLabs
+ * 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.psystem.rewriters;
+
+import java.util.Objects;
+
+import tools.refinery.viatra.runtime.matchers.psystem.PConstraint;
+import tools.refinery.viatra.runtime.matchers.psystem.PTraceable;
+
+/**
+ * @since 1.6
+ *
+ */
+public class AbstractRewriterTraceSource {
+
+    private IRewriterTraceCollector traceCollector = NopTraceCollector.INSTANCE;
+    
+    public void setTraceCollector(IRewriterTraceCollector traceCollector) {
+        this.traceCollector = Objects.requireNonNull(traceCollector);
+    }
+    
+    public IPTraceableTraceProvider getTraces() {
+        return traceCollector;
+    }
+    
+    protected IRewriterTraceCollector getTraceCollector() {
+        return traceCollector;
+    }
+    
+    /**
+     * Mark the given derivative to be originated from the given original constraint.
+     * @since 1.6
+     */
+    protected void addTrace(PTraceable original, PTraceable derivative){
+        traceCollector.addTrace(original, derivative);
+    }
+    
+    /**
+     * Indicate that the given derivative is removed from the resulting query, thus its trace
+     * information should be removed also.
+     * @since 1.6
+     */
+    protected void derivativeRemoved(PConstraint derivative, IDerivativeModificationReason reason){
+        traceCollector.derivativeRemoved(derivative, reason);
+    }
+
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/rewriters/ConstraintRemovalReason.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/rewriters/ConstraintRemovalReason.java
new file mode 100644
index 00000000..237a762d
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/rewriters/ConstraintRemovalReason.java
@@ -0,0 +1,23 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2017, Grill Balázs, IncQueryLabs
+ * 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.psystem.rewriters;
+
+/**
+ * Common reasons for removing constraint through rewriters
+ *
+ * @noreference This enum is not intended to be referenced by clients.
+ */
+public enum ConstraintRemovalReason implements IDerivativeModificationReason {
+
+    MOOT_EQUALITY,
+    WEAK_INEQUALITY_SELF_LOOP,
+    TYPE_SUBSUMED,
+    DUPLICATE
+    
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/rewriters/DefaultFlattenCallPredicate.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/rewriters/DefaultFlattenCallPredicate.java
new file mode 100644
index 00000000..3b5d7390
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/rewriters/DefaultFlattenCallPredicate.java
@@ -0,0 +1,23 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2015, Marton Bur, Zoltan Ujhelyi, Akos Horvath, 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.psystem.rewriters;
+import tools.refinery.viatra.runtime.matchers.psystem.basicenumerables.PositivePatternCall;
+
+/**
+ * @author Marton Bur
+ *
+ */
+public class DefaultFlattenCallPredicate implements IFlattenCallPredicate {
+
+    @Override
+    public boolean shouldFlatten(PositivePatternCall positivePatternCall) {
+        return true;
+    }
+
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/rewriters/FlattenerCopier.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/rewriters/FlattenerCopier.java
new file mode 100644
index 00000000..06b8d372
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/rewriters/FlattenerCopier.java
@@ -0,0 +1,129 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2014, Marton Bur, Akos Horvath, 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.psystem.rewriters;
+
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.Map.Entry;
+import java.util.Objects;
+import java.util.Set;
+import java.util.stream.Collectors;
+
+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.basicdeferred.Equality;
+import tools.refinery.viatra.runtime.matchers.psystem.basicdeferred.ExportedParameter;
+import tools.refinery.viatra.runtime.matchers.psystem.basicdeferred.ExpressionEvaluation;
+import tools.refinery.viatra.runtime.matchers.psystem.basicenumerables.PositivePatternCall;
+import tools.refinery.viatra.runtime.matchers.psystem.queries.PQuery;
+import tools.refinery.viatra.runtime.matchers.util.Preconditions;
+
+/**
+ * This rewriter class can add new equality constraints to the copied body
+ * 
+ * @author Marton Bur
+ *
+ */
+class FlattenerCopier extends PBodyCopier {
+
+    private final Map<PositivePatternCall, CallInformation> calls;
+
+    private static class CallInformation {
+        final PBody body;
+        final Map<PVariable, PVariable> variableMapping;
+        
+        private CallInformation(PBody body) {
+            this.body = body;
+            this.variableMapping = new HashMap<>();
+        }
+    }
+    
+    public FlattenerCopier(PQuery query, Map<PositivePatternCall, PBody> callsToFlatten) {
+        super(query);
+        this.calls = callsToFlatten.entrySet().stream().collect(Collectors.toMap(Entry::getKey, entry -> new CallInformation(entry.getValue())));
+    }
+    
+    protected void copyVariable(PositivePatternCall contextPatternCall, PVariable variable, String newName) {
+        PVariable newPVariable = body.getOrCreateVariableByName(newName);
+        calls.get(contextPatternCall).variableMapping.put(variable, newPVariable);
+        variableMapping.put(variable, newPVariable);
+    }
+
+    /**
+     * Merge all variables and constraints from the body called through the given pattern call to a target body. If
+     * multiple bodies are merged into a single one, use the renamer and filter options to avoid collisions.
+     * 
+     * @param sourceBody
+     * @param namingTool
+     * @param filter
+     */
+    public void mergeBody(PositivePatternCall contextPatternCall, IVariableRenamer namingTool,
+            IConstraintFilter filter) {
+
+        PBody sourceBody = calls.get(contextPatternCall).body;
+
+        // Copy variables
+        Set<PVariable> allVariables = sourceBody.getAllVariables();
+        for (PVariable pVariable : allVariables) {
+            if (pVariable.isUnique()) {
+                copyVariable(contextPatternCall, pVariable,
+                        namingTool.createVariableName(pVariable, sourceBody.getPattern()));
+            }
+        }
+
+        // Copy constraints which are not filtered
+        Set<PConstraint> constraints = sourceBody.getConstraints();
+        for (PConstraint pConstraint : constraints) {
+            if (!(pConstraint instanceof ExportedParameter) && !filter.filter(pConstraint)) {
+                copyConstraint(pConstraint);
+            }
+        }
+    }
+
+    @Override
+    protected void copyPositivePatternCallConstraint(PositivePatternCall positivePatternCall) {
+
+        if (!calls.containsKey(positivePatternCall)) {
+            // If the call was not flattened, copy the constraint
+            super.copyPositivePatternCallConstraint(positivePatternCall);
+        } else {
+            PBody calledBody = Objects.requireNonNull(calls.get(positivePatternCall).body);
+            Preconditions.checkArgument(positivePatternCall.getReferredQuery().equals(calledBody.getPattern()));
+
+            List<PVariable> symbolicParameters = calledBody.getSymbolicParameterVariables();
+            Object[] elements = positivePatternCall.getVariablesTuple().getElements();
+            for (int i = 0; i < elements.length; i++) {
+                // Create equality constraints between the caller PositivePatternCall and the corresponding body
+                // parameter variables
+                createEqualityConstraint((PVariable) elements[i], symbolicParameters.get(i), positivePatternCall);
+            }
+
+        }
+    }
+
+    private void createEqualityConstraint(PVariable pVariable1, PVariable pVariable2,
+            PositivePatternCall contextPatternCall) {
+        PVariable who = variableMapping.get(pVariable1);
+        PVariable withWhom = calls.get(contextPatternCall).variableMapping.get(pVariable2);
+        addTrace(contextPatternCall, new Equality(body, who, withWhom));
+    }
+
+    @Override
+    protected void copyExpressionEvaluationConstraint(final ExpressionEvaluation expressionEvaluation) {
+        Map<PVariable, PVariable> variableMapping = this.variableMapping.entrySet().stream()
+                .filter(input -> expressionEvaluation.getPSystem().getAllVariables().contains(input.getKey()))
+                .collect(Collectors.toMap(Entry::getKey, Entry::getValue));
+        
+        PVariable mappedOutputVariable = variableMapping.get(expressionEvaluation.getOutputVariable());
+        addTrace(expressionEvaluation, new ExpressionEvaluation(body, new VariableMappingExpressionEvaluatorWrapper(expressionEvaluation.getEvaluator(), variableMapping), mappedOutputVariable, expressionEvaluation.isUnwinding()));
+    }
+    
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/rewriters/IConstraintFilter.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/rewriters/IConstraintFilter.java
new file mode 100644
index 00000000..518b9c64
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/rewriters/IConstraintFilter.java
@@ -0,0 +1,48 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2015, Zoltan Ujhelyi, Marton Bur, 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.psystem.rewriters;
+
+import tools.refinery.viatra.runtime.matchers.psystem.PConstraint;
+import tools.refinery.viatra.runtime.matchers.psystem.basicdeferred.ExportedParameter;
+
+/**
+ * Helper interface to exclude constraints from PBody copy processes
+ * 
+ * @author Marton Bur
+ * 
+ */
+public interface IConstraintFilter {
+    /**
+     * Returns true, if the given constraint should be filtered (thus should not be copied)
+     * 
+     * @param constraint
+     *            to check
+     * @return true, if the constraint should be filtered
+     */
+    boolean filter(PConstraint constraint);
+    
+    public static class ExportedParameterFilter implements IConstraintFilter {
+        
+        @Override
+        public boolean filter(PConstraint constraint) {
+            return constraint instanceof ExportedParameter;
+        }
+        
+    }
+    
+    public static class AllowAllFilter implements IConstraintFilter {
+        
+        @Override
+        public boolean filter(PConstraint constraint) {
+            // Nothing is filtered
+            return false;
+        }
+        
+    }
+}
\ No newline at end of file
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/rewriters/IDerivativeModificationReason.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/rewriters/IDerivativeModificationReason.java
new file mode 100644
index 00000000..dbd6a78d
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/rewriters/IDerivativeModificationReason.java
@@ -0,0 +1,19 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2017, Grill Balázs, IncQueryLabs
+ * 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.psystem.rewriters;
+
+/**
+ * This is a role indication interface, implementations may provide a reason about
+ * why a modification is made during PQuery normalization.
+ * @since 1.6
+ *
+ */
+public interface IDerivativeModificationReason {
+
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/rewriters/IFlattenCallPredicate.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/rewriters/IFlattenCallPredicate.java
new file mode 100644
index 00000000..7e224e98
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/rewriters/IFlattenCallPredicate.java
@@ -0,0 +1,50 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2015, Marton Bur, Zoltan Ujhelyi, Akos Horvath, 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.psystem.rewriters;
+
+import tools.refinery.viatra.runtime.matchers.psystem.basicenumerables.PositivePatternCall;
+
+
+/**
+ * Interface used by the PQueryFlattener to decide which positive pattern calls to flatten
+ * 
+ * @author Marton Bur
+ *
+ */
+public interface IFlattenCallPredicate {
+    
+    /**
+     * Decides whether the called query by the pattern call should be flattened into the caller or not.
+     * 
+     * @param positivePatternCall
+     *            the pattern call
+     * @return true if the call should be flattened
+     */
+    boolean shouldFlatten(PositivePatternCall positivePatternCall);
+    
+    /**
+     * Flattens only if all operand predicates vote for flattening.
+     * @author Gabor Bergmann
+     * @since 2.1
+     */
+    public static class And implements IFlattenCallPredicate {
+        private IFlattenCallPredicate[] operands;
+        public And(IFlattenCallPredicate... operands) {
+            this.operands = operands;
+        }
+        
+        @Override
+        public boolean shouldFlatten(PositivePatternCall positivePatternCall) {
+            for (IFlattenCallPredicate operand : operands) {
+                if (!operand.shouldFlatten(positivePatternCall)) return false;
+            }
+            return true;
+        }
+    }
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/rewriters/IPTraceableTraceProvider.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/rewriters/IPTraceableTraceProvider.java
new file mode 100644
index 00000000..84da4d1b
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/rewriters/IPTraceableTraceProvider.java
@@ -0,0 +1,55 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2017, Grill Balázs, IncQueryLabs
+ * 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.psystem.rewriters;
+
+import java.util.stream.Stream;
+
+import tools.refinery.viatra.runtime.matchers.psystem.PTraceable;
+import tools.refinery.viatra.runtime.matchers.psystem.queries.PQuery;
+
+/**
+ * This interface provides methods to trace the {@link PTraceable}s of a transformed {@link PQuery} produced by
+ * a {@link PDisjunctionRewriter}. In case the associated rewriter is a composite (a.k.a. {@link PDisjunctionRewriterCacher}),
+ * this trace provider handles traces end-to-end, hiding all the intermediate transformation steps.
+ * 
+ * @since 1.6
+ * @noimplement This interface is not intended to be implemented by clients.
+ */
+public interface IPTraceableTraceProvider {
+
+    /**
+     * Find and return the canonical {@link PTraceable}s in the original query which are the sources of the given derivative
+     * {@link PTraceable} according to the transformation.
+     * 
+     * @param derivative a {@link PTraceable} which is contained by the {@link PQuery} produced by the associated rewriter
+     * @since 2.0
+     */
+    public Stream<PTraceable> getCanonicalTraceables(PTraceable derivative);
+    
+    /**
+     * Find and return the {@link PTraceable}s in the rewritten query which are the destinations of the given source
+     * {@link PTraceable} according to the transformation.
+     * 
+     * @param source a {@link PTraceable} which is contained by a {@link PQuery} before rewriting
+     * @since 2.0
+     */
+    public Stream<PTraceable> getRewrittenTraceables(PTraceable source);
+    
+    /**
+     * Returns whether the given traceable element has been removed by every rewriter for a reason.
+     */
+    public boolean isRemoved(PTraceable traceable);
+
+    /**
+     * Returns the reasons for which the traceable element has been removed by the rewriters.
+     * @return the reasons of removal during rewriting
+     * @since 2.0
+     */
+    public Stream<IDerivativeModificationReason> getRemovalReasons(PTraceable traceable);
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/rewriters/IRewriterTraceCollector.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/rewriters/IRewriterTraceCollector.java
new file mode 100644
index 00000000..70771ea7
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/rewriters/IRewriterTraceCollector.java
@@ -0,0 +1,33 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2017, Grill Balázs, IncQueryLabs
+ * 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.psystem.rewriters;
+
+import tools.refinery.viatra.runtime.matchers.psystem.PTraceable;
+
+/**
+ * This is the internal API of {@link IPTraceableTraceProvider} expected to be used by
+ * copier and rewriter implementations.
+ * 
+ * @since 1.6
+ * @noreference This interface is not intended to be referenced by clients.
+ */
+public interface IRewriterTraceCollector extends IPTraceableTraceProvider {
+
+    /**
+     * Mark the given derivative to be originated from the given original constraint.
+     */
+    public void addTrace(PTraceable origin, PTraceable derivative);
+    
+    /**
+     * Indicate that the given derivative is removed from the resulting query, thus its trace
+     * information should be removed also.
+     */
+    public void derivativeRemoved(PTraceable derivative, IDerivativeModificationReason reason);
+    
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/rewriters/IVariableRenamer.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/rewriters/IVariableRenamer.java
new file mode 100644
index 00000000..ce446e0d
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/rewriters/IVariableRenamer.java
@@ -0,0 +1,59 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2015, Zoltan Ujhelyi, Marton Bur, 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.psystem.rewriters;
+
+import tools.refinery.viatra.runtime.matchers.psystem.PVariable;
+import tools.refinery.viatra.runtime.matchers.psystem.queries.PQuery;
+
+/**
+ * Helper interface to ease the naming of the new variables during flattening
+ * 
+ * @author Marton Bur
+ * 
+ */
+public interface IVariableRenamer {
+    /**
+     * Creates a variable name based on a given variable and a given query. It only creates a String, doesn't set
+     * anything.
+     * 
+     * @param pVariable
+     * @param query
+     * @return the new variable name as a String
+     */
+    String createVariableName(PVariable pVariable, PQuery query);
+    
+    public class SameName implements IVariableRenamer {
+        @Override
+        public String createVariableName(PVariable pVariable, PQuery query) {
+            return pVariable.getName();
+        }
+    }
+    
+    public class HierarchicalName implements IVariableRenamer {
+
+        private int callCount;
+
+        public void setCallCount(int callCount) {
+            this.callCount = callCount;
+        }
+
+        @Override
+        public String createVariableName(PVariable pVariable, PQuery query) {
+            // make sure to keep the "_" prefix before anonymous variables
+            String newVarName = getShortName(query) + "<" + callCount + ">" + "_" + pVariable.getName();
+            return pVariable.getName().startsWith("_") ? "_" + newVarName : newVarName ;
+        }
+        
+        private String getShortName(PQuery query) {
+            String fullyQualifiedName = query.getFullyQualifiedName();
+            int beginIndex = fullyQualifiedName.lastIndexOf('.') + 1;
+            return fullyQualifiedName.substring(beginIndex);
+        }
+    }
+}
\ No newline at end of file
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/rewriters/MappingTraceCollector.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/rewriters/MappingTraceCollector.java
new file mode 100644
index 00000000..7429fc60
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/rewriters/MappingTraceCollector.java
@@ -0,0 +1,135 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2017, Grill Balázs, IncQueryLabs
+ * 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.psystem.rewriters;
+
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.LinkedList;
+import java.util.Map;
+import java.util.Queue;
+import java.util.Set;
+import java.util.function.Predicate;
+import java.util.stream.Stream;
+
+import tools.refinery.viatra.runtime.matchers.psystem.PTraceable;
+import tools.refinery.viatra.runtime.matchers.psystem.queries.PQuery;
+import tools.refinery.viatra.runtime.matchers.util.CollectionsFactory;
+import tools.refinery.viatra.runtime.matchers.util.CollectionsFactory.MemoryType;
+import tools.refinery.viatra.runtime.matchers.util.IMemoryView;
+import tools.refinery.viatra.runtime.matchers.util.IMultiLookup;
+import tools.refinery.viatra.runtime.matchers.util.Preconditions;
+
+/**
+ * Multimap-based implementation to contain and query traces
+ * 
+ * @since 1.6
+ *
+ */
+public class MappingTraceCollector implements IRewriterTraceCollector {
+
+    /**
+     * Traces from derivative to original
+     */
+    private final IMultiLookup<PTraceable, PTraceable> traces = CollectionsFactory.createMultiLookup(Object.class, MemoryType.SETS, Object.class);
+
+    /**
+     * Traces from original to derivative
+     */
+    private final IMultiLookup<PTraceable, PTraceable> inverseTraces = CollectionsFactory.createMultiLookup(Object.class, MemoryType.SETS, Object.class);
+    
+    /**
+     * Reasons for removing {@link PTraceable}s
+     */
+    private final Map<PTraceable, IDerivativeModificationReason> removals = new HashMap<>();
+    
+    /**
+     * Decides whether {@link PTraceable} is removed
+     */
+    private final Predicate<PTraceable> removed = removals::containsKey;
+
+    /**
+     * @since 2.0
+     */
+    @Override
+    public Stream<PTraceable> getCanonicalTraceables(PTraceable derivative) {
+        return findTraceEnds(derivative, traces).stream();
+    }
+
+    /**
+     * @since 2.0
+     */
+    @Override
+    public Stream<PTraceable> getRewrittenTraceables(PTraceable source) {
+        return findTraceEnds(source, inverseTraces).stream();
+    }
+
+    /**
+     * Returns the end of trace chains starting from the given {@link PTraceable} along the given trace edges. 
+     */
+    private Set<PTraceable> findTraceEnds(PTraceable traceable, IMultiLookup<PTraceable, PTraceable> traceRecords) {
+        if (traceable instanceof PQuery) { // PQueries are preserved
+            return Collections.singleton(traceable);
+        }
+        Set<PTraceable> visited = new HashSet<>();
+        Set<PTraceable> result = new HashSet<>();
+        Queue<PTraceable> queue = new LinkedList<>();
+        queue.add(traceable);
+        while(!queue.isEmpty()){
+            PTraceable aDerivative = queue.poll();
+            // Track visited elements to avoid infinite loop via directed cycles in traces
+            visited.add(aDerivative);
+            IMemoryView<PTraceable> nextOrigins = traceRecords.lookup(aDerivative);
+            if (nextOrigins == null){
+                // End of trace chain
+                result.add(aDerivative);
+            } else {
+                // Follow traces
+                for(PTraceable nextOrigin : nextOrigins){
+                    if (!visited.contains(nextOrigin)){
+                        queue.add(nextOrigin);
+                    }
+                }
+            }
+        }
+        return result;
+    }
+
+    @Override
+    public void addTrace(PTraceable original, PTraceable derivative){
+        traces.addPairOrNop(derivative, original);
+        inverseTraces.addPairOrNop(original, derivative);
+        // Even if this element was marked as removed earlier, now we replace it with another constraint!
+        removals.remove(original);
+    }
+    
+    @Override
+    public void derivativeRemoved(PTraceable derivative, IDerivativeModificationReason reason){
+        Preconditions.checkState(!removals.containsKey(derivative), "Traceable %s removed multiple times", derivative);
+        // XXX the derivative must not be removed from the trace chain, as some rewriters, e.g. the normalizer keeps trace links to deleted elements 
+        if (!inverseTraces.lookupExists(derivative)) {
+            // If there already exists a trace link, this removal means an update
+            removals.put(derivative, reason);
+        }
+    }
+
+    @Override
+    public boolean isRemoved(PTraceable traceable) {
+        return getRewrittenTraceables(traceable).allMatch(removed);
+    }
+
+    /**
+     * @since 2.0
+     */
+    @Override
+    public Stream<IDerivativeModificationReason> getRemovalReasons(PTraceable traceable) {
+        return getRewrittenTraceables(traceable).filter(removed).map(removals::get);
+    }
+
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/rewriters/NeverFlattenCallPredicate.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/rewriters/NeverFlattenCallPredicate.java
new file mode 100644
index 00000000..96c0b205
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/rewriters/NeverFlattenCallPredicate.java
@@ -0,0 +1,26 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2016, Grill Balázs, 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.psystem.rewriters;
+
+import tools.refinery.viatra.runtime.matchers.psystem.basicenumerables.PositivePatternCall;
+
+/**
+ * @author Grill Balázs
+ * @since 1.4
+ *
+ */
+public class NeverFlattenCallPredicate implements IFlattenCallPredicate {
+
+
+    @Override
+    public boolean shouldFlatten(PositivePatternCall positivePatternCall) {
+        return false;
+    }
+
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/rewriters/NopTraceCollector.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/rewriters/NopTraceCollector.java
new file mode 100644
index 00000000..15cf577e
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/rewriters/NopTraceCollector.java
@@ -0,0 +1,68 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2017, Grill Balázs, IncQueryLabs
+ * 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.psystem.rewriters;
+
+import java.util.stream.Stream;
+
+import tools.refinery.viatra.runtime.matchers.psystem.PTraceable;
+
+/**
+ * This implementation does not store any traces and scales to NOP for every traceability feature.
+ * @since 1.6
+ *
+ */
+public class NopTraceCollector implements IRewriterTraceCollector {
+
+    public static final IRewriterTraceCollector INSTANCE = new NopTraceCollector();
+    
+    private NopTraceCollector() {
+        // Private constructor to force using the common instance
+    }
+    
+    /**
+     * @since 2.0
+     */
+    @Override
+    public Stream<PTraceable> getCanonicalTraceables(PTraceable derivative) {
+        return Stream.empty();
+    }
+
+    /**
+     * @since 2.0
+     */
+    @Override
+    public Stream<PTraceable> getRewrittenTraceables(PTraceable source) {
+        return Stream.empty();
+    }
+
+
+    @Override
+    public void addTrace(PTraceable origin, PTraceable derivative) {
+        // ignored
+    }
+
+    @Override
+    public void derivativeRemoved(PTraceable derivative, IDerivativeModificationReason reason) {
+        // ignored
+    }
+
+    @Override
+    public boolean isRemoved(PTraceable traceable) {
+        return false;
+    }
+
+    /**
+     * @since 2.0
+     */
+    @Override
+    public Stream<IDerivativeModificationReason> getRemovalReasons(PTraceable traceable) {
+        return Stream.empty();
+    }
+
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/rewriters/PBodyCopier.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/rewriters/PBodyCopier.java
new file mode 100644
index 00000000..10ab19c8
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/rewriters/PBodyCopier.java
@@ -0,0 +1,307 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2014, Marton Bur, Akos Horvath, Zoltan Ujhelyi, Istvan Rath and Daniel Varro
+ * Copyright (c) 2023 The Refinery Authors <https://refinery.tools>
+ * 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.psystem.rewriters;
+
+import tools.refinery.viatra.runtime.matchers.planning.QueryProcessingException;
+import tools.refinery.viatra.runtime.matchers.psystem.EnumerablePConstraint;
+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.basicdeferred.*;
+import tools.refinery.viatra.runtime.matchers.psystem.basicenumerables.*;
+import tools.refinery.viatra.runtime.matchers.psystem.queries.PParameter;
+import tools.refinery.viatra.runtime.matchers.psystem.queries.PQuery;
+import tools.refinery.viatra.runtime.matchers.psystem.rewriters.IConstraintFilter.AllowAllFilter;
+import tools.refinery.viatra.runtime.matchers.psystem.rewriters.IVariableRenamer.SameName;
+import tools.refinery.viatra.runtime.matchers.tuple.Tuple;
+import tools.refinery.viatra.runtime.matchers.tuple.Tuples;
+
+import java.util.*;
+import java.util.stream.Collectors;
+
+/**
+ * This class can create a new PBody for a PQuery. The result body contains a copy of given variables and constraints.
+ *
+ * @author Marton Bur
+ *
+ */
+public class PBodyCopier extends AbstractRewriterTraceSource {
+
+    /**
+     * The created body
+     */
+    protected PBody body;
+    /**
+     * Mapping between the original and the copied variables
+     */
+    protected Map<PVariable, PVariable> variableMapping = new HashMap<>();
+
+    public Map<PVariable, PVariable> getVariableMapping() {
+        return variableMapping;
+    }
+
+    /**
+     * @since 1.6
+     */
+    public PBodyCopier(PBody body, IRewriterTraceCollector traceCollector) {
+        this.body = new PBody(body.getPattern());
+        setTraceCollector(traceCollector);
+
+        // do the actual copying
+        mergeBody(body);
+    }
+
+    /**
+     * @since 1.6
+     */
+    public PBodyCopier(PQuery query) {
+        this.body = new PBody(query);
+    }
+
+    public void mergeBody(PBody sourceBody) {
+        mergeBody(sourceBody, new SameName(), new AllowAllFilter());
+    }
+
+    /**
+     * Merge all variables and constraints from a source body to a target body. If multiple bodies are merged into a
+     * single one, use the renamer and filter options to avoid collisions.
+     */
+    public void mergeBody(PBody sourceBody, IVariableRenamer namingTool, IConstraintFilter filter) {
+
+        // Copy variables
+        Set<PVariable> allVariables = sourceBody.getAllVariables();
+        for (PVariable pVariable : allVariables) {
+            if (pVariable.isUnique()) {
+                copyVariable(pVariable, namingTool.createVariableName(pVariable, sourceBody.getPattern()));
+            }
+        }
+
+        // Copy exported parameters
+        this.body.setSymbolicParameters(sourceBody.getSymbolicParameters().stream()
+                .map(this::copyExportedParameterConstraint).collect(Collectors.toList()));
+
+        // Copy constraints which are not filtered
+        Set<PConstraint> constraints = sourceBody.getConstraints();
+        for (PConstraint pConstraint : constraints) {
+            if (!(pConstraint instanceof ExportedParameter) && !filter.filter(pConstraint)) {
+                copyConstraint(pConstraint);
+            }
+        }
+
+        // Add trace between original and copied body
+        addTrace(sourceBody, body);
+    }
+
+    protected void copyVariable(PVariable variable, String newName) {
+        PVariable newPVariable = body.getOrCreateVariableByName(newName);
+        variableMapping.put(variable, newPVariable);
+    }
+
+    /**
+     * Returns the body with the copied variables and constraints. The returned body is still uninitialized.
+     */
+    public PBody getCopiedBody() {
+        return body;
+    }
+
+    protected void copyConstraint(PConstraint constraint) {
+        if (constraint instanceof ExportedParameter) {
+            copyExportedParameterConstraint((ExportedParameter) constraint);
+        } else if (constraint instanceof Equality) {
+            copyEqualityConstraint((Equality) constraint);
+        } else if (constraint instanceof Inequality) {
+            copyInequalityConstraint((Inequality) constraint);
+        } else if (constraint instanceof TypeConstraint) {
+            copyTypeConstraint((TypeConstraint) constraint);
+        } else if (constraint instanceof TypeFilterConstraint) {
+            copyTypeFilterConstraint((TypeFilterConstraint) constraint);
+        } else if (constraint instanceof ConstantValue) {
+            copyConstantValueConstraint((ConstantValue) constraint);
+        } else if (constraint instanceof PositivePatternCall) {
+            copyPositivePatternCallConstraint((PositivePatternCall) constraint);
+        } else if (constraint instanceof NegativePatternCall) {
+            copyNegativePatternCallConstraint((NegativePatternCall) constraint);
+        } else if (constraint instanceof BinaryTransitiveClosure) {
+            copyBinaryTransitiveClosureConstraint((BinaryTransitiveClosure) constraint);
+                } else if (constraint instanceof RepresentativeElectionConstraint) {
+                        copyRepresentativeElectionConstraint((RepresentativeElectionConstraint) constraint);
+        } else if (constraint instanceof RelationEvaluation) {
+            copyRelationEvaluationConstraint((RelationEvaluation) constraint);
+        } else if (constraint instanceof BinaryReflexiveTransitiveClosure) {
+            copyBinaryReflexiveTransitiveClosureConstraint((BinaryReflexiveTransitiveClosure) constraint);
+        } else if (constraint instanceof PatternMatchCounter) {
+            copyPatternMatchCounterConstraint((PatternMatchCounter) constraint);
+        } else if (constraint instanceof AggregatorConstraint) {
+            copyAggregatorConstraint((AggregatorConstraint) constraint);
+        } else if (constraint instanceof ExpressionEvaluation) {
+            copyExpressionEvaluationConstraint((ExpressionEvaluation) constraint);
+        } else {
+            throw new QueryProcessingException("Unknown PConstraint {0} encountered while copying PBody",
+                    new String[] { constraint.getClass().getName() }, "Unknown PConstraint", body.getPattern());
+        }
+    }
+
+    protected ExportedParameter copyExportedParameterConstraint(ExportedParameter exportedParameter) {
+        PVariable mappedPVariable = variableMapping.get(exportedParameter.getParameterVariable());
+        PParameter parameter = exportedParameter.getPatternParameter();
+        ExportedParameter newExportedParameter;
+        newExportedParameter = new ExportedParameter(body, mappedPVariable, parameter);
+        body.getSymbolicParameters().add(newExportedParameter);
+        addTrace(exportedParameter, newExportedParameter);
+        return newExportedParameter;
+    }
+
+    protected void copyEqualityConstraint(Equality equality) {
+        PVariable who = equality.getWho();
+        PVariable withWhom = equality.getWithWhom();
+        addTrace(equality, new Equality(body, variableMapping.get(who), variableMapping.get(withWhom)));
+    }
+
+    protected void copyInequalityConstraint(Inequality inequality) {
+        PVariable who = inequality.getWho();
+        PVariable withWhom = inequality.getWithWhom();
+        addTrace(inequality, new Inequality(body, variableMapping.get(who), variableMapping.get(withWhom)));
+    }
+
+    protected void copyTypeConstraint(TypeConstraint typeConstraint) {
+        PVariable[] mappedVariables = extractMappedVariables(typeConstraint);
+        Tuple variablesTuple = Tuples.flatTupleOf((Object[]) mappedVariables);
+        addTrace(typeConstraint, new TypeConstraint(body, variablesTuple, typeConstraint.getSupplierKey()));
+    }
+
+    protected void copyTypeFilterConstraint(TypeFilterConstraint typeConstraint) {
+        PVariable[] mappedVariables = extractMappedVariables(typeConstraint);
+        Tuple variablesTuple = Tuples.flatTupleOf((Object[]) mappedVariables);
+        addTrace(typeConstraint, new TypeFilterConstraint(body, variablesTuple, typeConstraint.getInputKey()));
+    }
+
+    protected void copyConstantValueConstraint(ConstantValue constantValue) {
+        PVariable pVariable = (PVariable) constantValue.getVariablesTuple().getElements()[0];
+        addTrace(constantValue,
+                new ConstantValue(body, variableMapping.get(pVariable), constantValue.getSupplierKey()));
+    }
+
+    protected void copyPositivePatternCallConstraint(PositivePatternCall positivePatternCall) {
+        PVariable[] mappedVariables = extractMappedVariables(positivePatternCall);
+        Tuple variablesTuple = Tuples.flatTupleOf((Object[]) mappedVariables);
+        addTrace(positivePatternCall,
+                new PositivePatternCall(body, variablesTuple, positivePatternCall.getReferredQuery()));
+    }
+
+    protected void copyNegativePatternCallConstraint(NegativePatternCall negativePatternCall) {
+        PVariable[] mappedVariables = extractMappedVariables(negativePatternCall);
+        Tuple variablesTuple = Tuples.flatTupleOf((Object[]) mappedVariables);
+        addTrace(negativePatternCall,
+                new NegativePatternCall(body, variablesTuple, negativePatternCall.getReferredQuery()));
+    }
+
+    protected void copyBinaryTransitiveClosureConstraint(BinaryTransitiveClosure binaryTransitiveClosure) {
+        PVariable[] mappedVariables = extractMappedVariables(binaryTransitiveClosure);
+        Tuple variablesTuple = Tuples.flatTupleOf((Object[]) mappedVariables);
+        addTrace(binaryTransitiveClosure,
+                new BinaryTransitiveClosure(body, variablesTuple, binaryTransitiveClosure.getReferredQuery()));
+    }
+
+        protected void copyRepresentativeElectionConstraint(RepresentativeElectionConstraint constraint) {
+                var mappedVariables = extractMappedVariables(constraint);
+                var variablesTuple = Tuples.flatTupleOf((Object[]) mappedVariables);
+                addTrace(constraint, new RepresentativeElectionConstraint(body, variablesTuple, constraint.getReferredQuery(),
+                                constraint.getConnectivity()));
+        }
+
+    /**
+     * @since 2.8
+     */
+    protected void copyRelationEvaluationConstraint(RelationEvaluation relationEvaluation) {
+        PVariable[] mappedVariables = extractMappedVariables(relationEvaluation);
+        Tuple variablesTuple = Tuples.flatTupleOf((Object[]) mappedVariables);
+        addTrace(relationEvaluation, new RelationEvaluation(body, variablesTuple, relationEvaluation.getReferredQueries(),
+                relationEvaluation.getEvaluator()));
+    }
+
+    /**
+     * @since 2.0
+     */
+    protected void copyBinaryReflexiveTransitiveClosureConstraint(
+            BinaryReflexiveTransitiveClosure binaryReflexiveTransitiveClosure) {
+        PVariable[] mappedVariables = extractMappedVariables(binaryReflexiveTransitiveClosure);
+        Tuple variablesTuple = Tuples.flatTupleOf((Object[]) mappedVariables);
+        addTrace(binaryReflexiveTransitiveClosure,
+                new BinaryReflexiveTransitiveClosure(body, variablesTuple,
+                        binaryReflexiveTransitiveClosure.getReferredQuery(),
+                        binaryReflexiveTransitiveClosure.getUniverseType()));
+    }
+
+    protected void copyPatternMatchCounterConstraint(PatternMatchCounter patternMatchCounter) {
+        PVariable[] mappedVariables = extractMappedVariables(patternMatchCounter);
+        PVariable mappedResultVariable = variableMapping.get(patternMatchCounter.getResultVariable());
+        Tuple variablesTuple = Tuples.flatTupleOf((Object[]) mappedVariables);
+        addTrace(patternMatchCounter, new PatternMatchCounter(body, variablesTuple,
+                patternMatchCounter.getReferredQuery(), mappedResultVariable));
+    }
+
+    /**
+     * @since 1.4
+     */
+    protected void copyAggregatorConstraint(AggregatorConstraint constraint) {
+        PVariable[] mappedVariables = extractMappedVariables(constraint);
+        PVariable mappedResultVariable = variableMapping.get(constraint.getResultVariable());
+        Tuple variablesTuple = Tuples.flatTupleOf((Object[]) mappedVariables);
+        addTrace(constraint, new AggregatorConstraint(constraint.getAggregator(), body, variablesTuple,
+                constraint.getReferredQuery(), mappedResultVariable, constraint.getAggregatedColumn()));
+    }
+
+    protected void copyExpressionEvaluationConstraint(ExpressionEvaluation expressionEvaluation) {
+        PVariable mappedOutputVariable = variableMapping.get(expressionEvaluation.getOutputVariable());
+        addTrace(expressionEvaluation, new ExpressionEvaluation(body,
+                new VariableMappingExpressionEvaluatorWrapper(expressionEvaluation.getEvaluator(), variableMapping),
+                mappedOutputVariable, expressionEvaluation.isUnwinding()));
+    }
+
+    /**
+     * For positive pattern calls
+     *
+     * @param positivePatternCall
+     * @return the mapped variables to the pattern's parameters
+     */
+    protected PVariable[] extractMappedVariables(EnumerablePConstraint enumerablePConstraint) {
+        Object[] pVariables = enumerablePConstraint.getVariablesTuple().getElements();
+        return mapVariableList(pVariables);
+    }
+
+    /**
+     * For negative and count pattern calls.
+     *
+     * @param patternMatchCounter
+     * @return the mapped variables to the pattern's parameters
+     */
+    private PVariable[] extractMappedVariables(PatternCallBasedDeferred patternCallBasedDeferred) {
+        Object[] pVariables = patternCallBasedDeferred.getActualParametersTuple().getElements();
+        return mapVariableList(pVariables);
+    }
+
+    /**
+     * For type filters.
+     */
+    private PVariable[] extractMappedVariables(TypeFilterConstraint typeFilterConstraint) {
+        Object[] pVariables = typeFilterConstraint.getVariablesTuple().getElements();
+        return mapVariableList(pVariables);
+    }
+
+    private PVariable[] mapVariableList(Object[] pVariables) {
+        List<PVariable> list = new ArrayList<PVariable>();
+        for (int i = 0; i < pVariables.length; i++) {
+            PVariable mappedVariable = variableMapping.get(pVariables[i]);
+            list.add(mappedVariable);
+        }
+        return list.toArray(new PVariable[0]);
+    }
+
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/rewriters/PBodyNormalizer.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/rewriters/PBodyNormalizer.java
new file mode 100644
index 00000000..90943129
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/rewriters/PBodyNormalizer.java
@@ -0,0 +1,310 @@
+/*******************************************************************************
+ * 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.psystem.rewriters;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.LinkedHashSet;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Map;
+import java.util.Queue;
+import java.util.Set;
+
+import tools.refinery.viatra.runtime.matchers.context.IInputKey;
+import tools.refinery.viatra.runtime.matchers.context.IQueryMetaContext;
+import tools.refinery.viatra.runtime.matchers.planning.QueryProcessingException;
+import tools.refinery.viatra.runtime.matchers.planning.helpers.TypeHelper;
+import tools.refinery.viatra.runtime.matchers.psystem.ITypeConstraint;
+import tools.refinery.viatra.runtime.matchers.psystem.ITypeInfoProviderConstraint;
+import tools.refinery.viatra.runtime.matchers.psystem.PBody;
+import tools.refinery.viatra.runtime.matchers.psystem.PConstraint;
+import tools.refinery.viatra.runtime.matchers.psystem.TypeJudgement;
+import tools.refinery.viatra.runtime.matchers.psystem.basicdeferred.Equality;
+import tools.refinery.viatra.runtime.matchers.psystem.basicdeferred.Inequality;
+import tools.refinery.viatra.runtime.matchers.psystem.queries.PDisjunction;
+import tools.refinery.viatra.runtime.matchers.psystem.queries.PQuery;
+import tools.refinery.viatra.runtime.matchers.psystem.queries.PQuery.PQueryStatus;
+import tools.refinery.viatra.runtime.matchers.util.CollectionsFactory;
+
+/**
+ * A disjunction rewriter for creating a normalized form of specification, unifying variables and running basic sanity
+ * checks. This rewriter does not copy but modifies directly the original specification, requiring a mutable
+ * disjunction.
+ * 
+ * @author Gabor Bergmann
+ * 
+ */
+public class PBodyNormalizer extends PDisjunctionRewriter {
+
+    private IQueryMetaContext context;
+
+    public PBodyNormalizer(IQueryMetaContext context) {
+        this.context = context;
+    }
+
+    /**
+     * Returns whether unary constraint elimination is enabled. This behavior can be customized by creating a subclass
+     * with a custom implementation.
+     * 
+     * @since 1.6
+     */
+    protected boolean shouldCalculateImpliedTypes(PQuery query) {
+        return true;
+    }
+
+    /**
+     * Returns whether 'weakened alternative' suggestions of the context shall be expanded as additional PConstraints. 
+     * This behavior can be customized by creating a subclass
+     * with a custom implementation.
+     * 
+     * @since 1.6
+     */
+    protected boolean shouldExpandWeakenedAlternatives(PQuery query) {
+        return false;
+    }
+
+    @Override
+    public PDisjunction rewrite(PDisjunction disjunction) {
+        Set<PBody> normalizedBodies = new LinkedHashSet<>();
+        for (PBody body : disjunction.getBodies()) {
+            PBodyCopier copier = new PBodyCopier(body, getTraceCollector());
+            PBody modifiedBody = copier.getCopiedBody();
+            normalizeBody(modifiedBody);
+            normalizedBodies.add(modifiedBody);
+            modifiedBody.setStatus(PQueryStatus.OK);
+        }
+        return new PDisjunction(normalizedBodies);
+    }
+
+    public void setContext(IQueryMetaContext context) {
+        this.context = context;
+    }
+
+    /**
+     * Provides a normalized version of the pattern body. May return a different version than the original version if
+     * needed.
+     * 
+     * @param body
+     */
+    public PBody normalizeBody(PBody body) {
+        try {
+            return normalizeBodyInternal(body);
+        } catch (QueryProcessingException e) {
+            throw new RewriterException("Error during rewriting: {1}", new String[] { e.getMessage() },
+                    e.getShortMessage(), body.getPattern(), e);
+        }
+    }
+
+    PBody normalizeBodyInternal(PBody body) {
+        // UNIFICATION AND WEAK INEQUALITY ELIMINATION
+        unifyVariablesAlongEqualities(body);
+        eliminateWeakInequalities(body);
+        removeMootEqualities(body);
+
+        // ADDING WEAKENED ALTERNATIVES
+        if (shouldExpandWeakenedAlternatives(body.getPattern())) {
+            expandWeakenedAlternativeConstraints(body);
+        }
+        
+        // CONSTRAINT ELIMINATION WITH TYPE INFERENCE
+        if (shouldCalculateImpliedTypes(body.getPattern())) {
+            eliminateInferrableTypes(body, context);
+        } else {
+            // ELIMINATE DUPLICATE TYPE CONSTRAINTS
+            eliminateDuplicateTypeConstraints(body);
+        }
+
+        
+        // PREVENTIVE CHECKS
+        checkSanity(body);
+        return body;
+    }
+    
+    private void removeMootEqualities(PBody body) {
+        Set<Equality> equals = body.getConstraintsOfType(Equality.class);
+        for (Equality equality : equals) {
+            if (equality.isMoot()) {
+                equality.delete();
+                derivativeRemoved(equality, ConstraintRemovalReason.MOOT_EQUALITY);
+            }
+        }
+    }
+
+    /**
+     * Unifies allVariables along equalities so that they can be handled as one.
+     * 
+     * @param body
+     */
+    void unifyVariablesAlongEqualities(PBody body) {
+        Set<Equality> equals = body.getConstraintsOfType(Equality.class);
+        for (Equality equality : equals) {
+            if (!equality.isMoot()) {
+                equality.getWho().unifyInto(equality.getWithWhom());
+            }
+        }
+    }
+
+    /**
+     * Eliminates weak inequalities if they are not substantiated.
+     * 
+     * @param body
+     */
+    void eliminateWeakInequalities(PBody body) {
+        for (Inequality inequality : body.getConstraintsOfType(Inequality.class)){
+            if (inequality.isEliminable()){
+                inequality.eliminateWeak();
+                derivativeRemoved(inequality, ConstraintRemovalReason.WEAK_INEQUALITY_SELF_LOOP);
+            }
+        }
+    }
+
+    /**
+     * Eliminates all type constraints that are inferrable from other constraints.
+     */
+    void eliminateInferrableTypes(final PBody body, IQueryMetaContext context) {
+        Set<TypeJudgement> subsumedByRetainedConstraints = new HashSet<TypeJudgement>();
+        LinkedList<ITypeConstraint> allTypeConstraints = new LinkedList<ITypeConstraint>();
+        for (PConstraint pConstraint : body.getConstraints()) {
+            if (pConstraint instanceof ITypeConstraint) {
+                allTypeConstraints.add((ITypeConstraint) pConstraint);
+            } else if (pConstraint instanceof ITypeInfoProviderConstraint) {
+                // non-type constraints are all retained
+                final Set<TypeJudgement> directJudgements = ((ITypeInfoProviderConstraint) pConstraint)
+                        .getImpliedJudgements(context);
+                subsumedByRetainedConstraints = TypeHelper.typeClosure(subsumedByRetainedConstraints, directJudgements,
+                        context);
+            }
+        }
+        Comparator<ITypeConstraint> eliminationOrder = (o1, o2) -> {
+            IInputKey type1 = o1.getEquivalentJudgement().getInputKey();
+            IInputKey type2 = o2.getEquivalentJudgement().getInputKey();
+            
+            int result = context.getSuggestedEliminationOrdering().compare(type1, type2);
+            return (result == 0) 
+                    ? PConstraint.COMPARE_BY_MONOTONOUS_ID.compare(o1, o2) 
+                    : result;
+        }; 
+                
+        Collections.sort(allTypeConstraints, eliminationOrder);
+        Queue<ITypeConstraint> potentialConstraints = allTypeConstraints; // rename for better comprehension
+
+        while (!potentialConstraints.isEmpty()) {
+            ITypeConstraint candidate = potentialConstraints.poll();
+
+            boolean isSubsumed = subsumedByRetainedConstraints.contains(candidate.getEquivalentJudgement());
+            if (!isSubsumed) {
+                Set<TypeJudgement> typeClosure = subsumedByRetainedConstraints;
+                for (ITypeConstraint subsuming : potentialConstraints) { // the remaining ones
+                    final Set<TypeJudgement> directJudgements = subsuming.getImpliedJudgements(context);
+                    typeClosure = TypeHelper.typeClosure(typeClosure, directJudgements, context);
+
+                    if (typeClosure.contains(candidate.getEquivalentJudgement())) {
+                        isSubsumed = true;
+                        break;
+                    }
+                }
+            }
+            if (isSubsumed) { // eliminated
+                candidate.delete();
+                derivativeRemoved(candidate, ConstraintRemovalReason.TYPE_SUBSUMED);
+            } else { // retained
+                subsumedByRetainedConstraints = TypeHelper.typeClosure(subsumedByRetainedConstraints,
+                        candidate.getImpliedJudgements(context), context);
+            }
+        }
+    }
+
+    /**
+     * Inserts "weakened alternative" constraints suggested by the meta context that aid in coming up with a query plan.
+     */
+    void expandWeakenedAlternativeConstraints(PBody body) {
+        Set<TypeJudgement> allJudgements = new HashSet<TypeJudgement>();
+        Set<TypeJudgement> newJudgementsToAdd = new HashSet<TypeJudgement>();
+        Queue<TypeJudgement> judgementsToProcess = new LinkedList<TypeJudgement>();
+        Map<TypeJudgement, List<PConstraint>> traceability = CollectionsFactory.createMap();
+        
+        for (ITypeConstraint typeConstraint : body.getConstraintsOfType(ITypeConstraint.class)) {
+            TypeJudgement equivalentJudgement = typeConstraint.getEquivalentJudgement();
+            judgementsToProcess.add(equivalentJudgement);
+            allJudgements.add(equivalentJudgement);
+            traceability.computeIfAbsent(equivalentJudgement, k-> new ArrayList<>()).add(typeConstraint);
+        }
+        
+        while (!judgementsToProcess.isEmpty()) {
+            TypeJudgement judgement = judgementsToProcess.poll();
+            for (TypeJudgement alternativeJudgement : judgement.getWeakenedAlternativeJudgements(context)) {
+                if (allJudgements.add(alternativeJudgement)) {
+                    newJudgementsToAdd.add(alternativeJudgement);
+                    judgementsToProcess.add(alternativeJudgement);
+                    traceability.merge(
+                            alternativeJudgement, 
+                            traceability.getOrDefault(judgement, new ArrayList<>()),
+                            (old,further) -> {old.addAll(further); return old;}
+                    );
+                }
+            }
+        }
+        
+        for (TypeJudgement typeJudgement : newJudgementsToAdd) {
+            PConstraint newConstraint = typeJudgement.createConstraintFor(body);
+            for (PConstraint source : traceability.getOrDefault(typeJudgement, Collections.emptyList())) {
+                addTrace(source, newConstraint);
+            }
+        }        
+    }
+    
+    private Object getConstraintKey(PConstraint constraint) {
+        if (constraint instanceof ITypeConstraint) {
+            return ((ITypeConstraint) constraint).getEquivalentJudgement();
+        }
+        // Do not check duplication for any other types
+        return constraint;
+    }
+    
+    void eliminateDuplicateTypeConstraints(PBody body) {
+        Map<Object, PConstraint> constraints = new HashMap<>();
+        for (PConstraint constraint : body.getConstraints()) {
+            Object key = getConstraintKey(constraint);
+            // Retain first found instance of a constraint
+            if (!constraints.containsKey(key)) {
+                constraints.put(key, constraint);
+            }
+        }
+
+        // Retain collected constraints, remove everything else
+        Iterator<PConstraint> iterator = body.getConstraints().iterator();
+        Collection<PConstraint> toRetain = constraints.values(); 
+        while(iterator.hasNext()){
+            PConstraint next = iterator.next();
+            if (!toRetain.contains(next)){
+                derivativeRemoved(next, ConstraintRemovalReason.DUPLICATE);
+                iterator.remove();
+            }
+        }
+    }
+    
+    /**
+     * Verifies the sanity of all constraints. Should be issued as a preventive check before layouting.
+     * 
+     * @param body
+     * @throws RetePatternBuildException
+     */
+    void checkSanity(PBody body) {
+        for (PConstraint pConstraint : body.getConstraints())
+            pConstraint.checkSanity();
+    }
+
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/rewriters/PDisjunctionRewriter.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/rewriters/PDisjunctionRewriter.java
new file mode 100644
index 00000000..c844ccf7
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/rewriters/PDisjunctionRewriter.java
@@ -0,0 +1,27 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2014, 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.psystem.rewriters;
+
+import tools.refinery.viatra.runtime.matchers.psystem.queries.PDisjunction;
+import tools.refinery.viatra.runtime.matchers.psystem.queries.PQuery;
+
+/**
+ * An abstract base class for creating alternative representations for PDisjunctions.
+ * @author Zoltan Ujhelyi
+ *
+ */
+public abstract class PDisjunctionRewriter extends AbstractRewriterTraceSource{
+    
+    public abstract PDisjunction rewrite(PDisjunction disjunction);
+    
+    public PDisjunction rewrite(PQuery query) {
+        return rewrite(query.getDisjunctBodies());
+    }
+    
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/rewriters/PDisjunctionRewriterCacher.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/rewriters/PDisjunctionRewriterCacher.java
new file mode 100644
index 00000000..eb5422ca
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/rewriters/PDisjunctionRewriterCacher.java
@@ -0,0 +1,64 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2014, 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.psystem.rewriters;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.List;
+import java.util.WeakHashMap;
+
+import tools.refinery.viatra.runtime.matchers.psystem.queries.PDisjunction;
+
+/**
+ * A rewriter that stores the previously computed results of a rewriter or a rewriter chain.
+ * 
+ * @author Zoltan Ujhelyi
+ * @since 1.0
+ */
+public class PDisjunctionRewriterCacher extends PDisjunctionRewriter {
+
+    private final List<PDisjunctionRewriter> rewriterChain;
+    private WeakHashMap<PDisjunction, PDisjunction> cachedResults =
+            new WeakHashMap<PDisjunction, PDisjunction>();
+
+    private void setupTraceCollectorInChain(){
+        IRewriterTraceCollector collector = getTraceCollector();
+        for(PDisjunctionRewriter rewriter: rewriterChain){
+            rewriter.setTraceCollector(collector);
+        }
+    }
+    
+    public PDisjunctionRewriterCacher(PDisjunctionRewriter rewriter) {
+        rewriterChain = Collections.singletonList(rewriter);
+    }
+    
+    public PDisjunctionRewriterCacher(PDisjunctionRewriter... rewriters) {
+        rewriterChain = new ArrayList<>(Arrays.asList(rewriters));
+    }
+    
+    public PDisjunctionRewriterCacher(List<PDisjunctionRewriter> rewriterChain) {
+        this.rewriterChain = new ArrayList<>(rewriterChain);
+    }
+    
+    @Override
+    public PDisjunction rewrite(PDisjunction disjunction) {
+        if (!cachedResults.containsKey(disjunction)) {
+            PDisjunction rewritten = disjunction;
+            setupTraceCollectorInChain();
+            for (PDisjunctionRewriter rewriter : rewriterChain) {
+                rewritten = rewriter.rewrite(rewritten);
+            }
+            
+            cachedResults.put(disjunction, rewritten);
+        }
+        return cachedResults.get(disjunction);
+    }
+    
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/rewriters/PQueryFlattener.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/rewriters/PQueryFlattener.java
new file mode 100644
index 00000000..76311d8f
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/rewriters/PQueryFlattener.java
@@ -0,0 +1,253 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2014, Marton Bur, Akos Horvath, 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.psystem.rewriters;
+
+import java.util.ArrayDeque;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Deque;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.LinkedHashSet;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+
+import tools.refinery.viatra.runtime.matchers.psystem.PBody;
+import tools.refinery.viatra.runtime.matchers.psystem.PConstraint;
+import tools.refinery.viatra.runtime.matchers.psystem.basicenumerables.PositivePatternCall;
+import tools.refinery.viatra.runtime.matchers.psystem.queries.PDisjunction;
+import tools.refinery.viatra.runtime.matchers.psystem.queries.PQuery;
+import tools.refinery.viatra.runtime.matchers.psystem.queries.PQuery.PQueryStatus;
+import tools.refinery.viatra.runtime.matchers.psystem.rewriters.IConstraintFilter.AllowAllFilter;
+import tools.refinery.viatra.runtime.matchers.psystem.rewriters.IConstraintFilter.ExportedParameterFilter;
+import tools.refinery.viatra.runtime.matchers.psystem.rewriters.IVariableRenamer.HierarchicalName;
+import tools.refinery.viatra.runtime.matchers.psystem.rewriters.IVariableRenamer.SameName;
+import tools.refinery.viatra.runtime.matchers.util.Preconditions;
+import tools.refinery.viatra.runtime.matchers.util.Sets;
+
+/**
+ * This rewriter class holds the query flattening logic
+ * 
+ * @author Marton Bur
+ * 
+ */
+public class PQueryFlattener extends PDisjunctionRewriter {
+
+    /**
+     * Utility function to produce the permutation of every possible mapping of values.
+     * 
+     * @param values
+     * @return
+     */
+    private static <K, V> Set<Map<K, V>> permutation(Map<K, Set<V>> values) {
+        // An ordering of keys is defined here which will help restoring the appropriate values after the execution of
+        // the cartesian product
+        List<K> keyList = new ArrayList<>(values.keySet());
+
+        // Produce list of value sets with the ordering defined by keyList
+        List<Set<V>> valuesList = new ArrayList<Set<V>>(keyList.size());
+        for (K key : keyList) {
+            valuesList.add(values.get(key));
+        }
+
+        // Cartesian product will obey ordering of the list
+        Set<List<V>> valueMappings = Sets.cartesianProduct(valuesList);
+
+        // Build result
+        Set<Map<K, V>> result = new LinkedHashSet<>();
+        for (List<V> valueList : valueMappings) {
+            Map<K, V> map = new HashMap<>();
+            for (int i = 0; i < keyList.size(); i++) {
+                map.put(keyList.get(i), valueList.get(i));
+            }
+            result.add(map);
+        }
+
+        return result;
+    }
+
+    private IFlattenCallPredicate flattenCallPredicate;
+
+    public PQueryFlattener(IFlattenCallPredicate flattenCallPredicate) {
+        this.flattenCallPredicate = flattenCallPredicate;
+    }
+
+    @Override
+    public PDisjunction rewrite(PDisjunction disjunction) {
+        PQuery query = disjunction.getQuery();
+
+        // Check for recursion
+        Set<PQuery> allReferredQueries = disjunction.getAllReferredQueries();
+        for (PQuery referredQuery : allReferredQueries) {
+            if (referredQuery.getAllReferredQueries().contains(referredQuery)) {
+                throw new RewriterException("Recursive queries are not supported, can't flatten query named \"{1}\"",
+                        new String[] { query.getFullyQualifiedName() }, "Unsupported recursive query", query);
+            }
+        }
+
+        return this.doFlatten(disjunction);
+    }
+
+    /**
+     * Return the list of dependencies (including the root) in chronological order
+     * 
+     * @param rootDisjunction
+     * @return
+     */
+    private List<PDisjunction> disjunctionDependencies(PDisjunction rootDisjunction) {
+        // Disjunctions are first collected into a list usign a depth-first approach,
+        // which can be iterated backwards while removing duplicates
+        Deque<PDisjunction> stack = new ArrayDeque<>();
+        LinkedList<PDisjunction> list = new LinkedList<>();
+        stack.push(rootDisjunction);
+        list.add(rootDisjunction);
+
+        while (!stack.isEmpty()) {
+            PDisjunction disjunction = stack.pop();
+            // Collect dependencies
+            for (PBody pBody : disjunction.getBodies()) {
+                for (PConstraint constraint : pBody.getConstraints()) {
+                    if (constraint instanceof PositivePatternCall) {
+                        PositivePatternCall positivePatternCall = (PositivePatternCall) constraint;
+                        if (flattenCallPredicate.shouldFlatten(positivePatternCall)) {
+                            // If the above preconditions meet, the call should be flattened
+                            PDisjunction calledDisjunction = positivePatternCall.getReferredQuery().getDisjunctBodies();
+                            stack.push(calledDisjunction);
+                            list.add(calledDisjunction);
+                        }
+                    }
+                }
+            }
+        }
+
+        // Remove duplicates (keeping the last instance) and reverse order
+        Set<PDisjunction> visited = new HashSet<PDisjunction>();
+        List<PDisjunction> result = new ArrayList<PDisjunction>(list.size());
+        
+        list.descendingIterator().forEachRemaining(item -> {
+            if (!visited.contains(item)) {
+                result.add(item);
+                visited.add(item);
+            }
+            
+        });
+
+        return result;
+    }
+
+    /**
+     * This function holds the actual flattening logic for a PQuery
+     * 
+     * @param rootDisjunction
+     *            to be flattened
+     * @return the flattened bodies of the pQuery
+     */
+    private PDisjunction doFlatten(PDisjunction rootDisjunction) {
+
+        Map<PDisjunction, Set<PBody>> flatBodyMapping = new HashMap<>();
+
+        List<PDisjunction> dependencies = disjunctionDependencies(rootDisjunction);
+
+        for (PDisjunction disjunction : dependencies) {
+            Set<PBody> flatBodies = new LinkedHashSet<>();
+            for (PBody body : disjunction.getBodies()) {
+                if (isFlatteningNeeded(body)) {
+                    Map<PositivePatternCall, Set<PBody>> flattenedBodies = new HashMap<>();
+                    for (PConstraint pConstraint : body.getConstraints()) {
+
+                        if (pConstraint instanceof PositivePatternCall) {
+                            PositivePatternCall positivePatternCall = (PositivePatternCall) pConstraint;
+                            if (flattenCallPredicate.shouldFlatten(positivePatternCall)) {
+                                // If the above preconditions meet, do the flattening and return the disjoint bodies
+                                PDisjunction calledDisjunction = positivePatternCall.getReferredQuery()
+                                        .getDisjunctBodies();
+
+                                Set<PBody> flattenedBodySet = flatBodyMapping.get(calledDisjunction);
+                                Preconditions.checkArgument(!flattenedBodySet.isEmpty());
+                                flattenedBodies.put(positivePatternCall, flattenedBodySet);
+                            }
+                        }
+                    }
+                    flatBodies.addAll(createSetOfFlatPBodies(body, flattenedBodies));
+                } else {
+                    flatBodies.add(prepareFlatPBody(body));
+                }
+            }
+            flatBodyMapping.put(disjunction, flatBodies);
+        }
+
+        return new PDisjunction(rootDisjunction.getQuery(), flatBodyMapping.get(rootDisjunction));
+    }
+
+    /**
+     * Creates the flattened bodies based on the caller body and the called (and already flattened) disjunctions
+     * 
+     * @param pBody
+     *            the body to flatten
+     * @param flattenedDisjunctions
+     *            the
+     * @param flattenedCalls
+     * @return
+     */
+    private Set<PBody> createSetOfFlatPBodies(PBody pBody, Map<PositivePatternCall, Set<PBody>> flattenedCalls) {
+        PQuery pQuery = pBody.getPattern();
+
+        Set<Map<PositivePatternCall, PBody>> conjunctedCalls = permutation(flattenedCalls);
+
+        // The result set containing the merged conjuncted bodies
+        Set<PBody> conjunctedBodies = new HashSet<>();
+
+        for (Map<PositivePatternCall, PBody> calledBodies : conjunctedCalls) {
+            FlattenerCopier copier = createBodyCopier(pQuery, calledBodies);
+
+            int i = 0;
+            HierarchicalName hierarchicalNamingTool = new HierarchicalName();
+            for (PositivePatternCall patternCall : calledBodies.keySet()) {
+                // Merge each called body
+                hierarchicalNamingTool.setCallCount(i++);
+                copier.mergeBody(patternCall, hierarchicalNamingTool, new ExportedParameterFilter());
+            }
+
+            // Merge the caller's constraints to the conjunct body
+            copier.mergeBody(pBody);
+
+            PBody copiedBody = copier.getCopiedBody();
+            copiedBody.setStatus(PQueryStatus.OK);
+            conjunctedBodies.add(copiedBody);
+        }
+
+        return conjunctedBodies;
+    }
+
+    private FlattenerCopier createBodyCopier(PQuery query, Map<PositivePatternCall, PBody> calledBodies) {
+        FlattenerCopier flattenerCopier = new FlattenerCopier(query, calledBodies);
+        flattenerCopier.setTraceCollector(getTraceCollector());
+        return flattenerCopier;
+    }
+
+    private PBody prepareFlatPBody(PBody pBody) {
+        PBodyCopier copier = createBodyCopier(pBody.getPattern(), Collections.<PositivePatternCall, PBody> emptyMap());
+        copier.mergeBody(pBody, new SameName(), new AllowAllFilter());
+        // the copying of the body here is necessary for only one containing PDisjunction can be assigned to a PBody
+        return copier.getCopiedBody();
+    }
+
+    private boolean isFlatteningNeeded(PBody pBody) {
+        // Check if the body contains positive pattern call AND if it should be flattened
+        for (PConstraint pConstraint : pBody.getConstraints()) {
+            if (pConstraint instanceof PositivePatternCall) {
+                return flattenCallPredicate.shouldFlatten((PositivePatternCall) pConstraint);
+            }
+        }
+        return false;
+    }
+
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/rewriters/RewriterException.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/rewriters/RewriterException.java
new file mode 100644
index 00000000..d0fc286b
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/rewriters/RewriterException.java
@@ -0,0 +1,31 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2014, 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.psystem.rewriters;
+
+import tools.refinery.viatra.runtime.matchers.psystem.queries.QueryInitializationException;
+
+/**
+ * An exception to wrap various issues during PDisjunction rewriting.
+ * @author Zoltan Ujhelyi
+ *
+ */
+public class RewriterException extends QueryInitializationException {
+
+    private static final long serialVersionUID = -4703825954995497932L;
+
+    public RewriterException(String message, String[] context, String shortMessage, Object patternDescription,
+            Throwable cause) {
+        super(message, context, shortMessage, patternDescription, cause);
+    }
+
+    public RewriterException(String message, String[] context, String shortMessage, Object patternDescription) {
+        super(message, context, shortMessage, patternDescription);
+    }
+
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/rewriters/SurrogateQueryRewriter.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/rewriters/SurrogateQueryRewriter.java
new file mode 100644
index 00000000..71459558
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/rewriters/SurrogateQueryRewriter.java
@@ -0,0 +1,63 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2015, 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.psystem.rewriters;
+
+import java.util.LinkedHashSet;
+import java.util.Set;
+
+import tools.refinery.viatra.runtime.matchers.context.IInputKey;
+import tools.refinery.viatra.runtime.matchers.context.surrogate.SurrogateQueryRegistry;
+import tools.refinery.viatra.runtime.matchers.psystem.PBody;
+import tools.refinery.viatra.runtime.matchers.psystem.PVariable;
+import tools.refinery.viatra.runtime.matchers.psystem.basicenumerables.PositivePatternCall;
+import tools.refinery.viatra.runtime.matchers.psystem.basicenumerables.TypeConstraint;
+import tools.refinery.viatra.runtime.matchers.psystem.queries.PDisjunction;
+import tools.refinery.viatra.runtime.matchers.psystem.queries.PQuery;
+import tools.refinery.viatra.runtime.matchers.psystem.queries.PQuery.PQueryStatus;
+import tools.refinery.viatra.runtime.matchers.tuple.Tuple;
+import tools.refinery.viatra.runtime.matchers.tuple.Tuples;
+
+/**
+ * @author Zoltan Ujhelyi
+ *
+ */
+public class SurrogateQueryRewriter extends PDisjunctionRewriter {
+
+    @Override
+    public PDisjunction rewrite(PDisjunction disjunction) {
+        Set<PBody> replacedBodies = new LinkedHashSet<>();
+        for (PBody body : disjunction.getBodies()) {
+            PBodyCopier copier = new PBodyCopier(body, getTraceCollector()) {
+                
+                @Override
+                protected void copyTypeConstraint(TypeConstraint typeConstraint) {
+                    PVariable[] mappedVariables = extractMappedVariables(typeConstraint);
+                    Tuple variablesTuple = Tuples.flatTupleOf((Object[])mappedVariables);       
+                    final IInputKey supplierKey = typeConstraint.getSupplierKey();
+                    if(SurrogateQueryRegistry.instance().hasSurrogateQueryFQN(supplierKey)) {
+                        PQuery surrogateQuery = SurrogateQueryRegistry.instance().getSurrogateQuery(supplierKey);
+                        if (surrogateQuery == null) {
+                            throw new IllegalStateException(
+                                        String.format("Surrogate query for feature %s not found", 
+                                                        supplierKey.getPrettyPrintableName()));
+                        }
+                        addTrace(typeConstraint, new PositivePatternCall(getCopiedBody(), variablesTuple, surrogateQuery));
+                    } else {
+                        addTrace(typeConstraint, new TypeConstraint(getCopiedBody(), variablesTuple, supplierKey));
+                    }
+                }
+            };
+            PBody modifiedBody = copier.getCopiedBody();
+            replacedBodies.add(modifiedBody);
+            modifiedBody.setStatus(PQueryStatus.OK);
+        }
+        return new PDisjunction(replacedBodies);
+    }
+
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/rewriters/VariableMappingExpressionEvaluatorWrapper.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/rewriters/VariableMappingExpressionEvaluatorWrapper.java
new file mode 100644
index 00000000..10337979
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/rewriters/VariableMappingExpressionEvaluatorWrapper.java
@@ -0,0 +1,88 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2016, Grill Balázs, 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.psystem.rewriters;
+
+import java.util.HashMap;
+import java.util.LinkedHashMap;
+import java.util.Map;
+
+import tools.refinery.viatra.runtime.matchers.psystem.IExpressionEvaluator;
+import tools.refinery.viatra.runtime.matchers.psystem.IValueProvider;
+import tools.refinery.viatra.runtime.matchers.psystem.PVariable;
+import tools.refinery.viatra.runtime.matchers.util.Preconditions;
+
+/**
+ * A wrapper for {@link IExpressionEvaluator} which is capable of correctly mapping variable names used by the
+ * expression.
+ * 
+ * @author Grill Balázs
+ *
+ */
+class VariableMappingExpressionEvaluatorWrapper implements IExpressionEvaluator {
+
+    private final IExpressionEvaluator wrapped;
+    private final Map<String, String> variableMapping;
+    
+    public VariableMappingExpressionEvaluatorWrapper(IExpressionEvaluator wrapped,
+            Map<PVariable, PVariable> variableMapping) {
+        
+        // Support to rewrap an already wrapped expression.
+        boolean rewrap = wrapped instanceof VariableMappingExpressionEvaluatorWrapper;
+        this.wrapped = rewrap ? ((VariableMappingExpressionEvaluatorWrapper)wrapped).wrapped : wrapped;
+
+        // Instead of just saving the reference of the mapping, save the actual (trimmed) state of the mapping as it
+        // may change during copying (especially during flattening). A LinkedHashMap is used to retain ordering of
+        // original parameter names iterator.
+        this.variableMapping = new LinkedHashMap<>();
+
+        // Index map by variable names
+        Map<String, PVariable> names = new HashMap<>();
+        for (PVariable originalVar : variableMapping.keySet()) {
+            names.put(originalVar.getName(), originalVar);
+        }
+        
+        // In case of rewrapping, current names are contained by the previous mapping
+        Map<String, String> previousMapping = null;
+        if (rewrap){
+            previousMapping = ((VariableMappingExpressionEvaluatorWrapper)wrapped).variableMapping;
+        }
+
+        // Populate mapping
+        for (String inputParameterName : this.wrapped.getInputParameterNames()) {
+            String parameterName = rewrap ? previousMapping.get(inputParameterName) : inputParameterName;
+            Preconditions.checkArgument(parameterName != null);
+            PVariable original = names.get(parameterName);
+            Preconditions.checkArgument(original != null);
+            PVariable mapped = variableMapping.get(original);
+            if (mapped != null){
+                this.variableMapping.put(inputParameterName, mapped.getName());
+            }
+        }
+    }
+
+    @Override
+    public String getShortDescription() {
+        return wrapped.getShortDescription();
+    }
+
+    @Override
+    public Iterable<String> getInputParameterNames() {
+        return variableMapping.values();
+    }
+
+    @Override
+    public Object evaluateExpression(final IValueProvider provider) throws Exception {
+        return wrapped.evaluateExpression(variableName -> {
+            String mappedVariableName = variableMapping.get(variableName);
+            Preconditions.checkArgument(mappedVariableName != null, "Could not find variable %s", variableName);
+            return provider.getValue(mappedVariableName);
+        });
+    }
+
+}