## 4 Efficient Support of Online Data Publishing
### Phase I: Estimating the Generalization Level  
In this paper, we estimate the generalization level of each quasi-identifier attribute to achieve \(k\)-anonymity over the query results by leveraging the statistical information, such as the histograms that are maintained for query optimization purposes in most commercial database management systems. In general, a histogram on attribute \(A_{i}\) is constructed by dividing the entire value range of \(A_{i}\) into \(w\) disjointed subranges, \(H(A_{i})=\{x_{1},x_{2},\cdots,x_{w}\}\). Each subrange, \(x_{j}\), usually stores \(x_{j}^{s}\), \(x_{j}^{s}\), \(f_{j}\), and \(dv_{j}\). Here, \(x_{j}^{s}\) and \(x_{j}^{s}\) represent the start point and the end point of the subrange \(x_{j}\), respectively. Furthermore, \(f_{j}\) corresponds to the number of tuples whose \(A_{i}\) values lie between \(x_{j}^{s}\) and \(x_{j}^{s}\), and \(dv_{j}\) represents the number of distinct values in \(x_{j}\). Given a query, we first estimate the size of the query result. Estimating the query result size, which is known as a cardinality estimation, has been extensively studied over the past several decades [48; 49; 50; 51; 52; 53]. Although there are many complex algorithms that can provide a very high level of accuracy in a cardinality estimation, our approach uses a solution based on the assumption of attribute value independence. The cardinality estimation in many database management systems indeed relies on a method based on an attribute value independence assumption owing to its simplicity and reasonably good accuracy. For example, PostgreSQL [54], which is a well-known open-source DBMS, assumes that all attributes are mutually independent and maintains one-dimensional histograms [53]. Given a histogram \(H(A_{i})=\{x_{1},x_{2},\cdots,x_{w}\}\) and predicate \(pred_{u}\) involving attribute \(A_{i}\), let \(s_{u}\) be the selectivity ratio associated with \(pred_{u}\). The overall distribution of entire  
Figure 5: Overview of the proposed approach. values of the attribute \(A_{i}\) can be captured by using the histogram \(H(A_{i})\). Furthermore, we assume that attribute values in each subrange of \(H(A_{i})\) are uniformly distributed, which is a common assumption in modern database systems [53]. Then, the selectivity ratio \(s_{u}\) is obtained as follows: For the equality predicate (i.e., \(\sigma_{A_{i}=val}(R)\), where \(val\) denotes any integer value located within the range between \(x_{j}^{s}\) and \(x_{j}^{s}\)), \(s_{u}\) is defined as:  
\[s_{u}=\frac{f_{j}}{|R|}\times\frac{1}{d\sigma_{j}}.\]  
Here, \(|R|\) is the number of tuples in the relation \(R\). For the range predicate (i.e., \(\sigma_{val_{1}\leq A_{i}\leq val_{2}}(R)\), where \(val_{1}\) and \(val_{2}\) are any integer values located within the range of \(x_{j}^{s}\) and \(x_{j}^{s}\)), \(s_{u}\) is defined as:  
\[s_{u}=\frac{f_{j}}{|R|}\times\frac{val_{2}-val_{1}}{x_{j}^{e}-x_{j}^{s}}.\]  
Note that the above equation considers the case in which \(val_{1}\) and \(val_{2}\) are located within the same subrange \(x_{j}\). Let assume the case where \(val_{1}\) and \(val_{2}\) are located in different subranges, \(x_{j}\) and \(x_{j+k}\), respectively. In this case, subranges, \(x_{j+1},x_{j+2},\cdots,x_{j+k-1}\), are fully covered by the range predicate, while subranges, \(x_{j}\) and \(x_{j+k}\), are partially covered. Thus, in this case, the selectivity ratio \(s_{u}\) is computed as:  
\[s_{u} = \left(\frac{f_{j}}{|R|}\ \times\ \frac{x_{j}^{e}-val_{1}}{x_{j}^{e}-x_{j}^ {s}}\right)\ \ +\ \left(\sum_{c=j+1}^{j+k-1}\frac{f_{c}}{|R|}\right)\ \ +\ \left(\frac{f_{j+k}}{|R|}\ \times\ \frac{val_{2}-x_{j+k}^{s}}{x_{j+k}^{e}-x_{j+k}^{s}} \right).\]  
Given a query having \(l\) predicates, \(pred_{1}\), \(pred_{2}\), \(\cdots\), \(pred_{l}\), let \(R_{res}\) be the corresponding result relation.