通常のパスクエリ

データベース、特にグラフデータベースにおいて、正規パスクエリ^{[ 1 ]}またはRPQとは、特定の正規表現を満たすパスで接続されたデータベース内のエンドポイントのペアを要求するクエリです。SPARQLクエリ言語にも同様の機能が「プロパティパス」として存在します。

グラフデータベースは、エッジにラベルが付与された有向グラフで構成されます。正規パスクエリは、ラベルの集合に対する正規表現です。たとえば、頂点がユーザーを表し、親から子へのエッジに「親」というエッジラベルがあるグラフデータベースでは、正規パスクエリは次のようになります。${\displaystyle {\text{parent}}{\text{parent}}^{*}}$ノードxとxの子孫yのペアを選択し、 xからyへの「親」エッジの長さが 1 以上であるパスを選択します。

RPQの回答は、エンドポイントペア、つまり正規表現を満たす何らかのパスで接続されたノードxとyのペアで構成される場合もあれば、正規表現を満たすすべてのパスのリストで構成される場合もあります。ただし、このパスの集合は一般的に無限です。

結果の数が無限にならないようにするため、RPQ のセマンティクスは、単純なパス、つまり同じ頂点を 2 回通らないパス、またはトレイル、つまり同じエッジを 2 回通らないパスのみを返すように定義されることがあります。^{[ 2 ]}

すべてのエンドポイントペアを返すという意味での正規パスクエリ（RPQ）の評価は、多項式時間で実行できます。これを行うには、各エンドポイントペアについて、グラフデータベースを有限オートマトンとみなし、正規パスクエリも有限オートマトンとして表現し、積オートマトン構成などを用いて、両方の言語の共通部分が空でないことを確認することで（つまり、空でない問題を解決することで）、適切なパスが存在するかどうかをチェックします。

クエリに関する古典的な問題のいくつかは、正規パスクエリについて研究されており、クエリ包含^{[ 3 ]}やクエリ書き換え^{[ 4 ]}などがある。

データベース理論の研究では、RPQのより表現力豊かなバリエーションが調査されてきた。

• 双方向RPQ （ 2RPQとも呼ばれる）は、逆方向にもエッジをたどることができます。より正確には、2RPQは、グラフのラベルと逆方向のエッジに対応するラベルを組み合わせた正規表現です。例えば、RPQ${\displaystyle {\text{parent}}^{-}{\text{parent}}}$ノードxとyのペアを選択します。xからyへのパスは、まず親エッジに沿って後ろ向きに進み、次に親エッジに沿って前向きに進む必要があります。つまり、xとyは兄弟です。
• 結合正規パスクエリ（CRPQ）とは、原子が正規パスクエリ（RPQ）である結合クエリのことです。このようなクエリを用いることで、パスだけでなくより複雑なパターンをテストすることが可能になりますが、その評価は困難です。
• 論理和（結合クエリの和集合など）と双方向表現の両方を可能にするさらなる拡張として、 UC2RPQsがある。^{[ 5 ]}