Как обойти дерево RDF в SPARQL и найти связи вне дерева?

Рассмотрим дерево с корневым узлом «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>

sparql rdf semantic-web triplestore allegrograph
person Grapheneer    schedule 17.10.2019    source источник

Ответы (1)


arrow_upward
5
arrow_downward

Хитрость заключается в том, чтобы убедиться, что нет пути от корня вашего дерева к вашему внешнему родительскому узлу. Вы можете сделать это с помощью конструкции 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 }
}

Масштабируется ли это до «миллионов узлов», будет зависеть от а) глубины дерева и б) используемого вами тройного хранилища. Я выполнил запрос с помощью 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)
person Jeen Broekstra    schedule 17.10.2019