refactor: simplified Dnf parameter directions

28 files changed, 392 insertions, 686 deletions

diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/pquery/Dnf2PQuery.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/pquery/Dnf2PQuery.java
index ec880435..5b0ea61d 100644
--- a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/pquery/Dnf2PQuery.java
+++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/pquery/Dnf2PQuery.java
@@ -88,8 +88,7 @@ public class Dnf2PQuery {
                 List<PParameter> parameterList = new ArrayList<>();
                 for (var parameter : dnfQuery.getSymbolicParameters()) {
                         var direction = switch (parameter.getDirection()) {
-                                case IN_OUT -> PParameterDirection.INOUT;
-                                case OUT -> PParameterDirection.OUT;
+                                case OUT -> parameter.isUnifiable() ? PParameterDirection.INOUT : PParameterDirection.OUT;
                                 case IN -> throw new IllegalArgumentException("Query %s with input parameter %s is not supported"
                                                 .formatted(dnfQuery, parameter.getVariable()));
                         };
@@ -154,9 +153,9 @@ public class Dnf2PQuery {
         }
 
         private void translateEquivalenceLiteral(EquivalenceLiteral equivalenceLiteral, PBody body) {
-                PVariable varSource = body.getOrCreateVariableByName(equivalenceLiteral.getLeft().getUniqueName());
-                PVariable varTarget = body.getOrCreateVariableByName(equivalenceLiteral.getRight().getUniqueName());
-                if (equivalenceLiteral.isPositive()) {
+                PVariable varSource = body.getOrCreateVariableByName(equivalenceLiteral.left().getUniqueName());
+                PVariable varTarget = body.getOrCreateVariableByName(equivalenceLiteral.right().getUniqueName());
+                if (equivalenceLiteral.positive()) {
                         new Equality(body, varSource, varTarget);
                 } else {
                         new Inequality(body, varSource, varTarget);
@@ -213,13 +212,13 @@ public class Dnf2PQuery {
         }
 
         private void translateConstantLiteral(ConstantLiteral constantLiteral, PBody body) {
-                var variable = body.getOrCreateVariableByName(constantLiteral.getVariable().getUniqueName());
-                new ConstantValue(body, variable, constantLiteral.getNodeId());
+                var variable = body.getOrCreateVariableByName(constantLiteral.variable().getUniqueName());
+                new ConstantValue(body, variable, constantLiteral.nodeId());
         }
 
         private <T> void translateAssignLiteral(AssignLiteral<T> assignLiteral, PBody body) {
-                var variable = body.getOrCreateVariableByName(assignLiteral.getTargetVariable().getUniqueName());
-                var term = assignLiteral.getTerm();
+                var variable = body.getOrCreateVariableByName(assignLiteral.variable().getUniqueName());
+                var term = assignLiteral.term();
                 if (term instanceof ConstantTerm<T> constantTerm) {
                         new ConstantValue(body, variable, constantTerm.getValue());
                 } else {
@@ -229,7 +228,7 @@ public class Dnf2PQuery {
         }
 
         private void translateAssumeLiteral(AssumeLiteral assumeLiteral, PBody body) {
-                var evaluator = new AssumptionEvaluator(assumeLiteral.getTerm());
+                var evaluator = new AssumptionEvaluator(assumeLiteral.term());
                 new ExpressionEvaluation(body, evaluator, null);
         }
 
diff --git a/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/QueryTest.java b/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/QueryTest.java
index 46ce37b4..a9a2f71c 100644
--- a/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/QueryTest.java
+++ b/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/QueryTest.java
@@ -23,7 +23,6 @@ import tools.refinery.store.tuple.Tuple;
 import java.util.List;
 import java.util.Map;
 
-import static org.junit.jupiter.api.Assertions.assertThrows;
 import static tools.refinery.store.query.literal.Literals.assume;
 import static tools.refinery.store.query.literal.Literals.not;
 import static tools.refinery.store.query.term.int_.IntTerms.constant;
@@ -707,14 +706,4 @@ class QueryTest {
                 queryEngine.flushChanges();
                 assertResults(Map.of(), predicateResultSet);
         }
-
-        @Test
-        void alwaysTrueTest() {
-                var p1 = Variable.of("p1");
-                var predicate = Query.builder("AlwaysTrue").parameters(p1).clause().build();
-
-                var queryBuilder = ViatraModelQueryAdapter.builder();
-
-                assertThrows(IllegalArgumentException.class, () -> queryBuilder.queries(predicate));
-        }
 }
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 467b8d52..dd45ecd4 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
@@ -9,35 +9,30 @@ 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.literal.VariableDirection;
 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;
 
 import java.util.*;
 import java.util.function.Function;
-import java.util.stream.Collectors;
 
 class ClausePostProcessor {
-        private final Set<Variable> parameters;
-        private final Map<Variable, Integer> parameterWeights;
+        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 List<Literal> substitutedLiterals;
         private final Set<Variable> existentiallyQuantifiedVariables = new LinkedHashSet<>();
-        private Set<Variable> inputParameters;
         private Set<Variable> positiveVariables;
         private Map<Variable, Set<SortableLiteral>> variableToLiteralInputMap;
         private PriorityQueue<SortableLiteral> literalsWithAllInputsBound;
         private LinkedHashSet<Literal> topologicallySortedLiterals;
 
-        public ClausePostProcessor(Set<Variable> parameters, Map<Variable, Integer> parameterWeights,
-                                                           List<Literal> literals) {
+        public ClausePostProcessor(Map<Variable, ParameterInfo> parameters, List<Literal> literals) {
                 this.parameters = parameters;
-                this.parameterWeights = parameterWeights;
                 this.literals = literals;
         }
 
@@ -46,9 +41,10 @@ class ClausePostProcessor {
                 substitutedLiterals = new ArrayList<>(literals.size());
                 keepParameterEquivalences();
                 substituteLiterals();
+                computeExistentiallyQuantifiedVariables();
                 computePositiveVariables();
                 validatePositiveRepresentatives();
-                validateClosureVariables();
+                validatePrivateVariables();
                 topologicallySortLiterals();
                 var filteredLiterals = new ArrayList<Literal>(topologicallySortedLiterals.size());
                 for (var literal : topologicallySortedLiterals) {
@@ -71,20 +67,21 @@ class ClausePostProcessor {
                 for (var literal : literals) {
                         if (isPositiveEquivalence(literal)) {
                                 var equivalenceLiteral = (EquivalenceLiteral) literal;
-                                mergeVariables(equivalenceLiteral.getLeft(), equivalenceLiteral.getRight());
+                                mergeVariables(equivalenceLiteral.left(), equivalenceLiteral.right());
                         }
                 }
         }
 
         private static boolean isPositiveEquivalence(Literal literal) {
-                return literal instanceof EquivalenceLiteral equivalenceLiteral && equivalenceLiteral.isPositive();
+                return literal instanceof EquivalenceLiteral equivalenceLiteral && equivalenceLiteral.positive();
         }
 
         private void mergeVariables(NodeVariable left, NodeVariable right) {
                 var leftRepresentative = getRepresentative(left);
                 var rightRepresentative = getRepresentative(right);
-                if (parameters.contains(leftRepresentative) && (!parameters.contains(rightRepresentative) ||
-                                parameterWeights.get(leftRepresentative).compareTo(parameterWeights.get(rightRepresentative)) <= 0)) {
+                var leftInfo = parameters.get(leftRepresentative);
+                var rightInfo = parameters.get(rightRepresentative);
+                if (leftInfo != null && (rightInfo == null || leftInfo.index() <= rightInfo.index())) {
                         // Prefer the variable occurring earlier in the parameter list as a representative.
                         doMergeVariables(leftRepresentative, rightRepresentative);
                 } else {
@@ -123,7 +120,7 @@ class ClausePostProcessor {
                 for (var pair : representatives.entrySet()) {
                         var left = pair.getKey();
                         var right = pair.getValue();
-                        if (!left.equals(right) && parameters.contains(left) && parameters.contains(right)) {
+                        if (!left.equals(right) && parameters.containsKey(left) && parameters.containsKey(right)) {
                                 substitutedLiterals.add(left.isEquivalent(right));
                         }
                 }
@@ -148,27 +145,37 @@ class ClausePostProcessor {
                 }
         }
 
-        private void computePositiveVariables() {
+        private void computeExistentiallyQuantifiedVariables() {
                 for (var literal : substitutedLiterals) {
-                        var variableBinder = literal.getVariableBindingSite();
-                        variableBinder.getVariablesWithDirection(VariableDirection.IN_OUT)
-                                        .forEach(existentiallyQuantifiedVariables::add);
-                        variableBinder.getVariablesWithDirection(VariableDirection.OUT).forEach(variable -> {
+                        for (var variable : literal.getOutputVariables()) {
                                 boolean added = existentiallyQuantifiedVariables.add(variable);
-                                if (!added) {
-                                        throw new IllegalArgumentException("Variable %s has multiple %s bindings"
-                                                        .formatted(variable, VariableDirection.OUT));
+                                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));
+                                        }
                                 }
-                        });
+                        }
+                }
+        }
+
+        private void computePositiveVariables() {
+                positiveVariables = new LinkedHashSet<>();
+                for (var pair : parameters.entrySet()) {
+                        var variable = pair.getKey();
+                        if (pair.getValue().direction() == ParameterDirection.IN) {
+                                // 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"
+                                                .formatted(ParameterDirection.OUT, variable));
+                        }
                 }
-                // Input parameters are parameters not bound by any positive literal.
-                inputParameters = new LinkedHashSet<>(parameters);
-                inputParameters.removeAll(existentiallyQuantifiedVariables);
-                // Existentially quantified variables are variables appearing in positive literals that aren't parameters.
-                existentiallyQuantifiedVariables.removeAll(parameters);
-                // Positive variables are parameters (including input parameters) and variables bound by positive literals.
-                positiveVariables = new LinkedHashSet<>(parameters.size() + existentiallyQuantifiedVariables.size());
-                positiveVariables.addAll(parameters);
                 positiveVariables.addAll(existentiallyQuantifiedVariables);
         }
 
@@ -183,19 +190,16 @@ class ClausePostProcessor {
                 }
         }
 
-        private void validateClosureVariables() {
+        private void validatePrivateVariables() {
                 var negativeVariablesMap = new HashMap<Variable, Literal>();
                 for (var literal : substitutedLiterals) {
-                        var variableBinder = literal.getVariableBindingSite();
-                        variableBinder.getVariablesWithDirection(VariableDirection.CLOSURE, positiveVariables)
-                                        .forEach(variable -> {
-                                                var oldLiteral = negativeVariablesMap.put(variable, literal);
-                                                if (oldLiteral != null) {
-                                                        throw new IllegalArgumentException(
-                                                                        "Unbound variable %s appears in multiple literals %s and %s"
-                                                                                        .formatted(variable, oldLiteral, literal));
-                                                }
-                                        });
+                        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"
+                                                        .formatted(variable, oldLiteral, literal));
+                                }
+                        }
                 }
         }
 
@@ -219,16 +223,6 @@ class ClausePostProcessor {
                 }
         }
 
-        private void topologicallySortVariable(Variable variable) {
-                var literalSetForInput = variableToLiteralInputMap.remove(variable);
-                if (literalSetForInput == null) {
-                        return;
-                }
-                for (var targetSortableLiteral : literalSetForInput) {
-                        targetSortableLiteral.bindVariable(variable);
-                }
-        }
-
         private class SortableLiteral implements Comparable<SortableLiteral> {
                 private final int index;
                 private final Literal literal;
@@ -237,10 +231,12 @@ class ClausePostProcessor {
                 private SortableLiteral(int index, Literal literal) {
                         this.index = index;
                         this.literal = literal;
-                        remainingInputs = literal.getVariableBindingSite()
-                                        .getVariablesWithDirection(VariableDirection.IN, positiveVariables)
-                                        .collect(Collectors.toCollection(HashSet::new));
-                        remainingInputs.removeAll(inputParameters);
+                        remainingInputs = new HashSet<>(literal.getInputVariables(positiveVariables));
+                        for (var pair : parameters.entrySet()) {
+                                if (pair.getValue().direction() == ParameterDirection.IN) {
+                                        remainingInputs.remove(pair.getKey());
+                                }
+                        }
                 }
 
                 public void enqueue() {
@@ -282,11 +278,15 @@ class ClausePostProcessor {
                         }
                         // Add literal if we haven't yet added a duplicate of this literal.
                         topologicallySortedLiterals.add(literal);
-                        var variableBinder = literal.getVariableBindingSite();
-                        variableBinder.getVariablesWithDirection(VariableDirection.IN_OUT)
-                                        .forEach(ClausePostProcessor.this::topologicallySortVariable);
-                        variableBinder.getVariablesWithDirection(VariableDirection.OUT)
-                                        .forEach(ClausePostProcessor.this::topologicallySortVariable);
+                        for (var variable : literal.getOutputVariables()) {
+                                var literalSetForInput = variableToLiteralInputMap.remove(variable);
+                                if (literalSetForInput == null) {
+                                        continue;
+                                }
+                                for (var targetSortableLiteral : literalSetForInput) {
+                                        targetSortableLiteral.bindVariable(variable);
+                                }
+                        }
                 }
 
                 @Override
@@ -318,4 +318,7 @@ class ClausePostProcessor {
                 ALWAYS_TRUE,
                 ALWAYS_FALSE
         }
+
+        public record ParameterInfo(ParameterDirection direction, int index) {
+        }
 }
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 3fac4627..dcf7611d 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
@@ -7,15 +7,18 @@ package tools.refinery.store.query.dnf;
 
 import tools.refinery.store.query.dnf.callback.*;
 import tools.refinery.store.query.literal.Literal;
-import tools.refinery.store.query.term.*;
+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 java.util.*;
 
 @SuppressWarnings("UnusedReturnValue")
 public final class DnfBuilder {
         private final String name;
-        private final List<Variable> parameters = new ArrayList<>();
-        private final Map<Variable, ParameterDirection> directions = new HashMap<>();
+        private final Set<Variable> parameterVariables = new LinkedHashSet<>();
+        private final List<SymbolicParameter> parameters = new ArrayList<>();
         private final List<FunctionalDependency<Variable>> functionalDependencies = new ArrayList<>();
         private final List<List<Literal>> clauses = new ArrayList<>();
 
@@ -28,20 +31,16 @@ public final class DnfBuilder {
         }
 
         public NodeVariable parameter(String name) {
-                var variable = Variable.of(name);
-                parameter(variable);
-                return variable;
+                return parameter(name, ParameterDirection.OUT);
         }
 
         public NodeVariable parameter(ParameterDirection direction) {
-                var variable = parameter();
-                putDirection(variable, direction);
-                return variable;
+                return parameter((String) null, direction);
         }
 
         public NodeVariable parameter(String name, ParameterDirection direction) {
-                var variable = parameter(name);
-                putDirection(variable, direction);
+                var variable = Variable.of(name);
+                parameter(variable, direction);
                 return variable;
         }
 
@@ -50,50 +49,25 @@ public final class DnfBuilder {
         }
 
         public <T> DataVariable<T> parameter(String name, Class<T> type) {
-                var variable = Variable.of(name, type);
-                parameter(variable);
-                return variable;
+                return parameter(name, type, ParameterDirection.OUT);
         }
 
         public <T> DataVariable<T> parameter(Class<T> type, ParameterDirection direction) {
-                var variable = parameter(type);
-                putDirection(variable, direction);
-                return variable;
+                return parameter(null, type, direction);
         }
 
         public <T> DataVariable<T> parameter(String name, Class<T> type, ParameterDirection direction) {
-                var variable = parameter(name, type);
-                putDirection(variable, direction);
+                var variable = Variable.of(name, type);
+                parameter(variable, direction);
                 return variable;
         }
 
         public DnfBuilder parameter(Variable variable) {
-                if (parameters.contains(variable)) {
-                        throw new IllegalArgumentException("Duplicate parameter: " + variable);
-                }
-                parameters.add(variable);
-                return this;
+                return parameter(variable, ParameterDirection.OUT);
         }
 
         public DnfBuilder parameter(Variable variable, ParameterDirection direction) {
-                parameter(variable);
-                putDirection(variable, direction);
-                return this;
-        }
-
-        private void putDirection(Variable variable, ParameterDirection direction) {
-                if (variable.tryGetType().isPresent()) {
-                        if (direction == ParameterDirection.IN_OUT) {
-                                throw new IllegalArgumentException("%s direction is forbidden for data variable %s"
-                                                .formatted(direction, variable));
-                        }
-                } else {
-                        if (direction == ParameterDirection.OUT) {
-                                throw new IllegalArgumentException("%s direction is forbidden for node variable %s"
-                                                .formatted(direction, variable));
-                        }
-                }
-                directions.put(variable, direction);
+                return symbolicParameter(new SymbolicParameter(variable, direction));
         }
 
         public DnfBuilder parameters(Variable... variables) {
@@ -101,10 +75,7 @@ public final class DnfBuilder {
         }
 
         public DnfBuilder parameters(Collection<? extends Variable> variables) {
-                for (var variable : variables) {
-                        parameter(variable);
-                }
-                return this;
+                return parameters(variables, ParameterDirection.OUT);
         }
 
         public DnfBuilder parameters(Collection<? extends Variable> variables, ParameterDirection direction) {
@@ -114,9 +85,23 @@ public final class DnfBuilder {
                 return this;
         }
 
-        public DnfBuilder symbolicParameters(Collection<SymbolicParameter> parameters) {
-                for (var parameter : parameters) {
-                        parameter(parameter.getVariable(), parameter.getDirection());
+        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"
+                                        .formatted(variable, parameters));
+                }
+                parameters.add(symbolicParameter);
+                return this;
+        }
+
+        public DnfBuilder symbolicParameters(SymbolicParameter... symbolicParameters) {
+                return symbolicParameters(List.of(symbolicParameters));
+        }
+
+        public DnfBuilder symbolicParameters(Collection<SymbolicParameter> symbolicParameters) {
+                for (var symbolicParameter : symbolicParameters) {
+                        symbolicParameter(symbolicParameter);
                 }
                 return this;
         }
@@ -214,24 +199,24 @@ public final class DnfBuilder {
         }
 
         <T> void output(DataVariable<T> outputVariable) {
-                var fromParameters = Set.copyOf(parameters);
+                // Copy parameter variables to exclude the newly added {@code outputVariable}.
+                var fromParameters = Set.copyOf(parameterVariables);
                 parameter(outputVariable, ParameterDirection.OUT);
                 functionalDependency(fromParameters, Set.of(outputVariable));
         }
 
         public Dnf build() {
                 var postProcessedClauses = postProcessClauses();
-                return new Dnf(name, createParameterList(postProcessedClauses),
+                return new Dnf(name, Collections.unmodifiableList(parameters),
                                 Collections.unmodifiableList(functionalDependencies),
                                 Collections.unmodifiableList(postProcessedClauses));
         }
 
         private List<DnfClause> postProcessClauses() {
-                var parameterSet = Collections.unmodifiableSet(new LinkedHashSet<>(parameters));
-                var parameterWeights = getParameterWeights();
+                var parameterInfoMap = getParameterInfoMap();
                 var postProcessedClauses = new ArrayList<DnfClause>(clauses.size());
                 for (var literals : clauses) {
-                        var postProcessor = new ClausePostProcessor(parameterSet, parameterWeights, literals);
+                        var postProcessor = new ClausePostProcessor(parameterInfoMap, literals);
                         var result = postProcessor.postProcessClause();
                         if (result instanceof ClausePostProcessor.ClauseResult clauseResult) {
                                 postProcessedClauses.add(clauseResult.clause());
@@ -253,54 +238,14 @@ public final class DnfBuilder {
                 return postProcessedClauses;
         }
 
-        private Map<Variable, Integer> getParameterWeights() {
-                var mutableParameterWeights = new HashMap<Variable, Integer>();
+        private Map<Variable, ClausePostProcessor.ParameterInfo> getParameterInfoMap() {
+                var mutableParameterInfoMap = new LinkedHashMap<Variable, ClausePostProcessor.ParameterInfo>();
                 int arity = parameters.size();
                 for (int i = 0; i < arity; i++) {
-                        mutableParameterWeights.put(parameters.get(i), i);
-                }
-                return Collections.unmodifiableMap(mutableParameterWeights);
-        }
-
-        private List<SymbolicParameter> createParameterList(List<DnfClause> postProcessedClauses) {
-                var outputParameterVariables = new HashSet<>(parameters);
-                for (var clause : postProcessedClauses) {
-                        outputParameterVariables.retainAll(clause.positiveVariables());
-                }
-                var parameterList = new ArrayList<SymbolicParameter>(parameters.size());
-                for (var parameter : parameters) {
-                        ParameterDirection direction = getDirection(outputParameterVariables, parameter);
-                        parameterList.add(new SymbolicParameter(parameter, direction));
-                }
-                return Collections.unmodifiableList(parameterList);
-        }
-
-        private ParameterDirection getDirection(HashSet<Variable> outputParameterVariables, Variable parameter) {
-                var direction = getInferredDirection(outputParameterVariables, parameter);
-                var expectedDirection = directions.get(parameter);
-                if (expectedDirection == ParameterDirection.IN && direction == ParameterDirection.IN_OUT) {
-                        // Parameters may be explicitly marked as {@code @In} even if they are bound in all clauses.
-                        return expectedDirection;
-                }
-                if (expectedDirection != null && expectedDirection != direction) {
-                        throw new IllegalArgumentException("Expected parameter %s to have direction %s, but got %s instead"
-                                        .formatted(parameter, expectedDirection, direction));
-                }
-                return direction;
-        }
-
-        private static ParameterDirection getInferredDirection(HashSet<Variable> outputParameterVariables,
-                                                                                                                   Variable parameter) {
-                if (outputParameterVariables.contains(parameter)) {
-                        if (parameter instanceof NodeVariable) {
-                                return ParameterDirection.IN_OUT;
-                        } else if (parameter instanceof AnyDataVariable) {
-                                return ParameterDirection.OUT;
-                        } else {
-                                throw new IllegalArgumentException("Unknown parameter: " + parameter);
-                        }
-                } else {
-                        return ParameterDirection.IN;
+                        var parameter = parameters.get(i);
+                        mutableParameterInfoMap.put(parameter.getVariable(),
+                                        new ClausePostProcessor.ParameterInfo(parameter.getDirection(), i));
                 }
+                return Collections.unmodifiableMap(mutableParameterInfoMap);
         }
 }
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 57cb8baf..6f253012 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
@@ -6,17 +6,20 @@
 package tools.refinery.store.query.dnf;
 
 import tools.refinery.store.query.literal.CallPolarity;
-import tools.refinery.store.query.term.*;
+import tools.refinery.store.query.term.Aggregator;
+import tools.refinery.store.query.term.AssignedValue;
+import tools.refinery.store.query.term.NodeVariable;
+import tools.refinery.store.query.term.Variable;
 
 import java.util.ArrayList;
 import java.util.List;
 import java.util.Objects;
 
-public final class FunctionalQuery<T> implements Query<T> {
-        private final Dnf dnf;
+public final class FunctionalQuery<T> extends Query<T> {
         private final Class<T> type;
 
         FunctionalQuery(Dnf dnf, Class<T> type) {
+                super(dnf);
                 var parameters = dnf.getSymbolicParameters();
                 int outputIndex = dnf.arity() - 1;
                 for (int i = 0; i < outputIndex; i++) {
@@ -33,18 +36,12 @@ public final class FunctionalQuery<T> implements Query<T> {
                         throw new IllegalArgumentException("Expected parameter %s of %s to be %s, but got %s instead".formatted(
                                         outputParameter, dnf, type, outputParameterType.map(Class::getName).orElse("node")));
                 }
-                this.dnf = dnf;
                 this.type = type;
         }
 
         @Override
-        public String name() {
-                return dnf.name();
-        }
-
-        @Override
         public int arity() {
-                return dnf.arity() - 1;
+                return getDnf().arity() - 1;
         }
 
         @Override
@@ -57,17 +54,12 @@ public final class FunctionalQuery<T> implements Query<T> {
                 return null;
         }
 
-        @Override
-        public Dnf getDnf() {
-                return dnf;
-        }
-
         public AssignedValue<T> call(List<NodeVariable> arguments) {
                 return targetVariable -> {
                         var argumentsWithTarget = new ArrayList<Variable>(arguments.size() + 1);
                         argumentsWithTarget.addAll(arguments);
                         argumentsWithTarget.add(targetVariable);
-                        return dnf.call(CallPolarity.POSITIVE, argumentsWithTarget);
+                        return getDnf().call(CallPolarity.POSITIVE, argumentsWithTarget);
                 };
         }
 
@@ -81,7 +73,9 @@ public final class FunctionalQuery<T> implements Query<T> {
                         var argumentsWithPlaceholder = new ArrayList<Variable>(arguments.size() + 1);
                         argumentsWithPlaceholder.addAll(arguments);
                         argumentsWithPlaceholder.add(placeholderVariable);
-                        return dnf.aggregate(placeholderVariable, aggregator, argumentsWithPlaceholder).toLiteral(targetVariable);
+                        return getDnf()
+                                        .aggregate(placeholderVariable, aggregator, argumentsWithPlaceholder)
+                                        .toLiteral(targetVariable);
                 };
         }
 
@@ -93,17 +87,13 @@ public final class FunctionalQuery<T> implements Query<T> {
         public boolean equals(Object o) {
                 if (this == o) return true;
                 if (o == null || getClass() != o.getClass()) return false;
+                if (!super.equals(o)) return false;
                 FunctionalQuery<?> that = (FunctionalQuery<?>) o;
-                return dnf.equals(that.dnf) && type.equals(that.type);
+                return Objects.equals(type, that.type);
         }
 
         @Override
         public int hashCode() {
-                return Objects.hash(dnf, type);
-        }
-
-        @Override
-        public String toString() {
-                return dnf.toString();
+                return Objects.hash(super.hashCode(), type);
         }
 }
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 e94c0c6b..aaa52ce6 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
@@ -6,113 +6,158 @@
 package tools.refinery.store.query.dnf;
 
 import tools.refinery.store.query.dnf.callback.*;
+import tools.refinery.store.query.term.ParameterDirection;
 import tools.refinery.store.query.term.Variable;
 
-public sealed interface Query<T> extends AnyQuery permits RelationalQuery, FunctionalQuery {
-        String OUTPUT_VARIABLE_NAME = "output";
+import java.util.Objects;
 
+public abstract sealed class Query<T> implements AnyQuery permits FunctionalQuery, RelationalQuery {
+        private static final String OUTPUT_VARIABLE_NAME = "output";
+
+        private final Dnf dnf;
+
+        protected Query(Dnf dnf) {
+                for (var parameter : dnf.getSymbolicParameters()) {
+                        if (parameter.getDirection() != ParameterDirection.OUT) {
+                                throw new IllegalArgumentException("Query parameter %s with direction %s is not allowed"
+                                                .formatted(parameter.getVariable(), parameter.getDirection()));
+                        }
+                }
+                this.dnf = dnf;
+        }
+
+        @Override
+        public String name() {
+                return dnf.name();
+        }
+
+        @Override
+        public Dnf getDnf() {
+                return dnf;
+        }
+
+        // Allow redeclaration of the method with refined return type.
+        @SuppressWarnings("squid:S3038")
         @Override
-        Class<T> valueType();
+        public abstract Class<T> valueType();
 
-        T defaultValue();
+        public abstract T defaultValue();
+
+        @Override
+        public boolean equals(Object o) {
+                if (this == o) return true;
+                if (o == null || getClass() != o.getClass()) return false;
+                Query<?> that = (Query<?>) o;
+                return Objects.equals(dnf, that.dnf);
+        }
+
+        @Override
+        public int hashCode() {
+                return Objects.hash(dnf);
+        }
+
+        @Override
+        public String toString() {
+                return dnf.toString();
+        }
 
-        static QueryBuilder builder() {
+        public static QueryBuilder builder() {
                 return builder(null);
         }
 
-        static QueryBuilder builder(String name) {
+        public static QueryBuilder builder(String name) {
                 return new QueryBuilder(name);
         }
 
-        static RelationalQuery of(QueryCallback0 callback) {
+        public static RelationalQuery of(QueryCallback0 callback) {
                 return of(null, callback);
         }
 
-        static RelationalQuery of(String name, QueryCallback0 callback) {
+        public static RelationalQuery of(String name, QueryCallback0 callback) {
                 var builder = builder(name);
                 callback.accept(builder);
                 return builder.build();
         }
 
-        static RelationalQuery of(QueryCallback1 callback) {
+        public static RelationalQuery of(QueryCallback1 callback) {
                 return of(null, callback);
         }
 
-        static RelationalQuery of(String name, QueryCallback1 callback) {
+        public static RelationalQuery of(String name, QueryCallback1 callback) {
                 var builder = builder(name);
                 callback.accept(builder, builder.parameter("p1"));
                 return builder.build();
         }
 
-        static RelationalQuery of(QueryCallback2 callback) {
+        public static RelationalQuery of(QueryCallback2 callback) {
                 return of(null, callback);
         }
 
-        static RelationalQuery of(String name, QueryCallback2 callback) {
+        public static RelationalQuery of(String name, QueryCallback2 callback) {
                 var builder = builder(name);
                 callback.accept(builder, builder.parameter("p1"), builder.parameter("p2"));
                 return builder.build();
         }
 
-        static RelationalQuery of(QueryCallback3 callback) {
+        public static RelationalQuery of(QueryCallback3 callback) {
                 return of(null, callback);
         }
 
-        static RelationalQuery of(String name, QueryCallback3 callback) {
+        public static RelationalQuery of(String name, QueryCallback3 callback) {
                 var builder = builder(name);
                 callback.accept(builder, builder.parameter("p1"), builder.parameter("p2"), builder.parameter("p3"));
                 return builder.build();
         }
 
-        static RelationalQuery of(QueryCallback4 callback) {
+        public static RelationalQuery of(QueryCallback4 callback) {
                 return of(null, callback);
         }
 
-        static RelationalQuery of(String name, QueryCallback4 callback) {
+        public static RelationalQuery of(String name, QueryCallback4 callback) {
                 var builder = builder(name);
                 callback.accept(builder, builder.parameter("p1"), builder.parameter("p2"), builder.parameter("p3"),
                                 builder.parameter("p4"));
                 return builder.build();
         }
 
-        static <T> FunctionalQuery<T> of(Class<T> type, FunctionalQueryCallback0<T> callback) {
+        public static <T> FunctionalQuery<T> of(Class<T> type, FunctionalQueryCallback0<T> callback) {
                 return of(null, type, callback);
         }
 
-        static <T> FunctionalQuery<T> of(String name, Class<T> type, FunctionalQueryCallback0<T> callback) {
+        public static <T> FunctionalQuery<T> of(String name, Class<T> type, FunctionalQueryCallback0<T> callback) {
                 var outputVariable = Variable.of(OUTPUT_VARIABLE_NAME, type);
                 var builder = builder(name).output(outputVariable);
                 callback.accept(builder, outputVariable);
                 return builder.build();
         }
 
-        static <T> FunctionalQuery<T> of(Class<T> type, FunctionalQueryCallback1<T> callback) {
+        public static <T> FunctionalQuery<T> of(Class<T> type, FunctionalQueryCallback1<T> callback) {
                 return of(null, type, callback);
         }
 
-        static <T> FunctionalQuery<T> of(String name, Class<T> type, FunctionalQueryCallback1<T> callback) {
+        public static <T> FunctionalQuery<T> of(String name, Class<T> type, FunctionalQueryCallback1<T> callback) {
                 var outputVariable = Variable.of(OUTPUT_VARIABLE_NAME, type);
                 var builder = builder(name).output(outputVariable);
                 callback.accept(builder, builder.parameter("p1"), outputVariable);
                 return builder.build();
         }
 
-        static <T> FunctionalQuery<T> of(Class<T> type, FunctionalQueryCallback2<T> callback) {
+        public static <T> FunctionalQuery<T> of(Class<T> type, FunctionalQueryCallback2<T> callback) {
                 return of(null, type, callback);
         }
 
-        static <T> FunctionalQuery<T> of(String name, Class<T> type, FunctionalQueryCallback2<T> callback) {
+        public static <T> FunctionalQuery<T> of(String name, Class<T> type, FunctionalQueryCallback2<T> callback) {
                 var outputVariable = Variable.of(OUTPUT_VARIABLE_NAME, type);
                 var builder = builder(name).output(outputVariable);
                 callback.accept(builder, builder.parameter("p1"), builder.parameter("p2"), outputVariable);
                 return builder.build();
         }
 
-        static <T> FunctionalQuery<T> of(Class<T> type, FunctionalQueryCallback3<T> callback) {
+        public static <T> FunctionalQuery<T> of(Class<T> type, FunctionalQueryCallback3<T> callback) {
                 return of(null, type, callback);
         }
 
-        static <T> FunctionalQuery<T> of(String name, Class<T> type, FunctionalQueryCallback3<T> callback) {
+        public static <T> FunctionalQuery<T> of(String name, Class<T> type, FunctionalQueryCallback3<T> callback) {
                 var outputVariable = Variable.of(OUTPUT_VARIABLE_NAME, type);
                 var builder = builder(name).output(outputVariable);
                 callback.accept(builder, builder.parameter("p1"), builder.parameter("p2"), builder.parameter("p3"),
@@ -120,11 +165,11 @@ public sealed interface Query<T> extends AnyQuery permits RelationalQuery, Funct
                 return builder.build();
         }
 
-        static <T> FunctionalQuery<T> of(Class<T> type, FunctionalQueryCallback4<T> callback) {
+        public static <T> FunctionalQuery<T> of(Class<T> type, FunctionalQueryCallback4<T> callback) {
                 return of(null, type, callback);
         }
 
-        static <T> FunctionalQuery<T> of(String name, Class<T> type, FunctionalQueryCallback4<T> callback) {
+        public static <T> FunctionalQuery<T> of(String name, Class<T> type, FunctionalQueryCallback4<T> callback) {
                 var outputVariable = Variable.of(OUTPUT_VARIABLE_NAME, type);
                 var builder = builder(name).output(outputVariable);
                 callback.accept(builder, builder.parameter("p1"), builder.parameter("p2"), builder.parameter("p3"),
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 c043a285..d34a7ace 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
@@ -12,12 +12,10 @@ import tools.refinery.store.query.term.NodeVariable;
 
 import java.util.Collections;
 import java.util.List;
-import java.util.Objects;
-
-public final class RelationalQuery implements Query<Boolean> {
-        private final Dnf dnf;
 
+public final class RelationalQuery extends Query<Boolean> {
         RelationalQuery(Dnf dnf) {
+                super(dnf);
                 for (var parameter : dnf.getSymbolicParameters()) {
                         var parameterType = parameter.tryGetType();
                         if (parameterType.isPresent()) {
@@ -25,17 +23,11 @@ public final class RelationalQuery implements Query<Boolean> {
                                                 .formatted(parameter, dnf, parameterType.get().getName()));
                         }
                 }
-                this.dnf = dnf;
-        }
-
-        @Override
-        public String name() {
-                return dnf.name();
         }
 
         @Override
         public int arity() {
-                return dnf.arity();
+                return getDnf().arity();
         }
 
         @Override
@@ -48,50 +40,27 @@ public final class RelationalQuery implements Query<Boolean> {
                 return false;
         }
 
-        @Override
-        public Dnf getDnf() {
-                return dnf;
-        }
-
         public CallLiteral call(CallPolarity polarity, List<NodeVariable> arguments) {
-                return dnf.call(polarity, Collections.unmodifiableList(arguments));
+                return getDnf().call(polarity, Collections.unmodifiableList(arguments));
         }
 
         public CallLiteral call(CallPolarity polarity, NodeVariable... arguments) {
-                return dnf.call(polarity, arguments);
+                return getDnf().call(polarity, arguments);
         }
 
         public CallLiteral call(NodeVariable... arguments) {
-                return dnf.call(arguments);
+                return getDnf().call(arguments);
         }
 
         public CallLiteral callTransitive(NodeVariable left, NodeVariable right) {
-                return dnf.callTransitive(left, right);
+                return getDnf().callTransitive(left, right);
         }
 
         public AssignedValue<Integer> count(List<NodeVariable> arguments) {
-                return dnf.count(Collections.unmodifiableList(arguments));
+                return getDnf().count(Collections.unmodifiableList(arguments));
         }
 
         public AssignedValue<Integer> count(NodeVariable... arguments) {
-                return dnf.count(arguments);
-        }
-
-        @Override
-        public boolean equals(Object o) {
-                if (this == o) return true;
-                if (o == null || getClass() != o.getClass()) return false;
-                RelationalQuery that = (RelationalQuery) o;
-                return dnf.equals(that.dnf);
-        }
-
-        @Override
-        public int hashCode() {
-                return Objects.hash(dnf);
-        }
-
-        @Override
-        public String toString() {
-                return dnf.toString();
+                return getDnf().count(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 e2f05bde..e0d3ba1f 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
@@ -23,10 +23,14 @@ public final class SymbolicParameter extends Parameter {
                 return variable;
         }
 
+        public boolean isUnifiable() {
+                return variable.isUnifiable();
+        }
+
         @Override
         public String toString() {
                 var direction = getDirection();
-                if (direction == ParameterDirection.IN_OUT) {
+                if (direction == ParameterDirection.OUT) {
                         return variable.toString();
                 }
                 return "%s %s".formatted(getDirection(), variable);
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 55db04e0..ed7d3401 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
@@ -8,14 +8,16 @@ 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.ParameterDirection;
 import tools.refinery.store.query.term.Variable;
 
-import java.util.List;
-import java.util.Objects;
+import java.util.*;
 
 public abstract class AbstractCallLiteral implements Literal {
         private final Constraint target;
         private final List<Variable> arguments;
+        private final Set<Variable> inArguments;
+        private final Set<Variable> outArguments;
 
         protected AbstractCallLiteral(Constraint target, List<Variable> arguments) {
                 int arity = target.arity();
@@ -25,6 +27,8 @@ public abstract class AbstractCallLiteral implements Literal {
                 }
                 this.target = target;
                 this.arguments = arguments;
+                var mutableInArguments = new LinkedHashSet<Variable>();
+                var mutableOutArguments = new LinkedHashSet<Variable>();
                 var parameters = target.getParameters();
                 for (int i = 0; i < arity; i++) {
                         var argument = arguments.get(i);
@@ -33,6 +37,36 @@ public abstract class AbstractCallLiteral implements Literal {
                                 throw new IllegalArgumentException("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);
+                                }
+                                mutableInArguments.add(argument);
+                        }
+                        case OUT -> {
+                                if (mutableInArguments.contains(argument)) {
+                                        checkInOutUnifiable(argument);
+                                } else if (!mutableOutArguments.add(argument)) {
+                                        checkDuplicateOutUnifiable(argument);
+                                }
+                        }
+                        }
+                }
+                inArguments = Collections.unmodifiableSet(mutableInArguments);
+                outArguments = Collections.unmodifiableSet(mutableOutArguments);
+        }
+
+        private static void checkInOutUnifiable(Variable argument) {
+                if (!argument.isUnifiable()) {
+                        throw new IllegalArgumentException("Arguments %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("Arguments %s cannot be bound multiple times".formatted(argument));
                 }
         }
 
@@ -44,6 +78,23 @@ public abstract class AbstractCallLiteral implements Literal {
                 return arguments;
         }
 
+        protected Set<Variable> getArgumentsOfDirection(ParameterDirection direction) {
+                return switch (direction) {
+                        case IN -> inArguments;
+                        case OUT -> outArguments;
+                };
+        }
+
+        @Override
+        public Set<Variable> getInputVariables(Set<? extends Variable> positiveVariablesInClause) {
+                return getArgumentsOfDirection(ParameterDirection.IN);
+        }
+
+        @Override
+        public Set<Variable> getPrivateVariables(Set<? extends Variable> positiveVariablesInClause) {
+                return Set.of();
+        }
+
         @Override
         public Literal substitute(Substitution substitution) {
                 var substitutedArguments = arguments.stream().map(substitution::getSubstitute).toList();
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 51a33c1f..b2fec430 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
@@ -8,19 +8,16 @@ 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.Aggregator;
-import tools.refinery.store.query.term.ConstantTerm;
-import tools.refinery.store.query.term.DataVariable;
-import tools.refinery.store.query.term.Variable;
+import tools.refinery.store.query.term.*;
 
 import java.util.List;
 import java.util.Objects;
+import java.util.Set;
 
 public class AggregationLiteral<R, T> extends AbstractCallLiteral {
         private final DataVariable<R> resultVariable;
         private final DataVariable<T> inputVariable;
         private final Aggregator<R, T> aggregator;
-        private final VariableBindingSite variableBindingSite;
 
         public AggregationLiteral(DataVariable<R> resultVariable, Aggregator<R, T> aggregator,
                                                           DataVariable<T> inputVariable, Constraint target, List<Variable> arguments) {
@@ -29,6 +26,10 @@ public class AggregationLiteral<R, T> extends AbstractCallLiteral {
                         throw new IllegalArgumentException("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"
+                                        .formatted(inputVariable, ParameterDirection.OUT));
+                }
                 if (!resultVariable.getType().equals(aggregator.getResultType())) {
                         throw new IllegalArgumentException("Result variable %s must of type %s, got %s instead".formatted(
                                         resultVariable, aggregator.getResultType().getName(), resultVariable.getType().getName()));
@@ -40,14 +41,6 @@ public class AggregationLiteral<R, T> extends AbstractCallLiteral {
                 this.resultVariable = resultVariable;
                 this.inputVariable = inputVariable;
                 this.aggregator = aggregator;
-                variableBindingSite = VariableBindingSite.builder()
-                                .variable(resultVariable, VariableDirection.OUT)
-                                .parameterList(false, target.getParameters(), arguments)
-                                .build();
-                if (variableBindingSite.getDirection(inputVariable) != VariableDirection.CLOSURE) {
-                        throw new IllegalArgumentException(("Input variable %s must appear in the argument list as an output " +
-                                        "variable and should not be bound anywhere else").formatted(inputVariable));
-                }
         }
 
         public DataVariable<R> getResultVariable() {
@@ -63,8 +56,8 @@ public class AggregationLiteral<R, T> extends AbstractCallLiteral {
         }
 
         @Override
-        public VariableBindingSite getVariableBindingSite() {
-                return variableBindingSite;
+        public Set<Variable> getOutputVariables() {
+                return Set.of(resultVariable);
         }
 
         @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 079ba6bb..dbf999a2 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
@@ -9,43 +9,38 @@ 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.Term;
+import tools.refinery.store.query.term.Variable;
 
+import java.util.Collections;
 import java.util.Objects;
+import java.util.Set;
 
-public final class AssignLiteral<T> implements Literal {
-        private final DataVariable<T> variable;
-        private final Term<T> term;
-        private final VariableBindingSite variableBindingSite;
-
-        public AssignLiteral(DataVariable<T> variable, Term<T> term) {
+public record AssignLiteral<T>(DataVariable<T> variable, Term<T> term) implements Literal {
+        public AssignLiteral {
                 if (!term.getType().equals(variable.getType())) {
                         throw new IllegalArgumentException("Term %s must be of type %s, got %s instead".formatted(
                                         term, variable.getType().getName(), term.getType().getName()));
                 }
-                this.variable = variable;
-                this.term = term;
                 var inputVariables = term.getInputVariables();
                 if (inputVariables.contains(variable)) {
                         throw new IllegalArgumentException("Result variable %s must not appear in the term %s".formatted(
                                         variable, term));
                 }
-                variableBindingSite = VariableBindingSite.builder()
-                                .variable(variable, VariableDirection.OUT)
-                                .variables(inputVariables, VariableDirection.IN)
-                                .build();
         }
 
-        public DataVariable<T> getTargetVariable() {
-                return variable;
+        @Override
+        public Set<Variable> getOutputVariables() {
+                return Set.of(variable);
         }
 
-        public Term<T> getTerm() {
-                return term;
+        @Override
+        public Set<Variable> getInputVariables(Set<? extends Variable> positiveVariablesInClause) {
+                return Collections.unmodifiableSet(term.getInputVariables());
         }
 
         @Override
-        public VariableBindingSite getVariableBindingSite() {
-                return variableBindingSite;
+        public Set<Variable> getPrivateVariables(Set<? extends Variable> positiveVariablesInClause) {
+                return Set.of();
         }
 
         @Override
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/AssumeLiteral.java
index 3dfb8902..1ca04c77 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/AssumeLiteral.java
@@ -9,33 +9,36 @@ import tools.refinery.store.query.equality.LiteralEqualityHelper;
 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 java.util.Collections;
 import java.util.Objects;
+import java.util.Set;
 
-public final class AssumeLiteral implements Literal {
-        private final Term<Boolean> term;
-        private final VariableBindingSite variableBindingSite;
-
-        public AssumeLiteral(Term<Boolean> term) {
+public record AssumeLiteral(Term<Boolean> term) implements Literal {
+        public AssumeLiteral {
                 if (!term.getType().equals(Boolean.class)) {
                         throw new IllegalArgumentException("Term %s must be of type %s, got %s instead".formatted(
                                         term, Boolean.class.getName(), term.getType().getName()));
                 }
-                this.term = term;
-                variableBindingSite = VariableBindingSite.builder()
-                                .variables(term.getInputVariables(), VariableDirection.IN)
-                                .build();
         }
 
-        public Term<Boolean> getTerm() {
-                return term;
+        @Override
+        public Set<Variable> getOutputVariables() {
+                return Set.of();
+        }
+
+        @Override
+        public Set<Variable> getInputVariables(Set<? extends Variable> positiveVariablesInClause) {
+                return Collections.unmodifiableSet(term.getInputVariables());
         }
 
         @Override
-        public VariableBindingSite getVariableBindingSite() {
-                return variableBindingSite;
+        public Set<Variable> getPrivateVariables(Set<? extends Variable> positiveVariablesInClause) {
+                return Set.of();
         }
 
+
         @Override
         public Literal substitute(Substitution substitution) {
                 return new AssumeLiteral(term.substitute(substitution));
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 736b3537..f312d202 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
@@ -7,6 +7,9 @@ package tools.refinery.store.query.literal;
 
 import tools.refinery.store.query.equality.LiteralEqualityHelper;
 import tools.refinery.store.query.substitution.Substitution;
+import tools.refinery.store.query.term.Variable;
+
+import java.util.Set;
 
 public enum BooleanLiteral implements CanNegate<BooleanLiteral> {
         TRUE(true),
@@ -19,8 +22,18 @@ public enum BooleanLiteral implements CanNegate<BooleanLiteral> {
         }
 
         @Override
-        public VariableBindingSite getVariableBindingSite() {
-                return VariableBindingSite.EMPTY;
+        public Set<Variable> getOutputVariables() {
+                return Set.of();
+        }
+
+        @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
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 4f755e95..27d8ad60 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
@@ -8,14 +8,13 @@ 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.ParameterDirection;
 import tools.refinery.store.query.term.Variable;
 
-import java.util.List;
-import java.util.Objects;
+import java.util.*;
 
 public final class CallLiteral extends AbstractCallLiteral implements CanNegate<CallLiteral> {
         private final CallPolarity polarity;
-        private final VariableBindingSite variableBindingSite;
 
         public CallLiteral(CallPolarity polarity, Constraint target, List<Variable> arguments) {
                 super(target, arguments);
@@ -30,9 +29,6 @@ public final class CallLiteral extends AbstractCallLiteral implements CanNegate<
                         }
                 }
                 this.polarity = polarity;
-                variableBindingSite = VariableBindingSite.builder()
-                                .parameterList(polarity.isPositive(), parameters, arguments)
-                                .build();
         }
 
         public CallPolarity getPolarity() {
@@ -40,13 +36,16 @@ public final class CallLiteral extends AbstractCallLiteral implements CanNegate<
         }
 
         @Override
-        public VariableBindingSite getVariableBindingSite() {
-                return variableBindingSite;
+        protected Literal doSubstitute(Substitution substitution, List<Variable> substitutedArguments) {
+                return new CallLiteral(polarity, getTarget(), substitutedArguments);
         }
 
         @Override
-        protected Literal doSubstitute(Substitution substitution, List<Variable> substitutedArguments) {
-                return new CallLiteral(polarity, getTarget(), substitutedArguments);
+        public Set<Variable> getOutputVariables() {
+                if (polarity.isPositive()) {
+                        return getArgumentsOfDirection(ParameterDirection.OUT);
+                }
+                return Set.of();
         }
 
         @Override
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 1bc14bab..73545620 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
@@ -8,31 +8,25 @@ package tools.refinery.store.query.literal;
 import tools.refinery.store.query.equality.LiteralEqualityHelper;
 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 final class ConstantLiteral implements Literal {
-        private final NodeVariable variable;
-        private final int nodeId;
-        private final VariableBindingSite variableBindingSite;
-
-        public ConstantLiteral(NodeVariable variable, int nodeId) {
-                this.variable = variable;
-                this.nodeId = nodeId;
-                variableBindingSite = VariableBindingSite.builder().variable(variable, VariableDirection.IN_OUT).build();
-        }
-
-        public NodeVariable getVariable() {
-                return variable;
+public record ConstantLiteral(NodeVariable variable, int nodeId) implements Literal {
+        @Override
+        public Set<Variable> getOutputVariables() {
+                return Set.of(variable);
         }
 
-        public int getNodeId() {
-                return nodeId;
+        @Override
+        public Set<Variable> getInputVariables(Set<? extends Variable> positiveVariablesInClause) {
+                return Set.of();
         }
 
         @Override
-        public VariableBindingSite getVariableBindingSite() {
-                return variableBindingSite;
+        public Set<Variable> getPrivateVariables(Set<? extends Variable> positiveVariablesInClause) {
+                return Set.of();
         }
 
         @Override
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 0a47aa66..4d4749c8 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
@@ -14,10 +14,10 @@ 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;
-        private final VariableBindingSite variableBindingSite;
 
         public CountLiteral(DataVariable<Integer> resultVariable, Constraint target, List<Variable> arguments) {
                 super(target, arguments);
@@ -30,10 +30,6 @@ public class CountLiteral extends AbstractCallLiteral {
                                         .formatted(resultVariable));
                 }
                 this.resultVariable = resultVariable;
-                variableBindingSite = VariableBindingSite.builder()
-                                .variable(resultVariable, VariableDirection.OUT)
-                                .parameterList(false, target.getParameters(), arguments)
-                                .build();
         }
 
         public DataVariable<Integer> getResultVariable() {
@@ -41,8 +37,8 @@ public class CountLiteral extends AbstractCallLiteral {
         }
 
         @Override
-        public VariableBindingSite getVariableBindingSite() {
-                return variableBindingSite;
+        public Set<Variable> getOutputVariables() {
+                return Set.of(resultVariable);
         }
 
         @Override
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 b36c0e40..28ba7625 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
@@ -8,41 +8,26 @@ package tools.refinery.store.query.literal;
 import tools.refinery.store.query.equality.LiteralEqualityHelper;
 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 final class EquivalenceLiteral
+public record EquivalenceLiteral(boolean positive, NodeVariable left, NodeVariable right)
                 implements CanNegate<EquivalenceLiteral> {
-        private final boolean positive;
-        private final NodeVariable left;
-        private final NodeVariable right;
-        private final VariableBindingSite variableBindingSite;
-
-        public EquivalenceLiteral(boolean positive, NodeVariable left, NodeVariable right) {
-                this.positive = positive;
-                this.left = left;
-                this.right = right;
-                variableBindingSite = VariableBindingSite.builder()
-                                .variable(left, positive ? VariableDirection.IN_OUT : VariableDirection.IN)
-                                .variable(right, VariableDirection.IN)
-                                .build();
-        }
-
-        public boolean isPositive() {
-                return positive;
-        }
-
-        public NodeVariable getLeft() {
-                return left;
+        @Override
+        public Set<Variable> getOutputVariables() {
+                return Set.of(left);
         }
 
-        public NodeVariable getRight() {
-                return right;
+        @Override
+        public Set<Variable> getInputVariables(Set<? extends Variable> positiveVariablesInClause) {
+                return Set.of(right);
         }
 
         @Override
-        public VariableBindingSite getVariableBindingSite() {
-                return variableBindingSite;
+        public Set<Variable> getPrivateVariables(Set<? extends Variable> positiveVariablesInClause) {
+                return Set.of();
         }
 
         @Override
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 10e4cffd..ce6c11fe 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
@@ -7,9 +7,16 @@ package tools.refinery.store.query.literal;
 
 import tools.refinery.store.query.equality.LiteralEqualityHelper;
 import tools.refinery.store.query.substitution.Substitution;
+import tools.refinery.store.query.term.Variable;
+
+import java.util.Set;
 
 public interface Literal {
-        VariableBindingSite getVariableBindingSite();
+        Set<Variable> getOutputVariables();
+
+        Set<Variable> getInputVariables(Set<? extends Variable> positiveVariablesInClause);
+
+        Set<Variable> getPrivateVariables(Set<? extends Variable> positiveVariablesInClause);
 
         Literal substitute(Substitution substitution);
 
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/VariableBindingSite.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/VariableBindingSite.java
deleted file mode 100644
index 624af045..00000000
--- a/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/VariableBindingSite.java
+++ /dev/null
@@ -1,64 +0,0 @@
-/*
- * 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.term.Variable;
-
-import java.util.Map;
-import java.util.Set;
-import java.util.stream.Stream;
-
-public final class VariableBindingSite {
-        public static final VariableBindingSite EMPTY = new VariableBindingSite(Map.of());
-
-        private final Map<Variable, VariableDirection> directionMap;
-
-        VariableBindingSite(Map<Variable, VariableDirection> directionMap) {
-                this.directionMap = directionMap;
-        }
-
-        public VariableDirection getDirection(Variable variable) {
-                var direction = directionMap.get(variable);
-                if (direction == null) {
-                        throw new IllegalArgumentException("No such variable " + variable);
-                }
-                return direction;
-        }
-
-        public VariableDirection getDirection(Variable variable, Set<? extends Variable> positiveVariables) {
-                var direction = getDirection(variable);
-                return disambiguateDirection(direction, variable, positiveVariables);
-        }
-
-        public Stream<Variable> getVariablesWithDirection(VariableDirection direction) {
-                return directionMap.entrySet().stream()
-                                .filter(pair -> pair.getValue() == direction)
-                                .map(Map.Entry::getKey);
-        }
-
-        public Stream<Variable> getVariablesWithDirection(VariableDirection direction,
-                                                                                                          Set<? extends Variable> positiveVariables) {
-                if (direction == VariableDirection.NEUTRAL) {
-                        throw new IllegalArgumentException("Use #getVariablesWithDirection(VariableDirection) if disambiguation " +
-                                        "of VariableDirection#NEUTRAL variables according to the containing DnfClose is not desired");
-                }
-                return directionMap.entrySet().stream()
-                                .filter(pair -> disambiguateDirection(pair.getValue(), pair.getKey(), positiveVariables) == direction)
-                                .map(Map.Entry::getKey);
-        }
-
-        private VariableDirection disambiguateDirection(VariableDirection direction, Variable variable,
-                                                                                                        Set<? extends Variable> positiveVariables) {
-                if (direction != VariableDirection.NEUTRAL) {
-                        return direction;
-                }
-                return positiveVariables.contains(variable) ? VariableDirection.IN : VariableDirection.CLOSURE;
-        }
-
-        public static VariableBindingSiteBuilder builder() {
-                return new VariableBindingSiteBuilder();
-        }
-}
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/VariableBindingSiteBuilder.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/VariableBindingSiteBuilder.java
deleted file mode 100644
index 873db1ec..00000000
--- a/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/VariableBindingSiteBuilder.java
+++ /dev/null
@@ -1,137 +0,0 @@
-/*
- * 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.exceptions.IncompatibleParameterDirectionException;
-import tools.refinery.store.query.term.*;
-
-import java.util.*;
-
-public final class VariableBindingSiteBuilder {
-        private final Map<Variable, VariableDirection> directionMap = new LinkedHashMap<>();
-        private final Set<Variable> nonUnifiableVariables = new HashSet<>();
-
-        VariableBindingSiteBuilder() {
-        }
-
-        public VariableBindingSiteBuilder variable(Variable variable, VariableDirection direction) {
-                return variable(variable, direction, direction == VariableDirection.OUT);
-        }
-
-        public VariableBindingSiteBuilder variable(Variable variable, VariableDirection direction, boolean markAsUnique) {
-                validateUnique(direction, markAsUnique);
-                validateDirection(variable, direction);
-                boolean unique;
-                if (markAsUnique) {
-                        nonUnifiableVariables.add(variable);
-                        unique = true;
-                } else {
-                        unique = nonUnifiableVariables.contains(variable);
-                }
-                directionMap.compute(variable, (ignored, oldValue) -> {
-                        if (oldValue == null) {
-                                return direction;
-                        }
-                        if (unique) {
-                                throw new IllegalArgumentException("Duplicate binding for variable " + variable);
-                        }
-                        try {
-                                return merge(oldValue, direction);
-                        } catch (IncompatibleParameterDirectionException e) {
-                                var message = "%s for variable %s".formatted(e.getMessage(), variable);
-                                throw new IncompatibleParameterDirectionException(message, e);
-                        }
-                });
-                return this;
-        }
-
-        private static void validateUnique(VariableDirection direction, boolean markAsUnique) {
-                if (direction == VariableDirection.OUT && !markAsUnique) {
-                        throw new IllegalArgumentException("OUT binding must be marked as non-unifiable");
-                }
-                if (markAsUnique && (direction != VariableDirection.OUT && direction != VariableDirection.CLOSURE)) {
-                        throw new IllegalArgumentException("Only OUT or CLOSURE binding may be marked as non-unifiable");
-                }
-        }
-
-        private static void validateDirection(Variable variable, VariableDirection direction) {
-                if (variable instanceof AnyDataVariable) {
-                        if (direction == VariableDirection.IN_OUT) {
-                                throw new IllegalArgumentException("%s direction is not supported for data variable %s"
-                                                .formatted(direction, variable));
-                        }
-                } else if (variable instanceof NodeVariable) {
-                        if (direction == VariableDirection.OUT) {
-                                throw new IllegalArgumentException("%s direction is not supported for node variable %s"
-                                                .formatted(direction, variable));
-                        }
-                } else {
-                        throw new IllegalArgumentException("Unknown variable " + variable);
-                }
-        }
-
-        private static VariableDirection merge(VariableDirection left, VariableDirection right) {
-                return switch (left) {
-                        case IN_OUT -> switch (right) {
-                                case IN_OUT -> VariableDirection.IN_OUT;
-                                case OUT -> VariableDirection.OUT;
-                                case IN, NEUTRAL -> VariableDirection.IN;
-                                case CLOSURE -> throw incompatibleDirections(left, right);
-                        };
-                        case OUT -> switch (right) {
-                                case IN_OUT, OUT -> VariableDirection.OUT;
-                                case IN, NEUTRAL, CLOSURE -> throw incompatibleDirections(left, right);
-                        };
-                        case IN -> switch (right) {
-                                case IN_OUT, NEUTRAL, IN -> VariableDirection.IN;
-                                case OUT, CLOSURE -> throw incompatibleDirections(left, right);
-                        };
-                        case NEUTRAL -> switch (right) {
-                                case IN_OUT, IN -> VariableDirection.IN;
-                                case NEUTRAL -> VariableDirection.NEUTRAL;
-                                case CLOSURE -> VariableDirection.CLOSURE;
-                                case OUT -> throw incompatibleDirections(left, right);
-                        };
-                        case CLOSURE -> switch (right) {
-                                case NEUTRAL, CLOSURE -> VariableDirection.CLOSURE;
-                                case IN_OUT, IN, OUT -> throw incompatibleDirections(left, right);
-                        };
-                };
-        }
-
-        private static RuntimeException incompatibleDirections(VariableDirection left, VariableDirection right) {
-                return new IncompatibleParameterDirectionException("Incompatible variable directions %s and %s"
-                                .formatted(left, right));
-        }
-
-        public VariableBindingSiteBuilder variables(Collection<? extends Variable> variables, VariableDirection direction) {
-                for (var variable : variables) {
-                        variable(variable, direction);
-                }
-                return this;
-        }
-
-        public VariableBindingSiteBuilder parameterList(boolean positive, List<Parameter> parameters,
-                                                                                                        List<Variable> arguments) {
-                int arity = parameters.size();
-                if (arity != arguments.size()) {
-                        throw new IllegalArgumentException("Got %d arguments for %d parameters"
-                                        .formatted(arguments.size(), arity));
-                }
-                for (int i = 0; i < arity; i++) {
-                        var argument = arguments.get(i);
-                        var parameter = parameters.get(i);
-                        var parameterDirection = parameter.getDirection();
-                        var direction = VariableDirection.from(positive, parameterDirection);
-                        variable(argument, direction, parameterDirection == ParameterDirection.OUT);
-                }
-                return this;
-        }
-
-        public VariableBindingSite build() {
-                return new VariableBindingSite(directionMap);
-        }
-}
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/VariableDirection.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/VariableDirection.java
deleted file mode 100644
index 0b7a2960..00000000
--- a/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/VariableDirection.java
+++ /dev/null
@@ -1,82 +0,0 @@
-/*
- * 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.term.ParameterDirection;
-
-/**
- * Directions of the flow of a variable to ro from a clause.
- * <p>
- * During the evaluation of a clause
- * <ol>
- *     <li>reads already bound {@code IN} variables,</li>
- *     <li>enumerates over all possible bindings of {@code CLOSURE} variables, and</li>
- *     <li>
- *         produces bindings for
- *         <ul>
- *             <li>{@code IN_OUT} variables that may already be bound in clause (if they already have a binding,
- *             the existing values are compared to the new binding by {@link Object#equals(Object)}), and</li>
- *             <li>{@code OUT} variables that must not be already bound in the clause (because comparison by
- *             equality wouldn't produce an appropriate join).</li>
- *         </ul>
- *     </li>
- * </ol>
- * Variables marked as {@code NEUTRAL} may act as {@code IN} or {@code CLOSURE} depending on whether they have an
- * existing binding that can be read.
- */
-public enum VariableDirection {
-        /**
-         * Binds a node variable or check equality with a node variable.
-         * <p>
-         * This is the usual direction for positive constraints on nodes. A data variable may have multiple {@code IN_OUT}
-         * bindings, even on the same parameter list.
-         * <p>
-         * Cannot be used for data variables.
-         */
-        IN_OUT,
-
-        /**
-         * Binds a data variable.
-         * <p>
-         * A single variable must have at most one {@code OUT} binding. A variable with a {@code OUT} binding cannot
-         * appear in any other place in a parameter list.
-         * <p>
-         * Cannot be used for node variables.
-         */
-        OUT,
-
-        /**
-         * Takes an already bound variable.
-         * <p>
-         * May be used with node or data variables. An {@code IN_OUT} or {@code OUT} binding on the same parameter list
-         * cannot satisfy the {@code IN} binding, because it might introduce a (non-monotonic) circular dependency.
-         */
-        IN,
-
-        /**
-         * Either takes a bound data variable or enumerates all possible data variable bindings.
-         * <p>
-         * Cannot be used for data variables.
-         */
-        NEUTRAL,
-
-        /**
-         * Enumerates over all possible data variable bindings.
-         * <p>
-         * May be used with node or data variables. The variable may not appear in any other parameter list. A data
-         * variable may only appear once in the parameter list, but node variables can appear multiple times to form
-         * diagonal constraints.
-         */
-        CLOSURE;
-
-        public static VariableDirection from(boolean positive, ParameterDirection parameterDirection) {
-                return switch (parameterDirection) {
-                        case IN_OUT -> positive ? IN_OUT : NEUTRAL;
-                        case OUT -> positive ? OUT : CLOSURE;
-                        case IN -> IN;
-                };
-        }
-}
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 5864ee56..192c39c5 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
@@ -37,6 +37,11 @@ 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/NodeVariable.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/term/NodeVariable.java
index 37f9d477..a2f3261f 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
@@ -22,6 +22,11 @@ public final class NodeVariable extends Variable {
         }
 
         @Override
+        public boolean isUnifiable() {
+                return true;
+        }
+
+        @Override
         public NodeVariable renew(@Nullable String name) {
                 return Variable.of(name);
         }
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 351a353d..0fe297ab 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,7 +9,7 @@ import java.util.Objects;
 import java.util.Optional;
 
 public class Parameter {
-        public static final Parameter NODE_IN_OUT = new Parameter(null, ParameterDirection.IN_OUT);
+        public static final Parameter NODE_IN_OUT = new Parameter(null, ParameterDirection.OUT);
 
         private final Class<?> dataType;
         private final ParameterDirection direction;
@@ -17,13 +17,6 @@ public class Parameter {
         public Parameter(Class<?> dataType, ParameterDirection direction) {
                 this.dataType = dataType;
                 this.direction = direction;
-                if (isDataVariable()) {
-                        if (direction == ParameterDirection.IN_OUT) {
-                                throw new IllegalArgumentException("IN_OUT direction is not supported for data parameters");
-                        }
-                } else if (direction == ParameterDirection.OUT) {
-                        throw new IllegalArgumentException("OUT direction is not supported for node parameters");
-                }
         }
 
         public boolean isNodeVariable() {
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 652208aa..cd0739be 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,7 +6,6 @@
 package tools.refinery.store.query.term;
 
 public enum ParameterDirection {
-        IN_OUT("@InOut"),
         OUT("@Out"),
         IN("@In");
 
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 869120fa..a0268c8e 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,6 +38,8 @@ 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();
diff --git a/subprojects/store-query/src/test/java/tools/refinery/store/query/dnf/DnfBuilderLiteralEliminationTest.java b/subprojects/store-query/src/test/java/tools/refinery/store/query/dnf/DnfBuilderLiteralEliminationTest.java
index 4edea401..687b06db 100644
--- a/subprojects/store-query/src/test/java/tools/refinery/store/query/dnf/DnfBuilderLiteralEliminationTest.java
+++ b/subprojects/store-query/src/test/java/tools/refinery/store/query/dnf/DnfBuilderLiteralEliminationTest.java
@@ -10,6 +10,7 @@ import org.junit.jupiter.params.ParameterizedTest;
 import org.junit.jupiter.params.provider.CsvSource;
 import tools.refinery.store.query.literal.BooleanLiteral;
 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.bool.BoolTerms;
 import tools.refinery.store.query.view.KeyOnlyView;
@@ -28,7 +29,7 @@ class DnfBuilderLiteralEliminationTest {
         private final SymbolView<Boolean> friendView = new KeyOnlyView<>(friend);
         private final NodeVariable p = Variable.of("p");
         private final NodeVariable q = Variable.of("q");
-        private final Dnf trueDnf = Dnf.builder().parameter(p).clause().build();
+        private final Dnf trueDnf = Dnf.builder().parameter(p, ParameterDirection.IN).clause().build();
         private final Dnf falseDnf = Dnf.builder().parameter(p).build();
 
         @Test
@@ -84,11 +85,11 @@ class DnfBuilderLiteralEliminationTest {
         @Test
         void alwaysTrueTest() {
                 var actual = Dnf.builder()
-                                .parameters(p, q)
+                                .parameters(List.of(p, q), ParameterDirection.IN)
                                 .clause(friendView.call(p, q))
                                 .clause(BooleanLiteral.TRUE)
                                 .build();
-                var expected = Dnf.builder().parameters(p, q).clause().build();
+                var expected = Dnf.builder().parameters(List.of(p, q), ParameterDirection.IN).clause().build();
 
                 assertThat(actual, structurallyEqualTo(expected));
         }
@@ -130,11 +131,11 @@ class DnfBuilderLiteralEliminationTest {
         @Test
         void alwaysTrueDnfTest() {
                 var actual = Dnf.builder()
-                                .parameters(p, q)
+                                .parameters(List.of(p, q), ParameterDirection.IN)
                                 .clause(friendView.call(p, q))
                                 .clause(trueDnf.call(q))
                                 .build();
-                var expected = Dnf.builder().parameters(p, q).clause().build();
+                var expected = Dnf.builder().parameters(List.of(p, q), ParameterDirection.IN).clause().build();
 
                 assertThat(actual, structurallyEqualTo(expected));
         }
@@ -176,11 +177,11 @@ class DnfBuilderLiteralEliminationTest {
         @Test
         void alwaysNotFalseDnfTest() {
                 var actual = Dnf.builder()
-                                .parameters(p, q)
+                                .parameters(List.of(p, q), ParameterDirection.IN)
                                 .clause(friendView.call(p, q))
                                 .clause(not(falseDnf.call(q)))
                                 .build();
-                var expected = Dnf.builder().parameters(p, q).clause().build();
+                var expected = Dnf.builder().parameters(List.of(p, q), ParameterDirection.IN).clause().build();
 
                 assertThat(actual, structurallyEqualTo(expected));
         }
diff --git a/subprojects/store-query/src/test/java/tools/refinery/store/query/dnf/DnfToDefinitionStringTest.java b/subprojects/store-query/src/test/java/tools/refinery/store/query/dnf/DnfToDefinitionStringTest.java
index 2e93d78a..63310a78 100644
--- a/subprojects/store-query/src/test/java/tools/refinery/store/query/dnf/DnfToDefinitionStringTest.java
+++ b/subprojects/store-query/src/test/java/tools/refinery/store/query/dnf/DnfToDefinitionStringTest.java
@@ -6,6 +6,7 @@
 package tools.refinery.store.query.dnf;
 
 import org.junit.jupiter.api.Test;
+import tools.refinery.store.query.term.ParameterDirection;
 import tools.refinery.store.query.term.Variable;
 import tools.refinery.store.query.view.KeyOnlyView;
 import tools.refinery.store.representation.Symbol;
@@ -39,7 +40,7 @@ class DnfToDefinitionStringTest {
         @Test
         void emptyClauseTest() {
                 var p = Variable.of("p");
-                var dnf = Dnf.builder("Example").parameter(p).clause().build();
+                var dnf = Dnf.builder("Example").parameter(p, ParameterDirection.IN).clause().build();
 
                 assertThat(dnf.toDefinitionString(), is("""
                                 pred Example(@In p) <->
@@ -67,10 +68,13 @@ class DnfToDefinitionStringTest {
                 var q = Variable.of("q");
                 var friend = new Symbol<>("friend", 2, Boolean.class, false);
                 var friendView = new KeyOnlyView<>(friend);
-                var dnf = Dnf.builder("Example").parameter(p).clause(not(friendView.call(p, q))).build();
+                var dnf = Dnf.builder("Example")
+                                .parameter(p, ParameterDirection.IN)
+                                .clause(not(friendView.call(p, q)))
+                                .build();
 
                 assertThat(dnf.toDefinitionString(), is("""
-                                pred Example(p) <->
+                                pred Example(@In p) <->
                                     !(@RelationView("key") friend(p, q)).
                                 """));
         }