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

Tomasz Gogacz, Jerzy Marcinkowski

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

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

Fingerprint

Dive into the research topics of 'The Hunt for a Red Spider: Conjunctive Query Determinacy Is Undecidable'. Together they form a unique fingerprint.

Cite this