64 files changed, 1533 insertions, 431 deletions

diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/InvalidQueryException.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/InvalidQueryException.java
new file mode 100644
index 00000000..c39277a0
--- /dev/null
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/InvalidQueryException.java
@@ -0,0 +1,23 @@
+/*
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query;
+
+public class InvalidQueryException extends RuntimeException {
+        public InvalidQueryException() {
+        }
+
+        public InvalidQueryException(String message) {
+                super(message);
+        }
+
+        public InvalidQueryException(String message, Throwable cause) {
+                super(message, cause);
+        }
+
+        public InvalidQueryException(Throwable cause) {
+                super(cause);
+        }
+}
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/ModelQueryBuilder.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/ModelQueryBuilder.java
index c62a95b5..332e6381 100644
--- a/subprojects/store-query/src/main/java/tools/refinery/store/query/ModelQueryBuilder.java
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/ModelQueryBuilder.java
@@ -8,6 +8,7 @@ package tools.refinery.store.query;
 import tools.refinery.store.adapter.ModelAdapterBuilder;
 import tools.refinery.store.model.ModelStore;
 import tools.refinery.store.query.dnf.AnyQuery;
+import tools.refinery.store.query.rewriter.DnfRewriter;
 
 import java.util.Collection;
 import java.util.List;
@@ -25,6 +26,8 @@ public interface ModelQueryBuilder extends ModelAdapterBuilder {
 
         ModelQueryBuilder query(AnyQuery query);
 
+        ModelQueryBuilder rewriter(DnfRewriter rewriter);
+
         @Override
         ModelQueryStoreAdapter build(ModelStore store);
 }
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/ModelQueryStoreAdapter.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/ModelQueryStoreAdapter.java
index f0a950a6..8b67c5c1 100644
--- a/subprojects/store-query/src/main/java/tools/refinery/store/query/ModelQueryStoreAdapter.java
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/ModelQueryStoreAdapter.java
@@ -8,6 +8,7 @@ package tools.refinery.store.query;
 import tools.refinery.store.adapter.ModelStoreAdapter;
 import tools.refinery.store.model.Model;
 import tools.refinery.store.query.dnf.AnyQuery;
+import tools.refinery.store.query.dnf.Query;
 import tools.refinery.store.query.view.AnySymbolView;
 
 import java.util.Collection;
@@ -17,6 +18,12 @@ public interface ModelQueryStoreAdapter extends ModelStoreAdapter {
 
         Collection<AnyQuery> getQueries();
 
+        default AnyQuery getCanonicalQuery(AnyQuery query) {
+                return getCanonicalQuery((Query<?>) query);
+        }
+
+        <T> Query<T> getCanonicalQuery(Query<T> query);
+
         @Override
         ModelQueryAdapter createModelAdapter(Model model);
 }
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/ClausePostProcessor.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/ClausePostProcessor.java
index b5e7092b..8800a155 100644
--- a/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/ClausePostProcessor.java
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/ClausePostProcessor.java
@@ -6,13 +6,12 @@
 package tools.refinery.store.query.dnf;
 
 import org.jetbrains.annotations.NotNull;
-import tools.refinery.store.query.literal.BooleanLiteral;
-import tools.refinery.store.query.literal.EquivalenceLiteral;
-import tools.refinery.store.query.literal.Literal;
+import tools.refinery.store.query.Constraint;
+import tools.refinery.store.query.InvalidQueryException;
+import tools.refinery.store.query.literal.*;
 import tools.refinery.store.query.substitution.MapBasedSubstitution;
 import tools.refinery.store.query.substitution.StatelessSubstitution;
 import tools.refinery.store.query.substitution.Substitution;
-import tools.refinery.store.query.term.NodeVariable;
 import tools.refinery.store.query.term.ParameterDirection;
 import tools.refinery.store.query.term.Variable;
 
@@ -22,8 +21,8 @@ import java.util.function.Function;
 class ClausePostProcessor {
         private final Map<Variable, ParameterInfo> parameters;
         private final List<Literal> literals;
-        private final Map<NodeVariable, NodeVariable> representatives = new LinkedHashMap<>();
-        private final Map<NodeVariable, Set<NodeVariable>> equivalencePartition = new HashMap<>();
+        private final Map<Variable, Variable> representatives = new LinkedHashMap<>();
+        private final Map<Variable, Set<Variable>> equivalencePartition = new HashMap<>();
         private List<Literal> substitutedLiterals;
         private final Set<Variable> existentiallyQuantifiedVariables = new LinkedHashSet<>();
         private Set<Variable> positiveVariables;
@@ -58,6 +57,9 @@ class ClausePostProcessor {
                 if (filteredLiterals.isEmpty()) {
                         return ConstantResult.ALWAYS_TRUE;
                 }
+                if (hasContradictoryCall(filteredLiterals)) {
+                        return ConstantResult.ALWAYS_FALSE;
+                }
                 var clause = new DnfClause(Collections.unmodifiableSet(positiveVariables),
                                 Collections.unmodifiableList(filteredLiterals));
                 return new ClauseResult(clause);
@@ -67,16 +69,16 @@ class ClausePostProcessor {
                 for (var literal : literals) {
                         if (isPositiveEquivalence(literal)) {
                                 var equivalenceLiteral = (EquivalenceLiteral) literal;
-                                mergeVariables(equivalenceLiteral.left(), equivalenceLiteral.right());
+                                mergeVariables(equivalenceLiteral.getLeft(), equivalenceLiteral.getRight());
                         }
                 }
         }
 
         private static boolean isPositiveEquivalence(Literal literal) {
-                return literal instanceof EquivalenceLiteral equivalenceLiteral && equivalenceLiteral.positive();
+                return literal instanceof EquivalenceLiteral equivalenceLiteral && equivalenceLiteral.isPositive();
         }
 
-        private void mergeVariables(NodeVariable left, NodeVariable right) {
+        private void mergeVariables(Variable left, Variable right) {
                 var leftRepresentative = getRepresentative(left);
                 var rightRepresentative = getRepresentative(right);
                 var leftInfo = parameters.get(leftRepresentative);
@@ -89,7 +91,7 @@ class ClausePostProcessor {
                 }
         }
 
-        private void doMergeVariables(NodeVariable parentRepresentative, NodeVariable newChildRepresentative) {
+        private void doMergeVariables(Variable parentRepresentative, Variable newChildRepresentative) {
                 var parentSet = getEquivalentVariables(parentRepresentative);
                 var childSet = getEquivalentVariables(newChildRepresentative);
                 parentSet.addAll(childSet);
@@ -99,18 +101,18 @@ class ClausePostProcessor {
                 }
         }
 
-        private NodeVariable getRepresentative(NodeVariable variable) {
+        private Variable getRepresentative(Variable variable) {
                 return representatives.computeIfAbsent(variable, Function.identity());
         }
 
-        private Set<NodeVariable> getEquivalentVariables(NodeVariable variable) {
+        private Set<Variable> getEquivalentVariables(Variable variable) {
                 var representative = getRepresentative(variable);
                 if (!representative.equals(variable)) {
                         throw new AssertionError("NodeVariable %s already has a representative %s"
                                         .formatted(variable, representative));
                 }
                 return equivalencePartition.computeIfAbsent(variable, key -> {
-                        var set = new HashSet<NodeVariable>(1);
+                        var set = new HashSet<Variable>(1);
                         set.add(key);
                         return set;
                 });
@@ -121,7 +123,7 @@ class ClausePostProcessor {
                         var left = pair.getKey();
                         var right = pair.getValue();
                         if (!left.equals(right) && parameters.containsKey(left) && parameters.containsKey(right)) {
-                                substitutedLiterals.add(left.isEquivalent(right));
+                                substitutedLiterals.add(new EquivalenceLiteral(true, left, right));
                         }
                 }
         }
@@ -147,20 +149,7 @@ class ClausePostProcessor {
 
         private void computeExistentiallyQuantifiedVariables() {
                 for (var literal : substitutedLiterals) {
-                        for (var variable : literal.getOutputVariables()) {
-                                boolean added = existentiallyQuantifiedVariables.add(variable);
-                                if (!variable.isUnifiable()) {
-                                        var parameterInfo = parameters.get(variable);
-                                        if (parameterInfo != null && parameterInfo.direction() == ParameterDirection.IN) {
-                                                throw new IllegalArgumentException("Trying to bind %s parameter %s"
-                                                                .formatted(ParameterDirection.IN, variable));
-                                        }
-                                        if (!added) {
-                                                throw new IllegalArgumentException("Variable %s has multiple assigned values"
-                                                                .formatted(variable));
-                                        }
-                                }
-                        }
+                        existentiallyQuantifiedVariables.addAll(literal.getOutputVariables());
                 }
         }
 
@@ -172,7 +161,7 @@ class ClausePostProcessor {
                                 // Inputs count as positive, because they are already bound when we evaluate literals.
                                 positiveVariables.add(variable);
                         } else if (!existentiallyQuantifiedVariables.contains(variable)) {
-                                throw new IllegalArgumentException("Unbound %s parameter %s"
+                                throw new InvalidQueryException("Unbound %s parameter %s"
                                                 .formatted(ParameterDirection.OUT, variable));
                         }
                 }
@@ -184,7 +173,7 @@ class ClausePostProcessor {
                         var representative = pair.getKey();
                         if (!positiveVariables.contains(representative)) {
                                 var variableSet = pair.getValue();
-                                throw new IllegalArgumentException("Variables %s were merged by equivalence but are not bound"
+                                throw new InvalidQueryException("Variables %s were merged by equivalence but are not bound"
                                                 .formatted(variableSet));
                         }
                 }
@@ -196,7 +185,7 @@ class ClausePostProcessor {
                         for (var variable : literal.getPrivateVariables(positiveVariables)) {
                                 var oldLiteral = negativeVariablesMap.put(variable, literal);
                                 if (oldLiteral != null) {
-                                        throw new IllegalArgumentException("Unbound variable %s appears in multiple literals %s and %s"
+                                        throw new InvalidQueryException("Unbound variable %s appears in multiple literals %s and %s"
                                                         .formatted(variable, oldLiteral, literal));
                                 }
                         }
@@ -218,11 +207,60 @@ class ClausePostProcessor {
                         variable.addToSortedLiterals();
                 }
                 if (!variableToLiteralInputMap.isEmpty()) {
-                        throw new IllegalArgumentException("Unbound input variables %s"
+                        throw new InvalidQueryException("Unbound input variables %s"
                                         .formatted(variableToLiteralInputMap.keySet()));
                 }
         }
 
+        private boolean hasContradictoryCall(Collection<Literal> filteredLiterals) {
+                var positiveCalls = new HashMap<Constraint, Set<CallLiteral>>();
+                for (var literal : filteredLiterals) {
+                        if (literal instanceof CallLiteral callLiteral && callLiteral.getPolarity() == CallPolarity.POSITIVE) {
+                                var callsOfTarget = positiveCalls.computeIfAbsent(callLiteral.getTarget(), key -> new HashSet<>());
+                                callsOfTarget.add(callLiteral);
+                        }
+                }
+                for (var literal : filteredLiterals) {
+                        if (literal instanceof CallLiteral callLiteral && callLiteral.getPolarity() == CallPolarity.NEGATIVE) {
+                                var callsOfTarget = positiveCalls.get(callLiteral.getTarget());
+                                if (contradicts(callLiteral, callsOfTarget)) {
+                                        return true;
+                                }
+                        }
+                }
+                return false;
+        }
+
+        private boolean contradicts(CallLiteral negativeCall, Collection<CallLiteral> positiveCalls) {
+                if (positiveCalls == null) {
+                        return false;
+                }
+                for (var positiveCall : positiveCalls) {
+                        if (contradicts(negativeCall, positiveCall)) {
+                                return true;
+                        }
+                }
+                return false;
+        }
+
+        private boolean contradicts(CallLiteral negativeCall, CallLiteral positiveCall) {
+                var privateVariables = negativeCall.getPrivateVariables(positiveVariables);
+                var negativeArguments = negativeCall.getArguments();
+                var positiveArguments = positiveCall.getArguments();
+                int arity = negativeArguments.size();
+                for (int i = 0; i < arity; i++) {
+                        var negativeArgument = negativeArguments.get(i);
+                        if (privateVariables.contains(negativeArgument)) {
+                                continue;
+                        }
+                        var positiveArgument = positiveArguments.get(i);
+                        if (!negativeArgument.equals(positiveArgument)) {
+                                return false;
+                        }
+                }
+                return true;
+        }
+
         private class SortableLiteral implements Comparable<SortableLiteral> {
                 private final int index;
                 private final Literal literal;
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/Dnf.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/Dnf.java
index 50b245f7..86a1b6b2 100644
--- a/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/Dnf.java
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/Dnf.java
@@ -6,9 +6,12 @@
 package tools.refinery.store.query.dnf;
 
 import tools.refinery.store.query.Constraint;
-import tools.refinery.store.query.literal.Reduction;
+import tools.refinery.store.query.InvalidQueryException;
 import tools.refinery.store.query.equality.DnfEqualityChecker;
 import tools.refinery.store.query.equality.LiteralEqualityHelper;
+import tools.refinery.store.query.equality.SubstitutingLiteralEqualityHelper;
+import tools.refinery.store.query.equality.SubstitutingLiteralHashCodeHelper;
+import tools.refinery.store.query.literal.Reduction;
 import tools.refinery.store.query.term.Parameter;
 import tools.refinery.store.query.term.Variable;
 
@@ -53,7 +56,7 @@ public final class Dnf implements Constraint {
                                                                                    FunctionalDependency<Variable> functionalDependency) {
                 for (var variable : toValidate) {
                         if (!parameterSet.contains(variable)) {
-                                throw new IllegalArgumentException(
+                                throw new InvalidQueryException(
                                                 "Variable %s of functional dependency %s does not appear in the parameter list %s"
                                                                 .formatted(variable, functionalDependency, symbolicParameters));
                         }
@@ -66,7 +69,7 @@ public final class Dnf implements Constraint {
         }
 
         public boolean isExplicitlyNamed() {
-                return name == null;
+                return name != null;
         }
 
         public String getUniqueName() {
@@ -129,7 +132,7 @@ public final class Dnf implements Constraint {
                         return false;
                 }
                 for (int i = 0; i < numClauses; i++) {
-                        var literalEqualityHelper = new LiteralEqualityHelper(callEqualityChecker, symbolicParameters,
+                        var literalEqualityHelper = new SubstitutingLiteralEqualityHelper(callEqualityChecker, symbolicParameters,
                                         other.symbolicParameters);
                         if (!clauses.get(i).equalsWithSubstitution(literalEqualityHelper, other.clauses.get(i))) {
                                 return false;
@@ -146,6 +149,18 @@ public final class Dnf implements Constraint {
                 return false;
         }
 
+        public int hashCodeWithSubstitution() {
+                var helper = new SubstitutingLiteralHashCodeHelper();
+                int result = 0;
+                for (var symbolicParameter : symbolicParameters) {
+                        result = result * 31 + symbolicParameter.hashCodeWithSubstitution(helper);
+                }
+                for (var clause : clauses) {
+                        result = result * 31 + clause.hashCodeWithSubstitution(helper);
+                }
+                return result;
+        }
+
         @Override
         public String toString() {
                 return "%s/%d".formatted(name(), arity());
@@ -201,6 +216,13 @@ public final class Dnf implements Constraint {
                 return new DnfBuilder(name);
         }
 
+        public static DnfBuilder builderFrom(Dnf original) {
+                var builder = builder(original.name());
+                builder.symbolicParameters(original.getSymbolicParameters());
+                builder.functionalDependencies(original.getFunctionalDependencies());
+                return builder;
+        }
+
         public static Dnf of(Consumer<DnfBuilder> callback) {
                 return of(null, callback);
         }
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/DnfBuilder.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/DnfBuilder.java
index 8e38ca6b..0f9fd366 100644
--- a/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/DnfBuilder.java
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/DnfBuilder.java
@@ -5,12 +5,10 @@
  */
 package tools.refinery.store.query.dnf;
 
+import tools.refinery.store.query.InvalidQueryException;
 import tools.refinery.store.query.dnf.callback.*;
 import tools.refinery.store.query.literal.Literal;
-import tools.refinery.store.query.term.DataVariable;
-import tools.refinery.store.query.term.NodeVariable;
-import tools.refinery.store.query.term.ParameterDirection;
-import tools.refinery.store.query.term.Variable;
+import tools.refinery.store.query.term.*;
 
 import java.util.*;
 
@@ -62,6 +60,18 @@ public final class DnfBuilder {
                 return variable;
         }
 
+        public Variable parameter(Parameter parameter) {
+                return parameter(null, parameter);
+        }
+
+        public Variable parameter(String name, Parameter parameter) {
+                var type = parameter.tryGetType();
+                if (type.isPresent()) {
+                        return parameter(name, type.get(), parameter.getDirection());
+                }
+                return parameter(name, parameter.getDirection());
+        }
+
         public DnfBuilder parameter(Variable variable) {
                 return parameter(variable, ParameterDirection.OUT);
         }
@@ -88,7 +98,7 @@ public final class DnfBuilder {
         public DnfBuilder symbolicParameter(SymbolicParameter symbolicParameter) {
                 var variable = symbolicParameter.getVariable();
                 if (!parameterVariables.add(variable)) {
-                        throw new IllegalArgumentException("Variable %s is already on the parameter list %s"
+                        throw new InvalidQueryException("Variable %s is already on the parameter list %s"
                                         .formatted(variable, parameters));
                 }
                 parameters.add(symbolicParameter);
@@ -129,7 +139,7 @@ public final class DnfBuilder {
         }
 
         public <T> DnfBuilder clause(Class<T> type1, ClauseCallback1Data1<T> callback) {
-                return clause(callback.toLiterals(Variable.of("v1", type1)));
+                return clause(callback.toLiterals(Variable.of("d1", type1)));
         }
 
         public DnfBuilder clause(ClauseCallback2Data0 callback) {
@@ -206,57 +216,10 @@ public final class DnfBuilder {
         }
 
         public Dnf build() {
-                var postProcessedClauses = postProcessClauses();
+                var postProcessor = new DnfPostProcessor(parameters, clauses);
+                var postProcessedClauses = postProcessor.postProcessClauses();
                 return new Dnf(name, Collections.unmodifiableList(parameters),
                                 Collections.unmodifiableList(functionalDependencies),
                                 Collections.unmodifiableList(postProcessedClauses));
         }
-
-        private List<DnfClause> postProcessClauses() {
-                var parameterInfoMap = getParameterInfoMap();
-                var postProcessedClauses = new ArrayList<DnfClause>(clauses.size());
-                for (var literals : clauses) {
-                        var postProcessor = new ClausePostProcessor(parameterInfoMap, literals);
-                        var result = postProcessor.postProcessClause();
-                        if (result instanceof ClausePostProcessor.ClauseResult clauseResult) {
-                                postProcessedClauses.add(clauseResult.clause());
-                        } else if (result instanceof ClausePostProcessor.ConstantResult constantResult) {
-                                switch (constantResult) {
-                                case ALWAYS_TRUE -> {
-                                        var inputVariables = getInputVariables();
-                                        return List.of(new DnfClause(inputVariables, List.of()));
-                                }
-                                case ALWAYS_FALSE -> {
-                                        // Skip this clause because it can never match.
-                                }
-                                default -> throw new IllegalStateException("Unexpected ClausePostProcessor.ConstantResult: " +
-                                                constantResult);
-                                }
-                        } else {
-                                throw new IllegalStateException("Unexpected ClausePostProcessor.Result: " + result);
-                        }
-                }
-                return postProcessedClauses;
-        }
-
-        private Map<Variable, ClausePostProcessor.ParameterInfo> getParameterInfoMap() {
-                var mutableParameterInfoMap = new LinkedHashMap<Variable, ClausePostProcessor.ParameterInfo>();
-                int arity = parameters.size();
-                for (int i = 0; i < arity; i++) {
-                        var parameter = parameters.get(i);
-                        mutableParameterInfoMap.put(parameter.getVariable(),
-                                        new ClausePostProcessor.ParameterInfo(parameter.getDirection(), i));
-                }
-                return Collections.unmodifiableMap(mutableParameterInfoMap);
-        }
-
-        private Set<Variable> getInputVariables() {
-                var inputParameters = new LinkedHashSet<Variable>();
-                for (var parameter : parameters) {
-                        if (parameter.getDirection() == ParameterDirection.IN) {
-                                inputParameters.add(parameter.getVariable());
-                        }
-                }
-                return Collections.unmodifiableSet(inputParameters);
-        }
 }
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/DnfClause.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/DnfClause.java
index fdd0d47c..94327bad 100644
--- a/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/DnfClause.java
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/DnfClause.java
@@ -6,6 +6,7 @@
 package tools.refinery.store.query.dnf;
 
 import tools.refinery.store.query.equality.LiteralEqualityHelper;
+import tools.refinery.store.query.equality.LiteralHashCodeHelper;
 import tools.refinery.store.query.literal.Literal;
 import tools.refinery.store.query.term.Variable;
 
@@ -25,4 +26,12 @@ public record DnfClause(Set<Variable> positiveVariables, List<Literal> literals)
                 }
                 return true;
         }
+
+        public int hashCodeWithSubstitution(LiteralHashCodeHelper helper) {
+                int result = 0;
+                for (var literal : literals) {
+                        result = result * 31 + literal.hashCodeWithSubstitution(helper);
+                }
+                return result;
+        }
 }
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/DnfPostProcessor.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/DnfPostProcessor.java
new file mode 100644
index 00000000..50236642
--- /dev/null
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/DnfPostProcessor.java
@@ -0,0 +1,112 @@
+/*
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.dnf;
+
+import tools.refinery.store.query.InvalidQueryException;
+import tools.refinery.store.query.equality.DnfEqualityChecker;
+import tools.refinery.store.query.equality.SubstitutingLiteralEqualityHelper;
+import tools.refinery.store.query.equality.SubstitutingLiteralHashCodeHelper;
+import tools.refinery.store.query.literal.Literal;
+import tools.refinery.store.query.term.ParameterDirection;
+import tools.refinery.store.query.term.Variable;
+
+import java.util.*;
+
+class DnfPostProcessor {
+        private final List<SymbolicParameter> parameters;
+        private final List<List<Literal>> clauses;
+
+        public DnfPostProcessor(List<SymbolicParameter> parameters, List<List<Literal>> clauses) {
+                this.parameters = parameters;
+                this.clauses = clauses;
+        }
+
+        public List<DnfClause> postProcessClauses() {
+                var parameterInfoMap = getParameterInfoMap();
+                var postProcessedClauses = new LinkedHashSet<CanonicalClause>(clauses.size());
+                int index = 0;
+                for (var literals : clauses) {
+                        var postProcessor = new ClausePostProcessor(parameterInfoMap, literals);
+                        ClausePostProcessor.Result result;
+                        try {
+                                result = postProcessor.postProcessClause();
+                        } catch (InvalidQueryException e) {
+                                throw new InvalidClauseException(index, e);
+                        }
+                        if (result instanceof ClausePostProcessor.ClauseResult clauseResult) {
+                                postProcessedClauses.add(new CanonicalClause(clauseResult.clause()));
+                        } else if (result instanceof ClausePostProcessor.ConstantResult constantResult) {
+                                switch (constantResult) {
+                                case ALWAYS_TRUE -> {
+                                        var inputVariables = getInputVariables();
+                                        return List.of(new DnfClause(inputVariables, List.of()));
+                                }
+                                case ALWAYS_FALSE -> {
+                                        // Skip this clause because it can never match.
+                                }
+                                default -> throw new IllegalStateException("Unexpected ClausePostProcessor.ConstantResult: " +
+                                                constantResult);
+                                }
+                        } else {
+                                throw new IllegalStateException("Unexpected ClausePostProcessor.Result: " + result);
+                        }
+                        index++;
+                }
+                return postProcessedClauses.stream().map(CanonicalClause::getDnfClause).toList();
+        }
+
+        private Map<Variable, ClausePostProcessor.ParameterInfo> getParameterInfoMap() {
+                var mutableParameterInfoMap = new LinkedHashMap<Variable, ClausePostProcessor.ParameterInfo>();
+                int arity = parameters.size();
+                for (int i = 0; i < arity; i++) {
+                        var parameter = parameters.get(i);
+                        mutableParameterInfoMap.put(parameter.getVariable(),
+                                        new ClausePostProcessor.ParameterInfo(parameter.getDirection(), i));
+                }
+                return Collections.unmodifiableMap(mutableParameterInfoMap);
+        }
+
+        private Set<Variable> getInputVariables() {
+                var inputParameters = new LinkedHashSet<Variable>();
+                for (var parameter : parameters) {
+                        if (parameter.getDirection() == ParameterDirection.IN) {
+                                inputParameters.add(parameter.getVariable());
+                        }
+                }
+                return Collections.unmodifiableSet(inputParameters);
+        }
+
+        private class CanonicalClause {
+                private final DnfClause dnfClause;
+
+                public CanonicalClause(DnfClause dnfClause) {
+                        this.dnfClause = dnfClause;
+                }
+
+                public DnfClause getDnfClause() {
+                        return dnfClause;
+                }
+
+                @Override
+                public boolean equals(Object obj) {
+                        if (this == obj) {
+                                return true;
+                        }
+                        if (obj == null || getClass() != obj.getClass()) {
+                                return false;
+                        }
+                        var otherCanonicalClause = (CanonicalClause) obj;
+                        var helper = new SubstitutingLiteralEqualityHelper(DnfEqualityChecker.DEFAULT, parameters, parameters);
+                        return dnfClause.equalsWithSubstitution(helper, otherCanonicalClause.dnfClause);
+                }
+
+                @Override
+                public int hashCode() {
+                        var helper = new SubstitutingLiteralHashCodeHelper(parameters);
+                        return dnfClause.hashCodeWithSubstitution(helper);
+                }
+        }
+}
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/FunctionalDependency.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/FunctionalDependency.java
index b00b2cb7..aef07ee3 100644
--- a/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/FunctionalDependency.java
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/FunctionalDependency.java
@@ -5,6 +5,8 @@
  */
 package tools.refinery.store.query.dnf;
 
+import tools.refinery.store.query.InvalidQueryException;
+
 import java.util.HashSet;
 import java.util.Set;
 
@@ -13,7 +15,7 @@ public record FunctionalDependency<T>(Set<T> forEach, Set<T> unique) {
                 var uniqueForEach = new HashSet<>(unique);
                 uniqueForEach.retainAll(forEach);
                 if (!uniqueForEach.isEmpty()) {
-                        throw new IllegalArgumentException("Variables %s appear on both sides of the functional dependency"
+                        throw new InvalidQueryException("Variables %s appear on both sides of the functional dependency"
                                         .formatted(uniqueForEach));
                 }
         }
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/FunctionalQuery.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/FunctionalQuery.java
index 5a32b1ba..225f6844 100644
--- a/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/FunctionalQuery.java
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/FunctionalQuery.java
@@ -5,6 +5,7 @@
  */
 package tools.refinery.store.query.dnf;
 
+import tools.refinery.store.query.InvalidQueryException;
 import tools.refinery.store.query.literal.CallPolarity;
 import tools.refinery.store.query.term.Aggregator;
 import tools.refinery.store.query.term.AssignedValue;
@@ -26,14 +27,14 @@ public final class FunctionalQuery<T> extends Query<T> {
                         var parameter = parameters.get(i);
                         var parameterType = parameter.tryGetType();
                         if (parameterType.isPresent()) {
-                                throw new IllegalArgumentException("Expected parameter %s of %s to be a node variable, got %s instead"
+                                throw new InvalidQueryException("Expected parameter %s of %s to be a node variable, got %s instead"
                                                 .formatted(parameter, dnf, parameterType.get().getName()));
                         }
                 }
                 var outputParameter = parameters.get(outputIndex);
                 var outputParameterType = outputParameter.tryGetType();
                 if (outputParameterType.isEmpty() || !outputParameterType.get().equals(type)) {
-                        throw new IllegalArgumentException("Expected parameter %s of %s to be %s, but got %s instead".formatted(
+                        throw new InvalidQueryException("Expected parameter %s of %s to be %s, but got %s instead".formatted(
                                         outputParameter, dnf, type, outputParameterType.map(Class::getName).orElse("node")));
                 }
                 this.type = type;
@@ -54,6 +55,16 @@ public final class FunctionalQuery<T> extends Query<T> {
                 return null;
         }
 
+        @Override
+        protected FunctionalQuery<T> withDnfInternal(Dnf newDnf) {
+                return newDnf.asFunction(type);
+        }
+
+        @Override
+        public FunctionalQuery<T> withDnf(Dnf newDnf) {
+                return (FunctionalQuery<T>) super.withDnf(newDnf);
+        }
+
         public AssignedValue<T> call(List<NodeVariable> arguments) {
                 return targetVariable -> {
                         var argumentsWithTarget = new ArrayList<Variable>(arguments.size() + 1);
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/InvalidClauseException.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/InvalidClauseException.java
new file mode 100644
index 00000000..747574b9
--- /dev/null
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/InvalidClauseException.java
@@ -0,0 +1,35 @@
+/*
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.dnf;
+
+import tools.refinery.store.query.InvalidQueryException;
+
+public class InvalidClauseException extends InvalidQueryException {
+        private final int clauseIndex;
+
+        public InvalidClauseException(int clauseIndex) {
+                this.clauseIndex = clauseIndex;
+        }
+
+        public InvalidClauseException(int clauseIndex, String message) {
+                super(message);
+                this.clauseIndex = clauseIndex;
+        }
+
+        public InvalidClauseException(int clauseIndex, String message, Throwable cause) {
+                super(message, cause);
+                this.clauseIndex = clauseIndex;
+        }
+
+        public InvalidClauseException(int clauseIndex, Throwable cause) {
+                super(cause);
+                this.clauseIndex = clauseIndex;
+        }
+
+        public int getClauseIndex() {
+                return clauseIndex;
+        }
+}
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/Query.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/Query.java
index aaa52ce6..83fe6ccd 100644
--- a/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/Query.java
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/Query.java
@@ -43,6 +43,29 @@ public abstract sealed class Query<T> implements AnyQuery permits FunctionalQuer
 
         public abstract T defaultValue();
 
+        public Query<T> withDnf(Dnf newDnf) {
+                if (dnf.equals(newDnf)) {
+                        return this;
+                }
+                int arity = dnf.arity();
+                if (newDnf.arity() != arity) {
+                        throw new IllegalArgumentException("Arity of %s and %s do not match".formatted(dnf, newDnf));
+                }
+                var parameters = dnf.getParameters();
+                var newParameters = newDnf.getParameters();
+                for (int i = 0; i < arity; i++) {
+                        var parameter = parameters.get(i);
+                        var newParameter = newParameters.get(i);
+                        if (!parameter.matches(newParameter)) {
+                                throw new IllegalArgumentException("Parameter #%d mismatch: %s does not match %s"
+                                                .formatted(i, parameter, newParameter));
+                        }
+                }
+                return withDnfInternal(newDnf);
+        }
+
+        protected abstract Query<T> withDnfInternal(Dnf newDnf);
+
         @Override
         public boolean equals(Object o) {
                 if (this == o) return true;
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/RelationalQuery.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/RelationalQuery.java
index d34a7ace..98f71e11 100644
--- a/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/RelationalQuery.java
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/RelationalQuery.java
@@ -5,6 +5,7 @@
  */
 package tools.refinery.store.query.dnf;
 
+import tools.refinery.store.query.InvalidQueryException;
 import tools.refinery.store.query.literal.CallLiteral;
 import tools.refinery.store.query.literal.CallPolarity;
 import tools.refinery.store.query.term.AssignedValue;
@@ -19,7 +20,7 @@ public final class RelationalQuery extends Query<Boolean> {
                 for (var parameter : dnf.getSymbolicParameters()) {
                         var parameterType = parameter.tryGetType();
                         if (parameterType.isPresent()) {
-                                throw new IllegalArgumentException("Expected parameter %s of %s to be a node variable, got %s instead"
+                                throw new InvalidQueryException("Expected parameter %s of %s to be a node variable, got %s instead"
                                                 .formatted(parameter, dnf, parameterType.get().getName()));
                         }
                 }
@@ -40,6 +41,16 @@ public final class RelationalQuery extends Query<Boolean> {
                 return false;
         }
 
+        @Override
+        protected RelationalQuery withDnfInternal(Dnf newDnf) {
+                return newDnf.asRelation();
+        }
+
+        @Override
+        public RelationalQuery withDnf(Dnf newDnf) {
+                return (RelationalQuery) super.withDnf(newDnf);
+        }
+
         public CallLiteral call(CallPolarity polarity, List<NodeVariable> arguments) {
                 return getDnf().call(polarity, Collections.unmodifiableList(arguments));
         }
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/SymbolicParameter.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/SymbolicParameter.java
index e0d3ba1f..fe9cefcc 100644
--- a/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/SymbolicParameter.java
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/SymbolicParameter.java
@@ -5,6 +5,7 @@
  */
 package tools.refinery.store.query.dnf;
 
+import tools.refinery.store.query.equality.LiteralHashCodeHelper;
 import tools.refinery.store.query.term.Parameter;
 import tools.refinery.store.query.term.ParameterDirection;
 import tools.refinery.store.query.term.Variable;
@@ -23,8 +24,8 @@ public final class SymbolicParameter extends Parameter {
                 return variable;
         }
 
-        public boolean isUnifiable() {
-                return variable.isUnifiable();
+        public int hashCodeWithSubstitution(LiteralHashCodeHelper helper) {
+                return Objects.hash(super.hashCode(), helper.getVariableHashCode(variable));
         }
 
         @Override
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/equality/DeepDnfEqualityChecker.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/equality/DeepDnfEqualityChecker.java
index 1eeb5723..d6171314 100644
--- a/subprojects/store-query/src/main/java/tools/refinery/store/query/equality/DeepDnfEqualityChecker.java
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/equality/DeepDnfEqualityChecker.java
@@ -14,8 +14,7 @@ import tools.refinery.store.util.CycleDetectingMapper;
 import java.util.List;
 
 public class DeepDnfEqualityChecker implements DnfEqualityChecker {
-        private final CycleDetectingMapper<Pair, Boolean> mapper = new CycleDetectingMapper<>(Pair::toString,
-                        this::doCheckEqual);
+        private final CycleDetectingMapper<Pair, Boolean> mapper = new CycleDetectingMapper<>(this::doCheckEqual);
 
         @Override
         public boolean dnfEqual(Dnf left, Dnf right) {
@@ -38,7 +37,7 @@ public class DeepDnfEqualityChecker implements DnfEqualityChecker {
                         return false;
                 }
                 for (int i = 0; i < numClauses; i++) {
-                        var literalEqualityHelper = new LiteralEqualityHelper(this, symbolicParameters,
+                        var literalEqualityHelper = new SubstitutingLiteralEqualityHelper(this, symbolicParameters,
                                         other.getSymbolicParameters());
                         if (!equalsWithSubstitutionRaw(literalEqualityHelper, clauses.get(i), other.getClauses().get(i))) {
                                 return false;
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/equality/DnfEqualityChecker.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/equality/DnfEqualityChecker.java
index 4a8bee3b..e2cfd79b 100644
--- a/subprojects/store-query/src/main/java/tools/refinery/store/query/equality/DnfEqualityChecker.java
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/equality/DnfEqualityChecker.java
@@ -7,7 +7,11 @@ package tools.refinery.store.query.equality;
 
 import tools.refinery.store.query.dnf.Dnf;
 
+import java.util.Objects;
+
 @FunctionalInterface
 public interface DnfEqualityChecker {
+        DnfEqualityChecker DEFAULT = Objects::equals;
+
         boolean dnfEqual(Dnf left, Dnf right);
 }
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/equality/LiteralEqualityHelper.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/equality/LiteralEqualityHelper.java
index 9315fb30..5abc76ce 100644
--- a/subprojects/store-query/src/main/java/tools/refinery/store/query/equality/LiteralEqualityHelper.java
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/equality/LiteralEqualityHelper.java
@@ -6,49 +6,22 @@
 package tools.refinery.store.query.equality;
 
 import tools.refinery.store.query.dnf.Dnf;
-import tools.refinery.store.query.dnf.SymbolicParameter;
 import tools.refinery.store.query.term.Variable;
 
-import java.util.HashMap;
-import java.util.List;
-import java.util.Map;
+import java.util.Objects;
 
-public class LiteralEqualityHelper {
-        private final DnfEqualityChecker dnfEqualityChecker;
-        private final Map<Variable, Variable> leftToRight;
-        private final Map<Variable, Variable> rightToLeft;
-
-        public LiteralEqualityHelper(DnfEqualityChecker dnfEqualityChecker, List<SymbolicParameter> leftParameters,
-                                                                 List<SymbolicParameter> rightParameters) {
-                this.dnfEqualityChecker = dnfEqualityChecker;
-                var arity = leftParameters.size();
-                if (arity != rightParameters.size()) {
-                        throw new IllegalArgumentException("Parameter lists have unequal length");
-                }
-                leftToRight = new HashMap<>(arity);
-                rightToLeft = new HashMap<>(arity);
-                for (int i = 0; i < arity; i++) {
-                        if (!variableEqual(leftParameters.get(i).getVariable(), rightParameters.get(i).getVariable())) {
-                                throw new IllegalArgumentException("Parameter lists cannot be unified: duplicate parameter " + i);
-                        }
+public interface LiteralEqualityHelper extends DnfEqualityChecker {
+        LiteralEqualityHelper DEFAULT = new LiteralEqualityHelper() {
+                @Override
+                public boolean variableEqual(Variable left, Variable right) {
+                        return Objects.equals(left, right);
                 }
-        }
-
-        public boolean dnfEqual(Dnf left, Dnf right) {
-                return dnfEqualityChecker.dnfEqual(left, right);
-        }
 
-        public boolean variableEqual(Variable left, Variable right) {
-                if (checkMapping(leftToRight, left, right) && checkMapping(rightToLeft, right, left)) {
-                        leftToRight.put(left, right);
-                        rightToLeft.put(right, left);
-                        return true;
+                @Override
+                public boolean dnfEqual(Dnf left, Dnf right) {
+                        return DnfEqualityChecker.DEFAULT.dnfEqual(left, right);
                 }
-                return false;
-        }
+        };
 
-        private static boolean checkMapping(Map<Variable, Variable> map, Variable key, Variable expectedValue) {
-                var currentValue = map.get(key);
-                return currentValue == null || currentValue.equals(expectedValue);
-        }
+        boolean variableEqual(Variable left, Variable right);
 }
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/equality/LiteralHashCodeHelper.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/equality/LiteralHashCodeHelper.java
new file mode 100644
index 00000000..5495160a
--- /dev/null
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/equality/LiteralHashCodeHelper.java
@@ -0,0 +1,17 @@
+/*
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.equality;
+
+import tools.refinery.store.query.term.Variable;
+
+import java.util.Objects;
+
+@FunctionalInterface
+public interface LiteralHashCodeHelper {
+        LiteralHashCodeHelper DEFAULT = Objects::hashCode;
+
+        int getVariableHashCode(Variable variable);
+}
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/equality/SubstitutingLiteralEqualityHelper.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/equality/SubstitutingLiteralEqualityHelper.java
new file mode 100644
index 00000000..50a79e07
--- /dev/null
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/equality/SubstitutingLiteralEqualityHelper.java
@@ -0,0 +1,59 @@
+/*
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.equality;
+
+import tools.refinery.store.query.dnf.Dnf;
+import tools.refinery.store.query.dnf.SymbolicParameter;
+import tools.refinery.store.query.term.Variable;
+
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+
+public class SubstitutingLiteralEqualityHelper implements LiteralEqualityHelper {
+        private final DnfEqualityChecker dnfEqualityChecker;
+        private final Map<Variable, Variable> leftToRight;
+        private final Map<Variable, Variable> rightToLeft;
+
+        public SubstitutingLiteralEqualityHelper(DnfEqualityChecker dnfEqualityChecker,
+                                                                                         List<SymbolicParameter> leftParameters,
+                                                                                         List<SymbolicParameter> rightParameters) {
+                this.dnfEqualityChecker = dnfEqualityChecker;
+                var arity = leftParameters.size();
+                if (arity != rightParameters.size()) {
+                        throw new IllegalArgumentException("Parameter lists have unequal length");
+                }
+                leftToRight = new HashMap<>(arity);
+                rightToLeft = new HashMap<>(arity);
+                for (int i = 0; i < arity; i++) {
+                        if (!variableEqual(leftParameters.get(i).getVariable(), rightParameters.get(i).getVariable())) {
+                                throw new IllegalArgumentException("Parameter lists cannot be unified: duplicate parameter " + i);
+                        }
+                }
+        }
+
+        @Override
+        public boolean dnfEqual(Dnf left, Dnf right) {
+                return dnfEqualityChecker.dnfEqual(left, right);
+        }
+
+        @Override
+        public boolean variableEqual(Variable left, Variable right) {
+                if (left.tryGetType().equals(right.tryGetType()) &&
+                                checkMapping(leftToRight, left, right) &&
+                                checkMapping(rightToLeft, right, left)) {
+                        leftToRight.put(left, right);
+                        rightToLeft.put(right, left);
+                        return true;
+                }
+                return false;
+        }
+
+        private static boolean checkMapping(Map<Variable, Variable> map, Variable key, Variable expectedValue) {
+                var currentValue = map.get(key);
+                return currentValue == null || currentValue.equals(expectedValue);
+        }
+}
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/equality/SubstitutingLiteralHashCodeHelper.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/equality/SubstitutingLiteralHashCodeHelper.java
new file mode 100644
index 00000000..754f6976
--- /dev/null
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/equality/SubstitutingLiteralHashCodeHelper.java
@@ -0,0 +1,42 @@
+/*
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.equality;
+
+import tools.refinery.store.query.dnf.SymbolicParameter;
+import tools.refinery.store.query.term.Variable;
+
+import java.util.LinkedHashMap;
+import java.util.List;
+import java.util.Map;
+
+public class SubstitutingLiteralHashCodeHelper implements LiteralHashCodeHelper {
+        private final Map<Variable, Integer> assignedHashCodes = new LinkedHashMap<>();
+
+        // 0 is for {@code null}, so we start with 1.
+        private int next = 1;
+
+        public SubstitutingLiteralHashCodeHelper() {
+                this(List.of());
+        }
+
+        public SubstitutingLiteralHashCodeHelper(List<SymbolicParameter> parameters) {
+                for (var parameter : parameters) {
+                        getVariableHashCode(parameter.getVariable());
+                }
+        }
+
+        @Override
+        public int getVariableHashCode(Variable variable) {
+                if (variable == null) {
+                        return 0;
+                }
+                return assignedHashCodes.computeIfAbsent(variable, key -> {
+                        int sequenceNumber = next;
+                        next++;
+                        return variable.hashCodeWithSubstitution(sequenceNumber);
+                });
+        }
+}
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/AbstractCallLiteral.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/AbstractCallLiteral.java
index 8ef8e8b4..0e99d441 100644
--- a/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/AbstractCallLiteral.java
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/AbstractCallLiteral.java
@@ -6,14 +6,18 @@
 package tools.refinery.store.query.literal;
 
 import tools.refinery.store.query.Constraint;
+import tools.refinery.store.query.InvalidQueryException;
 import tools.refinery.store.query.equality.LiteralEqualityHelper;
+import tools.refinery.store.query.equality.LiteralHashCodeHelper;
 import tools.refinery.store.query.substitution.Substitution;
 import tools.refinery.store.query.term.ParameterDirection;
 import tools.refinery.store.query.term.Variable;
 
 import java.util.*;
 
-public abstract class AbstractCallLiteral implements Literal {
+// {@link Object#equals(Object)} is implemented by {@link AbstractLiteral}.
+@SuppressWarnings("squid:S2160")
+public abstract class AbstractCallLiteral extends AbstractLiteral {
         private final Constraint target;
         private final List<Variable> arguments;
         private final Set<Variable> inArguments;
@@ -24,7 +28,7 @@ public abstract class AbstractCallLiteral implements Literal {
         protected AbstractCallLiteral(Constraint target, List<Variable> arguments) {
                 int arity = target.arity();
                 if (arguments.size() != arity) {
-                        throw new IllegalArgumentException("%s needs %d arguments, but got %s".formatted(target.name(),
+                        throw new InvalidQueryException("%s needs %d arguments, but got %s".formatted(target.name(),
                                         target.arity(), arguments.size()));
                 }
                 this.target = target;
@@ -36,21 +40,17 @@ public abstract class AbstractCallLiteral implements Literal {
                         var argument = arguments.get(i);
                         var parameter = parameters.get(i);
                         if (!parameter.isAssignable(argument)) {
-                                throw new IllegalArgumentException("Argument %d of %s is not assignable to parameter %s"
+                                throw new InvalidQueryException("Argument %d of %s is not assignable to parameter %s"
                                                 .formatted(i, target, parameter));
                         }
                         switch (parameter.getDirection()) {
                         case IN -> {
-                                if (mutableOutArguments.remove(argument)) {
-                                        checkInOutUnifiable(argument);
-                                }
+                                mutableOutArguments.remove(argument);
                                 mutableInArguments.add(argument);
                         }
                         case OUT -> {
-                                if (mutableInArguments.contains(argument)) {
-                                        checkInOutUnifiable(argument);
-                                } else if (!mutableOutArguments.add(argument)) {
-                                        checkDuplicateOutUnifiable(argument);
+                                if (!mutableInArguments.contains(argument)) {
+                                        mutableOutArguments.add(argument);
                                 }
                         }
                         }
@@ -59,19 +59,6 @@ public abstract class AbstractCallLiteral implements Literal {
                 outArguments = Collections.unmodifiableSet(mutableOutArguments);
         }
 
-        private static void checkInOutUnifiable(Variable argument) {
-                if (!argument.isUnifiable()) {
-                        throw new IllegalArgumentException("Argument %s cannot appear with both %s and %s direction"
-                                        .formatted(argument, ParameterDirection.IN, ParameterDirection.OUT));
-                }
-        }
-
-        private static void checkDuplicateOutUnifiable(Variable argument) {
-                if (!argument.isUnifiable()) {
-                        throw new IllegalArgumentException("Argument %s cannot be bound multiple times".formatted(argument));
-                }
-        }
-
         public Constraint getTarget() {
                 return target;
         }
@@ -110,9 +97,18 @@ public abstract class AbstractCallLiteral implements Literal {
 
         protected abstract Literal doSubstitute(Substitution substitution, List<Variable> substitutedArguments);
 
+        public AbstractCallLiteral withTarget(Constraint newTarget) {
+                if (Objects.equals(target, newTarget)) {
+                        return this;
+                }
+                return withArguments(newTarget, arguments);
+        }
+
+        public abstract AbstractCallLiteral withArguments(Constraint newTarget, List<Variable> newArguments);
+
         @Override
         public boolean equalsWithSubstitution(LiteralEqualityHelper helper, Literal other) {
-                if (other == null || getClass() != other.getClass()) {
+                if (!super.equalsWithSubstitution(helper, other)) {
                         return false;
                 }
                 var otherCallLiteral = (AbstractCallLiteral) other;
@@ -129,15 +125,11 @@ public abstract class AbstractCallLiteral implements Literal {
         }
 
         @Override
-        public boolean equals(Object o) {
-                if (this == o) return true;
-                if (o == null || getClass() != o.getClass()) return false;
-                AbstractCallLiteral that = (AbstractCallLiteral) o;
-                return target.equals(that.target) && arguments.equals(that.arguments);
-        }
-
-        @Override
-        public int hashCode() {
-                return Objects.hash(getClass(), target, arguments);
+        public int hashCodeWithSubstitution(LiteralHashCodeHelper helper) {
+                int result = super.hashCodeWithSubstitution(helper) * 31 + target.hashCode();
+                for (var argument : arguments) {
+                        result = result * 31 + helper.getVariableHashCode(argument);
+                }
+                return result;
         }
 }
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/AbstractCountLiteral.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/AbstractCountLiteral.java
new file mode 100644
index 00000000..9bb572c0
--- /dev/null
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/AbstractCountLiteral.java
@@ -0,0 +1,107 @@
+/*
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.literal;
+
+import tools.refinery.store.query.Constraint;
+import tools.refinery.store.query.InvalidQueryException;
+import tools.refinery.store.query.equality.LiteralEqualityHelper;
+import tools.refinery.store.query.equality.LiteralHashCodeHelper;
+import tools.refinery.store.query.term.ConstantTerm;
+import tools.refinery.store.query.term.DataVariable;
+import tools.refinery.store.query.term.Variable;
+
+import java.util.List;
+import java.util.Objects;
+import java.util.Set;
+
+// {@link Object#equals(Object)} is implemented by {@link AbstractLiteral}.
+@SuppressWarnings("squid:S2160")
+public abstract class AbstractCountLiteral<T> extends AbstractCallLiteral {
+        private final Class<T> resultType;
+        private final DataVariable<T> resultVariable;
+
+        protected AbstractCountLiteral(Class<T> resultType, DataVariable<T> resultVariable, Constraint target,
+                                                                   List<Variable> arguments) {
+                super(target, arguments);
+                if (!resultVariable.getType().equals(resultType)) {
+                        throw new InvalidQueryException("Count result variable %s must be of type %s, got %s instead".formatted(
+                                        resultVariable, resultType, resultVariable.getType().getName()));
+                }
+                if (arguments.contains(resultVariable)) {
+                        throw new InvalidQueryException("Count result variable %s must not appear in the argument list"
+                                        .formatted(resultVariable));
+                }
+                this.resultType = resultType;
+                this.resultVariable = resultVariable;
+        }
+
+        public Class<T> getResultType() {
+                return resultType;
+        }
+
+        public DataVariable<T> getResultVariable() {
+                return resultVariable;
+        }
+
+        @Override
+        public Set<Variable> getOutputVariables() {
+                return Set.of(resultVariable);
+        }
+
+        protected abstract T zero();
+
+        protected abstract T one();
+
+        @Override
+        public Literal reduce() {
+                var reduction = getTarget().getReduction();
+                return switch (reduction) {
+                        case ALWAYS_FALSE -> getResultVariable().assign(new ConstantTerm<>(resultType, zero()));
+                        // The only way a constant {@code true} predicate can be called in a negative position is to have all of
+                        // its arguments bound as input variables. Thus, there will only be a single match.
+                        case ALWAYS_TRUE -> getResultVariable().assign(new ConstantTerm<>(resultType, one()));
+                        case NOT_REDUCIBLE -> this;
+                };
+        }
+
+        @Override
+        public boolean equalsWithSubstitution(LiteralEqualityHelper helper, Literal other) {
+                if (!super.equalsWithSubstitution(helper, other)) {
+                        return false;
+                }
+                var otherCountLiteral = (AbstractCountLiteral<?>) other;
+                return Objects.equals(resultType, otherCountLiteral.resultType) &&
+                                helper.variableEqual(resultVariable, otherCountLiteral.resultVariable);
+        }
+
+        @Override
+        public int hashCodeWithSubstitution(LiteralHashCodeHelper helper) {
+                return Objects.hash(super.hashCodeWithSubstitution(helper), resultType,
+                                helper.getVariableHashCode(resultVariable));
+        }
+
+        protected abstract String operatorName();
+
+        @Override
+        public String toString() {
+                var builder = new StringBuilder();
+                builder.append(resultVariable);
+                builder.append(" is ");
+                builder.append(operatorName());
+                builder.append(' ');
+                builder.append(getTarget().toReferenceString());
+                builder.append('(');
+                var argumentIterator = getArguments().iterator();
+                if (argumentIterator.hasNext()) {
+                        builder.append(argumentIterator.next());
+                        while (argumentIterator.hasNext()) {
+                                builder.append(", ").append(argumentIterator.next());
+                        }
+                }
+                builder.append(')');
+                return builder.toString();
+        }
+}
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/AbstractLiteral.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/AbstractLiteral.java
new file mode 100644
index 00000000..7d3cabd7
--- /dev/null
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/AbstractLiteral.java
@@ -0,0 +1,34 @@
+/*
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.literal;
+
+import tools.refinery.store.query.equality.LiteralEqualityHelper;
+import tools.refinery.store.query.equality.LiteralHashCodeHelper;
+
+public abstract class AbstractLiteral implements Literal {
+        @Override
+        public boolean equalsWithSubstitution(LiteralEqualityHelper helper, Literal other) {
+                return other != null && getClass() == other.getClass();
+        }
+
+        @Override
+        public int hashCodeWithSubstitution(LiteralHashCodeHelper helper) {
+                return getClass().hashCode();
+        }
+
+        @Override
+        public boolean equals(Object o) {
+                if (this == o) return true;
+                if (o == null || getClass() != o.getClass()) return false;
+                AbstractLiteral that = (AbstractLiteral) o;
+                return equalsWithSubstitution(LiteralEqualityHelper.DEFAULT, that);
+        }
+
+        @Override
+        public int hashCode() {
+                return hashCodeWithSubstitution(LiteralHashCodeHelper.DEFAULT);
+        }
+}
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/AggregationLiteral.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/AggregationLiteral.java
index 3a5eb5c7..e3acfacc 100644
--- a/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/AggregationLiteral.java
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/AggregationLiteral.java
@@ -6,7 +6,9 @@
 package tools.refinery.store.query.literal;
 
 import tools.refinery.store.query.Constraint;
+import tools.refinery.store.query.InvalidQueryException;
 import tools.refinery.store.query.equality.LiteralEqualityHelper;
+import tools.refinery.store.query.equality.LiteralHashCodeHelper;
 import tools.refinery.store.query.substitution.Substitution;
 import tools.refinery.store.query.term.*;
 
@@ -14,6 +16,8 @@ import java.util.List;
 import java.util.Objects;
 import java.util.Set;
 
+// {@link Object#equals(Object)} is implemented by {@link AbstractLiteral}.
+@SuppressWarnings("squid:S2160")
 public class AggregationLiteral<R, T> extends AbstractCallLiteral {
         private final DataVariable<R> resultVariable;
         private final DataVariable<T> inputVariable;
@@ -23,19 +27,19 @@ public class AggregationLiteral<R, T> extends AbstractCallLiteral {
                                                           DataVariable<T> inputVariable, Constraint target, List<Variable> arguments) {
                 super(target, arguments);
                 if (!inputVariable.getType().equals(aggregator.getInputType())) {
-                        throw new IllegalArgumentException("Input variable %s must of type %s, got %s instead".formatted(
+                        throw new InvalidQueryException("Input variable %s must of type %s, got %s instead".formatted(
                                         inputVariable, aggregator.getInputType().getName(), inputVariable.getType().getName()));
                 }
                 if (!getArgumentsOfDirection(ParameterDirection.OUT).contains(inputVariable)) {
-                        throw new IllegalArgumentException("Input variable %s must be bound with direction %s in the argument list"
+                        throw new InvalidQueryException("Input variable %s must be bound with direction %s in the argument list"
                                         .formatted(inputVariable, ParameterDirection.OUT));
                 }
                 if (!resultVariable.getType().equals(aggregator.getResultType())) {
-                        throw new IllegalArgumentException("Result variable %s must of type %s, got %s instead".formatted(
+                        throw new InvalidQueryException("Result variable %s must of type %s, got %s instead".formatted(
                                         resultVariable, aggregator.getResultType().getName(), resultVariable.getType().getName()));
                 }
                 if (arguments.contains(resultVariable)) {
-                        throw new IllegalArgumentException("Result variable %s must not appear in the argument list".formatted(
+                        throw new InvalidQueryException("Result variable %s must not appear in the argument list".formatted(
                                         resultVariable));
                 }
                 this.resultVariable = resultVariable;
@@ -63,7 +67,7 @@ public class AggregationLiteral<R, T> extends AbstractCallLiteral {
         @Override
         public Set<Variable> getInputVariables(Set<? extends Variable> positiveVariablesInClause) {
                 if (positiveVariablesInClause.contains(inputVariable)) {
-                        throw new IllegalArgumentException("Aggregation variable %s must not be bound".formatted(inputVariable));
+                        throw new InvalidQueryException("Aggregation variable %s must not be bound".formatted(inputVariable));
                 }
                 return super.getInputVariables(positiveVariablesInClause);
         }
@@ -77,7 +81,7 @@ public class AggregationLiteral<R, T> extends AbstractCallLiteral {
                                 yield emptyValue == null ? BooleanLiteral.FALSE :
                                                 resultVariable.assign(new ConstantTerm<>(resultVariable.getType(), emptyValue));
                         }
-                        case ALWAYS_TRUE -> throw new IllegalArgumentException("Trying to aggregate over an infinite set");
+                        case ALWAYS_TRUE -> throw new InvalidQueryException("Trying to aggregate over an infinite set");
                         case NOT_REDUCIBLE -> this;
                 };
         }
@@ -89,6 +93,11 @@ public class AggregationLiteral<R, T> extends AbstractCallLiteral {
         }
 
         @Override
+        public AbstractCallLiteral withArguments(Constraint newTarget, List<Variable> newArguments) {
+                return new AggregationLiteral<>(resultVariable, aggregator, inputVariable, newTarget, newArguments);
+        }
+
+        @Override
         public boolean equalsWithSubstitution(LiteralEqualityHelper helper, Literal other) {
                 if (!super.equalsWithSubstitution(helper, other)) {
                         return false;
@@ -100,18 +109,9 @@ public class AggregationLiteral<R, T> extends AbstractCallLiteral {
         }
 
         @Override
-        public boolean equals(Object o) {
-                if (this == o) return true;
-                if (o == null || getClass() != o.getClass()) return false;
-                if (!super.equals(o)) return false;
-                AggregationLiteral<?, ?> that = (AggregationLiteral<?, ?>) o;
-                return resultVariable.equals(that.resultVariable) && inputVariable.equals(that.inputVariable) &&
-                                aggregator.equals(that.aggregator);
-        }
-
-        @Override
-        public int hashCode() {
-                return Objects.hash(super.hashCode(), resultVariable, inputVariable, aggregator);
+        public int hashCodeWithSubstitution(LiteralHashCodeHelper helper) {
+                return Objects.hash(super.hashCodeWithSubstitution(helper), helper.getVariableHashCode(resultVariable),
+                                helper.getVariableHashCode(inputVariable), aggregator);
         }
 
         @Override
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/AssignLiteral.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/AssignLiteral.java
index dbf999a2..dadf487f 100644
--- a/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/AssignLiteral.java
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/AssignLiteral.java
@@ -5,7 +5,9 @@
  */
 package tools.refinery.store.query.literal;
 
+import tools.refinery.store.query.InvalidQueryException;
 import tools.refinery.store.query.equality.LiteralEqualityHelper;
+import tools.refinery.store.query.equality.LiteralHashCodeHelper;
 import tools.refinery.store.query.substitution.Substitution;
 import tools.refinery.store.query.term.DataVariable;
 import tools.refinery.store.query.term.Term;
@@ -15,17 +17,32 @@ import java.util.Collections;
 import java.util.Objects;
 import java.util.Set;
 
-public record AssignLiteral<T>(DataVariable<T> variable, Term<T> term) implements Literal {
-        public AssignLiteral {
+// {@link Object#equals(Object)} is implemented by {@link AbstractLiteral}.
+@SuppressWarnings("squid:S2160")
+public class AssignLiteral<T> extends AbstractLiteral {
+        private final DataVariable<T> variable;
+        private final Term<T> term;
+
+        public AssignLiteral(DataVariable<T> variable, Term<T> term) {
                 if (!term.getType().equals(variable.getType())) {
-                        throw new IllegalArgumentException("Term %s must be of type %s, got %s instead".formatted(
+                        throw new InvalidQueryException("Term %s must be of type %s, got %s instead".formatted(
                                         term, variable.getType().getName(), term.getType().getName()));
                 }
                 var inputVariables = term.getInputVariables();
                 if (inputVariables.contains(variable)) {
-                        throw new IllegalArgumentException("Result variable %s must not appear in the term %s".formatted(
+                        throw new InvalidQueryException("Result variable %s must not appear in the term %s".formatted(
                                         variable, term));
                 }
+                this.variable = variable;
+                this.term = term;
+        }
+
+        public DataVariable<T> getVariable() {
+                return variable;
+        }
+
+        public Term<T> getTerm() {
+                return term;
         }
 
         @Override
@@ -53,27 +70,19 @@ public record AssignLiteral<T>(DataVariable<T> variable, Term<T> term) implement
                 if (other == null || getClass() != other.getClass()) {
                         return false;
                 }
-                var otherLetLiteral = (AssignLiteral<?>) other;
-                return helper.variableEqual(variable, otherLetLiteral.variable) && term.equalsWithSubstitution(helper,
-                                otherLetLiteral.term);
-        }
-
-        @Override
-        public String toString() {
-                return "%s is (%s)".formatted(variable, term);
+                var otherAssignLiteral = (AssignLiteral<?>) other;
+                return helper.variableEqual(variable, otherAssignLiteral.variable) &&
+                                term.equalsWithSubstitution(helper, otherAssignLiteral.term);
         }
 
         @Override
-        public boolean equals(Object obj) {
-                if (obj == this) return true;
-                if (obj == null || obj.getClass() != this.getClass()) return false;
-                var that = (AssignLiteral<?>) obj;
-                return Objects.equals(this.variable, that.variable) &&
-                                Objects.equals(this.term, that.term);
+        public int hashCodeWithSubstitution(LiteralHashCodeHelper helper) {
+                return Objects.hash(super.hashCodeWithSubstitution(helper), helper.getVariableHashCode(variable),
+                                term.hashCodeWithSubstitution(helper));
         }
 
         @Override
-        public int hashCode() {
-                return Objects.hash(getClass(), variable, term);
+        public String toString() {
+                return "%s is (%s)".formatted(variable, term);
         }
 }
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/BooleanLiteral.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/BooleanLiteral.java
index f312d202..6cd320da 100644
--- a/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/BooleanLiteral.java
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/BooleanLiteral.java
@@ -6,6 +6,7 @@
 package tools.refinery.store.query.literal;
 
 import tools.refinery.store.query.equality.LiteralEqualityHelper;
+import tools.refinery.store.query.equality.LiteralHashCodeHelper;
 import tools.refinery.store.query.substitution.Substitution;
 import tools.refinery.store.query.term.Variable;
 
@@ -53,6 +54,11 @@ public enum BooleanLiteral implements CanNegate<BooleanLiteral> {
         }
 
         @Override
+        public int hashCodeWithSubstitution(LiteralHashCodeHelper helper) {
+                return hashCode();
+        }
+
+        @Override
         public String toString() {
                 return Boolean.toString(value);
         }
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/CallLiteral.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/CallLiteral.java
index 29772aee..2d0e4e97 100644
--- a/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/CallLiteral.java
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/CallLiteral.java
@@ -6,13 +6,17 @@
 package tools.refinery.store.query.literal;
 
 import tools.refinery.store.query.Constraint;
+import tools.refinery.store.query.InvalidQueryException;
 import tools.refinery.store.query.equality.LiteralEqualityHelper;
+import tools.refinery.store.query.equality.LiteralHashCodeHelper;
 import tools.refinery.store.query.substitution.Substitution;
 import tools.refinery.store.query.term.ParameterDirection;
 import tools.refinery.store.query.term.Variable;
 
 import java.util.*;
 
+// {@link Object#equals(Object)} is implemented by {@link AbstractLiteral}.
+@SuppressWarnings("squid:S2160")
 public final class CallLiteral extends AbstractCallLiteral implements CanNegate<CallLiteral> {
         private final CallPolarity polarity;
 
@@ -22,10 +26,14 @@ public final class CallLiteral extends AbstractCallLiteral implements CanNegate<
                 int arity = target.arity();
                 if (polarity.isTransitive()) {
                         if (arity != 2) {
-                                throw new IllegalArgumentException("Transitive closures can only take binary relations");
+                                throw new InvalidQueryException("Transitive closures can only take binary relations");
                         }
                         if (parameters.get(0).isDataVariable() || parameters.get(1).isDataVariable()) {
-                                throw new IllegalArgumentException("Transitive closures can only be computed over nodes");
+                                throw new InvalidQueryException("Transitive closures can only be computed over nodes");
+                        }
+                        if (parameters.get(0).getDirection() != ParameterDirection.OUT ||
+                                        parameters.get(1).getDirection() != ParameterDirection.OUT) {
+                                throw new InvalidQueryException("Transitive closures cannot take input parameters");
                         }
                 }
                 this.polarity = polarity;
@@ -85,22 +93,18 @@ public final class CallLiteral extends AbstractCallLiteral implements CanNegate<
         }
 
         @Override
-        public CallLiteral negate() {
-                return new CallLiteral(polarity.negate(), getTarget(), getArguments());
+        public int hashCodeWithSubstitution(LiteralHashCodeHelper helper) {
+                return Objects.hash(super.hashCodeWithSubstitution(helper), polarity);
         }
 
         @Override
-        public boolean equals(Object o) {
-                if (this == o) return true;
-                if (o == null || getClass() != o.getClass()) return false;
-                if (!super.equals(o)) return false;
-                CallLiteral that = (CallLiteral) o;
-                return polarity == that.polarity;
+        public CallLiteral negate() {
+                return new CallLiteral(polarity.negate(), getTarget(), getArguments());
         }
 
         @Override
-        public int hashCode() {
-                return Objects.hash(super.hashCode(), polarity);
+        public AbstractCallLiteral withArguments(Constraint newTarget, List<Variable> newArguments) {
+                return new CallLiteral(polarity, newTarget, newArguments);
         }
 
         @Override
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/CallPolarity.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/CallPolarity.java
index ca70b0fd..716c7109 100644
--- a/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/CallPolarity.java
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/CallPolarity.java
@@ -5,6 +5,8 @@
  */
 package tools.refinery.store.query.literal;
 
+import tools.refinery.store.query.InvalidQueryException;
+
 public enum CallPolarity {
         POSITIVE(true, false),
         NEGATIVE(false, false),
@@ -31,7 +33,7 @@ public enum CallPolarity {
                 return switch (this) {
                         case POSITIVE -> NEGATIVE;
                         case NEGATIVE -> POSITIVE;
-                        case TRANSITIVE -> throw new IllegalArgumentException("Transitive polarity cannot be negated");
+                        case TRANSITIVE -> throw new InvalidQueryException("Transitive polarity cannot be negated");
                 };
         }
 }
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/AssumeLiteral.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/CheckLiteral.java
index 1ca04c77..dfedd2cb 100644
--- a/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/AssumeLiteral.java
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/CheckLiteral.java
@@ -5,22 +5,35 @@
  */
 package tools.refinery.store.query.literal;
 
+import tools.refinery.store.query.InvalidQueryException;
 import tools.refinery.store.query.equality.LiteralEqualityHelper;
+import tools.refinery.store.query.equality.LiteralHashCodeHelper;
 import tools.refinery.store.query.substitution.Substitution;
 import tools.refinery.store.query.term.ConstantTerm;
 import tools.refinery.store.query.term.Term;
 import tools.refinery.store.query.term.Variable;
+import tools.refinery.store.query.term.bool.BoolNotTerm;
+import tools.refinery.store.query.term.bool.BoolTerms;
 
 import java.util.Collections;
 import java.util.Objects;
 import java.util.Set;
 
-public record AssumeLiteral(Term<Boolean> term) implements Literal {
-        public AssumeLiteral {
+// {@link Object#equals(Object)} is implemented by {@link AbstractLiteral}.
+@SuppressWarnings("squid:S2160")
+public class CheckLiteral extends AbstractLiteral implements CanNegate<CheckLiteral> {
+        private final Term<Boolean> term;
+
+        public CheckLiteral(Term<Boolean> term) {
                 if (!term.getType().equals(Boolean.class)) {
-                        throw new IllegalArgumentException("Term %s must be of type %s, got %s instead".formatted(
+                        throw new InvalidQueryException("Term %s must be of type %s, got %s instead".formatted(
                                         term, Boolean.class.getName(), term.getType().getName()));
                 }
+                this.term = term;
+        }
+
+        public Term<Boolean> getTerm() {
+                return term;
         }
 
         @Override
@@ -38,10 +51,17 @@ public record AssumeLiteral(Term<Boolean> term) implements Literal {
                 return Set.of();
         }
 
-
         @Override
         public Literal substitute(Substitution substitution) {
-                return new AssumeLiteral(term.substitute(substitution));
+                return new CheckLiteral(term.substitute(substitution));
+        }
+
+        @Override
+        public CheckLiteral negate() {
+                if (term instanceof BoolNotTerm notTerm) {
+                        return new CheckLiteral(notTerm.getBody());
+                }
+                return new CheckLiteral(BoolTerms.not(term));
         }
 
         @Override
@@ -49,11 +69,16 @@ public record AssumeLiteral(Term<Boolean> term) implements Literal {
                 if (other == null || getClass() != other.getClass()) {
                         return false;
                 }
-                var otherAssumeLiteral = (AssumeLiteral) other;
+                var otherAssumeLiteral = (CheckLiteral) other;
                 return term.equalsWithSubstitution(helper, otherAssumeLiteral.term);
         }
 
         @Override
+        public int hashCodeWithSubstitution(LiteralHashCodeHelper helper) {
+                return Objects.hash(super.hashCodeWithSubstitution(helper), term.hashCodeWithSubstitution(helper));
+        }
+
+        @Override
         public Literal reduce() {
                 if (term instanceof ConstantTerm<Boolean> constantTerm) {
                         // Return {@link BooleanLiteral#FALSE} for {@code false} or {@code null} literals.
@@ -67,17 +92,4 @@ public record AssumeLiteral(Term<Boolean> term) implements Literal {
         public String toString() {
                 return "(%s)".formatted(term);
         }
-
-        @Override
-        public boolean equals(Object obj) {
-                if (obj == this) return true;
-                if (obj == null || obj.getClass() != this.getClass()) return false;
-                var that = (AssumeLiteral) obj;
-                return Objects.equals(this.term, that.term);
-        }
-
-        @Override
-        public int hashCode() {
-                return Objects.hash(getClass(), term);
-        }
 }
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/Connectivity.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/Connectivity.java
new file mode 100644
index 00000000..a058094d
--- /dev/null
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/Connectivity.java
@@ -0,0 +1,18 @@
+/*
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.literal;
+
+import java.util.Locale;
+
+public enum Connectivity {
+        WEAK,
+        STRONG;
+
+        @Override
+        public String toString() {
+                return name().toLowerCase(Locale.ROOT);
+        }
+}
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/ConstantLiteral.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/ConstantLiteral.java
index 73545620..d83bd584 100644
--- a/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/ConstantLiteral.java
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/ConstantLiteral.java
@@ -6,6 +6,7 @@
 package tools.refinery.store.query.literal;
 
 import tools.refinery.store.query.equality.LiteralEqualityHelper;
+import tools.refinery.store.query.equality.LiteralHashCodeHelper;
 import tools.refinery.store.query.substitution.Substitution;
 import tools.refinery.store.query.term.NodeVariable;
 import tools.refinery.store.query.term.Variable;
@@ -13,7 +14,24 @@ import tools.refinery.store.query.term.Variable;
 import java.util.Objects;
 import java.util.Set;
 
-public record ConstantLiteral(NodeVariable variable, int nodeId) implements Literal {
+public class ConstantLiteral extends AbstractLiteral {
+        private final NodeVariable variable;
+        private final int nodeId;
+
+        public ConstantLiteral(NodeVariable variable, int nodeId) {
+                this.variable = variable;
+                this.nodeId = nodeId;
+        }
+
+        public NodeVariable getVariable() {
+                return variable;
+        }
+
+        public int getNodeId() {
+                return nodeId;
+        }
+
+
         @Override
         public Set<Variable> getOutputVariables() {
                 return Set.of(variable);
@@ -43,23 +61,13 @@ public record ConstantLiteral(NodeVariable variable, int nodeId) implements Lite
                 return helper.variableEqual(variable, otherConstantLiteral.variable) && nodeId == otherConstantLiteral.nodeId;
         }
 
-
-        @Override
-        public String toString() {
-                return "%s === @Constant %d".formatted(variable, nodeId);
-        }
-
         @Override
-        public boolean equals(Object obj) {
-                if (obj == this) return true;
-                if (obj == null || obj.getClass() != this.getClass()) return false;
-                var that = (ConstantLiteral) obj;
-                return Objects.equals(this.variable, that.variable) &&
-                                this.nodeId == that.nodeId;
+        public int hashCodeWithSubstitution(LiteralHashCodeHelper helper) {
+                return Objects.hash(super.hashCodeWithSubstitution(helper), helper.getVariableHashCode(variable), nodeId);
         }
 
         @Override
-        public int hashCode() {
-                return Objects.hash(getClass(), variable, nodeId);
+        public String toString() {
+                return "%s === @Constant %d".formatted(variable, nodeId);
         }
 }
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/CountLiteral.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/CountLiteral.java
index 4d4749c8..3d078d89 100644
--- a/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/CountLiteral.java
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/CountLiteral.java
@@ -6,96 +6,40 @@
 package tools.refinery.store.query.literal;
 
 import tools.refinery.store.query.Constraint;
-import tools.refinery.store.query.equality.LiteralEqualityHelper;
 import tools.refinery.store.query.substitution.Substitution;
 import tools.refinery.store.query.term.DataVariable;
 import tools.refinery.store.query.term.Variable;
-import tools.refinery.store.query.term.int_.IntTerms;
 
 import java.util.List;
-import java.util.Objects;
-import java.util.Set;
-
-public class CountLiteral extends AbstractCallLiteral {
-        private final DataVariable<Integer> resultVariable;
 
+public class CountLiteral extends AbstractCountLiteral<Integer> {
         public CountLiteral(DataVariable<Integer> resultVariable, Constraint target, List<Variable> arguments) {
-                super(target, arguments);
-                if (!resultVariable.getType().equals(Integer.class)) {
-                        throw new IllegalArgumentException("Count result variable %s must be of type %s, got %s instead".formatted(
-                                        resultVariable, Integer.class.getName(), resultVariable.getType().getName()));
-                }
-                if (arguments.contains(resultVariable)) {
-                        throw new IllegalArgumentException("Count result variable %s must not appear in the argument list"
-                                        .formatted(resultVariable));
-                }
-                this.resultVariable = resultVariable;
-        }
-
-        public DataVariable<Integer> getResultVariable() {
-                return resultVariable;
+                super(Integer.class, resultVariable, target, arguments);
         }
 
         @Override
-        public Set<Variable> getOutputVariables() {
-                return Set.of(resultVariable);
+        protected Integer zero() {
+                return 0;
         }
 
         @Override
-        public Literal reduce() {
-                var reduction = getTarget().getReduction();
-                return switch (reduction) {
-                        case ALWAYS_FALSE -> getResultVariable().assign(IntTerms.constant(0));
-                        // The only way a constant {@code true} predicate can be called in a negative position is to have all of
-                        // its arguments bound as input variables. Thus, there will only be a single match.
-                        case ALWAYS_TRUE -> getResultVariable().assign(IntTerms.constant(1));
-                        case NOT_REDUCIBLE -> this;
-                };
+        protected Integer one() {
+                return 1;
         }
 
         @Override
         protected Literal doSubstitute(Substitution substitution, List<Variable> substitutedArguments) {
-                return new CountLiteral(substitution.getTypeSafeSubstitute(resultVariable), getTarget(), substitutedArguments);
-        }
-
-        @Override
-        public boolean equalsWithSubstitution(LiteralEqualityHelper helper, Literal other) {
-                if (!super.equalsWithSubstitution(helper, other)) {
-                        return false;
-                }
-                var otherCountLiteral = (CountLiteral) other;
-                return helper.variableEqual(resultVariable, otherCountLiteral.resultVariable);
-        }
-
-        @Override
-        public boolean equals(Object o) {
-                if (this == o) return true;
-                if (o == null || getClass() != o.getClass()) return false;
-                if (!super.equals(o)) return false;
-                CountLiteral that = (CountLiteral) o;
-                return resultVariable.equals(that.resultVariable);
+                return new CountLiteral(substitution.getTypeSafeSubstitute(getResultVariable()), getTarget(),
+                                substitutedArguments);
         }
 
         @Override
-        public int hashCode() {
-                return Objects.hash(super.hashCode(), resultVariable);
+        public AbstractCallLiteral withArguments(Constraint newTarget, List<Variable> newArguments) {
+                return new CountLiteral(getResultVariable(), newTarget, newArguments);
         }
 
         @Override
-        public String toString() {
-                var builder = new StringBuilder();
-                builder.append(resultVariable);
-                builder.append(" is count ");
-                builder.append(getTarget().toReferenceString());
-                builder.append("(");
-                var argumentIterator = getArguments().iterator();
-                if (argumentIterator.hasNext()) {
-                        builder.append(argumentIterator.next());
-                        while (argumentIterator.hasNext()) {
-                                builder.append(", ").append(argumentIterator.next());
-                        }
-                }
-                builder.append(")");
-                return builder.toString();
+        protected String operatorName() {
+                return "count";
         }
 }
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/EquivalenceLiteral.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/EquivalenceLiteral.java
index 28ba7625..7343f709 100644
--- a/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/EquivalenceLiteral.java
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/EquivalenceLiteral.java
@@ -5,16 +5,44 @@
  */
 package tools.refinery.store.query.literal;
 
+import tools.refinery.store.query.InvalidQueryException;
 import tools.refinery.store.query.equality.LiteralEqualityHelper;
+import tools.refinery.store.query.equality.LiteralHashCodeHelper;
 import tools.refinery.store.query.substitution.Substitution;
-import tools.refinery.store.query.term.NodeVariable;
 import tools.refinery.store.query.term.Variable;
 
 import java.util.Objects;
 import java.util.Set;
 
-public record EquivalenceLiteral(boolean positive, NodeVariable left, NodeVariable right)
-                implements CanNegate<EquivalenceLiteral> {
+// {@link Object#equals(Object)} is implemented by {@link AbstractLiteral}.
+@SuppressWarnings("squid:S2160")
+public final class EquivalenceLiteral extends AbstractLiteral implements CanNegate<EquivalenceLiteral> {
+        private final boolean positive;
+        private final Variable left;
+        private final Variable right;
+
+        public EquivalenceLiteral(boolean positive, Variable left, Variable right) {
+                if (!left.tryGetType().equals(right.tryGetType())) {
+                        throw new InvalidQueryException("Variables %s and %s of different type cannot be equivalent"
+                                        .formatted(left, right));
+                }
+                this.positive = positive;
+                this.left = left;
+                this.right = right;
+        }
+
+        public boolean isPositive() {
+                return positive;
+        }
+
+        public Variable getLeft() {
+                return left;
+        }
+
+        public Variable getRight() {
+                return right;
+        }
+
         @Override
         public Set<Variable> getOutputVariables() {
                 return Set.of(left);
@@ -37,8 +65,8 @@ public record EquivalenceLiteral(boolean positive, NodeVariable left, NodeVariab
 
         @Override
         public EquivalenceLiteral substitute(Substitution substitution) {
-                return new EquivalenceLiteral(positive, substitution.getTypeSafeSubstitute(left),
-                                substitution.getTypeSafeSubstitute(right));
+                return new EquivalenceLiteral(positive, substitution.getSubstitute(left),
+                                substitution.getSubstitute(right));
         }
 
         @Override
@@ -55,27 +83,18 @@ public record EquivalenceLiteral(boolean positive, NodeVariable left, NodeVariab
                         return false;
                 }
                 var otherEquivalenceLiteral = (EquivalenceLiteral) other;
-                return helper.variableEqual(left, otherEquivalenceLiteral.left) && helper.variableEqual(right,
-                                otherEquivalenceLiteral.right);
-        }
-
-        @Override
-        public String toString() {
-                return "%s %s %s".formatted(left, positive ? "===" : "!==", right);
+                return helper.variableEqual(left, otherEquivalenceLiteral.left) &&
+                                helper.variableEqual(right, otherEquivalenceLiteral.right);
         }
 
         @Override
-        public boolean equals(Object obj) {
-                if (obj == this) return true;
-                if (obj == null || obj.getClass() != this.getClass()) return false;
-                var that = (EquivalenceLiteral) obj;
-                return this.positive == that.positive &&
-                                Objects.equals(this.left, that.left) &&
-                                Objects.equals(this.right, that.right);
+        public int hashCodeWithSubstitution(LiteralHashCodeHelper helper) {
+                return Objects.hash(super.hashCodeWithSubstitution(helper), helper.getVariableHashCode(left),
+                                helper.getVariableHashCode(right));
         }
 
         @Override
-        public int hashCode() {
-                return Objects.hash(getClass(), positive, left, right);
+        public String toString() {
+                return "%s %s %s".formatted(left, positive ? "===" : "!==", right);
         }
 }
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/Literal.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/Literal.java
index ce6c11fe..cb16ab00 100644
--- a/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/Literal.java
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/Literal.java
@@ -6,6 +6,7 @@
 package tools.refinery.store.query.literal;
 
 import tools.refinery.store.query.equality.LiteralEqualityHelper;
+import tools.refinery.store.query.equality.LiteralHashCodeHelper;
 import tools.refinery.store.query.substitution.Substitution;
 import tools.refinery.store.query.term.Variable;
 
@@ -26,4 +27,6 @@ public interface Literal {
 
         @SuppressWarnings("BooleanMethodIsAlwaysInverted")
         boolean equalsWithSubstitution(LiteralEqualityHelper helper, Literal other);
+
+        int hashCodeWithSubstitution(LiteralHashCodeHelper helper);
 }
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/Literals.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/Literals.java
index b3a87811..6056da45 100644
--- a/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/Literals.java
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/Literals.java
@@ -16,7 +16,7 @@ public final class Literals {
                 return literal.negate();
         }
 
-        public static AssumeLiteral assume(Term<Boolean> term) {
-                return new AssumeLiteral(term);
+        public static CheckLiteral check(Term<Boolean> term) {
+                return new CheckLiteral(term);
         }
 }
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/RepresentativeElectionLiteral.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/RepresentativeElectionLiteral.java
new file mode 100644
index 00000000..f7323947
--- /dev/null
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/RepresentativeElectionLiteral.java
@@ -0,0 +1,119 @@
+/*
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.literal;
+
+import tools.refinery.store.query.Constraint;
+import tools.refinery.store.query.InvalidQueryException;
+import tools.refinery.store.query.equality.LiteralEqualityHelper;
+import tools.refinery.store.query.equality.LiteralHashCodeHelper;
+import tools.refinery.store.query.substitution.Substitution;
+import tools.refinery.store.query.term.NodeVariable;
+import tools.refinery.store.query.term.ParameterDirection;
+import tools.refinery.store.query.term.Variable;
+
+import java.util.List;
+import java.util.Set;
+
+// {@link Object#equals(Object)} is implemented by {@link AbstractLiteral}.
+@SuppressWarnings("squid:S2160")
+public class RepresentativeElectionLiteral extends AbstractCallLiteral {
+        private final Connectivity connectivity;
+
+        public RepresentativeElectionLiteral(Connectivity connectivity, Constraint target, NodeVariable specific,
+                                                                                 NodeVariable representative) {
+                this(connectivity, target, List.of(specific, representative));
+        }
+
+        private RepresentativeElectionLiteral(Connectivity connectivity, Constraint target, List<Variable> arguments) {
+                super(target, arguments);
+                this.connectivity = connectivity;
+                var parameters = target.getParameters();
+                int arity = target.arity();
+                if (arity != 2) {
+                        throw new InvalidQueryException("SCCs can only take binary relations");
+                }
+                if (parameters.get(0).isDataVariable() || parameters.get(1).isDataVariable()) {
+                        throw new InvalidQueryException("SCCs can only be computed over nodes");
+                }
+                if (parameters.get(0).getDirection() != ParameterDirection.OUT ||
+                                parameters.get(1).getDirection() != ParameterDirection.OUT) {
+                        throw new InvalidQueryException("SCCs cannot take input parameters");
+                }
+        }
+
+        public Connectivity getConnectivity() {
+                return connectivity;
+        }
+
+        @Override
+        protected Literal doSubstitute(Substitution substitution, List<Variable> substitutedArguments) {
+                return new RepresentativeElectionLiteral(connectivity, getTarget(), substitutedArguments);
+        }
+
+        @Override
+        public Set<Variable> getOutputVariables() {
+                return getArgumentsOfDirection(ParameterDirection.OUT);
+        }
+
+        @Override
+        public Set<Variable> getInputVariables(Set<? extends Variable> positiveVariablesInClause) {
+                return Set.of();
+        }
+
+        @Override
+        public Set<Variable> getPrivateVariables(Set<? extends Variable> positiveVariablesInClause) {
+                return Set.of();
+        }
+
+        @Override
+        public Literal reduce() {
+                var reduction = getTarget().getReduction();
+                return switch (reduction) {
+                        case ALWAYS_FALSE -> BooleanLiteral.FALSE;
+                        case ALWAYS_TRUE -> throw new InvalidQueryException(
+                                        "Trying to elect representatives over an infinite set");
+                        case NOT_REDUCIBLE -> this;
+                };
+        }
+
+        @Override
+        public AbstractCallLiteral withArguments(Constraint newTarget, List<Variable> newArguments) {
+                return new RepresentativeElectionLiteral(connectivity, newTarget, newArguments);
+        }
+
+        @Override
+        public boolean equalsWithSubstitution(LiteralEqualityHelper helper, Literal other) {
+                if (!super.equalsWithSubstitution(helper, other)) {
+                        return false;
+                }
+                var otherRepresentativeElectionLiteral = (RepresentativeElectionLiteral) other;
+                return connectivity.equals(otherRepresentativeElectionLiteral.connectivity);
+        }
+
+        @Override
+        public int hashCodeWithSubstitution(LiteralHashCodeHelper helper) {
+                return super.hashCodeWithSubstitution(helper) * 31 + connectivity.hashCode();
+        }
+
+        @Override
+        public String toString() {
+                var builder = new StringBuilder();
+                builder.append("@Representative(\"");
+                builder.append(connectivity);
+                builder.append("\") ");
+                builder.append(getTarget().toReferenceString());
+                builder.append("(");
+                var argumentIterator = getArguments().iterator();
+                if (argumentIterator.hasNext()) {
+                        builder.append(argumentIterator.next());
+                        while (argumentIterator.hasNext()) {
+                                builder.append(", ").append(argumentIterator.next());
+                        }
+                }
+                builder.append(")");
+                return builder.toString();
+        }
+}
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/resultset/AbstractResultSet.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/resultset/AbstractResultSet.java
index a710c64d..dcfe6cc5 100644
--- a/subprojects/store-query/src/main/java/tools/refinery/store/query/resultset/AbstractResultSet.java
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/resultset/AbstractResultSet.java
@@ -28,7 +28,7 @@ public abstract class AbstractResultSet<T> implements ResultSet<T> {
         }
 
         @Override
-        public Query<T> getQuery() {
+        public Query<T> getCanonicalQuery() {
                 return query;
         }
 
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/resultset/AnyResultSet.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/resultset/AnyResultSet.java
index 02809477..5b75b103 100644
--- a/subprojects/store-query/src/main/java/tools/refinery/store/query/resultset/AnyResultSet.java
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/resultset/AnyResultSet.java
@@ -11,7 +11,7 @@ import tools.refinery.store.query.dnf.AnyQuery;
 public sealed interface AnyResultSet permits ResultSet {
         ModelQueryAdapter getAdapter();
 
-        AnyQuery getQuery();
+        AnyQuery getCanonicalQuery();
 
         int size();
 }
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/resultset/EmptyResultSet.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/resultset/EmptyResultSet.java
index 2795a44b..991b1e32 100644
--- a/subprojects/store-query/src/main/java/tools/refinery/store/query/resultset/EmptyResultSet.java
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/resultset/EmptyResultSet.java
@@ -18,7 +18,7 @@ public record EmptyResultSet<T>(ModelQueryAdapter adapter, Query<T> query) imple
         }
 
         @Override
-        public Query<T> getQuery() {
+        public Query<T> getCanonicalQuery() {
                 return query;
         }
 
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/resultset/OrderedResultSet.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/resultset/OrderedResultSet.java
index 39006d65..df12b967 100644
--- a/subprojects/store-query/src/main/java/tools/refinery/store/query/resultset/OrderedResultSet.java
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/resultset/OrderedResultSet.java
@@ -17,7 +17,7 @@ public class OrderedResultSet<T> implements AutoCloseable, ResultSet<T> {
         private final ResultSet<T> resultSet;
         private final OrderStatisticTree<Tuple> tree = new OrderStatisticTree<>();
         private final ResultSetListener<T> listener = (key, fromValue, toValue) -> {
-                var defaultValue = getQuery().defaultValue();
+                var defaultValue = getCanonicalQuery().defaultValue();
                 if (Objects.equals(defaultValue, toValue)) {
                         tree.remove(key);
                 } else {
@@ -45,8 +45,8 @@ public class OrderedResultSet<T> implements AutoCloseable, ResultSet<T> {
         }
 
         @Override
-        public Query<T> getQuery() {
-                return resultSet.getQuery();
+        public Query<T> getCanonicalQuery() {
+                return resultSet.getCanonicalQuery();
         }
 
         @Override
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/resultset/ResultSet.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/resultset/ResultSet.java
index 33d1ea95..a6e99784 100644
--- a/subprojects/store-query/src/main/java/tools/refinery/store/query/resultset/ResultSet.java
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/resultset/ResultSet.java
@@ -10,7 +10,7 @@ import tools.refinery.store.query.dnf.Query;
 import tools.refinery.store.tuple.Tuple;
 
 public non-sealed interface ResultSet<T> extends AnyResultSet {
-        Query<T> getQuery();
+        Query<T> getCanonicalQuery();
 
         T get(Tuple parameters);
 
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/rewriter/AbstractRecursiveRewriter.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/rewriter/AbstractRecursiveRewriter.java
new file mode 100644
index 00000000..fb4c14a7
--- /dev/null
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/rewriter/AbstractRecursiveRewriter.java
@@ -0,0 +1,26 @@
+/*
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.rewriter;
+
+import tools.refinery.store.query.dnf.Dnf;
+import tools.refinery.store.query.equality.DnfEqualityChecker;
+import tools.refinery.store.util.CycleDetectingMapper;
+
+public abstract class AbstractRecursiveRewriter implements DnfRewriter {
+        private final CycleDetectingMapper<Dnf, Dnf> mapper = new CycleDetectingMapper<>(Dnf::name, this::map);
+
+        @Override
+        public Dnf rewrite(Dnf dnf) {
+                return mapper.map(dnf);
+        }
+
+        protected Dnf map(Dnf dnf) {
+                var result = doRewrite(dnf);
+                return dnf.equalsWithSubstitution(DnfEqualityChecker.DEFAULT, result) ? dnf : result;
+        }
+
+        protected abstract Dnf doRewrite(Dnf dnf);
+}
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/rewriter/ClauseInputParameterResolver.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/rewriter/ClauseInputParameterResolver.java
new file mode 100644
index 00000000..aa06a05a
--- /dev/null
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/rewriter/ClauseInputParameterResolver.java
@@ -0,0 +1,160 @@
+/*
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.rewriter;
+
+import tools.refinery.store.query.dnf.Dnf;
+import tools.refinery.store.query.dnf.DnfClause;
+import tools.refinery.store.query.literal.*;
+import tools.refinery.store.query.substitution.Substitution;
+import tools.refinery.store.query.term.ParameterDirection;
+import tools.refinery.store.query.term.Variable;
+
+import java.util.*;
+
+class ClauseInputParameterResolver {
+        private final InputParameterResolver rewriter;
+        private final String dnfName;
+        private final int clauseIndex;
+        private final Set<Variable> positiveVariables = new LinkedHashSet<>();
+        private final List<Literal> inlinedLiterals = new ArrayList<>();
+        private final Deque<Literal> workList;
+        private int helperIndex = 0;
+
+        public ClauseInputParameterResolver(InputParameterResolver rewriter, List<Literal> context, DnfClause clause,
+                                                                                String dnfName, int clauseIndex) {
+                this.rewriter = rewriter;
+                this.dnfName = dnfName;
+                this.clauseIndex = clauseIndex;
+                workList = new ArrayDeque<>(clause.literals().size() + context.size());
+                for (var literal : context) {
+                        workList.addLast(literal);
+                }
+                for (var literal : clause.literals()) {
+                        workList.addLast(literal);
+                }
+        }
+
+        public List<Literal> rewriteClause() {
+                while (!workList.isEmpty()) {
+                        var literal = workList.removeFirst();
+                        processLiteral(literal);
+                }
+                return inlinedLiterals;
+        }
+
+        private void processLiteral(Literal literal) {
+                if (!(literal instanceof AbstractCallLiteral abstractCallLiteral) ||
+                                !(abstractCallLiteral.getTarget() instanceof Dnf targetDnf)) {
+                        markAsDone(literal);
+                        return;
+                }
+                boolean hasInputParameter = hasInputParameter(targetDnf);
+                if (!hasInputParameter) {
+                        targetDnf = rewriter.rewrite(targetDnf);
+                }
+                if (inlinePositiveClause(abstractCallLiteral, targetDnf)) {
+                        return;
+                }
+                if (eliminateDoubleNegation(abstractCallLiteral, targetDnf)) {
+                        return;
+                }
+                if (hasInputParameter) {
+                        rewriteWithCurrentContext(abstractCallLiteral, targetDnf);
+                        return;
+                }
+                markAsDone(abstractCallLiteral.withTarget(targetDnf));
+        }
+
+        private void markAsDone(Literal literal) {
+                positiveVariables.addAll(literal.getOutputVariables());
+                inlinedLiterals.add(literal);
+        }
+
+        private boolean inlinePositiveClause(AbstractCallLiteral abstractCallLiteral, Dnf targetDnf) {
+                var targetLiteral = getSingleLiteral(abstractCallLiteral, targetDnf, CallPolarity.POSITIVE);
+                if (targetLiteral == null) {
+                        return false;
+                }
+                var substitution = asSubstitution(abstractCallLiteral, targetDnf);
+                var substitutedLiteral = targetLiteral.substitute(substitution);
+                workList.addFirst(substitutedLiteral);
+                return true;
+        }
+
+        private boolean eliminateDoubleNegation(AbstractCallLiteral abstractCallLiteral, Dnf targetDnf) {
+                var targetLiteral = getSingleLiteral(abstractCallLiteral, targetDnf, CallPolarity.NEGATIVE);
+                if (!(targetLiteral instanceof CallLiteral targetCallLiteral) ||
+                                targetCallLiteral.getPolarity() != CallPolarity.NEGATIVE) {
+                        return false;
+                }
+                var substitution = asSubstitution(abstractCallLiteral, targetDnf);
+                var substitutedLiteral = (CallLiteral) targetCallLiteral.substitute(substitution);
+                workList.addFirst(substitutedLiteral.negate());
+                return true;
+        }
+
+        private void rewriteWithCurrentContext(AbstractCallLiteral abstractCallLiteral, Dnf targetDnf) {
+                var contextBuilder = Dnf.builder("%s#clause%d#helper%d".formatted(dnfName, clauseIndex, helperIndex));
+                helperIndex++;
+                contextBuilder.parameters(positiveVariables, ParameterDirection.OUT);
+                contextBuilder.clause(inlinedLiterals);
+                var contextDnf = contextBuilder.build();
+                var contextCall = new CallLiteral(CallPolarity.POSITIVE, contextDnf, List.copyOf(positiveVariables));
+                inlinedLiterals.clear();
+                var substitution = Substitution.builder().renewing().build();
+                var context = new ArrayList<Literal>();
+                context.add(contextCall.substitute(substitution));
+                int arity = targetDnf.arity();
+                for (int i = 0; i < arity; i++) {
+                        var parameter = targetDnf.getSymbolicParameters().get(i).getVariable();
+                        var argument = abstractCallLiteral.getArguments().get(i);
+                        context.add(new EquivalenceLiteral(true, parameter, substitution.getSubstitute(argument)));
+                }
+                var rewrittenDnf = rewriter.rewriteWithContext(context, targetDnf);
+                workList.addFirst(abstractCallLiteral.withTarget(rewrittenDnf));
+                workList.addFirst(contextCall);
+        }
+
+        private static boolean hasInputParameter(Dnf targetDnf) {
+                for (var parameter : targetDnf.getParameters()) {
+                        if (parameter.getDirection() != ParameterDirection.OUT) {
+                                return true;
+                        }
+                }
+                return false;
+        }
+
+        private static Literal getSingleLiteral(AbstractCallLiteral abstractCallLiteral, Dnf targetDnf,
+                                                                                        CallPolarity polarity) {
+                if (!(abstractCallLiteral instanceof CallLiteral callLiteral) ||
+                                callLiteral.getPolarity() != polarity) {
+                        return null;
+                }
+                var clauses = targetDnf.getClauses();
+                if (clauses.size() != 1) {
+                        return null;
+                }
+                var targetLiterals = clauses.get(0).literals();
+                if (targetLiterals.size() != 1) {
+                        return null;
+                }
+                return targetLiterals.get(0);
+        }
+
+        private static Substitution asSubstitution(AbstractCallLiteral callLiteral, Dnf targetDnf) {
+                var builder = Substitution.builder().renewing();
+                var arguments = callLiteral.getArguments();
+                var parameters = targetDnf.getSymbolicParameters();
+                int arity = arguments.size();
+                if (parameters.size() != arity) {
+                        throw new IllegalArgumentException("Call %s of %s arity mismatch".formatted(callLiteral, targetDnf));
+                }
+                for (int i = 0; i < arity; i++) {
+                        builder.putChecked(parameters.get(i).getVariable(), arguments.get(i));
+                }
+                return builder.build();
+        }
+}
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/rewriter/CompositeRewriter.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/rewriter/CompositeRewriter.java
new file mode 100644
index 00000000..5b4f65e5
--- /dev/null
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/rewriter/CompositeRewriter.java
@@ -0,0 +1,29 @@
+/*
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.rewriter;
+
+import tools.refinery.store.query.dnf.Dnf;
+
+import java.util.ArrayList;
+import java.util.List;
+
+public class CompositeRewriter implements DnfRewriter {
+        private final List<DnfRewriter> rewriterList = new ArrayList<>();
+
+        public void addFirst(DnfRewriter rewriter) {
+                rewriterList.add(rewriter);
+        }
+
+        @Override
+        public Dnf rewrite(Dnf dnf) {
+                Dnf rewrittenDnf = dnf;
+                for (int i = rewriterList.size() - 1; i >= 0; i--) {
+                        var rewriter = rewriterList.get(i);
+                        rewrittenDnf = rewriter.rewrite(rewrittenDnf);
+                }
+                return rewrittenDnf;
+        }
+}
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/rewriter/DnfRewriter.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/rewriter/DnfRewriter.java
new file mode 100644
index 00000000..5d8359d1
--- /dev/null
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/rewriter/DnfRewriter.java
@@ -0,0 +1,24 @@
+/*
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.rewriter;
+
+import tools.refinery.store.query.dnf.AnyQuery;
+import tools.refinery.store.query.dnf.Dnf;
+import tools.refinery.store.query.dnf.Query;
+
+@FunctionalInterface
+public interface DnfRewriter {
+        Dnf rewrite(Dnf dnf);
+
+        default AnyQuery rewrite(AnyQuery query) {
+                return rewrite((Query<?>) query);
+        }
+
+        default <T> Query<T> rewrite(Query<T> query) {
+                var rewrittenDnf = rewrite(query.getDnf());
+                return query.withDnf(rewrittenDnf);
+        }
+}
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/rewriter/DuplicateDnfRemover.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/rewriter/DuplicateDnfRemover.java
new file mode 100644
index 00000000..0c786470
--- /dev/null
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/rewriter/DuplicateDnfRemover.java
@@ -0,0 +1,98 @@
+/*
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.rewriter;
+
+import tools.refinery.store.query.dnf.Dnf;
+import tools.refinery.store.query.dnf.DnfClause;
+import tools.refinery.store.query.dnf.Query;
+import tools.refinery.store.query.equality.DnfEqualityChecker;
+import tools.refinery.store.query.literal.AbstractCallLiteral;
+import tools.refinery.store.query.literal.Literal;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+
+public class DuplicateDnfRemover extends AbstractRecursiveRewriter {
+        private final Map<CanonicalDnf, Dnf> dnfCache = new HashMap<>();
+        private final Map<Dnf, Query<?>> queryCache = new HashMap<>();
+
+        @Override
+        protected Dnf map(Dnf dnf) {
+                var result = super.map(dnf);
+                return dnfCache.computeIfAbsent(new CanonicalDnf(result), CanonicalDnf::getDnf);
+        }
+
+        @Override
+        protected Dnf doRewrite(Dnf dnf) {
+                var builder = Dnf.builderFrom(dnf);
+                for (var clause : dnf.getClauses()) {
+                        builder.clause(rewriteClause(clause));
+                }
+                return builder.build();
+        }
+
+        private List<Literal> rewriteClause(DnfClause clause) {
+                var originalLiterals = clause.literals();
+                var literals = new ArrayList<Literal>(originalLiterals.size());
+                for (var literal : originalLiterals) {
+                        var rewrittenLiteral = literal;
+                        if (literal instanceof AbstractCallLiteral abstractCallLiteral &&
+                                        abstractCallLiteral.getTarget() instanceof Dnf targetDnf) {
+                                var rewrittenTarget = rewrite(targetDnf);
+                                rewrittenLiteral = abstractCallLiteral.withTarget(rewrittenTarget);
+                        }
+                        literals.add(rewrittenLiteral);
+                }
+                return literals;
+        }
+
+        @Override
+        public <T> Query<T> rewrite(Query<T> query) {
+                var rewrittenDnf = rewrite(query.getDnf());
+                // {@code withDnf} will always return the appropriate type.
+                @SuppressWarnings("unchecked")
+                var rewrittenQuery = (Query<T>) queryCache.computeIfAbsent(rewrittenDnf, query::withDnf);
+                return rewrittenQuery;
+        }
+
+        private static class CanonicalDnf {
+                private final Dnf dnf;
+                private final int hash;
+
+                public CanonicalDnf(Dnf dnf) {
+                        this.dnf = dnf;
+                        hash = dnf.hashCodeWithSubstitution();
+                }
+
+                public Dnf getDnf() {
+                        return dnf;
+                }
+
+                @Override
+                public boolean equals(Object obj) {
+                        if (this == obj) {
+                                return true;
+                        }
+                        if (obj == null || getClass() != obj.getClass()) {
+                                return false;
+                        }
+                        var otherCanonicalDnf = (CanonicalDnf) obj;
+                        return dnf.equalsWithSubstitution(DnfEqualityChecker.DEFAULT, otherCanonicalDnf.dnf);
+                }
+
+                @Override
+                public int hashCode() {
+                        return hash;
+                }
+
+                @Override
+                public String toString() {
+                        return dnf.name();
+                }
+        }
+}
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/rewriter/InputParameterResolver.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/rewriter/InputParameterResolver.java
new file mode 100644
index 00000000..cd8a2e7d
--- /dev/null
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/rewriter/InputParameterResolver.java
@@ -0,0 +1,51 @@
+/*
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.rewriter;
+
+import tools.refinery.store.query.dnf.Dnf;
+import tools.refinery.store.query.dnf.DnfBuilder;
+import tools.refinery.store.query.literal.Literal;
+import tools.refinery.store.query.term.ParameterDirection;
+import tools.refinery.store.query.term.Variable;
+
+import java.util.HashSet;
+import java.util.List;
+
+public class InputParameterResolver extends AbstractRecursiveRewriter {
+        @Override
+        protected Dnf doRewrite(Dnf dnf) {
+                return rewriteWithContext(List.of(), dnf);
+        }
+
+        Dnf rewriteWithContext(List<Literal> context, Dnf dnf) {
+                var dnfName = dnf.name();
+                var builder = Dnf.builder(dnfName);
+                createSymbolicParameters(context, dnf, builder);
+                builder.functionalDependencies(dnf.getFunctionalDependencies());
+                var clauses = dnf.getClauses();
+                int clauseCount = clauses.size();
+                for (int i = 0; i < clauseCount; i++) {
+                        var clause = clauses.get(i);
+                        var clauseRewriter = new ClauseInputParameterResolver(this, context, clause, dnfName, i);
+                        builder.clause(clauseRewriter.rewriteClause());
+                }
+                return builder.build();
+        }
+
+        private static void createSymbolicParameters(List<Literal> context, Dnf dnf, DnfBuilder builder) {
+                var positiveInContext = new HashSet<Variable>();
+                for (var literal : context) {
+                        positiveInContext.addAll(literal.getOutputVariables());
+                }
+                for (var symbolicParameter : dnf.getSymbolicParameters()) {
+                        var variable = symbolicParameter.getVariable();
+                        var isOutput = symbolicParameter.getDirection() == ParameterDirection.OUT ||
+                                        positiveInContext.contains(variable);
+                        var direction = isOutput ? ParameterDirection.OUT : ParameterDirection.IN;
+                        builder.parameter(variable, direction);
+                }
+        }
+}
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/term/AbstractTerm.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/term/AbstractTerm.java
index d0ae3c12..5cecc35b 100644
--- a/subprojects/store-query/src/main/java/tools/refinery/store/query/term/AbstractTerm.java
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/term/AbstractTerm.java
@@ -6,6 +6,7 @@
 package tools.refinery.store.query.term;
 
 import tools.refinery.store.query.equality.LiteralEqualityHelper;
+import tools.refinery.store.query.equality.LiteralHashCodeHelper;
 
 import java.util.Objects;
 
@@ -17,13 +18,18 @@ public abstract class AbstractTerm<T> implements Term<T> {
         }
 
         @Override
+        public Class<T> getType() {
+                return type;
+        }
+
+        @Override
         public boolean equalsWithSubstitution(LiteralEqualityHelper helper, AnyTerm other) {
-                return getClass().equals(other.getClass()) && type.equals(other.getType());
+                return other != null && getClass() == other.getClass() && type.equals(other.getType());
         }
 
         @Override
-        public Class<T> getType() {
-                return type;
+        public int hashCodeWithSubstitution(LiteralHashCodeHelper helper) {
+                return Objects.hash(getClass(), type);
         }
 
         @Override
@@ -31,11 +37,11 @@ public abstract class AbstractTerm<T> implements Term<T> {
                 if (this == o) return true;
                 if (o == null || getClass() != o.getClass()) return false;
                 AbstractTerm<?> that = (AbstractTerm<?>) o;
-                return type.equals(that.type);
+                return equalsWithSubstitution(LiteralEqualityHelper.DEFAULT, that);
         }
 
         @Override
         public int hashCode() {
-                return Objects.hash(getClass(), type);
+                return hashCodeWithSubstitution(LiteralHashCodeHelper.DEFAULT);
         }
 }
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/term/AnyDataVariable.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/term/AnyDataVariable.java
index 192c39c5..3801bc11 100644
--- a/subprojects/store-query/src/main/java/tools/refinery/store/query/term/AnyDataVariable.java
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/term/AnyDataVariable.java
@@ -6,6 +6,7 @@
 package tools.refinery.store.query.term;
 
 import org.jetbrains.annotations.Nullable;
+import tools.refinery.store.query.InvalidQueryException;
 import tools.refinery.store.query.equality.LiteralEqualityHelper;
 
 import java.util.Optional;
@@ -22,8 +23,18 @@ public abstract sealed class AnyDataVariable extends Variable implements AnyTerm
         }
 
         @Override
+        public boolean isNodeVariable() {
+                return false;
+        }
+
+        @Override
+        public boolean isDataVariable() {
+                return true;
+        }
+
+        @Override
         public NodeVariable asNodeVariable() {
-                throw new IllegalStateException("%s is a data variable".formatted(this));
+                throw new InvalidQueryException("%s is a data variable".formatted(this));
         }
 
         @Override
@@ -37,11 +48,6 @@ public abstract sealed class AnyDataVariable extends Variable implements AnyTerm
         }
 
         @Override
-        public boolean isUnifiable() {
-                return false;
-        }
-
-        @Override
         public abstract AnyDataVariable renew(@Nullable String name);
 
         @Override
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/term/AnyTerm.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/term/AnyTerm.java
index c12c0166..f136b68d 100644
--- a/subprojects/store-query/src/main/java/tools/refinery/store/query/term/AnyTerm.java
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/term/AnyTerm.java
@@ -6,6 +6,7 @@
 package tools.refinery.store.query.term;
 
 import tools.refinery.store.query.equality.LiteralEqualityHelper;
+import tools.refinery.store.query.equality.LiteralHashCodeHelper;
 import tools.refinery.store.query.substitution.Substitution;
 
 import java.util.Set;
@@ -17,5 +18,7 @@ public sealed interface AnyTerm permits AnyDataVariable, Term {
 
         boolean equalsWithSubstitution(LiteralEqualityHelper helper, AnyTerm other);
 
+        int hashCodeWithSubstitution(LiteralHashCodeHelper helper);
+
         Set<AnyDataVariable> getInputVariables();
 }
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/term/BinaryTerm.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/term/BinaryTerm.java
index 8ad17839..cdbf592a 100644
--- a/subprojects/store-query/src/main/java/tools/refinery/store/query/term/BinaryTerm.java
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/term/BinaryTerm.java
@@ -5,7 +5,9 @@
  */
 package tools.refinery.store.query.term;
 
+import tools.refinery.store.query.InvalidQueryException;
 import tools.refinery.store.query.equality.LiteralEqualityHelper;
+import tools.refinery.store.query.equality.LiteralHashCodeHelper;
 import tools.refinery.store.query.substitution.Substitution;
 import tools.refinery.store.query.valuation.Valuation;
 
@@ -14,6 +16,8 @@ import java.util.HashSet;
 import java.util.Objects;
 import java.util.Set;
 
+// {@link Object#equals(Object)} is implemented by {@link AbstractTerm}.
+@SuppressWarnings("squid:S2160")
 public abstract class BinaryTerm<R, T1, T2> extends AbstractTerm<R> {
         private final Class<T1> leftType;
         private final Class<T2> rightType;
@@ -23,11 +27,11 @@ public abstract class BinaryTerm<R, T1, T2> extends AbstractTerm<R> {
         protected BinaryTerm(Class<R> type, Class<T1> leftType, Class<T2> rightType, Term<T1> left, Term<T2> right) {
                 super(type);
                 if (!left.getType().equals(leftType)) {
-                        throw new IllegalArgumentException("Expected left %s to be of type %s, got %s instead".formatted(
+                        throw new InvalidQueryException("Expected left %s to be of type %s, got %s instead".formatted(
                                         left, leftType.getName(), left.getType().getName()));
                 }
                 if (!right.getType().equals(rightType)) {
-                        throw new IllegalArgumentException("Expected right %s to be of type %s, got %s instead".formatted(
+                        throw new InvalidQueryException("Expected right %s to be of type %s, got %s instead".formatted(
                                         right, rightType.getName(), right.getType().getName()));
                 }
                 this.leftType = leftType;
@@ -80,6 +84,12 @@ public abstract class BinaryTerm<R, T1, T2> extends AbstractTerm<R> {
         }
 
         @Override
+        public int hashCodeWithSubstitution(LiteralHashCodeHelper helper) {
+                return Objects.hash(super.hashCodeWithSubstitution(helper), leftType.hashCode(), rightType.hashCode(),
+                                left.hashCodeWithSubstitution(helper), right.hashCodeWithSubstitution(helper));
+        }
+
+        @Override
         public Term<R> substitute(Substitution substitution) {
                 return doSubstitute(substitution, left.substitute(substitution), right.substitute(substitution));
         }
@@ -93,21 +103,4 @@ public abstract class BinaryTerm<R, T1, T2> extends AbstractTerm<R> {
                 inputVariables.addAll(right.getInputVariables());
                 return Collections.unmodifiableSet(inputVariables);
         }
-
-        @Override
-        public boolean equals(Object o) {
-                if (this == o) return true;
-                if (o == null || getClass() != o.getClass()) return false;
-                if (!super.equals(o)) return false;
-                BinaryTerm<?, ?, ?> that = (BinaryTerm<?, ?, ?>) o;
-                return Objects.equals(leftType, that.leftType) &&
-                                Objects.equals(rightType, that.rightType) &&
-                                Objects.equals(left, that.left) &&
-                                Objects.equals(right, that.right);
-        }
-
-        @Override
-        public int hashCode() {
-                return Objects.hash(super.hashCode(), leftType, rightType, left, right);
-        }
 }
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/term/ConstantTerm.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/term/ConstantTerm.java
index 2f6c56d1..415ae286 100644
--- a/subprojects/store-query/src/main/java/tools/refinery/store/query/term/ConstantTerm.java
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/term/ConstantTerm.java
@@ -5,20 +5,24 @@
  */
 package tools.refinery.store.query.term;
 
+import tools.refinery.store.query.InvalidQueryException;
 import tools.refinery.store.query.equality.LiteralEqualityHelper;
+import tools.refinery.store.query.equality.LiteralHashCodeHelper;
 import tools.refinery.store.query.substitution.Substitution;
 import tools.refinery.store.query.valuation.Valuation;
 
 import java.util.Objects;
 import java.util.Set;
 
+// {@link Object#equals(Object)} is implemented by {@link AbstractTerm}.
+@SuppressWarnings("squid:S2160")
 public final class ConstantTerm<T> extends AbstractTerm<T> {
         private final T value;
 
         public ConstantTerm(Class<T> type, T value) {
                 super(type);
                 if (value != null && !type.isInstance(value)) {
-                        throw new IllegalArgumentException("Value %s is not an instance of %s".formatted(value, type.getName()));
+                        throw new InvalidQueryException("Value %s is not an instance of %s".formatted(value, type.getName()));
                 }
                 this.value = value;
         }
@@ -47,6 +51,11 @@ public final class ConstantTerm<T> extends AbstractTerm<T> {
         }
 
         @Override
+        public int hashCodeWithSubstitution(LiteralHashCodeHelper helper) {
+                return Objects.hash(super.hashCodeWithSubstitution(helper), Objects.hash(value));
+        }
+
+        @Override
         public Set<AnyDataVariable> getInputVariables() {
                 return Set.of();
         }
@@ -55,17 +64,4 @@ public final class ConstantTerm<T> extends AbstractTerm<T> {
         public String toString() {
                 return value.toString();
         }
-
-        @Override
-        public boolean equals(Object o) {
-                if (this == o) return true;
-                if (o == null || getClass() != o.getClass()) return false;
-                ConstantTerm<?> that = (ConstantTerm<?>) o;
-                return Objects.equals(value, that.value);
-        }
-
-        @Override
-        public int hashCode() {
-                return Objects.hash(value);
-        }
 }
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/term/DataVariable.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/term/DataVariable.java
index 00950360..2206b522 100644
--- a/subprojects/store-query/src/main/java/tools/refinery/store/query/term/DataVariable.java
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/term/DataVariable.java
@@ -6,7 +6,10 @@
 package tools.refinery.store.query.term;
 
 import org.jetbrains.annotations.Nullable;
+import tools.refinery.store.query.InvalidQueryException;
 import tools.refinery.store.query.equality.LiteralEqualityHelper;
+import tools.refinery.store.query.equality.LiteralHashCodeHelper;
+import tools.refinery.store.query.literal.EquivalenceLiteral;
 import tools.refinery.store.query.literal.Literal;
 import tools.refinery.store.query.substitution.Substitution;
 import tools.refinery.store.query.valuation.Valuation;
@@ -39,8 +42,8 @@ public final class DataVariable<T> extends AnyDataVariable implements Term<T> {
         @Override
         public <U> DataVariable<U> asDataVariable(Class<U> newType) {
                 if (!getType().equals(newType)) {
-                        throw new IllegalStateException("%s is not of type %s but of type %s".formatted(this, newType.getName(),
-                                        getType().getName()));
+                        throw new InvalidQueryException("%s is not of type %s but of type %s"
+                                        .formatted(this, newType.getName(), getType().getName()));
                 }
                 @SuppressWarnings("unchecked")
                 var result = (DataVariable<U>) this;
@@ -62,6 +65,16 @@ public final class DataVariable<T> extends AnyDataVariable implements Term<T> {
                 return other instanceof DataVariable<?> dataVariable && helper.variableEqual(this, dataVariable);
         }
 
+        @Override
+        public int hashCodeWithSubstitution(LiteralHashCodeHelper helper) {
+                return helper.getVariableHashCode(this);
+        }
+
+        @Override
+        public int hashCodeWithSubstitution(int sequenceNumber) {
+                return Objects.hash(type, sequenceNumber);
+        }
+
         public Literal assign(AssignedValue<T> value) {
                 return value.toLiteral(this);
         }
@@ -79,4 +92,12 @@ public final class DataVariable<T> extends AnyDataVariable implements Term<T> {
         public int hashCode() {
                 return Objects.hash(super.hashCode(), type);
         }
+
+        public EquivalenceLiteral isEquivalent(DataVariable<T> other) {
+                return new EquivalenceLiteral(true, this, other);
+        }
+
+        public EquivalenceLiteral notEquivalent(DataVariable<T> other) {
+                return new EquivalenceLiteral(false, this, other);
+        }
 }
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/term/NodeVariable.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/term/NodeVariable.java
index a2f3261f..53c32e20 100644
--- a/subprojects/store-query/src/main/java/tools/refinery/store/query/term/NodeVariable.java
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/term/NodeVariable.java
@@ -6,6 +6,7 @@
 package tools.refinery.store.query.term;
 
 import org.jetbrains.annotations.Nullable;
+import tools.refinery.store.query.InvalidQueryException;
 import tools.refinery.store.query.literal.ConstantLiteral;
 import tools.refinery.store.query.literal.EquivalenceLiteral;
 
@@ -22,11 +23,6 @@ public final class NodeVariable extends Variable {
         }
 
         @Override
-        public boolean isUnifiable() {
-                return true;
-        }
-
-        @Override
         public NodeVariable renew(@Nullable String name) {
                 return Variable.of(name);
         }
@@ -37,13 +33,28 @@ public final class NodeVariable extends Variable {
         }
 
         @Override
+        public boolean isNodeVariable() {
+                return true;
+        }
+
+        @Override
+        public boolean isDataVariable() {
+                return false;
+        }
+
+        @Override
         public NodeVariable asNodeVariable() {
                 return this;
         }
 
         @Override
         public <T> DataVariable<T> asDataVariable(Class<T> type) {
-                throw new IllegalStateException("%s is a node variable".formatted(this));
+                throw new InvalidQueryException("%s is a node variable".formatted(this));
+        }
+
+        @Override
+        public int hashCodeWithSubstitution(int sequenceNumber) {
+                return sequenceNumber;
         }
 
         public ConstantLiteral isConstant(int value) {
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/term/Parameter.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/term/Parameter.java
index e5a0cdf1..577ac6e0 100644
--- a/subprojects/store-query/src/main/java/tools/refinery/store/query/term/Parameter.java
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/term/Parameter.java
@@ -9,11 +9,15 @@ import java.util.Objects;
 import java.util.Optional;
 
 public class Parameter {
-        public static final Parameter NODE_OUT = new Parameter(null, ParameterDirection.OUT);
+        public static final Parameter NODE_OUT = new Parameter(null);
 
         private final Class<?> dataType;
         private final ParameterDirection direction;
 
+        public Parameter(Class<?> dataType) {
+                this(dataType, ParameterDirection.OUT);
+        }
+
         public Parameter(Class<?> dataType, ParameterDirection direction) {
                 this.dataType = dataType;
                 this.direction = direction;
@@ -35,6 +39,10 @@ public class Parameter {
                 return direction;
         }
 
+        public boolean matches(Parameter other) {
+                return Objects.equals(dataType, other.dataType) && direction == other.direction;
+        }
+
         public boolean isAssignable(Variable variable) {
                 if (variable instanceof AnyDataVariable dataVariable) {
                         return dataVariable.getType().equals(dataType);
@@ -50,7 +58,7 @@ public class Parameter {
                 if (this == o) return true;
                 if (o == null || getClass() != o.getClass()) return false;
                 Parameter parameter = (Parameter) o;
-                return Objects.equals(dataType, parameter.dataType) && direction == parameter.direction;
+                return matches(parameter);
         }
 
         @Override
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/term/ParameterDirection.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/term/ParameterDirection.java
index cd0739be..da83f3c3 100644
--- a/subprojects/store-query/src/main/java/tools/refinery/store/query/term/ParameterDirection.java
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/term/ParameterDirection.java
@@ -6,8 +6,8 @@
 package tools.refinery.store.query.term;
 
 public enum ParameterDirection {
-        OUT("@Out"),
-        IN("@In");
+        OUT("out"),
+        IN("in");
 
         private final String name;
 
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/term/UnaryTerm.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/term/UnaryTerm.java
index a46ebe31..a464ece5 100644
--- a/subprojects/store-query/src/main/java/tools/refinery/store/query/term/UnaryTerm.java
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/term/UnaryTerm.java
@@ -5,13 +5,17 @@
  */
 package tools.refinery.store.query.term;
 
+import tools.refinery.store.query.InvalidQueryException;
 import tools.refinery.store.query.equality.LiteralEqualityHelper;
+import tools.refinery.store.query.equality.LiteralHashCodeHelper;
 import tools.refinery.store.query.substitution.Substitution;
 import tools.refinery.store.query.valuation.Valuation;
 
 import java.util.Objects;
 import java.util.Set;
 
+// {@link Object#equals(Object)} is implemented by {@link AbstractTerm}.
+@SuppressWarnings("squid:S2160")
 public abstract class UnaryTerm<R, T> extends AbstractTerm<R> {
         private final Class<T> bodyType;
         private final Term<T> body;
@@ -19,7 +23,7 @@ public abstract class UnaryTerm<R, T> extends AbstractTerm<R> {
         protected UnaryTerm(Class<R> type, Class<T> bodyType, Term<T> body) {
                 super(type);
                 if (!body.getType().equals(bodyType)) {
-                        throw new IllegalArgumentException("Expected body %s to be of type %s, got %s instead".formatted(body,
+                        throw new InvalidQueryException("Expected body %s to be of type %s, got %s instead".formatted(body,
                                         bodyType.getName(), body.getType().getName()));
                 }
                 this.bodyType = bodyType;
@@ -52,6 +56,11 @@ public abstract class UnaryTerm<R, T> extends AbstractTerm<R> {
         }
 
         @Override
+        public int hashCodeWithSubstitution(LiteralHashCodeHelper helper) {
+                return Objects.hash(super.hashCodeWithSubstitution(helper), bodyType, body.hashCodeWithSubstitution(helper));
+        }
+
+        @Override
         public Term<R> substitute(Substitution substitution) {
                 return doSubstitute(substitution, body.substitute(substitution));
         }
@@ -62,18 +71,4 @@ public abstract class UnaryTerm<R, T> extends AbstractTerm<R> {
         public Set<AnyDataVariable> getInputVariables() {
                 return body.getInputVariables();
         }
-
-        @Override
-        public boolean equals(Object o) {
-                if (this == o) return true;
-                if (o == null || getClass() != o.getClass()) return false;
-                if (!super.equals(o)) return false;
-                UnaryTerm<?, ?> unaryTerm = (UnaryTerm<?, ?>) o;
-                return Objects.equals(bodyType, unaryTerm.bodyType) && Objects.equals(body, unaryTerm.body);
-        }
-
-        @Override
-        public int hashCode() {
-                return Objects.hash(super.hashCode(), bodyType, body);
-        }
 }
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/term/Variable.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/term/Variable.java
index a0268c8e..1b553704 100644
--- a/subprojects/store-query/src/main/java/tools/refinery/store/query/term/Variable.java
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/term/Variable.java
@@ -38,16 +38,20 @@ public abstract sealed class Variable permits AnyDataVariable, NodeVariable {
                 return uniqueName;
         }
 
-        public abstract boolean isUnifiable();
-
         public abstract Variable renew(@Nullable String name);
 
         public abstract Variable renew();
 
+        public abstract boolean isNodeVariable();
+
+        public abstract boolean isDataVariable();
+
         public abstract NodeVariable asNodeVariable();
 
         public abstract <T> DataVariable<T> asDataVariable(Class<T> type);
 
+        public abstract int hashCodeWithSubstitution(int sequenceNumber);
+
         @Override
         public String toString() {
                 return getName();
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/term/uppercardinality/UpperCardinalitySumAggregator.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/term/uppercardinality/UpperCardinalitySumAggregator.java
index 5bbd3081..d31f00a2 100644
--- a/subprojects/store-query/src/main/java/tools/refinery/store/query/term/uppercardinality/UpperCardinalitySumAggregator.java
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/term/uppercardinality/UpperCardinalitySumAggregator.java
@@ -70,7 +70,7 @@ public class UpperCardinalitySumAggregator implements StatefulAggregator<UpperCa
 
                 @Override
                 public UpperCardinality getResult() {
-                        return countUnbounded > 0 ? UpperCardinalities.UNBOUNDED : UpperCardinalities.valueOf(sumFiniteUpperBounds);
+                        return countUnbounded > 0 ? UpperCardinalities.UNBOUNDED : UpperCardinalities.atMost(sumFiniteUpperBounds);
                 }
 
                 @Override
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/utils/OrderStatisticTree.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/utils/OrderStatisticTree.java
index b568b99d..2d8a10d1 100644
--- a/subprojects/store-query/src/main/java/tools/refinery/store/query/utils/OrderStatisticTree.java
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/utils/OrderStatisticTree.java
@@ -2,7 +2,7 @@
  * Copyright (c) 2021 Rodion Efremov
  * Copyright (c) 2023 The Refinery Authors <https://refinery.tools/>
  *
- * SPDX-License-Identifier: MIT OR EPL-2.0
+ * SPDX-License-Identifier: MIT
  */
 package tools.refinery.store.query.utils;
 
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/view/AbstractFunctionView.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/view/AbstractFunctionView.java
index fd37604e..f130fa59 100644
--- a/subprojects/store-query/src/main/java/tools/refinery/store/query/view/AbstractFunctionView.java
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/view/AbstractFunctionView.java
@@ -5,6 +5,7 @@
  */
 package tools.refinery.store.query.view;
 
+import tools.refinery.store.map.CursorAsIterator;
 import tools.refinery.store.model.Model;
 import tools.refinery.store.query.dnf.FunctionalDependency;
 import tools.refinery.store.query.term.Parameter;
@@ -83,6 +84,20 @@ public abstract class AbstractFunctionView<T> extends SymbolView<T> {
         }
 
         @Override
+        public boolean canIndexSlot(int slot) {
+                return slot >= 0 && slot < getSymbol().arity();
+        }
+
+        @Override
+        public Iterable<Object[]> getAdjacent(Model model, int slot, Object value) {
+                if (!(value instanceof Tuple1 tuple1)) {
+                        return Set.of();
+                }
+                return (() -> new CursorAsIterator<>(model.getInterpretation(getSymbol()).getAdjacent(slot, tuple1.get(0)),
+                                this::forwardMap, this::filter));
+        }
+
+        @Override
         public List<Parameter> getParameters() {
                 return parameters;
         }
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/view/AnySymbolView.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/view/AnySymbolView.java
index 90b27ebb..7e9bf6df 100644
--- a/subprojects/store-query/src/main/java/tools/refinery/store/query/view/AnySymbolView.java
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/view/AnySymbolView.java
@@ -28,4 +28,12 @@ public sealed interface AnySymbolView extends Constraint permits SymbolView {
         boolean get(Model model, Object[] tuple);
 
         Iterable<Object[]> getAll(Model model);
+
+        default Iterable<Object[]> getAdjacent(Model model, int slot, Object value) {
+                throw new IllegalArgumentException("Cannot index slot " + slot);
+        }
+
+        default boolean canIndexSlot(int slot) {
+                return false;
+        }
 }
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/view/FilteredView.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/view/FilteredView.java
index abae6e5c..924277ed 100644
--- a/subprojects/store-query/src/main/java/tools/refinery/store/query/view/FilteredView.java
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/view/FilteredView.java
@@ -5,6 +5,7 @@
  */
 package tools.refinery.store.query.view;
 
+import tools.refinery.store.query.InvalidQueryException;
 import tools.refinery.store.tuple.Tuple;
 import tools.refinery.store.representation.Symbol;
 
@@ -66,7 +67,7 @@ public class FilteredView<T> extends TuplePreservingView<T> {
                         // The predicate doesn't need to handle the default value if it is null.
                 }
                 if (matchesDefaultValue) {
-                        throw new IllegalArgumentException("Tuples with default value %s cannot be enumerated in %s"
+                        throw new InvalidQueryException("Tuples with default value %s cannot be enumerated in %s"
                                         .formatted(defaultValue, getSymbol()));
                 }
         }
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/view/TuplePreservingView.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/view/TuplePreservingView.java
index 6bc5a708..ed12cd9d 100644
--- a/subprojects/store-query/src/main/java/tools/refinery/store/query/view/TuplePreservingView.java
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/view/TuplePreservingView.java
@@ -5,6 +5,7 @@
  */
 package tools.refinery.store.query.view;
 
+import tools.refinery.store.map.CursorAsIterator;
 import tools.refinery.store.model.Model;
 import tools.refinery.store.query.term.Parameter;
 import tools.refinery.store.representation.Symbol;
@@ -14,6 +15,7 @@ import tools.refinery.store.tuple.Tuple1;
 import java.util.Arrays;
 import java.util.List;
 import java.util.Objects;
+import java.util.Set;
 
 public abstract class TuplePreservingView<T> extends SymbolView<T> {
         private final List<Parameter> parameters;
@@ -56,6 +58,20 @@ public abstract class TuplePreservingView<T> extends SymbolView<T> {
         }
 
         @Override
+        public boolean canIndexSlot(int slot) {
+                return slot >= 0 && slot < getSymbol().arity();
+        }
+
+        @Override
+        public Iterable<Object[]> getAdjacent(Model model, int slot, Object value) {
+                if (!(value instanceof Tuple1 tuple1)) {
+                        return Set.of();
+                }
+                return (() -> new CursorAsIterator<>(model.getInterpretation(getSymbol()).getAdjacent(slot, tuple1.get(0)),
+                                this::forwardMap, this::filter));
+        }
+
+        @Override
         public List<Parameter> getParameters() {
                 return parameters;
         }