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

# Tractable Query Answering under Epistemic Confidentiality Policies in DL Ontologies (extended version)
Source: [https://arxiv.org/html/2607.16715](https://arxiv.org/html/2607.16715)
11institutetext:Sapienza University of Rome, Italy
11email:\{marconi,rosati\}@diag\.uniroma1\.it
11email:rieti\.1762973@studenti\.uniroma1\.it###### 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 inDL\-Liteℛ\\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 ofDL\-Liteℛ\\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\.

## 1Introduction

We study*Controlled Query Evaluation*\(CQE\)\[[12](https://arxiv.org/html/2607.16715#bib.bib15),[2](https://arxiv.org/html/2607.16715#bib.bib36)\], a logical framework designed to allow answering queries over a database or knowledge base while keeping undisclosed pieces of knowledge that are considered sensitive\. In recent years, several works on CQE focused on Description Logic ontologies\[[4](https://arxiv.org/html/2607.16715#bib.bib29),[10](https://arxiv.org/html/2607.16715#bib.bib40),[9](https://arxiv.org/html/2607.16715#bib.bib102)\], which is the setting we consider here\. In particular, we focus on ontologies whose intentional part is expressed inDL\-Liteℛ\\text\{DL\-Lite\}\_\{\\mathcal\{R\}\}\[[6](https://arxiv.org/html/2607.16715#bib.bib98)\], the logic underpinning the OWL 2 QL profile\[[14](https://arxiv.org/html/2607.16715#bib.bib111)\]\.

In CQE, the information to be protected is specified using logical formulas, which are collected in the so\-called*policy*\. In the literature, policies are often expressed by means of*denial assertions*, i\.e\. logical sentences of the formq→⊥q\\rightarrow\\bot, whereqqis a Boolean conjunctive query \(BCQ\)\. Intuitively, such assertions are intended to prevent the disclosure ofqqto the end user, even indirectly through an unbounded sequence of queries\. The recent work\[[8](https://arxiv.org/html/2607.16715#bib.bib99)\]proposed the usage of*epistemic dependencies*\(EDs\) for enhancing the expressivity of the data protection policy\. An ED is a logical formula of the form∀x→​\(K​qb→K​qh\)\\forall\\vec\{x\}\\,\(\\mathrm\{K\}q\_\{b\}\\rightarrow\\mathrm\{K\}q\_\{h\}\), where bothqbq\_\{b\}andqhq\_\{h\}are \(possibly open\) CQs whose free variables occur inx→\\vec\{x\}, andK\\mathrm\{K\}denotes an epistemic operator\. Intuitively, for every instantiation of the variablesx→\\vec\{x\}, such a formula prevents the user from inferringqbq\_\{b\}unlessqhq\_\{h\}can also be inferred\.

In CQE, the key notion used to represent disclosable information is called*censor*\. A censor is a set of logical sentences that, even when combined with the intensional knowledge provided by the TBox, cannot be used to infer sensitive information\. Such sentences may be expressed in different formalisms, like the language of BCQs \(as in the aforementioned work\[[8](https://arxiv.org/html/2607.16715#bib.bib99)\]\) or ground atoms\. Specifically, censors consisting of ground atoms \(also referred to as*GA censors*\) provide a natural representation of disclosable information, since they can be viewed as an ABox\. GA censors are called*optimal*when maximal w\.r\.t\. set inclusion\.

###### Example 1

A hospital does not want to disclose the fact that a minor \(𝖬\\mathsf\{M\}\) is affected by \(𝖺𝖿𝖿𝖡𝗒\\mathsf\{affBy\}\) some disease\. Furthermore, the fact that someone is a minor can be disclosed only with parental consent \(𝗉𝖢𝗈𝗇𝗌𝖥𝗈𝗋\\mathsf\{pConsFor\}\)\. Finally, parental relationships \(𝗉𝖺𝗋𝖮𝖿\\mathsf\{parOf\}\) may be revealed only if they are biological \(𝖻𝗂𝗈𝖯𝖺𝗋𝖮𝖿\\mathsf\{bioParOf\}\)\. Consider a policy𝒫\\mathcal\{P\}made of three EDs, respectively encoding the above protection rules:

∀x,y\(K​\(𝖬​\(x\)∧𝖺𝖿𝖿𝖡𝗒​\(x,y\)\)→⊥\)∀x\(K​𝖬​\(x\)→K​∃y​𝗉𝖢𝗈𝗇𝗌𝖥𝗈𝗋​\(y,x\)\)∀x,y\(K​𝗉𝖺𝗋𝖮𝖿​\(y,x\)→K​𝖻𝗂𝗈𝖯𝖺𝗋𝖮𝖿​\(y,x\)\)\\begin\{array\}\[\]\{r@\{\\,\}l\}\\forall x,y&\(\\mathrm\{K\}\(\\mathsf\{M\}\(x\)\\land\\mathsf\{affBy\}\(x,y\)\)\\rightarrow\\bot\)\\\\ \\forall x&\(\\mathrm\{K\}\\mathsf\{M\}\(x\)\\rightarrow\\mathrm\{K\}\\exists y\\,\\mathsf\{pConsFor\}\(y,x\)\)\\\\ \\forall x,y&\(\\mathrm\{K\}\\mathsf\{parOf\}\(y,x\)\\rightarrow\\mathrm\{K\}\\mathsf\{bioParOf\}\(y,x\)\)\\end\{array\}The intensional knowledge is provided by means of a DL TBox𝒯\\mathcal\{T\}allowing to infer that if an individualxxgave a parental consent foryy, thenxxis a parent ofyy\(𝗉𝖢𝗈𝗇𝗌𝖥𝗈𝗋⊑𝗉𝖺𝗋𝖮𝖿\\mathsf\{pConsFor\}\\sqsubseteq\\mathsf\{parOf\}\), and that ifxxis affected byyy, thenyyis a disease \(∃𝖺𝖿𝖿𝖡𝗒−⊑𝖣𝗂𝗌\\exists\\mathsf\{affBy\}^\{\-\}\\sqsubseteq\\mathsf\{Dis\}\)\. Finally, the ground data is contained in the DL ABox𝒜\\mathcal\{A\}, which contains the fact that𝖺𝗇𝗇\\mathsf\{ann\}is a minor, she is affected by the disease𝖽\\mathsf\{d\}, and𝖻𝗈𝖻\\mathsf\{bob\}gave his consent to reveal that𝖺𝗇𝗇\\mathsf\{ann\}is a minor:𝒜=\{𝖬​\(𝖺𝗇𝗇\),𝖺𝖿𝖿𝖡𝗒​\(𝖺𝗇𝗇,𝖽\),𝗉𝖢𝗈𝗇𝗌𝖥𝗈𝗋​\(𝖻𝗈𝖻,𝖺𝗇𝗇\)\}\\mathcal\{A\}=\\\{\\mathsf\{M\}\(\\mathsf\{ann\}\),\\allowbreak\\mathsf\{affBy\}\(\\mathsf\{ann\},\\mathsf\{d\}\),\\allowbreak\\mathsf\{pConsFor\}\(\\mathsf\{bob\},\\mathsf\{ann\}\)\\\}\. Note that the facts𝗉𝖺𝗋𝖮𝖿​\(𝖻𝗈𝖻,𝖺𝗇𝗇\)\\mathsf\{parOf\}\(\\mathsf\{bob\},\\mathsf\{ann\}\)and𝖣𝗂𝗌​\(𝖽\)\\mathsf\{Dis\}\(\\mathsf\{d\}\)are also logical consequences of𝒯∪𝒜\\mathcal\{T\}\\cup\\mathcal\{A\}\. Since the fact that𝖻𝗈𝖻\\mathsf\{bob\}is the biological parent of𝖺𝗇𝗇\\mathsf\{ann\}cannot be revealed \(because it is not entailed by the ontology\), then also𝗉𝖢𝗈𝗇𝗌𝖥𝗈𝗋​\(𝖻𝗈𝖻,𝖺𝗇𝗇\)\\mathsf\{pConsFor\}\(\\mathsf\{bob\},\\mathsf\{ann\}\)\(which implies𝗉𝖺𝗋𝖮𝖿​\(𝖻𝗈𝖻,𝖺𝗇𝗇\)\\mathsf\{parOf\}\(\\mathsf\{bob\},\\mathsf\{ann\}\)via𝒯\\mathcal\{T\}\) must be kept undisclosed; in turn, the same applies to𝖬​\(𝖺𝗇𝗇\)\\mathsf\{M\}\(\\mathsf\{ann\}\)\. In this case, we have only one optimal GA censor, i\.e\.\{𝖺𝖿𝖿𝖡𝗒​\(𝖺𝗇𝗇,𝖽\),𝖣𝗂𝗌​\(𝖽\)\}\\\{\\mathsf\{affBy\}\(\\mathsf\{ann\},\\mathsf\{d\}\),\\mathsf\{Dis\}\(\\mathsf\{d\}\)\\\}, containing the only two facts that can be revealed\.

Differently, considering a policy𝒫′\\mathcal\{P\}^\{\\prime\}containing instead only the first ED, two optimal GA censors would exist, consisting of all the facts that are logical consequences of the ontology except, respectively,𝖬​\(𝖺𝗇𝗇\)\\mathsf\{M\}\(\\mathsf\{ann\}\)and𝖺𝖿𝖿𝖡𝗒​\(𝖺𝗇𝗇,𝖽\)\\mathsf\{affBy\}\(\\mathsf\{ann\},\\mathsf\{d\}\)\.

The paper\[[13](https://arxiv.org/html/2607.16715#bib.bib108)\]studied the properties of GA censors in the presence of EDs and the complexity of entailment of Boolean unions of conjunctive queries \(BUCQs\) under the so\-called*GA\-*and*IGA\-entailment*semantics, which we also use as a baseline for our analysis\. The former consists of checking whether every optimal GA censor, together with the given TBox, logically entails the input query; the latter, on the other hand, checks whether the query is entailed by the TBox and the intersection of all the optimal GA censors\. That paper focused onDL\-Liteℛ\\text\{DL\-Lite\}\_\{\\mathcal\{R\}\}ontologies and \(combinations of\) different subclasses of EDs, namely linear, full, and acyclic dependencies, showing nice computational properties for IGA\-entailment \(in the case where EDs are either linear\-full or acyclic\-full\), but lacking the whole expressivity offered by EDs in their general form\.

In this paper, forDL\-Liteℛ\\text\{DL\-Lite\}\_\{\\mathcal\{R\}\}ontologies and arbitrary EDs, we show that both GA\- and IGA\-entailment of BUCQs are intractable: specifically, they areΠ2p\\mathrm\{\\Pi\}^\{p\}\_\{2\}\-complete in data complexity, with hardness already holding even for an empty TBox\. Arbitrary EDs have a second important impact on the above entailment semantics: they do not enjoy a crucial property related to confidentiality preservation, known as*indistinguishability*\[[2](https://arxiv.org/html/2607.16715#bib.bib36)\]\. This property, already studied for EDs in\[[8](https://arxiv.org/html/2607.16715#bib.bib99)\], ensures that it is always possible to provide an ABox that contains no sensitive information, while guaranteeing that the CQE system with this new ABox as input behaves identically to the original one for every possible query\.

To overcome these limitations, we first continue investigating the linear case \(i\.e\. the case where only one atom occurs inqbq\_\{b\}\), without imposing the additional restrictions of\[[13](https://arxiv.org/html/2607.16715#bib.bib108)\]\. In this scenario, we observe that both GA\- and IGA\-entailment satisfy the indistinguishability property, and we show that both the BUCQ entailment problems become tractable in data complexity forDL\-Liteℛ\\text\{DL\-Lite\}\_\{\\mathcal\{R\}\}ontologies\. Linear EDs alone are, however, rather limited for expressing censoring rules: they cannot even capture denial assertions, which serve as thede factobaseline in most CQE studies, since they represent one of the most natural ways to specify protection rules\.

Thus, we propose a new approach, based on the notion of*minimal policy violation*\(MPV\)\. Each MPV is a minimal set of facts that are logical consequences of𝒯∪𝒜\\mathcal\{T\}\\cup\\mathcal\{A\}and that cause the violation of at least one ED in a given set of facts𝒜′\\mathcal\{A\}^\{\\prime\}\. Starting from a set𝒜′\\mathcal\{A\}^\{\\prime\}containing all the logical consequences of𝒯∪𝒜\\mathcal\{T\}\\cup\\mathcal\{A\}, we iteratively remove all occurring MPVs\. The fixpoint of such an iterative approach results in a GA censor, which we call an*MPV censor*\. We show that the resulting notion of MPV\-entailment:\(i\)\(i\)soundly approximates GA\- and IGA\-entailment and notably, coincides with IGA\-entailment when the dependencies are linear and the TBox is inDL\-Liteℛ\\text\{DL\-Lite\}\_\{\\mathcal\{R\}\}, or when the policy consists of denials;\(i​i\)\(ii\)satisfies the indistinguishability property;\(i​i​i\)\(iii\)is tractable \(PTIME\-complete\) in data complexity forDL\-Liteℛ\\text\{DL\-Lite\}\_\{\\mathcal\{R\}\}\.

Finally, we present an experimental evaluation of MPV\-entailment, focusing on the tractable setting identified in this paper, namelyDL\-Liteℛ\\text\{DL\-Lite\}\_\{\\mathcal\{R\}\}\. Unlike existing implementations\[[1](https://arxiv.org/html/2607.16715#bib.bib4),[13](https://arxiv.org/html/2607.16715#bib.bib108)\], which mainly rely on query rewriting techniques, our approach involves the construction of the MPV censor through suitable SQL\-based data manipulation queries\. Once the MPV censor is computed, query entailment is verified using standard techniques\. The experiments are based on OWL2Bench\[[17](https://arxiv.org/html/2607.16715#bib.bib2)\], a benchmark that supports the generation of custom\-sized ABoxes, which allowed us to test the scalability of our approach w\.r\.t\. the amount of ground data\.

The paper is organized as follows\. After recalling preliminary notions, in Section[3](https://arxiv.org/html/2607.16715#S3)we formally present our CQE framework\. Then, in Section[4](https://arxiv.org/html/2607.16715#S4)we analyze the computational properties of GA\- and IGA\-entailment in our framework\. In Section[5](https://arxiv.org/html/2607.16715#S5)we introduce the new MPV semantics for CQE and study the computational properties of MPV\-entailment for lightweight DLs\. In Section[6](https://arxiv.org/html/2607.16715#S6)we present our experimental evaluation of MPV\-entailment in the context ofDL\-Liteℛ\\text\{DL\-Lite\}\_\{\\mathcal\{R\}\}ontologies\. We conclude in Section[7](https://arxiv.org/html/2607.16715#S7)\.

## 2Preliminaries

We refer to standard notions of First\-Order \(FO\) Logic and Description Logic \(DL\)\. We consider an alphabetΣ\\mathrm\{\\Sigma\}of symbols partitioned into three countably infinite subsetsΣP\\mathrm\{\\Sigma\}\_\{P\},ΣV\\mathrm\{\\Sigma\}\_\{V\}, andΣI\\mathrm\{\\Sigma\}\_\{I\}, used respectively for denoting predicates, variables, and constant symbols \(or individuals\)\. In turn,ΣP\\mathrm\{\\Sigma\}\_\{P\}is partitioned into two mutually disjoint setsΣC\\mathrm\{\\Sigma\}\_\{C\}andΣR\\mathrm\{\\Sigma\}\_\{R\}, containing*concept*and*role*names, i\.e\., unary and binary predicates\. An*atom*α\\alphais a formula of the formP​\(t→\)P\(\\vec\{t\}\)where,P∈ΣPP\\in\\mathrm\{\\Sigma\}\_\{P\}andt→\\vec\{t\}is a sequence of*terms*\(i\.e\. symbols fromΣI∪ΣV\\mathrm\{\\Sigma\}\_\{I\}\\cup\\mathrm\{\\Sigma\}\_\{V\}\)\.α\\alphais called*ground*\(or a*fact*\) ifti∈ΣIt\_\{i\}\\in\\mathrm\{\\Sigma\}\_\{I\}for everyti∈t→t\_\{i\}\\in\\vec\{t\}\. An FO*sentence*is a formula without free variables\. To make explicit the free variablesx→\\vec\{x\}of a formulaϕ\\phi, we writeϕ​\(x→\)\\phi\(\\vec\{x\}\)\. Given an FO theory \(set of sentences\)Φ\\mathrm\{\\Phi\}, we denote byConst​\(Φ\)\\textit\{Const\}\(\\mathrm\{\\Phi\}\)the set of constants occurring in the formulas ofΦ\\mathrm\{\\Phi\}\. We writeeval​\(ϕ,ℐ\)\\textit\{eval\}\(\\phi,\\mathcal\{I\}\)to indicate the evaluation of an FO sentenceϕ\\phiover an FO interpretationℐ\\mathcal\{I\}\. A*model*of an FO theoryΦ\\Phiis an FO interpretation satisfying all sentences inΦ\\Phi\. We say thatΦ\\Phi*entails*an FO sentenceϕ\\phi, denoted byΦ⊧ϕ\\Phi\\models\\phi, ifeval​\(ϕ,ℐ\)\\textit\{eval\}\(\\phi,\\mathcal\{I\}\)is true in every modelℐ\\mathcal\{I\}ofΦ\\Phi\.

We use the term*query*as a synonym of FO formula\. We consider*conjunctive queries*\(CQs\), i\.e\., queries of the formq=∃x→​ϕ​\(y→\)q=\\exists\\vec\{x\}\\,\\phi\(\\vec\{y\}\), whereϕ\\phiis a conjunction of atoms andx→⊆y→\\vec\{x\}\\subseteq\\vec\{y\}\. Whenx→=y→\\vec\{x\}=\\vec\{y\}, we callqqa*Boolean conjunctive query*\(BCQ\)\.*\(Boolean\) unions of conjunctive queries*, or \(B\)UCQs, are disjunctions of \(Boolean\) conjunctive queriesq1​\(y→\)∨…∨qk​\(y→\)q\_\{1\}\(\\vec\{y\}\)\\lor\\ldots\\lor q\_\{k\}\(\\vec\{y\}\)\. We also consider the special ground CQ⊥\\botassuming thateval​\(⊥,ℐ\)\\textit\{eval\}\(\\bot,\\mathcal\{I\}\)is false for every FO interpretationℐ\\mathcal\{I\}\.

A*DL ontology*is an FO theory𝒪=𝒯∪𝒜\\mathcal\{O\}=\\mathcal\{T\}\\cup\\mathcal\{A\}, where𝒯\\mathcal\{T\}is called*TBox*and𝒜\\mathcal\{A\}is called*ABox*\. Every ABox is a set of facts, whereas the shape of a TBox depends on the specific DL considered\. The main complexity results provided in this work focus onDL\-Liteℛ\\text\{DL\-Lite\}\_\{\\mathcal\{R\}\}\[[6](https://arxiv.org/html/2607.16715#bib.bib98)\]\. In such a DL, a*basic role*RRis either a symbolP∈ΣRP\\in\\mathrm\{\\Sigma\}\_\{R\}, or its*inverse*P−P^\{\-\}\. A*basic concept*CCis either a symbol ofΣC\\mathrm\{\\Sigma\}\_\{C\}or a so\-called*unqualified existential restriction*∃R\\exists R, for some basic roleRR\. Then, aDL\-Liteℛ\\text\{DL\-Lite\}\_\{\\mathcal\{R\}\}TBox𝒯\\mathcal\{T\}is a finite set of inclusion and disjointness axioms between basic concepts or basic roles\. Specifically, these assertions take the formsC1⊑C2C\_\{1\}\\sqsubseteq C\_\{2\},C1⊑¬C2C\_\{1\}\\sqsubseteq\\neg C\_\{2\},R1⊑R2R\_\{1\}\\sqsubseteq R\_\{2\}, andR1⊑¬R2R\_\{1\}\\sqsubseteq\\neg R\_\{2\}, whereC1,C2C\_\{1\},C\_\{2\}are basic concepts andR1,R2R\_\{1\},R\_\{2\}are basic roles\.

Given an ontology𝒪=𝒯∪𝒜\\mathcal\{O\}=\\mathcal\{T\}\\cup\\mathcal\{A\}we write𝖼𝗅𝒯​\(𝒜\)\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)to denote the set of all ground atomsα\\alphasuch that𝒯∪𝒜⊧α\\mathcal\{T\}\\cup\\mathcal\{A\}\\models\\alpha\. Moreover, given a BUCQqqand an ontology𝒯∪𝒜\\mathcal\{T\}\\cup\\mathcal\{A\}, we call*image ofqqin𝒜\\mathcal\{A\}w\.r\.t\.𝒯\\mathcal\{T\}*any⊆\\subseteq\-minimal subsetI⊆𝒜I\\subseteq\\mathcal\{A\}such that𝒯∪I⊧q\\mathcal\{T\}\\cup I\\models q\. We denote byIm​\(q,𝒜,𝒯\)\\textit\{Im\}\(q,\\mathcal\{A\},\\mathcal\{T\}\)the set of all such images\.

All our complexity results refer to data complexity\[[18](https://arxiv.org/html/2607.16715#bib.bib14)\], i\.e\. the complexity with respect to the size of the ABox\. In the case ofDL\-Liteℛ\\text\{DL\-Lite\}\_\{\\mathcal\{R\}\}, standard entailment of a BUCQ is inPTIME\(actually inAC0\\mathrm\{AC\}^\{0\}\[[6](https://arxiv.org/html/2607.16715#bib.bib98)\]\) in data complexity\.

## 3CQE Framework

In CQE, data protection rules are expressed in terms of logical formulas\. In particular, we adopt epistemic dependencies\[[8](https://arxiv.org/html/2607.16715#bib.bib99)\], which are EQL\-Lite\(CQ\)\[[5](https://arxiv.org/html/2607.16715#bib.bib32)\]sentences defined as follows\.

###### Definition 1\(Epistemic dependency\)

An*epistemic dependency \(ED\)*is a sentenceτ\\tauof the following form

∀x→1,x→2​\(K​qb​\(x→1,x→2\)→K​qh​\(x→2\)\)\\forall\\vec\{x\}\_\{1\},\\vec\{x\}\_\{2\}\\,\(\\mathrm\{K\}q\_\{b\}\(\\vec\{x\}\_\{1\},\\vec\{x\}\_\{2\}\)\\rightarrow\\mathrm\{K\}q\_\{h\}\(\\vec\{x\}\_\{2\}\)\)

whereqb​\(x→1,x→2\)q\_\{b\}\(\\vec\{x\}\_\{1\},\\vec\{x\}\_\{2\}\)andqh​\(x→2\)q\_\{h\}\(\\vec\{x\}\_\{2\}\)are CQs, andK\\mathrm\{K\}denotes an epistemic operator\.111Observe that all the free variables ofqbq\_\{b\}andqhq\_\{h\}are universally quantified outside the scope of the implication\.Given an EDτ\\tauof the above form,𝖻𝗈𝖽𝗒​\(τ\)\\mathsf\{body\}\(\\tau\)denotesqbq\_\{b\}and𝗁𝖾𝖺𝖽​\(τ\)\\mathsf\{head\}\(\\tau\)denotesqhq\_\{h\}\.

Then, we call a finite set of EDs a*protection policy*\(or simply*policy*\)\. An EDτ\\tauis called*linear*if𝖻𝗈𝖽𝗒​\(τ\)\\mathsf\{body\}\(\\tau\)contains only one atom\. We indicate with𝖯𝖠\\mathsf\{P\_\{A\}\}and𝖯𝖫\\mathsf\{P\_\{L\}\}the classes of policies consisting, respectively, of arbitrary and linear EDs\. Moreover, given an EDτ\\tau, we call*ground substitution*forτ\\tauany mapping of its universally quantified variables to constants\. Then,gs​\(τ\)\\textit\{gs\}\(\\tau\)denotes the set of all the ground substitutions forτ\\tauand, given a setΓ\\Gammaof constants,gs​\(τ,Γ\)\\textit\{gs\}\(\\tau,\\Gamma\)denotes the finite subset ofgs​\(τ\)\\textit\{gs\}\(\\tau\)of substitutions over the constants ofΓ\\Gamma\.

An FO theoryΦ\\mathrm\{\\Phi\}is said to*satisfy*an EDτ\\tau\(writtenΦ⊧𝖤𝖰𝖫τ\\mathrm\{\\Phi\}\\models\_\{\\mathsf\{EQL\}\}\\tau\) if, for everyσ∈gs​\(τ\)\\sigma\\in\\textit\{gs\}\(\\tau\), wheneverΦ⊧𝖻𝗈𝖽𝗒​\(σ​\(τ\)\)\\mathrm\{\\Phi\}\\models\\mathsf\{body\}\(\\sigma\(\\tau\)\)holds, then alsoΦ⊧𝗁𝖾𝖺𝖽​\(σ​\(τ\)\)\\mathrm\{\\Phi\}\\models\\mathsf\{head\}\(\\sigma\(\\tau\)\)holds\. IfΦ\\mathrm\{\\Phi\}satisfies all EDs in a policy𝒫\\mathcal\{P\}, we say thatΦ\\mathrm\{\\Phi\}*satisfies*𝒫\\mathcal\{P\}, and writeΦ⊧𝖤𝖰𝖫𝒫\\mathrm\{\\Phi\}\\models\_\{\\mathsf\{EQL\}\}\\mathcal\{P\}\.

We remark that the above definition of satisfaction exploits the following property of the epistemic operatorK\\mathrm\{K\}in EQL: for every FO theoryΦ\\mathrm\{\\Phi\}and for every formula of the formK​ϕ\\mathrm\{K\}\\phisuch thatϕ\\phiis an FO sentence,Φ⊧𝖤𝖰𝖫K​ϕ\\mathrm\{\\Phi\}\\models\_\{\\mathsf\{EQL\}\}\\mathrm\{K\}\\phiiffΦ⊧ϕ\\mathrm\{\\Phi\}\\models\\phi\. Hence, the epistemic operator allows for expressing entailment with respect to an FO theory\. The next definitions exploit such a property so that, through the use of the epistemic operatorK\\mathrm\{K\}in EDs, the disclosability of a formula will be strictly related to the notion of FO entailment of the formula in the ontology\.

The tripleℰ=⟨𝒯,𝒫,𝒜⟩\\mathcal\{E\}=\\langle\\mathcal\{T\},\\mathcal\{P\},\\mathcal\{A\}\\rangle, called a*CQE instance*, contains the three main components of our framework\. Here,𝒯\\mathcal\{T\}is a DL TBox,𝒫\\mathcal\{P\}is a policy, and𝒜\\mathcal\{A\}is an ABox such that𝒯∪𝒜\\mathcal\{T\}\\cup\\mathcal\{A\}is consistent\. To emphasize that𝒯\\mathcal\{T\}is a TBox for a certain DLℒ\\mathcal\{L\}, we also callℰ\\mathcal\{E\}an*ℒ\\mathcal\{L\}CQE instance*\.

In general, it may happen that𝒯∪𝒜⊧̸𝖤𝖰𝖫𝒫\\mathcal\{T\}\\cup\\mathcal\{A\}\\not\\models\_\{\\mathsf\{EQL\}\}\\mathcal\{P\}, meaning that the ontology does not comply with the policy\. To prevent the disclosure of protected information, we adopt the notion of GA censor\[[9](https://arxiv.org/html/2607.16715#bib.bib102)\], which models a piece of ground knowledge that can be disclosed without violating the specified protection policy\.

###### Definition 2\(GA censor\)

Given a CQE instanceℰ=⟨𝒯,𝒫,𝒜⟩\\mathcal\{E\}=\\langle\\mathcal\{T\},\\mathcal\{P\},\\mathcal\{A\}\\rangle, a*ground atom \(GA\) censor*ofℰ\\mathcal\{E\}is any subset𝒞⊆𝖼𝗅𝒯​\(𝒜\)\\mathcal\{C\}\\subseteq\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)such that𝒯∪𝒞⊧𝖤𝖰𝖫𝒫\\mathcal\{T\}\\cup\\mathcal\{C\}\\models\_\{\\mathsf\{EQL\}\}\\mathcal\{P\}\. Furthermore, we call𝒞\\mathcal\{C\}*optimal*if no set𝒞′⊃𝒞\\mathcal\{C\}^\{\\prime\}\\supset\\mathcal\{C\}is a GA censor ofℰ\\mathcal\{E\}\. We denote by𝗈𝗉𝗍𝖢𝖾𝗇𝗌​\(ℰ\)\\mathsf\{optCens\}\(\\mathcal\{E\}\)the set of all the optimal GA censors ofℰ\\mathcal\{E\}\.

Since a given CQE instance may, in general, admit multiple optimal GA censors, a policy\-protected query answering framework must be equipped with a formal semantics specifying how censors are to be used in determining query entailment\. For GA censors, the most studied query answering semantics are the following ones\.

###### Definition 3\(GA\- and IGA\-entailment\)

For a CQE instanceℰ=⟨𝒯,𝒫,𝒜⟩\\mathcal\{E\}=\\langle\\mathcal\{T\},\\mathcal\{P\},\\mathcal\{A\}\\rangleand a BUCQqq, we say thatqqis

- •*GA\-entailed*byℰ\\mathcal\{E\}\(in symbols,ℰ⊧𝖦𝖠q\\mathcal\{E\}\\models\_\{\\mathsf\{GA\}\}q\) if𝒯∪𝒞⊧q\\mathcal\{T\}\\cup\\mathcal\{C\}\\models qfor each𝒞∈𝗈𝗉𝗍𝖢𝖾𝗇𝗌​\(ℰ\)\\mathcal\{C\}\\in\\mathsf\{optCens\}\(\\mathcal\{E\}\);
- •*IGA\-entailed*byℰ\\mathcal\{E\}\(in symbols,ℰ⊧𝖨𝖦𝖠q\\mathcal\{E\}\\models\_\{\\mathsf\{IGA\}\}q\) if𝒯∪𝒞𝖨𝖦𝖠ℰ⊧q\\mathcal\{T\}\\cup\\mathcal\{C\}\_\{\\mathsf\{IGA\}\}^\{\\mathcal\{E\}\}\\models q, where𝒞𝖨𝖦𝖠ℰ\\mathcal\{C\}\_\{\\mathsf\{IGA\}\}^\{\\mathcal\{E\}\}denotes the set⋂𝒞∈𝗈𝗉𝗍𝖢𝖾𝗇𝗌​\(ℰ\)𝒞\\bigcap\_\{\\mathcal\{C\}\\in\\mathsf\{optCens\}\(\\mathcal\{E\}\)\}\\mathcal\{C\}\.

We now introduce the decision problems related to the semantics defined above, parameterized with respect to a DLℒ\\mathcal\{L\}and a class of policiesCpC\_\{p\}\. We defineGA\-Ent​\[ℒ,Cp\]\\textsc\{GA\-Ent\}\[\\mathcal\{L\},C\_\{p\}\]\(resp\.,IGA\-Ent​\[ℒ,Cp\]\\textsc\{IGA\-Ent\}\[\\mathcal\{L\},C\_\{p\}\]\) as the problem of verifying whether, given anℒ\\mathcal\{L\}CQE instanceℰ=⟨𝒯,𝒫,𝒜⟩\\mathcal\{E\}=\\langle\\mathcal\{T\},\\mathcal\{P\},\\mathcal\{A\}\\ranglesuch that𝒫∈Cp\\mathcal\{P\}\\in C\_\{p\}and a BUCQqq,ℰ⊧𝖦𝖠q\\mathcal\{E\}\\models\_\{\\mathsf\{GA\}\}q\(resp\.,ℰ⊧𝖨𝖦𝖠q\\mathcal\{E\}\\models\_\{\\mathsf\{IGA\}\}q\)\.

Finally, we recall a fundamental property for CQE, namely indistinguishability\[[2](https://arxiv.org/html/2607.16715#bib.bib36)\], which has already been studied for EDs in\[[8](https://arxiv.org/html/2607.16715#bib.bib99)\]\. When enjoyed, this property ensures that a CQE system produces the same answers as a system whose ABox𝒜′\\mathcal\{A\}^\{\\prime\}is free of sensitive information\.

###### Definition 4\(Indistinguishability\)

Letℒ\\mathcal\{L\}be a DL andCpC\_\{p\}be a class of policies\. A CQE entailment relation⊧◇\\models\_\{\\Diamond\}satisfies the*indistinguishability*property forℒ\\mathcal\{L\}andCpC\_\{p\}if, for everyℒ\\mathcal\{L\}CQE instanceℰ=⟨𝒯,𝒫,𝒜⟩\\mathcal\{E\}=\\langle\\mathcal\{T\},\\mathcal\{P\},\\mathcal\{A\}\\ranglesuch that𝒫∈Cp\\mathcal\{P\}\\in C\_\{p\}, there exists a CQE instanceℰ′=⟨𝒯,𝒫,𝒜′⟩\\mathcal\{E\}^\{\\prime\}=\\langle\\mathcal\{T\},\\mathcal\{P\},\\mathcal\{A\}^\{\\prime\}\\ranglesuch that𝒯∪𝒜′⊧𝖤𝖰𝖫𝒫\\mathcal\{T\}\\cup\\mathcal\{A\}^\{\\prime\}\\models\_\{\\mathsf\{EQL\}\}\\mathcal\{P\}and, for every BUCQqq,ℰ⊧◇q\\mathcal\{E\}\\models\_\{\\Diamond\}qiffℰ′⊧◇q\\mathcal\{E\}^\{\\prime\}\\models\_\{\\Diamond\}q\.

## 4GA\- and IGA\-Entailment

We now study the data complexity of GA\- and IGA\-entailment in our CQE framework, first for arbitrary policies and then for linear policies\.

### 4\.1Arbitrary Epistemic Dependencies

We start by showing that both IGA\- and GA\-entailment are hard for the second level of the polynomial hierarchy, independently of the chosen DL\. This can be shown by adapting the proof of an analogous result provided in\[[7](https://arxiv.org/html/2607.16715#bib.bib46), Thm\. 4\.7\]in the context of database repairs\.

###### Lemma 1

For every DLℒ\\mathcal\{L\}, bothGA\-Ent​\[ℒ,𝖯𝖠\]\\textsc\{GA\-Ent\}\[\\mathcal\{L\},\\mathsf\{P\_\{A\}\}\]andIGA\-Ent​\[ℒ,𝖯𝖠\]\\textsc\{IGA\-Ent\}\[\\mathcal\{L\},\\mathsf\{P\_\{A\}\}\]areΠ2p\\mathrm\{\\Pi\}^\{p\}\_\{2\}\-hard in data complexity\.

###### Proof

We prove the thesis by showing a reduction from 2\-QBF, inspired by the proof of Theorem 4\.7 of\[[7](https://arxiv.org/html/2607.16715#bib.bib46)\]\. We assume that the given formula is in CNF\.

Let𝒯=∅\\mathcal\{T\}=\\emptyset, and let𝒫\\mathcal\{P\}consist of the following EDs:

∀v,t\(K​T​\(v,t\)→K​∃p​𝑃𝑜𝑠​\(v,p\)\)∀v,p\(K​𝑃𝑜𝑠​\(v,p\)→K​∃i​C​\(p,i\)\)∀p,t\(K​𝑃𝑜𝑙​\(p,t\)→K​∃i​C​\(p,i\)\)∀v,i\(K​C​\(v,i\)→K​∃j​S​\(i,j\)\)∀i,j\(K​S​\(i,j\)→K​∃v​C​\(v,j\)\)∀i,j\(KS\(i,j\)→K∃p,v,t\(C\(p,i\)∧𝑃𝑜𝑠\(v,p\)∧𝑃𝑜𝑙\(p,t\)∧T\(v,t\)\)\)∀v\(K​\(T​\(v,𝗍\)∧T​\(v,𝖿\)\)→K⊥\)\.\\begin\{array\}\[\]\{r@\{\\,\}l\}\\forall v,t&\(\\mathrm\{K\}T\(v,t\)\\rightarrow\\mathrm\{K\}\\exists p\\,\\mathit\{Pos\}\(v,p\)\)\\\\ \\forall v,p&\(\\mathrm\{K\}\\mathit\{Pos\}\(v,p\)\\rightarrow\\mathrm\{K\}\\exists i\\,C\(p,i\)\)\\\\ \\forall p,t&\(\\mathrm\{K\}\\mathit\{Pol\}\(p,t\)\\rightarrow\\mathrm\{K\}\\exists i\\,C\(p,i\)\)\\\\ \\forall v,i&\(\\mathrm\{K\}C\(v,i\)\\rightarrow\\mathrm\{K\}\\exists j\\,S\(i,j\)\)\\\\ \\forall i,j&\(\\mathrm\{K\}S\(i,j\)\\rightarrow\\mathrm\{K\}\\exists v\\,C\(v,j\)\)\\\\ \\forall i,j&\(\\mathrm\{K\}S\(i,j\)\\rightarrow\\mathrm\{K\}\\exists p,v,t\\,\(C\(p,i\)\\land\\mathit\{Pos\}\(v,p\)\\land\\\\ &\\hskip 95\.00014pt\\mathit\{Pol\}\(p,t\)\\land T\(v,t\)\)\)\\\\ \\forall v&\(\\mathrm\{K\}\(T\(v,\\mathsf\{t\}\)\\wedge T\(v,\\mathsf\{f\}\)\)\\rightarrow\\mathrm\{K\}\\bot\)\.\\end\{array\}Intuitively, the first four EDs impose what follows: every variable having a truth assignment must occur in some position; every position in which a variablevvoccurs \(or having polaritytt\) must occur in some clause; every clause must have a successor\. The combination of the fourth and fifth EDs forces a loop ofSS\-facts to collapse if one of them is missing\. The sixth ED imposes that, if a clauseψi\\psi\_\{i\}has a successorψj\\psi\_\{j\}, then a variablevvmust occur inψi\\psi\_\{i\}such that the truth value ofvvmatches its polarity inψi\\psi\_\{i\}\(i\.e\.,ψi\\psi\_\{i\}is satisfied\)\. Finally, the seventh ED guarantees that distinct truth values are not assigned to the same variable\.

Now letϕ=∀x→​∃y→​\(ψ1∧…∧ψn\)\\phi=\\forall\\vec\{x\}\\,\\exists\\vec\{y\}\\,\(\\psi\_\{1\}\\wedge\\ldots\\wedge\\psi\_\{n\}\)be a 2\-QBF, where everyψi\\psi\_\{i\}is a clause over the propositional variablesx→∪y→\\vec\{x\}\\cup\\vec\{y\}\. Moreover,𝒜=𝒜1∪𝒜2∪\{S​\(1,𝖺\)\}\\mathcal\{A\}=\\mathcal\{A\}\_\{1\}\\cup\\mathcal\{A\}\_\{2\}\\cup\\\{S\(1,\\mathsf\{a\}\)\\\}, where:

𝒜1=\{S\(0,0\)\}∪\{C\(𝗉x0,0\),𝑃𝑜𝑠\(𝗉x0,0\),𝑃𝑜𝑙\(𝗉x0,𝗍\),𝑃𝑜𝑙\(𝗉x0,𝖿\),T\(x,𝗍\),T\(x,𝖿\)∣x∈x→\}𝒜2=\{S\(i,\(imodn\)\+1\)∣1≤i≤n\}∪\{C\(𝗉vi,i\),𝑃𝑜𝑠\(v,𝗉vi\),𝑃𝑜𝑙\(𝗉vi,𝗍\),T\(v,𝗍\)∣voccurs positively inψi\}∪\{C\(𝗉vi,i\),𝑃𝑜𝑠\(v,𝗉vi\),𝑃𝑜𝑙\(𝗉vi,𝖿\),T\(v,𝖿\)∣voccurs negatively inψi\}\.\\begin\{array\}\[\]\{r@\{\\;\}l@\{\}l@\{\}l\}\\mathcal\{A\}\_\{1\}=&\\\{&S\(0,0\)\\\}\\,\\cup\\\\ &\\\{&C\(\\mathsf\{p\}\_\{x\}^\{0\},0\),\\mathit\{Pos\}\(\\mathsf\{p\}\_\{x\}^\{0\},0\),\\mathit\{Pol\}\(\\mathsf\{p\}\_\{x\}^\{0\},\\mathsf\{t\}\),\\mathit\{Pol\}\(\\mathsf\{p\}\_\{x\}^\{0\},\\mathsf\{f\}\),T\(x,\\mathsf\{t\}\),T\(x,\\mathsf\{f\}\)\\mid x\\in\\vec\{x\}\\\}\\\\ \\mathcal\{A\}\_\{2\}=&\\\{&S\(i,\(i\\bmod n\)\+1\)\\mid 1\\leq i\\leq n\\\}\\,\\cup\\\\ &\\\{&C\(\\mathsf\{p\}\_\{v\}^\{i\},i\),\\mathit\{Pos\}\(v,\\mathsf\{p\}\_\{v\}^\{i\}\),\\mathit\{Pol\}\(\\mathsf\{p\}\_\{v\}^\{i\},\\mathsf\{t\}\),T\(v,\\mathsf\{t\}\)\\mid v\\textrm\{ occurs positively in \}\\psi\_\{i\}\\\}\\,\\cup\\\\ &\\\{&C\(\\mathsf\{p\}\_\{v\}^\{i\},i\),\\mathit\{Pos\}\(v,\\mathsf\{p\}\_\{v\}^\{i\}\),\\mathit\{Pol\}\(\\mathsf\{p\}\_\{v\}^\{i\},\\mathsf\{f\}\),T\(v,\\mathsf\{f\}\)\\mid v\\textrm\{ occurs negatively in \}\\psi\_\{i\}\\\}\.\\end\{array\}We prove thatℰ⊧𝖦𝖠S​\(1,𝖺\)\\mathcal\{E\}\\models\_\{\\mathsf\{GA\}\}S\(1,\\mathsf\{a\}\)iffϕ\\phiis valid, whereℰ=⟨𝒯,𝒫,𝒜⟩\\mathcal\{E\}=\\langle\\mathcal\{T\},\\mathcal\{P\},\\mathcal\{A\}\\rangle\.

\(⇐\)\(\\Leftarrow\)First, for every interpretationIx→I\_\{\\vec\{x\}\}ofx→\\vec\{x\}, let

𝒜​\(Ix→\)=𝒜1∖\{T​\(x,𝖿\)∣x∈Ix→\}∖\{T​\(x,𝗍\)∣x∈x→∖Ix→\}\.\\mathcal\{A\}\(I\_\{\\vec\{x\}\}\)=\\mathcal\{A\}\_\{1\}\\setminus\\\{T\(x,\\mathsf\{f\}\)\\mid x\\in I\_\{\\vec\{x\}\}\\\}\\setminus\\\{T\(x,\\mathsf\{t\}\)\\mid x\\in\\vec\{x\}\\setminus I\_\{\\vec\{x\}\}\\\}\.
Now, let us assume thatϕ\\phiis not valid, and letIx→I\_\{\\vec\{x\}\}be an interpretation ofx→\\vec\{x\}such that there exists no interpretationIy→I\_\{\\vec\{y\}\}ofy→\\vec\{y\}such thatIx→∪Iy→I\_\{\\vec\{x\}\}\\cup I\_\{\\vec\{y\}\}satisfiesψ1∧…∧ψn\\psi\_\{1\}\\wedge\\ldots\\wedge\\psi\_\{n\}\. We prove that𝒜​\(Ix→\)\\mathcal\{A\}\(I\_\{\\vec\{x\}\}\)is an optimal GA censor ofℰ\\mathcal\{E\}\. Since𝒯∪𝒜​\(Ix→\)⊧𝖤𝖰𝖫𝒫\\mathcal\{T\}\\cup\\mathcal\{A\}\(I\_\{\\vec\{x\}\}\)\\models\_\{\\mathsf\{EQL\}\}\\mathcal\{P\}, we only have to show that no further fact from𝖼𝗅𝒯​\(𝒜\)\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)\(i\.e\. from𝒜\\mathcal\{A\}\) can be added to it without violating the policy𝒫\\mathcal\{P\}\.

First, notice that adding any fact from𝒜1\\mathcal\{A\}\_\{1\}to𝒜​\(Ix→\)\\mathcal\{A\}\(I\_\{\\vec\{x\}\}\)would violate the last dependency of𝒫\\mathcal\{P\}\. As for theTT\-facts contained in𝒜2\\mathcal\{A\}\_\{2\}, adding one of them would either violate the last dependency as well, or cause the addition of at least oneCC\-fact from𝒜2\\mathcal\{A\}\_\{2\}\(because of the first dependency\)\. However, if any fact from𝒜2∪\{S​\(1,𝖺\)\}\\mathcal\{A\}\_\{2\}\\cup\\\{S\(1,\\mathsf\{a\}\)\\\}with predicateCC,SS,𝑃𝑜𝑙\\mathit\{Pol\}, or𝑃𝑜𝑠\\mathit\{Pos\}is added to𝒜​\(Ix→\)\\mathcal\{A\}\(I\_\{\\vec\{x\}\}\), then the second, third, fourth and fifth dependencies would eventually require to add, for every clauseψi\\psi\_\{i\}, the corresponding factS​\(i,\(imodn\)\+1\)S\(i,\(i\\bmod n\)\+1\)from𝒜2\\mathcal\{A\}\_\{2\}\. Then, because of the sixth dependency, we would need to add, for everyψi\\psi\_\{i\}, four facts of the formC​\(p,i\)C\(p,i\),𝑃𝑜𝑠​\(v,p\)\\mathit\{Pos\}\(v,p\),𝑃𝑜𝑙​\(p,t\)\\mathit\{Pol\}\(p,t\),T​\(v,t\)T\(v,t\)from𝒜2\\mathcal\{A\}\_\{2\}for at least one variablevvoccurring inψi\\psi\_\{i\}\. However, due again to the last dependency of𝒫\\mathcal\{P\}and by construction of𝒜2\\mathcal\{A\}\_\{2\}, this could be done \(while preserving consistency\) only if it is possible to find a truth assignment for the variablesy→\\vec\{y\}such that at least one variable for each clauseψi\\psi\_\{i\}is assigned to a value corresponding to its polarity inψi\\psi\_\{i\}, i\.e\. only ifϕ\\phiis valid, which is a contradiction\. Consequently,𝒜​\(Ix→\)∈𝗈𝗉𝗍𝖢𝖾𝗇𝗌​\(ℰ\)\\mathcal\{A\}\(I\_\{\\vec\{x\}\}\)\\in\\mathsf\{optCens\}\(\\mathcal\{E\}\), which implies thatℰ⊧̸𝖦𝖠S​\(1,𝖺\)\\mathcal\{E\}\\not\\models\_\{\\mathsf\{GA\}\}S\(1,\\mathsf\{a\}\)\.

\(⇒\)\(\\Rightarrow\)Conversely, assume thatϕ\\phiis valid\. LetIx→I\_\{\\vec\{x\}\}be any interpretation ofx→\\vec\{x\}\. Then, there exists an interpretationIy→I\_\{\\vec\{y\}\}ofy→\\vec\{y\}such thatIx→∪Iy→I\_\{\\vec\{x\}\}\\cup I\_\{\\vec\{y\}\}satisfiesψ1∧…∧ψn\\psi\_\{1\}\\wedge\\ldots\\wedge\\psi\_\{n\}\. Similarly as above, this is possible only if there exists a subset𝒜′\\mathcal\{A\}^\{\\prime\}of𝒜2\\mathcal\{A\}\_\{2\}containing, for every1≤i≤n1\\leq i\\leq n, at least five facts of the formS​\(i,\(imodn\)\+1\)S\(i,\(i\\bmod n\)\+1\),C​\(p,i\)C\(p,i\),𝑃𝑜𝑠​\(v,p\)\\mathit\{Pos\}\(v,p\),𝑃𝑜𝑙​\(p,t\)\\mathit\{Pol\}\(p,t\),T​\(v,t\)T\(v,t\)and such that, for every variablevv, it does not contain bothT​\(v,𝗍\)T\(v,\\mathsf\{t\}\)andT​\(v,𝖿\)T\(v,\\mathsf\{f\}\)\.

It is immediate to verify that𝒯∪𝒜′⊧𝖤𝖰𝖫𝒫\\mathcal\{T\}\\cup\\mathcal\{A\}^\{\\prime\}\\models\_\{\\mathsf\{EQL\}\}\\mathcal\{P\}\. Now, suppose thatS​\(1,𝖺\)∉𝒞S\(1,\\mathsf\{a\}\)\\notin\\mathcal\{C\}for some𝒞∈𝗈𝗉𝗍𝖢𝖾𝗇𝗌​\(ℰ\)\\mathcal\{C\}\\in\\mathsf\{optCens\}\(\\mathcal\{E\}\)\. Since𝒞\\mathcal\{C\}is optimal, this is possible only if addingS​\(1,𝖺\)S\(1,\\mathsf\{a\}\)violates the fourth dependency, i\.e\. if no fact of the formC​\(\_,1\)C\(\\\_,1\)of𝒜\\mathcal\{A\}occurs in𝒞\\mathcal\{C\}\. Then, because of the fifth dependency, the factS​\(n,1\)S\(n,1\)\(i\.e\., the only fact of𝒜\\mathcal\{A\}of the formS​\(\_,1\)S\(\\\_,1\)\) does not belong to𝒞\\mathcal\{C\}\. Analogously,𝒞\\mathcal\{C\}cannot contain any fact of the formC​\(\_,n\)C\(\\\_,n\), norS​\(n−1,n\)S\(n\-1,n\), and so on: considering the effect of the first three dependencies as well, this iterative process forces*all*facts with predicate𝑃𝑜𝑠\\mathit\{Pos\},𝑃𝑜𝑙\\mathit\{Pol\},CCandSSoccurring in𝒜2\\mathcal\{A\}\_\{2\}to be excluded from𝒞\\mathcal\{C\}, other than all the facts of the formT​\(y,\_\)T\(y,\\\_\)such thaty∈y→y\\in\\vec\{y\}\. Note then that𝒞⊆𝒜1\\mathcal\{C\}\\subseteq\\mathcal\{A\}\_\{1\}, and recall that𝒯∪𝒞⊧𝖤𝖰𝖫𝒫\\mathcal\{T\}\\cup\\mathcal\{C\}\\models\_\{\\mathsf\{EQL\}\}\\mathcal\{P\}by definition of GA censor\. It is now straightforward to verify that𝒯∪𝒞∪𝒜′⊧𝖤𝖰𝖫𝒫\\mathcal\{T\}\\cup\\mathcal\{C\}\\cup\\mathcal\{A\}^\{\\prime\}\\models\_\{\\mathsf\{EQL\}\}\\mathcal\{P\}, thus contradicting the optimality of𝒞\\mathcal\{C\}\. Consequently,S​\(1,𝖺\)S\(1,\\mathsf\{a\}\)belongs to every optimal GA ofℰ\\mathcal\{E\}, i\.e\.ℰ⊧𝖦𝖠S​\(1,𝖺\)\\mathcal\{E\}\\models\_\{\\mathsf\{GA\}\}S\(1,\\mathsf\{a\}\)\.

Finally, we recall thatℰ⊧𝖦𝖠α\\mathcal\{E\}\\models\_\{\\mathsf\{GA\}\}\\alphaiffℰ⊧𝖨𝖦𝖠α\\mathcal\{E\}\\models\_\{\\mathsf\{IGA\}\}\\alphawhenα\\alphais a ground atom; thus, both theses are proved\. ∎

We then provide an upper bound for the same complexity class\. We start by showing a fundamental property of𝒞𝖨𝖦𝖠ℰ\\mathcal\{C\}\_\{\\mathsf\{IGA\}\}^\{\\mathcal\{E\}\}\. In the following, given a CQE instanceℰ=⟨𝒯,𝒫,𝒜⟩\\mathcal\{E\}=\\langle\\mathcal\{T\},\\mathcal\{P\},\\mathcal\{A\}\\rangle, we say that a set of facts from𝖼𝗅𝒯​\(𝒜\)\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)is*ℰ\\mathcal\{E\}\-disclosable*if it is contained in some GA censor ofℰ\\mathcal\{E\}, and*ℰ\\mathcal\{E\}\-undisclosable*otherwise\.

###### Proposition 1

Letℰ=⟨𝒯,𝒫,𝒜⟩\\mathcal\{E\}=\\langle\\mathcal\{T\},\\mathcal\{P\},\\mathcal\{A\}\\ranglebe a CQE instance\. For everyα∈𝖼𝗅𝒯​\(𝒜\)\\alpha\\in\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\),α∈𝒞𝖨𝖦𝖠ℰ\\alpha\\in\\mathcal\{C\}\_\{\\mathsf\{IGA\}\}^\{\\mathcal\{E\}\}iffα\\alphadoes not belong to any⊆\\subseteq\-minimalℰ\\mathcal\{E\}\-undisclosable subset of𝖼𝗅𝒯​\(𝒜\)\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)\.

###### Proof

\(⇒\)\(\\Rightarrow\)Letα∉𝒞𝖨𝖦𝖠ℰ\\alpha\\notin\\mathcal\{C\}\_\{\\mathsf\{IGA\}\}^\{\\mathcal\{E\}\}, which implies thatα∉𝒞\\alpha\\notin\\mathcal\{C\}for some𝒞∈𝗈𝗉𝗍𝖢𝖾𝗇𝗌​\(ℰ\)\\mathcal\{C\}\\in\\mathsf\{optCens\}\(\\mathcal\{E\}\)\. Since𝒞\\mathcal\{C\}is optimal, then𝒞∪\{α\}\\mathcal\{C\}\\cup\\\{\\alpha\\\}isℰ\\mathcal\{E\}\-undisclosable\. Moreover, every⊆\\subseteq\-minimal subsetSSof𝒞\\mathcal\{C\}such thatSSisℰ\\mathcal\{E\}\-undisclosable \(at least one of which does exist\) containsα\\alpha\.

\(⇐\)\(\\Leftarrow\)Letα\\alphabelong to some⊆\\subseteqminimalℰ\\mathcal\{E\}\-undisclosable subsetSSof𝖼𝗅𝒯​\(𝒜\)\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)\. By minimality, we have thatS∖\{α\}S\\setminus\\\{\\alpha\\\}is contained in some GA censor𝒞\\mathcal\{C\}ofℰ\\mathcal\{E\}, which obviously does not containα\\alpha\. Consequently,α∉𝒞𝖨𝖦𝖠ℰ\\alpha\\notin\\mathcal\{C\}\_\{\\mathsf\{IGA\}\}^\{\\mathcal\{E\}\}\. ∎

input :A CQE instance

ℰ=⟨𝒯,𝒫,𝒜⟩\\mathcal\{E\}=\\langle\\mathcal\{T\},\\mathcal\{P\},\\mathcal\{A\}\\rangle, a set of facts

𝒞\\mathcal\{C\}such that

𝒞⊆𝖼𝗅𝒯​\(𝒜\)\\mathcal\{C\}\\subseteq\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\);

output :A Boolean value;

*1*if*there exists a set of facts𝒞′\\mathcal\{C\}^\{\\prime\}such that:*

*2*

\(i\)\(i\)𝒞⊆𝒞′⊆𝖼𝗅𝒯​\(𝒜\)\\mathcal\{C\}\\subseteq\\mathcal\{C\}^\{\\prime\}\\subseteq\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)and

*3*

\(i​i\)\(ii\)for each

τ∈𝒫\\tau\\in\\mathcal\{P\}and

σ∈*gs*​\(τ,*Const*​\(𝒜\)\)\\sigma\\in\\textit\{gs\}\(\\tau,\\textit\{Const\}\(\\mathcal\{A\}\)\)
4

𝒯∪𝒞′⊧̸𝖻𝗈𝖽𝗒​\(σ​\(τ\)\)\\mathcal\{T\}\\cup\\mathcal\{C\}^\{\\prime\}\\not\\models\\mathsf\{body\}\(\\sigma\(\\tau\)\)or

𝒯∪𝒞′⊧𝗁𝖾𝖺𝖽​\(σ​\(τ\)\)\\mathcal\{T\}\\cup\\mathcal\{C\}^\{\\prime\}\\models\\mathsf\{head\}\(\\sigma\(\\tau\)\)then

5return*true;*

return*false;*

Algorithm 1𝖣𝗂𝗌𝖼𝗅𝗈𝗌𝖺𝖻𝗅𝖾\\mathsf\{Disclosable\}Algorithm[1](https://arxiv.org/html/2607.16715#algorithm1)simply guesses a superset of𝒞\\mathcal\{C\}and checks that it is a GA censor ofℰ\\mathcal\{E\}\. Then, the next property immediately follows by definition ofℰ\\mathcal\{E\}\-disclosability\.

###### Lemma 2

Letℰ=⟨𝒯,𝒫,𝒜⟩\\mathcal\{E\}=\\langle\\mathcal\{T\},\\mathcal\{P\},\\mathcal\{A\}\\ranglebe a CQE instance and let𝒞\\mathcal\{C\}be a set of ground atoms such that𝒞⊆𝖼𝗅𝒯​\(𝒜\)\\mathcal\{C\}\\subseteq\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)\. Then𝖣𝗂𝗌𝖼𝗅𝗈𝗌𝖺𝖻𝗅𝖾​\(ℰ,𝒞\)\\mathsf\{Disclosable\}\(\\mathcal\{E\},\\mathcal\{C\}\)returnstrueiff𝒞\\mathcal\{C\}is anℰ\\mathcal\{E\}\-disclosable subset of𝖼𝗅𝒯​\(𝒜\)\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)\.

input :A CQE instance

ℰ=⟨𝒯,𝒫,𝒜⟩\\mathcal\{E\}=\\langle\\mathcal\{T\},\\mathcal\{P\},\\mathcal\{A\}\\rangle, a BUCQ

qq;

output :A Boolean value;

*1*if*there exist an integerm≤\|𝖼𝗅𝒯​\(𝒜\)\|m\\leq\|\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)\|and sets𝒜′,S1,…,Sm⊆𝖼𝗅𝒯​\(𝒜\)\\mathcal\{A\}^\{\\prime\},S\_\{1\},\\ldots,S\_\{m\}\\subseteq\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)*

*2**\(with*

𝖼𝗅𝒯​\(𝒜\)∖𝒜′=\{α1,…,αm\}\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)\\setminus\\mathcal\{A\}^\{\\prime\}=\\allowbreak\\\{\\alpha\_\{1\},\\ldots,\\alpha\_\{m\}\\\}\) such that:

*3*2

𝒯∪𝒜′⊧̸q\\mathcal\{T\}\\cup\\mathcal\{A\}^\{\\prime\}\\not\\models q
*4*2for each

1≤i≤m1\\leq i\\leq m:

*5*2

αi∈Si\\alpha\_\{i\}\\in S\_\{i\}
*6*2

𝖣𝗂𝗌𝖼𝗅𝗈𝗌𝖺𝖻𝗅𝖾​\(ℰ,Si\)=*false*\\mathsf\{Disclosable\}\(\\mathcal\{E\},S\_\{i\}\)=\\texttt\{false\}
72for each

β∈Si\\beta\\in S\_\{i\},

𝖣𝗂𝗌𝖼𝗅𝗈𝗌𝖺𝖻𝗅𝖾​\(ℰ,Si∖\{β\}\)=*true*\\mathsf\{Disclosable\}\(\\mathcal\{E\},S\_\{i\}\\setminus\\\{\\beta\\\}\)=\\texttt\{true\}then

8return*false;*

return*true;*

Algorithm 2𝖨𝖦𝖠​\-​𝖤𝗇𝗍𝖺𝗂𝗅𝗌\\mathsf\{IGA\\text\{\-\}Entails\}We are now ready to introduce the algorithm𝖨𝖦𝖠​\-​𝖤𝗇𝗍𝖺𝗂𝗅𝗌\\mathsf\{IGA\\text\{\-\}Entails\}\(Algorithm[2](https://arxiv.org/html/2607.16715#algorithm2)\), which allows us to establish the next upper bound\.

###### Theorem 4\.1

IGA\-Ent​\[DL\-Liteℛ,𝖯𝖠\]\\textsc\{IGA\-Ent\}\[\\text\{DL\-Lite\}\_\{\\mathcal\{R\}\},\\mathsf\{P\_\{A\}\}\]isΠ2p\\mathrm\{\\Pi\}^\{p\}\_\{2\}\-complete in data complexity\.

###### Proof

The lower bound has been established in Lemma[1](https://arxiv.org/html/2607.16715#Thmlemma1)\. As for the upper bound, we first note that, forDL\-Liteℛ\\text\{DL\-Lite\}\_\{\\mathcal\{R\}\}TBoxes, Algorithm[1](https://arxiv.org/html/2607.16715#algorithm1)always terminates\. Moreover, in the given scenario, we prove that the algorithm decides whetherℰ⊧𝖨𝖦𝖠q\\mathcal\{E\}\\models\_\{\\mathsf\{IGA\}\}qin a sound and complete way\.

Remark 1\.Note that, by Lemma[2](https://arxiv.org/html/2607.16715#Thmlemma2), the combination of Conditions[2](https://arxiv.org/html/2607.16715#algorithm2)and[2](https://arxiv.org/html/2607.16715#algorithm2)cause eachSiS\_\{i\}to be a⊆\\subseteq\-minimalℰ\\mathcal\{E\}\-undisclosable subset of𝖼𝗅𝒯​\(𝒜\)\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)\. Therefore, since[2](https://arxiv.org/html/2607.16715#algorithm2)requiresαi∈Si\\alpha\_\{i\}\\in S\_\{i\}for every1≤i≤m1\\leq i\\leq m, by Proposition[1](https://arxiv.org/html/2607.16715#Thmproposition1)the whole Condition[2](https://arxiv.org/html/2607.16715#algorithm2)holds iff𝒜′⊇𝒞𝖨𝖦𝖠ℰ\\mathcal\{A\}^\{\\prime\}\\supseteq\\mathcal\{C\}\_\{\\mathsf\{IGA\}\}^\{\\mathcal\{E\}\}\.

Now, if𝒯∪𝒞𝖨𝖦𝖠ℰ⊧̸q\\mathcal\{T\}\\cup\\mathcal\{C\}\_\{\\mathsf\{IGA\}\}^\{\\mathcal\{E\}\}\\not\\models q, then the algorithm guesses𝒜′=𝒞𝖨𝖦𝖠ℰ\\mathcal\{A\}^\{\\prime\}=\\mathcal\{C\}\_\{\\mathsf\{IGA\}\}^\{\\mathcal\{E\}\}and\{α1,…,αm\}=𝖼𝗅𝒯​\(𝒜\)∖𝒞𝖨𝖦𝖠ℰ\\\{\\alpha\_\{1\},\\allowbreak\\ldots,\\allowbreak\\alpha\_\{m\}\\\}=\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)\\setminus\\mathcal\{C\}\_\{\\mathsf\{IGA\}\}^\{\\mathcal\{E\}\}, for which both Conditions[2](https://arxiv.org/html/2607.16715#algorithm2)and[2](https://arxiv.org/html/2607.16715#algorithm2)hold \(respectively, because𝒯∪𝒜′=𝒯∪𝒞𝖨𝖦𝖠ℰ⊧̸q\\mathcal\{T\}\\cup\\mathcal\{A\}^\{\\prime\}=\\mathcal\{T\}\\cup\\mathcal\{C\}\_\{\\mathsf\{IGA\}\}^\{\\mathcal\{E\}\}\\not\\models qand by Remark[4\.1](https://arxiv.org/html/2607.16715#Thmproofx3)\)\. This proves the soundness of the algorithm\.

On the other hand, consider any guess for which both Conditions[2](https://arxiv.org/html/2607.16715#algorithm2)and[2](https://arxiv.org/html/2607.16715#algorithm2)hold\. By Remark[4\.1](https://arxiv.org/html/2607.16715#Thmproofx3),𝒜′\\mathcal\{A\}^\{\\prime\}is such that𝒜′⊇𝒞𝖨𝖦𝖠ℰ\\mathcal\{A\}^\{\\prime\}\\supseteq\\mathcal\{C\}\_\{\\mathsf\{IGA\}\}^\{\\mathcal\{E\}\}\. Since𝒯∪𝒜′⊧̸q\\mathcal\{T\}\\cup\\mathcal\{A\}^\{\\prime\}\\not\\models q, then by monotonicity of FO entailment we have that𝒯∪𝒞𝖨𝖦𝖠ℰ⊧̸q\\mathcal\{T\}\\cup\\mathcal\{C\}\_\{\\mathsf\{IGA\}\}^\{\\mathcal\{E\}\}\\not\\models q, which proves the completeness of the algorithm\.

Finally, note that:

1. \(i\)\(i\)computing𝖼𝗅𝒯​\(𝒜\)\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)requires polynomial time in data complexity;
2. \(i​i\)\(ii\)Condition[2](https://arxiv.org/html/2607.16715#algorithm2)can be verified in polynomial time in data complexity \(by hypothesis\);
3. \(i​i​i\)\(iii\)Condition[2](https://arxiv.org/html/2607.16715#algorithm2)consists of a polynomial number of calls to an NP oracle \(i\.e\. Algorithm[1](https://arxiv.org/html/2607.16715#algorithm1)\)\. Indeed, such an algorithm guesses a superset ofSiS\_\{i\}and then makes a polynomial number of BCQ entailment checks \(note that\|gs​\(τ,Const​\(𝒜\)\)\|∼Θ​\(nk\)\|\\textit\{gs\}\(\\tau,\\textit\{Const\}\(\\mathcal\{A\}\)\)\|\\sim\\Theta\(n^\{k\}\), wheren=\|𝒜\|n=\|\\mathcal\{A\}\|andkkis the number of universally quantified variables ofτ\\tau\)\.

Then, the thesis follows from the above properties\. ∎

The same upper bound can be proven forGA\-Ent, again using Algorithm[1](https://arxiv.org/html/2607.16715#algorithm1)\.

###### Theorem 4\.2

GA\-Ent​\[DL\-Liteℛ,𝖯𝖠\]\\textsc\{GA\-Ent\}\[\\text\{DL\-Lite\}\_\{\\mathcal\{R\}\},\\mathsf\{P\_\{A\}\}\]isΠ2p\\mathrm\{\\Pi\}^\{p\}\_\{2\}\-complete in data complexity\.

###### Proof

The lower bound follows from Lemma[1](https://arxiv.org/html/2607.16715#Thmlemma1)\. As for the upper bound, observe that𝗈𝗉𝗍𝖢𝖾𝗇𝗌​\(ℰ\)\\mathsf\{optCens\}\(\\mathcal\{E\}\)is the set of all subsets𝒞\\mathcal\{C\}of𝖼𝗅𝒯​\(𝒜\)\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)such that\(i\)\(i\)𝒞\\mathcal\{C\}isℰ\\mathcal\{E\}\-disclosable and\(i​i\)\(ii\)for everyα∈𝖼𝗅𝒯​\(𝒜\)∖𝒞\\alpha\\in\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)\\setminus\\mathcal\{C\},𝒞∪\{α\}\\mathcal\{C\}\\cup\\\{\\alpha\\\}isℰ\\mathcal\{E\}\-undisclosable\. Consequently,GA\-Entcan be decided by guessing a set𝒞⊆𝖼𝗅𝒯​\(𝒜\)\\mathcal\{C\}\\subseteq\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)and checking that\(i\)\(i\)𝒞\\mathcal\{C\}isℰ\\mathcal\{E\}\-disclosable,\(i​i\)\(ii\)𝒞\\mathcal\{C\}becomesℰ\\mathcal\{E\}\-undisclosable when adding anyα\\alphafrom𝖼𝗅𝒯​\(𝒜\)\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\), and\(i​i​i\)\(iii\)𝒯∪𝒞⊧̸q\\mathcal\{T\}\\cup\\mathcal\{C\}\\not\\models q\. Since checkingℰ\\mathcal\{E\}\-disclosability is an NP task \(as shown in the proof of Theorem[4\.1](https://arxiv.org/html/2607.16715#S4.Thmtheorem1)\), the thesis follows\. ∎

Finally, we note that Example 5 of\[[3](https://arxiv.org/html/2607.16715#bib.bib107)\]can be used to show that GA\-entailment does not enjoy the indistinguishability property already for policies consisting of denials\. Indeed, that example shows that the set𝒞𝖨𝖦𝖠ℰ\\mathcal\{C\}\_\{\\mathsf\{IGA\}\}^\{\\mathcal\{E\}\}in general is not a GA censor\. When this happens, one can see that there exists no ABox𝒜′\\mathcal\{A\}^\{\\prime\}satisfying the requirements of Definition[4](https://arxiv.org/html/2607.16715#Thmdefinition4)\.

###### Proposition 2

For any DLℒ\\mathcal\{L\}, both GA\- and IGA\-entailment fail to satisfy the indistinguishability property forℒ\\mathcal\{L\}and𝖯𝖠\\mathsf\{P\_\{A\}\}\.

###### Proof

Recalling Example 1 of\[[13](https://arxiv.org/html/2607.16715#bib.bib108)\], consider the CQE instanceℰ=⟨𝒯,𝒫,𝒜⟩\\mathcal\{E\}=\\langle\\mathcal\{T\},\\mathcal\{P\},\\mathcal\{A\}\\rangle, where𝒯=∅\\mathcal\{T\}=\\emptyset,𝒜=\{C​\(0\),B​\(1\),B​\(2\)\}\\mathcal\{A\}=\\\{C\(0\),B\(1\),B\(2\)\\,\\\}, and𝒫=\{K​\(B​\(1\)∧B​\(2\)\)→K⊥,∀x​\(K​C​\(x\)→K​∃y​B​\(y\)\)\}\\mathcal\{P\}=\\\{K\(B\(1\)\\land B\(2\)\)\\rightarrow K\\bot,\\forall x\\,\(KC\(x\)\\rightarrow K\\exists y\\,B\(y\)\)\\\}\.

Note that𝒞𝖨𝖦𝖠ℰ\\mathcal\{C\}\_\{\\mathsf\{IGA\}\}^\{\\mathcal\{E\}\}\(i\.e\.\{C​\(0\)\}\\\{C\(0\)\\\}\) is not a GA censor ofℰ\\mathcal\{E\}\(as it does not satisfy the second ED of𝒫\\mathcal\{P\}\)\. Then, consider the BCQq=C​\(0\)q=C\(0\)\(which is both GA\- and IGA\-entailed byℰ\\mathcal\{E\}\), and let𝒜′\\mathcal\{A\}^\{\\prime\}be any ABox such that𝒯∪𝒜′⊧𝖤𝖰𝖫𝒫\\mathcal\{T\}\\cup\\mathcal\{A\}^\{\\prime\}\\models\_\{\\mathsf\{EQL\}\}\\mathcal\{P\}and𝒯∪𝒜′⊧𝖦𝖠q\\mathcal\{T\}\\cup\\mathcal\{A\}^\{\\prime\}\\models\_\{\\mathsf\{GA\}\}q\(resp\.,𝒯∪𝒜′⊧𝖨𝖦𝖠q\\mathcal\{T\}\\cup\\mathcal\{A\}^\{\\prime\}\\models\_\{\\mathsf\{IGA\}\}q\)\. It is immediate to see that every such𝒜′\\mathcal\{A\}^\{\\prime\}is such that𝒯∪𝒜′⊧𝖦𝖠B​\(c\)\\mathcal\{T\}\\cup\\mathcal\{A\}^\{\\prime\}\\models\_\{\\mathsf\{GA\}\}B\(c\)\(resp\.,𝒯∪𝒜′⊧𝖨𝖦𝖠B​\(c\)\\mathcal\{T\}\\cup\\mathcal\{A\}^\{\\prime\}\\models\_\{\\mathsf\{IGA\}\}B\(c\)\), for some constantcc\. ∎

### 4\.2Linear Epistemic Dependencies

All the negative results presented in Section[4\.1](https://arxiv.org/html/2607.16715#S4.SS1)motivate the need to investigate different approaches to the CQE problem in order to gain indistinguishability and, possibly, tractability of BUCQ entailment\.

We first focus on the notable class of linear EDs\. We remark that, as observed in\[[13](https://arxiv.org/html/2607.16715#bib.bib108)\], for linear EDs, only one optimal GA censor exists for everyDL\-Liteℛ\\text\{DL\-Lite\}\_\{\\mathcal\{R\}\}CQE instanceℰ\\mathcal\{E\}, which obviously coincides with𝒞𝖨𝖦𝖠ℰ\\mathcal\{C\}\_\{\\mathsf\{IGA\}\}^\{\\mathcal\{E\}\}\. We thus have, in this case, that GA\-entailment collapses to IGA\-entailment\. Also, the fact that the set𝒞𝖨𝖦𝖠ℰ\\mathcal\{C\}\_\{\\mathsf\{IGA\}\}^\{\\mathcal\{E\}\}is a GA censor ofℰ\\mathcal\{E\}means that it can play the role of the ABox𝒜′\\mathcal\{A\}^\{\\prime\}of Definition[4](https://arxiv.org/html/2607.16715#Thmdefinition4), which implies the next property\.

###### Proposition 3

Both GA\- and IGA\-entailment satisfy the indistinguishability property forDL\-Liteℛ\\text\{DL\-Lite\}\_\{\\mathcal\{R\}\}and𝖯𝖫\\mathsf\{P\_\{L\}\}\.

For linear EDs and forDL\-Liteℛ\\text\{DL\-Lite\}\_\{\\mathcal\{R\}\}ontologies, the paper\[[13](https://arxiv.org/html/2607.16715#bib.bib108)\]showed that when dependencies are also*full*\(i\.e\. their heads contain no existentially quantified variable\),GA\-EntandIGA\-Entbecome FO\-rewritable\. We show that the problems remain tractable—more precisely, they are both PTIME\-complete—when the full condition is not applied\. The aforementioned paper suggests a procedure for computing𝒞𝖨𝖦𝖠ℰ\\mathcal\{C\}\_\{\\mathsf\{IGA\}\}^\{\\mathcal\{E\}\}that, informally, iteratively removes from𝖼𝗅𝒯​\(𝒜\)\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)any fact that, together with𝒯\\mathcal\{T\}, leads to a violation of𝒫\\mathcal\{P\}, until a fixpoint is reached\. Here, we formalize that procedure in the following equivalent way\.

###### Definition 5\(LPV\)

Given a linearDL\-Liteℛ\\text\{DL\-Lite\}\_\{\\mathcal\{R\}\}CQE instanceℰ=⟨𝒯,𝒫,𝒜⟩\\mathcal\{E\}=\\langle\\mathcal\{T\},\\mathcal\{P\},\\mathcal\{A\}\\rangleand a subset𝒜′\\mathcal\{A\}^\{\\prime\}of𝖼𝗅𝒯​\(𝒜\)\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\), a*linear policy violation \(LPV\)*ofℰ\\mathcal\{E\}w\.r\.t\.𝒜′\\mathcal\{A\}^\{\\prime\}is an atomα∈𝖼𝗅𝒯​\(𝒜\)\\alpha\\in\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)such that there existτ∈𝒫\\tau\\in\\mathcal\{P\}andσ∈gs​\(τ\)\\sigma\\in\\textit\{gs\}\(\\tau\)such that𝒯∪\{α\}⊧𝖻𝗈𝖽𝗒​\(σ​\(τ\)\)\\mathcal\{T\}\\cup\\\{\\alpha\\\}\\models\\mathsf\{body\}\(\\sigma\(\\tau\)\)and𝒯∪𝒜′⊧̸𝗁𝖾𝖺𝖽​\(σ​\(τ\)\)\\mathcal\{T\}\\cup\\mathcal\{A\}^\{\\prime\}\\not\\models\\mathsf\{head\}\(\\sigma\(\\tau\)\)\.

We denote byLPV0​\(ℰ,𝒜′\)\\textit\{LPV\}\_\{0\}\(\\mathcal\{E\},\\mathcal\{A\}^\{\\prime\}\)the set constituted by the union of all the LPVs ofℰ\\mathcal\{E\}w\.r\.t\.𝒜′\\mathcal\{A\}^\{\\prime\}\. Then, we defineLPV​\(ℰ,0\)=∅\\textit\{LPV\}\(\\mathcal\{E\},0\)=\\emptyset, and, for every integeri≥0i\\geq 0:

LPV​\(ℰ,i\+1\)=LPV0​\(ℰ,𝖼𝗅𝒯​\(𝒜\)∖LPV​\(ℰ,i\)\)\\textit\{LPV\}\(\\mathcal\{E\},i\+1\)=\\textit\{LPV\}\_\{0\}\(\\mathcal\{E\},\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)\\setminus\\textit\{LPV\}\(\\mathcal\{E\},i\)\)

We now show the convergence of the above notion ofLPV​\(ℰ,i\)\\textit\{LPV\}\(\\mathcal\{E\},i\)to a fixpoint\.

###### Proposition 4

Letℰ=⟨𝒯,𝒫,𝒜⟩\\mathcal\{E\}=\\langle\\mathcal\{T\},\\mathcal\{P\},\\mathcal\{A\}\\ranglebe a linearDL\-Liteℛ\\text\{DL\-Lite\}\_\{\\mathcal\{R\}\}CQE instance\. Then:\(i\)\(i\)for every non\-negative integerii,LPV​\(ℰ,i\+1\)⊇LPV​\(ℰ,i\)\\textit\{LPV\}\(\\mathcal\{E\},i\+1\)\\supseteq\\textit\{LPV\}\(\\mathcal\{E\},i\);\(i​i\)\(ii\)for every integernnsuch thatn≥\|𝖼𝗅𝒯​\(𝒜\)\|n\\geq\|\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)\|,LPV​\(ℰ,n\)=LPV​\(ℰ,n\+1\)\\textit\{LPV\}\(\\mathcal\{E\},n\)=\\textit\{LPV\}\(\\mathcal\{E\},n\+1\)\.

###### Proof

First, we prove property\(i\)\(i\)\. Base case \(i=0i=0\): SinceLPV​\(ℰ,0\)=∅\\textit\{LPV\}\(\\mathcal\{E\},0\)=\\emptyset, the thesis immediately follows\. Inductive case \(i\>0i\>0\): SupposeLPV​\(ℰ,i\)⊇LPV​\(ℰ,i−1\)\\textit\{LPV\}\(\\mathcal\{E\},i\)\\supseteq\\textit\{LPV\}\(\\mathcal\{E\},i\-1\)and letα∈LPV​\(ℰ,i\)\\alpha\\in\\textit\{LPV\}\(\\mathcal\{E\},i\)\. SinceLPV​\(ℰ,i\)=LPV0​\(ℰ,𝖼𝗅𝒯​\(𝒜\)∖LPV​\(ℰ,i−1\)\)\\textit\{LPV\}\(\\mathcal\{E\},i\)=\\textit\{LPV\}\_\{0\}\(\\mathcal\{E\},\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)\\setminus\\textit\{LPV\}\(\\mathcal\{E\},i\-1\)\), there existτ∈𝒫\\tau\\in\\mathcal\{P\}andσ∈gs​\(τ\)\\sigma\\in\\textit\{gs\}\(\\tau\)such that𝒯∪\{α\}⊧𝖻𝗈𝖽𝗒​\(σ​\(τ\)\)\\mathcal\{T\}\\cup\\\{\\alpha\\\}\\models\\mathsf\{body\}\(\\sigma\(\\tau\)\)and𝒯∪\(𝖼𝗅𝒯​\(𝒜\)∖LPV​\(ℰ,i−1\)\)⊧̸𝗁𝖾𝖺𝖽​\(σ​\(τ\)\)\\mathcal\{T\}\\cup\(\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)\\setminus\\textit\{LPV\}\(\\mathcal\{E\},i\-1\)\)\\not\\models\\mathsf\{head\}\(\\sigma\(\\tau\)\)\. Now, sinceLPV​\(ℰ,i\)⊇LPV​\(ℰ,i−1\)\\textit\{LPV\}\(\\mathcal\{E\},i\)\\supseteq\\textit\{LPV\}\(\\mathcal\{E\},i\-1\), it follows that𝒯∪\(𝖼𝗅𝒯​\(𝒜\)∖LPV​\(ℰ,i\)\)⊧̸𝗁𝖾𝖺𝖽​\(σ​\(τ\)\)\\mathcal\{T\}\\cup\(\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)\\setminus\\textit\{LPV\}\(\\mathcal\{E\},i\)\)\\not\\models\\mathsf\{head\}\(\\sigma\(\\tau\)\), which implies thatα∈LPV​\(ℰ,i\+1\)\\alpha\\in\\textit\{LPV\}\(\\mathcal\{E\},i\+1\)\. Consequently,LPV​\(ℰ,i\+1\)⊇LPV​\(ℰ,i\)\\textit\{LPV\}\(\\mathcal\{E\},i\+1\)\\supseteq\\textit\{LPV\}\(\\mathcal\{E\},i\)\.

As for property\(i​i\)\(ii\): From Definition[5](https://arxiv.org/html/2607.16715#Thmdefinition5)it immediately follows that, ifLPV​\(ℰ,i\)=LPV​\(ℰ,i\+1\)\\textit\{LPV\}\(\\mathcal\{E\},i\)=\\textit\{LPV\}\(\\mathcal\{E\},i\+1\)for someii, thenLPV​\(ℰ,i\)=LPV​\(ℰ,j\)\\textit\{LPV\}\(\\mathcal\{E\},i\)=\\textit\{LPV\}\(\\mathcal\{E\},j\)for every integerjjsuch thatj\>ij\>i\. This property and property\(i\)\(i\)imply that eitherLPV​\(ℰ,\|𝖼𝗅𝒯​\(𝒜\)\|\)=𝖼𝗅𝒯​\(𝒜\)\\textit\{LPV\}\(\\mathcal\{E\},\|\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)\|\)=\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)or there existsi<\|𝖼𝗅𝒯​\(𝒜\)\|i<\|\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)\|such thatLPV​\(ℰ,i\)=LPV​\(ℰ,i\+1\)\\textit\{LPV\}\(\\mathcal\{E\},i\)=\\textit\{LPV\}\(\\mathcal\{E\},i\+1\)\. In both cases, it follows that, for everynnsuch thatn≥\|𝖼𝗅𝒯​\(𝒜\)\|n\\geq\|\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)\|,LPV​\(ℰ,n\)=LPV​\(ℰ,n\+1\)\\textit\{LPV\}\(\\mathcal\{E\},n\)=\\textit\{LPV\}\(\\mathcal\{E\},n\+1\)\. ∎

Now, we defineLPV​\(ℰ\)\\textit\{LPV\}\(\\mathcal\{E\}\)asLPV​\(ℰ,\|𝖼𝗅𝒯​\(𝒜\)\|\)\\textit\{LPV\}\(\\mathcal\{E\},\|\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)\|\)\(i\.e\. as the fixpoint ofLPV​\(ℰ,i\)\\textit\{LPV\}\(\\mathcal\{E\},i\)\)\.

###### Proposition 5

For every CQE instanceℰ=⟨𝒯,𝒫,𝒜⟩\\mathcal\{E\}=\\langle\\mathcal\{T\},\\mathcal\{P\},\\mathcal\{A\}\\rangle, the set𝖼𝗅𝒯​\(𝒜\)∖LPV​\(ℰ\)\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)\\setminus\\textit\{LPV\}\(\\mathcal\{E\}\)coincides with𝒞𝖨𝖦𝖠ℰ\\mathcal\{C\}\_\{\\mathsf\{IGA\}\}^\{\\mathcal\{E\}\}\.

###### Proof

It is easy to see that everyα\\alphaof Definition[5](https://arxiv.org/html/2607.16715#Thmdefinition5)is such that\{α\}\\\{\\alpha\\\}is a⊆\\subseteq\-minimalℰ\\mathcal\{E\}\-undisclosable subset of𝖼𝗅𝒯​\(𝒜\)\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)\. Then, the thesis follows by Proposition[1](https://arxiv.org/html/2607.16715#Thmproposition1)\. ∎

It is immediate to verify thatLPV​\(ℰ\)\\textit\{LPV\}\(\\mathcal\{E\}\)\(and therefore, by the above proposition,𝒞𝖨𝖦𝖠ℰ\\mathcal\{C\}\_\{\\mathsf\{IGA\}\}^\{\\mathcal\{E\}\}\), can be computed in polynomial time w\.r\.t\. the size of𝒜\\mathcal\{A\}\. Then, since standard BUCQ answering overDL\-Liteℛ\\text\{DL\-Lite\}\_\{\\mathcal\{R\}\}ontologies is in PTIME—in fact, inAC0\\mathrm\{AC\}^\{0\}\[[6](https://arxiv.org/html/2607.16715#bib.bib98)\]—, once the set𝒞𝖨𝖦𝖠ℰ\\mathcal\{C\}\_\{\\mathsf\{IGA\}\}^\{\\mathcal\{E\}\}is computed in polynomial time, one can check again in polynomial time whether𝒯∪𝒞𝖨𝖦𝖠ℰ⊧q\\mathcal\{T\}\\cup\\mathcal\{C\}\_\{\\mathsf\{IGA\}\}^\{\\mathcal\{E\}\}\\models q\. Hence, bothGA\-Ent​\[DL\-Liteℛ,𝖯𝖫\]\\textsc\{GA\-Ent\}\[\\text\{DL\-Lite\}\_\{\\mathcal\{R\}\},\\mathsf\{P\_\{L\}\}\]andIGA\-Ent​\[DL\-Liteℛ,𝖯𝖫\]\\textsc\{IGA\-Ent\}\[\\text\{DL\-Lite\}\_\{\\mathcal\{R\}\},\\mathsf\{P\_\{L\}\}\]are in PTIME in data complexity\. We can also provide a suitable query and set of EDs for which the problemIGA\-Entis also hard for PTIME \(even for empty TBoxes\)\. Thus, the following property holds\.

###### Theorem 4\.3

BothGA\-Ent​\[DL\-Liteℛ,𝖯𝖫\]\\textsc\{GA\-Ent\}\[\\text\{DL\-Lite\}\_\{\\mathcal\{R\}\},\\mathsf\{P\_\{L\}\}\]andIGA\-Ent​\[DL\-Liteℛ,𝖯𝖫\]\\textsc\{IGA\-Ent\}\[\\text\{DL\-Lite\}\_\{\\mathcal\{R\}\},\\mathsf\{P\_\{L\}\}\]are PTIME\-complete in data complexity\.

###### Proof

We prove the lower bound by showing a reduction from theHorn\-Satproblem\.

Letϕ\\phibe a set of ground Horn rules, and let us assume w\.l\.o\.g\. thatϕ\\phicontains at least one headless rule \(i\.e\. a clause with only negated variables\)\. Letϕ′\\phi^\{\\prime\}be another set obtained fromϕ\\phiby slightly modifying rules without heads as follows: every headless rulerris replaced by the rule with the same body asrrand with the new variableuuin the head; moreover, for every propositional variableppoccurring inϕ′\\phi^\{\\prime\}\(includinguu\), we add a rulep→pp\\rightarrow ptoϕ′\\phi^\{\\prime\}\. Notice that, by construction,ϕ′\\phi^\{\\prime\}always contains at least two rules withuuin the head\. It is immediate to verify thatϕ\\phiis unsatisfiable iffuubelongs to all the models \(and hence to the minimal model\) ofϕ′\\phi^\{\\prime\}\.

Now, we associate an identifierrixr\_\{i\}^\{x\}to every Horn rule inϕ′\\phi^\{\\prime\}having the variablexxin its head\. Then, leth​\[x\]h\[x\]be the number of rules ofϕ′\\phi^\{\\prime\}having the variablexxin their head, letV​a​r​s​\(ϕ′\)Vars\(\\phi^\{\\prime\}\)be the set of propositional variables occurring inϕ′\\phi^\{\\prime\}and, for every rulerir\_\{i\}, letB​V​a​r​s​\(ri\)BVars\(r\_\{i\}\)be the set of variables in the body ofrir\_\{i\}\. We define the ABox𝒜\\mathcal\{A\}as the set of facts:

⋃ri∈ϕ′\{B​\(ri,x\)∣x∈B​V​a​r​s​\(ri\)\}∪⋃x∈V​a​r​s​\(ϕ′\)⋃1≤i≤h​\[x\]\{H​\(rix,x\),S​\(rix,rjx\)∣j=\(imodh​\[x\]\)\+1\}\\begin\{array\}\[\]\{r@\{\\,\}l\}\\displaystyle\\bigcup\_\{r\_\{i\}\\in\\phi^\{\\prime\}\}&\\\{B\(r\_\{i\},x\)\\mid x\\in BVars\(r\_\{i\}\)\\\}\\\>\\cup\\\\ \\displaystyle\\bigcup\_\{x\\in Vars\(\\phi^\{\\prime\}\)\}\\bigcup\_\{1\\leq i\\leq h\[x\]\}&\\\{H\(r\_\{i\}^\{x\},x\),S\(r\_\{i\}^\{x\},r\_\{j\}^\{x\}\)\\mid j=\(i\\bmod h\[x\]\)\+1\\\}\\end\{array\}Moreover, we set𝒯=∅\\mathcal\{T\}=\\emptyset,q=∃r​H​\(r,u\)q=\\exists r\\,H\(r,u\)and𝒫\\mathcal\{P\}to the following set of linear EDs:

∀r,r′\(K​S​\(r,r′\)→K​∃r′′,v​S​\(r′,r′′\)∧H​\(r,v\)\)∀r,v\(K​H​\(r,v\)→K​∃r′​S​\(r,r′\)\)∀r,v\(K​H​\(r,v\)→K​∃v′​B​\(r,v′\)\)∀r,v\(K​B​\(r,v\)→K​∃r′​H​\(r′,v\)\)\\begin\{array\}\[\]\{r@\{\\,\}l\}\\forall r,r^\{\\prime\}\\\!&\(\\mathrm\{K\}S\(r,r^\{\\prime\}\)\\rightarrow\\mathrm\{K\}\\exists r^\{\\prime\\prime\},v\\,S\(r^\{\\prime\},r^\{\\prime\\prime\}\)\\land H\(r,v\)\)\\\\ \\forall r,v&\(\\mathrm\{K\}H\(r,v\)\\rightarrow\\mathrm\{K\}\\exists r^\{\\prime\}\\,S\(r,r^\{\\prime\}\)\)\\\\ \\forall r,v&\(\\mathrm\{K\}H\(r,v\)\\rightarrow\\mathrm\{K\}\\exists v^\{\\prime\}\\,B\(r,v^\{\\prime\}\)\)\\\\ \\forall r,v&\(\\mathrm\{K\}B\(r,v\)\\rightarrow\\mathrm\{K\}\\exists r^\{\\prime\}\\,H\(r^\{\\prime\},v\)\)\\\\ \\end\{array\}Observe that:

- •The first two EDs imply that the deletion of any fact of the formH​\(r,v\)H\(r,v\)causes the deletion of all the facts of the formH​\(\_,v\)H\(\\\_,v\)and all theSS\-facts related to the EDs havingvvin their head\.
- •The third ED implies that, if all theBB\-facts for the body variables of a rule are deleted, then also theHH\-fact for its head variable must be deleted\.
- •The fourth ED implies that, if all theHH\-facts for a variable are deleted, then also all itsBB\-fact must be deleted\.

The set𝒞𝖨𝖦𝖠ℰ\\mathcal\{C\}\_\{\\mathsf\{IGA\}\}^\{\\mathcal\{E\}\}ofℰ=⟨𝒯,𝒫,𝒜⟩\\mathcal\{E\}=\\langle\\mathcal\{T\},\\mathcal\{P\},\\mathcal\{A\}\\ranglecan be obtained starting from𝖼𝗅𝒯​\(𝒜\)\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)\(i\.e\. from𝒜\\mathcal\{A\}, because𝒯=∅\\mathcal\{T\}=\\emptyset\) and deterministically removing some facts according to the EDs of𝒫\\mathcal\{P\}\. We now prove that, for every variablex∈V​a​r​s​\(ϕ′\)x\\in Vars\(\\phi^\{\\prime\}\), no fact of the formH​\(\_,x\)H\(\\\_,x\)belongs to𝒞𝖨𝖦𝖠ℰ\\mathcal\{C\}\_\{\\mathsf\{IGA\}\}^\{\\mathcal\{E\}\}\(i\.e\.ℰ⊧̸𝖨𝖦𝖠q\\mathcal\{E\}\\not\\models\_\{\\mathsf\{IGA\}\}q, which for linear EDs holds iffℰ⊧̸𝖦𝖠q\\mathcal\{E\}\\not\\models\_\{\\mathsf\{GA\}\}q\) iffx∈Ix\\in I, whereIIis the minimal model ofϕ′\\phi^\{\\prime\}\.

\(⇐\)\(\\Leftarrow\)Letx∈Ix\\in I\. Note that this is possible only ifxxoccurs in the head of a ruler∈ϕ′r\\in\\phi^\{\\prime\}that either does not have a body \(*unit clause*\) or whose body variables all belong toII\.

- •In the first case, due to the first three EDs,𝒞𝖨𝖦𝖠ℰ\\mathcal\{C\}\_\{\\mathsf\{IGA\}\}^\{\\mathcal\{E\}\}does not contain any atom of the formH​\(\_,x\)H\(\\\_,x\)\.
- •The second case occurs instead when all variablesb1,…,bm∈B​V​a​r​s​\(r\)b\_\{1\},\\ldots,b\_\{m\}\\in BVars\(r\)either occur in unit clauses themselves or, in turn, occur as head variables in rules whose body variables belong toII\. By recursively applying the previous and the current point, respectively, one can see that all factsB​\(r,b1\),…,B​\(r,bm\)B\(r,b\_\{1\}\),\\ldots,B\(r,b\_\{m\}\)are removed from𝒞𝖨𝖦𝖠ℰ\\mathcal\{C\}\_\{\\mathsf\{IGA\}\}^\{\\mathcal\{E\}\}because of the fourth ED \(possibly combined with the first two\)\. As a result, by the first three EDs and sincexxoccurs in the head ofrr, it follows that no fact of the formH​\(\_,x\)H\(\\\_,x\)belongs to𝒞𝖨𝖦𝖠ℰ\\mathcal\{C\}\_\{\\mathsf\{IGA\}\}^\{\\mathcal\{E\}\}either\.

\(⇒\)\(\\Rightarrow\)Letxxbe such that no fact of the formH​\(\_,x\)H\(\\\_,x\)belongs to𝒞𝖨𝖦𝖠ℰ\\mathcal\{C\}\_\{\\mathsf\{IGA\}\}^\{\\mathcal\{E\}\}\. Note that, since every variable occurs in the head of some rule \(by the assumption that a rulep→pp\\rightarrow poccurs inϕ′\\phi^\{\\prime\}for everyp∈V​a​r​s​\(ϕ′\)p\\in Vars\(\\phi^\{\\prime\}\)\), then there exists a factH​\(\_,x\)∈𝒜H\(\\\_,x\)\\in\\mathcal\{A\}\. The absence of suchHH\-facts from𝒞𝖨𝖦𝖠ℰ\\mathcal\{C\}\_\{\\mathsf\{IGA\}\}^\{\\mathcal\{E\}\}can only be due to a violation of the third ED \(possibly combined with the first two\), i\.e\. all theB​\(r,\_\)B\(r,\\\_\)facts \(for some ruler=b1,…,bm→x∈ϕ′r=b\_\{1\},\\ldots,b\_\{m\}\\rightarrow x\\in\\phi^\{\\prime\}\) are missing from𝒞𝖨𝖦𝖠ℰ\\mathcal\{C\}\_\{\\mathsf\{IGA\}\}^\{\\mathcal\{E\}\}\.

Then, we either have thatrris a unit clause ofϕ′\\phi^\{\\prime\}\(which would imply thatx∈Ix\\in I\) or that every factB​\(r,bi\)B\(r,b\_\{i\}\)\(for1≤i≤m1\\leq i\\leq m\) occurring in𝒜\\mathcal\{A\}has been removed for building𝒞𝖨𝖦𝖠ℰ\\mathcal\{C\}\_\{\\mathsf\{IGA\}\}^\{\\mathcal\{E\}\}\. These last removals can only be due to a violation of the fourth ED \(possibly combined with the first two\), i\.e\. all factsH​\(\_,bi\)H\(\\\_,b\_\{i\}\)\(for every1≤i≤m1\\leq i\\leq m\) are missing from𝒞𝖨𝖦𝖠ℰ\\mathcal\{C\}\_\{\\mathsf\{IGA\}\}^\{\\mathcal\{E\}\}\. By recursively applying this point, we conclude that allbib\_\{i\}variables belong toII\(implying that alsox∈Ix\\in I\)\.

By instantiating the above property withx=ux=u, we have thatu∈Iu\\in I\(i\.e\.ϕ\\phiis unsatisfiable\) iffℰ⊧𝖨𝖦𝖠q\\mathcal\{E\}\\models\_\{\\mathsf\{IGA\}\}q\. ∎

## 5The MPV Censor

Towards the goal of identifying a well\-founded, sound approximation of the GA semantics that satisfies indistinguishability in the case of arbitrary EDs, we propose a method to compute a GA censor ofℰ\\mathcal\{E\}inspired by the clear, intuitive approach used to build the IGA censor for linear EDs\. Such a censor is built starting from𝖼𝗅𝒯​\(𝒜\)\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)and iteratively removing all⊆\\subseteq\-minimal subsets of facts that cause the violation of some EDτ∈𝒫\\tau\\in\\mathcal\{P\}\. Such a notion of violation extends the one of LPV \(Definition[5](https://arxiv.org/html/2607.16715#Thmdefinition5)\) by addressing an important issue: as long as multiple atoms may appear in the body, it is necessary to perform a minimality check on its images\. To account for this problem, we define the notion of minimal policy violation\.

###### Definition 6\(MPV\)

Given a CQE instanceℰ=⟨𝒯,𝒫,𝒜⟩\\mathcal\{E\}=\\langle\\mathcal\{T\},\\mathcal\{P\},\\mathcal\{A\}\\rangleand a subset𝒜′\\mathcal\{A\}^\{\\prime\}of𝖼𝗅𝒯​\(𝒜\)\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\), a*minimal policy violation \(MPV\)*ofℰ\\mathcal\{E\}w\.r\.t\.𝒜′\\mathcal\{A\}^\{\\prime\}is a⊆\\subseteq\-minimal subset𝒜′′\\mathcal\{A\}^\{\\prime\\prime\}of𝖼𝗅𝒯​\(𝒜\)\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)such that there existτ∈𝒫\\tau\\in\\mathcal\{P\}andσ∈gs​\(τ\)\\sigma\\in\\textit\{gs\}\(\\tau\)such that𝒯∪𝒜′′⊧𝖻𝗈𝖽𝗒​\(σ​\(τ\)\)\\mathcal\{T\}\\cup\\mathcal\{A\}^\{\\prime\\prime\}\\models\\mathsf\{body\}\(\\sigma\(\\tau\)\)and𝒯∪𝒜′⊧̸𝗁𝖾𝖺𝖽​\(σ​\(τ\)\)\\mathcal\{T\}\\cup\\mathcal\{A\}^\{\\prime\}\\not\\models\\mathsf\{head\}\(\\sigma\(\\tau\)\)\.

We denote byMPV0​\(ℰ,𝒜′\)\\textit\{MPV\}\_\{0\}\(\\mathcal\{E\},\\mathcal\{A\}^\{\\prime\}\)the set constituted by the union of all the MPVs ofℰ\\mathcal\{E\}w\.r\.t\.𝒜′\\mathcal\{A\}^\{\\prime\}\. Then, we defineMPV​\(ℰ,0\)=∅\\textit\{MPV\}\(\\mathcal\{E\},0\)=\\emptyset, and, for every non\-negative integerii:

MPV​\(ℰ,i\+1\)=MPV0​\(ℰ,𝖼𝗅𝒯​\(𝒜\)∖MPV​\(ℰ,i\)\)\.\\textit\{MPV\}\(\\mathcal\{E\},i\+1\)=\\textit\{MPV\}\_\{0\}\(\\mathcal\{E\},\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)\\setminus\\textit\{MPV\}\(\\mathcal\{E\},i\)\)\.

The next proposition states a key property ofMPV​\(ℰ,i\)\\textit\{MPV\}\(\\mathcal\{E\},i\)\.

###### Proposition 6

For every CQE instanceℰ=⟨𝒯,𝒫,𝒜⟩\\mathcal\{E\}=\\langle\\mathcal\{T\},\\mathcal\{P\},\\mathcal\{A\}\\rangleand for every integernnsuch thatn≥\|𝖼𝗅𝒯​\(𝒜\)\|n\\geq\|\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)\|,MPV​\(ℰ,n\)=MPV​\(ℰ,n\+1\)\\textit\{MPV\}\(\\mathcal\{E\},n\)=\\textit\{MPV\}\(\\mathcal\{E\},n\+1\)\.

###### Proof

From Definition[6](https://arxiv.org/html/2607.16715#Thmdefinition6), and in a way analogous to the proof of Proposition[4](https://arxiv.org/html/2607.16715#Thmproposition4), we get the following properties:

1. \(i\)\(i\)for everyiisuch that1≤i≤n1\\leq i\\leq n,MPV​\(ℰ,i\+1\)⊇MPV​\(ℰ,i\)\\textit\{MPV\}\(\\mathcal\{E\},i\+1\)\\supseteq\\textit\{MPV\}\(\\mathcal\{E\},i\);
2. \(i​i\)\(ii\)ifMPV​\(ℰ,i\+1\)=MPV​\(ℰ,i\)\\textit\{MPV\}\(\\mathcal\{E\},i\+1\)=\\textit\{MPV\}\(\\mathcal\{E\},i\), thenMPV​\(ℰ,j\)=MPV​\(ℰ,i\)\\textit\{MPV\}\(\\mathcal\{E\},j\)=\\textit\{MPV\}\(\\mathcal\{E\},i\)for everyj\>ij\>i\.

Now, two cases are possible:

1. 1\.there exists an integeriisuch that0≤i≤\|𝖼𝗅𝒯​\(𝒜\)−1\|0\\leq i\\leq\|\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)\-1\|andMPV​\(ℰ,i\+1\)=MPV​\(ℰ,i\)\\textit\{MPV\}\(\\mathcal\{E\},i\+1\)=\\textit\{MPV\}\(\\mathcal\{E\},i\)\. In this case, from the above property\(i​i\)\(ii\)it follows thatMPV​\(ℰ,n\)=MPV​\(ℰ,n\+1\)\\textit\{MPV\}\(\\mathcal\{E\},n\)=\\textit\{MPV\}\(\\mathcal\{E\},n\+1\)for every integernnsuch thatn≥\|𝖼𝗅𝒯​\(𝒜\)\|n\\geq\|\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)\|;
2. 2\.ifMPV​\(ℰ,i\+1\)⊃MPV​\(ℰ,i\)\\textit\{MPV\}\(\\mathcal\{E\},i\+1\)\\supset\\textit\{MPV\}\(\\mathcal\{E\},i\)for every integeriisuch that0≤i≤\|𝖼𝗅𝒯​\(𝒜\)−1\|0\\leq i\\leq\|\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)\-1\|\(i\.e\. everyMPV​\(ℰ,i\+1\)\\textit\{MPV\}\(\\mathcal\{E\},i\+1\)has at least one more atom thanMPV​\(ℰ,i\)\\textit\{MPV\}\(\\mathcal\{E\},i\)\), then\|MPV​\(ℰ,\|𝖼𝗅𝒯​\(𝒜\)\|\)\|≥\|𝖼𝗅𝒯​\(𝒜\)\|\|\\textit\{MPV\}\(\\mathcal\{E\},\|\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)\|\)\|\\geq\|\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)\|, and sinceMPV​\(ℰ,i\)\\textit\{MPV\}\(\\mathcal\{E\},i\)is by definition a subset of𝖼𝗅𝒯​\(𝒜\)\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\), it follows thatMPV​\(ℰ,\|𝖼𝗅𝒯​\(𝒜\)\|\)=𝖼𝗅𝒯​\(𝒜\)\\textit\{MPV\}\(\\mathcal\{E\},\|\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)\|\)=\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)\. For the same reason, it follows that MPV​\(ℰ,\|𝖼𝗅𝒯​\(𝒜\)\|\+1\)⊆𝖼𝗅𝒯​\(𝒜\)⊆MPV​\(ℰ,\|𝖼𝗅𝒯​\(𝒜\)\|\)\.\\textit\{MPV\}\(\\mathcal\{E\},\|\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)\|\+1\)\\subseteq\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)\\subseteq\\textit\{MPV\}\(\\mathcal\{E\},\|\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)\|\)\.On the other hand, by the above property\(i\)\(i\)it follows that MPV\(ℰ,\|𝖼𝗅𝒯\(𝒜\)\|\+1\)⊇MPV\(ℰ,\|𝖼𝗅𝒯\(𝒜\)\)\|\.\\textit\{MPV\}\(\\mathcal\{E\},\|\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)\|\+1\)\\supseteq\\textit\{MPV\}\(\\mathcal\{E\},\|\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)\)\|\.Consequently,MPV​\(ℰ,\|𝖼𝗅𝒯​\(𝒜\)\|\+1\)=MPV​\(ℰ,\|𝖼𝗅𝒯​\(𝒜\)\|\)\\textit\{MPV\}\(\\mathcal\{E\},\|\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)\|\+1\)=\\textit\{MPV\}\(\\mathcal\{E\},\|\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)\|\)\. Finally, from the above property\(i​i\)\(ii\)it follows thatMPV​\(ℰ,j\)=MPV​\(ℰ,\|𝖼𝗅𝒯​\(𝒜\)\|\)\\textit\{MPV\}\(\\mathcal\{E\},j\)=\\textit\{MPV\}\(\\mathcal\{E\},\|\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)\|\)for every integerjjsuch thatj≥\|𝖼𝗅𝒯​\(𝒜\)\|j\\geq\|\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)\|\.

∎

Then,MPV​\(ℰ\)\\textit\{MPV\}\(\\mathcal\{E\}\)denotes the setMPV​\(ℰ,\|𝖼𝗅𝒯​\(𝒜\)\|\)\\textit\{MPV\}\(\\mathcal\{E\},\|\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)\|\), i\.e\. it is the fixpoint ofMPV​\(ℰ,k\)\\textit\{MPV\}\(\\mathcal\{E\},k\)\. We now analyze how such a set relates to the notion of GA censor\.

###### Proposition 7

For every CQE instanceℰ=⟨𝒯,𝒫,𝒜⟩\\mathcal\{E\}=\\langle\\mathcal\{T\},\\mathcal\{P\},\\mathcal\{A\}\\rangle:

- \(i\)\(i\)for every set of ground atoms𝒜′\\mathcal\{A\}^\{\\prime\}, if𝒜′⊇MPV0​\(ℰ,𝖼𝗅𝒯​\(𝒜\)∖𝒜′\)\\mathcal\{A\}^\{\\prime\}\\supseteq\\textit\{MPV\}\_\{0\}\(\\mathcal\{E\},\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)\\setminus\\mathcal\{A\}^\{\\prime\}\), then𝖼𝗅𝒯​\(𝒜\)∖𝒜′\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)\\setminus\\mathcal\{A\}^\{\\prime\}is a GA censor ofℰ\\mathcal\{E\};
- \(i​i\)\(ii\)the set𝖼𝗅𝒯​\(𝒜\)∖MPV​\(ℰ\)\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)\\setminus\\textit\{MPV\}\(\\mathcal\{E\}\)is a GA censor ofℰ\\mathcal\{E\};
- \(i​i​i\)\(iii\)MPV​\(ℰ\)\\textit\{MPV\}\(\\mathcal\{E\}\)is the smallest set𝒜′⊆𝖼𝗅𝒯​\(𝒜\)\\mathcal\{A\}^\{\\prime\}\\subseteq\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)such that𝒜′⊇MPV0​\(ℰ,𝖼𝗅𝒯​\(𝒜\)∖𝒜′\)\\mathcal\{A\}^\{\\prime\}\\supseteq\\textit\{MPV\}\_\{0\}\(\\mathcal\{E\},\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)\\setminus\\mathcal\{A\}^\{\\prime\}\)\.

###### Proof

Let𝒞\\mathcal\{C\}denote the set𝖼𝗅𝒯​\(𝒜\)∖𝒜′\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)\\setminus\\mathcal\{A\}^\{\\prime\}\. Obviously,𝒞∩𝒜′=∅\\mathcal\{C\}\\cap\\mathcal\{A\}^\{\\prime\}=\\emptyset\. By contradiction, let𝒯∪𝒞⊧̸𝖤𝖰𝖫𝒫\\mathcal\{T\}\\cup\\mathcal\{C\}\\not\\models\_\{\\mathsf\{EQL\}\}\\mathcal\{P\}\. Now, let𝒜′′\\mathcal\{A\}^\{\\prime\\prime\}be the⊆\\subseteq\-minimal subset of𝒞\\mathcal\{C\}such that, for someτ∈𝒫\\tau\\in\\mathcal\{P\}andσ∈gs​\(τ\)\\sigma\\in\\textit\{gs\}\(\\tau\),𝒯∪𝒜′′⊧𝖻𝗈𝖽𝗒​\(σ​\(τ\)\)\\mathcal\{T\}\\cup\\mathcal\{A\}^\{\\prime\\prime\}\\models\\mathsf\{body\}\(\\sigma\(\\tau\)\)and𝒯∪𝒞⊧̸𝗁𝖾𝖺𝖽​\(σ​\(τ\)\)\\mathcal\{T\}\\cup\\mathcal\{C\}\\not\\models\\mathsf\{head\}\(\\sigma\(\\tau\)\)\(notice that such𝒜′′\\mathcal\{A\}^\{\\prime\\prime\}exists because𝒯∪𝒞⊧̸𝖤𝖰𝖫𝒫\\mathcal\{T\}\\cup\\mathcal\{C\}\\not\\models\_\{\\mathsf\{EQL\}\}\\mathcal\{P\}\)\. Since𝒞⊆𝖼𝗅𝒯​\(𝒜\)\\mathcal\{C\}\\subseteq\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)\(by construction\), then𝒜′′\\mathcal\{A\}^\{\\prime\\prime\}is also a⊆\\subseteq\-minimal subset of𝖼𝗅𝒯​\(𝒜\)\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)such that, for someτ∈𝒫\\tau\\in\\mathcal\{P\}andσ∈gs​\(τ\)\\sigma\\in\\textit\{gs\}\(\\tau\),𝒯∪𝒜′′⊧𝖻𝗈𝖽𝗒​\(σ​\(τ\)\)\\mathcal\{T\}\\cup\\mathcal\{A\}^\{\\prime\\prime\}\\models\\mathsf\{body\}\(\\sigma\(\\tau\)\)and𝒯∪𝒞⊧̸𝗁𝖾𝖺𝖽​\(σ​\(τ\)\)\\mathcal\{T\}\\cup\\mathcal\{C\}\\not\\models\\mathsf\{head\}\(\\sigma\(\\tau\)\), i\.e\.𝒜′′⊆MPV0​\(ℰ,𝒞\)\\mathcal\{A\}^\{\\prime\\prime\}\\subseteq\\textit\{MPV\}\_\{0\}\(\\mathcal\{E\},\\mathcal\{C\}\)\. However, sinceMPV0​\(ℰ,𝒞\)⊆𝒜′\\textit\{MPV\}\_\{0\}\(\\mathcal\{E\},\\mathcal\{C\}\)\\subseteq\\mathcal\{A\}^\{\\prime\}\(by hypothesis\), this contradicts the fact that𝒞∩𝒜′=∅\\mathcal\{C\}\\cap\\mathcal\{A\}^\{\\prime\}=\\emptyset, thus proving property\(i\)\(i\)\.

Then, by definition ofMPV​\(ℰ\)\\textit\{MPV\}\(\\mathcal\{E\}\), we haveMPV​\(ℰ\)=MPV0​\(ℰ,𝖼𝗅𝒯​\(𝒜\)∖MPV​\(ℰ\)\)\\textit\{MPV\}\(\\mathcal\{E\}\)=\\textit\{MPV\}\_\{0\}\(\\mathcal\{E\},\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)\\setminus\\textit\{MPV\}\(\\mathcal\{E\}\)\), hence by property\(i\)\(i\)we get property\(i​i\)\(ii\)\.

Finally, let𝒜′\\mathcal\{A\}^\{\\prime\}be any set of facts such that𝒜′⊇MPV0​\(ℰ,𝖼𝗅𝒯​\(𝒜\)∖𝒜′\)\\mathcal\{A\}^\{\\prime\}\\supseteq\\textit\{MPV\}\_\{0\}\(\\mathcal\{E\},\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)\\setminus\\mathcal\{A\}^\{\\prime\}\)\. We prove by induction that, for everyiisuch that1≤i≤\|𝖼𝗅𝒯​\(𝒜\)\|1\\leq i\\leq\|\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)\|,𝒜′⊃MPV​\(ℰ,i\)\\mathcal\{A\}^\{\\prime\}\\supset\\textit\{MPV\}\(\\mathcal\{E\},i\)\.

- •Base case \(i=0i=0\): trivially,𝒜′⊇∅=MPV​\(ℰ,0\)\\mathcal\{A\}^\{\\prime\}\\supseteq\\emptyset=\\textit\{MPV\}\(\\mathcal\{E\},0\)\.
- •Inductive case: suppose𝒜′⊇MPV​\(ℰ,i\)\\mathcal\{A\}^\{\\prime\}\\supseteq\\textit\{MPV\}\(\\mathcal\{E\},i\)\. Notice that, for every pair of setsS,S′S,S^\{\\prime\}, the setMPV0​\(ℰ,S\)\\textit\{MPV\}\_\{0\}\(\\mathcal\{E\},S\)monotonically decreases whenSSincreases, meaning thatMPV0​\(ℰ,S\)⊇MPV0​\(ℰ,S′\)\\textit\{MPV\}\_\{0\}\(\\mathcal\{E\},S\)\\supseteq\\textit\{MPV\}\_\{0\}\(\\mathcal\{E\},S^\{\\prime\}\)wheneverS⊆S′S\\subseteq S^\{\\prime\}\. This holds because, by Definition[6](https://arxiv.org/html/2607.16715#Thmdefinition6), the MPVs are searched in both cases among all possible subsets of𝖼𝗅𝒯​\(𝒜\)\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\), but the non\-entailment check is done onSSandS′S^\{\\prime\}, respectively\. Therefore,MPV0​\(ℰ,𝖼𝗅𝒯​\(𝒜\)∖𝒜′\)⊇MPV0​\(ℰ,𝖼𝗅𝒯​\(𝒜\)∖MPV​\(ℰ,i\)\)\\textit\{MPV\}\_\{0\}\(\\mathcal\{E\},\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)\\setminus\\mathcal\{A\}^\{\\prime\}\)\\supseteq\\textit\{MPV\}\_\{0\}\(\\mathcal\{E\},\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)\\setminus\\textit\{MPV\}\(\\mathcal\{E\},i\)\), and sinceMPV​\(ℰ,i\+1\)=MPV0​\(ℰ,𝖼𝗅𝒯​\(𝒜\)∖MPV​\(ℰ,i\)\)\\textit\{MPV\}\(\\mathcal\{E\},i\+1\)=\\textit\{MPV\}\_\{0\}\(\\mathcal\{E\},\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)\\setminus\\textit\{MPV\}\(\\mathcal\{E\},i\)\), it follows that𝒜′⊇MPV​\(ℰ,i\+1\)\\mathcal\{A\}^\{\\prime\}\\supseteq\\textit\{MPV\}\(\\mathcal\{E\},i\+1\)\.

SinceMPV​\(ℰ\)=MPV​\(ℰ,\|𝖼𝗅𝒯​\(𝒜\)\|\)\\textit\{MPV\}\(\\mathcal\{E\}\)=\\textit\{MPV\}\(\\mathcal\{E\},\|\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)\|\), it follows that𝒜′⊇MPV​\(ℰ\)\\mathcal\{A\}^\{\\prime\}\\supseteq\\textit\{MPV\}\(\\mathcal\{E\}\), thus proving property\(i​i​i\)\(iii\)\. ∎

The above property leads naturally to the definition of a new notion of censor\.

###### Definition 7\(MPV Censor\)

Given a CQE instanceℰ=⟨𝒯,𝒫,𝒜⟩\\mathcal\{E\}=\\langle\\mathcal\{T\},\\mathcal\{P\},\\mathcal\{A\}\\rangle, we define the*MPV censor ofℰ\\mathcal\{E\}*, denoted by𝒞𝖬𝖯𝖵ℰ\\mathcal\{C\}\_\{\\mathsf\{MPV\}\}^\{\\mathcal\{E\}\}, as the set𝖼𝗅𝒯​\(𝒜\)∖MPV​\(ℰ\)\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)\\setminus\\textit\{MPV\}\(\\mathcal\{E\}\)\.

By Proposition[6](https://arxiv.org/html/2607.16715#Thmproposition6), for every CQE instanceℰ\\mathcal\{E\}, the MPV censor ofℰ\\mathcal\{E\}always exists and is unique\.

###### Example 2

Consider the sets𝒯\\mathcal\{T\},𝒫\\mathcal\{P\}, and𝒜\\mathcal\{A\}of Example[1](https://arxiv.org/html/2607.16715#Thmexample1), and letℰ=⟨𝒯,𝒫,𝒜⟩\\mathcal\{E\}=\\langle\\mathcal\{T\},\\mathcal\{P\},\\mathcal\{A\}\\rangle\. Note that\{𝗉𝖢𝗈𝗇𝗌𝖥𝗈𝗋​\(𝖻𝗈𝖻,𝖺𝗇𝗇\)\}\\\{\\mathsf\{pConsFor\}\(\\mathsf\{bob\},\\mathsf\{ann\}\)\\\},\{𝗉𝖺𝗋𝖮𝖿​\(𝖻𝗈𝖻,𝖺𝗇𝗇\)\}\\\{\\mathsf\{parOf\}\(\\mathsf\{bob\},\\mathsf\{ann\}\)\\\}, and\{𝖬​\(𝖺𝗇𝗇\),𝖺𝖿𝖿𝖡𝗒​\(𝖺𝗇𝗇,𝖽\)\}\\\{\\mathsf\{M\}\(\\mathsf\{ann\}\),\\allowbreak\\mathsf\{affBy\}\(\\mathsf\{ann\},\\mathsf\{d\}\)\\\}are all MPVs ofℰ\\mathcal\{E\}w\.r\.t\.𝖼𝗅𝒯​\(𝒜\)\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\), and that the fixpoint ofMPV​\(ℰ,i\)\\textit\{MPV\}\(\\mathcal\{E\},i\)is already reached fori=1i=1\. Then,𝒞𝖬𝖯𝖵ℰ=𝖼𝗅𝒯​\(𝒜\)∖MPV​\(ℰ,1\)=\{𝖣𝗂𝗌​\(𝖽\)\}\\mathcal\{C\}\_\{\\mathsf\{MPV\}\}^\{\\mathcal\{E\}\}=\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)\\setminus\\textit\{MPV\}\(\\mathcal\{E\},1\)=\\\{\\mathsf\{Dis\}\(\\mathsf\{d\}\)\\\}, which is contained in the \(unique\) optimal GA censor mentioned in Example[1](https://arxiv.org/html/2607.16715#Thmexample1)\.

###### Example 3

Consider again the CQE instance of Example[1](https://arxiv.org/html/2607.16715#Thmexample1)and let𝒜\\mathcal\{A\}also contain the facts𝗍𝗋𝖡𝗒​\(𝖺𝗇𝗇,𝖼𝗅𝗈𝖾\)\\mathsf\{trBy\}\(\\mathsf\{ann\},\\mathsf\{cloe\}\)and𝖯​\(𝖼𝗅𝗈𝖾\)\\mathsf\{P\}\(\\mathsf\{cloe\}\), modelling the fact that𝖺𝗇𝗇\\mathsf\{ann\}is treated by \(𝗍𝗋𝖡𝗒\\mathsf\{trBy\}\)𝖼𝗅𝗈𝖾\\mathsf\{cloe\}, who is a pediatrician \(𝖯\\mathsf\{P\}\)\. Moreover, let𝒫\\mathcal\{P\}also contain the additional EDτ=∀x,y​\(K​\(𝗍𝗋𝖡𝗒​\(x,y\)∧𝖯​\(y\)\)→K​𝖬​\(x\)\)\\tau=\\forall x,y\\,\(\\mathrm\{K\}\(\\mathsf\{trBy\}\(x,y\)\\land\\mathsf\{P\}\(y\)\)\\rightarrow\\mathrm\{K\}\\mathsf\{M\}\(x\)\), which allows to reveal that an individualxxis treated by a pediatrician only if it can also be revealed thatxxis a minor\. In this case, the fixpoint ofMPV​\(ℰ,i\)\\textit\{MPV\}\(\\mathcal\{E\},i\)is reached fori=2i=2\. Specifically,MPV​\(ℰ,1\)\\textit\{MPV\}\(\\mathcal\{E\},1\)is as before, whileMPV​\(ℰ,2\)=MPV​\(ℰ,1\)∪\{𝗍𝗋𝖡𝗒​\(𝖺𝗇𝗇,𝖼𝗅𝗈𝖾\),𝖯​\(𝖼𝗅𝗈𝖾\)\}\\textit\{MPV\}\(\\mathcal\{E\},2\)=\\textit\{MPV\}\(\\mathcal\{E\},1\)\\cup\\\{\\mathsf\{trBy\}\(\\mathsf\{ann\},\\mathsf\{cloe\}\),\\allowbreak\\mathsf\{P\}\(\\mathsf\{cloe\}\)\\\}\. Thus,𝒞𝖬𝖯𝖵ℰ=\{𝖣𝗂𝗌​\(𝖽\)\}\\mathcal\{C\}\_\{\\mathsf\{MPV\}\}^\{\\mathcal\{E\}\}=\\\{\\mathsf\{Dis\}\(\\mathsf\{d\}\)\\\}\.

We now analyze the relation between the MPV censor and the IGA censor\. We start by showing the next property, whose proof is based on the following intuition: if there exists any overlap between a⊆\\subseteq\-minimalℰ\\mathcal\{E\}undisclosable set and a set𝒞\\mathcal\{C\}obtained by iteratively removing MPVs, then𝒞\\mathcal\{C\}has not reached the fixpoint yet \(i\.e\.𝒞≠𝒞𝖬𝖯𝖵ℰ\\mathcal\{C\}\\neq\\mathcal\{C\}\_\{\\mathsf\{MPV\}\}^\{\\mathcal\{E\}\}\)\.

###### Theorem 5\.1

Letℰ\\mathcal\{E\}be a CQE instance\. Then,𝒞𝖬𝖯𝖵ℰ⊆𝒞𝖨𝖦𝖠ℰ\\mathcal\{C\}\_\{\\mathsf\{MPV\}\}^\{\\mathcal\{E\}\}\\subseteq\\mathcal\{C\}\_\{\\mathsf\{IGA\}\}^\{\\mathcal\{E\}\}\.

###### Proof

In what follows, let𝑀𝑈𝑆​\(ℰ\)\\mathit\{MUS\}\(\\mathcal\{E\}\)be the set of all⊆\\subseteq\-minimalℰ\\mathcal\{E\}\-undisclosable subsets of𝖼𝗅𝒯​\(𝒜\)\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)\.

Claim 1\.*Let𝒞\\mathcal\{C\}be a GA censor ofℰ\\mathcal\{E\}such that there exists aS∈𝑀𝑈𝑆​\(ℰ\)S\\in\\mathit\{MUS\}\(\\mathcal\{E\}\)for which𝒞∩S≠∅\\mathcal\{C\}\\cap S\\neq\\emptyset\. Then, there existα∈𝒞\\alpha\\in\\mathcal\{C\},τ∈𝒫\\tau\\in\\mathcal\{P\},σ∈gs​\(τ\)\\sigma\\in\\textit\{gs\}\(\\tau\), andI∈Im​\(𝖻𝗈𝖽𝗒​\(σ​\(τ\)\),𝖼𝗅𝒯​\(𝒜\),𝒯\)I\\in\\textit\{Im\}\(\\mathsf\{body\}\(\\sigma\(\\tau\)\),\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\),\\mathcal\{T\}\)such thatα∈I\\alpha\\in Iand𝒯∪𝒞⊧̸𝗁𝖾𝖺𝖽​\(σ​\(τ\)\)\\mathcal\{T\}\\cup\\mathcal\{C\}\\not\\models\\mathsf\{head\}\(\\sigma\(\\tau\)\)\.*

We now prove the above claim\. LetSS\\SSbe the set of all sets in𝑀𝑈𝑆​\(ℰ\)\\mathit\{MUS\}\(\\mathcal\{E\}\)intersecting𝒞\\mathcal\{C\}\(which, by hypothesis, is non\-empty\)\. Note that no set inSS\\SSis a singleton \(otherwise it would be contained in𝒞\\mathcal\{C\}, hence contradicting the fact that𝒞\\mathcal\{C\}is a GA censor ofℰ\\mathcal\{E\}\)\.

Let nowS1∈𝑀𝑈𝑆​\(ℰ\)S\_\{1\}\\in\\mathit\{MUS\}\(\\mathcal\{E\}\)andα1∈S1∩𝒞\\alpha\_\{1\}\\in S\_\{1\}\\cap\\mathcal\{C\}, and suppose first that\(S1∪𝒞\)∖\{α1\}\(S\_\{1\}\\cup\\mathcal\{C\}\)\\setminus\\\{\\alpha\_\{1\}\\\}isℰ\\mathcal\{E\}\-disclosable, i\.e\. it is contained in some GA censor𝒞1\\mathcal\{C\}\_\{1\}ofℰ\\mathcal\{E\}\. SinceS1⊆𝒞1∪\{α1\}S\_\{1\}\\subseteq\\mathcal\{C\}\_\{1\}\\cup\\\{\\alpha\_\{1\}\\\}, then𝒞1∪\{α1\}\\mathcal\{C\}\_\{1\}\\cup\\\{\\alpha\_\{1\}\\\}is not a GA censor ofℰ\\mathcal\{E\}, i\.e\.𝒞1∪\{α1\}⊧̸𝖤𝖰𝖫𝒫\\mathcal\{C\}\_\{1\}\\cup\\\{\\alpha\_\{1\}\\\}\\not\\models\_\{\\mathsf\{EQL\}\}\\mathcal\{P\}\. Then, for someτ∈𝒫\\tau\\in\\mathcal\{P\}andσ∈gs​\(τ\)\\sigma\\in\\textit\{gs\}\(\\tau\),𝒯∪𝒞1∪\{α1\}⊧𝖻𝗈𝖽𝗒​\(σ​\(τ\)\)\\mathcal\{T\}\\cup\\mathcal\{C\}\_\{1\}\\cup\\\{\\alpha\_\{1\}\\\}\\models\\mathsf\{body\}\(\\sigma\(\\tau\)\)and𝒯∪𝒞1∪\{α1\}⊧̸𝗁𝖾𝖺𝖽​\(σ​\(τ\)\)\\mathcal\{T\}\\cup\\mathcal\{C\}\_\{1\}\\cup\\\{\\alpha\_\{1\}\\\}\\not\\models\\mathsf\{head\}\(\\sigma\(\\tau\)\)\. Now, letIIby any⊆\\subseteq\-minimal subset of𝒞1∪\{α1\}\\mathcal\{C\}\_\{1\}\\cup\\\{\\alpha\_\{1\}\\\}such that𝒯∪ℐ⊧𝖻𝗈𝖽𝗒​\(σ​\(τ\)\)\\mathcal\{T\}\\cup\\mathcal\{I\}\\models\\mathsf\{body\}\(\\sigma\(\\tau\)\)\. Note thatIIcannot be included in𝒞1\\mathcal\{C\}\_\{1\}\(as it would contradict the fact that𝒯∪𝒞1⊧𝖤𝖰𝖫τ\\mathcal\{T\}\\cup\\mathcal\{C\}\_\{1\}\\models\_\{\\mathsf\{EQL\}\}\\tau\), which implies thatα1∈I\\alpha\_\{1\}\\in I\. Furthermore, by monotonicity,I∈Im​\(𝖻𝗈𝖽𝗒​\(σ​\(τ\)\),𝖼𝗅𝒯​\(𝒜\),𝒯\)I\\in\\textit\{Im\}\(\\mathsf\{body\}\(\\sigma\(\\tau\)\),\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\),\\mathcal\{T\}\)and𝒯∪𝒞⊧̸𝗁𝖾𝖺𝖽​\(σ​\(τ\)\)\\mathcal\{T\}\\cup\\mathcal\{C\}\\not\\models\\mathsf\{head\}\(\\sigma\(\\tau\)\)\. Thus, in this case, the thesis would follow\.

On the other hand, let\(S1∪𝒞\)∖\{α1\}\(S\_\{1\}\\cup\\mathcal\{C\}\)\\setminus\\\{\\alpha\_\{1\}\\\}beℰ\\mathcal\{E\}\-undisclosable\. Then, it contains a setS2∈𝑀𝑈𝑆​\(ℰ\)S\_\{2\}\\in\\mathit\{MUS\}\(\\mathcal\{E\}\)\. Note thatα1∉S2\\alpha\_\{1\}\\not\\in S\_\{2\}, and thatS2S\_\{2\}cannot be entirely contained in𝒞\\mathcal\{C\}\(because𝒞\\mathcal\{C\}is a GA censor ofℰ\\mathcal\{E\}\) nor inS1S\_\{1\}\(by minimality ofS1S\_\{1\}\):S2S\_\{2\}is therefore only partially contained in𝒞\\mathcal\{C\}, i\.e\.S2∈SSS\_\{2\}\\in\\SS\.

Similarly, letα2∈S2∩𝒞\\alpha\_\{2\}\\in S\_\{2\}\\cap\\mathcal\{C\}, and suppose first that\(S2∪𝒞\)∖\{α1,α2\}\(S\_\{2\}\\cup\\mathcal\{C\}\)\\setminus\\\{\\alpha\_\{1\},\\alpha\_\{2\}\\\}isℰ\\mathcal\{E\}\-disclosable, i\.e\. it belongs to some GA censor𝒞2\\mathcal\{C\}\_\{2\}ofℰ\\mathcal\{E\}\. Again,𝒞2∪\{α2\}\\mathcal\{C\}\_\{2\}\\cup\\\{\\alpha\_\{2\}\\\}is not a GA censor ofℰ\\mathcal\{E\}\(as it entirely containsS2S\_\{2\}\), which \(analogously to the above\) leads to concluding that the thesis holds\. On the other hand, supposing that\(S2∪𝒞\)∖\{α1,α2\}\(S\_\{2\}\\cup\\mathcal\{C\}\)\\setminus\\\{\\alpha\_\{1\},\\alpha\_\{2\}\\\}isℰ\\mathcal\{E\}\-undisclosable would imply that it contains a setS3∈SSS\_\{3\}\\in\\SSthat, like before, does not containα1\\alpha\_\{1\}andα2\\alpha\_\{2\}\.

Since the setSS\\SSis finite, the claim follows by iterating the above argument\.

Suppose now that there existsS∈𝑀𝑈𝑆​\(ℰ\)S\\in\\mathit\{MUS\}\(\\mathcal\{E\}\)with𝒞𝖬𝖯𝖵ℰ∩S≠∅\\mathcal\{C\}\_\{\\mathsf\{MPV\}\}^\{\\mathcal\{E\}\}\\cap S\\neq\\emptyset\. Since, by Proposition[7](https://arxiv.org/html/2607.16715#Thmproposition7),𝒞𝖬𝖯𝖵ℰ\\mathcal\{C\}\_\{\\mathsf\{MPV\}\}^\{\\mathcal\{E\}\}is a GA censor ofℰ\\mathcal\{E\}, then by Claim[5](https://arxiv.org/html/2607.16715#Thmproofx11)there exists a factα∈𝒞𝖬𝖯𝖵ℰ\\alpha\\in\\mathcal\{C\}\_\{\\mathsf\{MPV\}\}^\{\\mathcal\{E\}\}belonging to an MPV ofℰ\\mathcal\{E\}w\.r\.t\.𝒞𝖬𝖯𝖵ℰ\\mathcal\{C\}\_\{\\mathsf\{MPV\}\}^\{\\mathcal\{E\}\}\. This would, however, contradict the definition of MPV censor\. Thus,𝒞𝖬𝖯𝖵ℰ⊆𝖼𝗅𝒯​\(𝒜\)∖⋃S∈𝑀𝑈𝑆​\(ℰ\)S=𝒞𝖨𝖦𝖠ℰ\\mathcal\{C\}\_\{\\mathsf\{MPV\}\}^\{\\mathcal\{E\}\}\\subseteq\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)\\setminus\\bigcup\_\{S\\in\\mathit\{MUS\}\(\\mathcal\{E\}\)\}S=\\mathcal\{C\}\_\{\\mathsf\{IGA\}\}^\{\\mathcal\{E\}\}\. ∎

Then, we show the following strict correspondences between𝒞𝖬𝖯𝖵ℰ\\mathcal\{C\}\_\{\\mathsf\{MPV\}\}^\{\\mathcal\{E\}\}and𝒞𝖨𝖦𝖠ℰ\\mathcal\{C\}\_\{\\mathsf\{IGA\}\}^\{\\mathcal\{E\}\}\.

###### Lemma 3

Letℰ=⟨𝒯,𝒫,𝒜⟩\\mathcal\{E\}=\\langle\\mathcal\{T\},\\mathcal\{P\},\\mathcal\{A\}\\ranglebe a CQE instance such thatMPV​\(ℰ\)=MPV​\(ℰ,1\)\\textit\{MPV\}\(\\mathcal\{E\}\)=\\textit\{MPV\}\(\\mathcal\{E\},1\)\. Then,𝒞𝖬𝖯𝖵ℰ=𝒞𝖨𝖦𝖠ℰ\\mathcal\{C\}\_\{\\mathsf\{MPV\}\}^\{\\mathcal\{E\}\}=\\mathcal\{C\}\_\{\\mathsf\{IGA\}\}^\{\\mathcal\{E\}\}\.

###### Proof

Note that, ifMPV​\(ℰ\)=MPV​\(ℰ,1\)\\textit\{MPV\}\(\\mathcal\{E\}\)=\\textit\{MPV\}\(\\mathcal\{E\},1\), thenMPV​\(ℰ\)\\textit\{MPV\}\(\\mathcal\{E\}\)coincides with the sets of⊆\\subseteq\-minimalℰ\\mathcal\{E\}\-undisclosable subsets of𝖼𝗅𝒯​\(𝒜\)\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)\. Then, the thesis follows by Definition[7](https://arxiv.org/html/2607.16715#Thmdefinition7)and Proposition[1](https://arxiv.org/html/2607.16715#Thmproposition1)\. ∎

###### Theorem 5\.2

Letℰ=⟨𝒯,𝒫,𝒜⟩\\mathcal\{E\}=\\langle\\mathcal\{T\},\\mathcal\{P\},\\mathcal\{A\}\\ranglebe a CQE instance\. Then:\(i\)\(i\)if𝒫\\mathcal\{P\}is a set of denials, then,𝒞𝖬𝖯𝖵ℰ=𝒞𝖨𝖦𝖠ℰ\\mathcal\{C\}\_\{\\mathsf\{MPV\}\}^\{\\mathcal\{E\}\}=\\mathcal\{C\}\_\{\\mathsf\{IGA\}\}^\{\\mathcal\{E\}\};\(i​i\)\(ii\)if𝒯\\mathcal\{T\}is aDL\-Liteℛ\\text\{DL\-Lite\}\_\{\\mathcal\{R\}\}TBox and𝒫\\mathcal\{P\}is linear, then𝒞𝖬𝖯𝖵ℰ=𝒞𝖨𝖦𝖠ℰ\\mathcal\{C\}\_\{\\mathsf\{MPV\}\}^\{\\mathcal\{E\}\}=\\mathcal\{C\}\_\{\\mathsf\{IGA\}\}^\{\\mathcal\{E\}\}\.

###### Proof

Note that, in the hypothesis\(i\)\(i\), the fixpoint forMPV​\(ℰ,i\)\\textit\{MPV\}\(\\mathcal\{E\},i\)is already reached fori=1i=1\(i\.e\.MPV​\(ℰ,1\)=MPV​\(ℰ\)\\textit\{MPV\}\(\\mathcal\{E\},1\)=\\textit\{MPV\}\(\\mathcal\{E\}\)\)\. Then,MPV​\(ℰ\)\\textit\{MPV\}\(\\mathcal\{E\}\)coincides with the sets of⊆\\subseteq\-minimalℰ\\mathcal\{E\}\-undisclosable subsets of𝖼𝗅𝒯​\(𝒜\)\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)\. Hence, the thesis follows by Definition[7](https://arxiv.org/html/2607.16715#Thmdefinition7)and Proposition[1](https://arxiv.org/html/2607.16715#Thmproposition1)\.

Under the hypothesis\(i​i\)\(ii\), Definition[5](https://arxiv.org/html/2607.16715#Thmdefinition5)and Definition[6](https://arxiv.org/html/2607.16715#Thmdefinition6)coincide; thus, the thesis follows immediately\. ∎

In the remainder of this section, we study BUCQ entailment under this new notion of censor, forDL\-Liteℛ\\text\{DL\-Lite\}\_\{\\mathcal\{R\}\}CQE instances\. Given a BUCQqq, we writeℰ⊧𝖬𝖯𝖵q\\mathcal\{E\}\\models\_\{\\mathsf\{MPV\}\}qif𝒯∪𝒞𝖬𝖯𝖵ℰ⊧q\\mathcal\{T\}\\cup\\mathcal\{C\}\_\{\\mathsf\{MPV\}\}^\{\\mathcal\{E\}\}\\models q\. Note that, by Theorem[5\.1](https://arxiv.org/html/2607.16715#S5.Thmtheorem1), this entailment semantics is a sound approximation of IGA\-entailment, which in turn soundly approximates GA\-entailment\. Then, we define the decision problem related to MPV\-entailment, again parameterized with respect to a DLℒ\\mathcal\{L\}and a class of policiesCpC\_\{p\}\. Given anℒ\\mathcal\{L\}CQE instanceℰ=⟨𝒯,𝒫,𝒜⟩\\mathcal\{E\}=\\langle\\mathcal\{T\},\\mathcal\{P\},\\mathcal\{A\}\\ranglesuch that𝒫∈Cp\\mathcal\{P\}\\in C\_\{p\}and a BUCQqq,MPV\-Ent​\[ℒ,Cp\]\\textsc\{MPV\-Ent\}\[\\mathcal\{L\},C\_\{p\}\]is the problem of checking whetherℰ⊧𝖬𝖯𝖵q\\mathcal\{E\}\\models\_\{\\mathsf\{MPV\}\}q\.

###### Example 4

Consider again the CQE instanceℰ\\mathcal\{E\}of Example[1](https://arxiv.org/html/2607.16715#Thmexample1)\. Then, it is easy to see thatℰ⊧𝖬𝖯𝖵∃x​𝖣𝗂𝗌​\(x\)\\mathcal\{E\}\\models\_\{\\mathsf\{MPV\}\}\\exists x\\,\\mathsf\{Dis\}\(x\)andℰ⊧̸𝖬𝖯𝖵∃x​𝖺𝖿𝖿𝖡𝗒​\(x,𝖽\)\\mathcal\{E\}\\not\\models\_\{\\mathsf\{MPV\}\}\\exists x\\,\\mathsf\{affBy\}\(x,\\mathsf\{d\}\)\. On the other hand, one can verify thatℰ⊧𝖨𝖦𝖠∃x​𝖺𝖿𝖿𝖡𝗒​\(x,𝖽\)\\mathcal\{E\}\\models\_\{\\mathsf\{IGA\}\}\\exists x\\,\\mathsf\{affBy\}\(x,\\mathsf\{d\}\)\.

###### Theorem 5\.3

MPV\-Ent​\[DL\-Liteℛ,𝖯𝖫\]\\textsc\{MPV\-Ent\}\[\\text\{DL\-Lite\}\_\{\\mathcal\{R\}\},\\mathsf\{P\_\{L\}\}\]andMPV\-Ent​\[DL\-Liteℛ,𝖯𝖠\]\\textsc\{MPV\-Ent\}\[\\text\{DL\-Lite\}\_\{\\mathcal\{R\}\},\\mathsf\{P\_\{A\}\}\]are, respectively, PTIME\-hard and in PTIME in data complexity\.

###### Proof

The PTIME\-hardness follows immediately from Theorem[4\.3](https://arxiv.org/html/2607.16715#S4.Thmtheorem3)and property\(i​i\)\(ii\)of Theorem[5\.2](https://arxiv.org/html/2607.16715#S5.Thmtheorem2)\.

To prove membership in PTIME, we show that, for every integeriisuch that1≤i≤\|𝖼𝗅𝒯​\(𝒜\)\|1\\leq i\\leq\|\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)\|, the setMPV​\(ℰ,k\)\\textit\{MPV\}\(\\mathcal\{E\},k\)can be computed in polynomial time\. This is a consequence of the following properties:

- •standard BUCQ answering forDL\-Liteℛ\\text\{DL\-Lite\}\_\{\\mathcal\{R\}\}is in PTIME, hence𝖼𝗅𝒯​\(𝒜\)\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)can be computed in polynomial time w\.r\.t\. the size of𝒜\\mathcal\{A\};
- •given any EDτ\\tau, there are polynomially many substitutions ings​\(τ,Const​\(𝒜\)\)\\textit\{gs\}\(\\tau,\\textit\{Const\}\(\\mathcal\{A\}\)\);
- •given any EDτ\\tauand substitutionσ\\sigma, there are polynomially many images of𝖻𝗈𝖽𝗒​\(σ​\(τ\)\)\\mathsf\{body\}\(\\sigma\(\\tau\)\)in𝖼𝗅𝒯​\(𝒜\)\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)w\.r\.t\.𝒯\\mathcal\{T\}, because in everyDL\-Liteℛ\\text\{DL\-Lite\}\_\{\\mathcal\{R\}\}ontology, every image of a BCQq′q^\{\\prime\}has size at mostkk, wherekkis the number of atoms inq′q^\{\\prime\}\[[6](https://arxiv.org/html/2607.16715#bib.bib98)\]\.

Therefore, every setMPV​\(ℰ,i\)\\textit\{MPV\}\(\\mathcal\{E\},i\)can be computed in polynomial time w\.r\.t\. the size of𝒜\\mathcal\{A\}, which implies the thesis\. ∎

We finally state the following fundamental property, which derives from the fact that the MPV censor can always be used as the ABox𝒜′\\mathcal\{A\}^\{\\prime\}of Definition[4](https://arxiv.org/html/2607.16715#Thmdefinition4)\.

###### Proposition 8

For every DLℒ\\mathcal\{L\}, MPV\-entailment satisfies the indistinguishability property forℒ\\mathcal\{L\}and𝖯𝖠\\mathsf\{P\_\{A\}\}\.

## 6Implementation and Experiments

We have conducted an experimental evaluation of MPV\-entailment overDL\-Liteℛ\\text\{DL\-Lite\}\_\{\\mathcal\{R\}\}CQE instances\. Our experiments are based on an implementation of an algorithm for MPV\-entailment that works withDL\-Liteℛ\\text\{DL\-Lite\}\_\{\\mathcal\{R\}\}CQE instances \(Algorithm[3](https://arxiv.org/html/2607.16715#algorithm3)\)\. Before describing the algorithm, we introduce some auxiliary notions\.

Given a BCQqq, a homomorphism forqqis a mappinghhof the terms occurring inqqto individuals, such thath​\(a\)=ah\(a\)=afor every individualaa\. Given a homomorphismh:x→→t→h:\\vec\{x\}\\rightarrow\\vec\{t\}forqq, we denote byh​\(q\)h\(q\)the set of atoms\{p​\(t→\)∣p​\(x→\)​occurs in​q​and​h​\(x→\)=t→\}\.\\\{p\(\\vec\{t\}\)\\mid p\(\\vec\{x\}\)\\textrm\{ occurs in \}q\\textrm\{ and \}h\(\\vec\{x\}\)=\\vec\{t\}\\\}\.

Given an ABox𝒜\\mathcal\{A\}, we call a subset𝒜′\\mathcal\{A\}^\{\\prime\}of𝒜\\mathcal\{A\}a*homomorphic image*ofqqin𝒜\\mathcal\{A\}if there exists a homomorphismhhforqqsuch that𝒜′=h​\(q\)\\mathcal\{A\}^\{\\prime\}=h\(q\)\. We denote byHI​\(q\)\\textit\{HI\}\(q\)the set of all homomorphic images ofqq\.

input :A

DL\-Liteℛ\\text\{DL\-Lite\}\_\{\\mathcal\{R\}\}CQE instance

⟨𝒯,𝒫,𝒜⟩\\langle\\mathcal\{T\},\\mathcal\{P\},\\mathcal\{A\}\\rangle, a BUCQ

qq;

output :A Boolean value;

1

𝒜′←∅\\mathcal\{A\}^\{\\prime\}\\leftarrow\\emptyset;

2repeat

3

𝒜p′←𝒜′\\mathcal\{A\}\_\{p\}^\{\\prime\}\\leftarrow\\mathcal\{A\}^\{\\prime\};

4

ℐ←∅\\mathcal\{I\}\\leftarrow\\emptyset;

5foreach*τ∈𝒫\\tau\\in\\mathcal\{P\}*do

6foreach*σ∈gs​\(τ,Const​\(𝒜\)\)\\sigma\\in\\textit\{gs\}\(\\tau,\\textit\{Const\}\(\\mathcal\{A\}\)\)*do

7if*𝒯∪𝒜⊧𝖻𝗈𝖽𝗒​\(σ​\(τ\)\)\\mathcal\{T\}\\cup\\mathcal\{A\}\\models\\mathsf\{body\}\(\\sigma\(\\tau\)\)and𝒯∪\(𝖼𝗅𝒯​\(𝒜\)∖𝒜p′\)⊧̸𝗁𝖾𝖺𝖽​\(σ​\(τ\)\)\\mathcal\{T\}\\cup\(\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)\\setminus\\mathcal\{A\}\_\{p\}^\{\\prime\}\)\\not\\models\\mathsf\{head\}\(\\sigma\(\\tau\)\)*then

8

ℐ←ℐ∪\{𝒜′′∣𝒜′′⊆𝖼𝗅𝒯\(𝒜\)\\mathcal\{I\}\\leftarrow\\mathcal\{I\}\\cup\\\{\\mathcal\{A\}^\{\\prime\\prime\}\\mid\\mathcal\{A\}^\{\\prime\\prime\}\\subseteq\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\),

𝒜′′∈HI​\(σ​\(q′\)\)\\mathcal\{A\}^\{\\prime\\prime\}\\in\\textit\{HI\}\(\\sigma\(q^\{\\prime\}\)\)and

q′∈QRew\(𝖻𝗈𝖽𝗒\(τ\),𝒯\)\}q^\{\\prime\}\\in\\textit\{QRew\}\(\\mathsf\{body\}\(\\tau\),\\mathcal\{T\}\)\\\};

9

ℐ←\{S∈ℐ∣∄​S′∈ℐ​s\.t\.​S′⊂S\}\\mathcal\{I\}\\leftarrow\\\{S\\in\\mathcal\{I\}\\mid\\nexists S^\{\\prime\}\\in\\mathcal\{I\}\\mbox\{ s\.t\.\\ \}S^\{\\prime\}\\subset S\\\};

10

𝒜′←𝒜′∪⋃𝒜′′∈ℐ𝒜′′\\mathcal\{A\}^\{\\prime\}\\leftarrow\\mathcal\{A\}^\{\\prime\}\\cup\\bigcup\_\{\\mathcal\{A\}^\{\\prime\\prime\}\\in\\mathcal\{I\}\}\\mathcal\{A\}^\{\\prime\\prime\};

11until*𝒜′=𝒜p′\\mathcal\{A\}^\{\\prime\}=\\mathcal\{A\}\_\{p\}^\{\\prime\}*;

12if*𝒯∪𝖼𝗅𝒯​\(𝒜\)∖𝒜′⊧q\\mathcal\{T\}\\cup\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)\\setminus\\mathcal\{A\}^\{\\prime\}\\models q*then

13return*true;*

return*false;*

Algorithm 3𝖬𝖯𝖵​\-​𝖤𝗇𝗍𝖺𝗂𝗅𝗌​\-​𝖣𝖫​\-​𝖫𝗂𝗍𝖾ℛ\\mathsf\{MPV\\text\{\-\}Entails\\text\{\-\}DL\\text\{\-\}Lite\_\{\\mathcal\{R\}\}\}We are now ready to present the algorithm𝖬𝖯𝖵​\-​𝖤𝗇𝗍𝖺𝗂𝗅𝗌​\-​𝖣𝖫​\-​𝖫𝗂𝗍𝖾ℛ\\mathsf\{MPV\\text\{\-\}Entails\\text\{\-\}DL\\text\{\-\}Lite\_\{\\mathcal\{R\}\}\}\(Algorithm[3](https://arxiv.org/html/2607.16715#algorithm3)\) that decides MPV\-entailment of BUCQs overDL\-Liteℛ\\text\{DL\-Lite\}\_\{\\mathcal\{R\}\}CQE instances\. In the algorithm,QRewdenotes a procedure for UCQ rewriting inDL\-Liteℛ\\text\{DL\-Lite\}\_\{\\mathcal\{R\}\}: for everyDL\-Liteℛ\\text\{DL\-Lite\}\_\{\\mathcal\{R\}\}TBox𝒯\\mathcal\{T\}and UCQqq,QRew​\(q,𝒯\)\\textit\{QRew\}\(q,\\mathcal\{T\}\)returns a UCQq′q^\{\\prime\}such that, for every ABox𝒜\\mathcal\{A\},𝒯∪𝒜⊧q​\(c→\)\\mathcal\{T\}\\cup\\mathcal\{A\}\\models q\(\\vec\{c\}\)iff𝒜⊧q′​\(c→\)\\mathcal\{A\}\\models q^\{\\prime\}\(\\vec\{c\}\)\.

###### Proposition 9

Letℰ\\mathcal\{E\}be aDL\-Liteℛ\\text\{DL\-Lite\}\_\{\\mathcal\{R\}\}CQE instance and letqqbe a BUCQ\. Then,𝖬𝖯𝖵​\-​𝖤𝗇𝗍𝖺𝗂𝗅𝗌​\-​𝖣𝖫​\-​𝖫𝗂𝗍𝖾ℛ​\(ℰ,q\)\\mathsf\{MPV\\text\{\-\}Entails\\text\{\-\}DL\\text\{\-\}Lite\_\{\\mathcal\{R\}\}\}\(\\mathcal\{E\},q\)returnstrueiffℰ⊧𝖬𝖯𝖵q\\mathcal\{E\}\\models\_\{\\mathsf\{MPV\}\}q\.

###### Proof

First, recall that, for everyτ∈𝒫\\tau\\in\\mathcal\{P\},QRew​\(𝖻𝗈𝖽𝗒​\(τ\),𝒯\)\\textit\{QRew\}\(\\mathsf\{body\}\(\\tau\),\\mathcal\{T\}\)returns a UCQq′q^\{\\prime\}such that for every ABox𝒜\\mathcal\{A\}and for everyσ∈gs​\(τ,Const​\(𝒜\)\)\\sigma\\in\\textit\{gs\}\(\\tau,\\textit\{Const\}\(\\mathcal\{A\}\)\),𝒯∪𝒜⊧𝖻𝗈𝖽𝗒​\(σ​\(τ\)\)\\mathcal\{T\}\\cup\\mathcal\{A\}\\models\\mathsf\{body\}\(\\sigma\(\\tau\)\)iff𝒜⊧σ​\(q′\)\\mathcal\{A\}\\models\\sigma\(q^\{\\prime\}\)\.

Then, we prove the following property \(\*\): at every iterationiiof the repeat–until loop of the algorithm, the set of setsℐ\\mathcal\{I\}computed after the minimization step of line[3](https://arxiv.org/html/2607.16715#algorithm3)is the set of all the minimal policy violations ofℰ\\mathcal\{E\}with respect to𝒜p′\\mathcal\{A\}\_\{p\}^\{\\prime\}\. Suppose𝒜′′\\mathcal\{A\}^\{\\prime\\prime\}is a minimal policy violation ofℰ\\mathcal\{E\}with respect to𝒜p′\\mathcal\{A\}\_\{p\}^\{\\prime\}\. Then, there existτ∈𝒫\\tau\\in\\mathcal\{P\}andσ∈gs​\(τ,Const​\(𝒜\)\)\\sigma\\in\\textit\{gs\}\(\\tau,\\textit\{Const\}\(\\mathcal\{A\}\)\)such that𝒯∪𝒜′′⊧𝖻𝗈𝖽𝗒​\(σ​\(τ\)\)\\mathcal\{T\}\\cup\\mathcal\{A\}^\{\\prime\\prime\}\\models\\mathsf\{body\}\(\\sigma\(\\tau\)\)and𝒯∪\(𝒞∖𝒜p′\)⊧̸𝗁𝖾𝖺𝖽​\(σ​\(τ\)\)\\mathcal\{T\}\\cup\(\\mathcal\{C\}\\setminus\\mathcal\{A\}\_\{p\}^\{\\prime\}\)\\not\\models\\mathsf\{head\}\(\\sigma\(\\tau\)\)\. Consequently,𝒜′′⊧σ​\(q′\)\\mathcal\{A\}^\{\\prime\\prime\}\\models\\sigma\(q^\{\\prime\}\), whereq′q^\{\\prime\}is the UCQ returned byQRew​\(𝖻𝗈𝖽𝗒​\(τ\),𝒯\)\\textit\{QRew\}\(\\mathsf\{body\}\(\\tau\),\\mathcal\{T\}\)\. Consequently,𝒜′′\\mathcal\{A\}^\{\\prime\\prime\}is a homomorphic image ofQRew​\(𝖻𝗈𝖽𝗒​\(τ\),𝒯\)\\textit\{QRew\}\(\\mathsf\{body\}\(\\tau\),\\mathcal\{T\}\)in𝖼𝗅𝒯​\(𝒜\)\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\), hence𝒜′′∈ℐ\\mathcal\{A\}^\{\\prime\\prime\}\\in\\mathcal\{I\}before the minimization ofℐ\\mathcal\{I\}\. Furthermore, it is immediate to verify that every set𝒜′′\\mathcal\{A\}^\{\\prime\\prime\}that belongs to the set of setsℐ\\mathcal\{I\}before its minimization contains a minimal policy violation ofℰ\\mathcal\{E\}with respect to𝒜p′\\mathcal\{A\}\_\{p\}^\{\\prime\}\. These two properties imply that, before its minimization, the set of setsℐ\\mathcal\{I\}computed by the algorithm contains all the minimal policy violations ofℰ\\mathcal\{E\}w\.r\.t\.𝒜p′\\mathcal\{A\}\_\{p\}^\{\\prime\}and supersets of them\. Consequently, property \(\*\) follows\.

Finally, property \(\*\) immediately implies that the set𝒜′\\mathcal\{A\}^\{\\prime\}computed by the algorithm at theii\-th iteration corresponds toMPV​\(ℰ,i\)\\textit\{MPV\}\(\\mathcal\{E\},i\)\. Consequently, the set𝒞\\mathcal\{C\}computed by the algorithm corresponds to𝒞𝖬𝖯𝖵ℰ\\mathcal\{C\}\_\{\\mathsf\{MPV\}\}^\{\\mathcal\{E\}\}, which implies the thesis\. ∎

We implemented the algorithm𝖬𝖯𝖵​\-​𝖤𝗇𝗍𝖺𝗂𝗅𝗌​\-​𝖣𝖫​\-​𝖫𝗂𝗍𝖾ℛ\\mathsf\{MPV\\text\{\-\}Entails\\text\{\-\}DL\\text\{\-\}Lite\_\{\\mathcal\{R\}\}\}as a procedure operating over a relational database storing ABox facts\. We ran the algorithm both in its full version and in a modified version \(called𝖠𝖬𝖯𝖵​\-​𝖤𝗇𝗍𝖺𝗂𝗅𝗌​\-​𝖣𝖫​\-​𝖫𝗂𝗍𝖾ℛ\\mathsf\{AMPV\\text\{\-\}Entails\\text\{\-\}DL\\text\{\-\}Lite\_\{\\mathcal\{R\}\}\}\), which does not perform the elimination of non\-minimal homomorphic images of the rewriting of the bodies of the violated EDs \(i\.e\. it skips Step[3](https://arxiv.org/html/2607.16715#algorithm3)of Algorithm[3](https://arxiv.org/html/2607.16715#algorithm3)\)\. In this way,𝖠𝖬𝖯𝖵​\-​𝖤𝗇𝗍𝖺𝗂𝗅𝗌​\-​𝖣𝖫​\-​𝖫𝗂𝗍𝖾ℛ\\mathsf\{AMPV\\text\{\-\}Entails\\text\{\-\}DL\\text\{\-\}Lite\_\{\\mathcal\{R\}\}\}computes a set of atoms𝒜′\\mathcal\{A\}^\{\\prime\}that is in general larger thanMPV​\(ℰ,i\)\\textit\{MPV\}\(\\mathcal\{E\},i\), since also non\-minimal homomorphic images \(i\.e\. non\-minimal policy violations\) are deleted from𝖼𝗅𝒯​\(𝒜\)\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)\. Such a set𝒜′\\mathcal\{A\}^\{\\prime\}is still a GA censor \(which is an immediate consequence of property\(i\)\(i\)of Proposition[7](https://arxiv.org/html/2607.16715#Thmproposition7)\), and we call it the AMPV censor ofℰ\\mathcal\{E\}\. Consequently,𝖠𝖬𝖯𝖵​\-​𝖤𝗇𝗍𝖺𝗂𝗅𝗌​\-​𝖣𝖫​\-​𝖫𝗂𝗍𝖾ℛ\\mathsf\{AMPV\\text\{\-\}Entails\\text\{\-\}DL\\text\{\-\}Lite\_\{\\mathcal\{R\}\}\}computes a sound approximation of MPV\-entailment\. Nevertheless, our experiments showed that such a minimization step is often computationally expensive, so we decided to test its real impact in terms of query answers\.

Experiments were run on a laptop with an Intel Core i7\-7700HQ processor running at 2\.80 GHz, and 8 GB of RAM; the prototype is written in Java 11 and relies on MySQL 8\.0 for ABox storage and manipulation\. The employed OWL ontology belongs to the OWL2Bench\[[17](https://arxiv.org/html/2607.16715#bib.bib2)\]benchmark, and it consists of a fixed TBox about the university domain, 10 OWL 2 QL queries\[[16](https://arxiv.org/html/2607.16715#bib.bib3)\], and a tool that, given as input a positive integerNN\(representing the number of universities\), generates an ABox of proportional size\. We consideredN∈\{1,5,10,20,25,50\}N\\in\\\{1,5,10,20,25,50\\\}, using the default seed for ABox generation\. Furthermore, we defined a policy consisting of 11 EDs of the general type\. The source code of our implementation is publicly available at[https://github\.com/iswc\-2026\-anon/MPVCensor](https://github.com/iswc-2026-anon/MPVCensor)\.

All the data manipulation steps required by Algorithm[3](https://arxiv.org/html/2607.16715#algorithm3)have been implemented, in practice, using suitable SQLUPDATEandDELETEoperations\. In our implementation, the functionQRewis provided by the tree\-witness query rewriter for OWL2 QL ontologies222[https://titan\.dcs\.bbk\.ac\.uk/˜roman/tw\-rewriting/](https://titan.dcs.bbk.ac.uk/~roman/tw-rewriting/)\[[11](https://arxiv.org/html/2607.16715#bib.bib6),[15](https://arxiv.org/html/2607.16715#bib.bib8)\]\. More details about the implementation and optimizations are provided in the Appendix\.

Dataset size \(NN\)1510202550\|𝒜\|\|\\mathcal\{A\}\|50\.2k325\.5k711\.1k1\.4M1\.7M3\.5M\|𝖼𝗅𝒯​\(𝒜\)\|\|\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)\|89\.6k595\.1k1\.3M2\.5M3\.1M6\.4M\#ampv\\\#\_\{\\textrm\{ampv\}\}14\.6k91\.1k191\.7k383\.9k462\.3k960\.1k\#mpva\\\#\_\{\\textrm\{mpv\\phantom\{a\}\}\}13\.3k82\.5k173\.3k–––tampvt\_\{\\textrm\{ampv\}\}29\.184\.3136\.7295\.1305\.7689\.1tmpvat\_\{\\textrm\{mpv\\phantom\{a\}\}\}80\.72568\.310621\.6t\.o\.t\.o\.t\.o\.Table 1:This table reports the cardinality of the original ABox𝒜\\mathcal\{A\}and of its closure w\.r\.t\.𝒯\\mathcal\{T\}, other than the number \(\#\\\#\) of facts removed from\|𝖼𝗅𝒯​\(𝒜\)\|\|\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)\|and the time \(tt, expressed in seconds\) to compute the \(A\)MPV censor\.NBenchmark queryq1q\_\{1\}q2q\_\{2\}q3q\_\{3\}q5q\_\{5\}q6q\_\{6\}q7q\_\{7\}q8q\_\{8\}q9q\_\{9\}q10q\_\{10\}11tat\_\{a\}2\.511\.10\.81\.10\.813\.24\.512\.53\.2tmt\_\{m\}2\.710\.20\.60\.70\.853\.36\.912\.7152\.9\#a6861684230057969314571\#m94316842300579170114571\#∅1427168466662422858282514510655tat\_\{a\}6\.989\.90\.71\.10\.576\.218\.558\.525\.1tmt\_\{m\}9\.497\.50\.41\.30\.550\.238\.2110\.368\.6\#a46261887252020395144181698453\#m633018872520203951112861698453\#∅9228188723435741623654891790416986421010tat\_\{a\}15\.5347\.90\.41\.80\.4297\.836\.6108\.440\.4tmt\_\{m\}32\.11172\.90\.41\.60\.4201\.993\.6101\.1138\.5\#a9947441901442409132983834341109\#m135424419014424091322465034341109\#∅1978244190756564358891196939278343414132020tat\_\{a\}29\.51342\.60\.63\.20\.5430\.663\.3259\.266\.7\#a1910988268229200168031915168422193\#∅382518826814314962693972312476555684227502525tat\_\{a\}37\.41848\.10\.45\.10\.4541\.890\.4297\.9106\.5\#a23586109957309260217552326484002684\#∅4733610995718015788863762863794381840034445050tat\_\{a\}263\.14058\.10\.57\.10\.41051\.1245\.1690\.9345\.6\#a4855222712064231604309847538182885052\#∅964862271203653658817494758409192944182887137Table 2:For each query and dataset size, the table reports the execution time \(tat\_\{a\}, in ms\) and the number of answers \(\#a\) for queries posed to the AMPV censor, whiletmt\_\{m\}and \#mrefer to query evaluation over the MPV censor\. We also report the query answers obtained in case𝒫=∅\\mathcal\{P\}=\\emptyset\(\#∅\) for a comparison\.Tables[1](https://arxiv.org/html/2607.16715#S6.T1)and[2](https://arxiv.org/html/2607.16715#S6.T2)report the performance evaluation of our experiments , in particular regarding the computation of the \(A\)MPV censor and the subsequent query evaluation\.

Considering Table[1](https://arxiv.org/html/2607.16715#S6.T1), we remark that, differently from the MPV censor, the time required for computing the AMPV censor increases linearly w\.r\.t\. the size of the original dataset\. On the other hand, the minimality check of Algorithm[3](https://arxiv.org/html/2607.16715#algorithm3)crucially affects the overall time required for computing the MPV censor\.

As for query evaluation, we considered all 10 CQs of the OWL2Bench benchmark; however, one of these queries \(q4q\_\{4\}\) produced no answers even in the uncensored case, so we do not report results about it\. Then, Table[2](https://arxiv.org/html/2607.16715#S6.T2)shows that:\(i\)\(i\)all queries, except forq2q\_\{2\}andq9q\_\{9\}, are affected significantly by the data protection policy;\(i​i\)\(ii\)one query \(q6q\_\{6\}\) does not have any answer in the MPV censor;\(i​i​i\)\(iii\)for two queries \(q1q\_\{1\}andq8q\_\{8\}\), the number of answers in the AMPV censor is significantly smaller than in the MPV censor\. All the other queries yield the same number of answers\.

## 7Conclusions

We investigated CQE under policies expressed via epistemic dependencies \(EDs\), focusing on the use of ground atom \(GA\) censors for safe information disclosure\. We first investigated GA\- and IGA\-entailment and analyzed their data complexity in the presence of ED\-based policies when the TBox is expressed inDL\-Liteℛ\\text\{DL\-Lite\}\_\{\\mathcal\{R\}\}, both in the case of linear ED and in the general case\. Since both semantics resulted in being computationally hard in terms of data complexity, we defined a new semantics, called MPV, and showed that it is computationally easier and provides a sound approximation of query answering with respect to the previous semantics\. Finally, we evaluated our approach with a prototype implementation, using the OWL2Bench benchmark\.

The present contribution can be extended in different directions\. Potential future work includes: finding new sufficient conditions for the MPV censor to coincide with the intersection𝒞𝖨𝖦𝖠ℰ\\mathcal\{C\}\_\{\\mathsf\{IGA\}\}^\{\\mathcal\{E\}\}of all optimal GA censors; studying the practical impact of the MPV semantics on the amount of information missed w\.r\.t\. the IGA semantics; extending the computational study of MPV\-entailment to ontologies expressed in other lightweight DLs likeℰ​ℒ\\mathcal\{EL\}orℛ​ℒ\\mathcal\{RL\}, the logics underlying the OWL 2 EL and OWL 2 RL profiles; finding alternative, well\-founded semantics that soundly approximateGA\-Entand preserve tractability of query answering even when using arbitrary EDs\.

## References

- \[1\]D\. Baura and D\. Calvanese\(2026\)Assessing privacy requirements for controlled query evaluation in OBDA\.InModeling Decisions for Artificial Intelligence,Cham,pp\. 183–197\.External Links:ISBN 978\-3\-032\-00891\-6Cited by:[§1](https://arxiv.org/html/2607.16715#S1.p8.1)\.
- \[2\]J\. Biskup and P\. A\. Bonatti\(2004\)Controlled query evaluation for enforcing confidentiality in complete information systems\.Int\. J\. Inf\. Sec\.3\(1\),pp\. 14–27\.Cited by:[§1](https://arxiv.org/html/2607.16715#S1.p1.1),[§1](https://arxiv.org/html/2607.16715#S1.p5.2),[§3](https://arxiv.org/html/2607.16715#S3.p9.1)\.
- \[3\]P\. A\. Bonatti, G\. Cima, D\. Lembo, F\. Magliocca, L\. Marconi, R\. Rosati, L\. Sauro, and D\. F\. Savo\(2025\)Enhancing cooperativity in controlled query evaluation over ontologies\.Artif\. Intell\.348,pp\. 104402\.External Links:[Document](https://dx.doi.org/10.1016/J.ARTINT.2025.104402)Cited by:[§4\.1](https://arxiv.org/html/2607.16715#S4.SS1.p6.2)\.
- \[4\]P\. A\. Bonatti and L\. Sauro\(2013\)A confidentiality model for ontologies\.InProc\. of the 12th Int\. Semantic Web Conf\. \(ISWC\),Lecture Notes in Computer Science, Vol\.8218,pp\. 17–32\.Cited by:[§1](https://arxiv.org/html/2607.16715#S1.p1.1)\.
- \[5\]D\. Calvanese, G\. De Giacomo, D\. Lembo, M\. Lenzerini, and R\. Rosati\(2007\)EQL\-Lite: effective first\-order query processing in description logics\.InProc\. of the 20th Int\. Joint Conf\. on Artificial Intelligence \(IJCAI\),pp\. 274–279\.Cited by:[§3](https://arxiv.org/html/2607.16715#S3.p1.1)\.
- \[6\]D\. Calvanese, G\. De Giacomo, D\. Lembo, M\. Lenzerini, and R\. Rosati\(2007\)Tractable reasoning and efficient query answering in description logics: theDL\-Litefamily\.J\. of Automated Reasoning39\(3\),pp\. 385–429\.Cited by:[§1](https://arxiv.org/html/2607.16715#S1.p1.1),[§2](https://arxiv.org/html/2607.16715#S2.p3.19),[§2](https://arxiv.org/html/2607.16715#S2.p5.3),[§4\.2](https://arxiv.org/html/2607.16715#S4.SS2.p6.10),[3rd item](https://arxiv.org/html/2607.16715#S5.I5.i3.p1.10)\.
- \[7\]J\. Chomicki and J\. Marcinkowski\(2005\)Minimal\-change integrity maintenance using tuple deletions\.Information and Computation197\(1\-2\),pp\. 90–121\.Cited by:[§4\.1](https://arxiv.org/html/2607.16715#S4.SS1.p1.1),[§4\.1](https://arxiv.org/html/2607.16715#Thmproofx1.p1.1)\.
- \[8\]G\. Cima, D\. Lembo, L\. Marconi, R\. Rosati, and D\. F\. Savo\(2024\-Aug\.\)Enhancing controlled query evaluation through epistemic policies\.InProc\. of the 33th Int\. Joint Conf\. on Artificial Intelligence \(IJCAI\),pp\. 3307–3314\.Cited by:[§1](https://arxiv.org/html/2607.16715#S1.p2.11),[§1](https://arxiv.org/html/2607.16715#S1.p3.1),[§1](https://arxiv.org/html/2607.16715#S1.p5.2),[§3](https://arxiv.org/html/2607.16715#S3.p1.1),[§3](https://arxiv.org/html/2607.16715#S3.p9.1)\.
- \[9\]G\. Cima, D\. Lembo, R\. Rosati, and D\. F\. Savo\(2024\)Controlled query evaluation in description logics through consistent query answering\.Artificial Intelligence334,pp\. 104176\.Cited by:[§0\.A\.1](https://arxiv.org/html/2607.16715#Pt0.A1.SS1.SSS0.Px3.SPx2.p1.3),[§1](https://arxiv.org/html/2607.16715#S1.p1.1),[§3](https://arxiv.org/html/2607.16715#S3.p6.1)\.
- \[10\]B\. Cuenca Grau, E\. Kharlamov, E\. V\. Kostylev, and D\. Zheleznyakov\(2013\)Controlled query evaluation over OWL 2 RL ontologies\.InProc\. of the 12th Int\. Semantic Web Conf\. \(ISWC\),pp\. 49–65\.Cited by:[§1](https://arxiv.org/html/2607.16715#S1.p1.1)\.
- \[11\]S\. Kikot, R\. Kontchakov, and M\. Zakharyaschev\(2012\)Conjunctive query answering with OWL 2 QL\.InProc\. of the 13th Int\. Conf\. on the Principles of Knowledge Representation and Reasoning \(KR\),Cited by:[§6](https://arxiv.org/html/2607.16715#S6.p7.1)\.
- \[12\]S\. L\., W\. de Jonge, and R\. P\. van de Riet\(1983\)Answering queries without revealing secrets\.ACM Trans\. on Database Systems8\(1\),pp\. 41–59\.Cited by:[§1](https://arxiv.org/html/2607.16715#S1.p1.1)\.
- \[13\]L\. Marconi, F\. Ricci, and R\. Rosati\(2025\)Controlled query evaluation under epistemic dependencies: algorithms and experiments\.InProc\. of the 24th Int\. Semantic Web Conf\. \(ISWC\),Lecture Notes in Computer Science, Vol\.16140,pp\. 521–538\.Cited by:[§1](https://arxiv.org/html/2607.16715#S1.p4.1),[§1](https://arxiv.org/html/2607.16715#S1.p6.2),[§1](https://arxiv.org/html/2607.16715#S1.p8.1),[§4\.2](https://arxiv.org/html/2607.16715#S4.SS2.p2.6),[§4\.2](https://arxiv.org/html/2607.16715#S4.SS2.p3.7),[§4\.1](https://arxiv.org/html/2607.16715#Thmproofx5.p1.4)\.
- \[14\]B\. Motik, A\. Fokoue, I\. Horrocks, Z\. Wu, C\. Lutz, and B\. Cuenca Grau\(2009\-10\)OWL Web Ontology Language profiles\.W3C RecommendationWorld Wide Web Consortium\.Note:Available at[http://www\.w3\.org/TR/owl\-profiles/](http://www.w3.org/TR/owl-profiles/)Cited by:[§1](https://arxiv.org/html/2607.16715#S1.p1.1)\.
- \[15\]M\. Rodriguez\-Muro, R\. Kontchakov, and M\. Zakharyaschev\(2013\)Ontology\-based data access: ontop of databases\.InProc\. of the 12th Int\. Semantic Web Conf\. \(ISWC\),Lecture Notes in Computer Science, Vol\.8218,pp\. 558–573\.Cited by:[§6](https://arxiv.org/html/2607.16715#S6.p7.1)\.
- \[16\]G\. Singh, S\. Bhatia, and R\. Mutharaju\(2020\-05\)OWL2Bench SPARQL queries\.Zenodo\.Note:Available at: https://zenodo\.org/records/3838735External Links:[Document](https://dx.doi.org/10.5281/zenodo.3838735),[Link](https://zenodo.org/records/3838735)Cited by:[§0\.A\.3\.1](https://arxiv.org/html/2607.16715#Pt0.A1.SS3.SSS1.Px1.p1.5),[Appendix 0\.B](https://arxiv.org/html/2607.16715#Pt0.A2.p1.1),[§6](https://arxiv.org/html/2607.16715#S6.p6.2)\.
- \[17\]G\. Singh, S\. Bhatia, and R\. Mutharaju\(2020\)OWL2Bench: A benchmark for OWL 2 reasoners\.InProc\. of the 19th Int\. Semantic Web Conf\. \(ISWC\),Lecture Notes in Computer Science, Vol\.12507,pp\. 81–96\.Cited by:[§1](https://arxiv.org/html/2607.16715#S1.p8.1),[§6](https://arxiv.org/html/2607.16715#S6.p6.2)\.
- \[18\]M\. Y\. Vardi\(1982\)The complexity of relational query languages\.InProc\. of the 14th ACM SIGACT Symp\. on Theory of Computing \(STOC\),pp\. 137–146\.Cited by:[§2](https://arxiv.org/html/2607.16715#S2.p5.3)\.

## Appendix

## Appendix 0\.APractical implementation and experiments

This section provides further details on our implementation and experimental evaluation\.

### 0\.A\.1System architecture and implementation setting

The ABox is stored in a MySQL database, where each predicate is represented by a table whose schema reflects the arity of the predicate\. Unary and binary predicates are mapped to single\-column \(attr1\) and two\-column \(attr1,attr2\) tables, respectively\.

The interaction between the application layer and the database is mediated by a SQL generation component, which translates logical formulas into executable SQL queries, which are used both for manipulating the data \(i\.e\. for computing the \(A\)MPV censor\) and for query answering\.

##### Input, output, and execution setup\.

The implemented software takes as input a TBox expressed as an OWL 2 QL ontology, a confidentiality policy specified through a JSON file, and an ABox stored in a relational database\. In the implementation, the ABox is accessed through a database connection\. The \(A\)MPV censor is stored in a new database instance\.

Before executing the algorithm for computing the \(A\)MPV censor, the software loads and preprocesses both the ontology and the policy\. The TBox is loaded and prepared in order to support ABox and policy expansion\. In particular, during the TBox preprocessing phase, data properties are removed from the input ontology, as they are not part ofDL\-Liteℛ\\text\{DL\-Lite\}\_\{\\mathcal\{R\}\}, and OWL axioms that are not supported by the tree\-witness library are rewritten as follows:

- •OWLEquivalentClassesAxiom axioms are expressed using two instances of OWLSubClassOfAxiom \(i\.e\., the equivalence between conceptsAAandBBis expressed asA⊑BA\\sqsubseteq BandB⊑AB\\sqsubseteq A\);
- •OWLEquivalentObjectPropertiesAxiom axioms are expressed using multiple instances of OWLSubObjectPropertyOfAxiom \(i\.e\., the equivalence between rolesRRandSSis expressed asR⊑SR\\sqsubseteq SandS⊑RS\\sqsubseteq R\);
- •OWLSymmetricObjectPropertyAxiom axioms are expressed using an OWLInverseObjectPropertiesAxiom and an OWLSubObjectPropertyOfAxiom \(i\.e\., role symmetry is expressed asR−⊑RR^\{\-\}\\sqsubseteq R\)\.

The policy is parsed from the JSON file and translated into a set ofEpistemicDependencyJava objects\.

###### Example 5

The linear ED

∀x​\(K​𝖤𝗆𝗉𝗅𝗈𝗒𝖾𝖾​\(x\)→K​∃y​𝗐𝗈𝗋𝗄𝗌𝖥𝗈𝗋​\(x,y\)\)\\forall x\\,\(\\mathrm\{K\}\\mathsf\{Employee\}\(x\)\\rightarrow\\mathrm\{K\}\\exists y\\,\\mathsf\{worksFor\}\(x,y\)\)can be specified in the JSON policy file as follows:

```
{
  "body": "Q(x) :- :Employee(x).",
  "head": "Q(x) :- :worksFor(x,y)."
}
```

##### Structure of the algorithm\.

The \(A\)MPV censor is constructed by iteratively modifying a working copy of the database, removing ABox assertions that violate the confidentiality policy\. In particular, the algorithm is organized into three main phases:

1. \(i\)\(i\)initialization phase, which prepares the input data and policy;
2. \(i​i\)\(ii\)iterative phase, in which policy violations are detected and the corresponding tuples are removed;
3. \(i​i​i\)\(iii\)final phase, in which a fixpoint is reached and no further deletions are performed\.

##### Initialization phase\.

The initialization phase consists of a sequence of steps, that prepare the data, the ontology, and the policy before the execution of the iterative censorship phase\. In the following, we analyze each of these steps\.

###### ABox cloning\.

As a first step of the initialization phase, a working copy of the database storing the ABox is created\. For each table of the original database, the corresponding table structure is recreated in the cloned database, and all tuples are copied\. This approach ensures that the censorship process operates on an isolated copy of the data\. As a result, the original ABox remains unchanged, while the algorithm can perform arbitrary data manipulation\.

###### ABox expansion\.

The next step includes the expansion of the ABox with respect to the TBox, i\.e\. the computation of𝖼𝗅𝒯​\(𝒜\)\\mathsf\{cl\}\_\{\\mathcal\{T\}\}\(\\mathcal\{A\}\)\. The expansion is performed predicate\-wise\. For each concept and object property occurring in the TBox, an atomic rewriting with respect to the ontology is computed by applying𝖠𝗍𝗈𝗆𝖱𝖾𝗐𝗋\\mathsf\{AtomRewr\}\[[9](https://arxiv.org/html/2607.16715#bib.bib102)\]\(a simplified implementation ofQRewfor atomic queries\) to the corresponding predicate atom\. Such a rewriting captures all the possible ways in which instances of the corresponding predicate can be inferred from existing ABox assertions and TBox axioms\.

###### Example 6

Consider the following TBox:

𝒯=\{\\displaystyle\\mathcal\{T\}=\\\{∃𝖺𝗍𝗍𝖾𝗇𝖽𝗌⊑𝖲𝗍𝗎𝖽𝖾𝗇𝗍,\\displaystyle\\exists\\,\\mathsf\{attends\}\\sqsubseteq\\mathsf\{Student\},∃𝖺𝗍𝗍𝖾𝗇𝖽𝗌−⊑𝖢𝗈𝗎𝗋𝗌𝖾\}\\displaystyle\\exists\\,\\mathsf\{attends\}^\{\-\}\\sqsubseteq\\mathsf\{Course\}\\,\\\}
By applying the atomic rewriting procedure𝖠𝗍𝗈𝗆𝖱𝖾𝗐𝗋\\mathsf\{AtomRewr\}to the predicate𝖲𝗍𝗎𝖽𝖾𝗇𝗍​\(x\)\\mathsf\{Student\}\(x\)with respect to the TBox, we obtain the following rewriting:

𝖲𝗍𝗎𝖽𝖾𝗇𝗍​\(x\)∨∃y​𝖺𝗍𝗍𝖾𝗇𝖽𝗌​\(x,y\)\.\\mathsf\{Student\}\(x\)\\;\\lor\\;\\exists y\\,\\mathsf\{attends\}\(x,y\)\.Intuitively, this rewriting captures the fact that any individual occurring as the first argument of the role𝖺𝗍𝗍𝖾𝗇𝖽𝗌\\mathsf\{attends\}must be an instance of𝖲𝗍𝗎𝖽𝖾𝗇𝗍\\mathsf\{Student\}\.

Similarly, applying𝖠𝗍𝗈𝗆𝖱𝖾𝗐𝗋\\mathsf\{AtomRewr\}to the predicate𝖢𝗈𝗎𝗋𝗌𝖾​\(x\)\\mathsf\{Course\}\(x\)yields the rewriting:

𝖢𝗈𝗎𝗋𝗌𝖾​\(x\)∨∃y​𝖺𝗍𝗍𝖾𝗇𝖽𝗌​\(y,x\),\\mathsf\{Course\}\(x\)\\;\\lor\\;\\exists y\\,\\mathsf\{attends\}\(y,x\),reflecting the fact that individuals occurring as the second argument of𝖺𝗍𝗍𝖾𝗇𝖽𝗌\\mathsf\{attends\}must be instances of𝖢𝗈𝗎𝗋𝗌𝖾\\mathsf\{Course\}\.

Each rewritten atom is then translated into an SQL query and executed on the working database\. The resulting tuples are inserted into the corresponding table, provided that they are not already present\. In this way, the ABox is incrementally saturated with respect to the TBox, while avoiding duplicate facts\. After this step, the database contains a materialized representation of the ABox closure under the TBox\.

###### Example 7

We refer to Example[6](https://arxiv.org/html/2607.16715#Thmexample6)and we consider the following ABox:

𝒜=\{𝖢𝗈𝗎𝗋𝗌𝖾​\(𝖼𝗈𝗎𝗋𝗌𝖾𝖠\),𝖺𝗍𝗍𝖾𝗇𝖽𝗌​\(𝖡𝗈𝖻,𝖼𝗈𝗎𝗋𝗌𝖾𝖠\),𝖲𝗍𝗎𝖽𝖾𝗇𝗍\(𝖠𝗅𝗂𝖼𝖾\)\}\.\\begin\{array\}\[\]\{r@\{\}l\}\\mathcal\{A\}=\\\{&\\mathsf\{Course\}\(\\mathsf\{courseA\}\),\\;\\mathsf\{attends\}\(\\mathsf\{Bob\},\\mathsf\{courseA\}\),\\\\ &\\mathsf\{Student\}\(\\mathsf\{Alice\}\)\\\}\.\\end\{array\}
The rewriting of𝖲𝗍𝗎𝖽𝖾𝗇𝗍​\(x\)\\mathsf\{Student\}\(x\)is translated into the following SQL query, which retrieves all individuals that explicitly occur as instances ofStudentor that can be inferred via the roleattends:

```
SELECT DISTINCT x FROM (
  SELECT attr1 AS x FROM attends
  UNION ALL
  SELECT attr1 AS x FROM student
) AS q0
```

When executed on the working database, this query returns the valuesBobandAlice, identifying the individuals that must be considered as instances of the predicateStudentaccording to the rewriting\.

To materialize these inferred assertions in the ABox, the result of the query is used to construct anINSERTstatement that adds the corresponding tuples to the table associated withStudent, provided that they are not already present\. This is achieved by adding to the query aNOT EXISTScondition, as shown below:

```
INSERT INTO student(attr1)
SELECT DISTINCT x FROM (
  SELECT attr1 AS x FROM attends
  UNION ALL
  SELECT attr1 AS x FROM student
) AS q0
WHERE NOT EXISTS (
  SELECT 1 FROM student t
  WHERE t.attr1 = q0.x
)
```

As a result, only the fact𝖲𝗍𝗎𝖽𝖾𝗇𝗍​\(𝖡𝗈𝖻\)\\mathsf\{Student\}\(\\mathsf\{Bob\}\)is inserted into the ABox during the expansion phase\.

###### Policy expansion\.

The next step of the initialization phase consists in expanding the confidentiality policy with respect to the TBox\. In the implementation, the body of each ED is rewritten with respect to the TBox by exploiting the tree\-witness rewriting algorithm\. For every rewritten version of the body, a new ED is generated by combining the rewritten body with the original head of the dependency\. During this process, the universally quantified variables are aligned with those of the original dependency\. The result of this step is a new expanded policy𝒫′\\mathcal\{P\}^\{\\prime\}that captures all potential policy violations induced by the TBox\.

###### Example 8

Consider the following TBox𝒯\\mathcal\{T\}and policy𝒫\\mathcal\{P\}:

𝒯=\\displaystyle\\mathcal\{T\}=\{B⊑C\},\\displaystyle\\\{\\,B\\sqsubseteq C\\,\\\},𝒫=\\displaystyle\\mathcal\{P\}=\{∀x​\(K​\(C​\(x\)∧A​\(x\)\)→K​D​\(x\)\)\}\.\\displaystyle\\\{\\,\\forall x\\,\(\\mathrm\{K\}\(C\(x\)\\wedge A\(x\)\)\\rightarrow\\mathrm\{K\}D\(x\)\)\\,\\\}\.The policy𝒫′\\mathcal\{P\}^\{\\prime\}obtained after the policy expansion step is the following:

𝒫′=\\displaystyle\\mathcal\{P\}^\{\\prime\}=\{∀x\(K\(C\(x\)∧A\(x\)\)→KD\(x\)\)\\displaystyle\\\{\\,\\forall x\\,\(\\mathrm\{K\}\(C\(x\)\\wedge A\(x\)\)\\rightarrow\\mathrm\{K\}D\(x\)\)∀x\(K\(B\(x\)∧A\(x\)\)→KD\(x\)\)\}\.\\displaystyle\\quad\\forall x\\,\(\\mathrm\{K\}\(B\(x\)\\wedge A\(x\)\)\\rightarrow\\mathrm\{K\}D\(x\)\)\\,\\\}\.

We remark that such a policy expansion step is used to implement the check𝒯∪𝒜⊧𝖻𝗈𝖽𝗒​\(σ​\(τ\)\)\\mathcal\{T\}\\cup\\mathcal\{A\}\\models\\mathsf\{body\}\(\\sigma\(\\tau\)\)done at line[3](https://arxiv.org/html/2607.16715#algorithm3)of Algorithm[3](https://arxiv.org/html/2607.16715#algorithm3)\(see the next paragraph “Further preprocessing steps"\)\.

###### Head expansion\.

As a final step of the initialization phase, also the rewriting of the head of every ED is precomputed, for optimization purposes\.

###### Further preprocessing steps\.

For each ED in the expanded policy, the algorithm constructs a temporary table representing the closure of its body with respect to the initial ABox and the TBox\. This table, calledbodyBase, contains all instantiations of the body that are implied by the ontology \(i\.e\. the homomorphic images described in Section[6](https://arxiv.org/html/2607.16715#S6)\)\. To this end, the body of each EDτ\\tauis compiled into an SQL query, which is executed on the working database, and its result is materialized into the correspondingbodyBasetable\.

###### Example 9

Consider the following ED:

τ:∀x,y\(K\(𝖺𝗍𝗍𝖾𝗇𝖽𝗌\(x,y\)∧𝖢𝗈𝗎𝗋𝗌𝖾\(y\)\)→K𝖲𝗍𝗎𝖽𝖾𝗇𝗍\(x\)\)\.\\tau:\\quad\\forall x,y\\,\\bigl\(\\mathrm\{K\}\\,\(\\mathsf\{attends\}\(x,y\)\\wedge\\mathsf\{Course\}\(y\)\)\\rightarrow\\mathrm\{K\}\\,\\mathsf\{Student\}\(x\)\\bigr\)\.Assume the following TBox:

𝒯=\{∃𝖺𝗍𝗍𝖾𝗇𝖽𝗌⊑𝖲𝗍𝗎𝖽𝖾𝗇𝗍\}\.\\mathcal\{T\}=\\\{\\,\\exists\\,\\mathsf\{attends\}\\sqsubseteq\\mathsf\{Student\}\\,\\\}\.Let the initial ABox be:

𝒜=\{𝖺𝗍𝗍𝖾𝗇𝖽𝗌​\(𝖡𝗈𝖻,𝖼𝗈𝗎𝗋𝗌𝖾𝖠\),𝖢𝗈𝗎𝗋𝗌𝖾​\(𝖼𝗈𝗎𝗋𝗌𝖾𝖠\)\}\.\\mathcal\{A\}=\\\{\\,\\mathsf\{attends\}\(\\mathsf\{Bob\},\\mathsf\{courseA\}\),\\mathsf\{Course\}\(\\mathsf\{courseA\}\)\\,\\\}\.
During the preprocessing step, the body ofτ\\tauis first translated into the formula𝖺𝗍𝗍𝖾𝗇𝖽𝗌​\(𝗑,𝗒\)∧𝖢𝗈𝗎𝗋𝗌𝖾​\(𝗒\)\\mathsf\{attends\(x,y\)\}\\wedge\\mathsf\{Course\(y\)\}that is then compiled into the following SQL query:

```
SELECT x, y
    FROM
      ( SELECT attr1 AS y
        FROM ‘course‘ Course1 ) q0
      NATURAL JOIN
      ( SELECT attr1 AS x, attr2 AS y
        FROM ‘attends‘ attends1 ) q1
```

The evaluation of this query over the working database retrieves all instantiations of the body that are implied by𝒯∪𝒜\\mathcal\{T\}\\cup\\mathcal\{A\}\.

The result of this query is materialized into the temporary tablebodyBase, which in this case contains the tuple\(x=𝖡𝗈𝖻,y=𝖼𝗈𝗎𝗋𝗌𝖾𝖠\)\(x=\\mathsf\{Bob\},\\,y=\\mathsf\{courseA\}\)\.

ThebodyBasetable associated with each EDτ\\tauis computed once during preprocessing, and it is never modified during the iterative censorship process\.

Observe that, for everyσ∈gs​\(τ\)\\sigma\\in\\textit\{gs\}\(\\tau\)and for every subset𝒜′′∈HI​\(𝖻𝗈𝖽𝗒​\(σ​\(τ\)\)\)\\mathcal\{A\}^\{\\prime\\prime\}\\in\\textit\{HI\}\(\\mathsf\{body\}\(\\sigma\(\\tau\)\)\), there exists a corresponding tuple in thebodyBasetable associated with𝖻𝗈𝖽𝗒​\(τ\)\\mathsf\{body\}\(\\tau\)\(and vice versa\)\. Now, the previous policy expansion step guarantees that, for everyτ∈𝒫\\tau\\in\\mathcal\{P\}and for every CQqqsuch thatq∈q′q\\in q^\{\\prime\}whereq′q^\{\\prime\}is the UCQ returned byQRew​\(𝖻𝗈𝖽𝗒​\(τ\),𝒯\)\\textit\{QRew\}\(\\mathsf\{body\}\(\\tau\),\\mathcal\{T\}\), there exists an EDτ′\\tau^\{\\prime\}in the policy expansion of𝒫\\mathcal\{P\}with respect to𝒯\\mathcal\{T\}such thatτ′\\tau^\{\\prime\}is obtained fromτ\\tauby replacing its body withqq\. Therefore, there exists abodyBasetable associated with each suchqq\. Consequently, for everyτ∈𝒫\\tau\\in\\mathcal\{P\}, for everyq∈q′q\\in q^\{\\prime\}, whereq′q^\{\\prime\}is the UCQ returned byQRew​\(𝖻𝗈𝖽𝗒​\(τ\),𝒯\)\\textit\{QRew\}\(\\mathsf\{body\}\(\\tau\),\\mathcal\{T\}\), for everyσ∈gs​\(τ\)\\sigma\\in\\textit\{gs\}\(\\tau\)and for every𝒜′′∈HI​\(σ​\(q\)\)\\mathcal\{A\}^\{\\prime\\prime\}\\in\\textit\{HI\}\(\\sigma\(q\)\), there exists a tuple representing𝒜′′\\mathcal\{A\}^\{\\prime\\prime\}in thebodyBasetable associated withqq\. This guarantees that all the potential MPVs needed to construct the MPV censor are correctly represented in thebodyBasetables\.

##### Iterative phase\.

At a high level, the iterative phase of the \(A\)MPV censor is built as follows:\(i\)\(i\)for each ED, a working temporary table is constructed containing the current instantiations of its body;\(i​i\)\(ii\)tuples that satisfy the head are removed from this table;\(i​i​i\)\(iii\)the remaining tuples correspond to violations and are deleted from the ABox;333For the MPV censor, this step is preceded by the minimality check, which here is not described, and it consists in collecting in Java all the results of the temporary table containing the candidate violations, mutually compare \(w\.r\.t\. set containment\) their representation as sets of facts, and use the minimal sets for the deletion process \(back with SQL\)\.\(i​v\)\(iv\)the process is repeated until a fixpoint is reached\.

We now analyze each algorithm step, highlighting the used data structures and their role in enforcing the policy\.

###### Construction of working body tables\.

At the beginning of each iteration, for every EDτ∈𝒫′\\tau\\in\\mathcal\{P\}^\{\\prime\}, the algorithm constructs a working temporary table, denoted asbodyWork, starting from the correspondingbodyBasetable \(which remains fixed throughout the whole execution\)\. ThebodyWorktable is created as a fresh copy ofbodyBaseand represents the current set of candidate body instantiations that may still lead to a policy violation in the current iteration\.

###### Identification of violating tuples\.

For each EDτ∈𝒫′\\tau\\in\\mathcal\{P\}^\{\\prime\}, the algorithm retrieves the correspondingbodyWorktable and considers the set of CQs obtained from the rewritingQRew​\(𝗁𝖾𝖺𝖽​\(τ\),𝒯\)\\textit\{QRew\}\(\\mathsf\{head\}\(\\tau\),\\mathcal\{T\}\)of its head with respect to the TBox\. Each of such CQs represents a sufficient condition under which the head ofτ\\tauis satisfied\. Operationally, for eachq∈QRew​\(𝗁𝖾𝖺𝖽​\(τ\),𝒯\)q\\in\\textit\{QRew\}\(\\mathsf\{head\}\(\\tau\),\\mathcal\{T\}\), the corresponding SQL query is created and evaluated against the current working ABox\. Specifically, tuples inbodyWorkwhose variable assignments are such that one of such CQs holds in the current ABox are removed from the table, as they do not constitute a policy violation\.

###### Example 10

Consider the TBox𝒯=\{∃𝗁𝖺𝗌𝖠𝗅𝗎𝗆𝗇𝗎𝗌−⊑𝖲𝗍𝗎𝖽𝖾𝗇𝗍\}\\mathcal\{T\}=\\\{\\exists\\mathsf\{hasAlumnus\}^\{\-\}\\sqsubseteq\\mathsf\{Student\}\\\}and the ED

τ0:∀x,y​\(K​\(𝖢𝗈𝗎𝗋𝗌𝖾​\(y\)∧𝖺𝗍𝗍𝖾𝗇𝖽𝗌​\(x,y\)\)→K​𝖲𝗍𝗎𝖽𝖾𝗇𝗍​\(x\)\)\.\\tau\_\{0\}:\\forall x,y\\,\\bigl\(\\mathrm\{K\}\(\\mathsf\{Course\}\(y\)\\wedge\\mathsf\{attends\}\(x,y\)\)\\rightarrow\\mathrm\{K\}\\,\\mathsf\{Student\}\(x\)\\bigr\)\.
In this case, the head ofτ0\\tau\_\{0\}is rewritten into the disjunctive formula𝖲𝗍𝗎𝖽𝖾𝗇𝗍​\(x\)∨∃b​𝗁𝖺𝗌𝖠𝗅𝗎𝗆𝗇𝗎𝗌​\(b,x\)\\mathsf\{Student\}\(x\)\\lor\\exists b\\,\\mathsf\{hasAlumnus\}\(b,x\), which is actually represented as a set:

h​e​a​d​R​e​w=\{𝖲𝗍𝗎𝖽𝖾𝗇𝗍​\(x\),∃b​𝗁𝖺𝗌𝖠𝗅𝗎𝗆𝗇𝗎𝗌​\(b,x\)\}\.headRew=\\bigl\\\{\\mathsf\{Student\}\(x\),\\;\\exists b\\,\\mathsf\{hasAlumnus\}\(b,x\)\\bigr\\\}\.Now consider the following ABox𝒜\\mathcal\{A\}:

𝒜=\{𝖺𝗍𝗍𝖾𝗇𝖽𝗌​\(𝗌𝟣,𝖼𝟣\),𝖢𝗈𝗎𝗋𝗌𝖾​\(𝖼𝟣\),𝖲𝗍𝗎𝖽𝖾𝗇𝗍​\(𝗌𝟣\),𝖺𝗍𝗍𝖾𝗇𝖽𝗌\(𝗌𝟤,𝖼𝟣\)\}\.\\begin\{array\}\[\]\{r@\{\}l\}\\mathcal\{A\}=\\\{&\\mathsf\{attends\}\(\\mathsf\{s1\},\\mathsf\{c1\}\),\\mathsf\{Course\}\(\\mathsf\{c1\}\),\\mathsf\{Student\}\(\\mathsf\{s1\}\),\\\\ &\\mathsf\{attends\}\(\\mathsf\{s2\},\\mathsf\{c1\}\)\\\}\.\\end\{array\}
ThebodyWork\_0table associated withτ0\\tau\_\{0\}has two columns, corresponding to the body variablesxxandyy, and contains the tuples\(x=𝗌𝟣,y=𝖼𝟣\)\(x=\\mathsf\{s1\},\\,y=\\mathsf\{c1\}\)and\(x=𝗌𝟤,y=𝖼𝟣\)\(x=\\mathsf\{s2\},\\,y=\\mathsf\{c1\}\), representing the two instantiations of the body ofτ0\\tau\_\{0\}in the current ABox\.

Since the assertion𝖲𝗍𝗎𝖽𝖾𝗇𝗍​\(𝗌𝟣\)\\mathsf\{Student\}\(\\mathsf\{s1\}\)is entailed by𝒯∪𝒜\\mathcal\{T\}\\cup\\mathcal\{A\}, the first head rewriting𝖲𝗍𝗎𝖽𝖾𝗇𝗍​\(x\)\\mathsf\{Student\}\(x\)is satisfied for the substitutionx=𝗌𝟣x=\\mathsf\{s1\}\. As a consequence, the body instantiation\(x=𝗌𝟣,y=𝖼𝟣\)\(x=\\mathsf\{s1\},\\,y=\\mathsf\{c1\}\)does not constitute a policy violation and must be removed frombodyWork\_0\.

Operationally, this filtering step is implemented by joiningbodyWork\_0with the SQL query corresponding to the head rewritings on the shared variablexx, and deleting all matching tuples\. For instance, the following deletion query removes the satisfied body instantiation:

```
DELETE bodyWork_0
FROM bodyWork_0
JOIN (
  SELECT attr1 AS x FROM student
) AS myAlias
ON bodyWork_0.x = myAlias.x
```

Analogously, the same procedure is applied to the second head rewriting:

```
DELETE bodyWork_0
FROM bodyWork_0
JOIN (
  SELECT attr2 AS x FROM hasalumnus
) AS myAlias
ON bodyWork_0.x = myAlias.x
```

After executing the above queries, the tuple\(x=𝗌𝟤,y=𝖼𝟣\)\(x=\\mathsf\{s2\},\\,y=\\mathsf\{c1\}\)remains inbodyWork\_0, as neither𝖲𝗍𝗎𝖽𝖾𝗇𝗍​\(𝗌𝟤\)\\mathsf\{Student\}\(\\mathsf\{s2\}\)nor𝗁𝖺𝗌𝖠𝗅𝗎𝗆𝗇𝗎𝗌​\(b,𝗌𝟤\)\\mathsf\{hasAlumnus\}\(b,\\mathsf\{s2\}\)can be inferred from the current ABox\.

###### Violating tuples deletion\.

At this point, for each ED, we have an associatedbodyWorktable, whose tuples correspond to body instantiations that violate the ED\.

In this step, we aim to delete the corresponding ground assertions of such violations from our “temporary” ABox\. To do that, for each EDτ∈𝒫′\\tau\\in\\mathcal\{P\}^\{\\prime\}, the algorithm retrieves the associatedbodyWorktable and, for each atom occurring in its body, it constructs a join\-basedDELETEstatement that removes from the corresponding ABox table all tuples whose attribute values match the violating instantiations stored inbodyWork\. The join condition is built by aligning the variables of the body atom with the columns of the ABox table, while constants are handled through equality conditions\.

###### Example 11

We continue Example[10](https://arxiv.org/html/2607.16715#Thmexample10)\. After the identification of violating tuple step, the tablebodyWork\_0contains exactly the body instantiations that violate the EDτ0\\tau\_\{0\}\.

In the violating tuples deletion step, the algorithm removes from the ABox all ground assertions that participate in this violation\. Since the body ofτ0\\tau\_\{0\}consists of the atoms𝖢𝗈𝗎𝗋𝗌𝖾​\(y\)\\mathsf\{Course\}\(y\)and𝖺𝗍𝗍𝖾𝗇𝖽𝗌​\(x,y\)\\mathsf\{attends\}\(x,y\), the algorithm processes each body atom separately\.

For the atom𝖺𝗍𝗍𝖾𝗇𝖽𝗌​\(x,y\)\\mathsf\{attends\}\(x,y\), the followingDELETEstatement is constructed and executed:

```
DELETE attends
FROM attends JOIN bodyWork_0 tmp
   ON tmp.x = attends.attr1
  AND tmp.y = attends.attr2
```

This query removes the violating tuple𝖺𝗍𝗍𝖾𝗇𝖽𝗌​\(𝗌𝟤,𝖼𝟣\)\\mathsf\{attends\}\(\\mathsf\{s2\},\\mathsf\{c1\}\)from the ABox\.

Analogously, for the atom𝖢𝗈𝗎𝗋𝗌𝖾​\(y\)\\mathsf\{Course\}\(y\), the followingDELETEstatement is constructed and executed:

```
DELETE course
FROM course JOIN bodyTemp_1 tmp
ON tmp.y = course.attr1
```

This query removes the violating tuple𝖢𝗈𝗎𝗋𝗌𝖾​\(𝖼𝟣\)\\mathsf\{Course\}\(\\mathsf\{c1\}\)from the ABox\.

After executing these deletions, all ground assertions participating in the policy violation have been removed, and the censored ABox is𝒜=\{𝖺𝗍𝗍𝖾𝗇𝖽𝗌​\(𝗌𝟣,𝖼𝟣\),𝖲𝗍𝗎𝖽𝖾𝗇𝗍​\(𝗌𝟣\)\}\\mathcal\{A\}=\\\{\\mathsf\{attends\(s1,c1\),Student\(s1\)\}\\\}\.

##### Final phase\.

The final phase corresponds to the termination of the iterative censorship process\. The algorithm stops when an iteration completes without performing any further deletions on the working database,444Java APIs return the number of deleted tuples after aDELETEquery\.meaning that a fixpoint has been reached\. At this point, the remaining ABox assertions no longer violate the confidentiality policy under the considered semantics, and the working database corresponds to the \(A\)MPV censor\.

### 0\.A\.2Optimizations

The algorithm for computing the AMPV censor requires several iterations over the ABox and repeated evaluations of EDs\. In order to make the approach scalable to large datasets, we implemented a number of optimizations aimed at reducing redundant computations, simplifying SQL queries, and improving database performance\. One of the main optimizations is constituted by the technique for tuple identification and deletion described above\. Further optimization techniques adopted in our implementation are listed below\.

##### Evaluation of active EDs\.

A first optimization concerns the identification of the EDs that need to be evaluated in the current iteration of the censoring algorithm\. A naive implementation would re\-evaluate all EDs at every iteration, even when no relevant changes have occurred in the underlying ABox, leading to a significant amount of redundant computation\. To avoid this, we introduce the notion of*active EDs*\. At the beginning of the algorithm, all dependenciesτ∈𝒫′\\tau\\in\\mathcal\{P\}^\{\\prime\}are considered active\. During each iteration, in the violating tuples deletion step, we track the body predicates whose corresponding ABox tables are affected by tuple deletions\. Intuitively, only those EDs whose head mentions affected predicates may become newly violated in the next iteration\. At the end of each iteration, the set of affected predicates is used to select only those EDs whose \(expanded\) heads contain at least one affected predicate\. All other dependencies are safely ignored in the next iteration\.

##### Database indexes\.

A further important optimization concerns the interaction with the underlying relational database\. The censoring algorithm repeatedly executes join\-basedDELETEstatements and selection queries over ABox tables\. Without appropriate indexing, these operations require full table scans, which become too expensive as the size of the data grows\. To mitigate this issue, we automatically create indexes on all columns of the cloned database tables before executing the censoring procedure\. Indexes allow the database engine to quickly locate tuples matching join conditions or selection predicates, thereby reducing the cost of query execution\. Although index creation introduces a small overhead in the initialization phase, this cost is amortized over the many SQL operations performed\.

### 0\.A\.3Experiments

In this section, we present more details about the experimental evaluation of our implementation of the proposed framework\. In particular, we analyze the scalability of the AMPV censor with respect to the size of the ABox, analyze its iterative behavior, assess the impact of the design choices and optimizations discussed in the previous sections, and evaluate the cost of query answering over the censored ABox\.

All experiments are conducted by varying the size of the ABox while keeping the TBox and the policy fixed\.

#### 0\.A\.3\.1Experimental setup

All experiments were conducted on a laptop with an Intel Core i7\-7700HQ processor running at 2\.80 GHz and 8 GB of RAM\. The implementation is written in Java 11 and relies on MySQL 8\.0 for storing and manipulating the ABox\.

##### Knowledge base\.

We rely on the OWL2Bench benchmark for OWL ontologies\[[16](https://arxiv.org/html/2607.16715#bib.bib3)\]\(∼\\sim140 classes and∼\\sim890 object properties, respectively concept and roles\), which models a university domain and provides a data generator for producing ABoxes of customizable size\. In particular, we consider ABoxes generated withN=1,5,10,20,25,N=1,5,10,20,25,and5050universities\. AsNNincreases, the size of the ABox grows accordingly, allowing us to evaluate the scalability of the censoring algorithm with respect to the number of assertions\. Table[1](https://arxiv.org/html/2607.16715#S6.T1)reports the size of the ABoxes used in the experiments, both before and after expansion with respect to the TBox\.

##### Policy\.

The policy used in the experimental evaluation consists of a fixed set of 11 EDs\. The complete list of EDs used in the experiments is reported in Appendix[0\.C](https://arxiv.org/html/2607.16715#Pt0.A3)\. The dependencies are arbitrary and capture heterogeneous structural patterns \(e\.g\., linear and non\-linear EDs\), interdependent violations requiring multiple iterations of the censoring algorithm, and non\-trivial interactions with the data\. They are semantically meaningful in the OWL2Bench university domain and are not trivially entailed by the TBox\. After expansion with respect to the TBox, the policy results in a total of 153 EDs\.

##### Queries\.

For the query answering evaluation, we rely on the OWL2Bench QL benchmark query set, consisting of ten SPARQL queries \(reported in Appendix[0\.B](https://arxiv.org/html/2607.16715#Pt0.A2)\), fixed across all experimental configurations\. For each dataset sizeN∈\{1,5,10,20,25,50\}N\\in\\\{1,5,10,20,25,50\\\}, queries are evaluated over the censored ABox produced by the \(A\)MPV censor\. Each query is first rewritten with respect to the TBox using the tree\-witness rewriting technique, and the resulting SQL query is then executed over the relational database storing the censored ABox\.

Dataset size \(N\)MPVAMPV15101510202550Initialization phaseABox cloning12\.4133\.226\.39\.629\.833\.943\.733\.059\.0Schema extraction0\.60\.90\.60\.60\.80\.60\.60\.70\.6Index creation8\.017\.214\.98\.512\.314\.849\.739\.597\.3ABox expansion3\.913\.824\.54\.012\.526\.964\.372\.8167\.2Policy expansion0\.20\.10\.20\.20\.30\.20\.20\.10\.2Auxiliary data structures2\.05\.611\.42\.08\.710\.021\.126\.861\.9Iterative phaseViolations identification1\.47\.214\.31\.57\.714\.932\.440\.991\.5Minimality check46\.12359\.110428\.9––––––Violations deletion4\.525\.784\.41\.47\.020\.856\.466\.6155\.1Final phase1\.65\.516\.11\.38\.214\.626\.725\.356\.3Total execution time80\.72568\.310621\.629\.184\.3136\.7295\.1305\.7689\.1Table 3:Execution time breakdown of the \(A\)MPV censor for increasing dataset sizes, reporting both the initialization and iterative phases\. Times are reported in seconds\.Dataset size \(N\)MPVAMPVIteration151015102025501tet\_\{e\}13\.0497\.92438\.81\.57\.420\.052\.662\.2143\.7\#a9487571061201631075265678138570278145334897700465\#e​d​s\\\#\_\{eds\}1381381381381381381381381382tet\_\{e\}30\.71481\.36340\.11\.15\.310\.928\.134\.876\.4\#a3880254225322838802542253228105799127450259660\#e​d​s\\\#\_\{eds\}6767676767676767673tet\_\{e\}8\.4412\.81748\.80\.31\.94\.77\.910\.426\.4\#a000000000\#e​d​s\\\#\_\{eds\}000000000Table 4:Execution time \(tet\_\{e\}, in seconds\), number of deleted ABox assertions \(\#a\) and number of active EDs \(\#e​d​s\\\#\_\{eds\}\) activated at the end of each iteration of the \(A\)MPV censor algorithm for different dataset sizes\.

#### 0\.A\.3\.2Results

We first provide a comparison between the AMPV and MPV algorithms, and then we provide a more detailed analysis of the AMPV censor\. The analysis focuses on both the scalability of the approach and the iterative behavior of the censoring algorithm, with particular attention to factors that influence execution time and convergence\.

##### AMPV\-MPV comparison\.

For both AMPV and MPV censor, Table[3](https://arxiv.org/html/2607.16715#Pt0.A1.T3)provides a breakdown of the total execution time across the main phases of the algorithm used for computing them\. A more fine\-grained view of the iterative process is given in Table[4](https://arxiv.org/html/2607.16715#Pt0.A1.T4), which reports, for each iteration and dataset size, the execution time and the number of deleted ABox assertions\. This allows us to analyze how the workload and deletion activity evolve across iterations and how they contribute to the overall convergence of the algorithm\.

##### Execution time\.

We now analyze the overall execution time and then provide a more detailed analysis by breaking it down into its main phases and internal components\.

![Refer to caption](https://arxiv.org/html/2607.16715v1/x1.png)Figure 1:Execution time of the AMPV censor for increasing values ofNN\. Each value ofNNcorresponds to an ABox of increasing size, as reported in Table[1](https://arxiv.org/html/2607.16715#S6.T1)\.Figure[1](https://arxiv.org/html/2607.16715#Pt0.A1.F1)reports the total time required to compute the AMPV censor as a function of the ABox size\. Interestingly, when compared with the growth of the expanded ABox size \(see Table[1](https://arxiv.org/html/2607.16715#S6.T1)\), the execution time exhibits a smooth and roughly proportional increase, suggesting stable scaling behavior across the considered dataset sizes\.

To better understand the factors contributing to the overall execution time, we next analyze how the cost is distributed between the initialization phase and the iterative censorship phase, and we further investigate the internal breakdown of each phase\.

![Refer to caption](https://arxiv.org/html/2607.16715v1/x2.png)Figure 2:Execution time breakdown of the AMPV censor into initialization and iterative phases for different dataset sizes\.###### Initialization vs\. iterative phase\.

Figure[2](https://arxiv.org/html/2607.16715#Pt0.A1.F2)reports the execution time of the AMPV censor by separating the initialization phase from the iterative censorship phase\. The initialization phase includes all preprocessing steps performed once before the fixpoint computation: database cloning, schema extraction, index creation, ABox and policy expansion, head expansion, and creation of temporary tables\. The iterative phase corresponds to the repeated identification and deletion of tuples violating the confidentiality policy until a fixpoint is reached\. As shown in the figure, for all dataset sizes, the initialization phase represents the dominant component of the overall execution time\. Although the cost of the iterative phase grows with the size of the input ABox, it remains consistently lower than that of the initialization phase\.

![Refer to caption](https://arxiv.org/html/2607.16715v1/x3.png)Figure 3:Execution time breakdown of the initialization phase of the AMPV censor for different dataset sizes\.
###### Initialization phase breakdown\.

Figure[3](https://arxiv.org/html/2607.16715#Pt0.A1.F3)reports the execution time of the initialization phase of the AMPV censor, broken down into its main components\. The initialization phase of the AMPV censor algorithm is composed of several steps, including ABox cloning, schema extraction, index creation, ABox and policy expansion, and a step devoted to the materialization of auxiliary data structures\. This latter step comprises head expansion and splitting, body atom explosion, and the creation of temporary tables that are later used during the iterative censorship phase\. The results show that the initialization cost is mainly dominated by ABox cloning, ABox expansion, index creation, and auxiliary data structure materialization\. In contrast, schema extraction and policy expansion contribute only marginally to the overall initialization time\.

![Refer to caption](https://arxiv.org/html/2607.16715v1/x4.png)Figure 4:Execution time breakdown of the iterative phase of the AMPV censor into the*violating tuple identification*and*violating tuple deletion*steps for different dataset sizes\.
###### Iterative phase breakdown\.

Figure[4](https://arxiv.org/html/2607.16715#Pt0.A1.F4)shows the execution time of the iterative phase of the AMPV censor, separated into the*violating tuples identification*and*violating tuples deletion*steps, for increasing dataset sizes\. The results indicate that for small datasets \(N=1 and N=5\), the two steps exhibit comparable execution times\. However, as the dataset size increases, the deletion step progressively dominates the overall cost of the iterative phase, while the identification step contributes to a smaller but non\-negligible portion of the total execution time\.

![Refer to caption](https://arxiv.org/html/2607.16715v1/x5.png)Figure 5:Execution time of each iteration of the iterative phase of the AMPV censor forN=50N=50\. The last iteration corresponds to the fixpoint check and does not perform any deletions\.
###### Cost per iteration\.

Figure[5](https://arxiv.org/html/2607.16715#Pt0.A1.F5)reports the execution time of each iteration of the iterative phase for the largest dataset \(N=50N=50\)\. While the first iterations account for most of the computational effort, the final iteration performs no deletions and only serves to detect the fixpoint of the process, thus incurring in a negligible cost\. The same behavior is observed for all other dataset sizes, where the first iteration consistently represents the most expensive one\.

##### Iterative behavior\.

In all the experimental configurations, the algorithm converges after a small and constant number of iterations, exactly three, independently of the size of the input ABox\. This behavior suggests that, in our experiments, convergence is primarily driven by the structure of the policy and by the dependencies among violations, rather than by the amount of data\. As a consequence, increasing the size of the ABox mainly affects the cost of each iteration, but not the total number of iterations required to reach the fixpoint\.

![Refer to caption](https://arxiv.org/html/2607.16715v1/x6.png)Figure 6:Number of ABox assertions deleted at each iteration of the AMPV censor for the largest dataset considered \(N=50N=50\)\.
##### Tuple deletions across iterations\.

Figure[6](https://arxiv.org/html/2607.16715#Pt0.A1.F6)reports the number of ABox assertions deleted at each iteration for the largest dataset considered \(N=50N=50\)\. Across all experimental configurations, a clear decreasing trend can be observed: the largest number of deletions occurs during the first iteration, and the number progressively decreases in subsequent iterations until the algorithm reaches a fixpoint\. This behavior reflects the dynamics of the censoring process\. Indeed, in our experiments, during the first iteration, the number of detected violations—and consequently the number of deletions—is maximal\. After this substantial clean\-up step, the ABox is already significantly reduced, and fewer violations remain to be addressed\. As a result, subsequent iterations involve progressively fewer deletions\. The decreasing number of removed assertions indicates that the algorithm is converging\. Eventually, no further violations are produced, and a fixpoint is reached\.

![Refer to caption](https://arxiv.org/html/2607.16715v1/x7.png)Figure 7:Number of active EDs at the start of each iteration of the AMPV censor for the largest dataset considered \(N=50N=50\)\. The red point represents the fixpoint reached at the end of the fifth iteration\.
##### Reduction of active EDs\.

Figure[7](https://arxiv.org/html/2607.16715#Pt0.A1.F7)reports the number of EDs that remain active at each iteration of the AMPV censor for the largest dataset considered\. The number of active dependencies decreases sharply across iterations, dropping from 153 in the first iteration to zero at convergence\. This behavior confirms the effectiveness of the optimization based on active EDs, which avoids re\-evaluating dependencies that cannot be affected by recent tuple deletions\. As a result, later iterations are significantly lighter than the initial ones, contributing to the overall scalability of the approach\.

##### Scalability considerations\.

When normalizing the execution time by the size of the final censored ABox, the average cost per retained tuple remains approximately stable across dataset sizes\. Formally, for each dataset sizeNN, we compute the average cost per tuple as follows:

Ttotal\|𝒜final\|,\\frac\{T\_\{\\text\{total\}\}\}\{\|\\mathcal\{A\}\_\{\\text\{final\}\}\|\},whereTtotalT\_\{\\text\{total\}\}denotes the total execution time of the censoring algorithm, measured in seconds, and\|𝒜final\|\|\\mathcal\{A\}\_\{\\text\{final\}\}\|is the number of ABox assertions remaining after the censorship process\. For presentation purposes, the resulting values are reported in milliseconds per tuple and summarized in Table[5](https://arxiv.org/html/2607.16715#Pt0.A1.T5)\.

NN\|𝒜final\|\|\\mathcal\{A\}\_\{\\text\{final\}\}\|ms/tuple175 0540\.385504 0360\.16101 113 4880\.12202 153 6700\.13252 677 0380\.11505 450 9410\.12Table 5:Average execution time per retained ABox tuple and size of the final censored ABox for increasing dataset sizes\.In particular, forN≥5N\\geq 5, the execution time ranges between0\.110\.11and0\.160\.16milliseconds per retained tuple\. This observation indicates that the increase in total runtime observed in the previous experiments is primarily explained by the growth of the processed data, rather than by a degradation in the efficiency of the censoring algorithm\. The higher normalized value observed forN=1N=1can be explained by the relative impact of fixed overhead costs \(database cloning, schema extraction, index creation, policy preprocessing, and the initialization of auxiliary data structures\)\. Although the initialization phase dominates the execution time across all dataset sizes, its cost does not grow proportionally with the size of the final censored ABox\. For small datasets, these fixed costs are amortized over a relatively small number of retained tuples, leading to a higher average cost per tuple\. As the dataset size increases, the number of retained assertions grows significantly, while the initialization overhead increases only moderately\. Consequently, when normalizing the execution time by\|𝒜final\|\|\\mathcal\{A\}\_\{\\text\{final\}\}\|, the fixed costs are distributed over a much larger number of tuples, and the average cost per tuple stabilizes\.

#### 0\.A\.3\.3Query answering results

In this section, we report the results of the experimental evaluation of query answering over the censored ABoxes produced by the AMPV censor\. The analysis focuses on the scalability of query answering and on the impact of confidentiality enforcement on query execution performance, by investigating how query execution time and the number of returned answers evolve as the size of the censored ABox increases\. Table[2](https://arxiv.org/html/2607.16715#S6.T2)summarizes the average execution times and the number of returned answers for each query and each dataset size\. These tables provide a quantitative overview that complements the graphical analysis presented in the following paragraphs\.

![Refer to caption](https://arxiv.org/html/2607.16715v1/x8.png)Figure 8:Number of returned answers for the benchmark queries with non\-empty result sets as a function of the dataset sizeNN\. A logarithmic scale on the y\-axis is adopted to clearly visualize the different growth rates, since the result sizes vary significantly across queries\.##### Execution time\.

All query execution times are measured after a short warm\-up phase\. For each query and each dataset size, one initial execution is performed and discarded, in order to mitigate the effects of caching, query compilation, and JVM warm\-up\. Subsequently, each query is executed three times over the same censored ABox, and the reported execution time corresponds to the average of these runs\. This methodology allows us to obtain more stable and representative measurements of query answering performance\.

Overall, the results show that query answering remains efficient and scalable across all dataset sizes considered\. For most queries, the execution time increases smoothly with the size of the censored ABox, reflecting the growth in the number of relevant tuples to be processed during query evaluation\. Even for the largest dataset \(N=50N=50\), query execution times remain within a few seconds, confirming that confidentiality enforcement through the AMPV censor does not introduce prohibitive overhead at query time\. A closer inspection reveals that the execution cost strongly depends on the structure of the query and on the cardinality of its result set\. Queries returning a large number of answers \(i\.e\. queries 1, 2, 7, 8, 9 and 10\) exhibit higher execution times\. In contrast, queries with limited or empty result sets \(i\.e\. queries 4 and 6\) are evaluated very efficiently, often requiring less than one millisecond even for the largest ABoxes\. These observations indicate that the dominant factor influencing query execution time is the size of the intermediate and final results, rather than the presence of censorship\.

![Refer to caption](https://arxiv.org/html/2607.16715v1/x9.png)Figure 9:Relationship between the number of returned answers and the average execution time of the benchmark queries\. Both axes are shown on a logarithmic scale\.
##### Returned answers\.

We analyze the number of answers returned by each query as the size of the censored ABox increases\. Figure[8](https://arxiv.org/html/2607.16715#Pt0.A1.F8)reports the results for the benchmark queries with non\-empty result set, as a function of the dataset size\. queries 1, 2, 7, 8, 9, and 10 return large result sets whose cardinality grows steadily withNN\. In particular, query 2 yields the largest number of answers, exceeding220,000220\{,\}000forN=50N=50\. This behavior reflects the presence of highly populated and strongly interconnected relations in the benchmark data\. Overall, query answering over censored ABoxes exhibits the same scaling trend as standard ontology\-based query answering\. queries 3 and 5 produce moderate result sets that increase monotonically withNN, but remain comparatively small due to their more restrictive patterns\. In contrast, queries 4 and 6 return no answers for any dataset size, as a consequence of the interaction between ontology semantics, data distribution, and the enforced confidentiality policy\.

##### Relation between execution time and returned answers\.

To further investigate the factors underlying the observed execution times, we analyze the relationship between query execution time and the number of returned answers\. Figure[9](https://arxiv.org/html/2607.16715#Pt0.A1.F9)reports the average execution time of the benchmark queries as a function of the size of their result sets\.

The scatter plot highlights a clear positive relationship between the two quantities: queries returning a larger number of answers tend to require longer execution times, whereas queries with empty or very small result sets are evaluated efficiently\. In particular, no queries with a small number of returned answers exhibit high execution times, nor do queries with large result sets achieve very low execution times\.

## Appendix 0\.BBenchmark queries

We report in Figure[10](https://arxiv.org/html/2607.16715#Pt0.A2.F10)the complete set of SPARQL queries for OWL 2 QL used in the query answering evaluation, as provided by the OWL2Bench benchmark for OWL ontologies\[[16](https://arxiv.org/html/2607.16715#bib.bib3)\]\.

q1:SELECT DISTINCT ?x ?yWHERE \{?x :knows ?y\}q2:SELECT DISTINCT ?x ?yWHERE \{?x :hasAlumnus ?y\}q3:SELECT DISTINCT ?x ?yWHERE \{?x :isAffiliatedOrganizationOf ?y\}q4:SELECT DISTINCT ?xWHERE \{?x :hasCollegeDiscipline :NonScience\}q5:SELECT DISTINCT ?x ?yWHERE \{?x :hasCollaborationWith ?y\}q6:SELECT DISTINCT ?x ?yWHERE \{?x :isAdvisedBy ?y\}q7:SELECT DISTINCT ?xWHERE \{?x rdf:type :Faculty\}q8:SELECT DISTINCT ?x ?yWHERE \{?x :hasSameHomeTownWith ?y\}q9:SELECT DISTINCT ?x ?yWHERE \{?x rdf:type :Student\.?x :isStudentOf ?y\.?y :isPartOf ?z\.?z :hasCollegeDiscipline :Engineering\}q10:SELECT DISTINCT ?s ?cWHERE \{?s rdf:type :Student\.?x rdf:type :Organization\.?x :hasDean ?z\.?z :teachesCourse ?c\.?s :takesCourse ?c\}Figure 10:The 10 queries for OWL 2 QL from the OWL2Bench benchmark\.
## Appendix 0\.CExperimental policy

Figure[11](https://arxiv.org/html/2607.16715#Pt0.A3.F11)presents the full set of EDs used in the experimental evaluation\. For the sake of readability, in these EDs we omit the universal quantification of the variables that are not existentially quantified\.

τ1:K​\(𝗄𝗇𝗈𝗐𝗌​\(x,y\)∧𝖶𝗈𝗆𝖺𝗇​\(x\)\)→K​∃z​\(𝗁𝖺𝗌𝖲𝖺𝗆𝖾𝖧𝗈𝗆𝖾𝖳𝗈𝗐𝗇𝖶𝗂𝗍𝗁​\(x,y\)∧𝗁𝖺𝗌𝖣𝗈𝖼𝗍𝗈𝗋𝖺𝗅𝖣𝖾𝗀𝗋𝖾𝖾𝖥𝗋𝗈𝗆​\(x,z\)\)τ2:K​\(𝗁𝖺𝗌𝖲𝖺𝗆𝖾𝖧𝗈𝗆𝖾𝖳𝗈𝗐𝗇𝖶𝗂𝗍𝗁​\(x,y\)∧𝖶𝗈𝗆𝖺𝗇​\(x\)\)→K​\(𝗁𝖺𝗌𝖢𝗈𝗅𝗅𝖺𝖻𝗈𝗋𝖺𝗍𝗂𝗈𝗇𝖶𝗂𝗍𝗁​\(x,y\)∧𝗄𝗇𝗈𝗐𝗌​\(x,y\)\)τ3:K​𝖶𝗈𝗆𝖺𝗇​\(x\)→K​∃y,z​\(𝗄𝗇𝗈𝗐𝗌​\(x,y\)∧𝗁𝖺𝗌𝖬𝖺𝗌𝗍𝖾𝗋𝖣𝖾𝗀𝗋𝖾𝖾𝖥𝗋𝗈𝗆​\(x,z\)\)τ4:K\(𝖲𝖼𝗂𝖾𝗇𝖼𝖾𝖲𝗍𝗎𝖽𝖾𝗇𝗍\(x\)∧𝗁𝖺𝗌𝖠𝖽𝗏𝗂𝗌𝗈𝗋\(x,y\)\)→K∃z\(𝖯𝗋𝗈𝖿𝖾𝗌𝗌𝗈𝗋\(y\)\)∧𝗁𝖺𝗌𝖬𝖺𝗌𝗍𝖾𝗋𝖣𝖾𝗀𝗋𝖾𝖾𝖥𝗋𝗈𝗆\(y,z\)\)τ5:K​∃y​𝗂𝗌𝖠𝖽𝗏𝗂𝗌𝖾𝖽𝖡𝗒​\(x,y\)→K​𝖶𝗈𝗆𝖺𝗇​\(x\)τ6:K​∃y​\(𝗁𝖺𝗌𝖢𝗈𝗅𝗅𝖺𝖻𝗈𝗋𝖺𝗍𝗂𝗈𝗇𝖶𝗂𝗍𝗁​\(x,y\)∧𝖯𝗋𝗈𝖿𝖾𝗌𝗌𝗈𝗋​\(x\)\)→K​∃z​𝗁𝖺𝗌𝖠𝖽𝗏𝗂𝗌𝗈𝗋​\(z,x\)τ7:K​∃d​\(𝗂𝗌𝖯𝖺𝗋𝗍𝖮𝖿​\(x,z\)∧𝗁𝖺𝗌𝖢𝗈𝗅𝗅𝖾𝗀𝖾𝖣𝗂𝗌𝖼𝗂𝗉𝗅𝗂𝗇𝖾​\(z,d\)\)→K​∃p​𝗁𝖺𝗌𝖯𝗋𝗈𝗀𝗋𝖺𝗆​\(x,p\)τ8:K​\(𝖥𝗎𝗅𝗅𝖯𝗋𝗈𝖿𝖾𝗌𝗌𝗈𝗋​\(y\)∧𝗂𝗌𝖠𝖽𝗏𝗂𝗌𝖾𝖽𝖡𝗒​\(x,y\)\)→K​∃z​𝗍𝖾𝖺𝖼𝗁𝖾𝗌𝖢𝗈𝗎𝗋𝗌𝖾​\(y,z\)τ9:K​𝗂𝗌𝖠𝖿𝖿𝗂𝗅𝗂𝖺𝗍𝖾𝖽𝖮𝗋𝗀𝖺𝗇𝗂𝗓𝖺𝗍𝗂𝗈𝗇𝖮𝖿​\(x,y\)→K​𝗁𝖺𝗌𝖢𝗈𝗅𝗅𝖾𝗀𝖾𝖣𝗂𝗌𝖼𝗂𝗉𝗅𝗂𝗇𝖾​\(x,S​c​i​e​n​c​e\)τ10:K​∃y,u​\(𝗍𝖾𝖺𝖼𝗁𝖾𝗌𝖢𝗈𝗎𝗋𝗌𝖾​\(x,y\)∧𝗁𝖺𝗌𝖬𝖺𝗌𝗍𝖾𝗋𝖣𝖾𝗀𝗋𝖾𝖾𝖥𝗋𝗈𝗆​\(x,u\)\)→K​∃v​𝗁𝖺𝗌𝖣𝗈𝖼𝗍𝗈𝗋𝖺𝗅𝖣𝖾𝗀𝗋𝖾𝖾𝖥𝗋𝗈𝗆​\(x,v\)τ11:K​∃y​\(𝖥𝖺𝖼𝗎𝗅𝗍𝗒​\(x\)∧𝗁𝖺𝗌𝖢𝗈𝗅𝗅𝖺𝖻𝗈𝗋𝖺𝗍𝗂𝗈𝗇𝖶𝗂𝗍𝗁​\(x,y\)\)→K​𝖶𝗈𝗆𝖺𝗇​\(x\)\\begin\{array\}\[\]\{r@\{\\;\}l\}\\tau\_\{1\}:&\\mathrm\{K\}\\,\(\\mathsf\{knows\}\(x,y\)\\wedge\\mathsf\{Woman\}\(x\)\)\\rightarrow\\mathrm\{K\}\\,\\exists z\\,\(\\mathsf\{hasSameHomeTownWith\}\(x,y\)\\wedge\\,\\mathsf\{hasDoctoralDegreeFrom\}\(x,z\)\)\\\\\[2\.84526pt\] \\tau\_\{2\}:&\\mathrm\{K\}\\,\(\\mathsf\{hasSameHomeTownWith\}\(x,y\)\\wedge\\mathsf\{Woman\}\(x\)\)\\rightarrow\\mathrm\{K\}\\,\(\\mathsf\{hasCollaborationWith\}\(x,y\)\\wedge\\mathsf\{knows\}\(x,y\)\)\\\\\[2\.84526pt\] \\tau\_\{3\}:&\\mathrm\{K\}\\,\\mathsf\{Woman\}\(x\)\\rightarrow\\mathrm\{K\}\\,\\exists y,z\\,\(\\mathsf\{knows\}\(x,y\)\\wedge\\,\\mathsf\{hasMasterDegreeFrom\}\(x,z\)\)\\\\\[2\.84526pt\] \\tau\_\{4\}:&\\mathrm\{K\}\(\\mathsf\{ScienceStudent\}\(x\)\\wedge\\mathsf\{hasAdvisor\}\(x,y\)\)\\rightarrow\\mathrm\{K\}\\,\\exists z\\,\(\\mathsf\{Professor\}\(y\)\)\\wedge\\,\\mathsf\{hasMasterDegreeFrom\}\(y,z\)\)\\\\\[2\.84526pt\] \\tau\_\{5\}:&\\mathrm\{K\}\\,\\exists y\\,\\mathsf\{isAdvisedBy\}\(x,y\)\\rightarrow\\mathrm\{K\}\\,\\mathsf\{Woman\}\(x\)\\\\\[2\.84526pt\] \\tau\_\{6\}:&\\mathrm\{K\}\\,\\exists y\\,\(\\mathsf\{hasCollaborationWith\}\(x,y\)\\wedge\\mathsf\{Professor\}\(x\)\)\\rightarrow\\mathrm\{K\}\\,\\exists z\\,\\mathsf\{hasAdvisor\}\(z,x\)\\\\\[2\.84526pt\] \\tau\_\{7\}:&\\mathrm\{K\}\\,\\exists d\\,\(\\mathsf\{isPartOf\}\(x,z\)\\wedge\\mathsf\{hasCollegeDiscipline\}\(z,d\)\)\\rightarrow\\mathrm\{K\}\\,\\exists p\\,\\mathsf\{hasProgram\}\(x,p\)\\\\\[2\.84526pt\] \\tau\_\{8\}:&\\mathrm\{K\}\\,\(\\mathsf\{FullProfessor\}\(y\)\\wedge\\mathsf\{isAdvisedBy\}\(x,y\)\)\\rightarrow\\mathrm\{K\}\\,\\exists z\\,\\mathsf\{teachesCourse\}\(y,z\)\\\\\[2\.84526pt\] \\tau\_\{9\}:&\\mathrm\{K\}\\,\\mathsf\{isAffiliatedOrganizationOf\}\(x,y\)\\rightarrow\\mathrm\{K\}\\,\\mathsf\{hasCollegeDiscipline\}\(x,Science\)\\\\\[2\.84526pt\] \\tau\_\{10\}:&\\mathrm\{K\}\\,\\exists y,u\\,\(\\mathsf\{teachesCourse\}\(x,y\)\\wedge\\,\\mathsf\{hasMasterDegreeFrom\}\(x,u\)\)\\rightarrow\\mathrm\{K\}\\,\\exists v\\,\\mathsf\{hasDoctoralDegreeFrom\}\(x,v\)\\\\\[2\.84526pt\] \\tau\_\{11\}:&\\mathrm\{K\}\\,\\exists y\\,\(\\mathsf\{Faculty\}\(x\)\\wedge\\mathsf\{hasCollaborationWith\}\(x,y\)\)\\rightarrow\\mathrm\{K\}\\,\\mathsf\{Woman\}\(x\)\\\\\[2\.84526pt\] \\end\{array\}Figure 11:The 11 EDs used for our experiments\.