## 3 The Proposed Distributed SPARQL Query Processing Scheme
### Query Decomposition  
A SPARQL query that is optimized to distributed data is divided into subqueries and transferred for query processing of RDF graph in a distributed environment. If queries that are unsuitable to distributed data are transferred and processed, efficient query processing cannot be conducted, and disk I/O cost and data communication cost are increased during query processing. In addition, communication cost increases as the number of subqueries increases during query processing after a SPARQL query is divided into subqueries. Thus, efficient query processing that can reduce the communication cost through grouping of subqueries is conducted. For example, if the RDF graph is distributed over a few nodes, as shown in Figure 2, only \(N_{1}\) is searched to know the job of the person called \"[PERSON]\" However, the communication cost has to be increased because slave nodes \(N_{1}\), \(N_{2}\), and \(N_{4}\) have to be searched once a SPARQL query is requested to find the living city of \"[PERSON]\" As shown in the above example, query decomposition is needed to reduce the communication cost and achieve efficient query processing. When a query is requested, the query is divided into multiple subqueries based on the WHERE clause. The divided subqueries are grouped through the proposed RDF index first. The subqueries grouped through the index are then second grouped with related subqueries among S, P, and O. The data communication cost is reduced during query processing through the second grouping. In addition, the second-grouped queries are stored as a format of RDD and utilized. This can not only reduce the disk I/O cost incurred in existing schemes by storing queries at the RDD format inside the Spark but also achieve more efficient query processing than existing schemes through query processing in the in-memory environment. A query that is optimized to distributed data should be sent to process RDF graph queries in a distributed environment. If queries that are unsuitable to distributed data are transferred and processed, efficient query processing cannot be conducted, and disk I/O cost and data communication cost are increased during query processing. Thus, efficient query processing can be conducted by decomposing a SPARQL query into subqueries. As shown in Figure 3, once the SPARQL query is entered, the WHERE clause in the SPARQL is divided. The WHERE clause is decomposed into subqueries. After being decomposed into subqueries, related nodes are searched through the index. The index is composed based on S, P, and O about all triple data. It has information about S, P, and O of each record, and information about all combinations of S, P, and O such as SP, PO, SO, or SPO, etc., are also stored. The ID numbers of the nodes that store the information are also stored. The index used is different according to the characteristics of the subqueries. For example, if the subject index's type is Name, all of the Name information is stored, and a node where the Name is stored is also stored along with the ID number of the node. If a data record  
Figure 2: Example of an RDF graph. called Name is stored in multiple nodes, plural ID numbers of the nodes are stored. For example, if there is a query (Kim, isj,ob,?A) among the subqueries, since \"?A\" in the object is a variable, the value is not known. In such a case, although the object is not known, the subject and predicate are known, thus that it can be searched through the SP index out of the indices. A query can be efficiently processed in the distributed stored RDF environment by decomposing a query entered by the client. However, in order to produce a final result when a single query is decomposed into multiple subqueries, intermediate results decomposed through communication should be made into a single final result with regard to query processing results of subqueries. A large amount of communication cost is incurred to have a single final result.