{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:08:05Z","timestamp":1750306085168,"version":"3.41.0"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2017,5,12]],"date-time":"2017-05-12T00:00:00Z","timestamp":1494547200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGMOD Rec."],"published-print":{"date-parts":[[2017,5,12]]},"abstract":"<jats:p>Many of today's graph query languages are based on graph pattern matching. We investigate optimization for treeshaped patterns with transitive closure. Such patterns are quite expressive, yet can be evaluated efficiently. The minimization problem aims at reducing the number of nodes in patterns and goes back to the early 2000's. We provide an example showing that, in contrast to earlier claims, tree patterns cannot be minimized by deleting nodes only. The example resolves the M ?\/= NR problem, which asks if a tree pattern is minimal if and only if it is nonredundant. The example can be adapted to also understand the complexity of minimization, which was another question that was open since the early research on the problem. Interestingly, the latter result also shows that, unless standard complexity assumptions are false, more general approaches for minimizing tree patterns are also bound to fail in some cases.<\/jats:p>","DOI":"10.1145\/3093754.3093759","type":"journal-article","created":{"date-parts":[[2017,5,15]],"date-time":"2017-05-15T12:13:58Z","timestamp":1494850438000},"page":"15-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Optimizing Tree Patterns for Querying Graph- and Tree-Structured Data"],"prefix":"10.1145","volume":"46","author":[{"given":"Wojciech","family":"Czerwinski","sequence":"first","affiliation":[{"name":"University of Warsaw"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wim","family":"Martens","sequence":"additional","affiliation":[{"name":"Universit\u00e4t Bayreuth"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matthias","family":"Niewerth","sequence":"additional","affiliation":[{"name":"Universit\u00e4t Bayreuth"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pawel","family":"Parys","sequence":"additional","affiliation":[{"name":"University of Warsaw"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,5,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1620585.1620590"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-002-0076-7"},{"key":"e_1_2_1_3_1","volume-title":"Foundations of modern graph query languages. CoRR, abs\/1610.06264","author":"Angles R.","year":"2016","unstructured":"R. Angles , M. Arenas , P. Barcel\u00f3 , A. Hogan , J. L. Reutter , and D. Vrgoc . Foundations of modern graph query languages. CoRR, abs\/1610.06264 , 2016 . R. Angles, M. Arenas, P. Barcel\u00f3, A. Hogan, J. L. Reutter, and D. Vrgoc. Foundations of modern graph query languages. CoRR, abs\/1610.06264, 2016."},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781139060158","volume-title":"Foundations of Data Exchange","author":"Arenas M.","year":"2014","unstructured":"M. Arenas , P. Barcel\u00f3 , L. Libkin , and F. Murlak . Foundations of Data Exchange . Cambridge University Press , 2014 . M. Arenas, P. Barcel\u00f3, L. Libkin, and F. Murlak. Foundations of Data Exchange. Cambridge University Press, 2014."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2187836.2187922"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1870103.1870107"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1346330.1346333"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.04.005"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40313-2_17"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/800105.803397"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376678"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902295"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2745754.2745766"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-012722442-8\/50022-7"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1326554.1326556"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39666-3_2"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902309"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1131342.1131345"},{"key":"e_1_2_1_19_1","volume-title":"github.com\/tinkerpop\/gremlin\/wiki","author":"Language Gremlin","year":"2013","unstructured":"Gremlin Language . github.com\/tinkerpop\/gremlin\/wiki , 2013 . Gremlin Language. github.com\/tinkerpop\/gremlin\/wiki, 2013."},{"key":"e_1_2_1_20_1","unstructured":"jsonpath.com\/ January 2017.  jsonpath.com\/ January 2017."},{"key":"e_1_2_1_21_1","volume-title":"Technical report","author":"Kay M.","year":"2015","unstructured":"M. Kay . XSL Transformations (XSLT) version 3.0. Technical report , World Wide Web Consortium , November 2015 . W3C Recommendation, www.w3.org\/TR\/2015\/CR-xslt-30-20151119\/. M. Kay. XSL Transformations (XSLT) version 3.0. Technical report, World Wide Web Consortium, November 2015. W3C Recommendation, www.w3.org\/TR\/2015\/CR-xslt-30-20151119\/."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1353343.1353355"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2494529"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/962446.962448"},{"key":"e_1_2_1_25_1","volume-title":"neo4j.com\/docs\/developer-manual\/current\/cypher\/","author":"The Cypher","year":"2016","unstructured":"The Cypher query language. neo4j.com\/docs\/developer-manual\/current\/cypher\/ , 2016 . The Cypher query language. neo4j.com\/docs\/developer-manual\/current\/cypher\/, 2016."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-2(3:1)2006"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564726"},{"key":"e_1_2_1_28_1","volume-title":"XML Path Language 3.0. Technical report","author":"Robie J.","year":"2014","unstructured":"J. Robie , D. Chamberlin , M. Dyck , and J. Snelson . XML Path Language 3.0. Technical report , World Wide Web Consortium , April 2014 . www.w3.org\/TR\/2014\/REC-xpath-30-20140408\/. J. Robie, D. Chamberlin, M. Dyck, and J. Snelson. XML Path Language 3.0. Technical report, World Wide Web Consortium, April 2014. www.w3.org\/TR\/2014\/REC-xpath-30-20140408\/."},{"key":"e_1_2_1_29_1","volume-title":"XQuery 3.0: An XML query language. Technical report","author":"Robie J.","year":"2014","unstructured":"J. Robie , D. Chamberlin , M. Dyck , and J. Snelson . XQuery 3.0: An XML query language. Technical report , World Wide Web Consortium , April 2014 . W3C Recommendation, www.w3.org\/TR\/2014\/REC-xquery-30-20140408\/. J. Robie, D. Chamberlin, M. Dyck, and J. Snelson. XQuery 3.0: An XML query language. Technical report, World Wide Web Consortium, April 2014. W3C Recommendation, www.w3.org\/TR\/2014\/REC-xquery-30-20140408\/."},{"key":"e_1_2_1_30_1","volume-title":"Graph Databases. O'Reilly, 2 edition","author":"Robinson I.","year":"2015","unstructured":"I. Robinson , J. Webber , and E. Eifrem . Graph Databases. O'Reilly, 2 edition , 2015 . I. Robinson, J. Webber, and E. Eifrem. Graph Databases. O'Reilly, 2 edition, 2015."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2815072.2815073"},{"key":"e_1_2_1_32_1","first-page":"144","volume-title":"International Conference on Database Theory (ICDT)","author":"Staworko S.","year":"2015","unstructured":"S. Staworko and P. Wieczorek . Characterizing XML twig queries with examples . In International Conference on Database Theory (ICDT) , pages 144 -- 160 , 2015 . S. Staworko and P. Wieczorek. Characterizing XML twig queries with examples. In International Conference on Database Theory (ICDT), pages 144--160, 2015."},{"volume-title":"www.w3.org\/TR\/sparql11-query\/","author":"SPARQL","key":"e_1_2_1_33_1","unstructured":"SPARQL 1.1 query language. www.w3.org\/TR\/sparql11-query\/ . World Wide Web Consortium . SPARQL 1.1 query language. www.w3.org\/TR\/sparql11-query\/. World Wide Web Consortium."},{"key":"e_1_2_1_34_1","unstructured":"Wikidata sparql query service examples. www.wikidata.org\/wiki\/Wikidata: SPARQL_query_service\/queries\/examples.  Wikidata sparql query service examples. www.wikidata.org\/wiki\/Wikidata: SPARQL_query_service\/queries\/examples."},{"key":"e_1_2_1_35_1","first-page":"13","volume-title":"WebDB","author":"Wood P. T.","year":"2001","unstructured":"P. T. Wood . Minimising simple XPath expressions . In WebDB , pages 13 -- 18 , 2001 . P. T. Wood. Minimising simple XPath expressions. In WebDB, pages 13--18, 2001."},{"volume-title":"International Conference on Very","author":"Xu W.","key":"e_1_2_1_36_1","unstructured":"W. Xu and Z. M. \u00d6zsoyoglu . Rewriting XPath queries using materialized views . In International Conference on Very W. Xu and Z. M. \u00d6zsoyoglu. Rewriting XPath queries using materialized views. In International Conference on Very"}],"container-title":["ACM SIGMOD Record"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3093754.3093759","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3093754.3093759","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:30:16Z","timestamp":1750217416000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3093754.3093759"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,5,12]]},"references-count":36,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,5,12]]}},"alternative-id":["10.1145\/3093754.3093759"],"URL":"https:\/\/doi.org\/10.1145\/3093754.3093759","relation":{},"ISSN":["0163-5808"],"issn-type":[{"type":"print","value":"0163-5808"}],"subject":[],"published":{"date-parts":[[2017,5,12]]},"assertion":[{"value":"2017-05-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}