The Hunt for a Red Spider: Conjunctive Query Determinacy Is Undecidable

DOI10.1109/LICS.2015.35MaRDI QIDQ4635811zbMATH OpenOpenAlexFDO

Authors Tomasz Gogacz, Jerzy Marcinkowski

Publication date 23 April 2018

Published in 2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Undecidability and degrees of sets of sentences (03D35) Database theory (68P15) Analysis of algorithms and problem complexity (68Q25)

Abstract: We solve a well known, long-standing open problem in relational databases theory, showing that the conjunctive query determinacy problem (in its "unrestricted" version) is undecidable.

Cited in

(5)

• Asymptotic determinacy of path queries using union-of-paths views
• SOME MODEL THEORY OF GUARDED NEGATION
• The first-order truth behind undecidability of regular path queries determinacy
• Can One Escape Red Chains?
• On Monotonic Determinacy and Rewritability for Recursive Queries and Views

This page was built for publication: The Hunt for a Red Spider: Conjunctive Query Determinacy Is Undecidable

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