Enabling Relational Databases for Effective CSP Solving 公开

Abstract

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, to having database systems that are capable of natively modeling and solving CSPs. This research introduces general concepts and techniques to extend a database system with constraint processing capabilities. The work focuses on relational constraint satisfaction problems (RCSP) and their specification in SQL, compiling RCSP into boolean satisfiability problems, supporting multiple solving algorithms, and automated problem decomposition.

Table of Contents

1 Introduction 1
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Constraint Satisfaction Problem . . . . . . . . . . . . . . . . . . . . . 2
1.3 Relational Database . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.4 Relational Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.5 Relational CSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.6 SQL CSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.7 Example Use Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2 Related Work 9
2.1 CONSQL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 D-Wave . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.3 Deductive Databases . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.4 Open Research Quesions . . . . . . . . . . . . . . . . . . . . . . . . . 13

3 Proposed Solution 14

3.1 Leveraging SQL's Data Definition Language . . . . . . . . . . . . . . 15
3.2 Translating RCSP to Boolean Satisfiability . . . . . . . . . . . . . . . 17
3.2.1 Variable Map . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.2.2 Extended Conjunctive Normal Form . . . . . . . . . . . . . . 20
3.2.3 SQL Constraint Patterns . . . . . . . . . . . . . . . . . . . . . 21
3.2.4 Translation Summary . . . . . . . . . . . . . . . . . . . . . . . 31
3.3 Problem Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.4 Solver Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

4 Implementation Details 40
4.1 The SCDE Command Language . . . . . . . . . . . . . . . . . . . . . 41
4.2 The RCSP Processor . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.2.1 Problem Modeler . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.2.2 Variable Map Processor . . . . . . . . . . . . . . . . . . . . . 45
4.2.3 Constraint Processor . . . . . . . . . . . . . . . . . . . . . . . 46
4.2.4 Problem Decomposer . . . . . . . . . . . . . . . . . . . . . . . 49
4.3 The eCNF Solver . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.3.1 Unifier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.3.2 Simplifer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.3.3 Translator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

4.3.4 Back-End Solvers . . . . . . . . . . . . . . . . . . . . . . . . . 55

5 Theoretical Analysis 57
5.1 On the Expressiveness of SCL . . . . . . . . . . . . . . . . . . . . . . 57
5.1.1 3-SAT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
5.1.2 Count Constraints . . . . . . . . . . . . . . . . . . . . . . . . 59
5.2 Variable Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
5.3 Boolean Clauses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
5.3.1 Check Exists . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
5.3.2 Check Count . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
5.3.3 Check Not Exist . . . . . . . . . . . . . . . . . . . . . . . . . 64
5.3.4 Check Not Exist Count . . . . . . . . . . . . . . . . . . . . . . 64

6 Experiments and Results 65
6.1 NQueens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
6.1.1 SCL Specification . . . . . . . . . . . . . . . . . . . . . . . . . 68
6.1.2 OPL and XCSP Specification . . . . . . . . . . . . . . . . . . 71
6.1.3 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
6.2 Round Robin Tournament . . . . . . . . . . . . . . . . . . . . . . . . 75
6.2.1 SCL Encoding . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
6.2.2 CB-Decomposition . . . . . . . . . . . . . . . . . . . . . . . . 77

6.2.3 OPL and XCSP Encodings . . . . . . . . . . . . . . . . . . . . 79
6.2.4 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
6.3 Course Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
6.3.1 SCL Specification . . . . . . . . . . . . . . . . . . . . . . . . . 88
6.3.2 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
6.4 Oxford College Freshman Partitioning . . . . . . . . . . . . . . . . . 93
6.4.1 SCL Specification . . . . . . . . . . . . . . . . . . . . . . . . . 94
6.4.2 OPL Specification . . . . . . . . . . . . . . . . . . . . . . . . . 96
6.4.3 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96

7 Conclusion 98
7.1 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
7.1.1 Optimization Problems . . . . . . . . . . . . . . . . . . . . . . 99
7.1.2 Interactive CSP Solving . . . . . . . . . . . . . . . . . . . . . 99
7.1.3 Other Decomposition Approaches . . . . . . . . . . . . . . . . 100
7.2 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100

About this Dissertation

Rights statement

• Permission granted by the author to include this thesis or dissertation in this repository. All rights reserved by the author. Please contact the author for information regarding the reproduction and use of this thesis or dissertation.

School	Laney Graduate School
Department	Math and Computer Science
Degree	PhD
Submission	Dissertation
Language	English
Research Field	Computer Science Artificial Intelligence
关键词	Constraint Satisfaction Problem Relational Database
Committee Chair / Thesis Advisor	Lu, James, Emory University
Committee Members	Mandelberg, Kenneth I, Emory University Xiong, Li, Emory University Parekh, Ojas, Emory University

最新修改

Primary PDF

Thumbnail	Title	Date Uploaded	Actions
	Enabling Relational Databases for Effective CSP Solving ()	2018-08-28 12:58:55 -0400	Press to Select an action Download

Supplemental Files

Thumbnail	Title	Date Uploaded	Actions
	Paper.tar.gz ()	2018-08-28 13:01:57 -0400	Press to Select an action Download