{"ID":2830470,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.11129","arxiv_id":"2512.11129","title":"Acyclic Conjunctive Regular Path Queries are no Harder than Corresponding Conjunctive Queries","abstract":"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.","short_abstract":"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...","url_abs":"https://arxiv.org/abs/2512.11129","url_pdf":"https://arxiv.org/pdf/2512.11129v2","authors":"[\"Mahmoud Abo Khamis\",\"Alexandru-Mihai Hurjui\",\"Ahmet Kara\",\"Dan Olteanu\",\"Dan Suciu\"]","published":"2025-12-11T21:25:15Z","proceeding":"cs.DB","tasks":"[\"cs.DB\"]","methods":"[]","has_code":false}