A Characterization of the Complexity of Resilience and Responsibility for Self-join-free Conjunctive Queries.
Cibele FreireWolfgang GatterbauerNeil ImmermanAlexandra MeliouPublished in: CoRR (2015)
Keyphrases
- conjunctive queries
- join queries
- conjunctive query containment
- query answering
- conp complete
- data complexity
- integrity constraints
- np complete
- query evaluation
- conjunctive regular path queries
- query language
- special case
- data exchange
- primary key
- bounded treewidth
- query rewriting
- lower complexity
- query containment
- decision procedures
- decision problems
- query optimization
- boolean expressions
- datalog programs
- pspace complete
- exptime complete
- probabilistic databases
- regular path queries
- query complexity
- unions of conjunctive queries
- lower bound
- computational complexity
- answering queries using views
- data analysis
- containment of conjunctive queries
- tuple generating dependencies
- fixed parameter tractable
- data management
- spatial databases
- join algorithms
- database systems