Рассчитать длину пути между узлами?

Question

Как я могу получить длину пути между двумя узлами? Например, учитывая организационную иерархию, как я могу определить, насколько далеко отделены родительская и дочерняя организации? Рассмотрим следующие сценарии:

1. OrgA -hasSubOrganization-> OrgB, OrgC

   Это очень упрощенный случай, когда я хочу получить все непосредственные суборганизации сущности. Следовательно, длина пути равна 1.

2. OrgA -> OrgB -> OrgC

   или общий случай

   OrgA -> OrgB - - - - - - - - OrgZ
   

Я хочу рекурсивно пройтись по графику и найти каждую организацию, принадлежащую другой организации, через hasSubOrganization имущество. Чтобы получить рекурсивную информацию для всех организаций, я могу использовать пути к свойствам, например, + оператор:

OrgA hasSubOrganization+ ?subOrg

Это даст мне все суборганизации вплоть до конечных узлов. Но моя конечная цель состоит в том, чтобы построить организационную иерархию, но информация о "количестве узлов / шагов / уровней / прыжков, на которых находится суборганизация" теряется. Это означает, что я не могу воссоздать структуру org для визуализации.

Как я могу получить информацию о "количестве удаленных узлов" в дополнение к названию суборганизации?

Answer 1

Это основано на том же методе, который используется для вычисления позиции элемента в списке RDF с использованием SPARQL, который описан в: Можно ли получить позицию элемента в RDF Collection в SPARQL?

Если у вас есть такие данные:

@prefix : <http://example.org> .

:orgA :hasSuborganization :orgB, :orgC, :orgD.
:orgB :hasSuborganization :orgE, :orgF.
:orgE :hasSuborganization :orgG.
:orgG :hasSuborganization :orgH.

который описывает иерархию как это:

тогда вы можете использовать такой запрос:

prefix : <http://example.org> 

select ?super ?sub (count(?mid) as ?distance) { 
  ?super :hasSuborganization* ?mid .
  ?mid :hasSuborganization+ ?sub .
}
group by ?super ?sub 
order by ?super ?sub

чтобы получить такие результаты:

$ sparql --query query.rq --data subs.n3
----------------------------
| super | sub   | distance |
============================
| :orgA | :orgB | 1        |
| :orgA | :orgC | 1        |
| :orgA | :orgD | 1        |
| :orgA | :orgE | 2        |
| :orgA | :orgF | 2        |
| :orgA | :orgG | 3        |
| :orgA | :orgH | 4        |
| :orgB | :orgE | 1        |
| :orgB | :orgF | 1        |
| :orgB | :orgG | 2        |
| :orgB | :orgH | 3        |
| :orgE | :orgG | 1        |
| :orgE | :orgH | 2        |
| :orgG | :orgH | 1        |
----------------------------

Хитрость заключается в том, чтобы признать, что любой путь от X до Y можно рассматривать как (возможно, пустой) путь от X к некоторому промежуточному узлу Z (непустой означает, что вы можете выбрать X в качестве Z), объединенный с (не пустым) путем из От Z до Y. Количество возможных способов выбора Z указывает длину пути.

Answer 2

Вы не можете сделать это, используя правильные пути, так как рабочая группа специально решила не делать эту информацию доступной, поскольку это делает реализацию намного более сложной.

Если вы хотите сгенерировать иерархию, вероятно, будет столь же эффективно сделать целую серию запросов SPARQL, где каждый запрос расширяет один лист иерархии и не использовать пути свойств вообще, если ваша цель - просто визуализировать иерархию

Могут быть другие подходы, использующие Jena Ontology API - я бы порекомендовал спросить в их списке рассылки [e-mail] для получения дополнительной помощи экспертов