I don't know if this constant full scan could be a performance problem, but I imagined the process to be something like this:
* When you add a relationship you change a chain counter for the number of "inconsistencies" it has, i.e:
  * ````inc```` for a missing prev if not the first and for missing next if not the last.
  * ````dec```` for touching an existing prev if not the first and for touching a next if not the last.
  * If, after adding a relationship to a chain, the chain counter is zero, there's a complete chain right there.

At least I think that should be able to work and would yield a constant O(1) add/check time vs. your O(n) that increases the larger the chains gets. But if it's not a problem then it's not a problem.