OWLオントロジ内の2つのノード間のすべてのパスを検索するクエリ

Question

Sparqlの新機能です。私はOWL形式の自動車オントロジーを持っています。私は2つのノードの名前を私から取得し、それらの間に存在するすべてのパスを表示するクエリを作成しようとしています。次の画像、例えば ： example of my ontology's graph、 入力ノードはGとE、それらの間のパスは GのCBE、 Gのcadbeすることができている場合、 GのCAのものがあること、 のG H Iは

を電子Eclipseから私のオントロジに接続するためにApache Jenaを使用しました。今私は上記のクエリを記述する必要があります。クエリを書くのに役立つ例はありますか？

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オントロジのノードのセットを接続するすべての有向パスを見つけました。必要な2つのノードを入力として使用できます。

あるグラフG= (V, E)考える：

向け

1. 、
2. 非環式、
3. 非加重、
4. は、2つの頂点（の間の複数のエッジを有していてもよく、したがって、ソースとデスティネーションでありますエッジを決定するのに十分ではない）。

与えられた頂点のセットについては、vSetとしましょう。頂点が含まれていますvRoot; pSetでいくつかのパスのソースとして表示される任意の頂点がVROOTから到達可能でなければなりません

1. ：私たちは次のことを尊重ALLパスpSetvSet間の要素を見つける必要があります。
2. pSetする必要があり、任意のパスがvSetから、その送信元と宛先を有し、vSetの他の頂点を含んではなりません。

以下のアルゴリズムは、それが別の頂点vSetのv1に達するまで、反復ごとに1つのエッジに電流経路のそれぞれを成長させる（上記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