Поиск паросочетаний графов с помощью T-SQL. Часть 1

Лара шла вдоль полотна по тропинке, протоптанной странниками и богомольцами, и свернула на луговую стежку, ведшую к лесу. Тут она остановилась и, зажмурив глаза, втянула в себя путано-пахучий воздух окрестной шири. Он был роднее отца и матери, лучше возлюбленного и умнее книги. На одно мгновение смысл существования опять открылся Ларе. Она тут — постигала она — для того, чтобы разобраться в сумасшедшей прелести земли и все назвать по имени…

Борис Пастернак «Доктор Живаго», 1957 г.

Общие принципы

Несколько лет назад я столкнулся с одной задачей из области T-SQL. Со временем я понял, что у нее должно быть практическое применение. Если эту идею удастся реализовать, то, вероятно, можно будет найти оптимизированные алгоритмические решения и на их основе работать над адаптацией для T-SQL.

Для многих математика передает «сумасшедшую прелесть земли», хотя Борис Пастернак вряд ли разделял это мнение, когда писал свой роман. Люди сталкиваются с логическими задачами и придумывают математические алгоритмы, чтобы решать их. Человечество экономит время, повторно используя эти решения и непрерывно совершенствуя их. Секрет в том, чтобы дать имена задачам и решениям. Впоследствии, называя задачи правильными именами, вы сокращаете путь к эффективному решению.

Итак, вот с какой задачей из области T-SQL я столкнулся однажды.

Даны две таблицы. Таблица G со столбцами x, y и уникальным ключом, определенным на комбинации (x, y). Таблица M со столбцами x, y и двумя уникальными ключами, один из которых определен на x, а другой на y. В таблице G уже есть несколько строк, а таблица M пустая. Задача — скопировать из G в M как можно больше строк.

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

Недавно я понял, что у этой задачи должно быть интересное практическое применение, а также более формализованное условие. Если мне удастся найти их, то, вероятно, я найду и существующие оптимизированные алгоритмические решения и на их основе смогу работать над адаптацией для T-SQL? Эта мысль оказалась верной.

Начнем с практического применения. Предположим, что в таблице G содержатся пары соискателей рабочих мест (столбец x) и рабочих мест или задач, для выполнения которых у соискателей есть необходимая квалификация (столбец y). В данном временном интервале (например, в течение смены) каждый соискатель может занимать только одно рабочее место, и для замещения каждого рабочего места требуется только один соискатель. Необходимо записать в таблицу M максимальное число пар «соискатель — рабочее место». Естественно, можно подыскать множество других примеров, например распределение учителей по классам, пилотов по рейсам и т. д.

В математической теории графов эта задача известна как поиск максимального по размеру паросочетания (M) в невзвешенном двудольном графе (G). Существуют алгоритмические решения, например алгоритм Форда-Фалкерсона, согласно которому выполняется повторяющийся поиск M c увеличением размера в G и обновление M с использованием симметрической разности этого пути и M.

Если вы смотрите на этот текст бессмысленным взглядом и почесываете затылок — не переживайте. Скоро вы освоитесь в этой теме. Тогда, перечитав предыдущий абзац, вы воскликнете: «Ну конечно!».

Но для этого потребуется несколько статей. В данной статье изложены общие принципы и термины, применяемые в задачах паросочетания графов. Также здесь будут описаны классические задачи, такие как наибольшее паросочетание и паросочетание максимального размера, и даны концептуальные описания соответствующих алгоритмов. В следующих статьях мы рассмотрим адаптации этих алгоритмов для T-SQL.

Принципы и термины

Обсуждать задачу паросочетания графов будет гораздо проще, если предварительно четко определить терминологию. Начнем с самого простого: вершин, ребер и графов.

В теории графов вершиной называется объект, который является частью набора. В нашем примере конкретный соискатель (в частности, ID A) представляет собой величину, или вершину, которая входит в набор соискателей, а конкретное рабочее место (в частности, ID 1) — величину, которая входит в набор рабочих мест.

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

Граф представляет собой набор ребер, соединяющих пары вершин. В нашем примере граф G представляет набор всех возможных ребер (соискатель, рабочее место), где соискатель квалифицирован для выполнения работы.

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

Взвешенный или невзвешенный граф. Граф является взвешенным, если каждому ребру назначен вес. Например, иногда нужно учесть зарплату соискателя или время, которое требуется для завершения работы. Если ребрам не назначен вес, то граф — невзвешенный. Наш граф G невзвешенный, так как в настоящее время его ребрам не назначен вес.

Двудольный граф. Граф является двудольным, если каждое ребро графа соединяет какую-то вершину из двух отдельных, или непересекающихся, наборов. Наш граф G двудольный, так как ребра всегда связывают элемент набора соискателей с элементом набора рабочих мест. Он никогда на соединяет соискателей с соискателями или рабочие места с рабочими местами.

Наш двудольный граф G может быть описан как множество:

G = (X, Y, E)

где X обозначает набор соискателей, Y — набор рабочих мест, а E — набор ребер, представляющих связи «соискатель — рабочие места».

На рисунке 1 показан наш граф с некоторыми образцовыми данными.

Рисунок 1. Граф G

Реализация вершин и ребер в SQL Server

Для реализации графа в SQL Server с использованием традиционных таблиц создайте таблицы X и Y для вершин и G для вершин графа (листинг 1).

Чтобы показать все существующие связи «соискатель — рабочее место», вы можете, естественно, использовать простые внутренние соединения (листинг 2).

Формируются выходные данные, показанные на экране 1.

Экран 1. Выходные данные исполнения листинга 2

Возможно, вы слышали о том, что в SQL Server 2017 появилась встроенная поддержка графов через функцию, именуемую SQL Graph (https://docs.microsoft.com/en-us/sql/relational-databases/graphs/sql-graph-overview). Начальная реализация позволяет явно определить таблицы вершин и ребер (с предложениями AS NODE и AS EDGE соответственно), и вместо традиционных объединений для связывания вершин через ребра, как показано в листинге 2, используется оператор MATCH (https://docs.microsoft.com/en-us/sql/t-sql/queries/match-sql-graph) с оператором WHERE.

В таблице вершин вы просто добавляете оператор AS NODE в конце определения таблицы. Для каждой вставляемой строки вершин SQL Server автоматически создается внутренний уникальный идентификатор (столбец с именем $node_id), который впоследствии используется в таблице ребер для соединения вершин. Пересоздадим таблицы вершин как встроенные таблицы SQL Graph (листинг 3).

Этот программный код формирует входные данные, показанные на экране 2.

Экран 2. Выходные данные исполнения листинга 3

Столбец $node_id представляет собой вычисленное каноническое представление в качестве строки JSON внутреннего столбца graph_id, что, естественно, более экономично (BIGINT).

Создавая таблицу вершин, вы добавляете уточнение, именуемое AS EDGE, в конце определения таблицы. SQL Server неявно создает три столбца: один называется $edge_id и уникально идентифицирует ребро; два, именуемые $from_id и $to_id, представляют вершины ребра. Чтобы добавить строки ребер в таблицу, необходимо предоставить значения $node_id вершин, соединяемых ребром для столбцов $from_id и $to_id. SQL Server автоматически формирует значения столбца $edge_id. В таблице не обязательно присутствуют дополнительные столбцы, поэтому программный код может не иметь явных определений столбцов. Это, без сомнения, можно сделать, если требуется назначить дополнительные свойства ребру, например вес в случае взвешенного графа. В нашем примере G не имеет дополнительных свойств, поэтому он создается и заполняется таким образом, как показано в листинге 4.

Этот программный код формирует выходные данные, представленные на экране 3.

Экран 3. Выходные данные для листинга 3

Чтобы показать все отношения «соискатель — рабочее место», вместо использования объединений укажите таблицы вершин и ребер в операторе FROM запроса, разделенные запятыми; в операторе WHERE введите уточнение MATCH, связывающее X с Y через G с использованием художественных символов ASCII (листинг 5).

Эта форма более изящна по сравнению с традиционной формой объединения, и вы несомненно оцените экономию при работе с более тесными отношениями.

Начальная реализация компонента SQL Graph в SQL Server 2017 пока не включает передовых возможностей, таких как полиморфизм и транзитивное замыкание. Также отсутствуют, например, функции самый короткий и длинный пути, с возможностью указывать поиск в ширину, breadth-first search (BFS), или поиск вглубь, depth-first search (DFS). Они будут добавлены со временем, по мере совершенствования компонента. Как часто бывает с новыми функциями T-SQL, вероятно, они в первую очередь будут появляться в базе данных SQL Azure и позднее в коробочном продукте. Такие возможности могут быть очень полезны при сопоставлении и назначении графов. Пока же мы воспользуемся более традиционным моделированием и инструментарием.

Дополнительно о принципах и терминах

Продолжим наше знакомство с принципами и терминологией графов. На этот раз обратимся к проблеме паросочетания графов. На рисунке 2 приведены примеры, иллюстрирующие некоторые концепции. M1, M2, M3 и M4 представляют различные подмножества ребер из G. Для некоторых Mn ребра, уникальные для G, представлены тонкими серыми линиями, а ребра, общие для G и Mn, показаны толстыми зелеными линиями.

Паросочетание. Паросочетание M в графе G — подмножество ребер G, в котором никакие два ребра не имеют общей вершины. На рисунке 2 M1, M3 и M4 — паросочетания в G, но не M2, так как имеется два ребра с общей вершиной B.

Наибольшее паросочетание. Паро­соче­тание M в графе G является наибольшим паросочетанием, если нельзя добавить больше ребер из G, которых еще нет в M, к M. На рисунке 2 как M3, так и M4 — наибольшее паросочетание. M1 — паросочетание, но не наибольшее, так как вы можете добавить вершину (C, 4).

Рисунок 2. Примеры паросочетаний графов

Паросочетание максимальной мощности. Паросочетание M в графе G является паросочетанием максимальной мощности, если имеет самое большое возможное число ребер. Каждое паросочетание максимальной мощности — наибольшее, но не всякое наибольшее паросочетание является паросочетанием максимальной мощности. На рисунке 2 M4 — паросочетание максимальной мощности, но M3 — нет. Это не распространяется на данные примера графа G, но для каждого графа может существовать несколько различных паросочетаний максимальной мощности.

На данном этапе приведенное выше описание задачи поиска паросочетаний должно стать для вас совершенно очевидным: эта задача известна как поиск паросочетания максимальной мощности (M) в невзвешенном двудольном графе (G).

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

Рисунок 3. Типы путей

Связанная вершина. Для данного паросочетания M в графе G связанная вершина является вершиной, которая принадлежит ребру в M.

Свободная вершина. Для данного паросочетания M в графе G свободная вершина является вершиной, которая не принадлежит никакому ребру в M.

Чередующийся путь. Чередующийся путь представляет собой путь, который состоит из ребер в паросочетании и не в паросочетании. Оба пути на рисунке 3 представляют собой чередующиеся пути.

Аугментальный, или увеличивающийся, путь. Увеличивающийся путь представляет собой чередующийся путь, который начинается и заканчивается свободными вершинами. На рисунке 3 путь на правом изображении представляет собой увеличивающийся путь, а путь на левом изображении — нет. Если P-увеличивающийся путь для паросочетания M в графе G, то вы можете использовать описание P как M-увеличивающийся путь в G.

Симметрическая разность, или исключающее ИЛИ. Симметрическая разность наборов U и V представляет собой набор элементов в каждом из этих наборов, но не в их пересечении. Символы ⊕ (плюс в круге),? (минус в круге) и? обычно используются для обозначения операции симметрической разности. Например, вы можете использовать запись W = U ⊕ V, чтобы показать, что набор W равен симметрической разности между U и V. Например, если U = {2, 3, 5} и V = {5, 7, 11), U ⊕ V = {2, 3, 7, 11}. На рисунке 4 показана диаграмма Венна симметрической разности двух наборов.

Рисунок 4. Симметрическая разность

На данном этапе описание алгоритма Форда-Фалкерсона для поиска паросочетаний максимальной мощности M в G, приведенное выше, должно быть очевидно вам на концептуальном уровне: повторно найти M-увеличивающийся путь в G и обновить M симметрической разностью этого пути и M.

В следующей статье эта задача и ее решение будут рассмотрены более подробно.

Попробуем подготовить решение T-SQL в виде хранимой процедуры с именем MaximalMatching, которая будет максимально эффективна для поиска наибольшего (пока не максимальной мощности) паросочетания M в G.

Относительно G: чтобы проверить правильность своего решения, используем малый набор данных из примера, представленного выше в этой статье. Если требуется воссоздать G, X и Y в традиционных таблицах и заполнить их заново, используйте программный код листинга 5.

Для M возьмем определение таблицы, приведенное в листинге 6.

Наша хранимая процедура должна начинаться с очистки M, а затем заполняться с наибольшим паросочетанием в G.

Чтобы протестировать решение, воспользуемся программным кодом листинга 7 для создания более крупного набора данных (X и Y удалены, так как они для нашей задачи не потребуются).

В следующей статье мы рассмотрим все решения. Затем можно будет перейти к новой задаче — поиску паросочетания максимальной мощности.

SET NOCOUNT ON;
USE tempdb;
-- Очистка
DROP TABLE IF EXISTS dbo.M, dbo.G, dbo.X, dbo.Y;
GO
-- Набор X, например, Applicants
CREATE TABLE dbo.X
(
  x VARCHAR(10) NOT NULL CONSTRAINT PK_X PRIMARY KEY,
  moreonx VARCHAR(20) NOT NULL
);
INSERT INTO dbo.X(x, moreonx) VALUES
  ('A', 'Applicant A'),
  ('B', 'Applicant B'),
  ('C', 'Applicant C'),
  ('D', 'Applicant D');
-- Набор Y, например, Jobs
CREATE TABLE dbo.Y
(
  y INT NOT NULL CONSTRAINT PK_Y PRIMARY KEY,
  moreony VARCHAR(20) NOT NULL
);
INSERT INTO dbo.Y(y, moreony) VALUES
  (1, 'Job 1'),
  (2, 'Job 2'),
  (3, 'Job 3'),
  (4, ‘Job 4’);
-- Граф G = (X, Y, E), например, возможные связи соискатель-рабочее место
CREATE TABLE dbo.G
(
  x VARCHAR(10) NOT NULL
    CONSTRAINT FK_G_X FOREIGN KEY REFERENCES dbo.X,
  y INT NOT NULL
    CONSTRAINT FK_G_Y FOREIGN KEY REFERENCES dbo.Y,
  CONSTRAINT PK_G PRIMARY KEY (x, y)
);
INSERT INTO dbo.G(x, y) VALUES
  ('A', 1),
  ('A', 2),
  ('B', 1),
  ('B', 3),
  ('C', 3),
  (‘C’, 4),
  (‘D’, 3);

SELECT
  X.x AS applicantid, X.moreonx AS applicantname,
  Y.y AS jobid, Y.moreony AS jobname
FROM dbo.X
  INNER JOIN dbo.G
    ON X.x = G.x
  INNER JOIN dbo.Y
    ON G.y = Y.y;

-- Очистка
DROP TABLE IF EXISTS dbo.G, dbo.X, dbo.Y;
GO

-- Набор X, например, Applicants
CREATE TABLE dbo.X
(
  x VARCHAR(10) NOT NULL CONSTRAINT PK_X PRIMARY KEY,
  moreonx VARCHAR(20) NOT NULL
) AS NODE;

INSERT INTO dbo.X(x, moreonx) VALUES
  ('A', 'Applicant A'),
  ('B', 'Applicant B'),
  ('C', 'Applicant C'),
  ('D', 'Applicant D');

SELECT $node_id, x, moreonx FROM dbo.X;

-- Набор Y, например, Jobs
CREATE TABLE dbo.Y
(
  y INT NOT NULL CONSTRAINT PK_Y PRIMARY KEY,
  moreony VARCHAR(20) NOT NULL
) AS NODE;

INSERT INTO dbo.Y(y, moreony) VALUES
  (1, 'Job 1'),
  (2, 'Job 2'),
  (3, 'Job 3'),
  (4, 'Job 4');
SELECT $node_id, y, moreony FROM dbo.Y;

-- Граф G = (V = (X, Y), E), например, возможные соединения соискатель-рабочее место
CREATE TABLE dbo.G AS EDGE;

INSERT INTO dbo.G($from_id, $to_id)
  SELECT X.$node_id, Y.$node_id
  FROM ( VALUES('A', 1),
               ('A', 2),
               ('B', 1),
               ('B', 3),
               ('C', 3),
               ('C', 4),
               ('D', 3) ) AS XY(x, y)
    INNER JOIN dbo.X
      ON XY.x = X.x
    INNER JOIN dbo.Y
      ON XY.y = Y.y;

SELECT $edge_id, $from_id, $to_id
FROM dbo.G;

Листинг 5. Вывод отношений соискатель-рабочее место без использования объединений
SELECT
  X.x AS applicantid, X.moreonx AS applicantname,
  Y.y AS jobid, Y.moreony AS jobname
FROM dbo.X, dbo.G, dbo.Y
WHERE MATCH(X-(G)->Y);

-- Традиционные таблицы X, Y и G
SET NOCOUNT ON;
USE tempdb;

-- Очистка
DROP TABLE IF EXISTS dbo.M, dbo.G, dbo.X, dbo.Y;
GO

-- Набор X, например, Applicants
CREATE TABLE dbo.X
(
  x VARCHAR(10) NOT NULL CONSTRAINT PK_X PRIMARY KEY,
  moreonx VARCHAR(20) NOT NULL
);
INSERT INTO dbo.X(x, moreonx) VALUES
  ('A', 'Applicant A'),
  ('B', 'Applicant B'),
  ('C', 'Applicant C'),
  ('D', 'Applicant D');

-- Набор Y, например, Jobs
CREATE TABLE dbo.Y
(
  y INT NOT NULL CONSTRAINT PK_Y PRIMARY KEY,
  moreony VARCHAR(20) NOT NULL
);
INSERT INTO dbo.Y(y, moreony) VALUES
  (1, 'Job 1'),
  (2, 'Job 2'),
  (3, 'Job 3'),
  (4, ‘Job 4’);

-- Граф G = (X, Y, E), например, возможные соединения соискатель-рабочее место
CREATE TABLE dbo.G

(
  x VARCHAR(10) NOT NULL
    CONSTRAINT FK_G_X FOREIGN KEY REFERENCES dbo.X,
  y INT NOT NULL
    CONSTRAINT FK_G_Y FOREIGN KEY REFERENCES dbo.Y,
  CONSTRAINT PK_G PRIMARY KEY (x, y)
);

INSERT INTO dbo.G(x, y) VALUES
  ('A', 1),
  ('A', 2),
  ('B', 1),
  ('B', 3),
  ('C', 3),
  (‘C’, 4),
  (‘D’, 3);

-- M паросочетается в G
DROP TABLE IF EXISTS dbo.M;
CREATE TABLE dbo.M
(
  x VARCHAR(10) NOT NULL
    CONSTRAINT UQ_M_x UNIQUE,
  y INT NOT NULL
    CONSTRAINT UQ_M_y UNIQUE,
  CONSTRAINT PK_M PRIMARY KEY (x, y),
  CONSTRAINT FK_M_G FOREIGN KEY (x, y) REFERENCES dbo.G(x, y)
);

-- Вспомогательная функция dbo.GetNums
DROP FUNCTION IF EXISTS 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

-- Более крупный набор образцовых данных для тестирования
DROP TABLE IF EXISTS dbo.M, dbo.G, dbo.X, dbo.Y;
GO

CREATE TABLE dbo.G
(
  x VARCHAR(10) NOT NULL,
  y INT NOT NULL,
  CONSTRAINT PK_G PRIMARY KEY (x, y)
);

CREATE TABLE dbo.M
(
  x VARCHAR(10) NOT NULL
    CONSTRAINT UQ_M_x UNIQUE,
  y INT NOT NULL
    CONSTRAINT UQ_M_y UNIQUE,
  CONSTRAINT PK_M PRIMARY KEY (x, y),
  CONSTRAINT FK_M_G FOREIGN KEY (x, y) REFERENCES dbo.G(x, y)
);
DECLARE @n AS INT = 10000000; -- ~ общее число строк
SET @n = SQRT(@n * 2); -- число членов арифметической последовательности
INSERT INTO dbo.G WITH (TABLOCK) (x, y)
  SELECT RIGHT('000000000' + CAST(X.n AS VARCHAR(10)), 10) AS x, Y.n AS y
  FROM dbo.GetNums(1, @n) AS X
    CROSS APPLY (SELECT TOP (@n - X.n + 1) n
                 FROM dbo.GetNums(1, @n)
                 ORDER BY NEWID()) AS Y;