60 files changed, 4297 insertions, 1227 deletions
diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/ViatraModelQuery.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/ViatraModelQuery.java
deleted file mode 100644
index 677e3c7d..00000000
--- a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/ViatraModelQuery.java
+++ /dev/null
@@ -1,21 +0,0 @@
-package tools.refinery.store.query.viatra;
-import tools.refinery.store.adapter.ModelAdapterBuilderFactory;
-import tools.refinery.store.model.ModelStoreBuilder;
-import tools.refinery.store.query.ModelQuery;
-import tools.refinery.store.query.viatra.internal.ViatraModelQueryBuilderImpl;
-public final class ViatraModelQuery extends ModelAdapterBuilderFactory<ViatraModelQueryAdapter,
-                ViatraModelQueryStoreAdapter, ViatraModelQueryBuilder> {
-        public static final ViatraModelQuery ADAPTER = new ViatraModelQuery();
-        private ViatraModelQuery() {
-                super(ViatraModelQueryAdapter.class, ViatraModelQueryStoreAdapter.class, ViatraModelQueryBuilder.class);
-                extendsAdapter(ModelQuery.ADAPTER);
-        }
-        @Override
-        public ViatraModelQueryBuilder createBuilder(ModelStoreBuilder storeBuilder) {
-                return new ViatraModelQueryBuilderImpl(storeBuilder);
-        }
-}
diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/ViatraModelQueryAdapter.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/ViatraModelQueryAdapter.java
index 7e21476b..12c93f62 100644
--- a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/ViatraModelQueryAdapter.java
+++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/ViatraModelQueryAdapter.java
@@ -1,8 +1,18 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
 package tools.refinery.store.query.viatra;
 import tools.refinery.store.query.ModelQueryAdapter;
+import tools.refinery.store.query.viatra.internal.ViatraModelQueryBuilderImpl;
 public interface ViatraModelQueryAdapter extends ModelQueryAdapter {
        @Override
        ViatraModelQueryStoreAdapter getStoreAdapter();
+        static ViatraModelQueryBuilder builder() {
+                return new ViatraModelQueryBuilderImpl();
+        }
 }
diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/ViatraModelQueryBuilder.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/ViatraModelQueryBuilder.java
index efc6146c..931a07aa 100644
--- a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/ViatraModelQueryBuilder.java
+++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/ViatraModelQueryBuilder.java
@@ -1,10 +1,16 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
 package tools.refinery.store.query.viatra;
 import org.eclipse.viatra.query.runtime.api.ViatraQueryEngineOptions;
 import org.eclipse.viatra.query.runtime.matchers.backend.IQueryBackendFactory;
 import org.eclipse.viatra.query.runtime.matchers.backend.QueryEvaluationHint;
 import tools.refinery.store.model.ModelStore;
-import tools.refinery.store.query.DNF;
+import tools.refinery.store.query.dnf.AnyQuery;
+import tools.refinery.store.query.dnf.Dnf;
 import tools.refinery.store.query.ModelQueryBuilder;
 import java.util.Collection;
@@ -23,26 +29,26 @@ public interface ViatraModelQueryBuilder extends ModelQueryBuilder {
        ViatraModelQueryBuilder searchBackend(IQueryBackendFactory queryBackendFactory);
        @Override
-        default ViatraModelQueryBuilder queries(DNF... queries) {
+        default ViatraModelQueryBuilder queries(AnyQuery... queries) {
                ModelQueryBuilder.super.queries(queries);
                return this;
        }
        @Override
-        default ViatraModelQueryBuilder queries(Collection<DNF> queries) {
+        default ViatraModelQueryBuilder queries(Collection<? extends AnyQuery> queries) {
                ModelQueryBuilder.super.queries(queries);
                return this;
        }
        @Override
-        ViatraModelQueryBuilder query(DNF query);
+        ViatraModelQueryBuilder query(AnyQuery query);
-        ViatraModelQueryBuilder query(DNF query, QueryEvaluationHint queryEvaluationHint);
+        ViatraModelQueryBuilder query(AnyQuery query, QueryEvaluationHint queryEvaluationHint);
-        ViatraModelQueryBuilder computeHint(Function<DNF, QueryEvaluationHint> computeHint);
+        ViatraModelQueryBuilder computeHint(Function<Dnf, QueryEvaluationHint> computeHint);
-        ViatraModelQueryBuilder hint(DNF dnf, QueryEvaluationHint queryEvaluationHint);
+        ViatraModelQueryBuilder hint(Dnf dnf, QueryEvaluationHint queryEvaluationHint);
        @Override
-        ViatraModelQueryStoreAdapter createStoreAdapter(ModelStore store);
+        ViatraModelQueryStoreAdapter build(ModelStore store);
 }
diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/ViatraModelQueryStoreAdapter.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/ViatraModelQueryStoreAdapter.java
index 1ee02f12..da6d7bd5 100644
--- a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/ViatraModelQueryStoreAdapter.java
+++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/ViatraModelQueryStoreAdapter.java
@@ -1,3 +1,8 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
 package tools.refinery.store.query.viatra;
 import org.eclipse.viatra.query.runtime.api.ViatraQueryEngineOptions;
diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/ViatraTupleLike.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/ViatraTupleLike.java
deleted file mode 100644
index 46c28434..00000000
--- a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/ViatraTupleLike.java
+++ /dev/null
@@ -1,18 +0,0 @@
-package tools.refinery.store.query.viatra;
-import org.eclipse.viatra.query.runtime.matchers.tuple.ITuple;
-import tools.refinery.store.tuple.Tuple1;
-import tools.refinery.store.tuple.TupleLike;
-public record ViatraTupleLike(ITuple wrappedTuple) implements TupleLike {
-        @Override
-        public int getSize() {
-                return wrappedTuple.getSize();
-        }
-        @Override
-        public int get(int element) {
-                var wrappedValue = (Tuple1) wrappedTuple.get(element);
-                return wrappedValue.value0();
-        }
-}
diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/RelationalScope.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/RelationalScope.java
index 8328e759..d1a65a89 100644
--- a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/RelationalScope.java
+++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/RelationalScope.java
@@ -1,3 +1,8 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
 package tools.refinery.store.query.viatra.internal;
 import org.apache.log4j.Logger;
diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/ViatraModelQueryAdapterImpl.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/ViatraModelQueryAdapterImpl.java
index 039f46fa..5f3e86b4 100644
--- a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/ViatraModelQueryAdapterImpl.java
+++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/ViatraModelQueryAdapterImpl.java
@@ -1,3 +1,8 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
 package tools.refinery.store.query.viatra.internal;
 import org.eclipse.viatra.query.runtime.api.AdvancedViatraQueryEngine;
@@ -7,62 +12,92 @@ import org.eclipse.viatra.query.runtime.internal.apiimpl.ViatraQueryEngineImpl;
 import org.eclipse.viatra.query.runtime.matchers.backend.IQueryBackend;
 import org.eclipse.viatra.query.runtime.matchers.backend.IQueryBackendFactory;
 import tools.refinery.store.model.Model;
-import tools.refinery.store.query.DNF;
+import tools.refinery.store.model.ModelListener;
-import tools.refinery.store.query.ResultSet;
+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.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.viatra.ViatraModelQueryAdapter;
+import tools.refinery.store.query.viatra.internal.matcher.FunctionalViatraMatcher;
+import tools.refinery.store.query.viatra.internal.matcher.RawPatternMatcher;
+import tools.refinery.store.query.viatra.internal.matcher.RelationalViatraMatcher;
 import java.lang.invoke.MethodHandle;
 import java.lang.invoke.MethodHandles;
 import java.util.Collection;
 import java.util.Collections;
-import java.util.HashMap;
+import java.util.LinkedHashMap;
 import java.util.Map;
-public class ViatraModelQueryAdapterImpl implements ViatraModelQueryAdapter {
+public class ViatraModelQueryAdapterImpl implements ViatraModelQueryAdapter, ModelListener {
        private static final String DELAY_MESSAGE_DELIVERY_FIELD_NAME = "delayMessageDelivery";
+        private static final MethodHandle SET_UPDATE_PROPAGATION_DELAYED_HANDLE;
        private static final String QUERY_BACKENDS_FIELD_NAME = "queryBackends";
+        private static final MethodHandle GET_QUERY_BACKENDS_HANDLE;
        private final Model model;
        private final ViatraModelQueryStoreAdapterImpl storeAdapter;
        private final ViatraQueryEngineImpl queryEngine;
-        private final MethodHandle setUpdatePropagationDelayedHandle;
+        private final Map<AnyQuery, AnyResultSet> resultSets;
-        private final MethodHandle getQueryBackendsHandle;
-        private final Map<DNF, ResultSet> resultSets;
        private boolean pendingChanges;
-        ViatraModelQueryAdapterImpl(Model model, ViatraModelQueryStoreAdapterImpl storeAdapter) {
+        static {
-                this.model = model;
-                this.storeAdapter = storeAdapter;
-                var scope = new RelationalScope(this);
-                queryEngine = (ViatraQueryEngineImpl) AdvancedViatraQueryEngine.createUnmanagedEngine(scope);
                try {
                        var lookup = MethodHandles.privateLookupIn(ViatraQueryEngineImpl.class, MethodHandles.lookup());
-                        setUpdatePropagationDelayedHandle = lookup.findSetter(ViatraQueryEngineImpl.class,
+                        SET_UPDATE_PROPAGATION_DELAYED_HANDLE = lookup.findSetter(ViatraQueryEngineImpl.class,
                                        DELAY_MESSAGE_DELIVERY_FIELD_NAME, Boolean.TYPE);
-                        getQueryBackendsHandle = lookup.findGetter(ViatraQueryEngineImpl.class, QUERY_BACKENDS_FIELD_NAME,
+                        GET_QUERY_BACKENDS_HANDLE = lookup.findGetter(ViatraQueryEngineImpl.class, QUERY_BACKENDS_FIELD_NAME,
                                        Map.class);
                } catch (IllegalAccessException | NoSuchFieldException e) {
                        throw new IllegalStateException("Cannot access private members of %s"
                                        .formatted(ViatraQueryEngineImpl.class.getName()), e);
                }
+        }
+        ViatraModelQueryAdapterImpl(Model model, ViatraModelQueryStoreAdapterImpl storeAdapter) {
+                this.model = model;
+                this.storeAdapter = storeAdapter;
+                var scope = new RelationalScope(this);
+                queryEngine = (ViatraQueryEngineImpl) AdvancedViatraQueryEngine.createUnmanagedEngine(scope,
+                                storeAdapter.getEngineOptions());
                var querySpecifications = storeAdapter.getQuerySpecifications();
                GenericQueryGroup.of(
                                Collections.<IQuerySpecification<?>>unmodifiableCollection(querySpecifications.values()).stream()
                ).prepare(queryEngine);
-                resultSets = new HashMap<>(querySpecifications.size());
+                var vacuousQueries = storeAdapter.getVacuousQueries();
+                resultSets = new LinkedHashMap<>(querySpecifications.size() + vacuousQueries.size());
                for (var entry : querySpecifications.entrySet()) {
-                        var matcher = queryEngine.getMatcher(entry.getValue());
+                        var rawPatternMatcher = queryEngine.getMatcher(entry.getValue());
-                        resultSets.put(entry.getKey(), matcher);
+                        var query = entry.getKey();
+                        resultSets.put(query, createResultSet((Query<?>) query, rawPatternMatcher));
+                }
+                for (var vacuousQuery : vacuousQueries) {
+                        resultSets.put(vacuousQuery, new EmptyResultSet<>(this, (Query<?>) vacuousQuery));
                }
                setUpdatePropagationDelayed(true);
+                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 RelationalViatraMatcher(this, relationalQuery, matcher);
+                        return resultSet;
+                } else if (query instanceof FunctionalQuery<T> functionalQuery) {
+                        return new FunctionalViatraMatcher<>(this, functionalQuery, matcher);
+                } else {
+                        throw new IllegalArgumentException("Unknown query: " + query);
+                }
        }
        private void setUpdatePropagationDelayed(boolean value) {
                try {
-                        setUpdatePropagationDelayedHandle.invokeExact(queryEngine, value);
+                        SET_UPDATE_PROPAGATION_DELAYED_HANDLE.invokeExact(queryEngine, value);
                } catch (Error e) {
                        // Fatal JVM errors should not be wrapped.
                        throw e;
@@ -74,7 +109,7 @@ public class ViatraModelQueryAdapterImpl implements ViatraModelQueryAdapter {
        private Collection<IQueryBackend> getQueryBackends() {
                try {
                        @SuppressWarnings("unchecked")
-                        var backendMap = (Map<IQueryBackendFactory, IQueryBackend>) getQueryBackendsHandle.invokeExact(queryEngine);
+                        var backendMap = (Map<IQueryBackendFactory, IQueryBackend>) GET_QUERY_BACKENDS_HANDLE.invokeExact(queryEngine);
                        return backendMap.values();
                } catch (Error e) {
                        // Fatal JVM errors should not be wrapped.
@@ -95,12 +130,14 @@ public class ViatraModelQueryAdapterImpl implements ViatraModelQueryAdapter {
        }
        @Override
-        public ResultSet getResultSet(DNF query) {
+        public <T> ResultSet<T> getResultSet(Query<T> query) {
                var resultSet = resultSets.get(query);
                if (resultSet == null) {
                        throw new IllegalArgumentException("No matcher for query %s in model".formatted(query.name()));
                }
-                return resultSet;
+                @SuppressWarnings("unchecked")
+                var typedResultSet = (ResultSet<T>) resultSet;
+                return typedResultSet;
        }
        @Override
@@ -132,4 +169,9 @@ public class ViatraModelQueryAdapterImpl implements ViatraModelQueryAdapter {
                }
                pendingChanges = false;
        }
+        @Override
+        public void afterRestore() {
+                flushChanges();
+        }
 }
diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/ViatraModelQueryBuilderImpl.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/ViatraModelQueryBuilderImpl.java
index 9f1e55b1..ce2467b4 100644
--- a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/ViatraModelQueryBuilderImpl.java
+++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/ViatraModelQueryBuilderImpl.java
@@ -1,115 +1,162 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
 package tools.refinery.store.query.viatra.internal;
 import org.eclipse.viatra.query.runtime.api.IQuerySpecification;
 import org.eclipse.viatra.query.runtime.api.ViatraQueryEngineOptions;
-import org.eclipse.viatra.query.runtime.localsearch.matcher.integration.LocalSearchGenericBackendFactory;
+import org.eclipse.viatra.query.runtime.localsearch.matcher.integration.LocalSearchHintOptions;
 import org.eclipse.viatra.query.runtime.matchers.backend.IQueryBackendFactory;
 import org.eclipse.viatra.query.runtime.matchers.backend.QueryEvaluationHint;
 import org.eclipse.viatra.query.runtime.rete.matcher.ReteBackendFactory;
 import tools.refinery.store.adapter.AbstractModelAdapterBuilder;
 import tools.refinery.store.model.ModelStore;
 import tools.refinery.store.model.ModelStoreBuilder;
-import tools.refinery.store.query.DNF;
+import tools.refinery.store.query.dnf.AnyQuery;
+import tools.refinery.store.query.dnf.Dnf;
 import tools.refinery.store.query.viatra.ViatraModelQueryBuilder;
-import tools.refinery.store.query.viatra.internal.pquery.DNF2PQuery;
+import tools.refinery.store.query.viatra.internal.localsearch.FlatCostFunction;
-import tools.refinery.store.query.viatra.internal.pquery.RawPatternMatcher;
+import tools.refinery.store.query.viatra.internal.localsearch.RelationalLocalSearchBackendFactory;
+import tools.refinery.store.query.viatra.internal.matcher.RawPatternMatcher;
+import tools.refinery.store.query.viatra.internal.pquery.Dnf2PQuery;
-import java.util.Collections;
+import java.util.*;
-import java.util.LinkedHashMap;
-import java.util.Map;
 import java.util.function.Function;
-public class ViatraModelQueryBuilderImpl extends AbstractModelAdapterBuilder implements ViatraModelQueryBuilder {
+public class ViatraModelQueryBuilderImpl extends AbstractModelAdapterBuilder<ViatraModelQueryStoreAdapterImpl>
+                implements ViatraModelQueryBuilder {
        private ViatraQueryEngineOptions.Builder engineOptionsBuilder;
-        private final DNF2PQuery dnf2PQuery = new DNF2PQuery();
+        private QueryEvaluationHint defaultHint = new QueryEvaluationHint(Map.of(
-        private final Map<DNF, IQuerySpecification<RawPatternMatcher>> querySpecifications = new LinkedHashMap<>();
+                        // 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 Dnf2PQuery dnf2PQuery = new Dnf2PQuery();
+        private final Set<AnyQuery> vacuousQueries = new LinkedHashSet<>();
+        private final Map<AnyQuery, IQuerySpecification<RawPatternMatcher>> querySpecifications = new LinkedHashMap<>();
-        public ViatraModelQueryBuilderImpl(ModelStoreBuilder storeBuilder) {
+        public ViatraModelQueryBuilderImpl() {
-                super(storeBuilder);
                engineOptionsBuilder = new ViatraQueryEngineOptions.Builder()
                                .withDefaultBackend(ReteBackendFactory.INSTANCE)
                                .withDefaultCachingBackend(ReteBackendFactory.INSTANCE)
-                                .withDefaultSearchBackend(LocalSearchGenericBackendFactory.INSTANCE);
+                                .withDefaultSearchBackend(RelationalLocalSearchBackendFactory.INSTANCE);
        }
        @Override
        public ViatraModelQueryBuilder engineOptions(ViatraQueryEngineOptions engineOptions) {
+                checkNotConfigured();
                engineOptionsBuilder = new ViatraQueryEngineOptions.Builder(engineOptions);
                return this;
        }
        @Override
        public ViatraModelQueryBuilder defaultHint(QueryEvaluationHint queryEvaluationHint) {
-                engineOptionsBuilder.withDefaultHint(queryEvaluationHint);
+                checkNotConfigured();
+                defaultHint = defaultHint.overrideBy(queryEvaluationHint);
                return this;
        }
        @Override
        public ViatraModelQueryBuilder backend(IQueryBackendFactory queryBackendFactory) {
+                checkNotConfigured();
                engineOptionsBuilder.withDefaultBackend(queryBackendFactory);
                return this;
        }
        @Override
        public ViatraModelQueryBuilder cachingBackend(IQueryBackendFactory queryBackendFactory) {
+                checkNotConfigured();
                engineOptionsBuilder.withDefaultCachingBackend(queryBackendFactory);
                return this;
        }
        @Override
        public ViatraModelQueryBuilder searchBackend(IQueryBackendFactory queryBackendFactory) {
+                checkNotConfigured();
                engineOptionsBuilder.withDefaultSearchBackend(queryBackendFactory);
                return this;
        }
        @Override
-        public ViatraModelQueryBuilder query(DNF query) {
+        public ViatraModelQueryBuilder query(AnyQuery query) {
-                if (querySpecifications.containsKey(query)) {
+                checkNotConfigured();
-                        throw new IllegalArgumentException("%s was already added to the query engine".formatted(query.name()));
+                if (querySpecifications.containsKey(query) || vacuousQueries.contains(query)) {
+                        // Ignore duplicate queries.
+                        return this;
+                }
+                var dnf = query.getDnf();
+                var reduction = dnf.getReduction();
+                switch (reduction) {
+                case NOT_REDUCIBLE -> {
+                        var pQuery = dnf2PQuery.translate(dnf);
+                        querySpecifications.put(query, pQuery.build());
+                }
+                case ALWAYS_FALSE -> vacuousQueries.add(query);
+                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);
                }
-                var pQuery = dnf2PQuery.translate(query);
-                querySpecifications.put(query, pQuery.build());
                return this;
        }
        @Override
-        public ViatraModelQueryBuilder query(DNF query, QueryEvaluationHint queryEvaluationHint) {
+        public ViatraModelQueryBuilder query(AnyQuery query, QueryEvaluationHint queryEvaluationHint) {
+                hint(query.getDnf(), queryEvaluationHint);
                query(query);
-                hint(query, queryEvaluationHint);
                return this;
        }
        @Override
-        public ViatraModelQueryBuilder computeHint(Function<DNF, QueryEvaluationHint> computeHint) {
+        public ViatraModelQueryBuilder computeHint(Function<Dnf, QueryEvaluationHint> computeHint) {
+                checkNotConfigured();
                dnf2PQuery.setComputeHint(computeHint);
                return this;
        }
        @Override
-        public ViatraModelQueryBuilder hint(DNF dnf, QueryEvaluationHint queryEvaluationHint) {
+        public ViatraModelQueryBuilder hint(Dnf dnf, QueryEvaluationHint queryEvaluationHint) {
-                var pQuery = dnf2PQuery.getAlreadyTranslated(dnf);
+                checkNotConfigured();
-                if (pQuery == null) {
+                dnf2PQuery.hint(dnf, queryEvaluationHint);
-                        throw new IllegalArgumentException(
-                                        "Cannot specify hint for %s, because it was not added to the query engine".formatted(dnf.name()));
-                }
-                pQuery.setEvaluationHints(pQuery.getEvaluationHints().overrideBy(queryEvaluationHint));
                return this;
        }
        @Override
-        public ViatraModelQueryStoreAdapterImpl createStoreAdapter(ModelStore store) {
+        public void doConfigure(ModelStoreBuilder storeBuilder) {
+                dnf2PQuery.assertNoUnusedHints();
+        }
+        @Override
+        public ViatraModelQueryStoreAdapterImpl doBuild(ModelStore store) {
                validateSymbols(store);
-                return new ViatraModelQueryStoreAdapterImpl(store, engineOptionsBuilder.build(), dnf2PQuery.getRelationViews(),
+                return new ViatraModelQueryStoreAdapterImpl(store, buildEngineOptions(), dnf2PQuery.getSymbolViews(),
-                                Collections.unmodifiableMap(querySpecifications));
+                                Collections.unmodifiableMap(querySpecifications), Collections.unmodifiableSet(vacuousQueries));
+        }
+        private ViatraQueryEngineOptions 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 relationView : dnf2PQuery.getRelationViews().keySet()) {
+                for (var symbolView : dnf2PQuery.getSymbolViews().keySet()) {
-                        var symbol = relationView.getSymbol();
+                        var symbol = symbolView.getSymbol();
                        if (!symbols.contains(symbol)) {
-                                throw new IllegalArgumentException("Cannot query relation view %s: symbol %s is not in the model"
+                                throw new IllegalArgumentException("Cannot query view %s: symbol %s is not in the model"
-                                                .formatted(relationView, symbol));
+                                                .formatted(symbolView, symbol));
                        }
                }
        }
diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/ViatraModelQueryStoreAdapterImpl.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/ViatraModelQueryStoreAdapterImpl.java
index 394e407e..11a3c7fd 100644
--- a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/ViatraModelQueryStoreAdapterImpl.java
+++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/ViatraModelQueryStoreAdapterImpl.java
@@ -1,3 +1,8 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
 package tools.refinery.store.query.viatra.internal;
 import org.eclipse.viatra.query.runtime.api.IQuerySpecification;
@@ -5,27 +10,34 @@ import org.eclipse.viatra.query.runtime.api.ViatraQueryEngineOptions;
 import org.eclipse.viatra.query.runtime.matchers.context.IInputKey;
 import tools.refinery.store.model.Model;
 import tools.refinery.store.model.ModelStore;
-import tools.refinery.store.query.DNF;
+import tools.refinery.store.query.dnf.AnyQuery;
 import tools.refinery.store.query.viatra.ViatraModelQueryStoreAdapter;
-import tools.refinery.store.query.viatra.internal.pquery.RawPatternMatcher;
+import tools.refinery.store.query.viatra.internal.matcher.RawPatternMatcher;
-import tools.refinery.store.query.view.AnyRelationView;
+import tools.refinery.store.query.view.AnySymbolView;
-import java.util.Collection;
+import java.util.*;
-import java.util.Map;
 public class ViatraModelQueryStoreAdapterImpl implements ViatraModelQueryStoreAdapter {
        private final ModelStore store;
        private final ViatraQueryEngineOptions engineOptions;
-        private final Map<AnyRelationView, IInputKey> inputKeys;
+        private final Map<AnySymbolView, IInputKey> inputKeys;
-        private final Map<DNF, IQuerySpecification<RawPatternMatcher>> querySpecifications;
+        private final Map<AnyQuery, IQuerySpecification<RawPatternMatcher>> querySpecifications;
+        private final Set<AnyQuery> vacuousQueries;
+        private final Set<AnyQuery> allQueries;
        ViatraModelQueryStoreAdapterImpl(ModelStore store, ViatraQueryEngineOptions engineOptions,
-                                                                         Map<AnyRelationView, IInputKey> inputKeys,
+                                                                         Map<AnySymbolView, IInputKey> inputKeys,
-                                                                         Map<DNF, IQuerySpecification<RawPatternMatcher>> querySpecifications) {
+                                                                         Map<AnyQuery, IQuerySpecification<RawPatternMatcher>> querySpecifications,
+                                                                         Set<AnyQuery> vacuousQueries) {
                this.store = store;
                this.engineOptions = engineOptions;
                this.inputKeys = inputKeys;
                this.querySpecifications = querySpecifications;
+                this.vacuousQueries = vacuousQueries;
+                var mutableAllQueries = new LinkedHashSet<AnyQuery>(querySpecifications.size() + vacuousQueries.size());
+                mutableAllQueries.addAll(querySpecifications.keySet());
+                mutableAllQueries.addAll(vacuousQueries);
+                this.allQueries = Collections.unmodifiableSet(mutableAllQueries);
        }
        @Override
@@ -33,23 +45,27 @@ public class ViatraModelQueryStoreAdapterImpl implements ViatraModelQueryStoreAd
                return store;
        }
-        public Collection<AnyRelationView> getRelationViews() {
+        public Collection<AnySymbolView> getSymbolViews() {
                return inputKeys.keySet();
        }
-        public Map<AnyRelationView, IInputKey> getInputKeys() {
+        public Map<AnySymbolView, IInputKey> getInputKeys() {
                return inputKeys;
        }
        @Override
-        public Collection<DNF> getQueries() {
+        public Collection<AnyQuery> getQueries() {
-                return querySpecifications.keySet();
+                return allQueries;
        }
-        Map<DNF, IQuerySpecification<RawPatternMatcher>> getQuerySpecifications() {
+        Map<AnyQuery, IQuerySpecification<RawPatternMatcher>> getQuerySpecifications() {
                return querySpecifications;
        }
+        Set<AnyQuery> getVacuousQueries() {
+                return vacuousQueries;
+        }
        @Override
        public ViatraQueryEngineOptions getEngineOptions() {
                return engineOptions;
diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/cardinality/UpperCardinalitySumAggregationOperator.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/cardinality/UpperCardinalitySumAggregationOperator.java
deleted file mode 100644
index e0bca9e0..00000000
--- a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/cardinality/UpperCardinalitySumAggregationOperator.java
+++ /dev/null
@@ -1,97 +0,0 @@
-package tools.refinery.store.query.viatra.internal.cardinality;
-import org.eclipse.viatra.query.runtime.matchers.psystem.aggregations.BoundAggregator;
-import org.eclipse.viatra.query.runtime.matchers.psystem.aggregations.IMultisetAggregationOperator;
-import tools.refinery.store.representation.cardinality.FiniteUpperCardinality;
-import tools.refinery.store.representation.cardinality.UnboundedUpperCardinality;
-import tools.refinery.store.representation.cardinality.UpperCardinalities;
-import tools.refinery.store.representation.cardinality.UpperCardinality;
-import java.util.stream.Stream;
-public class UpperCardinalitySumAggregationOperator implements IMultisetAggregationOperator<UpperCardinality,
-                UpperCardinalitySumAggregationOperator.Accumulator, UpperCardinality> {
-        public static final UpperCardinalitySumAggregationOperator INSTANCE = new UpperCardinalitySumAggregationOperator();
-        public static final BoundAggregator BOUND_AGGREGATOR = new BoundAggregator(INSTANCE, UpperCardinality.class,
-                        UpperCardinality.class);
-        private UpperCardinalitySumAggregationOperator() {
-                // Singleton constructor.
-        }
-        @Override
-        public String getName() {
-                return "sum<UpperCardinality>";
-        }
-        @Override
-        public String getShortDescription() {
-                return "%s computes the sum of finite or unbounded upper cardinalities".formatted(getName());
-        }
-        @Override
-        public Accumulator createNeutral() {
-                return new Accumulator();
-        }
-        @Override
-        public boolean isNeutral(Accumulator result) {
-                return result.sumFiniteUpperBounds == 0 && result.countUnbounded == 0;
-        }
-        @Override
-        public Accumulator update(Accumulator oldResult, UpperCardinality updateValue, boolean isInsertion) {
-                if (updateValue instanceof FiniteUpperCardinality finiteUpperCardinality) {
-                        int finiteUpperBound = finiteUpperCardinality.finiteUpperBound();
-                        if (isInsertion) {
-                                oldResult.sumFiniteUpperBounds += finiteUpperBound;
-                        } else {
-                                oldResult.sumFiniteUpperBounds -= finiteUpperBound;
-                        }
-                } else if (updateValue instanceof UnboundedUpperCardinality) {
-                        if (isInsertion) {
-                                oldResult.countUnbounded += 1;
-                        } else {
-                                oldResult.countUnbounded -= 1;
-                        }
-                } else {
-                        throw new IllegalArgumentException("Unknown UpperCardinality: " + updateValue);
-                }
-                return oldResult;
-        }
-        @Override
-        public UpperCardinality getAggregate(Accumulator result) {
-                return result.countUnbounded > 0 ? UpperCardinalities.UNBOUNDED :
-                                UpperCardinalities.valueOf(result.sumFiniteUpperBounds);
-        }
-        @Override
-        public UpperCardinality aggregateStream(Stream<UpperCardinality> stream) {
-                var result = stream.collect(this::createNeutral, (accumulator, value) -> update(accumulator, value, true),
-                                (left, right) -> new Accumulator(left.sumFiniteUpperBounds + right.sumFiniteUpperBounds,
-                                                left.countUnbounded + right.countUnbounded));
-                return getAggregate(result);
-        }
-        @Override
-        public Accumulator clone(Accumulator original) {
-                return new Accumulator(original.sumFiniteUpperBounds, original.countUnbounded);
-        }
-        public static class Accumulator {
-                private int sumFiniteUpperBounds;
-                private int countUnbounded;
-                private Accumulator(int sumFiniteUpperBounds, int countUnbounded) {
-                        this.sumFiniteUpperBounds = sumFiniteUpperBounds;
-                        this.countUnbounded = countUnbounded;
-                }
-                private Accumulator() {
-                        this(0, 0);
-                }
-        }
-}
diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/context/DummyBaseIndexer.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/context/DummyBaseIndexer.java
index 2a24b67c..8cb199d2 100644
--- a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/context/DummyBaseIndexer.java
+++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/context/DummyBaseIndexer.java
@@ -1,3 +1,8 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
 package tools.refinery.store.query.viatra.internal.context;
 import org.eclipse.viatra.query.runtime.api.scope.IBaseIndex;
diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/context/RelationalEngineContext.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/context/RelationalEngineContext.java
index 28bc69d0..7220f8ca 100644
--- a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/context/RelationalEngineContext.java
+++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/context/RelationalEngineContext.java
@@ -1,3 +1,8 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
 package tools.refinery.store.query.viatra.internal.context;
 import org.eclipse.viatra.query.runtime.api.scope.IBaseIndex;
diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/context/RelationalQueryMetaContext.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/context/RelationalQueryMetaContext.java
index cba3fa08..211eacb4 100644
--- a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/context/RelationalQueryMetaContext.java
+++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/context/RelationalQueryMetaContext.java
@@ -1,10 +1,16 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
 package tools.refinery.store.query.viatra.internal.context;
 import org.eclipse.viatra.query.runtime.matchers.context.AbstractQueryMetaContext;
 import org.eclipse.viatra.query.runtime.matchers.context.IInputKey;
 import org.eclipse.viatra.query.runtime.matchers.context.InputKeyImplication;
-import tools.refinery.store.query.viatra.internal.pquery.RelationViewWrapper;
+import org.eclipse.viatra.query.runtime.matchers.context.common.JavaTransitiveInstancesKey;
-import tools.refinery.store.query.view.AnyRelationView;
+import tools.refinery.store.query.viatra.internal.pquery.SymbolViewWrapper;
+import tools.refinery.store.query.view.AnySymbolView;
 import java.util.*;
@@ -12,9 +18,9 @@ import java.util.*;
 * The meta context information for String scopes.
 */
 public class RelationalQueryMetaContext extends AbstractQueryMetaContext {
-        private final Map<AnyRelationView, IInputKey> inputKeys;
+        private final Map<AnySymbolView, IInputKey> inputKeys;
-        RelationalQueryMetaContext(Map<AnyRelationView, IInputKey> inputKeys) {
+        RelationalQueryMetaContext(Map<AnySymbolView, IInputKey> inputKeys) {
                this.inputKeys = inputKeys;
        }
@@ -37,26 +43,43 @@ public class RelationalQueryMetaContext extends AbstractQueryMetaContext {
        @Override
        public Collection<InputKeyImplication> getImplications(IInputKey implyingKey) {
-                var relationView = checkKey(implyingKey);
+                if (implyingKey instanceof JavaTransitiveInstancesKey) {
-                var relationViewImplications = relationView.getImpliedRelationViews();
+                        return List.of();
+                }
+                var symbolView = checkKey(implyingKey);
+                var relationViewImplications = symbolView.getImpliedRelationViews();
                var inputKeyImplications = new HashSet<InputKeyImplication>(relationViewImplications.size());
                for (var relationViewImplication : relationViewImplications) {
-                        if (!relationView.equals(relationViewImplication.implyingRelationView())) {
+                        if (!symbolView.equals(relationViewImplication.implyingView())) {
                                throw new IllegalArgumentException("Relation view %s returned unrelated implication %s".formatted(
-                                                relationView, relationViewImplication));
+                                                symbolView, relationViewImplication));
                        }
-                        var impliedInputKey = inputKeys.get(relationViewImplication.impliedRelationView());
+                        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());
@@ -75,20 +98,20 @@ public class RelationalQueryMetaContext extends AbstractQueryMetaContext {
                return flattened;
        }
-        private static void checkValidIndices(AnyRelationView relationView, Collection<Integer> indices) {
+        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 AnyRelationView checkKey(IInputKey key) {
+        public AnySymbolView checkKey(IInputKey key) {
-                if (!(key instanceof RelationViewWrapper wrapper)) {
+                if (!(key instanceof SymbolViewWrapper wrapper)) {
                        throw new IllegalArgumentException("The input key %s is not a valid input key".formatted(key));
                }
-                var relationView = wrapper.getWrappedKey();
+                var symbolView = wrapper.getWrappedKey();
-                if (!inputKeys.containsKey(relationView)) {
+                if (!inputKeys.containsKey(symbolView)) {
                        throw new IllegalArgumentException("The input key %s is not present in the model".formatted(key));
                }
-                return relationView;
+                return symbolView;
        }
 }
diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/context/RelationalRuntimeContext.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/context/RelationalRuntimeContext.java
index 01d20d3e..0f2daca8 100644
--- a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/context/RelationalRuntimeContext.java
+++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/context/RelationalRuntimeContext.java
@@ -1,3 +1,8 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
 package tools.refinery.store.query.viatra.internal.context;
 import org.eclipse.viatra.query.runtime.matchers.context.*;
@@ -8,9 +13,9 @@ import org.eclipse.viatra.query.runtime.matchers.tuple.Tuples;
 import org.eclipse.viatra.query.runtime.matchers.util.Accuracy;
 import tools.refinery.store.model.Model;
 import tools.refinery.store.query.viatra.internal.ViatraModelQueryAdapterImpl;
-import tools.refinery.store.query.viatra.internal.pquery.RelationViewWrapper;
+import tools.refinery.store.query.viatra.internal.pquery.SymbolViewWrapper;
 import tools.refinery.store.query.viatra.internal.update.ModelUpdateListener;
-import tools.refinery.store.query.view.AnyRelationView;
+import tools.refinery.store.query.view.AnySymbolView;
 import java.lang.reflect.InvocationTargetException;
 import java.util.Iterator;
@@ -54,8 +59,9 @@ public class RelationalRuntimeContext implements IQueryRuntimeContext {
        @Override
        public boolean isIndexed(IInputKey key, IndexingService service) {
-                if (key instanceof AnyRelationView relationalKey) {
+                if (key instanceof SymbolViewWrapper wrapper) {
-                        return this.modelUpdateListener.containsRelationView(relationalKey);
+                        var symbolViewKey = wrapper.getWrappedKey();
+                        return this.modelUpdateListener.containsSymbolView(symbolViewKey);
                } else {
                        return false;
                }
@@ -68,13 +74,13 @@ public class RelationalRuntimeContext implements IQueryRuntimeContext {
                }
        }
-        AnyRelationView checkKey(IInputKey key) {
+        AnySymbolView checkKey(IInputKey key) {
-                if (key instanceof RelationViewWrapper wrappedKey) {
+                if (key instanceof SymbolViewWrapper wrappedKey) {
-                        var relationViewKey = wrappedKey.getWrappedKey();
+                        var symbolViewKey = wrappedKey.getWrappedKey();
-                        if (modelUpdateListener.containsRelationView(relationViewKey)) {
+                        if (modelUpdateListener.containsSymbolView(symbolViewKey)) {
-                                return relationViewKey;
+                                return symbolViewKey;
                        } else {
-                                throw new IllegalStateException("Query is asking for non-indexed key %s".formatted(relationViewKey));
+                                throw new IllegalStateException("Query is asking for non-indexed key %s".formatted(symbolViewKey));
                        }
                } else {
                        throw new IllegalStateException("Query is asking for non-relational key");
@@ -83,10 +89,7 @@ public class RelationalRuntimeContext implements IQueryRuntimeContext {
        @Override
        public int countTuples(IInputKey key, TupleMask seedMask, ITuple seed) {
-                var relationViewKey = checkKey(key);
+                Iterator<Object[]> iterator = enumerate(key, seedMask, seed).iterator();
-                Iterable<Object[]> allObjects = relationViewKey.getAll(model);
-                Iterable<Object[]> filteredBySeed = filter(allObjects, objectArray -> isMatching(objectArray, seedMask, seed));
-                Iterator<Object[]> iterator = filteredBySeed.iterator();
                int result = 0;
                while (iterator.hasNext()) {
                        iterator.next();
@@ -102,13 +105,25 @@ public class RelationalRuntimeContext implements IQueryRuntimeContext {
        @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 = relationViewKey.getAll(model);
-                Iterable<Object[]> filteredBySeed = filter(allObjects, objectArray -> isMatching(objectArray, seedMask, seed));
+                return filter(allObjects, objectArray -> isMatching(objectArray, seedMask, seed));
-                return map(filteredBySeed, Tuples::flatTupleOf);
        }
-        private boolean isMatching(Object[] tuple, TupleMask seedMask, ITuple seed) {
+        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]];
@@ -120,11 +135,6 @@ public class RelationalRuntimeContext implements IQueryRuntimeContext {
        }
        @Override
-        public Iterable<?> enumerateValues(IInputKey key, TupleMask seedMask, ITuple seed) {
-                return enumerateTuples(key, seedMask, seed);
-        }
-        @Override
        public boolean containsTuple(IInputKey key, ITuple seed) {
                var relationViewKey = checkKey(key);
                return relationViewKey.get(model, seed.getElements());
diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/localsearch/ExtendOperationExecutor.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/localsearch/ExtendOperationExecutor.java
new file mode 100644
index 00000000..37177cbf
--- /dev/null
+++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/localsearch/ExtendOperationExecutor.java
@@ -0,0 +1,76 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2013, Zoltan Ujhelyi, Akos Horvath, Istvan Rath and Daniel Varro
+ * Copyright (c) 2023 The Refinery Authors <https://refinery.tools/>
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v. 2.0 which is available at
+ * http://www.eclipse.org/legal/epl-v20.html.
+ * SPDX-License-Identifier: EPL-2.0
+ *******************************************************************************/
+package tools.refinery.store.query.viatra.internal.localsearch;
+import org.eclipse.viatra.query.runtime.localsearch.MatchingFrame;
+import org.eclipse.viatra.query.runtime.localsearch.matcher.ISearchContext;
+import org.eclipse.viatra.query.runtime.localsearch.operations.ISearchOperation.ISearchOperationExecutor;
+import java.util.Iterator;
+/**
+ * An operation that can be used to enumerate all possible values for a single position based on a constraint
+ * @author Zoltan Ujhelyi, Akos Horvath
+ * @since 2.0
+ */
+abstract class ExtendOperationExecutor<T> implements ISearchOperationExecutor {
+    private Iterator<? extends T> it;
+    /**
+     * Returns an iterator with the possible options from the current state
+     * @since 2.0
+     */
+        @SuppressWarnings("squid:S1452")
+    protected abstract Iterator<? extends T> getIterator(MatchingFrame frame, ISearchContext context);
+    /**
+     * Updates the frame with the next element of the iterator. Called during {@link #execute(MatchingFrame, ISearchContext)}.
+     *
+     * @return true if the update is successful or false otherwise; in case of false is returned, the next element should be taken from the iterator.
+     * @since 2.0
+     */
+    protected abstract boolean fillInValue(T newValue, MatchingFrame frame, ISearchContext context);
+    /**
+     * Restores the frame to the state before {@link #fillInValue(Object, MatchingFrame, ISearchContext)}. Called during
+     * {@link #onBacktrack(MatchingFrame, ISearchContext)}.
+     *
+     * @since 2.0
+     */
+    protected abstract void cleanup(MatchingFrame frame, ISearchContext context);
+    @Override
+    public void onInitialize(MatchingFrame frame, ISearchContext context) {
+        it = getIterator(frame, context);
+    }
+    @Override
+    public void onBacktrack(MatchingFrame frame, ISearchContext context) {
+        it = null;
+    }
+        /**
+         * Fixed version of {@link org.eclipse.viatra.query.runtime.localsearch.operations.ExtendOperationExecutor#execute}
+         * that handles failed unification of variables correctly.
+         * @param frame The matching frame to extend.
+         * @param context The search context.
+         * @return {@code true} if an extension was found, {@code false} otherwise.
+         */
+    @Override
+    public boolean execute(MatchingFrame frame, ISearchContext context) {
+                while (it.hasNext()) {
+                        var newValue = it.next();
+                        if (fillInValue(newValue, frame, context)) {
+                                return true;
+                        }
+                }
+                return false;
+    }
+}
diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/localsearch/ExtendPositivePatternCall.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/localsearch/ExtendPositivePatternCall.java
new file mode 100644
index 00000000..9d48c785
--- /dev/null
+++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/localsearch/ExtendPositivePatternCall.java
@@ -0,0 +1,117 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2016, Grill Balázs, IncQueryLabs
+ * Copyright (c) 2023 The Refinery Authors <https://refinery.tools/>
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v. 2.0 which is available at
+ * http://www.eclipse.org/legal/epl-v20.html.
+ * SPDX-License-Identifier: EPL-2.0
+ *******************************************************************************/
+package tools.refinery.store.query.viatra.internal.localsearch;
+import org.eclipse.viatra.query.runtime.localsearch.MatchingFrame;
+import org.eclipse.viatra.query.runtime.localsearch.matcher.ISearchContext;
+import org.eclipse.viatra.query.runtime.localsearch.operations.IPatternMatcherOperation;
+import org.eclipse.viatra.query.runtime.localsearch.operations.ISearchOperation;
+import org.eclipse.viatra.query.runtime.localsearch.operations.util.CallInformation;
+import org.eclipse.viatra.query.runtime.matchers.backend.IQueryResultProvider;
+import org.eclipse.viatra.query.runtime.matchers.tuple.Tuple;
+import org.eclipse.viatra.query.runtime.matchers.tuple.TupleMask;
+import org.eclipse.viatra.query.runtime.matchers.tuple.VolatileModifiableMaskedTuple;
+import java.util.Iterator;
+import java.util.List;
+import java.util.function.Function;
+/**
+ * @author Grill Balázs
+ * @since 1.4
+ *
+ */
+public class ExtendPositivePatternCall implements ISearchOperation, IPatternMatcherOperation {
+    private class Executor extends ExtendOperationExecutor<Tuple> {
+        private final VolatileModifiableMaskedTuple maskedTuple;
+        public Executor() {
+            maskedTuple = new VolatileModifiableMaskedTuple(information.getThinFrameMask());
+        }
+        @Override
+        protected Iterator<? extends Tuple> getIterator(MatchingFrame frame, ISearchContext context) {
+            maskedTuple.updateTuple(frame);
+            IQueryResultProvider matcher = context.getMatcher(information.getCallWithAdornment());
+            return matcher.getAllMatches(information.getParameterMask(), maskedTuple).iterator();
+        }
+        /**
+         * @since 2.0
+         */
+        @Override
+        protected boolean fillInValue(Tuple result, MatchingFrame frame, ISearchContext context) {
+            TupleMask mask = information.getFullFrameMask();
+            // The first loop clears out the elements from a possible previous iteration
+            for(int i : information.getFreeParameterIndices()) {
+                mask.set(frame, i, null);
+            }
+            for(int i : information.getFreeParameterIndices()) {
+                Object oldValue = mask.getValue(frame, i);
+                Object valueToFill = result.get(i);
+                if (oldValue != null && !oldValue.equals(valueToFill)){
+                    // If the inverse map contains more than one values for the same key, it means that these arguments are unified by the caller.
+                    // In this case if the callee assigns different values the frame shall be dropped
+                    return false;
+                }
+                mask.set(frame, i, valueToFill);
+            }
+            return true;
+        }
+        @Override
+        protected void cleanup(MatchingFrame frame, ISearchContext context) {
+            TupleMask mask = information.getFullFrameMask();
+            for(int i : information.getFreeParameterIndices()){
+                mask.set(frame, i, null);
+            }
+        }
+        @Override
+        public ISearchOperation getOperation() {
+            return ExtendPositivePatternCall.this;
+        }
+    }
+    private final CallInformation information;
+    /**
+     * @since 1.7
+     */
+    public ExtendPositivePatternCall(CallInformation information) {
+       this.information = information;
+    }
+    @Override
+    public ISearchOperationExecutor createExecutor() {
+        return new Executor();
+    }
+    @Override
+    public List<Integer> getVariablePositions() {
+        return information.getVariablePositions();
+    }
+    @Override
+    public String toString() {
+        return toString(Object::toString);
+    }
+    @Override
+    public String toString(@SuppressWarnings("squid:S4276") Function<Integer, String> variableMapping) {
+        return "extend find " + information.toString(variableMapping);
+    }
+    @Override
+    public CallInformation getCallInformation() {
+        return information;
+    }
+}
diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/localsearch/FlatCostFunction.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/localsearch/FlatCostFunction.java
new file mode 100644
index 00000000..cc906f22
--- /dev/null
+++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/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.viatra.internal.localsearch;
+import org.eclipse.viatra.query.runtime.localsearch.planner.cost.IConstraintEvaluationContext;
+import org.eclipse.viatra.query.runtime.localsearch.planner.cost.impl.StatisticsBasedConstraintCostFunction;
+import org.eclipse.viatra.query.runtime.matchers.context.IInputKey;
+import org.eclipse.viatra.query.runtime.matchers.psystem.basicenumerables.TypeConstraint;
+import org.eclipse.viatra.query.runtime.matchers.tuple.TupleMask;
+import org.eclipse.viatra.query.runtime.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-viatra/src/main/java/tools/refinery/store/query/viatra/internal/localsearch/GenericTypeExtend.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/localsearch/GenericTypeExtend.java
new file mode 100644
index 00000000..96ac4a72
--- /dev/null
+++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/localsearch/GenericTypeExtend.java
@@ -0,0 +1,137 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2017, Zoltan Ujhelyi, IncQuery Labs Ltd.
+ * Copyright (c) 2023 The Refinery Authors <https://refinery.tools/>
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v. 2.0 which is available at
+ * http://www.eclipse.org/legal/epl-v20.html.
+ * SPDX-License-Identifier: EPL-2.0
+ *******************************************************************************/
+package tools.refinery.store.query.viatra.internal.localsearch;
+import org.eclipse.viatra.query.runtime.localsearch.MatchingFrame;
+import org.eclipse.viatra.query.runtime.localsearch.matcher.ISearchContext;
+import org.eclipse.viatra.query.runtime.localsearch.operations.IIteratingSearchOperation;
+import org.eclipse.viatra.query.runtime.localsearch.operations.ISearchOperation;
+import org.eclipse.viatra.query.runtime.matchers.context.IInputKey;
+import org.eclipse.viatra.query.runtime.matchers.tuple.Tuple;
+import org.eclipse.viatra.query.runtime.matchers.tuple.TupleMask;
+import org.eclipse.viatra.query.runtime.matchers.tuple.VolatileMaskedTuple;
+import org.eclipse.viatra.query.runtime.matchers.util.Preconditions;
+import java.util.*;
+import java.util.function.Function;
+import java.util.stream.Collectors;
+/**
+ * @author Zoltan Ujhelyi
+ * @since 1.7
+ */
+public class GenericTypeExtend implements IIteratingSearchOperation {
+    private class Executor extends ExtendOperationExecutor<Tuple> {
+        private final VolatileMaskedTuple maskedTuple;
+        public Executor() {
+            this.maskedTuple = new VolatileMaskedTuple(callMask);
+        }
+        @Override
+        protected Iterator<? extends Tuple> getIterator(MatchingFrame frame, ISearchContext context) {
+            maskedTuple.updateTuple(frame);
+            return context.getRuntimeContext().enumerateTuples(type, indexerMask, maskedTuple).iterator();
+        }
+        @Override
+        protected boolean fillInValue(Tuple newTuple, MatchingFrame frame, ISearchContext context) {
+            for (Integer position : unboundVariableIndices) {
+                frame.setValue(position, null);
+            }
+            for (int i = 0; i < positions.length; i++) {
+                Object newValue = newTuple.get(i);
+                Object oldValue = frame.getValue(positions[i]);
+                if (oldValue != null && !Objects.equals(oldValue, newValue)) {
+                    // If positions tuple maps more than one values for the same element (e.g. loop), it means that
+                    // these arguments are to unified by the caller. In this case if the callee assigns different values
+                    // the frame shall be considered a failed match
+                    return false;
+                }
+                frame.setValue(positions[i], newValue);
+            }
+            return true;
+        }
+        @Override
+        protected void cleanup(MatchingFrame frame, ISearchContext context) {
+            for (Integer position : unboundVariableIndices) {
+                frame.setValue(position, null);
+            }
+        }
+                @Override
+        public ISearchOperation getOperation() {
+            return GenericTypeExtend.this;
+        }
+    }
+    private final IInputKey type;
+    private final int[] positions;
+    private final List<Integer> positionList;
+    private final Set<Integer> unboundVariableIndices;
+    private final TupleMask indexerMask;
+    private final TupleMask callMask;
+    /**
+     *
+     * @param type
+     *            the type to execute the extend operation on
+     * @param positions
+     *            the parameter positions that represent the variables of the input key
+     * @param unboundVariableIndices
+     *            the set of positions that are bound at the start of the operation
+     */
+    public GenericTypeExtend(IInputKey type, int[] positions, TupleMask callMask, TupleMask indexerMask, Set<Integer> unboundVariableIndices) {
+        Preconditions.checkArgument(positions.length == type.getArity(),
+                "The type %s requires %d parameters, but %d positions are provided", type.getPrettyPrintableName(),
+                type.getArity(), positions.length);
+        List<Integer> modifiablePositionList = new ArrayList<>();
+        for (int position : positions) {
+            modifiablePositionList.add(position);
+        }
+        this.positionList = Collections.unmodifiableList(modifiablePositionList);
+        this.positions = positions;
+        this.type = type;
+        this.unboundVariableIndices = unboundVariableIndices;
+        this.indexerMask = indexerMask;
+        this.callMask = callMask;
+    }
+    @Override
+    public IInputKey getIteratedInputKey() {
+        return type;
+    }
+    @Override
+    public ISearchOperationExecutor createExecutor() {
+        return new Executor();
+    }
+    @Override
+    public List<Integer> getVariablePositions() {
+        return positionList;
+    }
+    @Override
+    public String toString() {
+        return toString(Object::toString);
+    }
+    @Override
+    public String toString(@SuppressWarnings("squid:S4276") Function<Integer, String> variableMapping) {
+        return "extend    " + type.getPrettyPrintableName() + "("
+                + positionList.stream()
+                        .map(input -> String.format("%s%s", unboundVariableIndices.contains(input) ? "-" : "+", variableMapping.apply(input)))
+                        .collect(Collectors.joining(", "))
+                + ")";
+    }
+}
diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/localsearch/RelationalLocalSearchBackendFactory.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/localsearch/RelationalLocalSearchBackendFactory.java
new file mode 100644
index 00000000..0c77f587
--- /dev/null
+++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/localsearch/RelationalLocalSearchBackendFactory.java
@@ -0,0 +1,60 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.viatra.internal.localsearch;
+import org.eclipse.viatra.query.runtime.localsearch.matcher.integration.AbstractLocalSearchResultProvider;
+import org.eclipse.viatra.query.runtime.localsearch.matcher.integration.LocalSearchBackend;
+import org.eclipse.viatra.query.runtime.localsearch.matcher.integration.LocalSearchHints;
+import org.eclipse.viatra.query.runtime.localsearch.plan.IPlanProvider;
+import org.eclipse.viatra.query.runtime.localsearch.plan.SimplePlanProvider;
+import org.eclipse.viatra.query.runtime.matchers.backend.IMatcherCapability;
+import org.eclipse.viatra.query.runtime.matchers.backend.IQueryBackend;
+import org.eclipse.viatra.query.runtime.matchers.backend.IQueryBackendFactory;
+import org.eclipse.viatra.query.runtime.matchers.backend.QueryEvaluationHint;
+import org.eclipse.viatra.query.runtime.matchers.context.IQueryBackendContext;
+import org.eclipse.viatra.query.runtime.matchers.psystem.queries.PQuery;
+public class RelationalLocalSearchBackendFactory implements IQueryBackendFactory {
+        public static final RelationalLocalSearchBackendFactory INSTANCE = new RelationalLocalSearchBackendFactory();
+        private RelationalLocalSearchBackendFactory() {
+        }
+        @Override
+        public IQueryBackend create(IQueryBackendContext context) {
+                return new LocalSearchBackend(context) {
+                        // Create a new {@link IPlanProvider}, because the original {@link LocalSearchBackend#planProvider} is not
+                        // accessible.
+                        private final IPlanProvider planProvider = new SimplePlanProvider(context.getLogger());
+                        @Override
+                        protected AbstractLocalSearchResultProvider initializeResultProvider(PQuery query,
+                                                                                                                                                                 QueryEvaluationHint hints) {
+                                return new RelationalLocalSearchResultProvider(this, context, query, planProvider, hints);
+                        }
+                        @Override
+                        public IQueryBackendFactory getFactory() {
+                                return RelationalLocalSearchBackendFactory.this;
+                        }
+                };
+        }
+        @Override
+        public Class<? extends IQueryBackend> getBackendClass() {
+                return LocalSearchBackend.class;
+        }
+        @Override
+        public IMatcherCapability calculateRequiredCapability(PQuery pQuery, QueryEvaluationHint queryEvaluationHint) {
+                return LocalSearchHints.parse(queryEvaluationHint);
+        }
+        @Override
+        public boolean isCaching() {
+                return false;
+        }
+}
diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/localsearch/RelationalLocalSearchResultProvider.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/localsearch/RelationalLocalSearchResultProvider.java
new file mode 100644
index 00000000..da37be14
--- /dev/null
+++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/localsearch/RelationalLocalSearchResultProvider.java
@@ -0,0 +1,28 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.viatra.internal.localsearch;
+import org.eclipse.viatra.query.runtime.localsearch.matcher.integration.AbstractLocalSearchResultProvider;
+import org.eclipse.viatra.query.runtime.localsearch.matcher.integration.LocalSearchBackend;
+import org.eclipse.viatra.query.runtime.localsearch.matcher.integration.LocalSearchHints;
+import org.eclipse.viatra.query.runtime.localsearch.plan.IPlanProvider;
+import org.eclipse.viatra.query.runtime.localsearch.planner.compiler.IOperationCompiler;
+import org.eclipse.viatra.query.runtime.matchers.backend.QueryEvaluationHint;
+import org.eclipse.viatra.query.runtime.matchers.context.IQueryBackendContext;
+import org.eclipse.viatra.query.runtime.matchers.psystem.queries.PQuery;
+class RelationalLocalSearchResultProvider extends AbstractLocalSearchResultProvider {
+        public RelationalLocalSearchResultProvider(LocalSearchBackend backend, IQueryBackendContext context, PQuery query,
+                                                                                           IPlanProvider planProvider, QueryEvaluationHint userHints) {
+                super(backend, context, query, planProvider, userHints);
+        }
+        @Override
+        protected IOperationCompiler getOperationCompiler(IQueryBackendContext backendContext,
+                                                                                                          LocalSearchHints configuration) {
+                return new RelationalOperationCompiler(runtimeContext);
+        }
+}
diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/localsearch/RelationalOperationCompiler.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/localsearch/RelationalOperationCompiler.java
new file mode 100644
index 00000000..f76ef486
--- /dev/null
+++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/localsearch/RelationalOperationCompiler.java
@@ -0,0 +1,70 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.viatra.internal.localsearch;
+import org.eclipse.viatra.query.runtime.localsearch.operations.generic.GenericTypeExtendSingleValue;
+import org.eclipse.viatra.query.runtime.localsearch.operations.util.CallInformation;
+import org.eclipse.viatra.query.runtime.localsearch.planner.compiler.GenericOperationCompiler;
+import org.eclipse.viatra.query.runtime.matchers.context.IInputKey;
+import org.eclipse.viatra.query.runtime.matchers.context.IQueryRuntimeContext;
+import org.eclipse.viatra.query.runtime.matchers.psystem.PVariable;
+import org.eclipse.viatra.query.runtime.matchers.psystem.basicenumerables.PositivePatternCall;
+import org.eclipse.viatra.query.runtime.matchers.psystem.basicenumerables.TypeConstraint;
+import org.eclipse.viatra.query.runtime.matchers.tuple.Tuple;
+import org.eclipse.viatra.query.runtime.matchers.tuple.TupleMask;
+import java.util.*;
+public class RelationalOperationCompiler extends GenericOperationCompiler  {
+        public RelationalOperationCompiler(IQueryRuntimeContext runtimeContext) {
+                super(runtimeContext);
+        }
+        @Override
+        protected void createExtend(TypeConstraint typeConstraint, Map<PVariable, Integer> variableMapping) {
+                IInputKey inputKey = typeConstraint.getSupplierKey();
+                Tuple tuple = typeConstraint.getVariablesTuple();
+                int[] positions = new int[tuple.getSize()];
+                List<Integer> boundVariableIndices = new ArrayList<>();
+                List<Integer> boundVariables = new ArrayList<>();
+                Set<Integer> unboundVariables = new HashSet<>();
+                for (int i = 0; i < tuple.getSize(); i++) {
+                        PVariable variable = (PVariable) tuple.get(i);
+                        Integer position = variableMapping.get(variable);
+                        positions[i] = position;
+                        if (variableBindings.get(typeConstraint).contains(position)) {
+                                boundVariableIndices.add(i);
+                                boundVariables.add(position);
+                        } else {
+                                unboundVariables.add(position);
+                        }
+                }
+                TupleMask indexerMask = TupleMask.fromSelectedIndices(inputKey.getArity(), boundVariableIndices);
+                TupleMask callMask = TupleMask.fromSelectedIndices(variableMapping.size(), boundVariables);
+                // If multiple tuple elements from the indexer should be bound to the same variable, we must use a
+                // {@link GenericTypeExtend} check whether the tuple elements have the same value.
+                if (unboundVariables.size() == 1 && indexerMask.getSize() + 1 == indexerMask.getSourceWidth()) {
+                        operations.add(new GenericTypeExtendSingleValue(inputKey, positions, callMask, indexerMask,
+                                        unboundVariables.iterator().next()));
+                } else {
+                        // Use a fixed version of
+                        // {@code org.eclipse.viatra.query.runtime.localsearch.operations.generic.GenericTypeExtend} that handles
+                        // failed unification of variables correctly.
+                        operations.add(new GenericTypeExtend(inputKey, positions, callMask, indexerMask, unboundVariables));
+                }
+        }
+        @Override
+        protected void createExtend(PositivePatternCall pCall, Map<PVariable, Integer> variableMapping) {
+                CallInformation information = CallInformation.create(pCall, variableMapping, variableBindings.get(pCall));
+                // Use a fixed version of
+                // {@code org.eclipse.viatra.query.runtime.localsearch.operations.extend.ExtendPositivePatternCall} that handles
+                // failed unification of variables correctly.
+                operations.add(new ExtendPositivePatternCall(information));
+                dependencies.add(information.getCallWithAdornment());
+        }
+}
diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/AbstractViatraMatcher.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/AbstractViatraMatcher.java
new file mode 100644
index 00000000..99b0a3d8
--- /dev/null
+++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/AbstractViatraMatcher.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.viatra.internal.matcher;
+import org.eclipse.viatra.query.runtime.matchers.backend.IQueryResultProvider;
+import org.eclipse.viatra.query.runtime.matchers.backend.IUpdateable;
+import tools.refinery.store.query.dnf.Query;
+import tools.refinery.store.query.resultset.AbstractResultSet;
+import tools.refinery.store.query.viatra.internal.ViatraModelQueryAdapterImpl;
+public abstract class AbstractViatraMatcher<T> extends AbstractResultSet<T> implements IUpdateable {
+        protected final IQueryResultProvider backend;
+        protected AbstractViatraMatcher(ViatraModelQueryAdapterImpl 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-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/FunctionalCursor.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/FunctionalCursor.java
new file mode 100644
index 00000000..47efb2aa
--- /dev/null
+++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/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.viatra.internal.matcher;
+import org.eclipse.viatra.query.runtime.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<org.eclipse.viatra.query.runtime.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-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/FunctionalViatraMatcher.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/FunctionalViatraMatcher.java
new file mode 100644
index 00000000..db4740cd
--- /dev/null
+++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/FunctionalViatraMatcher.java
@@ -0,0 +1,88 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.viatra.internal.matcher;
+import org.eclipse.viatra.query.runtime.matchers.tuple.TupleMask;
+import org.eclipse.viatra.query.runtime.matchers.tuple.Tuples;
+import org.eclipse.viatra.query.runtime.rete.index.IterableIndexer;
+import org.eclipse.viatra.query.runtime.rete.matcher.RetePatternMatcher;
+import tools.refinery.store.map.Cursor;
+import tools.refinery.store.query.dnf.FunctionalQuery;
+import tools.refinery.store.query.viatra.internal.ViatraModelQueryAdapterImpl;
+import tools.refinery.store.tuple.Tuple;
+/**
+ * Directly access the tuples inside a VIATRA pattern matcher.<p>
+ * This class neglects calling
+ * {@link org.eclipse.viatra.query.runtime.matchers.context.IQueryRuntimeContext#wrapTuple(org.eclipse.viatra.query.runtime.matchers.tuple.Tuple)}
+ * and
+ * {@link org.eclipse.viatra.query.runtime.matchers.context.IQueryRuntimeContext#unwrapTuple(org.eclipse.viatra.query.runtime.matchers.tuple.Tuple)},
+ * because {@link tools.refinery.store.query.viatra.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 FunctionalViatraMatcher<T> extends AbstractViatraMatcher<T> {
+        private final TupleMask emptyMask;
+        private final TupleMask omitOutputMask;
+        private final IterableIndexer omitOutputIndexer;
+        public FunctionalViatraMatcher(ViatraModelQueryAdapterImpl 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 = IndexerUtils.getIndexer(reteBackend, 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(org.eclipse.viatra.query.runtime.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-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/IndexerUtils.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/IndexerUtils.java
new file mode 100644
index 00000000..15f00b2d
--- /dev/null
+++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/IndexerUtils.java
@@ -0,0 +1,53 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.viatra.internal.matcher;
+import org.eclipse.viatra.query.runtime.matchers.tuple.TupleMask;
+import org.eclipse.viatra.query.runtime.rete.index.Indexer;
+import org.eclipse.viatra.query.runtime.rete.matcher.ReteEngine;
+import org.eclipse.viatra.query.runtime.rete.matcher.RetePatternMatcher;
+import org.eclipse.viatra.query.runtime.rete.traceability.RecipeTraceInfo;
+import java.lang.invoke.MethodHandle;
+import java.lang.invoke.MethodHandles;
+import java.lang.invoke.MethodType;
+final class IndexerUtils {
+    private static final MethodHandle GET_ENGINE_HANDLE;
+    private static final MethodHandle GET_PRODUCTION_NODE_TRACE_HANDLE;
+    private static final MethodHandle ACCESS_PROJECTION_HANDLE;
+    static {
+        try {
+            var lookup = MethodHandles.privateLookupIn(RetePatternMatcher.class, MethodHandles.lookup());
+            GET_ENGINE_HANDLE = lookup.findGetter(RetePatternMatcher.class, "engine", ReteEngine.class);
+            GET_PRODUCTION_NODE_TRACE_HANDLE = lookup.findGetter(RetePatternMatcher.class, "productionNodeTrace",
+                    RecipeTraceInfo.class);
+            ACCESS_PROJECTION_HANDLE = lookup.findVirtual(ReteEngine.class, "accessProjection",
+                    MethodType.methodType(Indexer.class, RecipeTraceInfo.class, TupleMask.class));
+        } catch (IllegalAccessException | NoSuchFieldException | NoSuchMethodException e) {
+            throw new IllegalStateException("Cannot access private members of %s"
+                    .formatted(RetePatternMatcher.class.getPackageName()), e);
+        }
+    }
+    private IndexerUtils() {
+        throw new IllegalStateException("This is a static utility class and should not be instantiated directly");
+    }
+    public static Indexer getIndexer(RetePatternMatcher backend, TupleMask mask) {
+        try {
+            var engine = (ReteEngine) GET_ENGINE_HANDLE.invokeExact(backend);
+            var trace = (RecipeTraceInfo) GET_PRODUCTION_NODE_TRACE_HANDLE.invokeExact(backend);
+            return (Indexer) ACCESS_PROJECTION_HANDLE.invokeExact(engine, trace, mask);
+        } catch (Error e) {
+            // Fatal JVM errors should not be wrapped.
+            throw e;
+        } catch (Throwable e) {
+            throw new IllegalStateException("Cannot access matcher for mask " + mask, e);
+        }
+    }
+}
diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/MatcherUtils.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/MatcherUtils.java
new file mode 100644
index 00000000..6e24812a
--- /dev/null
+++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/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.viatra.internal.matcher;
+import org.eclipse.viatra.query.runtime.matchers.tuple.ITuple;
+import org.eclipse.viatra.query.runtime.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 org.eclipse.viatra.query.runtime.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-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/RawPatternMatcher.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/RawPatternMatcher.java
new file mode 100644
index 00000000..5b82c4b7
--- /dev/null
+++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/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.viatra.internal.matcher;
+import org.eclipse.viatra.query.runtime.api.GenericPatternMatcher;
+import org.eclipse.viatra.query.runtime.api.GenericQuerySpecification;
+import org.eclipse.viatra.query.runtime.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-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/RelationalCursor.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/RelationalCursor.java
new file mode 100644
index 00000000..1dc8f5db
--- /dev/null
+++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/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.viatra.internal.matcher;
+import org.eclipse.viatra.query.runtime.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-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/RelationalViatraMatcher.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/RelationalViatraMatcher.java
new file mode 100644
index 00000000..ac95dcc0
--- /dev/null
+++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/RelationalViatraMatcher.java
@@ -0,0 +1,80 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.viatra.internal.matcher;
+import org.eclipse.viatra.query.runtime.matchers.tuple.TupleMask;
+import org.eclipse.viatra.query.runtime.matchers.tuple.Tuples;
+import org.eclipse.viatra.query.runtime.rete.index.Indexer;
+import org.eclipse.viatra.query.runtime.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.viatra.internal.ViatraModelQueryAdapterImpl;
+import tools.refinery.store.tuple.Tuple;
+/**
+ * Directly access the tuples inside a VIATRA pattern matcher.<p>
+ * This class neglects calling
+ * {@link org.eclipse.viatra.query.runtime.matchers.context.IQueryRuntimeContext#wrapTuple(org.eclipse.viatra.query.runtime.matchers.tuple.Tuple)}
+ * and
+ * {@link org.eclipse.viatra.query.runtime.matchers.context.IQueryRuntimeContext#unwrapTuple(org.eclipse.viatra.query.runtime.matchers.tuple.Tuple)},
+ * because {@link tools.refinery.store.query.viatra.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 RelationalViatraMatcher extends AbstractViatraMatcher<Boolean> {
+        private final TupleMask emptyMask;
+        private final TupleMask identityMask;
+        private final Indexer emptyMaskIndexer;
+        public RelationalViatraMatcher(ViatraModelQueryAdapterImpl 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 = IndexerUtils.getIndexer(reteBackend, 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(org.eclipse.viatra.query.runtime.matchers.tuple.Tuple updateElement, boolean isInsertion) {
+                var key = MatcherUtils.toRefineryTuple(updateElement);
+                notifyChange(key, !isInsertion, isInsertion);
+        }
+}
diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/UnsafeFunctionalCursor.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/UnsafeFunctionalCursor.java
new file mode 100644
index 00000000..b0b507fe
--- /dev/null
+++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/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.viatra.internal.matcher;
+import org.eclipse.viatra.query.runtime.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-viatra/src/main/java/tools/refinery/store/query/viatra/internal/pquery/AssumptionEvaluator.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/pquery/AssumptionEvaluator.java
new file mode 100644
index 00000000..cf127291
--- /dev/null
+++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/pquery/AssumptionEvaluator.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.viatra.internal.pquery;
+import org.eclipse.viatra.query.runtime.matchers.psystem.IValueProvider;
+import tools.refinery.store.query.term.Term;
+class AssumptionEvaluator extends TermEvaluator<Boolean> {
+        public AssumptionEvaluator(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-viatra/src/main/java/tools/refinery/store/query/viatra/internal/pquery/DNF2PQuery.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/pquery/DNF2PQuery.java
deleted file mode 100644
index 60f1bcae..00000000
--- a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/pquery/DNF2PQuery.java
+++ /dev/null
@@ -1,223 +0,0 @@
-package tools.refinery.store.query.viatra.internal.pquery;
-import org.eclipse.viatra.query.runtime.matchers.backend.QueryEvaluationHint;
-import org.eclipse.viatra.query.runtime.matchers.context.IInputKey;
-import org.eclipse.viatra.query.runtime.matchers.psystem.PBody;
-import org.eclipse.viatra.query.runtime.matchers.psystem.PVariable;
-import org.eclipse.viatra.query.runtime.matchers.psystem.annotations.PAnnotation;
-import org.eclipse.viatra.query.runtime.matchers.psystem.basicdeferred.Equality;
-import org.eclipse.viatra.query.runtime.matchers.psystem.basicdeferred.ExportedParameter;
-import org.eclipse.viatra.query.runtime.matchers.psystem.basicdeferred.Inequality;
-import org.eclipse.viatra.query.runtime.matchers.psystem.basicdeferred.NegativePatternCall;
-import org.eclipse.viatra.query.runtime.matchers.psystem.basicenumerables.BinaryTransitiveClosure;
-import org.eclipse.viatra.query.runtime.matchers.psystem.basicenumerables.ConstantValue;
-import org.eclipse.viatra.query.runtime.matchers.psystem.basicenumerables.PositivePatternCall;
-import org.eclipse.viatra.query.runtime.matchers.psystem.basicenumerables.TypeConstraint;
-import org.eclipse.viatra.query.runtime.matchers.psystem.queries.PParameter;
-import org.eclipse.viatra.query.runtime.matchers.psystem.queries.PVisibility;
-import org.eclipse.viatra.query.runtime.matchers.tuple.Tuple;
-import org.eclipse.viatra.query.runtime.matchers.tuple.Tuples;
-import tools.refinery.store.query.DNF;
-import tools.refinery.store.query.DNFAnd;
-import tools.refinery.store.query.DNFUtils;
-import tools.refinery.store.query.Variable;
-import tools.refinery.store.query.atom.*;
-import tools.refinery.store.query.view.AnyRelationView;
-import java.util.*;
-import java.util.function.Function;
-import java.util.stream.Collectors;
-public class DNF2PQuery {
-        private static final Object P_CONSTRAINT_LOCK = new Object();
-        private final Set<DNF> translating = new LinkedHashSet<>();
-        private final Map<DNF, RawPQuery> dnf2PQueryMap = new HashMap<>();
-        private final Map<AnyRelationView, RelationViewWrapper> view2WrapperMap = new LinkedHashMap<>();
-        private final Map<AnyRelationView, RawPQuery> view2EmbeddedMap = new HashMap<>();
-        private Function<DNF, QueryEvaluationHint> computeHint = dnf -> new QueryEvaluationHint(null,
-                        QueryEvaluationHint.BackendRequirement.UNSPECIFIED);
-        public void setComputeHint(Function<DNF, QueryEvaluationHint> computeHint) {
-                this.computeHint = computeHint;
-        }
-        public RawPQuery translate(DNF dnfQuery) {
-                if (translating.contains(dnfQuery)) {
-                        var path = translating.stream().map(DNF::name).collect(Collectors.joining(" -> "));
-                        throw new IllegalStateException("Circular reference %s -> %s detected".formatted(path,
-                                        dnfQuery.name()));
-                }
-                // We can't use computeIfAbsent here, because translating referenced queries calls this method in a reentrant
-                // way, which would cause a ConcurrentModificationException with computeIfAbsent.
-                var pQuery = dnf2PQueryMap.get(dnfQuery);
-                if (pQuery == null) {
-                        translating.add(dnfQuery);
-                        try {
-                                pQuery = doTranslate(dnfQuery);
-                                dnf2PQueryMap.put(dnfQuery, pQuery);
-                        } finally {
-                                translating.remove(dnfQuery);
-                        }
-                }
-                return pQuery;
-        }
-        public Map<AnyRelationView, IInputKey> getRelationViews() {
-                return Collections.unmodifiableMap(view2WrapperMap);
-        }
-        public RawPQuery getAlreadyTranslated(DNF dnfQuery) {
-                return dnf2PQueryMap.get(dnfQuery);
-        }
-        private RawPQuery doTranslate(DNF dnfQuery) {
-                var pQuery = new RawPQuery(dnfQuery.getUniqueName());
-                pQuery.setEvaluationHints(computeHint.apply(dnfQuery));
-                Map<Variable, PParameter> parameters = new HashMap<>();
-                for (Variable variable : dnfQuery.getParameters()) {
-                        parameters.put(variable, new PParameter(variable.getUniqueName()));
-                }
-                List<PParameter> parameterList = new ArrayList<>();
-                for (var param : dnfQuery.getParameters()) {
-                        parameterList.add(parameters.get(param));
-                }
-                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);
-                }
-                // The constructor of {@link org.eclipse.viatra.query.runtime.matchers.psystem.BasePConstraint} mutates
-                // global static state (<code>nextID</code>) without locking. Therefore, we need to synchronize before creating
-                // any query constraints to avoid a data race.
-                synchronized (P_CONSTRAINT_LOCK) {
-                        for (DNFAnd clause : dnfQuery.getClauses()) {
-                                PBody body = new PBody(pQuery);
-                                List<ExportedParameter> symbolicParameters = new ArrayList<>();
-                                for (var param : dnfQuery.getParameters()) {
-                                        PVariable pVar = body.getOrCreateVariableByName(param.getUniqueName());
-                                        symbolicParameters.add(new ExportedParameter(body, pVar, parameters.get(param)));
-                                }
-                                body.setSymbolicParameters(symbolicParameters);
-                                pQuery.addBody(body);
-                                for (DNFAtom constraint : clause.constraints()) {
-                                        translateDNFAtom(constraint, body);
-                                }
-                        }
-                }
-                return pQuery;
-        }
-        private void translateDNFAtom(DNFAtom constraint, PBody body) {
-                if (constraint instanceof EquivalenceAtom equivalenceAtom) {
-                        translateEquivalenceAtom(equivalenceAtom, body);
-                } else if (constraint instanceof RelationViewAtom relationViewAtom) {
-                        translateRelationViewAtom(relationViewAtom, body);
-                } else if (constraint instanceof DNFCallAtom callAtom) {
-                        translateCallAtom(callAtom, body);
-                } else if (constraint instanceof ConstantAtom constantAtom) {
-                        translateConstantAtom(constantAtom, body);
-                } else {
-                        throw new IllegalArgumentException("Unknown constraint: " + constraint.toString());
-                }
-        }
-        private void translateEquivalenceAtom(EquivalenceAtom equivalence, PBody body) {
-                PVariable varSource = body.getOrCreateVariableByName(equivalence.left().getUniqueName());
-                PVariable varTarget = body.getOrCreateVariableByName(equivalence.right().getUniqueName());
-                if (equivalence.positive()) {
-                        new Equality(body, varSource, varTarget);
-                } else {
-                        new Inequality(body, varSource, varTarget);
-                }
-        }
-        private void translateRelationViewAtom(RelationViewAtom relationViewAtom, PBody body) {
-                var substitution = translateSubstitution(relationViewAtom.getSubstitution(), body);
-                var polarity = relationViewAtom.getPolarity();
-                var relationView = relationViewAtom.getTarget();
-                if (polarity == CallPolarity.POSITIVE) {
-                        new TypeConstraint(body, substitution, wrapView(relationView));
-                } else {
-                        var embeddedPQuery = translateEmbeddedRelationViewPQuery(relationView);
-                        switch (polarity) {
-                        case TRANSITIVE -> new BinaryTransitiveClosure(body, substitution, embeddedPQuery);
-                        case NEGATIVE -> new NegativePatternCall(body, substitution, embeddedPQuery);
-                        default -> throw new IllegalArgumentException("Unknown polarity: " + polarity);
-                        }
-                }
-        }
-        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 RawPQuery translateEmbeddedRelationViewPQuery(AnyRelationView relationView) {
-                return view2EmbeddedMap.computeIfAbsent(relationView, this::doTranslateEmbeddedRelationViewPQuery);
-        }
-        private RawPQuery doTranslateEmbeddedRelationViewPQuery(AnyRelationView relationView) {
-                var embeddedPQuery = new RawPQuery(DNFUtils.generateUniqueName(relationView.name()), PVisibility.EMBEDDED);
-                var body = new PBody(embeddedPQuery);
-                int arity = relationView.arity();
-                var parameters = new ArrayList<PParameter>(arity);
-                var arguments = new Object[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);
-                        arguments[i] = variable;
-                        symbolicParameters.add(new ExportedParameter(body, variable, parameter));
-                }
-                embeddedPQuery.setParameters(parameters);
-                body.setSymbolicParameters(symbolicParameters);
-                var argumentTuple = Tuples.flatTupleOf(arguments);
-                new TypeConstraint(body, argumentTuple, wrapView(relationView));
-                embeddedPQuery.addBody(body);
-                return embeddedPQuery;
-        }
-        private RelationViewWrapper wrapView(AnyRelationView relationView) {
-                return view2WrapperMap.computeIfAbsent(relationView, RelationViewWrapper::new);
-        }
-        private void translateCallAtom(DNFCallAtom callAtom, PBody body) {
-                var variablesTuple = translateSubstitution(callAtom.getSubstitution(), body);
-                var translatedReferred = translate(callAtom.getTarget());
-                var polarity = callAtom.getPolarity();
-                switch (polarity) {
-                case POSITIVE -> new PositivePatternCall(body, variablesTuple, translatedReferred);
-                case TRANSITIVE -> new BinaryTransitiveClosure(body, variablesTuple, translatedReferred);
-                case NEGATIVE -> new NegativePatternCall(body, variablesTuple, translatedReferred);
-                default -> throw new IllegalArgumentException("Unknown polarity: " + polarity);
-                }
-        }
-        private void translateConstantAtom(ConstantAtom constantAtom, PBody body) {
-                var variable = body.getOrCreateVariableByName(constantAtom.variable().getUniqueName());
-                new ConstantValue(body, variable, constantAtom.nodeId());
-        }
-}
diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/pquery/Dnf2PQuery.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/pquery/Dnf2PQuery.java
new file mode 100644
index 00000000..5b0ea61d
--- /dev/null
+++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/pquery/Dnf2PQuery.java
@@ -0,0 +1,266 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.viatra.internal.pquery;
+import org.eclipse.viatra.query.runtime.matchers.backend.IQueryBackendFactory;
+import org.eclipse.viatra.query.runtime.matchers.backend.QueryEvaluationHint;
+import org.eclipse.viatra.query.runtime.matchers.context.IInputKey;
+import org.eclipse.viatra.query.runtime.matchers.psystem.PBody;
+import org.eclipse.viatra.query.runtime.matchers.psystem.PVariable;
+import org.eclipse.viatra.query.runtime.matchers.psystem.aggregations.BoundAggregator;
+import org.eclipse.viatra.query.runtime.matchers.psystem.aggregations.IMultisetAggregationOperator;
+import org.eclipse.viatra.query.runtime.matchers.psystem.annotations.PAnnotation;
+import org.eclipse.viatra.query.runtime.matchers.psystem.basicdeferred.*;
+import org.eclipse.viatra.query.runtime.matchers.psystem.basicenumerables.BinaryTransitiveClosure;
+import org.eclipse.viatra.query.runtime.matchers.psystem.basicenumerables.ConstantValue;
+import org.eclipse.viatra.query.runtime.matchers.psystem.basicenumerables.PositivePatternCall;
+import org.eclipse.viatra.query.runtime.matchers.psystem.basicenumerables.TypeConstraint;
+import org.eclipse.viatra.query.runtime.matchers.psystem.queries.PParameter;
+import org.eclipse.viatra.query.runtime.matchers.psystem.queries.PParameterDirection;
+import org.eclipse.viatra.query.runtime.matchers.psystem.queries.PQuery;
+import org.eclipse.viatra.query.runtime.matchers.tuple.Tuple;
+import org.eclipse.viatra.query.runtime.matchers.tuple.Tuples;
+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 java.util.*;
+import java.util.function.Function;
+import java.util.stream.Collectors;
+public class Dnf2PQuery {
+        private static final Object P_CONSTRAINT_LOCK = new Object();
+        private final CycleDetectingMapper<Dnf, RawPQuery> mapper = new CycleDetectingMapper<>(Dnf::name,
+                        this::doTranslate);
+        private final QueryWrapperFactory wrapperFactory = new QueryWrapperFactory(this);
+        private final Map<Dnf, QueryEvaluationHint> hintOverrides = new LinkedHashMap<>();
+        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();
+        }
+        public void hint(Dnf dnf, QueryEvaluationHint hint) {
+                hintOverrides.compute(dnf, (ignoredKey, existingHint) ->
+                                existingHint == null ? hint : existingHint.overrideBy(hint));
+        }
+        private QueryEvaluationHint consumeHint(Dnf dnf) {
+                var defaultHint = computeHint.apply(dnf);
+                var existingHint = hintOverrides.remove(dnf);
+                return defaultHint.overrideBy(existingHint);
+        }
+        public void assertNoUnusedHints() {
+                if (hintOverrides.isEmpty()) {
+                        return;
+                }
+                var unusedHints = hintOverrides.keySet().stream().map(Dnf::name).collect(Collectors.joining(", "));
+                throw new IllegalStateException(
+                                "Unused query evaluation hints for %s. Hints must be set before a query is added to the engine"
+                                                .formatted(unusedHints));
+        }
+        private RawPQuery doTranslate(Dnf dnfQuery) {
+                var pQuery = new RawPQuery(dnfQuery.getUniqueName());
+                pQuery.setEvaluationHints(consumeHint(dnfQuery));
+                Map<SymbolicParameter, PParameter> parameters = new HashMap<>();
+                List<PParameter> parameterList = new ArrayList<>();
+                for (var parameter : dnfQuery.getSymbolicParameters()) {
+                        var direction = switch (parameter.getDirection()) {
+                                case OUT -> parameter.isUnifiable() ? PParameterDirection.INOUT : PParameterDirection.OUT;
+                                case IN -> throw new IllegalArgumentException("Query %s with input parameter %s is not supported"
+                                                .formatted(dnfQuery, parameter.getVariable()));
+                        };
+                        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);
+                }
+                // The constructor of {@link org.eclipse.viatra.query.runtime.matchers.psystem.BasePConstraint} mutates
+                // global static state (<code>nextID</code>) without locking. Therefore, we need to synchronize before creating
+                // any query literals to avoid a data race.
+                synchronized (P_CONSTRAINT_LOCK) {
+                        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 AssumeLiteral assumeLiteral) {
+                        translateAssumeLiteral(assumeLiteral, body);
+                } else if (literal instanceof CountLiteral countLiteral) {
+                        translateCountLiteral(countLiteral, body);
+                } else if (literal instanceof AggregationLiteral<?, ?> aggregationLiteral) {
+                        translateAggregationLiteral(aggregationLiteral, body);
+                } else {
+                        throw new IllegalArgumentException("Unknown literal: " + literal.toString());
+                }
+        }
+        private void translateEquivalenceLiteral(EquivalenceLiteral equivalenceLiteral, PBody body) {
+                PVariable varSource = body.getOrCreateVariableByName(equivalenceLiteral.left().getUniqueName());
+                PVariable varTarget = body.getOrCreateVariableByName(equivalenceLiteral.right().getUniqueName());
+                if (equivalenceLiteral.positive()) {
+                        new Equality(body, varSource, varTarget);
+                } else {
+                        new Inequality(body, varSource, varTarget);
+                }
+        }
+        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 constraint = callLiteral.getTarget();
+                        PQuery pattern;
+                        if (constraint instanceof Dnf dnf) {
+                                pattern = translate(dnf);
+                        } else if (constraint instanceof AnySymbolView symbolView) {
+                                pattern = wrapperFactory.wrapSymbolViewIdentityArguments(symbolView);
+                        } else {
+                                throw new IllegalArgumentException("Unknown Constraint: " + constraint);
+                        }
+                        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 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.variable().getUniqueName());
+                new ConstantValue(body, variable, constantLiteral.nodeId());
+        }
+        private <T> void translateAssignLiteral(AssignLiteral<T> assignLiteral, PBody body) {
+                var variable = body.getOrCreateVariableByName(assignLiteral.variable().getUniqueName());
+                var term = assignLiteral.term();
+                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 translateAssumeLiteral(AssumeLiteral assumeLiteral, PBody body) {
+                var evaluator = new AssumptionEvaluator(assumeLiteral.term());
+                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);
+        }
+}
diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/pquery/QueryWrapperFactory.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/pquery/QueryWrapperFactory.java
new file mode 100644
index 00000000..2b7280f2
--- /dev/null
+++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/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.viatra.internal.pquery;
+import org.eclipse.viatra.query.runtime.matchers.context.IInputKey;
+import org.eclipse.viatra.query.runtime.matchers.psystem.PBody;
+import org.eclipse.viatra.query.runtime.matchers.psystem.PVariable;
+import org.eclipse.viatra.query.runtime.matchers.psystem.basicdeferred.ExportedParameter;
+import org.eclipse.viatra.query.runtime.matchers.psystem.basicenumerables.PositivePatternCall;
+import org.eclipse.viatra.query.runtime.matchers.psystem.basicenumerables.TypeConstraint;
+import org.eclipse.viatra.query.runtime.matchers.psystem.queries.PParameter;
+import org.eclipse.viatra.query.runtime.matchers.psystem.queries.PQuery;
+import org.eclipse.viatra.query.runtime.matchers.psystem.queries.PVisibility;
+import org.eclipse.viatra.query.runtime.matchers.tuple.Tuple;
+import org.eclipse.viatra.query.runtime.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<>(
+                        RemappedConstraint::toString, 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 VIATRA 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-viatra/src/main/java/tools/refinery/store/query/viatra/internal/pquery/RawPQuery.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/pquery/RawPQuery.java
index 71b74396..255738c5 100644
--- a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/pquery/RawPQuery.java
+++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/pquery/RawPQuery.java
@@ -1,3 +1,8 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
 package tools.refinery.store.query.viatra.internal.pquery;
 import org.eclipse.viatra.query.runtime.api.GenericQuerySpecification;
@@ -9,6 +14,7 @@ import org.eclipse.viatra.query.runtime.matchers.psystem.queries.BasePQuery;
 import org.eclipse.viatra.query.runtime.matchers.psystem.queries.PParameter;
 import org.eclipse.viatra.query.runtime.matchers.psystem.queries.PVisibility;
 import tools.refinery.store.query.viatra.internal.RelationalScope;
+import tools.refinery.store.query.viatra.internal.matcher.RawPatternMatcher;
 import java.util.LinkedHashSet;
 import java.util.List;
diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/pquery/RawPatternMatcher.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/pquery/RawPatternMatcher.java
deleted file mode 100644
index e944e873..00000000
--- a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/pquery/RawPatternMatcher.java
+++ /dev/null
@@ -1,72 +0,0 @@
-package tools.refinery.store.query.viatra.internal.pquery;
-import org.eclipse.viatra.query.runtime.api.GenericPatternMatcher;
-import org.eclipse.viatra.query.runtime.api.GenericQuerySpecification;
-import tools.refinery.store.query.ResultSet;
-import tools.refinery.store.query.viatra.ViatraTupleLike;
-import tools.refinery.store.tuple.Tuple;
-import tools.refinery.store.tuple.TupleLike;
-import java.util.Optional;
-import java.util.stream.Stream;
-public class RawPatternMatcher extends GenericPatternMatcher implements ResultSet {
-        protected final Object[] empty;
-        public RawPatternMatcher(GenericQuerySpecification<? extends GenericPatternMatcher> specification) {
-                super(specification);
-                empty = new Object[specification.getParameterNames().size()];
-        }
-        @Override
-        public boolean hasResult() {
-                return backend.hasMatch(empty);
-        }
-        @Override
-        public boolean hasResult(Tuple parameters) {
-                return backend.hasMatch(toParametersArray(parameters));
-        }
-        @Override
-        public Optional<TupleLike> oneResult() {
-                return backend.getOneArbitraryMatch(empty).map(ViatraTupleLike::new);
-        }
-        @Override
-        public Optional<TupleLike> oneResult(Tuple parameters) {
-                return backend.getOneArbitraryMatch(toParametersArray(parameters)).map(ViatraTupleLike::new);
-        }
-        @Override
-        public Stream<TupleLike> allResults() {
-                return backend.getAllMatches(empty).map(ViatraTupleLike::new);
-        }
-        @Override
-        public Stream<TupleLike> allResults(Tuple parameters) {
-                return backend.getAllMatches(toParametersArray(parameters)).map(ViatraTupleLike::new);
-        }
-        @Override
-        public int countResults() {
-                return backend.countMatches(empty);
-        }
-        @Override
-        public int countResults(Tuple parameters) {
-                return backend.countMatches(toParametersArray(parameters));
-        }
-        private Object[] toParametersArray(Tuple tuple) {
-                int size = tuple.getSize();
-                var array = new Object[tuple.getSize()];
-                for (int i = 0; i < size; i++) {
-                        var value = tuple.get(i);
-                        if (value >= 0) {
-                                array[i] = Tuple.of(value);
-                        }
-                }
-                return array;
-        }
-}
diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/pquery/StatefulMultisetAggregator.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/pquery/StatefulMultisetAggregator.java
new file mode 100644
index 00000000..461416f7
--- /dev/null
+++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/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.viatra.internal.pquery;
+import org.eclipse.viatra.query.runtime.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-viatra/src/main/java/tools/refinery/store/query/viatra/internal/pquery/StatelessMultisetAggregator.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/pquery/StatelessMultisetAggregator.java
new file mode 100644
index 00000000..49175d75
--- /dev/null
+++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/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.viatra.internal.pquery;
+import org.eclipse.viatra.query.runtime.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-viatra/src/main/java/tools/refinery/store/query/viatra/internal/pquery/RelationViewWrapper.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/pquery/SymbolViewWrapper.java
index c442add8..a777613e 100644
--- a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/pquery/RelationViewWrapper.java
+++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/pquery/SymbolViewWrapper.java
@@ -1,10 +1,15 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
 package tools.refinery.store.query.viatra.internal.pquery;
 import org.eclipse.viatra.query.runtime.matchers.context.common.BaseInputKeyWrapper;
-import tools.refinery.store.query.view.AnyRelationView;
+import tools.refinery.store.query.view.AnySymbolView;
-public class RelationViewWrapper extends BaseInputKeyWrapper<AnyRelationView> {
+public class SymbolViewWrapper extends BaseInputKeyWrapper<AnySymbolView> {
-        public RelationViewWrapper(AnyRelationView wrappedKey) {
+        public SymbolViewWrapper(AnySymbolView wrappedKey) {
                super(wrappedKey);
        }
@@ -27,4 +32,9 @@ public class RelationViewWrapper extends BaseInputKeyWrapper<AnyRelationView> {
        public boolean isEnumerable() {
                return true;
        }
+        @Override
+        public String toString() {
+                return "RelationViewWrapper{wrappedKey=%s}".formatted(wrappedKey);
+        }
 }
diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/pquery/TermEvaluator.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/pquery/TermEvaluator.java
new file mode 100644
index 00000000..1187f57a
--- /dev/null
+++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/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.viatra.internal.pquery;
+import org.eclipse.viatra.query.runtime.matchers.psystem.IExpressionEvaluator;
+import org.eclipse.viatra.query.runtime.matchers.psystem.IValueProvider;
+import tools.refinery.store.query.term.Term;
+import tools.refinery.store.query.term.Variable;
+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-viatra/src/main/java/tools/refinery/store/query/viatra/internal/pquery/ValueProviderBasedValuation.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/pquery/ValueProviderBasedValuation.java
new file mode 100644
index 00000000..62cb8b3a
--- /dev/null
+++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/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.viatra.internal.pquery;
+import org.eclipse.viatra.query.runtime.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-viatra/src/main/java/tools/refinery/store/query/viatra/internal/update/ModelUpdateListener.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/update/ModelUpdateListener.java
index 8a467066..986bb0b1 100644
--- a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/update/ModelUpdateListener.java
+++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/update/ModelUpdateListener.java
@@ -1,47 +1,51 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
 package tools.refinery.store.query.viatra.internal.update;
 import org.eclipse.viatra.query.runtime.matchers.context.IInputKey;
 import org.eclipse.viatra.query.runtime.matchers.context.IQueryRuntimeContextListener;
 import org.eclipse.viatra.query.runtime.matchers.tuple.ITuple;
 import tools.refinery.store.query.viatra.internal.ViatraModelQueryAdapterImpl;
-import tools.refinery.store.query.view.AnyRelationView;
+import tools.refinery.store.query.view.AnySymbolView;
-import tools.refinery.store.query.view.RelationView;
+import tools.refinery.store.query.view.SymbolView;
 import java.util.HashMap;
 import java.util.Map;
 public class ModelUpdateListener {
-        private final Map<AnyRelationView, RelationViewUpdateListener<?>> relationViewUpdateListeners;
+        private final Map<AnySymbolView, SymbolViewUpdateListener<?>> symbolViewUpdateListeners;
        public ModelUpdateListener(ViatraModelQueryAdapterImpl adapter) {
-                var relationViews = adapter.getStoreAdapter().getInputKeys().keySet();
+                var symbolViews = adapter.getStoreAdapter().getInputKeys().keySet();
-                relationViewUpdateListeners = new HashMap<>(relationViews.size());
+                symbolViewUpdateListeners = new HashMap<>(symbolViews.size());
-                for (var relationView : relationViews) {
+                for (var symbolView : symbolViews) {
-                        registerView(adapter, (RelationView<?>) relationView);
+                        registerView(adapter, (SymbolView<?>) symbolView);
                }
        }
-        private <T> void registerView(ViatraModelQueryAdapterImpl adapter, RelationView<T> relationView) {
+        private <T> void registerView(ViatraModelQueryAdapterImpl adapter, SymbolView<T> view) {
-                var listener = RelationViewUpdateListener.of(adapter, relationView);
                var model = adapter.getModel();
-                var interpretation = model.getInterpretation(relationView.getSymbol());
+                var interpretation = model.getInterpretation(view.getSymbol());
-                interpretation.addListener(listener, true);
+                var listener = SymbolViewUpdateListener.of(adapter, view, interpretation);
-                relationViewUpdateListeners.put(relationView, listener);
+                symbolViewUpdateListeners.put(view, listener);
        }
-        public boolean containsRelationView(AnyRelationView relationView) {
+        public boolean containsSymbolView(AnySymbolView relationView) {
-                return relationViewUpdateListeners.containsKey(relationView);
+                return symbolViewUpdateListeners.containsKey(relationView);
        }
-        public void addListener(IInputKey key, AnyRelationView relationView, ITuple seed,
+        public void addListener(IInputKey key, AnySymbolView symbolView, ITuple seed,
                                                        IQueryRuntimeContextListener listener) {
-                var relationViewUpdateListener = relationViewUpdateListeners.get(relationView);
+                var symbolViewUpdateListener = symbolViewUpdateListeners.get(symbolView);
-                relationViewUpdateListener.addFilter(key, seed, listener);
+                symbolViewUpdateListener.addFilter(key, seed, listener);
        }
-        public void removeListener(IInputKey key, AnyRelationView relationView, ITuple seed,
+        public void removeListener(IInputKey key, AnySymbolView symbolView, ITuple seed,
                                                           IQueryRuntimeContextListener listener) {
-                var relationViewUpdateListener = relationViewUpdateListeners.get(relationView);
+                var symbolViewUpdateListener = symbolViewUpdateListeners.get(symbolView);
-                relationViewUpdateListener.removeFilter(key, seed, listener);
+                symbolViewUpdateListener.removeFilter(key, seed, listener);
        }
 }
diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/update/RelationViewFilter.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/update/RelationViewFilter.java
index 221f1b4a..efdbfcbe 100644
--- a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/update/RelationViewFilter.java
+++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/update/RelationViewFilter.java
@@ -1,3 +1,8 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
 package tools.refinery.store.query.viatra.internal.update;
 import org.eclipse.viatra.query.runtime.matchers.context.IInputKey;
diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/update/RelationViewUpdateListener.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/update/RelationViewUpdateListener.java
deleted file mode 100644
index bf6b4197..00000000
--- a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/update/RelationViewUpdateListener.java
+++ /dev/null
@@ -1,48 +0,0 @@
-package tools.refinery.store.query.viatra.internal.update;
-import org.eclipse.viatra.query.runtime.matchers.context.IInputKey;
-import org.eclipse.viatra.query.runtime.matchers.context.IQueryRuntimeContextListener;
-import org.eclipse.viatra.query.runtime.matchers.tuple.ITuple;
-import org.eclipse.viatra.query.runtime.matchers.tuple.Tuple;
-import tools.refinery.store.model.InterpretationListener;
-import tools.refinery.store.query.viatra.internal.ViatraModelQueryAdapterImpl;
-import tools.refinery.store.query.view.RelationView;
-import tools.refinery.store.query.view.TuplePreservingRelationView;
-import java.util.ArrayList;
-import java.util.List;
-public abstract class RelationViewUpdateListener<T> implements InterpretationListener<T> {
-        private final ViatraModelQueryAdapterImpl adapter;
-        private final List<RelationViewFilter> filters = new ArrayList<>();
-        protected RelationViewUpdateListener(ViatraModelQueryAdapterImpl adapter) {
-                this.adapter = adapter;
-        }
-        public void addFilter(IInputKey inputKey, ITuple seed, IQueryRuntimeContextListener listener) {
-                filters.add(new RelationViewFilter(inputKey, seed, listener));
-        }
-        public void removeFilter(IInputKey inputKey, ITuple seed, IQueryRuntimeContextListener listener) {
-                filters.remove(new RelationViewFilter(inputKey, seed, listener));
-        }
-        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> RelationViewUpdateListener<T> of(ViatraModelQueryAdapterImpl adapter,
-                                                                                                           RelationView<T> relationView) {
-                if (relationView instanceof TuplePreservingRelationView<T> tuplePreservingRelationView) {
-                        return new TuplePreservingRelationViewUpdateListener<>(adapter, tuplePreservingRelationView);
-                }
-                return new TupleChangingRelationViewUpdateListener<>(adapter, relationView);
-        }
-}
diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/update/SymbolViewUpdateListener.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/update/SymbolViewUpdateListener.java
new file mode 100644
index 00000000..f1a2ac7c
--- /dev/null
+++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/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.viatra.internal.update;
+import org.eclipse.viatra.query.runtime.matchers.context.IInputKey;
+import org.eclipse.viatra.query.runtime.matchers.context.IQueryRuntimeContextListener;
+import org.eclipse.viatra.query.runtime.matchers.tuple.ITuple;
+import org.eclipse.viatra.query.runtime.matchers.tuple.Tuple;
+import tools.refinery.store.model.Interpretation;
+import tools.refinery.store.model.InterpretationListener;
+import tools.refinery.store.query.viatra.internal.ViatraModelQueryAdapterImpl;
+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 ViatraModelQueryAdapterImpl adapter;
+        private final Interpretation<T> interpretation;
+        private final List<RelationViewFilter> filters = new ArrayList<>();
+        protected SymbolViewUpdateListener(ViatraModelQueryAdapterImpl 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(ViatraModelQueryAdapterImpl 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-viatra/src/main/java/tools/refinery/store/query/viatra/internal/update/TupleChangingRelationViewUpdateListener.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/update/TupleChangingRelationViewUpdateListener.java
deleted file mode 100644
index 14142884..00000000
--- a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/update/TupleChangingRelationViewUpdateListener.java
+++ /dev/null
@@ -1,37 +0,0 @@
-package tools.refinery.store.query.viatra.internal.update;
-import org.eclipse.viatra.query.runtime.matchers.tuple.Tuples;
-import tools.refinery.store.query.viatra.internal.ViatraModelQueryAdapterImpl;
-import tools.refinery.store.query.view.RelationView;
-import tools.refinery.store.tuple.Tuple;
-import java.util.Arrays;
-public class TupleChangingRelationViewUpdateListener<T> extends RelationViewUpdateListener<T> {
-        private final RelationView<T> relationView;
-        TupleChangingRelationViewUpdateListener(ViatraModelQueryAdapterImpl adapter, RelationView<T> relationView) {
-        super(adapter);
-        this.relationView = relationView;
-        }
-        @Override
-        public void put(Tuple key, T fromValue, T toValue, boolean restoring) {
-                boolean fromPresent = relationView.filter(key, fromValue);
-                boolean toPresent = relationView.filter(key, toValue);
-                if (fromPresent) {
-                        if (toPresent) { // value change
-                                var fromArray = relationView.forwardMap(key, fromValue);
-                                var toArray = relationView.forwardMap(key, toValue);
-                                if (!Arrays.equals(fromArray, toArray)) {
-                                        processUpdate(Tuples.flatTupleOf(fromArray), false);
-                                        processUpdate(Tuples.flatTupleOf(toArray), true);
-                                }
-                        } else { // fromValue disappears
-                                processUpdate(Tuples.flatTupleOf(relationView.forwardMap(key, fromValue)), false);
-                        }
-                } else if (toPresent) { // toValue appears
-                        processUpdate(Tuples.flatTupleOf(relationView.forwardMap(key, toValue)), true);
-                }
-        }
-}
diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/update/TupleChangingViewUpdateListener.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/update/TupleChangingViewUpdateListener.java
new file mode 100644
index 00000000..45d35571
--- /dev/null
+++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/update/TupleChangingViewUpdateListener.java
@@ -0,0 +1,44 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.viatra.internal.update;
+import org.eclipse.viatra.query.runtime.matchers.tuple.Tuples;
+import tools.refinery.store.model.Interpretation;
+import tools.refinery.store.query.viatra.internal.ViatraModelQueryAdapterImpl;
+import tools.refinery.store.query.view.SymbolView;
+import tools.refinery.store.tuple.Tuple;
+import java.util.Arrays;
+public class TupleChangingViewUpdateListener<T> extends SymbolViewUpdateListener<T> {
+        private final SymbolView<T> view;
+        TupleChangingViewUpdateListener(ViatraModelQueryAdapterImpl 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) {
+                        if (toPresent) { // value change
+                                var fromArray = view.forwardMap(key, fromValue);
+                                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(view.forwardMap(key, fromValue)), false);
+                        }
+                } else if (toPresent) { // toValue appears
+                        processUpdate(Tuples.flatTupleOf(view.forwardMap(key, toValue)), true);
+                }
+        }
+}
diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/update/TuplePreservingRelationViewUpdateListener.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/update/TuplePreservingViewUpdateListener.java
index 288e018a..c18dbafb 100644
--- a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/update/TuplePreservingRelationViewUpdateListener.java
+++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/update/TuplePreservingViewUpdateListener.java
@@ -1,16 +1,22 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
 package tools.refinery.store.query.viatra.internal.update;
 import org.eclipse.viatra.query.runtime.matchers.tuple.Tuples;
+import tools.refinery.store.model.Interpretation;
 import tools.refinery.store.query.viatra.internal.ViatraModelQueryAdapterImpl;
-import tools.refinery.store.query.view.TuplePreservingRelationView;
+import tools.refinery.store.query.view.TuplePreservingView;
 import tools.refinery.store.tuple.Tuple;
-public class TuplePreservingRelationViewUpdateListener<T> extends RelationViewUpdateListener<T> {
+public class TuplePreservingViewUpdateListener<T> extends SymbolViewUpdateListener<T> {
-        private final TuplePreservingRelationView<T> view;
+        private final TuplePreservingView<T> view;
-        TuplePreservingRelationViewUpdateListener(ViatraModelQueryAdapterImpl adapter,
+        TuplePreservingViewUpdateListener(ViatraModelQueryAdapterImpl adapter, TuplePreservingView<T> view,
-                                                                                          TuplePreservingRelationView<T> view) {
+                                                                          Interpretation<T> interpretation) {
-        super(adapter);
+        super(adapter, interpretation);
        this.view = view;
        }
diff --git a/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/DiagonalQueryTest.java b/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/DiagonalQueryTest.java
new file mode 100644
index 00000000..6aae2ebe
--- /dev/null
+++ b/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/DiagonalQueryTest.java
@@ -0,0 +1,390 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.viatra;
+import org.eclipse.viatra.query.runtime.matchers.backend.QueryEvaluationHint;
+import tools.refinery.store.model.ModelStore;
+import tools.refinery.store.query.ModelQueryAdapter;
+import tools.refinery.store.query.dnf.Dnf;
+import tools.refinery.store.query.dnf.Query;
+import tools.refinery.store.query.viatra.tests.QueryEngineTest;
+import tools.refinery.store.query.view.AnySymbolView;
+import tools.refinery.store.query.view.FunctionView;
+import tools.refinery.store.query.view.KeyOnlyView;
+import tools.refinery.store.representation.Symbol;
+import tools.refinery.store.tuple.Tuple;
+import java.util.List;
+import java.util.Map;
+import java.util.Optional;
+import static tools.refinery.store.query.literal.Literals.not;
+import static tools.refinery.store.query.term.int_.IntTerms.INT_SUM;
+import static tools.refinery.store.query.viatra.tests.QueryAssertions.assertNullableResults;
+import static tools.refinery.store.query.viatra.tests.QueryAssertions.assertResults;
+class DiagonalQueryTest {
+        private static final Symbol<Boolean> person = Symbol.of("Person", 1);
+        private static final Symbol<Boolean> friend = Symbol.of("friend", 2);
+        private static final Symbol<Boolean> symbol = Symbol.of("symbol", 4);
+        private static final Symbol<Integer> intSymbol = Symbol.of("intSymbol", 4, Integer.class);
+        private static final AnySymbolView personView = new KeyOnlyView<>(person);
+        private static final AnySymbolView friendView = new KeyOnlyView<>(friend);
+        private static final AnySymbolView symbolView = new KeyOnlyView<>(symbol);
+        private static final FunctionView<Integer> intSymbolView = new FunctionView<>(intSymbol);
+        @QueryEngineTest
+        void inputKeyNegationTest(QueryEvaluationHint hint) {
+                var query = Query.of("Diagonal", (builder, p1) -> builder.clause(p2 -> List.of(
+                                personView.call(p1),
+                                not(symbolView.call(p1, p1, p2, p2))
+                )));
+                var store = ModelStore.builder()
+                                .symbols(person, symbol)
+                                .with(ViatraModelQueryAdapter.builder()
+                                                .defaultHint(hint)
+                                                .queries(query))
+                                .build();
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var symbolInterpretation = model.getInterpretation(symbol);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var queryResultSet = queryEngine.getResultSet(query);
+                personInterpretation.put(Tuple.of(0), true);
+                personInterpretation.put(Tuple.of(1), true);
+                personInterpretation.put(Tuple.of(2), true);
+                symbolInterpretation.put(Tuple.of(0, 0, 1, 1), true);
+                symbolInterpretation.put(Tuple.of(0, 0, 1, 2), true);
+                symbolInterpretation.put(Tuple.of(1, 1, 0, 1), true);
+                symbolInterpretation.put(Tuple.of(1, 2, 1, 1), true);
+                queryEngine.flushChanges();
+                assertResults(Map.of(
+                                Tuple.of(0), false,
+                                Tuple.of(1), true,
+                                Tuple.of(2), true,
+                                Tuple.of(3), false
+                ), queryResultSet);
+        }
+        @QueryEngineTest
+        void subQueryNegationTest(QueryEvaluationHint hint) {
+                var subQuery = Query.of("SubQuery", (builder, p1, p2, p3, p4) -> builder
+                                .clause(
+                                                personView.call(p1),
+                                                symbolView.call(p1, p2, p3, p4)
+                                )
+                                .clause(
+                                                personView.call(p2),
+                                                symbolView.call(p1, p2, p3, p4)
+                                ));
+                var query = Query.of("Diagonal", (builder, p1) -> builder.clause(p2 -> List.of(
+                                personView.call(p1),
+                                not(subQuery.call(p1, p1, p2, p2))
+                )));
+                var store = ModelStore.builder()
+                                .symbols(person, symbol)
+                                .with(ViatraModelQueryAdapter.builder()
+                                                .defaultHint(hint)
+                                                .queries(query))
+                                .build();
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var symbolInterpretation = model.getInterpretation(symbol);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var queryResultSet = queryEngine.getResultSet(query);
+                personInterpretation.put(Tuple.of(0), true);
+                personInterpretation.put(Tuple.of(1), true);
+                personInterpretation.put(Tuple.of(2), true);
+                symbolInterpretation.put(Tuple.of(0, 0, 1, 1), true);
+                symbolInterpretation.put(Tuple.of(0, 0, 1, 2), true);
+                symbolInterpretation.put(Tuple.of(1, 1, 0, 1), true);
+                symbolInterpretation.put(Tuple.of(1, 2, 1, 1), true);
+                queryEngine.flushChanges();
+                assertResults(Map.of(
+                                Tuple.of(0), false,
+                                Tuple.of(1), true,
+                                Tuple.of(2), true,
+                                Tuple.of(3), false
+                ), queryResultSet);
+        }
+        @QueryEngineTest
+        void inputKeyCountTest(QueryEvaluationHint hint) {
+                var query = Query.of("Diagonal", Integer.class, (builder, p1, output) -> builder.clause(p2 -> List.of(
+                                personView.call(p1),
+                                output.assign(symbolView.count(p1, p1, p2, p2))
+                )));
+                var store = ModelStore.builder()
+                                .symbols(person, symbol)
+                                .with(ViatraModelQueryAdapter.builder()
+                                                .defaultHint(hint)
+                                                .queries(query))
+                                .build();
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var symbolInterpretation = model.getInterpretation(symbol);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var queryResultSet = queryEngine.getResultSet(query);
+                personInterpretation.put(Tuple.of(0), true);
+                personInterpretation.put(Tuple.of(1), true);
+                personInterpretation.put(Tuple.of(2), true);
+                symbolInterpretation.put(Tuple.of(0, 0, 1, 1), true);
+                symbolInterpretation.put(Tuple.of(0, 0, 2, 2), true);
+                symbolInterpretation.put(Tuple.of(0, 0, 1, 2), true);
+                symbolInterpretation.put(Tuple.of(1, 1, 0, 1), true);
+                symbolInterpretation.put(Tuple.of(1, 2, 1, 1), true);
+                queryEngine.flushChanges();
+                assertNullableResults(Map.of(
+                                Tuple.of(0), Optional.of(2),
+                                Tuple.of(1), Optional.of(0),
+                                Tuple.of(2), Optional.of(0),
+                                Tuple.of(3), Optional.empty()
+                ), queryResultSet);
+        }
+        @QueryEngineTest
+        void subQueryCountTest(QueryEvaluationHint hint) {
+                var subQuery = Query.of("SubQuery", (builder, p1, p2, p3, p4) -> builder.clause(
+                                                personView.call(p1),
+                                                symbolView.call(p1, p2, p3, p4)
+                                )
+                                .clause(
+                                                personView.call(p2),
+                                                symbolView.call(p1, p2, p3, p4)
+                                ));
+                var query = Query.of("Diagonal", Integer.class, (builder, p1, output) -> builder.clause(p2 -> List.of(
+                                personView.call(p1),
+                                output.assign(subQuery.count(p1, p1, p2, p2))
+                )));
+                var store = ModelStore.builder()
+                                .symbols(person, symbol)
+                                .with(ViatraModelQueryAdapter.builder()
+                                                .defaultHint(hint)
+                                                .queries(query))
+                                .build();
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var symbolInterpretation = model.getInterpretation(symbol);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var queryResultSet = queryEngine.getResultSet(query);
+                personInterpretation.put(Tuple.of(0), true);
+                personInterpretation.put(Tuple.of(1), true);
+                personInterpretation.put(Tuple.of(2), true);
+                symbolInterpretation.put(Tuple.of(0, 0, 1, 1), true);
+                symbolInterpretation.put(Tuple.of(0, 0, 2, 2), true);
+                symbolInterpretation.put(Tuple.of(0, 0, 1, 2), true);
+                symbolInterpretation.put(Tuple.of(1, 1, 0, 1), true);
+                symbolInterpretation.put(Tuple.of(1, 2, 1, 1), true);
+                queryEngine.flushChanges();
+                assertNullableResults(Map.of(
+                                Tuple.of(0), Optional.of(2),
+                                Tuple.of(1), Optional.of(0),
+                                Tuple.of(2), Optional.of(0),
+                                Tuple.of(3), Optional.empty()
+                ), queryResultSet);
+        }
+        @QueryEngineTest
+        void inputKeyAggregationTest(QueryEvaluationHint hint) {
+                var query = Query.of("Diagonal", Integer.class, (builder, p1, output) -> builder
+                                .clause((p2) -> List.of(
+                                                personView.call(p1),
+                                                output.assign(intSymbolView.aggregate(INT_SUM, p1, p1, p2, p2))
+                                )));
+                var store = ModelStore.builder()
+                                .symbols(person, intSymbol)
+                                .with(ViatraModelQueryAdapter.builder()
+                                                .defaultHint(hint)
+                                                .queries(query))
+                                .build();
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var intSymbolInterpretation = model.getInterpretation(intSymbol);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var queryResultSet = queryEngine.getResultSet(query);
+                personInterpretation.put(Tuple.of(0), true);
+                personInterpretation.put(Tuple.of(1), true);
+                personInterpretation.put(Tuple.of(2), true);
+                intSymbolInterpretation.put(Tuple.of(0, 0, 1, 1), 1);
+                intSymbolInterpretation.put(Tuple.of(0, 0, 2, 2), 2);
+                intSymbolInterpretation.put(Tuple.of(0, 0, 1, 2), 10);
+                intSymbolInterpretation.put(Tuple.of(1, 1, 0, 1), 11);
+                intSymbolInterpretation.put(Tuple.of(1, 2, 1, 1), 12);
+                queryEngine.flushChanges();
+                assertNullableResults(Map.of(
+                                Tuple.of(0), Optional.of(3),
+                                Tuple.of(1), Optional.of(0),
+                                Tuple.of(2), Optional.of(0),
+                                Tuple.of(3), Optional.empty()
+                ), queryResultSet);
+        }
+        @QueryEngineTest
+        void subQueryAggregationTest(QueryEvaluationHint hint) {
+                var subQuery = Dnf.of("SubQuery", builder -> {
+                        var p1 = builder.parameter("p1");
+                        var p2 = builder.parameter("p2");
+                        var p3 = builder.parameter("p3");
+                        var p4 = builder.parameter("p4");
+                        var x = builder.parameter("x", Integer.class);
+                        var y = builder.parameter("y", Integer.class);
+                        builder.clause(
+                                        personView.call(p1),
+                                        intSymbolView.call(p1, p2, p3, p4, x),
+                                        y.assign(x)
+                        );
+                        builder.clause(
+                                        personView.call(p2),
+                                        intSymbolView.call(p1, p2, p3, p4, x),
+                                        y.assign(x)
+                        );
+                });
+                var query = Query.of("Diagonal", Integer.class, (builder, p1, output) -> builder
+                                .clause(Integer.class, Integer.class, (p2, y, z) -> List.of(
+                                                personView.call(p1),
+                                                output.assign(subQuery.aggregateBy(y, INT_SUM, p1, p1, p2, p2, y, z))
+                                )));
+                var store = ModelStore.builder()
+                                .symbols(person, intSymbol)
+                                .with(ViatraModelQueryAdapter.builder()
+                                                .defaultHint(hint)
+                                                .queries(query))
+                                .build();
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var intSymbolInterpretation = model.getInterpretation(intSymbol);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var queryResultSet = queryEngine.getResultSet(query);
+                personInterpretation.put(Tuple.of(0), true);
+                personInterpretation.put(Tuple.of(1), true);
+                personInterpretation.put(Tuple.of(2), true);
+                intSymbolInterpretation.put(Tuple.of(0, 0, 1, 1), 1);
+                intSymbolInterpretation.put(Tuple.of(0, 0, 2, 2), 2);
+                intSymbolInterpretation.put(Tuple.of(0, 0, 1, 2), 10);
+                intSymbolInterpretation.put(Tuple.of(1, 1, 0, 1), 11);
+                intSymbolInterpretation.put(Tuple.of(1, 2, 1, 1), 12);
+                queryEngine.flushChanges();
+                assertNullableResults(Map.of(
+                                Tuple.of(0), Optional.of(3),
+                                Tuple.of(1), Optional.of(0),
+                                Tuple.of(2), Optional.of(0),
+                                Tuple.of(3), Optional.empty()
+                ), queryResultSet);
+        }
+        @QueryEngineTest
+        void inputKeyTransitiveTest(QueryEvaluationHint hint) {
+                var query = Query.of("Diagonal", (builder, p1) -> builder.clause(
+                                personView.call(p1),
+                                friendView.callTransitive(p1, p1)
+                ));
+                var store = ModelStore.builder()
+                                .symbols(person, friend)
+                                .with(ViatraModelQueryAdapter.builder()
+                                                .defaultHint(hint)
+                                                .queries(query))
+                                .build();
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var friendInterpretation = model.getInterpretation(friend);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var queryResultSet = queryEngine.getResultSet(query);
+                personInterpretation.put(Tuple.of(0), true);
+                personInterpretation.put(Tuple.of(1), true);
+                personInterpretation.put(Tuple.of(2), true);
+                friendInterpretation.put(Tuple.of(0, 0), true);
+                friendInterpretation.put(Tuple.of(0, 1), true);
+                friendInterpretation.put(Tuple.of(1, 2), true);
+                queryEngine.flushChanges();
+                assertResults(Map.of(
+                                Tuple.of(0), true,
+                                Tuple.of(1), false,
+                                Tuple.of(2), false,
+                                Tuple.of(3), false
+                ), queryResultSet);
+        }
+        @QueryEngineTest
+        void subQueryTransitiveTest(QueryEvaluationHint hint) {
+                var subQuery = Query.of("SubQuery", (builder, p1, p2) -> builder
+                                .clause(
+                                                personView.call(p1),
+                                                friendView.call(p1, p2)
+                                )
+                                .clause(
+                                                personView.call(p2),
+                                                friendView.call(p1, p2)
+                                ));
+                var query = Query.of("Diagonal", (builder, p1) -> builder.clause(
+                                personView.call(p1),
+                                subQuery.callTransitive(p1, p1)
+                ));
+                var store = ModelStore.builder()
+                                .symbols(person, friend)
+                                .with(ViatraModelQueryAdapter.builder()
+                                                .defaultHint(hint)
+                                                .queries(query))
+                                .build();
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var friendInterpretation = model.getInterpretation(friend);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var queryResultSet = queryEngine.getResultSet(query);
+                personInterpretation.put(Tuple.of(0), true);
+                personInterpretation.put(Tuple.of(1), true);
+                personInterpretation.put(Tuple.of(2), true);
+                friendInterpretation.put(Tuple.of(0, 0), true);
+                friendInterpretation.put(Tuple.of(0, 1), true);
+                friendInterpretation.put(Tuple.of(1, 2), true);
+                queryEngine.flushChanges();
+                assertResults(Map.of(
+                                Tuple.of(0), true,
+                                Tuple.of(1), false,
+                                Tuple.of(2), false,
+                                Tuple.of(3), false
+                ), queryResultSet);
+        }
+}
diff --git a/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/FunctionalQueryTest.java b/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/FunctionalQueryTest.java
new file mode 100644
index 00000000..258127e7
--- /dev/null
+++ b/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/FunctionalQueryTest.java
@@ -0,0 +1,483 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.viatra;
+import org.eclipse.viatra.query.runtime.matchers.backend.QueryEvaluationHint;
+import tools.refinery.store.map.Cursor;
+import tools.refinery.store.model.ModelStore;
+import tools.refinery.store.query.ModelQueryAdapter;
+import tools.refinery.store.query.dnf.Query;
+import tools.refinery.store.query.term.Variable;
+import tools.refinery.store.query.viatra.tests.QueryEngineTest;
+import tools.refinery.store.query.view.AnySymbolView;
+import tools.refinery.store.query.view.FilteredView;
+import tools.refinery.store.query.view.FunctionView;
+import tools.refinery.store.query.view.KeyOnlyView;
+import tools.refinery.store.representation.Symbol;
+import tools.refinery.store.representation.TruthValue;
+import tools.refinery.store.tuple.Tuple;
+import java.util.List;
+import java.util.Map;
+import java.util.Optional;
+import static org.hamcrest.MatcherAssert.assertThat;
+import static org.hamcrest.Matchers.is;
+import static org.hamcrest.Matchers.nullValue;
+import static org.junit.jupiter.api.Assertions.assertAll;
+import static org.junit.jupiter.api.Assertions.assertThrows;
+import static tools.refinery.store.query.literal.Literals.assume;
+import static tools.refinery.store.query.term.int_.IntTerms.*;
+import static tools.refinery.store.query.viatra.tests.QueryAssertions.assertNullableResults;
+import static tools.refinery.store.query.viatra.tests.QueryAssertions.assertResults;
+class FunctionalQueryTest {
+        private static final Symbol<Boolean> person = Symbol.of("Person", 1);
+        private static final Symbol<Integer> age = Symbol.of("age", 1, Integer.class);
+        private static final Symbol<TruthValue> friend = Symbol.of("friend", 2, TruthValue.class, TruthValue.FALSE);
+        private static final AnySymbolView personView = new KeyOnlyView<>(person);
+        private static final FunctionView<Integer> ageView = new FunctionView<>(age);
+        private static final AnySymbolView friendMustView = new FilteredView<>(friend, "must", TruthValue::must);
+        @QueryEngineTest
+        void inputKeyTest(QueryEvaluationHint hint) {
+                var query = Query.of("InputKey", Integer.class, (builder, p1, output) -> builder.clause(
+                                personView.call(p1),
+                                ageView.call(p1, output)
+                ));
+                var store = ModelStore.builder()
+                                .symbols(person, age)
+                                .with(ViatraModelQueryAdapter.builder()
+                                                .defaultHint(hint)
+                                                .queries(query))
+                                .build();
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var ageInterpretation = model.getInterpretation(age);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var queryResultSet = queryEngine.getResultSet(query);
+                personInterpretation.put(Tuple.of(0), true);
+                personInterpretation.put(Tuple.of(1), true);
+                ageInterpretation.put(Tuple.of(0), 12);
+                ageInterpretation.put(Tuple.of(1), 24);
+                ageInterpretation.put(Tuple.of(2), 36);
+                queryEngine.flushChanges();
+                assertNullableResults(Map.of(
+                                Tuple.of(0), Optional.of(12),
+                                Tuple.of(1), Optional.of(24),
+                                Tuple.of(2), Optional.empty()
+                ), queryResultSet);
+        }
+        @QueryEngineTest
+        void predicateTest(QueryEvaluationHint hint) {
+                var subQuery = Query.of("SubQuery", Integer.class, (builder, p1, x) -> builder.clause(
+                                personView.call(p1),
+                                ageView.call(p1, x)
+                ));
+                var query = Query.of("Predicate", Integer.class, (builder, p1, output) -> builder.clause(
+                                personView.call(p1),
+                                output.assign(subQuery.call(p1))
+                ));
+                var store = ModelStore.builder()
+                                .symbols(person, age)
+                                .with(ViatraModelQueryAdapter.builder()
+                                                .defaultHint(hint)
+                                                .queries(query))
+                                .build();
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var ageInterpretation = model.getInterpretation(age);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var queryResultSet = queryEngine.getResultSet(query);
+                personInterpretation.put(Tuple.of(0), true);
+                personInterpretation.put(Tuple.of(1), true);
+                ageInterpretation.put(Tuple.of(0), 12);
+                ageInterpretation.put(Tuple.of(1), 24);
+                ageInterpretation.put(Tuple.of(2), 36);
+                queryEngine.flushChanges();
+                assertNullableResults(Map.of(
+                                Tuple.of(0), Optional.of(12),
+                                Tuple.of(1), Optional.of(24),
+                                Tuple.of(2), Optional.empty()
+                ), queryResultSet);
+        }
+        @QueryEngineTest
+        void computationTest(QueryEvaluationHint hint) {
+                var query = Query.of("Computation", Integer.class, (builder, p1, output) -> builder.clause(() -> {
+                        var x = Variable.of("x", Integer.class);
+                        return List.of(
+                                        personView.call(p1),
+                                        ageView.call(p1, x),
+                                        output.assign(mul(x, constant(7)))
+                        );
+                }));
+                var store = ModelStore.builder()
+                                .symbols(person, age)
+                                .with(ViatraModelQueryAdapter.builder()
+                                                .defaultHint(hint)
+                                                .queries(query))
+                                .build();
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var ageInterpretation = model.getInterpretation(age);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var queryResultSet = queryEngine.getResultSet(query);
+                personInterpretation.put(Tuple.of(0), true);
+                personInterpretation.put(Tuple.of(1), true);
+                ageInterpretation.put(Tuple.of(0), 12);
+                ageInterpretation.put(Tuple.of(1), 24);
+                queryEngine.flushChanges();
+                assertNullableResults(Map.of(
+                                Tuple.of(0), Optional.of(84),
+                                Tuple.of(1), Optional.of(168),
+                                Tuple.of(2), Optional.empty()
+                ), queryResultSet);
+        }
+        @QueryEngineTest
+        void inputKeyCountTest(QueryEvaluationHint hint) {
+                var query = Query.of("Count", Integer.class, (builder, p1, output) -> builder.clause(
+                                personView.call(p1),
+                                output.assign(friendMustView.count(p1, Variable.of()))
+                ));
+                var store = ModelStore.builder()
+                                .symbols(person, friend)
+                                .with(ViatraModelQueryAdapter.builder()
+                                                .defaultHint(hint)
+                                                .queries(query))
+                                .build();
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var friendInterpretation = model.getInterpretation(friend);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var queryResultSet = queryEngine.getResultSet(query);
+                personInterpretation.put(Tuple.of(0), true);
+                personInterpretation.put(Tuple.of(1), true);
+                personInterpretation.put(Tuple.of(2), true);
+                friendInterpretation.put(Tuple.of(0, 1), TruthValue.TRUE);
+                friendInterpretation.put(Tuple.of(1, 0), TruthValue.TRUE);
+                friendInterpretation.put(Tuple.of(1, 2), TruthValue.TRUE);
+                queryEngine.flushChanges();
+                assertNullableResults(Map.of(
+                                Tuple.of(0), Optional.of(1),
+                                Tuple.of(1), Optional.of(2),
+                                Tuple.of(2), Optional.of(0),
+                                Tuple.of(3), Optional.empty()
+                ), queryResultSet);
+        }
+        @QueryEngineTest
+        void predicateCountTest(QueryEvaluationHint hint) {
+                var subQuery = Query.of("SubQuery", (builder, p1, p2) -> builder.clause(
+                                        personView.call(p1),
+                                        personView.call(p2),
+                                        friendMustView.call(p1, p2)
+                ));
+                var query = Query.of("Count", Integer.class, (builder, p1, output) -> builder.clause(
+                                personView.call(p1),
+                                output.assign(subQuery.count(p1, Variable.of()))
+                ));
+                var store = ModelStore.builder()
+                                .symbols(person, friend)
+                                .with(ViatraModelQueryAdapter.builder()
+                                                .defaultHint(hint)
+                                                .queries(query))
+                                .build();
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var friendInterpretation = model.getInterpretation(friend);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var queryResultSet = queryEngine.getResultSet(query);
+                personInterpretation.put(Tuple.of(0), true);
+                personInterpretation.put(Tuple.of(1), true);
+                personInterpretation.put(Tuple.of(2), true);
+                friendInterpretation.put(Tuple.of(0, 1), TruthValue.TRUE);
+                friendInterpretation.put(Tuple.of(1, 0), TruthValue.TRUE);
+                friendInterpretation.put(Tuple.of(1, 2), TruthValue.TRUE);
+                queryEngine.flushChanges();
+                assertNullableResults(Map.of(
+                                Tuple.of(0), Optional.of(1),
+                                Tuple.of(1), Optional.of(2),
+                                Tuple.of(2), Optional.of(0),
+                                Tuple.of(3), Optional.empty()
+                ), queryResultSet);
+        }
+        @QueryEngineTest
+        void inputKeyAggregationTest(QueryEvaluationHint hint) {
+                var query = Query.of("Aggregate", Integer.class, (builder, output) -> builder.clause(
+                                output.assign(ageView.aggregate(INT_SUM, Variable.of()))
+                ));
+                var store = ModelStore.builder()
+                                .symbols(age)
+                                .with(ViatraModelQueryAdapter.builder()
+                                                .defaultHint(hint)
+                                                .queries(query))
+                                .build();
+                var model = store.createEmptyModel();
+                var ageInterpretation = model.getInterpretation(age);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var queryResultSet = queryEngine.getResultSet(query);
+                ageInterpretation.put(Tuple.of(0), 12);
+                ageInterpretation.put(Tuple.of(1), 24);
+                queryEngine.flushChanges();
+                assertResults(Map.of(Tuple.of(), 36), queryResultSet);
+        }
+        @QueryEngineTest
+        void predicateAggregationTest(QueryEvaluationHint hint) {
+                var subQuery = Query.of("SubQuery", Integer.class, (builder, p1, x) -> builder.clause(
+                                personView.call(p1),
+                                ageView.call(p1, x)
+                ));
+                var query = Query.of("Aggregate", Integer.class, (builder, output) -> builder.clause(
+                                output.assign(subQuery.aggregate(INT_SUM, Variable.of()))
+                ));
+                var store = ModelStore.builder()
+                                .symbols(person, age)
+                                .with(ViatraModelQueryAdapter.builder()
+                                                .defaultHint(hint)
+                                                .queries(query))
+                                .build();
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var ageInterpretation = model.getInterpretation(age);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var queryResultSet = queryEngine.getResultSet(query);
+                personInterpretation.put(Tuple.of(0), true);
+                personInterpretation.put(Tuple.of(1), true);
+                ageInterpretation.put(Tuple.of(0), 12);
+                ageInterpretation.put(Tuple.of(1), 24);
+                queryEngine.flushChanges();
+                assertResults(Map.of(Tuple.of(), 36), queryResultSet);
+        }
+        @QueryEngineTest
+        void extremeValueTest(QueryEvaluationHint hint) {
+                var subQuery = Query.of("SubQuery", Integer.class, (builder, p1, x) -> builder.clause(
+                                personView.call(p1),
+                                x.assign(friendMustView.count(p1, Variable.of()))
+                ));
+                var minQuery = Query.of("Min", Integer.class, (builder, output) -> builder.clause(
+                                output.assign(subQuery.aggregate(INT_MIN, Variable.of()))
+                ));
+                var maxQuery = Query.of("Max", Integer.class, (builder, output) -> builder.clause(
+                                output.assign(subQuery.aggregate(INT_MAX, Variable.of()))
+                ));
+                var store = ModelStore.builder()
+                                .symbols(person, friend)
+                                .with(ViatraModelQueryAdapter.builder()
+                                                .defaultHint(hint)
+                                                .queries(minQuery, maxQuery))
+                                .build();
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var friendInterpretation = model.getInterpretation(friend);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var minResultSet = queryEngine.getResultSet(minQuery);
+                var maxResultSet = queryEngine.getResultSet(maxQuery);
+                assertResults(Map.of(Tuple.of(), Integer.MAX_VALUE), minResultSet);
+                assertResults(Map.of(Tuple.of(), Integer.MIN_VALUE), maxResultSet);
+                personInterpretation.put(Tuple.of(0), true);
+                personInterpretation.put(Tuple.of(1), true);
+                personInterpretation.put(Tuple.of(2), true);
+                friendInterpretation.put(Tuple.of(0, 1), TruthValue.TRUE);
+                friendInterpretation.put(Tuple.of(1, 0), TruthValue.TRUE);
+                friendInterpretation.put(Tuple.of(1, 2), TruthValue.TRUE);
+                queryEngine.flushChanges();
+                assertResults(Map.of(Tuple.of(), 0), minResultSet);
+                assertResults(Map.of(Tuple.of(), 2), maxResultSet);
+                friendInterpretation.put(Tuple.of(2, 0), TruthValue.TRUE);
+                friendInterpretation.put(Tuple.of(2, 1), TruthValue.TRUE);
+                queryEngine.flushChanges();
+                assertResults(Map.of(Tuple.of(), 1), minResultSet);
+                assertResults(Map.of(Tuple.of(), 2), maxResultSet);
+                friendInterpretation.put(Tuple.of(0, 1), TruthValue.FALSE);
+                friendInterpretation.put(Tuple.of(1, 0), TruthValue.FALSE);
+                friendInterpretation.put(Tuple.of(2, 0), TruthValue.FALSE);
+                queryEngine.flushChanges();
+                assertResults(Map.of(Tuple.of(), 0), minResultSet);
+                assertResults(Map.of(Tuple.of(), 1), maxResultSet);
+        }
+        @QueryEngineTest
+        void invalidComputationTest(QueryEvaluationHint hint) {
+                var query = Query.of("InvalidComputation", Integer.class,
+                                (builder, p1, output) -> builder.clause(Integer.class, (x) -> List.of(
+                                                personView.call(p1),
+                                                ageView.call(p1, x),
+                                                output.assign(div(constant(120), x))
+                                )));
+                var store = ModelStore.builder()
+                                .symbols(person, age)
+                                .with(ViatraModelQueryAdapter.builder()
+                                                .defaultHint(hint)
+                                                .queries(query))
+                                .build();
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var ageInterpretation = model.getInterpretation(age);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var queryResultSet = queryEngine.getResultSet(query);
+                personInterpretation.put(Tuple.of(0), true);
+                personInterpretation.put(Tuple.of(1), true);
+                ageInterpretation.put(Tuple.of(0), 0);
+                ageInterpretation.put(Tuple.of(1), 30);
+                queryEngine.flushChanges();
+                assertNullableResults(Map.of(
+                                Tuple.of(0), Optional.empty(),
+                                Tuple.of(1), Optional.of(4),
+                                Tuple.of(2), Optional.empty()
+                ), queryResultSet);
+        }
+        @QueryEngineTest
+        void invalidAssumeTest(QueryEvaluationHint hint) {
+                var query = Query.of("InvalidAssume", (builder, p1) -> builder.clause(Integer.class, (x) -> List.of(
+                                personView.call(p1),
+                                ageView.call(p1, x),
+                                assume(lessEq(div(constant(120), x), constant(5)))
+                )));
+                var store = ModelStore.builder()
+                                .symbols(person, age)
+                                .with(ViatraModelQueryAdapter.builder()
+                                                .defaultHint(hint)
+                                                .queries(query))
+                                .build();
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var ageInterpretation = model.getInterpretation(age);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var queryResultSet = queryEngine.getResultSet(query);
+                personInterpretation.put(Tuple.of(0), true);
+                personInterpretation.put(Tuple.of(1), true);
+                personInterpretation.put(Tuple.of(2), true);
+                ageInterpretation.put(Tuple.of(0), 0);
+                ageInterpretation.put(Tuple.of(1), 30);
+                ageInterpretation.put(Tuple.of(2), 20);
+                queryEngine.flushChanges();
+                assertResults(Map.of(
+                                Tuple.of(0), false,
+                                Tuple.of(1), true,
+                                Tuple.of(2), false,
+                                Tuple.of(3), false
+                ), queryResultSet);
+        }
+        @QueryEngineTest
+        void notFunctionalTest(QueryEvaluationHint hint) {
+                var query = Query.of("NotFunctional", Integer.class, (builder, p1, output) -> builder.clause((p2) -> List.of(
+                                personView.call(p1),
+                                friendMustView.call(p1, p2),
+                                ageView.call(p2, output)
+                )));
+                var store = ModelStore.builder()
+                                .symbols(person, age, friend)
+                                .with(ViatraModelQueryAdapter.builder()
+                                                .defaultHint(hint)
+                                                .queries(query))
+                                .build();
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var ageInterpretation = model.getInterpretation(age);
+                var friendInterpretation = model.getInterpretation(friend);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var queryResultSet = queryEngine.getResultSet(query);
+                personInterpretation.put(Tuple.of(0), true);
+                personInterpretation.put(Tuple.of(1), true);
+                personInterpretation.put(Tuple.of(2), true);
+                ageInterpretation.put(Tuple.of(0), 24);
+                ageInterpretation.put(Tuple.of(1), 30);
+                ageInterpretation.put(Tuple.of(2), 36);
+                friendInterpretation.put(Tuple.of(0, 1), TruthValue.TRUE);
+                friendInterpretation.put(Tuple.of(1, 0), TruthValue.TRUE);
+                friendInterpretation.put(Tuple.of(1, 2), TruthValue.TRUE);
+                queryEngine.flushChanges();
+                var invalidTuple = Tuple.of(1);
+                var cursor = queryResultSet.getAll();
+                assertAll(
+                                () -> assertThat("value for key 0", queryResultSet.get(Tuple.of(0)), is(30)),
+                                () -> assertThrows(IllegalStateException.class, () -> queryResultSet.get(invalidTuple),
+                                                "multiple values for key 1"),
+                                () -> assertThat("value for key 2", queryResultSet.get(Tuple.of(2)), is(nullValue())),
+                                () -> assertThat("value for key 3", queryResultSet.get(Tuple.of(3)), is(nullValue()))
+                );
+                if (hint.getQueryBackendRequirementType() != QueryEvaluationHint.BackendRequirement.DEFAULT_SEARCH) {
+                        // Local search doesn't support throwing an error on multiple function return values.
+                        assertThat("results size", queryResultSet.size(), is(2));
+                        assertThrows(IllegalStateException.class, () -> enumerateValues(cursor), "move cursor");
+                }
+        }
+        private static void enumerateValues(Cursor<?, ?> cursor) {
+                //noinspection StatementWithEmptyBody
+                while (cursor.move()) {
+                        // Nothing do, just let the cursor move through the result set.
+                }
+        }
+}
diff --git a/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/OrderedResultSetTest.java b/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/OrderedResultSetTest.java
new file mode 100644
index 00000000..8ede6c80
--- /dev/null
+++ b/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/OrderedResultSetTest.java
@@ -0,0 +1,117 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.viatra;
+import org.junit.jupiter.api.Test;
+import tools.refinery.store.model.ModelStore;
+import tools.refinery.store.query.ModelQueryAdapter;
+import tools.refinery.store.query.dnf.Query;
+import tools.refinery.store.query.resultset.OrderedResultSet;
+import tools.refinery.store.query.term.Variable;
+import tools.refinery.store.query.view.AnySymbolView;
+import tools.refinery.store.query.view.KeyOnlyView;
+import tools.refinery.store.representation.Symbol;
+import tools.refinery.store.tuple.Tuple;
+import static org.hamcrest.MatcherAssert.assertThat;
+import static org.hamcrest.Matchers.is;
+class OrderedResultSetTest {
+        private static final Symbol<Boolean> friend = Symbol.of("friend", 2);
+        private static final AnySymbolView friendView = new KeyOnlyView<>(friend);
+        @Test
+        void relationalFlushTest() {
+                var query = Query.of("Relation", (builder, p1, p2) -> builder.clause(
+                                 friendView.call(p1, p2)
+                ));
+                var store = ModelStore.builder()
+                                .symbols(friend)
+                                .with(ViatraModelQueryAdapter.builder()
+                                                .queries(query))
+                                .build();
+                var model = store.createEmptyModel();
+                var friendInterpretation = model.getInterpretation(friend);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var resultSet = queryEngine.getResultSet(query);
+                friendInterpretation.put(Tuple.of(0, 1), true);
+                friendInterpretation.put(Tuple.of(1, 2), true);
+                friendInterpretation.put(Tuple.of(1, 1), true);
+                queryEngine.flushChanges();
+                try (var orderedResultSet = new OrderedResultSet<>(resultSet)) {
+                        assertThat(orderedResultSet.size(), is(3));
+                        assertThat(orderedResultSet.getKey(0), is(Tuple.of(0, 1)));
+                        assertThat(orderedResultSet.getKey(1), is(Tuple.of(1, 1)));
+                        assertThat(orderedResultSet.getKey(2), is(Tuple.of(1, 2)));
+                        friendInterpretation.put(Tuple.of(1, 2), false);
+                        friendInterpretation.put(Tuple.of(0, 2), true);
+                        queryEngine.flushChanges();
+                        assertThat(orderedResultSet.size(), is(3));
+                        assertThat(orderedResultSet.getKey(0), is(Tuple.of(0, 1)));
+                        assertThat(orderedResultSet.getKey(1), is(Tuple.of(0, 2)));
+                        assertThat(orderedResultSet.getKey(2), is(Tuple.of(1, 1)));
+                }
+        }
+        @Test
+        void functionalFlushTest() {
+                var query = Query.of("Function", Integer.class, (builder, p1, output) -> builder.clause(
+                                friendView.call(p1, Variable.of()),
+                                output.assign(friendView.count(p1, Variable.of()))
+                ));
+                var store = ModelStore.builder()
+                                .symbols(friend)
+                                .with(ViatraModelQueryAdapter.builder()
+                                                .queries(query))
+                                .build();
+                var model = store.createEmptyModel();
+                var friendInterpretation = model.getInterpretation(friend);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var resultSet = queryEngine.getResultSet(query);
+                friendInterpretation.put(Tuple.of(0, 1), true);
+                friendInterpretation.put(Tuple.of(1, 2), true);
+                friendInterpretation.put(Tuple.of(1, 1), true);
+                queryEngine.flushChanges();
+                try (var orderedResultSet = new OrderedResultSet<>(resultSet)) {
+                        assertThat(orderedResultSet.size(), is(2));
+                        assertThat(orderedResultSet.getKey(0), is(Tuple.of(0)));
+                        assertThat(orderedResultSet.getKey(1), is(Tuple.of(1)));
+                        friendInterpretation.put(Tuple.of(0, 1), false);
+                        friendInterpretation.put(Tuple.of(2, 1), true);
+                        queryEngine.flushChanges();
+                        assertThat(orderedResultSet.size(), is(2));
+                        assertThat(orderedResultSet.getKey(0), is(Tuple.of(1)));
+                        assertThat(orderedResultSet.getKey(1), is(Tuple.of(2)));
+                        friendInterpretation.put(Tuple.of(1, 1), false);
+                        queryEngine.flushChanges();
+                        assertThat(orderedResultSet.size(), is(2));
+                        assertThat(orderedResultSet.getKey(0), is(Tuple.of(1)));
+                        assertThat(orderedResultSet.getKey(1), is(Tuple.of(2)));
+                        friendInterpretation.put(Tuple.of(1, 2), false);
+                        friendInterpretation.put(Tuple.of(1, 0), true);
+                        queryEngine.flushChanges();
+                        assertThat(orderedResultSet.size(), is(2));
+                        assertThat(orderedResultSet.getKey(0), is(Tuple.of(1)));
+                        assertThat(orderedResultSet.getKey(1), is(Tuple.of(2)));
+                }
+        }
+}
diff --git a/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/QueryTest.java b/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/QueryTest.java
index 6a37b54a..25bcb0dc 100644
--- a/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/QueryTest.java
+++ b/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/QueryTest.java
@@ -1,47 +1,57 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
 package tools.refinery.store.query.viatra;
+import org.eclipse.viatra.query.runtime.matchers.backend.QueryEvaluationHint;
 import org.junit.jupiter.api.Test;
 import tools.refinery.store.model.ModelStore;
-import tools.refinery.store.query.DNF;
+import tools.refinery.store.query.ModelQueryAdapter;
-import tools.refinery.store.query.ModelQuery;
+import tools.refinery.store.query.dnf.Query;
-import tools.refinery.store.query.Variable;
+import tools.refinery.store.query.term.Variable;
-import tools.refinery.store.query.atom.*;
+import tools.refinery.store.query.viatra.tests.QueryEngineTest;
-import tools.refinery.store.query.view.FilteredRelationView;
+import tools.refinery.store.query.view.AnySymbolView;
-import tools.refinery.store.query.view.KeyOnlyRelationView;
+import tools.refinery.store.query.view.FilteredView;
+import tools.refinery.store.query.view.FunctionView;
+import tools.refinery.store.query.view.KeyOnlyView;
 import tools.refinery.store.representation.Symbol;
 import tools.refinery.store.representation.TruthValue;
 import tools.refinery.store.tuple.Tuple;
-import tools.refinery.store.tuple.TupleLike;
-import java.util.HashSet;
+import java.util.List;
-import java.util.Set;
+import java.util.Map;
-import java.util.stream.Stream;
-import static org.junit.jupiter.api.Assertions.assertEquals;
+import static tools.refinery.store.query.literal.Literals.assume;
+import static tools.refinery.store.query.literal.Literals.not;
+import static tools.refinery.store.query.term.int_.IntTerms.constant;
+import static tools.refinery.store.query.term.int_.IntTerms.greaterEq;
+import static tools.refinery.store.query.viatra.tests.QueryAssertions.assertResults;
 class QueryTest {
-        @Test
+        private static final Symbol<Boolean> person = Symbol.of("Person", 1);
-        void typeConstraintTest() {
+        private static final Symbol<TruthValue> friend = Symbol.of("friend", 2, TruthValue.class, TruthValue.FALSE);
-                var person = new Symbol<>("Person", 1, Boolean.class, false);
+        private static final AnySymbolView personView = new KeyOnlyView<>(person);
-                var asset = new Symbol<>("Asset", 1, Boolean.class, false);
+        private static final AnySymbolView friendMustView = new FilteredView<>(friend, "must", TruthValue::must);
-                var personView = new KeyOnlyRelationView<>(person);
+        @QueryEngineTest
-                var p1 = new Variable("p1");
+        void typeConstraintTest(QueryEvaluationHint hint) {
-                var predicate = DNF.builder("TypeConstraint")
+                var asset = Symbol.of("Asset", 1);
-                                .parameters(p1)
-                                .clause(new RelationViewAtom(personView, p1))
+                var predicate = Query.of("TypeConstraint", (builder, p1) -> builder.clause(personView.call(p1)));
-                                .build();
                var store = ModelStore.builder()
                                .symbols(person, asset)
-                                .with(ViatraModelQuery.ADAPTER)
+                                .with(ViatraModelQueryAdapter.builder()
-                                .queries(predicate)
+                                                .defaultHint(hint)
+                                                .queries(predicate))
                                .build();
                var model = store.createEmptyModel();
                var personInterpretation = model.getInterpretation(person);
                var assetInterpretation = model.getInterpretation(asset);
-                var queryEngine = model.getAdapter(ModelQuery.ADAPTER);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
                var predicateResultSet = queryEngine.getResultSet(predicate);
                personInterpretation.put(Tuple.of(0), true);
@@ -51,42 +61,34 @@ class QueryTest {
                assetInterpretation.put(Tuple.of(2), true);
                queryEngine.flushChanges();
-                assertEquals(2, predicateResultSet.countResults());
+                assertResults(Map.of(
-                compareMatchSets(predicateResultSet.allResults(), Set.of(Tuple.of(0), Tuple.of(1)));
+                                Tuple.of(0), true,
+                                Tuple.of(1), true,
+                                Tuple.of(2), false
+                ), predicateResultSet);
        }
-        @Test
+        @QueryEngineTest
-        void relationConstraintTest() {
+        void relationConstraintTest(QueryEvaluationHint hint) {
-                var person = new Symbol<>("Person", 1, Boolean.class, false);
+                var predicate = Query.of("RelationConstraint", (builder, p1, p2) -> builder.clause(
-                var friend = new Symbol<>("friend", 2, TruthValue.class, TruthValue.FALSE);
+                                personView.call(p1),
-                var personView = new KeyOnlyRelationView<>(person);
+                                personView.call(p2),
-                var friendMustView = new FilteredRelationView<>(friend, "must", TruthValue::must);
+                                friendMustView.call(p1, p2)
+                ));
-                var p1 = new Variable("p1");
-                var p2 = new Variable("p2");
-                var predicate = DNF.builder("RelationConstraint")
-                                .parameters(p1, p2)
-                                .clause(
-                                                new RelationViewAtom(personView, p1),
-                                                new RelationViewAtom(personView, p2),
-                                                new RelationViewAtom(friendMustView, p1, p2)
-                                )
-                                .build();
                var store = ModelStore.builder()
                                .symbols(person, friend)
-                                .with(ViatraModelQuery.ADAPTER)
+                                .with(ViatraModelQueryAdapter.builder()
-                                .queries(predicate)
+                                                .defaultHint(hint)
+                                                .queries(predicate))
                                .build();
                var model = store.createEmptyModel();
                var personInterpretation = model.getInterpretation(person);
                var friendInterpretation = model.getInterpretation(friend);
-                var queryEngine = model.getAdapter(ModelQuery.ADAPTER);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
                var predicateResultSet = queryEngine.getResultSet(predicate);
-                assertEquals(0, predicateResultSet.countResults());
                personInterpretation.put(Tuple.of(0), true);
                personInterpretation.put(Tuple.of(1), true);
                personInterpretation.put(Tuple.of(2), true);
@@ -94,97 +96,36 @@ class QueryTest {
                friendInterpretation.put(Tuple.of(0, 1), TruthValue.TRUE);
                friendInterpretation.put(Tuple.of(1, 0), TruthValue.TRUE);
                friendInterpretation.put(Tuple.of(1, 2), TruthValue.TRUE);
+                friendInterpretation.put(Tuple.of(1, 3), TruthValue.TRUE);
-                assertEquals(0, predicateResultSet.countResults());
                queryEngine.flushChanges();
-                assertEquals(3, predicateResultSet.countResults());
+                assertResults(Map.of(
-                compareMatchSets(predicateResultSet.allResults(), Set.of(Tuple.of(0, 1), Tuple.of(1, 0), Tuple.of(1, 2)));
+                                Tuple.of(0, 1), true,
+                                Tuple.of(1, 0), true,
+                                Tuple.of(1, 2), true,
+                                Tuple.of(2, 1), false
+                ), predicateResultSet);
        }
-        @Test
+        @QueryEngineTest
-        void andTest() {
+        void existTest(QueryEvaluationHint hint) {
-                var person = new Symbol<>("Person", 1, Boolean.class, false);
+                var predicate = Query.of("Exists", (builder, p1) -> builder.clause((p2) -> List.of(
-                var friend = new Symbol<>("friend", 2, TruthValue.class, TruthValue.FALSE);
+                                personView.call(p1),
-                var personView = new KeyOnlyRelationView<>(person);
+                                personView.call(p2),
-                var friendMustView = new FilteredRelationView<>(friend, "must", TruthValue::must);
+                                friendMustView.call(p1, p2)
+                )));
-                var p1 = new Variable("p1");
-                var p2 = new Variable("p2");
-                var predicate = DNF.builder("RelationConstraint")
-                                .parameters(p1, p2)
-                                .clause(
-                                                new RelationViewAtom(personView, p1),
-                                                new RelationViewAtom(personView, p2),
-                                                new RelationViewAtom(friendMustView, p1, p2),
-                                                new RelationViewAtom(friendMustView, p2, p1)
-                                )
-                                .build();
                var store = ModelStore.builder()
                                .symbols(person, friend)
-                                .with(ViatraModelQuery.ADAPTER)
+                                .with(ViatraModelQueryAdapter.builder()
-                                .queries(predicate)
+                                                .defaultHint(hint)
+                                                .queries(predicate))
                                .build();
                var model = store.createEmptyModel();
                var personInterpretation = model.getInterpretation(person);
                var friendInterpretation = model.getInterpretation(friend);
-                var queryEngine = model.getAdapter(ModelQuery.ADAPTER);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
-                var predicateResultSet = queryEngine.getResultSet(predicate);
-                assertEquals(0, predicateResultSet.countResults());
-                personInterpretation.put(Tuple.of(0), true);
-                personInterpretation.put(Tuple.of(1), true);
-                personInterpretation.put(Tuple.of(2), true);
-                friendInterpretation.put(Tuple.of(0, 1), TruthValue.TRUE);
-                friendInterpretation.put(Tuple.of(0, 2), TruthValue.TRUE);
-                queryEngine.flushChanges();
-                assertEquals(0, predicateResultSet.countResults());
-                friendInterpretation.put(Tuple.of(1, 0), TruthValue.TRUE);
-                queryEngine.flushChanges();
-                assertEquals(2, predicateResultSet.countResults());
-                compareMatchSets(predicateResultSet.allResults(), Set.of(Tuple.of(0, 1), Tuple.of(1, 0)));
-                friendInterpretation.put(Tuple.of(2, 0), TruthValue.TRUE);
-                queryEngine.flushChanges();
-                assertEquals(4, predicateResultSet.countResults());
-                compareMatchSets(predicateResultSet.allResults(), Set.of(Tuple.of(0, 1), Tuple.of(1, 0), Tuple.of(0, 2),
-                                Tuple.of(2, 0)));
-        }
-        @Test
-        void existTest() {
-                var person = new Symbol<>("Person", 1, Boolean.class, false);
-                var friend = new Symbol<>("friend", 2, TruthValue.class, TruthValue.FALSE);
-                var personView = new KeyOnlyRelationView<>(person);
-                var friendMustView = new FilteredRelationView<>(friend, "must", TruthValue::must);
-                var p1 = new Variable("p1");
-                var p2 = new Variable("p2");
-                var predicate = DNF.builder("RelationConstraint")
-                                .parameters(p1)
-                                .clause(
-                                                new RelationViewAtom(personView, p1),
-                                                new RelationViewAtom(personView, p2),
-                                                new RelationViewAtom(friendMustView, p1, p2)
-                                )
-                                .build();
-                var store = ModelStore.builder()
-                                .symbols(person, friend)
-                                .with(ViatraModelQuery.ADAPTER)
-                                .queries(predicate)
-                                .build();
-                var model = store.createEmptyModel();
-                var personInterpretation = model.getInterpretation(person);
-                var friendInterpretation = model.getInterpretation(friend);
-                var queryEngine = model.getAdapter(ModelQuery.ADAPTER);
                var predicateResultSet = queryEngine.getResultSet(predicate);
                personInterpretation.put(Tuple.of(0), true);
@@ -194,50 +135,44 @@ class QueryTest {
                friendInterpretation.put(Tuple.of(0, 1), TruthValue.TRUE);
                friendInterpretation.put(Tuple.of(1, 0), TruthValue.TRUE);
                friendInterpretation.put(Tuple.of(1, 2), TruthValue.TRUE);
+                friendInterpretation.put(Tuple.of(3, 2), TruthValue.TRUE);
-                assertEquals(0, predicateResultSet.countResults());
                queryEngine.flushChanges();
-                assertEquals(2, predicateResultSet.countResults());
+                assertResults(Map.of(
-                compareMatchSets(predicateResultSet.allResults(), Set.of(Tuple.of(0), Tuple.of(1)));
+                                Tuple.of(0), true,
+                                Tuple.of(1), true,
+                                Tuple.of(2), false,
+                                Tuple.of(3), false
+                ), predicateResultSet);
        }
-        @Test
+        @QueryEngineTest
-        void orTest() {
+        void orTest(QueryEvaluationHint hint) {
-                var person = new Symbol<>("Person", 1, Boolean.class, false);
+                var animal = Symbol.of("Animal", 1);
-                var animal = new Symbol<>("Animal", 1, Boolean.class, false);
+                var animalView = new KeyOnlyView<>(animal);
-                var friend = new Symbol<>("friend", 2, TruthValue.class, TruthValue.FALSE);
-                var personView = new KeyOnlyRelationView<>(person);
+                var predicate = Query.of("Or", (builder, p1, p2) -> builder.clause(
-                var animalView = new KeyOnlyRelationView<>(animal);
+                                personView.call(p1),
-                var friendMustView = new FilteredRelationView<>(friend, "must", TruthValue::must);
+                                personView.call(p2),
+                                friendMustView.call(p1, p2)
-                var p1 = new Variable("p1");
+                ).clause(
-                var p2 = new Variable("p2");
+                                animalView.call(p1),
-                var predicate = DNF.builder("Or")
+                                animalView.call(p2),
-                                .parameters(p1, p2)
+                                friendMustView.call(p1, p2)
-                                .clause(
+                ));
-                                                new RelationViewAtom(personView, p1),
-                                                new RelationViewAtom(personView, p2),
-                                                new RelationViewAtom(friendMustView, p1, p2)
-                                )
-                                .clause(
-                                                new RelationViewAtom(animalView, p1),
-                                                new RelationViewAtom(animalView, p2),
-                                                new RelationViewAtom(friendMustView, p1, p2)
-                                )
-                                .build();
                var store = ModelStore.builder()
                                .symbols(person, animal, friend)
-                                .with(ViatraModelQuery.ADAPTER)
+                                .with(ViatraModelQueryAdapter.builder()
-                                .queries(predicate)
+                                                .defaultHint(hint)
+                                                .queries(predicate))
                                .build();
                var model = store.createEmptyModel();
                var personInterpretation = model.getInterpretation(person);
                var animalInterpretation = model.getInterpretation(animal);
                var friendInterpretation = model.getInterpretation(friend);
-                var queryEngine = model.getAdapter(ModelQuery.ADAPTER);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
                var predicateResultSet = queryEngine.getResultSet(predicate);
                personInterpretation.put(Tuple.of(0), true);
@@ -252,35 +187,33 @@ class QueryTest {
                friendInterpretation.put(Tuple.of(3, 0), TruthValue.TRUE);
                queryEngine.flushChanges();
-                assertEquals(2, predicateResultSet.countResults());
+                assertResults(Map.of(
-                compareMatchSets(predicateResultSet.allResults(), Set.of(Tuple.of(0, 1), Tuple.of(2, 3)));
+                                Tuple.of(0, 1), true,
+                                Tuple.of(0, 2), false,
+                                Tuple.of(2, 3), true,
+                                Tuple.of(3, 0), false,
+                                Tuple.of(3, 2), false
+                ), predicateResultSet);
        }
-        @Test
+        @QueryEngineTest
-        void equalityTest() {
+        void equalityTest(QueryEvaluationHint hint) {
-                var person = new Symbol<>("Person", 1, Boolean.class, false);
+                var predicate = Query.of("Equality", (builder, p1, p2) -> builder.clause(
-                var personView = new KeyOnlyRelationView<>(person);
+                                personView.call(p1),
+                                personView.call(p2),
-                var p1 = new Variable("p1");
+                                p1.isEquivalent(p2)
-                var p2 = new Variable("p2");
+                ));
-                var predicate = DNF.builder("Equality")
-                                .parameters(p1, p2)
-                                .clause(
-                                                new RelationViewAtom(personView, p1),
-                                                new RelationViewAtom(personView, p2),
-                                                new EquivalenceAtom(p1, p2)
-                                )
-                                .build();
                var store = ModelStore.builder()
                                .symbols(person)
-                                .with(ViatraModelQuery.ADAPTER)
+                                .with(ViatraModelQueryAdapter.builder()
-                                .queries(predicate)
+                                                .defaultHint(hint)
+                                                .queries(predicate))
                                .build();
                var model = store.createEmptyModel();
                var personInterpretation = model.getInterpretation(person);
-                var queryEngine = model.getAdapter(ModelQuery.ADAPTER);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
                var predicateResultSet = queryEngine.getResultSet(predicate);
                personInterpretation.put(Tuple.of(0), true);
@@ -288,41 +221,36 @@ class QueryTest {
                personInterpretation.put(Tuple.of(2), true);
                queryEngine.flushChanges();
-                assertEquals(3, predicateResultSet.countResults());
+                assertResults(Map.of(
-                compareMatchSets(predicateResultSet.allResults(), Set.of(Tuple.of(0, 0), Tuple.of(1, 1), Tuple.of(2, 2)));
+                                Tuple.of(0, 0), true,
+                                Tuple.of(1, 1), true,
+                                Tuple.of(2, 2), true,
+                                Tuple.of(0, 1), false,
+                                Tuple.of(3, 3), false
+                ), predicateResultSet);
        }
-        @Test
+        @QueryEngineTest
-        void inequalityTest() {
+        void inequalityTest(QueryEvaluationHint hint) {
-                var person = new Symbol<>("Person", 1, Boolean.class, false);
+                var predicate = Query.of("Inequality", (builder, p1, p2, p3) -> builder.clause(
-                var friend = new Symbol<>("friend", 2, TruthValue.class, TruthValue.FALSE);
+                                personView.call(p1),
-                var personView = new KeyOnlyRelationView<>(person);
+                                personView.call(p2),
-                var friendMustView = new FilteredRelationView<>(friend, "must", TruthValue::must);
+                                friendMustView.call(p1, p3),
+                                friendMustView.call(p2, p3),
-                var p1 = new Variable("p1");
+                                p1.notEquivalent(p2)
-                var p2 = new Variable("p2");
+                ));
-                var p3 = new Variable("p3");
-                var predicate = DNF.builder("Inequality")
-                                .parameters(p1, p2, p3)
-                                .clause(
-                                                new RelationViewAtom(personView, p1),
-                                                new RelationViewAtom(personView, p2),
-                                                new RelationViewAtom(friendMustView, p1, p3),
-                                                new RelationViewAtom(friendMustView, p2, p3),
-                                                new EquivalenceAtom(false, p1, p2)
-                                )
-                                .build();
                var store = ModelStore.builder()
                                .symbols(person, friend)
-                                .with(ViatraModelQuery.ADAPTER)
+                                .with(ViatraModelQueryAdapter.builder()
-                                .queries(predicate)
+                                                .defaultHint(hint)
+                                                .queries(predicate))
                                .build();
                var model = store.createEmptyModel();
                var personInterpretation = model.getInterpretation(person);
                var friendInterpretation = model.getInterpretation(friend);
-                var queryEngine = model.getAdapter(ModelQuery.ADAPTER);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
                var predicateResultSet = queryEngine.getResultSet(predicate);
                personInterpretation.put(Tuple.of(0), true);
@@ -333,49 +261,37 @@ class QueryTest {
                friendInterpretation.put(Tuple.of(1, 2), TruthValue.TRUE);
                queryEngine.flushChanges();
-                assertEquals(2, predicateResultSet.countResults());
+                assertResults(Map.of(
-                compareMatchSets(predicateResultSet.allResults(), Set.of(Tuple.of(0, 1, 2), Tuple.of(1, 0, 2)));
+                                Tuple.of(0, 1, 2), true,
+                                Tuple.of(1, 0, 2), true,
+                                Tuple.of(0, 0, 2), false
+                ), predicateResultSet);
        }
-        @Test
+        @QueryEngineTest
-        void patternCallTest() {
+        void patternCallTest(QueryEvaluationHint hint) {
-                var person = new Symbol<>("Person", 1, Boolean.class, false);
+                var friendPredicate = Query.of("Friend", (builder, p1, p2) -> builder.clause(
-                var friend = new Symbol<>("friend", 2, TruthValue.class, TruthValue.FALSE);
+                                personView.call(p1),
-                var personView = new KeyOnlyRelationView<>(person);
+                                personView.call(p2),
-                var friendMustView = new FilteredRelationView<>(friend, "must", TruthValue::must);
+                                friendMustView.call(p1, p2)
+                ));
-                var p1 = new Variable("p1");
+                var predicate = Query.of("PositivePatternCall", (builder, p3, p4) -> builder.clause(
-                var p2 = new Variable("p2");
+                                personView.call(p3),
-                var friendPredicate = DNF.builder("RelationConstraint")
+                                personView.call(p4),
-                                .parameters(p1, p2)
+                                friendPredicate.call(p3, p4)
-                                .clause(
+                ));
-                                                new RelationViewAtom(personView, p1),
-                                                new RelationViewAtom(personView, p2),
-                                                new RelationViewAtom(friendMustView, p1, p2)
-                                )
-                                .build();
-                var p3 = new Variable("p3");
-                var p4 = new Variable("p4");
-                var predicate = DNF.builder("PositivePatternCall")
-                                .parameters(p3, p4)
-                                .clause(
-                                                new RelationViewAtom(personView, p3),
-                                                new RelationViewAtom(personView, p4),
-                                                new DNFCallAtom(friendPredicate, p3, p4)
-                                )
-                                .build();
                var store = ModelStore.builder()
                                .symbols(person, friend)
-                                .with(ViatraModelQuery.ADAPTER)
+                                .with(ViatraModelQueryAdapter.builder()
-                                .queries(predicate)
+                                                .defaultHint(hint)
+                                                .queries(predicate))
                                .build();
                var model = store.createEmptyModel();
                var personInterpretation = model.getInterpretation(person);
                var friendInterpretation = model.getInterpretation(friend);
-                var queryEngine = model.getAdapter(ModelQuery.ADAPTER);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
                var predicateResultSet = queryEngine.getResultSet(predicate);
                personInterpretation.put(Tuple.of(0), true);
@@ -387,37 +303,33 @@ class QueryTest {
                friendInterpretation.put(Tuple.of(1, 2), TruthValue.TRUE);
                queryEngine.flushChanges();
-                assertEquals(3, predicateResultSet.countResults());
+                assertResults(Map.of(
+                                Tuple.of(0, 1), true,
+                                Tuple.of(1, 0), true,
+                                Tuple.of(1, 2), true,
+                                Tuple.of(2, 1), false
+                ), predicateResultSet);
        }
-        @Test
+        @QueryEngineTest
-        void negativeRelationViewTest() {
+        void negativeRelationViewTest(QueryEvaluationHint hint) {
-                var person = new Symbol<>("Person", 1, Boolean.class, false);
+                var predicate = Query.of("NegativePatternCall", (builder, p1, p2) -> builder.clause(
-                var friend = new Symbol<>("friend", 2, TruthValue.class, TruthValue.FALSE);
+                                personView.call(p1),
-                var personView = new KeyOnlyRelationView<>(person);
+                                personView.call(p2),
-                var friendMustView = new FilteredRelationView<>(friend, "must", TruthValue::must);
+                                not(friendMustView.call(p1, p2))
+                ));
-                var p1 = new Variable("p1");
-                var p2 = new Variable("p2");
-                var predicate = DNF.builder("NegativePatternCall")
-                                .parameters(p1, p2)
-                                .clause(
-                                                new RelationViewAtom(personView, p1),
-                                                new RelationViewAtom(personView, p2),
-                                                new RelationViewAtom(false, friendMustView, p1, p2)
-                                )
-                                .build();
                var store = ModelStore.builder()
                                .symbols(person, friend)
-                                .with(ViatraModelQuery.ADAPTER)
+                                .with(ViatraModelQueryAdapter.builder()
-                                .queries(predicate)
+                                                .defaultHint(hint)
+                                                .queries(predicate))
                                .build();
                var model = store.createEmptyModel();
                var personInterpretation = model.getInterpretation(person);
                var friendInterpretation = model.getInterpretation(friend);
-                var queryEngine = model.getAdapter(ModelQuery.ADAPTER);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
                var predicateResultSet = queryEngine.getResultSet(predicate);
                personInterpretation.put(Tuple.of(0), true);
@@ -429,48 +341,44 @@ class QueryTest {
                friendInterpretation.put(Tuple.of(1, 2), TruthValue.TRUE);
                queryEngine.flushChanges();
-                assertEquals(6, predicateResultSet.countResults());
+                assertResults(Map.of(
+                                Tuple.of(0, 0), true,
+                                Tuple.of(0, 2), true,
+                                Tuple.of(1, 1), true,
+                                Tuple.of(2, 0), true,
+                                Tuple.of(2, 1), true,
+                                Tuple.of(2, 2), true,
+                                Tuple.of(0, 1), false,
+                                Tuple.of(1, 0), false,
+                                Tuple.of(1, 2), false,
+                                Tuple.of(0, 3), false
+                ), predicateResultSet);
        }
-        @Test
+        @QueryEngineTest
-        void negativePatternCallTest() {
+        void negativePatternCallTest(QueryEvaluationHint hint) {
-                var person = new Symbol<>("Person", 1, Boolean.class, false);
+                var friendPredicate = Query.of("Friend", (builder, p1, p2) -> builder.clause(
-                var friend = new Symbol<>("friend", 2, TruthValue.class, TruthValue.FALSE);
+                                personView.call(p1),
-                var personView = new KeyOnlyRelationView<>(person);
+                                personView.call(p2),
-                var friendMustView = new FilteredRelationView<>(friend, "must", TruthValue::must);
+                                friendMustView.call(p1, p2)
+                ));
-                var p1 = new Variable("p1");
+                var predicate = Query.of("NegativePatternCall", (builder, p3, p4) -> builder.clause(
-                var p2 = new Variable("p2");
+                                personView.call(p3),
-                var friendPredicate = DNF.builder("RelationConstraint")
+                                personView.call(p4),
-                                .parameters(p1, p2)
+                                not(friendPredicate.call(p3, p4))
-                                .clause(
+                ));
-                                                new RelationViewAtom(personView, p1),
-                                                new RelationViewAtom(personView, p2),
-                                                new RelationViewAtom(friendMustView, p1, p2)
-                                )
-                                .build();
-                var p3 = new Variable("p3");
-                var p4 = new Variable("p4");
-                var predicate = DNF.builder("NegativePatternCall")
-                                .parameters(p3, p4)
-                                .clause(
-                                                new RelationViewAtom(personView, p3),
-                                                new RelationViewAtom(personView, p4),
-                                                new DNFCallAtom(false, friendPredicate, p3, p4)
-                                )
-                                .build();
                var store = ModelStore.builder()
                                .symbols(person, friend)
-                                .with(ViatraModelQuery.ADAPTER)
+                                .with(ViatraModelQueryAdapter.builder()
-                                .queries(predicate)
+                                                .defaultHint(hint)
+                                                .queries(predicate))
                                .build();
                var model = store.createEmptyModel();
                var personInterpretation = model.getInterpretation(person);
                var friendInterpretation = model.getInterpretation(friend);
-                var queryEngine = model.getAdapter(ModelQuery.ADAPTER);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
                var predicateResultSet = queryEngine.getResultSet(predicate);
                personInterpretation.put(Tuple.of(0), true);
@@ -482,37 +390,38 @@ class QueryTest {
                friendInterpretation.put(Tuple.of(1, 2), TruthValue.TRUE);
                queryEngine.flushChanges();
-                assertEquals(6, predicateResultSet.countResults());
+                assertResults(Map.of(
+                                Tuple.of(0, 0), true,
+                                Tuple.of(0, 2), true,
+                                Tuple.of(1, 1), true,
+                                Tuple.of(2, 0), true,
+                                Tuple.of(2, 1), true,
+                                Tuple.of(2, 2), true,
+                                Tuple.of(0, 1), false,
+                                Tuple.of(1, 0), false,
+                                Tuple.of(1, 2), false,
+                                Tuple.of(0, 3), false
+                ), predicateResultSet);
        }
-        @Test
+        @QueryEngineTest
-        void negativeRelationViewWithQuantificationTest() {
+        void negativeRelationViewWithQuantificationTest(QueryEvaluationHint hint) {
-                var person = new Symbol<>("Person", 1, Boolean.class, false);
+                var predicate = Query.of("Negative", (builder, p1) -> builder.clause(
-                var friend = new Symbol<>("friend", 2, TruthValue.class, TruthValue.FALSE);
+                                personView.call(p1),
-                var personView = new KeyOnlyRelationView<>(person);
+                                not(friendMustView.call(p1, Variable.of()))
-                var friendMustView = new FilteredRelationView<>(friend, "must", TruthValue::must);
+                ));
-                var p1 = new Variable("p1");
-                var p2 = new Variable("p2");
-                var predicate = DNF.builder("Count")
-                                .parameters(p1)
-                                .clause(
-                                                new RelationViewAtom(personView, p1),
-                                                new RelationViewAtom(false, friendMustView, p1, p2)
-                                )
-                                .build();
                var store = ModelStore.builder()
                                .symbols(person, friend)
-                                .with(ViatraModelQuery.ADAPTER)
+                                .with(ViatraModelQueryAdapter.builder()
-                                .queries(predicate)
+                                                .defaultHint(hint)
+                                                .queries(predicate))
                                .build();
                var model = store.createEmptyModel();
                var personInterpretation = model.getInterpretation(person);
                var friendInterpretation = model.getInterpretation(friend);
-                var queryEngine = model.getAdapter(ModelQuery.ADAPTER);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
                var predicateResultSet = queryEngine.getResultSet(predicate);
                personInterpretation.put(Tuple.of(0), true);
@@ -523,46 +432,37 @@ class QueryTest {
                friendInterpretation.put(Tuple.of(0, 2), TruthValue.TRUE);
                queryEngine.flushChanges();
-                assertEquals(2, predicateResultSet.countResults());
+                assertResults(Map.of(
+                                Tuple.of(0), false,
+                                Tuple.of(1), true,
+                                Tuple.of(2), true,
+                                Tuple.of(3), false
+                ), predicateResultSet);
        }
-        @Test
+        @QueryEngineTest
-        void negativeWithQuantificationTest() {
+        void negativeWithQuantificationTest(QueryEvaluationHint hint) {
-                var person = new Symbol<>("Person", 1, Boolean.class, false);
+                var called = Query.of("Called", (builder, p1, p2) -> builder.clause(
-                var friend = new Symbol<>("friend", 2, TruthValue.class, TruthValue.FALSE);
+                                personView.call(p1),
-                var personView = new KeyOnlyRelationView<>(person);
+                                personView.call(p2),
-                var friendMustView = new FilteredRelationView<>(friend, "must", TruthValue::must);
+                                friendMustView.call(p1, p2)
+                ));
-                var p1 = new Variable("p1");
+                var predicate = Query.of("Negative", (builder, p1) -> builder.clause(
-                var p2 = new Variable("p2");
+                                personView.call(p1),
+                                not(called.call(p1, Variable.of()))
-                var called = DNF.builder("Called")
+                ));
-                                .parameters(p1, p2)
-                                .clause(
-                                                new RelationViewAtom(personView, p1),
-                                                new RelationViewAtom(personView, p2),
-                                                new RelationViewAtom(friendMustView, p1, p2)
-                                )
-                                .build();
-                var predicate = DNF.builder("Count")
-                                .parameters(p1)
-                                .clause(
-                                                new RelationViewAtom(personView, p1),
-                                                new DNFCallAtom(false, called, p1, p2)
-                                )
-                                .build();
                var store = ModelStore.builder()
                                .symbols(person, friend)
-                                .with(ViatraModelQuery.ADAPTER)
+                                .with(ViatraModelQueryAdapter.builder()
-                                .queries(predicate)
+                                                .defaultHint(hint)
+                                                .queries(predicate))
                                .build();
                var model = store.createEmptyModel();
                var personInterpretation = model.getInterpretation(person);
                var friendInterpretation = model.getInterpretation(friend);
-                var queryEngine = model.getAdapter(ModelQuery.ADAPTER);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
                var predicateResultSet = queryEngine.getResultSet(predicate);
                personInterpretation.put(Tuple.of(0), true);
@@ -573,37 +473,33 @@ class QueryTest {
                friendInterpretation.put(Tuple.of(0, 2), TruthValue.TRUE);
                queryEngine.flushChanges();
-                assertEquals(2, predicateResultSet.countResults());
+                assertResults(Map.of(
+                                Tuple.of(0), false,
+                                Tuple.of(1), true,
+                                Tuple.of(2), true,
+                                Tuple.of(3), false
+                ), predicateResultSet);
        }
-        @Test
+        @QueryEngineTest
-        void transitiveRelationViewTest() {
+        void transitiveRelationViewTest(QueryEvaluationHint hint) {
-                var person = new Symbol<>("Person", 1, Boolean.class, false);
+                var predicate = Query.of("Transitive", (builder, p1, p2) -> builder.clause(
-                var friend = new Symbol<>("friend", 2, TruthValue.class, TruthValue.FALSE);
+                                personView.call(p1),
-                var personView = new KeyOnlyRelationView<>(person);
+                                personView.call(p2),
-                var friendMustView = new FilteredRelationView<>(friend, "must", TruthValue::must);
+                                friendMustView.callTransitive(p1, p2)
+                ));
-                var p1 = new Variable("p1");
-                var p2 = new Variable("p2");
-                var predicate = DNF.builder("TransitivePatternCall")
-                                .parameters(p1, p2)
-                                .clause(
-                                                new RelationViewAtom(personView, p1),
-                                                new RelationViewAtom(personView, p2),
-                                                new RelationViewAtom(CallPolarity.TRANSITIVE, friendMustView, p1, p2)
-                                )
-                                .build();
                var store = ModelStore.builder()
                                .symbols(person, friend)
-                                .with(ViatraModelQuery.ADAPTER)
+                                .with(ViatraModelQueryAdapter.builder()
-                                .queries(predicate)
+                                                .defaultHint(hint)
+                                                .queries(predicate))
                                .build();
                var model = store.createEmptyModel();
                var personInterpretation = model.getInterpretation(person);
                var friendInterpretation = model.getInterpretation(friend);
-                var queryEngine = model.getAdapter(ModelQuery.ADAPTER);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
                var predicateResultSet = queryEngine.getResultSet(predicate);
                personInterpretation.put(Tuple.of(0), true);
@@ -614,48 +510,44 @@ class QueryTest {
                friendInterpretation.put(Tuple.of(1, 2), TruthValue.TRUE);
                queryEngine.flushChanges();
-                assertEquals(3, predicateResultSet.countResults());
+                assertResults(Map.of(
+                                Tuple.of(0, 0), false,
+                                Tuple.of(0, 1), true,
+                                Tuple.of(0, 2), true,
+                                Tuple.of(1, 0), false,
+                                Tuple.of(1, 1), false,
+                                Tuple.of(1, 2), true,
+                                Tuple.of(2, 0), false,
+                                Tuple.of(2, 1), false,
+                                Tuple.of(2, 2), false,
+                                Tuple.of(2, 3), false
+                ), predicateResultSet);
        }
-        @Test
+        @QueryEngineTest
-        void transitivePatternCallTest() {
+        void transitivePatternCallTest(QueryEvaluationHint hint) {
-                var person = new Symbol<>("Person", 1, Boolean.class, false);
+                var called = Query.of("Called", (builder, p1, p2) -> builder.clause(
-                var friend = new Symbol<>("friend", 2, TruthValue.class, TruthValue.FALSE);
+                                personView.call(p1),
-                var personView = new KeyOnlyRelationView<>(person);
+                                personView.call(p2),
-                var friendMustView = new FilteredRelationView<>(friend, "must", TruthValue::must);
+                                friendMustView.call(p1, p2)
+                ));
-                var p1 = new Variable("p1");
+                var predicate = Query.of("Transitive", (builder, p1, p2) -> builder.clause(
-                var p2 = new Variable("p2");
+                                personView.call(p1),
-                var friendPredicate = DNF.builder("RelationConstraint")
+                                personView.call(p2),
-                                .parameters(p1, p2)
+                                called.callTransitive(p1, p2)
-                                .clause(
+                ));
-                                                new RelationViewAtom(personView, p1),
-                                                new RelationViewAtom(personView, p2),
-                                                new RelationViewAtom(friendMustView, p1, p2)
-                                )
-                                .build();
-                var p3 = new Variable("p3");
-                var p4 = new Variable("p4");
-                var predicate = DNF.builder("TransitivePatternCall")
-                                .parameters(p3, p4)
-                                .clause(
-                                                new RelationViewAtom(personView, p3),
-                                                new RelationViewAtom(personView, p4),
-                                                new DNFCallAtom(CallPolarity.TRANSITIVE, friendPredicate, p3, p4)
-                                )
-                                .build();
                var store = ModelStore.builder()
                                .symbols(person, friend)
-                                .with(ViatraModelQuery.ADAPTER)
+                                .with(ViatraModelQueryAdapter.builder()
-                                .queries(predicate)
+                                                .defaultHint(hint)
+                                                .queries(predicate))
                                .build();
                var model = store.createEmptyModel();
                var personInterpretation = model.getInterpretation(person);
                var friendInterpretation = model.getInterpretation(friend);
-                var queryEngine = model.getAdapter(ModelQuery.ADAPTER);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
                var predicateResultSet = queryEngine.getResultSet(predicate);
                personInterpretation.put(Tuple.of(0), true);
@@ -666,16 +558,150 @@ class QueryTest {
                friendInterpretation.put(Tuple.of(1, 2), TruthValue.TRUE);
                queryEngine.flushChanges();
-                assertEquals(3, predicateResultSet.countResults());
+                assertResults(Map.of(
+                                Tuple.of(0, 0), false,
+                                Tuple.of(0, 1), true,
+                                Tuple.of(0, 2), true,
+                                Tuple.of(1, 0), false,
+                                Tuple.of(1, 1), false,
+                                Tuple.of(1, 2), true,
+                                Tuple.of(2, 0), false,
+                                Tuple.of(2, 1), false,
+                                Tuple.of(2, 2), false,
+                                Tuple.of(2, 3), false
+                ), predicateResultSet);
+        }
+        @Test
+        void filteredIntegerViewTest() {
+                var distance = Symbol.of("distance", 2, Integer.class);
+                var nearView = new FilteredView<>(distance, value -> value < 2);
+                var farView = new FilteredView<>(distance, value -> value >= 5);
+                var dangerQuery = Query.of("danger", (builder, a1, a2) -> builder.clause((a3) -> List.of(
+                                a1.notEquivalent(a2),
+                                nearView.call(a1, a3),
+                                nearView.call(a2, a3),
+                                not(farView.call(a1, a2))
+                )));
+                var store = ModelStore.builder()
+                                .symbols(distance)
+                                .with(ViatraModelQueryAdapter.builder()
+                                                .queries(dangerQuery))
+                                .build();
+                var model = store.createEmptyModel();
+                var distanceInterpretation = model.getInterpretation(distance);
+                distanceInterpretation.put(Tuple.of(0, 1), 1);
+                distanceInterpretation.put(Tuple.of(1, 0), 1);
+                distanceInterpretation.put(Tuple.of(0, 2), 1);
+                distanceInterpretation.put(Tuple.of(2, 0), 1);
+                distanceInterpretation.put(Tuple.of(1, 2), 3);
+                distanceInterpretation.put(Tuple.of(2, 1), 3);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var dangerResultSet = queryEngine.getResultSet(dangerQuery);
+                queryEngine.flushChanges();
+                assertResults(Map.of(
+                                Tuple.of(0, 1), false,
+                                Tuple.of(0, 2), false,
+                                Tuple.of(1, 2), true,
+                                Tuple.of(2, 1), true
+                ), dangerResultSet);
+        }
+        @Test
+        void filteredDoubleViewTest() {
+                var distance = Symbol.of("distance", 2, Double.class);
+                var nearView = new FilteredView<>(distance, value -> value < 2);
+                var farView = new FilteredView<>(distance, value -> value >= 5);
+                var dangerQuery = Query.of("danger", (builder, a1, a2) -> builder.clause((a3) -> List.of(
+                                a1.notEquivalent(a2),
+                                nearView.call(a1, a3),
+                                nearView.call(a2, a3),
+                                not(farView.call(a1, a2))
+                )));
+                var store = ModelStore.builder()
+                                .symbols(distance)
+                                .with(ViatraModelQueryAdapter.builder()
+                                                .queries(dangerQuery))
+                                .build();
+                var model = store.createEmptyModel();
+                var distanceInterpretation = model.getInterpretation(distance);
+                distanceInterpretation.put(Tuple.of(0, 1), 1.0);
+                distanceInterpretation.put(Tuple.of(1, 0), 1.0);
+                distanceInterpretation.put(Tuple.of(0, 2), 1.0);
+                distanceInterpretation.put(Tuple.of(2, 0), 1.0);
+                distanceInterpretation.put(Tuple.of(1, 2), 3.0);
+                distanceInterpretation.put(Tuple.of(2, 1), 3.0);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var dangerResultSet = queryEngine.getResultSet(dangerQuery);
+                queryEngine.flushChanges();
+                assertResults(Map.of(
+                                Tuple.of(0, 1), false,
+                                Tuple.of(0, 2), false,
+                                Tuple.of(1, 2), true,
+                                Tuple.of(2, 1), true
+                ), dangerResultSet);
+        }
+        @QueryEngineTest
+        void assumeTest(QueryEvaluationHint hint) {
+                var age = Symbol.of("age", 1, Integer.class);
+                var ageView = new FunctionView<>(age);
+                var query = Query.of("Constraint", (builder, p1) -> builder.clause(Integer.class, (x) -> List.of(
+                                personView.call(p1),
+                                ageView.call(p1, x),
+                                assume(greaterEq(x, constant(18)))
+                )));
+                var store = ModelStore.builder()
+                                .symbols(person, age)
+                                .with(ViatraModelQueryAdapter.builder()
+                                                .defaultHint(hint)
+                                                .queries(query))
+                                .build();
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var ageInterpretation = model.getInterpretation(age);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var queryResultSet = queryEngine.getResultSet(query);
+                personInterpretation.put(Tuple.of(0), true);
+                personInterpretation.put(Tuple.of(1), true);
+                ageInterpretation.put(Tuple.of(0), 12);
+                ageInterpretation.put(Tuple.of(1), 24);
+                queryEngine.flushChanges();
+                assertResults(Map.of(
+                                Tuple.of(0), false,
+                                Tuple.of(1), true,
+                                Tuple.of(2), false
+                ), queryResultSet);
        }
-        static void compareMatchSets(Stream<TupleLike> matchSet, Set<Tuple> expected) {
+        @Test
-                Set<Tuple> translatedMatchSet = new HashSet<>();
+        void alwaysFalseTest() {
-                var iterator = matchSet.iterator();
+                var predicate = Query.of("AlwaysFalse", builder -> builder.parameter("p1"));
-                while (iterator.hasNext()) {
-                        var element = iterator.next();
+                var store = ModelStore.builder()
-                        translatedMatchSet.add(element.toTuple());
+                                .symbols(person)
-                }
+                                .with(ViatraModelQueryAdapter.builder()
-                assertEquals(expected, translatedMatchSet);
+                                                .queries(predicate))
+                                .build();
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var predicateResultSet = queryEngine.getResultSet(predicate);
+                personInterpretation.put(Tuple.of(0), true);
+                personInterpretation.put(Tuple.of(1), true);
+                personInterpretation.put(Tuple.of(2), true);
+                queryEngine.flushChanges();
+                assertResults(Map.of(), predicateResultSet);
        }
 }
diff --git a/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/QueryTransactionTest.java b/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/QueryTransactionTest.java
index 98995339..66f043c6 100644
--- a/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/QueryTransactionTest.java
+++ b/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/QueryTransactionTest.java
@@ -1,43 +1,163 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
 package tools.refinery.store.query.viatra;
+import org.eclipse.viatra.query.runtime.matchers.backend.QueryEvaluationHint;
+import org.junit.jupiter.api.Disabled;
 import org.junit.jupiter.api.Test;
 import tools.refinery.store.model.ModelStore;
-import tools.refinery.store.query.DNF;
+import tools.refinery.store.query.ModelQueryAdapter;
-import tools.refinery.store.query.ModelQuery;
+import tools.refinery.store.query.dnf.Query;
-import tools.refinery.store.query.Variable;
+import tools.refinery.store.query.dnf.RelationalQuery;
-import tools.refinery.store.query.atom.RelationViewAtom;
+import tools.refinery.store.query.view.AnySymbolView;
-import tools.refinery.store.query.view.KeyOnlyRelationView;
+import tools.refinery.store.query.view.FilteredView;
+import tools.refinery.store.query.view.FunctionView;
+import tools.refinery.store.query.view.KeyOnlyView;
 import tools.refinery.store.representation.Symbol;
 import tools.refinery.store.tuple.Tuple;
-import static org.junit.jupiter.api.Assertions.*;
+import java.util.Map;
+import java.util.Optional;
+import static org.junit.jupiter.api.Assertions.assertFalse;
+import static org.junit.jupiter.api.Assertions.assertTrue;
+import static tools.refinery.store.query.viatra.tests.QueryAssertions.assertNullableResults;
+import static tools.refinery.store.query.viatra.tests.QueryAssertions.assertResults;
 class QueryTransactionTest {
+        private static final Symbol<Boolean> person = Symbol.of("Person", 1);
+        private static final Symbol<Integer> age = Symbol.of("age", 1, Integer.class);
+        private static final AnySymbolView personView = new KeyOnlyView<>(person);
+        private static final AnySymbolView ageView = new FunctionView<>(age);
+        private static final RelationalQuery predicate = Query.of("TypeConstraint", (builder, p1) ->
+                        builder.clause(personView.call(p1)));
        @Test
        void flushTest() {
-                var person = new Symbol<>("Person", 1, Boolean.class, false);
+                var store = ModelStore.builder()
-                var asset = new Symbol<>("Asset", 1, Boolean.class, false);
+                                .symbols(person)
-                var personView = new KeyOnlyRelationView<>(person);
+                                .with(ViatraModelQueryAdapter.builder()
+                                                .queries(predicate))
-                var p1 = new Variable("p1");
-                var predicate = DNF.builder("TypeConstraint")
-                                .parameters(p1)
-                                .clause(new RelationViewAtom(personView, p1))
                                .build();
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var predicateResultSet = queryEngine.getResultSet(predicate);
+                assertResults(Map.of(
+                                Tuple.of(0), false,
+                                Tuple.of(1), false,
+                                Tuple.of(2), false,
+                                Tuple.of(3), false
+                ), predicateResultSet);
+                assertFalse(queryEngine.hasPendingChanges());
+                personInterpretation.put(Tuple.of(0), true);
+                personInterpretation.put(Tuple.of(1), true);
+                assertResults(Map.of(
+                                Tuple.of(0), false,
+                                Tuple.of(1), false,
+                                Tuple.of(2), false,
+                                Tuple.of(3), false
+                ), predicateResultSet);
+                assertTrue(queryEngine.hasPendingChanges());
+                queryEngine.flushChanges();
+                assertResults(Map.of(
+                                Tuple.of(0), true,
+                                Tuple.of(1), true,
+                                Tuple.of(2), false,
+                                Tuple.of(3), false
+                ), predicateResultSet);
+                assertFalse(queryEngine.hasPendingChanges());
+                personInterpretation.put(Tuple.of(1), false);
+                personInterpretation.put(Tuple.of(2), true);
+                assertResults(Map.of(
+                                Tuple.of(0), true,
+                                Tuple.of(1), true,
+                                Tuple.of(2), false,
+                                Tuple.of(3), false
+                ), predicateResultSet);
+                assertTrue(queryEngine.hasPendingChanges());
+                queryEngine.flushChanges();
+                assertResults(Map.of(
+                                Tuple.of(0), true,
+                                Tuple.of(1), false,
+                                Tuple.of(2), true,
+                                Tuple.of(3), false
+                ), predicateResultSet);
+                assertFalse(queryEngine.hasPendingChanges());
+        }
+        @Test
+        void localSearchTest() {
+                var store = ModelStore.builder()
+                                .symbols(person)
+                                .with(ViatraModelQueryAdapter.builder()
+                                        .defaultHint(new QueryEvaluationHint(null, QueryEvaluationHint.BackendRequirement.DEFAULT_SEARCH))
+                                        .queries(predicate))
+                                .build();
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var predicateResultSet = queryEngine.getResultSet(predicate);
+                assertResults(Map.of(
+                                Tuple.of(0), false,
+                                Tuple.of(1), false,
+                                Tuple.of(2), false,
+                                Tuple.of(3), false
+                ), predicateResultSet);
+                assertFalse(queryEngine.hasPendingChanges());
+                personInterpretation.put(Tuple.of(0), true);
+                personInterpretation.put(Tuple.of(1), true);
+                assertResults(Map.of(
+                                Tuple.of(0), true,
+                                Tuple.of(1), true,
+                                Tuple.of(2), false,
+                                Tuple.of(3), false
+                ), predicateResultSet);
+                assertFalse(queryEngine.hasPendingChanges());
+                personInterpretation.put(Tuple.of(1), false);
+                personInterpretation.put(Tuple.of(2), true);
+                assertResults(Map.of(
+                                Tuple.of(0), true,
+                                Tuple.of(1), false,
+                                Tuple.of(2), true,
+                                Tuple.of(3), false
+                ), predicateResultSet);
+                assertFalse(queryEngine.hasPendingChanges());
+        }
+        @Test
+        void unrelatedChangesTest() {
+                var asset = Symbol.of("Asset", 1);
                var store = ModelStore.builder()
                                .symbols(person, asset)
-                                .with(ViatraModelQuery.ADAPTER)
+                                .with(ViatraModelQueryAdapter.builder()
-                                .queries(predicate)
+                                                .queries(predicate))
                                .build();
                var model = store.createEmptyModel();
                var personInterpretation = model.getInterpretation(person);
                var assetInterpretation = model.getInterpretation(asset);
-                var queryEngine = model.getAdapter(ModelQuery.ADAPTER);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
                var predicateResultSet = queryEngine.getResultSet(predicate);
-                assertEquals(0, predicateResultSet.countResults());
                assertFalse(queryEngine.hasPendingChanges());
                personInterpretation.put(Tuple.of(0), true);
@@ -46,19 +166,208 @@ class QueryTransactionTest {
                assetInterpretation.put(Tuple.of(1), true);
                assetInterpretation.put(Tuple.of(2), true);
-                assertEquals(0, predicateResultSet.countResults());
+                assertResults(Map.of(
+                                Tuple.of(0), false,
+                                Tuple.of(1), false,
+                                Tuple.of(2), false,
+                                Tuple.of(3), false,
+                                Tuple.of(4), false
+                ), predicateResultSet);
                assertTrue(queryEngine.hasPendingChanges());
                queryEngine.flushChanges();
-                assertEquals(2, predicateResultSet.countResults());
+                assertResults(Map.of(
+                                Tuple.of(0), true,
+                                Tuple.of(1), true,
+                                Tuple.of(2), false,
+                                Tuple.of(3), false,
+                                Tuple.of(4), false
+                ), predicateResultSet);
                assertFalse(queryEngine.hasPendingChanges());
-                personInterpretation.put(Tuple.of(4), true);
+                assetInterpretation.put(Tuple.of(3), true);
-                assertEquals(2, predicateResultSet.countResults());
+                assertFalse(queryEngine.hasPendingChanges());
-                assertTrue(queryEngine.hasPendingChanges());
+                assertResults(Map.of(
+                                Tuple.of(0), true,
+                                Tuple.of(1), true,
+                                Tuple.of(2), false,
+                                Tuple.of(3), false,
+                                Tuple.of(4), false
+                ), predicateResultSet);
+                queryEngine.flushChanges();
+                assertResults(Map.of(
+                                Tuple.of(0), true,
+                                Tuple.of(1), true,
+                                Tuple.of(2), false,
+                                Tuple.of(3), false,
+                                Tuple.of(4), false
+                ), predicateResultSet);
+                assertFalse(queryEngine.hasPendingChanges());
+        }
+        @Test
+        void tupleChangingChangeTest() {
+                var query = Query.of("TypeConstraint", Integer.class, (builder, p1, output) -> builder.clause(
+                                personView.call(p1),
+                                ageView.call(p1, output)
+                ));
+                var store = ModelStore.builder()
+                                .symbols(person, age)
+                                .with(ViatraModelQueryAdapter.builder()
+                                                .queries(query))
+                                .build();
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var ageInterpretation = model.getInterpretation(age);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var queryResultSet = queryEngine.getResultSet(query);
+                personInterpretation.put(Tuple.of(0), true);
+                ageInterpretation.put(Tuple.of(0), 24);
+                queryEngine.flushChanges();
+                assertResults(Map.of(Tuple.of(0), 24), queryResultSet);
+                ageInterpretation.put(Tuple.of(0), 25);
                queryEngine.flushChanges();
-                assertEquals(3, predicateResultSet.countResults());
+                assertResults(Map.of(Tuple.of(0), 25), queryResultSet);
+                ageInterpretation.put(Tuple.of(0), null);
+                queryEngine.flushChanges();
+                assertNullableResults(Map.of(Tuple.of(0), Optional.empty()), queryResultSet);
+        }
+        @Test
+        void tuplePreservingUnchangedTest() {
+                var adultView = new FilteredView<>(age, "adult", n -> n != null && n >= 18);
+                var query = Query.of("TypeConstraint", (builder, p1) -> builder.clause(
+                                personView.call(p1),
+                                adultView.call(p1)
+                ));
+                var store = ModelStore.builder()
+                                .symbols(person, age)
+                                .with(ViatraModelQueryAdapter.builder()
+                                                .queries(query))
+                                .build();
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var ageInterpretation = model.getInterpretation(age);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var queryResultSet = queryEngine.getResultSet(query);
+                personInterpretation.put(Tuple.of(0), true);
+                ageInterpretation.put(Tuple.of(0), 24);
+                queryEngine.flushChanges();
+                assertResults(Map.of(Tuple.of(0), true), queryResultSet);
+                ageInterpretation.put(Tuple.of(0), 25);
+                queryEngine.flushChanges();
+                assertResults(Map.of(Tuple.of(0), true), queryResultSet);
+                ageInterpretation.put(Tuple.of(0), 17);
+                queryEngine.flushChanges();
+                assertResults(Map.of(Tuple.of(0), false), queryResultSet);
+        }
+        @Disabled("TODO Fix DiffCursor")
+        @Test
+        void commitAfterFlushTest() {
+                var store = ModelStore.builder()
+                                .symbols(person)
+                                .with(ViatraModelQueryAdapter.builder()
+                                                .queries(predicate))
+                                .build();
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var predicateResultSet = queryEngine.getResultSet(predicate);
+                personInterpretation.put(Tuple.of(0), true);
+                personInterpretation.put(Tuple.of(1), true);
+                queryEngine.flushChanges();
+                assertResults(Map.of(
+                                Tuple.of(0), true,
+                                Tuple.of(1), true,
+                                Tuple.of(2), false,
+                                Tuple.of(3), false
+                ), predicateResultSet);
+                var state1 = model.commit();
+                personInterpretation.put(Tuple.of(1), false);
+                personInterpretation.put(Tuple.of(2), true);
+                queryEngine.flushChanges();
+                assertResults(Map.of(
+                                Tuple.of(0), true,
+                                Tuple.of(1), false,
+                                Tuple.of(2), true,
+                                Tuple.of(3), false
+                ), predicateResultSet);
+                model.restore(state1);
+                assertFalse(queryEngine.hasPendingChanges());
+                assertResults(Map.of(
+                                Tuple.of(0), true,
+                                Tuple.of(1), true,
+                                Tuple.of(2), false,
+                                Tuple.of(3), false
+                ), predicateResultSet);
+        }
+        @Disabled("TODO Fix DiffCursor")
+        @Test
+        void commitWithoutFlushTest() {
+                var store = ModelStore.builder()
+                                .symbols(person)
+                                .with(ViatraModelQueryAdapter.builder()
+                                                .queries(predicate))
+                                .build();
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var predicateResultSet = queryEngine.getResultSet(predicate);
+                personInterpretation.put(Tuple.of(0), true);
+                personInterpretation.put(Tuple.of(1), true);
+                assertResults(Map.of(), predicateResultSet);
+                assertTrue(queryEngine.hasPendingChanges());
+                var state1 = model.commit();
+                personInterpretation.put(Tuple.of(1), false);
+                personInterpretation.put(Tuple.of(2), true);
+                assertResults(Map.of(), predicateResultSet);
+                assertTrue(queryEngine.hasPendingChanges());
+                model.restore(state1);
+                assertResults(Map.of(
+                                Tuple.of(0), true,
+                                Tuple.of(1), true,
+                                Tuple.of(2), false,
+                                Tuple.of(3), false
+                ), predicateResultSet);
                assertFalse(queryEngine.hasPendingChanges());
        }
 }
diff --git a/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/internal/cardinality/UpperCardinalitySumAggregationOperatorStreamTest.java b/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/internal/cardinality/UpperCardinalitySumAggregationOperatorStreamTest.java
deleted file mode 100644
index c529117e..00000000
--- a/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/internal/cardinality/UpperCardinalitySumAggregationOperatorStreamTest.java
+++ /dev/null
@@ -1,51 +0,0 @@
-package tools.refinery.store.query.viatra.internal.cardinality;
-import org.junit.jupiter.params.ParameterizedTest;
-import org.junit.jupiter.params.provider.Arguments;
-import org.junit.jupiter.params.provider.MethodSource;
-import tools.refinery.store.representation.cardinality.UpperCardinalities;
-import tools.refinery.store.representation.cardinality.UpperCardinality;
-import java.util.List;
-import java.util.stream.Stream;
-import static org.hamcrest.MatcherAssert.assertThat;
-import static org.hamcrest.Matchers.equalTo;
-class UpperCardinalitySumAggregationOperatorStreamTest {
-        @ParameterizedTest
-        @MethodSource
-        void testStream(List<UpperCardinality> list, UpperCardinality expected) {
-                var result = UpperCardinalitySumAggregationOperator.INSTANCE.aggregateStream(list.stream());
-                assertThat(result, equalTo(expected));
-        }
-        static Stream<Arguments> testStream() {
-                return Stream.of(
-                                Arguments.of(List.of(), UpperCardinalities.ZERO),
-                                Arguments.of(List.of(UpperCardinality.of(3)), UpperCardinality.of(3)),
-                                Arguments.of(
-                                                List.of(
-                                                                UpperCardinality.of(2),
-                                                                UpperCardinality.of(3)
-                                                ),
-                                                UpperCardinality.of(5)
-                                ),
-                                Arguments.of(List.of(UpperCardinalities.UNBOUNDED), UpperCardinalities.UNBOUNDED),
-                                Arguments.of(
-                                                List.of(
-                                                                UpperCardinalities.UNBOUNDED,
-                                                                UpperCardinalities.UNBOUNDED
-                                                ),
-                                                UpperCardinalities.UNBOUNDED
-                                ),
-                                Arguments.of(
-                                                List.of(
-                                                                UpperCardinalities.UNBOUNDED,
-                                                                UpperCardinality.of(3)
-                                                ),
-                                                UpperCardinalities.UNBOUNDED
-                                )
-                );
-        }
-}
diff --git a/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/internal/cardinality/UpperCardinalitySumAggregationOperatorTest.java b/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/internal/cardinality/UpperCardinalitySumAggregationOperatorTest.java
deleted file mode 100644
index 20dad543..00000000
--- a/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/internal/cardinality/UpperCardinalitySumAggregationOperatorTest.java
+++ /dev/null
@@ -1,87 +0,0 @@
-package tools.refinery.store.query.viatra.internal.cardinality;
-import org.junit.jupiter.api.BeforeEach;
-import org.junit.jupiter.api.Test;
-import tools.refinery.store.representation.cardinality.UpperCardinalities;
-import tools.refinery.store.representation.cardinality.UpperCardinality;
-import static org.hamcrest.MatcherAssert.assertThat;
-import static org.hamcrest.Matchers.equalTo;
-class UpperCardinalitySumAggregationOperatorTest {
-        private UpperCardinalitySumAggregationOperator.Accumulator accumulator;
-        @BeforeEach
-        void beforeEach() {
-                accumulator = UpperCardinalitySumAggregationOperator.INSTANCE.createNeutral();
-        }
-        @Test
-        void emptyAggregationTest() {
-                assertResult(UpperCardinality.of(0));
-        }
-        @Test
-        void singleBoundedTest() {
-                insert(UpperCardinality.of(3));
-                assertResult(UpperCardinality.of(3));
-        }
-        @Test
-        void multipleBoundedTest() {
-                insert(UpperCardinality.of(2));
-                insert(UpperCardinality.of(3));
-                assertResult(UpperCardinality.of(5));
-        }
-        @Test
-        void singleUnboundedTest() {
-                insert(UpperCardinalities.UNBOUNDED);
-                assertResult(UpperCardinalities.UNBOUNDED);
-        }
-        @Test
-        void multipleUnboundedTest() {
-                insert(UpperCardinalities.UNBOUNDED);
-                insert(UpperCardinalities.UNBOUNDED);
-                assertResult(UpperCardinalities.UNBOUNDED);
-        }
-        @Test
-        void removeBoundedTest() {
-                insert(UpperCardinality.of(2));
-                insert(UpperCardinality.of(3));
-                remove(UpperCardinality.of(2));
-                assertResult(UpperCardinality.of(3));
-        }
-        @Test
-        void removeAllUnboundedTest() {
-                insert(UpperCardinalities.UNBOUNDED);
-                insert(UpperCardinality.of(3));
-                remove(UpperCardinalities.UNBOUNDED);
-                assertResult(UpperCardinality.of(3));
-        }
-        @Test
-        void removeSomeUnboundedTest() {
-                insert(UpperCardinalities.UNBOUNDED);
-                insert(UpperCardinalities.UNBOUNDED);
-                insert(UpperCardinality.of(3));
-                remove(UpperCardinalities.UNBOUNDED);
-                assertResult(UpperCardinalities.UNBOUNDED);
-        }
-        private void insert(UpperCardinality value) {
-                accumulator = UpperCardinalitySumAggregationOperator.INSTANCE.update(accumulator, value, true);
-        }
-        private void remove(UpperCardinality value) {
-                accumulator = UpperCardinalitySumAggregationOperator.INSTANCE.update(accumulator, value, false);
-        }
-        private void assertResult(UpperCardinality expected) {
-                var result = UpperCardinalitySumAggregationOperator.INSTANCE.getAggregate(accumulator);
-                assertThat(result, equalTo(expected));
-        }
-}
diff --git a/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/internal/matcher/MatcherUtilsTest.java b/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/internal/matcher/MatcherUtilsTest.java
new file mode 100644
index 00000000..968c6c5e
--- /dev/null
+++ b/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/internal/matcher/MatcherUtilsTest.java
@@ -0,0 +1,239 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.viatra.internal.matcher;
+import org.eclipse.viatra.query.runtime.matchers.tuple.*;
+import org.junit.jupiter.api.Test;
+import tools.refinery.store.tuple.Tuple;
+import tools.refinery.store.tuple.*;
+import java.util.List;
+import static org.hamcrest.MatcherAssert.assertThat;
+import static org.hamcrest.Matchers.*;
+import static org.junit.jupiter.api.Assertions.assertThrows;
+class MatcherUtilsTest {
+        @Test
+        void toViatra0Test() {
+                var viatraTuple = MatcherUtils.toViatraTuple(Tuple.of());
+                assertThat(viatraTuple.getSize(), is(0));
+                assertThat(viatraTuple, instanceOf(FlatTuple0.class));
+        }
+        @Test
+        void toViatra1Test() {
+                var viatraTuple = MatcherUtils.toViatraTuple(Tuple.of(2));
+                assertThat(viatraTuple.getSize(), is(1));
+                assertThat(viatraTuple.get(0), is(Tuple.of(2)));
+                assertThat(viatraTuple, instanceOf(FlatTuple1.class));
+        }
+        @Test
+        void toViatra2Test() {
+                var viatraTuple = MatcherUtils.toViatraTuple(Tuple.of(2, 3));
+                assertThat(viatraTuple.getSize(), is(2));
+                assertThat(viatraTuple.get(0), is(Tuple.of(2)));
+                assertThat(viatraTuple.get(1), is(Tuple.of(3)));
+                assertThat(viatraTuple, instanceOf(FlatTuple2.class));
+        }
+        @Test
+        void toViatra3Test() {
+                var viatraTuple = MatcherUtils.toViatraTuple(Tuple.of(2, 3, 5));
+                assertThat(viatraTuple.getSize(), is(3));
+                assertThat(viatraTuple.get(0), is(Tuple.of(2)));
+                assertThat(viatraTuple.get(1), is(Tuple.of(3)));
+                assertThat(viatraTuple.get(2), is(Tuple.of(5)));
+                assertThat(viatraTuple, instanceOf(FlatTuple3.class));
+        }
+        @Test
+        void toViatra4Test() {
+                var viatraTuple = MatcherUtils.toViatraTuple(Tuple.of(2, 3, 5, 8));
+                assertThat(viatraTuple.getSize(), is(4));
+                assertThat(viatraTuple.get(0), is(Tuple.of(2)));
+                assertThat(viatraTuple.get(1), is(Tuple.of(3)));
+                assertThat(viatraTuple.get(2), is(Tuple.of(5)));
+                assertThat(viatraTuple.get(3), is(Tuple.of(8)));
+                assertThat(viatraTuple, instanceOf(FlatTuple4.class));
+        }
+        @Test
+        void toViatra5Test() {
+                var viatraTuple = MatcherUtils.toViatraTuple(Tuple.of(2, 3, 5, 8, 13));
+                assertThat(viatraTuple.getSize(), is(5));
+                assertThat(viatraTuple.get(0), is(Tuple.of(2)));
+                assertThat(viatraTuple.get(1), is(Tuple.of(3)));
+                assertThat(viatraTuple.get(2), is(Tuple.of(5)));
+                assertThat(viatraTuple.get(3), is(Tuple.of(8)));
+                assertThat(viatraTuple.get(4), is(Tuple.of(13)));
+                assertThat(viatraTuple, instanceOf(FlatTuple.class));
+        }
+        @Test
+        void toRefinery0Test() {
+                var refineryTuple = MatcherUtils.toRefineryTuple(Tuples.flatTupleOf());
+                assertThat(refineryTuple.getSize(), is(0));
+                assertThat(refineryTuple, instanceOf(Tuple0.class));
+        }
+        @Test
+        void toRefinery1Test() {
+                var refineryTuple = MatcherUtils.toRefineryTuple(Tuples.flatTupleOf(Tuple.of(2)));
+                assertThat(refineryTuple.getSize(), is(1));
+                assertThat(refineryTuple.get(0), is(2));
+                assertThat(refineryTuple, instanceOf(Tuple1.class));
+        }
+        @Test
+        void toRefinery2Test() {
+                var refineryTuple = MatcherUtils.toRefineryTuple(Tuples.flatTupleOf(Tuple.of(2), Tuple.of(3)));
+                assertThat(refineryTuple.getSize(), is(2));
+                assertThat(refineryTuple.get(0), is(2));
+                assertThat(refineryTuple.get(1), is(3));
+                assertThat(refineryTuple, instanceOf(Tuple2.class));
+        }
+        @Test
+        void toRefinery3Test() {
+                var refineryTuple = MatcherUtils.toRefineryTuple(Tuples.flatTupleOf(Tuple.of(2), Tuple.of(3), Tuple.of(5)));
+                assertThat(refineryTuple.getSize(), is(3));
+                assertThat(refineryTuple.get(0), is(2));
+                assertThat(refineryTuple.get(1), is(3));
+                assertThat(refineryTuple.get(2), is(5));
+                assertThat(refineryTuple, instanceOf(Tuple3.class));
+        }
+        @Test
+        void toRefinery4Test() {
+                var refineryTuple = MatcherUtils.toRefineryTuple(Tuples.flatTupleOf(Tuple.of(2), Tuple.of(3), Tuple.of(5),
+                                Tuple.of(8)));
+                assertThat(refineryTuple.getSize(), is(4));
+                assertThat(refineryTuple.get(0), is(2));
+                assertThat(refineryTuple.get(1), is(3));
+                assertThat(refineryTuple.get(2), is(5));
+                assertThat(refineryTuple.get(3), is(8));
+                assertThat(refineryTuple, instanceOf(Tuple4.class));
+        }
+        @Test
+        void toRefinery5Test() {
+                var refineryTuple = MatcherUtils.toRefineryTuple(Tuples.flatTupleOf(Tuple.of(2), Tuple.of(3), Tuple.of(5),
+                                Tuple.of(8), Tuple.of(13)));
+                assertThat(refineryTuple.getSize(), is(5));
+                assertThat(refineryTuple.get(0), is(2));
+                assertThat(refineryTuple.get(1), is(3));
+                assertThat(refineryTuple.get(2), is(5));
+                assertThat(refineryTuple.get(3), is(8));
+                assertThat(refineryTuple.get(4), is(13));
+                assertThat(refineryTuple, instanceOf(TupleN.class));
+        }
+        @Test
+        void toRefineryInvalidValueTest() {
+                var viatraTuple = Tuples.flatTupleOf(Tuple.of(2), -98);
+                assertThrows(IllegalArgumentException.class, () -> MatcherUtils.toRefineryTuple(viatraTuple));
+        }
+        @Test
+        void keyToRefinery0Test() {
+                var refineryTuple = MatcherUtils.keyToRefineryTuple(Tuples.flatTupleOf(-99));
+                assertThat(refineryTuple.getSize(), is(0));
+                assertThat(refineryTuple, instanceOf(Tuple0.class));
+        }
+        @Test
+        void keyToRefinery1Test() {
+                var refineryTuple = MatcherUtils.keyToRefineryTuple(Tuples.flatTupleOf(Tuple.of(2), -99));
+                assertThat(refineryTuple.getSize(), is(1));
+                assertThat(refineryTuple.get(0), is(2));
+                assertThat(refineryTuple, instanceOf(Tuple1.class));
+        }
+        @Test
+        void keyToRefinery2Test() {
+                var refineryTuple = MatcherUtils.keyToRefineryTuple(Tuples.flatTupleOf(Tuple.of(2), Tuple.of(3), -99));
+                assertThat(refineryTuple.getSize(), is(2));
+                assertThat(refineryTuple.get(0), is(2));
+                assertThat(refineryTuple.get(1), is(3));
+                assertThat(refineryTuple, instanceOf(Tuple2.class));
+        }
+        @Test
+        void keyToRefinery3Test() {
+                var refineryTuple = MatcherUtils.keyToRefineryTuple(Tuples.flatTupleOf(Tuple.of(2), Tuple.of(3), Tuple.of(5),
+                                -99));
+                assertThat(refineryTuple.getSize(), is(3));
+                assertThat(refineryTuple.get(0), is(2));
+                assertThat(refineryTuple.get(1), is(3));
+                assertThat(refineryTuple.get(2), is(5));
+                assertThat(refineryTuple, instanceOf(Tuple3.class));
+        }
+        @Test
+        void keyToRefinery4Test() {
+                var refineryTuple = MatcherUtils.keyToRefineryTuple(Tuples.flatTupleOf(Tuple.of(2), Tuple.of(3), Tuple.of(5),
+                                Tuple.of(8), -99));
+                assertThat(refineryTuple.getSize(), is(4));
+                assertThat(refineryTuple.get(0), is(2));
+                assertThat(refineryTuple.get(1), is(3));
+                assertThat(refineryTuple.get(2), is(5));
+                assertThat(refineryTuple.get(3), is(8));
+                assertThat(refineryTuple, instanceOf(Tuple4.class));
+        }
+        @Test
+        void keyToRefinery5Test() {
+                var refineryTuple = MatcherUtils.keyToRefineryTuple(Tuples.flatTupleOf(Tuple.of(2), Tuple.of(3), Tuple.of(5),
+                                Tuple.of(8), Tuple.of(13), -99));
+                assertThat(refineryTuple.getSize(), is(5));
+                assertThat(refineryTuple.get(0), is(2));
+                assertThat(refineryTuple.get(1), is(3));
+                assertThat(refineryTuple.get(2), is(5));
+                assertThat(refineryTuple.get(3), is(8));
+                assertThat(refineryTuple.get(4), is(13));
+                assertThat(refineryTuple, instanceOf(TupleN.class));
+        }
+        @Test
+        void keyToRefineryTooShortTest() {
+                var viatraTuple = Tuples.flatTupleOf();
+                assertThrows(IllegalArgumentException.class, () -> MatcherUtils.keyToRefineryTuple(viatraTuple));
+        }
+        @Test
+        void keyToRefineryInvalidValueTest() {
+                var viatraTuple = Tuples.flatTupleOf(Tuple.of(2), -98, -99);
+                assertThrows(IllegalArgumentException.class, () -> MatcherUtils.keyToRefineryTuple(viatraTuple));
+        }
+        @Test
+        void getSingleValueTest() {
+                var value = MatcherUtils.getSingleValue(List.of(Tuples.flatTupleOf(Tuple.of(2), -99)));
+                assertThat(value, is(-99));
+        }
+        // Static analysis accurately determines that the result is always {@code null}, but we check anyways.
+        @SuppressWarnings("ConstantValue")
+        @Test
+        void getSingleValueNullTest() {
+                var value = MatcherUtils.getSingleValue((Iterable<? extends ITuple>) null);
+                assertThat(value, nullValue());
+        }
+        @Test
+        void getSingleValueEmptyTest() {
+                var value = MatcherUtils.getSingleValue(List.of());
+                assertThat(value, nullValue());
+        }
+        @Test
+        void getSingleValueMultipleTest() {
+                var viatraTuples = List.of(Tuples.flatTupleOf(Tuple.of(2), -98), Tuples.flatTupleOf(Tuple.of(2), -99));
+                assertThrows(IllegalStateException.class, () -> MatcherUtils.getSingleValue(viatraTuples));
+        }
+}
diff --git a/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/tests/QueryAssertions.java b/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/tests/QueryAssertions.java
new file mode 100644
index 00000000..ca089a9d
--- /dev/null
+++ b/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/tests/QueryAssertions.java
@@ -0,0 +1,57 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.viatra.tests;
+import org.junit.jupiter.api.function.Executable;
+import tools.refinery.store.query.resultset.ResultSet;
+import tools.refinery.store.tuple.Tuple;
+import java.util.*;
+import static org.hamcrest.MatcherAssert.assertThat;
+import static org.hamcrest.Matchers.is;
+import static org.hamcrest.Matchers.nullValue;
+import static org.junit.jupiter.api.Assertions.assertAll;
+public final class QueryAssertions {
+        private QueryAssertions() {
+                throw new IllegalStateException("This is a static utility class and should not be instantiated directly");
+        }
+        public static <T> void assertNullableResults(Map<Tuple, Optional<T>> expected, ResultSet<T> resultSet) {
+                var nullableValuesMap = new LinkedHashMap<Tuple, T>(expected.size());
+                for (var entry : expected.entrySet()) {
+                        nullableValuesMap.put(entry.getKey(), entry.getValue().orElse(null));
+                }
+                assertResults(nullableValuesMap, resultSet);
+        }
+        public static <T> void assertResults(Map<Tuple, T> expected, ResultSet<T> resultSet) {
+                var defaultValue = resultSet.getQuery().defaultValue();
+                var filteredExpected = new LinkedHashMap<Tuple, T>();
+                var executables = new ArrayList<Executable>();
+                for (var entry : expected.entrySet()) {
+                        var key = entry.getKey();
+                        var value = entry.getValue();
+                        if (!Objects.equals(value, defaultValue)) {
+                                filteredExpected.put(key, value);
+                        }
+                        executables.add(() -> assertThat("value for key " + key,resultSet.get(key), is(value)));
+                }
+                executables.add(() -> assertThat("results size", resultSet.size(), is(filteredExpected.size())));
+                var actual = new LinkedHashMap<Tuple, T>();
+                var cursor = resultSet.getAll();
+                while (cursor.move()) {
+                        var key = cursor.getKey();
+                        var previous = actual.put(key, cursor.getValue());
+                        assertThat("duplicate value for key " + key, previous, nullValue());
+                }
+                executables.add(() -> assertThat("results cursor", actual, is(filteredExpected)));
+                assertAll(executables);
+        }
+}
diff --git a/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/tests/QueryBackendHint.java b/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/tests/QueryBackendHint.java
new file mode 100644
index 00000000..dc0e92c8
--- /dev/null
+++ b/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/tests/QueryBackendHint.java
@@ -0,0 +1,27 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.viatra.tests;
+import org.eclipse.viatra.query.runtime.matchers.backend.QueryEvaluationHint;
+/**
+ * Overrides {@link QueryEvaluationHint#toString()} for pretty names in parametric test names.
+ */
+class QueryBackendHint extends QueryEvaluationHint {
+        public QueryBackendHint(BackendRequirement backendRequirementType) {
+                super(null, backendRequirementType);
+        }
+        @Override
+        public String toString() {
+                return switch (getQueryBackendRequirementType()) {
+                        case UNSPECIFIED -> "default";
+                        case DEFAULT_CACHING -> "incremental";
+                        case DEFAULT_SEARCH -> "localSearch";
+                        default -> throw new IllegalStateException("Unknown BackendRequirement");
+                };
+        }
+}
diff --git a/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/tests/QueryEngineTest.java b/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/tests/QueryEngineTest.java
new file mode 100644
index 00000000..d4f16da7
--- /dev/null
+++ b/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/tests/QueryEngineTest.java
@@ -0,0 +1,21 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.viatra.tests;
+import org.junit.jupiter.params.ParameterizedTest;
+import org.junit.jupiter.params.provider.ArgumentsSource;
+import java.lang.annotation.ElementType;
+import java.lang.annotation.Retention;
+import java.lang.annotation.RetentionPolicy;
+import java.lang.annotation.Target;
+@ParameterizedTest(name = "backend = {0}")
+@ArgumentsSource(QueryEvaluationHintSource.class)
+@Target(ElementType.METHOD)
+@Retention(RetentionPolicy.RUNTIME)
+public @interface QueryEngineTest {
+}
diff --git a/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/tests/QueryEvaluationHintSource.java b/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/tests/QueryEvaluationHintSource.java
new file mode 100644
index 00000000..9e75d5f3
--- /dev/null
+++ b/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/tests/QueryEvaluationHintSource.java
@@ -0,0 +1,24 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.viatra.tests;
+import org.eclipse.viatra.query.runtime.matchers.backend.QueryEvaluationHint;
+import org.junit.jupiter.api.extension.ExtensionContext;
+import org.junit.jupiter.params.provider.Arguments;
+import org.junit.jupiter.params.provider.ArgumentsProvider;
+import java.util.stream.Stream;
+public class QueryEvaluationHintSource implements ArgumentsProvider {
+        @Override
+        public Stream<? extends Arguments> provideArguments(ExtensionContext context) {
+                return Stream.of(
+                                Arguments.of(new QueryBackendHint(QueryEvaluationHint.BackendRequirement.UNSPECIFIED)),
+                                Arguments.of(new QueryBackendHint(QueryEvaluationHint.BackendRequirement.DEFAULT_CACHING)),
+                                Arguments.of(new QueryBackendHint(QueryEvaluationHint.BackendRequirement.DEFAULT_SEARCH))
+                );
+        }
+}