Tractable Query Answering under Epistemic Confidentiality Policies in DL Ontologies (extended version)

• URL: http://arxiv.org/abs/2607.16715v2
• Date: Tue, 21 Jul 2026 06:39:04 GMT
• Title: Tractable Query Answering under Epistemic Confidentiality Policies in DL Ontologies (extended version)
• Abstract summary: We first address the problem of answering queries under known semantics for CQE (GA and I-GA-entailment)<n>We introduce a new semantics for CQE, based on the notion of minimal policy violation (MPV)<n>We show that the new semantics provides a sound approximation to the previous ones, while satisfying the indistinguishability property.
• Score: 2.985616980706464
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We study Controlled Query Evaluation (CQE), a declarative approach to confidentiality-preserving data access, in the context of Description Logic (DL) ontologies, and for confidentiality policies expressed through Epistemic Dependencies (EDs). We first address the problem of answering queries (specifically, Boolean unions of conjunctive queries) under known semantics for CQE (GA- and IGA-entailment). Our results show that if the TBox is expressed in $\text{DL-Lite}_{\mathcal{R}}$, CQE is computationally intractable in general. Moreover, in the presence of EDs, the IGA semantics has recently been proven not to satisfy an important confidentiality preservation property known as indistinguishability. With the goal of defining computationally easier and confidentiality-preserving forms of CQE, we introduce a new semantics for CQE, based on the notion of minimal policy violation (MPV). We show that the new semantics provides a sound approximation of the previous ones, while satisfying the indistinguishability property. We also prove that, in the case of $\text{DL-Lite}_{\mathcal{R}}$ ontologies, query entailment under the MPV semantics can be decided in polynomial time in data complexity. Finally, we present a software implementation of our framework that we used to evaluate the feasibility of this new approach using an existing benchmark for OWL 2 QL.

Related papers

• Neural Paging: Learning Context Management Policies for Turing-Complete Agents [9.896253083170066]
  We introduce textitNeural Paging, a hierarchical architecture that decouples symbolic reasoning from information resource management.<n>We provide theoretical analysis showing that, under bounded context window size$K$, Neural Paging reduces the complexity of long-horizon reasoning from quadratic $O(N2)$ to $O(N cdot K2)$.
  arXiv  Detail & Related papers  (2026-02-11T22:35:08Z)
• KBQA-R1: Reinforcing Large Language Models for Knowledge Base Question Answering [64.62317305868264]
  We present textbfKBQA-R1, a framework that shifts the paradigm from text imitation to interaction optimization via Reinforcement Learning.<n>Treating KBQA as a multi-turn decision process, our model learns to navigate the knowledge base using a list of actions.<n>Experiments on WebQSP, GrailQA, and GraphQuestions demonstrate that KBQA-R1 achieves state-of-the-art performance.
  arXiv  Detail & Related papers  (2025-12-10T17:45:42Z)
• ReAG: Reasoning-Augmented Generation for Knowledge-based Visual Question Answering [54.72902502486611]
  ReAG is a Reasoning-Augmented Multimodal RAG approach that combines coarse- and fine-grained retrieval with a critic model that filters irrelevant passages.<n>ReAG significantly outperforms prior methods, improving answer accuracy and providing interpretable reasoning grounded in retrieved evidence.
  arXiv  Detail & Related papers  (2025-11-27T19:01:02Z)
• CQE under Epistemic Dependencies: Algorithms and Experiments (extended version) [2.2770431622059792]
  We focus on answering Boolean unions of conjunctive queries (BUCQs) with respect to the intersection of all optimal GA censors.<n>First, we characterize the security of this intersection-based approach and identify a class of EDs (namely full EDs) that remains safe.<n>Finally, we report on experiments conducted in two different evaluation scenarios, showing the practical feasibility of our rewriting function.
  arXiv  Detail & Related papers  (2025-07-23T13:10:33Z)
• The benefits of query-based KGQA systems for complex and temporal questions in LLM era [55.20230501807337]
  Large language models excel in question-answering (QA) yet still struggle with multi-hop reasoning and temporal questions.<n> Query-based knowledge graph QA (KGQA) offers a modular alternative by generating executable queries instead of direct answers.<n>We explore multi-stage query-based framework for WikiData QA, proposing multi-stage approach that enhances performance on challenging multi-hop and temporal benchmarks.
  arXiv  Detail & Related papers  (2025-07-16T06:41:03Z)
• Few-shot Policy (de)composition in Conversational Question Answering [54.259440408606515]
  We propose a neuro-symbolic framework to detect policy compliance using large language models (LLMs) in a few-shot setting.<n>We show that our approach soundly reasons about policy compliance conversations by extracting sub-questions to be answered, assigning truth values from contextual information, and explicitly producing a set of logic statements from the given policies.<n>We apply this approach to the popular PCD and conversational machine reading benchmark, ShARC, and show competitive performance with no task-specific finetuning.
  arXiv  Detail & Related papers  (2025-01-20T08:40:15Z)
• Controlled Query Evaluation through Epistemic Dependencies [7.502796412126707]
  We show the expressive abilities of our framework and study the data complexity of CQE for (unions of) conjunctive queries. We prove tractability for the case of acyclic dependencies by providing a suitable query algorithm.
  arXiv  Detail & Related papers  (2024-05-03T19:48:07Z)
• Temporal-aware Hierarchical Mask Classification for Video Semantic Segmentation [62.275143240798236]
  Video semantic segmentation dataset has limited categories per video. Less than 10% of queries could be matched to receive meaningful gradient updates during VSS training. Our method achieves state-of-the-art performance on the latest challenging VSS benchmark VSPW without bells and whistles.
  arXiv  Detail & Related papers  (2023-09-14T20:31:06Z)
• CQE in OWL 2 QL: A "Longest Honeymoon" Approach (extended version) [13.169982133542266]
  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.
  arXiv  Detail & Related papers  (2022-07-22T15:51:15Z)
• Learning Implicitly with Noisy Data in Linear Arithmetic [94.66549436482306]
  We extend implicit learning in PAC-Semantics to handle intervals and threshold uncertainty in the language of linear arithmetic. We show that our implicit approach to learning optimal linear programming objective constraints significantly outperforms an explicit approach in practice.
  arXiv  Detail & Related papers  (2020-10-23T19:08:46Z)
• CQE in Description Logics Through Instance Indistinguishability (extended version) [0.0]
  We study privacy-preserving query answering in Description Logics (DLs) We derive data complexity results query answering over DL-Lite$_mathcal$$. We identify a semantically well-founded notion of approximated confidentiality answering for CQE.
  arXiv  Detail & Related papers  (2020-04-24T17:28:24Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.