(RPQ) consisting of Kleene closure (∗) is the most complex and dificult to handle due to the infinite recursion of Kleene closure. The infinite recursive process of Kleene closure can be preprocessed. However, the current optimization methods are less concerned with reducing query time through preprocessing. In this paper, we propose Node Clustered Index (NCI), and generating NCI in the preprocessing can solve the reachability problem on graphs. Moreover, we design a Kleene closure pattern tree decomposition algorithm, which combines with selective design to generate locally optimal query plans. Experimental results show that NCI can largely optimize Kleene closure regular path queries, and the RDF data sizes have little impact on query eficiency.
p1 … pn RDF p1 1 p1 p1 4 2
Key (predicate)
(subject, object) 3 p1 Node Clustered Index Generation
Algorithm …
5
Node Clustered Index p1 pn 6 null p1 HDFS . … – We propose a new type of node clustered index (NCI). The NCI is built in the data preprocessing, mainly to store the results of queries with Kleene closure in the form of clusters. – We design a regular expression decomposition algorithm, which can decompose complex regular expressions into ternary trees in units of Kleene closure. – We propose a selective design to optimize the query execution.
(p1/(p4/p2)*/p3)* p1/(p4/p2)*/p3 p4/p2 1 2 Kleene Closure Pattern Tree Decomposition Algorithm null p3 p1 pn 4
Query Executor 3 p1/(p4/p2)*/p3 p1 p4/p2
p3 ⋈ ⋈ Selective Design 5
2. Query Optimization 2.1. Node Clustered Index The NCI is a data storage method, and the specific details depend on its implementation. In short, the NCI can cluster the query results of the predicate (or expression) consisting of the Kleene closure. Algorithm 1 demonstrates the NCI generation process.
Taking the predicate as an example, the specific process of the NCI generation algorithm is as follows: 1. Get the subject-object table (value) of the current predicate (key) based on key-value storage. 2. Get the starting point table and the ending point table of the node cluster, where the starting points refer to the subject that does not appear in the object column, and the ending points refer to the object that does not appear in the subject column. 3. Traverse the starting point table to get the object corresponding to the current starting point (subject), take this object as the connection point, and carry out the self-join of the subject-object table until the object exists in the ending point table. Save all objects, and we can get the NCI with this starting point as the core. 4. Repeat step 3 until the starting points are traversed.
The result of the predicate consisting of Kleene closure can be aggregated data (the set of nodes on the path) through Algorithm 1. When we query ( )∗ , the system returns the set of results directly. 2.2. Query Plan Generation The query executor optimizes queries by parsing the pattern tree of the Kleene Closure Pattern Tree Generation Algorithm combined with the Selective Design to generate the query plan from the bottom up. 2.2.1. Kleene Closure Pattern Tree Decomposition Algorithm If the complex(nested) Kleene closure query is directly queried as a whole, it will undoubtedly cost much time due to the infinite recursion of Kleene closure. Therefore, we propose a unique Kleene closure pattern tree decomposition algorithm.
The basic idea is to decompose the expression consisting of Kleene closure as a unit and decompose three leaf nodes: , , and , as shown in the Query Parser section of Fig. 1. The refers to the string modified by the current Kleene closure, the refers to the string before the current Kleene closure unit, and the refers to the string located after the current Kleene closure unit. The algorithm is a recursive process until there is no expression consisting of Kleene closure in the leaf nodes. Finally, we can get a complete pattern tree. 3. Experiment and Evaluation We ran experiments on Intel (R) Xeon (R) CPU E5-4607 v2@2.60GHz, 4 cores, and 62 GB RAM. We used the dataset (LUBM1) to compare the SPARQL query system (JENA, Blazegraph, Virtuoso) on the query set2 (covering various types3 of Kleene closures). Also, to evaluate the system’s scalability, we compared it with diferent data sizes (10, 100, 200) of LUBM. The query results are shown in Fig. 2, and our proposed system is NCI_RPQ.
!"#$%& !"#$%&& !"#$'&& "" "! * ) ( ' & % $ # " ! ## #! ") "' "% "# "! ) ' % # ! && &! %& %! $& $! #& #! "& "! & !
The experimental results show that the eficiency of NCI_RPQ is less afected by the data sizes, especially compared with Jena, and the average query eficiency of NCI_RPQ is increased by at least 8.2 times when querying Q2-Q6, which is all due to NCI. In addition, compared to all other systems, the NCI_RPQ can handle various types of Kleene closure regular path queries due to the decomposition algorithm’s strong applicability.
Our methods solve the problem of infinite recursion of Kleene closure in RPQ, and has great scientific research value. However, our work is still inadequate, and further optimization of NCI storage space and selective design based on deep learning are subsequently considered. [1] Arroyuelo D , Hogan A , Navarro G , et al. Time- and Space-Eficient Regular Path Queries on Graphs[J]. 2021. [2] Fan Feng, Optimization of Kleene Closure Regular Path Query Based on Tree Structure[Master Thesis], Tianjin University, 2022. [3] Yakovets N , Godfrey P , Gryz J . Query Planning for Evaluating SPARQL Property Paths[C]//
International Conference on Management of Data. ACM, 2016. 1http://swat.cse.lehigh.edu/projects/lubm 2https://github.com/luer9/RPQ_QUERY/blob/main/RPQ_QUERY.md 3Four types: general (Q1), single predicate (Q2, Q3), expression (Q4, Q5, Q6), complex (Q7, Q8, Q9).