# Data structure for identifying elements while keeping track of relation

I'm looking for a data structure representing a finite set $$I$$ and a $$d$$-relation $$R \subseteq I^d$$ such that the following operations can be implemented efficiently:

1. Add a new element $$i$$ to $$I$$.
2. Identify elements $$i, j \in I$$, i.e. take the quotient set $$I' = I_{/ i \sim j}$$ and take for $$R'$$ the obvious relation on $$I'$$ induced by $$R$$, i.e. $$$$R'([i_1], \dots, [i_d]) \iff \exists j_1 \sim i_1, \dots, i_n \sim j_n: R(j_1, \dots, j_n)$$$$ where $$[-]$$ denotes equivalence class under $$\sim$$. For example, if $$d = 2$$ and $$k \neq i, j$$, then $$R'([i], [k]) \iff R(i, k) \lor R(j, k)$$.
3. Check whether elements $$i, j \in I$$ are equal/represent the same element.
4. Insert a tuple $$(i_1, \dots, i_d)$$ into $$R$$
5. Check whether a tuple $$(i_1, \dots, i_d)$$ is in $$R$$.

If it weren't for the relation $$R$$, then a union-find data structure would be a perfect solution, supporting 1, 2 (minus the relation part) and 3 in essentially constant time. On the other hand, a hash table would support 4 and 5 in constant time. I don't see a way of combining those data structures without blowing up some step to $$O(\mathrm{max}(|R|, |I|))$$ though.

Bonus points if the data structure can be adapted to support snapshots, i.e. saving the current $$(I, R)$$ and reverting back to it later efficiently.