  Star-join query is the fundamental task in data warehouse and has wide
applications in On-line Analytical Processing (OLAP) scenarios. Due to the
large number of foreign key constraints and the asymmetric effect in the
neighboring instance between the fact and dimension tables, even those latest
DP efforts specifically designed for join, if directly applied to star-join
query, will suffer from extremely large estimation errors and expensive
computational cost. In this paper, we are thus motivated to propose DP-starJ, a
novel Differentially Private framework for star-Join queries. DP-starJ consists
of a series of strategies tailored to specific features of star-join, including
1) we unveil the different effect of fact and dimension tables on the
neighboring database instances, and accordingly revisit the definitions
tailored to different cases of star-join; 2) we propose Predicate Mechanism
(PM), which utilizes predicate perturbation to inject noise into the join
procedure instead of the results; 3) to further boost the robust performance,
we propose a DP-compliant star-join algorithm for various types of star-join
tasks based on PM. We provide both theoretical analysis and empirical study,
which demonstrate the superiority of the proposed methods over the
state-of-the-art solutions in terms of accuracy, efficiency, and scalability.

Cryptography and Security;Databases