{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,19]],"date-time":"2025-11-19T06:26:10Z","timestamp":1763533570451,"version":"3.45.0"},"reference-count":34,"publisher":"Oxford University Press (OUP)","issue":"11","license":[{"start":{"date-parts":[[2025,5,19]],"date-time":"2025-05-19T00:00:00Z","timestamp":1747612800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/pages\/standard-publication-reuse-rights"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61972455"],"award-info":[{"award-number":["61972455"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025,11,13]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>As the core operator of regular path query (RPQ), the Kleene closure is essentially a recursive operation based on predicates. It has more expressive power than first-order logic, but its algorithmic complexity is an NP-hard problem and expensive to execute. Most approaches implement Kleene closure via online recursive queries (inefficient for large-scale data), yet significant reusable intermediate results emerge during execution. This paper proposes an efficient query optimization method based on offline preprocessing and tree-structured strategies to address the challenges of NP-hard complexity and low execution efficiency caused by the recursive nature of Kleene closure RPQs (KRPQs). The core contributions of this work include: (i) recursive index tree: by precomputing and materializing intermediate results of predicate paths offline, Kleene closure queries are transformed into non-recursive SPARQL queries. This allows direct retrieval of answer branches from the preconstructed index tree, eliminating redundant computations and reducing online complexity. (ii) Selectivity-driven dynamic optimization: a heuristic cost model estimates intermediate result sizes to guide query plan generation, minimizing redundant operations. (3) Query decomposition tree for nested KRPQs: a hierarchical decomposition algorithm processes nested Kleene closures layer-by-layer from inner to outer expressions, overcoming limitations of existing methods in handling complex nested structures. Experiments on large-scale RDF datasets demonstrate that the method reduces average response times by 50%\u201370% for single-predicate and expression-based Kleene closure queries compared to systems like Virtuoso, Jena, and KRPQ, with over 60% improvement for complex nested queries. Additionally, multithreaded preprocessing and path pool optimizations achieve up to a 76$\\times $ reduction in index construction time. Experiments show that the method can significantly reduce the time of KRPQs based on large RDF graphs.<\/jats:p>","DOI":"10.1093\/comjnl\/bxaf061","type":"journal-article","created":{"date-parts":[[2025,4,26]],"date-time":"2025-04-26T08:17:51Z","timestamp":1745655471000},"page":"1595-1609","source":"Crossref","is-referenced-by-count":0,"title":["Optimization of Kleene closure regular path query on large RDF graphs"],"prefix":"10.1093","volume":"68","author":[{"given":"Tenglong","family":"Ren","sequence":"first","affiliation":[{"name":"College of Intelligence and Computing , Tianjin University, No. 135, Ya Guan Road, Jinnan District, Tianjin,","place":["China"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaowang","family":"Zhang","sequence":"additional","affiliation":[{"name":"College of Intelligence and Computing , Tianjin University, No. 135, Ya Guan Road, Jinnan District, Tianjin,","place":["China"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhiyong","family":"Feng","sequence":"additional","affiliation":[{"name":"College of Intelligence and Computing , Tianjin University, No. 135, Ya Guan Road, Jinnan District, Tianjin,","place":["China"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2025,5,19]]},"reference":[{"key":"2025111901221123200_ref1","article-title":"SPARQL 1.1 query language","author":"Harris","year":"2013","journal-title":"Dent Rec"},{"key":"2025111901221123200_ref2","first-page":"1","article-title":"Foundations of modern query languages for graph databases","volume":"50","author":"Angles","year":"2017","journal-title":"ACM Trans Comput Surveys"},{"author":"World Wild Web Consortium (W3C)","key":"2025111901221123200_ref3"},{"key":"2025111901221123200_ref4","doi-asserted-by":"publisher","first-page":"1338","DOI":"10.1093\/bioinformatics\/btt765","article-title":"The EBI RDF platform: linked open data for the life sciences","volume":"30","author":"Jupp","year":"2014","journal-title":"Bioinformatics"},{"key":"2025111901221123200_ref5","first-page":"470","article-title":"TASWEET: optimizing disjunctive regular path queries in graph databases","volume-title":"Proeceedings of the International Conference on Extending Database Technology (EDBT)","author":"Abul-Basher","year":"2017"},{"key":"2025111901221123200_ref6","first-page":"219","article-title":"PDD graph: bridging electronic medical records and biomedical knowledge graphs via entity linking","volume-title":"Proceedings of the International Semantic Web Conference (ISWC)","author":"Wang","year":"2017"},{"key":"2025111901221123200_ref7","doi-asserted-by":"publisher","first-page":"1151","DOI":"10.1007\/s11280-015-0377-6","article-title":"Bottleneck-aware arrangement over event-based social networks: the max-min approach","volume":"19","author":"Tong","year":"2016","journal-title":"World Wide Web J"},{"key":"2025111901221123200_ref8","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1007\/s10472-013-9346-x","article-title":"The impact of transitive closure on the expressiveness of navigational query languages on unlabeled graphs","volume":"73","author":"George","year":"2015","journal-title":"Ann Math Artif Intell"},{"key":"2025111901221123200_ref9","first-page":"110","article-title":"Universality of data retrieval languages","volume-title":"Proceedings of the ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (POPL)","author":"Alfred","year":"1979"},{"key":"2025111901221123200_ref10","doi-asserted-by":"publisher","first-page":"655","DOI":"10.1007\/s00778-019-00558-9","article-title":"An analytical study of large SPARQL query logs","volume":"29","author":"Bonifati","year":"2020","journal-title":"VLDB J"},{"key":"2025111901221123200_ref11","doi-asserted-by":"publisher","first-page":"1235","DOI":"10.1137\/S009753979122370X","article-title":"Finding regular simple paths in graph databases","volume":"24","author":"Mendelzon","year":"1995","journal-title":"SIAM J Comput"},{"key":"2025111901221123200_ref12","doi-asserted-by":"publisher","first-page":"993","DOI":"10.1007\/s10115-020-01536-2","article-title":"Distributed processing of regular path queries in RDF graphs","volume":"63","author":"Guo","year":"2013","journal-title":"Knowl Inform Syst"},{"key":"2025111901221123200_ref13","first-page":"99","article-title":"Path indexing in the cypher query pipeline","volume-title":"Proceedings of the International Conference on Extending Database Technology (EDBT)","author":"Kuijpers","year":"2021"},{"key":"2025111901221123200_ref14","first-page":"101","article-title":"The complexity of evaluating path expressions in SPARQL","volume-title":"Proceedings of the ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (POPL)","author":"Losemann","year":"2013"},{"key":"2025111901221123200_ref15","first-page":"681","article-title":"On the optimization of recursive relational queries: application to graph queries","volume-title":"Proceedings of the International Conference on Management of Data (SIGMOD)","author":"Jachiet","year":"2020"},{"key":"2025111901221123200_ref16","first-page":"211","article-title":"On implementing provenance-aware regular path queries with relational query engines","volume-title":"Proceedings of the International Conference on Extending Database Technology and International Conference on Database Theory (EDBT\/ICDT)","author":"Dey","year":"2013"},{"key":"2025111901221123200_ref17","first-page":"53","article-title":"Path queries on semi-structured data","volume":"52","author":"Gyssens","year":"1996","journal-title":"J Comput Syst Sci"},{"key":"2025111901221123200_ref18","first-page":"63","article-title":"Regular path queries with constraints: a foundational framework","volume":"256","author":"Calvanese","year":"2000","journal-title":"Theor Comput Sci"},{"key":"2025111901221123200_ref19","first-page":"636","article-title":"Efficient regular path query evaluation using path indexes","volume-title":"Proceedings of the International Conference on Extending Database Technology (EDBT)","author":"Fletcher","year":"2016"},{"key":"2025111901221123200_ref20","first-page":"1","article-title":"An analysis of the feasibility of graph compression techniques for indexing regular path queries","volume-title":"Proceedings of the International Workshop on Graph Data-management Experiences Systems (GRADES)","author":"Letzel","year":"2017"},{"key":"2025111901221123200_ref21","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1145\/2484425.2484443","article-title":"SPARQling Kleene: fast property paths in RDF-3X","volume-title":"Proceedings of the International Workshop on Graph Data Management Experiences and Systems (GRADES)","author":"Gubichev","year":"2013"},{"key":"2025111901221123200_ref22","first-page":"13589","article-title":"Efficient regular path queries via matrix factorization","volume-title":"Proceedings of the Conference on Artificial Intelligence (AAAI)","author":"Zhang","year":"2023"},{"key":"2025111901221123200_ref23","first-page":"1234","article-title":"Reachability prediction for RDF graphs using graph neural networks","volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB)","author":"Wang","year":"2024"},{"key":"2025111901221123200_ref24","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1007\/978-3-642-31235-9_12","article-title":"Regular path queries on large graphs","volume-title":"Proceedings of the International Workshop on Statistical and Scientific Database Management (SSDBM)","author":"Koschmieder","year":"2012"},{"key":"2025111901221123200_ref25","doi-asserted-by":"publisher","first-page":"661","DOI":"10.1007\/s11280-022-01103-5","article-title":"FPIRPQ: accelerating regular path queries on knowledge graphs","volume":"26","author":"Xin","year":"2023","journal-title":"World Wide Web J"},{"key":"2025111901221123200_ref26","first-page":"74","article-title":"Jena: implementing the semantic web recommendations","volume-title":"Proceedings of the International World Wide Web Conference (WWW)","author":"Carroll","year":"2004"},{"key":"2025111901221123200_ref27","first-page":"3","article-title":"Virtuoso, a hybrid RDBMS\/graph column store","volume":"35","author":"Erling","year":"2012","journal-title":"IEEE Data Eng Bull"},{"key":"2025111901221123200_ref28","doi-asserted-by":"publisher","first-page":"1465","DOI":"10.1007\/s11280-019-00739-0","article-title":"Distributed pregel-based provenance aware regular path query processing on RDF knowledge graphs","volume":"23","author":"Wang","year":"2020","journal-title":"World Wide Web J"},{"key":"2025111901221123200_ref29","first-page":"67","article-title":"A reachability index for recursive label-concatenated graph queries","volume-title":"Proceedings of the International Conference on Data Engineering (ICDE)","author":"Zhang","year":"2022"},{"key":"2025111901221123200_ref30","doi-asserted-by":"publisher","first-page":"632","DOI":"10.1007\/978-3-319-46523-4_38","article-title":"Context-free path queries on RDF graphs","volume-title":"Proceedings of the International Semantic Web Conference (ISWC)","author":"Zhang","year":"2016"},{"key":"2025111901221123200_ref31","first-page":"123","article-title":"Regular path query evaluation sharing a reduced transitive closure based on graph reduction","volume":"34","author":"Wang","year":"2023","journal-title":"J Database Manage"},{"key":"2025111901221123200_ref32","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1016\/0020-0190(94)90128-7","article-title":"An efficient transitive closure algorithm for cyclic digraphs","volume":"52","author":"Nuutila","year":"1994","journal-title":"Inform Process Lett J"},{"key":"2025111901221123200_ref33","doi-asserted-by":"publisher","first-page":"475","DOI":"10.1007\/978-3-030-21348-0_31","article-title":"BeSEPPI: semantic-based benchmarking of property path implementations","volume-title":"Proceedings of the Extended Semantic Web Conference (ESWC)","author":"Skubella","year":"2019"},{"key":"2025111901221123200_ref34","first-page":"722","article-title":"DBpedia: a nucleus for a web of open data","volume-title":"Proceedings of the International Semantic Web Conference and Asian Semantic Web Conference (ISWC\/ASWC)","author":"Auer","year":"2007"}],"container-title":["The Computer Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/68\/11\/1595\/63237356\/bxaf061.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/68\/11\/1595\/63237356\/bxaf061.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,19]],"date-time":"2025-11-19T06:22:23Z","timestamp":1763533343000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comjnl\/article\/68\/11\/1595\/8137937"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5,19]]},"references-count":34,"journal-issue":{"issue":"11","published-online":{"date-parts":[[2025,5,19]]},"published-print":{"date-parts":[[2025,11,13]]}},"URL":"https:\/\/doi.org\/10.1093\/comjnl\/bxaf061","relation":{},"ISSN":["0010-4620","1460-2067"],"issn-type":[{"type":"print","value":"0010-4620"},{"type":"electronic","value":"1460-2067"}],"subject":[],"published-other":{"date-parts":[[2025,11]]},"published":{"date-parts":[[2025,5,19]]}}}