{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,24]],"date-time":"2025-08-24T01:40:38Z","timestamp":1755999638672,"version":"3.41.0"},"reference-count":55,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2022,5,23]],"date-time":"2022-05-23T00:00:00Z","timestamp":1653264000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001659","name":"German Research Foundation","doi-asserted-by":"crossref","award":["416776735"],"award-info":[{"award-number":["416776735"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2022,6,30]]},"abstract":"<jats:p>In practice, regular expressions are usually extended by so-called capture groups or capture variables, which allow to capture a subexpression by a variable that can be referenced in the regular expression in order to describe repetitions of subwords. We investigate how this concept could be used for pattern-based graph querying; i.e., we investigate conjunctive regular path queries (CRPQs) that are extended by capture variables.<\/jats:p>\n          <jats:p>If capture variables are added to CRPQs in a completely unrestricted way, then Boolean evaluation becomes PSPACE-hard in data complexity, even for single-edge graph patterns. On the other hand, if capture variables do not occur under a Kleene star, then the data complexity drops to NL-completeness. Combined complexity is in EXPSPACE but drops to PSPACE-completeness if the depth (i.e., the nesting depth of capture variables) is bounded, and it drops to NP-completeness if the size of the images of capture variables is bounded by a constant (regardless of the depth or of whether capture variables occur under a Kleene star).<\/jats:p>\n          <jats:p>In the application of regular expressions as string searching tools, references to capture variables only describe exact repetitions of subwords (i.e., they implement the equality relation on strings). Following recent developments in graph database research, we also study CRPQs with capture variables that describe arbitrary regular relations. We show that if the expressions have depth 0, or if the size of the images of capture variables is bounded by a constant, then we can allow arbitrary regular relations while staying in the same complexity bounds. We also investigate the problems of checking whether a given tuple is in the solution set and computing the whole solution set.<\/jats:p>\n          <jats:p>On the conceptual side, we add capture variables to CRPQs in such a way that they can be defined in an expression on one arc of the graph pattern but also referenced in expressions on other arcs. Hence, they add to CRPQs the possibility to define inter-dependencies between different paths, which is a relevant feature of pattern-based graph querying.<\/jats:p>","DOI":"10.1145\/3514230","type":"journal-article","created":{"date-parts":[[2022,2,23]],"date-time":"2022-02-23T21:50:46Z","timestamp":1645653046000},"page":"1-52","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Conjunctive Regular Path Queries with Capture Groups"],"prefix":"10.1145","volume":"47","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5137-1504","authenticated-orcid":false,"given":"Markus L.","family":"Schmid","sequence":"first","affiliation":[{"name":"Humboldt-Universit\u00e4t zu Berlin, Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,5,23]]},"reference":[{"issue":"5","key":"e_1_3_3_2_2","first-page":"68:1\u201368:40","article-title":"Foundations of modern query languages for graph databases","volume":"50","author":"Angles Renzo","year":"2017","unstructured":"Renzo Angles, Marcelo Arenas, Pablo Barcel\u00f3, Aidan Hogan, Juan L. Reutter, and Domagoj Vrgoc. 2017. Foundations of modern query languages for graph databases. ACM Comput. Surv. 50, 5 (2017), 68:1\u201368:40.","journal-title":"ACM Comput. Surv."},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-77525-8_75"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/2463664.2467795"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2017\/110"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/2463664.2465216"},{"key":"e_1_3_3_7_2","first-page":"104:1\u2013104:15","volume-title":"46th International Colloquium on Automata, Languages, and Programming (ICALP\u201919)","author":"Barcel\u00f3 Pablo","year":"2019","unstructured":"Pablo Barcel\u00f3, Diego Figueira, and Miguel Romero. 2019. Boundedness of conjunctive regular path queries. In 46th International Colloquium on Automata, Languages, and Programming (ICALP\u201919). 104:1\u2013104:15."},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/2389241.2389250"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/2559905"},{"issue":"2","key":"e_1_3_3_10_2","first-page":"10:1\u201310:41","article-title":"Graph logics with rational relations: The role of word combinatorics","volume":"18","author":"Barcel\u00f3 Pablo","year":"2017","unstructured":"Pablo Barcel\u00f3 and Pablo Mu\u00f1oz. 2017. Graph logics with rational relations: The role of word combinatorics. ACM Trans. Comput. Log. (TOCL) 18, 2 (2017), 10:1\u201310:41.","journal-title":"ACM Trans. Comput. Log. (TOCL)"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1137\/15M1034714"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1613\/jair.4577"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-45276-0_1"},{"issue":"2","key":"e_1_3_3_14_2","first-page":"149","article-title":"An analytical study of large SPARQL query logs","volume":"11","author":"Bonifati Angela","year":"2017","unstructured":"Angela Bonifati, Wim Martens, and Thomas Timm. 2017. An analytical study of large SPARQL query logs. PVLDB 11, 2 (2017), 149\u2013161.","journal-title":"PVLDB"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00558-9"},{"key":"e_1_3_3_16_2","first-page":"176","volume-title":"Principles of Knowledge Representation and Reasoning Proceedings of the 7th International Conference (KR\u201900).","author":"Calvanese Diego","year":"2000","unstructured":"Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, and Moshe Y. Vardi. 2000. Containment of conjunctive regular path queries with inverse. In Principles of Knowledge Representation and Reasoning Proceedings of the 7th International Conference (KR\u201900).176\u2013185."},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/959060.959076"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1142\/S012905410300214X"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00982-2_24"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICDT.2021.19"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/298514.298591"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/38713.38749"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/3180281"},{"key":"e_1_3_3_24_2","first-page":"21","volume-title":"Database Programming Languages, 8th International Workshop (DBPL\u201901), Revised Papers","author":"Deutsch Alin","year":"2001","unstructured":"Alin Deutsch and Val Tannen. 2001. Optimization properties for classes of conjunctive regular path queries. In Database Programming Languages, 8th International Workshop (DBPL\u201901), Revised Papers. 21\u201339."},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/3294052.3319684"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2015.03.006"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICDT.2020.9"},{"key":"e_1_3_3_28_2","article-title":"Containment of simple regular path queries","volume":"2003","author":"Figueira Diego","year":"2020","unstructured":"Diego Figueira, Adwait Godbole, Shankara Narayanan Krishna, Wim Martens, Matthias Niewerth, and Tina Trautner. 2020. Containment of simple regular path queries. CoRR abs\/2003.04411 (2020). arxiv:2003.04411https:\/\/arxiv.org\/abs\/2003.04411.","journal-title":"CoRR"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/275487.275503"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-012-9389-0"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-018-9874-1"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196967"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2019.04.001"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2013.01.008"},{"key":"e_1_3_3_35_2","volume-title":"Mastering Regular Expressions - Understand Your Data and Be More Productive: For Perl, PHP, Java, .NET, Ruby, and More","author":"Friedl Jeffrey E. F.","year":"2006","unstructured":"Jeffrey E. F. Friedl. 2006. Mastering Regular Expressions - Understand Your Data and Be More Productive: For Perl, PHP, Java, .NET, Ruby, and More (3rd ed.). O\u2019Reilly."},{"key":"e_1_3_3_36_2","first-page":"15:1\u201315:18","volume-title":"22nd International Conference on Database Theory (ICDT\u201919)","author":"Gluch Grzegorz","year":"2019","unstructured":"Grzegorz Gluch, Jerzy Marcinkowski, and Piotr Ostropolski-Nalewaja. 2019. The first order truth behind undecidability of regular path queries determinacy. In 22nd International Conference on Database Theory (ICDT\u201919). 15:1\u201315:18."},{"key":"e_1_3_3_37_2","volume-title":"SPARQL 1.1 Query Language. W3C Recommendation","author":"Harris Steve","year":"2013","unstructured":"Steve Harris and Andy Seaborne. 2013. SPARQL 1.1 Query Language. W3C Recommendation. Technical Reporthttps:\/\/www.w3.org\/TR\/sparql11-query\/. W3C."},{"key":"e_1_3_3_38_2","series-title":"Annals of Mathematics Studies","first-page":"3","volume-title":"Automata Studies","author":"Kleene S. C.","year":"1956","unstructured":"S. C. Kleene. 1956. Representation of events in nerve nets and finite automata. In Automata Studies, C. E. Shannon and J. McCarthy (Eds.). Annals of Mathematics Studies, Vol. 34. Princeton University Press, 3\u201341."},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2017.09.005"},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/2850413"},{"key":"e_1_3_3_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/2494529"},{"key":"e_1_3_3_42_2","volume-title":"37th Symposium on Theoretical Aspects of Computer Science (STACS\u201920)","author":"Martens Wim","year":"2020","unstructured":"Wim Martens, Matthias Niewerth, and Tina Trautner. 2020. A trichotomy for regular trail queries. In 37th Symposium on Theoretical Aspects of Computer Science (STACS\u201920). Accepted for publication."},{"key":"e_1_3_3_43_2","first-page":"19:1\u201319:21","volume-title":"21st International Conference on Database Theory (ICDT\u201918)","author":"Martens Wim","year":"2018","unstructured":"Wim Martens and Tina Trautner. 2018. Evaluation and enumeration problems for regular path queries. In 21st International Conference on Database Theory (ICDT\u201918). 19:1\u201319:21."},{"key":"e_1_3_3_44_2","doi-asserted-by":"publisher","DOI":"10.1145\/3371316.3371319"},{"key":"e_1_3_3_45_2","doi-asserted-by":"publisher","DOI":"10.1145\/3331446"},{"key":"e_1_3_3_46_2","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979122370X"},{"key":"e_1_3_3_47_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-016-9676-2"},{"key":"e_1_3_3_48_2","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2017.8005106"},{"key":"e_1_3_3_49_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2016.02.003"},{"key":"e_1_3_3_50_2","doi-asserted-by":"publisher","DOI":"10.1145\/3375395.3387663"},{"key":"e_1_3_3_51_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICDT.2021.4"},{"key":"e_1_3_3_52_2","doi-asserted-by":"publisher","DOI":"10.1145\/3452021.3458325"},{"key":"e_1_3_3_53_2","article-title":"The Neo4j cypher manual v3.5","author":"Team The Neo4j","year":"2016","unstructured":"The Neo4j Team. 2016. The Neo4j cypher manual v3.5. Retrieved from https:\/\/neo4j.com\/docs\/developer-manual\/current\/cypher\/.","journal-title":"Retrieved from https:\/\/neo4j.com\/docs\/developer-manual\/current\/cypher\/"},{"key":"e_1_3_3_54_2","doi-asserted-by":"publisher","DOI":"10.1145\/363347.363387"},{"key":"e_1_3_3_55_2","article-title":"Gremlin language","year":"2013","unstructured":"Apache TinkerPop\u2122. 2013. Gremlin language. Retrieved from https:\/\/tinkerpop.apache.org\/gremlin.html.","journal-title":"Retrieved from https:\/\/tinkerpop.apache.org\/gremlin.html"},{"key":"e_1_3_3_56_2","doi-asserted-by":"publisher","DOI":"10.1145\/2206869.2206879"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3514230","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3514230","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:10:14Z","timestamp":1750183814000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3514230"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,23]]},"references-count":55,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,6,30]]}},"alternative-id":["10.1145\/3514230"],"URL":"https:\/\/doi.org\/10.1145\/3514230","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2022,5,23]]},"assertion":[{"value":"2020-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-05-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}