sparql - 如何遍历SPARQL中的RDF树并在树外查找连接？

考虑具有根节点“ A”和“ hasChild”关系（例如产品结构）的树，如下所示：


目标是找出：
树外有哪些节点的父母？

在这种情况下，答案应为“ B”和“ Q”，因为他们的父母在树外。

该查询应该转到每个节点并检查其父节点，而不是创建一个子节点列表，然后检查每个子节点。

我如何有效地（应为数百万个节点工作）如何遍历这棵SPARQL树并回答呢？

这是我尝试过的，但给出了0个结果：

PREFIX xxx:         <http://example.org/xxx#>

select * where {
   xxx:A   xxx:hasChild*  ?child .
   ?child  ^xxx:hasChild  ?foreignParent .
   ?child  ^xxx:hasChild  ?parent .
   FILTER (?parent =! ?foreignParent) .
}

随附了相应的样本数据：

<?xml version="1.0"?>
<rdf:RDF
    xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
    xmlns:owl="http://www.w3.org/2002/07/owl#"
    xmlns:xxx="http://example.org/xxx#"
    xmlns:rdfs="http://www.w3.org/2000/01/rdf-schema#"
    xmlns:xsd="http://www.w3.org/2001/XMLSchema#"
  xml:base="http://example.org/xxx">
  <owl:Ontology rdf:about="">
    <owl:versionInfo>Created with TopBraid Composer</owl:versionInfo>
  </owl:Ontology>
  <owl:Class rdf:ID="Other">
    <rdfs:label>Other</rdfs:label>
    <rdfs:subClassOf rdf:resource="http://www.w3.org/2002/07/owl#Thing"/>
  </owl:Class>
  <owl:Class rdf:ID="Item">
    <rdfs:label>Item</rdfs:label>
    <rdfs:subClassOf rdf:resource="http://www.w3.org/2002/07/owl#Thing"/>
  </owl:Class>
  <rdf:Property rdf:ID="hasChild">
    <rdfs:range rdf:resource="#Item"/>
    <rdfs:range rdf:resource="#Other"/>
    <rdfs:domain rdf:resource="#Item"/>
    <rdfs:label>has child</rdfs:label>
  </rdf:Property>
  <xxx:Other rdf:ID="Fake_1">
    <xxx:hasChild>
      <xxx:Item rdf:ID="B">
        <xxx:hasChild>
          <xxx:Item rdf:ID="D">
            <xxx:hasChild>
              <xxx:Item rdf:ID="F"/>
            </xxx:hasChild>
            <xxx:hasChild>
              <xxx:Item rdf:ID="E"/>
            </xxx:hasChild>
          </xxx:Item>
        </xxx:hasChild>
        <xxx:hasChild>
          <xxx:Item rdf:ID="C"/>
        </xxx:hasChild>
      </xxx:Item>
    </xxx:hasChild>
    <rdfs:label>Fake 1</rdfs:label>
  </xxx:Other>
  <xxx:Other rdf:ID="Fake_2">
    <xxx:hasChild>
      <xxx:Item rdf:ID="Q"/>
    </xxx:hasChild>
    <rdfs:label>Fake 2</rdfs:label>
  </xxx:Other>
  <xxx:Item rdf:ID="A">
    <xxx:hasChild>
      <xxx:Item rdf:ID="G">
        <xxx:hasChild>
          <xxx:Item rdf:ID="X">
            <xxx:hasChild>
              <xxx:Item rdf:ID="Z"/>
            </xxx:hasChild>
            <xxx:hasChild>
              <xxx:Item rdf:ID="Y"/>
            </xxx:hasChild>
          </xxx:Item>
        </xxx:hasChild>
        <xxx:hasChild>
          <xxx:Item rdf:ID="R">
            <xxx:hasChild>
              <xxx:Item rdf:ID="W"/>
            </xxx:hasChild>
            <xxx:hasChild>
              <xxx:Item rdf:ID="S">
                <xxx:hasChild>
                  <xxx:Item rdf:ID="V"/>
                </xxx:hasChild>
                <xxx:hasChild>
                  <xxx:Item rdf:ID="U"/>
                </xxx:hasChild>
                <xxx:hasChild>
                  <xxx:Item rdf:ID="T"/>
                </xxx:hasChild>
              </xxx:Item>
            </xxx:hasChild>
          </xxx:Item>
        </xxx:hasChild>
        <xxx:hasChild>
          <xxx:Item rdf:ID="M">
            <xxx:hasChild rdf:resource="#Q"/>
            <xxx:hasChild>
              <xxx:Item rdf:ID="P"/>
            </xxx:hasChild>
            <xxx:hasChild>
              <xxx:Item rdf:ID="O"/>
            </xxx:hasChild>
            <xxx:hasChild>
              <xxx:Item rdf:ID="N"/>
            </xxx:hasChild>
          </xxx:Item>
        </xxx:hasChild>
        <xxx:hasChild>
          <xxx:Item rdf:ID="H">
            <xxx:hasChild>
              <xxx:Item rdf:ID="L"/>
            </xxx:hasChild>
            <xxx:hasChild>
              <xxx:Item rdf:ID="K"/>
            </xxx:hasChild>
            <xxx:hasChild>
              <xxx:Item rdf:ID="J"/>
            </xxx:hasChild>
            <xxx:hasChild>
              <xxx:Item rdf:ID="I"/>
            </xxx:hasChild>
          </xxx:Item>
        </xxx:hasChild>
      </xxx:Item>
    </xxx:hasChild>
    <xxx:hasChild rdf:resource="#B"/>
  </xxx:Item>
</rdf:RDF>

最佳答案

诀窍是确保从树根到外部父节点没有路径。您可以通过FILTER NOT EXISTS构造来做到这一点，如下所示：

PREFIX xxx: <http://example.org/xxx#>
SELECT ?child ?foreignParent
WHERE {
   xxx:A xxx:hasChild+ ?child.
   ?child ^xxx:hasChild ?foreignParent.
   FILTER NOT EXISTS { xxx:A xxx:hasChild* ?foreignParent }
}

是否缩放到“数百万个节点”将取决于a）树的深度和b）您使用的三元组。我使用您提供的测试数据在笔记本电脑上使用RDF4J运行了查询，并得到了以下信息：

Evaluating SPARQL query...
+-------------------------------------+-------------------------------------+
| child                               | foreignParent                       |
+-------------------------------------+-------------------------------------+
| <http://example.org/xxx#B>          | <http://example.org/xxx#Fake_1>     |
| <http://example.org/xxx#Q>          | <http://example.org/xxx#Fake_2>     |
+-------------------------------------+-------------------------------------+
2 result(s) (19 ms)