You're discussing a problem that already exists today, just on a smaller scale. It'w worth noting that there are (for the purposes of this discussion) two kinds of data.
Data that comes from all over and has the potential to simultaneously affect the same data element. A ruthless example is a stock exchange. A more common example would be a retail shop.
Data that really can only come from one source. An example of this is an individual's medical data. A person can only be in one place at one time, so there's no risk to their medical data running into concurrency problems when it's absorbed into, e.g., the "central database."
Both kinds of data have problems when they become massive (and we're talking massive on a scale that boggles the mind). Gratefully, the vast majority of data is archival, which means it doesn't need to be synchronized. But we do have one practical limitation to consider first.
As we understand physics today, nothing moves faster than the speed of light. That means, for example, we're modulating a very impressive laser to ship data between star systems. It also means data updates between star systems take years.
Let's ignore C
C is boring. You cannot have a centralized galactic government if C is involved. By the time the reigning monarch's first decree arrived at the far rim said monarch and hundreds of generations of heirs would be long dead. So, let's ignore C and suggest you have a way to transit data in a pracitcal amount of time... like instantaneously.
Not all databases need centralization
First of all, most of your data will be gathered regionally and only the important bits (e.g. summaries, abstracts, compounded affects, etc.) would be moved elsewhere. There's no need for every database in the galaxy to have a copy of Lauren Farseer's latest novel. In this regard, you need to think like a library system. The less common data is copied out to remote users as-needed rather than stored at all locations. This may increase access time, but it makes the database more practical.
Concurency needs rules
Is it fair that your bid for Omicronian Jelly Beans came in so late that the price had gone up and down a dozen times, making it no longer valid? Even in today's marketplace, stocks and commodities are usually purchased through brokers, people "on site" who will act on your behalf. It's been a while since I cared about organizations like Ameritrade, but when I was trading, even though it looked like I was directly on the floor expressing trades, I wasn't. Ameritrade was my broker and they were acting on my behalf. And according to their rules, if my order came in too late, it was ignored.
You'll need to set up similar rules. No matter how "instantaneous" communication appears to be, it really isn't. It isn't even now on our own planet and never will be. You can always slice time just a bit thinner. Rules exist in today's exchanges to ensure that this very problem can't upset the trading system. You'll need to set up similar rules.
But, bear in mind my previous assertion. What's the point of bidding on Rigelian Wheat when you're on the far rim of the galaxy? Shipping won't get it to you before your sun has turned supernova. Even at FTL... that's a long trip. So why would anyone care other than to play the market for profit? One of your first rules will likely be there is no central stock exchange, only regional exchanges, and goods/stocks for sale on those exchanges must actually be within the region before they can be listed.
And this is likely the specific answer to your question, despite my lengthy soliloquy. People on one side of the galaxy don't need real-time data on flight availability from the other side of the galaxy. Your database management will become highly localized with rules governing how that information gets outside the local regions. If, for some reason, the Monarch wants to go on a tour of the galaxy, I can imagine a "bot" the manages the itineary "as he goes," dealing with databases in local regions and pre-informing the next region in line to anticipate his requests.
Tagging data really isn't your problem
Today we can tag data with time to the microsecond. Frankly, it would be trivial to tag it with time to the nanosecond... but we really don't have a reason to do that (yet). Your future world could easily tag timem to the femtosecond, which would alleviate most concurrency problems. Tag the data as well with an "originating location" and you're done making the data element unique. This isn't at all different than how the Internet works today. We started with IPv4 (255.255.255.255) which addressed 4.3 billion computers. Now we have IPv6 that cann address 281.4 trillion computers. You just keep adding blocks of 256 (remember that computers start at 0). And just in case you're a privacy nut, you can rest assured that the Galactic Fraternity of TOR can be found in your neighbor's homes throughout the galaxy.
Your real problem is relevancy
The amount of data you're talking about is ENORMOUS. In our world today, the top-10 data centers add up to about 25 MILLION square feet. That's a lot of hard drives! So, your real problem is figuring out how to balance local needs (million square feet data centers placed around a planet) with regional solutions (that fill small moons) to "galactic" solutions that fill entire planets.
Frankly, coordinating the data is easy compared to finding places to put it on that scale. This means you'll need a spectacular effort to realize the relevance of data ... and dump what isn't.
If, on the other hand, you're dedicated to retaining every random thought that enters a teenager's mind and every photo mom takes of the family vacation... then the option is to have Death Star sized data centers floating by the millions throughout the galaxy.