Is there a way to use OT or CRDT (or something similar) for relational data?

Question

I'm working on a syncing process between offline-first databases and a central server. As a simple example, there are items and departments and an item belongs to a department. Each client can modify any of the entities.

I know for text documents there are algorithms/technology for handling conflicts like OT and CRDT:

• https://en.wikipedia.org/wiki/Operational_transformation
• https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type
• Differences between OT and CRDT

But I'm wondering if you can either use these for more complex structures like you might have in a database. In my case, let's keep it simple and say you have :

• items - id, name, department_id
• departments - id, name

Changes in properties like "name" in individual elements are manageable (maybe using a version, delta, timestamp). Deletes are a little tricker, but you might just discard the name change because the element is deleted.

And it's even more tricky when there are relations. What happens when one client moves items to a department and the other deletes the department.

At a certain level, some of these conflicts are similar to those that could happen in text using OT. Someone changes a title and someone else deletes it. Or someone adds an element to a bulleted list and someone else moves the list to a different part of the document.

My question is, can you use OT or CRDT for relational data and if so, how would you do it? If not, are there other similar algorithms or techniques to handle conflicts in relational data?

Answer 1

There are some recent tools providing relational DBs that sync using CRDTs. Ones that I'm aware of:

• VLCN: SQLite extension that syncs DBs over arbitrary networks (e.g. a WebSocket to a central server).
• ElectricSQL: Platform that syncs between client SQLite DBs and a server Postgres DB.
• TinyBase: Browser data store with an option to synchronize data using CRDT plugins.

On the academic side, these papers describe "Conflict-free Replicated Relations (CRR)", a general approach to modeling relational data using CRDTs:

• Weihai Yu and Claudia-Lavinia Ignat. Conflict-free replicated relations for multi-synchronous database management at edge. In IEEE International Conference on Smart Data Services, SMDS 2020, pages 113--121. IEEE, October 2020. Official, preprint.
• Iver Toft Tomter and Weihai Yu. Augmenting SQLite for local-first software. In European Conference on Advances in Databases and Information Systems, ADBIS 2021, pages 247--257. Springer, August 2021. Official, preprint