Can One Escape Red Chains?

DOI10.1145/3209108.3209120MaRDI QIDQ5145324zbMATH OpenOpenAlexFDO

Authors Grzegorz Głuch, Jerzy Marcinkowski, Piotr Ostropolski-Nalewaja

Publication date 20 January 2021

Published in Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1802.01554

Mathematics Subject Classification ID

Database theory (68P15)

Abstract: For a given set of queries (which are expressions in some query language) $$, $$ and for another query $Q_0$ we say that $mathcalQ$ determines $Q_0$ if -- informally speaking -- for every database $mathbbD$, the information contained in the views $mathcalQ(mathbbD)$ is sufficient to compute $Q_0(mathbbD)$. Query Determinacy Problem is the problem of deciding, for given $mathcalQ$ and $Q_0$, whether $mathcalQ$ 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.

Recommendations

• The first-order truth behind undecidability of regular path queries determinacy
• The Hunt for a Red Spider: Conjunctive Query Determinacy Is Undecidable
• On decidability of boundedness property for regular path queries
• The Computability Path Ordering: The End of a Quest
• The first-order theory of lexicographic path orderings is undecidable
• On the Complexity of Evaluating Regular Path Queries over Linear Existential Rules
• From decidability to undecidability by considering regular sets of instances
• Irredundant algorithms for traversing directed graphs: The deterministic case
• Completeness of path-problems via logical reductions
• All-instances termination of chase is undecidable

Cited in

(4)

• Asymptotic determinacy of path queries using union-of-paths views
• The first-order truth behind undecidability of regular path queries determinacy
• Asymptotic determinacy of path queries using union-of-paths views
• On Monotonic Determinacy and Rewritability for Recursive Queries and Views

This page was built for publication: Can One Escape Red Chains?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5145324)