The Hunt for a Red Spider: Conjunctive Query Determinacy Is Undecidable
Tomasz Gogacz, Jerzy Marcinkowski·2015-01-08·via cs.DB updates on arXiv.org
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.