In this paper, we designed a highly parallel engine for RDF, which includes a new RDF storage model with little memory dependence and a Machine Learning algorithm. Based on the above two points, we present a heuristic query decomposition algorithm to split a SPARQL query into subqueries and then process these subqueries parallelly. Experiments show that our engine perform better on SPARQL query execution with maximizing the usage of memory.
In this paper, we propose a novel approach to manage RDF data(named TriStore). Figure 1 is an example of TriStore used to store RDF data. In order to save memory usage, instead of storing entire strings or URIs, we use shortened versions or keys. For each RDF element value, TriStore maintains a mapping table that maps these keys to their corresponding strings. After encoding, we convert Figure 1(a) into Figure 1(b). In order to match queries more e ciently, subject predicate object rdf:George rdf:hasJob rdf:FullProfes
sor rrrdddfffSS:::GttUUaaettnneeoiissttreegdde rrrdddfff::ll:iitvvyeepIIenn rrrdddfffSS:::CttUUaaottnnueeiinsstteetrddy rdf:FullProfes rdf:type rdf:Professor
sor rdf:Professor rdf:workAt rdf:University rdf:Canada rdf:type rdf:Country (a) we use three tables(Figure 1(c), Figure 1(d), Figure 1(e)) to store set of triples Di in memory, which support the following query operations, where s, p and o are subject, predicate and object: 1. given p, return set f(s; o)j < s; p; o >2 Dig 2. given s and p, return set foj < s; p; o >2 Dig 3. given o and p, return set fsj < s; p; o >2 Dig
Where Figure 1(c), Figure 1(d) and Figure 1(e) are used to support query types 1, 2 and 3 above, respectively. For the rst type of query, only the predicate p is known, and we want to get all p-related s and o. For TriStore, we rst get the encoding number m of string p, and then we only need to output all the data of line m in Figure 1(c) (it can be observed that the line number of the table is equal to the encoding of the predicate). For example, we perform this SPARQL query(Select wheref?x rdf : type ?y:g). First nd the digital encoding of the predicate rdf : type, after nding that the encoding is 2, then directly output all the data in the second row of Figure 1(c). Therefore, after obtaining the encoding of string p, corresponding data can be quickly found with O(1) time complexity.
Figure 1(d) used to support fast matching of the second type of query, where s and p are known. What we want to get is o which is related to both s and p. For TriStore, the encoding m and n of string s and p should be obtained rst. As we can see from the running examples, line m in Figure 1(d) stores all PIDs and OIDs associated with the SID m (there are a mapping table that maps PIDs to OIDs). Hence, we only need to output all the data in the m-th line with the key n.
In order to maximize the e ciency of SPARQL queries in parallel environment,
we split Q into several subqueries with the same cost. We accept the machine
learning based method in [
Heuristic SPARQL Decomposition Using exhaustive method to decompose the SPARQL is less e cient. In this section, we present a heuristic query decomposition algorithm, which can e ciently split query into two subqueries with equal execution cost. We use degree(denoted as dn) to represent the number of SELECT ?prof ?stud WHERE { ?prof worksFor CS .
?stud advisor ?prof. } (a) SPARQL ?prof worksFor
CS advisor ?stud (b) Graph edges connected to node n in SPARQL graph. For example, in Figure2 (b), d?prof = 2; dCS = 1; d?stud = 1. It is easy to see that the nodes with higher degree are usually the center of SPARQL query graph (or regional center). Hence, we try to split the query from the nodes with higher degree. Note that, the query Q is decomposed only when the formula: maxfT (q1); T (q2)g < 0:8 T (Q) is satis ed. 0.8 is the value we obtained through experiments. Since a Q is decomposed into q1 and q2, an additional join operation must be performed. Next, we will try to decompose the subqueries q1 and q2 obtained in this round until the formula cannot be satis ed.
Joining Order There are three types of Join processing trees commonly used in databases: left-deep tree, right-deep tree and bushy tree. In order to improve e ciency as much as possible, and to use the parallel processing power of the computer. it is essential to use a strategy that can create bushy join trees (rather than focusing on left-deep or right-deep trees). 4
In the case of not processing the SPARQL query in parallel, we compare our engine with RDF3X in query e ciency. As can be seen from Figure 3, our engine is more e cient than RDF3X even without parallel acceleration. In Figure 4, we tested our engine in a parallel environment. We have found that our engine can indeed improve the e ciency of query execution in a parallel environment. 4 0 0 Mmoyre(M)B 23 00 00 1 0 0
RO Du rF A3 pX p r a o c h 33 05 00 00 2 5 0 0 iTem)sm( 112 500 000 000 5 0 0 0 1 2
Finally, we compare the memory usage of our storage model with
Hexastore [
In this paper, we design a highly parallel RDF engine for RDF by our designed RDF storage model, to take less memory and respond faster to queries in a highly parallel way.. We believe that our approach is helpful to maximize the performation of limited computing resources.
This work is supported by the National Key Research and Development Program of China (2017YFC0908401) and the National Natural Science Foundation of China (61972455,61672377). Xiaowang Zhang is supported by the Peiyang Young Scholars in Tianjin University (2019XRX-0032).