{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,15]],"date-time":"2026-06-15T10:18:47Z","timestamp":1781518727290,"version":"3.54.1"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2013,11,1]],"date-time":"2013-11-01T00:00:00Z","timestamp":1383264000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004963","name":"Seventh Framework Programme","doi-asserted-by":"publisher","award":["24761 (Net2)"],"award-info":[{"award-number":["24761 (Net2)"]}],"id":[{"id":"10.13039\/501100004963","id-type":"DOI","asserted-by":"publisher"}]},{"name":"VID","award":["U-Inicia 11\/04"],"award-info":[{"award-number":["U-Inicia 11\/04"]}]},{"DOI":"10.13039\/501100001821","name":"Vienna Science and Technology Fund","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001821","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":["11110404"],"award-info":[{"award-number":["11110404"]}],"id":[{"id":"10.13039\/501100002850","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100002428","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":[[2013,11]]},"abstract":"<jats:p>\n            Static analysis is a fundamental task in query optimization. In this article we study static analysis and optimization techniques for SPARQL, which is the standard language for querying Semantic Web data. Of particular interest for us is the\n            <jats:italic>optionality<\/jats:italic>\n            feature in SPARQL. It is crucial in Semantic Web data management, where data sources are inherently incomplete and the user is usually interested in partial answers to queries. This feature is one of the most complicated constructors in SPARQL and also the one that makes this language depart from classical query languages such as relational conjunctive queries. We focus on the class of well-designed SPARQL queries, which has been proposed in the literature as a fragment of the language with good properties regarding query evaluation. We first propose a tree representation for SPARQL queries, called pattern trees, which captures the class of well-designed SPARQL graph patterns. Among other results, we propose several rules that can be used to transform pattern trees into a simple normal form, and study equivalence and containment. We also study the evaluation and enumeration problems for this class of queries.\n          <\/jats:p>","DOI":"10.1145\/2500130","type":"journal-article","created":{"date-parts":[[2013,12,10]],"date-time":"2013-12-10T13:28:12Z","timestamp":1386682092000},"page":"1-45","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":43,"title":["Static analysis and optimization of semantic web queries"],"prefix":"10.1145","volume":"38","author":[{"given":"Andr\u00e9s","family":"Letelier","sequence":"first","affiliation":[{"name":"PUC Chile, Chile"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jorge","family":"P\u00e9rez","sequence":"additional","affiliation":[{"name":"Universidad de Chile, Chile"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Reinhard","family":"Pichler","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t Wien, Austria"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sebastian","family":"Skritek","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t Wien, Austria"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2013,12,4]]},"reference":[{"key":"e_1_2_2_1_1","volume-title":"Proceedings of the 33rd International Conference on Very Large Data Bases (VLDB'07)","author":"Abadi D. J.","unstructured":"Abadi , D. J. , Marcus , A. , Madden , S. , and Hollenbach , K. J . 2007. Scalable semantic web data management using vertical partitioning . In Proceedings of the 33rd International Conference on Very Large Data Bases (VLDB'07) . ACM Press, New York, 411--422. Abadi, D. J., Marcus, A., Madden, S., and Hollenbach, K. J. 2007. Scalable semantic web data management using vertical partitioning. In Proceedings of the 33rd International Conference on Very Large Data Bases (VLDB'07). ACM Press, New York, 411--422."},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1691"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-88564-1_8"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989284.1989312"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/2392389.2392412"},{"key":"e_1_2_2_6_1","unstructured":"Berners-Lee T. 2006. Linked data -- Design issues. http:\/\/www.w3.org\/DesignIssues\/LinkedData.html.  Berners-Lee T. 2006. Linked data -- Design issues. http:\/\/www.w3.org\/DesignIssues\/LinkedData.html."},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.4018\/jswis.2009081901"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/800105.803397"},{"key":"e_1_2_2_9_1","volume-title":"Proceedings of the 26th AAAI Conference on Artificial Intelligence (AAAI'12)","author":"Chekol M. W.","unstructured":"Chekol , M. W. , Euzenat , J. , Geneves , P. , and Layaida , N . 2012. SPARQL query containment under shi axioms . In Proceedings of the 26th AAAI Conference on Artificial Intelligence (AAAI'12) . AAAI Press. Chekol, M. W., Euzenat, J., Geneves, P., and Layaida, N. 2012. SPARQL query containment under shi axioms. In Proceedings of the 26th AAAI Conference on Artificial Intelligence (AAAI'12). AAAI Press."},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00220-0"},{"key":"e_1_2_2_11_1","volume-title":"Proceedings of the 32nd International Conference on Very Large Data Bases (VLDB'06)","author":"Cohen S.","unstructured":"Cohen , S. , Fadida , I. , Kanza , Y. , Kimelfeld , B. , and Sagiv , Y . 2006. Full disjunctions: Polynomial-delay iterators in action . In Proceedings of the 32nd International Conference on Very Large Data Bases (VLDB'06) . ACM Press, New York, 739--750. Cohen, S., Fadida, I., Kanza, Y., Kimelfeld, B., and Sagiv, Y. 2006. Full disjunctions: Polynomial-delay iterators in action. In Proceedings of the 32nd International Conference on Very Large Data Bases (VLDB'06). ACM Press, New York, 739--750."},{"key":"e_1_2_2_12_1","unstructured":"DBPedia. 2012. DBPedia.org. http:\/\/DBpedia.org\/sparql.  DBPedia. 2012. DBPedia.org. http:\/\/DBpedia.org\/sparql."},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/602220.602222"},{"key":"e_1_2_2_14_1","volume-title":"Proceedings of the 1st International Workshop on Usage Analysis and the Web of Data (USEWOD'11)","author":"Gallego M. A.","unstructured":"Gallego , M. A. , Fernandez , J. D. , Martinez-Prieto , M. A. , and de la Fuente, P. 2011. An empirical study of real-world SPARQL queries . In Proceedings of the 1st International Workshop on Usage Analysis and the Web of Data (USEWOD'11) . Gallego, M. A., Fernandez, J. D., Martinez-Prieto, M. A., and de la Fuente, P. 2011. An empirical study of real-world SPARQL queries. In Proceedings of the 1st International Workshop on Usage Analysis and the Web of Data (USEWOD'11)."},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(00)00078-3"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1809"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807085.1807127"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/1886008.1886032"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.04.009"},{"key":"e_1_2_2_20_1","unstructured":"HM GOVERNMENT. 2012. data.gov.uk.http:\/\/data.gov.uk.  HM GOVERNMENT. 2012. data.gov.uk.http:\/\/data.gov.uk."},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(88)90065-8"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1811"},{"key":"e_1_2_2_23_1","volume-title":"Proceedings of the 31st International Conference on Very Large Data Bases (VLDB'05)","author":"Larson P.-A.","unstructured":"Larson , P.-A. and Zhou , J . 2005. View matching for outer-join views . In Proceedings of the 31st International Conference on Very Large Data Bases (VLDB'05) . ACM Press, New York, 445--456. Larson, P.-A. and Zhou, J. 2005. View matching for outer-join views. In Proceedings of the 31st International Conference on Very Large Data Bases (VLDB'05). ACM Press, New York, 445--456."},{"key":"e_1_2_2_24_1","unstructured":"Lassila O. and Swick R. R. 1999. Resource description framework (RDF) model and syntax. W3C Recommendation. http:\/\/www.w3.org\/TR\/PR-rdf-syntax.  Lassila O. and Swick R. R. 1999. Resource description framework (RDF) model and syntax. W3C Recommendation. http:\/\/www.w3.org\/TR\/PR-rdf-syntax."},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/2367502.2367547"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213572"},{"key":"e_1_2_2_27_1","volume-title":"Proceedings of the International Semantic Web Conference. 421--437","author":"Mallea A.","unstructured":"Mallea , A. , Arenas , M. , Hogan , A. , and Polleres , A . 2011. On blank nodes . In Proceedings of the International Semantic Web Conference. 421--437 . Mallea, A., Arenas, M., Hogan, A., and Polleres, A. 2011. On blank nodes. In Proceedings of the International Semantic Web Conference. 421--437."},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-009-0165-y"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/11926078_3"},{"key":"e_1_2_2_30_1","unstructured":"P\u00e9rez J. Arenas M. and Gutierrez C. 2006b. Semantics of SPARQL. Tech. rep. TR\/DCC-2006-17 Universidad de Chile. http:\/\/users.dcc.uchile.cl\/&sim;jperez\/papers\/sparql.semantics.pdf.  P\u00e9rez J. Arenas M. and Gutierrez C. 2006b. Semantics of SPARQL. Tech. rep. TR\/DCC-2006-17 Universidad de Chile. http:\/\/users.dcc.uchile.cl\/&sim;jperez\/papers\/sparql.semantics.pdf."},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1567274.1567278"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1999299.1999306"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1242572.1242679"},{"key":"e_1_2_2_34_1","unstructured":"Prudhommeaux E. and Seaborne A. 2008. SPARQL query language for RDF. W3C Recommendation. http:\/\/www.w3.org\/TR\/rdf-sparql-query\/.  Prudhommeaux E. and Seaborne A. 2008. SPARQL query language for RDF. W3C Recommendation. http:\/\/www.w3.org\/TR\/rdf-sparql-query\/."},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-88564-1_6"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1804669.1804675"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/11574620_44"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.14778\/1454159.1454227"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1367497.1367578"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.5555\/645502.656100"},{"key":"e_1_2_2_41_1","unstructured":"US GOVERNMENT. 2012. data.gov.http:\/\/www.data.gov.  US GOVERNMENT. 2012. data.gov.http:\/\/www.data.gov."},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453965"},{"key":"e_1_2_2_43_1","volume-title":"Proceedings of the 7th International Conference on Very Large Data Bases (VLDB'81)","author":"Yannakakis M.","year":"1981","unstructured":"Yannakakis , M. 1981 . Algorithms for acyclic database schemes . In Proceedings of the 7th International Conference on Very Large Data Bases (VLDB'81) . 82--94. Yannakakis, M. 1981. Algorithms for acyclic database schemes. In Proceedings of the 7th International Conference on Very Large Data Bases (VLDB'81). 82--94."}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2500130","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2500130","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:34:31Z","timestamp":1750232071000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2500130"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,11]]},"references-count":43,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2013,11]]}},"alternative-id":["10.1145\/2500130"],"URL":"https:\/\/doi.org\/10.1145\/2500130","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,11]]},"assertion":[{"value":"2012-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-12-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}