OWL 온톨로지에서 두 노드 사이의 모든 경로를 찾는 쿼리

Question

Sparql의 새로운 기능입니다. OWL 형식의 자동차 온톨로지가 있습니다. 나에게서 두 노드의 이름을 가져 와서 그들 사이의 모든 기존 경로를 보여주는 쿼리를 작성하려고합니다. 다음 그림에서 예를 들어 : 입력 노드 G와 E, 경우 example of my ontology's graph, 그들 사이의 경로는 G h를 내가

을 전자, 는 G CBE, G의 cadbe이 G의 캘리포니아의 일이 될 수 있습니다 Eclipse에서 온톨로지에 연결하기 위해 Jena라는 Apache를 사용했습니다. 이제 위에서 언급 한 쿼리를 작성해야합니다. 쿼리를 작성하는 데 도움이되는 예제가 있습니까?

Answer 1

SPARQL이 빛나는 유스 케이스가 아닙니다. SPARQL은 은유로 그래프를 사용하지만 고전적인 그래프 알고리즘을 구현하는 데는 그리 이상적이지 않습니다.

경우에 따라 여러 개의 반복 쿼리를 사용하여 구현하는 것이 가장 쉽습니다. 다른 경우 SPARQL을 사용하여 관련 개인 및 속성 어설 션을 포함하는 하위 그래프를 만든 다음이를 일반 알고리즘 중 하나에 대한 입력으로 사용하는 것이 더 쉽습니다.

finding all paths between two nodes is NP-hard의 문제이므로 고려해야 할 노드 수를 줄이는 것이 좋습니다. 대신에 k 최단 경로를 찾으십시오.이 주제에 대한 ESWC 2016 시험 결과는 이제 available입니다. 불행하게도이 서류는 현재 자체 보관 또는 공개되지 않습니다.

트리플 저장소의 구현 및 그래프의 구조에 따라, 각 C되도록 찾음으로써 및 B 사이에 경로에 관련된 모든 트리플을 찾을 실현 될 수있다 올빼미 : topObjectProperty + C와 올빼미 C :? topObjectProperty + B. 이러한 종류의 쿼리로 인해 서버가 녹을 수도 있고 DBA가 사용자를 의자에 묶고 UPS 부품으로 악의적 인 일을 할 수도 있습니다.

일부 시스템에서는 이러한 알고리즘을 쉽게 구현할 수있는 확장을 제공합니다. 예를 들어 AllegroGraph는 first class paths에 대한 비표준 지원을 제공합니다.

Answer 2

나는 그것을 수행하는 가장 좋은 방법은 알고리즘을 구현하는 것이라고 생각합니다! 이 작업은 SPARQL 또는 일부 쿼리 방법을 사용하여 완료 할 수 있다고 생각하지 않습니다. Java와 Jena에서 다음 알고리즘을 구현하여 OWL 온톨로지의 노드 집합을 연결하는 모든 경로를 찾았습니다. 두 개의 필수 노드를 입력으로 사용할 수 있습니다.

는 그래프 G= (V, E) 주어 :

1. 가 감독
2. 비순환를
3. 비 가중치
4. 가질 수보다 두 정점들 (따라서, 소스와 목적지된다 간의 하나의 에지보다 가장자리를 결정하기에 충분하지 않음).

그리고 주어진 정점 세트를 vSet이라고합니다. 버텍스가 포함 된 vRoot; 우리는 ALL 경로를 찾을 필요가 다음을 존중 pSetvSet 사이의 요소 :

1. Vroot를에서 연결할 수 있어야 pSet에서 어떤 경로의 소스로 나타나는 정점.
2. pSet의 경로는 vSet의 출처와 대상을 가져야하며 vSet의 다른 꼭지점을 포함해서는 안됩니다.

다음의 알고리즘은 다른 정점 vSet의 v1 도달 할 때까지 반복 당 하나의 에지에 전류 경로를 각각 증가 (상기 1)에 따르면 vRoot에서 시작하는, BFS 유사하다; 이 도달 경로를 저장하고 v1부터 시작하는 새로운 경로 집합을 시작하십시오.

output = ∅; 
maxLengthPaths = ∅; 
1. add all edges that vRoot is there source to maxLengthPaths 
2. while size(maxlengthpaths) != ∅ do 
    (a) paths := ∅; 
    (b) extendedPaths := ∅; 
    (c) foreach path p in maxLengthPaths do 
    i. if (destination of p in vSet) 
     1. add p to output 
     2. for each edge e that destination of p is its source 
     A. add e to extendedPaths 
    ii. else 
     1. add p to paths 
    iii. for path p1 in paths 
     1. for each edge that destination of p1 is its source 
     A. extend p1 by a edge and add it to extendedPaths 
    (d) maxLengthPaths = extendedPaths