The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems
| Autor: | Gianluigi Greco, Francesco Scarcello |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Mathematical optimization
Theoretical computer science General Computer Science General Mathematics 0102 computer and information sciences 01 natural sciences 03 medical and health sciences 0302 clinical medicine 010201 computation theory & mathematics 030220 oncology & carcinogenesis Local consistency Database theory Conjunctive query Decomposition method (constraint satisfaction) Tuple Heuristics Computer Science::Databases Constraint satisfaction problem Boolean conjunctive query Mathematics |
| Zdroj: | SIAM Journal on Computing. 46:1111-1145 |
| ISSN: | 1095-7111 0097-5397 |
| DOI: | 10.1137/16m1090272 |
| Popis: | Answering conjunctive queries is a fundamental problem in database theory, and it is equivalent to solving constraint satisfaction problems in artificial intelligence and to other fundamental problems arising in computer science, which can be recast in terms of looking for homomorphisms between relational structures. The problem is NP-hard, so that several research efforts have been made in the literature for identifying tractable classes, known as islands of tractability, as well as for devising clever heuristics for solving efficiently real-world instances. Many heuristic approaches are based on enforcing on the given instance a property called local consistency (also, relational arc-consistency), where each tuple in every query atom matches at least one tuple in every other query atom. Interestingly, for many well-known classes of instances, such as for the acyclic ones, enforcing local consistency is even sufficient to solve the given instance correctly. However, the precise power of such a procedure ... |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|