Новость из категории: Информация

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

Содержание:
1. Часть I;
2. Часть II ;
3. Часть III (Вы читаете данный раздел);
4. Часть IV .
Поиск паросочетаний графов с помощью T-SQL. Часть III

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

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

Поиск паросочетаний графов с помощью T-SQL. Часть III
Создание таблиц X и Y для вершин и таблицы G для вершин графа

Чтобы показать все существующие связи «соискатель — рабочее место», вы можете, естественно, использовать простые внутренние соединения (код ниже). Тут нет ничего сложного, и данный этап определенно точно не вызовет у вас не головной, ни зубной боли. Впрочем, если зубы все же заболят, то причина тут явно не в T-SQL и решить ее сможет только опытный стоматолог (подробнее на https://www.lumident.kiev.ua/).

Поиск паросочетаний графов с помощью T-SQL. Часть III
Просмотр существующих связей соискатель — рабочее место

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

Поиск паросочетаний графов с помощью T-SQL. Часть III
Выходные данные исполнения кода, представленного выше

Возможно, вы слышали о том, что в 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 (код ниже).

Поиск паросочетаний графов с помощью T-SQL. Часть III
Создание таблиц вершин с помощью SQL Graph

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

Поиск паросочетаний графов с помощью T-SQL. Часть III
Выходные данные исполнения кода, представленного выше

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

Поиск паросочетаний графов с помощью T-SQL. Часть III
Заполнение столбцов для графа G

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

Поиск паросочетаний графов с помощью T-SQL. Часть III
Выходные данные для кода, представленного выше

Поиск паросочетаний графов с помощью T-SQL. Часть III
Воссоздание множеств G, X и Y в традиционных таблицах и заполнение их

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

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

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

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

Рейтинг статьи

Оценка
0/5
голосов: 0
Ваша оценка статье по пятибальной шкале:
 
 
   

Поделиться

Перевести статью:

Похожие новости

Комментарии

Информация

^ Наверх