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查询计算复杂度

回答

相关问题