ВКР: Оптимизация алгоритма поиска путей с контекстно-свободными ограничениями, основанного на произведении Кронекера

Оглавление

• Алгоритм построения индекса с заданным набором стар-

3

Введение

Одной из фундаментальных областей программной инженерии являет-ся разработка СУБД. На данный момент создано множество разных моделей построения таковых. Например, одной из них является графо-вая модель, в которой данные представлены в виде вершин — сущности

• дуг — связи между сущностями. Примерами графовых СУБД явля-

ются RedisGraph¹, Neo4j² и TigerGraph³.

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

В этой связи особый интерес представляют контекстно-свободные (КС) грамматики, так как обладают более выразительной способностью в отличии, например, от регулярных. То есть данный тип грамматики позволяет задавать более сложные ограничения на пути. Поэтому за-просы с КС-ограничениями используют и в других областях, например, биоинформатика [11] или статический анализ кода [9].

Существует множество алгоритмов, решающих задачу поиска путей основываясь на теории формальных языков, например, алгоритм Элле Хеллингса [8], восходящий алгоритм Фреди