Extending SQL with Graph Matching and Set Covering for Decision Support Applications

Abstract:

Graph matching, set covering, and partitioning problems are both theoretically and practically important in decision support systems. Numerous decision support applications have been modeled as graph matching, set covering, and partitioning problems. These include applications in the areas of task assignment, marriage problem. airline crew scheduling. truck deliveries or vehicle routing. political redistricting, and the like. Currently. these applications are supported through programs written in external (to the database system) programming languages that use only the data in the database system. Thus, decision makers or application programmers require extra effort to get required decision support information. As opposed to database systems, the purpose of a model management system (MMS) is to make a wide variety of models available to decision makers so they can apply these models without having to become involved in technical and/or procedural aspects of implementation. The goal of this research is to integrate database systems and model systems for zero-one integer programming problems especially concerning graph matching. set covering, and partitioning problems. Users utilize a single integrated language for both problem formulation and model execution. In order to achieve this goal, we extend relationl operators and the query language SQL. The relational operators are extended with six operators, namely, match, maxmatch, cover, mincover, partition, and minpartition. Some of these operators may take a very long time to find an optimal solution. In this article, we adopted genetic algorithms to find a near-optimal solution of this kind of operators. We found they performed well both on the computational effort and on the quality of the solutions through a variety of test problems. These algorithms are bounded by a polynomial time. therefore, they enable a DBMS to respond to queries involving proposed operators in a restricted amount of time.

Key Words and Phrases::

• decision support systems
• genetic algorithms
• integer programming
• model management systems
• relational database
• SQL

Additional information

Notes on contributors

Jorng-Tzong Horng

Jorng-Tzong Horng is Associate Professor of Computer Science and Information Engineering at the National Central University, Chungli, Taiwan. He received his Ph.D. in computer science from National Taiwan University. His major research focus is on database systems, object-oriented databases, and combinatorial optimization.

Gwo-Dong Chen

Gwo-Dong Chen is Associate Professor of Computer Science and Information Engineering at the National Central University, Chungli, Taiwan. He received his Ph.D. in electrical engineering from National Taiwan University. His major research focus is on object-oriented databases, multimedia, and intelligent computer-assisted learning systems.

Baw-Jhiune Liu

Baw-Jhiune Liu is Professor of Computer Science and Information Engineering at the National Central University, Chungli, Taiwan. He received his Ph.D. in electrical engineering from National Taiwan University. His major research focus is on database systems, object-oriented databases, and combinatorial optimization.