Towards Answering Star-Join Queries Under Central Differential Privacy

doi:10.3778/j.issn.1002-8331.2410-0121

Abstract

Abstract: Star-Join queries have attracted extensive attention from researchers in addressing multi-relational table join problems with foreign key constraints. Existing multi-relational table query algorithms with foreign key constraints have two limitations: firstly, they can only handle Star-Join query data for low-dimensional relational table join problems； secondly, due to the processing of the SQL statements of queries, the proposed algorithms need to consider the functional dependencies between the table attributes involved in the query statements. To address the shortcomings of existing algorithms, an effective Star-Join query algorithm satisfying differential privacy, namely SJFD (star join function dependence), is proposed. The algorithm fully leverages the characteristics of the star schema and designs an input-side perturbation mechanism. It takes the predicate value domain of the Star-Join query as the perturbation value domain and filters each dimension table through the perturbed predicates. The goal of reducing the sensitivity of Star-Join queries when processing high-dimensional relational table join problems is achieved through two aspects： the functional dependencies within dimension tables and the value domain coverage relationships between tables. The SJFD algorithm is compared with four existing algorithms on the SSB (star schema benchmark) dataset, and the experimental results show that its query response performance is superior to that of similar algorithms.

Key words: Star-Join query, , differential privacy, functional dependency, fact table, dimensional table

摘要： Star-Join查询在具有外键约束的多关系表连接问题上已经引起了研究者的广泛关注。现有的带外键约束的多关系表查询算法存在两个缺陷：首先现有算法仅能处理低维关系表连接问题上的Star-Join查询数据，其次由于对查询的SQL语句进行处理，因此所提算法需要考虑到查询语句所涉及到的表属性之间存在函数依赖关系。针对现有算法的不足，提出一种有效且满足差分隐私的Star-Join查询算法SJFD（star join function dependence）。该算法充分利用星形模型的特点，设计了一种从输入端进行扰动的机制SJFD。该算法以星形连接查询的谓词值域作为扰动值域，通过扰动后的谓词来过滤每个维表。通过维表内部之间的函数依赖关系和表与表之间的值域覆盖关系两个方面来达到降低在处理高维关系表连接问题上的Star-Join查询的敏感度目的。SJFD算法与现有的四个算法在SSB（star schema benchmark）数据集上分别进行比较，实验结果表明其响应查询算法优于同类算法。

关键词: 星形连接查询, 差分隐私, 函数依赖, 事实表, 维度表

ZHANG Xiaojian, CHEN Xu, WANG Haofeng. Towards Answering Star-Join Queries Under Central Differential Privacy[J]. Computer Engineering and Applications, 2025, 61(24): 281-292.

张啸剑, 陈旭, 王浩锋. 基于中心化差分隐私的星形连接查询方法[J]. 计算机工程与应用, 2025, 61(24): 281-292.

References

[1] DWORK C, ROTH A. The algorithmic foundations of differential privacy[J]. Foundations and Trends? in Theoretical Computer Science, 2014, 9(3/4): 211-407.
[2] LIEW S P, TAKAHASHI T, TAKAGI S, et al. Network shuffling: privacy amplification via random walks[C]//Proceedings of the 2022 International Conference on Management of Data. New York: ACM, 2022: 773-787.
[3] QARDAJI W, YANG W N, LI N H. Understanding hierarchical methods for differentially private histograms[J]. Proceedings of the VLDB Endowment, 2013, 6(14): 1954-1965.
[4] TAKAGI S, TAKAHASHI T, CAO Y, et al. P3GM: private high-dimensional data release via privacy preserving phased generative model[C]//Proceedings of the 2021 IEEE 37th International Conference on Data Engineering. Piscataway: IEEE, 2021: 169-180.
[5] WANG T H, LOPUHA?-ZWAKENBERG M, LI Z T, et al. Locally differentially private frequency estimation with consistency[J]. arXiv:1905.08320, 2019.
[6] XU J, ZHANG Z J, XIAO X K, et al. Differentially private histogram publication[J]. The VLDB Journal, 2013, 22(6): 797-822.
[7] ZHENG S Y, CAO Y, YOSHIKAWA M. Secure shapley value for cross-silo federated learning (technical report)[J]. arXiv:2209.04856, 2022.
[8] KOTSOGIANNIS I, TAO Y C, HE X, et al. PrivateSQL: a differentially private SQL query engine[J]. Proceedings of the VLDB Endowment, 2019, 12(11): 1371-1384.
[9] TAO Y C, HE X, MACHANAVAJJHALA A, et al. Computing local sensitivities of counting queries with joins[C]//Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2020: 479-494.
[10] DONG W, FANG J R, YI K, et al. R2T: instance-optimal truncation for differentially private query evaluation with foreign keys[C]//Proceedings of the 2022 International Conference on Management of Data. New York: ACM, 2022: 759-772.
[11] FU C C, LI H, LOU J, et al. DP-starJ: a differential private scheme towards analytical star-join queries[J]. Proceedings of the ACM on Management of Data, 2023, 1(4): 1-24.
[12] NISSIM K, RASKHODNIKOVA S, SMITH A. Smooth sensitivity and sampling in private data analysis[C]//Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing. New York: ACM, 2007: 75-84.
[13] DONG W, YI K. Residual sensitivity for differentially private multi-way joins[C]//Proceedings of the 2021 International Conference on Management of Data. New York: ACM, 2021: 432-444.
[14] CAI K T, XIAO X K, CORMODE G. PrivLava: synthesizing relational data with foreign keys under differential privacy[J]. Proceedings of the ACM on Management of Data, 2023, 1(2): 1-25.
[15] NARAYAN A, HAEBERLEN A. DJoin: differentially private join queries over distributed databases[C]//Proceedings of the USENIX Symposium on Operating Systems Design and Implementation, 2012.
[16] PEI J, AMER-YAHIA S, JOHNSON N, et al. Towards practical differential privacy for SQL queries[J]. Proceedings of the VLDB Endowment, 2018, 11(5): 526-539.
[17] DONG W, YI K. Residual sensitivity for differentially private multi-way joins[C]//Proceedings of the 2021 International Conference on Management of Data. New York: ACM, 2021: 432-444.
[18] BARAK B, CHAUDHURI K, DWORK C, et al. Privacy, accuracy, and consistency too: a holistic solution to contingency table release[C]//Proceedings of the Twenty-Sixth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems. New York: ACM, 2007: 273-282.
[19] BLASIOK J, BUN M, NIKOLOV A, et al. Towards instance-optimal private query release[C]//Proceedings of the Thirt-ieth Annual ACM-SIAM Symposium on Discrete Algorithms. New York: ACM, 2019: 2480-2497.
[20] DAY W Y, LI N H, LYU M. Publishing graph degree distribution with node differential privacy[C]//Proceedings of the 2016 International Conference on Management of Data. New York: ACM, 2016: 123-138.
[21] HARDT M, LIGETT K, MCSHERRY F. A simple and practical algorithm for differentially private data release[C]//Proceedings of the 26th International Conference on Neural Information Processing Systems. New York: ACM, 2012: 2339-2347.
[22] LI C, MIKLAU G, HAY M, et al. The matrix mechanism: optimizing linear counting queries under differential privacy[J]. The VLDB Journal, 2015, 24(6): 757-781.
[23] NIKOLOV A, TALWAR K, ZHANG L. The geometry of differential privacy: the sparse and approximate cases[C]//Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing. New York: ACM, 2013: 351-360.
[24] QARDAJI W, YANG W N, LI N H. PriView: practical differentially private release of marginal contingency tables[C]//Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2014: 1435-1446.
[25] XIAO X K, WANG G Z, GEHRKE J. Differential privacy via wavelet transforms[J]. IEEE Transactions on Knowledge and Data Engineering, 2011, 23(8): 1200-1214.
[26] ZHANG X J, CHEN R, XU J L, et al. Towards accurate histogram publication under differential privacy[C]//Proceedings of the 2014 SIAM International Conference on Data Mining. Society for Industrial and Applied Mathematics, 2014: 587-595.
[27] YAO A C. Protocols for secure computations[C]//Proceedings of the 23rd Annual Symposium on Foundations of Computer Science. Piscataway: IEEE, 2008: 160-164.
[28] O’NEIL P E, O’NEIL E J, CHEN X. The star schema benchmark (SSB)[J]. Pat, 2007, 200: 50.