DL本体中基于认知保密策略的可处理查询回答（扩展版）

# DL本体中认知机密性策略下的可处理查询回答（扩展版）  
来源：https://arxiv.org/html/2607.16715  

11institutetext:罗马萨皮恩扎大学，意大利  
11email:\{marconi,rosati\}@diag\.uniroma1\.it  
11email:rieti\.1762973@studenti\.uniroma1\.it  

###### 摘要  
我们在描述逻辑（DL）本体背景下研究受控查询评估（CQE）——一种声明式的保密数据访问方法，并针对通过认知依赖（EDs）表达的机密性策略。我们首先解决在CQE已知语义（GA-和IGA-蕴含）下回答查询（特别地，布尔合取查询的并集）的问题。我们的结果表明，如果TBox以DL-Lite_R表达，则CQE通常计算上难以处理。此外，在EDs存在的情况下，IGA语义最近被证明不满足一个重要的保密保存属性，即*不可区分性*。为了定义计算上更简单且保密性更强的CQE形式，我们引入了一种基于*最小策略违反*（MPV）概念的新CQE语义。我们表明新语义提供了先前语义的可靠近似，同时满足不可区分性属性。我们还证明，在DL-Lite_R本体的情况下，基于MPV语义的查询蕴含可以在数据复杂度上以多项式时间判定。最后，我们展示了我们框架的一个软件实现，并使用现有OWL 2 QL基准测试评估了这种新方法的可行性。  

## 1 引言  
我们研究*受控查询评估*（CQE）[12 (https://arxiv.org/html/2607.16715#bib.bib15),2 (https://arxiv.org/html/2607.16715#bib.bib36)]，这是一个逻辑框架，旨在允许回答对数据库或知识库的查询，同时隐藏被视为敏感的知识片段。近年来，关于CQE的几项工作集中在描述逻辑本体上[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)]，这是我们在这里考虑的背景。特别地，我们关注其意图部分用DL-Lite_R[6 (https://arxiv.org/html/2607.16715#bib.bib98)]表达的本体，该逻辑支撑OWL 2 QL配置文件[14 (https://arxiv.org/html/2607.16715#bib.bib111)]。在CQE中，要保护的信息使用逻辑公式指定，这些公式收集在所谓的*策略*中。在文献中，策略通常通过*拒绝断言*来表达，即形式为q→⊥的逻辑句子，其中q是布尔合取查询（BCQ）。直观上，此类断言旨在防止最终用户即使通过无限序列的查询间接地获知q。最近的工作[8 (https://arxiv.org/html/2607.16715#bib.bib99)]提出了使用*认知依赖*（EDs）来增强数据保护策略的表达能力。ED是一个形式为∀x→\(Kqb→Kqh\)的逻辑公式，其中qb和qh都是（可能开放的）CQs，其自由变量出现在x→中，K表示一个认知算子。直观上，对于x→中变量的每个实例化，这样的公式防止用户推断出qb，除非也能推断出qh。在CQE中，用于表示可披露信息的关键概念称为*审查器*。审查器是一组逻辑句子，即使与TBox提供的意向知识结合，也不能用于推断敏感信息。这样的句子可以用不同的形式表示，如BCQs的语言（如前述工作[8 (https://arxiv.org/html/2607.16715#bib.bib99)]所述）或基原子。特别地，由基原子组成的审查器（也称为*GA审查器*）提供了可披露信息的自然表示，因为它们可以被视为ABox。当GA审查器相对于集合包含是最大的时，它们被称为*最优*的。  

###### 示例 1  
一家医院不希望披露未成年人（M）患有（affBy）某种疾病的事实。此外，只有在父母同意（pConsFor）的情况下才能披露某人是未成年人。最后，亲子关系（parOf）只有在是生物学关系（bioParOf）时才允许披露。考虑一个由三个ED组成的策略P，分别编码上述保护规则：  
∀x,y \(K(M(x)∧affBy(x,y))→⊥\)  
∀x \(KM(x)→K∃y pConsFor(y,x)\)  
∀x,y \(KparOf(y,x)→KbioParOf(y,x)\)  
意向知识通过DL TBox T提供，该TBox允许推断，如果个体x给予了y的父母同意，那么x是y的父母（pConsFor⊑parOf），并且如果x受y的影响，那么y是一种疾病（∃affBy−⊑Dis）。最后，基础数据包含在DL ABox A中，其中包含事实：ann是未成年人，她患有疾病d，并且bob同意披露ann是未成年人：  
A={M(ann), affBy(ann,d), pConsFor(bob,ann)}。注意，事实parOf(bob,ann)和Dis(d)也是T∪A的逻辑推论。由于不能披露bob是ann的生物学父母这一事实（因为本体不能推导出它），因此也必须保密pConsFor(bob,ann)（它通过T隐含parOf(bob,ann)）；同样，这适用于M(ann)。在这种情况下，我们只有一个最优的GA审查器，即{affBy(ann,d), Dis(d)}，包含唯一可以披露的两个事实。相反，考虑一个只包含第一个ED的策略P'，则会存在两个最优GA审查器，分别由除M(ann)和affBy(ann,d)之外的本体逻辑推论的所有事实组成。  

论文[13 (https://arxiv.org/html/2607.16715#bib.bib108)]研究了ED存在下GA审查器的性质，以及在所谓的*GA-*和*IGA-蕴含*语义下布尔合取查询并集（BUCQs）的蕴含复杂度，我们也将其作为分析的基线。前者包括检查每个最优GA审查器与给定TBox一起是否逻辑上蕴含输入查询；后者则检查查询是否由TBox和所有最优GA审查器的交集蕴含。该论文聚焦于DL-Lite_R本体和EDs的不同子类（即线性、全依赖和非循环依赖）的（组合），展示了IGA蕴含的良好计算性质（在EDs是线性-全或非循环-全的情况下），但缺乏以一般形式提供的EDs的全部表达能力。在本文中，对于DL-Lite_R本体和任意EDs，我们证明BUCQs的GA-和IGA-蕴含都是难处理的：具体来说，它们在数据复杂度上是Π2p-完全的，即使对于空的TBox也已经成立。任意EDs对上述蕴含语义还有第二个重要影响：它们不满足一个与保密保护相关的关键属性，称为*不可区分性*[2 (https://arxiv.org/html/2607.16715#bib.bib36)]。这个属性已在[8 (https://arxiv.org/html/2607.16715#bib.bib99)]中为EDs研究过，它确保总是可能提供一个不包含敏感信息的ABox，同时保证具有这个新ABox的CQE系统对于每个可能的查询行为与原始系统完全相同。为了克服这些限制，我们首先继续研究线性的情况（即qb中只出现一个原子），而不强加[13 (https://arxiv.org/html/2607.16715#bib.bib108)]的额外限制。在这种场景下，我们观察到GA-和IGA-蕴含都满足不可区分性属性，并且我们证明了对于DL-Lite_R本体，两个BUCQ蕴含问题在数据复杂度上都变得可处理。然而，单独的线性EDs对于表达审查规则是相当有限的：它们甚至不能捕获拒绝断言，而拒绝断言在大多数CQE研究中作为事实上的基线，因为它们代表了指定保护规则的最自然方式之一。因此，我们提出了一种基于*最小策略违反*（MPV）概念的新方法。每个MPV是一组最小的事实，这些事实是T∪A的逻辑推论，并且在一个给定事实集A'中至少导致一个ED被违反。从一个包含T∪A所有逻辑推论的事实集A'开始，我们迭代地移除所有出现的MPV。这种迭代方法的固定点产生一个GA审查器，我们称之为*MPV审查器*。我们证明了由此产生的MPV蕴含概念：(i) 可靠地近似GA-和IGA-蕴含，并且值得注意的是，当依赖关系是线性的且TBox在DL-Lite_R中，或者策略由拒绝组成时，它与IGA-蕴含一致；(ii) 满足不可区分性属性；(iii) 对于DL-Lite_R，在数据复杂度上是可处理的（PTIME完全）。最后，我们给出了MPV蕴含的实验评估，重点关注本文中确定的可处理设置，即DL-Lite_R。与主要依赖查询重写技术的现有实现[1 (https://arxiv.org/html/2607.16715#bib.bib4),13 (https://arxiv.org/html/2607.16715#bib.bib108)]不同，我们的方法涉及通过合适的基于SQL的数据操作查询构建MPV审查器。一旦计算出MPV审查器，就使用标准技术验证查询蕴含。实验基于OWL2Bench[17 (https://arxiv.org/html/2607.16715#bib.bib2)]，这是一个支持生成自定义大小ABox的基准测试，使我们能够测试我们的方法在基础数据量方面的可扩展性。本文组织如下。在回顾预备知识之后，在第三节 (https://arxiv.org/html/2607.16715#S3)中我们正式介绍我们的CQE框架。然后，在第四节 (https://arxiv.org/html/2607.16715#S4)中我们分析我们框架中GA-和IGA-蕴含的计算性质。在第五节 (https://arxiv.org/html/2607.16715#S5)中我们介绍用于CQE的新MPV语义，并研究轻量级DL中MPV蕴含的计算性质。在第六节 (https://arxiv.org/html/2607.16715#S6)中我们介绍在DL-Lite_R本体背景下MPV蕴含的实验评估。我们在第七节 (https://arxiv.org/html/2607.16715#S7)中得出结论。  

## 2 预备知识  
我们引用一阶（FO）逻辑和描述逻辑（DL）的标准概念。我们考虑一个符号字母表Σ，划分为三个可数无限子集ΣP、ΣV和ΣI，分别用于表示谓词、变量和常量符号（或个体）。反过来，ΣP又划分为两个互不相交的集合ΣC和ΣR，包含*概念*和*角色*名称，即一元和二元谓词。一个*原子*α是形式为P(t→)的公式，其中P∈ΣP，t→是一个*项*序列（即来自ΣI∪ΣV的符号）。α被称为*基*（或*事实*），如果对于每个ti∈t→有ti∈ΣI。一个FO*句子*是没有自由变量的公式。为了明确公式φ的自由变量x→，我们写作φ(x→)。给定一个FO理论（句子集合）Φ，我们用Const(Φ)表示出现在Φ的公式中的常量集合。我们写作eval(φ,I)表示在FO解释I上计算FO句子φ。FO理论Φ的一个*模型*是满足Φ中所有句子的一个FO解释。我们说Φ*蕴含*一个FO句子φ，记作Φ⊧φ，如果对于Φ的每一个模型I，eval(φ,I)为真。我们使用术语*查询*作为FO公式的同义词。我们考虑*合取查询*（CQs），即形式为q=∃x→ φ(y→)的查询，其中φ是多个原子的合取，且x→⊆y→。当x→=y→时，我们称q为一个*布尔合取查询*（BCQ）。*（布尔）合取查询的并集*，或（B）UCQs，是（布尔）合取查询q1(y→)∨...∨qk(y→)的析取。我们还考虑特殊的基CQ ⊥，假设eval(⊥,I)对于每个FO解释I都为假。一个*DL本体*是一个FO理论O=T∪A，其中T称为*TBox*，A称为*ABox*。每个ABox是一个事实集合，而TBox的形状取决于所考虑的特定DL。本文中提供的主要复杂度结果聚焦于DL-Lite_R[6 (https://arxiv.org/html/2607.16715#bib.bib98)]。在这样的DL中，一个*基本角色*R要么是符号P∈ΣR，要么是其*逆*P−。一个*基本概念*C要么是ΣC中的符号，要么是一个所谓的*无资格存在限制*∃R，针对某个基本角色R。然后，一个DL-Lite_R TBox T是一个有限的基本概念或基本角色之间的包含和不相交公理集合。具体来说，这些断言的形式为C1⊑C2、C1⊑¬C2、R1⊑R2、