We study Consistent Query Answering (CQA) over knowledge bases with existential rules. Specifically, we propose a novel framework for CQA that combines previous approaches, allowing for the simultaneous presence of both open and closed predicates, i.e. predicates interpreted under open- and closed-world assumption, respectively. We establish the data complexity of answering unions of conjunctive queries in such a new framework under the so-called AR semantics and for different classes of existential rules. We also provide new complexity results for the standard (i.e. non-inconsistency tolerant) query answering in the presence of both open and closed predicates. Our results show that, for certain classes of rules, the complexity of CQA matches that of non-inconsistency-tolerant query answering.

We propose a general framework for assessing the exposure of sensitive knowledge in policy-protected knowledge bases (KBs), where knowledge is represented as logical theories and data protection policies are defined declaratively using epistemic dependencies. The framework models scenarios in which confidential parts of the KB may be publicly known due to security breaches. We study two fundamental decision problems: determining whether the exposed knowledge violates the data protection policy (leakage), and whether there exists a secure view of the KB that complies with the policy. We analyze the computational complexity (specifically, data complexity) of these problems, focusing on the DL-Lite_R and EL_\bot Description Logics. Our findings show that, for DL-Lite_R with restricted forms of policy, both the problems can be efficiently solved through query rewriting methods. For EL_\bot, we establish conditions for tractable computational bounds. Our results highlight the potential of this framework for practical applications in confidentiality-preserving knowledge management.

Controlled Query Evaluation (CQE) is a methodology designed to maintain confidentiality by either rejecting specific queries or adjusting responses to safeguard sensitive information. In this investigation, our focus centers on CQE within Description Logic ontologies, aiming to ensure that queries are answered truthfully as long as possible before resorting to deceptive responses, a cooperativity property which is called the “longest honeymoon”. Our work introduces new semantics for CQE, denoted as MC-CQE, which enjoys the longest honeymoon property and outperforms previous methodologies in terms of cooperativity. We study the complexity of query answering in this new framework for ontologies expressed in the Description Logic DL-Lite_R. Specifically, we establish data complexity results under different maximally cooperative semantics and for different classes of queries. Our results identify both tractable and intractable cases. In particular, we show that the evaluation of Boolean unions of conjunctive queries is the same under all the above semantics and its data complexity is in AC^0. This result makes query answering amenable to SQL query rewriting. However, this favorable property does not extend to open queries, even with a restricted query language limited to conjunctions of atoms. While, in general, answering open queries in the MC-CQE framework is intractable, we identify a sub-family of semantics under which answering full conjunctive queries is tractable.

In this paper we study Controlled Query Evaluation (CQE), a declarative approach to privacy-preserving query answering over databases, knowledge bases, and ontologies. CQE is based on the notion of censor, which defines the answers to each query posed to the data/knowledge base. We investigate both semantic and computational properties of CQE in the context of OWL ontologies, and specifically in the description logic DL-LiteR, which underpins the OWL 2 QL profile. In our analysis, we focus on semantics of CQE based on censors (called optimal GA censors) that enjoy the so-called indistinguishability property, analyzing the trade-off between maximizing the amount of data disclosed by query answers and minimizing the computational cost of privacy-preserving query answering. We first study the data complexity of skeptical entailment of unions of conjunctive queries under all the optimal GA censors, showing that the computational cost of query answering in this setting is intractable. To overcome this computational issue, we then define a different semantics for CQE centered around the notion of intersection of all the optimal GA censors. We show that query answering over OWL 2 QL ontologies under the new intersection-based semantics for CQE enjoys tractability and is first-order rewritable, i.e. amenable to be implemented through SQL query rewriting techniques and the use of standard relational database systems; on the other hand, this approach shows limitations in terms of amount of data disclosed. To improve this aspect, we add preferences between ontology predicates to the CQE framework, and identify a semantics under which query answering over OWL 2 QL ontologies maintains the same computational properties of the intersection-based approach without preferences.