# Sensitivity Estimation for Differentially Private Query Processing
## 4 Sensitivity Estimation for Join Queries
### Limitation of Existing Sensitivity Measures  
This subsection is derived from the previous sections. Prior to presenting our sensitivity estimation methods, we first revisit existing exact sensitivity computation methods in previous work. For instance, the sensitivity of \"SELECT Count(*) FROM data WHERE Salary \(>\) 5000;\" is 1, as modifying one record affects the result by, at most, 1. However, join queries present greater complexity, since a single record change may significantly impact the query results. Consider query \(q=Count(R_{1}(A,B)\Join R_{2}(B,C)\Join R_{3}(C,D))\) on the relations shown in Figure 2; calculating its sensitivity while maintaining privacy, accuracy, and efficiency is challenging. Current solutions like ES and RS use the smooth upper bound of local sensitivity, yet they still face accuracy and efficiency limitations.  
A join query \(q=Count(R_{1}(A,B)\bigstar R_{2}(B,C)\bigstar R_{3}(C,D))\) is shown in Figure 2. ES and RS use different ways to compute the upper bound of the local sensitivity when deleting or inserting a tuple into the relations.  
(1) ES calculates the upper bound based on the maximum frequency of each join attribute as follows:  
\[max(mf(R_{1}.B)\cdot mf(R_{2}.C)\] \[mf(R_{1}.B)\cdot mf(R_{3}.C)\] \[mf(R_{2}.B)\cdot mf(R_{3}.C))\]  
Here, \(mf(X)\) denotes the most-frequent value frequency of attribute \(X\). The product \(mf(R_{1}.B)\cdot mf(R_{2}.C)\) gives the upper bound for attribute \(C\)'s frequency in \(R_{1}\bigstar R_{2}\). The worst-case sensitivity occurs when each tuple in \(R_{2}\) with the most frequent value for \((R_{2}.C)\) also contains the attribute value \((R_{2}.B)\), matching the most frequent value of \((R_{1}.B)\). However, as shown in Figure 2, reality often differs from this worst-case scenario. Here, \((R_{1}.B)\)'s most frequent value \(b_{1}\) doesn't match the most frequent value \(c_{2}\) of \((R_{2}.C)\). Therefore, the upper bound is much higher than the actual influence of inserting or deleting a tuple from \(R_{3}\).  
(2) RS calculates the upper bound of the local sensitivity using a list of group-by queries. For example, to compute the impact of adding one tuple from \(R_{3}\) on the query result, RS derives a statistic called \"maximum boundary\" for the residual query \(R_{1}\bigstar R_{2}\) of \(q\), which means the maximum frequency of attribute \(R_{2}.C\) in \(R_{1}\bigstar R_{2}\). Since \(R_{2}.C\) can join with \(R_{3}\), the maximum boundary of \(R_{1}\bigstar R_{2}\) determines the maximum influence of adding a tuple to \(R_{3}\). The boundary value is obtained through the following query:  
\(Q_{1}\): SELECT MAX(count) from (SELECT R2.C, COUNT(*) from R1,R2 where R1.B=R2.B GROUP BY R2.C) as T;  
RS provides more accurate sensitivity estimates for \(R_{3}\) tuple modifications by accounting for the actual join results of \(R_{1}\bigstar R_{2}\). However, this approach remains computationally expensive due to the join and group-by operations required. The cost escalates further when considering tuple modifications across all tables in join query \(q\), necessitating multiple group-by queries, like \(Q_{1}\). The results in [11] show that RS increases query processing time by \(10\times\) compared to ES, making it impractical for time-sensitive applications.