Constraint processing in relational database systems: From theory to implementation

Constraint satisfaction problems (CSP) are frequently solved over data residing in relational database systems. In such scenarios, the database is typically just used as a data storage back end. However, there exist important advantages, such as the wide availability of database practices and tools for modeling, to having database systems that are capable of natively modeling and solving CSPs. This paper introduces general concepts and techniques to extend a database system with constraint processing capabilities. Input CSPs are modeled via SQL, augmented with a non-deterministic guess operator as introduced by Cadoli and Mancini (TPLP 2007). Problems are represented with a combination of internal relations and parse trees, and are translated to a flexible intermediate problem representation that is subsequently translated into several common representations for SAT. Benchmarks with a prototype system show the feasibility of the approach and demonstrate the promise of a strong integration of CSP solvers and database systems.