A Case Study in Engineering SQL Constraint Database Systems (Extended Abstract)

摘要

Practical contexts for constraint satisfaction problems (CSP) often involve large relational databases. The recent proposal by Cadoli and Mancini, CONSQL, shows that a simple extension to SQL provides a viable basis for modeling CSP [1]. This enables the transparent integration of CSP solvers with databases using SQL - the most widely known and popular database language, and opens the possibility for making the power of CSP technology accessible to SQL knowledgeable users. To realize this potential, substantial engineering efforts, each with the goal of delivering increasingly sophisticated tools will be required. To that end, this extended abstract describes a case study in the design and implementation of a SQL constraint data engine (SCDE). SCDE manages the internal representation and solving of constraints through a combination of ordinary SQL and a complete, high-performance satisfiability (SAT) solver, SATO. This design complements the simulator described in [1] for CONSQL, which exploits an incomplete constraint solver JLocal. Motivations for the orthogonal design are as follows. First, many CSPs over relational databases involve finite domains and can be represented and solved within the SAT paradigm. Second, significant advances have occurred in the last decade in (DPLL-based) complete SAT solvers, including systems that allow the process of partial model generation to be intertwined with problem-specific literal selections strategies [10]. Third, the completeness property and the ability to enumerate solutions provides opportunities for interesting post-processing of CSP solutions inside the database engine.