 |
HAL-LIRMM - Open Archive |  |
Conference papers
A First Practical Algorithm for High Levels of Relational Consistency
Abstract : Consistency properties and algorithms for achieving them are at the heart of the success of Constraint Programming. In this paper, we study the relational consistency property R(∗,m)C, which is equivalent to m-wise consistency proposed in rela- tional databases. We also define wR(∗,m)C, a weaker variant of this property. We propose an algorithm for enforcing these properties on a Constraint Satisfaction Problem by tighten- ing the existing relations and without introducing new ones. We empirically show that wR(∗,m)C solves in a backtrack- free manner all the instances of some CSP benchmark classes, thus hinting at the tractability of those classes.
Cited literature [17 references]
https://hal-lirmm.ccsd.cnrs.fr/lirmm-00558132
Contributor : Martine Peridier Connect in order to contact the contributor
Submitted on : Friday, January 21, 2011 - 9:54:44 AM
Last modification on : Friday, October 22, 2021 - 3:07:33 PM
Contributor : Martine Peridier Connect in order to contact the contributor
Submitted on : Friday, January 21, 2011 - 9:54:44 AM
Last modification on : Friday, October 22, 2021 - 3:07:33 PM