View-Based Query Determinacy for Walk-Based Semantics

We start by showing how the classical query determinacy problem translates to our setting. As a side result, we remark that the query rewriting problem using views [19] turns out to be trivial in our setting: the rewriting, when it exists, will simply be the original query itself. Then our main contribution is to prove upper and lower complexity bounds for the problem of deciding query determinacy under all-walks, trail and shortest walk semantics. First, we establish a lower bound that covers all three semantics:

In this work, we assume that the regular path queries are given as finite automata. Thus, it is a natural concern whether the complexity depends on the properties of the specific automaton that implements the query. Our result, however, shows that the lower bound holds even in the favorable case where the automaton is deterministic. Next, we prove a matching upper bound for all-walks and trail semantics, which makes the problem PSpace-complete:

Finally, we prove a matching upper bound for shortest walk semantics, which turns out to be our most difficult result:

This upper bound only holds when the query is given as a deterministic automaton (the automata defining the view may be nondeterministic). One could always choose to determinize the input to use this decision algorithm, but then the upper bound becomes ExpSpace, and no longer matches the lower bound. Unfortunately, this gap remains as an open question: we neither have a better upper bound for the nondeterministic case, nor a tighter lower bound when the automaton can be nondeterministic.

Section 2 defines the data and query models of our setting. Section 3 defines the view-based query determinacy problem and shows preliminary results that apply to all three semantics, including the PSpace lower bound. Section 4 proves the upper bound for the all-walks and trail semantics. While interesting in its own right, this section also serves as a warm-up for Section 5 where we prove the upper bound for the shortest walk semantics. Indeed, the techniques in Section 5 reuse and expand upon the core ideas of Section 4.

Let everything be defined as in the statement of the lemma. Let $\pi \in Q_X(D)$ such that $\pi$ is not a walk in $\text{Data}({𝒱}_X(D))$. Then there exists an edge $e$ that occurs in $\pi$ but not in $\text{Data}({𝒱}_X(D))$. Let $D^{\prime }$ be a copy of $D$ without this edge. Then one simply has to remark that ${𝒱}_X(D)={𝒱}_X(D^{\prime })$, but $\pi \notin Q_X(D^{\prime })$. $◀$

Let $V\in 𝒱$. We show that $V_X(D)=V_X(\text{Data}({𝒱}_X(D)))$.

$(\subseteq )$

Let $\pi \in V_X(D)$. Then, by definition, $\pi$ is a walk in $\text{Data}({𝒱}_X(D))$. Thus, $\pi$ matches $V$. Since $\text{Data}({𝒱}_X(D))$ is a substructure of $D$, if $\pi$ is a trail in $D$, it is also a trail in $\text{Data}({𝒱}_X(D))$. Similarly, if $\pi$ is a shortest walk between its endpoints in $D$, it is also a shortest walk in $\text{Data}({𝒱}_X(D))$.

$(\supseteq )$

Let $\pi \in V_X(\text{Data}({𝒱}_X(D)))$. As in the previous case, $\pi$ is a walk of $D$ that matches $V$, and if $\pi$ is a trail in $\text{Data}({𝒱}_X(D))$, then it is a trail in $D$. The only interesting question is whether $\pi$ is a shortest walk in $D$ when $X=short$. Assume for the sake of contradiction that there is a walk ${\pi }^{\prime }\in V_{short}(D)$ such that ${\pi }^{\prime }$ has the same endpoints as $\pi$ and is shorter than $\pi$. Then, by definition, ${\pi }^{\prime }$ is a walk in $\text{Data}({𝒱}_{short}(D))$. Thus $\pi \notin V_X(\text{Data}({𝒱}_{short}(D)))$, which is a contradiction.

$◀$

Lemma 17 and Lemma 18 imply that, in our setting, determinacy admits an alternate and much simpler definition:

$(\Rightarrow )$

This is immediately given as the contraposition of Lemma 17.

$(\Leftarrow )$

Assume that for all databases $D$, for all walks $\pi \in Q_X(D)$, $\pi$ is a walk in $\text{Data}({𝒱}_X(D))$.

Let $D_1$ and $D_2$ be two databases such that ${𝒱}_X(D_1)={𝒱}_X(D_2)$. Let $\pi \in Q_X(D_1)$. Then $\pi \in \text{Data}({𝒱}_X(D_1))$, which yields $\pi \in \text{Data}({𝒱}_X(D_2))$. If $X=walk$ (resp. $X=trail$), the result immediately follows: $\pi$ is then a walk (resp. trail) in $D_2$ that matches $Q$, thus $\pi \in Q_X(D_2)$, which means $𝒱{\twoheadrightarrow }_{X}Q$.

Assume now that $X=short$. Since $\pi$ is a walk of $D_2$ that matches $Q$, there are two cases: either $\pi \in Q_{short}(D_2)$ and there is nothing more to prove, or there exists a shorter walk $\mu$ in $Q_{short}(D_2)$ that has the same endpoints as $\pi$. In that case, the assumption yields that $\mu$ is a walk in $\text{Data}({𝒱}_X(D_2))$. Thus it is a walk in $\text{Data}({𝒱}_X(D_1))$. This means that $\pi$ is not a shorter walk in $D_1$ either, which is a contradiction.

$◀$

When the view determines the query, one may be interested in finding rewritings, that is, queries whose answer on the view image coincides with the answer to the original query on the original data [19]. This task may require additional techniques and ideas. In our setting, it turns out that the two tasks coincide. Indeed, Proposition 20 together with Lemma 18 lead to the corollary below, which states that when the view determines the query, a rewriting of the query is the query itself.

We are now ready to prove the first complexity result: deciding determinacy is PSpace-hard under all-walks, trail and shortest walk semantics.

Let $X\in \{walk,trail,short\}$. The proof is done by reduction from the Intersection Emptiness problem [15], which asks, given $n$ deterministic automata $A_1,\mathrm{\dots },A_n$ whether $L(A_1)\cap \mathrm{\dots }\cap L(A_n)=\mathrm{\varnothing }$. Here, we will use the equivalent Union Universality problem: given $n$ deterministic automata $A_1,\mathrm{\dots },A_n$, does $L(A_1)\cup \mathrm{\dots }\cup L(A_n)={\mathrm{\Sigma }}^{\ast }$?

Let $start,end$ be two fresh symbols that do not occur in $\mathrm{\Sigma }$. We define $A$ as the usual 3-state deterministic automaton that accepts $start\cdot {\mathrm{\Sigma }}^{\ast }\cdot end$ and we extend each automaton $A_i$ into a deterministic automaton $A_i^{\prime }$ with a new initial and final state such that $L(A_i^{\prime })=start\cdot L(A_i)\cdot end$.

Then it remains to remark that Proposition 20 implies that $\{A_i^{\prime }\}{\twoheadrightarrow }_{X}A$ if and only if $L(A_1)\cup \mathrm{\dots }\cup L(A_n)$ is universal. $◀$

$(\Rightarrow )$

If $𝒱{\twoheadrightarrow }_{X}Q$, then Lemma 17 implies that $\pi$ is a walk in $\text{Data}({𝒱}_X(\pi ))$. Since $\text{Data}({𝒱}_X(\pi ))$ is a substructure of $\text{Data}(\pi$), this implies that $\text{Data}({𝒱}_X(\pi ))=\text{Data}(\pi )$.

$(\Leftarrow )$

Conversely, assume that for all databases that consist of only a simply labeled simple walk $\pi$ matching $Q$, $\text{Data}({𝒱}_X(\pi ))=\text{Data}(\pi )$. Let $D$ be an arbitrary database and $\pi$ be a (not necessarily simple) walk in $Q_X(D)$.

Since $\pi$ matches $Q$, there exists $w\in \text{Lbl}(\pi )$ such that $w\in L(Q)$. Let $\mu$ be an unfolding of $\pi$ that is simply labeled by $w$. Formally, $\mu$ is a copy of $\pi$ in which each extra occurrence of a repeating edge or vertex of $\pi$ is replaced by a fresh copy. Additionally, only one label of each edge is kept, so that $\text{Lbl}(\mu )=w$. Then, the assumption applied to the database that contains only $\mu$ yields $\text{Data}({𝒱}_X(\mu ))=\text{Data}(\mu )$.

Assume $X=walk$ (resp. $X$ = trail). Let $\phi$ be the homomorphism (resp. edge-injective homomorphism) that folds $\mu$ into $\pi$, that is, $\phi$ maps each vertex and edge of $\mu$ to the original object in $\pi$. Since $X$ is closed under homomorphism (resp. edge-injective homomorphism), $\text{Data}(\phi (\mu ))\subseteq \text{Data}({𝒱}_X(\phi (\mu )))$, which means $\text{Data}(\pi )\subseteq \text{Data}({𝒱}_X(\pi ))$.

Moreover, $X$ is monotone, thus $\text{Data}({𝒱}_X(\pi ))\subseteq \text{Data}({𝒱}_X(D))$. This implies that $\pi$ is a walk (resp. trail) in $\text{Data}({𝒱}_X(D))$. Therefore, Proposition 20 implies that $𝒱{\twoheadrightarrow }_{X}Q$.

$◀$

Proposition 23 leads to the definition of a counterexample, that is, a specific word in $L(Q)$ whose existence proves that $𝒱{\twoheadrightarrow ̸}_{X}Q$.

Proposition 25 is a simple consequence of Proposition 23. Indeed, $𝒱{\twoheadrightarrow ̸}_{X}Q$ if and only if there is a simply labeled simple walk $\pi$ that matches $Q$ such that $\text{Data}({𝒱}_X(\pi ))\ne \text{Data}(\pi )$, that is, there is an edge $e$ of $\pi$ such that $e$ is not returned by any $V\in 𝒱$. It then remains to remark that a suitable counterexample is $w=\text{Lbl}(\pi )$, with $a=\text{Lbl}(e)$. $◀$

Proposition 25 is the main ingredient for proving Theorem 2: we show that the set of counterexamples is actually a regular language, whose emptiness can be checked in PSpace.

Let $X\in \{walk,short\}$. Let $𝒱=\{V_1,\mathrm{\dots },V_n\}$ be a regular path view and $Q$ be a regular path query. Let $L_{𝒱,Q}$ be the set of counterexamples for $𝒱{\twoheadrightarrow }_{X}Q$ as defined in Definition 24. Let $A_{𝒱}=(\mathrm{\Sigma },S_{𝒱},{\mathrm{\Delta }}_{𝒱},I_{𝒱},F_{𝒱})$ be any automaton for $L(V_1)\cup \mathrm{\dots }\cup L(V_n)$ and $A_Q=(\mathrm{\Sigma },S_Q,{\mathrm{\Delta }}_Q,I_Q,F_Q)$ be an automaton for $Q$. Our goal is to construct an automaton $A_{𝒱,Q}$ of at most exponential size such that $L(A_{𝒱,Q})=L_{𝒱,Q}$, whose emptiness can then be checked in PSpace.

The existence of $A_{𝒱,Q}$ can be shown by using well-known closure properties of regular languages. We do this in Appendix B. Here, we will instead show a direct construction of $A_{𝒱,Q}$. In addition to proving Theorem 2, this also serves as an introduction to the main result of Section 5, which expands upon the construction shown here.

Intuitively, $A_{𝒱,Q}$ runs on a word $w\in L(Q)$ for which it nondeterministically guesses the factorization $u\cdot a\cdot v$ that yields the position $a$ that should be hidden to $𝒱$. Then $A_{𝒱,Q}$ runs $𝒱$ in parallel on each possible starting position in $u$, and checks that $𝒱$ does not accept a factor of $w$ that contains $a$.

Formally, $A_{𝒱,Q}=(\mathrm{\Sigma },S_{𝒱,Q},{\mathrm{\Delta }}_{𝒱,Q},I_{𝒱,Q},F_{𝒱,Q})$ is defined as follows:

• $\mathrm{■}$

  $S_{𝒱,Q}=S_Q\times 2^{S_{𝒱}}\times \{0,1\}$

• $\mathrm{■}$

  $I_{𝒱,Q}=I_Q\times 2^{I_{𝒱}}\times \{0\}$

• $\mathrm{■}$

  $F_{𝒱,Q}=F_Q\times 2^{S_{𝒱}-F_{𝒱}}\times \{1\}$

• $\mathrm{■}$

  For $q\in S_Q,P\subseteq S_{𝒱}$ and $b\in \mathrm{\Sigma }$, ${\mathrm{\Delta }}_{𝒱,Q}$ contains transitions of the following forms:

  1. 1.

     $(q,P,0)\stackrel{𝑏}{\to }{\mathrm{\Delta }}_Q(q,b)\times \{{\mathrm{\Delta }}_{𝒱}(P,b)\cup I_{𝒱}\}\times \{0\}$

  2. 2.

     $(q,P,0)\stackrel{𝑏}{\to }{\mathrm{\Delta }}_Q(q,b)\times \{{\mathrm{\Delta }}_{𝒱}(P,b)\}\times \{1\}$  if ${\mathrm{\Delta }}_{𝒱}(P,b)\cap F_{𝒱}=\mathrm{\varnothing }$

  3. 3.

     $(q,P,1)\stackrel{𝑏}{\to }{\mathrm{\Delta }}_Q(q,b)\times \{{\mathrm{\Delta }}_{𝒱}(P,b)\}\times \{1\}$  if ${\mathrm{\Delta }}_{𝒱}(P,b)\cap F_{𝒱}=\mathrm{\varnothing }$

Assume that $w\in L(A_{𝒱,Q})$. Then $A_{𝒱,Q}$ has an accepting run over $w$ that starts in some state $(q_0,P_0,0)$ and ends in $(q_n,P_n,1)$. Remark that transitions of the form $(2)$ have to be used exactly once, as they are the only transitions that change the last component from $0$ to $1$, and there is no transition that changes $1$ back to $0$. This defines a unique factorization of $w$ as $u\cdot a\cdot v$, where the transition is used when reading $a$ after having read $u$.

Then, we prove by a straightforward induction that the state $(q_i,P_i,f_i)$ that is reached after reading the prefix $w_i$ of $w$ of length $i$ satisfies the following:

• $\mathrm{■}$

  $q_i\in {\mathrm{\Delta }}_Q(I_Q,w_i)$ simulates a run of $A_Q$ on $w_i$.

• $\mathrm{■}$

  If $i\le \text{Len}(u)$, then $P_i$ contains all states of $A_{𝒱}$ that can be reached at position $i$ by starting on any position before $i$. That is, $p\in P_i$ if and only if there exists a suffix $u_2$ of $w_i$ such that $p\in {\mathrm{\Delta }}_{𝒱}(I_V,u_2)$.

• $\mathrm{■}$

  If $i\ge \text{Len}(u\cdot a)$, then $P_i$ contains all states of $A_{𝒱}$ that can be reached at the current position by starting on any position of $u$. That is, $p\in P_i$ if and only if $w_i$ if of the form $u_1\cdot u_2\cdot a\cdot v_2$, with $u=u_1\cdot u_2$ and $p\in {\mathrm{\Delta }}_{𝒱}(I_V,u_2\cdot a\cdot v_2)$.

We conclude the proof by remarking that transitions of the form $(2)$ and $(3)$ enforce that $P\cap F_{𝒱}=\mathrm{\varnothing }$. This means that for all factorizations of $w$ as $u_1\cdot u_2\cdot a\cdot v_2\cdot v_1$ with $u=u_1\cdot u_2$ and $v=v_2\cdot v_1$, we have $u_2\cdot a\cdot v_2\notin L(A_{𝒱})$, which is precisely what Definition 24 requires. Thus $w\in L_{𝒱,Q}$.

The converse direction is proved in a very similar way. Assume that $w\in L_{𝒱,Q}$. Then $w\in L(Q)$ and is of the form $w=u\cdot a\cdot v$. We then exhibit an accepting run of $A_{𝒱,Q}$ on $w$ that uses the nondeterministic transition $(2)$ precisely when reading $a$.

This is done by performing a reachability test from any initial state of $A_{𝒱,Q}$ to any accepting state of $A_{𝒱,Q}$. As $A_{𝒱,Q}$ is a graph of exponential size, it is well known that this can be done in PSpace.

Therefore, emptiness of $L_{𝒱,Q}$ can be checked in PSpace. Proposition 25 states that $L_{𝒱,Q}=\mathrm{\varnothing }$ if and only if $𝒱{\twoheadrightarrow }_{X}Q$ for $X\in \{walk,trail\}$. This concludes the proof. $◀$