Balancing expressiveness and inexpressiveness in view design

Michael Benedikt, Pierre Bourhis, Louis Jachiet, Efthymia Tsamoura

Introduction

In the modern data ecosystem, organizations such as healthcare providers and government agencies face a fundamental paradox: the necessity of sharing data for collaborative research versus the legal and ethical mandate to protect sensitive information. This paper explores the "Goldilocks zone" of data publishing. It investigates how to design database views that are expressive enough to answer specific, useful queries (utility) while remaining "inexpressive" enough to prevent the disclosure of sensitive secrets (privacy).

While previous research has largely focused on verifying whether existing views leak information or satisfy a query, this work tackles the proactive design problem. The authors provide a formal framework to determine when such views exist and how to construct them, even when dealing with complex distributed data sources and background knowledge.

Defining the Design Problem

The core challenge lies in satisfying two competing requirements simultaneously:

  1. Utility: The view must provide enough information to uniquely determine the answer to a target query, a concept known as query determinacy.
  2. Privacy (Non-disclosure): The view must be designed such that an adversary, even with background knowledge, can never be certain about the answer to a designated "secret" query.

To bridge these requirements, the authors focus on "minimally informative" views—those that reveal the absolute bare minimum required to satisfy the utility goal—and "non-disclosing" views that act as a shield against unauthorized inference.

Methodology and Formal Framework

The authors employ formal logic and database theory to analyze these trade-offs, utilizing several key technical tools:

  • Determinacy: This information-theoretic notion defines utility. A view is considered useful if the answer to a target query can be uniquely reconstructed from the view's output, regardless of the specific underlying data instance.
  • Canonical Views: For Conjunctive Queries (CQs), the authors define a baseline design that partitions data based on the specific joins required by the target query.
  • Invariant Shuffle Views: To achieve true minimality among arbitrary mathematical functions (beyond standard SQL), the authors introduce "shuffles." These are mappings of variables that help identify which parts of a join are strictly necessary and which can be obscured to enhance privacy.
  • The Chase and Product Construction: The "chase" is used to reason about data dependencies and query containment. To handle "non-local" background knowledge—such as when a table is replicated across multiple independent sources—the authors introduce a novel product construction approach.

Key Insights: The Minimality Gap and Background Knowledge

One of the paper's most significant contributions is the identification of the Minimality Gap. The authors demonstrate a difference between being "minimally informative" within a specific query language (like SQL or CQs) versus being minimal among all possible mathematical functions. To reach absolute minimality, views often require "unsafe disjunctions" or complex relational algebra that goes beyond standard projections.

Furthermore, the paper highlights how background knowledge changes the design landscape:

  • Local Knowledge: If data sources follow internal rules (e.g., "every patient record must link to a doctor"), the canonical view design remains effective as long as these rules are integrated into the design phase.
  • Replication and Non-local Knowledge: When data is replicated across sources, the situation becomes more volatile. In some cases, a single "best" minimal view may not even exist. However, replication can also be exploited by a clever designer to create non-standard, highly complex views that hide secrets more effectively than simple projections.
  • Isomorphism Invariance: While most database queries are indifferent to the specific names of data elements, the paper reveals that breaking this property might be necessary to achieve optimal privacy in the presence of data replication.

Theoretical Results and Complexity

The research establishes several rigorous bounds and proofs:

  • Characterization (Theorems 2 & 3): The authors successfully characterize minimally informative views for CQs and provide a construction method for views that are minimal among all possible functions.
  • Complexity: The problem of checking if a CQ-based view is both useful and non-disclosing is generally situated in the $\Sigma^p_2$ complexity class. However, this complexity drops to coNP if the utility query is already "minimal" (containing no redundant components).
  • Existence: The authors prove that while local constraints are manageable, non-local replication can lead to scenarios where no optimal view exists, forcing designers to make difficult trade-offs between protecting different secrets.

Limitations and Future Directions

As a foundational theoretical work, the paper focuses primarily on Boolean Conjunctive Queries without constants. Extending these results to more expressive query languages and handling the nuances of strictly finite databases (where some "chase" procedures might differ) remain open areas for research. Additionally, while the paper provides algorithms for many scenarios, the general decidability of whether an arbitrary view exists for any given utility/privacy pair continues to be a subject for future investigation.

Summary updated

Abstract

We study the design of data publishing mechanisms that allow a collection of autonomous distributed datasources to collaborate to support queries. A common mechanism for data publishing is via views: functions that expose derived data to users, usually specified as declarative queries. Our autonomy assumption is that the views must be on individual sources, but with the intention of supporting integrated queries. In deciding what data to expose to users, two considerations must be balanced. The views must be sufficiently expressive to support queries that users want to ask -- the utility of the publishing mechanism. But there may also be some expressiveness restriction. Here we consider two restrictions, a minimal information requirement, saying that the views should reveal as little as possible while supporting the utility query, and a non-disclosure requirement, formalizing the need to prevent external users from computing information that data owners do not want revealed. We investigate the problem of designing views that satisfy both an expressiveness and an inexpressiveness requirement, for views in a restricted declarative language (conjunctive queries), and for arbitrary views.
BibTeX
@article{benedikt2020balancing,
  author = {Michael Benedikt and Pierre Bourhis and Louis Jachiet and Efthymia Tsamoura},
  title = {{Balancing expressiveness and inexpressiveness in view design}},
  journal = {ACM Trans. Database Syst.},
  year = {2020},
  doi = {10.1145/3488370},
}
Figure