TY - GEN
T1 - Reformulating positive table constraints using functional dependencies
AU - Cambazard, Hadrien
AU - O'Sullivan, Barry
PY - 2008
Y1 - 2008
N2 - Constraints that are defined by tables of allowed tuples of assignments are common in constraint programming. In this paper we present an approach to reformulating table constraints of large arity into a conjunction of lower arity constraints. Our approach exploits functional dependencies. We study the complexity of finding reformulations that either minimize the memory size or arity of a constraint using a set of its functional dependencies. We also present an algorithm to compute such reformulations. We show that our technique is complementary to existing approaches for compressing extensional constraints.
AB - Constraints that are defined by tables of allowed tuples of assignments are common in constraint programming. In this paper we present an approach to reformulating table constraints of large arity into a conjunction of lower arity constraints. Our approach exploits functional dependencies. We study the complexity of finding reformulations that either minimize the memory size or arity of a constraint using a set of its functional dependencies. We also present an algorithm to compute such reformulations. We show that our technique is complementary to existing approaches for compressing extensional constraints.
UR - https://www.scopus.com/pages/publications/56449087084
U2 - 10.1007/978-3-540-85958-1_28
DO - 10.1007/978-3-540-85958-1_28
M3 - Conference proceeding
AN - SCOPUS:56449087084
SN - 3540859578
SN - 9783540859574
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 418
EP - 432
BT - Principles and Practice of Constraint Programming - 14th International Conference, CP 2008, Proceedings
T2 - 14th International Conference on Principles and Practice of Constraint Programming, CP 2008
Y2 - 14 September 2008 through 18 September 2008
ER -