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

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.