Improving Relational Consistency Algorithms Using Dynamic Relation Partitioning
| Autor: | Robert J. Woodward, Berthe Y. Choueiry, Christian Bessiere, Anthony Schneider |
|---|---|
| Přispěvatelé: | Constraint Systems Laboratory, University of Nebraska [Lincoln], University of Nebraska System-University of Nebraska System, Agents, Apprentissage, Contraintes (COCONUT), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), European Project: 284715,EC:FP7:ICT,FP7-ICT-2011-C,ICON(2012), University of Nebraska–Lincoln, Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS) |
| Jazyk: | angličtina |
| Rok vydání: | 2014 |
| Předmět: |
Consistency (database systems)
Theoretical computer science Weak consistency Relation (database) Sequential consistency Local consistency Consistency model Causal consistency Computer Science::Computational Complexity Algorithm Constraint satisfaction problem Mathematics [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI] |
| Zdroj: | 20th International Conference on Principles and Practice of Constraint Programming CP: Principles and Practice of Constraint Programming CP: Principles and Practice of Constraint Programming, Sep 2014, Lyon, France. pp.688-704, ⟨10.1007/978-3-319-10428-7_50⟩ Lecture Notes in Computer Science ISBN: 9783319104270 CP |
| DOI: | 10.1007/978-3-319-10428-7_50⟩ |
| Popis: | International audience; Relational consistency algorithms are instrumental for solving difficult instances of Constraint Satisfaction Problems (CSPs), often allowing backtrack-free search. In this paper, we improve an algorithm for enforcing relational consistency by exploiting the property that the constraints of the dual encoding of a CSP are piecewise functional. This property allows us to partition a CSP relation into blocks of equivalent tuples at varying levels of granularity. Our new algorithm dynamically exploits those partitions. Our experiments show a significant improvement of the processing time for enforcing relational consistency. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|