{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T17:03:00Z","timestamp":1759683780330,"version":"3.41.0"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2018,7,25]],"date-time":"2018-07-25T00:00:00Z","timestamp":1532476800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Poland's National Science Centre","award":["UMO-2013\/11\/D\/ST6\/03075"],"award-info":[{"award-number":["UMO-2013\/11\/D\/ST6\/03075"]}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"crossref","award":["4938\/2-1"],"award-info":[{"award-number":["4938\/2-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2018,8,31]]},"abstract":"<jats:p>Many of today\u2019s graph query languages are based on graph pattern matching. We investigate optimization of tree-shaped patterns that have transitive closure operators. Such patterns not only appear in the context of graph databases but also were originally studied for querying tree-structured data, where they can perform child, descendant, node label, and wildcard tests.<\/jats:p>\n          <jats:p>\n            The\n            <jats:italic>minimization<\/jats:italic>\n            problem aims at reducing the number of nodes in patterns and goes back to the early 2000s. 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 =\n            <jats:sup>?<\/jats:sup>\n            NR problem, which asks if a tree pattern is minimal if and only if it is nonredundant. The example can be adapted to prove that minimization is \u03a3\n            <jats:sup>\n              <jats:italic>P<\/jats:italic>\n            <\/jats:sup>\n            <jats:sub>2<\/jats:sub>\n            -complete, which resolves another question that was open since the early research on the problem. The latter result shows that, unless NP = \u03a0\n            <jats:sup>\n              <jats:italic>P<\/jats:italic>\n            <\/jats:sup>\n            <jats:sub>2<\/jats:sub>\n            , more general approaches for minimizing tree patterns are also bound to fail in general.\n          <\/jats:p>","DOI":"10.1145\/3180281","type":"journal-article","created":{"date-parts":[[2018,7,26]],"date-time":"2018-07-26T11:58:04Z","timestamp":1532606284000},"page":"1-46","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Minimization of Tree Patterns"],"prefix":"10.1145","volume":"65","author":[{"given":"Wojciech","family":"Czerwi\u0143ski","sequence":"first","affiliation":[{"name":"University of Warsaw, Warsaw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wim","family":"Martens","sequence":"additional","affiliation":[{"name":"University of Bayreuth, Bayreuth, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matthias","family":"Niewerth","sequence":"additional","affiliation":[{"name":"University of Bayreuth, Bayreuth, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pawe\u0142","family":"Parys","sequence":"additional","affiliation":[{"name":"University of Warsaw, Warsaw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,7,25]]},"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","unstructured":"Renzo Angles Marcelo Arenas Pablo Barcel\u00f3 Aidan Hogan Juan L. Reutter and Domagoj Vrgoc. 2016. Foundations of modern graph query languages. arXiv:1610.06264.  Renzo Angles Marcelo Arenas Pablo Barcel\u00f3 Aidan Hogan Juan L. Reutter and Domagoj Vrgoc. 2016. Foundations of modern graph query languages. arXiv:1610.06264."},{"volume-title":"Foundations of Data Exchange","author":"Arenas Marcelo","key":"e_1_2_1_4_1","unstructured":"Marcelo Arenas , Pablo Barcel\u00f3 , Leonid Libkin , and Filip Murlak . 2014. Foundations of Data Exchange . Cambridge University Press . Marcelo Arenas, Pablo Barcel\u00f3, Leonid Libkin, and Filip Murlak. 2014. Foundations of Data Exchange. Cambridge University Press."},{"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\/1346330.1346332"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1870103.1870107"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1346330.1346333"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.04.005"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40313-2_17"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Angela Bonifati Wim Martens and Thomas Timm. 2017. An analytical study of large SPARQL query logs. arXiv:1708.00363.  Angela Bonifati Wim Martens and Thomas Timm. 2017. An analytical study of large SPARQL query logs. arXiv:1708.00363.","DOI":"10.14778\/3167892.3167895"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/800105.803397"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376678"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902295"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2745754.2745766"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2448496.2448521"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1866480.1866504"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2010.203"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/1315451.1315466"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1326554.1326556"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39666-3_2"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902309"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1131342.1131345"},{"key":"e_1_2_1_24_1","unstructured":"Gremlin. 2013. Gremlin Language. Retrieved from https:\/\/github.com\/tinkerpop\/gremlin\/wiki.  Gremlin. 2013. Gremlin Language. Retrieved from https:\/\/github.com\/tinkerpop\/gremlin\/wiki."},{"key":"e_1_2_1_25_1","unstructured":"JSONPath. 2016. JSONPath Online Evaluator. Retrieved from http:\/\/jsonpath.com\/.  JSONPath. 2016. JSONPath Online Evaluator. Retrieved from http:\/\/jsonpath.com\/."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1353343.1353355"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2850413"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2494529"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/962446.962448"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/645503.656266"},{"key":"e_1_2_1_31_1","unstructured":"Neo4j Cypher. 2016. The Cypher Query Language. Retrieved from https:\/\/neo4j.com\/docs\/developer-manual\/current\/cypher\/.  Neo4j Cypher. 2016. The Cypher Query Language. Retrieved from https:\/\/neo4j.com\/docs\/developer-manual\/current\/cypher\/."},{"key":"e_1_2_1_32_1","volume-title":"On the complexity of XPath containment in the presence of disjunction, DTDs, and variables. Log. Methods Comput. 2, 3","author":"Neven Frank","year":"2006","unstructured":"Frank Neven and Thomas Schwentick . 2006. On the complexity of XPath containment in the presence of disjunction, DTDs, and variables. Log. Methods Comput. 2, 3 ( 2006 ), Article 1. Frank Neven and Thomas Schwentick. 2006. On the complexity of XPath containment in the presence of disjunction, DTDs, and variables. Log. Methods Comput. 2, 3 (2006), Article 1."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564726"},{"key":"e_1_2_1_35_1","volume-title":"Graph Databases","author":"Robinson Ian","unstructured":"Ian Robinson , Jim Webber , and Emil Eifrem . 2015. Graph Databases ( 2 nd ed.). O\u2019Reilly . Ian Robinson, Jim Webber, and Emil Eifrem. 2015. Graph Databases (2nd ed.). O\u2019Reilly.","edition":"2"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2815072.2815073"},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of the International Conference on Database Theory (ICDT\u201915)","author":"Staworko Slawek","year":"2015","unstructured":"Slawek Staworko and Piotr Wieczorek . 2015 . Characterizing XML twig queries with examples . In Proceedings of the International Conference on Database Theory (ICDT\u201915) . 144--160. Slawek Staworko and Piotr Wieczorek. 2015. Characterizing XML twig queries with examples. In Proceedings of the International Conference on Database Theory (ICDT\u201915). 144--160."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90061-X"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-008-9151-9"},{"key":"e_1_2_1_40_1","unstructured":"W3C Sparql. 2013. SPARQL 1.1 Query Language. Retrieved from https:\/\/www.w3.org\/TR\/sparql11-query\/.  W3C Sparql. 2013. SPARQL 1.1 Query Language. Retrieved from https:\/\/www.w3.org\/TR\/sparql11-query\/."},{"key":"e_1_2_1_41_1","unstructured":"Wikidata Examples. 2016. WikiData SPARQL Query Service Examples. Retrieved from https:\/\/www.wikidata.org\/wiki\/Wikidata:SPARQL_query_service\/queries\/examples.  Wikidata Examples. 2016. WikiData SPARQL Query Service Examples. Retrieved from https:\/\/www.wikidata.org\/wiki\/Wikidata:SPARQL_query_service\/queries\/examples."},{"key":"e_1_2_1_42_1","volume-title":"Proceedings of the 4th International Workshop on the Web and Databases (WebDB\u201901)","author":"Wood Peter T.","year":"2001","unstructured":"Peter T. Wood . 2001 . Minimising simple XPath expressions . In Proceedings of the 4th International Workshop on the Web and Databases (WebDB\u201901) . 13--18. Peter T. Wood. 2001. Minimising simple XPath expressions. In Proceedings of the 4th International Workshop on the Web and Databases (WebDB\u201901). 13--18."},{"key":"e_1_2_1_43_1","volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB\u201905)","author":"Xu Wanhong","year":"2005","unstructured":"Wanhong Xu and Z. Meral \u00d6zsoyoglu . 2005 . Rewriting XPath queries using materialized views . In Proceedings of the International Conference on Very Large Data Bases (VLDB\u201905) . 121--132. Wanhong Xu and Z. Meral \u00d6zsoyoglu. 2005. Rewriting XPath queries using materialized views. In Proceedings of the International Conference on Very Large Data Bases (VLDB\u201905). 121--132."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3180281","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3180281","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:39:30Z","timestamp":1750210770000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3180281"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,7,25]]},"references-count":42,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,8,31]]}},"alternative-id":["10.1145\/3180281"],"URL":"https:\/\/doi.org\/10.1145\/3180281","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2018,7,25]]},"assertion":[{"value":"2017-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-07-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}