rdf - 为什么在OWL EL中添加析取运算会使其计算更加复杂？

我试图理解为什么在OWL EL中添加析取关系会使语言的计算更加复杂（例如，为什么在多项式时间内添加“或”将使可满足性，一致性和/或包含检查无法实现……它们是p-标准OWL EL中的时间）

OWL EL配置文件除其他外，不允许析取和求反。我很难理解为什么不能通过创建包含以给定类表达式的析取作为子集的新类来使用现有的OWL EL构造来实现析取。

例如，可以表达式（以曼彻斯特语法）：

  Class1 and (Class2 or Class3) and (Property1 some (Class3 or Class4))

改写为：

  Class1 and NewClass1 and (Property1 some NewClass2)

  where Class2 is a subset of NewClass1,
        Class3 is a subset of NewClass1,
        Class3 is a subset of NewClass2,
        Class4 is a subset of NewClass2

？

我知道答案是“否”，但为什么是“否”？

最佳答案

通过“重写为”，我想您的意思是您用命名类C or D替换了原始本体中的所有析取表达式C_or_D并添加了公理：

`C subClassOf C_or_D`
`D subClassOf C_or_D`

您必须递归执行此操作，因为C（分别为D）本身可能包含析取关系。然后，您将拥有一个带有更多公理，更多概念名称的本体，而且语义似乎非常紧密。但是，当您怀疑自己时，您就错了。考虑以下示例：

A subClass C or D
C subClassOf B
D subClassOf B

使用建议的重写，您将得到：

A subClass C_or_D
C subClassOf C_or_D
D subClassOf C_or_D
C subClassOf B
D subClassOf B

第一个本体包含A subClassOf B，而第二个本体则不需要。

通常，析取在推理中是有问题的，因为它会导致其他选择。例如，如果要检查一致性，则必须尝试为替代方案的一个分支找到一个可能的世界安排，如果失败，则为替代方案的第二个分支找到一个可能的世界安排。每个析取运算可能会将处理时间乘以2。使用n个析取运算，您可能会得到2乘以n种可能性进行探索。

命题逻辑也是如此：如果您有一个合取范式而没有析取，则可满足性是一个愚蠢的简单问题。当允许析取时，它是NP完全的。