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

Tomasz Gogacz, Jerzy Marcinkowski

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.
Original languageEnglish
Title of host publicationLogic in Computer Science (LICS), 2015 30th Annual ACM/IEEE Symposium on
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Pages281 - 292
Number of pages12
ISBN (Print)978-1-4799-8875-4
Publication statusPublished - 2015

Cite this