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