## 3 Hybrid Index System
### Two-Step SPARQL Query Processing  
Two types of queries that we concentrate on are the single and join triple query patterns. Because the processing of the single triple query pattern is straightforward, we focus on the join triple query pattern, which is expressed as a conjunction of multiple triple patterns. There are eight triple patterns in the SPARQL queries: (s, p, o), (s, p,?o), (?s, p, o), (s,?p, o), (s,?p, o), (?s,?p, o), (?s, p,?o), and (?s,?p,?o) [13]. Because (?s,?p,?o) requires a full scan and the matching number of (s, p, o) is either 0 or 1, only the execution procedures regarding the other six triple patterns need to be evaluated. Due to page length limitations, we only explain the evaluation of (s, p,?o) here. The processing of this pattern comprises two steps: the filtering and refinement phases. The filtering phase prunes the search space using the 3D R*-tree. Using this tree, we determine all candidate MBBs that possibly provide the result. The triple pattern (s, p,?o) is first transformed into coordinates in the three-dimensional space by applying the same hash function used for building the MDH*. Because the triple pattern includes a query variable (prefixed with?) at the object position, this processing is treated as a line rather than a point (note that (?s, p,?o) is treated as a plane). Using this query line, we can locate all MBBs overlapping the line in the 3D R*-tree. After identifying all candidate MBBs, we can refine the immediate result using the \(k\)-d trees. For the immediate result obtained in the filtering phase, the refinement phase precisely evaluates the query condition. Using our 3D R*-tree, we can quickly select MBBs that contain all possible extended RDF tuples matching the join triple query pattern. Considering Example 1 of the (s, p,?o) (?s, p,?o) chain query type, the join triple query pattern combines extended RDF tuples using two or more candidate results. Although join processing has been extensively studied in the literature, algorithms designed for traditional join processing can hardly be used for the SPARQL join without modifications. Only the nested-loop join algorithm can be used without any modification. Thus, the nested-loop join algorithm serves as the starting point. Algorithm 2 shows a detailed illustration of our MDH*-based join processing algorithm for the chain query type. It is a revised version of the traditional nested-loop join algorithm. In line 1, we determine whether a query is a possible SPARQL triple pattern. In line 4, we obtain a filtering result by joining the previous and current results using MBB. The input of our refinement phase is a set of pairs of relevant extended RDF tuples in the \(k\)-d trees. In the join procedure of line 13, two input sets (X and Y) are compared in the inner loop using equijoin techniques to determine the matching between the sets. If \(\alpha\
eq 0\), lines 17-20 are performed. This process first checks whether the two input sets satisfy the join condition. If so, these two tuples are appended to the final result and \(\alpha\) is decremented by 1. This procedure is repeated until \(\alpha\) becomes 0. Therefore, our algorithm can skip unnecessary operations that clearly do not fulfill the join condition. After eliminating thesefalse hits, a recursive URI lookup process [4] is performed using link traversal techniques. A similar algorithm is applied to \(\beta\) for the (?s, p, o) \(\Join\) (?s, p,?o) query pattern (e.g., select?n where {?f foa:lastName Lucy. ?n foaf:knows?f}). Example 1 shows a SPARQL query expressing the join between two triple patterns. In traditional join techniques, after receiving a SPARQL query, a query engine usually performs a nested-loop join algorithm without considering the count frequencies. Figure 8 shows two input sets of the nested-loop join algorithm using our running example. The input sets in this figure are shaded. The join cost will be approximately 3 \(\times\) 9 = 27 tuple comparisons.