Введение 4
1. Обзор 6
1.1. Базовые определения 6
1.2. Алгоритм, основанный на произведении Кронекера ... 7
1.3. Алгоритм, основанный на матричном умножении .... 10
1.4. Сравнение алгоритмов, основанных на операциях линейной алгебры 10
1.5. Библиотека SuiteSparse 11
2. Постановка задачи 13
3. Улучшение построения индекса 14
4. Алгоритм восстановления путей 16
5. Алгоритм построения индекса с заданным набором стартовых вершин 18
6. Детали реализаций 21
7. Замеры производительности 23
7.1. Окружение и данные для экспериментов 23
7.2. Эксперименты над улучшением алгоритма построения индекса 24
7.3. Эксперименты над алгоритмом извлечения путей .... 26
7.4. Эксперименты над алгоритмом обнаружения путей с заданным набором стартовых вершин 27
Заключение 29
Список литературы 30
Одной из фундаментальных областей программной инженерии является разработка СУБД. На данный момент создано множество разных моделей построения таковых. Например, одной из них является графовая модель, в которой данные представлены в виде вершин — сущности и дуг — связи между сущностями. Примерами графовых СУБД являются RedisGraph , Neo4j и TigerGraph .
К графовой базе данных необходимо выполнять запросы. В ходе их рассмотрения появляется задача поиска путей в графе с ограничениями, которые выразимы в терминах формальной грамматики. В таком случае каждому пути соответствует слово, полученное конкатенацией меток, находящихся на его дугах в порядке обхода. Именно это слово будет проверяться на принадлежность заданной грамматике.
В этой связи особый интерес представляют контекстно-свободные (КС) грамматики, так как обладают более выразительной способностью в отличии, например, от регулярных. То есть данный тип грамматики позволяет задавать более сложные ограничения на пути. Поэтому запросы с КС-ограничениями используют и в других областях, например, биоинформатика [11] или статический анализ кода [9].
Существует множество алгоритмов, решающих задачу поиска путей основываясь на теории формальных языков, например, алгоритм Элле Хеллингса [8], восходящий алгоритм Фреди Сантоса [10] или алгоритм Петтери Севона [11]. Однако, в статье Йохима Куйперса и др. [13] про-демонстрировано, что существующие алгоритмы могут быть успешно применены лишь при определенных условиях на входные данные, а в общем случае их реализации требуют большой объем вычислительных мощностей в процессе работы, что не оправдывает их применение в промышленных продуктах. В то же время Никита Мишин и др. в статье [7] и Егор Орачев и др. в исследовании [5], взяв собранный набор данных CFPQ_Data4показали, что алгоритмы, основанные на линейной алгебре, а именно алгоритм, основанный на матричном умножении, и алгоритм, основанный на произведении Кронекера, демонстрируют высокую производительность на реальных входных данных.
Однако в исследовании [5] авторы замечают неоптимальность предложенного алгоритма, основанного на произведении Кронекера, что влечет потребность в улучшении текущего результата
В ходе работы были выполнены следующие задачи.
1. Улучшен алгоритм построения индекса с использованием динамического пересчета некоторых шагов алгоритма и реализовано полученное улучшение.
2. Разработан и реализован алгоритм извлечения путей по результату работы алгоритма построения индекса.
3. Разработан и реализован алгоритм построения индекса с фиксированным набором стартовых вершин.
4. Произведено экспериментальное исследование производительности реализаций. Полученное улучшение алгоритма поиска путей демонстрирует уменьшение времени до 38 % по сравнению с версией без улучшения. Разработанный алгоритм с набором стартовых вершин быстрее существующего аналога. Однако алгоритм извлечения путей оказался медленнее до 100 раз того же аналога ввиду более сложно устроенных структур необходимых в процессе его работы.
Также результат был изложен в статье ’’Context-Free Path Querying with All-Path Semantics by Matrix Multiplication”, которая принята на конференцию GRADES-NDA 2021.
