Move DSE to new subproject

24 files changed, 2660 insertions, 0 deletions

diff --git a/subprojects/store-dse/build.gradle.kts b/subprojects/store-dse/build.gradle.kts
new file mode 100644
index 00000000..bb1dee7d
--- /dev/null
+++ b/subprojects/store-dse/build.gradle.kts
@@ -0,0 +1,16 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+
+plugins {
+        id("tools.refinery.gradle.java-library")
+}
+
+dependencies {
+        api(project(":refinery-store-query"))
+        api(project(":refinery-store-query-viatra"))
+        api(project(":refinery-store-reasoning"))
+        api(project(":refinery-visualization"))
+}
diff --git a/subprojects/store-dse/src/main/java/tools/refinery/store/dse/ActionFactory.java b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/ActionFactory.java
new file mode 100644
index 00000000..2af22963
--- /dev/null
+++ b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/ActionFactory.java
@@ -0,0 +1,9 @@
+package tools.refinery.store.dse;
+
+import org.eclipse.collections.api.block.procedure.Procedure;
+import tools.refinery.store.model.Model;
+import tools.refinery.store.tuple.Tuple;
+
+public interface ActionFactory {
+        Procedure<Tuple> prepare(Model model);
+}
diff --git a/subprojects/store-dse/src/main/java/tools/refinery/store/dse/DesignSpaceExplorationAdapter.java b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/DesignSpaceExplorationAdapter.java
new file mode 100644
index 00000000..729a6fc9
--- /dev/null
+++ b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/DesignSpaceExplorationAdapter.java
@@ -0,0 +1,61 @@
+package tools.refinery.store.dse;
+
+import tools.refinery.store.adapter.ModelAdapter;
+import tools.refinery.store.map.Version;
+import tools.refinery.store.dse.internal.Activation;
+import tools.refinery.store.dse.internal.DesignSpaceExplorationBuilderImpl;
+import tools.refinery.store.dse.objectives.Fitness;
+import tools.refinery.store.dse.objectives.ObjectiveComparatorHelper;
+import tools.refinery.store.tuple.Tuple;
+import tools.refinery.store.tuple.Tuple1;
+
+import java.util.Collection;
+import java.util.List;
+import java.util.Random;
+
+public interface DesignSpaceExplorationAdapter extends ModelAdapter {
+        @Override
+        DesignSpaceExplorationStoreAdapter getStoreAdapter();
+
+        static DesignSpaceExplorationBuilder builder() {
+                return new DesignSpaceExplorationBuilderImpl();
+        }
+
+        Collection<Version> explore();
+
+        public int getModelSize();
+
+        public Tuple1 createObject();
+
+        public Tuple deleteObject(Tuple tuple);
+
+        public boolean checkGlobalConstraints();
+
+        public boolean backtrack();
+
+        public Fitness calculateFitness();
+
+        public void newSolution();
+
+        public int getDepth();
+
+        public Collection<Activation> getUntraversedActivations();
+
+        public boolean fireActivation(Activation activation);
+
+        public void fireRandomActivation();
+
+        public boolean isCurrentInTrajectory();
+
+        public List<Version> getTrajectory();
+
+        public boolean isCurrentStateAlreadyTraversed();
+
+        public ObjectiveComparatorHelper getObjectiveComparatorHelper();
+
+        public void restoreTrajectory(List<Version>  trajectory);
+
+        public void setRandom(Random random);
+
+        public void setRandom(long seed);
+}
diff --git a/subprojects/store-dse/src/main/java/tools/refinery/store/dse/DesignSpaceExplorationBuilder.java b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/DesignSpaceExplorationBuilder.java
new file mode 100644
index 00000000..8ca0037d
--- /dev/null
+++ b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/DesignSpaceExplorationBuilder.java
@@ -0,0 +1,43 @@
+package tools.refinery.store.dse;
+
+import tools.refinery.store.adapter.ModelAdapterBuilder;
+import tools.refinery.store.query.dnf.RelationalQuery;
+import tools.refinery.store.dse.internal.TransformationRule;
+import tools.refinery.store.dse.objectives.Objective;
+
+import java.util.Collection;
+import java.util.List;
+
+public interface DesignSpaceExplorationBuilder extends ModelAdapterBuilder {
+        default DesignSpaceExplorationBuilder transformations(TransformationRule... transformationRules) {
+                return transformations(List.of(transformationRules));
+        }
+
+        default DesignSpaceExplorationBuilder transformations(Collection<? extends TransformationRule> transformationRules) {
+                transformationRules.forEach(this::transformation);
+                return this;
+        }
+
+        default DesignSpaceExplorationBuilder globalConstraints(RelationalQuery... globalConstraints) {
+                return globalConstraints(List.of(globalConstraints));
+        }
+
+        default DesignSpaceExplorationBuilder globalConstraints(Collection<RelationalQuery> globalConstraints) {
+                globalConstraints.forEach(this::globalConstraint);
+                return this;
+        }
+
+        default DesignSpaceExplorationBuilder objectives(Objective... objectives) {
+                return objectives(List.of(objectives));
+        }
+
+        default DesignSpaceExplorationBuilder objectives(Collection<? extends Objective> objectives) {
+                objectives.forEach(this::objective);
+                return this;
+        }
+
+        DesignSpaceExplorationBuilder transformation(TransformationRule transformationRule);
+        DesignSpaceExplorationBuilder globalConstraint(RelationalQuery globalConstraint);
+        DesignSpaceExplorationBuilder objective(Objective objective);
+        DesignSpaceExplorationBuilder strategy(Strategy strategy);
+}
diff --git a/subprojects/store-dse/src/main/java/tools/refinery/store/dse/DesignSpaceExplorationStoreAdapter.java b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/DesignSpaceExplorationStoreAdapter.java
new file mode 100644
index 00000000..5964cd82
--- /dev/null
+++ b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/DesignSpaceExplorationStoreAdapter.java
@@ -0,0 +1,6 @@
+package tools.refinery.store.dse;
+
+import tools.refinery.store.adapter.ModelStoreAdapter;
+
+public interface DesignSpaceExplorationStoreAdapter extends ModelStoreAdapter {
+}
diff --git a/subprojects/store-dse/src/main/java/tools/refinery/store/dse/Strategy.java b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/Strategy.java
new file mode 100644
index 00000000..cef43386
--- /dev/null
+++ b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/Strategy.java
@@ -0,0 +1,8 @@
+package tools.refinery.store.dse;
+
+public interface Strategy {
+
+        public void initStrategy(DesignSpaceExplorationAdapter designSpaceExplorationAdapter);
+
+        public void explore();
+}
diff --git a/subprojects/store-dse/src/main/java/tools/refinery/store/dse/internal/Activation.java b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/internal/Activation.java
new file mode 100644
index 00000000..f1de00e6
--- /dev/null
+++ b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/internal/Activation.java
@@ -0,0 +1,9 @@
+package tools.refinery.store.dse.internal;
+
+import tools.refinery.store.tuple.Tuple;
+
+public record Activation(TransformationRule transformationRule, Tuple activation) {
+        public boolean fire() {
+                return transformationRule.fireActivation(activation);
+        }
+}
diff --git a/subprojects/store-dse/src/main/java/tools/refinery/store/dse/internal/DesignSpaceExplorationAdapterImpl.java b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/internal/DesignSpaceExplorationAdapterImpl.java
new file mode 100644
index 00000000..5fb54da9
--- /dev/null
+++ b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/internal/DesignSpaceExplorationAdapterImpl.java
@@ -0,0 +1,283 @@
+package tools.refinery.store.dse.internal;
+
+import tools.refinery.store.map.Version;
+import tools.refinery.store.model.Interpretation;
+import tools.refinery.store.model.Model;
+import tools.refinery.store.query.ModelQueryAdapter;
+import tools.refinery.store.query.dnf.RelationalQuery;
+import tools.refinery.store.dse.DesignSpaceExplorationAdapter;
+import tools.refinery.store.dse.DesignSpaceExplorationStoreAdapter;
+import tools.refinery.store.dse.Strategy;
+import tools.refinery.store.dse.objectives.Fitness;
+import tools.refinery.store.dse.objectives.Objective;
+import tools.refinery.store.dse.objectives.ObjectiveComparatorHelper;
+import tools.refinery.store.query.resultset.ResultSet;
+import tools.refinery.store.representation.Symbol;
+import tools.refinery.store.tuple.Tuple;
+import tools.refinery.store.tuple.Tuple1;
+import tools.refinery.visualization.ModelVisualizerAdapter;
+
+import java.util.*;
+
+public class DesignSpaceExplorationAdapterImpl implements DesignSpaceExplorationAdapter {
+        static final Symbol<Integer> NODE_COUNT_SYMBOL = Symbol.of("MODEL_SIZE", 0, Integer.class, 0);
+        private final Model model;
+        private final ModelQueryAdapter queryEngine;
+        private final DesignSpaceExplorationStoreAdapterImpl storeAdapter;
+        private final LinkedHashSet<TransformationRule> transformationRules;
+        private final LinkedHashSet<RelationalQuery> globalConstraints;
+        private final List<Objective> objectives;
+        private final LinkedHashSet<ResultSet<Boolean>> globalConstraintResultSets = new LinkedHashSet<>();
+        private final Interpretation<Integer> sizeInterpretation;
+        private final Strategy strategy;
+
+        private ObjectiveComparatorHelper objectiveComparatorHelper;
+        private List<Version> trajectory = new LinkedList<>();
+        private Fitness lastFitness;
+        private final LinkedHashSet<Version> solutions = new LinkedHashSet<>();
+        private Map<Version, LinkedHashSet<Activation>> statesAndUntraversedActivations;
+        private Map<Version, LinkedHashSet<Activation>> statesAndTraversedActivations;
+        private Random random = new Random();
+        private boolean isNewState = false;
+        private final boolean isVisualizationEnabled;
+        private final ModelVisualizerAdapter modelVisualizerAdapter;
+
+        public List<Version> getTrajectory() {
+                return new LinkedList<>(trajectory);
+        }
+
+        public DesignSpaceExplorationAdapterImpl(Model model, DesignSpaceExplorationStoreAdapterImpl storeAdapter) {
+                this.model = model;
+                this.storeAdapter = storeAdapter;
+                this.sizeInterpretation = model.getInterpretation(NODE_COUNT_SYMBOL);
+                queryEngine = model.getAdapter(ModelQueryAdapter.class);
+
+                globalConstraints = storeAdapter.getGlobalConstraints();
+                for (var constraint : globalConstraints) {
+                        globalConstraintResultSets.add(queryEngine.getResultSet(constraint));
+                }
+
+                transformationRules = storeAdapter.getTransformationSpecifications();
+                for (var rule : transformationRules) {
+                        rule.prepare(model, queryEngine);
+                }
+
+                objectives = storeAdapter.getObjectives();
+                statesAndUntraversedActivations = new HashMap<>();
+                statesAndTraversedActivations = new HashMap<>();
+                strategy = storeAdapter.getStrategy();
+                modelVisualizerAdapter = model.tryGetAdapter(ModelVisualizerAdapter.class).orElse(null);
+                isVisualizationEnabled = modelVisualizerAdapter != null;
+
+        }
+
+        @Override
+        public Model getModel() {
+                return model;
+        }
+
+        @Override
+        public DesignSpaceExplorationStoreAdapter getStoreAdapter() {
+                return storeAdapter;
+        }
+
+        @Override
+        public LinkedHashSet<Version> explore() {
+                var state = model.commit();
+                trajectory.add(state);
+                statesAndUntraversedActivations.put(state, getAllActivations());
+                statesAndTraversedActivations.put(state, new LinkedHashSet<>());
+                strategy.initStrategy(this);
+                strategy.explore();
+                return solutions;
+        }
+
+        @Override
+        public int getModelSize() {
+                return sizeInterpretation.get(Tuple.of());
+        }
+
+        @Override
+        public Tuple1 createObject() {
+                var newNodeId =  getModelSize();
+                sizeInterpretation.put(Tuple.of(), newNodeId + 1);
+                return Tuple.of(newNodeId);
+        }
+
+        @Override
+        public Tuple deleteObject(Tuple tuple) {
+                if (tuple.getSize() != 1) {
+                        throw new IllegalArgumentException("Tuple size must be 1");
+                }
+//              TODO: implement more efficient deletion
+//              if (tuple.get(0) == getModelSize() - 1) {
+//                      sizeInterpretation.put(Tuple.of(), getModelSize() - 1);
+//              }
+                return tuple;
+        }
+
+        @Override
+        public boolean checkGlobalConstraints() {
+                for (var resultSet : globalConstraintResultSets) {
+                        if (resultSet.size() > 0) {
+                                return false;
+                        }
+                }
+                return true;
+        }
+
+        @Override
+        public boolean backtrack() {
+                if (trajectory.size() < 2) {
+                        return false;
+                }
+                if (isVisualizationEnabled) {
+                        modelVisualizerAdapter.addTransition(trajectory.get(trajectory.size() - 1),
+                                        trajectory.get(trajectory.size() - 2), "backtrack");
+                }
+                model.restore(trajectory.get(trajectory.size() - 2));
+                trajectory.remove(trajectory.size() - 1);
+                return true;
+        }
+
+        @Override
+        public void restoreTrajectory(List<Version> trajectory) {
+                model.restore(trajectory.get(trajectory.size() - 1));
+//              if (isVisualizationEnabled) {
+//                      modelVisualizerAdapter.addTransition(this.trajectory.get(trajectory.size() - 1),
+//                                      trajectory.get(trajectory.size() - 1), "restore");
+//              }
+                this.trajectory = trajectory;
+
+        }
+
+        @Override
+        public void setRandom(Random random) {
+                this.random = random;
+        }
+
+        @Override
+        public void setRandom(long seed) {
+                this.random = new Random(seed);
+        }
+
+        @Override
+        public Fitness calculateFitness() {
+                Fitness result = new Fitness();
+                boolean satisfiesHardObjectives = true;
+                for (Objective objective : objectives) {
+                        var fitness = objective.getFitness(this);
+                        result.put(objective.getName(), fitness);
+                        if (objective.isHardObjective() && !objective.satisfiesHardObjective(fitness)) {
+                                satisfiesHardObjectives = false;
+                        }
+                }
+                result.setSatisfiesHardObjectives(satisfiesHardObjectives);
+
+                lastFitness = result;
+
+                return result;
+        }
+
+        @Override
+        public void newSolution() {
+                var state = model.getState();
+                solutions.add(state);
+                if (isVisualizationEnabled) {
+                        modelVisualizerAdapter.addSolution(state);
+                }
+        }
+
+        @Override
+        public int getDepth() {
+                return trajectory.size() - 1;
+        }
+
+        public LinkedHashSet<Activation> getUntraversedActivations() {
+//              return statesAndUntraversedActivations.get(model.getState());
+                LinkedHashSet<Activation> untraversedActivations = new LinkedHashSet<>();
+                for (Activation activation : getAllActivations()) {
+                        if (!statesAndTraversedActivations.get(model.getState()).contains(activation)) {
+                                untraversedActivations.add(activation);
+                        }
+                }
+
+                return untraversedActivations;
+        }
+
+        @Override
+        public boolean fireActivation(Activation activation) {
+                if (activation == null) {
+                        return false;
+                }
+                var previousState = model.getState();
+                if (!statesAndUntraversedActivations.get(previousState).contains(activation)) {
+//                      TODO: throw exception?
+                        return false;
+                }
+                if (!activation.fire()) {
+                        return false;
+                }
+                statesAndUntraversedActivations.get(previousState).remove(activation);
+                statesAndTraversedActivations.get(previousState).add(activation);
+                var newState = model.commit();
+                trajectory.add(newState);
+                isNewState = !statesAndUntraversedActivations.containsKey(newState);
+                statesAndUntraversedActivations.put(newState, getAllActivations());
+                statesAndTraversedActivations.put(newState, new LinkedHashSet<>());
+                if (isVisualizationEnabled) {
+                        if (isNewState) {
+                                modelVisualizerAdapter.addState(newState);
+                        }
+                        modelVisualizerAdapter.addTransition(trajectory.get(trajectory.size() - 2),
+                                        trajectory.get(trajectory.size() - 1), activation.transformationRule().getName(),
+                                        activation.activation());
+                }
+                return true;
+        }
+
+        @Override
+        public void fireRandomActivation() {
+                var activations = getUntraversedActivations();
+                if (activations.isEmpty()) {
+//                      TODO: throw exception
+                        return;
+                }
+                int index = random.nextInt(activations.size());
+                var iterator = activations.iterator();
+                while (index-- > 0) {
+                        iterator.next();
+                }
+                var activationId = iterator.next();
+                fireActivation(activationId);
+        }
+
+        @Override
+        public boolean isCurrentInTrajectory() {
+                return trajectory.contains(model.getState());
+        }
+
+        public LinkedHashSet<Activation> getAllActivations() {
+                LinkedHashSet<Activation> result = new LinkedHashSet<>();
+                for (var rule : transformationRules) {
+                        result.addAll(rule.getAllActivations());
+                }
+                return result;
+        }
+
+        public boolean isCurrentStateAlreadyTraversed() {
+//              TODO: check isomorphism?
+                return !isNewState;
+        }
+
+        public Fitness getLastFitness() {
+                return lastFitness;
+        }
+
+        public ObjectiveComparatorHelper getObjectiveComparatorHelper() {
+                if (objectiveComparatorHelper == null) {
+                        objectiveComparatorHelper = new ObjectiveComparatorHelper(objectives);
+                }
+                return objectiveComparatorHelper;
+        }
+}
diff --git a/subprojects/store-dse/src/main/java/tools/refinery/store/dse/internal/DesignSpaceExplorationBuilderImpl.java b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/internal/DesignSpaceExplorationBuilderImpl.java
new file mode 100644
index 00000000..03508adc
--- /dev/null
+++ b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/internal/DesignSpaceExplorationBuilderImpl.java
@@ -0,0 +1,62 @@
+package tools.refinery.store.dse.internal;
+
+import tools.refinery.store.adapter.AbstractModelAdapterBuilder;
+import tools.refinery.store.model.ModelStore;
+import tools.refinery.store.model.ModelStoreBuilder;
+import tools.refinery.store.query.dnf.RelationalQuery;
+import tools.refinery.store.dse.DesignSpaceExplorationBuilder;
+import tools.refinery.store.dse.Strategy;
+import tools.refinery.store.dse.objectives.Objective;
+
+import java.util.LinkedHashSet;
+import java.util.LinkedList;
+import java.util.List;
+
+public class DesignSpaceExplorationBuilderImpl
+                extends AbstractModelAdapterBuilder<DesignSpaceExplorationStoreAdapterImpl>
+                implements DesignSpaceExplorationBuilder {
+        private final LinkedHashSet<TransformationRule> transformationSpecifications = new LinkedHashSet<>();
+        private final LinkedHashSet<RelationalQuery> globalConstraints = new LinkedHashSet<>();
+        private final List<Objective> objectives = new LinkedList<>();
+        private Strategy strategy;
+
+        @Override
+        protected DesignSpaceExplorationStoreAdapterImpl doBuild(ModelStore store) {
+                return new DesignSpaceExplorationStoreAdapterImpl(store, transformationSpecifications, globalConstraints,
+                                objectives, strategy);
+        }
+
+        @Override
+        public DesignSpaceExplorationBuilder transformation(TransformationRule transformationRule) {
+                checkNotConfigured();
+                transformationSpecifications.add(transformationRule);
+                return this;
+        }
+
+        @Override
+        public DesignSpaceExplorationBuilder globalConstraint(RelationalQuery globalConstraint) {
+                checkNotConfigured();
+                globalConstraints.add(globalConstraint);
+                return this;
+        }
+
+        @Override
+        public DesignSpaceExplorationBuilder objective(Objective objective) {
+                checkNotConfigured();
+                objectives.add(objective);
+                return this;
+        }
+
+        @Override
+        public DesignSpaceExplorationBuilder strategy(Strategy strategy) {
+                checkNotConfigured();
+                this.strategy = strategy;
+                return this;
+        }
+
+        @Override
+        protected void doConfigure(ModelStoreBuilder storeBuilder) {
+                storeBuilder.symbols(DesignSpaceExplorationAdapterImpl.NODE_COUNT_SYMBOL);
+                super.doConfigure(storeBuilder);
+        }
+}
diff --git a/subprojects/store-dse/src/main/java/tools/refinery/store/dse/internal/DesignSpaceExplorationStoreAdapterImpl.java b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/internal/DesignSpaceExplorationStoreAdapterImpl.java
new file mode 100644
index 00000000..b06462ce
--- /dev/null
+++ b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/internal/DesignSpaceExplorationStoreAdapterImpl.java
@@ -0,0 +1,57 @@
+package tools.refinery.store.dse.internal;
+
+import tools.refinery.store.adapter.ModelAdapter;
+import tools.refinery.store.model.Model;
+import tools.refinery.store.model.ModelStore;
+import tools.refinery.store.query.dnf.RelationalQuery;
+import tools.refinery.store.dse.DesignSpaceExplorationStoreAdapter;
+import tools.refinery.store.dse.Strategy;
+import tools.refinery.store.dse.objectives.Objective;
+
+import java.util.LinkedHashSet;
+import java.util.List;
+
+public class DesignSpaceExplorationStoreAdapterImpl implements DesignSpaceExplorationStoreAdapter {
+        private final ModelStore store;
+        private final LinkedHashSet<TransformationRule> transformationSpecifications;
+        private final LinkedHashSet<RelationalQuery> globalConstraints;
+        private final List<Objective> objectives;
+        private final Strategy strategy;
+
+        public DesignSpaceExplorationStoreAdapterImpl(ModelStore store,
+                                                                                                  LinkedHashSet<TransformationRule> transformationSpecifications,
+                                                                                                  LinkedHashSet<RelationalQuery> globalConstraints,
+                                                                                                  List<Objective> objectives, Strategy strategy) {
+                        this.store = store;
+                        this.transformationSpecifications = transformationSpecifications;
+                        this.globalConstraints = globalConstraints;
+                        this.objectives = objectives;
+                        this.strategy = strategy;
+        }
+
+        @Override
+        public ModelStore getStore() {
+                return store;
+        }
+
+        @Override
+        public ModelAdapter createModelAdapter(Model model) {
+                return new DesignSpaceExplorationAdapterImpl(model, this);
+        }
+
+        public LinkedHashSet<TransformationRule> getTransformationSpecifications() {
+                return transformationSpecifications;
+        }
+
+        public LinkedHashSet<RelationalQuery> getGlobalConstraints() {
+                return globalConstraints;
+        }
+
+        public List<Objective> getObjectives() {
+                return objectives;
+        }
+
+        public Strategy getStrategy() {
+                return strategy;
+        }
+}
diff --git a/subprojects/store-dse/src/main/java/tools/refinery/store/dse/internal/TransformationRule.java b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/internal/TransformationRule.java
new file mode 100644
index 00000000..ed2e77f1
--- /dev/null
+++ b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/internal/TransformationRule.java
@@ -0,0 +1,84 @@
+package tools.refinery.store.dse.internal;
+
+import org.eclipse.collections.api.block.procedure.Procedure;
+import tools.refinery.store.model.Model;
+import tools.refinery.store.query.ModelQueryAdapter;
+import tools.refinery.store.query.dnf.RelationalQuery;
+import tools.refinery.store.dse.ActionFactory;
+import tools.refinery.store.query.resultset.OrderedResultSet;
+import tools.refinery.store.query.resultset.ResultSet;
+import tools.refinery.store.tuple.Tuple;
+
+import java.util.LinkedHashSet;
+import java.util.Random;
+
+public class TransformationRule {
+
+        private final String name;
+        private final RelationalQuery precondition;
+        private final ActionFactory actionFactory;
+        private Procedure<Tuple> action;
+        private OrderedResultSet<Boolean> activations;
+        private Random random;
+        private ModelQueryAdapter queryEngine;
+
+        public TransformationRule(String name, RelationalQuery precondition, ActionFactory actionFactory) {
+                this(name, precondition, actionFactory, new Random());
+        }
+
+        public TransformationRule(String name, RelationalQuery precondition, ActionFactory actionFactory, long seed) {
+                this(name, precondition, actionFactory, new Random(seed));
+        }
+
+        public TransformationRule(String name, RelationalQuery precondition, ActionFactory actionFactory, Random random) {
+                this.name = name;
+                this.precondition = precondition;
+                this.actionFactory = actionFactory;
+                this.random = random;
+        }
+        public boolean prepare(Model model, ModelQueryAdapter queryEngine) {
+                action = actionFactory.prepare(model);
+                this.queryEngine = queryEngine;
+                activations = new OrderedResultSet<>(queryEngine.getResultSet(precondition));
+                return true;
+        }
+
+        public boolean fireActivation(Tuple activation) {
+                action.accept(activation);
+                queryEngine.flushChanges();
+                return true;
+        }
+
+        public boolean fireRandomActivation() {
+                return getRandomActivation().fire();
+        }
+
+        public String getName() {
+                return name;
+        }
+
+        public RelationalQuery getPrecondition() {
+                return precondition;
+        }
+
+        public ResultSet<Boolean> getAllActivationsAsSets() {
+                return activations;
+        }
+
+        public LinkedHashSet<Activation> getAllActivations() {
+                var result = new LinkedHashSet<Activation>();
+                var cursor = activations.getAll();
+                while (cursor.move()) {
+                        result.add(new Activation(this, cursor.getKey()));
+                }
+                return result;
+        }
+
+        public Activation getRandomActivation() {
+                return new Activation(this, activations.getKey(random.nextInt(activations.size())));
+        }
+
+        public Activation getActivation(int index) {
+                return new Activation(this, activations.getKey(index));
+        }
+}
diff --git a/subprojects/store-dse/src/main/java/tools/refinery/store/dse/objectives/AlwaysSatisfiedDummyHardObjective.java b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/objectives/AlwaysSatisfiedDummyHardObjective.java
new file mode 100644
index 00000000..82695704
--- /dev/null
+++ b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/objectives/AlwaysSatisfiedDummyHardObjective.java
@@ -0,0 +1,51 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2016, Andras Szabolcs Nagy, Zoltan Ujhelyi and Daniel Varro
+ * 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.dse.objectives;
+
+import tools.refinery.store.dse.DesignSpaceExplorationAdapter;
+
+/**
+ * This hard objective is fulfilled in any circumstances. Use it if all states should be regarded as a valid solution.
+ *
+ * @author Andras Szabolcs Nagy
+ *
+ */
+public class AlwaysSatisfiedDummyHardObjective extends BaseObjective {
+
+        private static final String DEFAULT_NAME = "AlwaysSatisfiedDummyHardObjective";
+
+        public AlwaysSatisfiedDummyHardObjective() {
+                super(DEFAULT_NAME);
+        }
+
+        public AlwaysSatisfiedDummyHardObjective(String name) {
+                super(name);
+        }
+
+        @Override
+        public Double getFitness(DesignSpaceExplorationAdapter context) {
+                return 0d;
+        }
+
+        @Override
+        public boolean isHardObjective() {
+                return true;
+        }
+
+        @Override
+        public boolean satisfiesHardObjective(Double fitness) {
+                return true;
+        }
+
+        @Override
+        public Objective createNew() {
+                return this;
+        }
+
+}
diff --git a/subprojects/store-dse/src/main/java/tools/refinery/store/dse/objectives/BaseObjective.java b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/objectives/BaseObjective.java
new file mode 100644
index 00000000..24e3280d
--- /dev/null
+++ b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/objectives/BaseObjective.java
@@ -0,0 +1,131 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2015, Andras Szabolcs Nagy, Abel Hegedus, Akos Horvath, Zoltan Ujhelyi and Daniel Varro
+ * 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.dse.objectives;
+
+import tools.refinery.store.dse.DesignSpaceExplorationAdapter;
+
+import java.util.Comparator;
+import java.util.Objects;
+
+/**
+ * This abstract class implements the basic functionality of an objective ({@link Objective} namely its name,
+ * comparator, level and fitness hard constraint.
+ *
+ * @author Andras Szabolcs Nagy
+ *
+ */
+public abstract class BaseObjective implements Objective {
+
+        protected final String name;
+        protected Comparator<Double> comparator = Comparators.HIGHER_IS_BETTER;
+
+        protected double fitnessConstraint;
+        protected boolean isThereFitnessConstraint = false;
+        protected Comparator<Double> fitnessConstraintComparator;
+
+        public BaseObjective(String name) {
+                Objects.requireNonNull(name, "Name of the objective cannot be null.");
+                this.name = name;
+        }
+
+        @Override
+        public String getName() {
+                return name;
+        }
+
+        @Override
+        public void setComparator(Comparator<Double> comparator) {
+                this.comparator = comparator;
+        }
+
+        @Override
+        public Comparator<Double> getComparator() {
+                return comparator;
+        }
+
+        public BaseObjective withComparator(Comparator<Double> comparator) {
+                setComparator(comparator);
+                return this;
+        }
+
+        /**
+         * Adds a hard constraint on the fitness value. For example, the fitness value must be better than 10 to accept the
+         * current state as a solution.
+         *
+         * @param fitnessConstraint
+         *            Solutions should be better than this value.
+         * @param fitnessConstraintComparator
+         *            {@link Comparator} to determine if the current state is better than the given value.
+         * @return The actual instance to enable builder pattern like usage.
+         */
+        public BaseObjective withHardConstraintOnFitness(double fitnessConstraint,
+                                                                                                         Comparator<Double> fitnessConstraintComparator) {
+                this.fitnessConstraint = fitnessConstraint;
+                this.fitnessConstraintComparator = fitnessConstraintComparator;
+                this.isThereFitnessConstraint = true;
+                return this;
+        }
+
+        /**
+         * Adds a hard constraint on the fitness value. For example, the fitness value must be better than 10 to accept the
+         * current state as a solution. The provided comparator will be used.
+         *
+         * @param fitnessConstraint
+         *            Solutions should be better than this value.
+         * @return The actual instance to enable builder pattern like usage.
+         */
+        public BaseObjective withHardConstraintOnFitness(double fitnessConstraint) {
+                return withHardConstraintOnFitness(fitnessConstraint, null);
+        }
+
+        @Override
+        public void init(DesignSpaceExplorationAdapter context) {
+                if (fitnessConstraintComparator == null) {
+                        fitnessConstraintComparator = comparator;
+                }
+        }
+
+        @Override
+        public boolean isHardObjective() {
+                return isThereFitnessConstraint;
+        }
+
+        @Override
+        public boolean satisfiesHardObjective(Double fitness) {
+                if (isThereFitnessConstraint) {
+                        int compare = fitnessConstraintComparator.compare(fitness, fitnessConstraint);
+                        if (compare < 0) {
+                                return false;
+                        }
+                }
+                return true;
+        }
+
+        @Override
+        public int hashCode() {
+                return name.hashCode();
+        }
+
+        @Override
+        public boolean equals(Object obj) {
+                if (this == obj) {
+                        return true;
+                }
+                if (obj instanceof BaseObjective baseObjective) {
+                        return name.equals(baseObjective.getName());
+                }
+                return false;
+        }
+
+        @Override
+        public String toString() {
+                return name;
+        }
+
+}
diff --git a/subprojects/store-dse/src/main/java/tools/refinery/store/dse/objectives/Comparators.java b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/objectives/Comparators.java
new file mode 100644
index 00000000..e64e04e8
--- /dev/null
+++ b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/objectives/Comparators.java
@@ -0,0 +1,25 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2015, Andras Szabolcs Nagy, Abel Hegedus, Akos Horvath, Zoltan Ujhelyi and Daniel Varro
+ * 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.dse.objectives;
+
+import java.util.Comparator;
+
+public class Comparators {
+
+        private Comparators() { /*Utility class constructor*/ }
+
+        public static final Comparator<Double> HIGHER_IS_BETTER = (o1, o2) -> o1.compareTo(o2);
+
+        public static final Comparator<Double> LOWER_IS_BETTER = (o1, o2) -> o2.compareTo(o1);
+
+        private static final Double ZERO = (double) 0;
+
+        public static final Comparator<Double> DIFFERENCE_TO_ZERO_IS_BETTER = (o1, o2) -> ZERO.compareTo(Math.abs(o1)-Math.abs(o2));
+
+}
diff --git a/subprojects/store-dse/src/main/java/tools/refinery/store/dse/objectives/Fitness.java b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/objectives/Fitness.java
new file mode 100644
index 00000000..16caed85
--- /dev/null
+++ b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/objectives/Fitness.java
@@ -0,0 +1,21 @@
+package tools.refinery.store.dse.objectives;
+
+import java.util.HashMap;
+
+public class Fitness extends HashMap<String, Double> {
+
+        private boolean satisfiesHardObjectives;
+
+        public boolean isSatisfiesHardObjectives() {
+                return satisfiesHardObjectives;
+        }
+
+        public void setSatisfiesHardObjectives(boolean satisfiesHardObjectives) {
+                this.satisfiesHardObjectives = satisfiesHardObjectives;
+        }
+
+        @Override
+        public String toString() {
+                return super.toString() + " hardObjectives=" + satisfiesHardObjectives;
+        }
+}
diff --git a/subprojects/store-dse/src/main/java/tools/refinery/store/dse/objectives/Objective.java b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/objectives/Objective.java
new file mode 100644
index 00000000..4e14c9a3
--- /dev/null
+++ b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/objectives/Objective.java
@@ -0,0 +1,100 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2014, Miklos Foldenyi, Andras Szabolcs Nagy, Abel Hegedus, Akos Horvath, Zoltan Ujhelyi and Daniel Varro
+ * 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.dse.objectives;
+
+import tools.refinery.store.dse.DesignSpaceExplorationAdapter;
+
+import java.util.Comparator;
+
+/**
+ *
+ * Implementation of this interface represents a single objective of the DSE problem, which can assess a solution
+ * (trajectory) in a single number. It has a name and a comparator which orders two solution based on the calculated
+ * value.
+ * <p>
+ * Objectives can be either hard or soft objectives. Hard objectives can be satisfied or unsatisfied. If all of the hard
+ * objectives are satisfied on a single solution, then it is considered to be a valid (or goal) solution.
+ * <p>
+ * Certain objectives can have inner state for calculating the fitness value. In this case a new instance is necessary
+ * for every new thread, and the {@code createNew} method should not return the same instance more than once.
+ *
+ * @author Andras Szabolcs Nagy
+ *
+ */
+public interface Objective {
+
+        /**
+         * Returns the name of the objective.
+         *
+         * @return The name of the objective.
+         */
+        String getName();
+
+        /**
+         * Sets the {@link Comparator} which is used to compare fitness (doubles). It determines whether the objective is to
+         * minimize or maximize (or minimize or maximize a delta from a given number).
+         *
+         * @param comparator The comparator.
+         */
+        void setComparator(Comparator<Double> comparator);
+
+        /**
+         * Returns a {@link Comparator} which is used to compare fitness (doubles). It determines whether the objective is
+         * to minimize or maximize (or minimize or maximize a delta from a given number).
+         *
+         * @return The comparator.
+         */
+        Comparator<Double> getComparator();
+
+        /**
+         * Calculates the value of the objective on a given solution (trajectory).
+         *
+         * @param context
+         *            The {@link DesignSpaceExplorationAdapter}
+         * @return The objective value in double.
+         */
+        Double getFitness(DesignSpaceExplorationAdapter context);
+
+        /**
+         * Initializes the objective. It is called exactly once for every thread starts.
+         *
+         * @param context
+         *            The {@link DesignSpaceExplorationAdapter}.
+         */
+        void init(DesignSpaceExplorationAdapter context);
+
+        /**
+         * Returns an instance of the {@link Objective}. If it returns the same instance, all the methods has to be thread
+         * save as they are called concurrently.
+         *
+         * @return An instance of the objective.
+         */
+        Objective createNew();
+
+        /**
+         * Returns true if the objective is a hard objective. In such a case the method
+         * {@link Objective#satisfiesHardObjective(Double)} is called.
+         *
+         * @return True if the objective is a hard objective.
+         * @see Objective#satisfiesHardObjective(Double)
+         * @see Objective
+         */
+        boolean isHardObjective();
+
+        /**
+         * Determines if the given fitness value satisfies the hard objective.
+         *
+         * @param fitness
+         *            The fitness value of a solution.
+         * @return True if it satisfies the hard objective or it is a soft constraint.
+         * @see Objective
+         */
+        boolean satisfiesHardObjective(Double fitness);
+
+}
diff --git a/subprojects/store-dse/src/main/java/tools/refinery/store/dse/objectives/ObjectiveComparatorHelper.java b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/objectives/ObjectiveComparatorHelper.java
new file mode 100644
index 00000000..3184b8c4
--- /dev/null
+++ b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/objectives/ObjectiveComparatorHelper.java
@@ -0,0 +1,58 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2015, Andras Szabolcs Nagy, Abel Hegedus, Akos Horvath, Zoltan Ujhelyi and Daniel Varro
+ * 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.dse.objectives;
+
+import java.util.List;
+
+/**
+ * This class is responsible to compare and sort fitness values.
+ *
+ * @author András Szabolcs Nagy
+ */
+public class ObjectiveComparatorHelper {
+
+        private final List<Objective> objectives;
+
+        public ObjectiveComparatorHelper(List<Objective> objectives) {
+                this.objectives = objectives;
+        }
+
+        /**
+         * Compares two fitnesses based on dominance. Returns -1 if the second parameter {@code o2} is a better
+         * solution ({@code o2} dominates {@code o1}), 1 if the first parameter {@code o1} is better ({@code o1} dominates
+         * {@code o2}) and returns 0 if they are non-dominating each other.
+         */
+        public int compare(Fitness o1, Fitness o2) {
+
+                boolean o1HasBetterFitness = false;
+                boolean o2HasBetterFitness = false;
+
+                for (Objective objective : objectives) {
+                        String objectiveName = objective.getName();
+                        int sgn = objective.getComparator().compare(o1.get(objectiveName), o2.get(objectiveName));
+
+                        if (sgn < 0) {
+                                o2HasBetterFitness = true;
+                        }
+                        if (sgn > 0) {
+                                o1HasBetterFitness = true;
+                        }
+                        if (o1HasBetterFitness && o2HasBetterFitness) {
+                                break;
+                        }
+                }
+                if (o2HasBetterFitness) {
+                } else if (o1HasBetterFitness) {
+                        return 1;
+                }
+
+                return 0;
+
+        }
+}
diff --git a/subprojects/store-dse/src/main/java/tools/refinery/store/dse/strategy/BestFirstStrategy.java b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/strategy/BestFirstStrategy.java
new file mode 100644
index 00000000..05cc5bac
--- /dev/null
+++ b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/strategy/BestFirstStrategy.java
@@ -0,0 +1,190 @@
+package tools.refinery.store.dse.strategy;
+
+import tools.refinery.store.map.Version;
+import tools.refinery.store.dse.DesignSpaceExplorationAdapter;
+import tools.refinery.store.dse.Strategy;
+import tools.refinery.store.dse.internal.Activation;
+import tools.refinery.store.dse.objectives.Fitness;
+import tools.refinery.store.dse.objectives.ObjectiveComparatorHelper;
+
+import java.util.Collection;
+import java.util.Iterator;
+import java.util.List;
+import java.util.PriorityQueue;
+
+public class BestFirstStrategy implements Strategy {
+
+        private DesignSpaceExplorationAdapter dseAdapter;
+
+        private int maxDepth;
+        private boolean backTrackIfSolution = true;
+        private boolean onlyBetterFirst = false;
+
+        private PriorityQueue<TrajectoryWithFitness> trajectoriesToExplore;
+
+        private static class TrajectoryWithFitness {
+
+                public List<Version> trajectory;
+                public Fitness fitness;
+
+                public TrajectoryWithFitness(List<Version> trajectory, Fitness fitness) {
+                        super();
+                        this.trajectory = trajectory;
+                        this.fitness = fitness;
+                }
+
+                @Override
+                public String toString() {
+                        return trajectory.toString() + fitness.toString();
+                }
+
+        }
+
+        public BestFirstStrategy() {
+                this(-1);
+        }
+
+        public BestFirstStrategy(int maxDepth) {
+                if (maxDepth < 0) {
+                        this.maxDepth = Integer.MAX_VALUE;
+                } else {
+                        this.maxDepth = maxDepth;
+                }
+        }
+
+        public BestFirstStrategy continueIfHardObjectivesFulfilled() {
+                backTrackIfSolution = false;
+                return this;
+        }
+
+        public BestFirstStrategy goOnOnlyIfFitnessIsBetter() {
+                onlyBetterFirst = true;
+                return this;
+        }
+
+        @Override
+        public void initStrategy(DesignSpaceExplorationAdapter designSpaceExplorationAdapter) {
+                this.dseAdapter = designSpaceExplorationAdapter;
+                final ObjectiveComparatorHelper objectiveComparatorHelper = dseAdapter.getObjectiveComparatorHelper();
+
+                trajectoriesToExplore = new PriorityQueue<TrajectoryWithFitness>(11,
+                                (o1, o2) -> objectiveComparatorHelper.compare(o2.fitness, o1.fitness));
+        }
+
+        @Override
+        public void explore() {
+                final ObjectiveComparatorHelper objectiveComparatorHelper = dseAdapter.getObjectiveComparatorHelper();
+
+                boolean globalConstraintsAreSatisfied = dseAdapter.checkGlobalConstraints();
+                if (!globalConstraintsAreSatisfied) {
+                        // "Global constraint is not satisfied in the first state. Terminate.");
+                        return;
+                }
+
+                final Fitness firstFitness = dseAdapter.calculateFitness();
+                if (firstFitness.isSatisfiesHardObjectives()) {
+                        dseAdapter.newSolution();
+                        // "First state is a solution. Terminate.");
+                        if (backTrackIfSolution) {
+                                return;
+                        }
+                }
+
+                if (maxDepth == 0) {
+                        return;
+                }
+
+                final List<Version> firstTrajectory = dseAdapter.getTrajectory();
+                TrajectoryWithFitness currentTrajectoryWithFitness = new TrajectoryWithFitness(firstTrajectory, firstFitness);
+                trajectoriesToExplore.add(currentTrajectoryWithFitness);
+
+                mainLoop: while (true) {
+
+                        if (currentTrajectoryWithFitness == null) {
+                                if (trajectoriesToExplore.isEmpty()) {
+                                        // "State space is fully traversed.");
+                                        return;
+                                } else {
+                                        currentTrajectoryWithFitness = trajectoriesToExplore.element();
+//                                      if (logger.isDebugEnabled()) {
+//                                               "New trajectory is chosen: " + currentTrajectoryWithFitness);
+//                                      }
+                                        dseAdapter.restoreTrajectory(currentTrajectoryWithFitness.trajectory);
+                                }
+                        }
+
+                        Collection<Activation> activations = dseAdapter.getUntraversedActivations();
+                        Iterator<Activation> iterator = activations.iterator();
+
+
+
+                        while (iterator.hasNext()) {
+                                final Activation nextActivation = iterator.next();
+                                if (!iterator.hasNext()) {
+                                        // "Last untraversed activation of the state.");
+                                        trajectoriesToExplore.remove(currentTrajectoryWithFitness);
+                                }
+
+//                              if (logger.isDebugEnabled()) {
+//                                       "Executing new activation: " + nextActivation);
+//                              }
+                                dseAdapter.fireActivation(nextActivation);
+                                if (dseAdapter.isCurrentStateAlreadyTraversed()) {
+                                        // "The new state is already visited.");
+                                        dseAdapter.backtrack();
+                                } else if (!dseAdapter.checkGlobalConstraints()) {
+                                        // "Global constraint is not satisfied.");
+                                        dseAdapter.backtrack();
+                                } else {
+                                        final Fitness nextFitness = dseAdapter.calculateFitness();
+                                        if (nextFitness.isSatisfiesHardObjectives()) {
+                                                dseAdapter.newSolution();
+                                                // "Found a solution.");
+                                                if (backTrackIfSolution) {
+                                                        dseAdapter.backtrack();
+                                                        continue;
+                                                }
+                                        }
+                                        if (dseAdapter.getDepth() >= maxDepth) {
+                                                // "Reached max depth.");
+                                                dseAdapter.backtrack();
+                                                continue;
+                                        }
+
+                                        TrajectoryWithFitness nextTrajectoryWithFitness = new TrajectoryWithFitness(
+                                                        dseAdapter.getTrajectory(), nextFitness);
+                                        trajectoriesToExplore.add(nextTrajectoryWithFitness);
+
+                                        int compare = objectiveComparatorHelper.compare(currentTrajectoryWithFitness.fitness,
+                                                        nextTrajectoryWithFitness.fitness);
+                                        if (compare < 0) {
+                                                // "Better fitness, moving on: " + nextFitness);
+                                                currentTrajectoryWithFitness = nextTrajectoryWithFitness;
+                                                continue mainLoop;
+                                        } else if (compare == 0) {
+                                                if (onlyBetterFirst) {
+                                                        // "Equally good fitness, backtrack: " + nextFitness);
+                                                        dseAdapter.backtrack();
+                                                        continue;
+                                                } else {
+                                                        // "Equally good fitness, moving on: " + nextFitness);
+                                                        currentTrajectoryWithFitness = nextTrajectoryWithFitness;
+                                                        continue mainLoop;
+                                                }
+                                        } else {
+                                                // "Worse fitness.");
+                                                currentTrajectoryWithFitness = null;
+                                                continue mainLoop;
+                                        }
+                                }
+                        }
+
+                        // "State is fully traversed.");
+                        trajectoriesToExplore.remove(currentTrajectoryWithFitness);
+                        currentTrajectoryWithFitness = null;
+
+                }
+                // "Interrupted.");
+
+        }
+}
diff --git a/subprojects/store-dse/src/main/java/tools/refinery/store/dse/strategy/DepthFirstStrategy.java b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/strategy/DepthFirstStrategy.java
new file mode 100644
index 00000000..42985013
--- /dev/null
+++ b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/strategy/DepthFirstStrategy.java
@@ -0,0 +1,108 @@
+package tools.refinery.store.dse.strategy;
+
+import tools.refinery.store.dse.DesignSpaceExplorationAdapter;
+import tools.refinery.store.dse.Strategy;
+import tools.refinery.store.dse.internal.Activation;
+import tools.refinery.store.dse.objectives.Fitness;
+
+import java.util.Collection;
+
+public class DepthFirstStrategy implements Strategy {
+
+        private DesignSpaceExplorationAdapter dseAdapter;
+
+        private int maxDepth;
+        private boolean backTrackIfSolution = true;
+
+        public DepthFirstStrategy() {
+                this(-1);
+        }
+
+        public DepthFirstStrategy(int maxDepth) {
+                if (maxDepth < 0) {
+                        this.maxDepth = Integer.MAX_VALUE;
+                } else {
+                        this.maxDepth = maxDepth;
+                }
+        }
+
+        public DepthFirstStrategy continueIfHardObjectivesFulfilled() {
+                backTrackIfSolution = false;
+                return this;
+        }
+
+        @Override
+        public void initStrategy(DesignSpaceExplorationAdapter designSpaceExplorationAdapter) {
+                this.dseAdapter = designSpaceExplorationAdapter;
+        }
+
+        @Override
+        public void explore() {
+                mainloop: while (true) {
+                        var globalConstraintsAreSatisfied = dseAdapter.checkGlobalConstraints();
+                        if (!globalConstraintsAreSatisfied) {
+                                var isSuccessfulUndo = dseAdapter.backtrack();
+                                if (!isSuccessfulUndo) {
+//                                      "Global constraint is not satisfied and cannot backtrack."
+                                        break;
+                                }
+                                else {
+//                                      "Global constraint is not satisfied, backtrack."
+                                        continue;
+                                }
+                        }
+
+                        Fitness fitness = dseAdapter.calculateFitness();
+                        if (fitness.isSatisfiesHardObjectives()) {
+                                dseAdapter.newSolution();
+                                if (backTrackIfSolution) {
+                                        var isSuccessfulUndo = dseAdapter.backtrack();
+                                        if (!isSuccessfulUndo) {
+//                                      "Found a solution but cannot backtrack."
+                                                break;
+                                        } else {
+//                                      "Found a solution, backtrack."
+                                                continue;
+                                        }
+                                }
+                        }
+
+                        var depth = dseAdapter.getDepth();
+                        if (dseAdapter.getDepth() >= maxDepth) {
+                                var isSuccessfulUndo = dseAdapter.backtrack();
+                                if (!isSuccessfulUndo) {
+//                                      "Reached max depth but cannot backtrack."
+                                        break;
+                                }
+                        }
+
+                        Collection<Activation> activations;
+                        do {
+                                activations = dseAdapter.getUntraversedActivations();
+                                if (activations.isEmpty()) {
+                                        if (!dseAdapter.backtrack()) {
+        //                                      "No more transitions from current state and cannot backtrack."
+                                                break mainloop;
+                                        }
+                                        else {
+        //                                      "No more transitions from current state, backtrack."
+                                                continue;
+                                        }
+                                }
+                        } while (activations.isEmpty());
+
+                        dseAdapter.fireRandomActivation();
+//                      if (dseAdapter.isCurrentInTrajectory()) {
+//                              if (!dseAdapter.backtrack()) {
+////                                    TODO: throw exception
+////                                    "The new state is present in the trajectory but cannot backtrack. Should never happen!"
+//                                      break;
+//                              }
+//                              else {
+////                                    "The new state is already visited in the trajectory, backtrack."
+//                                      continue;
+//                              }
+//                      }
+                }
+        }
+}
diff --git a/subprojects/store-dse/src/test/java/tools/refinery/store/dse/CRAExamplesTest.java b/subprojects/store-dse/src/test/java/tools/refinery/store/dse/CRAExamplesTest.java
new file mode 100644
index 00000000..e7cc60d6
--- /dev/null
+++ b/subprojects/store-dse/src/test/java/tools/refinery/store/dse/CRAExamplesTest.java
@@ -0,0 +1,274 @@
+package tools.refinery.store.dse;
+
+import org.junit.jupiter.api.Test;
+import tools.refinery.store.model.ModelStore;
+import tools.refinery.store.query.ModelQueryAdapter;
+import tools.refinery.store.query.dnf.Query;
+import tools.refinery.store.query.dnf.RelationalQuery;
+import tools.refinery.store.dse.internal.TransformationRule;
+import tools.refinery.store.dse.strategy.BestFirstStrategy;
+import tools.refinery.store.dse.strategy.DepthFirstStrategy;
+import tools.refinery.store.query.viatra.ViatraModelQueryAdapter;
+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 tools.refinery.visualization.ModelVisualizerAdapter;
+import tools.refinery.visualization.internal.FileFormat;
+
+import java.util.List;
+
+import static tools.refinery.store.query.literal.Literals.not;
+
+public class CRAExamplesTest {
+        private static final Symbol<String> name = Symbol.of("Name", 1, String.class);
+
+//      private static final Symbol<Boolean> classModel = Symbol.of("ClassModel", 1);
+        private static final Symbol<Boolean> classElement = Symbol.of("ClassElement", 1);
+//      private static final Symbol<Boolean> feature = Symbol.of("Feature", 1);
+        private static final Symbol<Boolean> attribute = Symbol.of("Attribute", 1);
+        private static final Symbol<Boolean> method = Symbol.of("Method", 1);
+
+//      private static final Symbol<Boolean> isEncapsulatedBy = Symbol.of("IsEncapsulatedBy", 2);
+        private static final Symbol<Boolean> encapsulates = Symbol.of("Encapsulates", 2);
+        private static final Symbol<Boolean> dataDependency = Symbol.of("DataDependency", 2);
+        private static final Symbol<Boolean> functionalDependency = Symbol.of("FunctionalDependency", 2);
+
+        private static final Symbol<Boolean> features = Symbol.of("Features", 2);
+        private static final Symbol<Boolean> classes = Symbol.of("Classes", 2);
+
+//      private static final AnySymbolView classModelView = new KeyOnlyView<>(classModel);
+        private static final AnySymbolView classElementView = new KeyOnlyView<>(classElement);
+//      private static final AnySymbolView featureView = new KeyOnlyView<>(feature);
+        private static final AnySymbolView attributeView = new KeyOnlyView<>(attribute);
+        private static final AnySymbolView methodView = new KeyOnlyView<>(method);
+//      private static final AnySymbolView isEncapsulatedByView = new KeyOnlyView<>(isEncapsulatedBy);
+        private static final AnySymbolView encapsulatesView = new KeyOnlyView<>(encapsulates);
+        private static final AnySymbolView dataDependencyView = new KeyOnlyView<>(dataDependency);
+        private static final AnySymbolView functionalDependencyView = new KeyOnlyView<>(functionalDependency);
+        private static final AnySymbolView featuresView = new KeyOnlyView<>(features);
+        private static final AnySymbolView classesView = new KeyOnlyView<>(classes);
+
+        /*Example Transformation rules*/
+        private static final RelationalQuery feature = Query.of("Feature",
+                        (builder, f) -> builder.clause(
+                                attributeView.call(f))
+                        .clause(
+                                methodView.call(f))
+                        );
+
+        private static final RelationalQuery assignFeaturePreconditionHelper = Query.of("AssignFeaturePreconditionHelper",
+                        (builder, c, f) -> builder.clause(
+                                        classElementView.call(c),
+//                                      classesView.call(model, c),
+                                        encapsulatesView.call(c, f)
+                        ));
+
+        private static final RelationalQuery assignFeaturePrecondition = Query.of("AssignFeaturePrecondition",
+                        (builder, f, c1) -> builder.clause((c2) -> List.of(
+//                                      classModelView.call(model),
+                                        feature.call(f),
+                                        classElementView.call(c1),
+//                                      featuresView.call(model, f),
+                                        not(assignFeaturePreconditionHelper.call(c2, f)),
+                                        not(encapsulatesView.call(c1, f))
+                        )));
+
+        private static final RelationalQuery deleteEmptyClassPrecondition = Query.of("DeleteEmptyClassPrecondition",
+                        (builder, c) -> builder.clause((f) -> List.of(
+//                                      classModelView.call(model),
+                                        classElementView.call(c),
+//                                      featuresView.call(model, f),
+                                        not(encapsulatesView.call(c, f))
+                        )));
+
+        private static final RelationalQuery createClassPreconditionHelper = Query.of("CreateClassPreconditionHelper",
+                        (builder, f, c) -> builder.clause(
+                                        classElementView.call(c),
+//                                      classesView.call(model, c),
+                                        encapsulatesView.call(c, f)
+                        ));
+
+        private static final RelationalQuery createClassPrecondition = Query.of("CreateClassPrecondition",
+                        (builder, f) -> builder.clause((c) -> List.of(
+//                                      classModelView.call(model),
+                                        feature.call(f),
+                                        not(createClassPreconditionHelper.call(f, c))
+                        )));
+
+        private static final RelationalQuery moveFeaturePrecondition = Query.of("MoveFeature",
+                        (builder, c1, c2, f) -> builder.clause(
+//                                      classModelView.call(model),
+                                        classElementView.call(c1),
+                                        classElementView.call(c2),
+                                        c1.notEquivalent(c2),
+                                        feature.call(f),
+//                                      classesView.call(model, c1),
+//                                      classesView.call(model, c2),
+//                                      featuresView.call(model, f),
+                                        encapsulatesView.call(c1, f)
+                        ));
+
+        private static final TransformationRule assignFeatureRule = new TransformationRule("AssignFeature",
+                        assignFeaturePrecondition,
+                        (model) -> {
+//                              var isEncapsulatedByInterpretation = model.getInterpretation(isEncapsulatedBy);
+                                var encapsulatesInterpretation = model.getInterpretation(encapsulates);
+                                return ((Tuple activation) -> {
+                                        var feature = activation.get(0);
+                                        var classElement = activation.get(1);
+
+//                                      isEncapsulatedByInterpretation.put(Tuple.of(feature, classElement), true);
+                                        encapsulatesInterpretation.put(Tuple.of(classElement, feature), true);
+                                });
+                        });
+
+        private static final TransformationRule deleteEmptyClassRule = new TransformationRule("DeleteEmptyClass",
+                        deleteEmptyClassPrecondition,
+                        (model) -> {
+//                              var classesInterpretation = model.getInterpretation(classes);
+                                var classElementInterpretation = model.getInterpretation(classElement);
+                                return ((Tuple activation) -> {
+                                        // TODO: can we move dseAdapter outside?
+                                        var dseAdapter = model.getAdapter(DesignSpaceExplorationAdapter.class);
+//                                      var modelElement = activation.get(0);
+                                        var classElement = activation.get(0);
+
+//                                      classesInterpretation.put(Tuple.of(modelElement, classElement), false);
+                                        classElementInterpretation.put(Tuple.of(classElement), false);
+                                        dseAdapter.deleteObject(Tuple.of(classElement));
+                                });
+                        });
+
+        private static final TransformationRule createClassRule = new TransformationRule("CreateClass",
+                        createClassPrecondition,
+                        (model) -> {
+                                var classElementInterpretation = model.getInterpretation(classElement);
+//                              var classesInterpretation = model.getInterpretation(classes);
+                                var encapsulatesInterpretation = model.getInterpretation(encapsulates);
+                                return ((Tuple activation) -> {
+                                        // TODO: can we move dseAdapter outside?
+                                        var dseAdapter = model.getAdapter(DesignSpaceExplorationAdapter.class);
+//                                      var modelElement = activation.get(0);
+                                        var feature = activation.get(0);
+
+                                        var newClassElement = dseAdapter.createObject();
+                                        var newClassElementId = newClassElement.get(0);
+                                        classElementInterpretation.put(newClassElement, true);
+//                                      classesInterpretation.put(Tuple.of(modelElement, newClassElementId), true);
+                                        encapsulatesInterpretation.put(Tuple.of(newClassElementId, feature), true);
+                                });
+                        });
+
+        private static final TransformationRule moveFeatureRule = new TransformationRule("MoveFeature",
+                        moveFeaturePrecondition,
+                        (model) -> {
+                                var encapsulatesInterpretation = model.getInterpretation(encapsulates);
+                                return ((Tuple activation) -> {
+                                        var classElement1 = activation.get(0);
+                                        var classElement2 = activation.get(1);
+                                        var feature = activation.get(2);
+
+                                        encapsulatesInterpretation.put(Tuple.of(classElement1, feature), false);
+                                        encapsulatesInterpretation.put(Tuple.of(classElement2, feature), true);
+                                });
+                        });
+
+        @Test
+        void craTest() {
+                var store = ModelStore.builder()
+                                .symbols(classElement, encapsulates, classes, features, attribute, method, dataDependency,
+                                                functionalDependency, name)
+                                .with(ViatraModelQueryAdapter.builder()
+                                                .queries(feature, assignFeaturePreconditionHelper, assignFeaturePrecondition,
+                                                                deleteEmptyClassPrecondition, createClassPreconditionHelper, createClassPrecondition,
+                                                                moveFeaturePrecondition))
+                                .with(ModelVisualizerAdapter.builder())
+                                .with(DesignSpaceExplorationAdapter.builder()
+                                                .transformations(assignFeatureRule, deleteEmptyClassRule, createClassRule, moveFeatureRule)
+//                                              .strategy(new DepthFirstStrategy(3).continueIfHardObjectivesFulfilled()
+                                                .strategy(new BestFirstStrategy(6).continueIfHardObjectivesFulfilled()
+//                                                              .goOnOnlyIfFitnessIsBetter()
+                                                ))
+                                .build();
+
+                var model = store.createEmptyModel();
+                var dseAdapter = model.getAdapter(DesignSpaceExplorationAdapter.class);
+//              dseAdapter.setRandom(1);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+
+//              var modelInterpretation = model.getInterpretation(classModel);
+                var nameInterpretation = model.getInterpretation(name);
+                var methodInterpretation = model.getInterpretation(method);
+                var attributeInterpretation = model.getInterpretation(attribute);
+                var dataDependencyInterpretation = model.getInterpretation(dataDependency);
+                var functionalDependencyInterpretation = model.getInterpretation(functionalDependency);
+
+//              var modelElement = dseAdapter.createObject();
+                var method1 = dseAdapter.createObject();
+                var method1Id = method1.get(0);
+                var method2 = dseAdapter.createObject();
+                var method2Id = method2.get(0);
+                var method3 = dseAdapter.createObject();
+                var method3Id = method3.get(0);
+                var method4 = dseAdapter.createObject();
+                var method4Id = method4.get(0);
+                var attribute1 = dseAdapter.createObject();
+                var attribute1Id = attribute1.get(0);
+                var attribute2 = dseAdapter.createObject();
+                var attribute2Id = attribute2.get(0);
+                var attribute3 = dseAdapter.createObject();
+                var attribute3Id = attribute3.get(0);
+                var attribute4 = dseAdapter.createObject();
+                var attribute4Id = attribute4.get(0);
+                var attribute5 = dseAdapter.createObject();
+                var attribute5Id = attribute5.get(0);
+
+                nameInterpretation.put(method1, "M1");
+                nameInterpretation.put(method2, "M2");
+                nameInterpretation.put(method3, "M3");
+                nameInterpretation.put(method4, "M4");
+                nameInterpretation.put(attribute1, "A1");
+                nameInterpretation.put(attribute2, "A2");
+                nameInterpretation.put(attribute3, "A3");
+                nameInterpretation.put(attribute4, "A4");
+                nameInterpretation.put(attribute5, "A5");
+
+
+
+//              modelInterpretation.put(modelElement, true);
+                methodInterpretation.put(method1, true);
+                methodInterpretation.put(method2, true);
+                methodInterpretation.put(method3, true);
+                methodInterpretation.put(method4, true);
+                attributeInterpretation.put(attribute1, true);
+                attributeInterpretation.put(attribute2, true);
+                attributeInterpretation.put(attribute3, true);
+                attributeInterpretation.put(attribute4, true);
+                attributeInterpretation.put(attribute5, true);
+
+                dataDependencyInterpretation.put(Tuple.of(method1Id, attribute1Id), true);
+                dataDependencyInterpretation.put(Tuple.of(method1Id, attribute3Id), true);
+                dataDependencyInterpretation.put(Tuple.of(method2Id, attribute2Id), true);
+                dataDependencyInterpretation.put(Tuple.of(method3Id, attribute3Id), true);
+                dataDependencyInterpretation.put(Tuple.of(method3Id, attribute4Id), true);
+                dataDependencyInterpretation.put(Tuple.of(method4Id, attribute3Id), true);
+                dataDependencyInterpretation.put(Tuple.of(method4Id, attribute5Id), true);
+
+                functionalDependencyInterpretation.put(Tuple.of(method1Id, attribute3Id), true);
+                functionalDependencyInterpretation.put(Tuple.of(method1Id, attribute4Id), true);
+                functionalDependencyInterpretation.put(Tuple.of(method2Id, attribute1Id), true);
+                functionalDependencyInterpretation.put(Tuple.of(method3Id, attribute1Id), true);
+                functionalDependencyInterpretation.put(Tuple.of(method3Id, attribute4Id), true);
+                functionalDependencyInterpretation.put(Tuple.of(method4Id, attribute2Id), true);
+
+                queryEngine.flushChanges();
+
+                var states = dseAdapter.explore();
+                System.out.println("states size: " + states.size());
+                System.out.println("states: " + states);
+                var visualizer = model.getAdapter(ModelVisualizerAdapter.class);
+                visualizer.renderDesignSpace("test_output", FileFormat.SVG);
+        }
+
+}
diff --git a/subprojects/store-dse/src/test/java/tools/refinery/store/dse/DebugTest.java b/subprojects/store-dse/src/test/java/tools/refinery/store/dse/DebugTest.java
new file mode 100644
index 00000000..911c0661
--- /dev/null
+++ b/subprojects/store-dse/src/test/java/tools/refinery/store/dse/DebugTest.java
@@ -0,0 +1,117 @@
+package tools.refinery.store.dse;
+
+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.dse.internal.TransformationRule;
+import tools.refinery.store.dse.strategy.BestFirstStrategy;
+import tools.refinery.store.dse.strategy.DepthFirstStrategy;
+import tools.refinery.store.query.viatra.ViatraModelQueryAdapter;
+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 tools.refinery.visualization.ModelVisualizerAdapter;
+import tools.refinery.visualization.internal.FileFormat;
+
+public class DebugTest {
+        private static final Symbol<Boolean> classModel = Symbol.of("ClassModel", 1);
+        private static final Symbol<Boolean> classElement = Symbol.of("ClassElement", 1);
+        private static final Symbol<Boolean> feature = Symbol.of("Feature", 1);
+
+        private static final Symbol<Boolean> isEncapsulatedBy = Symbol.of("IsEncapsulatedBy", 2);
+        private static final Symbol<Boolean> encapsulates = Symbol.of("Encapsulates", 2);
+
+        private static final Symbol<Boolean> features = Symbol.of("Features", 2);
+        private static final Symbol<Boolean> classes = Symbol.of("Classes", 2);
+
+        private static final AnySymbolView classModelView = new KeyOnlyView<>(classModel);
+        private static final AnySymbolView classElementView = new KeyOnlyView<>(classElement);
+        private static final AnySymbolView featureView = new KeyOnlyView<>(feature);
+        private static final AnySymbolView isEncapsulatedByView = new KeyOnlyView<>(isEncapsulatedBy);
+        private static final AnySymbolView encapsulatesView = new KeyOnlyView<>(encapsulates);
+        private static final AnySymbolView featuresView = new KeyOnlyView<>(features);
+        private static final AnySymbolView classesView = new KeyOnlyView<>(classes);
+
+
+        @Test
+        void BFSTest() {
+                var createClassPrecondition = Query.of("CreateClassPrecondition",
+                                (builder, model) -> builder.clause(
+                                                classModelView.call(model)
+                                ));
+
+                var createClassRule = new TransformationRule("CreateClass",
+                                createClassPrecondition,
+                                (model) -> {
+                                        var classesInterpretation = model.getInterpretation(classes);
+                                        var classElementInterpretation = model.getInterpretation(classElement);
+                                        return ((Tuple activation) -> {
+                                                var dseAdapter = model.getAdapter(DesignSpaceExplorationAdapter.class);
+                                                var modelElement = activation.get(0);
+
+                                                var newClassElement = dseAdapter.createObject();
+                                                var newClassElementId = newClassElement.get(0);
+
+                                                classesInterpretation.put(Tuple.of(modelElement, newClassElementId), true);
+                                                classElementInterpretation.put(Tuple.of(newClassElementId), true);
+                                        });
+                                });
+
+                var createFeaturePrecondition = Query.of("CreateFeaturePrecondition",
+                                (builder, model) -> builder.clause(
+                                                classModelView.call(model)
+                                ));
+
+                var createFeatureRule = new TransformationRule("CreateFeature",
+                                createFeaturePrecondition,
+                                (model) -> {
+                                        var featuresInterpretation = model.getInterpretation(features);
+                                        var featureInterpretation = model.getInterpretation(feature);
+                                        return ((Tuple activation) -> {
+                                                var dseAdapter = model.getAdapter(DesignSpaceExplorationAdapter.class);
+                                                var modelElement = activation.get(0);
+
+                                                var newClassElement = dseAdapter.createObject();
+                                                var newClassElementId = newClassElement.get(0);
+
+                                                featuresInterpretation.put(Tuple.of(modelElement, newClassElementId), true);
+                                                featureInterpretation.put(Tuple.of(newClassElementId), true);
+                                        });
+                                });
+
+                var store = ModelStore.builder()
+                                .symbols(classModel, classElement, feature, isEncapsulatedBy, encapsulates, classes, features)
+                                .with(ViatraModelQueryAdapter.builder()
+                                                .queries(createClassPrecondition, createFeaturePrecondition))
+                                .with(ModelVisualizerAdapter.builder())
+                                .with(DesignSpaceExplorationAdapter.builder()
+                                                .transformations(createClassRule, createFeatureRule)
+                                                .strategy(new DepthFirstStrategy(4).continueIfHardObjectivesFulfilled()
+//                                              .strategy(new BestFirstStrategy(4).continueIfHardObjectivesFulfilled()
+//                                                              .goOnOnlyIfFitnessIsBetter()
+                                                ))
+                                .build();
+
+                var model = store.createEmptyModel();
+                var dseAdapter = model.getAdapter(DesignSpaceExplorationAdapter.class);
+//              dseAdapter.setRandom(1);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+
+                var modelElementInterpretation = model.getInterpretation(classModel);
+                var classElementInterpretation = model.getInterpretation(classElement);
+                var modelElement = dseAdapter.createObject();
+                modelElementInterpretation.put(modelElement, true);
+                classElementInterpretation.put(modelElement, true);
+                queryEngine.flushChanges();
+
+
+                var states = dseAdapter.explore();
+                var visualizer = model.getAdapter(ModelVisualizerAdapter.class);
+                visualizer.renderDesignSpace("test_output", FileFormat.SVG);
+                System.out.println("states size: " + states.size());
+                System.out.println("states: " + states);
+
+        }
+}
diff --git a/subprojects/store-dse/src/test/java/tools/refinery/store/dse/DesignSpaceExplorationTest.java b/subprojects/store-dse/src/test/java/tools/refinery/store/dse/DesignSpaceExplorationTest.java
new file mode 100644
index 00000000..c454f4ec
--- /dev/null
+++ b/subprojects/store-dse/src/test/java/tools/refinery/store/dse/DesignSpaceExplorationTest.java
@@ -0,0 +1,487 @@
+package tools.refinery.store.dse;
+
+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.dse.internal.TransformationRule;
+import tools.refinery.store.dse.strategy.BestFirstStrategy;
+import tools.refinery.store.dse.strategy.DepthFirstStrategy;
+import tools.refinery.store.query.viatra.ViatraModelQueryAdapter;
+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 tools.refinery.visualization.ModelVisualizerAdapter;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+
+public class DesignSpaceExplorationTest {
+//      private static final Symbol<Boolean> namedElement = Symbol.of("NamedElement", 1);
+//      private static final Symbol<Boolean> attribute = Symbol.of("Attribute", 1);
+//      private static final Symbol<Boolean> method = Symbol.of("Method", 1);
+//      private static final Symbol<Boolean> dataDependency = Symbol.of("DataDependency", 2);
+//      private static final Symbol<Boolean> functionalDependency = Symbol.of("FunctionalDependency", 2);
+
+        private static final Symbol<Boolean> classModel = Symbol.of("ClassModel", 1);
+        private static final Symbol<Boolean> classElement = Symbol.of("ClassElement", 1);
+        private static final Symbol<Boolean> feature = Symbol.of("Feature", 1);
+
+        private static final Symbol<Boolean> isEncapsulatedBy = Symbol.of("IsEncapsulatedBy", 2);
+        private static final Symbol<Boolean> encapsulates = Symbol.of("Encapsulates", 2);
+
+        private static final Symbol<Boolean> features = Symbol.of("Features", 2);
+        private static final Symbol<Boolean> classes = Symbol.of("Classes", 2);
+
+        private static final AnySymbolView classModelView = new KeyOnlyView<>(classModel);
+        private static final AnySymbolView classElementView = new KeyOnlyView<>(classElement);
+        private static final AnySymbolView featureView = new KeyOnlyView<>(feature);
+        private static final AnySymbolView isEncapsulatedByView = new KeyOnlyView<>(isEncapsulatedBy);
+        private static final AnySymbolView encapsulatesView = new KeyOnlyView<>(encapsulates);
+        private static final AnySymbolView featuresView = new KeyOnlyView<>(features);
+        private static final AnySymbolView classesView = new KeyOnlyView<>(classes);
+
+        @Test
+        void createObjectTest() {
+                var store = ModelStore.builder()
+                                .with(ViatraModelQueryAdapter.builder())
+                                .with(DesignSpaceExplorationAdapter.builder())
+                                .build();
+
+                var model = store.createEmptyModel();
+                var dseAdapter = model.getAdapter(DesignSpaceExplorationAdapter.class);
+
+                assertEquals(0, dseAdapter.getModelSize());
+
+                var newModel = dseAdapter.createObject();
+                var newModelId = newModel.get(0);
+                var newClass1 = dseAdapter.createObject();
+                var newClass1Id = newClass1.get(0);
+                var newClass2 = dseAdapter.createObject();
+                var newClass2Id = newClass2.get(0);
+                var newField = dseAdapter.createObject();
+                var newFieldId = newField.get(0);
+
+                assertEquals(0, newModelId);
+                assertEquals(1, newClass1Id);
+                assertEquals(2, newClass2Id);
+                assertEquals(3, newFieldId);
+                assertEquals(4, dseAdapter.getModelSize());
+        }
+
+        @Test
+        void deleteMiddleObjectTest() {
+                var store = ModelStore.builder()
+                                .with(ViatraModelQueryAdapter.builder())
+                                .with(DesignSpaceExplorationAdapter.builder())
+                                .build();
+
+                var model = store.createEmptyModel();
+                var dseAdapter = model.getAdapter(DesignSpaceExplorationAdapter.class);
+
+                assertEquals(0, dseAdapter.getModelSize());
+
+                var newObject0 = dseAdapter.createObject();
+                var newObject0Id = newObject0.get(0);
+                var newObject1 = dseAdapter.createObject();
+                var newObject1Id = newObject1.get(0);
+                var newObject2 = dseAdapter.createObject();
+                var newObject2Id = newObject2.get(0);
+                var newObject3 = dseAdapter.createObject();
+                var newObject3Id = newObject3.get(0);
+
+                assertEquals(0, newObject0Id);
+                assertEquals(1, newObject1Id);
+                assertEquals(2, newObject2Id);
+                assertEquals(3, newObject3Id);
+                assertEquals(4, dseAdapter.getModelSize());
+
+                dseAdapter.deleteObject(newObject1);
+                assertEquals(4, dseAdapter.getModelSize());
+
+                var newObject4 = dseAdapter.createObject();
+                var newObject4Id = newObject4.get(0);
+                assertEquals(4, newObject4Id);
+                assertEquals(5, dseAdapter.getModelSize());
+
+                dseAdapter.deleteObject(newObject4);
+                assertEquals(5, dseAdapter.getModelSize());
+        }
+
+        @Test
+        void DFSTrivialTest() {
+                var store = ModelStore.builder()
+                                .symbols(classModel)
+                                .with(ViatraModelQueryAdapter.builder())
+                                .with(ModelVisualizerAdapter.builder())
+                                .with(DesignSpaceExplorationAdapter.builder()
+                                                .strategy(new DepthFirstStrategy(0)))
+                                .build();
+
+                var model = store.createEmptyModel();
+                var dseAdapter = model.getAdapter(DesignSpaceExplorationAdapter.class);
+
+                var states = dseAdapter.explore();
+                assertEquals(1, states.size());
+                assertEquals(0, states.iterator().next());
+        }
+
+        @Test
+        void DFSOneRuleTest() {
+                var createClassPrecondition = Query.of("CreateClassPrecondition",
+                                (builder, model) -> builder.clause(
+                                                classModelView.call(model)
+                                ));
+
+                var createClassRule = new TransformationRule("CreateClass",
+                                createClassPrecondition,
+                                (model) -> {
+                                        var classesInterpretation = model.getInterpretation(classes);
+                                        var classElementInterpretation = model.getInterpretation(classElement);
+                                        return ((Tuple activation) -> {
+                                                var dseAdapter = model.getAdapter(DesignSpaceExplorationAdapter.class);
+                                                var modelElement = activation.get(0);
+
+                                                var newClassElement = dseAdapter.createObject();
+                                                var newClassElementId = newClassElement.get(0);
+
+                                                classesInterpretation.put(Tuple.of(modelElement, newClassElementId), true);
+                                                classElementInterpretation.put(Tuple.of(newClassElementId), true);
+                                        });
+                                });
+
+                var store = ModelStore.builder()
+                                .symbols(classModel, classElement, classes)
+                                .with(ViatraModelQueryAdapter.builder()
+                                                .queries(createClassPrecondition))
+                                .with(ModelVisualizerAdapter.builder())
+                                .with(DesignSpaceExplorationAdapter.builder()
+                                                .transformations(createClassRule)
+                                                .strategy(new DepthFirstStrategy(4)
+                                                ))
+                                .build();
+
+                var model = store.createEmptyModel();
+                var dseAdapter = model.getAdapter(DesignSpaceExplorationAdapter.class);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+
+                var modelElementInterpretation = model.getInterpretation(classModel);
+                modelElementInterpretation.put(dseAdapter.createObject(), true);
+                queryEngine.flushChanges();
+
+                var states = dseAdapter.explore();
+                assertEquals(1, states.size());
+                assertEquals(0, states.iterator().next());
+        }
+
+        @Test
+        void DFSContinueTest() {
+                var createClassPrecondition = Query.of("CreateClassPrecondition",
+                                (builder, model) -> builder.clause(
+                                                classModelView.call(model)
+                                ));
+
+                var createClassRule = new TransformationRule("CreateClass",
+                                createClassPrecondition,
+                                (model) -> {
+                                        var classesInterpretation = model.getInterpretation(classes);
+                                        var classElementInterpretation = model.getInterpretation(classElement);
+                                        return ((Tuple activation) -> {
+                                                var dseAdapter = model.getAdapter(DesignSpaceExplorationAdapter.class);
+                                                var modelElement = activation.get(0);
+
+                                                var newClassElement = dseAdapter.createObject();
+                                                var newClassElementId = newClassElement.get(0);
+
+                                                classesInterpretation.put(Tuple.of(modelElement, newClassElementId), true);
+                                                classElementInterpretation.put(Tuple.of(newClassElementId), true);
+                                        });
+                                });
+
+                var store = ModelStore.builder()
+                                .symbols(classModel, classElement, classes)
+                                .with(ViatraModelQueryAdapter.builder()
+                                                .queries(createClassPrecondition))
+                                .with(ModelVisualizerAdapter.builder())
+                                .with(DesignSpaceExplorationAdapter.builder()
+                                                .transformations(createClassRule)
+                                                .strategy(new DepthFirstStrategy(4).continueIfHardObjectivesFulfilled()
+                                                ))
+                                .build();
+
+                var model = store.createEmptyModel();
+                var dseAdapter = model.getAdapter(DesignSpaceExplorationAdapter.class);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+
+                var modelElementInterpretation = model.getInterpretation(classModel);
+                modelElementInterpretation.put(dseAdapter.createObject(), true);
+                queryEngine.flushChanges();
+
+                var states = dseAdapter.explore();
+                var iterator = states.iterator();
+                assertEquals(5, states.size());
+                assertEquals(0, iterator.next());
+                assertEquals(1, iterator.next());
+                assertEquals(2, iterator.next());
+                assertEquals(3, iterator.next());
+                assertEquals(4, iterator.next());
+        }
+
+        @Test
+        void DFSCompletenessTest() {
+                var createClassPrecondition = Query.of("CreateClassPrecondition",
+                                (builder, model) -> builder.clause(
+                                                classModelView.call(model)
+                                ));
+
+                var createClassRule = new TransformationRule("CreateClass",
+                                createClassPrecondition,
+                                (model) -> {
+                                        var classesInterpretation = model.getInterpretation(classes);
+                                        var classElementInterpretation = model.getInterpretation(classElement);
+                                        return ((Tuple activation) -> {
+                                                var dseAdapter = model.getAdapter(DesignSpaceExplorationAdapter.class);
+                                                var modelElement = activation.get(0);
+
+                                                var newClassElement = dseAdapter.createObject();
+                                                var newClassElementId = newClassElement.get(0);
+
+                                                classesInterpretation.put(Tuple.of(modelElement, newClassElementId), true);
+                                                classElementInterpretation.put(Tuple.of(newClassElementId), true);
+                                        });
+                                });
+
+                var createFeaturePrecondition = Query.of("CreateFeaturePrecondition",
+                                (builder, model) -> builder.clause(
+                                                classModelView.call(model)
+                                ));
+
+                var createFeatureRule = new TransformationRule("CreateFeature",
+                                createFeaturePrecondition,
+                                (model) -> {
+                                        var featuresInterpretation = model.getInterpretation(features);
+                                        var featureInterpretation = model.getInterpretation(feature);
+                                        return ((Tuple activation) -> {
+                                                var dseAdapter = model.getAdapter(DesignSpaceExplorationAdapter.class);
+                                                var modelElement = activation.get(0);
+
+                                                var newClassElement = dseAdapter.createObject();
+                                                var newClassElementId = newClassElement.get(0);
+
+                                                featuresInterpretation.put(Tuple.of(modelElement, newClassElementId), true);
+                                                featureInterpretation.put(Tuple.of(newClassElementId), true);
+                                        });
+                                });
+
+                var store = ModelStore.builder()
+                                .symbols(classModel, classElement, classes, feature, features, isEncapsulatedBy, encapsulates)
+                                .with(ViatraModelQueryAdapter.builder()
+                                                .queries(createClassPrecondition, createFeaturePrecondition))
+                                .with(ModelVisualizerAdapter.builder())
+                                .with(DesignSpaceExplorationAdapter.builder()
+                                                .transformations(createClassRule, createFeatureRule)
+                                                .strategy(new DepthFirstStrategy(10).continueIfHardObjectivesFulfilled()
+                                                ))
+                                .build();
+
+                var model = store.createEmptyModel();
+                var dseAdapter = model.getAdapter(DesignSpaceExplorationAdapter.class);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+
+                var modelElementInterpretation = model.getInterpretation(classModel);
+                modelElementInterpretation.put(dseAdapter.createObject(), true);
+                queryEngine.flushChanges();
+
+                var states = dseAdapter.explore();
+                assertEquals(2047, states.size());
+        }
+
+        @Test
+        void BFSTrivialTest() {
+                var store = ModelStore.builder()
+                                .symbols(classModel)
+                                .with(ViatraModelQueryAdapter.builder())
+                                .with(ModelVisualizerAdapter.builder())
+                                .with(DesignSpaceExplorationAdapter.builder()
+                                                .strategy(new BestFirstStrategy(0)))
+                                .build();
+
+                var model = store.createEmptyModel();
+                var dseAdapter = model.getAdapter(DesignSpaceExplorationAdapter.class);
+
+                var states = dseAdapter.explore();
+                assertEquals(1, states.size());
+                assertEquals(0, states.iterator().next());
+        }
+
+        @Test
+        void BFSOneRuleTest() {
+                var createClassPrecondition = Query.of("CreateClassPrecondition",
+                                (builder, model) -> builder.clause(
+                                                classModelView.call(model)
+                                ));
+
+                var createClassRule = new TransformationRule("CreateClass",
+                                createClassPrecondition,
+                                (model) -> {
+                                        var classesInterpretation = model.getInterpretation(classes);
+                                        var classElementInterpretation = model.getInterpretation(classElement);
+                                        return ((Tuple activation) -> {
+                                                var dseAdapter = model.getAdapter(DesignSpaceExplorationAdapter.class);
+                                                var modelElement = activation.get(0);
+
+                                                var newClassElement = dseAdapter.createObject();
+                                                var newClassElementId = newClassElement.get(0);
+
+                                                classesInterpretation.put(Tuple.of(modelElement, newClassElementId), true);
+                                                classElementInterpretation.put(Tuple.of(newClassElementId), true);
+                                        });
+                                });
+
+                var store = ModelStore.builder()
+                                .symbols(classModel, classElement, classes)
+                                .with(ViatraModelQueryAdapter.builder()
+                                                .queries(createClassPrecondition))
+                                .with(ModelVisualizerAdapter.builder())
+                                .with(DesignSpaceExplorationAdapter.builder()
+                                                .transformations(createClassRule)
+                                                .strategy(new BestFirstStrategy(4)
+                                                ))
+                                .build();
+
+                var model = store.createEmptyModel();
+                var dseAdapter = model.getAdapter(DesignSpaceExplorationAdapter.class);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+
+                var modelElementInterpretation = model.getInterpretation(classModel);
+                modelElementInterpretation.put(dseAdapter.createObject(), true);
+                queryEngine.flushChanges();
+
+                var states = dseAdapter.explore();
+                assertEquals(1, states.size());
+                assertEquals(0, states.iterator().next());
+        }
+
+        @Test
+        void BFSContinueTest() {
+                var createClassPrecondition = Query.of("CreateClassPrecondition",
+                                (builder, model) -> builder.clause(
+                                                classModelView.call(model)
+                                ));
+
+                var createClassRule = new TransformationRule("CreateClass",
+                                createClassPrecondition,
+                                (model) -> {
+                                        var classesInterpretation = model.getInterpretation(classes);
+                                        var classElementInterpretation = model.getInterpretation(classElement);
+                                        return ((Tuple activation) -> {
+                                                var dseAdapter = model.getAdapter(DesignSpaceExplorationAdapter.class);
+                                                var modelElement = activation.get(0);
+
+                                                var newClassElement = dseAdapter.createObject();
+                                                var newClassElementId = newClassElement.get(0);
+
+                                                classesInterpretation.put(Tuple.of(modelElement, newClassElementId), true);
+                                                classElementInterpretation.put(Tuple.of(newClassElementId), true);
+                                        });
+                                });
+
+                var store = ModelStore.builder()
+                                .symbols(classModel, classElement, classes)
+                                .with(ViatraModelQueryAdapter.builder()
+                                                .queries(createClassPrecondition))
+                                .with(ModelVisualizerAdapter.builder())
+                                .with(DesignSpaceExplorationAdapter.builder()
+                                                .transformations(createClassRule)
+                                                .strategy(new BestFirstStrategy(4).continueIfHardObjectivesFulfilled()
+                                                ))
+                                .build();
+
+                var model = store.createEmptyModel();
+                var dseAdapter = model.getAdapter(DesignSpaceExplorationAdapter.class);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+
+                var modelElementInterpretation = model.getInterpretation(classModel);
+                modelElementInterpretation.put(dseAdapter.createObject(), true);
+                queryEngine.flushChanges();
+
+                var states = dseAdapter.explore();
+                var iterator = states.iterator();
+                assertEquals(5, states.size());
+                assertEquals(0, iterator.next());
+                assertEquals(1, iterator.next());
+                assertEquals(2, iterator.next());
+                assertEquals(3, iterator.next());
+                assertEquals(4, iterator.next());
+        }
+
+        @Test
+        void BFSCompletenessTest() {
+                var createClassPrecondition = Query.of("CreateClassPrecondition",
+                                (builder, model) -> builder.clause(
+                                                classModelView.call(model)
+                                ));
+
+                var createClassRule = new TransformationRule("CreateClass",
+                                createClassPrecondition,
+                                (model) -> {
+                                        var classesInterpretation = model.getInterpretation(classes);
+                                        var classElementInterpretation = model.getInterpretation(classElement);
+                                        return ((Tuple activation) -> {
+                                                var dseAdapter = model.getAdapter(DesignSpaceExplorationAdapter.class);
+                                                var modelElement = activation.get(0);
+
+                                                var newClassElement = dseAdapter.createObject();
+                                                var newClassElementId = newClassElement.get(0);
+
+                                                classesInterpretation.put(Tuple.of(modelElement, newClassElementId), true);
+                                                classElementInterpretation.put(Tuple.of(newClassElementId), true);
+                                        });
+                                });
+
+                var createFeaturePrecondition = Query.of("CreateFeaturePrecondition",
+                                (builder, model) -> builder.clause(
+                                                classModelView.call(model)
+                                ));
+
+                var createFeatureRule = new TransformationRule("CreateFeature",
+                                createFeaturePrecondition,
+                                (model) -> {
+                                        var featuresInterpretation = model.getInterpretation(features);
+                                        var featureInterpretation = model.getInterpretation(feature);
+                                        return ((Tuple activation) -> {
+                                                var dseAdapter = model.getAdapter(DesignSpaceExplorationAdapter.class);
+                                                var modelElement = activation.get(0);
+
+                                                var newClassElement = dseAdapter.createObject();
+                                                var newClassElementId = newClassElement.get(0);
+
+                                                featuresInterpretation.put(Tuple.of(modelElement, newClassElementId), true);
+                                                featureInterpretation.put(Tuple.of(newClassElementId), true);
+                                        });
+                                });
+
+                var store = ModelStore.builder()
+                                .symbols(classModel, classElement, classes, feature, features, isEncapsulatedBy, encapsulates)
+                                .with(ViatraModelQueryAdapter.builder()
+                                                .queries(createClassPrecondition, createFeaturePrecondition))
+                                .with(ModelVisualizerAdapter.builder())
+                                .with(DesignSpaceExplorationAdapter.builder()
+                                                .transformations(createClassRule, createFeatureRule)
+                                                .strategy(new BestFirstStrategy(10).continueIfHardObjectivesFulfilled()
+                                                ))
+                                .build();
+
+                var model = store.createEmptyModel();
+                var dseAdapter = model.getAdapter(DesignSpaceExplorationAdapter.class);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+
+                var modelElementInterpretation = model.getInterpretation(classModel);
+                modelElementInterpretation.put(dseAdapter.createObject(), true);
+                queryEngine.flushChanges();
+
+                var states = dseAdapter.explore();
+                assertEquals(2047, states.size());
+        }
+
+}
diff --git a/subprojects/store-dse/src/test/java/tools/refinery/store/dse/TransformationRuleTest.java b/subprojects/store-dse/src/test/java/tools/refinery/store/dse/TransformationRuleTest.java
new file mode 100644
index 00000000..a32d392b
--- /dev/null
+++ b/subprojects/store-dse/src/test/java/tools/refinery/store/dse/TransformationRuleTest.java
@@ -0,0 +1,403 @@
+package tools.refinery.store.dse;
+
+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.dse.internal.TransformationRule;
+import tools.refinery.store.query.viatra.ViatraModelQueryAdapter;
+import tools.refinery.store.query.view.AnySymbolView;
+import tools.refinery.store.query.view.KeyOnlyView;
+import tools.refinery.store.representation.Symbol;
+import tools.refinery.store.tuple.Tuple;
+
+import java.util.List;
+import java.util.Map;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+import static tools.refinery.store.query.literal.Literals.not;
+import static tools.refinery.store.dse.tests.QueryAssertions.assertResults;
+
+public class TransformationRuleTest {
+
+        private static final Symbol<Boolean> classModel = Symbol.of("ClassModel", 1);
+        private static final Symbol<Boolean> classElement = Symbol.of("ClassElement", 1);
+        private static final Symbol<Boolean> feature = Symbol.of("Feature", 1);
+
+        private static final Symbol<Boolean> isEncapsulatedBy = Symbol.of("IsEncapsulatedBy", 2);
+        private static final Symbol<Boolean> encapsulates = Symbol.of("Encapsulates", 2);
+
+        private static final Symbol<Boolean> features = Symbol.of("Features", 2);
+        private static final Symbol<Boolean> classes = Symbol.of("Classes", 2);
+
+        private static final AnySymbolView classModelView = new KeyOnlyView<>(classModel);
+        private static final AnySymbolView classElementView = new KeyOnlyView<>(classElement);
+        private static final AnySymbolView featureView = new KeyOnlyView<>(feature);
+        private static final AnySymbolView isEncapsulatedByView = new KeyOnlyView<>(isEncapsulatedBy);
+        private static final AnySymbolView encapsulatesView = new KeyOnlyView<>(encapsulates);
+        private static final AnySymbolView featuresView = new KeyOnlyView<>(features);
+        private static final AnySymbolView classesView = new KeyOnlyView<>(classes);
+
+        @Test
+        void activationsTest() {
+                var assignFeaturePreconditionHelper = Query.of("AssignFeaturePreconditionHelper",
+                                (builder, model, c, f) -> builder.clause(
+                                                classElementView.call(c),
+                                                classesView.call(model, c),
+                                                encapsulatesView.call(c, f)
+                                ));
+
+                var assignFeaturePrecondition = Query.of("AssignFeaturePrecondition", (builder, c2, f)
+                                -> builder.clause((model, c1) -> List.of(
+                                classModelView.call(model),
+                                featureView.call(f),
+                                classElementView.call(c2),
+                                featuresView.call(model, f),
+                                classesView.call(model, c1),
+                                not(assignFeaturePreconditionHelper.call(model, c2, f)),
+                                not(encapsulatesView.call(c2, f))
+                )));
+
+                var deleteEmptyClassPrecondition = Query.of("DeleteEmptyClassPrecondition",
+                                (builder, model, c) -> builder.clause((f) -> List.of(
+                                                classModelView.call(model),
+                                                classElementView.call(c),
+                                                featuresView.call(model, f),
+                                                not(encapsulatesView.call(c, f))
+                                )));
+
+                TransformationRule assignFeatureRule = new TransformationRule("AssignFeature",
+                                assignFeaturePrecondition,
+                                (model) -> {
+                                        var isEncapsulatedByInterpretation = model.getInterpretation(isEncapsulatedBy);
+                                        return ((Tuple activation) -> {
+                                                var feature = activation.get(0);
+                                                var classElement = activation.get(1);
+
+                                                isEncapsulatedByInterpretation.put(Tuple.of(feature, classElement), true);
+                                        });
+                                });
+
+                TransformationRule deleteEmptyClassRule = new TransformationRule("DeleteEmptyClass",
+                                deleteEmptyClassPrecondition,
+                                (model) -> {
+                                        var classesInterpretation = model.getInterpretation(classes);
+                                        var classElementInterpretation = model.getInterpretation(classElement);
+                                        return ((Tuple activation) -> {
+                                                var modelElement = activation.get(0);
+                                                var classElement = activation.get(1);
+
+                                                classesInterpretation.put(Tuple.of(modelElement, classElement), false);
+                                                classElementInterpretation.put(Tuple.of(classElement), false);
+                                        });
+                                });
+
+
+                var store = ModelStore.builder()
+                                .symbols(classModel, classElement, feature, isEncapsulatedBy, encapsulates, classes, features)
+                                .with(ViatraModelQueryAdapter.builder()
+                                                .queries(assignFeaturePrecondition, assignFeaturePreconditionHelper,
+                                                                deleteEmptyClassPrecondition))
+                                .with(DesignSpaceExplorationAdapter.builder())
+                                .build();
+
+                var model = store.createEmptyModel();
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                assignFeatureRule.prepare(model, queryEngine);
+                deleteEmptyClassRule.prepare(model, queryEngine);
+
+                var classModelInterpretation = model.getInterpretation(classModel);
+                var classElementInterpretation = model.getInterpretation(classElement);
+                var featureInterpretation = model.getInterpretation(feature);
+                var featuresInterpretation = model.getInterpretation(features);
+                var classesInterpretation = model.getInterpretation(classes);
+
+                var dseAdapter = model.getAdapter(DesignSpaceExplorationAdapter.class);
+                var newModel = dseAdapter.createObject();
+                var newModelId = newModel.get(0);
+                var newClass1 = dseAdapter.createObject();
+                var newClass1Id = newClass1.get(0);
+                var newClass2 = dseAdapter.createObject();
+                var newClass2Id = newClass2.get(0);
+                var newField = dseAdapter.createObject();
+                var newFieldId = newField.get(0);
+
+                classModelInterpretation.put(newModel, true);
+                classElementInterpretation.put(newClass1, true);
+                classElementInterpretation.put(newClass2, true);
+                featureInterpretation.put(newField, true);
+                classesInterpretation.put(Tuple.of(newModelId, newClass1Id), true);
+                classesInterpretation.put(Tuple.of(newModelId, newClass2Id), true);
+                featuresInterpretation.put(Tuple.of(newModelId, newFieldId), true);
+
+                queryEngine.flushChanges();
+
+                var assignFeatureRuleActivations = assignFeatureRule.getAllActivationsAsSets();
+                var deleteEmptyClassRuleActivations = deleteEmptyClassRule.getAllActivationsAsSets();
+
+                assertResults(Map.of(
+                                Tuple.of(newClass1Id, newFieldId), true,
+                                Tuple.of(newClass2Id, newFieldId), true
+                ), assignFeatureRuleActivations);
+
+                assertResults(Map.of(
+                                Tuple.of(newModelId, newClass1Id), true,
+                                Tuple.of(newModelId, newClass2Id), true
+                ), deleteEmptyClassRuleActivations);
+        }
+
+        @Test
+        void randomActivationTest() {
+                var deleteEmptyClassPrecondition = Query.of("DeleteEmptyClassPrecondition",
+                                (builder, model, c) -> builder.clause((f) -> List.of(
+                                                classModelView.call(model),
+                                                classElementView.call(c),
+                                                featuresView.call(model, f),
+                                                not(encapsulatesView.call(c, f))
+                                )));
+
+                TransformationRule deleteEmptyClassRule0 = new TransformationRule("DeleteEmptyClass0",
+                                deleteEmptyClassPrecondition,
+                                (model) -> {
+                                        var classesInterpretation = model.getInterpretation(classes);
+                                        var classElementInterpretation = model.getInterpretation(classElement);
+                                        return ((Tuple activation) -> {
+                                                var modelElement = activation.get(0);
+                                                var classElement = activation.get(1);
+
+                                                classesInterpretation.put(Tuple.of(modelElement, classElement), false);
+                                                classElementInterpretation.put(Tuple.of(classElement), false);
+                                        });
+                                },
+                                0L);
+
+                TransformationRule deleteEmptyClassRule1 = new TransformationRule("DeleteEmptyClass1",
+                                deleteEmptyClassPrecondition,
+                                (model) -> {
+                                        var classesInterpretation = model.getInterpretation(classes);
+                                        var classElementInterpretation = model.getInterpretation(classElement);
+                                        return ((Tuple activation) -> {
+                                                var modelElement = activation.get(0);
+                                                var classElement = activation.get(1);
+
+                                                classesInterpretation.put(Tuple.of(modelElement, classElement), false);
+                                                classElementInterpretation.put(Tuple.of(classElement), false);
+                                        });
+                                },
+                                78634L);
+
+                var store = ModelStore.builder()
+                                .symbols(classModel, classElement, feature, isEncapsulatedBy, encapsulates, classes, features)
+                                .with(ViatraModelQueryAdapter.builder()
+                                                .queries(deleteEmptyClassPrecondition))
+                                .with(DesignSpaceExplorationAdapter.builder())
+                                .build();
+
+                var model = store.createEmptyModel();
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                deleteEmptyClassRule0.prepare(model, queryEngine);
+                deleteEmptyClassRule1.prepare(model, queryEngine);
+
+                var classModelInterpretation = model.getInterpretation(classModel);
+                var classElementInterpretation = model.getInterpretation(classElement);
+                var featureInterpretation = model.getInterpretation(feature);
+                var featuresInterpretation = model.getInterpretation(features);
+                var classesInterpretation = model.getInterpretation(classes);
+
+                var dseAdapter = model.getAdapter(DesignSpaceExplorationAdapter.class);
+                var newModel = dseAdapter.createObject();
+                var newModelId = newModel.get(0);
+                var newClass1 = dseAdapter.createObject();
+                var newClass1Id = newClass1.get(0);
+                var newClass2 = dseAdapter.createObject();
+                var newClass2Id = newClass2.get(0);
+                var newField = dseAdapter.createObject();
+                var newFieldId = newField.get(0);
+
+                classModelInterpretation.put(newModel, true);
+                classElementInterpretation.put(newClass1, true);
+                classElementInterpretation.put(newClass2, true);
+                featureInterpretation.put(newField, true);
+                classesInterpretation.put(Tuple.of(newModelId, newClass1Id), true);
+                classesInterpretation.put(Tuple.of(newModelId, newClass2Id), true);
+                featuresInterpretation.put(Tuple.of(newModelId, newFieldId), true);
+
+                queryEngine.flushChanges();
+
+
+                var activation0 = deleteEmptyClassRule0.getRandomActivation().activation();
+                var activation1 = deleteEmptyClassRule1.getRandomActivation().activation();
+
+                assertResults(Map.of(
+                                Tuple.of(newModelId, newClass1Id), true,
+                                Tuple.of(newModelId, newClass2Id), true
+                ), deleteEmptyClassRule0.getAllActivationsAsSets());
+
+                assertResults(Map.of(
+                                Tuple.of(newModelId, newClass1Id), true,
+                                Tuple.of(newModelId, newClass2Id), true
+                ), deleteEmptyClassRule1.getAllActivationsAsSets());
+
+                assertEquals(Tuple.of(newModelId, newClass2Id), activation0);
+                assertEquals(Tuple.of(newModelId, newClass1Id), activation1);
+
+        }
+
+        @Test
+        void fireTest() {
+                var deleteEmptyClassPrecondition = Query.of("DeleteEmptyClassPrecondition",
+                                (builder, model, c) -> builder.clause((f) -> List.of(
+                                                classModelView.call(model),
+                                                classElementView.call(c),
+                                                featuresView.call(model, f),
+                                                not(encapsulatesView.call(c, f))
+                                )));
+
+                TransformationRule deleteEmptyClassRule = new TransformationRule("DeleteEmptyClass",
+                                deleteEmptyClassPrecondition,
+                                (model) -> {
+                                        var classesInterpretation = model.getInterpretation(classes);
+                                        var classElementInterpretation = model.getInterpretation(classElement);
+                                        return ((Tuple activation) -> {
+                                                var modelElement = activation.get(0);
+                                                var classElement = activation.get(1);
+
+                                                classesInterpretation.put(Tuple.of(modelElement, classElement), false);
+                                                classElementInterpretation.put(Tuple.of(classElement), false);
+                                        });
+                                });
+
+                var store = ModelStore.builder()
+                                .symbols(classModel, classElement, feature, isEncapsulatedBy, encapsulates, classes, features)
+                                .with(ViatraModelQueryAdapter.builder()
+                                                .queries(deleteEmptyClassPrecondition))
+                                .with(DesignSpaceExplorationAdapter.builder())
+                                .build();
+
+                var model = store.createEmptyModel();
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                deleteEmptyClassRule.prepare(model, queryEngine);
+
+                var classModelInterpretation = model.getInterpretation(classModel);
+                var classElementInterpretation = model.getInterpretation(classElement);
+                var featureInterpretation = model.getInterpretation(feature);
+                var featuresInterpretation = model.getInterpretation(features);
+                var classesInterpretation = model.getInterpretation(classes);
+
+                var dseAdapter = model.getAdapter(DesignSpaceExplorationAdapter.class);
+                var newModel = dseAdapter.createObject();
+                var newModelId = newModel.get(0);
+                var newClass1 = dseAdapter.createObject();
+                var newClass1Id = newClass1.get(0);
+                var newClass2 = dseAdapter.createObject();
+                var newClass2Id = newClass2.get(0);
+                var newField = dseAdapter.createObject();
+                var newFieldId = newField.get(0);
+
+                classModelInterpretation.put(newModel, true);
+                classElementInterpretation.put(newClass1, true);
+                classElementInterpretation.put(newClass2, true);
+                featureInterpretation.put(newField, true);
+                classesInterpretation.put(Tuple.of(newModelId, newClass1Id), true);
+                classesInterpretation.put(Tuple.of(newModelId, newClass2Id), true);
+                featuresInterpretation.put(Tuple.of(newModelId, newFieldId), true);
+
+                queryEngine.flushChanges();
+
+                assertResults(Map.of(
+                                Tuple.of(newModelId, newClass1Id), true,
+                                Tuple.of(newModelId, newClass2Id), true
+                ), deleteEmptyClassRule.getAllActivationsAsSets());
+
+
+                deleteEmptyClassRule.fireActivation(Tuple.of(0, 1));
+
+                assertResults(Map.of(
+                                Tuple.of(newModelId, newClass1Id), false,
+                                Tuple.of(newModelId, newClass2Id), true
+                ), deleteEmptyClassRule.getAllActivationsAsSets());
+        }
+
+        @Test
+        void randomFireTest() {
+                var deleteEmptyClassPrecondition = Query.of("DeleteEmptyClassPrecondition",
+                                (builder, model, c) -> builder.clause((f) -> List.of(
+                                                classModelView.call(model),
+                                                classElementView.call(c),
+                                                featuresView.call(model, f),
+                                                not(encapsulatesView.call(c, f))
+                                )));
+
+                TransformationRule deleteEmptyClassRule = new TransformationRule("DeleteEmptyClass0",
+                                deleteEmptyClassPrecondition,
+                                (model) -> {
+                                        var classesInterpretation = model.getInterpretation(classes);
+                                        var classElementInterpretation = model.getInterpretation(classElement);
+                                        return ((Tuple activation) -> {
+                                                var modelElement = activation.get(0);
+                                                var classElement = activation.get(1);
+
+                                                classesInterpretation.put(Tuple.of(modelElement, classElement), false);
+                                                classElementInterpretation.put(Tuple.of(classElement), false);
+                                        });
+                                },
+                                0L);
+
+                var store = ModelStore.builder()
+                                .symbols(classModel, classElement, feature, isEncapsulatedBy, encapsulates, classes, features)
+                                .with(ViatraModelQueryAdapter.builder()
+                                                .queries(deleteEmptyClassPrecondition))
+                                .with(DesignSpaceExplorationAdapter.builder())
+                                .build();
+
+                var model = store.createEmptyModel();
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                deleteEmptyClassRule.prepare(model, queryEngine);
+
+                var classModelInterpretation = model.getInterpretation(classModel);
+                var classElementInterpretation = model.getInterpretation(classElement);
+                var featureInterpretation = model.getInterpretation(feature);
+                var featuresInterpretation = model.getInterpretation(features);
+                var classesInterpretation = model.getInterpretation(classes);
+
+                var dseAdapter = model.getAdapter(DesignSpaceExplorationAdapter.class);
+                var newModel = dseAdapter.createObject();
+                var newModelId = newModel.get(0);
+                var newClass1 = dseAdapter.createObject();
+                var newClass1Id = newClass1.get(0);
+                var newClass2 = dseAdapter.createObject();
+                var newClass2Id = newClass2.get(0);
+                var newField = dseAdapter.createObject();
+                var newFieldId = newField.get(0);
+
+                classModelInterpretation.put(newModel, true);
+                classElementInterpretation.put(newClass1, true);
+                classElementInterpretation.put(newClass2, true);
+                featureInterpretation.put(newField, true);
+                classesInterpretation.put(Tuple.of(newModelId, newClass1Id), true);
+                classesInterpretation.put(Tuple.of(newModelId, newClass2Id), true);
+                featuresInterpretation.put(Tuple.of(newModelId, newFieldId), true);
+
+                queryEngine.flushChanges();
+
+                assertResults(Map.of(
+                                Tuple.of(newModelId, newClass1Id), true,
+                                Tuple.of(newModelId, newClass2Id), true
+                ), deleteEmptyClassRule.getAllActivationsAsSets());
+
+                deleteEmptyClassRule.fireRandomActivation();
+
+                assertResults(Map.of(
+                                Tuple.of(newModelId, newClass1Id), true,
+                                Tuple.of(newModelId, newClass2Id), false
+                ), deleteEmptyClassRule.getAllActivationsAsSets());
+
+                deleteEmptyClassRule.fireRandomActivation();
+
+                assertResults(Map.of(
+                                Tuple.of(newModelId, newClass1Id), false,
+                                Tuple.of(newModelId, newClass2Id), false
+                ), deleteEmptyClassRule.getAllActivationsAsSets());
+
+        }
+}
diff --git a/subprojects/store-dse/src/test/java/tools/refinery/store/dse/tests/QueryAssertions.java b/subprojects/store-dse/src/test/java/tools/refinery/store/dse/tests/QueryAssertions.java
new file mode 100644
index 00000000..be514eaf
--- /dev/null
+++ b/subprojects/store-dse/src/test/java/tools/refinery/store/dse/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.dse.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);
+        }
+}