Для студентов СПбГУ по предмету ДругиеРазработка матричного алгоритма поиска путей с контекстно-свободными ограничениями для RedisGraphРазработка матричного алгоритма поиска путей с контекстно-свободными ограничениями для RedisGraph
2024-08-032024-08-03СтудИзба
Курсовая работа: Разработка матричного алгоритма поиска путей с контекстно-свободными ограничениями для RedisGraph
Описание
Оглавление
3
Введение
Поиск путей в графе с ограничением в виде формальных языков [3]
— это задача, в которой формальные языки используются для задания множества искомых путей. В таком подходе каждый путь соответствует слову, состоящему из меток его рёбер, а ограничением на путь является принадлежность соответствующего ему слова некоторому заданному формальному языку.
Наиболее удобным и подходящим инструментом для работы с граф-структурированными данными являются графовые базы данных. Так же как и реляционные, графовые базы данных поддерживают свой язык запросов. С его помощью графовые базы данных позволяют ре-шать вышеупомянутую задачу поиска путей. Но ограничения на пути, которые поддерживается в наиболее распространённых базах данных, являются в лучшем случае регулярными.
Отсутствие поддержки контекстно-свободных ограничений в графо-вых базах данных, во-первых, сильно ограничивает
| Введение | 4 | |||
| 1. | Постановка задачи | 6 | ||
| 2. | Обзор | 7 | ||
| 2.1. | Терминология ......................... | 7 | ||
| 2.2. | Графовыебазыданных.................... | 8 | ||
| 2.3. | Существующиерешения ................... | 10 | ||
| 2.3.1. | Парсер-комбинаторы для Neo4j . . . . . . . . . . . | 10 | ||
| 2.3.2. | Расширение языка запросов SPARQL . . . . . . . | 10 | ||
| 2.3.3. Существующие реализации алгоритмов решения за- | ||||
| дачи контекстно-свободной достижимости . . . . . | 11 | |||
| 2.4. | Матричный алгоритм Рустама Азимова . . . . . . . . . . | 12 | ||
| 2.5. | RedisGraph . . . . . . . . . . . . . . . . . . . . . . . . . . . | 13 | ||
| 2.6. | Расширение языка Cypher . . . . . . . . . . . . . . . . . . | 14 | ||
| 3. | Реализация | 17 | ||
| 3.1. | Планвыполнениязапроса . . . . . . . . . . . . . . . . . . | 17 | ||
| 3.2. | Промежуточное представление . . . . . . . . . . . . . . . | 18 | ||
| 3.3. | Трансляция в матричные выражения . . . . . . . . . . . | 20 | ||
| 3.4. | Формирование и вычисление операции плана выполнения | 23 | ||
| 4. | Замеры производительности | 25 | ||
| 4.1. | Сравнение с парсер-комбинаторами . . . . . . . . . . . . . | 25 | ||
| 4.2. | Сравнение с матричным алгоритмом . . . . . . . . . . . . | 26 | ||
| 4.3. | Сравнение с анализом Йохема Куйперса . . . . . . . . . . | 27 | ||
| 4.4. | Выводы............................. | 28 | ||
| Заключение | 29 | |||
| Список литературы | 30 | |||
3
Введение
Поиск путей в графе с ограничением в виде формальных языков [3]
— это задача, в которой формальные языки используются для задания множества искомых путей. В таком подходе каждый путь соответствует слову, состоящему из меток его рёбер, а ограничением на путь является принадлежность соответствующего ему слова некоторому заданному формальному языку.
- качестве класса формальных языков по иерархии Хомского наи-больший интерес представляют контекстно-свободные языки. В отли-чие от регулярных они обладают большей выразительностью. Поэто-му в задаче поиска путей контекстно-свободные ограничения позволя-ют задавать более сложные отношения между вершинами. Так, напри-мер, важный класс запросов поиска вершин, лежащих на одном уровне иерархии [5], задаётся только контекстно-свободными, но не регуляр-ными ограничениями. Запросы такого вида, как и другие запросы с контекстно-свободными ограничениями имеют широкое применение в биоинформатике [21] и при обработке rdf-файлов [5].
Наиболее удобным и подходящим инструментом для работы с граф-структурированными данными являются графовые базы данных. Так же как и реляционные, графовые базы данных поддерживают свой язык запросов. С его помощью графовые базы данных позволяют ре-шать вышеупомянутую задачу поиска путей. Но ограничения на пути, которые поддерживается в наиболее распространённых базах данных, являются в лучшем случае регулярными.
Отсутствие поддержки контекстно-свободных ограничений в графо-вых базах данных, во-первых, сильно ограничивает
Характеристики курсовой работы
СПбГУСписок файлов
Разработка матричного алгоритма поиска путей с контекстно-свободными ограничениями для RedisGraph.doc
Tortuga
03 августа 2024 в 18:48
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
