AAAI Publications, Twenty-Fourth AAAI Conference on Artificial Intelligence

Font Size: 
A First Practical Algorithm for High Levels of Relational Consistency
Shant Karakashian, Robert J. Woodward, Christopher G. Reeson, Berthe Y. Choueiry, Christian Bessiere

Last modified: 2010-07-03


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 relational 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 tightening 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.


CSP; non-binary constraints; local consistency; relational consistency; search; backtracking

Full Text: PDF