Red Spider Meets a Rainworm: Conjunctive Query Finite Determinacy Is Undecidable.
Tomasz GogaczJerzy MarcinkowskiPublished in: CoRR (2015)
Keyphrases
- conjunctive queries
- unions of conjunctive queries
- guarded fragment
- query containment
- np complete
- query answering
- integrity constraints
- datalog programs
- query evaluation
- data complexity
- data exchange
- query rewriting
- query language
- special case
- probabilistic databases
- decision procedures
- relational queries
- bounded treewidth
- data model
- boolean expressions
- acyclic conjunctive queries
- data integration
- search algorithm
- functional dependencies
- dnf formulas
- lower bound
- computational complexity
- knowledge base