On the Efficiency of Checking Perfect Privacy

Summary: Shows that checking perfect privacy (whether answered query QV leaks information about secret QS) is Pi^p_2-complete in general but tractable for large, practical subclasses of conjunctive queries. Key idea: reduce perfect-privacy checking to query containment, transferring containment complexity/algorithms to privacy enforcement and unifying tractability results. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h50f3feb6a8c70959
Venue: PODS
Year: 2006
Pagerank: 6.7094069e-05
Overall Rank: 4,240 | 71.50%
DOI: 10.1145/1142351.1142375

Incoming Non-self Citations Over Time

Authors

1. Ashwin Machanavajjhala (Cornell University; IBM)
2. Johannes Gehrke (Cornell University)

BibTeX Citation

@inproceedings{machanavajjhala_pods06,
        address = {New York, NY, USA},
        series = {{PODS} '06},
        title = {{On the Efficiency of Checking Perfect Privacy}},
        url = {https://dl.acm.org/doi/10.1145/1142351.1142375},
        doi = {10.1145/1142351.1142375},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Machanavajjhala, Ashwin and Gehrke, Johannes},
        year = {2006}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,984	Materialized Views in Probabilistic Databases: For Information Exchange and Query Optimization	2007	VLDB	7.7830089e-05
4,133	Privacy Skyline: Privacy with Multidimensional Adversarial Knowledge	2007	VLDB	6.7880955e-05
6,838	Efficient Auditing For Complex SQL queries	2011	SIGMOD	5.6678362e-05
12,582	On Scaling Up Sensitive Data Auditing	2013	VLDB	4.9793485e-05
12,682	Whodunit: An Auditing Tool for Detecting Data Breaches	2011	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
390	Conjunctive-Query Containment and Constraint Satisfaction	1998	PODS	0.00019248147
608	An Authorization Mechanism for a Relational Data Base System	1976	SIGMOD	0.00015599661
1,109	A Formal Analysis of Information Disclosure in Data Exchange	2004	SIGMOD	0.00011987291
2,449	Simulatable Auditing	2005	PODS	8.4490697e-05
3,870	On the Complexity of the Containment Problem for Conjunctive Queries with Built-in Predicates	1998	PODS	6.9551842e-05
8,053	Polynomial-time program transformations in deductive databases	1990	PODS	5.3986864e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,803	Residual Sensitivity for Differentially Private Multi-Way Joins	2021	SIGMOD
2	4,040	Epistemic Privacy	2008	PODS
3	8,334	Continual Observation of Joins under Differential Privacy	2024	SIGMOD
4	9,778	Answering Private Linear Queries Adaptively using the Common Mechanism	2023	VLDB
5	2,488	Computing Local Sensitivities of Counting Queries with Joins	2020	SIGMOD
6	1,735	The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints	2015	PODS
7	6,661	Better than Composition: How to Answer Multiple Relational Queries under Differential Privacy	2023	SIGMOD
8	879	Relationship Privacy: Output Perturbation for Queries with Joins	2009	PODS
9	3,870	On the Complexity of the Containment Problem for Conjunctive Queries with Built-in Predicates	1998	PODS
10	7,439	A Nearly Instance-optimal Differentially Private Mechanism for Conjunctive Queries	2022	PODS