On the Undecidability of the Equivalence of Second-Order Tuple Generating Dependencies.
Ingo FeinererReinhard PichlerEmanuel SallingerVadim SavenkovPublished in: AMW (2011)
Keyphrases
- query containment
- tuple generating dependencies
- conjunctive queries
- query answering
- transitive closure
- inconsistent databases
- integrity constraints
- data exchange
- datalog programs
- function symbols
- np complete
- decision procedures
- data complexity
- query rewriting
- special case
- answering queries
- query language
- query evaluation
- query optimization
- regular expressions
- incomplete information
- tree patterns
- data integration
- inclusion dependencies
- unions of conjunctive queries
- exptime complete
- object oriented
- database schema
- dl lite
- description logics
- state space