Тестовая настройка
Я включаю мою настройку теста для тех, кто хочет проверить ее самостоятельно:
CREATE TEMP TABLE usage_log (
usage_id int primary key
, pc_id int
, memory_stick_id int);
INSERT INTO usage_log VALUES
(1,1,2)
, (2,3,2)
, (3,3,4)
, (4,5,4)
, (5,5,6)
, (6,7,6)
, (7,9,8)
, (8,9,10)
, (9,3,12)
, (10,11,12)
, (11,11,13);
CREATE TEMP TABLE virus(
pc_id int
, virus_id int);
INSERT INTO virus values
(3, 4)
, (3, 5)
, (5, 6)
/* Alternative test:
TRUNCATE VIRUS;
INSERT INTO virus values
(9, 4)
, (9, 5);
*/
Запрос с двумя рекурсивными CTE
Этот запрос должен найти все компьютеры и флешки, возможно, рекурсивно зараженные внутренним использованием:
WITH RECURSIVE v_start AS (
SELECT pc_id, max(u.usage_id) AS usage_id
FROM virus v
JOIN usage_log u USING (pc_id)
GROUP BY 1
),
v_down AS (
SELECT u.*
FROM usage_log u
JOIN v_start v USING (usage_id)
UNION
SELECT DISTINCT u.*
FROM usage_log u
JOIN v_down v ON u.pc_id = v.pc_id OR u.memory_stick_id = v.memory_stick_id
WHERE u.usage_id < v.usage_id
),
v_up AS (
SELECT u.*
FROM usage_log u
JOIN v_down v USING (usage_id)
UNION
SELECT DISTINCT u.*
FROM usage_log u
JOIN v_up v ON u.pc_id = v.pc_id OR u.memory_stick_id = v.memory_stick_id
WHERE u.usage_id > v.usage_id
)
SELECT pc_id, 1 AS device_type -- PCs
FROM v_up
GROUP BY 1
UNION ALL
SELECT memory_stick_id, 2 AS device_type -- USB-sticks
FROM v_up
GROUP BY 1
ORDER BY 2, 1
Объяснить запрос
Я полагаю, usage_id - это последовательный столбец, который отражает временную шкалу.
Редактировать: в первом CTE v_start Я нахожу последнюю запись в журнале для каждого зараженного ПК. Вид вируса полностью игнорируется. В моей первой версии у меня было самое раннее использование min(usage_id), но это было до того, как я улучшил запрос, включив в него все прекурсоры, и , а затем позволил ему распространиться по временной шкале. Мы должны начать с последнего использования сейчас, которое будет включать еще больше подозреваемых. Мы могли бы сузить поиск, если бы у нас было больше информации для работы.
Первый CTE также RECURSIVE, потому что технически вы можете использовать только один тип CTE одновременно. Без части UNION это фактически обычный CTE . Подробнее в руководстве о предложении WITH (CTE) .
В следующих двух CTE я возвращаюсь назад во времени, а затем снова иду вперед, чтобы найти любой USB-флешку или ПК, который мог соприкоснуться. Хронологический порядок актуален. См. Объяснение ниже.
Обратите внимание, что я использую UNION - вместо UNION ALL в моем первом наброске. Должно быть намного эффективнее устранять дубликаты с каждым шагом.
Финальная SELECT - это функция сводной таблицы бедного человека, в то же время удаляя любые дубликаты среди ПК и USB-флешек. В этом случае оба списка объединяются с UNION ALL. Окончательный результат упорядочен по типу устройства и идентификатору устройства.
Объяснить стратегию
Наихудший сценарий - это то, что мы должны предположить, и это означает, что ПК мог быть заражен во время любого использования.
Нам нужно вырастить назад (v_down) из последнего использования, чтобы включить любые устройства, с которых мог появиться вирус.
Затем, из всех подозрительных рядов, мы прыгаем вперед (v_up) через раз, чтобы найти любое и все устройства, которые могли быть инфицированы дополнительно.
Вуаля: все компьютеры и USB-накопители, которые могут быть задействованы.
Объясните примером
Рассмотрим эту настройку:
INSERT INTO usage_log VALUES
(1,1,2) -- PC 1 connects to stick 3
, (3,3,4) -- PC 3 connects to stick 4
, (2,3,2) -- PC 3 connects to stick 2
, (2,3,6); -- PC 3 connects to stick 6
Здесь ручка 4 никогда не соприкасается с USB 2, прокси или нет. Но они были бы связаны, если бы мы игнорировали график.
Стик 6 подключается к флешке 2 через прокси, потому что он подключается к ПК 3 после того, как установил контакт с флешкой 2.