DB_CSP: A Framework and Algorithms for Applying Constraint Solving within Relational Databases

Abstract. We examine combinatorial search problems that arise when evaluating combinatorial queries in relational database systems. Such queries request tuples from multiple relations that satisfy a conjunction of constraints on tuple attribute values, and are not executed efficiently by current database systems. We propose an approach by which such problems can be addressed with constraint solving technology. First, we formalize combinatorial queries in databases as a new type of constraint satisfaction problem: what we call Database Constraint Satisfaction Problems (DB_CSPs). Then, we develop algorithms for solving DB_CSPs that integrate database data management technology with conventional CSP solving techniques. Our algorithms enable efficient domain refinement for tuple-valued data and minimize I/O operations when relations are stored on disk. Finally, we present experimental studies that both quantify the performance of our approach and permit comparison with a conventional database system. We show that our approach is superior for solving complex combinatorial queries.