CQE in Description Logics Through Instance Indistinguishability (extended version)

2020/04/24 by Gianluca Cima, Domenico Lembo, Cima, Gianluca +5
Computer Science · Decision Sciences · #Artificial Intelligence (cs.AI) #Data Quality and Management #Databases (cs.DB) #FOS: Computer and information sciences #Logic, Reasoning, and Knowledge #Semantic Web and Ontologies #cs.AI #cs.DB

paper · pdf · doi:10.48550/arxiv.2004.11870

9 pages

arxiv created 2020/04/24 · openalex publication_date 2020/04/24 · arxiv updated 2020/04/27 · openalex created_date 2020/05/01 · openalex updated_date 2026/07/28

Abstract

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_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_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.

Related

• Tractable Query Answering under Epistemic Confidentiality Policies in DL Ontologies (extended version)
• Controlled Query Evaluation through Epistemic Dependencies
• CQE under Epistemic Dependencies: Algorithms and Experiments (extended version)
• Querying Circumscribed Description Logic Knowledge Bases
• When is Ontology-Mediated Querying Efficient?