CQE in OWL 2 QL: A "Longest Honeymoon" Approach (extended version)
This work addresses data privacy for users of Semantic Web ontologies by introducing a dynamic approach that is more cooperative than static methods, though it is incremental as it builds on existing CQE frameworks.
The paper tackles the problem of protecting confidential information in Semantic Web ontologies by proposing a dynamic Controlled Query Evaluation method that alters query answers based on previous queries to maximize cooperativeness, showing that this approach is first-order rewritable and in AC0 in data complexity for OWL 2 QL ontologies.
Controlled Query Evaluation (CQE) has been recently studied in the context of Semantic Web ontologies. The goal of CQE is concealing some query answers so as to prevent external users from inferring confidential information. In general, there exist multiple, mutually incomparable ways of concealing answers, and previous CQE approaches choose in advance which answers are visible and which are not. In this paper, instead, we study a dynamic CQE method, namely, we propose to alter the answer to the current query based on the evaluation of previous ones. We aim at a system that, besides being able to protect confidential data, is maximally cooperative, which intuitively means that it answers affirmatively to as many queries as possible; it achieves this goal by delaying answer modifications as much as possible. We also show that the behavior we get cannot be intensionally simulated through a static approach, independent of query history. Interestingly, for OWL 2 QL ontologies and policy expressed through denials, query evaluation under our semantics is first-order rewritable, and thus in AC0 in data complexity. This paves the way for the development of practical algorithms, which we also preliminarily discuss in the paper.