Query Rewriting-Based View Generation for Efficient Multi-Relation Multi-Query with Differential Privacy

Xinglin Du, Peng Tang, Rui Chen, Ning Wang, Chengyu Hu, Shanqing GuoEDBT 2025 · OpenReview

Abstract

Differential Privacy (DP) provides strong privacy guarantees for database queries but often suffers from significant utility loss in multi-query scenarios due to privacy budget exhaustion. This paper introduces ViewRewrite, a novel system that mitigates "view proliferation"—the excessive creation of private views for complex nested queries. By applying algebraic query rewriting, ViewRewrite transforms diverse SQL queries into a compact, unified set of views. Experimental results on TPC-H and Census datasets demonstrate that ViewRewrite maintains a constant number of views regardless of workload size, achieving significantly higher accuracy and faster execution than state-of-the-art systems like PrivateSQL.

Introduction

Differential Privacy (DP) has become the standard for protecting individual privacy in data analysis. However, implementing DP for complex, multi-relation SQL workloads remains challenging. Each query consumes a portion of a finite "privacy budget" ($ε$). In systems that answer queries using private synopses (views), complex nested queries often trigger the creation of many specialized views. This "view proliferation" leads to high noise levels and rapid budget depletion, rendering the data analysis ineffective for large workloads.

The Challenge of View Proliferation

Existing solutions like PrivateSQL attempt to solve this by creating private views to answer multiple queries. However, these systems are sensitive to minor variations in subquery filters. For instance, two queries differing only in a WHERE clause threshold might require two distinct private views. As the number of queries grows, the number of views grows linearly, causing the privacy budget to be spread too thin and destroying data utility.

The ViewRewrite System

The core innovation of ViewRewrite is a Query Rewriting module that optimizes SQL structures to minimize the required number of private views.

1. Query Classification

The system first categorizes incoming queries into distinct types, including Correlated Nested, Non-Correlated Nested, and Derived Table queries. This classification allows the system to apply targeted rewriting rules for each structure.

Classification of query types handled by the ViewRewrite system.

2. Algebraic Rewriting and Predicate Pushing

Instead of simple syntactic changes, ViewRewrite uses algebraic transformations to "push down" predicates and merge subqueries. The goal is to decouple filters from the underlying views. By moving subquery filters to the outer query layer, a single, broader private view can serve a wide variety of queries with different filtering criteria.

Example of algebraic rewriting for a derived table query, demonstrating how filter conditions are moved to allow view sharing.

3. DP-Aware Constraints and Rewrite Traps

Standard SQL optimization techniques often use DISTINCT or specific joins that can be problematic under DP due to sensitivity issues. ViewRewrite avoids these "rewrite traps" by using GROUP BY and aggregation functions that maintain query equivalence without violating DP constraints. It also employs COALESCE and left outer joins to ensure that the rewritten logic remains identical to the original query, even when handling null values or empty join results.

Evaluation and Results

The authors evaluated ViewRewrite using the TPC-H benchmark, U.S. Census data, and custom workloads containing up to 12,000 queries.

  • Superior Utility: ViewRewrite consistently outperformed PrivateSQL, maintaining a median relative error below 0.1 for most workloads when $ε \ge 4$.
  • Scalability: While PrivateSQL's view count grew linearly with the number of queries, ViewRewrite maintained a constant number of views (typically 14-15) even as the workload scaled into the thousands.
  • Performance: By reducing the number of views to be generated and protected—the most computationally expensive step—ViewRewrite achieved up to a 5x speedup over existing methods for large workloads.

Conclusion

ViewRewrite demonstrates that query rewriting is a powerful tool for enhancing the utility of Differential Privacy in complex database environments. By transforming queries to share a minimal set of views, the system effectively manages the privacy budget, enabling accurate and efficient large-scale data analysis.

Summary updated

BibTeX
@inproceedings{du2025query,
  author = {Xinglin Du and Peng Tang and Rui Chen and Ning Wang and Chengyu Hu and Shanqing Guo},
  title = {{Query Rewriting-Based View Generation for Efficient Multi-Relation Multi-Query with Differential Privacy}},
  booktitle = {EDBT},
  year = {2025},
  url = {https://openreview.net/forum?id=a56r5pRNCI},
}
Figure