本体计算复杂度

Question

我想知道本体的计算复杂度。我正在使用NIFSTD本体，并希望根据某些特定查询计算时间（大O）来创建层次结构。

我读过SPARQL本身是Pspace-complete。如您所知，本体通常基于RDF并通过SPARQL进行查询。

我想要在本体（选择）和搜索条件（其中{...}）中搜索概念的代价。

此外，是开放和读取和本体O（n）的计算复杂度，其中n等于本体文件的大小？

由于事先 阿里夫

Answer 1

搜索在IRI是已知的概念是非常快的 - 大多数API具有索引这些，所以你可以为这个（1）假设O操作。

使用where条件搜索完全取决于条件。条件越复杂，成本越高 - 上限与您提到的最差情况相同。

另一个需要考虑的因素是您是否希望在分析中包含任何推断机制;如果是这样的话，那么还有另一个未知复杂的来源 - OWL 2 DL推理具有指数最坏情况的复杂性，但是给定本体的实际推理难度取决于许多因素，并且不容易预测。还是一个开放的研究问题。

加载本体的成本大小与其大小成正比，尽管一些公理需要比其他公理更多的处理。预计不同API之间会有很大差异;我会考虑O（n）一个可接受的近似值。