## 3 The Proposed Distributed SPARQL Query Processing Scheme
### Query Processing Procedure  
The communication and join costs incurred when distributed intermediate results are combined into a single final result during query processing in the distributed stored RDF environment. In addition, a query processing order and joining method can increase or decrease the cost of query processing. Thus, the optimal query execution path is created to reduce the join and data communication costs incurred during query processing in the query processing execution path. A query execution path is created in consideration of data parsing, communication cost between nodes, and queuing time to reduce the query processing cost incurred during query processing, which is not taken into consideration in existing schemes. The join and communication costs can be reduced by performing query processing through the created query execution paths. Figure 5 shows the overall query processing procedure. First, when a query is inputted, the proposed scheme decomposes the query. Once the subqueries grouped from query decomposition are entered, all possible query execution paths are generated. After all possible query execution paths are generated, the cost of performing the query paths is calculated through the proposed algorithm. The optimal query execution path is selected through the cost calculation, and queries are processed through the selected query execution path. We obtain a final result. We cannot know if it is possible to process a query using which query execution path when processing it in the distributed stored RDF environment. Thus, we create all possible query execution paths based on the subqueries. A large amount of the join and communication costs can be incurred during query processing performed according to the created query execution paths. Thus, an efficient and optimal query execution path is selected from all possible executable query paths to process a query. The join and communication costs can be reduced during query processing by processing a query through the selection of the selected query execution path. The optimal query path is selected through the cost calculation of the created query paths. First, the query cost of the group by node is calculated via Equation (1). \(Parse(SQ_{i})\) refers to the cost of data parsing for the \(SQ_{i}\) in the corresponding node. The query processing cost when the number of \(SQ_{i}\) in the corresponding node is only one is \(Result(SQ_{i})\). However, if the number of \(SQ_{i}\) is more than one, the query processing cost of the group by node is calculated including join cost \(Join(Parse(SQ_{i})+Result(SQ_{i-1}))\) among \(SQ_{i}\). \[Result(SQ_{i})=\left\{ \begin{array}{rl}Join(Parse(SQ_{i})+Result(SQ_{i-1}) ),&i>1\\ Parse(SQ_{i}),&i=1\end{array} \right. \tag{1}\]  
The cost is calculated by dividing a case when the number of subqueries is one and two or more according to the group by node. When subqueries are connected adjacently inside the group, even if the number of subqueries is more than two, it is regarded as a single subquery to calculate the cost. Once the cost for each group inside each node is calculated, all possible query paths are created through Equation (2) (ETE: Estimated Time Equation algorithm) based on the join variables between groups by node overall. After all the query paths are determined based  
Figure 5: Query processing procedure. on the join variables between groups, the cost of the query paths is calculated. To calculate Equation (2), which node is used to process \(GQ_{i}\) (Groups by node) should be determined as presented in Equation (3). If \(GQ_{1}\) and \(GQ_{2}\) can be joined, and which \(GQ_{i}\) is moved is determined through Equation (3) to process a query. The cost is compared via Equation (3) between \(GQ_{1}\) to \(GQ_{2}\left(T^{r}_{GQ1-GQ2}\right)\) or from \(GQ_{2}\) to \(GQ_{1}\left(T^{r}_{GQ2-GQ1}\right)\), and \(GQ\) is moved to the less-cost direction.