A First Practical Algorithm for High Levels of Relational Consistency

Authors

  • Shant Karakashian University of Nebraska-Lincoln
  • Robert Woodward University of Nebraska-Lincoln
  • Christopher Reeson University of Nebraska-Lincoln
  • Berthe Choueiry University of Nebraska-Lincoln
  • Christian Bessiere University of Montpellier, France

DOI:

https://doi.org/10.1609/aaai.v24i1.7535

Keywords:

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

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

Downloads

Published

2010-07-03

How to Cite

Karakashian, S., Woodward, R., Reeson, C., Choueiry, B., & Bessiere, C. (2010). A First Practical Algorithm for High Levels of Relational Consistency. Proceedings of the AAAI Conference on Artificial Intelligence, 24(1), 101-107. https://doi.org/10.1609/aaai.v24i1.7535

Issue

Vol. 24 No. 1 (2010): Twenty-Fourth AAAI Conference on Artificial Intelligence

Section

Constraints, Satisfiability, and Search