{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,3]],"date-time":"2026-07-03T16:21:36Z","timestamp":1783095696629,"version":"3.54.6"},"reference-count":50,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2023,6,13]],"date-time":"2023-06-13T00:00:00Z","timestamp":1686614400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100012338","name":"the Alan Turing Institute.","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100012338","id-type":"DOI","asserted-by":"crossref"}]},{"name":"the UKRI Prosperity Partnership Scheme","award":["the EPSRC Grant EP\/V056883\/1"],"award-info":[{"award-number":["the EPSRC Grant EP\/V056883\/1"]}]},{"name":"the National Research Foundation, Singapore"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2023,6,13]]},"abstract":"<jats:p>Answering database queries while preserving privacy is an important problem that has attracted considerable research attention in recent years. A canonical approach to this problem is to use synthetic data. That is, we replace the input database R with a synthetic database R* that preserves the characteristics of R, and use R* to answer queries. Existing solutions for relational data synthesis, however, either fail to provide strong privacy protection, or assume that R contains a single relation. In addition, it is challenging to extend the existing single-relation solutions to the case of multiple relations, because they are unable to model the complex correlations induced by the foreign keys. Therefore, multi-relational data synthesis with strong privacy guarantees is an open problem.<\/jats:p>\n          <jats:p>In this paper, we address the above open problem by proposing PrivLava, the first solution for synthesizing relational data with foreign keys under differential privacy, a rigorous privacy framework widely adopted in both academia and industry. The key idea of PrivLava is to model the data distribution in R using graphical models, with latent variables included to capture the inter-relational correlations caused by foreign keys. We show that PrivLava supports arbitrary foreign key references that form a directed acyclic graph, and is able to tackle the common case when R contains a mixture of public and private relations. Extensive experiments on census data sets and the TPC-H benchmark demonstrate that PrivLava significantly outperforms its competitors in terms of the accuracy of aggregate queries processed on the synthetic data.<\/jats:p>","DOI":"10.1145\/3589287","type":"journal-article","created":{"date-parts":[[2023,6,20]],"date-time":"2023-06-20T20:26:45Z","timestamp":1687292805000},"page":"1-25","source":"Crossref","is-referenced-by-count":22,"title":["PrivLava: Synthesizing Relational Data with Foreign Keys under Differential Privacy"],"prefix":"10.1145","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0009-0006-8278-716X","authenticated-orcid":false,"given":"Kuntai","family":"Cai","sequence":"first","affiliation":[{"name":"National University of Singapore, Singapore, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0914-4580","authenticated-orcid":false,"given":"Xiaokui","family":"Xiao","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0698-0922","authenticated-orcid":false,"given":"Graham","family":"Cormode","sequence":"additional","affiliation":[{"name":"University of Warwick, Coventry, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,6,20]]},"reference":[{"key":"e_1_2_2_1_1","unstructured":"2022. TPC-H benchmark homepage. https:\/\/www.tpc.org\/tpch\/."},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2012.80"},{"key":"e_1_2_2_3_1","volume-title":"Proceedings of the 35th International Conference on Machine Learning. 394--403","author":"Balle Borja","year":"2018","unstructured":"Borja Balle and Yu-Xiang Wang. 2018. Improving the gaussian mechanism for differential privacy: Analytical calibration and optimal denoising. In Proceedings of the 35th International Conference on Machine Learning. 394--403."},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.14778\/3055330.3055334"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.14778\/3291264.3291274"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407854"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.14778\/3055540.3055542"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.152"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476272"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2304.04545"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.18128\/D020.V7.3"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2004.04.007"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196906"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2274576.2274608"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/773153.773173"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517844"},{"key":"e_1_2_2_17_1","doi-asserted-by":"crossref","unstructured":"Cynthia Dwork Frank McSherry Kobbi Nissim and Adam Smith. 2006. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography. 265--284.","DOI":"10.1007\/11681878_14"},{"key":"e_1_2_2_18_1","doi-asserted-by":"crossref","unstructured":"Cynthia Dwork Aaron Roth et al. 2014. The algorithmic foundations of differential privacy. Foundations and Trends\u00ae in Theoretical Computer Science 9 3--4 (2014) 211--407.","DOI":"10.1561\/0400000042"},{"key":"e_1_2_2_19_1","volume-title":"Proceedings of the 31th International Conference on Machine Learning. 1170--1178","author":"Gaboardi Marco","year":"2014","unstructured":"Marco Gaboardi, Emilio Jes\u00fas Gallego Arias, Justin Hsu, Aaron Roth, and Zhiwei Steven Wu. 2014. Dual query: Practical private query release for high dimensional data. In Proceedings of the 31th International Conference on Machine Learning. 1170--1178."},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.14778\/3467861.3467876"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457242"},{"key":"e_1_2_2_22_1","unstructured":"Moritz Hardt Katrina Ligett and Frank McSherry. 2012. A simple and practical algorithm for differentially private data release. In Advances in Neural Information Processing Systems 25. 2348--2356."},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3187009.3177733"},{"key":"e_1_2_2_24_1","volume-title":"Proceedings of the 7th International Conference on Learning Representations.","author":"Jordon James","year":"2019","unstructured":"James Jordon, Jinsung Yoon, and Mihaela Van Der Schaar. 2019. PATE-GAN: Generating synthetic data with differential privacy guarantees. In Proceedings of the 7th International Conference on Learning Representations."},{"key":"e_1_2_2_25_1","volume-title":"Tyler Simko, and Kosuke Imai.","author":"Kenny Christopher T","year":"2021","unstructured":"Christopher T Kenny, Shiro Kuriwaki, Cory McCartan, Evan TR Rosenman, Tyler Simko, and Kosuke Imai. 2021. The use of differential privacy for census data and its impact on redistricting: The case of the 2020 US Census. Science Advances 7, 41 (2021), eabk3283."},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342274"},{"key":"e_1_2_2_27_1","volume-title":"Disclosure avoidance techniques at the US Census Bureau: Current practices and research","author":"Lauger Amy","year":"2014","unstructured":"Amy Lauger, Billy Wisniewski, and Laura McKenna. 2014. Disclosure avoidance techniques at the US Census Bureau: Current practices and research. Center for Disclosure Avoidance Research, US Census Bureau (2014)."},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732269.2732271"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-015-0398-x"},{"key":"e_1_2_2_30_1","volume-title":"Proceedings of the 17th International Conference on Extending Database Technology. 475--486","author":"Li Haoran","year":"2014","unstructured":"Haoran Li, Li Xiong, and Xiaoqian Jiang. 2014. Differentially private synthesization of multi-dimensional data using copula functions. In Proceedings of the 17th International Conference on Extending Database Technology. 475--486."},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2014.6816689"},{"key":"e_1_2_2_32_1","volume-title":"Proceedings of the 2007 FCSM Research Conference.","author":"Massell Paul M","year":"2007","unstructured":"Paul M Massell and Jeremy M Funk. 2007. Recent developments in the use of noise for protecting magnitude data tables: Balancing to improve data quality and rounding that preserves protection. In Proceedings of the 2007 FCSM Research Conference."},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.14778\/3231751.3231769"},{"key":"e_1_2_2_35_1","volume-title":"Proceedings of the 36th International Conference on Machine Learning. 4435--4444","author":"McKenna Ryan","year":"2019","unstructured":"Ryan McKenna, Daniel Sheldon, and Gerome Miklau. 2019. Graphical-model based estimation and inference for differential privacy. In Proceedings of the 36th International Conference on Machine Learning. 4435--4444."},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559850"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020487"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213876"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/130938943"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.14778\/3231751.3231757"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732296.2732300"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2588575"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.18128\/D010.V12.0"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389762"},{"key":"e_1_2_2_45_1","volume-title":"et al","author":"Wainwright Martin J","year":"2008","unstructured":"Martin J Wainwright, Michael I Jordan, et al . 2008. Graphical models, exponential families, and variational inference. Foundations and Trends\u00ae in Machine Learning 1, 1--2 (2008), 1--305."},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319891"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.2478\/popets-2020-0025"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIFS.2017.2737966"},{"key":"e_1_2_2_49_1","unstructured":"Lei Xu Maria Skoularidou Alfredo Cuesta-Infante and Kalyan Veeramachaneni. 2019. Modeling tabular data using conditional GAN. In Advances in Neural Information Processing Systems 32. 7333--7343."},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3134428"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882928"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3589287","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3589287","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:48:54Z","timestamp":1750182534000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3589287"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,13]]},"references-count":50,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,6,13]]}},"alternative-id":["10.1145\/3589287"],"URL":"https:\/\/doi.org\/10.1145\/3589287","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6,13]]}}}