{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,7]],"date-time":"2026-03-07T16:08:43Z","timestamp":1772899723160,"version":"3.50.1"},"reference-count":62,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2022,11,16]],"date-time":"2022-11-16T00:00:00Z","timestamp":1668556800000},"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":["ACM Trans. Web"],"published-print":{"date-parts":[[2022,11,30]]},"abstract":"<jats:p>Resource Description Framework datasets can be queried using the SPARQL language but are often irregularly structured and incomplete, which may make precise query formulation hard for users. The SPARQL<jats:sup><jats:italic>AR<\/jats:italic><\/jats:sup>language extends SPARQL 1.1 with two operators\u2014APPROX and RELAX\u2014to allow flexible querying over property paths. These operators encapsulate different dimensions of query flexibility, namely, approximation and generalisation, and they allow users to query complex, heterogeneous knowledge graphs without needing to know precisely how the data is structured. Earlier work has described the syntax, semantics, and complexity of SPARQL<jats:sup><jats:italic>AR<\/jats:italic><\/jats:sup>, has demonstrated its practical feasibility, but has also highlighted the need for improving the speed of query evaluation. In the present article, we focus on the design of two optimisation techniques targeted at speeding up the execution of SPARQL<jats:sup><jats:italic>AR<\/jats:italic><\/jats:sup>queries and on their empirical evaluation on three knowledge graphs: LUBM, DBpedia, and YAGO. We show that applying these optimisations can result in substantial improvements in the execution times of longer-running queries (sometimes by one or more orders of magnitude) without incurring significant performance penalties for fast queries.<\/jats:p>","DOI":"10.1145\/3532855","type":"journal-article","created":{"date-parts":[[2022,6,24]],"date-time":"2022-06-24T14:12:02Z","timestamp":1656079922000},"page":"1-44","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Optimisation Techniques for Flexible SPARQL Queries"],"prefix":"10.1145","volume":"16","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5231-5616","authenticated-orcid":false,"given":"Riccardo","family":"Frosini","sequence":"first","affiliation":[{"name":"Knowledge Lab, Birkbeck, University of London, London, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8981-4104","authenticated-orcid":false,"given":"Alexandra","family":"Poulovassilis","sequence":"additional","affiliation":[{"name":"Knowledge Lab, Birkbeck, University of London, London, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3704-1431","authenticated-orcid":false,"given":"Peter T.","family":"Wood","sequence":"additional","affiliation":[{"name":"Knowledge Lab, Birkbeck, University of London, London, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5678-6899","authenticated-orcid":false,"given":"Andrea","family":"Cal\u00ed","sequence":"additional","affiliation":[{"name":"Knowledge Lab, Birkbeck, University of London, London, UK and Oxford-Man Institute, Oxford, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,11,16]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.websem.2009.02.002"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-45563-0_27"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007581"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-88564-1_8"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872822"},{"key":"e_1_3_3_7_2","doi-asserted-by":"crossref","unstructured":"Christian Bizer Richard Cyganiak and Tom Heath. 2007. How to publish Linked Data on the Web. Retrieved from http:\/\/www4.wiwiss.fu-berlin.de\/bizer\/pub\/LinkedDataTutorial\/.","DOI":"10.1145\/1367497.1367760"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2020.12.019"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.4018\/978-1-59904-853-6.ch008"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10844-008-0071-6"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00962923"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70504-8_15"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-45563-0_28"},{"key":"e_1_3_3_14_2","first-page":"176","volume-title":"Proceedings of the KR","author":"Calvanese Diego","year":"2000","unstructured":"Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, and Moshe Y. Vardi. 2000. Containment of conjunctive regular path queries with inverse. In Proceedings of the KR. 176\u2013185."},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/959060.959076"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-018-0528-3"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/1988688.1988736"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.5555\/767141.767147"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00122129"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/2457317.2457352"},{"key":"e_1_3_3_21_2","first-page":"283","volume-title":"Proceedings of the FQAS","author":"Virgilio Roberto De","year":"2015","unstructured":"Roberto De Virgilio, Antonio Maccioni, and Riccardo Torlone. 2015. A unified framework for flexible query answering over heterogeneous data sources. In Proceedings of the FQAS. 283\u2013294."},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10844-008-0070-7"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-21064-8_5"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.24963\/kr.2020\/38"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/1938551.1938575"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1109\/BigData47090.2019.9005466"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/275487.275503"},{"key":"e_1_3_3_28_2","doi-asserted-by":"crossref","unstructured":"Riccardo Frosini. 2017. Flexible Query Processing of SPARQL Queries . PhD Thesis.","DOI":"10.3233\/SW-150206"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.3233\/SW-150206"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0055999"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10472-005-9016-8"},{"key":"e_1_3_3_32_2","unstructured":"S. Harris and A. Seaborne. 2013. SPARQL 1.1 Query Language. W3C Recommendation."},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/1357054.1357203"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1109\/CIMSiM.2010.22"},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-30284-8_53"},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17616-6_34"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85481-4_14"},{"key":"e_1_3_3_38_2","first-page":"31","article-title":"Query relaxation in RDF","author":"Hurtado Carlos A.","year":"2008","unstructured":"Carlos A. Hurtado, Alexandra Poulovassilis, and Peter T. Wood. 2008. Query relaxation in RDF. J. Data Semant. X (2008), 31\u201361.","journal-title":"J. Data Semant."},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02121-3_22"},{"key":"e_1_3_3_40_2","first-page":"174","volume-title":"Proceedings of the VLDB","author":"Ioannidis Y.","year":"1999","unstructured":"Y. Ioannidis and V. Poosala. 1999. Histogram-based approximation of set-valued query-answers. In Proceedings of the VLDB. 174\u2013185."},{"key":"e_1_3_3_41_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2002.994703"},{"key":"e_1_3_3_42_2","first-page":"1","article-title":"A survey on semantic schema discovery","author":"Kellou-Menouer Kenza","year":"2021","unstructured":"Kenza Kellou-Menouer, Nikolaos Kardoulakis, Georgia Troullinou, Zoubida Kedad, Dimitris Plexousakis, and Haridimos Kondylakis. 2021. A survey on semantic schema discovery. VLDB J. (2021), 1\u201336.","journal-title":"VLDB J."},{"key":"e_1_3_3_43_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-76298-0_22"},{"key":"e_1_3_3_44_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-25007-6_1"},{"key":"e_1_3_3_45_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2010.02.002"},{"key":"e_1_3_3_46_2","doi-asserted-by":"publisher","DOI":"10.1145\/3186727"},{"key":"e_1_3_3_47_2","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319864"},{"key":"e_1_3_3_48_2","doi-asserted-by":"publisher","DOI":"10.1145\/1516360.1516386"},{"key":"e_1_3_3_49_2","doi-asserted-by":"crossref","first-page":"601","DOI":"10.1007\/978-3-540-85565-1_74","volume-title":"Knowledge-Based Intelligent Information and Engineering Systems","author":"Meng X.","year":"2008","unstructured":"X. Meng, Z. M. Ma, and L. Yan. 2008. Providing flexible queries over web databases. In Knowledge-Based Intelligent Information and Engineering Systems. Springer, 601\u2013606."},{"key":"e_1_3_3_50_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-76336-9_17"},{"key":"e_1_3_3_51_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-72667-8_6"},{"key":"e_1_3_3_52_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0034705"},{"key":"e_1_3_3_53_2","doi-asserted-by":"publisher","DOI":"10.1145\/1567274.1567278"},{"key":"e_1_3_3_54_2","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594542"},{"key":"e_1_3_3_55_2","doi-asserted-by":"publisher","DOI":"10.1145\/2851613.2851690"},{"key":"e_1_3_3_56_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.websem.2016.08.001"},{"key":"e_1_3_3_57_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17746-0_40"},{"key":"e_1_3_3_58_2","first-page":"37","volume-title":"Proceedings of the URSW","author":"Reddy B. R. K.","year":"2010","unstructured":"B. R. K. Reddy and P. S. Kumar. 2010. Efficient approximate SPARQL querying of web of linked data. In Proceedings of the URSW. 37\u201348."},{"key":"e_1_3_3_59_2","volume-title":"Foundations of SPARQL Query Optimization","author":"Schmidt Michael","year":"2009","unstructured":"Michael Schmidt. 2009. Foundations of SPARQL Query Optimization. Ph.D. Dissertation. Albert-Ludwigs-Universitat Freiburg. Retrieved from http:\/\/www.informatik.uni-freiburg.de\/mschmidt\/docs\/diss_final01122010.pdf."},{"key":"e_1_3_3_60_2","first-page":"625","volume-title":"Proceedings of the VLDB","author":"Theobald M.","year":"2005","unstructured":"M. Theobald, R. Schenkel, and G. Weikum. 2005. An efficient and versatile query engine for TopX search. In Proceedings of the VLDB. 625\u2013636."},{"key":"e_1_3_3_61_2","doi-asserted-by":"publisher","DOI":"10.14778\/2732286.2732293"},{"key":"e_1_3_3_62_2","doi-asserted-by":"publisher","DOI":"10.14778\/2983200.2983201"},{"key":"e_1_3_3_63_2","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247541"}],"container-title":["ACM Transactions on the Web"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3532855","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3532855","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:00:37Z","timestamp":1750186837000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3532855"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,11,16]]},"references-count":62,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,11,30]]}},"alternative-id":["10.1145\/3532855"],"URL":"https:\/\/doi.org\/10.1145\/3532855","relation":{},"ISSN":["1559-1131","1559-114X"],"issn-type":[{"value":"1559-1131","type":"print"},{"value":"1559-114X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,11,16]]},"assertion":[{"value":"2021-09-21","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-06-14","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-11-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}