Special relativity has no such problem. In SR you can easily define a “time” coordinate everywhere such that all events can be timestamped with that coordinate and will respect causality.
GR at least usually has this property as well. (It doesn’t in the presence of closed timelike curves. It does in weak gravity and in the FLRW metric in cosmology. I’m not sure about the general strong gravity case.
Of course every inertial frame in SR has a well defined time coordinate, but that is not a universal time - other frames will disagree on which of two not-causally-connected events happened first. This is normally explained through the lack of a well defined "simultaneity" across different inertial frames.
You are correct that there is no truly capital-U-Universal time, but it doesn't matter. You control the whole system, so just choose one and call it "true time" and make everything participating in the system match it. Simultaneity in all inertial frames can be translated between one another, so if you go to a new place that has, for example, more time dilation due to different gravity, just note the parameters and translate it into your chosen "true time" and adjust the spread.
My point is not that it isn't possible, but that it is arbitrary and has no physical meaning. Writes thrown away in one frame because another concurrent write was "later" would in fact be kept in another frame. This is why it feels like a 'bug' to me conceptually - it's not how the universe works so why should a database need it.
To summarize, you're saying 'The universe doesn't need linear serializeability, so why should we?'
We build abstractions because they're useful to us, not because they have some special meaning to the universe. Systems with simpler abstractions are easier to understand and therefore build on top of. Complex numbers, for example, have no direct physical meaning in the (non-quantum mechanical) universe but can still be extremely useful and are sometimes the only/best way to solve some classical problems.
If you want to use a database where a required step of querying it is specifying a reference frame that the ordering of events is relative to, feel free. "In fact, for any two spacelike separated events, it is possible to find a reference frame where you can reverse the order in which they happen."[1] Personally I'll take a hard pass on bug reports like 'Foreign key constraint fails in reference frame 0.992c at 37.2Mm vector towards Alpha Centauri' which reads like the climax of Dante's Inferno for Systems Programmers.
No, I'm saying the less impedance mismatch we have with the real physical world the easier things will be to work and make scale beyond earth (we will need a network that can scale to mars, for example, soonish). Fundamentally, we are limited by the laws of physics, so it is beneficial to understand them.
We build abstractions because they are useful, but we also often build the wrong abstractions - this is the entire history of science - building better abstractions. Simpler abstractions are great, but they can limit you. We can build all kinds of wonderful machinery with just classical physics, but if you want the modern world with GPS etc. you need relativity to make it work. All the databases based on truetime are great and marvels of engineering, but they won't be able to scale to even a second planet (getting a GPS equivalent to work across two planets is orders of magnitude harder than the earth one, not to mention the latency).
I'm not condoning your idea of a database that explicitly uses frames, but rather something based on more physical foundations like cause-and-effect. As I mentioned, I think vector clocks satisfy this. But maybe there are other better alternatives.
I'm fully aware of the physics (I have a MPhys, and DPhil in Particle Physics from Oxford).
GR at least usually has this property as well. (It doesn’t in the presence of closed timelike curves. It does in weak gravity and in the FLRW metric in cosmology. I’m not sure about the general strong gravity case.