# Squill: Testing DBMS with Correctness Feedback and Accurate Instantiation
## 3 Design of Squill
### Semantics-Aware Instantiation
#### 3.2.2 Instantiation of Complicated Semantics  
Instantiation of complicated semantics is performed in SQL statements with column-table dependency, including SELECT, INSERT, and UPDATE statements. It is performed within one SQL statement, as the dependency between column and table is not across statements. For example, there are two independent SELECT statements. The columnname in the former and the table name in the latter are irrelevant. The instantiation of complicated semantics includes three stages, collecting nodes, building dependency, and filling semantics, as shown in Algorithm 3. Note that since an input of Squill is composed of multiple SQL statements, the instantiation of complicated semantics is often performed multiple times for an input. ```
1:\(ColumnList\gets Column[]\);
2:\(VirtualTableList\gets VirtualTable[]\);
3:\(DependencyList\gets map(Column,VirtualTable)\);
4:functionInstantiation(\(root\))
5:// A. Collecting Nodes
6:for each ColumnNode in SelectTarget, Where...do
7:// Convert node to Column
8:ColumnList.add(ColumnParser(ColumnNode));
9:endfor
10:for each TableNode in From, InsertTable, UpdateTable do
11:// Convert node to VirtualTable
12:VirtualTableList.add(TableParser(TableNode));
13:endfor
14:for each SubQueryNode do
15:// Process subquery recursively
16:Instantiation(SubQueryNode);
17:if SubQueryNode is in From then
18:VirtualTableList.add(SubQueryParser(SubQueryNode));
19:endif
20:endfor
21:// B. Building Dependency
22:for each Column in ColumnList do
23:DependencyList[Column]=RandChoose(VirtualTableList);
24:endfor
25:// C. Filling Semantics
26:for each (Column, VirtualTable) in DependencyList do
27:if VirtualTable is not filled then
28: FillVirtualTable(VirtualTable);
29:endif
30: FillColumn(Column);
31:endfor
32: FillVirtualTableNotInDependencyList();
33:endfunction
```  
**Algorithm 3** Instantiation of complicated semantics. **A. Collecting Nodes. ** While traversing AST, we collect the node with complicated semantics based on the type and context information of the current node and store it in the corresponding data structure (Line 5-20). For the SELECT statement, we collect column name nodes in select target, function parameter, WHERE, GROUP BY, ORDER BY, and WINDOW clauses, storing them in the data structure called Column (Line 6-9). Column stores not only the column name node but also the alias node and the table name node corresponding to the column name node, if they exist. With the help of context information, we can describe a column abstractly. Similarly, we collect the column name node in the insert and update the target clause of the INSERT and UPDATE statement. For the table name, since we want to treat the result of the subquery as a table, we define a data structure called VirtualTable to represent a table. VirtualTable includes a table name node, an array of Column, and the alias node of the table, which can describe a table or the result of a subquery. For the SELECT statement, we collect the table name node in the FROM clause. For INSERT and UPDATE statements, we collect their target table name nodes (Line 10-13). For subqueries, we process them recursively, instantiating them from inner to outer (Line 14-20). For the subquery in FROM clause of the SELECT statement, we treat the result of it as a table in the subsequent dependency construction. For the subquery in other clauses, such as in the WHERE clause, we instantiate it like a SELECT statement since there is no external dependency within it. Figure 5 shows the data structure that contains nodes in the main SELECT statement, where Column_x4 and Column_x5 are the data structure Column which contains nodes x4 and x5. VirtualTable describes a table (x10) or the result of a subquery (s1) by filling different fields (TableNameNode or ColumnList). When parsing, we recursively processed subqueries, which means that the subquery and the main SELECT statement will be parsed with the same function, and the subquery will be instantiated before the outer query.