Can One Escape Red Chains? Regular Path Queries Determinacy is Undecidable

Abstract

For a given set of queries (which are expressions in some query language) $\mathcal{Q}=\{Q_1$, $Q_2,\dots Q_k\}$ and for another query $Q_0$ we say that $\mathcal{Q}$ determines $Q_0$ if -- informally speaking -- for every database $\mathbb{D}$, the information contained in the views $\mathcal{Q}(\mathbb{D})$ is sufficient to compute $Q_0(\mathbb{D})$. Query Determinacy Problem is the problem of deciding, for given $\mathcal{Q}$ and $Q_0$, whether $\mathcal{Q}$ determines $Q_0$. Many versions of this problem, for different query languages, were studied in database theory. In this paper we solve a problem stated in [CGLV02] and show that Query Determinacy Problem is undecidable for the Regular Path Queries -- the paradigmatic query language of graph databases.

References in corpus (2)

• Datalog Rewritings of Regular Path Queries using Views
• The View Update Problem Revisited