chore: remove VIATRA branding

Rename VIATRA subprojects to Refinery Interpreter to avoid interfering with
Eclipse Foundation trademarks.

Uses refering to a specific (historical) version of VIATRA were kept to avoid
ambiguity.

46 files changed, 5494 insertions, 0 deletions

diff --git a/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/QueryInterpreterAdapter.java b/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/QueryInterpreterAdapter.java
new file mode 100644
index 00000000..83e69ae8
--- /dev/null
+++ b/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/QueryInterpreterAdapter.java
@@ -0,0 +1,18 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.interpreter;
+
+import tools.refinery.store.query.ModelQueryAdapter;
+import tools.refinery.store.query.interpreter.internal.QueryInterpreterBuilderImpl;
+
+public interface QueryInterpreterAdapter extends ModelQueryAdapter {
+        @Override
+        QueryInterpreterStoreAdapter getStoreAdapter();
+
+        static QueryInterpreterBuilder builder() {
+                return new QueryInterpreterBuilderImpl();
+        }
+}
diff --git a/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/QueryInterpreterBuilder.java b/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/QueryInterpreterBuilder.java
new file mode 100644
index 00000000..6e167d0d
--- /dev/null
+++ b/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/QueryInterpreterBuilder.java
@@ -0,0 +1,54 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.interpreter;
+
+import tools.refinery.store.model.ModelStore;
+import tools.refinery.store.query.ModelQueryBuilder;
+import tools.refinery.store.query.dnf.AnyQuery;
+import tools.refinery.store.query.dnf.Dnf;
+import tools.refinery.store.query.rewriter.DnfRewriter;
+import tools.refinery.interpreter.api.InterpreterEngineOptions;
+import tools.refinery.interpreter.matchers.backend.IQueryBackendFactory;
+import tools.refinery.interpreter.matchers.backend.QueryEvaluationHint;
+
+import java.util.Collection;
+import java.util.function.Function;
+
+@SuppressWarnings("UnusedReturnValue")
+public interface QueryInterpreterBuilder extends ModelQueryBuilder {
+        QueryInterpreterBuilder engineOptions(InterpreterEngineOptions engineOptions);
+
+        QueryInterpreterBuilder defaultHint(QueryEvaluationHint queryEvaluationHint);
+
+        QueryInterpreterBuilder backend(IQueryBackendFactory queryBackendFactory);
+
+        QueryInterpreterBuilder cachingBackend(IQueryBackendFactory queryBackendFactory);
+
+        QueryInterpreterBuilder searchBackend(IQueryBackendFactory queryBackendFactory);
+
+        @Override
+        default QueryInterpreterBuilder queries(AnyQuery... queries) {
+                ModelQueryBuilder.super.queries(queries);
+                return this;
+        }
+
+        @Override
+        default QueryInterpreterBuilder queries(Collection<? extends AnyQuery> queries) {
+                ModelQueryBuilder.super.queries(queries);
+                return this;
+        }
+
+        @Override
+        QueryInterpreterBuilder query(AnyQuery query);
+
+        @Override
+        QueryInterpreterBuilder rewriter(DnfRewriter rewriter);
+
+        QueryInterpreterBuilder computeHint(Function<Dnf, QueryEvaluationHint> computeHint);
+
+        @Override
+        QueryInterpreterStoreAdapter build(ModelStore store);
+}
diff --git a/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/QueryInterpreterStoreAdapter.java b/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/QueryInterpreterStoreAdapter.java
new file mode 100644
index 00000000..9c55ecc2
--- /dev/null
+++ b/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/QueryInterpreterStoreAdapter.java
@@ -0,0 +1,17 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.interpreter;
+
+import tools.refinery.interpreter.api.InterpreterEngineOptions;
+import tools.refinery.store.model.Model;
+import tools.refinery.store.query.ModelQueryStoreAdapter;
+
+public interface QueryInterpreterStoreAdapter extends ModelQueryStoreAdapter {
+        InterpreterEngineOptions getEngineOptions();
+
+        @Override
+        QueryInterpreterAdapter createModelAdapter(Model model);
+}
diff --git a/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/QueryInterpreterAdapterImpl.java b/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/QueryInterpreterAdapterImpl.java
new file mode 100644
index 00000000..ee527fd3
--- /dev/null
+++ b/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/QueryInterpreterAdapterImpl.java
@@ -0,0 +1,122 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.interpreter.internal;
+
+import tools.refinery.store.model.Model;
+import tools.refinery.store.model.ModelListener;
+import tools.refinery.store.query.dnf.AnyQuery;
+import tools.refinery.store.query.dnf.FunctionalQuery;
+import tools.refinery.store.query.dnf.Query;
+import tools.refinery.store.query.dnf.RelationalQuery;
+import tools.refinery.store.query.resultset.AnyResultSet;
+import tools.refinery.store.query.resultset.EmptyResultSet;
+import tools.refinery.store.query.resultset.ResultSet;
+import tools.refinery.store.query.interpreter.QueryInterpreterAdapter;
+import tools.refinery.store.query.interpreter.internal.matcher.InterpretedFunctionalMatcher;
+import tools.refinery.store.query.interpreter.internal.matcher.RawPatternMatcher;
+import tools.refinery.store.query.interpreter.internal.matcher.InterpretedRelationalMatcher;
+import tools.refinery.interpreter.CancellationToken;
+import tools.refinery.interpreter.api.AdvancedInterpreterEngine;
+import tools.refinery.interpreter.api.GenericQueryGroup;
+import tools.refinery.interpreter.api.IQuerySpecification;
+
+import java.util.Collections;
+import java.util.LinkedHashMap;
+import java.util.Map;
+
+public class QueryInterpreterAdapterImpl implements QueryInterpreterAdapter, ModelListener {
+        private final Model model;
+        private final QueryInterpreterStoreAdapterImpl storeAdapter;
+        private final AdvancedInterpreterEngine queryEngine;
+        private final Map<AnyQuery, AnyResultSet> resultSets;
+        private boolean pendingChanges;
+
+        QueryInterpreterAdapterImpl(Model model, QueryInterpreterStoreAdapterImpl storeAdapter) {
+                this.model = model;
+                this.storeAdapter = storeAdapter;
+                var scope = new RelationalScope(this);
+                queryEngine = AdvancedInterpreterEngine.createUnmanagedEngine(scope,
+                                storeAdapter.getEngineOptions());
+
+                var querySpecifications = storeAdapter.getQuerySpecifications();
+                GenericQueryGroup.of(
+                                Collections.<IQuerySpecification<?>>unmodifiableCollection(querySpecifications.values()).stream()
+                ).prepare(queryEngine);
+                queryEngine.flushChanges();
+                var vacuousQueries = storeAdapter.getVacuousQueries();
+                resultSets = new LinkedHashMap<>(querySpecifications.size() + vacuousQueries.size());
+                for (var entry : querySpecifications.entrySet()) {
+                        var rawPatternMatcher = queryEngine.getMatcher(entry.getValue());
+                        var query = entry.getKey();
+                        resultSets.put(query, createResultSet((Query<?>) query, rawPatternMatcher));
+                }
+                for (var vacuousQuery : vacuousQueries) {
+                        resultSets.put(vacuousQuery, new EmptyResultSet<>(this, (Query<?>) vacuousQuery));
+                }
+
+                model.addListener(this);
+        }
+
+        private <T> ResultSet<T> createResultSet(Query<T> query, RawPatternMatcher matcher) {
+                if (query instanceof RelationalQuery relationalQuery) {
+                        @SuppressWarnings("unchecked")
+                        var resultSet = (ResultSet<T>) new InterpretedRelationalMatcher(this, relationalQuery, matcher);
+                        return resultSet;
+                } else if (query instanceof FunctionalQuery<T> functionalQuery) {
+                        return new InterpretedFunctionalMatcher<>(this, functionalQuery, matcher);
+                } else {
+                        throw new IllegalArgumentException("Unknown query: " + query);
+                }
+        }
+
+        @Override
+        public Model getModel() {
+                return model;
+        }
+
+        @Override
+        public QueryInterpreterStoreAdapterImpl getStoreAdapter() {
+                return storeAdapter;
+        }
+
+        public CancellationToken getCancellationToken() {
+                return storeAdapter.getCancellationToken();
+        }
+
+        @Override
+        public <T> ResultSet<T> getResultSet(Query<T> query) {
+                var canonicalQuery = storeAdapter.getCanonicalQuery(query);
+                var resultSet = resultSets.get(canonicalQuery);
+                if (resultSet == null) {
+                        throw new IllegalArgumentException("No matcher for query %s in model".formatted(query.name()));
+                }
+                @SuppressWarnings("unchecked")
+                var typedResultSet = (ResultSet<T>) resultSet;
+                return typedResultSet;
+        }
+
+        @Override
+        public boolean hasPendingChanges() {
+                return pendingChanges;
+        }
+
+        public void markAsPending() {
+                if (!pendingChanges) {
+                        pendingChanges = true;
+                }
+        }
+
+        @Override
+        public void flushChanges() {
+                queryEngine.flushChanges();
+                pendingChanges = false;
+        }
+
+        @Override
+        public void afterRestore() {
+                flushChanges();
+        }
+}
diff --git a/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/QueryInterpreterBuilderImpl.java b/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/QueryInterpreterBuilderImpl.java
new file mode 100644
index 00000000..c0d802da
--- /dev/null
+++ b/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/QueryInterpreterBuilderImpl.java
@@ -0,0 +1,169 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.interpreter.internal;
+
+import tools.refinery.store.adapter.AbstractModelAdapterBuilder;
+import tools.refinery.store.model.ModelStore;
+import tools.refinery.store.query.dnf.AnyQuery;
+import tools.refinery.store.query.dnf.Dnf;
+import tools.refinery.store.query.rewriter.CompositeRewriter;
+import tools.refinery.store.query.rewriter.DnfRewriter;
+import tools.refinery.store.query.rewriter.DuplicateDnfRemover;
+import tools.refinery.store.query.rewriter.InputParameterResolver;
+import tools.refinery.store.query.interpreter.QueryInterpreterBuilder;
+import tools.refinery.store.query.interpreter.internal.localsearch.FlatCostFunction;
+import tools.refinery.store.query.interpreter.internal.matcher.RawPatternMatcher;
+import tools.refinery.store.query.interpreter.internal.pquery.Dnf2PQuery;
+import tools.refinery.interpreter.api.IQuerySpecification;
+import tools.refinery.interpreter.api.InterpreterEngineOptions;
+import tools.refinery.interpreter.localsearch.matcher.integration.LocalSearchGenericBackendFactory;
+import tools.refinery.interpreter.localsearch.matcher.integration.LocalSearchHintOptions;
+import tools.refinery.interpreter.matchers.backend.IQueryBackendFactory;
+import tools.refinery.interpreter.matchers.backend.QueryEvaluationHint;
+import tools.refinery.interpreter.rete.matcher.ReteBackendFactory;
+
+import java.util.*;
+import java.util.function.Function;
+
+public class QueryInterpreterBuilderImpl extends AbstractModelAdapterBuilder<QueryInterpreterStoreAdapterImpl>
+                implements QueryInterpreterBuilder {
+        private InterpreterEngineOptions.Builder engineOptionsBuilder;
+        private QueryEvaluationHint defaultHint = new QueryEvaluationHint(Map.of(
+                        // Use a cost function that ignores the initial (empty) model but allows higher arity input keys.
+                        LocalSearchHintOptions.PLANNER_COST_FUNCTION, new FlatCostFunction()
+        ), (IQueryBackendFactory) null);
+        private final CompositeRewriter rewriter;
+        private final Dnf2PQuery dnf2PQuery = new Dnf2PQuery();
+        private final Set<AnyQuery> queries = new LinkedHashSet<>();
+
+        public QueryInterpreterBuilderImpl() {
+                engineOptionsBuilder = new InterpreterEngineOptions.Builder()
+                                .withDefaultBackend(ReteBackendFactory.INSTANCE)
+                                .withDefaultCachingBackend(ReteBackendFactory.INSTANCE)
+                                .withDefaultSearchBackend(LocalSearchGenericBackendFactory.INSTANCE);
+                rewriter = new CompositeRewriter();
+                rewriter.addFirst(new DuplicateDnfRemover());
+                rewriter.addFirst(new InputParameterResolver());
+        }
+
+        @Override
+        public QueryInterpreterBuilder engineOptions(InterpreterEngineOptions engineOptions) {
+                checkNotConfigured();
+                engineOptionsBuilder = new InterpreterEngineOptions.Builder(engineOptions);
+                return this;
+        }
+
+        @Override
+        public QueryInterpreterBuilder defaultHint(QueryEvaluationHint queryEvaluationHint) {
+                checkNotConfigured();
+                defaultHint = defaultHint.overrideBy(queryEvaluationHint);
+                return this;
+        }
+
+        @Override
+        public QueryInterpreterBuilder backend(IQueryBackendFactory queryBackendFactory) {
+                checkNotConfigured();
+                engineOptionsBuilder.withDefaultBackend(queryBackendFactory);
+                return this;
+        }
+
+        @Override
+        public QueryInterpreterBuilder cachingBackend(IQueryBackendFactory queryBackendFactory) {
+                checkNotConfigured();
+                engineOptionsBuilder.withDefaultCachingBackend(queryBackendFactory);
+                return this;
+        }
+
+        @Override
+        public QueryInterpreterBuilder searchBackend(IQueryBackendFactory queryBackendFactory) {
+                checkNotConfigured();
+                engineOptionsBuilder.withDefaultSearchBackend(queryBackendFactory);
+                return this;
+        }
+
+        @Override
+        public QueryInterpreterBuilder queries(Collection<? extends AnyQuery> queries) {
+                checkNotConfigured();
+                this.queries.addAll(queries);
+                return this;
+        }
+
+        @Override
+        public QueryInterpreterBuilder query(AnyQuery query) {
+                checkNotConfigured();
+                queries.add(query);
+                return this;
+        }
+
+        @Override
+        public QueryInterpreterBuilder rewriter(DnfRewriter rewriter) {
+                this.rewriter.addFirst(rewriter);
+                return this;
+        }
+
+        @Override
+        public QueryInterpreterBuilder computeHint(Function<Dnf, QueryEvaluationHint> computeHint) {
+                checkNotConfigured();
+                dnf2PQuery.setComputeHint(computeHint);
+                return this;
+        }
+
+        @Override
+        public QueryInterpreterStoreAdapterImpl doBuild(ModelStore store) {
+                var canonicalQueryMap = new HashMap<AnyQuery, AnyQuery>();
+                var querySpecifications = new LinkedHashMap<AnyQuery, IQuerySpecification<RawPatternMatcher>>();
+                var vacuousQueries = new LinkedHashSet<AnyQuery>();
+                for (var query : queries) {
+                        var canonicalQuery = rewriter.rewrite(query);
+                        canonicalQueryMap.put(query, canonicalQuery);
+                        var dnf = canonicalQuery.getDnf();
+                        var reduction = dnf.getReduction();
+                        switch (reduction) {
+                        case NOT_REDUCIBLE -> {
+                                var pQuery = dnf2PQuery.translate(dnf);
+                                querySpecifications.put(canonicalQuery, pQuery.build());
+                        }
+                        case ALWAYS_FALSE -> vacuousQueries.add(canonicalQuery);
+                        case ALWAYS_TRUE -> throw new IllegalArgumentException(
+                                        "Query %s is relationally unsafe (it matches every tuple)".formatted(query.name()));
+                        default -> throw new IllegalArgumentException("Unknown reduction: " + reduction);
+                        }
+                }
+
+                validateSymbols(store);
+                return new QueryInterpreterStoreAdapterImpl(store, buildEngineOptions(), dnf2PQuery.getSymbolViews(),
+                                Collections.unmodifiableMap(canonicalQueryMap), Collections.unmodifiableMap(querySpecifications),
+                                Collections.unmodifiableSet(vacuousQueries), store::checkCancelled);
+        }
+
+        private InterpreterEngineOptions buildEngineOptions() {
+                // Workaround: manually override the default backend, because {@link ViatraQueryEngineOptions.Builder}
+                // ignores all backend requirements except {@code SPECIFIC}.
+                switch (defaultHint.getQueryBackendRequirementType()) {
+                case SPECIFIC -> engineOptionsBuilder.withDefaultBackend(defaultHint.getQueryBackendFactory());
+                case DEFAULT_CACHING -> engineOptionsBuilder.withDefaultBackend(
+                                engineOptionsBuilder.build().getDefaultCachingBackendFactory());
+                case DEFAULT_SEARCH -> engineOptionsBuilder.withDefaultBackend(
+                                engineOptionsBuilder.build().getDefaultSearchBackendFactory());
+                case UNSPECIFIED -> {
+                        // Nothing to do, leave the default backend unchanged.
+                }
+                }
+                engineOptionsBuilder.withDefaultHint(defaultHint);
+                return engineOptionsBuilder.build();
+        }
+
+        private void validateSymbols(ModelStore store) {
+                var symbols = store.getSymbols();
+                for (var symbolView : dnf2PQuery.getSymbolViews().keySet()) {
+                        var symbol = symbolView.getSymbol();
+                        if (!symbols.contains(symbol)) {
+                                throw new IllegalArgumentException("Cannot query view %s: symbol %s is not in the model"
+                                                .formatted(symbolView, symbol));
+                        }
+                }
+        }
+}
diff --git a/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/QueryInterpreterStoreAdapterImpl.java b/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/QueryInterpreterStoreAdapterImpl.java
new file mode 100644
index 00000000..10e7a402
--- /dev/null
+++ b/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/QueryInterpreterStoreAdapterImpl.java
@@ -0,0 +1,100 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.interpreter.internal;
+
+import tools.refinery.interpreter.CancellationToken;
+import tools.refinery.interpreter.api.IQuerySpecification;
+import tools.refinery.interpreter.api.InterpreterEngineOptions;
+import tools.refinery.interpreter.matchers.context.IInputKey;
+import tools.refinery.store.model.Model;
+import tools.refinery.store.model.ModelStore;
+import tools.refinery.store.query.dnf.AnyQuery;
+import tools.refinery.store.query.dnf.Query;
+import tools.refinery.store.query.interpreter.QueryInterpreterStoreAdapter;
+import tools.refinery.store.query.interpreter.internal.matcher.RawPatternMatcher;
+import tools.refinery.store.query.view.AnySymbolView;
+
+import java.util.*;
+
+public class QueryInterpreterStoreAdapterImpl implements QueryInterpreterStoreAdapter {
+        private final ModelStore store;
+        private final InterpreterEngineOptions engineOptions;
+        private final Map<AnySymbolView, IInputKey> inputKeys;
+        private final Map<AnyQuery, AnyQuery> canonicalQueryMap;
+        private final Map<AnyQuery, IQuerySpecification<RawPatternMatcher>> querySpecifications;
+        private final Set<AnyQuery> vacuousQueries;
+        private final Set<AnyQuery> allQueries;
+        private final CancellationToken cancellationToken;
+
+        QueryInterpreterStoreAdapterImpl(ModelStore store, InterpreterEngineOptions engineOptions,
+                                                                         Map<AnySymbolView, IInputKey> inputKeys,
+                                                                         Map<AnyQuery, AnyQuery> canonicalQueryMap,
+                                                                         Map<AnyQuery, IQuerySpecification<RawPatternMatcher>> querySpecifications,
+                                                                         Set<AnyQuery> vacuousQueries, CancellationToken cancellationToken) {
+                this.store = store;
+                this.engineOptions = engineOptions;
+                this.inputKeys = inputKeys;
+                this.canonicalQueryMap = canonicalQueryMap;
+                this.querySpecifications = querySpecifications;
+                this.vacuousQueries = vacuousQueries;
+                this.cancellationToken = cancellationToken;
+                var mutableAllQueries = new LinkedHashSet<AnyQuery>(querySpecifications.size() + vacuousQueries.size());
+                mutableAllQueries.addAll(querySpecifications.keySet());
+                mutableAllQueries.addAll(vacuousQueries);
+                this.allQueries = Collections.unmodifiableSet(mutableAllQueries);
+        }
+
+        @Override
+        public ModelStore getStore() {
+                return store;
+        }
+
+        public Collection<AnySymbolView> getSymbolViews() {
+                return inputKeys.keySet();
+        }
+
+        public Map<AnySymbolView, IInputKey> getInputKeys() {
+                return inputKeys;
+        }
+
+        @Override
+        public Collection<AnyQuery> getQueries() {
+                return allQueries;
+        }
+
+        public CancellationToken getCancellationToken() {
+                return cancellationToken;
+        }
+
+        @Override
+        public <T> Query<T> getCanonicalQuery(Query<T> query) {
+                // We know that canonical forms of queries do not change output types.
+                @SuppressWarnings("unchecked")
+                var canonicalQuery = (Query<T>) canonicalQueryMap.get(query);
+                if (canonicalQuery == null) {
+                        throw new IllegalArgumentException("Unknown query: " + query);
+                }
+                return canonicalQuery;
+        }
+
+        Map<AnyQuery, IQuerySpecification<RawPatternMatcher>> getQuerySpecifications() {
+                return querySpecifications;
+        }
+
+        Set<AnyQuery> getVacuousQueries() {
+                return vacuousQueries;
+        }
+
+        @Override
+        public InterpreterEngineOptions getEngineOptions() {
+                return engineOptions;
+        }
+
+        @Override
+        public QueryInterpreterAdapterImpl createModelAdapter(Model model) {
+                return new QueryInterpreterAdapterImpl(model, this);
+        }
+}
diff --git a/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/RelationalScope.java b/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/RelationalScope.java
new file mode 100644
index 00000000..7eef5b85
--- /dev/null
+++ b/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/RelationalScope.java
@@ -0,0 +1,27 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.interpreter.internal;
+
+import org.apache.log4j.Logger;
+import tools.refinery.interpreter.api.InterpreterEngine;
+import tools.refinery.interpreter.api.scope.IEngineContext;
+import tools.refinery.interpreter.api.scope.IIndexingErrorListener;
+import tools.refinery.interpreter.api.scope.QueryScope;
+import tools.refinery.store.query.interpreter.internal.context.RelationalEngineContext;
+
+public class RelationalScope extends QueryScope {
+        private final QueryInterpreterAdapterImpl adapter;
+
+        public RelationalScope(QueryInterpreterAdapterImpl adapter) {
+                this.adapter = adapter;
+        }
+
+        @Override
+        protected IEngineContext createEngineContext(InterpreterEngine engine, IIndexingErrorListener errorListener,
+                                                                                                 Logger logger) {
+                return new RelationalEngineContext(adapter);
+        }
+}
diff --git a/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/context/DummyBaseIndexer.java b/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/context/DummyBaseIndexer.java
new file mode 100644
index 00000000..e9a05fe9
--- /dev/null
+++ b/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/context/DummyBaseIndexer.java
@@ -0,0 +1,66 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.interpreter.internal.context;
+
+import tools.refinery.interpreter.api.scope.IBaseIndex;
+import tools.refinery.interpreter.api.scope.IIndexingErrorListener;
+import tools.refinery.interpreter.api.scope.IInstanceObserver;
+import tools.refinery.interpreter.api.scope.InterpreterBaseIndexChangeListener;
+
+import java.lang.reflect.InvocationTargetException;
+import java.util.concurrent.Callable;
+
+/**
+ * Copied from <code>tools.refinery.viatra.runtime.tabular.TabularEngineContext</code>
+ */
+public class DummyBaseIndexer implements IBaseIndex {
+        DummyBaseIndexer() {
+        }
+
+        @Override
+        public <V> V coalesceTraversals(Callable<V> callable) throws InvocationTargetException {
+                try {
+                        return callable.call();
+                } catch (Exception e) {
+                        throw new InvocationTargetException(e);
+                }
+        }
+
+        @Override
+        public void addBaseIndexChangeListener(InterpreterBaseIndexChangeListener listener) {
+                // no notification support
+        }
+
+        @Override
+        public void removeBaseIndexChangeListener(InterpreterBaseIndexChangeListener listener) {
+                // no notification support
+        }
+
+        @Override
+        public void resampleDerivedFeatures() {
+                throw new UnsupportedOperationException();
+        }
+
+        @Override
+        public boolean addIndexingErrorListener(IIndexingErrorListener listener) {
+                return false;
+        }
+
+        @Override
+        public boolean removeIndexingErrorListener(IIndexingErrorListener listener) {
+                return false;
+        }
+
+        @Override
+        public boolean addInstanceObserver(IInstanceObserver observer, Object observedObject) {
+                return false;
+        }
+
+        @Override
+        public boolean removeInstanceObserver(IInstanceObserver observer, Object observedObject) {
+                return false;
+        }
+}
diff --git a/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/context/RelationalEngineContext.java b/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/context/RelationalEngineContext.java
new file mode 100644
index 00000000..f6e8b605
--- /dev/null
+++ b/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/context/RelationalEngineContext.java
@@ -0,0 +1,35 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.interpreter.internal.context;
+
+import tools.refinery.interpreter.api.scope.IBaseIndex;
+import tools.refinery.interpreter.api.scope.IEngineContext;
+import tools.refinery.interpreter.matchers.context.IQueryRuntimeContext;
+import tools.refinery.store.query.interpreter.internal.QueryInterpreterAdapterImpl;
+
+public class RelationalEngineContext implements IEngineContext {
+        private final IBaseIndex baseIndex = new DummyBaseIndexer();
+        private final RelationalRuntimeContext runtimeContext;
+
+        public RelationalEngineContext(QueryInterpreterAdapterImpl adapter) {
+                runtimeContext = new RelationalRuntimeContext(adapter);
+        }
+
+        @Override
+        public IBaseIndex getBaseIndex() {
+                return this.baseIndex;
+        }
+
+        @Override
+        public void dispose() {
+                // Nothing to dispose, because lifecycle is not controlled by the engine.
+        }
+
+        @Override
+        public IQueryRuntimeContext getQueryRuntimeContext() {
+                return runtimeContext;
+        }
+}
diff --git a/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/context/RelationalQueryMetaContext.java b/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/context/RelationalQueryMetaContext.java
new file mode 100644
index 00000000..2b1ff2b4
--- /dev/null
+++ b/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/context/RelationalQueryMetaContext.java
@@ -0,0 +1,117 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.interpreter.internal.context;
+
+import tools.refinery.interpreter.matchers.context.AbstractQueryMetaContext;
+import tools.refinery.interpreter.matchers.context.IInputKey;
+import tools.refinery.interpreter.matchers.context.InputKeyImplication;
+import tools.refinery.interpreter.matchers.context.common.JavaTransitiveInstancesKey;
+import tools.refinery.store.query.interpreter.internal.pquery.SymbolViewWrapper;
+import tools.refinery.store.query.view.AnySymbolView;
+
+import java.util.*;
+
+/**
+ * The meta context information for String scopes.
+ */
+public class RelationalQueryMetaContext extends AbstractQueryMetaContext {
+        private final Map<AnySymbolView, IInputKey> inputKeys;
+
+        RelationalQueryMetaContext(Map<AnySymbolView, IInputKey> inputKeys) {
+                this.inputKeys = inputKeys;
+        }
+
+        @Override
+        public boolean isEnumerable(IInputKey key) {
+                checkKey(key);
+                return key.isEnumerable();
+        }
+
+        @Override
+        public boolean isStateless(IInputKey key) {
+                checkKey(key);
+                return true;
+        }
+
+        @Override
+        public boolean canLeadOutOfScope(IInputKey key) {
+                return false;
+        }
+
+        @Override
+        public Collection<InputKeyImplication> getImplications(IInputKey implyingKey) {
+                if (implyingKey instanceof JavaTransitiveInstancesKey) {
+                        return List.of();
+                }
+                var symbolView = checkKey(implyingKey);
+                var relationViewImplications = symbolView.getImpliedRelationViews();
+                var inputKeyImplications = new HashSet<InputKeyImplication>(relationViewImplications.size());
+                for (var relationViewImplication : relationViewImplications) {
+                        if (!symbolView.equals(relationViewImplication.implyingView())) {
+                                throw new IllegalArgumentException("Relation view %s returned unrelated implication %s".formatted(
+                                                symbolView, relationViewImplication));
+                        }
+                        var impliedInputKey = inputKeys.get(relationViewImplication.impliedView());
+                        // Ignore implications not relevant for any queries included in the model.
+                        if (impliedInputKey != null) {
+                                inputKeyImplications.add(new InputKeyImplication(implyingKey, impliedInputKey,
+                                                relationViewImplication.impliedIndices()));
+                        }
+                }
+                var parameters = symbolView.getParameters();
+                int arity = symbolView.arity();
+                for (int i = 0; i < arity; i++) {
+                        var parameter = parameters.get(i);
+                        var parameterType = parameter.tryGetType();
+                        if (parameterType.isPresent()) {
+                                var javaTransitiveInstancesKey = new JavaTransitiveInstancesKey(parameterType.get());
+                                var javaImplication = new InputKeyImplication(implyingKey, javaTransitiveInstancesKey, List.of(i));
+                                inputKeyImplications.add(javaImplication);
+                        }
+                }
+                return inputKeyImplications;
+        }
+
+        @Override
+        public Map<Set<Integer>, Set<Integer>> getFunctionalDependencies(IInputKey key) {
+                if (key instanceof JavaTransitiveInstancesKey) {
+                        return Map.of();
+                }
+                var relationView = checkKey(key);
+                var functionalDependencies = relationView.getFunctionalDependencies();
+                var flattened = new HashMap<Set<Integer>, Set<Integer>>(functionalDependencies.size());
+                for (var functionalDependency : functionalDependencies) {
+                        var forEach = functionalDependency.forEach();
+                        checkValidIndices(relationView, forEach);
+                        var unique = functionalDependency.unique();
+                        checkValidIndices(relationView, unique);
+                        var existing = flattened.get(forEach);
+                        if (existing == null) {
+                                flattened.put(forEach, new HashSet<>(unique));
+                        } else {
+                                existing.addAll(unique);
+                        }
+                }
+                return flattened;
+        }
+
+        private static void checkValidIndices(AnySymbolView relationView, Collection<Integer> indices) {
+                indices.stream().filter(relationView::invalidIndex).findAny().ifPresent(i -> {
+                        throw new IllegalArgumentException("Index %d is invalid for %s".formatted(i, relationView));
+                });
+        }
+
+        public AnySymbolView checkKey(IInputKey key) {
+                if (!(key instanceof SymbolViewWrapper wrapper)) {
+                        throw new IllegalArgumentException("The input key %s is not a valid input key".formatted(key));
+                }
+                var symbolView = wrapper.getWrappedKey();
+                if (!inputKeys.containsKey(symbolView)) {
+                        throw new IllegalArgumentException("The input key %s is not present in the model".formatted(key));
+                }
+                return symbolView;
+        }
+}
diff --git a/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/context/RelationalRuntimeContext.java b/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/context/RelationalRuntimeContext.java
new file mode 100644
index 00000000..5870b0c2
--- /dev/null
+++ b/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/context/RelationalRuntimeContext.java
@@ -0,0 +1,204 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.interpreter.internal.context;
+
+import tools.refinery.interpreter.CancellationToken;
+import tools.refinery.interpreter.matchers.context.*;
+import tools.refinery.interpreter.matchers.tuple.ITuple;
+import tools.refinery.interpreter.matchers.tuple.Tuple;
+import tools.refinery.interpreter.matchers.tuple.TupleMask;
+import tools.refinery.interpreter.matchers.tuple.Tuples;
+import tools.refinery.interpreter.matchers.util.Accuracy;
+import tools.refinery.store.model.Model;
+import tools.refinery.store.query.interpreter.internal.QueryInterpreterAdapterImpl;
+import tools.refinery.store.query.interpreter.internal.pquery.SymbolViewWrapper;
+import tools.refinery.store.query.interpreter.internal.update.ModelUpdateListener;
+import tools.refinery.store.query.view.AnySymbolView;
+
+import java.lang.reflect.InvocationTargetException;
+import java.util.Iterator;
+import java.util.Optional;
+import java.util.concurrent.Callable;
+
+import static tools.refinery.store.util.CollectionsUtil.filter;
+import static tools.refinery.store.util.CollectionsUtil.map;
+
+public class RelationalRuntimeContext implements IQueryRuntimeContext {
+        private final RelationalQueryMetaContext metaContext;
+
+        private final ModelUpdateListener modelUpdateListener;
+
+        private final Model model;
+
+        private final CancellationToken cancellationToken;
+
+        RelationalRuntimeContext(QueryInterpreterAdapterImpl adapter) {
+                model = adapter.getModel();
+                metaContext = new RelationalQueryMetaContext(adapter.getStoreAdapter().getInputKeys());
+                modelUpdateListener = new ModelUpdateListener(adapter);
+                cancellationToken = adapter.getCancellationToken();
+        }
+
+        @Override
+        public IQueryMetaContext getMetaContext() {
+                return metaContext;
+        }
+
+        @Override
+        public <V> V coalesceTraversals(Callable<V> callable) throws InvocationTargetException {
+                try {
+                        return callable.call();
+                } catch (Exception e) {
+                        throw new InvocationTargetException(e);
+                }
+        }
+
+        @Override
+        public boolean isCoalescing() {
+                return false;
+        }
+
+        @Override
+        public boolean isIndexed(IInputKey key, IndexingService service) {
+                if (key instanceof SymbolViewWrapper wrapper) {
+                        var symbolViewKey = wrapper.getWrappedKey();
+                        return this.modelUpdateListener.containsSymbolView(symbolViewKey);
+                } else {
+                        return false;
+                }
+        }
+
+        @Override
+        public void ensureIndexed(IInputKey key, IndexingService service) {
+                if (!isIndexed(key, service)) {
+                        throw new IllegalStateException("Engine tries to index a new key %s".formatted(key));
+                }
+        }
+
+        AnySymbolView checkKey(IInputKey key) {
+                if (key instanceof SymbolViewWrapper wrappedKey) {
+                        var symbolViewKey = wrappedKey.getWrappedKey();
+                        if (modelUpdateListener.containsSymbolView(symbolViewKey)) {
+                                return symbolViewKey;
+                        } else {
+                                throw new IllegalStateException("Query is asking for non-indexed key %s".formatted(symbolViewKey));
+                        }
+                } else {
+                        throw new IllegalStateException("Query is asking for non-relational key");
+                }
+        }
+
+        @Override
+        public int countTuples(IInputKey key, TupleMask seedMask, ITuple seed) {
+                Iterator<Object[]> iterator = enumerate(key, seedMask, seed).iterator();
+                int result = 0;
+                while (iterator.hasNext()) {
+                        iterator.next();
+                        result++;
+                }
+                return result;
+        }
+
+        @Override
+        public Optional<Long> estimateCardinality(IInputKey key, TupleMask groupMask, Accuracy requiredAccuracy) {
+                return Optional.empty();
+        }
+
+        @Override
+        public Iterable<Tuple> enumerateTuples(IInputKey key, TupleMask seedMask, ITuple seed) {
+                var filteredBySeed = enumerate(key, seedMask, seed);
+                return map(filteredBySeed, Tuples::flatTupleOf);
+        }
+
+        @Override
+        public Iterable<?> enumerateValues(IInputKey key, TupleMask seedMask, ITuple seed) {
+                var index = seedMask.getFirstOmittedIndex().orElseThrow(
+                                () -> new IllegalArgumentException("Seed mask does not omit a value"));
+                var filteredBySeed = enumerate(key, seedMask, seed);
+                return map(filteredBySeed, array -> array[index]);
+        }
+
+        private Iterable<Object[]> enumerate(IInputKey key, TupleMask seedMask, ITuple seed) {
+                var relationViewKey = checkKey(key);
+                Iterable<Object[]> allObjects = getAllObjects(relationViewKey, seedMask, seed);
+                return filter(allObjects, objectArray -> isMatching(objectArray, seedMask, seed));
+        }
+
+        private Iterable<Object[]> getAllObjects(AnySymbolView key, TupleMask seedMask, ITuple seed) {
+                for (int i = 0; i < seedMask.indices.length; i++) {
+                        int slot = seedMask.indices[i];
+                        if (key.canIndexSlot(slot)) {
+                                return key.getAdjacent(model, slot, seed.get(i));
+                        }
+                }
+                return key.getAll(model);
+        }
+
+        private static boolean isMatching(Object[] tuple, TupleMask seedMask, ITuple seed) {
+                for (int i = 0; i < seedMask.indices.length; i++) {
+                        final Object seedElement = seed.get(i);
+                        final Object tupleElement = tuple[seedMask.indices[i]];
+                        if (!tupleElement.equals(seedElement)) {
+                                return false;
+                        }
+                }
+                return true;
+        }
+
+        @Override
+        public boolean containsTuple(IInputKey key, ITuple seed) {
+                var relationViewKey = checkKey(key);
+                return relationViewKey.get(model, seed.getElements());
+        }
+
+        @Override
+        public void addUpdateListener(IInputKey key, Tuple seed, IQueryRuntimeContextListener listener) {
+                var relationViewKey = checkKey(key);
+                this.modelUpdateListener.addListener(key, relationViewKey, seed, listener);
+
+        }
+
+        @Override
+        public void removeUpdateListener(IInputKey key, Tuple seed, IQueryRuntimeContextListener listener) {
+                var relationViewKey = checkKey(key);
+                this.modelUpdateListener.removeListener(key, relationViewKey, seed, listener);
+        }
+
+        @Override
+        public Object wrapElement(Object externalElement) {
+                return externalElement;
+        }
+
+        @Override
+        public Object unwrapElement(Object internalElement) {
+                return internalElement;
+        }
+
+        @Override
+        public Tuple wrapTuple(Tuple externalElements) {
+                return externalElements;
+        }
+
+        @Override
+        public Tuple unwrapTuple(Tuple internalElements) {
+                return internalElements;
+        }
+
+        @Override
+        public void ensureWildcardIndexing(IndexingService service) {
+                throw new UnsupportedOperationException();
+        }
+
+        @Override
+        public void executeAfterTraversal(Runnable runnable) {
+                runnable.run();
+        }
+
+        @Override
+        public CancellationToken getCancellationToken() {
+                return cancellationToken;
+        }
+}
diff --git a/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/localsearch/FlatCostFunction.java b/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/localsearch/FlatCostFunction.java
new file mode 100644
index 00000000..45fd9fbd
--- /dev/null
+++ b/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/localsearch/FlatCostFunction.java
@@ -0,0 +1,35 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.interpreter.internal.localsearch;
+
+import tools.refinery.interpreter.localsearch.planner.cost.IConstraintEvaluationContext;
+import tools.refinery.interpreter.localsearch.planner.cost.impl.StatisticsBasedConstraintCostFunction;
+import tools.refinery.interpreter.matchers.context.IInputKey;
+import tools.refinery.interpreter.matchers.psystem.basicenumerables.TypeConstraint;
+import tools.refinery.interpreter.matchers.tuple.TupleMask;
+import tools.refinery.interpreter.matchers.util.Accuracy;
+
+import java.util.Optional;
+
+public class FlatCostFunction extends StatisticsBasedConstraintCostFunction {
+        public FlatCostFunction() {
+                // No inverse navigation penalty thanks to relational storage.
+                super(0);
+        }
+
+        @Override
+        public Optional<Long> projectionSize(IConstraintEvaluationContext input, IInputKey supplierKey, TupleMask groupMask, Accuracy requiredAccuracy) {
+                // We always start from an empty model, where every projection is of size 0.
+                // Therefore, projection size estimation is meaningless.
+                return Optional.empty();
+        }
+
+        @Override
+        protected double _calculateCost(TypeConstraint constraint, IConstraintEvaluationContext input) {
+                // Assume a flat cost for each relation. Maybe adjust in the future if we perform indexing?
+                return DEFAULT_COST;
+        }
+}
diff --git a/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/matcher/AbstractInterpretedMatcher.java b/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/matcher/AbstractInterpretedMatcher.java
new file mode 100644
index 00000000..8cec0bf6
--- /dev/null
+++ b/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/matcher/AbstractInterpretedMatcher.java
@@ -0,0 +1,32 @@
+/*
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.interpreter.internal.matcher;
+
+import tools.refinery.interpreter.matchers.backend.IQueryResultProvider;
+import tools.refinery.interpreter.matchers.backend.IUpdateable;
+import tools.refinery.store.query.dnf.Query;
+import tools.refinery.store.query.resultset.AbstractResultSet;
+import tools.refinery.store.query.interpreter.internal.QueryInterpreterAdapterImpl;
+
+public abstract class AbstractInterpretedMatcher<T> extends AbstractResultSet<T> implements IUpdateable {
+        protected final IQueryResultProvider backend;
+
+        protected AbstractInterpretedMatcher(QueryInterpreterAdapterImpl adapter, Query<T> query,
+                                                                                 RawPatternMatcher rawPatternMatcher) {
+                super(adapter, query);
+                backend = rawPatternMatcher.getBackend();
+        }
+
+        @Override
+        protected void startListeningForChanges() {
+                backend.addUpdateListener(this, this, false);
+        }
+
+        @Override
+        protected void stopListeningForChanges() {
+                backend.removeUpdateListener(this);
+        }
+}
diff --git a/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/matcher/FunctionalCursor.java b/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/matcher/FunctionalCursor.java
new file mode 100644
index 00000000..e3b53f6b
--- /dev/null
+++ b/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/matcher/FunctionalCursor.java
@@ -0,0 +1,52 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.interpreter.internal.matcher;
+
+import tools.refinery.interpreter.rete.index.IterableIndexer;
+import tools.refinery.store.map.Cursor;
+import tools.refinery.store.tuple.Tuple;
+
+import java.util.Iterator;
+
+class FunctionalCursor<T> implements Cursor<Tuple, T> {
+        private final IterableIndexer indexer;
+        private final Iterator<tools.refinery.interpreter.matchers.tuple.Tuple> iterator;
+        private boolean terminated;
+        private Tuple key;
+        private T value;
+
+        public FunctionalCursor(IterableIndexer indexer) {
+                this.indexer = indexer;
+                iterator = indexer.getSignatures().iterator();
+        }
+
+        @Override
+        public Tuple getKey() {
+                return key;
+        }
+
+        @Override
+        public T getValue() {
+                return value;
+        }
+
+        @Override
+        public boolean isTerminated() {
+                return terminated;
+        }
+
+        @Override
+        public boolean move() {
+                if (!terminated && iterator.hasNext()) {
+                        var match = iterator.next();
+                        key = MatcherUtils.toRefineryTuple(match);
+                        value = MatcherUtils.getSingleValue(indexer.get(match));
+                        return true;
+                }
+                terminated = true;
+                return false;
+        }
+}
diff --git a/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/matcher/InterpretedFunctionalMatcher.java b/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/matcher/InterpretedFunctionalMatcher.java
new file mode 100644
index 00000000..249664a4
--- /dev/null
+++ b/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/matcher/InterpretedFunctionalMatcher.java
@@ -0,0 +1,89 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.interpreter.internal.matcher;
+
+import tools.refinery.interpreter.matchers.context.IQueryRuntimeContext;
+import tools.refinery.interpreter.matchers.tuple.TupleMask;
+import tools.refinery.interpreter.matchers.tuple.Tuples;
+import tools.refinery.interpreter.rete.index.IterableIndexer;
+import tools.refinery.interpreter.rete.matcher.RetePatternMatcher;
+import tools.refinery.store.map.Cursor;
+import tools.refinery.store.query.dnf.FunctionalQuery;
+import tools.refinery.store.query.interpreter.internal.QueryInterpreterAdapterImpl;
+import tools.refinery.store.tuple.Tuple;
+
+/**
+ * Directly access the tuples inside a Refinery Interpreter pattern matcher.<p>
+ * This class neglects calling
+ * {@link IQueryRuntimeContext#wrapTuple(tools.refinery.interpreter.matchers.tuple.Tuple)}
+ * and
+ * {@link IQueryRuntimeContext#unwrapTuple(tools.refinery.interpreter.matchers.tuple.Tuple)},
+ * because {@link tools.refinery.store.query.interpreter.internal.context.RelationalRuntimeContext} provides a trivial
+ * implementation for these methods.
+ * Using this class with any other runtime context may lead to undefined behavior.
+ */
+public class InterpretedFunctionalMatcher<T> extends AbstractInterpretedMatcher<T> {
+        private final TupleMask emptyMask;
+        private final TupleMask omitOutputMask;
+        private final IterableIndexer omitOutputIndexer;
+
+        public InterpretedFunctionalMatcher(QueryInterpreterAdapterImpl adapter, FunctionalQuery<T> query,
+                                                                                RawPatternMatcher rawPatternMatcher) {
+                super(adapter, query, rawPatternMatcher);
+                int arity = query.arity();
+                int arityWithOutput = arity + 1;
+                emptyMask = TupleMask.empty(arityWithOutput);
+                omitOutputMask = TupleMask.omit(arity, arityWithOutput);
+                if (backend instanceof RetePatternMatcher reteBackend) {
+                        var maybeIterableOmitOutputIndexer = reteBackend.getInternalIndexer(omitOutputMask);
+                        if (maybeIterableOmitOutputIndexer instanceof IterableIndexer iterableOmitOutputIndexer) {
+                                omitOutputIndexer = iterableOmitOutputIndexer;
+                        } else {
+                                omitOutputIndexer = null;
+                        }
+                } else {
+                        omitOutputIndexer = null;
+                }
+        }
+
+        @Override
+        public T get(Tuple parameters) {
+                var tuple = MatcherUtils.toViatraTuple(parameters);
+                if (omitOutputIndexer == null) {
+                        return MatcherUtils.getSingleValue(backend.getAllMatches(omitOutputMask, tuple).iterator());
+                } else {
+                        return MatcherUtils.getSingleValue(omitOutputIndexer.get(tuple));
+                }
+        }
+
+        @Override
+        public Cursor<Tuple, T> getAll() {
+                if (omitOutputIndexer == null) {
+                        var allMatches = backend.getAllMatches(emptyMask, Tuples.staticArityFlatTupleOf());
+                        return new UnsafeFunctionalCursor<>(allMatches.iterator());
+                }
+                return new FunctionalCursor<>(omitOutputIndexer);
+        }
+
+        @Override
+        public int size() {
+                if (omitOutputIndexer == null) {
+                        return backend.countMatches(emptyMask, Tuples.staticArityFlatTupleOf());
+                }
+                return omitOutputIndexer.getBucketCount();
+        }
+
+        @Override
+        public void update(tools.refinery.interpreter.matchers.tuple.Tuple updateElement, boolean isInsertion) {
+                var key = MatcherUtils.keyToRefineryTuple(updateElement);
+                var value = MatcherUtils.<T>getValue(updateElement);
+                if (isInsertion) {
+                        notifyChange(key, null, value);
+                } else {
+                        notifyChange(key, value, null);
+                }
+        }
+}
diff --git a/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/matcher/InterpretedRelationalMatcher.java b/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/matcher/InterpretedRelationalMatcher.java
new file mode 100644
index 00000000..9278b46d
--- /dev/null
+++ b/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/matcher/InterpretedRelationalMatcher.java
@@ -0,0 +1,81 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.interpreter.internal.matcher;
+
+import tools.refinery.interpreter.matchers.context.IQueryRuntimeContext;
+import tools.refinery.interpreter.matchers.tuple.TupleMask;
+import tools.refinery.interpreter.matchers.tuple.Tuples;
+import tools.refinery.interpreter.rete.index.Indexer;
+import tools.refinery.interpreter.rete.matcher.RetePatternMatcher;
+import tools.refinery.store.map.Cursor;
+import tools.refinery.store.map.Cursors;
+import tools.refinery.store.query.dnf.RelationalQuery;
+import tools.refinery.store.query.interpreter.internal.QueryInterpreterAdapterImpl;
+import tools.refinery.store.tuple.Tuple;
+
+/**
+ * Directly access the tuples inside a Refinery Interpreter pattern matcher.<p>
+ * This class neglects calling
+ * {@link IQueryRuntimeContext#wrapTuple(tools.refinery.interpreter.matchers.tuple.Tuple)}
+ * and
+ * {@link IQueryRuntimeContext#unwrapTuple(tools.refinery.interpreter.matchers.tuple.Tuple)},
+ * because {@link tools.refinery.store.query.interpreter.internal.context.RelationalRuntimeContext} provides a trivial
+ * implementation for these methods.
+ * Using this class with any other runtime context may lead to undefined behavior.
+ */
+public class InterpretedRelationalMatcher extends AbstractInterpretedMatcher<Boolean> {
+        private final TupleMask emptyMask;
+        private final TupleMask identityMask;
+        private final Indexer emptyMaskIndexer;
+
+        public InterpretedRelationalMatcher(QueryInterpreterAdapterImpl adapter, RelationalQuery query,
+                                                                                RawPatternMatcher rawPatternMatcher) {
+                super(adapter, query, rawPatternMatcher);
+                int arity = query.arity();
+                emptyMask = TupleMask.empty(arity);
+                identityMask = TupleMask.identity(arity);
+                if (backend instanceof RetePatternMatcher reteBackend) {
+                        emptyMaskIndexer = reteBackend.getInternalIndexer(emptyMask);
+                } else {
+                        emptyMaskIndexer = null;
+                }
+        }
+
+        @Override
+        public Boolean get(Tuple parameters) {
+                var tuple = MatcherUtils.toViatraTuple(parameters);
+                if (emptyMaskIndexer == null) {
+                        return backend.hasMatch(identityMask, tuple);
+                }
+                var matches = emptyMaskIndexer.get(Tuples.staticArityFlatTupleOf());
+                return matches != null && matches.contains(tuple);
+        }
+
+        @Override
+        public Cursor<Tuple, Boolean> getAll() {
+                if (emptyMaskIndexer == null) {
+                        var allMatches = backend.getAllMatches(emptyMask, Tuples.staticArityFlatTupleOf());
+                        return new RelationalCursor(allMatches.iterator());
+                }
+                var matches = emptyMaskIndexer.get(Tuples.staticArityFlatTupleOf());
+                return matches == null ? Cursors.empty() : new RelationalCursor(matches.stream().iterator());
+        }
+
+        @Override
+        public int size() {
+                if (emptyMaskIndexer == null) {
+                        return backend.countMatches(emptyMask, Tuples.staticArityFlatTupleOf());
+                }
+                var matches = emptyMaskIndexer.get(Tuples.staticArityFlatTupleOf());
+                return matches == null ? 0 : matches.size();
+        }
+
+        @Override
+        public void update(tools.refinery.interpreter.matchers.tuple.Tuple updateElement, boolean isInsertion) {
+                var key = MatcherUtils.toRefineryTuple(updateElement);
+                notifyChange(key, !isInsertion, isInsertion);
+        }
+}
diff --git a/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/matcher/MatcherUtils.java b/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/matcher/MatcherUtils.java
new file mode 100644
index 00000000..b30b83b5
--- /dev/null
+++ b/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/matcher/MatcherUtils.java
@@ -0,0 +1,115 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.interpreter.internal.matcher;
+
+import tools.refinery.interpreter.matchers.tuple.ITuple;
+import tools.refinery.interpreter.matchers.tuple.Tuples;
+import org.jetbrains.annotations.Nullable;
+import tools.refinery.store.tuple.*;
+
+import java.util.Iterator;
+
+final class MatcherUtils {
+        private MatcherUtils() {
+                throw new IllegalStateException("This is a static utility class and should not be instantiated directly");
+        }
+
+        public static tools.refinery.interpreter.matchers.tuple.Tuple toViatraTuple(Tuple refineryTuple) {
+                if (refineryTuple instanceof Tuple0) {
+                        return Tuples.staticArityFlatTupleOf();
+                } else if (refineryTuple instanceof Tuple1) {
+                        return Tuples.staticArityFlatTupleOf(refineryTuple);
+                } else if (refineryTuple instanceof Tuple2 tuple2) {
+                        return Tuples.staticArityFlatTupleOf(Tuple.of(tuple2.value0()), Tuple.of(tuple2.value1()));
+                } else if (refineryTuple instanceof Tuple3 tuple3) {
+                        return Tuples.staticArityFlatTupleOf(Tuple.of(tuple3.value0()), Tuple.of(tuple3.value1()),
+                                        Tuple.of(tuple3.value2()));
+                } else if (refineryTuple instanceof Tuple4 tuple4) {
+                        return Tuples.staticArityFlatTupleOf(Tuple.of(tuple4.value0()), Tuple.of(tuple4.value1()),
+                                        Tuple.of(tuple4.value2()), Tuple.of(tuple4.value3()));
+                } else {
+                        int arity = refineryTuple.getSize();
+                        var values = new Object[arity];
+                        for (int i = 0; i < arity; i++) {
+                                values[i] = Tuple.of(refineryTuple.get(i));
+                        }
+                        return Tuples.flatTupleOf(values);
+                }
+        }
+
+        public static Tuple toRefineryTuple(ITuple viatraTuple) {
+                int arity = viatraTuple.getSize();
+                if (arity == 1) {
+                        return getWrapper(viatraTuple, 0);
+                }
+                return prefixToRefineryTuple(viatraTuple, viatraTuple.getSize());
+        }
+
+        public static Tuple keyToRefineryTuple(ITuple viatraTuple) {
+                return prefixToRefineryTuple(viatraTuple, viatraTuple.getSize() - 1);
+        }
+
+        private static Tuple prefixToRefineryTuple(ITuple viatraTuple, int targetArity) {
+                if (targetArity < 0) {
+                        throw new IllegalArgumentException("Requested negative prefix %d of %s"
+                                        .formatted(targetArity, viatraTuple));
+                }
+                return switch (targetArity) {
+                        case 0 -> Tuple.of();
+                        case 1 -> Tuple.of(unwrap(viatraTuple, 0));
+                        case 2 -> Tuple.of(unwrap(viatraTuple, 0), unwrap(viatraTuple, 1));
+                        case 3 -> Tuple.of(unwrap(viatraTuple, 0), unwrap(viatraTuple, 1), unwrap(viatraTuple, 2));
+                        case 4 -> Tuple.of(unwrap(viatraTuple, 0), unwrap(viatraTuple, 1), unwrap(viatraTuple, 2),
+                                        unwrap(viatraTuple, 3));
+                        default -> {
+                                var entries = new int[targetArity];
+                                for (int i = 0; i < targetArity; i++) {
+                                        entries[i] = unwrap(viatraTuple, i);
+                                }
+                                yield Tuple.of(entries);
+                        }
+                };
+        }
+
+        private static Tuple1 getWrapper(ITuple viatraTuple, int index) {
+                if (!((viatraTuple.get(index)) instanceof Tuple1 wrappedObjectId)) {
+                        throw new IllegalArgumentException("Element %d of tuple %s is not an object id"
+                                        .formatted(index, viatraTuple));
+                }
+                return wrappedObjectId;
+        }
+
+        private static int unwrap(ITuple viatraTuple, int index) {
+                return getWrapper(viatraTuple, index).value0();
+        }
+
+        public static <T> T getValue(ITuple match) {
+                // This is only safe if we know for sure that match came from a functional query of type {@code T}.
+                @SuppressWarnings("unchecked")
+                var result = (T) match.get(match.getSize() - 1);
+                return result;
+        }
+
+        public static <T> T getSingleValue(@Nullable Iterable<? extends ITuple> viatraTuples) {
+                if (viatraTuples == null) {
+                        return null;
+                }
+                return getSingleValue(viatraTuples.iterator());
+        }
+
+        public static <T> T getSingleValue(Iterator<? extends ITuple> iterator) {
+                if (!iterator.hasNext()) {
+                        return null;
+                }
+                var match = iterator.next();
+                var result = MatcherUtils.<T>getValue(match);
+                if (iterator.hasNext()) {
+                        var input = keyToRefineryTuple(match);
+                        throw new IllegalStateException("Query is not functional for input tuple: " + input);
+                }
+                return result;
+        }
+}
diff --git a/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/matcher/RawPatternMatcher.java b/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/matcher/RawPatternMatcher.java
new file mode 100644
index 00000000..fcd5a236
--- /dev/null
+++ b/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/matcher/RawPatternMatcher.java
@@ -0,0 +1,20 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.interpreter.internal.matcher;
+
+import tools.refinery.interpreter.api.GenericPatternMatcher;
+import tools.refinery.interpreter.api.GenericQuerySpecification;
+import tools.refinery.interpreter.matchers.backend.IQueryResultProvider;
+
+public class RawPatternMatcher extends GenericPatternMatcher {
+    public RawPatternMatcher(GenericQuerySpecification<? extends GenericPatternMatcher> specification) {
+        super(specification);
+    }
+
+        IQueryResultProvider getBackend() {
+                return backend;
+        }
+}
diff --git a/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/matcher/RelationalCursor.java b/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/matcher/RelationalCursor.java
new file mode 100644
index 00000000..45eb9fff
--- /dev/null
+++ b/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/matcher/RelationalCursor.java
@@ -0,0 +1,47 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.interpreter.internal.matcher;
+
+import tools.refinery.interpreter.matchers.tuple.ITuple;
+import tools.refinery.store.map.Cursor;
+import tools.refinery.store.tuple.Tuple;
+
+import java.util.Iterator;
+
+class RelationalCursor implements Cursor<Tuple, Boolean> {
+    private final Iterator<? extends ITuple> tuplesIterator;
+    private boolean terminated;
+    private Tuple key;
+
+    public RelationalCursor(Iterator<? extends ITuple> tuplesIterator) {
+        this.tuplesIterator = tuplesIterator;
+    }
+
+    @Override
+    public Tuple getKey() {
+        return key;
+    }
+
+    @Override
+    public Boolean getValue() {
+        return true;
+    }
+
+    @Override
+    public boolean isTerminated() {
+        return terminated;
+    }
+
+    @Override
+    public boolean move() {
+        if (!terminated && tuplesIterator.hasNext()) {
+            key = MatcherUtils.toRefineryTuple(tuplesIterator.next());
+            return true;
+        }
+        terminated = true;
+        return false;
+    }
+}
diff --git a/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/matcher/UnsafeFunctionalCursor.java b/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/matcher/UnsafeFunctionalCursor.java
new file mode 100644
index 00000000..d3a7c743
--- /dev/null
+++ b/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/matcher/UnsafeFunctionalCursor.java
@@ -0,0 +1,55 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.interpreter.internal.matcher;
+
+import tools.refinery.interpreter.matchers.tuple.ITuple;
+import tools.refinery.store.map.Cursor;
+import tools.refinery.store.tuple.Tuple;
+
+import java.util.Iterator;
+
+/**
+ * Cursor for a functional result set that iterates over a stream of raw matches and doesn't check whether the
+ * functional dependency of the output on the inputs is obeyed.
+ * @param <T> The output type.
+ */
+class UnsafeFunctionalCursor<T> implements Cursor<Tuple, T> {
+        private final Iterator<? extends ITuple> tuplesIterator;
+        private boolean terminated;
+        private Tuple key;
+        private T value;
+
+        public UnsafeFunctionalCursor(Iterator<? extends ITuple> tuplesIterator) {
+                this.tuplesIterator = tuplesIterator;
+        }
+
+        @Override
+        public Tuple getKey() {
+                return key;
+        }
+
+        @Override
+        public T getValue() {
+                return value;
+        }
+
+        @Override
+        public boolean isTerminated() {
+                return terminated;
+        }
+
+        @Override
+        public boolean move() {
+                if (!terminated && tuplesIterator.hasNext()) {
+                        var match = tuplesIterator.next();
+                        key = MatcherUtils.keyToRefineryTuple(match);
+                        value = MatcherUtils.getValue(match);
+                        return true;
+                }
+                terminated = true;
+                return false;
+        }
+}
diff --git a/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/pquery/CheckEvaluator.java b/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/pquery/CheckEvaluator.java
new file mode 100644
index 00000000..4a71e879
--- /dev/null
+++ b/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/pquery/CheckEvaluator.java
@@ -0,0 +1,21 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.interpreter.internal.pquery;
+
+import tools.refinery.interpreter.matchers.psystem.IValueProvider;
+import tools.refinery.store.query.term.Term;
+
+class CheckEvaluator extends TermEvaluator<Boolean> {
+        public CheckEvaluator(Term<Boolean> term) {
+                super(term);
+        }
+
+        @Override
+        public Object evaluateExpression(IValueProvider provider) {
+                var result = super.evaluateExpression(provider);
+                return result == null ? Boolean.FALSE : result;
+        }
+}
diff --git a/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/pquery/Dnf2PQuery.java b/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/pquery/Dnf2PQuery.java
new file mode 100644
index 00000000..73ce4043
--- /dev/null
+++ b/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/pquery/Dnf2PQuery.java
@@ -0,0 +1,253 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.interpreter.internal.pquery;
+
+import tools.refinery.interpreter.matchers.psystem.basicdeferred.*;
+import tools.refinery.interpreter.matchers.psystem.basicenumerables.*;
+import tools.refinery.interpreter.matchers.psystem.basicenumerables.Connectivity;
+import tools.refinery.store.query.Constraint;
+import tools.refinery.store.query.dnf.Dnf;
+import tools.refinery.store.query.dnf.DnfClause;
+import tools.refinery.store.query.dnf.SymbolicParameter;
+import tools.refinery.store.query.literal.*;
+import tools.refinery.store.query.term.ConstantTerm;
+import tools.refinery.store.query.term.StatefulAggregator;
+import tools.refinery.store.query.term.StatelessAggregator;
+import tools.refinery.store.query.term.Variable;
+import tools.refinery.store.query.view.AnySymbolView;
+import tools.refinery.store.util.CycleDetectingMapper;
+import tools.refinery.interpreter.matchers.backend.IQueryBackendFactory;
+import tools.refinery.interpreter.matchers.backend.QueryEvaluationHint;
+import tools.refinery.interpreter.matchers.context.IInputKey;
+import tools.refinery.interpreter.matchers.psystem.PBody;
+import tools.refinery.interpreter.matchers.psystem.PVariable;
+import tools.refinery.interpreter.matchers.psystem.aggregations.BoundAggregator;
+import tools.refinery.interpreter.matchers.psystem.aggregations.IMultisetAggregationOperator;
+import tools.refinery.interpreter.matchers.psystem.annotations.PAnnotation;
+import tools.refinery.interpreter.matchers.psystem.queries.PParameter;
+import tools.refinery.interpreter.matchers.psystem.queries.PParameterDirection;
+import tools.refinery.interpreter.matchers.psystem.queries.PQuery;
+import tools.refinery.interpreter.matchers.tuple.Tuple;
+import tools.refinery.interpreter.matchers.tuple.Tuples;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.function.Function;
+
+public class Dnf2PQuery {
+        private final CycleDetectingMapper<Dnf, RawPQuery> mapper = new CycleDetectingMapper<>(Dnf::name,
+                        this::doTranslate);
+        private final QueryWrapperFactory wrapperFactory = new QueryWrapperFactory(this);
+        private Function<Dnf, QueryEvaluationHint> computeHint = dnf -> new QueryEvaluationHint(null,
+                        (IQueryBackendFactory) null);
+
+        public void setComputeHint(Function<Dnf, QueryEvaluationHint> computeHint) {
+                this.computeHint = computeHint;
+        }
+
+        public RawPQuery translate(Dnf dnfQuery) {
+                return mapper.map(dnfQuery);
+        }
+
+        public Map<AnySymbolView, IInputKey> getSymbolViews() {
+                return wrapperFactory.getSymbolViews();
+        }
+
+        private RawPQuery doTranslate(Dnf dnfQuery) {
+                var pQuery = new RawPQuery(dnfQuery.getUniqueName());
+                pQuery.setEvaluationHints(computeHint.apply(dnfQuery));
+
+                Map<SymbolicParameter, PParameter> parameters = new HashMap<>();
+                List<PParameter> parameterList = new ArrayList<>();
+                for (var parameter : dnfQuery.getSymbolicParameters()) {
+                        var direction = switch (parameter.getDirection()) {
+                                case OUT -> PParameterDirection.INOUT;
+                                case IN -> throw new IllegalArgumentException("Query %s with input parameter %s is not supported"
+                                                .formatted(dnfQuery, parameter.getVariable()));
+                        };
+                        var pParameter = new PParameter(parameter.getVariable().getUniqueName(), null, null, direction);
+                        parameters.put(parameter, pParameter);
+                        parameterList.add(pParameter);
+                }
+
+                pQuery.setParameters(parameterList);
+
+                for (var functionalDependency : dnfQuery.getFunctionalDependencies()) {
+                        var functionalDependencyAnnotation = new PAnnotation("FunctionalDependency");
+                        for (var forEachVariable : functionalDependency.forEach()) {
+                                functionalDependencyAnnotation.addAttribute("forEach", forEachVariable.getUniqueName());
+                        }
+                        for (var uniqueVariable : functionalDependency.unique()) {
+                                functionalDependencyAnnotation.addAttribute("unique", uniqueVariable.getUniqueName());
+                        }
+                        pQuery.addAnnotation(functionalDependencyAnnotation);
+                }
+
+                for (DnfClause clause : dnfQuery.getClauses()) {
+                        PBody body = new PBody(pQuery);
+                        List<ExportedParameter> parameterExports = new ArrayList<>();
+                        for (var parameter : dnfQuery.getSymbolicParameters()) {
+                                PVariable pVar = body.getOrCreateVariableByName(parameter.getVariable().getUniqueName());
+                                parameterExports.add(new ExportedParameter(body, pVar, parameters.get(parameter)));
+                        }
+                        body.setSymbolicParameters(parameterExports);
+                        pQuery.addBody(body);
+                        for (Literal literal : clause.literals()) {
+                                translateLiteral(literal, body);
+                        }
+                }
+
+                return pQuery;
+        }
+
+        private void translateLiteral(Literal literal, PBody body) {
+                if (literal instanceof EquivalenceLiteral equivalenceLiteral) {
+                        translateEquivalenceLiteral(equivalenceLiteral, body);
+                } else if (literal instanceof CallLiteral callLiteral) {
+                        translateCallLiteral(callLiteral, body);
+                } else if (literal instanceof ConstantLiteral constantLiteral) {
+                        translateConstantLiteral(constantLiteral, body);
+                } else if (literal instanceof AssignLiteral<?> assignLiteral) {
+                        translateAssignLiteral(assignLiteral, body);
+                } else if (literal instanceof CheckLiteral checkLiteral) {
+                        translateCheckLiteral(checkLiteral, body);
+                } else if (literal instanceof CountLiteral countLiteral) {
+                        translateCountLiteral(countLiteral, body);
+                } else if (literal instanceof AggregationLiteral<?, ?> aggregationLiteral) {
+                        translateAggregationLiteral(aggregationLiteral, body);
+                } else if (literal instanceof RepresentativeElectionLiteral representativeElectionLiteral) {
+                        translateRepresentativeElectionLiteral(representativeElectionLiteral, body);
+                } else {
+                        throw new IllegalArgumentException("Unknown literal: " + literal.toString());
+                }
+        }
+
+        private void translateEquivalenceLiteral(EquivalenceLiteral equivalenceLiteral, PBody body) {
+                PVariable varSource = body.getOrCreateVariableByName(equivalenceLiteral.getLeft().getUniqueName());
+                PVariable varTarget = body.getOrCreateVariableByName(equivalenceLiteral.getRight().getUniqueName());
+                if (equivalenceLiteral.isPositive()) {
+                        new Equality(body, varSource, varTarget);
+                } else {
+                        new Inequality(body, varSource, varTarget);
+                }
+        }
+
+        private void translateCallLiteral(CallLiteral callLiteral, PBody body) {
+                var polarity = callLiteral.getPolarity();
+                switch (polarity) {
+                case POSITIVE -> {
+                        var substitution = translateSubstitution(callLiteral.getArguments(), body);
+                        var constraint = callLiteral.getTarget();
+                        if (constraint instanceof Dnf dnf) {
+                                var pattern = translate(dnf);
+                                new PositivePatternCall(body, substitution, pattern);
+                        } else if (constraint instanceof AnySymbolView symbolView) {
+                                var inputKey = wrapperFactory.getInputKey(symbolView);
+                                new TypeConstraint(body, substitution, inputKey);
+                        } else {
+                                throw new IllegalArgumentException("Unknown Constraint: " + constraint);
+                        }
+                }
+                case TRANSITIVE -> {
+                        var substitution = translateSubstitution(callLiteral.getArguments(), body);
+                        var pattern = wrapConstraintWithIdentityArguments(callLiteral.getTarget());
+                        new BinaryTransitiveClosure(body, substitution, pattern);
+                }
+                case NEGATIVE -> {
+                        var wrappedCall = wrapperFactory.maybeWrapConstraint(callLiteral);
+                        var substitution = translateSubstitution(wrappedCall.remappedArguments(), body);
+                        var pattern = wrappedCall.pattern();
+                        new NegativePatternCall(body, substitution, pattern);
+                }
+                default -> throw new IllegalArgumentException("Unknown polarity: " + polarity);
+                }
+        }
+
+        private PQuery wrapConstraintWithIdentityArguments(Constraint constraint) {
+                if (constraint instanceof Dnf dnf) {
+                        return translate(dnf);
+                } else if (constraint instanceof AnySymbolView symbolView) {
+                        return wrapperFactory.wrapSymbolViewIdentityArguments(symbolView);
+                } else {
+                        throw new IllegalArgumentException("Unknown Constraint: " + constraint);
+                }
+        }
+
+        private static Tuple translateSubstitution(List<Variable> substitution, PBody body) {
+                int arity = substitution.size();
+                Object[] variables = new Object[arity];
+                for (int i = 0; i < arity; i++) {
+                        var variable = substitution.get(i);
+                        variables[i] = body.getOrCreateVariableByName(variable.getUniqueName());
+                }
+                return Tuples.flatTupleOf(variables);
+        }
+
+        private void translateConstantLiteral(ConstantLiteral constantLiteral, PBody body) {
+                var variable = body.getOrCreateVariableByName(constantLiteral.getVariable().getUniqueName());
+                new ConstantValue(body, variable, tools.refinery.store.tuple.Tuple.of(constantLiteral.getNodeId()));
+        }
+
+        private <T> void translateAssignLiteral(AssignLiteral<T> assignLiteral, PBody body) {
+                var variable = body.getOrCreateVariableByName(assignLiteral.getVariable().getUniqueName());
+                var term = assignLiteral.getTerm();
+                if (term instanceof ConstantTerm<T> constantTerm) {
+                        new ConstantValue(body, variable, constantTerm.getValue());
+                } else {
+                        var evaluator = new TermEvaluator<>(term);
+                        new ExpressionEvaluation(body, evaluator, variable);
+                }
+        }
+
+        private void translateCheckLiteral(CheckLiteral checkLiteral, PBody body) {
+                var evaluator = new CheckEvaluator(checkLiteral.getTerm());
+                new ExpressionEvaluation(body, evaluator, null);
+        }
+
+        private void translateCountLiteral(CountLiteral countLiteral, PBody body) {
+                var wrappedCall = wrapperFactory.maybeWrapConstraint(countLiteral);
+                var substitution = translateSubstitution(wrappedCall.remappedArguments(), body);
+                var resultVariable = body.getOrCreateVariableByName(countLiteral.getResultVariable().getUniqueName());
+                new PatternMatchCounter(body, substitution, wrappedCall.pattern(), resultVariable);
+        }
+
+        private <R, T> void translateAggregationLiteral(AggregationLiteral<R, T> aggregationLiteral, PBody body) {
+                var aggregator = aggregationLiteral.getAggregator();
+                IMultisetAggregationOperator<T, ?, R> aggregationOperator;
+                if (aggregator instanceof StatelessAggregator<R, T> statelessAggregator) {
+                        aggregationOperator = new StatelessMultisetAggregator<>(statelessAggregator);
+                } else if (aggregator instanceof StatefulAggregator<R, T> statefulAggregator) {
+                        aggregationOperator = new StatefulMultisetAggregator<>(statefulAggregator);
+                } else {
+                        throw new IllegalArgumentException("Unknown aggregator: " + aggregator);
+                }
+                var wrappedCall = wrapperFactory.maybeWrapConstraint(aggregationLiteral);
+                var substitution = translateSubstitution(wrappedCall.remappedArguments(), body);
+                var inputVariable = body.getOrCreateVariableByName(aggregationLiteral.getInputVariable().getUniqueName());
+                var aggregatedColumn = substitution.invertIndex().get(inputVariable);
+                if (aggregatedColumn == null) {
+                        throw new IllegalStateException("Input variable %s not found in substitution %s".formatted(inputVariable,
+                                        substitution));
+                }
+                var boundAggregator = new BoundAggregator(aggregationOperator, aggregator.getInputType(),
+                                aggregator.getResultType());
+                var resultVariable = body.getOrCreateVariableByName(aggregationLiteral.getResultVariable().getUniqueName());
+                new AggregatorConstraint(boundAggregator, body, substitution, wrappedCall.pattern(), resultVariable,
+                                aggregatedColumn);
+        }
+
+        private void translateRepresentativeElectionLiteral(RepresentativeElectionLiteral literal, PBody body) {
+                var substitution = translateSubstitution(literal.getArguments(), body);
+                var pattern = wrapConstraintWithIdentityArguments(literal.getTarget());
+                var connectivity = switch (literal.getConnectivity()) {
+                        case WEAK -> Connectivity.WEAK;
+                        case STRONG -> Connectivity.STRONG;
+                };
+                new RepresentativeElectionConstraint(body, substitution, pattern, connectivity);
+        }
+}
diff --git a/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/pquery/QueryWrapperFactory.java b/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/pquery/QueryWrapperFactory.java
new file mode 100644
index 00000000..a710dab3
--- /dev/null
+++ b/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/pquery/QueryWrapperFactory.java
@@ -0,0 +1,189 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.interpreter.internal.pquery;
+
+import tools.refinery.interpreter.matchers.context.IInputKey;
+import tools.refinery.interpreter.matchers.psystem.PBody;
+import tools.refinery.interpreter.matchers.psystem.PVariable;
+import tools.refinery.interpreter.matchers.psystem.basicdeferred.ExportedParameter;
+import tools.refinery.interpreter.matchers.psystem.basicenumerables.PositivePatternCall;
+import tools.refinery.interpreter.matchers.psystem.basicenumerables.TypeConstraint;
+import tools.refinery.interpreter.matchers.psystem.queries.PParameter;
+import tools.refinery.interpreter.matchers.psystem.queries.PQuery;
+import tools.refinery.interpreter.matchers.psystem.queries.PVisibility;
+import tools.refinery.interpreter.matchers.tuple.Tuple;
+import tools.refinery.interpreter.matchers.tuple.Tuples;
+import tools.refinery.store.query.Constraint;
+import tools.refinery.store.query.dnf.Dnf;
+import tools.refinery.store.query.dnf.DnfUtils;
+import tools.refinery.store.query.literal.AbstractCallLiteral;
+import tools.refinery.store.query.term.ParameterDirection;
+import tools.refinery.store.query.term.Variable;
+import tools.refinery.store.query.view.AnySymbolView;
+import tools.refinery.store.query.view.SymbolView;
+import tools.refinery.store.util.CycleDetectingMapper;
+
+import java.util.*;
+import java.util.function.ToIntFunction;
+
+class QueryWrapperFactory {
+        private final Dnf2PQuery dnf2PQuery;
+        private final Map<AnySymbolView, SymbolViewWrapper> view2WrapperMap = new LinkedHashMap<>();
+        private final CycleDetectingMapper<RemappedConstraint, RawPQuery> wrapConstraint = new CycleDetectingMapper<>(
+                        this::doWrapConstraint);
+
+        QueryWrapperFactory(Dnf2PQuery dnf2PQuery) {
+                this.dnf2PQuery = dnf2PQuery;
+        }
+
+        public PQuery wrapSymbolViewIdentityArguments(AnySymbolView symbolView) {
+                var identity = new int[symbolView.arity()];
+                for (int i = 0; i < identity.length; i++) {
+                        identity[i] = i;
+                }
+                return maybeWrapConstraint(symbolView, identity);
+        }
+
+        public WrappedCall maybeWrapConstraint(AbstractCallLiteral callLiteral) {
+                var arguments = callLiteral.getArguments();
+                int arity = arguments.size();
+                var remappedParameters = new int[arity];
+                var unboundVariableIndices = new HashMap<Variable, Integer>();
+                var appendVariable = new VariableAppender();
+                for (int i = 0; i < arity; i++) {
+                        var variable = arguments.get(i);
+                        // Unify all variables to avoid Refinery Interpreter bugs, even if they're bound in the containing clause.
+                        remappedParameters[i] = unboundVariableIndices.computeIfAbsent(variable, appendVariable::applyAsInt);
+                }
+                var pattern = maybeWrapConstraint(callLiteral.getTarget(), remappedParameters);
+                return new WrappedCall(pattern, appendVariable.getRemappedArguments());
+        }
+
+        private PQuery maybeWrapConstraint(Constraint constraint, int[] remappedParameters) {
+                if (remappedParameters.length != constraint.arity()) {
+                        throw new IllegalArgumentException("Constraint %s expected %d parameters, but got %d parameters".formatted(
+                                        constraint, constraint.arity(), remappedParameters.length));
+                }
+                if (constraint instanceof Dnf dnf && isIdentity(remappedParameters)) {
+                        return dnf2PQuery.translate(dnf);
+                }
+                return wrapConstraint.map(new RemappedConstraint(constraint, remappedParameters));
+        }
+
+        private static boolean isIdentity(int[] remappedParameters) {
+                for (int i = 0; i < remappedParameters.length; i++) {
+                        if (remappedParameters[i] != i) {
+                                return false;
+                        }
+                }
+                return true;
+        }
+
+        private RawPQuery doWrapConstraint(RemappedConstraint remappedConstraint) {
+                var constraint = remappedConstraint.constraint();
+                var remappedParameters = remappedConstraint.remappedParameters();
+
+                checkNoInputParameters(constraint);
+
+                var embeddedPQuery = new RawPQuery(DnfUtils.generateUniqueName(constraint.name()), PVisibility.EMBEDDED);
+                var body = new PBody(embeddedPQuery);
+                int arity = Arrays.stream(remappedParameters).max().orElse(-1) + 1;
+                var parameters = new ArrayList<PParameter>(arity);
+                var parameterVariables = new PVariable[arity];
+                var symbolicParameters = new ArrayList<ExportedParameter>(arity);
+                for (int i = 0; i < arity; i++) {
+                        var parameterName = "p" + i;
+                        var parameter = new PParameter(parameterName);
+                        parameters.add(parameter);
+                        var variable = body.getOrCreateVariableByName(parameterName);
+                        parameterVariables[i] = variable;
+                        symbolicParameters.add(new ExportedParameter(body, variable, parameter));
+                }
+                embeddedPQuery.setParameters(parameters);
+                body.setSymbolicParameters(symbolicParameters);
+
+                var arguments = new Object[remappedParameters.length];
+                for (int i = 0; i < remappedParameters.length; i++) {
+                        arguments[i] = parameterVariables[remappedParameters[i]];
+                }
+                var argumentTuple = Tuples.flatTupleOf(arguments);
+
+                addPositiveConstraint(constraint, body, argumentTuple);
+                embeddedPQuery.addBody(body);
+                return embeddedPQuery;
+        }
+
+        private static void checkNoInputParameters(Constraint constraint) {
+                for (var constraintParameter : constraint.getParameters()) {
+                        if (constraintParameter.getDirection() == ParameterDirection.IN) {
+                                throw new IllegalArgumentException("Input parameter %s of %s is not supported"
+                                                .formatted(constraintParameter, constraint));
+                        }
+                }
+        }
+
+        private void addPositiveConstraint(Constraint constraint, PBody body, Tuple argumentTuple) {
+                if (constraint instanceof SymbolView<?> view) {
+                        new TypeConstraint(body, argumentTuple, getInputKey(view));
+                } else if (constraint instanceof Dnf dnf) {
+                        var calledPQuery = dnf2PQuery.translate(dnf);
+                        new PositivePatternCall(body, argumentTuple, calledPQuery);
+                } else {
+                        throw new IllegalArgumentException("Unknown Constraint: " + constraint);
+                }
+        }
+
+        public IInputKey getInputKey(AnySymbolView symbolView) {
+                return view2WrapperMap.computeIfAbsent(symbolView, SymbolViewWrapper::new);
+        }
+
+        public Map<AnySymbolView, IInputKey> getSymbolViews() {
+                return Collections.unmodifiableMap(view2WrapperMap);
+        }
+
+        public record WrappedCall(PQuery pattern, List<Variable> remappedArguments) {
+        }
+
+        private static class VariableAppender implements ToIntFunction<Variable> {
+                private final List<Variable> remappedArguments = new ArrayList<>();
+                private int nextIndex = 0;
+
+                @Override
+                public int applyAsInt(Variable variable) {
+                        remappedArguments.add(variable);
+                        int index = nextIndex;
+                        nextIndex++;
+                        return index;
+                }
+
+                public List<Variable> getRemappedArguments() {
+                        return remappedArguments;
+                }
+        }
+
+        private record RemappedConstraint(Constraint constraint, int[] remappedParameters) {
+                @Override
+                public boolean equals(Object o) {
+                        if (this == o) return true;
+                        if (o == null || getClass() != o.getClass()) return false;
+                        RemappedConstraint that = (RemappedConstraint) o;
+                        return constraint.equals(that.constraint) && Arrays.equals(remappedParameters, that.remappedParameters);
+                }
+
+                @Override
+                public int hashCode() {
+                        int result = Objects.hash(constraint);
+                        result = 31 * result + Arrays.hashCode(remappedParameters);
+                        return result;
+                }
+
+                @Override
+                public String toString() {
+                        return "RemappedConstraint{constraint=%s, remappedParameters=%s}".formatted(constraint,
+                                        Arrays.toString(remappedParameters));
+                }
+        }
+}
diff --git a/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/pquery/RawPQuery.java b/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/pquery/RawPQuery.java
new file mode 100644
index 00000000..bbb35f91
--- /dev/null
+++ b/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/pquery/RawPQuery.java
@@ -0,0 +1,87 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.interpreter.internal.pquery;
+
+import tools.refinery.interpreter.api.GenericQuerySpecification;
+import tools.refinery.interpreter.api.InterpreterEngine;
+import tools.refinery.interpreter.api.scope.QueryScope;
+import tools.refinery.interpreter.matchers.psystem.PBody;
+import tools.refinery.interpreter.matchers.psystem.annotations.PAnnotation;
+import tools.refinery.interpreter.matchers.psystem.queries.BasePQuery;
+import tools.refinery.interpreter.matchers.psystem.queries.PParameter;
+import tools.refinery.interpreter.matchers.psystem.queries.PVisibility;
+import tools.refinery.store.query.interpreter.internal.RelationalScope;
+import tools.refinery.store.query.interpreter.internal.matcher.RawPatternMatcher;
+
+import java.util.LinkedHashSet;
+import java.util.List;
+import java.util.Set;
+
+public class RawPQuery extends BasePQuery {
+        private final String fullyQualifiedName;
+        private List<PParameter> parameters;
+        private final LinkedHashSet<PBody> bodies = new LinkedHashSet<>();
+
+        public RawPQuery(String name, PVisibility visibility) {
+                super(visibility);
+                fullyQualifiedName = name;
+        }
+
+        public RawPQuery(String name) {
+                this(name, PVisibility.PUBLIC);
+        }
+
+        @Override
+        public String getFullyQualifiedName() {
+                return fullyQualifiedName;
+        }
+
+        public void setParameters(List<PParameter> parameters) {
+                this.parameters = parameters;
+        }
+
+        @Override
+        public void addAnnotation(PAnnotation annotation) {
+                super.addAnnotation(annotation);
+        }
+
+        @Override
+        public List<PParameter> getParameters() {
+                return parameters;
+        }
+
+        public void addBody(PBody body) {
+                bodies.add(body);
+        }
+
+        @Override
+        protected Set<PBody> doGetContainedBodies() {
+                return bodies;
+        }
+
+        public GenericQuerySpecification<RawPatternMatcher> build() {
+                return new GenericQuerySpecification<>(this) {
+                        @Override
+                        public Class<? extends QueryScope> getPreferredScopeClass() {
+                                return RelationalScope.class;
+                        }
+
+                        @Override
+                        protected RawPatternMatcher instantiate(InterpreterEngine engine) {
+                                RawPatternMatcher matcher = engine.getExistingMatcher(this);
+                                if (matcher == null) {
+                                        matcher = engine.getMatcher(this);
+                                }
+                                return matcher;
+                        }
+
+                        @Override
+                        public RawPatternMatcher instantiate() {
+                                return new RawPatternMatcher(this);
+                        }
+                };
+        }
+}
diff --git a/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/pquery/StatefulMultisetAggregator.java b/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/pquery/StatefulMultisetAggregator.java
new file mode 100644
index 00000000..7552117b
--- /dev/null
+++ b/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/pquery/StatefulMultisetAggregator.java
@@ -0,0 +1,65 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.interpreter.internal.pquery;
+
+import tools.refinery.interpreter.matchers.psystem.aggregations.IMultisetAggregationOperator;
+import tools.refinery.store.query.term.StatefulAggregate;
+import tools.refinery.store.query.term.StatefulAggregator;
+
+import java.util.stream.Stream;
+
+record StatefulMultisetAggregator<R, T>(StatefulAggregator<R, T> aggregator)
+        implements IMultisetAggregationOperator<T, StatefulAggregate<R, T>, R> {
+        @Override
+        public String getShortDescription() {
+                return getName();
+        }
+
+        @Override
+        public String getName() {
+                return aggregator.toString();
+        }
+
+        @Override
+        public StatefulAggregate<R, T> createNeutral() {
+                return aggregator.createEmptyAggregate();
+        }
+
+        @Override
+        public boolean isNeutral(StatefulAggregate<R, T> result) {
+                return result.isEmpty();
+        }
+
+        @Override
+        public StatefulAggregate<R, T> update(StatefulAggregate<R, T> oldResult, T updateValue, boolean isInsertion) {
+                if (isInsertion) {
+                        oldResult.add(updateValue);
+                } else {
+                        oldResult.remove(updateValue);
+                }
+                return oldResult;
+        }
+
+        @Override
+        public R getAggregate(StatefulAggregate<R, T> result) {
+                return result.getResult();
+        }
+
+        @Override
+        public R aggregateStream(Stream<T> stream) {
+                return aggregator.aggregateStream(stream);
+        }
+
+        @Override
+        public StatefulAggregate<R, T> clone(StatefulAggregate<R, T> original) {
+                return original.deepCopy();
+        }
+
+        @Override
+        public boolean contains(T value, StatefulAggregate<R, T> accumulator) {
+                return accumulator.contains(value);
+        }
+}
diff --git a/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/pquery/StatelessMultisetAggregator.java b/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/pquery/StatelessMultisetAggregator.java
new file mode 100644
index 00000000..2da7ba87
--- /dev/null
+++ b/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/pquery/StatelessMultisetAggregator.java
@@ -0,0 +1,55 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.interpreter.internal.pquery;
+
+import tools.refinery.interpreter.matchers.psystem.aggregations.IMultisetAggregationOperator;
+import tools.refinery.store.query.term.StatelessAggregator;
+
+import java.util.stream.Stream;
+
+record StatelessMultisetAggregator<R, T>(StatelessAggregator<R, T> aggregator)
+                implements IMultisetAggregationOperator<T, R, R> {
+        @Override
+        public String getShortDescription() {
+                return getName();
+        }
+
+        @Override
+        public String getName() {
+                return aggregator.toString();
+        }
+
+        @Override
+        public R createNeutral() {
+                return aggregator.getEmptyResult();
+        }
+
+        @Override
+        public boolean isNeutral(R result) {
+                return createNeutral().equals(result);
+        }
+
+        @Override
+        public R update(R oldResult, T updateValue, boolean isInsertion) {
+                return isInsertion ? aggregator.add(oldResult, updateValue) : aggregator.remove(oldResult, updateValue);
+        }
+
+        @Override
+        public R getAggregate(R result) {
+                return result;
+        }
+
+        @Override
+        public R clone(R original) {
+                // Aggregate result is immutable.
+                return original;
+        }
+
+        @Override
+        public R aggregateStream(Stream<T> stream) {
+                return aggregator.aggregateStream(stream);
+        }
+}
diff --git a/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/pquery/SymbolViewWrapper.java b/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/pquery/SymbolViewWrapper.java
new file mode 100644
index 00000000..51795f4a
--- /dev/null
+++ b/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/pquery/SymbolViewWrapper.java
@@ -0,0 +1,40 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.interpreter.internal.pquery;
+
+import tools.refinery.interpreter.matchers.context.common.BaseInputKeyWrapper;
+import tools.refinery.store.query.view.AnySymbolView;
+
+public class SymbolViewWrapper extends BaseInputKeyWrapper<AnySymbolView> {
+        public SymbolViewWrapper(AnySymbolView wrappedKey) {
+                super(wrappedKey);
+        }
+
+        @Override
+        public String getPrettyPrintableName() {
+                return wrappedKey.name();
+        }
+
+        @Override
+        public String getStringID() {
+                return getPrettyPrintableName();
+        }
+
+        @Override
+        public int getArity() {
+                return wrappedKey.arity();
+        }
+
+        @Override
+        public boolean isEnumerable() {
+                return true;
+        }
+
+        @Override
+        public String toString() {
+                return "RelationViewWrapper{wrappedKey=%s}".formatted(wrappedKey);
+        }
+}
diff --git a/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/pquery/TermEvaluator.java b/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/pquery/TermEvaluator.java
new file mode 100644
index 00000000..ed991091
--- /dev/null
+++ b/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/pquery/TermEvaluator.java
@@ -0,0 +1,37 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.interpreter.internal.pquery;
+
+import tools.refinery.store.query.term.Term;
+import tools.refinery.store.query.term.Variable;
+import tools.refinery.interpreter.matchers.psystem.IExpressionEvaluator;
+import tools.refinery.interpreter.matchers.psystem.IValueProvider;
+
+import java.util.stream.Collectors;
+
+class TermEvaluator<T> implements IExpressionEvaluator {
+        private final Term<T> term;
+
+        public TermEvaluator(Term<T> term) {
+                this.term = term;
+        }
+
+        @Override
+        public String getShortDescription() {
+                return term.toString();
+        }
+
+        @Override
+        public Iterable<String> getInputParameterNames() {
+                return term.getInputVariables().stream().map(Variable::getUniqueName).collect(Collectors.toUnmodifiableSet());
+        }
+
+        @Override
+        public Object evaluateExpression(IValueProvider provider) {
+                var valuation = new ValueProviderBasedValuation(provider);
+                return term.evaluate(valuation);
+        }
+}
diff --git a/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/pquery/ValueProviderBasedValuation.java b/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/pquery/ValueProviderBasedValuation.java
new file mode 100644
index 00000000..4124c9bb
--- /dev/null
+++ b/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/pquery/ValueProviderBasedValuation.java
@@ -0,0 +1,19 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.interpreter.internal.pquery;
+
+import tools.refinery.interpreter.matchers.psystem.IValueProvider;
+import tools.refinery.store.query.term.DataVariable;
+import tools.refinery.store.query.valuation.Valuation;
+
+public record ValueProviderBasedValuation(IValueProvider valueProvider) implements Valuation {
+        @Override
+        public <T> T getValue(DataVariable<T> variable) {
+                @SuppressWarnings("unchecked")
+                var value = (T) valueProvider.getValue(variable.getUniqueName());
+                return value;
+        }
+}
diff --git a/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/update/ModelUpdateListener.java b/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/update/ModelUpdateListener.java
new file mode 100644
index 00000000..fad53675
--- /dev/null
+++ b/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/update/ModelUpdateListener.java
@@ -0,0 +1,51 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.interpreter.internal.update;
+
+import tools.refinery.interpreter.matchers.context.IInputKey;
+import tools.refinery.interpreter.matchers.context.IQueryRuntimeContextListener;
+import tools.refinery.interpreter.matchers.tuple.ITuple;
+import tools.refinery.store.query.interpreter.internal.QueryInterpreterAdapterImpl;
+import tools.refinery.store.query.view.AnySymbolView;
+import tools.refinery.store.query.view.SymbolView;
+
+import java.util.HashMap;
+import java.util.Map;
+
+public class ModelUpdateListener {
+        private final Map<AnySymbolView, SymbolViewUpdateListener<?>> symbolViewUpdateListeners;
+
+        public ModelUpdateListener(QueryInterpreterAdapterImpl adapter) {
+                var symbolViews = adapter.getStoreAdapter().getInputKeys().keySet();
+                symbolViewUpdateListeners = new HashMap<>(symbolViews.size());
+                for (var symbolView : symbolViews) {
+                        registerView(adapter, (SymbolView<?>) symbolView);
+                }
+        }
+
+        private <T> void registerView(QueryInterpreterAdapterImpl adapter, SymbolView<T> view) {
+                var model = adapter.getModel();
+                var interpretation = model.getInterpretation(view.getSymbol());
+                var listener = SymbolViewUpdateListener.of(adapter, view, interpretation);
+                symbolViewUpdateListeners.put(view, listener);
+        }
+
+        public boolean containsSymbolView(AnySymbolView relationView) {
+                return symbolViewUpdateListeners.containsKey(relationView);
+        }
+
+        public void addListener(IInputKey key, AnySymbolView symbolView, ITuple seed,
+                                                        IQueryRuntimeContextListener listener) {
+                var symbolViewUpdateListener = symbolViewUpdateListeners.get(symbolView);
+                symbolViewUpdateListener.addFilter(key, seed, listener);
+        }
+
+        public void removeListener(IInputKey key, AnySymbolView symbolView, ITuple seed,
+                                                           IQueryRuntimeContextListener listener) {
+                var symbolViewUpdateListener = symbolViewUpdateListeners.get(symbolView);
+                symbolViewUpdateListener.removeFilter(key, seed, listener);
+        }
+}
diff --git a/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/update/RelationViewFilter.java b/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/update/RelationViewFilter.java
new file mode 100644
index 00000000..4b4c73eb
--- /dev/null
+++ b/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/update/RelationViewFilter.java
@@ -0,0 +1,71 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.interpreter.internal.update;
+
+import tools.refinery.interpreter.matchers.context.IInputKey;
+import tools.refinery.interpreter.matchers.context.IQueryRuntimeContextListener;
+import tools.refinery.interpreter.matchers.tuple.ITuple;
+import tools.refinery.interpreter.matchers.tuple.Tuple;
+
+import java.util.Arrays;
+import java.util.Objects;
+
+public final class RelationViewFilter {
+        private final IInputKey inputKey;
+        private final Object[] seed;
+        private final IQueryRuntimeContextListener listener;
+
+        public RelationViewFilter(IInputKey inputKey, ITuple seed, IQueryRuntimeContextListener listener) {
+                this.inputKey = inputKey;
+                this.seed = seedToArray(seed);
+                this.listener = listener;
+        }
+
+        public void update(Tuple updateTuple, boolean isInsertion) {
+                if (isMatching(updateTuple)) {
+                        listener.update(inputKey, updateTuple, isInsertion);
+                }
+        }
+
+        private boolean isMatching(ITuple tuple) {
+                if (seed == null) {
+                        return true;
+                }
+                int size = seed.length;
+                for (int i = 0; i < size; i++) {
+                        var filterElement = seed[i];
+                        if (filterElement != null && !filterElement.equals(tuple.get(i))) {
+                                return false;
+                        }
+                }
+                return true;
+        }
+
+        // Use <code>null</code> instead of an empty array to speed up comparisons.
+        @SuppressWarnings("squid:S1168")
+        private static Object[] seedToArray(ITuple seed) {
+                for (var element : seed.getElements()) {
+                        if (element != null) {
+                                return seed.getElements();
+                        }
+                }
+                return null;
+        }
+
+        @Override
+        public boolean equals(Object obj) {
+                if (obj == this) return true;
+                if (obj == null || obj.getClass() != this.getClass()) return false;
+                var that = (RelationViewFilter) obj;
+                return Objects.equals(this.inputKey, that.inputKey) && Arrays.equals(this.seed, that.seed) &&
+                                Objects.equals(this.listener, that.listener);
+        }
+
+        @Override
+        public int hashCode() {
+                return Objects.hash(inputKey, Arrays.hashCode(seed), listener);
+        }
+}
diff --git a/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/update/SymbolViewUpdateListener.java b/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/update/SymbolViewUpdateListener.java
new file mode 100644
index 00000000..68020b11
--- /dev/null
+++ b/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/update/SymbolViewUpdateListener.java
@@ -0,0 +1,65 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.interpreter.internal.update;
+
+import tools.refinery.interpreter.matchers.context.IInputKey;
+import tools.refinery.interpreter.matchers.context.IQueryRuntimeContextListener;
+import tools.refinery.interpreter.matchers.tuple.ITuple;
+import tools.refinery.interpreter.matchers.tuple.Tuple;
+import tools.refinery.store.model.Interpretation;
+import tools.refinery.store.model.InterpretationListener;
+import tools.refinery.store.query.interpreter.internal.QueryInterpreterAdapterImpl;
+import tools.refinery.store.query.view.SymbolView;
+import tools.refinery.store.query.view.TuplePreservingView;
+
+import java.util.ArrayList;
+import java.util.List;
+
+public abstract class SymbolViewUpdateListener<T> implements InterpretationListener<T> {
+        private final QueryInterpreterAdapterImpl adapter;
+        private final Interpretation<T> interpretation;
+        private final List<RelationViewFilter> filters = new ArrayList<>();
+
+        protected SymbolViewUpdateListener(QueryInterpreterAdapterImpl adapter, Interpretation<T> interpretation) {
+                this.adapter = adapter;
+                this.interpretation = interpretation;
+        }
+
+        public void addFilter(IInputKey inputKey, ITuple seed, IQueryRuntimeContextListener listener) {
+                if (filters.isEmpty()) {
+                        // First filter to be added, from now on we have to subscribe to model updates.
+                        interpretation.addListener(this, true);
+                }
+                filters.add(new RelationViewFilter(inputKey, seed, listener));
+        }
+
+        public void removeFilter(IInputKey inputKey, ITuple seed, IQueryRuntimeContextListener listener) {
+                if (filters.remove(new RelationViewFilter(inputKey, seed, listener)) && filters.isEmpty()) {
+                        // Last listener to be added, we don't have be subscribed to model updates anymore.
+                        interpretation.removeListener(this);
+                }
+        }
+
+        protected void processUpdate(Tuple tuple, boolean isInsertion) {
+                adapter.markAsPending();
+                int size = filters.size();
+                // Use a for loop instead of a for-each loop to avoid <code>Iterator</code> allocation overhead.
+                //noinspection ForLoopReplaceableByForEach
+                for (int i = 0; i < size; i++) {
+                        filters.get(i).update(tuple, isInsertion);
+                }
+        }
+
+        public static <T> SymbolViewUpdateListener<T> of(QueryInterpreterAdapterImpl adapter,
+                                                     SymbolView<T> view,
+                                                     Interpretation<T> interpretation) {
+                if (view instanceof TuplePreservingView<T> tuplePreservingRelationView) {
+                        return new TuplePreservingViewUpdateListener<>(adapter, tuplePreservingRelationView,
+                                        interpretation);
+                }
+                return new TupleChangingViewUpdateListener<>(adapter, view, interpretation);
+        }
+}
diff --git a/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/update/TupleChangingViewUpdateListener.java b/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/update/TupleChangingViewUpdateListener.java
new file mode 100644
index 00000000..13b4af80
--- /dev/null
+++ b/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/update/TupleChangingViewUpdateListener.java
@@ -0,0 +1,45 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.interpreter.internal.update;
+
+import tools.refinery.store.model.Interpretation;
+import tools.refinery.store.query.interpreter.internal.QueryInterpreterAdapterImpl;
+import tools.refinery.store.query.view.SymbolView;
+import tools.refinery.store.tuple.Tuple;
+import tools.refinery.interpreter.matchers.tuple.Tuples;
+
+import java.util.Arrays;
+
+public class TupleChangingViewUpdateListener<T> extends SymbolViewUpdateListener<T> {
+        private final SymbolView<T> view;
+
+        TupleChangingViewUpdateListener(QueryInterpreterAdapterImpl adapter, SymbolView<T> view,
+                                    Interpretation<T> interpretation) {
+        super(adapter, interpretation);
+        this.view = view;
+        }
+
+        @Override
+        public void put(Tuple key, T fromValue, T toValue, boolean restoring) {
+                boolean fromPresent = view.filter(key, fromValue);
+                boolean toPresent = view.filter(key, toValue);
+                if (fromPresent) {
+                        var fromArray = view.forwardMap(key, fromValue);
+                        if (toPresent) { // value change
+                                var toArray = view.forwardMap(key, toValue);
+                                if (!Arrays.equals(fromArray, toArray)) {
+                                        processUpdate(Tuples.flatTupleOf(fromArray), false);
+                                        processUpdate(Tuples.flatTupleOf(toArray), true);
+                                }
+                        } else { // fromValue disappears
+                                processUpdate(Tuples.flatTupleOf(fromArray), false);
+                        }
+                } else if (toPresent) { // toValue appears
+                        var toArray = view.forwardMap(key, toValue);
+                        processUpdate(Tuples.flatTupleOf(toArray), true);
+                }
+        }
+}
diff --git a/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/update/TuplePreservingViewUpdateListener.java b/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/update/TuplePreservingViewUpdateListener.java
new file mode 100644
index 00000000..c9f69145
--- /dev/null
+++ b/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/update/TuplePreservingViewUpdateListener.java
@@ -0,0 +1,33 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.interpreter.internal.update;
+
+import tools.refinery.interpreter.matchers.tuple.Tuples;
+import tools.refinery.store.model.Interpretation;
+import tools.refinery.store.query.interpreter.internal.QueryInterpreterAdapterImpl;
+import tools.refinery.store.query.view.TuplePreservingView;
+import tools.refinery.store.tuple.Tuple;
+
+public class TuplePreservingViewUpdateListener<T> extends SymbolViewUpdateListener<T> {
+        private final TuplePreservingView<T> view;
+
+        TuplePreservingViewUpdateListener(QueryInterpreterAdapterImpl adapter, TuplePreservingView<T> view,
+                                      Interpretation<T> interpretation) {
+        super(adapter, interpretation);
+        this.view = view;
+        }
+
+        @Override
+        public void put(Tuple key, T fromValue, T toValue, boolean restoring) {
+                boolean fromPresent = view.filter(key, fromValue);
+                boolean toPresent = view.filter(key, toValue);
+                if (fromPresent == toPresent) {
+                        return;
+                }
+                var translated = Tuples.flatTupleOf(view.forwardMap(key));
+                processUpdate(translated, toPresent);
+        }
+}
diff --git a/subprojects/store-query-interpreter/src/test/java/tools/refinery/store/query/interpreter/DiagonalQueryTest.java b/subprojects/store-query-interpreter/src/test/java/tools/refinery/store/query/interpreter/DiagonalQueryTest.java
new file mode 100644
index 00000000..76de8679
--- /dev/null
+++ b/subprojects/store-query-interpreter/src/test/java/tools/refinery/store/query/interpreter/DiagonalQueryTest.java
@@ -0,0 +1,391 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.interpreter;
+
+import tools.refinery.interpreter.matchers.backend.QueryEvaluationHint;
+import tools.refinery.store.model.ModelStore;
+import tools.refinery.store.query.ModelQueryAdapter;
+import tools.refinery.store.query.dnf.Dnf;
+import tools.refinery.store.query.dnf.Query;
+import tools.refinery.store.query.interpreter.tests.QueryEngineTest;
+import tools.refinery.store.query.view.AnySymbolView;
+import tools.refinery.store.query.view.FunctionView;
+import tools.refinery.store.query.view.KeyOnlyView;
+import tools.refinery.store.representation.Symbol;
+import tools.refinery.store.tuple.Tuple;
+
+import java.util.List;
+import java.util.Map;
+import java.util.Optional;
+
+import static tools.refinery.store.query.literal.Literals.not;
+import static tools.refinery.store.query.term.int_.IntTerms.INT_SUM;
+import static tools.refinery.store.query.interpreter.tests.QueryAssertions.assertNullableResults;
+import static tools.refinery.store.query.interpreter.tests.QueryAssertions.assertResults;
+
+class DiagonalQueryTest {
+        private static final Symbol<Boolean> person = Symbol.of("Person", 1);
+        private static final Symbol<Boolean> friend = Symbol.of("friend", 2);
+        private static final Symbol<Boolean> symbol = Symbol.of("symbol", 4);
+        private static final Symbol<Integer> intSymbol = Symbol.of("intSymbol", 4, Integer.class);
+        private static final AnySymbolView personView = new KeyOnlyView<>(person);
+        private static final AnySymbolView friendView = new KeyOnlyView<>(friend);
+        private static final AnySymbolView symbolView = new KeyOnlyView<>(symbol);
+        private static final FunctionView<Integer> intSymbolView = new FunctionView<>(intSymbol);
+
+        @QueryEngineTest
+        void inputKeyNegationTest(QueryEvaluationHint hint) {
+                var query = Query.of("Diagonal", (builder, p1) -> builder.clause(p2 -> List.of(
+                                personView.call(p1),
+                                not(symbolView.call(p1, p1, p2, p2))
+                )));
+
+                var store = ModelStore.builder()
+                                .symbols(person, symbol)
+                                .with(QueryInterpreterAdapter.builder()
+                                                .defaultHint(hint)
+                                                .queries(query))
+                                .build();
+
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var symbolInterpretation = model.getInterpretation(symbol);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var queryResultSet = queryEngine.getResultSet(query);
+
+                personInterpretation.put(Tuple.of(0), true);
+                personInterpretation.put(Tuple.of(1), true);
+                personInterpretation.put(Tuple.of(2), true);
+
+                symbolInterpretation.put(Tuple.of(0, 0, 1, 1), true);
+                symbolInterpretation.put(Tuple.of(0, 0, 1, 2), true);
+                symbolInterpretation.put(Tuple.of(1, 1, 0, 1), true);
+                symbolInterpretation.put(Tuple.of(1, 2, 1, 1), true);
+
+                queryEngine.flushChanges();
+                assertResults(Map.of(
+                                Tuple.of(0), false,
+                                Tuple.of(1), true,
+                                Tuple.of(2), true,
+                                Tuple.of(3), false
+                ), queryResultSet);
+        }
+
+        @QueryEngineTest
+        void subQueryNegationTest(QueryEvaluationHint hint) {
+                var subQuery = Query.of("SubQuery", (builder, p1, p2, p3, p4) -> builder
+                                .clause(
+                                                personView.call(p1),
+                                                symbolView.call(p1, p2, p3, p4)
+                                )
+                                .clause(
+                                                personView.call(p2),
+                                                symbolView.call(p1, p2, p3, p4)
+                                ));
+                var query = Query.of("Diagonal", (builder, p1) -> builder.clause(p2 -> List.of(
+                                personView.call(p1),
+                                not(subQuery.call(p1, p1, p2, p2))
+                )));
+
+                var store = ModelStore.builder()
+                                .symbols(person, symbol)
+                                .with(QueryInterpreterAdapter.builder()
+                                                .defaultHint(hint)
+                                                .queries(query))
+                                .build();
+
+                var model = store.createEmptyModel();
+
+                var personInterpretation = model.getInterpretation(person);
+                var symbolInterpretation = model.getInterpretation(symbol);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var queryResultSet = queryEngine.getResultSet(query);
+
+                personInterpretation.put(Tuple.of(0), true);
+                personInterpretation.put(Tuple.of(1), true);
+                personInterpretation.put(Tuple.of(2), true);
+
+                symbolInterpretation.put(Tuple.of(0, 0, 1, 1), true);
+                symbolInterpretation.put(Tuple.of(0, 0, 1, 2), true);
+                symbolInterpretation.put(Tuple.of(1, 1, 0, 1), true);
+                symbolInterpretation.put(Tuple.of(1, 2, 1, 1), true);
+
+                queryEngine.flushChanges();
+                assertResults(Map.of(
+                                Tuple.of(0), false,
+                                Tuple.of(1), true,
+                                Tuple.of(2), true,
+                                Tuple.of(3), false
+                ), queryResultSet);
+        }
+
+        @QueryEngineTest
+        void inputKeyCountTest(QueryEvaluationHint hint) {
+                var query = Query.of("Diagonal", Integer.class, (builder, p1, output) -> builder.clause(p2 -> List.of(
+                                personView.call(p1),
+                                output.assign(symbolView.count(p1, p1, p2, p2))
+                )));
+
+                var store = ModelStore.builder()
+                                .symbols(person, symbol)
+                                .with(QueryInterpreterAdapter.builder()
+                                                .defaultHint(hint)
+                                                .queries(query))
+                                .build();
+
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var symbolInterpretation = model.getInterpretation(symbol);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var queryResultSet = queryEngine.getResultSet(query);
+
+                personInterpretation.put(Tuple.of(0), true);
+                personInterpretation.put(Tuple.of(1), true);
+                personInterpretation.put(Tuple.of(2), true);
+
+                symbolInterpretation.put(Tuple.of(0, 0, 1, 1), true);
+                symbolInterpretation.put(Tuple.of(0, 0, 2, 2), true);
+                symbolInterpretation.put(Tuple.of(0, 0, 1, 2), true);
+                symbolInterpretation.put(Tuple.of(1, 1, 0, 1), true);
+                symbolInterpretation.put(Tuple.of(1, 2, 1, 1), true);
+
+                queryEngine.flushChanges();
+                assertNullableResults(Map.of(
+                                Tuple.of(0), Optional.of(2),
+                                Tuple.of(1), Optional.of(0),
+                                Tuple.of(2), Optional.of(0),
+                                Tuple.of(3), Optional.empty()
+                ), queryResultSet);
+        }
+
+        @QueryEngineTest
+        void subQueryCountTest(QueryEvaluationHint hint) {
+                var subQuery = Query.of("SubQuery", (builder, p1, p2, p3, p4) -> builder.clause(
+                                                personView.call(p1),
+                                                symbolView.call(p1, p2, p3, p4)
+                                )
+                                .clause(
+                                                personView.call(p2),
+                                                symbolView.call(p1, p2, p3, p4)
+                                ));
+                var query = Query.of("Diagonal", Integer.class, (builder, p1, output) -> builder.clause(p2 -> List.of(
+                                personView.call(p1),
+                                output.assign(subQuery.count(p1, p1, p2, p2))
+                )));
+
+                var store = ModelStore.builder()
+                                .symbols(person, symbol)
+                                .with(QueryInterpreterAdapter.builder()
+                                                .defaultHint(hint)
+                                                .queries(query))
+                                .build();
+
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var symbolInterpretation = model.getInterpretation(symbol);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var queryResultSet = queryEngine.getResultSet(query);
+
+                personInterpretation.put(Tuple.of(0), true);
+                personInterpretation.put(Tuple.of(1), true);
+                personInterpretation.put(Tuple.of(2), true);
+
+                symbolInterpretation.put(Tuple.of(0, 0, 1, 1), true);
+                symbolInterpretation.put(Tuple.of(0, 0, 2, 2), true);
+                symbolInterpretation.put(Tuple.of(0, 0, 1, 2), true);
+                symbolInterpretation.put(Tuple.of(1, 1, 0, 1), true);
+                symbolInterpretation.put(Tuple.of(1, 2, 1, 1), true);
+
+                queryEngine.flushChanges();
+                assertNullableResults(Map.of(
+                                Tuple.of(0), Optional.of(2),
+                                Tuple.of(1), Optional.of(0),
+                                Tuple.of(2), Optional.of(0),
+                                Tuple.of(3), Optional.empty()
+                ), queryResultSet);
+        }
+
+        @QueryEngineTest
+        void inputKeyAggregationTest(QueryEvaluationHint hint) {
+                var query = Query.of("Diagonal", Integer.class, (builder, p1, output) -> builder
+                                .clause((p2) -> List.of(
+                                                personView.call(p1),
+                                                output.assign(intSymbolView.aggregate(INT_SUM, p1, p1, p2, p2))
+                                )));
+
+                var store = ModelStore.builder()
+                                .symbols(person, intSymbol)
+                                .with(QueryInterpreterAdapter.builder()
+                                                .defaultHint(hint)
+                                                .queries(query))
+                                .build();
+
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var intSymbolInterpretation = model.getInterpretation(intSymbol);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var queryResultSet = queryEngine.getResultSet(query);
+
+                personInterpretation.put(Tuple.of(0), true);
+                personInterpretation.put(Tuple.of(1), true);
+                personInterpretation.put(Tuple.of(2), true);
+
+                intSymbolInterpretation.put(Tuple.of(0, 0, 1, 1), 1);
+                intSymbolInterpretation.put(Tuple.of(0, 0, 2, 2), 2);
+                intSymbolInterpretation.put(Tuple.of(0, 0, 1, 2), 10);
+                intSymbolInterpretation.put(Tuple.of(1, 1, 0, 1), 11);
+                intSymbolInterpretation.put(Tuple.of(1, 2, 1, 1), 12);
+
+                queryEngine.flushChanges();
+                assertNullableResults(Map.of(
+                                Tuple.of(0), Optional.of(3),
+                                Tuple.of(1), Optional.of(0),
+                                Tuple.of(2), Optional.of(0),
+                                Tuple.of(3), Optional.empty()
+                ), queryResultSet);
+        }
+
+        @QueryEngineTest
+        void subQueryAggregationTest(QueryEvaluationHint hint) {
+                var subQuery = Dnf.of("SubQuery", builder -> {
+                        var p1 = builder.parameter("p1");
+                        var p2 = builder.parameter("p2");
+                        var p3 = builder.parameter("p3");
+                        var p4 = builder.parameter("p4");
+                        var x = builder.parameter("x", Integer.class);
+                        var y = builder.parameter("y", Integer.class);
+                        builder.clause(
+                                        personView.call(p1),
+                                        intSymbolView.call(p1, p2, p3, p4, x),
+                                        y.assign(x)
+                        );
+                        builder.clause(
+                                        personView.call(p2),
+                                        intSymbolView.call(p1, p2, p3, p4, x),
+                                        y.assign(x)
+                        );
+                });
+                var query = Query.of("Diagonal", Integer.class, (builder, p1, output) -> builder
+                                .clause(Integer.class, Integer.class, (p2, y, z) -> List.of(
+                                                personView.call(p1),
+                                                output.assign(subQuery.aggregateBy(y, INT_SUM, p1, p1, p2, p2, y, z))
+                                )));
+
+                var store = ModelStore.builder()
+                                .symbols(person, intSymbol)
+                                .with(QueryInterpreterAdapter.builder()
+                                                .defaultHint(hint)
+                                                .queries(query))
+                                .build();
+
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var intSymbolInterpretation = model.getInterpretation(intSymbol);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var queryResultSet = queryEngine.getResultSet(query);
+
+                personInterpretation.put(Tuple.of(0), true);
+                personInterpretation.put(Tuple.of(1), true);
+                personInterpretation.put(Tuple.of(2), true);
+
+                intSymbolInterpretation.put(Tuple.of(0, 0, 1, 1), 1);
+                intSymbolInterpretation.put(Tuple.of(0, 0, 2, 2), 2);
+                intSymbolInterpretation.put(Tuple.of(0, 0, 1, 2), 10);
+                intSymbolInterpretation.put(Tuple.of(1, 1, 0, 1), 11);
+                intSymbolInterpretation.put(Tuple.of(1, 2, 1, 1), 12);
+
+                queryEngine.flushChanges();
+                assertNullableResults(Map.of(
+                                Tuple.of(0), Optional.of(3),
+                                Tuple.of(1), Optional.of(0),
+                                Tuple.of(2), Optional.of(0),
+                                Tuple.of(3), Optional.empty()
+                ), queryResultSet);
+        }
+
+        @QueryEngineTest
+        void inputKeyTransitiveTest(QueryEvaluationHint hint) {
+                var query = Query.of("Diagonal", (builder, p1) -> builder.clause(
+                                personView.call(p1),
+                                friendView.callTransitive(p1, p1)
+                ));
+
+                var store = ModelStore.builder()
+                                .symbols(person, friend)
+                                .with(QueryInterpreterAdapter.builder()
+                                                .defaultHint(hint)
+                                                .queries(query))
+                                .build();
+
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var friendInterpretation = model.getInterpretation(friend);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var queryResultSet = queryEngine.getResultSet(query);
+
+                personInterpretation.put(Tuple.of(0), true);
+                personInterpretation.put(Tuple.of(1), true);
+                personInterpretation.put(Tuple.of(2), true);
+
+                friendInterpretation.put(Tuple.of(0, 0), true);
+                friendInterpretation.put(Tuple.of(0, 1), true);
+                friendInterpretation.put(Tuple.of(1, 2), true);
+
+                queryEngine.flushChanges();
+                assertResults(Map.of(
+                                Tuple.of(0), true,
+                                Tuple.of(1), false,
+                                Tuple.of(2), false,
+                                Tuple.of(3), false
+                ), queryResultSet);
+        }
+
+        @QueryEngineTest
+        void subQueryTransitiveTest(QueryEvaluationHint hint) {
+                var subQuery = Query.of("SubQuery", (builder, p1, p2) -> builder
+                                .clause(
+                                                personView.call(p1),
+                                                friendView.call(p1, p2)
+                                )
+                                .clause(
+                                                personView.call(p2),
+                                                friendView.call(p1, p2)
+                                ));
+                var query = Query.of("Diagonal", (builder, p1) -> builder.clause(
+                                personView.call(p1),
+                                subQuery.callTransitive(p1, p1)
+                ));
+
+                var store = ModelStore.builder()
+                                .symbols(person, friend)
+                                .with(QueryInterpreterAdapter.builder()
+                                                .defaultHint(hint)
+                                                .queries(query))
+                                .build();
+
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var friendInterpretation = model.getInterpretation(friend);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var queryResultSet = queryEngine.getResultSet(query);
+
+                personInterpretation.put(Tuple.of(0), true);
+                personInterpretation.put(Tuple.of(1), true);
+                personInterpretation.put(Tuple.of(2), true);
+
+                friendInterpretation.put(Tuple.of(0, 0), true);
+                friendInterpretation.put(Tuple.of(0, 1), true);
+                friendInterpretation.put(Tuple.of(1, 2), true);
+
+                queryEngine.flushChanges();
+                assertResults(Map.of(
+                                Tuple.of(0), true,
+                                Tuple.of(1), false,
+                                Tuple.of(2), false,
+                                Tuple.of(3), false
+                ), queryResultSet);
+        }
+}
diff --git a/subprojects/store-query-interpreter/src/test/java/tools/refinery/store/query/interpreter/FunctionalQueryTest.java b/subprojects/store-query-interpreter/src/test/java/tools/refinery/store/query/interpreter/FunctionalQueryTest.java
new file mode 100644
index 00000000..00721a34
--- /dev/null
+++ b/subprojects/store-query-interpreter/src/test/java/tools/refinery/store/query/interpreter/FunctionalQueryTest.java
@@ -0,0 +1,519 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.interpreter;
+
+import tools.refinery.interpreter.matchers.backend.QueryEvaluationHint;
+import tools.refinery.store.map.Cursor;
+import tools.refinery.store.model.ModelStore;
+import tools.refinery.store.query.ModelQueryAdapter;
+import tools.refinery.store.query.dnf.Query;
+import tools.refinery.store.query.term.Variable;
+import tools.refinery.store.query.interpreter.tests.QueryEngineTest;
+import tools.refinery.store.query.view.AnySymbolView;
+import tools.refinery.store.query.view.FilteredView;
+import tools.refinery.store.query.view.FunctionView;
+import tools.refinery.store.query.view.KeyOnlyView;
+import tools.refinery.store.representation.Symbol;
+import tools.refinery.store.representation.TruthValue;
+import tools.refinery.store.tuple.Tuple;
+
+import java.util.List;
+import java.util.Map;
+import java.util.Optional;
+
+import static org.hamcrest.MatcherAssert.assertThat;
+import static org.hamcrest.Matchers.is;
+import static org.hamcrest.Matchers.nullValue;
+import static org.junit.jupiter.api.Assertions.assertAll;
+import static org.junit.jupiter.api.Assertions.assertThrows;
+import static tools.refinery.store.query.literal.Literals.check;
+import static tools.refinery.store.query.term.int_.IntTerms.*;
+import static tools.refinery.store.query.interpreter.tests.QueryAssertions.assertNullableResults;
+import static tools.refinery.store.query.interpreter.tests.QueryAssertions.assertResults;
+
+class FunctionalQueryTest {
+        private static final Symbol<Boolean> person = Symbol.of("Person", 1);
+        private static final Symbol<Integer> age = Symbol.of("age", 1, Integer.class);
+        private static final Symbol<TruthValue> friend = Symbol.of("friend", 2, TruthValue.class, TruthValue.FALSE);
+        private static final AnySymbolView personView = new KeyOnlyView<>(person);
+        private static final FunctionView<Integer> ageView = new FunctionView<>(age);
+        private static final AnySymbolView friendMustView = new FilteredView<>(friend, "must", TruthValue::must);
+
+        @QueryEngineTest
+        void inputKeyTest(QueryEvaluationHint hint) {
+                var query = Query.of("InputKey", Integer.class, (builder, p1, output) -> builder.clause(
+                                personView.call(p1),
+                                ageView.call(p1, output)
+                ));
+
+                var store = ModelStore.builder()
+                                .symbols(person, age)
+                                .with(QueryInterpreterAdapter.builder()
+                                                .defaultHint(hint)
+                                                .queries(query))
+                                .build();
+
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var ageInterpretation = model.getInterpretation(age);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var queryResultSet = queryEngine.getResultSet(query);
+
+                personInterpretation.put(Tuple.of(0), true);
+                personInterpretation.put(Tuple.of(1), true);
+
+                ageInterpretation.put(Tuple.of(0), 12);
+                ageInterpretation.put(Tuple.of(1), 24);
+                ageInterpretation.put(Tuple.of(2), 36);
+
+                queryEngine.flushChanges();
+                assertNullableResults(Map.of(
+                                Tuple.of(0), Optional.of(12),
+                                Tuple.of(1), Optional.of(24),
+                                Tuple.of(2), Optional.empty()
+                ), queryResultSet);
+        }
+
+        @QueryEngineTest
+        void predicateTest(QueryEvaluationHint hint) {
+                var subQuery = Query.of("SubQuery", Integer.class, (builder, p1, x) -> builder.clause(
+                                personView.call(p1),
+                                ageView.call(p1, x)
+                ));
+                var query = Query.of("Predicate", Integer.class, (builder, p1, output) -> builder.clause(
+                                personView.call(p1),
+                                output.assign(subQuery.call(p1))
+                ));
+
+                var store = ModelStore.builder()
+                                .symbols(person, age)
+                                .with(QueryInterpreterAdapter.builder()
+                                                .defaultHint(hint)
+                                                .queries(query))
+                                .build();
+
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var ageInterpretation = model.getInterpretation(age);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var queryResultSet = queryEngine.getResultSet(query);
+
+                personInterpretation.put(Tuple.of(0), true);
+                personInterpretation.put(Tuple.of(1), true);
+
+                ageInterpretation.put(Tuple.of(0), 12);
+                ageInterpretation.put(Tuple.of(1), 24);
+                ageInterpretation.put(Tuple.of(2), 36);
+
+                queryEngine.flushChanges();
+                assertNullableResults(Map.of(
+                                Tuple.of(0), Optional.of(12),
+                                Tuple.of(1), Optional.of(24),
+                                Tuple.of(2), Optional.empty()
+                ), queryResultSet);
+        }
+
+        @QueryEngineTest
+        void computationTest(QueryEvaluationHint hint) {
+                var query = Query.of("Computation", Integer.class, (builder, p1, output) -> builder.clause(() -> {
+                        var x = Variable.of("x", Integer.class);
+                        return List.of(
+                                        personView.call(p1),
+                                        ageView.call(p1, x),
+                                        output.assign(mul(x, constant(7)))
+                        );
+                }));
+
+                var store = ModelStore.builder()
+                                .symbols(person, age)
+                                .with(QueryInterpreterAdapter.builder()
+                                                .defaultHint(hint)
+                                                .queries(query))
+                                .build();
+
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var ageInterpretation = model.getInterpretation(age);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var queryResultSet = queryEngine.getResultSet(query);
+
+                personInterpretation.put(Tuple.of(0), true);
+                personInterpretation.put(Tuple.of(1), true);
+
+                ageInterpretation.put(Tuple.of(0), 12);
+                ageInterpretation.put(Tuple.of(1), 24);
+
+                queryEngine.flushChanges();
+                assertNullableResults(Map.of(
+                                Tuple.of(0), Optional.of(84),
+                                Tuple.of(1), Optional.of(168),
+                                Tuple.of(2), Optional.empty()
+                ), queryResultSet);
+        }
+
+        @QueryEngineTest
+        void inputKeyCountTest(QueryEvaluationHint hint) {
+                var query = Query.of("Count", Integer.class, (builder, p1, output) -> builder.clause(
+                                personView.call(p1),
+                                output.assign(friendMustView.count(p1, Variable.of()))
+                ));
+
+                var store = ModelStore.builder()
+                                .symbols(person, friend)
+                                .with(QueryInterpreterAdapter.builder()
+                                                .defaultHint(hint)
+                                                .queries(query))
+                                .build();
+
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var friendInterpretation = model.getInterpretation(friend);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var queryResultSet = queryEngine.getResultSet(query);
+
+                personInterpretation.put(Tuple.of(0), true);
+                personInterpretation.put(Tuple.of(1), true);
+                personInterpretation.put(Tuple.of(2), true);
+
+                friendInterpretation.put(Tuple.of(0, 1), TruthValue.TRUE);
+                friendInterpretation.put(Tuple.of(1, 0), TruthValue.TRUE);
+                friendInterpretation.put(Tuple.of(1, 2), TruthValue.TRUE);
+
+                queryEngine.flushChanges();
+                assertNullableResults(Map.of(
+                                Tuple.of(0), Optional.of(1),
+                                Tuple.of(1), Optional.of(2),
+                                Tuple.of(2), Optional.of(0),
+                                Tuple.of(3), Optional.empty()
+                ), queryResultSet);
+        }
+
+        @QueryEngineTest
+        void predicateCountTest(QueryEvaluationHint hint) {
+                var subQuery = Query.of("SubQuery", (builder, p1, p2) -> builder.clause(
+                                        personView.call(p1),
+                                        personView.call(p2),
+                                        friendMustView.call(p1, p2)
+                ));
+                var query = Query.of("Count", Integer.class, (builder, p1, output) -> builder.clause(
+                                personView.call(p1),
+                                output.assign(subQuery.count(p1, Variable.of()))
+                ));
+
+                var store = ModelStore.builder()
+                                .symbols(person, friend)
+                                .with(QueryInterpreterAdapter.builder()
+                                                .defaultHint(hint)
+                                                .queries(query))
+                                .build();
+
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var friendInterpretation = model.getInterpretation(friend);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var queryResultSet = queryEngine.getResultSet(query);
+
+                personInterpretation.put(Tuple.of(0), true);
+                personInterpretation.put(Tuple.of(1), true);
+                personInterpretation.put(Tuple.of(2), true);
+
+                friendInterpretation.put(Tuple.of(0, 1), TruthValue.TRUE);
+                friendInterpretation.put(Tuple.of(1, 0), TruthValue.TRUE);
+                friendInterpretation.put(Tuple.of(1, 2), TruthValue.TRUE);
+
+                queryEngine.flushChanges();
+                assertNullableResults(Map.of(
+                                Tuple.of(0), Optional.of(1),
+                                Tuple.of(1), Optional.of(2),
+                                Tuple.of(2), Optional.of(0),
+                                Tuple.of(3), Optional.empty()
+                ), queryResultSet);
+        }
+
+        @QueryEngineTest
+        void inputKeyAggregationTest(QueryEvaluationHint hint) {
+                var query = Query.of("Aggregate", Integer.class, (builder, output) -> builder.clause(
+                                output.assign(ageView.aggregate(INT_SUM, Variable.of()))
+                ));
+
+                var store = ModelStore.builder()
+                                .symbols(age)
+                                .with(QueryInterpreterAdapter.builder()
+                                                .defaultHint(hint)
+                                                .queries(query))
+                                .build();
+
+                var model = store.createEmptyModel();
+                var ageInterpretation = model.getInterpretation(age);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var queryResultSet = queryEngine.getResultSet(query);
+
+                ageInterpretation.put(Tuple.of(0), 12);
+                ageInterpretation.put(Tuple.of(1), 24);
+
+                queryEngine.flushChanges();
+                assertResults(Map.of(Tuple.of(), 36), queryResultSet);
+        }
+
+        @QueryEngineTest
+        void predicateAggregationTest(QueryEvaluationHint hint) {
+                var subQuery = Query.of("SubQuery", Integer.class, (builder, p1, x) -> builder.clause(
+                                personView.call(p1),
+                                ageView.call(p1, x)
+                ));
+                var query = Query.of("Aggregate", Integer.class, (builder, output) -> builder.clause(
+                                output.assign(subQuery.aggregate(INT_SUM, Variable.of()))
+                ));
+
+                var store = ModelStore.builder()
+                                .symbols(person, age)
+                                .with(QueryInterpreterAdapter.builder()
+                                                .defaultHint(hint)
+                                                .queries(query))
+                                .build();
+
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var ageInterpretation = model.getInterpretation(age);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var queryResultSet = queryEngine.getResultSet(query);
+
+                personInterpretation.put(Tuple.of(0), true);
+                personInterpretation.put(Tuple.of(1), true);
+
+                ageInterpretation.put(Tuple.of(0), 12);
+                ageInterpretation.put(Tuple.of(1), 24);
+
+                queryEngine.flushChanges();
+                assertResults(Map.of(Tuple.of(), 36), queryResultSet);
+        }
+
+        @QueryEngineTest
+        void extremeValueTest(QueryEvaluationHint hint) {
+                var subQuery = Query.of("SubQuery", Integer.class, (builder, p1, x) -> builder.clause(
+                                personView.call(p1),
+                                x.assign(friendMustView.count(p1, Variable.of()))
+                ));
+                var minQuery = Query.of("Min", Integer.class, (builder, output) -> builder.clause(
+                                output.assign(subQuery.aggregate(INT_MIN, Variable.of()))
+                ));
+                var maxQuery = Query.of("Max", Integer.class, (builder, output) -> builder.clause(
+                                output.assign(subQuery.aggregate(INT_MAX, Variable.of()))
+                ));
+
+                var store = ModelStore.builder()
+                                .symbols(person, friend)
+                                .with(QueryInterpreterAdapter.builder()
+                                                .defaultHint(hint)
+                                                .queries(minQuery, maxQuery))
+                                .build();
+
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var friendInterpretation = model.getInterpretation(friend);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var minResultSet = queryEngine.getResultSet(minQuery);
+                var maxResultSet = queryEngine.getResultSet(maxQuery);
+
+                assertResults(Map.of(Tuple.of(), Integer.MAX_VALUE), minResultSet);
+                assertResults(Map.of(Tuple.of(), Integer.MIN_VALUE), maxResultSet);
+
+                personInterpretation.put(Tuple.of(0), true);
+                personInterpretation.put(Tuple.of(1), true);
+                personInterpretation.put(Tuple.of(2), true);
+
+                friendInterpretation.put(Tuple.of(0, 1), TruthValue.TRUE);
+                friendInterpretation.put(Tuple.of(1, 0), TruthValue.TRUE);
+                friendInterpretation.put(Tuple.of(1, 2), TruthValue.TRUE);
+
+                queryEngine.flushChanges();
+                assertResults(Map.of(Tuple.of(), 0), minResultSet);
+                assertResults(Map.of(Tuple.of(), 2), maxResultSet);
+
+                friendInterpretation.put(Tuple.of(2, 0), TruthValue.TRUE);
+                friendInterpretation.put(Tuple.of(2, 1), TruthValue.TRUE);
+
+                queryEngine.flushChanges();
+                assertResults(Map.of(Tuple.of(), 1), minResultSet);
+                assertResults(Map.of(Tuple.of(), 2), maxResultSet);
+
+                friendInterpretation.put(Tuple.of(0, 1), TruthValue.FALSE);
+                friendInterpretation.put(Tuple.of(1, 0), TruthValue.FALSE);
+                friendInterpretation.put(Tuple.of(2, 0), TruthValue.FALSE);
+
+                queryEngine.flushChanges();
+                assertResults(Map.of(Tuple.of(), 0), minResultSet);
+                assertResults(Map.of(Tuple.of(), 1), maxResultSet);
+        }
+
+        @QueryEngineTest
+        void invalidComputationTest(QueryEvaluationHint hint) {
+                var query = Query.of("InvalidComputation", Integer.class,
+                                (builder, p1, output) -> builder.clause(Integer.class, (x) -> List.of(
+                                                personView.call(p1),
+                                                ageView.call(p1, x),
+                                                output.assign(div(constant(120), x))
+                                )));
+
+                var store = ModelStore.builder()
+                                .symbols(person, age)
+                                .with(QueryInterpreterAdapter.builder()
+                                                .defaultHint(hint)
+                                                .queries(query))
+                                .build();
+
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var ageInterpretation = model.getInterpretation(age);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var queryResultSet = queryEngine.getResultSet(query);
+
+                personInterpretation.put(Tuple.of(0), true);
+                personInterpretation.put(Tuple.of(1), true);
+
+                ageInterpretation.put(Tuple.of(0), 0);
+                ageInterpretation.put(Tuple.of(1), 30);
+
+                queryEngine.flushChanges();
+                assertNullableResults(Map.of(
+                                Tuple.of(0), Optional.empty(),
+                                Tuple.of(1), Optional.of(4),
+                                Tuple.of(2), Optional.empty()
+                ), queryResultSet);
+        }
+
+        @QueryEngineTest
+        void invalidAssumeTest(QueryEvaluationHint hint) {
+                var query = Query.of("InvalidAssume", (builder, p1) -> builder.clause(Integer.class, (x) -> List.of(
+                                personView.call(p1),
+                                ageView.call(p1, x),
+                                check(lessEq(div(constant(120), x), constant(5)))
+                )));
+
+                var store = ModelStore.builder()
+                                .symbols(person, age)
+                                .with(QueryInterpreterAdapter.builder()
+                                                .defaultHint(hint)
+                                                .queries(query))
+                                .build();
+
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var ageInterpretation = model.getInterpretation(age);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var queryResultSet = queryEngine.getResultSet(query);
+
+                personInterpretation.put(Tuple.of(0), true);
+                personInterpretation.put(Tuple.of(1), true);
+                personInterpretation.put(Tuple.of(2), true);
+
+                ageInterpretation.put(Tuple.of(0), 0);
+                ageInterpretation.put(Tuple.of(1), 30);
+                ageInterpretation.put(Tuple.of(2), 20);
+
+                queryEngine.flushChanges();
+                assertResults(Map.of(
+                                Tuple.of(0), false,
+                                Tuple.of(1), true,
+                                Tuple.of(2), false,
+                                Tuple.of(3), false
+                ), queryResultSet);
+        }
+
+        @QueryEngineTest
+        void multipleAssignmentTest(QueryEvaluationHint hint) {
+                var query = Query.of("MultipleAssignment", Integer.class, (builder, p1, p2, output) -> builder
+                                .clause(Integer.class, Integer.class, (x1, x2) -> List.of(
+                                                ageView.call(p1, x1),
+                                                ageView.call(p2, x2),
+                                                output.assign(mul(x1, constant(2))),
+                                                output.assign(mul(x2, constant(3)))
+                                )));
+
+                var store = ModelStore.builder()
+                                .symbols(age)
+                                .with(QueryInterpreterAdapter.builder()
+                                                .defaultHint(hint)
+                                                .queries(query))
+                                .build();
+
+                var model = store.createEmptyModel();
+                var ageInterpretation = model.getInterpretation(age);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var queryResultSet = queryEngine.getResultSet(query);
+
+                ageInterpretation.put(Tuple.of(0), 3);
+                ageInterpretation.put(Tuple.of(1), 2);
+                ageInterpretation.put(Tuple.of(2), 15);
+                ageInterpretation.put(Tuple.of(3), 10);
+
+                queryEngine.flushChanges();
+                assertNullableResults(Map.of(
+                                Tuple.of(0, 1), Optional.of(6),
+                                Tuple.of(1, 0), Optional.empty(),
+                                Tuple.of(2, 3), Optional.of(30),
+                                Tuple.of(3, 2), Optional.empty()
+                ), queryResultSet);
+        }
+
+        @QueryEngineTest
+        void notFunctionalTest(QueryEvaluationHint hint) {
+                var query = Query.of("NotFunctional", Integer.class, (builder, p1, output) -> builder.clause((p2) -> List.of(
+                                personView.call(p1),
+                                friendMustView.call(p1, p2),
+                                ageView.call(p2, output)
+                )));
+
+                var store = ModelStore.builder()
+                                .symbols(person, age, friend)
+                                .with(QueryInterpreterAdapter.builder()
+                                                .defaultHint(hint)
+                                                .queries(query))
+                                .build();
+
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var ageInterpretation = model.getInterpretation(age);
+                var friendInterpretation = model.getInterpretation(friend);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var queryResultSet = queryEngine.getResultSet(query);
+
+                personInterpretation.put(Tuple.of(0), true);
+                personInterpretation.put(Tuple.of(1), true);
+                personInterpretation.put(Tuple.of(2), true);
+
+                ageInterpretation.put(Tuple.of(0), 24);
+                ageInterpretation.put(Tuple.of(1), 30);
+                ageInterpretation.put(Tuple.of(2), 36);
+
+                friendInterpretation.put(Tuple.of(0, 1), TruthValue.TRUE);
+                friendInterpretation.put(Tuple.of(1, 0), TruthValue.TRUE);
+                friendInterpretation.put(Tuple.of(1, 2), TruthValue.TRUE);
+
+                queryEngine.flushChanges();
+                var invalidTuple = Tuple.of(1);
+                var cursor = queryResultSet.getAll();
+                assertAll(
+                                () -> assertThat("value for key 0", queryResultSet.get(Tuple.of(0)), is(30)),
+                                () -> assertThrows(IllegalStateException.class, () -> queryResultSet.get(invalidTuple),
+                                                "multiple values for key 1"),
+                                () -> assertThat("value for key 2", queryResultSet.get(Tuple.of(2)), is(nullValue())),
+                                () -> assertThat("value for key 3", queryResultSet.get(Tuple.of(3)), is(nullValue()))
+                );
+                if (hint.getQueryBackendRequirementType() != QueryEvaluationHint.BackendRequirement.DEFAULT_SEARCH) {
+                        // Local search doesn't support throwing an error on multiple function return values.
+                        assertThat("results size", queryResultSet.size(), is(2));
+                        assertThrows(IllegalStateException.class, () -> enumerateValues(cursor), "move cursor");
+                }
+        }
+
+        private static void enumerateValues(Cursor<?, ?> cursor) {
+                //noinspection StatementWithEmptyBody
+                while (cursor.move()) {
+                        // Nothing do, just let the cursor move through the result set.
+                }
+        }
+}
diff --git a/subprojects/store-query-interpreter/src/test/java/tools/refinery/store/query/interpreter/OrderedResultSetTest.java b/subprojects/store-query-interpreter/src/test/java/tools/refinery/store/query/interpreter/OrderedResultSetTest.java
new file mode 100644
index 00000000..96d0f302
--- /dev/null
+++ b/subprojects/store-query-interpreter/src/test/java/tools/refinery/store/query/interpreter/OrderedResultSetTest.java
@@ -0,0 +1,117 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.interpreter;
+
+import org.junit.jupiter.api.Test;
+import tools.refinery.store.model.ModelStore;
+import tools.refinery.store.query.ModelQueryAdapter;
+import tools.refinery.store.query.dnf.Query;
+import tools.refinery.store.query.resultset.OrderedResultSet;
+import tools.refinery.store.query.term.Variable;
+import tools.refinery.store.query.view.AnySymbolView;
+import tools.refinery.store.query.view.KeyOnlyView;
+import tools.refinery.store.representation.Symbol;
+import tools.refinery.store.tuple.Tuple;
+
+import static org.hamcrest.MatcherAssert.assertThat;
+import static org.hamcrest.Matchers.is;
+
+class OrderedResultSetTest {
+        private static final Symbol<Boolean> friend = Symbol.of("friend", 2);
+        private static final AnySymbolView friendView = new KeyOnlyView<>(friend);
+
+        @Test
+        void relationalFlushTest() {
+                var query = Query.of("Relation", (builder, p1, p2) -> builder.clause(
+                                 friendView.call(p1, p2)
+                ));
+
+                var store = ModelStore.builder()
+                                .symbols(friend)
+                                .with(QueryInterpreterAdapter.builder()
+                                                .queries(query))
+                                .build();
+
+                var model = store.createEmptyModel();
+                var friendInterpretation = model.getInterpretation(friend);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var resultSet = queryEngine.getResultSet(query);
+
+                friendInterpretation.put(Tuple.of(0, 1), true);
+                friendInterpretation.put(Tuple.of(1, 2), true);
+                friendInterpretation.put(Tuple.of(1, 1), true);
+                queryEngine.flushChanges();
+
+                try (var orderedResultSet = new OrderedResultSet<>(resultSet)) {
+                        assertThat(orderedResultSet.size(), is(3));
+                        assertThat(orderedResultSet.getKey(0), is(Tuple.of(0, 1)));
+                        assertThat(orderedResultSet.getKey(1), is(Tuple.of(1, 1)));
+                        assertThat(orderedResultSet.getKey(2), is(Tuple.of(1, 2)));
+
+                        friendInterpretation.put(Tuple.of(1, 2), false);
+                        friendInterpretation.put(Tuple.of(0, 2), true);
+                        queryEngine.flushChanges();
+
+                        assertThat(orderedResultSet.size(), is(3));
+                        assertThat(orderedResultSet.getKey(0), is(Tuple.of(0, 1)));
+                        assertThat(orderedResultSet.getKey(1), is(Tuple.of(0, 2)));
+                        assertThat(orderedResultSet.getKey(2), is(Tuple.of(1, 1)));
+                }
+        }
+
+        @Test
+        void functionalFlushTest() {
+                var query = Query.of("Function", Integer.class, (builder, p1, output) -> builder.clause(
+                                friendView.call(p1, Variable.of()),
+                                output.assign(friendView.count(p1, Variable.of()))
+                ));
+
+                var store = ModelStore.builder()
+                                .symbols(friend)
+                                .with(QueryInterpreterAdapter.builder()
+                                                .queries(query))
+                                .build();
+
+                var model = store.createEmptyModel();
+                var friendInterpretation = model.getInterpretation(friend);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var resultSet = queryEngine.getResultSet(query);
+
+                friendInterpretation.put(Tuple.of(0, 1), true);
+                friendInterpretation.put(Tuple.of(1, 2), true);
+                friendInterpretation.put(Tuple.of(1, 1), true);
+                queryEngine.flushChanges();
+
+                try (var orderedResultSet = new OrderedResultSet<>(resultSet)) {
+                        assertThat(orderedResultSet.size(), is(2));
+                        assertThat(orderedResultSet.getKey(0), is(Tuple.of(0)));
+                        assertThat(orderedResultSet.getKey(1), is(Tuple.of(1)));
+
+                        friendInterpretation.put(Tuple.of(0, 1), false);
+                        friendInterpretation.put(Tuple.of(2, 1), true);
+                        queryEngine.flushChanges();
+
+                        assertThat(orderedResultSet.size(), is(2));
+                        assertThat(orderedResultSet.getKey(0), is(Tuple.of(1)));
+                        assertThat(orderedResultSet.getKey(1), is(Tuple.of(2)));
+
+                        friendInterpretation.put(Tuple.of(1, 1), false);
+                        queryEngine.flushChanges();
+
+                        assertThat(orderedResultSet.size(), is(2));
+                        assertThat(orderedResultSet.getKey(0), is(Tuple.of(1)));
+                        assertThat(orderedResultSet.getKey(1), is(Tuple.of(2)));
+
+                        friendInterpretation.put(Tuple.of(1, 2), false);
+                        friendInterpretation.put(Tuple.of(1, 0), true);
+                        queryEngine.flushChanges();
+
+                        assertThat(orderedResultSet.size(), is(2));
+                        assertThat(orderedResultSet.getKey(0), is(Tuple.of(1)));
+                        assertThat(orderedResultSet.getKey(1), is(Tuple.of(2)));
+                }
+        }
+}
diff --git a/subprojects/store-query-interpreter/src/test/java/tools/refinery/store/query/interpreter/QueryTest.java b/subprojects/store-query-interpreter/src/test/java/tools/refinery/store/query/interpreter/QueryTest.java
new file mode 100644
index 00000000..72728dcd
--- /dev/null
+++ b/subprojects/store-query-interpreter/src/test/java/tools/refinery/store/query/interpreter/QueryTest.java
@@ -0,0 +1,794 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.interpreter;
+
+import tools.refinery.interpreter.matchers.backend.QueryEvaluationHint;
+import org.junit.jupiter.api.Test;
+import tools.refinery.store.model.ModelStore;
+import tools.refinery.store.query.ModelQueryAdapter;
+import tools.refinery.store.query.dnf.Dnf;
+import tools.refinery.store.query.dnf.Query;
+import tools.refinery.store.query.term.ParameterDirection;
+import tools.refinery.store.query.term.Variable;
+import tools.refinery.store.query.interpreter.tests.QueryEngineTest;
+import tools.refinery.store.query.view.AnySymbolView;
+import tools.refinery.store.query.view.FilteredView;
+import tools.refinery.store.query.view.FunctionView;
+import tools.refinery.store.query.view.KeyOnlyView;
+import tools.refinery.store.representation.Symbol;
+import tools.refinery.store.representation.TruthValue;
+import tools.refinery.store.tuple.Tuple;
+
+import java.util.List;
+import java.util.Map;
+
+import static tools.refinery.store.query.literal.Literals.check;
+import static tools.refinery.store.query.literal.Literals.not;
+import static tools.refinery.store.query.term.int_.IntTerms.constant;
+import static tools.refinery.store.query.term.int_.IntTerms.greaterEq;
+import static tools.refinery.store.query.interpreter.tests.QueryAssertions.assertResults;
+
+class QueryTest {
+        private static final Symbol<Boolean> person = Symbol.of("Person", 1);
+        private static final Symbol<TruthValue> friend = Symbol.of("friend", 2, TruthValue.class, TruthValue.FALSE);
+        private static final AnySymbolView personView = new KeyOnlyView<>(person);
+        private static final AnySymbolView friendMustView = new FilteredView<>(friend, "must", TruthValue::must);
+
+        @QueryEngineTest
+        void typeConstraintTest(QueryEvaluationHint hint) {
+                var asset = Symbol.of("Asset", 1);
+
+                var predicate = Query.of("TypeConstraint", (builder, p1) -> builder.clause(personView.call(p1)));
+
+                var store = ModelStore.builder()
+                                .symbols(person, asset)
+                                .with(QueryInterpreterAdapter.builder()
+                                                .defaultHint(hint)
+                                                .queries(predicate))
+                                .build();
+
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var assetInterpretation = model.getInterpretation(asset);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var predicateResultSet = queryEngine.getResultSet(predicate);
+
+                personInterpretation.put(Tuple.of(0), true);
+                personInterpretation.put(Tuple.of(1), true);
+
+                assetInterpretation.put(Tuple.of(1), true);
+                assetInterpretation.put(Tuple.of(2), true);
+
+                queryEngine.flushChanges();
+                assertResults(Map.of(
+                                Tuple.of(0), true,
+                                Tuple.of(1), true,
+                                Tuple.of(2), false
+                ), predicateResultSet);
+        }
+
+        @QueryEngineTest
+        void relationConstraintTest(QueryEvaluationHint hint) {
+                var predicate = Query.of("RelationConstraint", (builder, p1, p2) -> builder.clause(
+                                personView.call(p1),
+                                personView.call(p2),
+                                friendMustView.call(p1, p2)
+                ));
+
+                var store = ModelStore.builder()
+                                .symbols(person, friend)
+                                .with(QueryInterpreterAdapter.builder()
+                                                .defaultHint(hint)
+                                                .queries(predicate))
+                                .build();
+
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var friendInterpretation = model.getInterpretation(friend);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var predicateResultSet = queryEngine.getResultSet(predicate);
+
+                personInterpretation.put(Tuple.of(0), true);
+                personInterpretation.put(Tuple.of(1), true);
+                personInterpretation.put(Tuple.of(2), true);
+
+                friendInterpretation.put(Tuple.of(0, 1), TruthValue.TRUE);
+                friendInterpretation.put(Tuple.of(1, 0), TruthValue.TRUE);
+                friendInterpretation.put(Tuple.of(1, 2), TruthValue.TRUE);
+                friendInterpretation.put(Tuple.of(1, 3), TruthValue.TRUE);
+
+                queryEngine.flushChanges();
+                assertResults(Map.of(
+                                Tuple.of(0, 1), true,
+                                Tuple.of(1, 0), true,
+                                Tuple.of(1, 2), true,
+                                Tuple.of(2, 1), false
+                ), predicateResultSet);
+        }
+
+        @QueryEngineTest
+        void isConstantTest(QueryEvaluationHint hint) {
+                var predicate = Query.of("RelationConstraint", (builder, p1, p2) -> builder.clause(
+                                personView.call(p1),
+                                p1.isConstant(1),
+                                friendMustView.call(p1, p2)
+                ));
+
+                var store = ModelStore.builder()
+                                .symbols(person, friend)
+                                .with(QueryInterpreterAdapter.builder()
+                                                .defaultHint(hint)
+                                                .queries(predicate))
+                                .build();
+
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var friendInterpretation = model.getInterpretation(friend);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var predicateResultSet = queryEngine.getResultSet(predicate);
+
+                personInterpretation.put(Tuple.of(0), true);
+                personInterpretation.put(Tuple.of(1), true);
+                personInterpretation.put(Tuple.of(2), true);
+
+                friendInterpretation.put(Tuple.of(0, 1), TruthValue.TRUE);
+                friendInterpretation.put(Tuple.of(1, 0), TruthValue.TRUE);
+                friendInterpretation.put(Tuple.of(1, 2), TruthValue.TRUE);
+
+                queryEngine.flushChanges();
+                assertResults(Map.of(
+                                Tuple.of(0, 1), false,
+                                Tuple.of(1, 0), true,
+                                Tuple.of(1, 2), true,
+                                Tuple.of(2, 1), false
+                ), predicateResultSet);
+        }
+
+        @QueryEngineTest
+        void existTest(QueryEvaluationHint hint) {
+                var predicate = Query.of("Exists", (builder, p1) -> builder.clause((p2) -> List.of(
+                                personView.call(p1),
+                                personView.call(p2),
+                                friendMustView.call(p1, p2)
+                )));
+
+                var store = ModelStore.builder()
+                                .symbols(person, friend)
+                                .with(QueryInterpreterAdapter.builder()
+                                                .defaultHint(hint)
+                                                .queries(predicate))
+                                .build();
+
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var friendInterpretation = model.getInterpretation(friend);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var predicateResultSet = queryEngine.getResultSet(predicate);
+
+                personInterpretation.put(Tuple.of(0), true);
+                personInterpretation.put(Tuple.of(1), true);
+                personInterpretation.put(Tuple.of(2), true);
+
+                friendInterpretation.put(Tuple.of(0, 1), TruthValue.TRUE);
+                friendInterpretation.put(Tuple.of(1, 0), TruthValue.TRUE);
+                friendInterpretation.put(Tuple.of(1, 2), TruthValue.TRUE);
+                friendInterpretation.put(Tuple.of(3, 2), TruthValue.TRUE);
+
+                queryEngine.flushChanges();
+                assertResults(Map.of(
+                                Tuple.of(0), true,
+                                Tuple.of(1), true,
+                                Tuple.of(2), false,
+                                Tuple.of(3), false
+                ), predicateResultSet);
+        }
+
+        @QueryEngineTest
+        void orTest(QueryEvaluationHint hint) {
+                var animal = Symbol.of("Animal", 1);
+                var animalView = new KeyOnlyView<>(animal);
+
+                var predicate = Query.of("Or", (builder, p1, p2) -> builder.clause(
+                                personView.call(p1),
+                                personView.call(p2),
+                                friendMustView.call(p1, p2)
+                ).clause(
+                                animalView.call(p1),
+                                animalView.call(p2),
+                                friendMustView.call(p1, p2)
+                ));
+
+                var store = ModelStore.builder()
+                                .symbols(person, animal, friend)
+                                .with(QueryInterpreterAdapter.builder()
+                                                .defaultHint(hint)
+                                                .queries(predicate))
+                                .build();
+
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var animalInterpretation = model.getInterpretation(animal);
+                var friendInterpretation = model.getInterpretation(friend);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var predicateResultSet = queryEngine.getResultSet(predicate);
+
+                personInterpretation.put(Tuple.of(0), true);
+                personInterpretation.put(Tuple.of(1), true);
+
+                animalInterpretation.put(Tuple.of(2), true);
+                animalInterpretation.put(Tuple.of(3), true);
+
+                friendInterpretation.put(Tuple.of(0, 1), TruthValue.TRUE);
+                friendInterpretation.put(Tuple.of(0, 2), TruthValue.TRUE);
+                friendInterpretation.put(Tuple.of(2, 3), TruthValue.TRUE);
+                friendInterpretation.put(Tuple.of(3, 0), TruthValue.TRUE);
+
+                queryEngine.flushChanges();
+                assertResults(Map.of(
+                                Tuple.of(0, 1), true,
+                                Tuple.of(0, 2), false,
+                                Tuple.of(2, 3), true,
+                                Tuple.of(3, 0), false,
+                                Tuple.of(3, 2), false
+                ), predicateResultSet);
+        }
+
+        @QueryEngineTest
+        void equalityTest(QueryEvaluationHint hint) {
+                var predicate = Query.of("Equality", (builder, p1, p2) -> builder.clause(
+                                personView.call(p1),
+                                personView.call(p2),
+                                p1.isEquivalent(p2)
+                ));
+
+                var store = ModelStore.builder()
+                                .symbols(person)
+                                .with(QueryInterpreterAdapter.builder()
+                                                .defaultHint(hint)
+                                                .queries(predicate))
+                                .build();
+
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var predicateResultSet = queryEngine.getResultSet(predicate);
+
+                personInterpretation.put(Tuple.of(0), true);
+                personInterpretation.put(Tuple.of(1), true);
+                personInterpretation.put(Tuple.of(2), true);
+
+                queryEngine.flushChanges();
+                assertResults(Map.of(
+                                Tuple.of(0, 0), true,
+                                Tuple.of(1, 1), true,
+                                Tuple.of(2, 2), true,
+                                Tuple.of(0, 1), false,
+                                Tuple.of(3, 3), false
+                ), predicateResultSet);
+        }
+
+        @QueryEngineTest
+        void inequalityTest(QueryEvaluationHint hint) {
+                var predicate = Query.of("Inequality", (builder, p1, p2, p3) -> builder.clause(
+                                personView.call(p1),
+                                personView.call(p2),
+                                friendMustView.call(p1, p3),
+                                friendMustView.call(p2, p3),
+                                p1.notEquivalent(p2)
+                ));
+
+                var store = ModelStore.builder()
+                                .symbols(person, friend)
+                                .with(QueryInterpreterAdapter.builder()
+                                                .defaultHint(hint)
+                                                .queries(predicate))
+                                .build();
+
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var friendInterpretation = model.getInterpretation(friend);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var predicateResultSet = queryEngine.getResultSet(predicate);
+
+                personInterpretation.put(Tuple.of(0), true);
+                personInterpretation.put(Tuple.of(1), true);
+                personInterpretation.put(Tuple.of(2), true);
+
+                friendInterpretation.put(Tuple.of(0, 2), TruthValue.TRUE);
+                friendInterpretation.put(Tuple.of(1, 2), TruthValue.TRUE);
+
+                queryEngine.flushChanges();
+                assertResults(Map.of(
+                                Tuple.of(0, 1, 2), true,
+                                Tuple.of(1, 0, 2), true,
+                                Tuple.of(0, 0, 2), false
+                ), predicateResultSet);
+        }
+
+        @QueryEngineTest
+        void patternCallTest(QueryEvaluationHint hint) {
+                var friendPredicate = Query.of("Friend", (builder, p1, p2) -> builder.clause(
+                                personView.call(p1),
+                                personView.call(p2),
+                                friendMustView.call(p1, p2)
+                ));
+                var predicate = Query.of("PositivePatternCall", (builder, p3, p4) -> builder.clause(
+                                personView.call(p3),
+                                personView.call(p4),
+                                friendPredicate.call(p3, p4)
+                ));
+
+                var store = ModelStore.builder()
+                                .symbols(person, friend)
+                                .with(QueryInterpreterAdapter.builder()
+                                                .defaultHint(hint)
+                                                .queries(predicate))
+                                .build();
+
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var friendInterpretation = model.getInterpretation(friend);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var predicateResultSet = queryEngine.getResultSet(predicate);
+
+                personInterpretation.put(Tuple.of(0), true);
+                personInterpretation.put(Tuple.of(1), true);
+                personInterpretation.put(Tuple.of(2), true);
+
+                friendInterpretation.put(Tuple.of(0, 1), TruthValue.TRUE);
+                friendInterpretation.put(Tuple.of(1, 0), TruthValue.TRUE);
+                friendInterpretation.put(Tuple.of(1, 2), TruthValue.TRUE);
+
+                queryEngine.flushChanges();
+                assertResults(Map.of(
+                                Tuple.of(0, 1), true,
+                                Tuple.of(1, 0), true,
+                                Tuple.of(1, 2), true,
+                                Tuple.of(2, 1), false
+                ), predicateResultSet);
+        }
+
+        @QueryEngineTest
+        void patternCallInputArgumentTest(QueryEvaluationHint hint) {
+                var friendPredicate = Dnf.of("Friend", builder -> {
+                        var p1 = builder.parameter("p1", ParameterDirection.IN);
+                        var p2 = builder.parameter("p2", ParameterDirection.IN);
+                        builder.clause(
+                                        personView.call(p1),
+                                        personView.call(p2),
+                                        friendMustView.call(p1, p2)
+                        );
+                });
+                var predicate = Query.of("PositivePatternCall", (builder, p3, p4) -> builder.clause(
+                                personView.call(p3),
+                                personView.call(p4),
+                                friendPredicate.call(p3, p4)
+                ));
+
+                var store = ModelStore.builder()
+                                .symbols(person, friend)
+                                .with(QueryInterpreterAdapter.builder()
+                                                .defaultHint(hint)
+                                                .queries(predicate))
+                                .build();
+
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var friendInterpretation = model.getInterpretation(friend);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var predicateResultSet = queryEngine.getResultSet(predicate);
+
+                personInterpretation.put(Tuple.of(0), true);
+                personInterpretation.put(Tuple.of(1), true);
+                personInterpretation.put(Tuple.of(2), true);
+
+                friendInterpretation.put(Tuple.of(0, 1), TruthValue.TRUE);
+                friendInterpretation.put(Tuple.of(1, 0), TruthValue.TRUE);
+                friendInterpretation.put(Tuple.of(1, 2), TruthValue.TRUE);
+
+                queryEngine.flushChanges();
+                assertResults(Map.of(
+                                Tuple.of(0, 1), true,
+                                Tuple.of(1, 0), true,
+                                Tuple.of(1, 2), true,
+                                Tuple.of(2, 1), false
+                ), predicateResultSet);
+        }
+
+        @QueryEngineTest
+        void negativeRelationViewTest(QueryEvaluationHint hint) {
+                var predicate = Query.of("NegativePatternCall", (builder, p1, p2) -> builder.clause(
+                                personView.call(p1),
+                                personView.call(p2),
+                                not(friendMustView.call(p1, p2))
+                ));
+
+                var store = ModelStore.builder()
+                                .symbols(person, friend)
+                                .with(QueryInterpreterAdapter.builder()
+                                                .defaultHint(hint)
+                                                .queries(predicate))
+                                .build();
+
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var friendInterpretation = model.getInterpretation(friend);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var predicateResultSet = queryEngine.getResultSet(predicate);
+
+                personInterpretation.put(Tuple.of(0), true);
+                personInterpretation.put(Tuple.of(1), true);
+                personInterpretation.put(Tuple.of(2), true);
+
+                friendInterpretation.put(Tuple.of(0, 1), TruthValue.TRUE);
+                friendInterpretation.put(Tuple.of(1, 0), TruthValue.TRUE);
+                friendInterpretation.put(Tuple.of(1, 2), TruthValue.TRUE);
+
+                queryEngine.flushChanges();
+                assertResults(Map.of(
+                                Tuple.of(0, 0), true,
+                                Tuple.of(0, 2), true,
+                                Tuple.of(1, 1), true,
+                                Tuple.of(2, 0), true,
+                                Tuple.of(2, 1), true,
+                                Tuple.of(2, 2), true,
+                                Tuple.of(0, 1), false,
+                                Tuple.of(1, 0), false,
+                                Tuple.of(1, 2), false,
+                                Tuple.of(0, 3), false
+                ), predicateResultSet);
+        }
+
+        @QueryEngineTest
+        void negativePatternCallTest(QueryEvaluationHint hint) {
+                var friendPredicate = Query.of("Friend", (builder, p1, p2) -> builder.clause(
+                                personView.call(p1),
+                                personView.call(p2),
+                                friendMustView.call(p1, p2)
+                ));
+                var predicate = Query.of("NegativePatternCall", (builder, p3, p4) -> builder.clause(
+                                personView.call(p3),
+                                personView.call(p4),
+                                not(friendPredicate.call(p3, p4))
+                ));
+
+                var store = ModelStore.builder()
+                                .symbols(person, friend)
+                                .with(QueryInterpreterAdapter.builder()
+                                                .defaultHint(hint)
+                                                .queries(predicate))
+                                .build();
+
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var friendInterpretation = model.getInterpretation(friend);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var predicateResultSet = queryEngine.getResultSet(predicate);
+
+                personInterpretation.put(Tuple.of(0), true);
+                personInterpretation.put(Tuple.of(1), true);
+                personInterpretation.put(Tuple.of(2), true);
+
+                friendInterpretation.put(Tuple.of(0, 1), TruthValue.TRUE);
+                friendInterpretation.put(Tuple.of(1, 0), TruthValue.TRUE);
+                friendInterpretation.put(Tuple.of(1, 2), TruthValue.TRUE);
+
+                queryEngine.flushChanges();
+                assertResults(Map.of(
+                                Tuple.of(0, 0), true,
+                                Tuple.of(0, 2), true,
+                                Tuple.of(1, 1), true,
+                                Tuple.of(2, 0), true,
+                                Tuple.of(2, 1), true,
+                                Tuple.of(2, 2), true,
+                                Tuple.of(0, 1), false,
+                                Tuple.of(1, 0), false,
+                                Tuple.of(1, 2), false,
+                                Tuple.of(0, 3), false
+                ), predicateResultSet);
+        }
+
+        @QueryEngineTest
+        void negativeRelationViewWithQuantificationTest(QueryEvaluationHint hint) {
+                var predicate = Query.of("Negative", (builder, p1) -> builder.clause(
+                                personView.call(p1),
+                                not(friendMustView.call(p1, Variable.of()))
+                ));
+
+                var store = ModelStore.builder()
+                                .symbols(person, friend)
+                                .with(QueryInterpreterAdapter.builder()
+                                                .defaultHint(hint)
+                                                .queries(predicate))
+                                .build();
+
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var friendInterpretation = model.getInterpretation(friend);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var predicateResultSet = queryEngine.getResultSet(predicate);
+
+                personInterpretation.put(Tuple.of(0), true);
+                personInterpretation.put(Tuple.of(1), true);
+                personInterpretation.put(Tuple.of(2), true);
+
+                friendInterpretation.put(Tuple.of(0, 1), TruthValue.TRUE);
+                friendInterpretation.put(Tuple.of(0, 2), TruthValue.TRUE);
+
+                queryEngine.flushChanges();
+                assertResults(Map.of(
+                                Tuple.of(0), false,
+                                Tuple.of(1), true,
+                                Tuple.of(2), true,
+                                Tuple.of(3), false
+                ), predicateResultSet);
+        }
+
+        @QueryEngineTest
+        void negativeWithQuantificationTest(QueryEvaluationHint hint) {
+                var called = Query.of("Called", (builder, p1, p2) -> builder.clause(
+                                personView.call(p1),
+                                personView.call(p2),
+                                friendMustView.call(p1, p2)
+                ));
+                var predicate = Query.of("Negative", (builder, p1) -> builder.clause(
+                                personView.call(p1),
+                                not(called.call(p1, Variable.of()))
+                ));
+
+                var store = ModelStore.builder()
+                                .symbols(person, friend)
+                                .with(QueryInterpreterAdapter.builder()
+                                                .defaultHint(hint)
+                                                .queries(predicate))
+                                .build();
+
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var friendInterpretation = model.getInterpretation(friend);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var predicateResultSet = queryEngine.getResultSet(predicate);
+
+                personInterpretation.put(Tuple.of(0), true);
+                personInterpretation.put(Tuple.of(1), true);
+                personInterpretation.put(Tuple.of(2), true);
+
+                friendInterpretation.put(Tuple.of(0, 1), TruthValue.TRUE);
+                friendInterpretation.put(Tuple.of(0, 2), TruthValue.TRUE);
+
+                queryEngine.flushChanges();
+                assertResults(Map.of(
+                                Tuple.of(0), false,
+                                Tuple.of(1), true,
+                                Tuple.of(2), true,
+                                Tuple.of(3), false
+                ), predicateResultSet);
+        }
+
+        @QueryEngineTest
+        void transitiveRelationViewTest(QueryEvaluationHint hint) {
+                var predicate = Query.of("Transitive", (builder, p1, p2) -> builder.clause(
+                                personView.call(p1),
+                                personView.call(p2),
+                                friendMustView.callTransitive(p1, p2)
+                ));
+
+                var store = ModelStore.builder()
+                                .symbols(person, friend)
+                                .with(QueryInterpreterAdapter.builder()
+                                                .defaultHint(hint)
+                                                .queries(predicate))
+                                .build();
+
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var friendInterpretation = model.getInterpretation(friend);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var predicateResultSet = queryEngine.getResultSet(predicate);
+
+                personInterpretation.put(Tuple.of(0), true);
+                personInterpretation.put(Tuple.of(1), true);
+                personInterpretation.put(Tuple.of(2), true);
+
+                friendInterpretation.put(Tuple.of(0, 1), TruthValue.TRUE);
+                friendInterpretation.put(Tuple.of(1, 2), TruthValue.TRUE);
+
+                queryEngine.flushChanges();
+                assertResults(Map.of(
+                                Tuple.of(0, 0), false,
+                                Tuple.of(0, 1), true,
+                                Tuple.of(0, 2), true,
+                                Tuple.of(1, 0), false,
+                                Tuple.of(1, 1), false,
+                                Tuple.of(1, 2), true,
+                                Tuple.of(2, 0), false,
+                                Tuple.of(2, 1), false,
+                                Tuple.of(2, 2), false,
+                                Tuple.of(2, 3), false
+                ), predicateResultSet);
+        }
+
+        @QueryEngineTest
+        void transitivePatternCallTest(QueryEvaluationHint hint) {
+                var called = Query.of("Called", (builder, p1, p2) -> builder.clause(
+                                personView.call(p1),
+                                personView.call(p2),
+                                friendMustView.call(p1, p2)
+                ));
+                var predicate = Query.of("Transitive", (builder, p1, p2) -> builder.clause(
+                                personView.call(p1),
+                                personView.call(p2),
+                                called.callTransitive(p1, p2)
+                ));
+
+                var store = ModelStore.builder()
+                                .symbols(person, friend)
+                                .with(QueryInterpreterAdapter.builder()
+                                                .defaultHint(hint)
+                                                .queries(predicate))
+                                .build();
+
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var friendInterpretation = model.getInterpretation(friend);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var predicateResultSet = queryEngine.getResultSet(predicate);
+
+                personInterpretation.put(Tuple.of(0), true);
+                personInterpretation.put(Tuple.of(1), true);
+                personInterpretation.put(Tuple.of(2), true);
+
+                friendInterpretation.put(Tuple.of(0, 1), TruthValue.TRUE);
+                friendInterpretation.put(Tuple.of(1, 2), TruthValue.TRUE);
+
+                queryEngine.flushChanges();
+                assertResults(Map.of(
+                                Tuple.of(0, 0), false,
+                                Tuple.of(0, 1), true,
+                                Tuple.of(0, 2), true,
+                                Tuple.of(1, 0), false,
+                                Tuple.of(1, 1), false,
+                                Tuple.of(1, 2), true,
+                                Tuple.of(2, 0), false,
+                                Tuple.of(2, 1), false,
+                                Tuple.of(2, 2), false,
+                                Tuple.of(2, 3), false
+                ), predicateResultSet);
+        }
+
+        @Test
+        void filteredIntegerViewTest() {
+                var distance = Symbol.of("distance", 2, Integer.class);
+                var nearView = new FilteredView<>(distance, value -> value < 2);
+                var farView = new FilteredView<>(distance, value -> value >= 5);
+                var dangerQuery = Query.of("danger", (builder, a1, a2) -> builder.clause((a3) -> List.of(
+                                a1.notEquivalent(a2),
+                                nearView.call(a1, a3),
+                                nearView.call(a2, a3),
+                                not(farView.call(a1, a2))
+                )));
+                var store = ModelStore.builder()
+                                .symbols(distance)
+                                .with(QueryInterpreterAdapter.builder()
+                                                .queries(dangerQuery))
+                                .build();
+
+                var model = store.createEmptyModel();
+                var distanceInterpretation = model.getInterpretation(distance);
+                distanceInterpretation.put(Tuple.of(0, 1), 1);
+                distanceInterpretation.put(Tuple.of(1, 0), 1);
+                distanceInterpretation.put(Tuple.of(0, 2), 1);
+                distanceInterpretation.put(Tuple.of(2, 0), 1);
+                distanceInterpretation.put(Tuple.of(1, 2), 3);
+                distanceInterpretation.put(Tuple.of(2, 1), 3);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var dangerResultSet = queryEngine.getResultSet(dangerQuery);
+                queryEngine.flushChanges();
+                assertResults(Map.of(
+                                Tuple.of(0, 1), false,
+                                Tuple.of(0, 2), false,
+                                Tuple.of(1, 2), true,
+                                Tuple.of(2, 1), true
+                ), dangerResultSet);
+        }
+
+        @Test
+        void filteredDoubleViewTest() {
+                var distance = Symbol.of("distance", 2, Double.class);
+                var nearView = new FilteredView<>(distance, value -> value < 2);
+                var farView = new FilteredView<>(distance, value -> value >= 5);
+                var dangerQuery = Query.of("danger", (builder, a1, a2) -> builder.clause((a3) -> List.of(
+                                a1.notEquivalent(a2),
+                                nearView.call(a1, a3),
+                                nearView.call(a2, a3),
+                                not(farView.call(a1, a2))
+                )));
+                var store = ModelStore.builder()
+                                .symbols(distance)
+                                .with(QueryInterpreterAdapter.builder()
+                                                .queries(dangerQuery))
+                                .build();
+
+                var model = store.createEmptyModel();
+                var distanceInterpretation = model.getInterpretation(distance);
+                distanceInterpretation.put(Tuple.of(0, 1), 1.0);
+                distanceInterpretation.put(Tuple.of(1, 0), 1.0);
+                distanceInterpretation.put(Tuple.of(0, 2), 1.0);
+                distanceInterpretation.put(Tuple.of(2, 0), 1.0);
+                distanceInterpretation.put(Tuple.of(1, 2), 3.0);
+                distanceInterpretation.put(Tuple.of(2, 1), 3.0);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var dangerResultSet = queryEngine.getResultSet(dangerQuery);
+                queryEngine.flushChanges();
+                assertResults(Map.of(
+                                Tuple.of(0, 1), false,
+                                Tuple.of(0, 2), false,
+                                Tuple.of(1, 2), true,
+                                Tuple.of(2, 1), true
+                ), dangerResultSet);
+        }
+
+        @QueryEngineTest
+        void assumeTest(QueryEvaluationHint hint) {
+                var age = Symbol.of("age", 1, Integer.class);
+                var ageView = new FunctionView<>(age);
+
+                var query = Query.of("Constraint", (builder, p1) -> builder.clause(Integer.class, (x) -> List.of(
+                                personView.call(p1),
+                                ageView.call(p1, x),
+                                check(greaterEq(x, constant(18)))
+                )));
+
+                var store = ModelStore.builder()
+                                .symbols(person, age)
+                                .with(QueryInterpreterAdapter.builder()
+                                                .defaultHint(hint)
+                                                .queries(query))
+                                .build();
+
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var ageInterpretation = model.getInterpretation(age);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var queryResultSet = queryEngine.getResultSet(query);
+
+                personInterpretation.put(Tuple.of(0), true);
+                personInterpretation.put(Tuple.of(1), true);
+
+                ageInterpretation.put(Tuple.of(0), 12);
+                ageInterpretation.put(Tuple.of(1), 24);
+
+                queryEngine.flushChanges();
+                assertResults(Map.of(
+                                Tuple.of(0), false,
+                                Tuple.of(1), true,
+                                Tuple.of(2), false
+                ), queryResultSet);
+        }
+
+        @Test
+        void alwaysFalseTest() {
+                var predicate = Query.of("AlwaysFalse", builder -> builder.parameter("p1"));
+
+                var store = ModelStore.builder()
+                                .symbols(person)
+                                .with(QueryInterpreterAdapter.builder()
+                                                .queries(predicate))
+                                .build();
+
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var predicateResultSet = queryEngine.getResultSet(predicate);
+
+                personInterpretation.put(Tuple.of(0), true);
+                personInterpretation.put(Tuple.of(1), true);
+                personInterpretation.put(Tuple.of(2), true);
+
+                queryEngine.flushChanges();
+                assertResults(Map.of(), predicateResultSet);
+        }
+}
diff --git a/subprojects/store-query-interpreter/src/test/java/tools/refinery/store/query/interpreter/QueryTransactionTest.java b/subprojects/store-query-interpreter/src/test/java/tools/refinery/store/query/interpreter/QueryTransactionTest.java
new file mode 100644
index 00000000..1cd05d91
--- /dev/null
+++ b/subprojects/store-query-interpreter/src/test/java/tools/refinery/store/query/interpreter/QueryTransactionTest.java
@@ -0,0 +1,370 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.interpreter;
+
+import tools.refinery.interpreter.matchers.backend.QueryEvaluationHint;
+import org.junit.jupiter.api.Test;
+import tools.refinery.store.model.ModelStore;
+import tools.refinery.store.query.ModelQueryAdapter;
+import tools.refinery.store.query.dnf.Query;
+import tools.refinery.store.query.dnf.RelationalQuery;
+import tools.refinery.store.query.view.AnySymbolView;
+import tools.refinery.store.query.view.FilteredView;
+import tools.refinery.store.query.view.FunctionView;
+import tools.refinery.store.query.view.KeyOnlyView;
+import tools.refinery.store.representation.Symbol;
+import tools.refinery.store.tuple.Tuple;
+
+import java.util.Map;
+import java.util.Optional;
+
+import static org.junit.jupiter.api.Assertions.assertFalse;
+import static org.junit.jupiter.api.Assertions.assertTrue;
+import static tools.refinery.store.query.interpreter.tests.QueryAssertions.assertNullableResults;
+import static tools.refinery.store.query.interpreter.tests.QueryAssertions.assertResults;
+
+class QueryTransactionTest {
+        private static final Symbol<Boolean> person = Symbol.of("Person", 1);
+        private static final Symbol<Integer> age = Symbol.of("age", 1, Integer.class);
+        private static final AnySymbolView personView = new KeyOnlyView<>(person);
+        private static final AnySymbolView ageView = new FunctionView<>(age);
+        private static final RelationalQuery predicate = Query.of("TypeConstraint", (builder, p1) ->
+                        builder.clause(personView.call(p1)));
+
+        @Test
+        void flushTest() {
+                var store = ModelStore.builder()
+                                .symbols(person)
+                                .with(QueryInterpreterAdapter.builder()
+                                                .queries(predicate))
+                                .build();
+
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var predicateResultSet = queryEngine.getResultSet(predicate);
+
+                assertResults(Map.of(
+                                Tuple.of(0), false,
+                                Tuple.of(1), false,
+                                Tuple.of(2), false,
+                                Tuple.of(3), false
+                ), predicateResultSet);
+                assertFalse(queryEngine.hasPendingChanges());
+
+                personInterpretation.put(Tuple.of(0), true);
+                personInterpretation.put(Tuple.of(1), true);
+
+                assertResults(Map.of(
+                                Tuple.of(0), false,
+                                Tuple.of(1), false,
+                                Tuple.of(2), false,
+                                Tuple.of(3), false
+                ), predicateResultSet);
+                assertTrue(queryEngine.hasPendingChanges());
+
+                queryEngine.flushChanges();
+                assertResults(Map.of(
+                                Tuple.of(0), true,
+                                Tuple.of(1), true,
+                                Tuple.of(2), false,
+                                Tuple.of(3), false
+                ), predicateResultSet);
+                assertFalse(queryEngine.hasPendingChanges());
+
+                personInterpretation.put(Tuple.of(1), false);
+                personInterpretation.put(Tuple.of(2), true);
+
+                assertResults(Map.of(
+                                Tuple.of(0), true,
+                                Tuple.of(1), true,
+                                Tuple.of(2), false,
+                                Tuple.of(3), false
+                ), predicateResultSet);
+                assertTrue(queryEngine.hasPendingChanges());
+
+                queryEngine.flushChanges();
+                assertResults(Map.of(
+                                Tuple.of(0), true,
+                                Tuple.of(1), false,
+                                Tuple.of(2), true,
+                                Tuple.of(3), false
+                ), predicateResultSet);
+                assertFalse(queryEngine.hasPendingChanges());
+        }
+
+        @Test
+        void localSearchTest() {
+                var store = ModelStore.builder()
+                                .symbols(person)
+                                .with(QueryInterpreterAdapter.builder()
+                                        .defaultHint(new QueryEvaluationHint(null, QueryEvaluationHint.BackendRequirement.DEFAULT_SEARCH))
+                                        .queries(predicate))
+                                .build();
+
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var predicateResultSet = queryEngine.getResultSet(predicate);
+
+                assertResults(Map.of(
+                                Tuple.of(0), false,
+                                Tuple.of(1), false,
+                                Tuple.of(2), false,
+                                Tuple.of(3), false
+                ), predicateResultSet);
+                assertFalse(queryEngine.hasPendingChanges());
+
+                personInterpretation.put(Tuple.of(0), true);
+                personInterpretation.put(Tuple.of(1), true);
+
+                assertResults(Map.of(
+                                Tuple.of(0), true,
+                                Tuple.of(1), true,
+                                Tuple.of(2), false,
+                                Tuple.of(3), false
+                ), predicateResultSet);
+                assertFalse(queryEngine.hasPendingChanges());
+
+                personInterpretation.put(Tuple.of(1), false);
+                personInterpretation.put(Tuple.of(2), true);
+
+                assertResults(Map.of(
+                                Tuple.of(0), true,
+                                Tuple.of(1), false,
+                                Tuple.of(2), true,
+                                Tuple.of(3), false
+                ), predicateResultSet);
+                assertFalse(queryEngine.hasPendingChanges());
+        }
+
+        @Test
+        void unrelatedChangesTest() {
+                var asset = Symbol.of("Asset", 1);
+
+                var store = ModelStore.builder()
+                                .symbols(person, asset)
+                                .with(QueryInterpreterAdapter.builder()
+                                                .queries(predicate))
+                                .build();
+
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var assetInterpretation = model.getInterpretation(asset);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var predicateResultSet = queryEngine.getResultSet(predicate);
+
+                assertFalse(queryEngine.hasPendingChanges());
+
+                personInterpretation.put(Tuple.of(0), true);
+                personInterpretation.put(Tuple.of(1), true);
+
+                assetInterpretation.put(Tuple.of(1), true);
+                assetInterpretation.put(Tuple.of(2), true);
+
+                assertResults(Map.of(
+                                Tuple.of(0), false,
+                                Tuple.of(1), false,
+                                Tuple.of(2), false,
+                                Tuple.of(3), false,
+                                Tuple.of(4), false
+                ), predicateResultSet);
+                assertTrue(queryEngine.hasPendingChanges());
+
+                queryEngine.flushChanges();
+                assertResults(Map.of(
+                                Tuple.of(0), true,
+                                Tuple.of(1), true,
+                                Tuple.of(2), false,
+                                Tuple.of(3), false,
+                                Tuple.of(4), false
+                ), predicateResultSet);
+                assertFalse(queryEngine.hasPendingChanges());
+
+                assetInterpretation.put(Tuple.of(3), true);
+                assertFalse(queryEngine.hasPendingChanges());
+
+                assertResults(Map.of(
+                                Tuple.of(0), true,
+                                Tuple.of(1), true,
+                                Tuple.of(2), false,
+                                Tuple.of(3), false,
+                                Tuple.of(4), false
+                ), predicateResultSet);
+
+                queryEngine.flushChanges();
+                assertResults(Map.of(
+                                Tuple.of(0), true,
+                                Tuple.of(1), true,
+                                Tuple.of(2), false,
+                                Tuple.of(3), false,
+                                Tuple.of(4), false
+                ), predicateResultSet);
+                assertFalse(queryEngine.hasPendingChanges());
+        }
+
+        @Test
+        void tupleChangingChangeTest() {
+                var query = Query.of("TypeConstraint", Integer.class, (builder, p1, output) -> builder.clause(
+                                personView.call(p1),
+                                ageView.call(p1, output)
+                ));
+
+                var store = ModelStore.builder()
+                                .symbols(person, age)
+                                .with(QueryInterpreterAdapter.builder()
+                                                .queries(query))
+                                .build();
+
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var ageInterpretation = model.getInterpretation(age);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var queryResultSet = queryEngine.getResultSet(query);
+
+                personInterpretation.put(Tuple.of(0), true);
+
+                ageInterpretation.put(Tuple.of(0), 24);
+
+                queryEngine.flushChanges();
+                assertResults(Map.of(Tuple.of(0), 24), queryResultSet);
+
+                ageInterpretation.put(Tuple.of(0), 25);
+
+                queryEngine.flushChanges();
+                assertResults(Map.of(Tuple.of(0), 25), queryResultSet);
+
+                ageInterpretation.put(Tuple.of(0), null);
+
+                queryEngine.flushChanges();
+                assertNullableResults(Map.of(Tuple.of(0), Optional.empty()), queryResultSet);
+        }
+
+        @Test
+        void tuplePreservingUnchangedTest() {
+                var adultView = new FilteredView<>(age, "adult", n -> n != null && n >= 18);
+
+                var query = Query.of("TypeConstraint", (builder, p1) -> builder.clause(
+                                personView.call(p1),
+                                adultView.call(p1)
+                ));
+
+                var store = ModelStore.builder()
+                                .symbols(person, age)
+                                .with(QueryInterpreterAdapter.builder()
+                                                .queries(query))
+                                .build();
+
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var ageInterpretation = model.getInterpretation(age);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var queryResultSet = queryEngine.getResultSet(query);
+
+                personInterpretation.put(Tuple.of(0), true);
+
+                ageInterpretation.put(Tuple.of(0), 24);
+
+                queryEngine.flushChanges();
+                assertResults(Map.of(Tuple.of(0), true), queryResultSet);
+
+                ageInterpretation.put(Tuple.of(0), 25);
+
+                queryEngine.flushChanges();
+                assertResults(Map.of(Tuple.of(0), true), queryResultSet);
+
+                ageInterpretation.put(Tuple.of(0), 17);
+
+                queryEngine.flushChanges();
+                assertResults(Map.of(Tuple.of(0), false), queryResultSet);
+        }
+
+        @Test
+        void commitAfterFlushTest() {
+                var store = ModelStore.builder()
+                                .symbols(person)
+                                .with(QueryInterpreterAdapter.builder()
+                                                .queries(predicate))
+                                .build();
+
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var predicateResultSet = queryEngine.getResultSet(predicate);
+
+                personInterpretation.put(Tuple.of(0), true);
+                personInterpretation.put(Tuple.of(1), true);
+
+                queryEngine.flushChanges();
+                assertResults(Map.of(
+                                Tuple.of(0), true,
+                                Tuple.of(1), true,
+                                Tuple.of(2), false,
+                                Tuple.of(3), false
+                ), predicateResultSet);
+
+                var state1 = model.commit();
+
+                personInterpretation.put(Tuple.of(1), false);
+                personInterpretation.put(Tuple.of(2), true);
+
+                queryEngine.flushChanges();
+                assertResults(Map.of(
+                                Tuple.of(0), true,
+                                Tuple.of(1), false,
+                                Tuple.of(2), true,
+                                Tuple.of(3), false
+                ), predicateResultSet);
+
+                model.restore(state1);
+
+                assertFalse(queryEngine.hasPendingChanges());
+                assertResults(Map.of(
+                                Tuple.of(0), true,
+                                Tuple.of(1), true,
+                                Tuple.of(2), false,
+                                Tuple.of(3), false
+                ), predicateResultSet);
+        }
+
+        @Test
+        void commitWithoutFlushTest() {
+                var store = ModelStore.builder()
+                                .symbols(person)
+                                .with(QueryInterpreterAdapter.builder()
+                                                .queries(predicate))
+                                .build();
+
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var predicateResultSet = queryEngine.getResultSet(predicate);
+
+                personInterpretation.put(Tuple.of(0), true);
+                personInterpretation.put(Tuple.of(1), true);
+
+                assertResults(Map.of(), predicateResultSet);
+                assertTrue(queryEngine.hasPendingChanges());
+
+                var state1 = model.commit();
+
+                personInterpretation.put(Tuple.of(1), false);
+                personInterpretation.put(Tuple.of(2), true);
+
+                assertResults(Map.of(), predicateResultSet);
+                assertTrue(queryEngine.hasPendingChanges());
+
+                model.restore(state1);
+
+                assertResults(Map.of(
+                                Tuple.of(0), true,
+                                Tuple.of(1), true,
+                                Tuple.of(2), false,
+                                Tuple.of(3), false
+                ), predicateResultSet);
+                assertFalse(queryEngine.hasPendingChanges());
+        }
+}
diff --git a/subprojects/store-query-interpreter/src/test/java/tools/refinery/store/query/interpreter/StronglyConnectedComponentsTest.java b/subprojects/store-query-interpreter/src/test/java/tools/refinery/store/query/interpreter/StronglyConnectedComponentsTest.java
new file mode 100644
index 00000000..edbd9aff
--- /dev/null
+++ b/subprojects/store-query-interpreter/src/test/java/tools/refinery/store/query/interpreter/StronglyConnectedComponentsTest.java
@@ -0,0 +1,261 @@
+/*
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.interpreter;
+
+import org.junit.jupiter.api.Test;
+import tools.refinery.store.model.ModelStore;
+import tools.refinery.store.query.ModelQueryAdapter;
+import tools.refinery.store.query.dnf.Query;
+import tools.refinery.store.query.literal.Connectivity;
+import tools.refinery.store.query.literal.RepresentativeElectionLiteral;
+import tools.refinery.store.query.view.AnySymbolView;
+import tools.refinery.store.query.view.KeyOnlyView;
+import tools.refinery.store.representation.Symbol;
+import tools.refinery.store.tuple.Tuple;
+
+import java.util.List;
+import java.util.Map;
+
+import static org.hamcrest.MatcherAssert.assertThat;
+import static org.hamcrest.Matchers.is;
+import static tools.refinery.store.query.interpreter.tests.QueryAssertions.assertResults;
+
+class StronglyConnectedComponentsTest {
+        private static final Symbol<Boolean> friend = Symbol.of("friend", 2);
+        private static final AnySymbolView friendView = new KeyOnlyView<>(friend);
+
+        @Test
+        void symbolViewTest() {
+                var query = Query.of("SymbolViewRepresentative", (builder, p1, p2) -> builder
+                                .clause(v1 -> List.of(
+                                                new RepresentativeElectionLiteral(Connectivity.STRONG, friendView, p1, v1),
+                                                new RepresentativeElectionLiteral(Connectivity.STRONG, friendView, p2, v1)
+                                )));
+
+                var store = ModelStore.builder()
+                                .symbols(friend)
+                                .with(QueryInterpreterAdapter.builder()
+                                                .queries(query))
+                                .build();
+
+                var model = store.createEmptyModel();
+                var friendInterpretation = model.getInterpretation(friend);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var resultSet = queryEngine.getResultSet(query);
+
+                friendInterpretation.put(Tuple.of(0, 1), true);
+                friendInterpretation.put(Tuple.of(1, 0), true);
+                friendInterpretation.put(Tuple.of(1, 2), true);
+                queryEngine.flushChanges();
+
+                assertResults(Map.of(
+                                Tuple.of(0, 0), true,
+                                Tuple.of(0, 1), true,
+                                Tuple.of(1, 0), true,
+                                Tuple.of(1, 1), true,
+                                Tuple.of(2, 2), true
+                ), resultSet);
+        }
+
+        @Test
+        void symbolViewInsertTest() {
+                var query = Query.of("SymbolViewRepresentative", (builder, p1, p2) -> builder
+                                .clause(v1 -> List.of(
+                                                new RepresentativeElectionLiteral(Connectivity.STRONG, friendView, p1, v1),
+                                                new RepresentativeElectionLiteral(Connectivity.STRONG, friendView, p2, v1)
+                                )));
+
+                var store = ModelStore.builder()
+                                .symbols(friend)
+                                .with(QueryInterpreterAdapter.builder()
+                                                .queries(query))
+                                .build();
+
+                var model = store.createEmptyModel();
+                var friendInterpretation = model.getInterpretation(friend);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var resultSet = queryEngine.getResultSet(query);
+
+                friendInterpretation.put(Tuple.of(0, 1), true);
+                friendInterpretation.put(Tuple.of(1, 0), true);
+                friendInterpretation.put(Tuple.of(1, 2), true);
+                queryEngine.flushChanges();
+
+                friendInterpretation.put(Tuple.of(2, 0), true);
+                friendInterpretation.put(Tuple.of(0, 3), true);
+                queryEngine.flushChanges();
+
+                assertResults(Map.of(
+                                Tuple.of(0, 0), true,
+                                Tuple.of(0, 1), true,
+                                Tuple.of(0, 2), true,
+                                Tuple.of(1, 1), true,
+                                Tuple.of(1, 0), true,
+                                Tuple.of(1, 2), true,
+                                Tuple.of(2, 0), true,
+                                Tuple.of(2, 1), true,
+                                Tuple.of(2, 2), true,
+                                Tuple.of(3, 3), true
+                ), resultSet);
+        }
+
+        @Test
+        void symbolViewDeleteTest() {
+                var query = Query.of("SymbolViewRepresentative", (builder, p1, p2) -> builder
+                                .clause(v1 -> List.of(
+                                                new RepresentativeElectionLiteral(Connectivity.STRONG, friendView, p1, v1),
+                                                new RepresentativeElectionLiteral(Connectivity.STRONG, friendView, p2, v1)
+                                )));
+
+                var store = ModelStore.builder()
+                                .symbols(friend)
+                                .with(QueryInterpreterAdapter.builder()
+                                                .queries(query))
+                                .build();
+
+                var model = store.createEmptyModel();
+                var friendInterpretation = model.getInterpretation(friend);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var resultSet = queryEngine.getResultSet(query);
+
+                friendInterpretation.put(Tuple.of(0, 1), true);
+                friendInterpretation.put(Tuple.of(1, 0), true);
+                friendInterpretation.put(Tuple.of(1, 2), true);
+                queryEngine.flushChanges();
+
+                friendInterpretation.put(Tuple.of(1, 0), false);
+                friendInterpretation.put(Tuple.of(1, 2), false);
+                queryEngine.flushChanges();
+
+                assertResults(Map.of(
+                                Tuple.of(0, 0), true,
+                                Tuple.of(1, 1), true
+                ), resultSet);
+        }
+
+        @Test
+        void diagonalSymbolViewTest() {
+                var person = Symbol.of("Person", 1);
+                var personView = new KeyOnlyView<>(person);
+
+                var query = Query.of("SymbolViewRepresentative", (builder, p1) -> builder
+                                .clause(
+                                                personView.call(p1),
+                                                new RepresentativeElectionLiteral(Connectivity.STRONG, friendView, p1, p1)
+                                ));
+
+                var store = ModelStore.builder()
+                                .symbols(person, friend)
+                                .with(QueryInterpreterAdapter.builder()
+                                                .queries(query))
+                                .build();
+
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var friendInterpretation = model.getInterpretation(friend);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var resultSet = queryEngine.getResultSet(query);
+
+                personInterpretation.put(Tuple.of(0), true);
+                personInterpretation.put(Tuple.of(1), true);
+                personInterpretation.put(Tuple.of(2), true);
+
+                friendInterpretation.put(Tuple.of(0, 1), true);
+                friendInterpretation.put(Tuple.of(1, 0), true);
+                friendInterpretation.put(Tuple.of(1, 2), true);
+                queryEngine.flushChanges();
+
+                assertThat(resultSet.size(), is(2));
+                assertThat(resultSet.get(Tuple.of(2)), is(true));
+        }
+
+        @Test
+        void diagonalDnfTest() {
+                var person = Symbol.of("Person", 1);
+                var personView = new KeyOnlyView<>(person);
+
+                var subQuery = Query.of("SubQuery", (builder, p1, p2) -> builder
+                                .clause(
+                                                personView.call(p1),
+                                                personView.call(p2),
+                                                friendView.call(p1, p2)
+                                ))
+                                .getDnf();
+                var query = Query.of("SymbolViewRepresentative", (builder, p1) -> builder
+                                .clause(
+                                                personView.call(p1),
+                                                new RepresentativeElectionLiteral(Connectivity.STRONG, subQuery, p1, p1)
+                                ));
+
+                var store = ModelStore.builder()
+                                .symbols(person, friend)
+                                .with(QueryInterpreterAdapter.builder()
+                                                .queries(query))
+                                .build();
+
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var friendInterpretation = model.getInterpretation(friend);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var resultSet = queryEngine.getResultSet(query);
+
+                personInterpretation.put(Tuple.of(0), true);
+                personInterpretation.put(Tuple.of(1), true);
+                personInterpretation.put(Tuple.of(2), true);
+
+                friendInterpretation.put(Tuple.of(0, 1), true);
+                friendInterpretation.put(Tuple.of(1, 0), true);
+                friendInterpretation.put(Tuple.of(1, 2), true);
+                queryEngine.flushChanges();
+
+                assertThat(resultSet.size(), is(2));
+                assertThat(resultSet.get(Tuple.of(2)), is(true));
+        }
+
+        @Test
+        void loopTest() {
+                var query = Query.of("SymbolViewRepresentative", (builder, p1, p2) -> builder
+                                .clause(v1 -> List.of(
+                                                new RepresentativeElectionLiteral(Connectivity.STRONG, friendView, p1, v1),
+                                                new RepresentativeElectionLiteral(Connectivity.STRONG, friendView, p2, v1)
+                                )));
+
+                var store = ModelStore.builder()
+                                .symbols(friend)
+                                .with(QueryInterpreterAdapter.builder()
+                                                .queries(query))
+                                .build();
+
+                var model = store.createEmptyModel();
+                var friendInterpretation = model.getInterpretation(friend);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var resultSet = queryEngine.getResultSet(query);
+
+                friendInterpretation.put(Tuple.of(0, 1), true);
+                friendInterpretation.put(Tuple.of(1, 2), true);
+                friendInterpretation.put(Tuple.of(2, 3), true);
+                friendInterpretation.put(Tuple.of(3, 0), true);
+                friendInterpretation.put(Tuple.of(3, 4), true);
+                queryEngine.flushChanges();
+
+                assertThat(resultSet.get(Tuple.of(0, 1)), is(true));
+                assertThat(resultSet.get(Tuple.of(1, 2)), is(true));
+                assertThat(resultSet.get(Tuple.of(2, 3)), is(true));
+                assertThat(resultSet.get(Tuple.of(3, 0)), is(true));
+                assertThat(resultSet.get(Tuple.of(3, 4)), is(false));
+
+                friendInterpretation.put(Tuple.of(2, 3), false);
+                queryEngine.flushChanges();
+
+                assertThat(resultSet.get(Tuple.of(0, 1)), is(false));
+                assertThat(resultSet.get(Tuple.of(0, 2)), is(false));
+                assertThat(resultSet.get(Tuple.of(0, 3)), is(false));
+                assertThat(resultSet.get(Tuple.of(1, 2)), is(false));
+                assertThat(resultSet.get(Tuple.of(2, 3)), is(false));
+                assertThat(resultSet.get(Tuple.of(3, 0)), is(false));
+                assertThat(resultSet.get(Tuple.of(3, 4)), is(false));
+        }
+}
diff --git a/subprojects/store-query-interpreter/src/test/java/tools/refinery/store/query/interpreter/WeaklyConnectedComponentsTest.java b/subprojects/store-query-interpreter/src/test/java/tools/refinery/store/query/interpreter/WeaklyConnectedComponentsTest.java
new file mode 100644
index 00000000..3fc85480
--- /dev/null
+++ b/subprojects/store-query-interpreter/src/test/java/tools/refinery/store/query/interpreter/WeaklyConnectedComponentsTest.java
@@ -0,0 +1,188 @@
+/*
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.interpreter;
+
+import org.junit.jupiter.api.Test;
+import tools.refinery.store.model.ModelStore;
+import tools.refinery.store.query.ModelQueryAdapter;
+import tools.refinery.store.query.dnf.Query;
+import tools.refinery.store.query.literal.Connectivity;
+import tools.refinery.store.query.literal.RepresentativeElectionLiteral;
+import tools.refinery.store.query.view.AnySymbolView;
+import tools.refinery.store.query.view.KeyOnlyView;
+import tools.refinery.store.representation.Symbol;
+import tools.refinery.store.tuple.Tuple;
+
+import java.util.List;
+import java.util.Map;
+
+import static org.hamcrest.MatcherAssert.assertThat;
+import static org.hamcrest.Matchers.is;
+import static tools.refinery.store.query.interpreter.tests.QueryAssertions.assertResults;
+
+class WeaklyConnectedComponentsTest {
+        private static final Symbol<Boolean> friend = Symbol.of("friend", 2);
+        private static final AnySymbolView friendView = new KeyOnlyView<>(friend);
+
+        @Test
+        void symbolViewTest() {
+                var query = Query.of("SymbolViewRepresentative", (builder, p1, p2) -> builder
+                                .clause(v1 -> List.of(
+                                                new RepresentativeElectionLiteral(Connectivity.WEAK, friendView, p1, v1),
+                                                new RepresentativeElectionLiteral(Connectivity.WEAK, friendView, p2, v1)
+                                )));
+
+                var store = ModelStore.builder()
+                                .symbols(friend)
+                                .with(QueryInterpreterAdapter.builder()
+                                                .queries(query))
+                                .build();
+
+                var model = store.createEmptyModel();
+                var friendInterpretation = model.getInterpretation(friend);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var resultSet = queryEngine.getResultSet(query);
+
+                friendInterpretation.put(Tuple.of(0, 1), true);
+                friendInterpretation.put(Tuple.of(1, 0), true);
+                friendInterpretation.put(Tuple.of(2, 3), true);
+                queryEngine.flushChanges();
+
+                assertResults(Map.of(
+                                Tuple.of(0, 0), true,
+                                Tuple.of(0, 1), true,
+                                Tuple.of(1, 0), true,
+                                Tuple.of(1, 1), true,
+                                Tuple.of(2, 2), true,
+                                Tuple.of(2, 3), true,
+                                Tuple.of(3, 2), true,
+                                Tuple.of(3, 3), true
+                ), resultSet);
+        }
+
+        @Test
+        void symbolViewUpdateTest() {
+                var query = Query.of("SymbolViewRepresentative", (builder, p1, p2) -> builder
+                                .clause(v1 -> List.of(
+                                                new RepresentativeElectionLiteral(Connectivity.WEAK, friendView, p1, v1),
+                                                new RepresentativeElectionLiteral(Connectivity.WEAK, friendView, p2, v1)
+                                )));
+
+                var store = ModelStore.builder()
+                                .symbols(friend)
+                                .with(QueryInterpreterAdapter.builder()
+                                                .queries(query))
+                                .build();
+
+                var model = store.createEmptyModel();
+                var friendInterpretation = model.getInterpretation(friend);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var resultSet = queryEngine.getResultSet(query);
+
+                friendInterpretation.put(Tuple.of(0, 1), true);
+                friendInterpretation.put(Tuple.of(1, 0), true);
+                friendInterpretation.put(Tuple.of(2, 3), true);
+                queryEngine.flushChanges();
+
+                friendInterpretation.put(Tuple.of(2, 3), false);
+                friendInterpretation.put(Tuple.of(1, 0), false);
+                friendInterpretation.put(Tuple.of(1, 2), true);
+                queryEngine.flushChanges();
+
+                assertResults(Map.of(
+                                Tuple.of(0, 0), true,
+                                Tuple.of(0, 1), true,
+                                Tuple.of(0, 2), true,
+                                Tuple.of(1, 0), true,
+                                Tuple.of(1, 1), true,
+                                Tuple.of(1, 2), true,
+                                Tuple.of(2, 0), true,
+                                Tuple.of(2, 1), true,
+                                Tuple.of(2, 2), true
+                ), resultSet);
+        }
+
+        @Test
+        void diagonalSymbolViewTest() {
+                var person = Symbol.of("Person", 1);
+                var personView = new KeyOnlyView<>(person);
+
+                var query = Query.of("SymbolViewRepresentative", (builder, p1) -> builder
+                                .clause(
+                                                personView.call(p1),
+                                                new RepresentativeElectionLiteral(Connectivity.WEAK, friendView, p1, p1)
+                                ));
+
+                var store = ModelStore.builder()
+                                .symbols(person, friend)
+                                .with(QueryInterpreterAdapter.builder()
+                                                .queries(query))
+                                .build();
+
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var friendInterpretation = model.getInterpretation(friend);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var resultSet = queryEngine.getResultSet(query);
+
+                personInterpretation.put(Tuple.of(0), true);
+                personInterpretation.put(Tuple.of(1), true);
+                personInterpretation.put(Tuple.of(2), true);
+                personInterpretation.put(Tuple.of(3), true);
+
+                friendInterpretation.put(Tuple.of(0, 1), true);
+                friendInterpretation.put(Tuple.of(1, 0), true);
+                friendInterpretation.put(Tuple.of(2, 3), true);
+                queryEngine.flushChanges();
+
+                assertThat(resultSet.size(), is(2));
+                assertThat(resultSet.get(Tuple.of(2)), is(true));
+        }
+
+        @Test
+        void diagonalDnfTest() {
+                var person = Symbol.of("Person", 1);
+                var personView = new KeyOnlyView<>(person);
+
+                var subQuery = Query.of("SubQuery", (builder, p1, p2) -> builder
+                                .clause(
+                                                personView.call(p1),
+                                                personView.call(p2),
+                                                friendView.call(p1, p2)
+                                ))
+                                .getDnf();
+                var query = Query.of("SymbolViewRepresentative", (builder, p1) -> builder
+                                .clause(
+                                                personView.call(p1),
+                                                new RepresentativeElectionLiteral(Connectivity.WEAK, subQuery, p1, p1)
+                                ));
+
+                var store = ModelStore.builder()
+                                .symbols(person, friend)
+                                .with(QueryInterpreterAdapter.builder()
+                                                .queries(query))
+                                .build();
+
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var friendInterpretation = model.getInterpretation(friend);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var resultSet = queryEngine.getResultSet(query);
+
+                personInterpretation.put(Tuple.of(0), true);
+                personInterpretation.put(Tuple.of(1), true);
+                personInterpretation.put(Tuple.of(2), true);
+                personInterpretation.put(Tuple.of(3), true);
+
+                friendInterpretation.put(Tuple.of(0, 1), true);
+                friendInterpretation.put(Tuple.of(1, 0), true);
+                friendInterpretation.put(Tuple.of(2, 3), true);
+                queryEngine.flushChanges();
+
+                assertThat(resultSet.size(), is(2));
+                assertThat(resultSet.get(Tuple.of(2)), is(true));
+        }
+}
diff --git a/subprojects/store-query-interpreter/src/test/java/tools/refinery/store/query/interpreter/internal/matcher/MatcherUtilsTest.java b/subprojects/store-query-interpreter/src/test/java/tools/refinery/store/query/interpreter/internal/matcher/MatcherUtilsTest.java
new file mode 100644
index 00000000..1c8044ea
--- /dev/null
+++ b/subprojects/store-query-interpreter/src/test/java/tools/refinery/store/query/interpreter/internal/matcher/MatcherUtilsTest.java
@@ -0,0 +1,239 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.interpreter.internal.matcher;
+
+import tools.refinery.interpreter.matchers.tuple.*;
+import org.junit.jupiter.api.Test;
+import tools.refinery.store.tuple.Tuple;
+import tools.refinery.store.tuple.*;
+
+import java.util.List;
+
+import static org.hamcrest.MatcherAssert.assertThat;
+import static org.hamcrest.Matchers.*;
+import static org.junit.jupiter.api.Assertions.assertThrows;
+
+class MatcherUtilsTest {
+        @Test
+        void toViatra0Test() {
+                var viatraTuple = MatcherUtils.toViatraTuple(Tuple.of());
+                assertThat(viatraTuple.getSize(), is(0));
+                assertThat(viatraTuple, instanceOf(FlatTuple0.class));
+        }
+
+        @Test
+        void toViatra1Test() {
+                var viatraTuple = MatcherUtils.toViatraTuple(Tuple.of(2));
+                assertThat(viatraTuple.getSize(), is(1));
+                assertThat(viatraTuple.get(0), is(Tuple.of(2)));
+                assertThat(viatraTuple, instanceOf(FlatTuple1.class));
+        }
+
+        @Test
+        void toViatra2Test() {
+                var viatraTuple = MatcherUtils.toViatraTuple(Tuple.of(2, 3));
+                assertThat(viatraTuple.getSize(), is(2));
+                assertThat(viatraTuple.get(0), is(Tuple.of(2)));
+                assertThat(viatraTuple.get(1), is(Tuple.of(3)));
+                assertThat(viatraTuple, instanceOf(FlatTuple2.class));
+        }
+
+        @Test
+        void toViatra3Test() {
+                var viatraTuple = MatcherUtils.toViatraTuple(Tuple.of(2, 3, 5));
+                assertThat(viatraTuple.getSize(), is(3));
+                assertThat(viatraTuple.get(0), is(Tuple.of(2)));
+                assertThat(viatraTuple.get(1), is(Tuple.of(3)));
+                assertThat(viatraTuple.get(2), is(Tuple.of(5)));
+                assertThat(viatraTuple, instanceOf(FlatTuple3.class));
+        }
+
+        @Test
+        void toViatra4Test() {
+                var viatraTuple = MatcherUtils.toViatraTuple(Tuple.of(2, 3, 5, 8));
+                assertThat(viatraTuple.getSize(), is(4));
+                assertThat(viatraTuple.get(0), is(Tuple.of(2)));
+                assertThat(viatraTuple.get(1), is(Tuple.of(3)));
+                assertThat(viatraTuple.get(2), is(Tuple.of(5)));
+                assertThat(viatraTuple.get(3), is(Tuple.of(8)));
+                assertThat(viatraTuple, instanceOf(FlatTuple4.class));
+        }
+
+        @Test
+        void toViatra5Test() {
+                var viatraTuple = MatcherUtils.toViatraTuple(Tuple.of(2, 3, 5, 8, 13));
+                assertThat(viatraTuple.getSize(), is(5));
+                assertThat(viatraTuple.get(0), is(Tuple.of(2)));
+                assertThat(viatraTuple.get(1), is(Tuple.of(3)));
+                assertThat(viatraTuple.get(2), is(Tuple.of(5)));
+                assertThat(viatraTuple.get(3), is(Tuple.of(8)));
+                assertThat(viatraTuple.get(4), is(Tuple.of(13)));
+                assertThat(viatraTuple, instanceOf(FlatTuple.class));
+        }
+
+        @Test
+        void toRefinery0Test() {
+                var refineryTuple = MatcherUtils.toRefineryTuple(Tuples.flatTupleOf());
+                assertThat(refineryTuple.getSize(), is(0));
+                assertThat(refineryTuple, instanceOf(Tuple0.class));
+        }
+
+        @Test
+        void toRefinery1Test() {
+                var refineryTuple = MatcherUtils.toRefineryTuple(Tuples.flatTupleOf(Tuple.of(2)));
+                assertThat(refineryTuple.getSize(), is(1));
+                assertThat(refineryTuple.get(0), is(2));
+                assertThat(refineryTuple, instanceOf(Tuple1.class));
+        }
+
+        @Test
+        void toRefinery2Test() {
+                var refineryTuple = MatcherUtils.toRefineryTuple(Tuples.flatTupleOf(Tuple.of(2), Tuple.of(3)));
+                assertThat(refineryTuple.getSize(), is(2));
+                assertThat(refineryTuple.get(0), is(2));
+                assertThat(refineryTuple.get(1), is(3));
+                assertThat(refineryTuple, instanceOf(Tuple2.class));
+        }
+
+        @Test
+        void toRefinery3Test() {
+                var refineryTuple = MatcherUtils.toRefineryTuple(Tuples.flatTupleOf(Tuple.of(2), Tuple.of(3), Tuple.of(5)));
+                assertThat(refineryTuple.getSize(), is(3));
+                assertThat(refineryTuple.get(0), is(2));
+                assertThat(refineryTuple.get(1), is(3));
+                assertThat(refineryTuple.get(2), is(5));
+                assertThat(refineryTuple, instanceOf(Tuple3.class));
+        }
+
+        @Test
+        void toRefinery4Test() {
+                var refineryTuple = MatcherUtils.toRefineryTuple(Tuples.flatTupleOf(Tuple.of(2), Tuple.of(3), Tuple.of(5),
+                                Tuple.of(8)));
+                assertThat(refineryTuple.getSize(), is(4));
+                assertThat(refineryTuple.get(0), is(2));
+                assertThat(refineryTuple.get(1), is(3));
+                assertThat(refineryTuple.get(2), is(5));
+                assertThat(refineryTuple.get(3), is(8));
+                assertThat(refineryTuple, instanceOf(Tuple4.class));
+        }
+
+        @Test
+        void toRefinery5Test() {
+                var refineryTuple = MatcherUtils.toRefineryTuple(Tuples.flatTupleOf(Tuple.of(2), Tuple.of(3), Tuple.of(5),
+                                Tuple.of(8), Tuple.of(13)));
+                assertThat(refineryTuple.getSize(), is(5));
+                assertThat(refineryTuple.get(0), is(2));
+                assertThat(refineryTuple.get(1), is(3));
+                assertThat(refineryTuple.get(2), is(5));
+                assertThat(refineryTuple.get(3), is(8));
+                assertThat(refineryTuple.get(4), is(13));
+                assertThat(refineryTuple, instanceOf(TupleN.class));
+        }
+
+        @Test
+        void toRefineryInvalidValueTest() {
+                var viatraTuple = Tuples.flatTupleOf(Tuple.of(2), -98);
+                assertThrows(IllegalArgumentException.class, () -> MatcherUtils.toRefineryTuple(viatraTuple));
+        }
+
+        @Test
+        void keyToRefinery0Test() {
+                var refineryTuple = MatcherUtils.keyToRefineryTuple(Tuples.flatTupleOf(-99));
+                assertThat(refineryTuple.getSize(), is(0));
+                assertThat(refineryTuple, instanceOf(Tuple0.class));
+        }
+
+        @Test
+        void keyToRefinery1Test() {
+                var refineryTuple = MatcherUtils.keyToRefineryTuple(Tuples.flatTupleOf(Tuple.of(2), -99));
+                assertThat(refineryTuple.getSize(), is(1));
+                assertThat(refineryTuple.get(0), is(2));
+                assertThat(refineryTuple, instanceOf(Tuple1.class));
+        }
+
+        @Test
+        void keyToRefinery2Test() {
+                var refineryTuple = MatcherUtils.keyToRefineryTuple(Tuples.flatTupleOf(Tuple.of(2), Tuple.of(3), -99));
+                assertThat(refineryTuple.getSize(), is(2));
+                assertThat(refineryTuple.get(0), is(2));
+                assertThat(refineryTuple.get(1), is(3));
+                assertThat(refineryTuple, instanceOf(Tuple2.class));
+        }
+
+        @Test
+        void keyToRefinery3Test() {
+                var refineryTuple = MatcherUtils.keyToRefineryTuple(Tuples.flatTupleOf(Tuple.of(2), Tuple.of(3), Tuple.of(5),
+                                -99));
+                assertThat(refineryTuple.getSize(), is(3));
+                assertThat(refineryTuple.get(0), is(2));
+                assertThat(refineryTuple.get(1), is(3));
+                assertThat(refineryTuple.get(2), is(5));
+                assertThat(refineryTuple, instanceOf(Tuple3.class));
+        }
+
+        @Test
+        void keyToRefinery4Test() {
+                var refineryTuple = MatcherUtils.keyToRefineryTuple(Tuples.flatTupleOf(Tuple.of(2), Tuple.of(3), Tuple.of(5),
+                                Tuple.of(8), -99));
+                assertThat(refineryTuple.getSize(), is(4));
+                assertThat(refineryTuple.get(0), is(2));
+                assertThat(refineryTuple.get(1), is(3));
+                assertThat(refineryTuple.get(2), is(5));
+                assertThat(refineryTuple.get(3), is(8));
+                assertThat(refineryTuple, instanceOf(Tuple4.class));
+        }
+
+        @Test
+        void keyToRefinery5Test() {
+                var refineryTuple = MatcherUtils.keyToRefineryTuple(Tuples.flatTupleOf(Tuple.of(2), Tuple.of(3), Tuple.of(5),
+                                Tuple.of(8), Tuple.of(13), -99));
+                assertThat(refineryTuple.getSize(), is(5));
+                assertThat(refineryTuple.get(0), is(2));
+                assertThat(refineryTuple.get(1), is(3));
+                assertThat(refineryTuple.get(2), is(5));
+                assertThat(refineryTuple.get(3), is(8));
+                assertThat(refineryTuple.get(4), is(13));
+                assertThat(refineryTuple, instanceOf(TupleN.class));
+        }
+
+        @Test
+        void keyToRefineryTooShortTest() {
+                var viatraTuple = Tuples.flatTupleOf();
+                assertThrows(IllegalArgumentException.class, () -> MatcherUtils.keyToRefineryTuple(viatraTuple));
+        }
+
+        @Test
+        void keyToRefineryInvalidValueTest() {
+                var viatraTuple = Tuples.flatTupleOf(Tuple.of(2), -98, -99);
+                assertThrows(IllegalArgumentException.class, () -> MatcherUtils.keyToRefineryTuple(viatraTuple));
+        }
+
+        @Test
+        void getSingleValueTest() {
+                var value = MatcherUtils.getSingleValue(List.of(Tuples.flatTupleOf(Tuple.of(2), -99)));
+                assertThat(value, is(-99));
+        }
+
+        // Static analysis accurately determines that the result is always {@code null}, but we check anyways.
+        @SuppressWarnings("ConstantValue")
+        @Test
+        void getSingleValueNullTest() {
+                var value = MatcherUtils.getSingleValue((Iterable<? extends ITuple>) null);
+                assertThat(value, nullValue());
+        }
+
+        @Test
+        void getSingleValueEmptyTest() {
+                var value = MatcherUtils.getSingleValue(List.of());
+                assertThat(value, nullValue());
+        }
+
+        @Test
+        void getSingleValueMultipleTest() {
+                var viatraTuples = List.of(Tuples.flatTupleOf(Tuple.of(2), -98), Tuples.flatTupleOf(Tuple.of(2), -99));
+                assertThrows(IllegalStateException.class, () -> MatcherUtils.getSingleValue(viatraTuples));
+        }
+}
diff --git a/subprojects/store-query-interpreter/src/test/java/tools/refinery/store/query/interpreter/tests/QueryAssertions.java b/subprojects/store-query-interpreter/src/test/java/tools/refinery/store/query/interpreter/tests/QueryAssertions.java
new file mode 100644
index 00000000..c4659a98
--- /dev/null
+++ b/subprojects/store-query-interpreter/src/test/java/tools/refinery/store/query/interpreter/tests/QueryAssertions.java
@@ -0,0 +1,57 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.interpreter.tests;
+
+import org.junit.jupiter.api.function.Executable;
+import tools.refinery.store.query.resultset.ResultSet;
+import tools.refinery.store.tuple.Tuple;
+
+import java.util.*;
+
+import static org.hamcrest.MatcherAssert.assertThat;
+import static org.hamcrest.Matchers.is;
+import static org.hamcrest.Matchers.nullValue;
+import static org.junit.jupiter.api.Assertions.assertAll;
+
+public final class QueryAssertions {
+        private QueryAssertions() {
+                throw new IllegalStateException("This is a static utility class and should not be instantiated directly");
+        }
+
+        public static <T> void assertNullableResults(Map<Tuple, Optional<T>> expected, ResultSet<T> resultSet) {
+                var nullableValuesMap = new LinkedHashMap<Tuple, T>(expected.size());
+                for (var entry : expected.entrySet()) {
+                        nullableValuesMap.put(entry.getKey(), entry.getValue().orElse(null));
+                }
+                assertResults(nullableValuesMap, resultSet);
+        }
+
+        public static <T> void assertResults(Map<Tuple, T> expected, ResultSet<T> resultSet) {
+                var defaultValue = resultSet.getCanonicalQuery().defaultValue();
+                var filteredExpected = new LinkedHashMap<Tuple, T>();
+                var executables = new ArrayList<Executable>();
+                for (var entry : expected.entrySet()) {
+                        var key = entry.getKey();
+                        var value = entry.getValue();
+                        if (!Objects.equals(value, defaultValue)) {
+                                filteredExpected.put(key, value);
+                        }
+                        executables.add(() -> assertThat("value for key " + key,resultSet.get(key), is(value)));
+                }
+                executables.add(() -> assertThat("results size", resultSet.size(), is(filteredExpected.size())));
+
+                var actual = new LinkedHashMap<Tuple, T>();
+                var cursor = resultSet.getAll();
+                while (cursor.move()) {
+                        var key = cursor.getKey();
+                        var previous = actual.put(key, cursor.getValue());
+                        assertThat("duplicate value for key " + key, previous, nullValue());
+                }
+                executables.add(() -> assertThat("results cursor", actual, is(filteredExpected)));
+
+                assertAll(executables);
+        }
+}
diff --git a/subprojects/store-query-interpreter/src/test/java/tools/refinery/store/query/interpreter/tests/QueryBackendHint.java b/subprojects/store-query-interpreter/src/test/java/tools/refinery/store/query/interpreter/tests/QueryBackendHint.java
new file mode 100644
index 00000000..f9d5b219
--- /dev/null
+++ b/subprojects/store-query-interpreter/src/test/java/tools/refinery/store/query/interpreter/tests/QueryBackendHint.java
@@ -0,0 +1,27 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.interpreter.tests;
+
+import tools.refinery.interpreter.matchers.backend.QueryEvaluationHint;
+
+/**
+ * Overrides {@link QueryEvaluationHint#toString()} for pretty names in parametric test names.
+ */
+class QueryBackendHint extends QueryEvaluationHint {
+        public QueryBackendHint(BackendRequirement backendRequirementType) {
+                super(null, backendRequirementType);
+        }
+
+        @Override
+        public String toString() {
+                return switch (getQueryBackendRequirementType()) {
+                        case UNSPECIFIED -> "default";
+                        case DEFAULT_CACHING -> "incremental";
+                        case DEFAULT_SEARCH -> "localSearch";
+                        default -> throw new IllegalStateException("Unknown BackendRequirement");
+                };
+        }
+}
diff --git a/subprojects/store-query-interpreter/src/test/java/tools/refinery/store/query/interpreter/tests/QueryEngineTest.java b/subprojects/store-query-interpreter/src/test/java/tools/refinery/store/query/interpreter/tests/QueryEngineTest.java
new file mode 100644
index 00000000..a5cc7e9c
--- /dev/null
+++ b/subprojects/store-query-interpreter/src/test/java/tools/refinery/store/query/interpreter/tests/QueryEngineTest.java
@@ -0,0 +1,21 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.interpreter.tests;
+
+import org.junit.jupiter.params.ParameterizedTest;
+import org.junit.jupiter.params.provider.ArgumentsSource;
+
+import java.lang.annotation.ElementType;
+import java.lang.annotation.Retention;
+import java.lang.annotation.RetentionPolicy;
+import java.lang.annotation.Target;
+
+@ParameterizedTest(name = "backend = {0}")
+@ArgumentsSource(QueryEvaluationHintSource.class)
+@Target(ElementType.METHOD)
+@Retention(RetentionPolicy.RUNTIME)
+public @interface QueryEngineTest {
+}
diff --git a/subprojects/store-query-interpreter/src/test/java/tools/refinery/store/query/interpreter/tests/QueryEvaluationHintSource.java b/subprojects/store-query-interpreter/src/test/java/tools/refinery/store/query/interpreter/tests/QueryEvaluationHintSource.java
new file mode 100644
index 00000000..6503ff2f
--- /dev/null
+++ b/subprojects/store-query-interpreter/src/test/java/tools/refinery/store/query/interpreter/tests/QueryEvaluationHintSource.java
@@ -0,0 +1,24 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.interpreter.tests;
+
+import tools.refinery.interpreter.matchers.backend.QueryEvaluationHint;
+import org.junit.jupiter.api.extension.ExtensionContext;
+import org.junit.jupiter.params.provider.Arguments;
+import org.junit.jupiter.params.provider.ArgumentsProvider;
+
+import java.util.stream.Stream;
+
+public class QueryEvaluationHintSource implements ArgumentsProvider {
+        @Override
+        public Stream<? extends Arguments> provideArguments(ExtensionContext context) {
+                return Stream.of(
+                                Arguments.of(new QueryBackendHint(QueryEvaluationHint.BackendRequirement.UNSPECIFIED)),
+                                Arguments.of(new QueryBackendHint(QueryEvaluationHint.BackendRequirement.DEFAULT_CACHING)),
+                                Arguments.of(new QueryBackendHint(QueryEvaluationHint.BackendRequirement.DEFAULT_SEARCH))
+                );
+        }
+}