Title :
The Hunt for a Red Spider: Conjunctive Query Determinacy Is Undecidable
Author :
Gogacz, Tomasz ; Marcinkowski, Jerzy
Author_Institution :
Inst. of Comput. Sci., Univ. of Wroclaw, Wroclaw, Poland
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.
Keywords :
decidability; query processing; relational databases; conjunctive query determinacy problem; relational database theory; undecidable problem; Context; Databases; Head; Image color analysis; Legged locomotion; Periodic structures; Standards; chase; conjunctive queries; determinacy;
Conference_Titel :
Logic in Computer Science (LICS), 2015 30th Annual ACM/IEEE Symposium on
Conference_Location :
Kyoto
DOI :
10.1109/LICS.2015.35
