CQE under Epistemic Dependencies: Algorithms and Experiments (extended version)
This work addresses secure information disclosure in knowledge bases for applications like data privacy, but it is incremental as it builds on existing CQE frameworks and focuses on specific logical settings.
The paper tackles Controlled Query Evaluation over ontologies with epistemic dependencies, showing that for a subclass of dependencies and DL-Lite_R ontologies, answering Boolean unions of conjunctive queries is in AC^0 in data complexity via a first-order rewriting algorithm, with experiments demonstrating practical feasibility.
We investigate Controlled Query Evaluation (CQE) over ontologies, where information disclosure is regulated by epistemic dependencies (EDs), a family of logical rules recently proposed for the CQE framework. In particular, we combine EDs with the notion of optimal GA censors, i.e. maximal sets of ground atoms that are entailed by the ontology and can be safely revealed. We focus on answering Boolean unions of conjunctive queries (BUCQs) with respect to the intersection of all optimal GA censors - an approach that has been shown in other contexts to ensure strong security guarantees with favorable computational behavior. First, we characterize the security of this intersection-based approach and identify a class of EDs (namely, full EDs) for which it remains safe. Then, for a subclass of EDs and for DL-Lite_R ontologies, we show that answering BUCQs in the above CQE semantics is in AC^0 in data complexity by presenting a suitable, detailed first-order rewriting algorithm. Finally, we report on experiments conducted in two different evaluation scenarios, showing the practical feasibility of our rewriting function.