TL;DR
This paper revisits Controlled Query Evaluation (CQE), a framework for protecting sensitive data in knowledge bases by modifying query answers. The authors explore query answering over all possible "optimal" censors, not just one, and investigate its relationship with Consistent Query Answering (CQA) in Description Logics (DLs). They provide complexity results for different censor languages and DL profiles, offering a deeper understanding of privacy-preserving reasoning in DL-based systems.
What Problem Does This Paper Address?
In many real-world applications, knowledge bases contain sensitive information that must be protected while still allowing users to query the data. Controlled Query Evaluation (CQE) offers a solution by introducing a "policy" that specifies what information is confidential and a "censor" that modifies query answers to prevent the inference of this sensitive data. The challenge arises when multiple "optimal" censors exist – censors that hide the minimum necessary information to satisfy the policy. Choosing one arbitrarily might not be ideal. This paper addresses this by considering query answering across all optimal censors, aiming for a more robust and less discretionary approach. Furthermore, it delves into the connection between CQE and Consistent Query Answering (CQA), another framework for managing inconsistencies in knowledge bases, to better understand the computational properties of privacy-preserving query evaluation.
Methods
The paper adapts the CQE framework from previous work, defining a CQE instance as a triple: a TBox (schema), an ABox (data), and a policy (denial assertions). A key contribution is the shift from considering a single optimal censor to analyzing query answers across the intersection of answers from all optimal censors. This is formalized by defining the set of theories of all optimal censors, denoted $Th^o(E)$.
A significant part of the paper is dedicated to exploring the relationship between CQE and CQA. They introduce notions of CQE-reducibility to CQA and CQA-reducibility to CQE. These reducibility conditions allow them to leverage existing results from CQA to derive complexity bounds for CQE. Specifically, they analyze different censor languages:
- ABox-based censors: The censor can only select facts from the ABox.
- Ground atom (GA) censors: The censor can select ground atoms.
- Conjunctive Query (CQ) censors: The most expressive, allowing censors to use conjunctive queries.
They analyze these scenarios for DL-LiteR and EL₁ DL profiles, which are popular lightweight DLs.
Datasets
Not discussed in the paper. The paper focuses on theoretical aspects and complexity analysis rather than empirical evaluation on specific datasets.
Key Insights and Ideas
- Querying over all optimal censors: The core idea is that by considering the intersection of answers from all optimal censors, we achieve a more robust and less arbitrary form of privacy. This avoids making a single, potentially biased, choice of censor.
- Deep connection between CQE and CQA: The paper establishes formal reducibility conditions between CQE and CQA. This is crucial because it allows transferring complexity results and insights from the well-studied CQA domain to CQE, and vice-versa.
- Surprising complexity results for restricted censor languages: For DL-LiteR, the complexity of CQE with restricted censor languages (ABox or GA) is higher than with the more expressive CQ censor language. This is counter-intuitive and stems from the fact that with the full CQ language, one can compute the intersection of optimal censor theories efficiently, whereas restricted languages require more complex, potentially exponential, reasoning.
- DL-LiteR vs. EL₁ differences: While both DL profiles are analyzed, the paper highlights differences in their complexity behavior, particularly concerning the expressiveness of censor languages and the computational feasibility of reasoning.
Key Results
The paper provides several complexity results for CQE instances in DL-LiteR and EL₁:
- ABox-Cens-Entailment of BCQs: This is coNP-complete in data complexity for both DL-LiteR and EL₁ CQE instances. This result is achieved by showing mutual reducibility with CQA under AR-semantics.
- GA-Cens-Instance-Checking and GA-Cens-Entailment of BCQs (DL-LiteR): GA-Cens-Instance-Checking is in AC⁰, and GA-Cens-Entailment of BCQs is coNP-complete in data complexity.
- GA-Cens-Entailment of BCQs (EL₁): This is coNP-complete in data complexity.
- CQ-Cens-Entailment of BCQs (DL-LiteR): This is in PTIME in data complexity. This is a notable result, suggesting that with a more expressive censor language, reasoning can be more efficient for DL-LiteR.
- CQk-Cens-Entailment of BCQs (EL₁): This is coNP-complete in data complexity.
Limitations and Future Work
- EL₁ Complexity Gaps: The paper leaves open the exact complexity for GA-Cens-Instance-Checking and ABox-Cens-Instance-Checking for EL₁ CQE instances. Additionally, the complexity of full CQ-Cens-Entailment of BCQs for EL₁ remains an open question.
- Refining DL-LiteR CQ-Cens-Entailment: While PTIME is established for DL-LiteR CQ-Cens-Entailment, the authors believe an AC⁰ bound might be achievable, suggesting further research into first-order rewritability techniques.
- Broader DL and Language Support: The authors suggest extending the analysis to other Description Logics and more expressive policy and censor languages.
- Practical Implementation: A significant future direction is to explore practical techniques for implementing CQE extensions in existing DL reasoners and Ontology-Based Data Access (OBDA) systems.
Summary updated