Обычный запрос пути

В базах данных и конкретно в графовых базах данных обычный запрос пути ^[1] или RPQ — это запрос, запрашивающий пары конечных точек в базе данных, которые соединены путем, удовлетворяющим определенному регулярному выражению . Похожая функция существует в языке запросов SPARQL как «пути к свойствам».

Определение

База данных графов состоит из ориентированного графа , ребра которого несут метку. Обычный запрос пути — это просто регулярное выражение для набора меток. Например, в базе данных графов, где вершины представляют пользователей и существует метка ребра «родительский» для ребер от родительского элемента к дочернему, обычный запрос пути ${\text{parent}}{\text{parent}}^{*}$ выберет пары узла x и потомка y от x с путем от x до y «родительских» ребер, имеющих длину 1 или более.

Семантика

Ответы на RPQ могут состоять из пар конечных точек , т. е. пар узлов x и y , которые соединены некоторым путем, удовлетворяющим регулярному выражению; или он может состоять из списка всех путей, удовлетворяющих регулярному выражению. Однако этот набор путей, как правило, бесконечен.

Чтобы гарантировать, что количество результатов не будет бесконечным, семантика RPQ иногда определяется так, чтобы возвращать только простые пути , т. е. пути, которые не проходят дважды через одну и ту же вершину; или следы , т. е. пути, которые не проходят дважды через одно и то же ребро. ^[2]

Сложность

Оценка обычных запросов пути (RPQ) в смысле возврата всех пар конечных точек может выполняться за полиномиальное время . Для этого для каждой пары конечных точек мы можем рассматривать базу данных графов как конечный автомат , также представлять обычный запрос пути как конечный автомат и проверять, существует ли подходящий путь, проверяя, что пересечение обоих языков непусто (т.е. , решение проблемы пустоты ), например, посредством построения автомата-произведения .

Другие проблемы

Несколько классических проблем, связанных с запросами, были изучены для запросов с обычными путями, таких как сдерживание запроса. ^[3] и переписывание запросов . ^[4]

Расширения

Исследования в области теории баз данных исследовали более выразительные варианты RPQ:

Двусторонние RPQ , также известные как 2RPQ , которые также могут пересекать ребра в обратном направлении. Точнее, 2RPQ — это регулярное выражение, которое использует метки графа вместе с метками, соответствующими обратным ребрам. Например, RPQ ${\text{parent}}^{-}{\text{parent}}$ выбирает пары узлов x и y с путем от x до y , идущим сначала назад по родительскому ребру, затем вперед по родительскому ребру, т. е. x и y являются братьями и сестрами.
Конъюнктивные запросы регулярного пути, также известные как CRPQ , представляют собой конъюнктивные запросы , атомами которых являются RPQ. Такие запросы позволяют проверять более сложные шаблоны, чем просто пути, однако их сложно оценить.
Дальнейшее расширение, позволяющее как дизъюнкции (например, объединение конъюнктивных запросов ), так и двусторонние выражения, — это UC2RPQ . ^[5]

Ссылки

^ Кальванезе, Д.; Де Джакомо, Дж.; Лензерини, М.; Варди, МЮ (2000). Ответы на обычные запросы путей с использованием представлений . стр. 389–398. дои : 10.1109/ICDE.2000.839439 . ISBN 0-7695-0506-6 . Проверено 18 января 2024 г.
^ Мартенс, Вим; Траутнер, Тина (15 октября 2019 г.). «Дихотомии для оценки простых запросов регулярного пути» . Транзакции ACM в системах баз данных . 44 (4): 16:1–16:46. дои : 10.1145/3331446 . ISSN 0362-5915 . S2CID 204728561 .
^ Кальванезе, Д.; Де Джакомо, Дж.; Лензерини, М.; Варди, МЮ (1 декабря 2003 г.). «Рассуждения о регулярных запросах пути» . Запись ACM SIGMOD . 32 (4): 83–92. дои : 10.1145/959060.959076 . ISSN 0163-5808 . S2CID 1803399 .
^ Кальванезе, Диего; Де Джакомо, Джузеппе; Лензерини, Маурицио; Варди, Моше Ю. (1 мая 1999 г.). «Переписывание регулярных выражений и регулярных запросов пути» . Материалы восемнадцатого симпозиума ACM SIGMOD-SIGACT-SIGART по принципам систем баз данных . ПОДС '99. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 194–204. дои : 10.1145/303976.303996 . ISBN 978-1-58113-062-1 .
^ Фигейра, Диего; Морван, Реми (ноябрь 2023 г.). Ширина семантического дерева и ширина пути конъюнктивных запросов регулярного пути .

[1] Кальванезе, Д.; Де Джакомо, Дж.; Лензерини, М.; Варди, МЮ (2000). Ответы на обычные запросы путей с использованием представлений . стр. 389–398. дои : 10.1109/ICDE.2000.839439 . ISBN 0-7695-0506-6 . Проверено 18 января 2024 г.

[2] Мартенс, Вим; Траутнер, Тина (15 октября 2019 г.). «Дихотомии для оценки простых запросов регулярного пути» . Транзакции ACM в системах баз данных . 44 (4): 16:1–16:46. дои : 10.1145/3331446 . ISSN 0362-5915 . S2CID 204728561 .

[3] Кальванезе, Д.; Де Джакомо, Дж.; Лензерини, М.; Варди, МЮ (1 декабря 2003 г.). «Рассуждения о регулярных запросах пути» . Запись ACM SIGMOD . 32 (4): 83–92. дои : 10.1145/959060.959076 . ISSN 0163-5808 . S2CID 1803399 .

[4] Кальванезе, Диего; Де Джакомо, Джузеппе; Лензерини, Маурицио; Варди, Моше Ю. (1 мая 1999 г.). «Переписывание регулярных выражений и регулярных запросов пути» . Материалы восемнадцатого симпозиума ACM SIGMOD-SIGACT-SIGART по принципам систем баз данных . ПОДС '99. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 194–204. дои : 10.1145/303976.303996 . ISBN 978-1-58113-062-1 .

[5] Фигейра, Диего; Морван, Реми (ноябрь 2023 г.). Ширина семантического дерева и ширина пути конъюнктивных запросов регулярного пути .

[1]

[2]

[3]

[4]

[5]