The Hunt for a Red Spider: Conjunctive Query Determinacy Is Undecidable.
Tomasz GogaczJerzy MarcinkowskiPublished 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