The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems.
Gianluigi GrecoFrancesco ScarcelloPublished in: SIAM J. Comput. (2017)
Keyphrases
- constraint satisfaction problems
- conjunctive queries
- np complete
- constraint networks
- constraint satisfaction
- global constraints
- constraint problems
- data complexity
- path consistency
- query answering
- constraint programming
- np hard
- constraint propagation
- consistency checking
- integrity constraints
- query evaluation
- decision procedures
- database theory
- maintaining arc consistency
- arc consistency
- query language
- disjunctive constraints
- non binary
- constraint solving
- query containment
- special case
- data exchange
- satisfiability problem
- combinatorial problems
- binary constraints
- finite domain
- computational complexity
- search space
- tree decomposition
- reasoning problems
- bounded treewidth
- sat problem
- temporal constraints
- computational problems
- dl lite
- datalog programs
- decomposition methods
- query processing
- data management
- constraint solver
- expressive power
- phase transition