CQE in Description Logics Through Instance Indistinguishability (extended version)
This work addresses privacy concerns in querying knowledge bases for users of Description Logics, though it appears incremental as it builds on existing confidentiality-preserving approaches.
The paper tackles privacy-preserving query answering in Description Logics by proposing a controlled query evaluation approach based on instance indistinguishability, showing that for DL-Lite_R ontologies, this method is tractable in data complexity and first-order rewritable.
We study privacy-preserving query answering in Description Logics (DLs). Specifically, we consider the approach of controlled query evaluation (CQE) based on the notion of instance indistinguishability. We derive data complexity results for query answering over DL-Lite$_{\mathcal{R}}$ ontologies, through a comparison with an alternative, existing confidentiality-preserving approach to CQE. Finally, we identify a semantically well-founded notion of approximated query answering for CQE, and prove that, for DL-Lite$_{\mathcal{R}}$ ontologies, this form of CQE is tractable with respect to data complexity and is first-order rewritable, i.e., it is always reducible to the evaluation of a first-order query over the data instance.