Extending the relational model with constraint satisfaction

Abstract

We propose a new approach to data driven constraint programming. By extending the relational model to handle constraints and variables as first class citizens, we are able to express first order logic SAT problems using an extended SQL which we refer to as SAT/SQL. With SAT/SQL, one can efficiently solve a wide range of practical constraint and optimization problems. SAT/SQL integrates both SAT solver and relational data processing to enable efficient and large scale data driven constraint programming. Furthermore, our research presents two novel meta-programming operators: MINREPAIR and MIN-CONFLICT which are iterative debugging facilities for constraint programming with SAT/SQL.