{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,13]],"date-time":"2026-05-13T09:14:02Z","timestamp":1778663642493,"version":"3.51.4"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2008,2,1]],"date-time":"2008-02-01T00:00:00Z","timestamp":1201824000000},"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":["J. ACM"],"published-print":{"date-parts":[[2008,2]]},"abstract":"<jats:p>\n            XPath expressions define navigational queries on XML data and are issued on XML documents to select sets of element nodes. Due to the wide use of XPath, which is embedded into several languages for querying and manipulating XML data, the problem of efficiently answering XPath queries has received increasing attention from the research community. As the efficiency of computing the answer of an XPath query depends on its size, replacing XPath expressions with equivalent ones having the smallest size is a crucial issue in this direction. This article investigates the minimization problem for a wide fragment of XPath (namely\n            <jats:italic>X P<\/jats:italic>\n            <jats:sup>[\u2736]<\/jats:sup>\n            ), where the use of the most common operators (child, descendant, wildcard and branching) is allowed with some syntactic restrictions. The examined fragment consists of expressions which have not been specifically studied in the relational setting before: neither are they mere conjunctive queries (as the combination of \u201c\/\/\u201d and \u201c*\u201d enables an implicit form of disjunction to be expressed) nor do they coincide with disjunctive ones (as the latter are more expressive). Three main contributions are provided. The \u201cglobal minimality\u201d property is shown to hold: the minimization of a given XPath expression can be accomplished by removing pieces of the expression, without having to re-formulate it (as for \u201cgeneral\u201d disjunctive queries). Then, the complexity of the minimization problem is characterized, showing that it is the same as the containment problem. Finally, specific forms of XPath expressions are identified, which can be minimized in polynomial time.\n          <\/jats:p>","DOI":"10.1145\/1326554.1326556","type":"journal-article","created":{"date-parts":[[2008,2,28]],"date-time":"2008-02-28T14:02:33Z","timestamp":1204207353000},"page":"1-46","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":18,"title":["On the minimization of XPath queries"],"prefix":"10.1145","volume":"55","author":[{"given":"S.","family":"Flesca","sequence":"first","affiliation":[{"name":"DEIS\u2014Universit\u00e0 della Calabria, Rende, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"F.","family":"Furfaro","sequence":"additional","affiliation":[{"name":"DEIS\u2014Universit\u00e0 della Calabria, Rende, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"E.","family":"Masciari","sequence":"additional","affiliation":[{"name":"ICAR\u2014CNR, Rende, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,2,22]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(89)90019-7"},{"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":"Proceedings of the 9th International Conference on Database Theory (ICDT)","author":"Benedikt M."},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 30th International Conference on Very Large Data Bases (VLDB)","author":"Chan C. Y."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/800105.803397"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 6th International Conference on Database Theory (ICDT)","author":"Chekuri C."},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 8th International Workshop on Knowledge Representation Meets Databases (KRDB)","author":"Deutsch A."},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 28th International Conference on Very Large Databases (VLDB)","author":"Gottlob G."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1353343.1353355"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1713"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/962446.962448"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 7th International Conference on Database Theory (ICDT)","author":"Milo T."},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 9th International Conference on Database Theory (ICDT)","author":"Neven F."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564726"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322221"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/974121.974140"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0743-1066(93)90040-N"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/647482.728290"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 4th International Workshop on the Web and Databases (WebDB)","author":"Wood P. T.","year":"2001"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/645505.656434"},{"key":"e_1_2_1_21_1","unstructured":"XLi. 2004. XML Linking Language (XLink) Version 1.0---W3C Recommendation. In http:\/\/www.w3.org\/TR\/2001\/REC-xlink-20010627\/.  XLi. 2004. XML Linking Language (XLink) Version 1.0---W3C Recommendation. In http:\/\/www.w3.org\/TR\/2001\/REC-xlink-20010627\/."},{"key":"e_1_2_1_22_1","unstructured":"XML. 2004. Extensible Markup Language (XML) 1.0 (Third Edition)---W3C Recommendation. In http:\/\/www.w3c.org\/TR\/2004\/REC-xml-20040204\/.  XML. 2004. Extensible Markup Language (XML) 1.0 (Third Edition)---W3C Recommendation. In http:\/\/www.w3c.org\/TR\/2004\/REC-xml-20040204\/."},{"key":"e_1_2_1_23_1","unstructured":"XPa. 1999. XML Path Language (XPath) Version 1.0---W3C Recommendation. In http:\/\/www.w3.org\/TR\/xpath.  XPa. 1999. XML Path Language (XPath) Version 1.0---W3C Recommendation. In http:\/\/www.w3.org\/TR\/xpath."},{"key":"e_1_2_1_24_1","unstructured":"XPo. 2002. XML Pointer Language (XPointer)---W3C Working Draft. In http:\/\/www.w3.org\/TR\/2002\/WD-xptr-20020816\/.  XPo. 2002. XML Pointer Language (XPointer)---W3C Working Draft. In http:\/\/www.w3.org\/TR\/2002\/WD-xptr-20020816\/."},{"key":"e_1_2_1_25_1","unstructured":"XQu. 2004. XQuery 1.0: An XML Query Language---W3C Working Draft. In http:\/\/www.w3.org\/TR\/xquery\/.  XQu. 2004. XQuery 1.0: An XML Query Language---W3C Working Draft. In http:\/\/www.w3.org\/TR\/xquery\/."},{"key":"e_1_2_1_26_1","unstructured":"XSc. 2001. XML Schema Part 0: Primer---W3C Recommendation. In http:\/\/www.w3.org\/TR\/xmlschema-0\/.  XSc. 2001. XML Schema Part 0: Primer---W3C Recommendation. In http:\/\/www.w3.org\/TR\/xmlschema-0\/."},{"key":"e_1_2_1_27_1","unstructured":"XSLT. 1999. XSL Transformations (XSLT) Version 1.0---W3C Recommendation. In http:\/\/www. w3.org\/TR\/xslt.  XSLT. 1999. XSL Transformations (XSLT) Version 1.0---W3C Recommendation. In http:\/\/www. w3.org\/TR\/xslt."},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the 7th International Conference on Very Large Databases (VLDB)","author":"Yannakakis M.","year":"1981"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1326554.1326556","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1326554.1326556","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:56:25Z","timestamp":1750254985000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1326554.1326556"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,2]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2008,2]]}},"alternative-id":["10.1145\/1326554.1326556"],"URL":"https:\/\/doi.org\/10.1145\/1326554.1326556","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,2]]},"assertion":[{"value":"2004-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2007-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-02-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}