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.

34 files changed, 2486 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);
+        }
+}