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

Question

考虑一棵树与根节点 "A" 和 "hasChild" 的关系（例如产品结构）如下：

目标是找出：树外有哪些节点parents？

在这种情况下，答案应该是“B”和“Q”，因为它们 parents 在树之外。

查询应该转到每个节点并检查它的 parents 而不是创建一个 children 的列表并检查我猜的每个节点。

我怎样才能有效地（应该为数百万个节点工作）遍历这棵树和 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>

Answer 1

诀窍是确保没有从树根到外部父节点的路径。您可以通过 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 }
}

这是否扩展到 "millions of nodes" 将取决于 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)

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

How to traverse RDF tree in SPARQL and find connections outside of the tree?

sparql

rdf

semantic-web

triplestore

allegrograph