{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T20:07:36Z","timestamp":1784232456642,"version":"3.55.0"},"reference-count":50,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["G049165"],"award-info":[{"award-number":["G049165"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004963","name":"Seventh Framework Programme","doi-asserted-by":"publisher","award":["233599"],"award-info":[{"award-number":["233599"]}],"id":[{"id":"10.13039\/501100004963","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002850","name":"Fondo Nacional de Desarrollo Cient\u00edfico y Tecnol\u00f3gico","doi-asserted-by":"publisher","award":["1110171"],"award-info":[{"award-number":["1110171"]}],"id":[{"id":"10.13039\/501100002850","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2014,1]]},"abstract":"<jats:p>Graph data appears in a variety of application domains, and many uses of it, such as querying, matching, and transforming data, naturally result in incompletely specified graph data, that is, graph patterns. While queries need to be posed against such data, techniques for querying patterns are generally lacking, and properties of such queries are not well understood.<\/jats:p>\n          <jats:p>Our goal is to study the basics of querying graph patterns. The key features of patterns we consider here are node and label variables and edges specified by regular expressions. We provide a classification of patterns, and study standard graph queries on graph patterns. We give precise characterizations of both data and combined complexity for each class of patterns. If complexity is high, we do further analysis of features that lead to intractability, as well as lower-complexity restrictions. Since our patterns are based on regular expressions, query answering for them can be captured by a new automata model. These automata have two modes of acceptance: one captures queries returning nodes, and the other queries returning paths. We study properties of such automata, and the key computational tasks associated with them. Finally, we provide additional restrictions for tractability, and show that some intractable cases can be naturally cast as instances of constraint satisfaction problems.<\/jats:p>","DOI":"10.1145\/2559905","type":"journal-article","created":{"date-parts":[[2014,2,4]],"date-time":"2014-02-04T14:16:21Z","timestamp":1391523381000},"page":"1-54","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":39,"title":["Querying Regular Graph Patterns"],"prefix":"10.1145","volume":"61","author":[{"given":"Pablo","family":"Barcel\u00f3","sequence":"first","affiliation":[{"name":"Universidad de Chile"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Leonid","family":"Libkin","sequence":"additional","affiliation":[{"name":"University of Edinburgh"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Juan L.","family":"Reutter","sequence":"additional","affiliation":[{"name":"University of Edinburgh and Pontificia Universidad Cat\u00f3lica de Chile"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2014,1]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/324746"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1322432.1322433"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","unstructured":"Arenas M. Barcel\u00f3 P. Libkin L. and Murlak F. 2010. Relational and XML Data Exchange. Morgan & Claypool.","DOI":"10.5555\/1941440"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807085.1807089"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1870103.1870107"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.12.036"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/1783534.1783542"},{"key":"e_1_2_2_8_1","first-page":"4","article-title":"The complexity of enriched mu-calculi","volume":"8","author":"Bonatti P. A.","year":"2008","unstructured":"Bonatti, P. A., Lutz, C., Murano, A., and Vardi, M. Y. 2008. The complexity of enriched mu-calculi. Log. Meth. Comput. Sci. 8, 4.","journal-title":"Log. Meth. Comput. Sci."},{"key":"e_1_2_2_9_1","doi-asserted-by":"crossref","unstructured":"B\u00f6rger E. Gr\u00e4edel E. and Gurevich Y. 1997. The Classical Decision Problem. Perspectives in Mathematical Logics Springer-Verlag.","DOI":"10.1007\/978-3-642-59207-2"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/233269.233368"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/846219.847323"},{"key":"e_1_2_2_12_1","volume-title":"Proceedings of the 7th International Conference on Principles of Knowledge Representation and Reasoning (KR). 176--185","author":"Calvanese D.","unstructured":"Calvanese, D., De Giacomo, G., Lenzerini, M., and Vardi, M. 2000b. Containment of conjunctive regular path queries with inverse. In Proceedings of the 7th International Conference on Principles of Knowledge Representation and Reasoning (KR). 176--185."},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/788022.789018"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1805"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1938551.1938568"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497500"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30570-5_9"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/298514.298591"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/38713.38749"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/1622767.1622770"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","unstructured":"Dechter R. 2003. Constraint Processing. Morgan-Kauffman.","DOI":"10.5555\/861888"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/648294.754678"},{"key":"e_1_2_2_23_1","volume-title":"Graph Theory","author":"Diestel R.","unstructured":"Diestel, R. 2005. Graph Theory. Springer."},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/1085304.1085309"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920878"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920986"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767858"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(96)00095-6"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1131342.1131345"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.04.009"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.298174"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1634.1886"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(84)90081-3"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1811"},{"key":"e_1_2_2_35_1","doi-asserted-by":"crossref","unstructured":"Kolaitis P. and Vardi M. 2007. A logical approach to constraint satisfaction. In Finite Model Theory and Its Applications Springer 339--370.","DOI":"10.1007\/3-540-68804-8_6"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1977.16"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.2000.2893"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.5555\/1316689.1316702"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543644"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","unstructured":"Leser U. 2005. A query language for biological networks. Bioinformatics 21 2 ii33--ii39. 10.1093\/bioinformatics\/bti1105","DOI":"10.1093\/bioinformatics\/bti1105"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.5555\/1024196"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989284.1989294"},{"key":"e_1_2_2_43_1","doi-asserted-by":"crossref","unstructured":"Milo R. Shen-Orr S. Itzkovitz S. Kashtan N. Chklovskii D. and Alon U. 2002. Network motifs: Simple building blocks of complex networks. Science 298 5594 824--827.","DOI":"10.1126\/science.298.5594.824"},{"key":"e_1_2_2_44_1","first-page":"273","article-title":"Understanding the structure of a drug trafficking organization: A conversational analysis","volume":"11","author":"Natarajan M.","year":"2000","unstructured":"Natarajan, M. 2000. Understanding the structure of a drug trafficking organization: A conversational analysis. Crime Prevention Studies 11, 273--298.","journal-title":"Crime Prevention Studies"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1089\/153623103322006652"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1567274.1567278"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.172"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02121-3_24"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281192.1281271"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/1498765.1498784"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2559905","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2559905","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:10:25Z","timestamp":1750234225000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2559905"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,1]]},"references-count":50,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,1]]}},"alternative-id":["10.1145\/2559905"],"URL":"https:\/\/doi.org\/10.1145\/2559905","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,1]]},"assertion":[{"value":"2011-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-11-01","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-01-01","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}