build: migration to Gradle 7

52 files changed, 3950 insertions, 0 deletions

diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/map/ContinousHashProvider.java b/store/src/main/java/org/eclipse/viatra/solver/data/map/ContinousHashProvider.java
new file mode 100644
index 00000000..dd64f901
--- /dev/null
+++ b/store/src/main/java/org/eclipse/viatra/solver/data/map/ContinousHashProvider.java
@@ -0,0 +1,69 @@
+package org.eclipse.viatra.solver.data.map;
+
+import org.eclipse.viatra.solver.data.map.internal.Node;
+
+/**
+ * A class representing an equivalence relation for a type {@code K} with a
+ * continuous hash function.
+ * 
+ * @author Oszkar Semerath
+ *
+ * @param <K> Target java type.
+ */
+public interface ContinousHashProvider<K> {
+        public static final int EFFECTIVE_BITS = Node.EFFECTIVE_BITS;
+        public static final int EFFECTIVE_BIT_MASK = (1 << (EFFECTIVE_BITS)) - 1;
+
+        /**
+         * Maximal practical depth for differentiating keys. If two keys have the same
+         * hash code until that depth, the algorithm can stop.
+         */
+        public static final int MAX_PRACTICAL_DEPTH = 500;
+
+        /**
+         * Provides a hash code for a object {@code key} with a given {@code index}. It
+         * has the following contracts:
+         * <ul>
+         * <li>If {@link #equals}{@code (key1,key2)}, then
+         * {@code getHash(key1, index) == getHash(key2, index)} for all values of
+         * {@code index}.</li>
+         * <li>If {@code getHash(key1,index) == getHash(key2, index)} for all values of
+         * {@code index}, then {@link #equals}{@code (key1, key2)}</li>
+         * <li>In current implementation, we use only the least significant
+         * {@link #EFFECTIVE_BITS}
+         * </ul>
+         * Check {@link #equals} for further details.
+         * 
+         * @param key   The target data object.
+         * @param index The depth of the the hash code. Needs to be non-negative.
+         * @return A hash code.
+         */
+        public int getHash(K key, int index);
+
+        public default int getEffectiveHash(K key, int index) {
+                return getHash(key, index) & EFFECTIVE_BIT_MASK;
+        }
+
+        public default int compare(K key1, K key2) {
+                if (key1.equals(key2)) {
+                        return 0;
+                } else {
+                        for (int i = 0; i < ContinousHashProvider.MAX_PRACTICAL_DEPTH; i++) {
+                                int hash1 = getEffectiveHash(key1, i);
+                                int hash2 = getEffectiveHash(key2, i);
+                                for(int j = 0; j<Integer.SIZE/Node.BRANCHING_FACTOR_BITS; j++) {
+                                        final int factorMask = (1<<Node.BRANCHING_FACTOR_BITS)-1;
+                                        int hashFragment1 = (hash1>>>j*Node.BRANCHING_FACTOR_BITS) & factorMask;
+                                        int hashFragment2 = (hash2>>>j*Node.BRANCHING_FACTOR_BITS) & factorMask;
+                                        var result = Integer.compare(hashFragment1, hashFragment2);
+                                        if (result != 0) {
+                                                return result;
+                                        }
+                                }
+                        }
+                        throw new IllegalArgumentException("Two different keys (" + key1 + " and " + key2
+                                        + ") have the same hashcode over the practical depth limitation ("
+                                        + ContinousHashProvider.MAX_PRACTICAL_DEPTH + ")!");
+                }
+        }
+}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/map/Cursor.java b/store/src/main/java/org/eclipse/viatra/solver/data/map/Cursor.java
new file mode 100644
index 00000000..e45b1f20
--- /dev/null
+++ b/store/src/main/java/org/eclipse/viatra/solver/data/map/Cursor.java
@@ -0,0 +1,14 @@
+package org.eclipse.viatra.solver.data.map;
+
+import java.util.List;
+
+public interface Cursor<K,V> {
+        public K getKey();
+        public V getValue();
+        public boolean isTerminated();
+        public boolean move();
+        public boolean isDirty();
+        
+        @SuppressWarnings("squid:S1452")
+        public List<VersionedMap<?,?>> getDependingMaps();
+}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/map/CursorAsIterator.java b/store/src/main/java/org/eclipse/viatra/solver/data/map/CursorAsIterator.java
new file mode 100644
index 00000000..b29b3119
--- /dev/null
+++ b/store/src/main/java/org/eclipse/viatra/solver/data/map/CursorAsIterator.java
@@ -0,0 +1,57 @@
+package org.eclipse.viatra.solver.data.map;
+
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+import java.util.function.BiFunction;
+import java.util.function.BiPredicate;
+
+public class CursorAsIterator<K,V,D> implements Iterator<D> {
+        private final Cursor<K, V> internal;
+        private final BiFunction<K, V, D> entryTransformation;
+        private final BiPredicate<K,V> filtering;
+        
+        D lastValidElement;
+        
+        public CursorAsIterator(Cursor<K, V> internal, BiFunction<K, V, D> entryTransformation, BiPredicate<K,V> filtering) {
+                this.internal = internal;
+                this.entryTransformation = entryTransformation;
+                this.filtering = filtering;
+                
+                moveToNext();
+        }
+        public CursorAsIterator(Cursor<K, V> internal, BiFunction<K, V, D> entryTransformation) {
+                this.internal = internal;
+                this.entryTransformation = entryTransformation;
+                this.filtering = ((k,v)->true);
+                
+                moveToNext();
+        }
+        
+        private void moveToNext() {
+                internal.move();
+                while(!internal.isTerminated() && !filtering.test(internal.getKey(), internal.getValue())) {
+                        internal.move();
+                }
+                if(!internal.isTerminated()) {
+                        lastValidElement = entryTransformation.apply(internal.getKey(), internal.getValue());
+                }
+        }
+        
+        
+        @Override
+        public boolean hasNext() {
+                return !internal.isTerminated();
+        }
+        @Override
+        public D next() {
+                if(hasNext()) {
+                        D last = lastValidElement;
+                        moveToNext();
+                        return last;
+                } else {
+                        throw new NoSuchElementException();
+                }
+
+        }
+        
+}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/map/DiffCursor.java b/store/src/main/java/org/eclipse/viatra/solver/data/map/DiffCursor.java
new file mode 100644
index 00000000..f0af1436
--- /dev/null
+++ b/store/src/main/java/org/eclipse/viatra/solver/data/map/DiffCursor.java
@@ -0,0 +1,6 @@
+package org.eclipse.viatra.solver.data.map;
+
+public interface DiffCursor<K, V> extends Cursor<K,V> {
+        public V getFromValue();
+        public V getToValue();
+}
\ No newline at end of file
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/map/MapAsIterable.java b/store/src/main/java/org/eclipse/viatra/solver/data/map/MapAsIterable.java
new file mode 100644
index 00000000..22b5e6c1
--- /dev/null
+++ b/store/src/main/java/org/eclipse/viatra/solver/data/map/MapAsIterable.java
@@ -0,0 +1,26 @@
+package org.eclipse.viatra.solver.data.map;
+
+import java.util.Iterator;
+import java.util.function.BiFunction;
+import java.util.function.BiPredicate;
+
+public class MapAsIterable<K,V,D> implements Iterable<D> {
+        private final VersionedMap<K, V> internal;
+        private final BiFunction<K, V, D> entryTransformation;
+        private final BiPredicate<K,V> filtering;
+        
+        public MapAsIterable(VersionedMap<K, V> internal, BiFunction<K, V, D> entryTransformation, BiPredicate<K,V> filtering) {
+                this.internal = internal;
+                this.entryTransformation = entryTransformation;
+                this.filtering = filtering;
+        }
+        public MapAsIterable(VersionedMap<K, V> internal, BiFunction<K, V, D> entryTransformation) {
+                this.internal = internal;
+                this.entryTransformation = entryTransformation;
+                this.filtering = ((k,v)->true);
+        }
+        @Override
+        public Iterator<D> iterator() {
+                return new CursorAsIterator<>(internal.getAll(), entryTransformation, filtering);
+        }
+}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/map/Versioned.java b/store/src/main/java/org/eclipse/viatra/solver/data/map/Versioned.java
new file mode 100644
index 00000000..e46be237
--- /dev/null
+++ b/store/src/main/java/org/eclipse/viatra/solver/data/map/Versioned.java
@@ -0,0 +1,7 @@
+package org.eclipse.viatra.solver.data.map;
+
+public interface Versioned {
+        public long commit();
+        //maybe revert()?
+        public void restore(long state);
+}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/map/VersionedMap.java b/store/src/main/java/org/eclipse/viatra/solver/data/map/VersionedMap.java
new file mode 100644
index 00000000..3a35b9f0
--- /dev/null
+++ b/store/src/main/java/org/eclipse/viatra/solver/data/map/VersionedMap.java
@@ -0,0 +1,13 @@
+package org.eclipse.viatra.solver.data.map;
+
+public interface VersionedMap<K,V> extends Versioned{
+        public V get(K key);
+        public Cursor<K,V> getAll();
+        
+        public V put(K key, V value);
+        public void putAll(Cursor<K,V> cursor);
+        
+        public long getSize();
+        
+        public DiffCursor<K,V> getDiffCursor(long state);
+}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/map/VersionedMapStore.java b/store/src/main/java/org/eclipse/viatra/solver/data/map/VersionedMapStore.java
new file mode 100644
index 00000000..0ff0773f
--- /dev/null
+++ b/store/src/main/java/org/eclipse/viatra/solver/data/map/VersionedMapStore.java
@@ -0,0 +1,14 @@
+package org.eclipse.viatra.solver.data.map;
+
+import java.util.Set;
+
+public interface VersionedMapStore<K, V> {
+        
+        public VersionedMap<K, V> createMap();
+
+        public VersionedMap<K, V> createMap(long state);
+        
+        public Set<Long> getStates();
+
+        public DiffCursor<K,V> getDiffCursor(long fromState, long toState);
+}
\ No newline at end of file
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/map/VersionedMapStoreConfiguration.java b/store/src/main/java/org/eclipse/viatra/solver/data/map/VersionedMapStoreConfiguration.java
new file mode 100644
index 00000000..be768e98
--- /dev/null
+++ b/store/src/main/java/org/eclipse/viatra/solver/data/map/VersionedMapStoreConfiguration.java
@@ -0,0 +1,48 @@
+package org.eclipse.viatra.solver.data.map;
+
+public class VersionedMapStoreConfiguration {
+        
+        public VersionedMapStoreConfiguration() {
+                
+        }
+        public VersionedMapStoreConfiguration(boolean immutableWhenCommiting, boolean sharedNodeCacheInStore,
+                        boolean sharedNodeCacheInStoreGroups) {
+                super();
+                this.immutableWhenCommiting = immutableWhenCommiting;
+                this.sharedNodeCacheInStore = sharedNodeCacheInStore;
+                this.sharedNodeCacheInStoreGroups = sharedNodeCacheInStoreGroups;
+        }
+
+        /**
+         * If true root is replaced with immutable node when committed. Frees up memory
+         * by releasing immutable nodes, but it may decrease performance by recreating
+         * immutable nodes upon changes (some evidence).
+         */
+        private boolean immutableWhenCommiting = true;
+        public boolean isImmutableWhenCommiting() {
+                return immutableWhenCommiting;
+        }
+
+        /**
+         * If true, all subnodes are cached within a {@link VersionedMapStore}. It
+         * decreases the memory requirements. It may increase performance by discovering
+         * existing immutable copy of a node (some evidence). Additional overhead may
+         * decrease performance (no example found). The option permits the efficient
+         * implementation of version deletion.
+         */
+        private boolean sharedNodeCacheInStore = true;
+        public boolean isSharedNodeCacheInStore() {
+                return sharedNodeCacheInStore;
+        }
+        
+        /**
+         * If true, all subnodes are cached within a group of
+         * {@link VersionedMapStoreImpl#createSharedVersionedMapStores(int, ContinousHashProvider, Object, VersionedMapStoreConfiguration)}.
+         * If {@link VersionedMapStoreConfiguration#sharedNodeCacheInStore} is
+         * <code>false</code>, then it has currently no impact.
+         */
+        private boolean sharedNodeCacheInStoreGroups = true;
+        public boolean isSharedNodeCacheInStoreGroups() {
+                return sharedNodeCacheInStoreGroups;
+        }
+}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/map/VersionedMapStoreImpl.java b/store/src/main/java/org/eclipse/viatra/solver/data/map/VersionedMapStoreImpl.java
new file mode 100644
index 00000000..83d0e8cd
--- /dev/null
+++ b/store/src/main/java/org/eclipse/viatra/solver/data/map/VersionedMapStoreImpl.java
@@ -0,0 +1,135 @@
+package org.eclipse.viatra.solver.data.map;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+
+import org.eclipse.viatra.solver.data.map.internal.ImmutableNode;
+import org.eclipse.viatra.solver.data.map.internal.MapDiffCursor;
+import org.eclipse.viatra.solver.data.map.internal.Node;
+import org.eclipse.viatra.solver.data.map.internal.VersionedMapImpl;
+
+public class VersionedMapStoreImpl<K, V> implements VersionedMapStore<K, V> {
+        // Configuration
+        private final boolean immutableWhenCommiting;
+
+        // Static data
+        protected final ContinousHashProvider<K> hashProvider;
+        protected final V defaultValue;
+
+        // Dynamic data
+        protected final Map<Long, ImmutableNode<K, V>> states = new HashMap<>();
+        protected final Map<Node<K, V>, ImmutableNode<K, V>> nodeCache;
+        protected long nextID = 0;
+
+        public VersionedMapStoreImpl(ContinousHashProvider<K> hashProvider, V defaultValue,
+                        VersionedMapStoreConfiguration config) {
+                this.immutableWhenCommiting = config.isImmutableWhenCommiting();
+                this.hashProvider = hashProvider;
+                this.defaultValue = defaultValue;
+                if (config.isSharedNodeCacheInStore()) {
+                        nodeCache = new HashMap<>();
+                } else {
+                        nodeCache = null;
+                }
+        }
+
+        private VersionedMapStoreImpl(ContinousHashProvider<K> hashProvider, V defaultValue,
+                        Map<Node<K, V>, ImmutableNode<K, V>> nodeCache, VersionedMapStoreConfiguration config) {
+                this.immutableWhenCommiting = config.isImmutableWhenCommiting();
+                this.hashProvider = hashProvider;
+                this.defaultValue = defaultValue;
+                this.nodeCache = nodeCache;
+        }
+
+        public VersionedMapStoreImpl(ContinousHashProvider<K> hashProvider, V defaultValue) {
+                this(hashProvider, defaultValue, new VersionedMapStoreConfiguration());
+        }
+
+        public static <K, V> List<VersionedMapStore<K, V>> createSharedVersionedMapStores(int amount,
+                        ContinousHashProvider<K> hashProvider, V defaultValue,
+                        VersionedMapStoreConfiguration config) {
+                List<VersionedMapStore<K, V>> result = new ArrayList<>(amount);
+                if (config.isSharedNodeCacheInStoreGroups()) {
+                        Map<Node<K, V>, ImmutableNode<K, V>> nodeCache;
+                        if (config.isSharedNodeCacheInStore()) {
+                                nodeCache = new HashMap<>();
+                        } else {
+                                nodeCache = null;
+                        }
+                        for (int i = 0; i < amount; i++) {
+                                result.add(new VersionedMapStoreImpl<>(hashProvider, defaultValue, nodeCache, config));
+                        }
+                } else {
+                        for (int i = 0; i < amount; i++) {
+                                result.add(new VersionedMapStoreImpl<>(hashProvider, defaultValue, config));
+                        }
+                }
+                return result;
+        }
+
+        public static <K, V> List<VersionedMapStore<K, V>> createSharedVersionedMapStores(int amount,
+                        ContinousHashProvider<K> hashProvider, V defaultValue) {
+                return createSharedVersionedMapStores(amount, hashProvider, defaultValue, new VersionedMapStoreConfiguration());
+        }
+        
+        @Override
+        public synchronized Set<Long> getStates() {
+                return new HashSet<>(states.keySet());
+        }
+
+        @Override
+        public VersionedMap<K, V> createMap() {
+                return new VersionedMapImpl<>(this, hashProvider, defaultValue);
+        }
+
+        @Override
+        public VersionedMap<K, V> createMap(long state) {
+                ImmutableNode<K, V> data = revert(state);
+                return new VersionedMapImpl<>(this, hashProvider, defaultValue, data);
+        }
+        
+
+        public synchronized ImmutableNode<K, V> revert(long state) {
+                if (states.containsKey(state)) {
+                        return states.get(state);
+                } else {
+                        ArrayList<Long> existingKeys = new ArrayList<>(states.keySet());
+                        Collections.sort(existingKeys);
+                        throw new IllegalArgumentException("Store does not contain state " + state + "! Avaliable states: "
+                                        + Arrays.toString(existingKeys.toArray()));
+                }
+        }
+
+        public synchronized long commit(Node<K, V> data, VersionedMapImpl<K, V> mapToUpdateRoot) {
+                ImmutableNode<K, V> immutable;
+                if (data != null) {
+                        immutable = data.toImmutable(this.nodeCache);
+                } else {
+                        immutable = null;
+                }
+
+                if (nextID == Long.MAX_VALUE)
+                        throw new IllegalStateException("Map store run out of Id-s");
+                long id = nextID++;
+                this.states.put(id, immutable);
+                if (this.immutableWhenCommiting) {
+                        mapToUpdateRoot.setRoot(immutable);
+                }
+                return id;
+        }
+
+        @Override
+        public DiffCursor<K, V> getDiffCursor(long fromState, long toState) {
+                VersionedMap<K, V> map1 = createMap(fromState);
+                VersionedMap<K, V> map2 = createMap(toState);
+                Cursor<K, V> cursor1 = map1.getAll();
+                Cursor<K, V> cursor2 = map2.getAll();
+                return new MapDiffCursor<>(this.hashProvider, this.defaultValue, cursor1, cursor2);
+        }
+}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/ImmutableNode.java b/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/ImmutableNode.java
new file mode 100644
index 00000000..04a9b19a
--- /dev/null
+++ b/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/ImmutableNode.java
@@ -0,0 +1,379 @@
+package org.eclipse.viatra.solver.data.map.internal;
+
+import java.util.Arrays;
+import java.util.Map;
+
+import org.eclipse.viatra.solver.data.map.ContinousHashProvider;
+
+public class ImmutableNode<K, V> extends Node<K, V> {
+        /**
+         * Bitmap defining the stored key and values.
+         */
+        final int dataMap;
+        /**
+         * Bitmap defining the positions of further nodes.
+         */
+        final int nodeMap;
+        /**
+         * Stores Keys, Values, and subnodes. Structure: (K,V)*,NODE; NODES are stored backwards. 
+         */
+        final Object[] content;
+        
+        /**
+         * Hash code derived from immutable hash code
+         */
+        final int precalculatedHash;
+                
+        private ImmutableNode(int dataMap, int nodeMap, Object[] content, int precalculatedHash) {
+                super();
+                this.dataMap = dataMap;
+                this.nodeMap = nodeMap;
+                this.content = content;
+                this.precalculatedHash = precalculatedHash;
+        }
+
+        /**
+         * Constructor that copies a mutable node to an immutable.
+         * 
+         * @param node  A mutable node.
+         * @param cache A cache of existing immutable nodes. It can be used to search
+         *              and place reference immutable nodes. It can be null, if no cache
+         *              available.
+         * @return an immutable version of the input node.
+         */
+        @SuppressWarnings("unchecked")
+        static <K,V> ImmutableNode<K,V> constructImmutable(MutableNode<K,V> node, Map<Node<K, V>, ImmutableNode<K, V>> cache) {
+                // 1. try to return from cache
+                if(cache != null) {
+                        ImmutableNode<K, V> cachedResult = cache.get(node);
+                        if(cachedResult != null) {
+                                // 1.1 Already cached, return from cache.
+                                return cachedResult;
+                        }
+                }
+                
+                // 2. otherwise construct a new ImmutableNode
+                int size = 0;
+                for(int i = 0; i<node.content.length; i++) {
+                        if(node.content[i]!=null) {
+                                size++;
+                        }
+                }
+                
+                int datas = 0;
+                int nodes = 0;
+                int resultDataMap = 0;
+                int resultNodeMap = 0;
+                final Object[] resultContent = new Object[size];
+                int bitposition = 1;
+                for(int i = 0; i<FACTOR; i++) {
+                        Object key = node.content[i*2];
+                        if(key != null) {
+                                resultDataMap |= bitposition;
+                                resultContent[datas*2] = key;
+                                resultContent[datas*2+1] = node.content[i*2+1];
+                                datas++;
+                        } else {
+                                Node<K,V> subnode = (Node<K, V>) node.content[i*2+1];
+                                if(subnode != null) {
+                                        ImmutableNode<K, V> immutableSubnode = subnode.toImmutable(cache);
+                                        resultNodeMap |=bitposition;
+                                        resultContent[size-1-nodes] = immutableSubnode;
+                                        nodes++;
+                                }
+                        }
+                        bitposition<<=1;
+                }
+                final int resultHash = node.hashCode();
+                ImmutableNode<K,V> newImmutable = new ImmutableNode<>(resultDataMap, resultNodeMap, resultContent, resultHash);
+                
+                // 3. save new immutable.
+                if(cache != null) {
+                        cache.put(newImmutable, newImmutable);
+                }
+                return newImmutable;
+        }
+        
+        private int index(int bitmap, int bitpos) {
+                return Integer.bitCount(bitmap & (bitpos-1));
+        }
+        
+        @SuppressWarnings("unchecked")
+        @Override
+        public V getValue(K key, ContinousHashProvider<? super K> hashProvider, V defaultValue, int hash, int depth) {
+                int selectedHashFragment = hashFragment(hash,shiftDepth(depth));
+                int bitposition = 1 << selectedHashFragment;
+                // If the key is stored as a data
+                if((dataMap & bitposition) != 0) {
+                        int keyIndex = 2*index(dataMap, bitposition);
+                        K keyCandidate = (K) content[keyIndex];
+                        if(keyCandidate.equals(key)) {
+                                return (V) content[keyIndex+1];
+                        } else {
+                                return defaultValue;
+                        }
+                }
+                // the key is stored as a node
+                else if((nodeMap & bitposition) != 0) {
+                        int keyIndex = content.length-1-index(nodeMap, bitposition);
+                        ImmutableNode<K,V> subNode = (ImmutableNode<K,V>) content[keyIndex];
+                        int newDepth = depth+1;
+                        int newHash = newHash(hashProvider, key, hash, newDepth);
+                        return subNode.getValue(key, hashProvider, defaultValue, newHash, newDepth);
+                }
+                // the key is not stored at all
+                else {
+                        return defaultValue;
+                }
+        }
+        
+        @SuppressWarnings("unchecked")
+        @Override
+        public Node<K,V> putValue(K key, V value, OldValueBox<V> oldValue, ContinousHashProvider<? super K> hashProvider, V defaultValue, int hash, int depth) {
+                int selectedHashFragment = hashFragment(hash,shiftDepth(depth));
+                int bitposition = 1 << selectedHashFragment;
+                if((dataMap & bitposition) != 0) {
+                        int keyIndex = 2*index(dataMap, bitposition);
+                        K keyCandidate = (K) content[keyIndex];
+                        if(keyCandidate.equals(key)) {
+                                if(value == defaultValue) {
+                                        // delete
+                                        MutableNode<K, V> mutable = this.toMutable();
+                                        return mutable.removeEntry(selectedHashFragment,oldValue);
+                                } else if(value == content[keyIndex+1]) {
+                                        // dont change
+                                        oldValue.setOldValue(value);
+                                        return this;
+                                } else {
+                                        // update existing value
+                                        MutableNode<K, V> mutable = this.toMutable();
+                                        return mutable.updateValue(value, oldValue, selectedHashFragment);
+                                }
+                        } else {
+                                if(value == defaultValue) {
+                                        // dont change
+                                        oldValue.setOldValue(defaultValue);
+                                        return this;
+                                } else {
+                                        // add new key + value
+                                        MutableNode<K, V> mutable = this.toMutable();
+                                        return mutable.putValue(key, value, oldValue, hashProvider, defaultValue, hash, depth);
+                                }
+                        }
+                } else if((nodeMap & bitposition)!=0) {
+                        
+                        int keyIndex = content.length-1-index(nodeMap, bitposition);
+                        ImmutableNode<K,V> subNode = (ImmutableNode<K,V>) content[keyIndex];
+                        int newDepth = depth+1;
+                        int newHash = newHash(hashProvider, key, hash, newDepth);
+                        Node<K,V> newsubNode = subNode.putValue(key, value, oldValue, hashProvider, defaultValue, newHash, newDepth);
+                        
+                        if(subNode == newsubNode) {
+                                // nothing changed
+                                return this;
+                        } else {
+                                MutableNode<K, V> mutable  = toMutable();
+                                return mutable.updateWithSubNode(selectedHashFragment, newsubNode, value.equals(defaultValue));
+                        }
+                } else {
+                        // add new key + value
+                        MutableNode<K, V> mutable = this.toMutable();
+                        return mutable.putValue(key, value, oldValue, hashProvider, defaultValue, hash, depth);
+                }
+        }
+        
+        
+        @SuppressWarnings("unchecked")
+        @Override
+        public long getSize() {
+                int result = Integer.bitCount(this.dataMap);
+                for(int subnodeIndex = 0; subnodeIndex < Integer.bitCount(this.nodeMap); subnodeIndex++) {
+                        ImmutableNode<K,V> subnode =
+                                (ImmutableNode<K, V>) this.content[this.content.length-1-subnodeIndex];
+                        result += subnode.getSize();
+                }
+                return result;
+        }
+        
+        @Override
+        protected MutableNode<K,V> toMutable() {
+                return new MutableNode<>(this);
+        }
+        
+        @Override
+        public ImmutableNode<K, V> toImmutable(
+                        Map<Node<K, V>, ImmutableNode<K, V>> cache) {
+                return this;
+        }
+        
+        @Override
+        protected MutableNode<K, V> isMutable() {
+                return null;
+        }
+        
+        @SuppressWarnings("unchecked")
+        @Override
+        boolean moveToNext(MapCursor<K, V> cursor) {
+                // 1. try to move to data
+                int datas = Integer.bitCount(this.dataMap);
+                if(cursor.dataIndex != MapCursor.INDEX_FINISH) {
+                        int newDataIndex = cursor.dataIndex + 1;
+                        if(newDataIndex < datas) {
+                                cursor.dataIndex = newDataIndex;
+                                cursor.key = (K) this.content[newDataIndex*2];
+                                cursor.value = (V) this.content[newDataIndex*2+1];
+                                return true;
+                        } else {
+                                cursor.dataIndex = MapCursor.INDEX_FINISH;
+                        }
+                }
+                
+                // 2. look inside the subnodes
+                int nodes = Integer.bitCount(this.nodeMap);
+                int newNodeIndex = cursor.nodeIndexStack.peek() + 1;
+                if(newNodeIndex < nodes) {
+                        // 2.1 found next subnode, move down to the subnode
+                        Node<K, V> subnode = (Node<K, V>) this.content[this.content.length-1-newNodeIndex];
+                        cursor.dataIndex = MapCursor.INDEX_START;
+                        cursor.nodeIndexStack.pop();
+                        cursor.nodeIndexStack.push(newNodeIndex);
+                        cursor.nodeIndexStack.push(MapCursor.INDEX_START);
+                        cursor.nodeStack.push(subnode);
+                        return subnode.moveToNext(cursor);
+                } else {
+                        // 3. no subnode found, move up
+                        cursor.nodeStack.pop();
+                        cursor.nodeIndexStack.pop();
+                        if(!cursor.nodeStack.isEmpty()) {
+                                Node<K, V> supernode = cursor.nodeStack.peek();
+                                return supernode.moveToNext(cursor);
+                        } else {
+                                cursor.key = null;
+                                cursor.value = null;
+                                return false;
+                        }
+                }
+        }
+        
+        @Override
+        public void prettyPrint(StringBuilder builder, int depth, int code) {
+                for(int i = 0; i<depth; i++) {
+                        builder.append("\t");
+                }
+                if(code>=0) {
+                        builder.append(code);
+                        builder.append(":");
+                }
+                builder.append("Immutable(");
+                boolean hadContent = false;
+                int dataMask = 1;
+                for(int i = 0; i<FACTOR; i++) {
+                        if((dataMask & dataMap) != 0) {
+                                if(hadContent) {
+                                        builder.append(",");
+                                }
+                                builder.append(i);
+                                builder.append(":[");
+                                builder.append(content[2*index(dataMap, dataMask)].toString());
+                                builder.append("]->[");
+                                builder.append(content[2*index(dataMap, dataMask)+1].toString());
+                                builder.append("]");
+                                hadContent = true;
+                        }
+                        dataMask<<=1;
+                }
+                builder.append(")");
+                int nodeMask = 1;
+                for(int i = 0; i<FACTOR; i++) {
+                        if((nodeMask & nodeMap)!=0) {
+                                @SuppressWarnings("unchecked")
+                                Node<K,V> subNode = (Node<K, V>) content[content.length-1-index(nodeMap, nodeMask)];
+                                builder.append("\n");
+                                subNode.prettyPrint(builder, depth+1, i);
+                        }
+                        nodeMask<<=1;
+                }
+        }
+        
+        @SuppressWarnings("unchecked")
+        @Override
+        public void checkIntegrity(ContinousHashProvider<? super K> hashProvider, V defaultValue, int depth) {
+                if(depth>0) {
+                        boolean orphaned = Integer.bitCount(dataMap) == 1 && nodeMap == 0;
+                        if(orphaned) {
+                                throw new IllegalStateException("Orphaned node! " + dataMap + ": " +  content[0]);
+                        }
+                }
+                // check the place of data
+                
+                // check subnodes
+                for(int i = 0; i<Integer.bitCount(nodeMap); i++) {
+                        Node<K,V> subnode = (Node<K, V>) this.content[this.content.length-1-i];
+                        if(! (subnode instanceof ImmutableNode<?,?>)) {
+                                throw new IllegalStateException("Immutable node contains mutable subnodes!");
+                        } else {
+                                subnode.checkIntegrity(hashProvider, defaultValue, depth+1);
+                        }
+                }
+        }
+        
+        @Override
+        public int hashCode() {
+                return this.precalculatedHash;
+        }
+
+        @Override
+        public boolean equals(Object obj) {
+                if (this == obj)
+                        return true;
+                if (obj == null)
+                        return false;
+                if (obj instanceof ImmutableNode<?,?>) {
+                        ImmutableNode<?,?> other = (ImmutableNode<?,?>) obj;
+                        if (precalculatedHash != other.precalculatedHash || dataMap != other.dataMap || nodeMap != other.nodeMap || !Arrays.deepEquals(content, other.content))
+                                return false;
+                        else return true;
+                } else if(obj instanceof MutableNode<?,?>) {
+                        return ImmutableNode.compareImmutableMutable(this, (MutableNode<?, ?>) obj);
+                } else {
+                        return false;
+                }
+        }
+        public static boolean compareImmutableMutable(
+                        ImmutableNode<?, ?> immutable,
+                        MutableNode<?, ?> mutable)
+        {
+                int datas = 0;
+                int nodes = 0;
+                final int immutableLength = immutable.content.length;
+                for(int i = 0; i<FACTOR; i++) {
+                        Object key = mutable.content[i*2];
+                        // For each key candidate
+                        if(key != null) {
+                                // Check whether a new Key-Value pair can fit into the immutable container 
+                                if(datas*2+nodes+2 <= immutableLength) {
+                                        if(     !immutable.content[datas*2].equals(key) ||
+                                                !immutable.content[datas*2+1].equals(mutable.content[i*2+1]))
+                                        {
+                                                return false;
+                                        }
+                                } else return false;
+                                datas++;
+                        } else {
+                                Node<?,?> mutableSubnode = (Node<?, ?>) mutable.content[i*2+1];
+                                if(mutableSubnode != null) {
+                                        if(datas*2+nodes+1 <= immutableLength) {
+                                                Object immutableSubnode = immutable.content[immutableLength-1-nodes];
+                                                if(!mutableSubnode.equals(immutableSubnode)) {
+                                                        return false;
+                                                }
+                                                nodes++;
+                                        } else {
+                                                return false;
+                                        }
+                                }
+                        }
+                }
+                return true;
+        }
+}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/MapCursor.java b/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/MapCursor.java
new file mode 100644
index 00000000..cc5a3982
--- /dev/null
+++ b/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/MapCursor.java
@@ -0,0 +1,131 @@
+package org.eclipse.viatra.solver.data.map.internal;
+
+import java.util.ArrayDeque;
+import java.util.ConcurrentModificationException;
+import java.util.Iterator;
+import java.util.List;
+
+import org.eclipse.viatra.solver.data.map.Cursor;
+import org.eclipse.viatra.solver.data.map.VersionedMap;
+
+public class MapCursor<K,V> implements Cursor<K,V> {
+        // Constants
+        static final int INDEX_START = -1;
+        static final int INDEX_FINISH = -2;
+        
+        // Tree stack
+        ArrayDeque<Node<K,V>> nodeStack;
+        ArrayDeque<Integer> nodeIndexStack;
+        int dataIndex;
+        
+        // Values
+        K key;
+        V value;
+        
+        // Hash code for checking concurrent modifications
+        final VersionedMap<K,V> map;
+        final int creationHash; 
+        
+        public MapCursor(Node<K, V> root, VersionedMap<K,V> map) {
+                // Initializing tree stack
+                super();
+                this.nodeStack = new ArrayDeque<>();
+                this.nodeIndexStack = new ArrayDeque<>();
+                if(root != null) {
+                        this.nodeStack.add(root);
+                        this.nodeIndexStack.push(INDEX_START);
+                }
+                
+                this.dataIndex = INDEX_START;
+                
+                // Initializing cache
+                this.key = null;
+                this.value = null;
+                
+                // Initializing state
+                this.map=map;
+                this.creationHash = map.hashCode();
+        }
+        
+        public K getKey() {
+                return key;
+        }
+        
+        public V getValue() {
+                return value;
+        }
+        
+        public boolean isTerminated() {
+                return this.nodeStack.isEmpty();
+        }
+        
+        public boolean move() {
+                if(isDirty()) {
+                        throw new ConcurrentModificationException();
+                }
+                if(!isTerminated()) {
+                        boolean result = this.nodeStack.peek().moveToNext(this);
+                        if(this.nodeIndexStack.size() != this.nodeStack.size()) {
+                                throw new IllegalArgumentException("Node stack is corrupted by illegal moves!");
+                        }
+                        return result;
+                }
+                return false;
+        }
+        public boolean skipCurrentNode() {
+                nodeStack.pop();
+                nodeIndexStack.pop();
+                dataIndex = INDEX_FINISH;
+                return move();
+        }
+        @Override
+        public boolean isDirty() {
+                return this.map.hashCode() != this.creationHash;
+        }
+        @Override
+        public List<VersionedMap<?, ?>> getDependingMaps() {
+                return List.of(this.map);
+        }
+        
+        public static <K,V> boolean sameSubnode(MapCursor<K,V> cursor1, MapCursor<K,V> cursor2) {
+                Node<K, V> nodeOfCursor1 = cursor1.nodeStack.peek();
+                Node<K, V> nodeOfCursor2 = cursor2.nodeStack.peek();
+                if(nodeOfCursor1 != null && nodeOfCursor2 != null) {
+                        return nodeOfCursor1.equals(nodeOfCursor2);
+                } else {
+                        return false;
+                }
+        }
+        
+        /**
+         * 
+         * @param <K>
+         * @param <V>
+         * @param cursor1
+         * @param cursor2
+         * @return Positive number if cursor 1 is behind, negative number if cursor 2 is behind, and 0 if they are at the same position.
+         */
+        public static <K,V> int compare(MapCursor<K,V> cursor1, MapCursor<K,V> cursor2) {
+                // two cursors are equally deep
+                Iterator<Integer> stack1 = cursor1.nodeIndexStack.descendingIterator();
+                Iterator<Integer> stack2 = cursor2.nodeIndexStack.descendingIterator();
+                if(stack1.hasNext()) {
+                        if(!stack2.hasNext()) {
+                                // stack 2 has no more element, thus stack 1 is deeper
+                                return 1;
+                        }
+                        int val1 = stack1.next();
+                        int val2 = stack2.next();
+                        if(val1 < val2) {
+                                return -1;
+                        } else if(val2 < val1) {
+                                return 1;
+                        }
+                }
+                if(stack2.hasNext()) {
+                        // stack 2 has more element, thus stack 2 is deeper
+                        return 1;
+                }
+                return Integer.compare(cursor1.dataIndex, cursor2.dataIndex);
+        }
+}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/MapDiffCursor.java b/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/MapDiffCursor.java
new file mode 100644
index 00000000..e97e4aa1
--- /dev/null
+++ b/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/MapDiffCursor.java
@@ -0,0 +1,214 @@
+package org.eclipse.viatra.solver.data.map.internal;
+
+import java.util.List;
+import java.util.stream.Collectors;
+import java.util.stream.Stream;
+
+import org.eclipse.viatra.solver.data.map.ContinousHashProvider;
+import org.eclipse.viatra.solver.data.map.Cursor;
+import org.eclipse.viatra.solver.data.map.DiffCursor;
+import org.eclipse.viatra.solver.data.map.VersionedMap;
+
+/**
+ * A cursor representing the difference between two states of a map.
+ * @author Oszkar Semerath
+ *
+ */
+public class MapDiffCursor<K,V> implements DiffCursor<K, V>, Cursor<K,V>{
+        /**
+         * Default value representing missing elements.
+         */
+        private V defaultValue;
+        private MapCursor<K,V> cursor1;
+        private MapCursor<K,V> cursor2;
+        private ContinousHashProvider<? super K> hashProvider;
+        
+        // Values
+        private K key;
+        private V fromValue;
+        private V toValue;
+        
+        // State
+        /**
+         * Positive number if cursor 1 is behind, negative number if cursor 2 is behind, and 0 if they are at the same position.
+         */
+        private int cursorRelation;
+        /**
+         * Denotes a state when two cursors are in the same position, but they contain different keys.
+         * Possible values:
+         * <ul>
+         * <li>0: not stuck</li>
+         * <li>1: hashClash, next it should return the key of cursor 1.</li>
+         * <li>2: hashClash, next it should return the key of cursor 2.</li>
+         * </ul>
+         */
+        private int hashClash=0;
+        
+        public MapDiffCursor(ContinousHashProvider<? super K> hashProvider, V defaultValue, Cursor<K, V> cursor1, Cursor<K, V> cursor2) {
+                super();
+                this.hashProvider = hashProvider;
+                this.defaultValue = defaultValue;
+                this.cursor1 = (MapCursor<K, V>) cursor1;
+                this.cursor2 = (MapCursor<K, V>) cursor2;
+        }
+        @Override
+        public K getKey() {
+                return key;
+        }
+        @Override
+        public V getFromValue() {
+                return fromValue;
+        }
+        @Override
+        public V getToValue() {
+                return toValue;
+        }
+        @Override
+        public V getValue() {
+                return getToValue();
+        }
+        public boolean isTerminated() {
+                return cursor1.isTerminated() && cursor2.isTerminated();
+        }
+        @Override
+        public boolean isDirty() {
+                return this.cursor1.isDirty() || this.cursor2.isDirty();
+        }
+        @Override
+        public List<VersionedMap<?, ?>> getDependingMaps() {
+                return Stream.concat(
+                                cursor1.getDependingMaps().stream(),
+                                cursor2.getDependingMaps().stream()
+                        ).collect(Collectors.toList());
+        }
+        
+        protected void updateState() {
+                if(!isTerminated()) {
+                        this.cursorRelation = MapCursor.compare(cursor1, cursor2);
+                        if(cursorRelation > 0 || cursor2.isTerminated()) {
+                                this.key = cursor1.getKey();
+                                this.fromValue = cursor1.getValue();
+                                this.toValue = defaultValue;
+                        } else if(cursorRelation < 0 || cursor1.isTerminated()){
+                                this.key = cursor2.getKey();
+                                this.fromValue = defaultValue;
+                                this.toValue = cursor1.getValue();
+                        } else {
+                                // cursor1 = cursor2
+                                if(cursor1.getKey().equals(cursor2.getKey())) {
+                                        this.key = cursor1.getKey();
+                                        this.fromValue = cursor1.getValue();
+                                        this.toValue = defaultValue;
+                                } else {
+                                        resolveHashClash1();
+                                }
+                        }
+                }
+        }
+        protected void resolveHashClash1() {
+                int compareResult = this.hashProvider.compare(cursor1.key, cursor2.key);
+                if(compareResult<0) {
+                        this.hashClash = 2;
+                        this.cursorRelation = 0;
+                        this.key = cursor1.key;
+                        this.fromValue = cursor1.value;
+                        this.toValue = defaultValue;
+                } else if(compareResult>0) {
+                        this.hashClash = 1;
+                        this.cursorRelation = 0;
+                        this.key = cursor2.key;
+                        this.fromValue = defaultValue;
+                        this.toValue = cursor2.value;
+                } else {
+                        throw new IllegalArgumentException("Inconsistent compare result for diffcursor");
+                }
+        }
+        protected boolean isInHashClash() {
+                return this.hashClash != 0;
+        }
+        protected void resolveHashClash2() {
+                if(hashClash == 1) {
+                        this.hashClash = 0;
+                        this.cursorRelation = 0;
+                        this.key = cursor1.key;
+                        this.fromValue = cursor1.value;
+                        this.toValue = defaultValue;
+                } else if(hashClash == 2) {
+                        this.hashClash = 0;
+                        this.cursorRelation = 0;
+                        this.key = cursor2.key;
+                        this.fromValue = defaultValue;
+                        this.toValue = cursor2.value;
+                } else throw new IllegalArgumentException("Inconsistent compare result for diffcursor");
+        }
+
+        
+        protected boolean sameValues() {
+                if(this.fromValue == null) {
+                        return this.toValue == null;
+                } else {
+                        return this.fromValue.equals(this.toValue);
+                }
+        }
+        protected boolean moveOne() {
+                if(isTerminated()) {
+                        return false;
+                }
+                if(this.cursorRelation > 0 || cursor2.isTerminated()) {
+                        return cursor1.move();
+                } else if(this.cursorRelation < 0 || cursor1.isTerminated()) {
+                        return cursor2.move();
+                } else {
+                        boolean moved1 = cursor1.move();
+                        boolean moved2 = cursor2.move();
+                        return moved1 && moved2;
+                }
+        }
+        private boolean skipNode() {
+                if(isTerminated()) {
+                        throw new IllegalStateException("DiffCursor tries to skip when terminated!");
+                }
+                boolean update1 = cursor1.skipCurrentNode();
+                boolean update2 = cursor2.skipCurrentNode();
+                updateState();
+                return update1 && update2;
+        }
+        
+        protected boolean moveToConsistentState() {
+                if(!isTerminated()) {
+                        boolean changed;
+                        boolean lastResult = true;
+                        do {
+                                changed = false;
+                                if(MapCursor.sameSubnode(cursor1, cursor2)) {
+                                        lastResult = skipNode();
+                                        changed = true;
+                                }
+                                if(sameValues()) {
+                                        lastResult = moveOne();
+                                        changed = true;
+                                }
+                                updateState();
+                        } while(changed && !isTerminated());
+                        return lastResult;
+                } else {
+                        return false;
+                }
+        }
+        
+        public boolean move() {
+                if(!isTerminated()) {
+                        if(isInHashClash()) {
+                                this.resolveHashClash2();
+                                return true;
+                        } else {
+                                if(moveOne()) {
+                                        return moveToConsistentState();
+                                } else {
+                                        return false;
+                                }
+                        }
+                        
+                } else return false;
+        }
+}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/MutableNode.java b/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/MutableNode.java
new file mode 100644
index 00000000..9e63b941
--- /dev/null
+++ b/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/MutableNode.java
@@ -0,0 +1,449 @@
+package org.eclipse.viatra.solver.data.map.internal;
+
+import java.util.Arrays;
+import java.util.Map;
+
+import org.eclipse.viatra.solver.data.map.ContinousHashProvider;
+
+public class MutableNode<K, V> extends Node<K, V> {
+        int cachedHash;
+        protected Object[] content;
+
+        protected MutableNode() {
+                this.content = new Object[2 * FACTOR];
+                updateHash();
+        }
+
+        public static <K, V> MutableNode<K, V> initialize(K key, V value, ContinousHashProvider<? super K> hashProvider,
+                        V defaultValue) {
+                if (value == defaultValue) {
+                        return null;
+                } else {
+                        int hash = hashProvider.getHash(key, 0);
+                        int fragment = hashFragment(hash, 0);
+                        MutableNode<K, V> res = new MutableNode<>();
+                        res.content[2 * fragment] = key;
+                        res.content[2 * fragment + 1] = value;
+                        res.updateHash();
+                        return res;
+                }
+        }
+
+        /**
+         * Constructs a {@link MutableNode} as a copy of an {@link ImmutableNode}
+         * 
+         * @param node
+         */
+        protected MutableNode(ImmutableNode<K, V> node) {
+                this.content = new Object[2 * FACTOR];
+                int dataUsed = 0;
+                int nodeUsed = 0;
+                for (int i = 0; i < FACTOR; i++) {
+                        int bitposition = 1 << i;
+                        if ((node.dataMap & bitposition) != 0) {
+                                content[2 * i] = node.content[dataUsed * 2];
+                                content[2 * i + 1] = node.content[dataUsed * 2 + 1];
+                                dataUsed++;
+                        } else if ((node.nodeMap & bitposition) != 0) {
+                                content[2 * i + 1] = node.content[node.content.length - 1 - nodeUsed];
+                                nodeUsed++;
+                        }
+                }
+                this.cachedHash = node.hashCode();
+        }
+
+        @SuppressWarnings("unchecked")
+        @Override
+        public V getValue(K key, ContinousHashProvider<? super K> hashProvider, V defaultValue, int hash, int depth) {
+                int selectedHashFragment = hashFragment(hash, shiftDepth(depth));
+                K keyCandidate = (K) this.content[2 * selectedHashFragment];
+                if (keyCandidate != null) {
+                        if (keyCandidate.equals(key)) {
+                                return (V) this.content[2 * selectedHashFragment + 1];
+                        } else {
+                                return defaultValue;
+                        }
+                } else {
+                        Node<K, V> nodeCandidate = (Node<K, V>) content[2 * selectedHashFragment + 1];
+                        if (nodeCandidate != null) {
+                                int newDepth = depth + 1;
+                                int newHash = newHash(hashProvider, key, hash, newDepth);
+                                return nodeCandidate.getValue(key, hashProvider, defaultValue, newHash, newDepth);
+                        } else {
+                                return defaultValue;
+                        }
+                }
+        }
+
+        @SuppressWarnings("unchecked")
+        @Override
+        public Node<K, V> putValue(K key, V value, OldValueBox<V> oldValue, ContinousHashProvider<? super K> hashProvider, V defaultValue, int hash,
+                        int depth) {
+                int selectedHashFragment = hashFragment(hash, shiftDepth(depth));
+                K keyCandidate = (K) content[2 * selectedHashFragment];
+                if (keyCandidate != null) {
+                        // If has key
+                        if (keyCandidate.equals(key)) {
+                                // The key is equals to an existing key -> update entry
+                                if (value == defaultValue) {
+                                        return removeEntry(selectedHashFragment, oldValue);
+                                } else {
+                                        return updateValue(value, oldValue, selectedHashFragment);
+                                }
+                        } else {
+                                // The key is not equivalent to an existing key on the same hash bin
+                                // -> split entry if it is necessary
+                                if (value == defaultValue) {
+                                        // Value is default -> do not need to add new node
+                                        oldValue.setOldValue(defaultValue);
+                                        return this;
+                                } else {
+                                        // Value is not default -> Split entry data to a new node
+                                        oldValue.setOldValue(defaultValue);
+                                        return moveDownAndSplit(hashProvider, key, value, keyCandidate, hash, depth, selectedHashFragment);
+                                }
+                        }
+                } else {
+                        // If it does not have key, check for value
+                        Node<K, V> nodeCandidate = (Node<K, V>) content[2 * selectedHashFragment + 1];
+                        if (nodeCandidate != null) {
+                                // If it has value, it is a subnode -> upate that
+                                Node<K, V> newNode = nodeCandidate.putValue(key, value, oldValue, hashProvider, defaultValue,
+                                                newHash(hashProvider, key, hash, depth + 1), depth + 1);
+                                return updateWithSubNode(selectedHashFragment, newNode, value.equals(defaultValue));
+                        } else {
+                                // If it does not have value, put it in the empty place
+                                if (value == defaultValue) {
+                                        // dont need to add new key-value pair
+                                        oldValue.setOldValue(defaultValue);
+                                        return this;
+                                } else {
+                                        return addEntry(key, value, oldValue, selectedHashFragment);
+                                }
+
+                        }
+                }
+        }
+
+        @SuppressWarnings("unchecked")
+        private Node<K, V> addEntry(K key, V value, OldValueBox<V> oldValue, int selectedHashFragment) {
+                content[2 * selectedHashFragment] = key;
+                oldValue.setOldValue((V) content[2 * selectedHashFragment + 1]);
+                content[2 * selectedHashFragment + 1] = value;
+                updateHash();
+                return this;
+        }
+
+        /**
+         * Updates an entry in a selected hash-fragment to a non-default value.
+         * 
+         * @param value
+         * @param selectedHashFragment
+         * @return
+         */
+        @SuppressWarnings("unchecked")
+        Node<K, V> updateValue(V value, OldValueBox<V> oldValue, int selectedHashFragment) {
+                oldValue.setOldValue((V) content[2 * selectedHashFragment + 1]);
+                content[2 * selectedHashFragment + 1] = value;
+                updateHash();
+                return this;
+        }
+
+        /**
+         * 
+         * @param selectedHashFragment
+         * @param newNode
+         * @return
+         */
+        Node<K, V> updateWithSubNode(int selectedHashFragment, Node<K, V> newNode, boolean deletionHappened) {
+                if (deletionHappened) {
+                        if (newNode == null) {
+                                // Check whether this node become empty
+                                content[2 * selectedHashFragment + 1] = null; // i.e. the new node
+                                if (hasContent()) {
+                                        updateHash();
+                                        return this;
+                                } else {
+                                        return null;
+                                }
+                        } else {
+                                // check whether newNode is orphan
+                                MutableNode<K, V> immutableNewNode = newNode.isMutable();
+                                if (immutableNewNode != null) {
+                                        int orphaned = immutableNewNode.isOrphaned();
+                                        if (orphaned >= 0) {
+                                                // orphan subnode data is replaced with data
+                                                content[2 * selectedHashFragment] = immutableNewNode.content[orphaned * 2];
+                                                content[2 * selectedHashFragment + 1] = immutableNewNode.content[orphaned * 2 + 1];
+                                                updateHash();
+                                                return this;
+                                        }
+                                }
+                        }
+                }
+                // normal behaviour
+                content[2 * selectedHashFragment + 1] = newNode;
+                updateHash();
+                return this;
+
+        }
+
+        private boolean hasContent() {
+                for (Object element : this.content) {
+                        if (element != null)
+                                return true;
+                }
+                return false;
+        }
+
+        @Override
+        protected MutableNode<K, V> isMutable() {
+                return this;
+        }
+
+        protected int isOrphaned() {
+                int dataFound = -2;
+                for (int i = 0; i < FACTOR; i++) {
+                        if (content[i * 2] != null) {
+                                if (dataFound >= 0) {
+                                        return -1;
+                                } else {
+                                        dataFound = i;
+                                }
+                        } else if (content[i * 2 + 1] != null) {
+                                return -3;
+                        }
+                }
+                return dataFound;
+        }
+
+        @SuppressWarnings("unchecked")
+        private Node<K, V> moveDownAndSplit(ContinousHashProvider<? super K> hashProvider, K newKey, V newValue,
+                        K previousKey, int hashOfNewKey, int depth, int selectedHashFragmentOfCurrentDepth) {
+                V previousValue = (V) content[2 * selectedHashFragmentOfCurrentDepth + 1];
+
+                MutableNode<K, V> newSubNode = newNodeWithTwoEntries(hashProvider, previousKey, previousValue,
+                                hashProvider.getHash(previousKey, hashDepth(depth)), newKey, newValue, hashOfNewKey, depth + 1);
+
+                content[2 * selectedHashFragmentOfCurrentDepth] = null;
+                content[2 * selectedHashFragmentOfCurrentDepth + 1] = newSubNode;
+                updateHash();
+                return this;
+        }
+
+        private MutableNode<K, V> newNodeWithTwoEntries(ContinousHashProvider<? super K> hashProvider, K key1, V value1,
+                        int oldHash1, K key2, V value2, int oldHash2, int newdepth) {
+                int newHash1 = newHash(hashProvider, key1, oldHash1, newdepth);
+                int newHash2 = newHash(hashProvider, key2, oldHash2, newdepth);
+                int newFragment1 = hashFragment(newHash1, shiftDepth(newdepth));
+                int newFragment2 = hashFragment(newHash2, shiftDepth(newdepth));
+
+                MutableNode<K, V> subNode = new MutableNode<>();
+                if (newFragment1 != newFragment2) {
+                        subNode.content[newFragment1 * 2] = key1;
+                        subNode.content[newFragment1 * 2 + 1] = value1;
+
+                        subNode.content[newFragment2 * 2] = key2;
+                        subNode.content[newFragment2 * 2 + 1] = value2;
+                } else {
+                        MutableNode<K, V> subSubNode = newNodeWithTwoEntries(hashProvider, key1, value1, newHash1, key2, value2,
+                                        newHash2, newdepth + 1);
+                        subNode.content[newFragment1 * 2 + 1] = subSubNode;
+                }
+                subNode.updateHash();
+                return subNode;
+        }
+
+        @SuppressWarnings("unchecked")
+        Node<K, V> removeEntry(int selectedHashFragment, OldValueBox<V> oldValue) {
+                content[2 * selectedHashFragment] = null;
+                oldValue.setOldValue((V) content[2 * selectedHashFragment + 1]);
+                content[2 * selectedHashFragment + 1] = null;
+                if (hasContent()) {
+                        updateHash();
+                        return this;
+                } else {
+                        return null;
+                }
+        }
+
+        @SuppressWarnings("unchecked")
+        @Override
+        public long getSize() {
+                int size = 0;
+                for (int i = 0; i < FACTOR; i++) {
+                        if (content[i * 2] != null) {
+                                size++;
+                        } else {
+                                Node<K, V> nodeCandidate = (Node<K, V>) content[i * 2 + 1];
+                                if (nodeCandidate != null) {
+                                        size += nodeCandidate.getSize();
+                                }
+                        }
+                }
+                return size;
+        }
+
+        @Override
+        protected MutableNode<K, V> toMutable() {
+                return this;
+        }
+
+        @Override
+        public ImmutableNode<K, V> toImmutable(Map<Node<K, V>, ImmutableNode<K, V>> cache) {
+                return ImmutableNode.constructImmutable(this, cache);
+        }
+
+        @SuppressWarnings("unchecked")
+        @Override
+        boolean moveToNext(MapCursor<K, V> cursor) {
+                // 1. try to move to data
+                if (cursor.dataIndex != MapCursor.INDEX_FINISH) {
+                        for (int index = cursor.dataIndex + 1; index < FACTOR; index++) {
+                                if (this.content[index * 2] != null) {
+                                        // 1.1 found next data
+                                        cursor.dataIndex = index;
+                                        cursor.key = (K) this.content[index * 2];
+                                        cursor.value = (V) this.content[index * 2 + 1];
+                                        return true;
+                                }
+                        }
+                        cursor.dataIndex = MapCursor.INDEX_FINISH;
+                }
+
+                // 2. look inside the subnodes
+                for (int index = cursor.nodeIndexStack.peek() + 1; index < FACTOR; index++) {
+                        if (this.content[index * 2] == null && this.content[index * 2 + 1] != null) {
+                                // 2.1 found next subnode, move down to the subnode
+                                Node<K, V> subnode = (Node<K, V>) this.content[index * 2 + 1];
+
+                                cursor.dataIndex = MapCursor.INDEX_START;
+                                cursor.nodeIndexStack.pop();
+                                cursor.nodeIndexStack.push(index);
+                                cursor.nodeIndexStack.push(MapCursor.INDEX_START);
+                                cursor.nodeStack.push(subnode);
+
+                                return subnode.moveToNext(cursor);
+                        }
+                }
+                // 3. no subnode found, move up
+                cursor.nodeStack.pop();
+                cursor.nodeIndexStack.pop();
+                if (!cursor.nodeStack.isEmpty()) {
+                        Node<K, V> supernode = cursor.nodeStack.peek();
+                        return supernode.moveToNext(cursor);
+                } else {
+                        cursor.key = null;
+                        cursor.value = null;
+                        return false;
+                }
+        }
+
+        @Override
+        public void prettyPrint(StringBuilder builder, int depth, int code) {
+                for (int i = 0; i < depth; i++) {
+                        builder.append("\t");
+                }
+                if (code >= 0) {
+                        builder.append(code);
+                        builder.append(":");
+                }
+                builder.append("Mutable(");
+                // print content
+                boolean hadContent = false;
+                for (int i = 0; i < FACTOR; i++) {
+                        if (content[2 * i] != null) {
+                                if (hadContent) {
+                                        builder.append(",");
+                                }
+                                builder.append(i);
+                                builder.append(":[");
+                                builder.append(content[2 * i].toString());
+                                builder.append("]->[");
+                                builder.append(content[2 * i + 1].toString());
+                                builder.append("]");
+                                hadContent = true;
+                        }
+                }
+                builder.append(")");
+                // print subnodes
+                for (int i = 0; i < FACTOR; i++) {
+                        if (content[2 * i] == null && content[2 * i + 1] != null) {
+                                @SuppressWarnings("unchecked")
+                                Node<K, V> subNode = (Node<K, V>) content[2 * i + 1];
+                                builder.append("\n");
+                                subNode.prettyPrint(builder, depth + 1, i);
+                        }
+                }
+        }
+
+        @SuppressWarnings({ "unchecked" })
+        @Override
+        public void checkIntegrity(ContinousHashProvider<? super K> hashProvider, V defaultValue, int depth) {
+                // check for orphan nodes
+                if (depth > 0) {
+                        int orphaned = isOrphaned();
+                        if (orphaned >= 0) {
+                                throw new IllegalStateException("Orphaned node! " + orphaned + ": " + content[2 * orphaned]);
+                        }
+                }
+                // check the place of data
+                for (int i = 0; i < FACTOR; i++) {
+                        if (this.content[2 * i] != null) {
+                                K key = (K) this.content[2 * i];
+                                V value = (V) this.content[2 * i + 1];
+
+                                if (value == defaultValue) {
+                                        throw new IllegalStateException("Node contains default value!");
+                                }
+                                int hashCode = hashProvider.getHash(key, hashDepth(depth));
+                                int shiftDepth = shiftDepth(depth);
+                                int selectedHashFragment = hashFragment(hashCode, shiftDepth);
+                                if (i != selectedHashFragment) {
+                                        throw new IllegalStateException("Key " + key + " with hash code " + hashCode
+                                                        + " is in bad place! Fragment=" + selectedHashFragment + ", Place=" + i);
+                                }
+                        }
+                }
+                // check subnodes
+                for (int i = 0; i < FACTOR; i++) {
+                        if (this.content[2 * i + 1] != null && this.content[2 * i] == null) {
+                                Node<K, V> subNode = (Node<K, V>) this.content[2 * i + 1];
+                                subNode.checkIntegrity(hashProvider, defaultValue, depth + 1);
+                        }
+                }
+                // check the hash
+                int oldHash = this.cachedHash;
+                updateHash();
+                int newHash = this.cachedHash;
+                if (oldHash != newHash) {
+                        throw new IllegalStateException("Hash code was not up to date! (old=" + oldHash + ",new=" + newHash + ")");
+                }
+        }
+
+        protected void updateHash() {
+                this.cachedHash = Arrays.hashCode(content);
+        }
+
+        @Override
+        public int hashCode() {
+                return this.cachedHash;
+        }
+
+        @Override
+        public boolean equals(Object obj) {
+                if (this == obj)
+                        return true;
+                if (obj == null)
+                        return false;
+                if (obj instanceof MutableNode<?, ?>) {
+                        MutableNode<?, ?> other = (MutableNode<?, ?>) obj;
+                        return Arrays.deepEquals(this.content, other.content);
+                } else if (obj instanceof ImmutableNode<?, ?>) {
+                        ImmutableNode<?, ?> other = (ImmutableNode<?, ?>) obj;
+                        return ImmutableNode.compareImmutableMutable(other, this);
+                } else {
+                        return false;
+                }
+        }
+}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/Node.java b/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/Node.java
new file mode 100644
index 00000000..d40f980a
--- /dev/null
+++ b/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/Node.java
@@ -0,0 +1,85 @@
+package org.eclipse.viatra.solver.data.map.internal;
+
+import java.util.Map;
+
+import org.eclipse.viatra.solver.data.map.ContinousHashProvider;
+
+public abstract class Node<K,V>{
+        public static final int BRANCHING_FACTOR_BITS = 5;
+        public static final int FACTOR = 1<<BRANCHING_FACTOR_BITS;
+        protected static final int NUMBER_OF_FACTORS = Integer.SIZE / BRANCHING_FACTOR_BITS;
+        protected static final int FACTOR_MASK = FACTOR-1;
+        public static final int EFFECTIVE_BITS = BRANCHING_FACTOR_BITS * NUMBER_OF_FACTORS;
+        
+        /**
+         * Calculates the index for the continuous hash.
+         * @param depth The depth of the node in the tree.
+         * @return The index of the continuous hash.
+         */
+        protected static int hashDepth(int depth) {
+                return depth/NUMBER_OF_FACTORS;
+        }
+        
+        /**
+         * Calculates the which segment of a single hash should be used.
+         * @param depth The depth of the node in the tree. 
+         * @return The segment of a hash code.
+         */
+        protected static int shiftDepth(int depth) {
+                return depth%NUMBER_OF_FACTORS;
+        }
+        /**
+         * Selects a segments from a complete hash for a given depth.
+         * @param hash A complete hash.
+         * @param shiftDepth The index of the segment.
+         * @return The segment as an integer.
+         */
+        protected static int hashFragment(int hash, int shiftDepth) {
+                if(shiftDepth<0 || Node.NUMBER_OF_FACTORS<shiftDepth) throw new IllegalArgumentException("Invalid shift depth! valid intervall=[0;5], input="+shiftDepth);
+                return (hash >>> shiftDepth*BRANCHING_FACTOR_BITS) & FACTOR_MASK;
+        }
+        
+        /**
+         * Returns the hash code for a given depth. It may calculate new hash code, or reuse a hash code calculated for depth-1.
+         * @param key The key.
+         * @param hash Hash code for depth-1
+         * @param depth The depth.
+         * @return The new hash code.
+         */
+        protected int newHash(final ContinousHashProvider<? super K> hashProvider, K key, int hash, int depth) {
+                final int hashDepth = hashDepth(depth);
+                if(hashDepth>=ContinousHashProvider.MAX_PRACTICAL_DEPTH) {
+                        throw new IllegalArgumentException("Key "+key+" have the clashing hashcode over the practical depth limitation ("+ContinousHashProvider.MAX_PRACTICAL_DEPTH+")!");
+                }
+                return depth%NUMBER_OF_FACTORS == 0?
+                                hashProvider.getHash(key, hashDepth) :
+                                hash;
+        }
+        
+        
+        public abstract V getValue(K key, ContinousHashProvider<? super K> hashProvider, V defaultValue,  int hash, int depth);
+        public abstract Node<K,V> putValue(K key, V value, OldValueBox<V> old, ContinousHashProvider<? super K> hashProvider, V defaultValue, int hash, int depth);
+        public abstract long getSize();
+        
+        abstract MutableNode<K, V> toMutable();
+        public abstract ImmutableNode<K, V> toImmutable(
+                        Map<Node<K, V>,ImmutableNode<K, V>> cache);
+        protected abstract MutableNode<K, V> isMutable();
+        /**
+         * Moves a {@link MapCursor} to its next position.
+         * @param cursor the cursor
+         * @return Whether there was a next value to move on.
+         */
+        abstract boolean moveToNext(MapCursor<K,V> cursor);
+        
+        ///////// FOR printing
+        public abstract void prettyPrint(StringBuilder builder, int depth, int code);
+        @Override
+        public String toString() {
+                StringBuilder stringBuilder = new StringBuilder();
+                prettyPrint(stringBuilder, 0, -1);
+                return stringBuilder.toString();
+        }
+        public void checkIntegrity(ContinousHashProvider<? super K> hashProvider, V defaultValue, int depth) {}
+        
+}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/OldValueBox.java b/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/OldValueBox.java
new file mode 100644
index 00000000..23502857
--- /dev/null
+++ b/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/OldValueBox.java
@@ -0,0 +1,19 @@
+package org.eclipse.viatra.solver.data.map.internal;
+
+public class OldValueBox<V>{
+        V oldValue;
+        boolean isSet = false;
+
+        public V getOldValue() {
+                if(!isSet) throw new IllegalStateException();
+                isSet = false;
+                return oldValue;
+        }
+
+        public void setOldValue(V ouldValue) {
+                if(isSet) throw new IllegalStateException();
+                this.oldValue = ouldValue;
+                isSet = true;
+        }
+        
+}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/VersionedMapImpl.java b/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/VersionedMapImpl.java
new file mode 100644
index 00000000..de41e602
--- /dev/null
+++ b/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/VersionedMapImpl.java
@@ -0,0 +1,171 @@
+package org.eclipse.viatra.solver.data.map.internal;
+
+import java.util.Iterator;
+import java.util.LinkedList;
+import java.util.List;
+
+import org.eclipse.viatra.solver.data.map.ContinousHashProvider;
+import org.eclipse.viatra.solver.data.map.Cursor;
+import org.eclipse.viatra.solver.data.map.DiffCursor;
+import org.eclipse.viatra.solver.data.map.VersionedMap;
+import org.eclipse.viatra.solver.data.map.VersionedMapStoreImpl;
+
+/**
+ * Not threadSafe in itself
+ * @author Oszkar Semerath
+ *
+ * @param <K>
+ * @param <V>
+ */
+public class VersionedMapImpl<K,V> implements VersionedMap<K,V>{
+        protected final VersionedMapStoreImpl<K,V> store;
+        
+        protected final ContinousHashProvider<K> hashProvider;
+        protected final V defaultValue;
+        protected Node<K,V> root;
+        
+        private OldValueBox<V> oldValueBox = new OldValueBox<>();
+        
+        public VersionedMapImpl(
+                        VersionedMapStoreImpl<K,V> store,
+                        ContinousHashProvider<K> hashProvider,
+                        V defaultValue)
+        {
+                this.store = store;
+                this.hashProvider = hashProvider;
+                this.defaultValue = defaultValue;
+                this.root = null;
+        }
+        public VersionedMapImpl(
+                        VersionedMapStoreImpl<K,V> store,
+                        ContinousHashProvider<K> hashProvider,
+                        V defaultValue, Node<K,V> data)
+        {
+                this.store = store;
+                this.hashProvider = hashProvider;
+                this.defaultValue = defaultValue;
+                this.root = data;
+        }
+                
+        public V getDefaultValue() {
+                return defaultValue;
+        }
+        public ContinousHashProvider<K> getHashProvider() {
+                return hashProvider;
+        }
+        @Override
+        public V put(K key, V value) {
+                if(root!=null) {
+                        root = root.putValue(key, value, oldValueBox, hashProvider, defaultValue, hashProvider.getHash(key, 0), 0);
+                        return oldValueBox.getOldValue();
+                } else {
+                        root = MutableNode.initialize(key, value, hashProvider, defaultValue);
+                        return defaultValue;
+                }
+        }
+        
+        @Override
+        public void putAll(Cursor<K, V> cursor) {
+                if(cursor.getDependingMaps().contains(this)) {
+                        List<K> keys = new LinkedList<>();
+                        List<V> values = new LinkedList<>();
+                        while(cursor.move()) {
+                                keys.add(cursor.getKey());
+                                values.add(cursor.getValue());
+                        }
+                        Iterator<K> keyIterator = keys.iterator();
+                        Iterator<V> valueIterator = values.iterator();
+                        while(keyIterator.hasNext()) {
+                                this.put(keyIterator.next(), valueIterator.next());
+                        }
+                } else {
+                        while(cursor.move()) {
+                                this.put(cursor.getKey(), cursor.getValue());
+                        }
+                }
+        }
+        
+        @Override
+        public V get(K key) {
+                if(root!=null) {
+                        return root.getValue(key, hashProvider, defaultValue, hashProvider.getHash(key, 0), 0);
+                } else {
+                        return defaultValue;
+                }
+        }
+        @Override
+        public long getSize() {
+                if(root == null) {
+                        return 0;
+                } else {
+                        return root.getSize();
+                }
+        }
+
+        @Override
+        public Cursor<K, V> getAll() {
+                return new MapCursor<>(this.root,this);
+        }
+        @Override
+        public DiffCursor<K, V> getDiffCursor(long toVersion) {
+                Cursor<K, V> fromCursor = this.getAll();
+                VersionedMap<K, V> toMap = this.store.createMap(toVersion);
+                Cursor<K, V> toCursor = toMap.getAll();
+                return new MapDiffCursor<>(this.hashProvider,this.defaultValue, fromCursor, toCursor);
+                
+        }
+        
+
+        @Override
+        public long commit() {
+                return this.store.commit(root,this);
+        }
+        public void setRoot(Node<K, V> root) {
+                this.root = root;
+        }
+
+        @Override
+        public void restore(long state) {
+                root = this.store.revert(state);
+        }
+        
+        @Override
+        public int hashCode() {
+                final int prime = 31;
+                int result = 1;
+                result = prime * result + ((root == null) ? 0 : root.hashCode());
+                return result;
+        }
+        
+        @Override
+        public boolean equals(Object obj) {
+                if (this == obj)
+                        return true;
+                if (obj == null)
+                        return false;
+                if (getClass() != obj.getClass())
+                        return false;
+                VersionedMapImpl<?,?> other = (VersionedMapImpl<?,?>) obj;
+                if (root == null) {
+                        if (other.root != null)
+                                return false;
+                } else if (!root.equals(other.root))
+                        return false;
+                return true;
+        }
+        public void prettyPrint() {
+                StringBuilder s = new StringBuilder();
+                if(this.root != null) {
+                        this.root.prettyPrint(s, 0, -1);
+                        System.out.println(s.toString());
+                } else {
+                        System.out.println("empty tree");
+                }
+        }
+        public void checkIntegrity() {
+                if(this.root != null) {
+                        this.root.checkIntegrity(hashProvider, defaultValue, 0);
+                }
+        }
+
+}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/model/Model.java b/store/src/main/java/org/eclipse/viatra/solver/data/model/Model.java
new file mode 100644
index 00000000..2b21e3e7
--- /dev/null
+++ b/store/src/main/java/org/eclipse/viatra/solver/data/model/Model.java
@@ -0,0 +1,20 @@
+package org.eclipse.viatra.solver.data.model;
+
+import java.util.Set;
+
+import org.eclipse.viatra.solver.data.map.Cursor;
+import org.eclipse.viatra.solver.data.map.Versioned;
+import org.eclipse.viatra.solver.data.model.representation.DataRepresentation;
+
+public interface Model extends Versioned{
+        @SuppressWarnings("squid:S1452")
+        Set<DataRepresentation<?, ?>> getDataRepresentations();
+        
+        <K,V> V get(DataRepresentation<K,V> representation, K key);
+        <K,V> Cursor<K,V> getAll(DataRepresentation<K,V> representation);
+        <K,V> V put(DataRepresentation<K,V> representation, K key, V value);
+        <K,V> void putAll(DataRepresentation<K,V> representation, Cursor<K,V> cursor);
+        <K,V> long getSize(DataRepresentation<K,V> representation);
+        
+        ModelDiffCursor getDiffCursor(long to);
+}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/model/ModelCursor.java b/store/src/main/java/org/eclipse/viatra/solver/data/model/ModelCursor.java
new file mode 100644
index 00000000..3157c9f0
--- /dev/null
+++ b/store/src/main/java/org/eclipse/viatra/solver/data/model/ModelCursor.java
@@ -0,0 +1,25 @@
+package org.eclipse.viatra.solver.data.model;
+
+import java.util.Map;
+
+import org.eclipse.viatra.solver.data.map.Cursor;
+import org.eclipse.viatra.solver.data.model.representation.DataRepresentation;
+
+public class ModelCursor {
+        final Map<DataRepresentation<?, ?>,Cursor<?,?>> cursors;
+
+        public ModelCursor(Map<DataRepresentation<?, ?>, Cursor<?, ?>> cursors) {
+                super();
+                this.cursors = cursors;
+        }
+        
+        @SuppressWarnings("unchecked")
+        public <K,V> Cursor<K,V> getCursor(DataRepresentation<K, V> representation) {
+                Cursor<?, ?> cursor = cursors.get(representation);
+                if(cursor != null) {
+                        return (Cursor<K, V>) cursor;
+                } else {
+                        throw new IllegalArgumentException("ModelCursor does not contain cursor for representation "+representation);
+                }
+        }
+}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/model/ModelDiffCursor.java b/store/src/main/java/org/eclipse/viatra/solver/data/model/ModelDiffCursor.java
new file mode 100644
index 00000000..d3551e47
--- /dev/null
+++ b/store/src/main/java/org/eclipse/viatra/solver/data/model/ModelDiffCursor.java
@@ -0,0 +1,26 @@
+package org.eclipse.viatra.solver.data.model;
+
+import java.util.Map;
+
+import org.eclipse.viatra.solver.data.map.Cursor;
+import org.eclipse.viatra.solver.data.map.DiffCursor;
+import org.eclipse.viatra.solver.data.model.representation.DataRepresentation;
+
+public class ModelDiffCursor {
+        final Map<DataRepresentation<?, ?>,DiffCursor<?,?>> diffcursors;
+
+        public ModelDiffCursor(Map<DataRepresentation<?, ?>, DiffCursor<?, ?>> diffcursors) {
+                super();
+                this.diffcursors = diffcursors;
+        }
+        
+        @SuppressWarnings("unchecked")
+        public <K,V> DiffCursor<K,V> getCursor(DataRepresentation<K, V> representation) {
+                Cursor<?, ?> cursor = diffcursors.get(representation);
+                if(cursor != null) {
+                        return (DiffCursor<K, V>) cursor;
+                } else {
+                        throw new IllegalArgumentException("ModelCursor does not contain cursor for representation "+representation);
+                }
+        }
+}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/model/ModelStore.java b/store/src/main/java/org/eclipse/viatra/solver/data/model/ModelStore.java
new file mode 100644
index 00000000..35ac72b5
--- /dev/null
+++ b/store/src/main/java/org/eclipse/viatra/solver/data/model/ModelStore.java
@@ -0,0 +1,16 @@
+package org.eclipse.viatra.solver.data.model;
+
+import java.util.Set;
+
+import org.eclipse.viatra.solver.data.model.representation.DataRepresentation;
+
+public interface ModelStore {
+        @SuppressWarnings("squid:S1452")
+        Set<DataRepresentation<?, ?>> getDataRepresentations();
+        
+        Model createModel();
+        Model createModel(long state);
+        
+        Set<Long> getStates();
+        ModelDiffCursor getDiffCursor(long from, long to);
+}
\ No newline at end of file
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/model/ModelStoreImpl.java b/store/src/main/java/org/eclipse/viatra/solver/data/model/ModelStoreImpl.java
new file mode 100644
index 00000000..f5e3b141
--- /dev/null
+++ b/store/src/main/java/org/eclipse/viatra/solver/data/model/ModelStoreImpl.java
@@ -0,0 +1,127 @@
+package org.eclipse.viatra.solver.data.model;
+
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Map;
+import java.util.Map.Entry;
+import java.util.Set;
+
+import org.eclipse.viatra.solver.data.map.ContinousHashProvider;
+import org.eclipse.viatra.solver.data.map.DiffCursor;
+import org.eclipse.viatra.solver.data.map.VersionedMap;
+import org.eclipse.viatra.solver.data.map.VersionedMapStore;
+import org.eclipse.viatra.solver.data.map.VersionedMapStoreImpl;
+import org.eclipse.viatra.solver.data.model.internal.ModelImpl;
+import org.eclipse.viatra.solver.data.model.internal.SimilarRelationEquivalenceClass;
+import org.eclipse.viatra.solver.data.model.representation.AuxilaryData;
+import org.eclipse.viatra.solver.data.model.representation.DataRepresentation;
+import org.eclipse.viatra.solver.data.model.representation.Relation;
+
+public class ModelStoreImpl implements ModelStore {
+
+        private final Map<DataRepresentation<?, ?>, VersionedMapStore<?, ?>> stores;
+
+        public ModelStoreImpl(Set<DataRepresentation<?, ?>> dataRepresentations) {
+                stores = initStores(dataRepresentations);
+        }
+
+        private Map<DataRepresentation<?, ?>, VersionedMapStore<?, ?>> initStores(
+                        Set<DataRepresentation<?, ?>> dataRepresentations) {
+                Map<DataRepresentation<?, ?>, VersionedMapStore<?, ?>> result = new HashMap<>();
+
+                Map<SimilarRelationEquivalenceClass, List<Relation<?>>> symbolRepresentationsPerHashPerArity = new HashMap<>();
+
+                for (DataRepresentation<?, ?> dataRepresentation : dataRepresentations) {
+                        if (dataRepresentation instanceof Relation<?>) {
+                                Relation<?> symbolRepresentation = (Relation<?>) dataRepresentation;
+                                addOrCreate(symbolRepresentationsPerHashPerArity,
+                                                new SimilarRelationEquivalenceClass(symbolRepresentation), symbolRepresentation);
+                        } else if (dataRepresentation instanceof AuxilaryData<?, ?>) {
+                                VersionedMapStoreImpl<?, ?> store = new VersionedMapStoreImpl<>(dataRepresentation.getHashProvider(),
+                                                dataRepresentation.getDefaultValue());
+                                result.put(dataRepresentation, store);
+                        } else {
+                                throw new UnsupportedOperationException(
+                                                "Model store does not have strategy to use " + dataRepresentation.getClass() + "!");
+                        }
+                }
+                for (List<Relation<?>> symbolGroup : symbolRepresentationsPerHashPerArity.values()) {
+                        initRepresentationGroup(result, symbolGroup);
+                }
+
+                return result;
+        }
+
+        private void initRepresentationGroup(Map<DataRepresentation<?, ?>, VersionedMapStore<?, ?>> result,
+                        List<Relation<?>> symbolGroup) {
+                final ContinousHashProvider<Tuple> hashProvider = symbolGroup.get(0).getHashProvider();
+                final Object defaultValue = symbolGroup.get(0).getDefaultValue();
+                
+                List<VersionedMapStore<Tuple, Object>> maps = VersionedMapStoreImpl
+                                .createSharedVersionedMapStores(symbolGroup.size(), hashProvider, defaultValue);
+                
+                for (int i = 0; i < symbolGroup.size(); i++) {
+                        result.put(symbolGroup.get(i), maps.get(i));
+                }
+        }
+
+        private static <K, V> void addOrCreate(Map<K, List<V>> map, K key, V value) {
+                List<V> list;
+                if (map.containsKey(key)) {
+                        list = map.get(key);
+                } else {
+                        list = new LinkedList<>();
+                        map.put(key, list);
+                }
+                list.add(value);
+        }
+
+        @Override
+        public Set<DataRepresentation<?, ?>> getDataRepresentations() {
+                return this.stores.keySet();
+        }
+
+        @Override
+        public ModelImpl createModel() {
+                Map<DataRepresentation<?, ?>, VersionedMap<?, ?>> maps = new HashMap<>();
+                for (Entry<DataRepresentation<?, ?>, VersionedMapStore<?, ?>> entry : this.stores.entrySet()) {
+                        maps.put(entry.getKey(), entry.getValue().createMap());
+                }
+                return new ModelImpl(this, maps);
+        }
+
+        @Override
+        public synchronized ModelImpl createModel(long state) {
+                Map<DataRepresentation<?, ?>, VersionedMap<?, ?>> maps = new HashMap<>();
+                for (Entry<DataRepresentation<?, ?>, VersionedMapStore<?, ?>> entry : this.stores.entrySet()) {
+                        maps.put(entry.getKey(), entry.getValue().createMap(state));
+                }
+                return new ModelImpl(this, maps);
+        }
+        
+        @Override
+        @SuppressWarnings("squid:S1751")
+        public synchronized Set<Long> getStates() {
+                // if not empty, return first
+                for(VersionedMapStore<?, ?> store : stores.values()) {
+                        return new HashSet<>(store.getStates());
+                }
+                // if empty
+                Set<Long> result = new HashSet<>();
+                result.add(0l);
+                return result;
+        }
+
+        @Override
+        public synchronized ModelDiffCursor getDiffCursor(long from, long to) {
+                Map<DataRepresentation<?, ?>,DiffCursor<?,?>> diffcursors = new HashMap<>();
+                for(Entry<DataRepresentation<?, ?>, VersionedMapStore<?, ?>> entry : stores.entrySet()) {
+                        DataRepresentation<?, ?> representation = entry.getKey();
+                        DiffCursor<?, ?> diffCursor = entry.getValue().getDiffCursor(from, to);
+                        diffcursors.put(representation, diffCursor);
+                }
+                return new ModelDiffCursor(diffcursors);
+        }
+}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/model/Tuple.java b/store/src/main/java/org/eclipse/viatra/solver/data/model/Tuple.java
new file mode 100644
index 00000000..ca6548a4
--- /dev/null
+++ b/store/src/main/java/org/eclipse/viatra/solver/data/model/Tuple.java
@@ -0,0 +1,148 @@
+package org.eclipse.viatra.solver.data.model;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.List;
+
+public abstract class Tuple {
+        private static final int CUSTOMTUPLESIZE = 2;
+        protected static final List<Tuple1> tuple1Cash = new ArrayList<>(1024);
+        
+        public abstract int getSize();
+        public abstract int get(int element);
+        public abstract int[] toArray();
+        
+        @Override
+        public String toString() {
+                StringBuilder b = new StringBuilder();
+                b.append("[");
+                for(int i = 0; i<getSize(); i++) {
+                        if(i!=0) {
+                                b.append(",");
+                        }
+                        b.append(get(i));
+                }
+                b.append("]");
+                return b.toString();
+        }
+        
+        public static Tuple1 of1(int value) {
+                if(value < tuple1Cash.size()) {
+                        return tuple1Cash.get(value);
+                } else {
+                        Tuple1 newlyCreated = null;
+                        while(value >= tuple1Cash.size()) {
+                                newlyCreated = new Tuple1(tuple1Cash.size());
+                                tuple1Cash.add(newlyCreated);
+                        }
+                        return newlyCreated;
+                }
+        }
+        
+        public static Tuple of(int... values) {
+                if(values.length == 0) {
+                        return new Tuple0();
+                } else if(values.length == 1) {
+                        return of1(values[0]);
+                } else if(values.length == 2) {
+                        return new Tuple2(values[0],values[1]);
+                } else return new TupleN(values);
+        }
+        
+        protected IllegalArgumentException doesNotContain(int element) {
+                return new IllegalArgumentException("Tuple does not contain element "+element);
+        }
+        
+        public static class Tuple0 extends Tuple{
+                protected Tuple0() { }
+                @Override public int getSize() { return 0; }
+                @Override public int get(int element) {
+                        throw doesNotContain(element);
+                }
+                @Override public int[] toArray() {return new int[]{};}
+                @Override public int hashCode() { return TupleHashProvider.singleton().getHash(this, 0); }
+                @Override
+                public boolean equals(Object obj) {
+                        if (this == obj)
+                                return true;
+                        if (obj == null)
+                                return false;
+                        if (getClass() != obj.getClass())
+                                return false;
+                        return true;
+                }
+        }
+        public static class Tuple1 extends Tuple{
+                final int value0;
+                protected Tuple1(int value0) { this.value0 = value0; }
+                @Override public int getSize() { return 1; }
+                @Override public int get(int element) {
+                        if(element == 0) return value0;
+                        throw doesNotContain(element);
+                }
+                @Override public int[] toArray() {return new int[]{ value0 };}
+                @Override public int hashCode() { return TupleHashProvider.singleton().getHash(this, 0); }
+                @Override
+                public boolean equals(Object obj) {
+                        if (this == obj)
+                                return true;
+                        if (obj == null)
+                                return false;
+                        if (getClass() != obj.getClass())
+                                return false;
+                        Tuple1 other = (Tuple1) obj;
+                        return value0 == other.value0;
+                }
+        }
+        public static class Tuple2 extends Tuple{
+                final int value0;
+                final int value1;
+                protected Tuple2(int value0, int value1) { this.value0 = value0; this.value1 = value1; }
+                @Override public int getSize() { return 2; }
+                @Override public int get(int element) {
+                        if(element == 0) return value0;
+                        else if(element == 1) return value1;
+                        throw doesNotContain(element);
+                }
+                @Override public int[] toArray() {return new int[]{ value0,value1 };}
+                @Override public int hashCode() { return TupleHashProvider.singleton().getHash(this, 0); }
+                @Override
+                public boolean equals(Object obj) {
+                        if (this == obj)
+                                return true;
+                        if (obj == null)
+                                return false;
+                        if (getClass() != obj.getClass())
+                                return false;
+                        Tuple2 other = (Tuple2) obj;
+                        return value0 == other.value0 && value1 == other.value1;
+                }
+        }
+        public static class TupleN extends Tuple{
+                final int[] values;
+                protected TupleN(int[] values) { 
+                        if(values.length<CUSTOMTUPLESIZE)
+                                throw new IllegalArgumentException();
+                        this.values = Arrays.copyOf(values, values.length);
+                }
+                @Override public int getSize() { return values.length; }
+                @Override public int get(int element) {
+                        if(0<=element && element < values.length) {
+                                return values[element];
+                        } else throw doesNotContain(element);
+                }
+                @Override public int[] toArray() { return values; }
+                @Override public int hashCode() { return TupleHashProvider.singleton().getHash(this, 0); }
+                @Override
+                public boolean equals(Object obj) {
+                        if (this == obj)
+                                return true;
+                        if (obj == null)
+                                return false;
+                        if (getClass() != obj.getClass())
+                                return false;
+                        TupleN other = (TupleN) obj;
+                        return Arrays.equals(values, other.values);
+                }
+        }
+}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/model/TupleHashProvider.java b/store/src/main/java/org/eclipse/viatra/solver/data/model/TupleHashProvider.java
new file mode 100644
index 00000000..6c37aa37
--- /dev/null
+++ b/store/src/main/java/org/eclipse/viatra/solver/data/model/TupleHashProvider.java
@@ -0,0 +1,65 @@
+package org.eclipse.viatra.solver.data.model;
+
+import org.eclipse.viatra.solver.data.map.ContinousHashProvider;
+
+public class TupleHashProvider implements ContinousHashProvider<Tuple> {
+        protected static TupleHashProvider instance;
+
+        public static TupleHashProvider singleton() {
+                if (instance == null) {
+                        instance = new TupleHashProvider();
+                }
+                return instance;
+        }
+
+        protected static final int[] primes = new int[] { 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101,
+                        103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211,
+                        223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337,
+                        347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461,
+                        463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601,
+                        607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739,
+                        743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881,
+                        883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021,
+                        1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151,
+                        1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283,
+                        1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429,
+                        1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549,
+                        1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667,
+                        1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811,
+                        1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973,
+                        1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089,
+                        2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243,
+                        2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377,
+                        2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531,
+                        2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677,
+                        2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791,
+                        2797, 2801, 2803, 2819, 3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209, 3217,
+                        3221, 3229, 3251, 3253, 3257, 3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331, 3343, 3347, 3359,
+                        3361, 3371, 3373, 3389, 3391, 3407, 3413, 3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499, 3511, 3517,
+                        3527, 3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571, 3581, 3583, 3593, 3607, 3613, 3617, 3623, 3631, 3637,
+                        3643, 3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709, 3719, 3727, 3733, 3739, 3761, 3767, 3769, 3779, 3793,
+                        3797, 3803, 3821, 3823, 3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889, 3907, 3911 };
+        
+        protected static final long LARGESTPRIME30BITS = 1073741789;
+
+        public TupleHashProvider() {
+                if (primes.length < MAX_PRACTICAL_DEPTH) {
+                        throw new UnsupportedOperationException(
+                                        "Not enough prime numbers to support the practical depth of continuous hash!");
+                }
+        }
+
+        @Override
+        public int getHash(Tuple key, int index) {
+                if (index >= primes.length) {
+                        throw new IllegalArgumentException("Not enough prime numbers to support index");
+                }
+                long accumulator = 0;
+                final int prime = primes[index];
+                for (int i = 0; i < key.getSize(); i++) {
+                        accumulator = (prime * accumulator + key.get(i)) % LARGESTPRIME30BITS;
+                }
+
+                return (int) accumulator;
+        }
+}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/model/TupleHashProviderBitMagic.java b/store/src/main/java/org/eclipse/viatra/solver/data/model/TupleHashProviderBitMagic.java
new file mode 100644
index 00000000..2a514d66
--- /dev/null
+++ b/store/src/main/java/org/eclipse/viatra/solver/data/model/TupleHashProviderBitMagic.java
@@ -0,0 +1,28 @@
+package org.eclipse.viatra.solver.data.model;
+
+import org.eclipse.viatra.solver.data.map.ContinousHashProvider;
+
+public class TupleHashProviderBitMagic implements ContinousHashProvider<Tuple> {
+
+        @Override
+        public int getHash(Tuple key, int index) {
+                if(key.getSize() == 1) {
+                        return key.get(0);
+                }
+                
+                int result = 0;
+                final int startBitIndex = index*30;
+                final int finalBitIndex = startBitIndex+30;
+                final int arity = key.getSize();
+                
+                for(int i = startBitIndex; i<=finalBitIndex; i++) {
+                        final int selectedKey = key.get(i%arity);
+                        final int selectedPosition = 1<<(i/arity);
+                        if((selectedKey&selectedPosition) != 0) {
+                                result |= 1<<(i%30);
+                        }
+                }
+                
+                return result;
+        }
+}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/model/internal/ModelImpl.java b/store/src/main/java/org/eclipse/viatra/solver/data/model/internal/ModelImpl.java
new file mode 100644
index 00000000..6d7f4e97
--- /dev/null
+++ b/store/src/main/java/org/eclipse/viatra/solver/data/model/internal/ModelImpl.java
@@ -0,0 +1,124 @@
+package org.eclipse.viatra.solver.data.model.internal;
+
+import java.util.HashMap;
+import java.util.Map;
+import java.util.Set;
+
+import org.eclipse.viatra.solver.data.map.ContinousHashProvider;
+import org.eclipse.viatra.solver.data.map.Cursor;
+import org.eclipse.viatra.solver.data.map.DiffCursor;
+import org.eclipse.viatra.solver.data.map.VersionedMap;
+import org.eclipse.viatra.solver.data.map.internal.MapDiffCursor;
+import org.eclipse.viatra.solver.data.model.Model;
+import org.eclipse.viatra.solver.data.model.ModelDiffCursor;
+import org.eclipse.viatra.solver.data.model.ModelStore;
+import org.eclipse.viatra.solver.data.model.representation.DataRepresentation;
+
+public class ModelImpl implements Model {
+        private final ModelStore store;
+        private final Map<DataRepresentation<?, ?>, VersionedMap<?, ?>> maps;
+
+        public ModelImpl(ModelStore store, Map<DataRepresentation<?, ?>, VersionedMap<?, ?>> maps) {
+                this.store = store;
+                this.maps = maps;
+        }
+
+        @Override
+        public Set<DataRepresentation<?, ?>> getDataRepresentations() {
+                return maps.keySet();
+        }
+
+        @SuppressWarnings("unchecked")
+        private <K, V> VersionedMap<K, V> getMap(DataRepresentation<K, V> representation) {
+                if (maps.containsKey(representation)) {
+                        return (VersionedMap<K, V>) maps.get(representation);
+                } else {
+                        throw new IllegalArgumentException("Model does have representation " + representation);
+                }
+        }
+
+        private <K, V> VersionedMap<K, V> getMapValidateKey(DataRepresentation<K, V> representation, K key) {
+                if (representation.isValidKey(key)) {
+                        return getMap(representation);
+                } else {
+                        throw new IllegalArgumentException(
+                                        "Key is not valid for representation! (representation=" + representation + ", key=" + key + ");");
+                }
+        }
+
+        @Override
+        public <K, V> V get(DataRepresentation<K, V> representation, K key) {
+                return getMapValidateKey(representation, key).get(key);
+        }
+
+        @Override
+        public <K, V> Cursor<K, V> getAll(DataRepresentation<K, V> representation) {
+                return getMap(representation).getAll();
+        }
+
+        @Override
+        public <K, V> V put(DataRepresentation<K, V> representation, K key, V value) {
+                return getMapValidateKey(representation, key).put(key, value);
+        }
+
+        @Override
+        public <K, V> void putAll(DataRepresentation<K, V> representation, Cursor<K, V> cursor) {
+                getMap(representation).putAll(cursor);
+        }
+
+        @Override
+        public <K, V> long getSize(DataRepresentation<K, V> representation) {
+                return getMap(representation).getSize();
+        }
+
+        @Override
+        public ModelDiffCursor getDiffCursor(long to) {
+                Model toModel = store.createModel(to);
+                Map<DataRepresentation<?, ?>, DiffCursor<?, ?>> diffCursors = new HashMap<>();
+                for (DataRepresentation<?, ?> representation : this.maps.keySet()) {
+                        MapDiffCursor<?, ?> diffCursor = constructDiffCursor(toModel, representation);
+                        diffCursors.put(representation, diffCursor);
+                }
+                return new ModelDiffCursor(diffCursors);
+        }
+
+        private <K, V> MapDiffCursor<K, V> constructDiffCursor(Model toModel, DataRepresentation<K, V> representation) {
+                @SuppressWarnings("unchecked")
+                Cursor<K, V> fromCursor = (Cursor<K, V>) this.maps.get(representation).getAll();
+                Cursor<K, V> toCursor = toModel.getAll(representation);
+
+                ContinousHashProvider<K> hashProvider = representation.getHashProvider();
+                V defaultValue = representation.getDefaultValue();
+                return new MapDiffCursor<>(hashProvider, defaultValue, fromCursor, toCursor);
+        }
+
+        @Override
+        public long commit() {
+                long version = 0;
+                boolean versionSet = false;
+                for (VersionedMap<?, ?> map : maps.values()) {
+                        long newVersion = map.commit();
+                        if (versionSet) {
+                                if (version != newVersion) {
+                                        throw new IllegalStateException(
+                                                        "Maps in model have different versions! (" + version + " and" + newVersion + ")");
+                                }
+                        } else {
+                                version = newVersion;
+                                versionSet = true;
+                        }
+                }
+                return version;
+        }
+
+        @Override
+        public void restore(long state) {
+                if(store.getStates().contains(state)) {
+                        for (VersionedMap<?, ?> map : maps.values()) {
+                                map.restore(state);
+                        }
+                } else {
+                        throw new IllegalArgumentException("Map does not contain state "+state+"!");
+                }
+        }
+}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/model/internal/SimilarRelationEquivalenceClass.java b/store/src/main/java/org/eclipse/viatra/solver/data/model/internal/SimilarRelationEquivalenceClass.java
new file mode 100644
index 00000000..7054e4db
--- /dev/null
+++ b/store/src/main/java/org/eclipse/viatra/solver/data/model/internal/SimilarRelationEquivalenceClass.java
@@ -0,0 +1,33 @@
+package org.eclipse.viatra.solver.data.model.internal;
+
+import java.util.Objects;
+
+import org.eclipse.viatra.solver.data.map.ContinousHashProvider;
+import org.eclipse.viatra.solver.data.model.Tuple;
+import org.eclipse.viatra.solver.data.model.representation.Relation;
+
+public class SimilarRelationEquivalenceClass {
+        final ContinousHashProvider<Tuple> hashProvider;
+        final Object defaultValue;
+        final int arity;
+        public SimilarRelationEquivalenceClass(Relation<?> representation) {
+                this.hashProvider = representation.getHashProvider();
+                this.defaultValue = representation.getDefaultValue();
+                this.arity = representation.getArity();
+        }
+        @Override
+        public int hashCode() {
+                return Objects.hash(arity, defaultValue, hashProvider);
+        }
+        @Override
+        public boolean equals(Object obj) {
+                if (this == obj)
+                        return true;
+                if (!(obj instanceof SimilarRelationEquivalenceClass))
+                        return false;
+                SimilarRelationEquivalenceClass other = (SimilarRelationEquivalenceClass) obj;
+                return arity == other.arity && Objects.equals(defaultValue, other.defaultValue)
+                                && Objects.equals(hashProvider, other.hashProvider);
+        }
+        
+}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/model/representation/AuxilaryData.java b/store/src/main/java/org/eclipse/viatra/solver/data/model/representation/AuxilaryData.java
new file mode 100644
index 00000000..7fc79348
--- /dev/null
+++ b/store/src/main/java/org/eclipse/viatra/solver/data/model/representation/AuxilaryData.java
@@ -0,0 +1,22 @@
+package org.eclipse.viatra.solver.data.model.representation;
+
+import org.eclipse.viatra.solver.data.map.ContinousHashProvider;
+
+public class AuxilaryData<K,V> extends DataRepresentation<K, V> {
+        private final String name;
+
+        public AuxilaryData(String name, ContinousHashProvider<K> hashProvider, V defaultValue) {
+                super(hashProvider, defaultValue);
+                this.name = name;
+        }
+        
+        @Override
+        public String getName() {
+                return name;
+        }
+        
+        @Override
+        public boolean isValidKey(K key) {
+                return true;
+        }
+}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/model/representation/DataRepresentation.java b/store/src/main/java/org/eclipse/viatra/solver/data/model/representation/DataRepresentation.java
new file mode 100644
index 00000000..fd48eb94
--- /dev/null
+++ b/store/src/main/java/org/eclipse/viatra/solver/data/model/representation/DataRepresentation.java
@@ -0,0 +1,24 @@
+package org.eclipse.viatra.solver.data.model.representation;
+
+import org.eclipse.viatra.solver.data.map.ContinousHashProvider;
+
+public abstract class DataRepresentation<K, V> {
+        protected final ContinousHashProvider<K> hashProvider;
+        protected final V defaultValue;
+
+        protected DataRepresentation(ContinousHashProvider<K> hashProvider,     V defaultValue) {
+                this.hashProvider = hashProvider;
+                this.defaultValue = defaultValue;
+        }
+        
+        public abstract String getName();
+        
+        public ContinousHashProvider<K> getHashProvider() {
+                return hashProvider;
+        }
+        public abstract boolean isValidKey(K key);
+
+        public V getDefaultValue() {
+                return defaultValue;
+        }
+}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/model/representation/Relation.java b/store/src/main/java/org/eclipse/viatra/solver/data/model/representation/Relation.java
new file mode 100644
index 00000000..eafb5c56
--- /dev/null
+++ b/store/src/main/java/org/eclipse/viatra/solver/data/model/representation/Relation.java
@@ -0,0 +1,31 @@
+package org.eclipse.viatra.solver.data.model.representation;
+
+import org.eclipse.viatra.solver.data.model.Tuple;
+import org.eclipse.viatra.solver.data.model.TupleHashProvider;
+
+public class Relation<D> extends DataRepresentation<Tuple, D> {
+        private final String name;
+        private final int arity;
+
+        public Relation(String name, int arity, D defaultValue) {
+                super(TupleHashProvider.singleton(), defaultValue);
+                this.name = name;
+                this.arity = arity;
+        }
+
+        @Override
+        public String getName() {
+                return name;
+        }
+
+        public int getArity() {
+                return arity;
+        }
+
+        @Override
+        public boolean isValidKey(Tuple key) {
+                if(key == null) {
+                        return false;
+                } else return key.getSize() == getArity();
+        }
+}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/model/representation/TruthValue.java b/store/src/main/java/org/eclipse/viatra/solver/data/model/representation/TruthValue.java
new file mode 100644
index 00000000..aeccde9e
--- /dev/null
+++ b/store/src/main/java/org/eclipse/viatra/solver/data/model/representation/TruthValue.java
@@ -0,0 +1,44 @@
+package org.eclipse.viatra.solver.data.model.representation;
+
+public class TruthValue {
+        public static final TruthValue True = new TruthValue("true");
+        public static final TruthValue False = new TruthValue("false");
+        public static final TruthValue Unknown = new TruthValue("unknown");
+        public static final TruthValue Error = new TruthValue("error");
+        
+        private final String name;
+        protected TruthValue(String name) {
+                this.name = name;
+        }
+        
+        public String getName() {
+                return name;
+        }
+        
+        public static TruthValue toTruthValue(boolean value) {
+                if(value) return True;
+                else return False;
+        }
+        public boolean isConsistent() {
+                return this != Error;
+        }
+        public boolean isComplete() {
+                return this != Unknown;
+        }
+        public boolean must() {
+                return this == True || this == Error;
+        }
+        public boolean may() {
+                return this == True || this == Unknown;
+        }
+        
+        public TruthValue not() {
+                if(this == True) {
+                        return False;
+                } else if(this == False) {
+                        return True;
+                } else {
+                        return this;
+                }
+        }
+}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/query/RelationalScope.java b/store/src/main/java/org/eclipse/viatra/solver/data/query/RelationalScope.java
new file mode 100644
index 00000000..97b33935
--- /dev/null
+++ b/store/src/main/java/org/eclipse/viatra/solver/data/query/RelationalScope.java
@@ -0,0 +1,34 @@
+package org.eclipse.viatra.solver.data.query;
+
+import java.util.Set;
+
+import org.apache.log4j.Logger;
+import org.eclipse.viatra.query.runtime.api.ViatraQueryEngine;
+import org.eclipse.viatra.query.runtime.api.scope.IEngineContext;
+import org.eclipse.viatra.query.runtime.api.scope.IIndexingErrorListener;
+import org.eclipse.viatra.query.runtime.api.scope.QueryScope;
+import org.eclipse.viatra.solver.data.model.Model;
+import org.eclipse.viatra.solver.data.model.Tuple;
+import org.eclipse.viatra.solver.data.query.internal.RelationUpdateListener;
+import org.eclipse.viatra.solver.data.query.internal.RelationalEngineContext;
+import org.eclipse.viatra.solver.data.query.view.RelationView;
+
+public class RelationalScope extends QueryScope{
+        private final Model model;
+        private final RelationUpdateListener updateListener;
+        
+        public RelationalScope(Model model, Set<RelationView<?>> relationViews) {
+                this.model = model;
+                updateListener = new RelationUpdateListener(relationViews);
+        }
+        
+        public <D> void processUpdate(RelationView<D> relationView, Tuple key, D oldValue, D newValue) {
+                updateListener.processChange(relationView, key, oldValue, newValue);
+        }
+
+        @Override
+        protected IEngineContext createEngineContext(ViatraQueryEngine engine, IIndexingErrorListener errorListener,
+                        Logger logger) {
+                return new RelationalEngineContext(model, updateListener);
+        }
+}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/query/building/DNFAnd.java b/store/src/main/java/org/eclipse/viatra/solver/data/query/building/DNFAnd.java
new file mode 100644
index 00000000..ff5a7848
--- /dev/null
+++ b/store/src/main/java/org/eclipse/viatra/solver/data/query/building/DNFAnd.java
@@ -0,0 +1,37 @@
+package org.eclipse.viatra.solver.data.query.building;
+
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+
+public class DNFAnd {
+        private Set<Variable> existentiallyQuantified;
+        private List<DNFAtom> constraints;
+        public DNFAnd(Set<Variable> quantifiedVariables, List<DNFAtom> constraints) {
+                super();
+                this.existentiallyQuantified = quantifiedVariables;
+                this.constraints = constraints;
+        }
+        public Set<Variable> getExistentiallyQuantified() {
+                return existentiallyQuantified;
+        }
+        public List<DNFAtom> getConstraints() {
+                return constraints;
+        }
+        void unifyVariables(Map<String,Variable> uniqueVariableMap) {
+                Map<String,Variable> uniqueVariableMapForClause = new HashMap<>(uniqueVariableMap);
+                for(DNFAtom atom : constraints) {
+                        atom.unifyVariables(uniqueVariableMapForClause);
+                }
+        }
+        void collectQuantifiedVariables(Set<Variable> parameters) {
+                Set<Variable> result = new HashSet<>();
+                for(DNFAtom constraint : constraints) {
+                        constraint.collectAllVariables(result);
+                }
+                result.removeAll(parameters);
+                existentiallyQuantified = result;
+        }
+}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/query/building/DNFAtom.java b/store/src/main/java/org/eclipse/viatra/solver/data/query/building/DNFAtom.java
new file mode 100644
index 00000000..05a3e3f8
--- /dev/null
+++ b/store/src/main/java/org/eclipse/viatra/solver/data/query/building/DNFAtom.java
@@ -0,0 +1,33 @@
+package org.eclipse.viatra.solver.data.query.building;
+
+import java.util.Collection;
+import java.util.Iterator;
+import java.util.Map;
+import java.util.Set;
+
+public interface DNFAtom {
+        void unifyVariables(Map<String,Variable> variables);
+        static Variable unifyVariables(Map<String,Variable> unifiedVariables, Variable variable) {
+                if(variable != null) {
+                        if(variable.isNamed() && unifiedVariables.containsKey(variable.getName())) {
+                                return unifiedVariables.get(variable.getName());
+                        }
+                        return variable;
+                } else {
+                        return null;
+                }
+        }
+        void collectAllVariables(Set<Variable> variables);
+        static void addToCollection(Set<Variable> variables, Variable variable) {
+                if(variable != null) {
+                        variables.add(variable);
+                }
+        }
+        static void addToCollection(Set<Variable> variables, Collection<Variable> variableCollection) {
+                Iterator<Variable> iterator = variableCollection.iterator();
+                while(iterator.hasNext()) {
+                        Variable variable = iterator.next();
+                        addToCollection(variables, variable);
+                }
+        }
+}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/query/building/DNFPredicate.java b/store/src/main/java/org/eclipse/viatra/solver/data/query/building/DNFPredicate.java
new file mode 100644
index 00000000..8ee540ae
--- /dev/null
+++ b/store/src/main/java/org/eclipse/viatra/solver/data/query/building/DNFPredicate.java
@@ -0,0 +1,72 @@
+package org.eclipse.viatra.solver.data.query.building;
+
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Map;
+import java.util.UUID;
+
+public class DNFPredicate {
+        private final String name;
+        private final String uniqueName;
+        private final List<Variable> parameters;
+        private final List<DNFAnd> clauses;
+        
+        public DNFPredicate(String name, List<Variable> parameters, List<DNFAnd> clauses) {
+                this.name = name;
+                this.uniqueName = generateUniqueName(name,"predicate");
+                this.parameters = parameters;
+                this.clauses = clauses;
+                
+                postProcess();
+        }
+        
+        public static String generateUniqueName(String originalName, String defaultPrefix) {
+                UUID uuid = UUID.randomUUID();
+                String uniqueString = uuid.toString().replace('-', '_');
+                if(originalName == null) {
+                        return defaultPrefix+uniqueString;
+                } else {
+                        return originalName+uniqueString;
+                }
+        }
+        
+        public String getName() {
+                return name;
+        }
+        public String getUniqueName() {
+                return uniqueName;
+        }
+        public List<Variable> getVariables() {
+                return parameters;
+        }
+        public List<DNFAnd> getClauses() {
+                return clauses;
+        }
+        
+        public void unifyVariables() {
+                Map<String,Variable> uniqueVariableMap = new HashMap<>();
+                for(Variable parameter : this.parameters) {
+                        if(parameter.isNamed()) {
+                                String parameterName = parameter.getName();
+                                if(uniqueVariableMap.containsKey(parameterName)) {
+                                        throw new IllegalArgumentException("Multiple parameters has the name "+parameterName);
+                                } else {
+                                        uniqueVariableMap.put(parameterName, parameter);
+                                }
+                        }
+                }
+                for(DNFAnd clause : this.clauses) {
+                        clause.unifyVariables(uniqueVariableMap);
+                }
+        }
+        public void collectQuantifiedVariables() {
+                for(DNFAnd clause : this.clauses) {
+                        clause.collectQuantifiedVariables(new HashSet<>(parameters));
+                }
+        }
+        public void postProcess() {
+                unifyVariables();
+                collectQuantifiedVariables();
+        }
+}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/query/building/EquivalenceAtom.java b/store/src/main/java/org/eclipse/viatra/solver/data/query/building/EquivalenceAtom.java
new file mode 100644
index 00000000..b47fe2a8
--- /dev/null
+++ b/store/src/main/java/org/eclipse/viatra/solver/data/query/building/EquivalenceAtom.java
@@ -0,0 +1,44 @@
+package org.eclipse.viatra.solver.data.query.building;
+
+import java.util.Map;
+import java.util.Set;
+
+public class EquivalenceAtom implements DNFAtom{
+        private boolean positive;
+        private Variable left;
+        private Variable right;
+        public EquivalenceAtom(boolean positive, Variable left, Variable right) {
+                this.positive = positive;
+                this.left = left;
+                this.right = right;
+        }
+        public boolean isPositive() {
+                return positive;
+        }
+        public void setPositive(boolean positive) {
+                this.positive = positive;
+        }
+        public Variable getLeft() {
+                return left;
+        }
+        public void setLeft(Variable left) {
+                this.left = left;
+        }
+        public Variable getRight() {
+                return right;
+        }
+        public void setRight(Variable right) {
+                this.right = right;
+        }
+        
+        @Override
+        public void unifyVariables(Map<String, Variable> variables) {
+                this.left = DNFAtom.unifyVariables(variables,left);
+                this.right = DNFAtom.unifyVariables(variables,right);
+        }
+        @Override
+        public void collectAllVariables(Set<Variable> variables) {
+                DNFAtom.addToCollection(variables, left);
+                DNFAtom.addToCollection(variables, right);
+        }
+}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/query/building/PredicateAtom.java b/store/src/main/java/org/eclipse/viatra/solver/data/query/building/PredicateAtom.java
new file mode 100644
index 00000000..3e5ef88e
--- /dev/null
+++ b/store/src/main/java/org/eclipse/viatra/solver/data/query/building/PredicateAtom.java
@@ -0,0 +1,57 @@
+package org.eclipse.viatra.solver.data.query.building;
+
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+
+public class PredicateAtom implements DNFAtom{
+        private DNFPredicate referred;
+        private List<Variable> substitution;
+        private boolean positive;
+        private boolean transitive;
+        
+        public PredicateAtom(boolean positive, boolean transitive, DNFPredicate referred, List<Variable> substitution) {
+                this.positive = positive;
+                this.referred = referred;
+                this.substitution = substitution;
+                this.transitive = transitive;
+        }
+        public DNFPredicate getReferred() {
+                return referred;
+        }
+        public void setReferred(DNFPredicate referred) {
+                this.referred = referred;
+        }
+        public List<Variable> getSubstitution() {
+                return substitution;
+        }
+        public void setSubstitution(List<Variable> substitution) {
+                this.substitution = substitution;
+        }
+        public boolean isPositive() {
+                return positive;
+        }
+        public void setPositive(boolean positive) {
+                this.positive = positive;
+        }
+        public boolean isTransitive() {
+                return transitive;
+        }
+        public void setTransitive(boolean transitive) {
+                this.transitive = transitive;
+        }
+        @Override
+        public void unifyVariables(Map<String, Variable> variables) {
+                for(int i = 0; i<this.substitution.size(); i++) {
+                        final Object term = this.substitution.get(i);
+                        if(term instanceof Variable) {
+                                Variable variableReference = (Variable) term;
+                                this.substitution.set(i, DNFAtom.unifyVariables(variables, variableReference));
+                        }
+                }
+        }
+        @Override
+        public void collectAllVariables(Set<Variable> variables) {
+                DNFAtom.addToCollection(variables, substitution);
+        }
+}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/query/building/PredicateBuilder_string.java b/store/src/main/java/org/eclipse/viatra/solver/data/query/building/PredicateBuilder_string.java
new file mode 100644
index 00000000..41f85d39
--- /dev/null
+++ b/store/src/main/java/org/eclipse/viatra/solver/data/query/building/PredicateBuilder_string.java
@@ -0,0 +1,107 @@
+package org.eclipse.viatra.solver.data.query.building;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.HashSet;
+import java.util.List;
+
+import org.eclipse.viatra.solver.data.query.view.RelationView;
+
+public class PredicateBuilder_string {
+        private PredicateBuilder_string() {}
+        
+        public static PredicateBuild1 predicate(String name) {
+                return new PredicateBuild1(name);
+        }
+        public static class PredicateBuild1 {
+                private String name;
+                public PredicateBuild1(String name) {
+                        this.name = name;
+                }
+                public PredicateBuild2 parameters(String... parameters) {
+                        return new PredicateBuild2(name, parameters);
+                }
+        }
+        public static class PredicateBuild2 {
+                private String name;
+                private String[] parameters;
+                public PredicateBuild2(String name, String[] parameters) {
+                        this.name = name;
+                        this.parameters = parameters;
+                }
+                
+                public PredicateBuild3 clause(DNFAtom...constraints) {
+                        return new PredicateBuild3(name,parameters,List.<DNFAtom[]>of(constraints));
+                }
+        }
+        public static class PredicateBuild3 {
+                String name;
+                String[] parameters;
+                List<DNFAtom[]> clauses;
+                public PredicateBuild3(String name, String[] parameters, List<DNFAtom[]> clauses) {
+                        super();
+                        this.name = name;
+                        this.parameters = parameters;
+                        this.clauses = clauses;
+                }
+                
+                public PredicateBuild3 clause(DNFAtom...constraints) {
+                        List<DNFAtom[]> newClauses = new ArrayList<>();
+                        newClauses.addAll(clauses);
+                        newClauses.add(constraints);
+                        return new PredicateBuild3(name, parameters, newClauses);
+                }
+                public DNFPredicate build() {
+                        List<Variable> newParameters = new ArrayList<>(this.parameters.length);
+                        for(int i = 0; i<this.parameters.length; i++) {
+                                newParameters.add(new Variable(parameters[i]));
+                        }
+                        
+                        List<DNFAnd> newClauses = new ArrayList<>(this.clauses.size());
+                        for(DNFAtom[] clause : this.clauses) {
+                                List<DNFAtom> constraints = new ArrayList<>(clause.length);
+                                Collections.addAll(constraints, clause);
+                                newClauses.add(new DNFAnd(new HashSet<>(), constraints));
+                        }
+                        
+                        return new DNFPredicate(name,newParameters,newClauses);
+                }
+        }
+        
+        private static Variable stringToVariable(String name) {
+                if(name != null) {
+                        return new Variable(name);
+                } else {
+                        return null;
+                }
+        }
+        private static List<Variable> stringToVariable(String[] names) {
+                List<Variable> variables = new ArrayList<>();
+                for(int i = 0; i<names.length; i++) {
+                        variables.add(stringToVariable(names[i]));
+                }
+                return variables;
+        }
+        
+        public static EquivalenceAtom cEquals(String v1, String v2) {
+                return new EquivalenceAtom(true,stringToVariable(v1),stringToVariable(v2));
+        }
+        public static EquivalenceAtom cNotEquals(String v1, String v2) {
+                return new EquivalenceAtom(false,stringToVariable(v1),stringToVariable(v2));
+        }
+        
+        public static RelationAtom cInRelation(RelationView<?> view, String... variables) {
+                
+                return new RelationAtom(view, stringToVariable(variables));
+        }
+        
+        public static PredicateAtom cInPredicate(DNFPredicate referred, String... variables) {
+                return new PredicateAtom(true, false, referred, stringToVariable(variables));
+        }
+        public static PredicateAtom cInTransitivePredicate(DNFPredicate referred, String... variables) {
+                return new PredicateAtom(true, true, referred, stringToVariable(variables));
+        }
+        public static PredicateAtom cNotInPredicate(DNFPredicate referred, String... variables) {
+                return new PredicateAtom(false, false, referred, stringToVariable(variables));
+        }
+}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/query/building/RelationAtom.java b/store/src/main/java/org/eclipse/viatra/solver/data/query/building/RelationAtom.java
new file mode 100644
index 00000000..f7152bba
--- /dev/null
+++ b/store/src/main/java/org/eclipse/viatra/solver/data/query/building/RelationAtom.java
@@ -0,0 +1,45 @@
+package org.eclipse.viatra.solver.data.query.building;
+
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+
+import org.eclipse.viatra.solver.data.query.view.FilteredRelationView;
+import org.eclipse.viatra.solver.data.query.view.RelationView;
+
+public class RelationAtom implements DNFAtom{
+        RelationView<?> view;
+        List<Variable> substitution;
+        
+        public RelationAtom(RelationView<?> view, List<Variable> substitution) {
+                this.view = view;
+                this.substitution = substitution;
+        }
+        public RelationView<?> getView() {
+                return view;
+        }
+        public void setView(FilteredRelationView<?> view) {
+                this.view = view;
+        }
+        public List<Variable> getSubstitution() {
+                return substitution;
+        }
+        public void setSubstitution(List<Variable> substitution) {
+                this.substitution = substitution;
+        }
+        
+        @Override
+        public void unifyVariables(Map<String, Variable> variables) {
+                for(int i = 0; i<this.substitution.size(); i++) {
+                        final Object term = this.substitution.get(i);
+                        if(term instanceof Variable) {
+                                Variable variableReference = (Variable) term;
+                                this.substitution.set(i, DNFAtom.unifyVariables(variables, variableReference));
+                        }
+                }
+        }
+        @Override
+        public void collectAllVariables(Set<Variable> variables) {
+                DNFAtom.addToCollection(variables, substitution);
+        }
+}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/query/building/Variable.java b/store/src/main/java/org/eclipse/viatra/solver/data/query/building/Variable.java
new file mode 100644
index 00000000..29f9fc8b
--- /dev/null
+++ b/store/src/main/java/org/eclipse/viatra/solver/data/query/building/Variable.java
@@ -0,0 +1,22 @@
+package org.eclipse.viatra.solver.data.query.building;
+
+public class Variable {
+        private final String name;
+        private final String uniqueName;
+
+        public Variable(String name) {
+                super();
+                this.name = name;
+                this.uniqueName = DNFPredicate.generateUniqueName(name, "variable");
+                
+        }
+        public String getName() {
+                return name;
+        }
+        public String getUniqueName() {
+                return uniqueName;
+        }
+        public boolean isNamed() {
+                return name != null;
+        }
+}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/query/internal/DummyBaseIndexer.java b/store/src/main/java/org/eclipse/viatra/solver/data/query/internal/DummyBaseIndexer.java
new file mode 100644
index 00000000..042ec3dc
--- /dev/null
+++ b/store/src/main/java/org/eclipse/viatra/solver/data/query/internal/DummyBaseIndexer.java
@@ -0,0 +1,59 @@
+package org.eclipse.viatra.solver.data.query.internal;
+
+import java.lang.reflect.InvocationTargetException;
+import java.util.concurrent.Callable;
+
+import org.eclipse.viatra.query.runtime.api.scope.IBaseIndex;
+import org.eclipse.viatra.query.runtime.api.scope.IIndexingErrorListener;
+import org.eclipse.viatra.query.runtime.api.scope.IInstanceObserver;
+import org.eclipse.viatra.query.runtime.api.scope.ViatraBaseIndexChangeListener;
+
+/**
+ * copied from org.eclipse.viatra.query.runtime.tabular.TabularEngineContext;
+ */
+public class DummyBaseIndexer implements IBaseIndex{
+
+        @Override
+        public <V> V coalesceTraversals(Callable<V> callable) throws InvocationTargetException {
+                try {
+                        return callable.call();
+                } catch (Exception e) {
+                        throw new InvocationTargetException(e);
+                }
+        }
+
+        @Override
+        public void addBaseIndexChangeListener(ViatraBaseIndexChangeListener listener) {
+                // no notification support
+        }
+
+        @Override
+        public void removeBaseIndexChangeListener(ViatraBaseIndexChangeListener listener) {
+                // no notification support
+        }
+
+        @Override
+        public void resampleDerivedFeatures() {
+                throw new UnsupportedOperationException();
+        }
+
+        @Override
+        public boolean addIndexingErrorListener(IIndexingErrorListener listener) {
+                return true;
+        }
+
+        @Override
+        public boolean removeIndexingErrorListener(IIndexingErrorListener listener) {
+                return true;
+        }
+
+        @Override
+        public boolean addInstanceObserver(IInstanceObserver observer, Object observedObject) {
+                return true;
+        }
+
+        @Override
+        public boolean removeInstanceObserver(IInstanceObserver observer, Object observedObject) {
+                return true;
+        }
+}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/query/internal/PredicateTranslator.java b/store/src/main/java/org/eclipse/viatra/solver/data/query/internal/PredicateTranslator.java
new file mode 100644
index 00000000..54cb4bab
--- /dev/null
+++ b/store/src/main/java/org/eclipse/viatra/solver/data/query/internal/PredicateTranslator.java
@@ -0,0 +1,209 @@
+package org.eclipse.viatra.solver.data.query.internal;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.LinkedHashSet;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+
+import org.eclipse.viatra.query.runtime.api.GenericPatternMatcher;
+import org.eclipse.viatra.query.runtime.api.GenericQuerySpecification;
+import org.eclipse.viatra.query.runtime.api.ViatraQueryEngine;
+import org.eclipse.viatra.query.runtime.api.scope.QueryScope;
+import org.eclipse.viatra.query.runtime.matchers.backend.QueryEvaluationHint;
+import org.eclipse.viatra.query.runtime.matchers.psystem.PBody;
+import org.eclipse.viatra.query.runtime.matchers.psystem.PVariable;
+import org.eclipse.viatra.query.runtime.matchers.psystem.basicdeferred.Equality;
+import org.eclipse.viatra.query.runtime.matchers.psystem.basicdeferred.ExportedParameter;
+import org.eclipse.viatra.query.runtime.matchers.psystem.basicdeferred.Inequality;
+import org.eclipse.viatra.query.runtime.matchers.psystem.basicdeferred.NegativePatternCall;
+import org.eclipse.viatra.query.runtime.matchers.psystem.basicenumerables.BinaryReflexiveTransitiveClosure;
+import org.eclipse.viatra.query.runtime.matchers.psystem.basicenumerables.BinaryTransitiveClosure;
+import org.eclipse.viatra.query.runtime.matchers.psystem.basicenumerables.PositivePatternCall;
+import org.eclipse.viatra.query.runtime.matchers.psystem.basicenumerables.TypeConstraint;
+import org.eclipse.viatra.query.runtime.matchers.psystem.queries.BasePQuery;
+import org.eclipse.viatra.query.runtime.matchers.psystem.queries.PParameter;
+import org.eclipse.viatra.query.runtime.matchers.psystem.queries.PQuery;
+import org.eclipse.viatra.query.runtime.matchers.psystem.queries.PVisibility;
+import org.eclipse.viatra.query.runtime.matchers.tuple.Tuples;
+import org.eclipse.viatra.solver.data.query.RelationalScope;
+import org.eclipse.viatra.solver.data.query.view.RelationView;
+
+public class PredicateTranslator extends BasePQuery {
+
+        private final Map<String, PParameter> parameters = new HashMap<String, PParameter>();
+        private String fullyQualifiedName;
+        private LinkedList<PBody> bodies = new LinkedList<PBody>();
+        private List<ExportedParameter> symbolicParameters;
+
+        public PredicateTranslator(String fullyQualifiedName) {
+                super(PVisibility.PUBLIC);
+                this.fullyQualifiedName = fullyQualifiedName;
+                PBody body = new PBody(this);
+                bodies.add(body);
+        }
+
+        @Override
+        public String getFullyQualifiedName() {
+                return fullyQualifiedName;
+        }
+
+        public PredicateTranslator addParameter(String name, RelationView<?> type) {
+                PParameter parameter = new PParameter(name);
+                parameters.put(name, parameter);
+                
+                PBody body = bodies.peekLast();
+                List<ExportedParameter> symbolicParameters = new ArrayList<>();
+                parameters.forEach((pName, pParameter) -> {
+                        PVariable var = body.getOrCreateVariableByName(pName);
+                        symbolicParameters.add(new ExportedParameter(body, var, pParameter));
+                });
+                body.setSymbolicParameters(symbolicParameters);
+                
+                return this;
+        }
+
+        @Override
+        public List<PParameter> getParameters() {
+                return new ArrayList<PParameter>(parameters.values());
+        }
+        public <D> PredicateTranslator addConstraint(RelationView<D> view, String... name) {
+                if(name.length != view.getArity()) {
+                        throw new IllegalArgumentException("Arity ("+view.getArity()+") does not match parameter numbers ("+name.length+")");
+                }
+                PBody body = bodies.peekLast();
+                Object[] variables = new Object[name.length]; 
+                for(int i = 0; i<name.length; i++) {
+                        variables[i] = body.getOrCreateVariableByName(name[i]);
+                }
+                new TypeConstraint(body, Tuples.flatTupleOf(variables), view);
+                return this;
+        }
+
+//      // Type constraint
+//      public RelationQuery addConstraint(String type, String name) {
+//              PBody body = bodies.peekLast();
+//              PVariable var = body.getOrCreateVariableByName(name);
+//              new TypeConstraint(body, Tuples.flatTupleOf(var), new StringExactInstancesKey(type));
+//              return this;
+//      }
+//
+//      // Relation constraint
+//      public RelationQuery addConstraint(String type, String sourceName, String targetName) {
+//              PBody body = bodies.peekLast();
+//              PVariable var_source = body.getOrCreateVariableByName(sourceName);
+//              PVariable var_target = body.getOrCreateVariableByName(targetName);
+//              new TypeConstraint(body, Tuples.flatTupleOf(var_source, var_target),
+//                              new StringStructuralFeatureInstancesKey(type));
+//              return this;
+//      }
+
+        // Create new Body
+        public PredicateTranslator or() {
+                PBody body = new PBody(this);
+                List<ExportedParameter> symbolicParameters = new ArrayList<>();
+                parameters.forEach((name, parameter) -> {
+                        PVariable var = body.getOrCreateVariableByName(name);
+                        symbolicParameters.add(new ExportedParameter(body, var, parameter));
+                });
+                body.setSymbolicParameters(symbolicParameters);
+                bodies.add(body);
+                return this;
+        }
+
+        // Equality constraint
+        public PredicateTranslator addEquality(String sourceName, String targetName) {
+                PBody body = bodies.peekLast();
+                PVariable var_source = body.getOrCreateVariableByName(sourceName);
+                PVariable var_target = body.getOrCreateVariableByName(targetName);
+                new Equality(body, var_source, var_target);
+                return this;
+        }
+
+        // Inequality constraint
+        public PredicateTranslator addInequality(String sourceName, String targetName) {
+                PBody body = bodies.peekLast();
+                PVariable var_source = body.getOrCreateVariableByName(sourceName);
+                PVariable var_target = body.getOrCreateVariableByName(targetName);
+                new Inequality(body, var_source, var_target);
+                return this;
+        }
+
+        // Positive pattern call
+        public PredicateTranslator addPatternCall(PQuery query, String... names) {
+                PBody body = bodies.peekLast();
+                PVariable[] vars = new PVariable[names.length];
+                for (int i = 0; i < names.length; i++) {
+                        vars[i] = body.getOrCreateVariableByName(names[i]);
+                }
+                new PositivePatternCall(body, Tuples.flatTupleOf(vars), query);
+                return this;
+        }
+
+        // Negative pattern call
+        public PredicateTranslator addNegativePatternCall(PQuery query, String... names) {
+                PBody body = bodies.peekLast();
+                PVariable[] vars = new PVariable[names.length];
+                for (int i = 0; i < names.length; i++) {
+                        vars[i] = body.getOrCreateVariableByName(names[i]);
+                }
+                new NegativePatternCall(body, Tuples.flatTupleOf(vars), query);
+                return this;
+        }
+
+        // Binary transitive closure pattern call
+        public PredicateTranslator addBinaryTransitiveClosure(PQuery query, String sourceName, String targetName) {
+                PBody body = bodies.peekLast();
+                PVariable var_source = body.getOrCreateVariableByName(sourceName);
+                PVariable var_target = body.getOrCreateVariableByName(targetName);
+                new BinaryTransitiveClosure(body, Tuples.flatTupleOf(var_source, var_target), query);
+                return this;
+        }
+
+        // Binary reflexive transitive closure pattern call
+        public PredicateTranslator addBinaryReflexiveTransitiveClosure(PQuery query, String sourceName, String targetName) {
+                PBody body = bodies.peekLast();
+                PVariable var_source = body.getOrCreateVariableByName(sourceName);
+                PVariable var_target = body.getOrCreateVariableByName(targetName);
+                new BinaryReflexiveTransitiveClosure(body, Tuples.flatTupleOf(var_source, var_target), query,
+                                query.getParameters().get(0).getDeclaredUnaryType());
+                return this;
+        }
+
+        @Override
+        public Set<PBody> doGetContainedBodies() {
+                setEvaluationHints(new QueryEvaluationHint(null, QueryEvaluationHint.BackendRequirement.UNSPECIFIED));
+                return new LinkedHashSet<PBody>(bodies);
+        }
+
+        public void addSymbolicParameters(ExportedParameter symbolicParameter) {
+                checkMutability();
+                if (symbolicParameters == null) {
+                        symbolicParameters = new ArrayList<>();
+                }
+                symbolicParameters.add(symbolicParameter);
+        }
+        
+        public GenericQuerySpecification<GenericPatternMatcher> build() {
+                return new GenericQuerySpecification<GenericPatternMatcher>(this) {
+
+                        @Override
+                        public Class<? extends QueryScope> getPreferredScopeClass() {
+                                return RelationalScope.class;
+                        }
+
+                        @Override
+                        protected GenericPatternMatcher instantiate(ViatraQueryEngine engine) {
+                                return defaultInstantiate(engine);
+                        }
+                        
+                        @Override
+                        public GenericPatternMatcher instantiate() {
+                                return new GenericPatternMatcher(this);
+                        }
+
+                };
+        }
+}
\ No newline at end of file
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/query/internal/RelationUpdateListener.java b/store/src/main/java/org/eclipse/viatra/solver/data/query/internal/RelationUpdateListener.java
new file mode 100644
index 00000000..c6d12614
--- /dev/null
+++ b/store/src/main/java/org/eclipse/viatra/solver/data/query/internal/RelationUpdateListener.java
@@ -0,0 +1,51 @@
+package org.eclipse.viatra.solver.data.query.internal;
+
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Map;
+import java.util.Set;
+
+import org.eclipse.viatra.query.runtime.matchers.context.IQueryRuntimeContextListener;
+import org.eclipse.viatra.query.runtime.matchers.tuple.ITuple;
+import org.eclipse.viatra.solver.data.model.Tuple;
+import org.eclipse.viatra.solver.data.query.view.RelationView;
+
+public class RelationUpdateListener {
+        private final Map<RelationView<?>,Set<RelationUpdateListenerEntry<?>>> view2Listeners;
+        
+        public RelationUpdateListener(Set<RelationView<?>> relationViews) {
+                view2Listeners = new HashMap<>();
+                for(RelationView<?> relationView : relationViews) {
+                        view2Listeners.put(relationView, new HashSet<>());
+                }
+        }
+        public boolean containsRelationalView(RelationView<?> relationalKey) {
+                RelationView<?> relationView = relationalKey.getWrappedKey();
+                return view2Listeners.containsKey(relationView);
+        }
+        public void addListener(RelationView<?> relationalKey, ITuple seed, IQueryRuntimeContextListener listener) {
+                RelationView<?> relationView = relationalKey.getWrappedKey();
+                if(view2Listeners.containsKey(relationView)) {
+                        RelationUpdateListenerEntry<?> entry = new RelationUpdateListenerEntry<>(relationalKey, seed, listener);
+                        view2Listeners.get(relationView).add(entry);
+                } else throw new IllegalArgumentException();
+        }
+        public void removeListener(RelationView<?> relationalKey, ITuple seed, IQueryRuntimeContextListener listener) {
+                RelationView<?> relationView = relationalKey.getWrappedKey();
+                if(view2Listeners.containsKey(relationView)) {
+                        RelationUpdateListenerEntry<?> entry = new RelationUpdateListenerEntry<>(relationalKey, seed, listener);
+                        view2Listeners.get(relationView).remove(entry);
+                } else throw new IllegalArgumentException();
+        }
+        
+        public <D> void processChange(RelationView<D> relationView, Tuple tuple, D oldValue, D newValue) {
+                Set<RelationUpdateListenerEntry<?>> listeners = view2Listeners.get(relationView);
+                if(listeners != null) {
+                        for(RelationUpdateListenerEntry<?> listener : listeners) {
+                                @SuppressWarnings("unchecked")
+                                RelationUpdateListenerEntry<D> typeCorrectListener = (RelationUpdateListenerEntry<D>) listener;
+                                typeCorrectListener.processChange(tuple, oldValue, newValue);
+                        }
+                } else throw new IllegalArgumentException("View was not indexed in constructor "+relationView);
+        }
+}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/query/internal/RelationUpdateListenerEntry.java b/store/src/main/java/org/eclipse/viatra/solver/data/query/internal/RelationUpdateListenerEntry.java
new file mode 100644
index 00000000..55aed7c8
--- /dev/null
+++ b/store/src/main/java/org/eclipse/viatra/solver/data/query/internal/RelationUpdateListenerEntry.java
@@ -0,0 +1,63 @@
+package org.eclipse.viatra.solver.data.query.internal;
+
+import java.util.Arrays;
+import java.util.Objects;
+
+import org.eclipse.viatra.query.runtime.matchers.context.IQueryRuntimeContextListener;
+import org.eclipse.viatra.query.runtime.matchers.tuple.ITuple;
+import org.eclipse.viatra.query.runtime.matchers.tuple.Tuples;
+import org.eclipse.viatra.solver.data.model.Tuple;
+import org.eclipse.viatra.solver.data.query.view.RelationView;
+
+public class RelationUpdateListenerEntry<D> {
+        final RelationView<D> key;
+        final ITuple filter;
+        final IQueryRuntimeContextListener listener;
+        
+        public RelationUpdateListenerEntry(RelationView<D> key, ITuple filter, IQueryRuntimeContextListener listener) {
+                super();
+                this.key = key;
+                this.filter = filter;
+                this.listener = listener;
+        }
+        
+        public void processChange(Tuple tuple, D oldValue, D newValue) {
+                Object[] oldTuple = isMatching(key.getWrappedKey().transform(tuple, oldValue), filter);
+                Object[] newTuple = isMatching(key.getWrappedKey().transform(tuple, newValue), filter);
+                
+                if(!Arrays.equals(oldTuple, newTuple)) {
+                        if(oldTuple != null) {
+                                listener.update(key, Tuples.flatTupleOf(oldTuple), false);
+                        }
+                        if(newTuple != null) {
+                                listener.update(key, Tuples.flatTupleOf(newTuple), true);
+                        }
+                }
+        }
+        
+        private Object[] isMatching(Object[] tuple, ITuple filter) {
+                for(int i = 0; i<filter.getSize(); i++) {
+                        final Object filterObject = filter.get(i);
+                        if(filterObject != null && !filterObject.equals(tuple[i])) {
+                                return null;
+                        }
+                }
+                return tuple;
+        }
+
+        @Override
+        public int hashCode() {
+                return Objects.hash(filter, key, listener);
+        }
+
+        @Override
+        public boolean equals(Object obj) {
+                if (this == obj)
+                        return true;
+                if (!(obj instanceof RelationUpdateListenerEntry))
+                        return false;
+                RelationUpdateListenerEntry<?> other = (RelationUpdateListenerEntry<?>) obj;
+                return Objects.equals(filter, other.filter) && Objects.equals(key, other.key)
+                                && Objects.equals(listener, other.listener);
+        }
+}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/query/internal/RelationalEngineContext.java b/store/src/main/java/org/eclipse/viatra/solver/data/query/internal/RelationalEngineContext.java
new file mode 100644
index 00000000..01948828
--- /dev/null
+++ b/store/src/main/java/org/eclipse/viatra/solver/data/query/internal/RelationalEngineContext.java
@@ -0,0 +1,32 @@
+package org.eclipse.viatra.solver.data.query.internal;
+
+import org.eclipse.viatra.query.runtime.api.scope.IBaseIndex;
+import org.eclipse.viatra.query.runtime.api.scope.IEngineContext;
+import org.eclipse.viatra.query.runtime.matchers.context.IQueryRuntimeContext;
+import org.eclipse.viatra.solver.data.model.Model;
+
+public class RelationalEngineContext implements IEngineContext{
+        private final IBaseIndex baseIndex = new DummyBaseIndexer();
+        private final RelationalRuntimeContext runtimeContext;
+        
+
+        public RelationalEngineContext(Model model, RelationUpdateListener updateListener) {
+                runtimeContext = new RelationalRuntimeContext(model, updateListener);
+        }
+
+        @Override
+        public IBaseIndex getBaseIndex() {
+                return this.baseIndex;
+        }
+
+        @Override
+        public void dispose() {
+                //lifecycle not controlled by engine
+        }
+
+        @Override
+        public IQueryRuntimeContext getQueryRuntimeContext() {
+                return runtimeContext;
+        }
+
+}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/query/internal/RelationalQueryMetaContext.java b/store/src/main/java/org/eclipse/viatra/solver/data/query/internal/RelationalQueryMetaContext.java
new file mode 100644
index 00000000..de500fc9
--- /dev/null
+++ b/store/src/main/java/org/eclipse/viatra/solver/data/query/internal/RelationalQueryMetaContext.java
@@ -0,0 +1,57 @@
+package org.eclipse.viatra.solver.data.query.internal;
+
+import java.util.Collection;
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Map;
+import java.util.Set;
+
+import org.eclipse.viatra.query.runtime.matchers.context.AbstractQueryMetaContext;
+import org.eclipse.viatra.query.runtime.matchers.context.IInputKey;
+import org.eclipse.viatra.query.runtime.matchers.context.InputKeyImplication;
+import org.eclipse.viatra.solver.data.query.view.RelationView;
+
+/**
+ * The meta context information for String scopes.
+ */
+public final class RelationalQueryMetaContext extends AbstractQueryMetaContext {
+
+        @Override
+        public boolean isEnumerable(IInputKey key) {            
+        ensureValidKey(key);
+        return key.isEnumerable();
+        }
+
+        @Override
+        public boolean isStateless(IInputKey key) {
+        ensureValidKey(key);
+        return key instanceof RelationView<?>;
+        }
+
+        @Override
+        public Collection<InputKeyImplication> getImplications(IInputKey implyingKey) {
+        ensureValidKey(implyingKey);
+        return new HashSet<InputKeyImplication>();
+        }               
+
+        @Override
+    public Map<Set<Integer>, Set<Integer>> getFunctionalDependencies(IInputKey key) {
+        ensureValidKey(key);
+        if (key instanceof RelationView) {
+            return new HashMap<Set<Integer>, Set<Integer>>();
+        } else {
+            return Collections.emptyMap();
+        }
+    }
+
+    public void ensureValidKey(IInputKey key) {
+        if (! (key instanceof RelationView<?>))
+            illegalInputKey(key);
+    }
+
+    public void illegalInputKey(IInputKey key) {
+        throw new IllegalArgumentException("The input key " + key + " is not a valid input key.");
+    }
+        
+}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/query/internal/RelationalRuntimeContext.java b/store/src/main/java/org/eclipse/viatra/solver/data/query/internal/RelationalRuntimeContext.java
new file mode 100644
index 00000000..7d1682b2
--- /dev/null
+++ b/store/src/main/java/org/eclipse/viatra/solver/data/query/internal/RelationalRuntimeContext.java
@@ -0,0 +1,187 @@
+package org.eclipse.viatra.solver.data.query.internal;
+
+import static org.eclipse.viatra.solver.data.util.CollectionsUtil.filter;
+import static org.eclipse.viatra.solver.data.util.CollectionsUtil.map;
+
+import java.lang.reflect.InvocationTargetException;
+import java.util.Iterator;
+import java.util.Optional;
+import java.util.concurrent.Callable;
+
+import org.eclipse.viatra.query.runtime.base.core.NavigationHelperImpl;
+import org.eclipse.viatra.query.runtime.matchers.context.IInputKey;
+import org.eclipse.viatra.query.runtime.matchers.context.IQueryMetaContext;
+import org.eclipse.viatra.query.runtime.matchers.context.IQueryRuntimeContext;
+import org.eclipse.viatra.query.runtime.matchers.context.IQueryRuntimeContextListener;
+import org.eclipse.viatra.query.runtime.matchers.context.IndexingService;
+import org.eclipse.viatra.query.runtime.matchers.tuple.ITuple;
+import org.eclipse.viatra.query.runtime.matchers.tuple.Tuple;
+import org.eclipse.viatra.query.runtime.matchers.tuple.TupleMask;
+import org.eclipse.viatra.query.runtime.matchers.tuple.Tuples;
+import org.eclipse.viatra.query.runtime.matchers.util.Accuracy;
+import org.eclipse.viatra.solver.data.model.Model;
+import org.eclipse.viatra.solver.data.query.view.RelationView;
+
+public class RelationalRuntimeContext implements IQueryRuntimeContext {
+        private final RelationalQueryMetaContext metaContext = new RelationalQueryMetaContext();
+        private final RelationUpdateListener relationUpdateListener;
+        private final Model model;
+        
+        public RelationalRuntimeContext(Model model, RelationUpdateListener relationUpdateListener) {
+                this.model = model;
+                this.relationUpdateListener = relationUpdateListener;
+        }
+        
+        @Override
+        public IQueryMetaContext getMetaContext() {
+                return metaContext;
+        }
+
+        // 
+        /**
+         * TODO: check {@link NavigationHelperImpl#coalesceTraversals(Callable)}
+         */
+        @Override
+        public <V> V coalesceTraversals(Callable<V> callable) throws InvocationTargetException {
+        try {
+            return callable.call();
+        } catch (Exception e) {
+            throw new InvocationTargetException(e);
+        }
+        }
+
+        @Override
+        public boolean isCoalescing() {
+                return true;
+        }
+
+        @Override
+        public boolean isIndexed(IInputKey key, IndexingService service) {
+                if(key instanceof RelationView<?>) {
+                        RelationView<?> relationalKey = (RelationView<?>) key;
+                        return this.relationUpdateListener.containsRelationalView(relationalKey);
+                } else {
+                        return false;
+                }
+        }
+
+        @Override
+        public void ensureIndexed(IInputKey key, IndexingService service) {
+                if(!isIndexed(key, service)) {
+                        throw new IllegalStateException("Engine tries to index a new key " +key);
+                }
+        }
+        
+        RelationView<?> checkKey(IInputKey key) {
+                if(key instanceof RelationView) {
+                        RelationView<?> relationViewKey = (RelationView<?>) key;
+                        if(relationUpdateListener.containsRelationalView(relationViewKey)) {
+                                return relationViewKey;
+                        } else {
+                                throw new IllegalStateException("Query is asking for non-indexed key");
+                        }
+                } else {
+                        throw new IllegalStateException("Query is asking for non-relational key");
+                }
+        }
+        
+        @Override
+        public int countTuples(IInputKey key, TupleMask seedMask, ITuple seed) {
+                RelationView<?> relationalViewKey = checkKey(key);
+                Iterable<Object[]> allObjects = relationalViewKey.getAll(model);
+                Iterable<Object[]> filteredBySeed = filter(allObjects,objectArray -> isMatching(objectArray,seedMask,seed));
+                Iterator<Object[]> iterator = filteredBySeed.iterator();
+                int result = 0;
+                while(iterator.hasNext()) {
+                        iterator.next();
+                        result++;
+                }
+                return result;
+        }
+
+        @Override
+        public Optional<Long> estimateCardinality(IInputKey key, TupleMask groupMask, Accuracy requiredAccuracy) {
+                return Optional.empty();
+        }
+
+        @Override
+        public Iterable<Tuple> enumerateTuples(IInputKey key, TupleMask seedMask, ITuple seed) {
+                RelationView<?> relationalViewKey = checkKey(key);
+                Iterable<Object[]> allObjects = relationalViewKey.getAll(model);
+                Iterable<Object[]> filteredBySeed = filter(allObjects,objectArray -> isMatching(objectArray,seedMask,seed));
+                return map(filteredBySeed,Tuples::flatTupleOf);
+        }
+        
+        private boolean isMatching(Object[] tuple, TupleMask seedMask, ITuple seed) {
+                for(int i=0; i<seedMask.indices.length; i++) {
+                        final Object seedElement = seed.get(i);
+                        final Object tupleElement = tuple[seedMask.indices[i]];
+                        if(!tupleElement.equals(seedElement)) {
+                                return false;
+                        }
+                }
+                return true;
+        }
+//      private Object[] toObjectMask(RelationViewKey<?> relationalViewKey, TupleMask seedMask, ITuple seed) {
+//              final int arity = relationalViewKey.getArity();
+//              Object[] result = new Object[arity];
+//              for(int i = 0; i<seedMask.indices.length; i++) {
+//                      result[seedMask.indices[i]] = seed.get(i);
+//              }
+//              return result;
+//      }
+
+        @Override
+        public Iterable<? extends Object> enumerateValues(IInputKey key, TupleMask seedMask, ITuple seed) {
+                return enumerateTuples(key, seedMask, seed);
+        }
+
+        @Override
+        public boolean containsTuple(IInputKey key, ITuple seed) {
+                RelationView<?> relationalViewKey = checkKey(key);
+                return relationalViewKey.get(model,seed.getElements());
+        }
+
+        @Override
+        public void addUpdateListener(IInputKey key, Tuple seed, IQueryRuntimeContextListener listener) {
+                RelationView<?> relationalKey = checkKey(key);
+                this.relationUpdateListener.addListener(relationalKey, seed, listener);
+                
+        }
+
+        @Override
+        public void removeUpdateListener(IInputKey key, Tuple seed, IQueryRuntimeContextListener listener) {
+                RelationView<?> relationalKey = checkKey(key);
+                this.relationUpdateListener.removeListener(relationalKey, seed, listener);
+        }
+
+        @Override
+        public Object wrapElement(Object externalElement) {
+                return externalElement;
+        }
+
+        @Override
+        public Object unwrapElement(Object internalElement) {
+                return internalElement;
+        }
+
+        @Override
+        public Tuple wrapTuple(Tuple externalElements) {
+                return externalElements;
+        }
+
+        @Override
+        public Tuple unwrapTuple(Tuple internalElements) {
+                return internalElements;
+        }
+
+        @Override
+        public void ensureWildcardIndexing(IndexingService service) {
+                throw new UnsupportedOperationException();
+        }
+
+        @Override
+        public void executeAfterTraversal(Runnable runnable) throws InvocationTargetException {
+                runnable.run();
+        }
+}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/query/view/FilteredRelationView.java b/store/src/main/java/org/eclipse/viatra/solver/data/query/view/FilteredRelationView.java
new file mode 100644
index 00000000..edc534b7
--- /dev/null
+++ b/store/src/main/java/org/eclipse/viatra/solver/data/query/view/FilteredRelationView.java
@@ -0,0 +1,48 @@
+package org.eclipse.viatra.solver.data.query.view;
+
+import java.util.function.BiPredicate;
+
+import org.eclipse.viatra.solver.data.model.Model;
+import org.eclipse.viatra.solver.data.model.Tuple;
+import org.eclipse.viatra.solver.data.model.Tuple.Tuple1;
+import org.eclipse.viatra.solver.data.model.representation.Relation;
+
+public class FilteredRelationView<D> extends RelationView<D>{
+        private final BiPredicate<Tuple,D> predicate;
+
+        public FilteredRelationView(Relation<D> representation, BiPredicate<Tuple,D> predicate) {
+                super(representation);
+                this.predicate = predicate;
+        }
+        @Override
+        protected Object[] forwardMap(Tuple key, D value) {
+                return toTuple1Array(key);
+        }
+        @Override
+        public boolean get(Model model, Object[] tuple) {
+                int[] content = new int[tuple.length];
+                for(int i = 0; i<tuple.length; i++) {
+                        content[i] =((Tuple1)tuple[i]).get(0);
+                }
+                Tuple key = Tuple.of(content);
+                D value = model.get(representation, key);
+                return filter(key, value);
+        }
+        
+        public static Object[] toTuple1Array(Tuple t) {
+                Object[] result = new Object[t.getSize()];
+                for(int i = 0; i<t.getSize(); i++) {
+                        result[i] = t.get(i);
+                }
+                return result;
+        }
+        
+        @Override
+        public int getArity() {
+                return this.representation.getArity();
+        }
+        @Override
+        protected boolean filter(Tuple key, D value) {
+                return this.predicate.test(key, value);
+        }
+}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/query/view/FunctionalRelationView.java b/store/src/main/java/org/eclipse/viatra/solver/data/query/view/FunctionalRelationView.java
new file mode 100644
index 00000000..4aa7cfd0
--- /dev/null
+++ b/store/src/main/java/org/eclipse/viatra/solver/data/query/view/FunctionalRelationView.java
@@ -0,0 +1,50 @@
+package org.eclipse.viatra.solver.data.query.view;
+
+import org.eclipse.viatra.solver.data.model.Model;
+import org.eclipse.viatra.solver.data.model.Tuple;
+import org.eclipse.viatra.solver.data.model.Tuple.Tuple1;
+import org.eclipse.viatra.solver.data.model.representation.Relation;
+
+public class FunctionalRelationView<D> extends RelationView<D> {
+
+        public FunctionalRelationView(Relation<D> representation) {
+                super(representation);
+        }
+
+        @Override
+        protected boolean filter(Tuple key, D value) {
+                return true;
+        }
+
+        @Override
+        protected Object[] forwardMap(Tuple key, D value) {
+                return toTuple1ArrayPlusValue(key, value);
+        }
+
+        @Override
+        public boolean get(Model model, Object[] tuple) {
+                int[] content = new int[tuple.length-1];
+                for(int i = 0; i<tuple.length-1; i++) {
+                        content[i] =((Tuple1)tuple[i]).get(0);
+                }
+                Tuple key = Tuple.of(content);
+                @SuppressWarnings("unchecked")
+                D valueInTuple = (D) tuple[tuple.length-1];
+                D valueInMap = model.get(representation, key);
+                return valueInTuple.equals(valueInMap);
+        }
+        
+        public static <D> Object[] toTuple1ArrayPlusValue(Tuple t, D value) {
+                Object[] result = new Object[t.getSize()+1];
+                for(int i = 0; i<t.getSize(); i++) {
+                        result[i] = t.get(i);
+                }
+                result[t.getSize()] = value;
+                return result;
+        }
+        
+        @Override
+        public int getArity() {
+                return this.representation.getArity()+1;
+        }
+}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/query/view/KeyOnlyRelationView.java b/store/src/main/java/org/eclipse/viatra/solver/data/query/view/KeyOnlyRelationView.java
new file mode 100644
index 00000000..11a24fc8
--- /dev/null
+++ b/store/src/main/java/org/eclipse/viatra/solver/data/query/view/KeyOnlyRelationView.java
@@ -0,0 +1,16 @@
+package org.eclipse.viatra.solver.data.query.view;
+
+import org.eclipse.viatra.solver.data.model.Tuple;
+import org.eclipse.viatra.solver.data.model.representation.Relation;
+
+public class KeyOnlyRelationView extends FilteredRelationView<Boolean>{
+
+        public KeyOnlyRelationView(Relation<Boolean> representation) {
+                super(representation, (k,v)->true);
+        }
+        @Override
+        protected boolean filter(Tuple key, Boolean value) {
+                return true;
+        }
+        
+}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/query/view/RelationView.java b/store/src/main/java/org/eclipse/viatra/solver/data/query/view/RelationView.java
new file mode 100644
index 00000000..c5bc5228
--- /dev/null
+++ b/store/src/main/java/org/eclipse/viatra/solver/data/query/view/RelationView.java
@@ -0,0 +1,85 @@
+package org.eclipse.viatra.solver.data.query.view;
+
+import java.util.Objects;
+
+import org.eclipse.viatra.query.runtime.matchers.context.common.BaseInputKeyWrapper;
+import org.eclipse.viatra.solver.data.map.CursorAsIterator;
+import org.eclipse.viatra.solver.data.model.Model;
+import org.eclipse.viatra.solver.data.model.Tuple;
+import org.eclipse.viatra.solver.data.model.representation.Relation;
+
+/**
+ * Represents a view of a {@link Relation} that can be queried.
+ * 
+ * @author Oszkar Semerath
+ *
+ * @param <D>
+ */
+public abstract class RelationView<D> extends BaseInputKeyWrapper<RelationView<D>> {
+        protected final Relation<D> representation;
+
+        protected RelationView(Relation<D> representation) {
+                super(null);
+                this.wrappedKey = this;
+                this.representation = representation;
+        }
+
+        @Override
+        public String getPrettyPrintableName() {
+                return representation.getName();
+        }
+
+        @Override
+        public String getStringID() {
+                return representation.getName() + this.getClass().getName();
+        }
+
+        public Relation<D> getRepresentation() {
+                return representation;
+        }
+
+        @Override
+        public boolean isEnumerable() {
+                return true;
+        }
+
+        protected abstract boolean filter(Tuple key, D value);
+
+        protected abstract Object[] forwardMap(Tuple key, D value);
+
+        public abstract boolean get(Model model, Object[] tuple);
+
+        public Object[] transform(Tuple tuple, D value) {
+                if (filter(tuple, value)) {
+                        return forwardMap(tuple, value);
+                } else
+                        return null;
+        }
+
+        public Iterable<Object[]> getAll(Model model) {
+                return (() -> new CursorAsIterator<>(model.getAll(representation), (k, v) -> forwardMap(k, v),
+                                (k, v) -> filter(k, v)));
+        }
+
+        @Override
+        public int hashCode() {
+                final int prime = 31;
+                int result = 1;
+                result = prime * result + Objects.hash(representation);
+                return result;
+        }
+
+        @Override
+        public boolean equals(Object obj) {
+                if (this == obj)
+                        return true;
+                if (!super.equals(obj))
+                        return false;
+                if (!(obj instanceof RelationView))
+                        return false;
+                @SuppressWarnings("unchecked")
+                RelationView<D> other = ((RelationView<D>) obj);
+                return Objects.equals(representation, other.representation);
+        }
+
+}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/util/CollectionsUtil.java b/store/src/main/java/org/eclipse/viatra/solver/data/util/CollectionsUtil.java
new file mode 100644
index 00000000..21b0a9df
--- /dev/null
+++ b/store/src/main/java/org/eclipse/viatra/solver/data/util/CollectionsUtil.java
@@ -0,0 +1,72 @@
+package org.eclipse.viatra.solver.data.util;
+
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+import java.util.function.Function;
+import java.util.function.Predicate;
+
+public final class CollectionsUtil {
+        private CollectionsUtil() {
+                throw new UnsupportedOperationException();
+        }
+        
+        public static <S,T> Iterator<T> map(Iterator<S> source, Function<S, T> transformation) {
+                return new Iterator<T>() {
+
+                        @Override
+                        public boolean hasNext() {
+                                return source.hasNext();
+                        }
+
+                        @Override
+                        public T next() {
+                                return transformation.apply(source.next());
+                        }
+                };
+        }
+        
+        public static <S,T> Iterable<T> map(Iterable<S> source, Function<S, T> transformation) {
+                return (()->map(source.iterator(),transformation));
+        }
+        
+        public static <T> Iterator<T> filter(Iterator<T> source, Predicate<T> condition) {
+                return new Iterator<T>() {
+                        T internalNext = move();
+                        boolean internalHasNext;
+                        
+                        private T move() {
+                                internalHasNext = source.hasNext();
+                                if(internalHasNext) {
+                                        internalNext = source.next();
+                                }
+                                while(internalHasNext && !condition.test(internalNext)) {
+                                        internalHasNext = source.hasNext();
+                                        if(internalHasNext) {
+                                                internalNext = source.next();
+                                        }
+                                }
+                                return internalNext;
+                        }
+
+                        @Override
+                        public boolean hasNext() {
+                                return internalHasNext;
+                        }
+
+                        @Override
+                        public T next() {
+                                if(!internalHasNext) {
+                                        throw new NoSuchElementException();
+                                } else {
+                                        T result = internalNext;
+                                        move();
+                                        return result;
+                                }
+                        }
+                };
+        }
+        
+        public static <T> Iterable<T> filter(Iterable<T> source, Predicate<T> condition) {
+                return (()->filter(source.iterator(),condition));
+        }
+}