Constraint processing in relational database systems: From theory to implementation

J.J. Lu, S. Siva, O. Parekh, G.H.L. Fletcher, Hantao Zhang

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

4 Citations (Scopus)


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.
Original languageEnglish
Title of host publicationProceedings 25th ACM Symposium on Applied Computing (SAC'10, Sierre, Switzerland, March 22-26, 2010)
EditorsS.Y. Shin, S. Ossowski, M. Schumacher, M.J. Palakal, C.C. Hung
Place of PublicationNew York NY
PublisherAssociation for Computing Machinery, Inc
ISBN (Print)978-1-60558-639-7
Publication statusPublished - 2010


Dive into the research topics of 'Constraint processing in relational database systems: From theory to implementation'. Together they form a unique fingerprint.

Cite this