{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:11:29Z","timestamp":1779174689482,"version":"3.51.4"},"reference-count":58,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2019,10,15]],"date-time":"2019-10-15T00:00:00Z","timestamp":1571097600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["4938\/4-1"],"award-info":[{"award-number":["4938\/4-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2019,12,31]]},"abstract":"<jats:p>Regular path queries (RPQs) are a central component of graph databases. We investigate decision and enumeration problems concerning the evaluation of RPQs under several semantics that have recently been considered: arbitrary paths, shortest paths, paths without node repetitions (simple paths), and paths without edge repetitions (trails).<\/jats:p>\n          <jats:p>\n            Whereas arbitrary and shortest paths can be dealt with efficiently, simple paths and trails become computationally difficult already for very small RPQs. We study RPQ evaluation for simple paths and trails from a parameterized complexity perspective and define a class of\n            <jats:italic>simple transitive expressions<\/jats:italic>\n            that is prominent in practice and for which we can prove dichotomies for the evaluation problem. We observe that, even though simple path and trail semantics are intractable for RPQs in general, they are feasible for the vast majority of RPQs that are used in practice. At the heart of this study is a result of independent interest: the two disjoint paths problem in directed graphs is W[1]-hard if parameterized by the length of one of the two paths.\n          <\/jats:p>","DOI":"10.1145\/3331446","type":"journal-article","created":{"date-parts":[[2019,10,15]],"date-time":"2019-10-15T16:35:58Z","timestamp":1571157358000},"page":"1-46","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["Dichotomies for Evaluating Simple Regular Path Queries"],"prefix":"10.1145","volume":"44","author":[{"given":"Wim","family":"Martens","sequence":"first","affiliation":[{"name":"University of Bayreuth, Bayreuth, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tina","family":"Trautner","sequence":"additional","affiliation":[{"name":"University of Bayreuth, Bayreuth, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,10,15]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.03.018"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/210332.210337"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3190654"},{"key":"e_1_2_2_4_1","volume-title":"Foundations of modern query languages for graph databases. Comput. Surveys 50, 5","author":"Angles Renzo","year":"2017","unstructured":"Renzo Angles , Marcelo Arenas , Pablo Barcel\u00f3 , Aidan Hogan , Juan L. Reutter , and Domagoj Vrgo\u010d . 2017. Foundations of modern query languages for graph databases. Comput. Surveys 50, 5 ( 2017 ), 68:1--68:40. Renzo Angles, Marcelo Arenas, Pablo Barcel\u00f3, Aidan Hogan, Juan L. Reutter, and Domagoj Vrgo\u010d. 2017. Foundations of modern query languages for graph databases. Comput. Surveys 50, 5 (2017), 68:1--68:40."},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2187836.2187922"},{"key":"e_1_2_2_6_1","volume-title":"A trichotomy for regular simple path queries on graphs. CoRR abs\/1212.6857","author":"Bagan Guillaume","year":"2012","unstructured":"Guillaume Bagan , Angela Bonifati , and Beno\u00eet Groz . 2012. A trichotomy for regular simple path queries on graphs. CoRR abs\/1212.6857 ( 2012 ). http:\/\/arxiv.org\/abs\/1212.6857. Guillaume Bagan, Angela Bonifati, and Beno\u00eet Groz. 2012. A trichotomy for regular simple path queries on graphs. CoRR abs\/1212.6857 (2012). http:\/\/arxiv.org\/abs\/1212.6857."},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463664.2467795"},{"key":"e_1_2_2_8_1","volume-title":"Symposium on Principles of Database Systems (PODS). 175--188","author":"Barcel\u00f3 Pablo","year":"2013","unstructured":"Pablo Barcel\u00f3 . 2013 . Querying graph databases . In Symposium on Principles of Database Systems (PODS). 175--188 . Pablo Barcel\u00f3. 2013. Querying graph databases. In Symposium on Principles of Database Systems (PODS). 175--188."},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060745.1060848"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1017074.1017095"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1735886.1735890"},{"key":"e_1_2_2_12_1","volume-title":"International Conference on Very Large Data Bases. 998--1009","author":"Bex Geert Jan","year":"2007","unstructured":"Geert Jan Bex , Frank Neven , and Stijn Vansummeren . 2007 . Inferring XML schema definitions from XML data (VLDB) . In International Conference on Very Large Data Bases. 998--1009 . Geert Jan Bex, Frank Neven, and Stijn Vansummeren. 2007. Inferring XML schema definitions from XML data (VLDB). In International Conference on Very Large Data Bases. 998--1009."},{"key":"e_1_2_2_13_1","doi-asserted-by":"crossref","unstructured":"Andreas Bj\u00f6rklund Thore Husfeldt and Sanjeev Khanna. 2004. Approximating longest directed paths and cycles. In International Colloquium on Automata Languages and Programming (ICALP). 222--233.  Andreas Bj\u00f6rklund Thore Husfeldt and Sanjeev Khanna. 2004. Approximating longest directed paths and cycles. In International Colloquium on Automata Languages and Programming (ICALP). 222--233.","DOI":"10.1007\/978-3-540-27836-8_21"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3308558.3313472"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/3167892.3167895"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/321239.321249"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53536-3_6"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2007.21"},{"key":"e_1_2_2_19_1","volume-title":"Symposium on Principles of Database Systems (PODS). 404--416","author":"Mariano","unstructured":"Mariano P. Consens and Alberto O. Mendelzon. 1990. GraphLog: A visual formalism for real life recursion . In Symposium on Principles of Database Systems (PODS). 404--416 . Mariano P. Consens and Alberto O. Mendelzon. 1990. GraphLog: A visual formalism for real life recursion. In Symposium on Principles of Database Systems (PODS). 404--416."},{"key":"e_1_2_2_20_1","volume-title":"ACM SIGMOD International Conference on Management of Data (SIGMOD). 323--330","author":"Cruz Isabel F.","unstructured":"Isabel F. Cruz , Alberto O. Mendelzon , and Peter T. Wood . 1987. A graphical query language supporting recursion . In ACM SIGMOD International Conference on Management of Data (SIGMOD). 323--330 . Isabel F. Cruz, Alberto O. Mendelzon, and Peter T. Wood. 1987. A graphical query language supporting recursion. In ACM SIGMOD International Conference on Management of Data (SIGMOD). 323--330."},{"key":"e_1_2_2_21_1","volume-title":"Parameterized Algorithms","author":"Cygan Marek","unstructured":"Marek Cygan , Fedor V. Fomin , Lukasz Kowalik , Daniel Lokshtanov , Daniel Marx , Marcin Pilipczuk , Michal Pilipczuk , and Saket Saurabh . 2015. Parameterized Algorithms . Springer . Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. 2015. Parameterized Algorithms. Springer."},{"key":"e_1_2_2_22_1","unstructured":"Holger Dell. 2017. Personal communication.  Holger Dell. 2017. Personal communication."},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792228228"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)00097-3"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703427203"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2886094"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(80)90009-2"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/3402707.3402739"},{"key":"e_1_2_2_29_1","doi-asserted-by":"crossref","unstructured":"Martin Grohe and Magdalena Gr\u00fcber. 2007. Parameterized approximability of the disjoint cycle problem. In International Colloquium on Automata Languages and Programming (ICALP). 363--374.  Martin Grohe and Magdalena Gr\u00fcber. 2007. Parameterized approximability of the disjoint cycle problem. In International Colloquium on Automata Languages and Programming (ICALP). 363--374.","DOI":"10.1007\/978-3-540-73420-8_33"},{"key":"e_1_2_2_30_1","volume-title":"International Conference on Extending Database Technology (EDBT). 282--293","author":"Kalinsky Oren","year":"2017","unstructured":"Oren Kalinsky , Yoav Etsion , and Benny Kimelfeld . 2017 . Flexible caching in trie joins . In International Conference on Extending Database Technology (EDBT). 282--293 . Oren Kalinsky, Yoav Etsion, and Benny Kimelfeld. 2017. Flexible caching in trie joins. In International Conference on Extending Database Technology (EDBT). 282--293."},{"key":"e_1_2_2_31_1","volume-title":"Symposium on Discrete Algorithms (SODA). 551--557","author":"Kannan Sampath","unstructured":"Sampath Kannan , Z. Sweedyk , and Stephen R. Mahaney . 1995. Counting and random generation of strings in regular languages . In Symposium on Discrete Algorithms (SODA). 551--557 . Sampath Kannan, Z. Sweedyk, and Stephen R. Mahaney. 1995. Counting and random generation of strings in regular languages. In Symposium on Discrete Algorithms (SODA). 551--557."},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2448496.2448526"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230140403"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(80)90057-4"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.18.7.401"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2850413"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2494529"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.5555\/274167.274171"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3105960"},{"key":"e_1_2_2_40_1","doi-asserted-by":"crossref","unstructured":"Wim Martens Frank Neven and Thomas Schwentick. 2004. Complexity of decision problems for simple regular expressions. In Mathematical Foundations of Computer Science (MFCS). 889--900.  Wim Martens Frank Neven and Thomas Schwentick. 2004. Complexity of decision problems for simple regular expressions. In Mathematical Foundations of Computer Science (MFCS). 889--900.","DOI":"10.1007\/978-3-540-28629-5_70"},{"key":"e_1_2_2_41_1","volume-title":"International Conference on Database Theory (ICDT). 19:1--19:21","author":"Martens Wim","year":"2018","unstructured":"Wim Martens and Tina Trautner . 2018 . Evaluation and enumeration problems for regular path queries . In International Conference on Database Theory (ICDT). 19:1--19:21 . Wim Martens and Tina Trautner. 2018. Evaluation and enumeration problems for regular path queries. In International Conference on Database Theory (ICDT). 19:1--19:21."},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979122370X"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-0208(08)73110-4"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.16.3.682"},{"key":"e_1_2_2_45_1","unstructured":"Neo4j. 2017. Intro to Cypher. https:\/\/neo4j.com\/developer\/cypher-query-language\/.  Neo4j. 2017. Intro to Cypher. https:\/\/neo4j.com\/developer\/cypher-query-language\/."},{"key":"e_1_2_2_46_1","volume-title":"www.opencypher.org. Visited on","author":"OpenCypher OpenCypher","year":"2017","unstructured":"OpenCypher [n.d.]. OpenCypher . www.opencypher.org. Visited on Sept. 14, 2017 . OpenCypher [n.d.]. OpenCypher. www.opencypher.org. Visited on Sept. 14, 2017."},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/322047.322048"},{"key":"e_1_2_2_48_1","volume-title":"CIP2017-01-18 -- Configurable Pattern Matching Semantics. https:\/\/github.com\/boggle\/openCypher\/blob\/isomatch\/cip\/1.accepted\/CIP2017-01-18-configurable-pattern-matching-semantics.adoc. Visited on","author":"Plantikow Stefan","year":"2017","unstructured":"Stefan Plantikow , Mats Rydberg , and Petra Selmer . [n.d.]. CIP2017-01-18 -- Configurable Pattern Matching Semantics. https:\/\/github.com\/boggle\/openCypher\/blob\/isomatch\/cip\/1.accepted\/CIP2017-01-18-configurable-pattern-matching-semantics.adoc. Visited on Aug. 08, 2017 . Stefan Plantikow, Mats Rydberg, and Petra Selmer. [n.d.]. CIP2017-01-18 -- Configurable Pattern Matching Semantics. https:\/\/github.com\/boggle\/openCypher\/blob\/isomatch\/cip\/1.accepted\/CIP2017-01-18-configurable-pattern-matching-semantics.adoc. Visited on Aug. 08, 2017."},{"key":"e_1_2_2_49_1","volume-title":"The Algorithm Design Manual","author":"Skiena Steven","unstructured":"Steven Skiena . 2008. The Algorithm Design Manual ( 2 nd ed.). Springer . Steven Skiena. 2008. The Algorithm Design Manual (2nd ed.). Springer.","edition":"2"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.5555\/1958204.1958207"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1093\/jigpal\/jzv028"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1137\/0208032"},{"key":"e_1_2_2_53_1","unstructured":"Domagoj Vrgo\u010d. 2018. Personal communication. After a talk of Wim Martens at PUC Chile the query was discussed in more detail and Domagoj Vrgo\u010d who attended the talk informed us that he wrote the query.  Domagoj Vrgo\u010d. 2018. Personal communication. After a talk of Wim Martens at PUC Chile the query was discussed in more detail and Domagoj Vrgo\u010d who attended the talk informed us that he wrote the query."},{"key":"e_1_2_2_54_1","volume-title":"SPARQL","year":"2013","unstructured":"W3C SPARQL 2013 . SPARQL 1.1 Query Language. https:\/\/www.w3.org\/TR\/sparql11-query\/. World Wide Web Consortium. W3C SPARQL 2013. SPARQL 1.1 Query Language. https:\/\/www.w3.org\/TR\/sparql11-query\/. World Wide Web Consortium."},{"key":"e_1_2_2_55_1","volume-title":"Visited on","author":"World Wide Web Consortium [n.d.].","year":"2017","unstructured":"World Wide Web Consortium [n.d.]. World Wide Web Consortium. www.w3.org . Visited on Sept. 14, 2017 . World Wide Web Consortium [n.d.]. World Wide Web Consortium. www.w3.org. Visited on Sept. 14, 2017."},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/298514.298576"},{"key":"e_1_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.17.11.712"},{"key":"e_1_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/321707.321712"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3331446","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3331446","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:43:28Z","timestamp":1750207408000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3331446"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,10,15]]},"references-count":58,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,12,31]]}},"alternative-id":["10.1145\/3331446"],"URL":"https:\/\/doi.org\/10.1145\/3331446","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,10,15]]},"assertion":[{"value":"2018-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-10-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}