本体计算复杂性

Question

我想知道本体的计算复杂性。我正在使用NIFSTD本体，并希望根据一些特定的查询计算时间(big O)建立一个层次结构。

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

我想要在本体中搜索概念(select)和搜索条件(where {...})的成本。

此外，打开和读取的计算复杂度是否为O(n)，其中n等于本体文件的大小？

先谢谢你，阿瑞夫

Answer 1

搜索IRI已知的概念是非常快的-大多数API都有这些概念的索引，所以您可以假设O(1)。

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

另一个要考虑的因素是，您是否希望在分析中包括任何推理机制；如果是这样，则存在另一个未知复杂性的来源- OWL 2 DL推理具有指数最坏情况复杂性，但在给定本体上推理的实际难度取决于许多因素，并且不容易预测。这仍然是一个悬而未决的研究问题。

加载本体的成本与其大小大致成正比，尽管一些公理比其他公理需要更多的处理。不同API之间的巨大差异是可以预期的；我认为O(n)是一个可以接受的近似值。