Проблема интервальных графов, часть 2

В статье «Проблема интервальных графов, часть 1», опубликованной в предыдущем номере, была представлена задача, предложенная Джоном Полем Куком, дипломированным медицинским работником и обладателем статуса SQL Server MVP. Требовалось рассчитать дозу лекарства для пациента на основе модели данных, выполненной в виде интервального графа. Полное описание задачи приведено в публикации «Counting Drug Exposure in SAS® with Interval Graph Modeling» (www.nesug.org/Proceedings/nesug10/hl/hl06.pdf). Там показано, как использовать для решения SAS. Джон попросил меня применить решение T-SQL на основе наборов.

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

Задача прошлого месяца

В задаче используются данные о назначенных лекарственных препаратах. Запустите программный код в листинге 1, чтобы создать таблицы Prescriptions и Drugs и заполнить их небольшим набором тестовых данных для проверки ваших решений.

Далее запустите программный код в листинге 2, чтобы создать вспомогательную функцию с именем GetNums и заполнить таблицы большими наборами данных для проверки производительности решений.

Первой частью задачи было собрать рецепты для каждого пациента и его лекарственные препараты по списку. На рисунке 1 графически показаны ввод и желаемые результаты (полоски обозначают входные рецептурные периоды, а стрелки — результирующие упакованные назначения).

Рисунок 1. Входные и упакованные интервалы

На рисунке 2 показаны упакованные назначения как вывод запроса.

Рисунок 2. Упакованные назначения

Набор, представляющий упакованные назначения, используется в качестве входного для второй части задачи, которая рассматривается в данной статье. Запустите программный код листинга 3, чтобы создать представление с именем PackedPrescriptions, основанное на запросе в решении из первой части статьи.

Напомню, каким способом представлена информация об упакованных назначениях лекарств. Начальная дата — это первая дата в каждом упакованном периоде, когда пациент принимает лекарство, а дата завершения — дата, следующая за последним днем приема. Например, пациент 1 принял 10 дневных доз лекарства 2, начиная с 1 января 2014 года и заканчивая 11 января 2014 года. В математике такой интервал называют замкнутый слева, открытый справа, так как в него входит начальная точка, но не входит конечная. Стандартное обозначение такого интервала [startdate, enddate).

Задача текущего месяца

Задача этого месяца работает с представлением PackedPrescriptions в качестве входных данных. Задача заключается в определении периодов, в течение которых пациент подвергается риску из-за приема определенного минимального количества препаратов (указывается входной интервал величиной @cnt) конкретного класса. Например, предположим, что @cnt = 3. На рисунке 3 входные рецептурные периоды показаны стрелками, а желательные выходные периоды риска — красными прямоугольниками.

Рисунок 3. Периоды риска более 3

На рисунке 4 показан желаемый вывод, который должно выдать решение.

Рисунок 4. Желаемый результат для подсчета трех и?более лекарств

Аналогично, на рисунках 5 и 6 информация показана в предположении, что @cnt = 4.

Рисунок 5. Периоды риска более 4

Рисунок 6. Желаемый результат для подсчета четырех и более лекарств

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

Первый шаг — разнести даты начала и завершения рецептурного периода по отдельным строкам. Это достигается с помощью следующего запроса (предложение ORDER BY используется для того, чтобы обеспечить ясный порядок представления):

SELECT patientid, drugid, type, dt
FROM dbo.PackedPrescriptions
CROSS JOIN(VALUES(1),(-1)) AS ET(type)
CROSS APPLY(VALUES(CASE type WHEN 1 THEN startdate WHEN -1 THEN enddate END)) AS A(dt)
ORDER BY patientid, drugid, dt;

В запросе применяется перекрестное объединение для формирования двух копий каждой исходной строки из представления. Одна копия представляет события начала (отмечены типом 1), а другая представляет события завершения (отмечены типом -1). Затем оператор CROSS APPLY используется для возвращения к нужной дате для текущей строки (начала или завершения) как нового столбца dt. На рисунке 7 показан вывод этого запроса в сокращенном виде.

Рисунок 7. Раздельные даты начала и завершения (сокращенный вид)

Второй шаг — вычислить число лекарственных препаратов, принимаемых одновременно, по пациенту и дате. Это делается с помощью следующего запроса:

SELECT patientid, dt, SUM(type) AS datecnt,
SUM(SUM(type)) OVER(PARTITION BY patientid
ORDER BY dt
ROWS UNBOUNDED PRECEDING) AS cnt
FROM dbo.PackedPrescriptions
CROSS JOIN(VALUES(1),(-1)) AS ET(type)
CROSS APPLY(VALUES(CASE type WHEN 1 THEN startdate WHEN -1 THEN enddate END)) AS A(dt)
GROUP BY patientid, dt
ORDER BY patientid, dt;

Отправная точка — запрос из предыдущего шага. Несведенные события группируются по пациенту и дате. Сгруппированный результат статистической обработки SUM применяется к столбцу типа (помните, 1 — событие начала, а -1 — событие завершения) для вычисления дневной разности. Например, если два периода начались и три завершились, то в этот день разность составляет -1. Затем оконный результат статистической обработки SUM вычисляет сгруппированный SUM с нарастающим итогом, чтобы подвести баланс по дате (препараты, одновременно принятые в этот день). На рисунке 8 показан вывод этого шага.

Рисунок 8. Число лекарственных препаратов, одновременно принимаемых пациентом в течение дня

Цель третьего шага — вычислить два столбца с именами isstart и isend, отмечая, является ли дата началом или концом периода, в который пациент подвергается риску. Ниже приводится запрос, реализующий третий шаг:

DECLARE @cnt AS INT = 3;
WITH C1 AS
(
SELECT patientid, dt, SUM(type) AS datecnt,
SUM(SUM(type)) OVER(PARTITION BY patientid
ORDER BY dt
ROWS UNBOUNDED PRECEDING) AS cnt
FROM dbo.PackedPrescriptions
CROSS JOIN(VALUES(1),(-1)) AS ET(type)
CROSS APPLY(VALUES(CASE type WHEN 1 THEN startdate WHEN -1 THEN enddate END)) AS A(dt)
GROUP BY patientid, dt
)
SELECT *
-- , (ROW_NUMBER() OVER(PARTITION BY patientid ORDER BY dt) — 1) / 2 + 1 AS grp
FROM C1
CROSS APPLY(VALUES(CASE WHEN cnt >= @cnt AND cnt — datecnt < @cnt THEN 1 ELSE 0 END,
CASE WHEN cnt < @cnt AND cnt — datecnt >= @cnt THEN 1 ELSE 0 END )) AS A(isstart, isend)
--WHERE isstart = 1 OR isend = 1
ORDER BY patientid, dt;

Этот запрос определяет CTE с именем C1 на основе запроса, реализующего второй шаг. Внешний запрос вычисляет isstart как 1, если выполняются два условия:

* Cnt (число препаратов, одновременно принятых в этот день) больше или равно @cnt (входной подсчет);

* Cnt в предыдущий день (cnt — datecnt) был меньше, чем @cnt.

В противном случае программа вычисляет isstart как 0.

Аналогично, isend принимает значение 1, если выполняются условия:

* Cnt меньше или равно @cnt;

* Cnt в следующий день больше или равен, чем @cnt.

В противном случае программа вычисляет isend как 0. На рисунке 9 показан вывод на третьем шаге.

Рисунок 9. Вычисление isstart и isend

Четвертый шаг предназначен для фильтрации событий начала и завершения. Также вычисляется идентификатор целевого периода (grp) для каждой пары последовательных событий начала и завершения. Возможно, вы заметили, что программный код шага 3 уже содержит элементы, реализующие шаг 4, выключенные комментариями. Снимите значки комментариев с операций фильтрации и вычисления grp и повторно выполните программный код, один раз @cnt = 3 и вновь с @cnt = 4. На рисунке 10 показан результат выполнения кода с @cnt = 3.

Рисунок 10. Фильтрованные события начала и завершения для подсчетов со значением три и более

На рисунке 11 показан результат этого кода с @cnt = 4.

Рисунок 11. Фильтрованные события начала и завершения для подсчетов со значением четыре и более

Решение завершается шагом 5, на котором выполняется сведение фильтрованных событий, чтобы возвратить каждый период, в котором пациент подвергается риску в одной строке. Для этого следует определить CTE с именем C2 на основе внешнего запроса из шага 4. Затем во внешнем запросе этого шага группируются строки из C2 по patientid и grp, и возвращается MIN(dt) как дата начала и MAX(dt) как дата завершения. В листинге 4 приведен полный исходный текст решения.

Полное решение

На моем компьютере полное решение с большим набором тестовых данных было выполнено за 9 секунд. Это весьма неплохая производительность, учитывая сложность задачи. Около 3 секунд приходится на первую часть решения (описанную в статье «Проблема интервальных графов, часть 1») с упаковочной логикой. Оставшиеся 6 секунд приходятся на вторую часть (описанную в этой статье). Возможно, вам удастся найти и более быстрое решение!

SET NOCOUNT ON;
USE tempdb;
IF OBJECT_ID(N'dbo.Prescriptions', N'U') IS NOT NULL DROP TABLE dbo.Prescriptions;
IF OBJECT_ID(N'dbo.Patients', N'U') IS NOT NULL DROP TABLE dbo.Patients;
CREATE TABLE dbo.Patients
(
patientid INT NOT NULL,
CONSTRAINT PK_Patients PRIMARY KEY(patientid)
);
CREATE TABLE dbo.Prescriptions
(
prescriptionid INT NOT NULL IDENTITY,
patientid INT NOT NULL,
drugid INT NOT NULL,
startdate DATE NOT NULL,
numdays INT NOT NULL,
enddate AS DATEADD(day, numdays, startdate),
CONSTRAINT CHK_Prescriptions_ed_sd CHECK(numdays > 0)
);
CREATE UNIQUE CLUSTERED INDEX idx_start
ON dbo.Prescriptions(patientid, drugid, startdate, prescriptionid);
ALTER TABLE dbo.Prescriptions
ADD CONSTRAINT PK_Prescriptions PRIMARY KEY NONCLUSTERED(prescriptionid);
— программный код для заполнения таблиц небольшим набором тестовых данных
TRUNCATE TABLE dbo.Prescriptions;
TRUNCATE TABLE dbo.Patients;
INSERT INTO dbo.Patients(patientid) VALUES(1);
INSERT INTO dbo.Prescriptions(patientid, drugid, startdate, numdays) VALUES
(1, 1, '20140101', 3),
(1, 2, '20140101', 5),
(1, 3, '20140102', 4),
(1, 4, '20140102', 5),
(1, 4, '20140103', 2),
(1, 2, '20140105', 5),
(1, 3, '20140106', 4),
(1, 1, '20140107', 3),
(1, 4, '20140108', 1),
(1, 4, '20140120', 4),
(1, 4, '20140122', 1),
(1, 5, '20140212', 3),
(1, 5, '20140215', 3),
(1, 5, '20140220', 1),
(1, 5, '20140223', 1),
(1, 5, '20140226', 1);

IF OBJECT_ID(N'dbo.GetNums', N'IF') IS NOT NULL DROP FUNCTION dbo.GetNums;
GO
CREATE FUNCTION dbo.GetNums(@low AS BIGINT, @high AS BIGINT) RETURNS TABLE
AS
RETURN
WITH
L0 AS (SELECT c FROM (SELECT 1 UNION ALL SELECT 1) AS D(c)),
L1 AS (SELECT 1 AS c FROM L0 AS A CROSS JOIN L0 AS B),
L2 AS (SELECT 1 AS c FROM L1 AS A CROSS JOIN L1 AS B),
L3 AS (SELECT 1 AS c FROM L2 AS A CROSS JOIN L2 AS B),
L4 AS (SELECT 1 AS c FROM L3 AS A CROSS JOIN L3 AS B),
L5 AS (SELECT 1 AS c FROM L4 AS A CROSS JOIN L4 AS B),
Nums AS (SELECT ROW_NUMBER() OVER(ORDER BY (SELECT NULL)) AS rownum
FROM L5)
SELECT TOP(@high — @low + 1) @low + rownum — 1 AS n
FROM Nums
ORDER BY rownum;
GO
DECLARE
@numpatients AS INT = 10000,
@numdrugs AS INT = 10,
@numprescriptions AS INT = 10,
@firststartdate AS DATE = '20140101',
@laststartdate AS DATE = '20141231',
@maxnumdays AS INT = 30;
TRUNCATE TABLE dbo.Prescriptions;
TRUNCATE TABLE dbo.Patients;
INSERT INTO dbo.Patients(patientid)
SELECT PT.n AS patientid
FROM dbo.GetNums(1, @numpatients) AS PT;
INSERT INTO dbo.Prescriptions(patientid, drugid, startdate, numdays)
SELECT
PT.n AS patientid,
D.n AS drugid,
DATEADD(day,
ABS(CHECKSUM(NEWID())) % DATEDIFF(day, @firststartdate, @laststartdate),
@firststartdate ) AS startdate,
ABS(CHECKSUM(NEWID())) % @maxnumdays + 1 AS numdays
FROM dbo.GetNums(1, @numpatients) AS PT
CROSS JOIN dbo.GetNums(1, @numdrugs) AS D
CROSS JOIN dbo.GetNums(1, @numprescriptions) AS PR;

IF OBJECT_ID(N'dbo.PackedPrescriptions', N'V') IS NOT NULL
DROP VIEW dbo.PackedPrescriptions;
GO
CREATE VIEW dbo.PackedPrescriptions
AS
WITH C1 AS
(
SELECT prescriptionid, patientid, drugid, startdate, numdays,
DATEADD(day,
— SUM(numdays) OVER(PARTITION BY patientid, drugid
ORDER BY startdate, prescriptionid
ROWS UNBOUNDED PRECEDING) + numdays,
startdate) AS grphelper
FROM dbo.Prescriptions
),
C2 AS
(
SELECT patientid, drugid, startdate, numdays,
MAX(grphelper) OVER(PARTITION BY patientid, drugid
ORDER BY startdate, prescriptionid
ROWS UNBOUNDED PRECEDING) AS grp
FROM C1
)
SELECT
patientid, drugid,
MIN(startdate) AS startdate,
DATEADD(day, SUM(numdays), MIN(startdate)) AS enddate
FROM C2
GROUP BY patientid, drugid, grp;
GO

DECLARE @cnt AS INT = 3;
WITH C1 AS
(
SELECT patientid, dt, SUM(type) AS datecnt,
SUM(SUM(type)) OVER(PARTITION BY patientid
ORDER BY dt
ROWS UNBOUNDED PRECEDING) AS cnt
FROM dbo.PackedPrescriptions
CROSS JOIN(VALUES(1),(-1)) AS ET(type)
CROSS APPLY(VALUES(CASE type WHEN 1 THEN startdate WHEN -1 THEN enddate END)) AS A(dt)
GROUP BY patientid, dt
),
C2 AS
(
SELECT *,
(ROW_NUMBER() OVER(PARTITION BY patientid ORDER BY dt) — 1) / 2 + 1 AS grp
FROM C1
CROSS APPLY(VALUES(CASE WHEN cnt >= @cnt AND cnt — datecnt < @cnt THEN 1 ELSE 0 END,
CASE WHEN cnt < @cnt AND cnt — datecnt >= @cnt THEN 1 ELSE 0 END )) AS A(isstart, isend)
WHERE isstart = 1 OR isend = 1
)
SELECT patientid, MIN(dt) AS startdate, MAX(dt) AS enddate
FROM C2
GROUP BY patientid, grp;
GO