CQE under Epistemic Dependencies: Algorithms and Experiments (extended version)

• URL: http://arxiv.org/abs/2507.17487v2
• Date: Mon, 28 Jul 2025 16:42:27 GMT
• Title: CQE under Epistemic Dependencies: Algorithms and Experiments (extended version)
• Authors: Lorenzo Marconi, Flavia Ricci, Riccardo Rosati,
• Abstract summary: 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.
• Score: 2.2770431622059792
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: 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.

Related papers

• Respecting Temporal-Causal Consistency: Entity-Event Knowledge Graphs for Retrieval-Augmented Generation [69.45495166424642]
  We develop a robust and discriminative QA benchmark to measure temporal, causal, and character consistency understanding in narrative documents.<n>We then introduce Entity-Event RAG (E2RAG), a dual-graph framework that keeps separate entity and event subgraphs linked by a bipartite mapping.<n>Across ChronoQA, our approach outperforms state-of-the-art unstructured and KG-based RAG baselines, with notable gains on causal and character consistency queries.
  arXiv  Detail & Related papers  (2025-06-06T10:07:21Z)
• Predicate-Conditional Conformalized Answer Sets for Knowledge Graph Embeddings [27.138935426612306]
  CondKGCP approximates predicate-conditional coverage guarantees while maintaining compact prediction sets.<n>We prove the theoretical guarantees and demonstrate empirical effectiveness of CondKGCP by comprehensive evaluations.
  arXiv  Detail & Related papers  (2025-05-22T16:33:20Z)
• Advancing Neural Network Verification through Hierarchical Safety Abstract Interpretation [52.626086874715284]
  We introduce a novel problem formulation called Abstract DNN-Verification, which verifies a hierarchical structure of unsafe outputs.<n>By leveraging abstract interpretation and reasoning about output reachable sets, our approach enables assessing multiple safety levels during the formal verification process.<n>Our contributions include a theoretical exploration of the relationship between our novel abstract safety formulation and existing approaches.
  arXiv  Detail & Related papers  (2025-05-08T13:29:46Z)
• Q-Learning with Clustered-SMART (cSMART) Data: Examining Moderators in the Construction of Clustered Adaptive Interventions [3.9650359172757743]
  A clustered adaptive intervention (cAI) is a sequence of decision rules that guides practitioners on how best to tailor cluster-level intervention to improve outcomes.<n>We introduce a clustered Q-learning framework with the M-out-of-N Cluster Bootstrap to evaluate whether a set of candidate tailoring variables may be useful in defining an optimal cAI.
  arXiv  Detail & Related papers  (2025-05-01T19:24:39Z)
• AlignRAG: Leveraging Critique Learning for Evidence-Sensitive Retrieval-Augmented Reasoning [61.28113271728859]
  RAG has become a widely adopted paradigm for enabling knowledge-grounded large language models (LLMs)<n>Standard RAG pipelines often fail to ensure that model reasoning remains consistent with the evidence retrieved, leading to factual inconsistencies or unsupported conclusions.<n>In this work, we reinterpret RAG as Retrieval-Augmented Reasoning and identify a central but underexplored problem: textitReasoning Misalignment.
  arXiv  Detail & Related papers  (2025-04-21T04:56:47Z)
• 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)
• Coherent Entity Disambiguation via Modeling Topic and Categorical Dependency [87.16283281290053]
  Previous entity disambiguation (ED) methods adopt a discriminative paradigm, where prediction is made based on matching scores between mention context and candidate entities. We propose CoherentED, an ED system equipped with novel designs aimed at enhancing the coherence of entity predictions. We achieve new state-of-the-art results on popular ED benchmarks, with an average improvement of 1.3 F1 points.
  arXiv  Detail & Related papers  (2023-11-06T16:40:13Z)
• CAR: Conceptualization-Augmented Reasoner for Zero-Shot Commonsense Question Answering [56.592385613002584]
  We propose Conceptualization-Augmented Reasoner (CAR) to tackle the task of zero-shot commonsense question answering. CAR abstracts a commonsense knowledge triple to many higher-level instances, which increases the coverage of CommonSense Knowledge Bases. CAR more robustly generalizes to answering questions about zero-shot commonsense scenarios than existing methods.
  arXiv  Detail & Related papers  (2023-05-24T08:21:31Z)
• 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)
• Reasoning over Hybrid Chain for Table-and-Text Open Domain QA [69.8436986668218]
  We propose a ChAin-centric Reasoning and Pre-training framework (CARP) CARP utilizes hybrid chain to model the explicit intermediate reasoning process across table and text for question answering. We also propose a novel chain-centric pre-training method, to enhance the pre-trained model in identifying the cross-modality reasoning process.
  arXiv  Detail & Related papers  (2022-01-15T16:11:55Z)
• 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.