A First Practical Algorithm for High Levels of Relational Consistency - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Conference Papers Year : 2010

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.
Fichier principal
Vignette du fichier
aaai10-rwise.pdf (208.45 Ko) Télécharger le fichier
Loading...

Dates and versions

lirmm-00558132 , version 1 (21-01-2011)

Identifiers

  • HAL Id : lirmm-00558132 , version 1

Cite

Shant Karakashian, Robert J. Woodward, Christopher Reeson, Berthe Y. Choueiry, Christian Bessiere. A First Practical Algorithm for High Levels of Relational Consistency. AAAI Conference on Artificial Intelligence, Jul 2010, Atlanta, GA, United States. pp.101-107. ⟨lirmm-00558132⟩
113 View
9 Download

Share

More