{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T13:13:01Z","timestamp":1778764381258,"version":"3.51.4"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T00:00:00Z","timestamp":1778716800000},"content-version":"vor","delay-in-days":2,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["IIS 2314527"],"award-info":[{"award-number":["IIS 2314527"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["SHF 2312195"],"award-info":[{"award-number":["SHF 2312195"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["III 2507117"],"award-info":[{"award-number":["III 2507117"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Microsoft","award":["Microsoft professorship"],"award-info":[{"award-number":["Microsoft professorship"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2026,5,12]]},"abstract":"<jats:p>We present an output-sensitive algorithm for evaluating an acyclic Conjunctive Regular Path Query (CRPQ). Its complexity is written in terms of the input size, the output size, and a well-known parameter of the query that is called the ''free-connex fractional hypertree width''. Our algorithm improves upon the complexity of the recently introduced output-sensitive algorithm for acyclic CRPQs. More notably, the complexity of our algorithm for a given acyclic CRPQ Q matches the best known output-sensitive complexity for the ''corresponding'' conjunctive query (CQ), that is the CQ that has the same structure as the CRPQ Q except that each RPQ is replaced with a binary atom (or a join of two binary atoms). This implies that it is not possible to improve upon our complexity for acyclic CRPQs without improving the state-of-the-art on output-sensitive evaluation for acyclic CQs. Our result is surprising because RPQs, and by extension CRPQs, are equivalent to recursive Datalog programs, which are generally poorly understood from a complexity standpoint. Yet, our result implies that the recursion aspect of acyclic CRPQs does not add any extra complexity on top of the corresponding (non-recursive) CQs, at least as far as output-sensitive analysis is concerned.<\/jats:p>","DOI":"10.1145\/3801891","type":"journal-article","created":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T12:50:22Z","timestamp":1778763022000},"page":"1-24","source":"Crossref","is-referenced-by-count":0,"title":["Acyclic Conjunctive Regular Path Queries are no Harder than Corresponding Conjunctive Queries"],"prefix":"10.1145","volume":"4","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3894-6494","authenticated-orcid":false,"given":"Mahmoud","family":"Abo Khamis","sequence":"first","affiliation":[{"name":"RelationalAI, Berkeley, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-2799-4694","authenticated-orcid":false,"given":"Alexandru-Mihai","family":"Hurjui","sequence":"additional","affiliation":[{"name":"University of Zurich, Zurich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8155-8070","authenticated-orcid":false,"given":"Ahmet","family":"Kara","sequence":"additional","affiliation":[{"name":"OTH Regensburg, Regensburg, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4682-7068","authenticated-orcid":false,"given":"Dan","family":"Olteanu","sequence":"additional","affiliation":[{"name":"University of Zurich, Zurich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4144-0868","authenticated-orcid":false,"given":"Dan","family":"Suciu","sequence":"additional","affiliation":[{"name":"University of Washington, Seattle, WA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,5,14]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 4670-4703","author":"Abboud Amir","year":"2024","unstructured":"Amir Abboud, Karl Bringmann, Nick Fischer, and Marvin K\u00fcnnemann. 2024. The Time Complexity of Fully Sparse Matrix Multiplication. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 4670-4703."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3426865"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3725235"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2509.20204"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3725242"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902280"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.46298\/theoretics.25.12"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/210332.210337"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1514894.1514909"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463664.2465216"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74915-8_18"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-43948-7_19"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/3149193.3149196"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3308558.3313472"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.46298\/LMCS-19(4:15)2023"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICDT.2023.13"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380607"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3695838"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.24963\/KR.2020\/38"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3725237"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3190657"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265535"},{"key":"e_1_2_1_23_1","unstructured":"Steve Harris and Andy Seaborne. 2013. SPARQL 1.1 Query Language. W3C Recommendation. http:\/\/www.w3.org\/TR\/sparql11-query\/."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3725241"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-00668-6_23"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICDT.2018.19"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3371316.3371319"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979122370X"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","unstructured":"Hung Q. Ngo. 2018. Worst-Case Optimal Join Algorithms: Techniques Results and Open Problems. In PODS. 111\u2013124. doi:10.1145\/3196959.3196990","DOI":"10.1145\/3196959.3196990"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213565"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2590989.2590991"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2656335"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2448496.2448498"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02165411"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5441\/002\/ICDT.2014.13"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","unstructured":"Virginia Vassilevska Williams Yinzhan Xu Zixuan Xu and Renfei Zhou. [n.d.]. New Bounds for Matrix Multiplication: from Alpha to Omega. 3792-3835. arXiv:https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/1.9781611977912.134 doi:10.1137\/1.9781611977912.134","DOI":"10.1137\/1.9781611977912.134"},{"key":"e_1_2_1_37_1","first-page":"82","article-title":"Algorithms for Acyclic Database Schemes","author":"Yannakakis Mihalis","year":"1981","unstructured":"Mihalis Yannakakis. 1981. Algorithms for Acyclic Database Schemes. In VLDB. 82-94.","journal-title":"VLDB."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3801891","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3801891","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T12:52:11Z","timestamp":1778763131000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3801891"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,12]]},"references-count":37,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,5,12]]}},"alternative-id":["10.1145\/3801891"],"URL":"https:\/\/doi.org\/10.1145\/3801891","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5,12]]}}}