Conjunctive Path Query (CPQ) Syntax

A conjunctive path query can be recursively constructed from the operations of identity $id$, edge label $l$, inverse edge label $l^-$, join $\circ$ and conjunction $\cap$. This results in the following grammar:

\[CPQ ::= id \mid l \mid l^- \mid CPQ \circ CPQ \mid CPQ \cap CPQ \mid(CPQ)\]

The exact definition of these operations when evaluated on a graph $\mathcal{G}$ with vertex set $\mathcal{V}$, edge label set $\mathcal{L}$ and edge set $\mathcal{E} = \mathcal{V} \times \mathcal{V} \times \mathcal{L}$ is then given as follows:

\[\begin{align*} [ id ]_\mathcal{G} &= \{(v,v) \mid v \in \mathcal{V}\}\\ [ l ]_\mathcal{G} &= \{(v,u) \mid (v,u,l) \in \mathcal{E}\}\\ [ l^- ]_\mathcal{G} &= \{(u,v) \mid (v,u,l) \in \mathcal{E}\}\\ [ q_1 \circ q_2 ]_\mathcal{G} &= \{(v,u) \mid \exists m \in \mathcal{V} : (v,m) \in [ q_1 ]_\mathcal{G} \land (m,u) \in [ q_2 ]_\mathcal{G}\}\\ [ q_1 \cap q_2 ]_\mathcal{G} &= \{(v,u) \mid (v,u) \in [ q_1 ]_\mathcal{G} \land (v,u) \in [ q_2 ]_\mathcal{G}\}\\ [ (q_1) ]_\mathcal{G} &= [ q_1 ]\mathcal{G} \end{align*}\]

This means that the result of evaluating a CPQ is a set of vertex pairs.

The diameter of a CPQ

For an expression $q \in CPQ$, we define the diameter $\text{dia}(q)$ of $q$ as follows. The identity operation has diameter zero; every edge label has diameter one; $\text{dia}(q1 \cap q2) = \max(\text{dia}(q1), \text{dia}(q2))$; and, $\text{dia}(q1 ◦ q2) = \text{dia}(q1) + \text{dia}(q2)$. Intuitively, the diameter of an expression is the maximum number of edge labels to which the join operation is applied. For a non-negative integer $k$, we denote by $CPQ_k$ the set of all expressions in $CPQ$ of diameter at most $k$. Essentially the diameter is the longest path from source to target within the CPQ itself.

Conjunctive Path Query (CPQ) Syntax

The diameter of a CPQ

References: