refactor: split query and partial from store

Allows more complicated dependency hiearchies (e.g., use
store-query-viatra for testing store-partial) and better separation of
test fixtures.

30 files changed, 1050 insertions, 0 deletions

diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/Dnf.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/Dnf.java
new file mode 100644
index 00000000..760b264b
--- /dev/null
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/Dnf.java
@@ -0,0 +1,112 @@
+package tools.refinery.store.query;
+
+import tools.refinery.store.query.literal.CallPolarity;
+import tools.refinery.store.query.literal.DnfCallLiteral;
+import tools.refinery.store.query.literal.LiteralReduction;
+
+import java.util.*;
+
+public final class Dnf implements RelationLike {
+        private final String name;
+
+        private final String uniqueName;
+
+        private final List<Variable> parameters;
+
+        private final List<FunctionalDependency<Variable>> functionalDependencies;
+
+        private final List<DnfClause> clauses;
+
+        Dnf(String name, List<Variable> parameters, List<FunctionalDependency<Variable>> functionalDependencies,
+                List<DnfClause> clauses) {
+                validateFunctionalDependencies(parameters, functionalDependencies);
+                this.name = name;
+                this.uniqueName = DnfUtils.generateUniqueName(name);
+                this.parameters = parameters;
+                this.functionalDependencies = functionalDependencies;
+                this.clauses = clauses;
+        }
+
+        private static void validateFunctionalDependencies(
+                        Collection<Variable> parameters, Collection<FunctionalDependency<Variable>> functionalDependencies) {
+                var parameterSet = new HashSet<>(parameters);
+                for (var functionalDependency : functionalDependencies) {
+                        validateParameters(parameters, parameterSet, functionalDependency.forEach(), functionalDependency);
+                        validateParameters(parameters, parameterSet, functionalDependency.unique(), functionalDependency);
+                }
+        }
+
+        private static void validateParameters(Collection<Variable> parameters, Set<Variable> parameterSet,
+                                                                                   Collection<Variable> toValidate,
+                                                                                   FunctionalDependency<Variable> functionalDependency) {
+                for (var variable : toValidate) {
+                        if (!parameterSet.contains(variable)) {
+                                throw new IllegalArgumentException(
+                                                "Variable %s of functional dependency %s does not appear in the parameter list %s"
+                                                                .formatted(variable, functionalDependency, parameters));
+                        }
+                }
+        }
+
+        @Override
+        public String name() {
+                return name;
+        }
+
+        public String getUniqueName() {
+                return uniqueName;
+        }
+
+        public List<Variable> getParameters() {
+                return parameters;
+        }
+
+        public List<FunctionalDependency<Variable>> getFunctionalDependencies() {
+                return functionalDependencies;
+        }
+
+        @Override
+        public int arity() {
+                return parameters.size();
+        }
+
+        public List<DnfClause> getClauses() {
+                return clauses;
+        }
+
+        public LiteralReduction getReduction() {
+                if (clauses.isEmpty()) {
+                        return LiteralReduction.ALWAYS_FALSE;
+                }
+                for (var clause : clauses) {
+                        if (clause.literals().isEmpty()) {
+                                return LiteralReduction.ALWAYS_TRUE;
+                        }
+                }
+                return LiteralReduction.NOT_REDUCIBLE;
+        }
+
+        public DnfCallLiteral call(CallPolarity polarity, List<Variable> arguments) {
+                return new DnfCallLiteral(polarity, this, arguments);
+        }
+
+        public DnfCallLiteral call(CallPolarity polarity, Variable... arguments) {
+                return call(polarity, List.of(arguments));
+        }
+
+        public DnfCallLiteral call(Variable... arguments) {
+                return call(CallPolarity.POSITIVE, arguments);
+        }
+
+        public DnfCallLiteral callTransitive(Variable left, Variable right) {
+                return call(CallPolarity.TRANSITIVE, List.of(left, right));
+        }
+
+        public static DnfBuilder builder() {
+                return builder(null);
+        }
+
+        public static DnfBuilder builder(String name) {
+                return new DnfBuilder(name);
+        }
+}
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/DnfBuilder.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/DnfBuilder.java
new file mode 100644
index 00000000..b18b5177
--- /dev/null
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/DnfBuilder.java
@@ -0,0 +1,108 @@
+package tools.refinery.store.query;
+
+import tools.refinery.store.query.literal.Literal;
+
+import java.util.*;
+
+@SuppressWarnings("UnusedReturnValue")
+public class DnfBuilder {
+        private final String name;
+
+        private final List<Variable> parameters = new ArrayList<>();
+
+        private final List<FunctionalDependency<Variable>> functionalDependencies = new ArrayList<>();
+
+        private final List<List<Literal>> clauses = new ArrayList<>();
+
+        DnfBuilder(String name) {
+                this.name = name;
+        }
+
+        public DnfBuilder parameter(Variable variable) {
+                parameters.add(variable);
+                return this;
+        }
+
+        public DnfBuilder parameters(Variable... variables) {
+                return parameters(List.of(variables));
+        }
+
+        public DnfBuilder parameters(Collection<Variable> variables) {
+                parameters.addAll(variables);
+                return this;
+        }
+
+        public DnfBuilder functionalDependencies(Collection<FunctionalDependency<Variable>> functionalDependencies) {
+                this.functionalDependencies.addAll(functionalDependencies);
+                return this;
+        }
+
+        public DnfBuilder functionalDependency(FunctionalDependency<Variable> functionalDependency) {
+                functionalDependencies.add(functionalDependency);
+                return this;
+        }
+
+        public DnfBuilder functionalDependency(Set<Variable> forEach, Set<Variable> unique) {
+                return functionalDependency(new FunctionalDependency<>(forEach, unique));
+        }
+
+        public DnfBuilder clause(Literal... literals) {
+                clause(List.of(literals));
+                return this;
+        }
+
+        public DnfBuilder clause(Collection<Literal> literals) {
+                var filteredLiterals = new ArrayList<Literal>(literals.size());
+                for (var literal : literals) {
+                        var reduction = literal.getReduction();
+                        switch (reduction) {
+                        case NOT_REDUCIBLE -> filteredLiterals.add(literal);
+                        case ALWAYS_TRUE -> {
+                                // Literals reducible to {@code true} can be omitted, because the model is always assumed to have at
+                                // least on object.
+                        }
+                        case ALWAYS_FALSE -> {
+                                // Clauses with {@code false} literals can be omitted entirely.
+                                return this;
+                        }
+                        default -> throw new IllegalStateException("Invalid reduction %s".formatted(reduction));
+                        }
+                }
+                clauses.add(Collections.unmodifiableList(filteredLiterals));
+                return this;
+        }
+
+        public DnfBuilder clause(DnfClause clause) {
+                return clause(clause.literals());
+        }
+
+        public DnfBuilder clauses(DnfClause... clauses) {
+                for (var clause : clauses) {
+                        this.clause(clause);
+                }
+                return this;
+        }
+
+        public DnfBuilder clauses(Collection<DnfClause> clauses) {
+                for (var clause : clauses) {
+                        this.clause(clause);
+                }
+                return this;
+        }
+
+        public Dnf build() {
+                var postProcessedClauses = new ArrayList<DnfClause>(clauses.size());
+                for (var constraints : clauses) {
+                        var variables = new HashSet<Variable>();
+                        for (var constraint : constraints) {
+                                constraint.collectAllVariables(variables);
+                        }
+                        parameters.forEach(variables::remove);
+                        postProcessedClauses.add(new DnfClause(Collections.unmodifiableSet(variables),
+                                        Collections.unmodifiableList(constraints)));
+                }
+                return new Dnf(name, Collections.unmodifiableList(parameters),
+                                Collections.unmodifiableList(functionalDependencies),
+                                Collections.unmodifiableList(postProcessedClauses));
+        }
+}
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/DnfClause.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/DnfClause.java
new file mode 100644
index 00000000..2ba6becc
--- /dev/null
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/DnfClause.java
@@ -0,0 +1,9 @@
+package tools.refinery.store.query;
+
+import tools.refinery.store.query.literal.Literal;
+
+import java.util.List;
+import java.util.Set;
+
+public record DnfClause(Set<Variable> quantifiedVariables, List<Literal> literals) {
+}
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/DnfUtils.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/DnfUtils.java
new file mode 100644
index 00000000..17564d43
--- /dev/null
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/DnfUtils.java
@@ -0,0 +1,24 @@
+package tools.refinery.store.query;
+
+import java.util.Map;
+import java.util.UUID;
+
+public final class DnfUtils {
+        private DnfUtils() {
+                throw new IllegalStateException("This is a static utility class and should not be instantiated directly");
+        }
+
+        public static String generateUniqueName(String originalName) {
+                UUID uuid = UUID.randomUUID();
+                String uniqueString = "_" + uuid.toString().replace('-', '_');
+                if (originalName == null) {
+                        return uniqueString;
+                } else {
+                        return originalName + uniqueString;
+                }
+        }
+
+        public static Variable maybeSubstitute(Variable variable, Map<Variable, Variable> substitution) {
+                return substitution.getOrDefault(variable, variable);
+        }
+}
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/FunctionalDependency.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/FunctionalDependency.java
new file mode 100644
index 00000000..63a81713
--- /dev/null
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/FunctionalDependency.java
@@ -0,0 +1,15 @@
+package tools.refinery.store.query;
+
+import java.util.HashSet;
+import java.util.Set;
+
+public record FunctionalDependency<T>(Set<T> forEach, Set<T> unique) {
+        public FunctionalDependency {
+                var uniqueForEach = new HashSet<>(unique);
+                uniqueForEach.retainAll(forEach);
+                if (!uniqueForEach.isEmpty()) {
+                        throw new IllegalArgumentException("Variables %s appear on both sides of the functional dependency"
+                                        .formatted(uniqueForEach));
+                }
+        }
+}
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/ModelQuery.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/ModelQuery.java
new file mode 100644
index 00000000..6a1aeabb
--- /dev/null
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/ModelQuery.java
@@ -0,0 +1,11 @@
+package tools.refinery.store.query;
+
+import tools.refinery.store.adapter.ModelAdapterType;
+
+public final class ModelQuery extends ModelAdapterType<ModelQueryAdapter, ModelQueryStoreAdapter, ModelQueryBuilder> {
+        public static final ModelQuery ADAPTER = new ModelQuery();
+
+        private ModelQuery() {
+                super(ModelQueryAdapter.class, ModelQueryStoreAdapter.class, ModelQueryBuilder.class);
+        }
+}
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/ModelQueryAdapter.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/ModelQueryAdapter.java
new file mode 100644
index 00000000..f7762444
--- /dev/null
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/ModelQueryAdapter.java
@@ -0,0 +1,13 @@
+package tools.refinery.store.query;
+
+import tools.refinery.store.adapter.ModelAdapter;
+
+public interface ModelQueryAdapter extends ModelAdapter {
+        ModelQueryStoreAdapter getStoreAdapter();
+
+        ResultSet getResultSet(Dnf query);
+
+        boolean hasPendingChanges();
+
+        void flushChanges();
+}
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/ModelQueryBuilder.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/ModelQueryBuilder.java
new file mode 100644
index 00000000..b3cfb4b4
--- /dev/null
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/ModelQueryBuilder.java
@@ -0,0 +1,23 @@
+package tools.refinery.store.query;
+
+import tools.refinery.store.adapter.ModelAdapterBuilder;
+import tools.refinery.store.model.ModelStore;
+
+import java.util.Collection;
+import java.util.List;
+
+public interface ModelQueryBuilder extends ModelAdapterBuilder {
+        default ModelQueryBuilder queries(Dnf... queries) {
+                return queries(List.of(queries));
+        }
+
+        default ModelQueryBuilder queries(Collection<Dnf> queries) {
+                queries.forEach(this::query);
+                return this;
+        }
+
+        ModelQueryBuilder query(Dnf query);
+
+        @Override
+        ModelQueryStoreAdapter createStoreAdapter(ModelStore store);
+}
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/ModelQueryStoreAdapter.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/ModelQueryStoreAdapter.java
new file mode 100644
index 00000000..091d6d06
--- /dev/null
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/ModelQueryStoreAdapter.java
@@ -0,0 +1,16 @@
+package tools.refinery.store.query;
+
+import tools.refinery.store.query.view.AnyRelationView;
+import tools.refinery.store.adapter.ModelStoreAdapter;
+import tools.refinery.store.model.Model;
+
+import java.util.Collection;
+
+public interface ModelQueryStoreAdapter extends ModelStoreAdapter {
+        Collection<AnyRelationView> getRelationViews();
+
+        Collection<Dnf> getQueries();
+
+        @Override
+        ModelQueryAdapter createModelAdapter(Model model);
+}
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/RelationLike.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/RelationLike.java
new file mode 100644
index 00000000..8c784d8b
--- /dev/null
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/RelationLike.java
@@ -0,0 +1,11 @@
+package tools.refinery.store.query;
+
+public interface RelationLike {
+        String name();
+
+        int arity();
+
+        default boolean invalidIndex(int i) {
+                return i < 0 || i >= arity();
+        }
+}
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/ResultSet.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/ResultSet.java
new file mode 100644
index 00000000..3542e252
--- /dev/null
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/ResultSet.java
@@ -0,0 +1,25 @@
+package tools.refinery.store.query;
+
+import tools.refinery.store.tuple.Tuple;
+import tools.refinery.store.tuple.TupleLike;
+
+import java.util.Optional;
+import java.util.stream.Stream;
+
+public interface ResultSet {
+        boolean hasResult();
+
+        boolean hasResult(Tuple parameters);
+
+        Optional<TupleLike> oneResult();
+
+        Optional<TupleLike> oneResult(Tuple parameters);
+
+        Stream<TupleLike> allResults();
+
+        Stream<TupleLike> allResults(Tuple parameters);
+
+        int countResults();
+
+        int countResults(Tuple parameters);
+}
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/Variable.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/Variable.java
new file mode 100644
index 00000000..2eb87649
--- /dev/null
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/Variable.java
@@ -0,0 +1,58 @@
+package tools.refinery.store.query;
+
+import tools.refinery.store.query.literal.ConstantLiteral;
+import tools.refinery.store.query.literal.EquivalenceLiteral;
+
+import java.util.Objects;
+
+public class Variable {
+        private final String name;
+        private final String uniqueName;
+
+        public Variable() {
+                this(null);
+        }
+
+        public Variable(String name) {
+                super();
+                this.name = name;
+                this.uniqueName = DnfUtils.generateUniqueName(name);
+
+        }
+        public String getName() {
+                return name;
+        }
+
+        public String getUniqueName() {
+                return uniqueName;
+        }
+
+        public boolean isNamed() {
+                return name != null;
+        }
+
+        public ConstantLiteral isConstant(int value) {
+                return new ConstantLiteral(this, value);
+        }
+
+        public EquivalenceLiteral isEquivalent(Variable other) {
+                return new EquivalenceLiteral(true, this, other);
+        }
+
+        public EquivalenceLiteral notEquivalent(Variable other) {
+                return new EquivalenceLiteral(false, this, other);
+        }
+
+        @Override
+        public boolean equals(Object o) {
+                if (this == o) return true;
+                if (o == null || getClass() != o.getClass()) return false;
+                Variable variable = (Variable) o;
+                return Objects.equals(uniqueName, variable.uniqueName);
+        }
+
+        @Override
+        public int hashCode() {
+                return Objects.hash(uniqueName);
+        }
+}
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
new file mode 100644
index 00000000..fd2f1eec
--- /dev/null
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/BooleanLiteral.java
@@ -0,0 +1,37 @@
+package tools.refinery.store.query.literal;
+
+import tools.refinery.store.query.Variable;
+
+import java.util.Map;
+import java.util.Set;
+
+public class BooleanLiteral implements Literal {
+        public static final BooleanLiteral TRUE = new BooleanLiteral(LiteralReduction.ALWAYS_TRUE);
+        public static final BooleanLiteral FALSE = new BooleanLiteral(LiteralReduction.ALWAYS_FALSE);
+
+        private final LiteralReduction reduction;
+
+        private BooleanLiteral(LiteralReduction reduction) {
+                this.reduction = reduction;
+        }
+
+        @Override
+        public void collectAllVariables(Set<Variable> variables) {
+                // No variables to collect.
+        }
+
+        @Override
+        public Literal substitute(Map<Variable, Variable> substitution) {
+                // No variables to substitute.
+                return this;
+        }
+
+        @Override
+        public LiteralReduction getReduction() {
+                return reduction;
+        }
+
+        public static BooleanLiteral fromBoolean(boolean value) {
+                return value ? TRUE : FALSE;
+        }
+}
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
new file mode 100644
index 00000000..5e1ae94d
--- /dev/null
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/CallLiteral.java
@@ -0,0 +1,66 @@
+package tools.refinery.store.query.literal;
+
+import tools.refinery.store.query.DnfUtils;
+import tools.refinery.store.query.RelationLike;
+import tools.refinery.store.query.Variable;
+
+import java.util.List;
+import java.util.Map;
+import java.util.Objects;
+import java.util.Set;
+
+public abstract class CallLiteral<T extends RelationLike> implements Literal {
+        private final CallPolarity polarity;
+        private final T target;
+        private final List<Variable> arguments;
+
+        protected CallLiteral(CallPolarity polarity, T target, List<Variable> arguments) {
+                if (arguments.size() != target.arity()) {
+                        throw new IllegalArgumentException("%s needs %d arguments, but got %s".formatted(target.name(),
+                                        target.arity(), arguments.size()));
+                }
+                if (polarity.isTransitive() && target.arity() != 2) {
+                        throw new IllegalArgumentException("Transitive closures can only take binary relations");
+                }
+                this.polarity = polarity;
+                this.target = target;
+                this.arguments = arguments;
+        }
+
+        public CallPolarity getPolarity() {
+                return polarity;
+        }
+
+        public T getTarget() {
+                return target;
+        }
+
+        public List<Variable> getArguments() {
+                return arguments;
+        }
+
+        @Override
+        public void collectAllVariables(Set<Variable> variables) {
+                if (polarity.isPositive()) {
+                        variables.addAll(arguments);
+                }
+        }
+
+        protected List<Variable> substituteArguments(Map<Variable, Variable> substitution) {
+                return arguments.stream().map(variable -> DnfUtils.maybeSubstitute(variable, substitution)).toList();
+        }
+
+        @Override
+        public boolean equals(Object o) {
+                if (this == o) return true;
+                if (o == null || getClass() != o.getClass()) return false;
+                CallLiteral<?> callAtom = (CallLiteral<?>) o;
+                return polarity == callAtom.polarity && Objects.equals(target, callAtom.target) &&
+                                Objects.equals(arguments, callAtom.arguments);
+        }
+
+        @Override
+        public int hashCode() {
+                return Objects.hash(polarity, target, arguments);
+        }
+}
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/CallPolarity.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/CallPolarity.java
new file mode 100644
index 00000000..84b4b771
--- /dev/null
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/CallPolarity.java
@@ -0,0 +1,32 @@
+package tools.refinery.store.query.literal;
+
+public enum CallPolarity {
+        POSITIVE(true, false),
+        NEGATIVE(false, false),
+        TRANSITIVE(true, true);
+
+        private final boolean positive;
+
+        private final boolean transitive;
+
+        CallPolarity(boolean positive, boolean transitive) {
+                this.positive = positive;
+                this.transitive = transitive;
+        }
+
+        public boolean isPositive() {
+                return positive;
+        }
+
+        public boolean isTransitive() {
+                return transitive;
+        }
+
+        public CallPolarity negate() {
+                return switch (this) {
+                        case POSITIVE -> NEGATIVE;
+                        case NEGATIVE -> POSITIVE;
+                        case TRANSITIVE -> throw new IllegalArgumentException("Transitive polarity cannot be negated");
+                };
+        }
+}
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
new file mode 100644
index 00000000..746d23af
--- /dev/null
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/ConstantLiteral.java
@@ -0,0 +1,19 @@
+package tools.refinery.store.query.literal;
+
+import tools.refinery.store.query.DnfUtils;
+import tools.refinery.store.query.Variable;
+
+import java.util.Map;
+import java.util.Set;
+
+public record ConstantLiteral(Variable variable, int nodeId) implements Literal {
+        @Override
+        public void collectAllVariables(Set<Variable> variables) {
+                variables.add(variable);
+        }
+
+        @Override
+        public ConstantLiteral substitute(Map<Variable, Variable> substitution) {
+                return new ConstantLiteral(DnfUtils.maybeSubstitute(variable, substitution), nodeId);
+        }
+}
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/DnfCallLiteral.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/DnfCallLiteral.java
new file mode 100644
index 00000000..de6c6005
--- /dev/null
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/DnfCallLiteral.java
@@ -0,0 +1,29 @@
+package tools.refinery.store.query.literal;
+
+import tools.refinery.store.query.Dnf;
+import tools.refinery.store.query.Variable;
+
+import java.util.List;
+import java.util.Map;
+
+public final class DnfCallLiteral extends CallLiteral<Dnf> implements PolarLiteral<DnfCallLiteral> {
+        public DnfCallLiteral(CallPolarity polarity, Dnf target, List<Variable> arguments) {
+                super(polarity, target, arguments);
+        }
+
+        @Override
+        public DnfCallLiteral substitute(Map<Variable, Variable> substitution) {
+                return new DnfCallLiteral(getPolarity(), getTarget(), substituteArguments(substitution));
+        }
+
+        @Override
+        public DnfCallLiteral negate() {
+                return new DnfCallLiteral(getPolarity().negate(), getTarget(), getArguments());
+        }
+
+        @Override
+        public LiteralReduction getReduction() {
+                var dnfReduction = getTarget().getReduction();
+                return getPolarity().isPositive() ? dnfReduction : dnfReduction.negate();
+        }
+}
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
new file mode 100644
index 00000000..f30179b2
--- /dev/null
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/EquivalenceLiteral.java
@@ -0,0 +1,35 @@
+package tools.refinery.store.query.literal;
+
+import tools.refinery.store.query.DnfUtils;
+import tools.refinery.store.query.Variable;
+
+import java.util.Map;
+import java.util.Set;
+
+public record EquivalenceLiteral(boolean positive, Variable left, Variable right)
+                implements PolarLiteral<EquivalenceLiteral> {
+        @Override
+        public void collectAllVariables(Set<Variable> variables) {
+                variables.add(left);
+                variables.add(right);
+        }
+
+        @Override
+        public EquivalenceLiteral negate() {
+                return new EquivalenceLiteral(!positive, left, right);
+        }
+
+        @Override
+        public EquivalenceLiteral substitute(Map<Variable, Variable> substitution) {
+                return new EquivalenceLiteral(positive, DnfUtils.maybeSubstitute(left, substitution),
+                                DnfUtils.maybeSubstitute(right, substitution));
+        }
+
+        @Override
+        public LiteralReduction getReduction() {
+                if (left.equals(right)) {
+                        return positive ? LiteralReduction.ALWAYS_TRUE : LiteralReduction.ALWAYS_FALSE;
+                }
+                return LiteralReduction.NOT_REDUCIBLE;
+        }
+}
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
new file mode 100644
index 00000000..a6893acf
--- /dev/null
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/Literal.java
@@ -0,0 +1,16 @@
+package tools.refinery.store.query.literal;
+
+import tools.refinery.store.query.Variable;
+
+import java.util.Map;
+import java.util.Set;
+
+public interface Literal {
+        void collectAllVariables(Set<Variable> variables);
+
+        Literal substitute(Map<Variable, Variable> substitution);
+
+        default LiteralReduction getReduction() {
+                return LiteralReduction.NOT_REDUCIBLE;
+        }
+}
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/LiteralReduction.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/LiteralReduction.java
new file mode 100644
index 00000000..146089f6
--- /dev/null
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/LiteralReduction.java
@@ -0,0 +1,26 @@
+package tools.refinery.store.query.literal;
+
+public enum LiteralReduction {
+        /**
+         * Signifies that a literal should be preserved in the clause.
+         */
+        NOT_REDUCIBLE,
+
+        /**
+         * Signifies that the literal may be omitted from the cause (if the model being queried is nonempty).
+         */
+        ALWAYS_TRUE,
+
+        /**
+         * Signifies that the clause with the literal may be omitted entirely.
+         */
+        ALWAYS_FALSE;
+
+        public LiteralReduction negate() {
+                return switch (this) {
+                        case NOT_REDUCIBLE -> NOT_REDUCIBLE;
+                        case ALWAYS_TRUE -> ALWAYS_FALSE;
+                        case ALWAYS_FALSE -> ALWAYS_TRUE;
+                };
+        }
+}
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/Literals.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/Literals.java
new file mode 100644
index 00000000..2c7e893f
--- /dev/null
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/Literals.java
@@ -0,0 +1,11 @@
+package tools.refinery.store.query.literal;
+
+public final class Literals {
+        private Literals() {
+                throw new IllegalStateException("This is a static utility class and should not be instantiated directly");
+        }
+
+        public static <T extends PolarLiteral<T>> T not(PolarLiteral<T> literal) {
+                return literal.negate();
+        }
+}
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/PolarLiteral.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/PolarLiteral.java
new file mode 100644
index 00000000..32523675
--- /dev/null
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/PolarLiteral.java
@@ -0,0 +1,5 @@
+package tools.refinery.store.query.literal;
+
+public interface PolarLiteral<T extends PolarLiteral<T>> extends Literal {
+        T negate();
+}
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/RelationViewLiteral.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/RelationViewLiteral.java
new file mode 100644
index 00000000..4718b550
--- /dev/null
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/RelationViewLiteral.java
@@ -0,0 +1,24 @@
+package tools.refinery.store.query.literal;
+
+import tools.refinery.store.query.Variable;
+import tools.refinery.store.query.view.AnyRelationView;
+
+import java.util.List;
+import java.util.Map;
+
+public final class RelationViewLiteral extends CallLiteral<AnyRelationView>
+                implements PolarLiteral<RelationViewLiteral> {
+        public RelationViewLiteral(CallPolarity polarity, AnyRelationView target, List<Variable> arguments) {
+                super(polarity, target, arguments);
+        }
+
+        @Override
+        public RelationViewLiteral substitute(Map<Variable, Variable> substitution) {
+                return new RelationViewLiteral(getPolarity(), getTarget(), substituteArguments(substitution));
+        }
+
+        @Override
+        public RelationViewLiteral negate() {
+                return new RelationViewLiteral(getPolarity().negate(), getTarget(), getArguments());
+        }
+}
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/view/AnyRelationView.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/view/AnyRelationView.java
new file mode 100644
index 00000000..328cde3a
--- /dev/null
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/view/AnyRelationView.java
@@ -0,0 +1,24 @@
+package tools.refinery.store.query.view;
+
+import tools.refinery.store.model.Model;
+import tools.refinery.store.query.FunctionalDependency;
+import tools.refinery.store.representation.AnySymbol;
+import tools.refinery.store.query.RelationLike;
+
+import java.util.Set;
+
+public sealed interface AnyRelationView extends RelationLike permits RelationView {
+        AnySymbol getSymbol();
+
+        default Set<FunctionalDependency<Integer>> getFunctionalDependencies() {
+                return Set.of();
+        }
+
+        default Set<RelationViewImplication> getImpliedRelationViews() {
+                return Set.of();
+        }
+
+        boolean get(Model model, Object[] tuple);
+
+        Iterable<Object[]> getAll(Model model);
+}
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/view/FilteredRelationView.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/view/FilteredRelationView.java
new file mode 100644
index 00000000..64c601bb
--- /dev/null
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/view/FilteredRelationView.java
@@ -0,0 +1,49 @@
+package tools.refinery.store.query.view;
+
+import tools.refinery.store.tuple.Tuple;
+import tools.refinery.store.representation.Symbol;
+
+import java.util.Objects;
+import java.util.function.BiPredicate;
+import java.util.function.Predicate;
+
+public class FilteredRelationView<T> extends TuplePreservingRelationView<T> {
+        private final BiPredicate<Tuple, T> predicate;
+
+        public FilteredRelationView(Symbol<T> symbol, String name, BiPredicate<Tuple, T> predicate) {
+                super(symbol, name);
+                this.predicate = predicate;
+        }
+
+        public FilteredRelationView(Symbol<T> symbol, BiPredicate<Tuple, T> predicate) {
+                super(symbol);
+                this.predicate = predicate;
+        }
+
+        public FilteredRelationView(Symbol<T> symbol, String name, Predicate<T> predicate) {
+                this(symbol, name, (k, v) -> predicate.test(v));
+        }
+
+        public FilteredRelationView(Symbol<T> symbol, Predicate<T> predicate) {
+                this(symbol, (k, v) -> predicate.test(v));
+        }
+
+        @Override
+        public boolean filter(Tuple key, T value) {
+                return this.predicate.test(key, value);
+        }
+
+        @Override
+        public boolean equals(Object o) {
+                if (this == o) return true;
+                if (o == null || getClass() != o.getClass()) return false;
+                if (!super.equals(o)) return false;
+                FilteredRelationView<?> that = (FilteredRelationView<?>) o;
+                return Objects.equals(predicate, that.predicate);
+        }
+
+        @Override
+        public int hashCode() {
+                return Objects.hash(super.hashCode(), predicate);
+        }
+}
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/view/FunctionalRelationView.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/view/FunctionalRelationView.java
new file mode 100644
index 00000000..3d278a8b
--- /dev/null
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/view/FunctionalRelationView.java
@@ -0,0 +1,71 @@
+package tools.refinery.store.query.view;
+
+import tools.refinery.store.model.Model;
+import tools.refinery.store.query.FunctionalDependency;
+import tools.refinery.store.representation.Symbol;
+import tools.refinery.store.tuple.Tuple;
+import tools.refinery.store.tuple.Tuple1;
+
+import java.util.Set;
+import java.util.stream.Collectors;
+import java.util.stream.IntStream;
+
+public final class FunctionalRelationView<T> extends RelationView<T> {
+        public FunctionalRelationView(Symbol<T> symbol, String name) {
+                super(symbol, name);
+        }
+
+        public FunctionalRelationView(Symbol<T> symbol) {
+                super(symbol);
+        }
+
+        @Override
+        public Set<FunctionalDependency<Integer>> getFunctionalDependencies() {
+                var arity = getSymbol().arity();
+                var forEach = IntStream.range(0, arity).boxed().collect(Collectors.toUnmodifiableSet());
+                var unique = Set.of(arity);
+                return Set.of(new FunctionalDependency<>(forEach, unique));
+        }
+
+        @Override
+        public Set<RelationViewImplication> getImpliedRelationViews() {
+                var symbol = getSymbol();
+                var impliedIndices = IntStream.range(0, symbol.arity()).boxed().toList();
+                var keyOnlyRelationView = new KeyOnlyRelationView<>(symbol);
+                return Set.of(new RelationViewImplication(this, keyOnlyRelationView, impliedIndices));
+        }
+
+        @Override
+        public boolean filter(Tuple key, T value) {
+                return true;
+        }
+
+        @Override
+        public Object[] forwardMap(Tuple key, T value) {
+                int size = key.getSize();
+                Object[] result = new Object[size + 1];
+                for (int i = 0; i < size; i++) {
+                        result[i] = Tuple.of(key.get(i));
+                }
+                result[key.getSize()] = value;
+                return result;
+        }
+
+        @Override
+        public boolean get(Model model, Object[] tuple) {
+                int[] content = new int[tuple.length - 1];
+                for (int i = 0; i < tuple.length - 1; i++) {
+                        content[i] = ((Tuple1) tuple[i]).value0();
+                }
+                Tuple key = Tuple.of(content);
+                @SuppressWarnings("unchecked")
+                T valueInTuple = (T) tuple[tuple.length - 1];
+                T valueInMap = model.getInterpretation(getSymbol()).get(key);
+                return valueInTuple.equals(valueInMap);
+        }
+
+        @Override
+        public int arity() {
+                return getSymbol().arity() + 1;
+        }
+}
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/view/KeyOnlyRelationView.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/view/KeyOnlyRelationView.java
new file mode 100644
index 00000000..e1b2e45b
--- /dev/null
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/view/KeyOnlyRelationView.java
@@ -0,0 +1,36 @@
+package tools.refinery.store.query.view;
+
+import tools.refinery.store.representation.Symbol;
+import tools.refinery.store.tuple.Tuple;
+
+import java.util.Objects;
+
+public final class KeyOnlyRelationView<T> extends TuplePreservingRelationView<T> {
+        public static final String VIEW_NAME = "key";
+
+        private final T defaultValue;
+
+        public KeyOnlyRelationView(Symbol<T> symbol) {
+                super(symbol, VIEW_NAME);
+                defaultValue = symbol.defaultValue();
+        }
+
+        @Override
+        public boolean filter(Tuple key, T value) {
+                return !Objects.equals(value, defaultValue);
+        }
+
+        @Override
+        public boolean equals(Object o) {
+                if (this == o) return true;
+                if (o == null || getClass() != o.getClass()) return false;
+                if (!super.equals(o)) return false;
+                KeyOnlyRelationView<?> that = (KeyOnlyRelationView<?>) o;
+                return Objects.equals(defaultValue, that.defaultValue);
+        }
+
+        @Override
+        public int hashCode() {
+                return Objects.hash(super.hashCode(), defaultValue);
+        }
+}
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/view/RelationView.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/view/RelationView.java
new file mode 100644
index 00000000..2714a8c5
--- /dev/null
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/view/RelationView.java
@@ -0,0 +1,82 @@
+package tools.refinery.store.query.view;
+
+import tools.refinery.store.query.Variable;
+import tools.refinery.store.map.CursorAsIterator;
+import tools.refinery.store.model.Model;
+import tools.refinery.store.query.literal.CallPolarity;
+import tools.refinery.store.query.literal.RelationViewLiteral;
+import tools.refinery.store.representation.Symbol;
+import tools.refinery.store.tuple.Tuple;
+
+import java.util.List;
+import java.util.Objects;
+import java.util.UUID;
+
+/**
+ * Represents a view of a {@link Symbol} that can be queried.
+ *
+ * @param <T>
+ * @author Oszkar Semerath
+ */
+public abstract non-sealed class RelationView<T> implements AnyRelationView {
+        private final Symbol<T> symbol;
+
+        private final String name;
+
+        protected RelationView(Symbol<T> symbol, String name) {
+                this.symbol = symbol;
+                this.name = name;
+        }
+
+        protected RelationView(Symbol<T> representation) {
+                this(representation, UUID.randomUUID().toString());
+        }
+
+        @Override
+        public Symbol<T> getSymbol() {
+                return symbol;
+        }
+
+        @Override
+        public String name() {
+                return symbol.name() + "#" + name;
+        }
+
+        public abstract boolean filter(Tuple key, T value);
+
+        public abstract Object[] forwardMap(Tuple key, T value);
+
+        @Override
+        public Iterable<Object[]> getAll(Model model) {
+                return (() -> new CursorAsIterator<>(model.getInterpretation(symbol).getAll(), this::forwardMap, this::filter));
+        }
+
+        public RelationViewLiteral call(CallPolarity polarity, List<Variable> arguments) {
+                return new RelationViewLiteral(polarity, this, arguments);
+        }
+
+        public RelationViewLiteral call(CallPolarity polarity, Variable... arguments) {
+                return call(polarity, List.of(arguments));
+        }
+
+        public RelationViewLiteral call(Variable... arguments) {
+                return call(CallPolarity.POSITIVE, arguments);
+        }
+
+        public RelationViewLiteral callTransitive(Variable left, Variable right) {
+                return call(CallPolarity.TRANSITIVE, List.of(left, right));
+        }
+
+        @Override
+        public boolean equals(Object o) {
+                if (this == o) return true;
+                if (o == null || getClass() != o.getClass()) return false;
+                RelationView<?> that = (RelationView<?>) o;
+                return Objects.equals(symbol, that.symbol) && Objects.equals(name, that.name);
+        }
+
+        @Override
+        public int hashCode() {
+                return Objects.hash(symbol, name);
+        }
+}
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/view/RelationViewImplication.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/view/RelationViewImplication.java
new file mode 100644
index 00000000..2ba1fcc4
--- /dev/null
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/view/RelationViewImplication.java
@@ -0,0 +1,19 @@
+package tools.refinery.store.query.view;
+
+import java.util.List;
+
+public record RelationViewImplication(AnyRelationView implyingRelationView, AnyRelationView impliedRelationView,
+                                                                          List<Integer> impliedIndices) {
+        public RelationViewImplication {
+                if (impliedIndices.size() != impliedRelationView.arity()) {
+                        throw new IllegalArgumentException("Expected %d implied indices for %s, but %d are provided"
+                                        .formatted(impliedRelationView.arity(), impliedRelationView, impliedIndices.size()));
+                }
+                for (var index : impliedIndices) {
+                        if (impliedRelationView.invalidIndex(index)) {
+                                throw new IllegalArgumentException("%d is not a valid index for %s".formatted(index,
+                                                implyingRelationView));
+                        }
+                }
+        }
+}
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/view/TuplePreservingRelationView.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/view/TuplePreservingRelationView.java
new file mode 100644
index 00000000..8cc4986e
--- /dev/null
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/view/TuplePreservingRelationView.java
@@ -0,0 +1,44 @@
+package tools.refinery.store.query.view;
+
+import tools.refinery.store.model.Model;
+import tools.refinery.store.tuple.Tuple;
+import tools.refinery.store.tuple.Tuple1;
+import tools.refinery.store.representation.Symbol;
+
+public abstract class TuplePreservingRelationView<T> extends RelationView<T> {
+        protected TuplePreservingRelationView(Symbol<T> symbol, String name) {
+                super(symbol, name);
+        }
+
+        protected TuplePreservingRelationView(Symbol<T> symbol) {
+                super(symbol);
+        }
+
+        public Object[] forwardMap(Tuple key) {
+                Object[] result = new Object[key.getSize()];
+                for (int i = 0; i < key.getSize(); i++) {
+                        result[i] = Tuple.of(key.get(i));
+                }
+                return result;
+        }
+
+        @Override
+        public Object[] forwardMap(Tuple key, T value) {
+                return forwardMap(key);
+        }
+
+        @Override
+        public boolean get(Model model, Object[] tuple) {
+                int[] content = new int[tuple.length];
+                for (int i = 0; i < tuple.length; i++) {
+                        content[i] = ((Tuple1) tuple[i]).value0();
+                }
+                Tuple key = Tuple.of(content);
+                T value = model.getInterpretation(getSymbol()).get(key);
+                return filter(key, value);
+        }
+
+        public int arity() {
+                return this.getSymbol().arity();
+        }
+}