Sensitivity of Counting Queries

Myrto Arapinis, Diego Figueira, Marco Gaboardi

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

In the context of statistical databases, the release of accurate statistical information about the collected data often puts at risk the privacy of the individual contributors. The goal of differential privacy is to maximise the utility of a query while protecting the individual records in the database. A natural way to achieve differential privacy is to add statistical noise to the result of the query. In this context, a mechanism for releasing statistical information is thus a trade-off between utility and privacy. In order to balance these two “conflicting” requirements, privacy preserving mechanisms calibrate the added noise to the so-called sensitivity of the query, and thus a precise estimate of the sensitivity of the query is necessary to determine the amplitude of the noise to be added.

In this paper, we initiate a systematic study of sensitivity of counting queries over relational databases. We first observe that the sensitivity of a Relational Algebra query with counting is not computable in general, and that while the sensitivity of Conjunctive Queries with counting is computable, it becomes unbounded as soon as the query includes a join. We then consider restricted classes of databases (databases with constraints), and study the problem of computing the sensitivity of a query given such constraints. We are able to establish bounds on the sensitivity of counting conjunctive queries over constrained databases. The kind of constraints studied here are: functional dependencies and cardinality dependencies. The latter is a natural generalisation of functional dependencies that allows us to provide tight bounds on the sensitivity of counting conjunctive queries.
Original languageEnglish
Title of host publication43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Place of PublicationRome, Italy
PublisherSchloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany
Pages120:1-120:13
Number of pages13
Volume55
ISBN (Electronic)978-3-95977-013-2
DOIs
Publication statusPublished - 23 Aug 2016
Event43rd International Colloquium on Automata, Languages and Programming (ICALP 2016), the main European conference in Theoretical Computer Science and annual meeting of the European Association for Theoretical Computer Science - Sapienza University of Rome, Rome, Italy
Duration: 12 Jul 201615 Jul 2016
http://www.easyconferences.eu/icalp2016/
http://www.easyconferences.eu/icalp2016/index.html

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
PublisherSchloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Volume55
ISSN (Electronic)1868-8969

Conference

Conference43rd International Colloquium on Automata, Languages and Programming (ICALP 2016), the main European conference in Theoretical Computer Science and annual meeting of the European Association for Theoretical Computer Science
Abbreviated titleICALP 2016
Country/TerritoryItaly
CityRome
Period12/07/1615/07/16
Internet address

Fingerprint

Dive into the research topics of 'Sensitivity of Counting Queries'. Together they form a unique fingerprint.

Cite this