Calcular la longitud de la ruta entre los nodos?

Question

¿Cómo puedo recuperar la longitud de una ruta entre dos nodos? Por ejemplo, dada una jerarquía organizacional, ¿cómo puedo determinar qué tan separados están un padre y una organización descendiente? Considere los siguientes escenarios:

1. OrgA -hasSubOrganization-> OrgB, OrgC

   Este es el caso muy simplista donde quiero conseguir todas las suborganizaciones inmediatas de una entidad. Por lo tanto la longitud del camino es 1.

2. OrgA -> OrgB -> OrgC

   o el caso general

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

Quiero atravesar de forma recursiva abajo el gráfico y encontrar cada organización que pertenece a otra organización a través de la hasSubOrganization propiedad. Para obtener todas las suborganizaciones recursivo que pueden utilizar property paths, por ejemplo, el operador de +:

OrgA hasSubOrganization+ ?subOrg 

Esto me dará todas las suborganizaciones hasta los nodos hoja. Pero mi objetivo final es construir la jerarquía de la organización, pero la información sobre el "Número de nodos/pasos/niveles/saltos de una suborganización es" se pierde. Esto significa que no puedo recrear la estructura organizativa para una visualización.

¿Cómo puedo capturar la información del "número de nodos" además del nombre de la suborganización?

Answer 1

Esto se basa en la misma técnica que se utiliza para calcular la posición de un elemento en una lista RDF utilizando SPARQL que se describe en: Is it possible to get the position of an element in an RDF Collection in SPARQL?

Si tiene datos de la siguiente manera:

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

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

que describe una jerarquía de esta manera:

continuación, se puede utilizar una consulta como esta:

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 

para obtener resultados como estos:

$ 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  | 
---------------------------- 

El truco aquí es reconocer que cualquier camino de X a Y puede ser visto como un (posiblemente vacío) de X a algún nodo intermedio Z (no vacío significa que puede elegir X como Z) concatenado con una ruta (no vacía) de Z a Y. El número de formas posibles de seleccionar Z indica la longitud de la ruta.

Answer 2

No se puede hacer esto utilizando rutas de propiedad, ya que el grupo de trabajo eligió específicamente no hacer esta información disponible ya que hace la implementación mucho más compleja.

Si desea generar una jerarquía, probablemente sea igual de eficiente realizar toda una serie de consultas SPARQL donde cada consulta expande una hoja de la jerarquía y no usa rutas de propiedades en absoluto si su objetivo es solo visualizar la jerarquía

Puede haber otros enfoques que utilicen la API de Ontología de Jena. Recomiendo consultar en su lista de correo jena-users@incubator.apache.org para obtener ayuda más experta