Can One Escape Red Chains?: Regular Path Queries Determinacy is Undecidable.
Grzegorz GluchJerzy MarcinkowskiPiotr Ostropolski-NalewajaPublished in: LICS (2018)
Keyphrases
- regular path queries
- conjunctive queries
- query containment
- unions of conjunctive queries
- query rewriting
- query answering
- np complete
- integrity constraints
- query evaluation
- datalog programs
- data complexity
- semistructured databases
- data exchange
- query language
- special case
- decision procedures
- automata theoretic
- regular expressions
- deductive databases
- transitive closure
- schema mappings
- knowledge base
- semistructured data
- graph databases
- query optimization