SPARQL查詢計算複雜度

我有一個列表SPARQL查詢與各種模式（例如，選擇，聯盟，聯接）。我想通過使用大O符號（例如O（n），O（nlogn））來計算它們的時間複雜度。請讓我知道如何做到這一點。我的RDF圖中有三千萬以上的三元組。SPARQL查詢計算複雜度

以下是一些例子查詢查詢

Query 1: 
select ?o where { <http://example.com/person_info/242622027> vocab:info_gender ?o} 

Query 2: 
select ?o ?k where { 
    { 
    ?s vocab:person_info_pid '242622027'^^xsd:decimal. 
    ?s vocab:person_info_homeloc ?o 
    } 
UNION 
    { 
    ?i vocab:activities_pid '242622027'^^xsd:decimal. 
    ?i vocab:activities_purpose ?k     
    } 
} 

Query3: 
select (count(*) as ?no) where{ 
    ?s vocab:outputparttwo_iteration '0'^^xsd:decimal 
    }

來源

2014-11-21 Beautiful Mind

圖中有300多億個三元組？ – 2014-11-21 03:28:26

SPARQL只是一種查詢語言;實現可以用很多不同的方式實現，所以對於給定查詢的運行時複雜性沒有一般答案。這取決於實施。也就是說，大型三聯商店通常會對數據進行索引，因此查詢1和查詢3將非常快速。查詢二可能是O（O（？s？o query）+ O（？i？k query））。 – 2014-11-21 03:33:16

是的，我有一個大圖。我可以理解SPARQL的實現。假設沒有索引，那麼查詢1和3的複雜度是多少？對於查詢2，你說複雜度可能是O（O（？s？o query）+ O（？i？k query）。什麼是「查詢」在這裏？是否有任何費用加入？ – 2014-11-21 08:43:30

SPARQL本身是PSPACE-complete。對於任何給定的查詢，您可能只能想出最佳的案例複雜性。現實世界的複雜性將取決於數據庫在一定程度上的實現。

來源

2014-11-21 20:57:45 Michael

SPARQL查詢計算複雜度

回答

相關問題