# An Approach to Aid Decision-Making by Solving Complex Optimization Problems Using SQL Queries
## 2 Materials and Methods
### Three-Coloring Graph Problem  
Graph Coloring Problems and their generalizations help model various scheduling and assignment problems. Some examples are manufacturing systems [25], DSS for timetabling [26], DSS to solve the scheduling problem of an Earth-observing satellite constellation [27], and self-organization in modern networking [28], among others. In this section, we present the three-coloring problem on graphs (3 CG) and propose a SQL statement for solving small instances of the 3 CG problem. The 3 CG is a well-known combinatorial problem. The optimization version of this problem searches for the minimum number of colors such that any pair of adjacent vertices of a graph does not have the same color. Figure 2: General SQL query in BNF format to solve the MCP. The Graph Coloring Problem has applications in several real-world problems such as scheduling [29] or register allocation in a microprocessor [30]. In the scheduling area, different jobs that interfere with each other in using particular resources (e.g., time) must be scheduled to perform a particular job. The jobs and their conflicts can be modeled through a graph. The jobs and their competition for resources can be modeled using a graph. Some instances of the job scheduling problem can be mapped to a 3 CG problem. In register allocation, there is a process that maps the values of program code to a limited set of physical registers in a microprocessor target architecture. The efficient allocation of the registers directly impacts the performance of the execution of a program. An aliveness analysis is conducted to define pairs of program variables that are needed simultaneously (this means that each of the pairs cannot share the same physical register) to find the minimum number of physical registers needed to execute a program efficiently. The pairs of variables represent the edges of a graph, and the program variables represent the graph's nodes. Then, the minimum number of colors needed to guarantee that a pair of adjacent nodes do not have the same color indicates the minimum number of computer registers needed to execute a program efficiently. The 3 CG problem also has applications in real-world problems, e.g., in the resource coordination for wireless environments. In [31], it was shown that an Overlapped Basic Service Sets (OBSSs) environment could be modeled as a planar graph; therefore, the 3 CG problem can be used to solve the channel assignment problem [32] in those networks. In general, the 3 CG problem can be formally defined as follows: a graph \(G=(V,E)\), where \(V\) is the set of nodes and \(E\) is the set of edges linking the nodes, which is the color function \(\mathcal{C}:V\leftarrow\{1,2,\cdots,k\}\) that minimizes the value \(k\) and assigns a color to each vertex \(v_{i}\in V\) such that \(\mathcal{C}(v_{i})\
eq\mathcal{C}(v_{j})\), for all \((v_{i},v_{j})\in E\). SQL Approach for Solving 3 CG  
This subsection presents a SQL statement proposed to solve a 3 CG problem instance. An instance of the 3 CG problem is described as a graph \(G=(V,E)\). Once the query has been created, it is executed in a database management system. The following paragraphs illustrate how to construct a SQL query to solve a 3 CG problem instance. The SQL statements show how to solve the problem for \(K\) colors; after that, solving 3 CG implies using a value of \(K=3\). The proposed SQL query only uses a table that stores the \(K\) colors available for solving a \(K\)-coloring instance. The table is called _colors_ and is composed by the fields \(color,b_{k},b_{k-1},\ldots,b_{1}\). The field _color_ stores the integer value for the different colors. The fields \(b_{i}\), for \(1\leq i\leq k\), have binary values: if the value is 1, it indicates that edge \(i\) has color \"i\"; if the value is 0, it indicates that edge \(i\) does not have color \"i\". Figure 3 shows the generalization of the SQL query to solve MCG instances. The query is given using the BNF notation [24].