algorithm - SPARQL查询计算复杂度

我有一个具有不同模式的SPARQL查询列表（例如，SELECT、UNION、Engin）。我想用大O符号来计算它们的时间复杂度（例如O（n），O（nLogn））。请告诉我怎么做我的rdf图中有超过3000000000个三倍。
下面是一些查询查询示例

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
  }

最佳答案

SPARQL本身为PSPACE-complete。对于任何给定的查询，您可能只提出最佳的情况复杂度。真实世界的复杂性将在某种程度上取决于数据库的实现。