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

Tomasz Gogacz Jerzy Marcinkowski

Published in: LICS (2015)

Keyphrases

conjunctive queries
query containment
np complete
unions of conjunctive queries
datalog programs
query answering
query evaluation

integrity constraints
data complexity
query rewriting
query language
probabilistic databases
database theory

decision procedures
data exchange
np hard
special case
relational database theory
guarded fragment

boolean expressions
answering queries
satisfiability problem
deductive databases
schema mappings
databases