正如下面的评论中所述,这不会产生 OP 想要的“最小数字”结果。我暂时将其发布,等待进一步讨论和可能的改进。其他发布的答案可能是最简单的答案。
我将假设一种一般情况,其中顺序 ID
无关紧要,并且 PreviousID
值的序列可能会任意上下跳跃。我还将允许序列可能线性进展然后陷入可能包含或不包含原始 ID 值的循环的情况。
检测循环的一种方法是构建已访问 ID 值列表,并根据已访问 ID 列表检查每个新 ID。由于 SQL Server 没有数组或类似的多值类型,我们可以回退到以字符串形式存储的以逗号分隔的已访问 ID 列表。该列表将使用原始 ID 值初始化,其他 ID 将附加在 CTE 的递归部分中。 适当分隔的 CHARINDEX()
测试可以检查我们是否已到达先前访问的 ID。
就像是:
WITH q AS (
SELECT
0 lvl, ID, PreviousID, PreviousID LastId
,Location, Location as OriginalLocation
,CAST(CONCAT(',', ID, ',') AS VARCHAR(MAX)) as VisitedIDs
,CAST(0 AS BIGINT) AS LoopDetected
FROM IDs
where ID in (select OrderID from ORDERID)
UNION ALL
SELECT lvl+1, q.ID,u.PreviousId,q.PreviousId LastId
,q.Location,u.Location
,CONCAT(VisitedIDs, u.ID, ',')
,CHARINDEX(CONCAT(',', u.ID, ','), VisitedIDs) AS LoopDetected
FROM q
INNER JOIN IDs u ON u.ID = q.PreviousID
WHERE q.LoopDetected = 0
)
select lvl, ID, coalesce(LastId,Id) OriginalId,Location,OriginalLocation
, q.LoopDetected, q.VisitedIDs
, CASE WHEN q.LoopDetected > 0 THEN 'Loop detected' ELSE '' END AS ErrorCheck
from q
where (PreviousId is null OR q.LoopDetected > 0)
order by id, lvl;
请注意, CHARINDEX()
测试用逗号括住 ID 值,以确保例如 ID = 5
仅匹配 ...,5,...
并且不匹配 ...,15,...
或 ...,51,...
。 VisitedIDs
还有额外的逗号来支持此测试。
样本结果(附带一些额外的测试数据):
等级
|
ID
|
原始ID
|
地点
|
原始位置
|
检测到环路
|
访问 ID
|
错误检查
|
0
|
2
|
2
|
1235
|
1235
|
0
|
,2,
|
|
2
|
4
|
2
|
1239
|
1235
|
0
|
,4,3,2,
|
|
4
|
8
|
8
|
1237
|
1237
|
1
|
,8,11,10,9,8,
|
检测到环路
|
4
|
10
|
10
|
1235
|
1235
|
1
|
,10,9,8,11,10,
|
检测到环路
|
4
|
11
|
11
|
1237
|
1237
|
1
|
,11,10,9,8,11,
|
检测到环路
|
8
|
12
|
10
|
9999
|
1235
|
11
|
,12,5,13,6,10,9,8,11,10,
|
检测到环路
|
3
|
23
|
22
|
9999
|
9999
|
0
|
,23,21,24,22,
|
|
如果您想避免创建列表,您可以跟踪一个样本先前 ID(最初是起始 ID),并根据该跟踪 ID 检查每个步骤。问题是可能会出现不包括原始 ID 的循环。为了处理这种情况,您可以以增加的间隔(2 的幂)重置跟踪 ID,这样当进入循环时,跟踪 ID 最终 最终 循环 。
WITH q AS (
SELECT
0 lvl, ID, PreviousID, PreviousID LastId
,Location, Location as OriginalLocation
,ID as LoopCheckID
FROM IDs
where ID in (select OrderID from ORDERID)
UNION ALL
SELECT lvl+1, q.ID,u.PreviousId,q.PreviousId LastId
,q.Location,u.Location
,CASE WHEN lvl & (lvl - 1) = 0 THEN u.ID ELSE q.LoopCheckID END
FROM q
INNER JOIN IDs u ON u.ID = q.PreviousID
WHERE q.PreviousID <> q.LoopCheckID
)
select lvl, ID, coalesce(LastId,Id) OriginalId,Location,OriginalLocation
, q.PreviousID, q.LoopCheckID
, CASE WHEN q.PreviousID = q.LoopCheckID THEN 'Loop detected' ELSE '' END AS ErrorCheck
from q
where (PreviousId is null OR q.PreviousID = q.LoopCheckID)
order by id, lvl;
这 lvl & (lvl - 1) = 0
是一个棘手的位操作检查,当 lvl
是 2 的幂(1、2、4、8、16……)时为真。
示例结果:
等级
|
ID
|
原始ID
|
地点
|
原始位置
|
以前的ID
|
回路检查编号
|
错误检查
|
0
|
2
|
2
|
1235
|
1235
|
p12
|
2
|
|
2
|
4
|
2
|
1239
|
1235
|
p13
|
2
|
|
8
|
8
|
8
|
1237
|
1237
|
11
|
11
|
检测到环路
|
8
|
10
|
10
|
1235
|
1235
|
9
|
9
|
检测到环路
|
8
|
11
|
11
|
1237
|
1237
|
10
|
10
|
检测到环路
|
8
|
12
|
10
|
9999
|
1235
|
9
|
9
|
检测到环路
|
3
|
23
|
22
|
9999
|
9999
|
p14
|
22
|
|
请注意,在上述几种情况下,循环检测比早期基于列表的解决方案晚了几个步骤。
请参阅 this db<>fiddle 了解上述两种技术的演示。
另一种可能的方法是提前检查整个 IDs
表以确定哪些 ID 可以从具有 的行中(反向)到达 PreviousID = null
。一旦建立了该列表,任何不在该列表中的 ID 都将被视为循环的一部分。(我还没有编写这种方法。)