TY - JOUR
T1 - Extending SQL with graph matching and set covering for decision support applications
AU - Horng, Jorng Tzong
AU - Chen, Gwo Dong
AU - Liu, Baw Jhiune
PY - 1994
Y1 - 1994
N2 - 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 redis-tricting, 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 relational 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.
AB - 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 redis-tricting, 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 relational 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.
KW - Decision support systems
KW - Genetic algorithms
KW - Integer programming
KW - Model management systems
KW - Relational database
KW - SQL
UR - http://www.scopus.com/inward/record.url?scp=71549122652&partnerID=8YFLogxK
U2 - 10.1080/07421222.1994.11518032
DO - 10.1080/07421222.1994.11518032
M3 - 期刊論文
AN - SCOPUS:71549122652
SN - 0742-1222
VL - 11
SP - 101
EP - 129
JO - Journal of Management Information Systems
JF - Journal of Management Information Systems
IS - 1
ER -