View source for Regular path query

In [[Database|database]]s and specifically in [[Graph database|graph database]]s, a '''regular path query'''<ref>{{Cite web |title=Answering regular path queries using views {{!}} IEEE Conference Publication {{!}} IEEE Xplore |url=https://ieeexplore.ieee.org/abstract/document/839439 |access-date=2024-01-18 |website=ieeexplore.ieee.org}}</ref> or '''RPQ''' is a query asking for pairs of endpoints in the database that are connected by a path satisfying a certain [[Regular expression|regular expression]]. A similar feature exists in the [[SPARQL]] query language as "property paths"

== Definition ==

A graph database consists of a directed graph whose edges carry a label. A regular path query is just a [[Regular expression|regular expression]] over the set of labels. For instance, in a graph database where vertices represent users and there is an edge label "parent" for edges from a parent to a child, the regular path query <math>\text{parent} \text{parent}^*</math> would select pairs of a node ''x'' and a descendant ''y'' of ''x'', with a path from ''x'' to ''y'' of "parent" edges having length 1 or more.

== Semantics ==

The answers to RPQs can consist of ''endpoint pairs'', i.e., pairs of nodes ''x'' and ''y'' that are connected by some path satisfying the regular expression; or it can consist of the ''list of all paths'' satisfying the regular expression. However, this set of paths is generally infinite.

To ensure that the number of results is not infinite, the semantics of RPQs is sometimes defined to return only the simple paths, i.e., the paths that do not go twice via the same vertex; or the trails, i.e., the paths that do not go twice through the same edge.<ref>{{Cite journal |last=Martens |first=Wim |last2=Trautner |first2=Tina |date=2019-10-15 |title=Dichotomies for Evaluating Simple Regular Path Queries |url=https://doi.org/10.1145/3331446 |journal=ACM Transactions on Database Systems |volume=44 |issue=4 |pages=16:1–16:46 |doi=10.1145/3331446 |issn=0362-5915}}</ref>

== Complexity ==

The evaluation of regular path queries (RPQ), in the sense of returning all endpoint pairs, can be performed in polynomial time. To do this, for every endpoint pair, we can see the graph database as a finite automaton, also represent the regular path query as a finite automaton, and check if a suitable path exists by checking that the intersection of both languages is nonempty (i.e., solving the [[Emptiness problem|emptiness problem]]), for instance via the product automaton construction.

== Other problems ==

Several classical problems about queries have been studied for regular path queries, such as query containment<ref>{{Cite journal |last=Calvanese |first=D. |last2=De Giacomo |first2=G. |last3=Lenzerini |first3=M. |last4=Vardi |first4=M. Y. |date=2003-12-01 |title=Reasoning on regular path queries |url=https://doi.org/10.1145/959060.959076 |journal=ACM SIGMOD Record |volume=32 |issue=4 |pages=83–92 |doi=10.1145/959060.959076 |issn=0163-5808}}</ref> and [[Query rewriting|query rewriting]].<ref>{{Cite journal |last=Calvanese |first=Diego |last2=De Giacomo |first2=Giuseppe |last3=Lenzerini |first3=Maurizio |last4=Vardi |first4=Moshe Y. |date=1999-05-01 |title=Rewriting of regular expressions and regular path queries |url=https://dl.acm.org/doi/10.1145/303976.303996 |journal=Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems |series=PODS '99 |location=New York, NY, USA |publisher=Association for Computing Machinery |pages=194–204 |doi=10.1145/303976.303996 |isbn=978-1-58113-062-1}}</ref>

== Extensions ==

[[Database theory]] research has investigated more expressive variants of RPQs:

* '''Two-way RPQs''' aka '''2RPQs''', which can also traverse edges in the reverse direction. More precisely, a 2RPQ is a regular expression that uses the labels of the graph together with labels corresponding to reverse edges. For instance, the RPQ <math>\text{parent}^- \text{parent}</math> selects pairs of nodes ''x'' and ''y'' with a path from ''x'' to ''y'' going first backward on a parent edge, then forward on a parent edge, i.e., ''x'' and ''y'' are siblings.
* '''Conjunctive regular path queries''' aka '''CRPQ''', which are [[Conjunctive query|conjunctive queries]] whose atoms are RPQs. Such queries make it possible to test for more complex patterns than just paths, however they are intractable to evaluate.
* A further extension allowing both disjunctions (like union of conjunctive queries) and two-way expressions are '''UC2RPQs'''.<ref>{{Cite book |last=Figueira |first=Diego |url=https://hal.science/hal-04311290 |title=Semantic Tree-Width and Path-Width of Conjunctive Regular Path Queries |last2=Morvan |first2=Rémi |date=November 2023}}</ref>

== References ==
<references/>

[[Category:Graph databases]]
[[Category:Query languages]]
[[Category:Database theory]]

{{Sourceattribution|Regular path query}}