How to become an author
Search
Write a publication
Pull to refresh

Как найти самый длинный непрерывный ряд событий с помощью SQL

Reading time5 min
Views33K
SQL*Data Mining*Data visualization*
Translation
Original author: Lukas Eder
Задача поиска непрерывных последовательностей событий довольно легко решается с помощью SQL. Давайте уточним, что из себя представляют эти последовательности.

Для примера возьмём Stack Overflow. Он использует клёвую систему репутации с наградами за определенные достижения. Как и во многих социальных проектах, они поощряют пользователей ежедневно посещать ресурс. Обратим внимание на эти две награды:



Нетрудно понять, что они означают. Зайдите на сайт в первый день. Затем на второй день. Затем на третий (возможно несколько раз, это не имеет значения). Не зашли на четвёртый? Начинаем считать заново.

Как отследить это с помощью SQL?


Для доступа к данным мы будем использовать Stack Exchange Data Explorer.

Обратите внимание, что мы не будем запрашивать даты посещений, так как эта информация не предоставляется. Вместо этого, давайте запросим даты размещённых пользователем сообщений.

В качестве базы данных используется SQL Server, следовательно мы можем использовать следующий запрос:

SELECT DISTINCT CAST(CreationDate AS DATE) AS date
FROM Posts
WHERE OwnerUserId = ##UserId##
ORDER BY 1

…который выдаст что-то подобное:

date          
----------
2010-11-26
2010-11-27
2010-11-29
2010-11-30
2010-12-01
2010-12-02
2010-12-03
2010-12-05
2010-12-06
2010-12-07
2010-12-08
2010-12-09
2010-12-13
2010-12-14
...
(769 rows)

(можете сделать запрос самостоятельно, здесь)

Как можно заметить, есть несколько пропусков:

date          
--------------------------------------
2010-11-26
2010-11-27 <---- Пропуск после 2 дней

2010-11-29
2010-11-30
2010-12-01
2010-12-02
2010-12-03 <---- Пропуск после 5 дней

2010-12-05
2010-12-06
2010-12-07
2010-12-08
2010-12-09 <---- Пропуск после 5 дней

2010-12-13
2010-12-14
...

Человеку легко увидеть, сколько дней подряд идут даты без пропусков. Но как сделать это посредством SQL?

Чтобы упростить задачу, давайте «сохраним» индивидуальные запросы в обобщённых табличных выражениях. Предыдущий запрос мы назовём dates:

WITH
 
  -- This table contains all the distinct date 
  -- instances in the data set
  dates(date) AS (
    SELECT DISTINCT CAST(CreationDate AS DATE)
    FROM Posts
    WHERE OwnerUserId = ##UserId##
  )
...

Теперь цель полученного запроса — поместить все последовательные даты в одну и ту же группу, чтобы мы могли объединить их. Вот как мы это сделаем:

SELECT
  COUNT(*) AS consecutiveDates,
  MIN(week) AS minDate,
  MAX(week) AS maxDate
FROM groups
GROUP BY grp -- This "grp" value will be explained later
ORDER BY 1 DESC, 2 DESC

Мы хотим объединить каждую группу «grp» и подсчитать количество дат в группе, а также найти минимум и максимум в каждой группе.

Создание групп для последовательных дат


Давайте теперь посмотрим на результат запроса, и, чтобы было понятнее, мы пронумеруем строки независимо от пропусков в датах:

row number   date          
--------------------------------
1            2010-11-26
2            2010-11-27

3            2010-11-29 <-- пропуск перед этой строкой
4            2010-11-30
5            2010-12-01
6            2010-12-02
7            2010-12-03

8            2010-12-05 <-- пропуск перед этой строкой

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

SELECT
  ROW_NUMBER() OVER (ORDER BY date) AS [row number],
  date
FROM dates

Теперь давайте посмотрим вот такой интересный запрос:

WITH
 
  -- This table contains all the distinct date 
  -- instances in the data set
  dates(date) AS (
    SELECT DISTINCT CAST(CreationDate AS DATE)
    FROM Posts
    WHERE OwnerUserId = ##UserId##
  ),
   
  -- Generate "groups" of dates by subtracting the
  -- date's row number (no gaps) from the date itself
  -- (with potential gaps). Whenever there is a gap,
  -- there will be a new group
  groups AS (
    SELECT
      ROW_NUMBER() OVER (ORDER BY date) AS rn,
      dateadd(day, -ROW_NUMBER() OVER (ORDER BY date), date) AS grp,
      date
    FROM dates
  )
SELECT *
FROM groups
ORDER BY rn

Приведённый выше запрос даёт нам следующий результат:

rn  grp          date          
--- ----------   ----------
1   2010-11-25   2010-11-26
2   2010-11-25   2010-11-27

3   2010-11-26   2010-11-29
4   2010-11-26   2010-11-30
5   2010-11-26   2010-12-01
6   2010-11-26   2010-12-02
7   2010-11-26   2010-12-03

8   2010-11-27   2010-12-05
9   2010-11-27   2010-12-06
10  2010-11-27   2010-12-07
11  2010-11-27   2010-12-08
12  2010-11-27   2010-12-09

13  2010-11-30   2010-12-13
14  2010-11-30   2010-12-14

(можете сделать запрос самостоятельно, здесь)

Все, что мы сделали, это вычли номер строки из дня, чтобы получить новую дату «grp». Полученная таким образом дата не имеет смысла, это просто вспомогательное значение.

Однако, мы можем гарантировать, что для последовательных дат, значение «grp» будет одинаковое, потому что для всех последовательно идущих дат, следующие два уравнения верны:

date2 - date1 = 1 // разница в днях между двумя датами
rn2 - rn1 = 1 // Разница в цифрах строк

Для непоследовательных дат, разница в номерах строк будет также 1, но разница в днях будет больше единицы. Группы теперь можно легко различить:

rn  grp          date          
--- ----------   ----------
1   2010-11-25   2010-11-26
2   2010-11-25   2010-11-27

3   2010-11-26   2010-11-29
4   2010-11-26   2010-11-30
5   2010-11-26   2010-12-01
6   2010-11-26   2010-12-02
7   2010-11-26   2010-12-03

8   2010-11-27   2010-12-05
9   2010-11-27   2010-12-06
10  2010-11-27   2010-12-07
11  2010-11-27   2010-12-08
12  2010-11-27   2010-12-09

13  2010-11-30   2010-12-13
14  2010-11-30   2010-12-14

Таким образом, финальный запрос будет следующим:

WITH
 
  -- This table contains all the distinct date 
  -- instances in the data set
  dates(date) AS (
    SELECT DISTINCT CAST(CreationDate AS DATE)
    FROM Posts
    WHERE OwnerUserId = ##UserId##
  ),
   
  -- Generate "groups" of dates by subtracting the
  -- date's row number (no gaps) from the date itself
  -- (with potential gaps). Whenever there is a gap,
  -- there will be a new group
  groups AS (
    SELECT
      ROW_NUMBER() OVER (ORDER BY date) AS rn,
      dateadd(day, -ROW_NUMBER() OVER (ORDER BY date), date) AS grp,
      date
    FROM dates
  )
SELECT
  COUNT(*) AS consecutiveDates,
  MIN(week) AS minDate,
  MAX(week) AS maxDate
FROM groups
GROUP BY grp
ORDER BY 1 DESC, 2 DESC

И его результат:

consecutiveDates minDate       maxDate       
---------------- ------------- ------------- 
14               2012-08-13    2012-08-26
14               2012-02-03    2012-02-16
10               2013-10-24    2013-11-02
10               2011-05-11    2011-05-20
9                2011-06-30    2011-07-08
7                2012-01-17    2012-01-23
7                2011-06-14    2011-06-20
6                2012-04-10    2012-04-15
6                2012-04-02    2012-04-07
6                2012-03-26    2012-03-31
6                2011-10-27    2011-11-01
6                2011-07-17    2011-07-22
6                2011-05-23    2011-05-28
...

(можете сделать запрос самостоятельно, здесь)

Бонус: найти последовательность недель


То, что мы использовали дни — это просто наш выбор. Мы взяли точное время и округлили его до дня с помощью функции CAST:

SELECT DISTINCT CAST(CreationDate AS DATE)

Если бы мы хотели узнать последовательность, например, из недель, мы могли бы округлять время до недель:

SELECT DISTINCT datepart(year, CreationDate) * 100 
              + datepart(week, CreationDate)

Этот запрос использует численное выражение года и недели и создаёт числа типа 201503 для третьей недели 2015 года. Остальная часть запроса остаётся без изменений:

WITH
  weeks(week) AS (
    SELECT DISTINCT datepart(year, CreationDate) * 100 
                  + datepart(week, CreationDate)
    FROM Posts
    WHERE OwnerUserId = ##UserId##
  ),
  groups AS (
    SELECT
      ROW_NUMBER() OVER (ORDER BY week) AS rn,
      dateadd(day, -ROW_NUMBER() OVER (ORDER BY week), week) AS grp,
      week
    FROM weeks
  )
SELECT
  COUNT(*) AS consecutiveWeeks,
  MIN(week) AS minWeek,
  MAX(week) AS maxWeek
FROM groups
GROUP BY grp
ORDER BY 1 DESC, 2 DESC

И вот что мы получим:

consecutiveWeeks minWeek maxWeek 
---------------- ------- ------- 
45               201401  201445  
29               201225  201253  
25               201114  201138  
23               201201  201223  
20               201333  201352  
16               201529  201544  
15               201305  201319  
12               201514  201525  
12               201142  201153  
9                201502  201510  
7                201447  201453  
7                201321  201327  
6                201048  201053  
4                201106  201109  
3                201329  201331  
3                201102  201104  
2                201301  201302  
2                201111  201112  
1                201512  201512

(можете сделать запрос самостоятельно, здесь)

Неудивительно, что последовательные недели охватывают гораздо более длинные диапазоны, так как автор регулярно пишет на Stack Overflow.
Tags:
Hubs:
Total votes 22: ↑21 and ↓1+20
Comments16
33
Karma
0
Rating
@Z80A

Тыжпрограммист

Send message

Articles

Show the best of all time

Your account

Sections

Information

Services

Support
© 2006–2024, Habr