Блог

Главная - Вопросы по программированию - Максимальная длина последовательной цепочки

Максимальная длина последовательной цепочки

#sql-server #sql-server-2016

#sql-сервер #sql-server-2016

Вопрос:

У меня есть куча пар значений (до, После) от пользователей в таблице. В идеальных сценариях эти значения должны образовывать непрерывную цепочку. например

 | UserId | Before | After |
|--------|--------|-------|
| 1      | 0      | 10    |
| 1      | 10     | 20    |
| 1      | 20     | 30    |
| 1      | 30     | 40    |
| 1      | 40     | 30    |
| 1      | 30     | 52    |
| 1      | 52     | 0     |

К сожалению, эти записи происходят из нескольких разных таблиц и импортируются в мою таблицу исследований. Другие значения в таблице не поддаются упорядочению (например, CreatedDate) из-за некоторых особенностей системы, из-за которых они не упорядочены.

Мне нужно создать список пользователей с пробелами в их данных. например

 | UserId | Before | After |
|--------|--------|-------|
| 1      | 0      | 10    |
| 1      | 10     | 20    |
| 1      | 20     | 30    |
// Row Deleted (30->40)
| 1      | 40     | 30    |
| 1      | 30     | 52    |
| 1      | 52     | 0     |

Я просмотрел другие вопросы последовательной цепочки в SO (и онлайн в целом), но все они, похоже, относятся к заданному проблемному пространству, где одно значение в паре всегда предсказуемым образом ниже другого. В моем случае может быть увеличение или уменьшение.

Есть ли способ быстро вычислить самую длинную цепочку, которую можно создать? У меня есть CreatedAt столбец, который обеспечивал бы некоторый (очень приблизительный) относительный порядок — когда даты отличаются друг от друга более чем на 10 секунд, мы могли бы считать их упорядоченными)

Ответ №1:

Не поэтому ли вы просто после этого получаете первую строку, в которой «цепочка» разорвана?

 SELECT UserID, Before, After
FROM dbo.YourTable YT
WHERE NOT EXISTS (SELECT 1
                  FROM dbo.YourTable NE
                  WHERE NE.After = YT.Before)
  AND YT.Before != 0;

Если вы хотите, чтобы последняя строка находилась там, где строка, в которой «цепочка» разорвана, просто поменяйте местами псевдонимы в столбцах в WHERE в NOT EXISTS .

Комментарии:

1. К сожалению, нет, поскольку значения могут увеличиваться или уменьшаться с помощью любых значений, может существовать один (или много) экземпляров значений до / после. Я попытался использовать LAG функцию (вероятно, мне следует добавить это к моему вопросу на самом деле), чтобы сравнить ожидаемое с фактическим, но порядок все испортил.

2. Обычно ошибка уравновешивается сама собой, но если последняя запись в моем заказе также имеет разницу, она, как правило, не уравновешивается в целом

3. Итак, что вам здесь нужно. Укажите ожидаемые результаты в своем вопросе, @ObsidianPhoenix .

4. Примечание LAG здесь вам не поможет, если значение может уменьшаться и увеличиваться, поскольку у вас (согласно вашим выборочным данным) нет ключа / идентификатора always ascending.

Ответ №2:

далее выполняется иерархическая рекурсия данных вашего примера и вычисляется столбец «chain» count с именем ‘h_level’.

 ;with recur_cte([UserId], [Before], [After], h_level) as (
    select [UserId], [Before], [After], 0 
    from dbo.test_table
    where [Before] is null
    union all
    select tt.[UserId], tt.[Before], tt.[After], rc.h_level 1 
    from dbo.test_table tt join recur_cte rc on tt.UserId=rc.UserId 
                                                and tt.[Before]=rc.[After]
    where tt.[Before]<tt.[after])
select * from recur_cte;

Результаты:

 UserId  Before  After   h_level
1       NULL    10      0
1       10      20      1
1       20      30      2
1       30      40      3
1       30      52      3

Полезно ли это? Не могли бы вы дополнительно определить, какие строки исключить?

Ответ №3:

Если вы хотите, чтобы пользователи имели более одной цепочки:

 select t.UserID
from <T> as t left outer join <T> as t2
    on t2.UserID = t.UserID and t2.Before = t.After
where t2.UserID is null
group by t.UserID
having count(*) > 1;