Red Spider Meets a Rainworm: Conjunctive Query Finite Determinacy Is Undecidable

We solve a well known and long-standing open problem in database theory, proving that Conjunctive Query Finite Determinacy Problem is undecidable. The technique we use builds on the top of our Red Spider method which we developed in our paper [GM15] to show undecidability of the same problem in the "unrestricted case" -- when database instances are allowed to be infinite. We also show a specific instance Q0, cal Q= Q1, Q2, ldots Qk such that the set cal Q of CQs does not determine CQ Q0 but finitely determines it. Finally, we claim that while Q0 is finitely determined by cal Q, there is no FO-rewriting of Q0, with respect to cal Q, and we outline a proof of this claim