The Hunt for a Red Spider: Conjunctive Query Determinacy Is Undecidable.
Tomasz GogaczJerzy MarcinkowskiPublished in: CoRR (2015)
Keyphrases
- conjunctive queries
- query containment
- datalog programs
- np complete
- unions of conjunctive queries
- query answering
- query evaluation
- integrity constraints
- data complexity
- query language
- query rewriting
- database theory
- data exchange
- special case
- decision procedures
- probabilistic databases
- guarded fragment
- relational database theory
- satisfiability problem
- np hard
- deductive databases
- expressive power
- bounded treewidth
- boolean expressions
- computational complexity
- acyclic conjunctive queries
- conjunctive query containment