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

Tomasz Gogacz; Jerzy Marcinkowski

doi:10.1109/LICS.2015.35

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

Tomasz Gogacz, Jerzy Marcinkowski

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English
Title of host publication	Logic in Computer Science (LICS), 2015 30th Annual ACM/IEEE Symposium on
Publisher	Institute of Electrical and Electronics Engineers (IEEE)
Pages	281 - 292
Number of pages	12
ISBN (Print)	978-1-4799-8875-4
DOIs	https://doi.org/10.1109/LICS.2015.35
Publication status	Published - 2015

Access to Document

10.1109/LICS.2015.35

1501.01817v2Accepted author manuscript, 242 KB

http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=7174889

Cite this

@inproceedings{2eda857b895248988beecde3311fc3ed,

title = "The Hunt for a Red Spider: Conjunctive Query Determinacy Is Undecidable",

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.",

author = "Tomasz Gogacz and Jerzy Marcinkowski",

year = "2015",

doi = "10.1109/LICS.2015.35",

language = "English",

isbn = "978-1-4799-8875-4",

pages = "281 -- 292",

booktitle = "Logic in Computer Science (LICS), 2015 30th Annual ACM/IEEE Symposium on",

publisher = "Institute of Electrical and Electronics Engineers (IEEE)",

address = "United States",

}

TY - GEN

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

AU - Gogacz, Tomasz

AU - Marcinkowski, Jerzy

PY - 2015

Y1 - 2015

N2 - 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.

AB - 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.

U2 - 10.1109/LICS.2015.35

DO - 10.1109/LICS.2015.35

M3 - Conference contribution

SN - 978-1-4799-8875-4

SP - 281

EP - 292

BT - Logic in Computer Science (LICS), 2015 30th Annual ACM/IEEE Symposium on

PB - Institute of Electrical and Electronics Engineers (IEEE)

ER -