sql - In a reversely linked list, how to get a sublist of it efficiently?

Question

Supposed I have a reversely linked list, i.e. a data structure where each node points to its predecessor:

A <- B <- C <- D

This is a pattern you can find in Git, for example, where each commit contains the ID of its predecessor.

Now let's assume the following scenario: Every time a new node is added to the list, another component gets notified. Unfortunately, from time to time, some of these notifications get lost, so there is no guarantee that all the notifications arrive. For the list given above, the notifications should be:

A
B
C
D

But, as an example, the following is received:

A
D

Now I would like to detect "holes" in the receiving component. I.e., when D is received, the component can detect that something is missing, since the predecessor of D has not been received as well. So it asks the sending component for the part that is missing. What can be told is: The last one that was received is A, and the newest one received is D.

So now the component managing the original list has the task of effectively figuring out that what is missing is the sublist B <- C.

And this is finally, where my question comes into play: How to do this effectively? I mean, the simplest approach would be to move backwards from D, until we reach A. Everything in between is apparently what's missing.

Supposed every node is stored as a single record in a table in a relational database system: What is the most efficient way to figure out this sublist? Obviously, I could run SELECT in a loop over and over and over again. Is there a better way for this?

The table layout of the Nodes table basically looks like this:

ID                                   | PredecessorID                        | Data
-------------------------------------|--------------------------------------|-----------------
43b1e103-d8c6-40f9-b031-e5d9ef18a739 | null                                 | ...
55f6951b-5ed3-46c8-9ad5-64e496cb521a | 43b1e103-d8c6-40f9-b031-e5d9ef18a739 | ...
3eaa0889-31a6-449d-a499-e4beb9e4cad1 | 55f6951b-5ed3-46c8-9ad5-64e496cb521a | ...

This means, as the IDs are not numerical, you can not simply select the range of the missing nodes.

PS: The only solution I'm aware of is introducing a position field which actually is an increasing numerical ID, but I explicitly do not want to have something as this, as then I need a single point of failure which consistently hands out the next ID, and this is something I would like to avoid.

标签： sqlgitdata-structureslinked-listsingly-linked-list