Как пройти по дереву RDF в SPARQL и найти связи вне дерева? - PullRequest
Новая
       116

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

3 голосов
/ 18 октября 2019

Рассматривая дерево с отношениями корневого узла "A" и "hasChild" (например, структура продукта) следующим образом: tree diagram

Цель состоит в том, чтобы выяснить:У каких узлов есть родители вне дерева?

В этом случае ответом должны быть «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>

1 Ответ

4 голосов
/ 18 октября 2019

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