A SQL database system for solving constraints

ABSTRACT

It has long been recognized that practical contexts for constraint satisfaction problems (CSP) often involve large relational databases (RDB). Early attempts to marry constraint solving systems and relational database systems include deductive and constraint databases that reuse important ideas from logic programming. These techniques required knowledge outside the scope of traditional database users. The recent proposal by Cadoli and Mancini, "consql", shows that a simple extension to SQL provides a viable basis for modeling CSP. This opens the possibility for transparently integrating CSP with databases using SQL - the most widely known and popular database language. Such an extension brings the power of constraint problem solving to SQL knowledgeable users. Towards that end, the current research describes a case study in the engineering details of designing and implementing such a prototype. The SQL-based constraint data engine (SCDE) supports key concepts of "consql", with several new syntax to better align the administration of CSP related notions with ordinary SQL. SCDE manages the internal representation and solving of constraints through a combination of ordinary SQL and a satisfiability solver, SATO. Initial performance tests on the 1997-98 ACC Basketball Scheduling problem shows the feasibility and potential of the SCDE design. Ongoing and future work include completing a programming environment for end-users to specify, test and debug constraint problem specification; combining the database engine with a more interactive version of SATO to support objective functions, and automatic problem analysis and decomposition for improving the performance of hard constraint problems.

REFERENCES

• 1: Marco Cadoli , Toni Mancini, Combining relational algebra, SQL, constraint modelling, and local search, Theory and Practice of Logic Programming, v.7 n.1-2, p.37-65, January 2007 [doi>10.1017/S1471068406002857]
• 2: D. Chimenti , R. Gamboa , R. Krishnamurthy , S. Naqvi , S. Tsur , C. Zaniolo, The LDL System Prototype, IEEE Transactions on Knowledge and Data Engineering, v.2 n.1, p.76-90, March 1990 [doi>10.1109/69.50907]
• 3: F. Bacchus, CSPs: Adding Structure to SAT. In SAT, 10, 2006.
• 4: H. Ganzinger, G. Hagen, R. Nieuwenhuis, A. Oliveras, and C. Tinelli. DPLL(T): Fast decision procedures. In CAV, 175--188, 2004.
• 5: Martin Henz, Scheduling a Major College Basketball Conference--Revisited, Operations Research, v.49 n.1, p.163-168, January 2001 [doi>10.1287/opre.49.1.163.11193]
• 6: J. Jaffar and M. J. Maher. Constraint Logic Programming: A Survey. Journal of Logic Programming, 19/20:503--581, 1994.
• 7: Paris C. Kanellakis , Dina Q. Goldin, Constraint Programming and Database Query Languages, Proceedings of the International Conference on Theoretical Aspects of Computer Software, p.96-120, April 19-22, 1994
• 8: J. Liu, X. Dong and A. Halevy. Answering Structured Queries on Unstructured Data, In WebDB, 37--65, 2006.
• 9: Robin Lohfert , James J. Lu , Dongfang Zhao, Solving SQL Constraints by Incremental Translation to SAT, Proceedings of the 21st international conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems: New Frontiers in Applied Artificial Intelligence, June 18-20, 2008, Wrocław, Poland [doi>10.1007/978-3-540-69052-8_70]
• 10: K. Marriott, P. Stuckey. Programming with constraints. MIT Press, Cambridge, MA, 1998.
• 11: George L. Nemhauser , Michael A. Trick, Scheduling a Major College Basketball Conference, Operations Research, v.46 n.1, p.1-8, January 1998 [doi>10.1287/opre.46.1.1]
• 12: S. Siva. Ph.D. Thesis, in progress.
• 13: Carlo Zaniolo, Deductive databases—theory meets practice, Proceedings of the 2nd international conference on extending database technology: Advances in Database Technology, p.1-15, March 1990, Venice, Italy
• 14: Hantao Zhang, SATO: An Efficient Propositional Prover, Proceedings of the 14th International Conference on Automated Deduction, p.272-275, July 13-17, 1997
• 15: H. Zhang. The SatBox Library http://www.cs.uiowa.edu/~hzhang/satbox/, 2006
• 16: H. Zhang, Generating college conference basketball schedules by a SAT solver, Fifth International Symposium on Theory and Applications of Satisfiability Testing, 281--291, 2002.
• 17: H. Zhang, D. Li, and H. Shen. A SAT based scheduler for tournament schedules. In SAT, 2005.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Scheduling

General Terms:
Algorithms, Design, Languages

Keywords:
SQL, constraint databases, satisfiability (sat)