为什么向OWL EL添加析取会使其在计算上更加复杂？

Question

我试图理解为什么向OWL EL添加析取会使该语言在计算上更加复杂(例如。为什么添加'or‘会使得在多项式时间内不可能进行可满足性、一致性和/或包含检查……它们是标准猫头鹰EL中的p-time )

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

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

Answer 1

通过“重写到”，我猜您的意思是用命名类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个析取，您可能会得到n个可能性的幂的2来探索。

这在命题逻辑中也是一样的:如果你有一个没有析取出现的合取范式，那么可满足性是一个愚蠢的简单问题。当你允许析取时，它是NP完全的。