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

Question

我试图理解为什么向 OWL EL 添加析取会使语言在计算上更加复杂(例如，为什么添加“或”会使可满足性、一致性和/或包含检查在多项式时间内变得不可能......他们'标准 OWL EL 中的 re 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 或 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 完全的。