本體計算複雜度

Question

我想知道本體的計算複雜度。我正在使用NIFSTD本體，並希望根據某些特定查詢計算時間（大O）來創建層次結構。

我讀過SPARQL本身是Pspace-complete。如您所知，本體通常基於RDF並通過SPARQL進行查詢。

我想要在本體（選擇）和搜索條件（其中{...}）中搜索概念的代價。

此外，是開放和讀取和本體O（n）的計算複雜度，其中n等於本體文件的大小？

由於事先 阿里夫

Answer 1

搜索在IRI是已知的概念是非常快的 - 大多數API具有索引這些，所以你可以爲這個（1）假設O操作。

使用where條件搜索完全取決於條件。條件越複雜，成本越高 - 上限與您提到的最差情況相同。

另一個需要考慮的因素是您是否希望在分析中包含任何推斷機制;如果是這樣的話，那麼還有另一個未知複雜的來源 - OWL 2 DL推理具有指數最壞情況的複雜性，但是給定本體的實際推理難度取決於許多因素，並且不容易預測。還是一個開放的研究問題。

加載本體的成本大小與其大小成正比，儘管一些公理需要比其他公理更多的處理。預計不同API之間會有很大差異;我會考慮O（n）一個可接受的近似值。