{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,4]],"date-time":"2026-05-04T10:21:55Z","timestamp":1777890115891,"version":"3.51.4"},"reference-count":31,"publisher":"SAGE Publications","issue":"3","license":[{"start":{"date-parts":[[2024,5,14]],"date-time":"2024-05-14T00:00:00Z","timestamp":1715644800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SW"],"published-print":{"date-parts":[[2024,5,14]]},"abstract":"<jats:p>Differential privacy is a framework that provides formal tools to develop algorithms to access databases and answer statistical queries with quantifiable accuracy and privacy guarantees. The notions of differential privacy are defined independently of the data model and the query language at steak. Most differential privacy results have been obtained on aggregation queries such as counting or finding maximum or average values, and on grouping queries over aggregations such as the creation of histograms. So far, the data model used by the framework research has typically been the relational model and the query language SQL. However, effective realizations of differential privacy for SQL queries that required joins had been limited. This has imposed severe restrictions on applying differential privacy in RDF knowledge graphs and SPARQL queries. By the simple nature of RDF data, most useful queries accessing RDF graphs will require intensive use of joins. Recently, new differential privacy techniques have been developed that can be applied to many types of joins in SQL with reasonable results. This opened the question of whether these new results carry over to RDF and SPARQL. In this paper we provide a positive answer to this question by presenting an algorithm that can answer counting queries over a large class of SPARQL queries that guarantees differential privacy, if the RDF graph is accompanied with semantic information about its structure. We have implemented our algorithm and conducted several experiments, showing the feasibility of our approach for large graph databases. Our aim has been to present an approach that can be used as a stepping stone towards extensions and other realizations of differential privacy for SPARQL and RDF.<\/jats:p>","DOI":"10.3233\/sw-233474","type":"journal-article","created":{"date-parts":[[2023,12,12]],"date-time":"2023-12-12T11:42:11Z","timestamp":1702381331000},"page":"745-773","source":"Crossref","is-referenced-by-count":1,"title":["Differential privacy and SPARQL"],"prefix":"10.1177","volume":"15","author":[{"given":"Carlos","family":"Buil-Aranda","sequence":"first","affiliation":[{"name":"Departamento de Inform\u00e1tica, Universidad T\u00e9cnica Federico Santa Mar\u00eda and IMFD Chile, Avda Espa\u00f1a 1680, Valpara\u00edso, Chile"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jorge","family":"Lobo","sequence":"additional","affiliation":[{"name":"ICREA and Universitat Pompeu Fabra, c\/Roc Boronat 148, Barcelona, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Federico","family":"Olmedo","sequence":"additional","affiliation":[{"name":"Departamento de Ciencias de la Computaci\u00f3n, Universidad de Chile and IMFD, Beauchef 851, Santiago, Chile"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","reference":[{"key":"10.3233\/SW-233474_ref1","doi-asserted-by":"crossref","unstructured":"G.\u00a0Alu\u00e7, O.\u00a0Hartig, M.T.\u00a0\u00d6zsu and K.\u00a0Daudjee, Diversified stress testing of RDF data management systems, in: International Semantic Web Conference, Springer, 2014, pp.\u00a0197\u2013212.","DOI":"10.1007\/978-3-319-11964-9_13"},{"key":"10.3233\/SW-233474_ref2","unstructured":"M.\u00a0Arapinis, D.\u00a0Figueira and M.\u00a0Gaboardi, Sensitivity of counting queries, in: 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11\u201315, 2016, Rome, Italy, I.\u00a0Chatzigiannakis, M.\u00a0Mitzenmacher, Y.\u00a0Rabani and D.\u00a0Sangiorgi, eds, LIPIcs, Vol.\u00a055, Schloss Dagstuhl\u00a0\u2013 Leibniz-Zentrum f\u00fcr Informatik, 2016, pp.\u00a0120\u2013112013."},{"key":"10.3233\/SW-233474_ref3","doi-asserted-by":"publisher","DOI":"10.1145\/2422436.2422449"},{"key":"10.3233\/SW-233474_ref4","doi-asserted-by":"publisher","DOI":"10.1145\/3308558.3313472"},{"key":"10.3233\/SW-233474_ref5","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465304"},{"key":"10.3233\/SW-233474_ref6","unstructured":"R.\u00a0Cyganiak, D.\u00a0Wood and M.\u00a0Lanthaler, RDF 1.1 Concepts and Abstract Syntax, 2014."},{"key":"10.3233\/SW-233474_ref7","doi-asserted-by":"crossref","unstructured":"R.\u00a0Delanaux, A.\u00a0Bonifati, M.-C.\u00a0Rousset and R.\u00a0Thion, Query-based linked data anonymization, in: International Semantic Web Conference, Springer, 2018, pp.\u00a0530\u2013546.","DOI":"10.1007\/978-3-030-00671-6_31"},{"key":"10.3233\/SW-233474_ref8","doi-asserted-by":"publisher","DOI":"10.1145\/3366423.3380265"},{"key":"10.3233\/SW-233474_ref9","doi-asserted-by":"crossref","unstructured":"C.\u00a0Dwork, Differential privacy, in: 33rd International Colloquium on Automata, Languages and Programming, Part II (ICALP 2006), Lecture Notes in Computer Science, Vol.\u00a04052, Springer Verlag, 2006, pp.\u00a01\u201312, https:\/\/www.microsoft.com\/en-us\/research\/publication\/differential-privacy\/. ISBN 3-540-35907-9.","DOI":"10.1007\/11787006_1"},{"key":"10.3233\/SW-233474_ref10","doi-asserted-by":"crossref","unstructured":"C.\u00a0Dwork, Differential privacy: A survey of results, in: International Conference on Theory and Applications of Models of Computation, Springer, 2008, pp.\u00a01\u201319.","DOI":"10.1007\/978-3-540-79228-4_1"},{"key":"10.3233\/SW-233474_ref11","doi-asserted-by":"crossref","unstructured":"C.\u00a0Dwork, K.\u00a0Kenthapadi, F.\u00a0McSherry, I.\u00a0Mironov and M.\u00a0Naor, Our data, ourselves: Privacy via distributed noise generation, in: Annual International Conference on the Theory and Applications of Cryptographic Techniques, Springer, 2006, pp.\u00a0486\u2013503.","DOI":"10.1007\/11761679_29"},{"issue":"3\u20134","key":"10.3233\/SW-233474_ref12","first-page":"211","article-title":"The algorithmic foundations of differential privacy","volume":"9","author":"Dwork","year":"2014","journal-title":"Foundations and Trends\u00ae in Theoretical Computer Science"},{"key":"10.3233\/SW-233474_ref13","unstructured":"B.C.\u00a0Grau and E.V.\u00a0Kostylev, Logical foundations of privacy-preserving publishing of linked data, in: Thirtieth AAAI Conference on Artificial Intelligence, 2016."},{"key":"10.3233\/SW-233474_ref14","doi-asserted-by":"publisher","DOI":"10.1145\/1055558.1055573"},{"key":"10.3233\/SW-233474_ref15","doi-asserted-by":"publisher","DOI":"10.1016\/j.websem.2021.100696"},{"key":"10.3233\/SW-233474_ref17","unstructured":"B.\u00a0Heitmann, F.\u00a0Hermsen and S.\u00a0Decker, k\u00a0\u2013 RDF-neighbourhood anonymity: Combining structural and attribute-based anonymisation for linked data, in: PrivOn ISWC, 2017."},{"key":"10.3233\/SW-233474_ref18","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-30793-6_15"},{"issue":"5","key":"10.3233\/SW-233474_ref19","doi-asserted-by":"publisher","first-page":"526","DOI":"10.1145\/3187009.3177733","article-title":"Towards practical differential privacy for SQL queries","volume":"11","author":"Johnson","year":"2018","journal-title":"Proceedings of the VLDB Endowment"},{"key":"10.3233\/SW-233474_ref20","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989345"},{"key":"10.3233\/SW-233474_ref21","doi-asserted-by":"crossref","unstructured":"N.\u00a0Li, T.\u00a0Li and S.\u00a0Venkatasubramanian, t-Closeness: Privacy beyond k-anonymity and l-diversity, in: Data Engineering, 2007. ICDE 2007. IEEE 23rd International Conference on, IEEE, 2007, pp.\u00a0106\u2013115.","DOI":"10.1109\/ICDE.2007.367856"},{"key":"10.3233\/SW-233474_ref22","doi-asserted-by":"crossref","unstructured":"N.\u00a0Li, W.\u00a0Qardaji, D.\u00a0Su, Y.\u00a0Wu and W.\u00a0Yang, Membership privacy: A unifying framework for privacy definitions, in: Proceedings of the 2013 ACM SIGSAC Conference on Computer & Communications Security, ACM, 2013, pp.\u00a0889\u2013900.","DOI":"10.1145\/2508859.2516686"},{"key":"10.3233\/SW-233474_ref23","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.1"},{"key":"10.3233\/SW-233474_ref24","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559850"},{"issue":"1","key":"10.3233\/SW-233474_ref26","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1145\/234313.234327","article-title":"Randomized algorithms","volume":"28","author":"Motwani","year":"1996","journal-title":"ACM Computing Surveys (CSUR)"},{"key":"10.3233\/SW-233474_ref27","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250803"},{"key":"10.3233\/SW-233474_ref29","doi-asserted-by":"crossref","unstructured":"J.\u00a0P\u00e9rez, M.\u00a0Arenas and C.\u00a0Gutierrez, Semantics and complexity of SPARQL, TODS 34(3) (2009), 16.","DOI":"10.1145\/1567274.1567278"},{"issue":"8","key":"10.3233\/SW-233474_ref30","doi-asserted-by":"publisher","first-page":"637","DOI":"10.14778\/2732296.2732300","article-title":"Calibrating data to sensitivity in private data analysis: A platform for differentially-private analysis of weighted datasets","volume":"7","author":"Proserpio","year":"2014","journal-title":"Proceedings of the VLDB Endowment"},{"key":"10.3233\/SW-233474_ref31","doi-asserted-by":"crossref","unstructured":"F.\u00a0Radulovic, R.\u00a0Garc\u00eda Castro and A.\u00a0G\u00f3mez-P\u00e9rez, Towards the Anonymisation of RDF Data, 2015.","DOI":"10.18293\/SEKE2015-167"},{"key":"10.3233\/SW-233474_ref32","doi-asserted-by":"publisher","DOI":"10.1145\/3105831.3105838"},{"issue":"05","key":"10.3233\/SW-233474_ref33","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1142\/S0218488502001648","article-title":"k-Anonymity: A model for protecting privacy","volume":"10","author":"Sweeney","year":"2002","journal-title":"International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems"},{"issue":"10","key":"10.3233\/SW-233474_ref34","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1145\/2629489","article-title":"Wikidata: A free collaborative knowledgebase","volume":"57","author":"Vrande\u010di\u0107","year":"2014","journal-title":"Communications of the ACM"}],"container-title":["Semantic Web"],"original-title":[],"link":[{"URL":"https:\/\/content.iospress.com\/download?id=10.3233\/SW-233474","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T05:27:10Z","timestamp":1777613230000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/full\/10.3233\/SW-233474"}},"subtitle":[],"editor":[{"given":"Michel","family":"Dumontier","sequence":"additional","affiliation":[{"name":"Maastricht University, The Netherlands"}],"role":[{"role":"editor","vocabulary":"crossref"}]},{"given":"Sabrina","family":"Kirrane","sequence":"additional","affiliation":[{"name":"Vienna University of Economics and Business, Austria"}],"role":[{"role":"editor","vocabulary":"crossref"}]},{"given":"Oshani","family":"Seneviratne","sequence":"additional","affiliation":[{"name":"Rensselaer Polytechnic Institute, USA"}],"role":[{"role":"editor","vocabulary":"crossref"}]},{"given":"Michel","family":"Dumontier","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]},{"given":"Sabrina","family":"Kirrane","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]},{"given":"Oshani","family":"Seneviratne","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2024,5,14]]},"references-count":31,"journal-issue":{"issue":"3"},"URL":"https:\/\/doi.org\/10.3233\/sw-233474","relation":{},"ISSN":["2210-4968","1570-0844"],"issn-type":[{"value":"2210-4968","type":"electronic"},{"value":"1570-0844","type":"print"}],"subject":[],"published":{"date-parts":[[2024,5,14]]}}}