Интеграция алгоритма выполнения запросов с ограничениями в виде регулярных языков в графовую базу данных FalkorDB

Использование регулярных выражений для фильтрации путей в графе с метками на рёбрах (RPQ, Regular Path Querying) — одна из важных составляющих современных языков запросов к графам. В частности, RPQ являются частью стандартизованного языка запросов GQL. Это стимулирует разработку высокопроизводительных и экономичных по памяти алгоритмов для решения RPQ. В частности, на кафедре, Георгием Беляниным, был разработан алгоритм решения этой задачи, основанный на операциях над разреженными булевыми матрицами. Предлагается интегрировать данный алгоритм в FalkorDB и сравнить производительность получившегося решения с изначальным вариантом поддержки RPQ в FalkorDB.

Требования к студенту
  • Отличное знание языка программирования C и соответствующего инструментария для сборки, отладки, тестирования.
  • Отличное знание основ теории графов: различные типы графов (ориентированные, неориентированные, с метками на рёбрах и т.д.), способов представления графов (матрица смежности, список смежности и т.д.), алгоритмы обхода графов (в ширину, глубину), алгоритмы решения задачи достижимости, поиска путей и т.д.
  • Отличное знание основ теории формальных языков: регулярные языки, конечные автоматы, алгоритмы работы с ними (пересечение регулярных языков, детерминизация конечных автоматов и т.д.).
  • Знание основ линейной алгебры: матрицы, вектора, операции над ними (умножение, поэлементные операции), кольца, полукольца, свойства операций (коммутативность, идемпотентность и т.д.).
Уровень

Бакалаврская ВКР

Руководитель

Григорьев Семен Вячеславович

Консультант

Grigorev Semyon

Источник

Кафедра системного программирования СПбГУ