DEIM Forum 2019 F5-2

Shape Expression Schema におけるパターン問合せの充足可能性判定
松岡

栞†

鈴木

伸崇††

† 筑波大学情報学群知識情報・図書館学類 〒 305–8550 茨城県つくば市春日 1-2†† 筑波大学図書館情報メディア系 〒 305–8550 茨城県つくば市春日 1-2
E-mail: †s1511560@s.tsukuba.ac.jp, ††nsuzuki@slis.tsukuba.ac.jp
あらまし Shape Expression Schema(ShEx) はグラフデータのスキーマを記述するために新たに提案されたスキーマ
言語である．一般に，グラフデータは莫大なデータ量をもち，このようなデータに充足不能なパターン問合せを行う
場合，その検索は明らかに無駄である．そのため，充足不能なパターンを ShEx の定義から発見できることが望ましい．しかし，ShEx には選言による分岐が存在し，部分グラフ同型問題を適用して解くのは不十分である．そこで本研
究では部分グラフ同型問題の解法の一つである Ullman Algorithm を拡張し，適応させた．考案アルゴリズムを用いることで問合せ時間を短時間で済ますことが可能だと確認した．
キーワード

Shape Expression Schema，パターン問合せ，充足可能性判定
選言「|」を用いて，「E1 |E2 」のように E1 または E2 に一致す

1 はじめに近年，RDF データ/グラフデータは急速に増加し，様々なところで用いられている．グラフデータは規模が大きいことが多いため，より効率の良い問合せ処理が必要とされている．ス
キーマは RDB や XML などではよく活用され，技術も確立しているが，グラフデータのスキーマの活用についてはまだ途上の段階である．グラフデータのスキーマは多様であり，例として RDF Schema [1] やグラフスキーマが挙げられる．RDF

Schema は従来の RDF のスキーマ言語として提案されているものである．しかし，オントロジ記述言語としての性格が強く，スキーマ言語としてのセマンティクスが W3C で定義されていない．さらに，グラフスキーマはスキーマをグラフとして表現するものであるが繰り返しや入れ子といった表現力が低い．そこで，グラフデータの普及に伴い，RDF Schema やグラフス
キーマより適切に記述することの可能なスキーマが必要となり，

Shape Expression Schema（以下 ShEx）[2] が誕生した．ShEx
は型を Regular Bag Expression(以下 RBE) という規則に基づいて表し，グラフの各ノードに対し型を割り当てられるスキーマである．
パターン問合せは，問合せとしてグラフの断片（パターン）を指定してグラフからそのパターンにマッチする部分を検索するもので，グラフに対する最も基本的かつ重要な問合せである．
一般にグラフデータは莫大なデータ量をもつ．このようなデー
タに対してパターン問合せを行う場合，その莫大なデータの中からマッチするパターンを検索しなければならない．パターン

P と ShEx S に対して，S に妥当かつ P を含むようなグラフ
データ（RDF データ）が存在しなかった場合，すなわち充足不能であった場合は膨大なデータを検索したのちに解が存在しないという結果が返される．しかし，その検索は明らかに無駄である．また，パターンがマッチするかどうか調べる場合，一
般には部分グラフ同型問題を解けばよいとされるが，ShEx はるという型を定義できる．検索する ShEx に選言「|」による分岐が存在した場合，部分グラフ同型問題では解くことができな
い．なぜなら，分岐しているうちの一方のエッジが選択された
場合，他方のエッジは以降のマッチングにおいて利用することができないからである．
そこで本研究では，グラフデータと比較して容量の著しく軽い ShEx を修正 AND/OR グラフで表現し，パターン問合せの充足可能性を判定するアルゴリズムを提案する．より具体的には，まず ShEx を最もサイズの小さい修正 AND/OR グラフで表現し，その中で選言「|」による分岐をもつノードを抽出する．その後，部分グラフ同型問題の解法の一つである Ullman

Algorithm [3] を元に，パターンと修正 AND/OR グラフとのマッチングを行う．この際，Ullman Algorithm に選言「|」に対応した判定を加え，実行する．マッチング中のノードが選言「|」による分岐をもつノードであった場合には，同時に分岐しているエッジを使用せずにマッチング可能かの判定，マッチン
グ中のノードに接続している元のノードが選言「|」による分岐をもつノードであった場合には，ほかの分岐先のエッジを使用済みでないかの判定を行う．パターンのノード全てとマッチすることが可能であれば，充足可能として処理を終了するアルゴ
リズムである．本研究の目的が達成されれば，大規模なグラフ
データをより効率よく問合せることが可能となり，グラフデー
タを利用する研究者・開発者にとって有用と考えられる．著者の知る限り，ShEx の下でのパターン問合せ充足可能性問題を解くためのアルゴリズムはこれまで提案されていない．
提案アルゴリズムを実装し，充足不能なパターンを対象として評価実験を行った．その結果，提案アルゴリズムが充足可能性判定を行えること，充足不能な場合に処理時間を少なく済ませられることを確認した．
本稿の構成は以下の通りである．第２章では，グラフ，ShEx，
充足可能性問題の定義を行う．第３章では，ShEx に対する前処理および提案するアルゴリズムについて述べる．第４章では，

評価実験について述べる．第５章では，本研究のまとめについ

くのスキーマでは，型を定義する際に Regular Expression(正て述べる．

規表現) を用いる．ShEx では，Regular Expression ではなくRegular Bag Expression(以下 RBE) を用いている．Regular

2 諸 定 義Expression と違い，RBE は連結 || において順序が無視され本章では本研究 で扱うグ ラフの 概要，Shape Expression

Schema，充足可能性問題について述べる．
2. 1 グラフの概要

る．RBE の規則は以下のようになっている．

•

ϵ と a ∈ Σ は RBE である．

•

E1 , E2 , · · · , Ek が RBE であるならば，E1 |E2 | · · · |Ek

は RBE である．ここで，‘|本研究ではラベル付き有向グラフ (以下グラフ) を利用している．グラフを G = (V, E) とする．ここで，Σ はラベルの集合，V はノードの集合，E ⊆ V × Σ × V はラベル付き有向辺の集合である．以下，エッジ (n, a, n′ ) を n −→ n′ と表記するこaとがある．例として，図 1 に簡単なグラフ G0 を示す．

•

は選言を表す．

E1 , E2 , · · · , Ek が RBE であるならば， E1 ∥ E2 ∥ · · · ∥Ek は RBE である．ここで，‘∥’ は順序を無視した連結を表す．
•

E が RBE であるならば，E [n,m] は RBE である．ここで，[n, m] は n 回以上 m 回以下の繰り返しを表す．

ShEx は S = (Σ, Γ, δ) と表現される．ここで，Σ はラベルの集合，Γ は型の集合，δ は RBE を使用した型を定義する関数である．例として１つ以下に挙げる．
S：Σ= {a, b, c}Γ= {t0 , t1 , t2 , t3 , t4 }δ(t0 ) = (a :: t1 |b :: t2 |c :: t2 )∗δ(t1 ) = b :: t3 |c :: t4

図 1 グラフ G0

δ(t2 ) = c :: t3
δ(t3 ) = ε

ここで，グラフ G0 は，

δ(t4 ) = a :: t3Σ= {a, b, c}V= {n0 , n1 , n2 , n3 , n4 }E

= {n0 −
→ n1 , n 0 −→ n2 , n 0 −→ n3 , n 1 −→ n3 ,acc

ShEx には，1 つのノードが 1 つの型のみをもつ single type
b

b

a

n2 −
→ n3 , n 2 −→ n4 }である．また，エッジを出力しているノードを出力ノード，エッsemantics と複数の型をもつことのできる multi type semanticsとがある．本研究では single type semantics についてのみ検討している．

ジの向かう先である受け取り側のノードを入力ノードと呼称す

第３節で述べる提案アルゴリズムでは，ShEx をグラフとしる．各ノードは出力ノードである場合，入力ノードである場合，て表した上で充足可能性を判定する．ShEx S = (Σ, Γ, δ) でさらに，出力ノードであり入力ノードである場合がある．

あった場合，作成されるスキーマグラフ GS = (VS , ES ) は以

一般的な AND/OR グラフでは同時に存在する「AND」の下のように定義される．

エッジに円弧を描くことでグラフ中の分岐を可視化している

VS = Γ

が，本研究では分岐を表す「OR」のエッジに注目するため，図ES = {(t −→ t′ ) | δ(t) に a :: t′ が出現する }a2 のように「OR」のエッジに円弧を描いている．これを修正
AND/OR グラフと呼ぶことにする．

具体的には，先に述べた ShEx S から作成されるスキーマグラ
フ GS = (VS , ES ) は，VS

= {t0 , t1 , t2 , t3 , t4 }ES

= {t0 −
→ t1 , t0 −→ t2 , t 0 −→ t2 , t 1 −→ t3 , t1 −→ t4 ,

a

c

b

c

b

c

a

t2 −
→ t3 , t4 −→ t3 }となる．
図 2 グラフ G0

2. 3 充足可能性問題
本節では充足可能性問題を定義する．

2. 2 Shape Expression Schema
本節では，Shape Expression Schema(以下 ShEx) を定義する．

XML のスキーマである DTD や XML Schema といった多本研究では，問合せとしてパターンを考える．ここで，パターンもグラフである．パターン問合せとは，グラフ問合せにおいて最も基本的かつ重要なもので，データグラフにおいてパターンと同型である（マッチする）部分グラフが解となる．問合せ

q ，ShEx S に対して，「S に妥当かつ q の問合せ結果が空でな

いグラフデータが存在する」と q は S の下で充足可能であると本研究で提案するアルゴリズムは，部分グラフ同型問題の解法いう．このとき，問合せが充足可能であるかどうかを判定するの一つである Ullman Algorithm に判定を追加したものである．

問題を充足可能性問題という．2.2 節で述べたような ShEx に

Algorithm 3.2.1 に文献 [4] の表記に従って Ullman Algorithm

おいて，δ(t1 ) をもつノード n1 ，δ(t3 ) をもつノード n2 ，δ(t4 )を引用する．

bcをもつノード n3 が存在した際，n1 −→ n2 かつ n1 −→ n3 である
パターンはそれぞれが同時に存在することが選言「|」で接続されていることから不可能であり，充足不能となる．なお，部分グラフ同型問題は NP 困難であるため，同様に本研究の充足可能性問題も NP 困難である．

Algorithm 3.1 GENERIC QUERY PROC
Input: query graph q, data graph g
Output: all subgraph isomorphisms of q in g
1: M := ∅;2: for each u ∈ V (q) do
3:

3 提案手法C(u) := FILTERCANDIDATES (q, g, u, ...);[[∀v ∈ C(u)((v ∈ V (g)) ∧ (L(u) ⊆ L(v)))]]
4:

本章では，ShEx におけるパターン問合せの充足可能性判定
アルゴリズムについて述べる．

if C(u) = ∅ thenreturn;5:
6:

end if

7: end for3. 1 前 処 理

8: SUBGRAPHSEARCH (q, g, M, ...)

本節では，充足可能性判定の際に用いる ShEx を元に作成するグラフについて述べる．

Subroutine SUBGRAPHSEARCH (q, g, M, ...)
1: if |M | = |V (q)| then

本研究においては充足可能性の判定を行うことが目的である．

2:

report M ;したがって，充足可能性の判定においては，エッジの出現回数

3: elseは考慮する必要がないため，型の定義について，0 回以上の繰

4:

り返しを表現する「∗」，0 または 1 回の出現を表現する「?」，

1 回以上の繰り返しを表現する「+」についてはいずれも 1 回のみの繰り返しとする．さらに，[n, m] については n 回の出現

u := NEXTQUERYVERTEX (...);[[u ∈ V (q) ∧ ∀(u′ , v) ∈ M (u′ =| u)]]
5:

CR := REFINECANDIDATES (M, u, C(u), ...);[[CR ⊆ C(u)]]6:として作成する．選言「|」が存在する場合は区別のために円弧7:を描くが，選言「|」で接続されたノードが繰り返し処理の中に

8:

for each v ∈ CR such that v is not yet matched do
if ISJOINABLE (q, g, M, u, v, ...) then[[∀(u′ , v ′ ) ∈ M ((u, u′ ) ∈ E(q) ==> (V, V ′ ) ∈ E(g) ∧L(u, u′ ) = L(v, v ′ ))]]

含まれていた場合は充足可能性には影響を及ぼさないため，円弧を描かず各エッジが一本ずつ出力することとなる．例として

UPDATESTATE (M, u, v, ...);

9:[[(u, v) ∈ M ]]以下を挙げる．
型 δ(t0 ) = (a :: t1 |b :: t2 |c :: t2 )∗ から
a

b

10:

SUBGRAPHSEARCH (q, g, M, ...);

11:

RESTORESTATE (M, u, v, ...);

ct0 −→ t1 , t0 −→ t2 , t 0 −→ t2の三本のエッジが作成される

3. 2 アルゴリズム[[(u, v) ∈/ M ]]
12:

end if13:

end for

14: end if

本節では，ShEx におけるパターン問合せの充足可能性判定
アルゴリズムについて述べる．
前述のように，ShEx は修正 AND/OR グラフとして表すこ

続いて，Algorithm 3.2.2 に提案アルゴリズムを示す．
提案するアルゴリズムは Algorithm3.2.1 中に選言「|」にかとができる．したがって，もし ShEx が選言「|」を含まない

かわる判定を 3 つ追加する．1 つ目は，「FilterCandidates」後にのであれば， パターン問合せが ShEx のグラフに部分グラフ

選言「|」を含むノードを抽出する関数「BranchExtraction」でとして出現するかどうかを判定する，すなわち，部分グラフ同ある．2 つ目は，「IsJoinable」の判定内容にマッチング中のノー型問題を解くことにより，充足可能性を判定できる．しかし，

ドが選言「|」を含むノードであるか判定する関数「IsBranch-

ShEx が選言「|」を含む場合，部分グラフ同型問題をそのまま解くだけでは正しく判定を行うことができない．なぜならば，選言「|」を含むエッジを同時に選択する必要のあるパターンで問合せを行った場合，どちらか一方のエッジを採択した時点でもう一方のエッジを利用することは選言「|」によって阻害されてしまうが，使用可能であるかを判定することができず，存在
してはいけないエッジを使用してしまうことがあるからだ．そこで，部分グラフ同型問題を解くアルゴリズムを拡張することで，ShEx におけるパターン問合せの充足可能性判定ができる
ようにする．

Former」を，3 つ目は，同様の位置にマッチング中のノードと隣接するマッチング中のノードが選言「|」を含むノードであるか判定する関数「IsBranchDestination」である．

Algorithm 3.2 SATISFIABILITY DECISION
Input: query graph q, schema graph g

各関数について説明していく．

•

FilterCandidates は入出力エッジがマッチング中のパ

Output: 充足可能かどうか

ターンと一致する可能性のある，前処理で作成されたグラフ

1: M := ∅;（以下スキーマグラフ）のノード集合をもとめる関数である．

2: for each u ∈ V (q) do
3:

C(u) := FILTERCANDIDATES (q, g, u, ...);[[∀v ∈ C(u)((v ∈ V (g)) ∧ (L(u) ⊆ L(v)))]]
4:

B := BRANCHEXTRACTION (u, ...);

5:

if C(u) = ∅ then7:

end ifSubroutine SUBGRAPHSEARCH (q, g, M, ...)
1: if |M | = |V (q)| thenreport 充足可能;

3: else

5:

6:
7:

•

NextQueryVertex はパターングラフ中のノード一つを各ノードごとの集合 C(u) から順に選択される．

9: SUBGRAPHSEARCH (q, g, M, ...)

4:

ある．

した FilterCandidates を通して作成されたパターングラフの8: end for2:

BranchExtraction はスキーマグラフ中の選言「|」で分岐しているエッジの接続元であるノード集合をもとめる関数で選択し，マッチングを進めるために取得する関数である．前述

return;6:••

RefineCandidates はスキーマグラフ中の候補ノードから NextQueryVertex で取得した u よりも次数の小さい頂点を候補から外す関数である．アルゴリズムの高速化に大きく関わる関数であるが，本研究が対象とする ShEx のスキーマグラフ

u := NEXTQUERYVERTEX (...);

はサイズが極めて小さいため現時点ではあまり重要視してい[[u ∈ V (q) ∧ ∀(u′ , v) ∈ M (u′ =| u)]]

ない．

CR := REFINECANDIDATES (M, u, C(u), ...);•

IsJoinable は隣接する頂点について以降の判定を行って[[CR ⊆ C(u)]]いく関数である．u と隣接する頂点がスキーマグラフ中のいず

for each v ∈ CR such that v is not yet matched do

れのノードともマッチングしていない場合は判定をスキップしif ISJOINABLE (q, g, M, u, v, ...) then[[∀(u′ , v ′ ) ∈ M ((u, u′ ) ∈ E(q) ==> (V, V ′ ) ∈ E(g) ∧8:

L(u, u′ ) = L(v, v ′ ))]]
if ISBRANCHFORMER (q, g, M, u, v, ...) then9:

if ISBRANCHDESTINATION (q, g, M, u, v) then

10:

11:

て次の処理へと進む．マッチングしていた場合はマッチング済のノード (u′ , v ′ ) とマッチング中のノード (u, v) とを接続する
エッジが一致しているかを確認していく．

•

IsBranchFormer はマッチング中のノード v について，

UPDATESTATE (M, u, v, ...);

BranchExtraction で作成したノード集合 B 中に含まれている[[(u, v) ∈ M ]]か判定する関数である．含まれていない場合はいずれのエッジ

12:

SUBGRAPHSEARCH (q, g, M, ...);

を選択しても充足可能性は損なわれないため，次の処理へと進13:

RESTORESTATE (M, u, v, ...);

む．しかし，含まれていた場合，すでにマッチング済のノード[[(u, v) ∈/ M ]]
end if14:

end if15:
16:

end if17:

end for18:

report 充足不能;

19: end ifへと接続するエッジが選言「|」で分岐しているうちの二本以上であった場合，それらのエッジを同時に使用してはいけない
ためにマッチング中のノードは不適切であるとなるため，次のノード候補へと戻り，処理を再開させる．

•

IsBranchDestination はマッチング済のノードであり，マッチング中のノードと隣接している頂点 v ′ について，BranchEx-

traction で作成したノード集合 B 中に含まれているか判定する
2〜8 行目で，パターン問合せ q の各ノード u に対して，u関数である．含まれていない場合は，マッチング中のノードがにマッチし得る候補ノード集合 C(u) を求める．候補ノード v

加わっても充足可能性は損なわれないため，次の処理へと進む．

から選言「|」でエッジが出力されている場合，v を B に追加

しかし，含まれていた場合はほかの選言「|」で分岐している

する．9 行目で SubgraphSearch により q を再帰的に探索し，エッジを使用しているか否かの判定を行う必要がある．マッチ

パターン問合せを実行する．SubgraphSearch では 1 行目でパ

ング済でマッチング中のノードと隣接しているノードを (u′ , v ′ )ターングラフのノード数とマッチしたノード集合 M のサイズとした際，ノード v ′ から出力しているエッジ中に分岐が存在が一致しているか判定する．一致していれば「充足可能」と出していて，かつ，マッチング中のノードでないノードと接続す力し終了，不一致であれば 3 行目以降へと進む．4〜6 行目で以るエッジを使用済みであった場合，マッチング中のノードを使降の判定を行うスキーマグラフ中の候補ノード v を決定する．

用してしまうと，分岐であるに関わらず，同時に存在すること

7〜10 行目で候補ノード v が正しいか判定を行う．マッチしたになってしまうため不適切である．エッジが使用されているか場合は 11 行目で集合 M に組み合わせを追加，12 行目で再びの判定は，マッチングのために使用しようとしているエッジが，SubgraphSearch を呼び出す．マッチしなかった場合は 13 行目

使用しているまたは使用してはいけないエッジの集合 U B 中にで探索していた組み合わせを削除し，次の候補ノードを探索す

含まれているか調べることで行う．不適切であったと判明した

る．すべての候補ノードを探索し，かつ q のノード数と集合 M

場合，IsBranchFormer と同様，次のノード候補へと戻り，処のサイズが不一致であれば「充足不能」と出力し，終了する．

理を再開することになる．

•UpdateState は IsJoinable，IsBranchFormer，IsBranch

Destination をすべて適切であるという判断をなされたペア(u, v) をマッチしたペアを格納する集合 M に追加する関数である．ほかの処理として，IsBranchFormer 及び IsBranchDesti-

nation で使用したエッジ，使用したエッジと分岐していたエッジ全てを，使用しているまたは使用してはいけないエッジの集
合 U B に追加する．UpdateState によって要素を追加された
集合 M のサイズがパターングラフのノード数と一致した場合，

図 4 マッチング 1

本アルゴリズムは終了となる．

•

RestoreState はマッチしたノードの集合 M から (u, v)

を 取 り 除 く 関 数 で あ る ．IsJoinable，IsBranchFormer，Is-

BranchDestination のいずれかの関数で (u, v) がマッチしないと判断された場合はこの関数を通り，次の候補にあたることとなる.
ここからは SubgraphSearch の動きを具体的に説明を進める．
以下のような ShEx を考える．

集合 M に格納され，再び SubgraphSearch が呼び出される．
続いて，図 5 は M = {(u1 , t0 )} であり，(u2 , t1 ) のマッチングを行っている状態を示している．マッチング済みのノードとaa接続するエッジは，u1 −→ u2 と t0 −→ t1 であり，一致している
ため，IsJoinable を通過する．t1 ∈/ B であるため，IsBranch-

Former は条件に該当せずスキップとなるが，接続している t0
が t0 ∈ B であるため，IsBranchDestination にて判定を行う必δ(t0 ) = a :: t1 |a :: t2 |b :: t3

要がある．t0 から出力している分岐をもつエッジおよびノード

δ(t1 ) = b :: t3

は，t0 −→ t1 ，t0 −→ t2 ，t0 −→ t3 である．これらの中には使用

δ(t2 ) = c :: t3

済みのエッジを保存する集合である U B に含まれるものは存在

δ(t3 ) = ε

しないため t0 −→ t1 は使用してよい．マッチング中の (u2 , t1 )

a

a

b

a

上記のような ShEx を元に，前述した前処理を施して作成されるスキーマグラフは図 3 の右側のようになる．これに対する問合せとしてのパターングラフを図 3 の左側のような形とする．

の組み合わせはマッチし，集合 M に格納され，集合 U B に前述の三つのエッジを保存し，再び SubgraphSearch が呼び出される．

なお，エッジにおいて，実線で表記されたものは使用可能なもの，点線で表記されたものは使用不可なものとする．

図 5 マッチング 2

図3

マッチング

最後に，図 6 は M = {(u1 , t0 ), (u2 , t1 )} であり，(u3 , t3 ) のマッチングを行っている状態を示している．マッチング済みのb

SubgraphSearch 以前の FilterCandidates，BranchExtraction による処理によって以下の通りに集合が作成されている．

bb

ノードと接続するエッジは，u1 −→ u3 と t0 −→ t3 ，u2 −→ u3bと t1 −→ t3 であり，一致しているため，IsJoinable を通過する．t3 ∈/ B であるため，IsBranchFormer は条件に該当せず

C(u1 ) = {t0 }スキップとなるが，接続している t0 が t0 ∈ B であるため，

C(u2 ) = {t1 }IsBranchDestination にて判定を行う必要がある．t0 から出力C(u3 ) = {t3 }している分岐をもつエッジおよびノードは，t0 −→ t1 ，t0 −→ t2 ，

B= {t0 }

図 4 はマッチング済みのものを保存する M が空であり，

a

b

a

a

t0 −
→ t3 である．これらの中で，t0 −→ t1 は現時点までの処理の間に利用してしまっている．そのため他二本のエッジは同時にb(u1 , t0 ) のマッチングを行っている状態を示している．集合 M

使用不可となり，t0 −→ t3 を使用することができない場合，現在は空であるため，IsJoinable を通過する．t0 ∈ B であるため，マッチング中の (u3 , t3 ) の組み合わせは，不適当な組み合わせ

IsBranchFormer にて判定を行う必要があるが，集合 M は空となる．したがって，マッチング中の (u3 , t3 ) の組み合わせはであるため，(u1 , t0 ) は不適切な組み合わせではないといえる．

マッチ不可であり，集合 M から削除され，他候補から探索を行

IsBranchDestination は条件に該当しないためスキップされる．

おうとする．しかし今回の例の場合，候補集合の C(u3 ) = {t3 }したがって，マッチング中の (u1 , t0 ) の組み合わせはマッチし，が不適であることから他に u3 とマッチする可能性のあるノー

ドは存在しないため，充足不能と出力し終了することとなる．

図 6 マッチング 3
図 7 SP 2 Bench のデータ構造

4 評価実験
本章では，提案アルゴリズムに関する評価実験について述べる．

4. 1 概要評価実験では，始めに第 3 章で述べた提案アルゴリズムをRuby を用いて実装した．次に，SP 2 Bench で作成した RDF
データと，それを元に妥当となるように作成した ShEx それぞれのグラフを用意した．最後に，作成された RDF データグラ
フと ShEx を元にしたグラフに充足不能なパターンを作成し，問合せにかかった時間を計測した．SP 2 Bench [5] は SPARQL

図 8 DBLP と SP 2 Bench のラベルの対応関係の包括的なベンチマークソフトであり，コンピュータ科学に関する書誌学ウェブサイトのデータベースである DBLP に基づき指定したトリプル数の RDF データを作成する．図 7 にSP 2 Bench のデータ構造，図 8 に DBLP と SP 2 Bench のラベルの対応関係を示す (いずれも文献 [5] からの引用）．生成
されるデータ例として評価実験に用いたファイルの一部を図9 に挙げる．生成されるデータは，各行ごとに名前空間またはトリプルを意味する．名前空間は DBLP 固有の文書クラスを定義している．トリプルは「出力ノード ラベル 入力ノー
ド .」とそれぞれ空白で区切られた状態で記述される．具体的には「http://localhost/publications/journals/Journal1/1940

dc:title ”Journal 1 (1940)”^^xsd:string.」といったものである．
これは，http://localhost/publications/journals/Journal1/1940という URI をもつリソースのタイトルが Journal 1 (1940) であることを表している．ノードは以下 4 種類ある．
一般ノード

リソースの URI と表記されるノード

匿名ノード

先頭に「 :」を付けて表記されるノード

リテラルノード 「”」で囲まれ，末尾に XML Schema のデー
タ型を表記されるノード
クラスノード先頭に名前空間接頭辞「bench:」を付けて表記されるノード本研究においては，生成されるデータの内，名前空間を除いたトリプルを表記した行を利用して探索を行う．また，実験ではサイズが 5,400,848B，トリプル数が 10000 のものとサイズが16,228,701B，トリプル数が 50000 の 2 つの RDF データを作成し，利用した．

図 9 SP 2 Bench で作成されるグラフデータ例

前述したグラフ構造とラベルに基づいて ShEx を次のように定義する．
ここで δ(tt ) と δ(t0 ) はどちらも ε の型であるが，tt はリテ
ラルノード，t0 はクラスノードを表すため，表記を分けている．

δ(tt )= εδ(t0 ) = εδ(t1 ) = rdf : type :: t0 ||swrc : isbn :: tt ||dc : publisher ::tt ||dc : title :: tt ||(f oaf : homepage :: tt )?||dcterms :issued :: tt ||(swrc : series :: tt ||swrc : volume ::: creator :: t8 )+ ||(swrc∗
t8 ) ||(dcterms : ref erences :: t9 )?)tt )|((dc:editor::δ(t2 ) = rdf : type :: t0 ||bench : booktitle :: tt ||rdf s :seeAlso :: tt ||swrc : pages :: tt ||dc : title :: tt ||(f oaf :図 12

充足不能なパターン 3

図 13

充足不能なパターン 4

homepage :: tt )?||dcterms : issued :: tt ||(dcterms :partOf :: t1 )?||(dc : creator :: t8 )+ ||(dcterms :ref erences :: t9 )?
δ(t3 ) = rdf : type :: t0 ||swrc : number :: tt ||dc : title ::tt ||swrc : volume :: tt ||dcterms : issued :: tt ||(swrc :editor :: t8 )∗δ(t4 ) = rdf : type :: t0 ||(bench : abstract :: tt )?||(bench :cdrom :: tt )?||rdf s : seeAlso :: tt ||(swrc : month ::tt )?||(swrc : note :: tt )?||swrc : pages :: tt ||dc : title ::tt ||(f oaf : homepage :: tt )?||swrc : journal :: t3||(dc :creator :: t8)+ ||(dcterms : ref erences :: t9)?
δ(t5 ) = rdf : type :: t0 ||dc : publisher :: tt ||dc : title ::評価実験の環境は以下の通りである．

tt ||(f oaf : homepage :: tt )?||dcterms : issued ::プロセッサ

tt ||(dc : creator :: t8 )+1.60GHzδ(t6 ) = rdf : type :: t0 ||(rdf s : seeAlso :: tt )?||dc : publisher ::Intel(R) Core(TM) m3-7Y30 CPU @ 1.00GHz

主記憶 4.00 GB (3.88 GB 使用可能)

tt ||dc : title :: tt ||(f oaf : homepage :: tt )?||dcterms :OS Windows 10 Home

issued :: tt ||(dc : creator :: t8 )+使用言語

ruby 2.5.1

4. 2 結果δ(t7 ) = rdf : type :: t0 ||bench : booktitle :: tt ||swrc : pages ::tt ||dc : title :: tt ||(f oaf : homepage :: tt )?||dcterms ::issued :: tt ||(dc : creator :: t8 )+ ||(rdf s : seeAlso ::tt )?
δ(t8 ) = rdf : type :: t0 ||f oaf : name :: tt
δ(t9 ) = rdf : type :: t0 ||rdf :: : (t2 |t3 |t4 |t6 |t7 |t8 )∗前節で述べた RDF データ，ShEx，パターンを用いて充足不能なパターン問合せを行い，それぞれのグラフに対する問合せにかかる時間を計測し比較を行った．処理時間の計測は Rubyの Benchmark メソッドを使用して計測したため，測定結果のまた，実験には充足不能なパターンの問合せを行った場合の時間差を利用するため，図 10，図 11，図 12，図 13 の 4 つのようなパターンを作成した．

単位は秒である．結果を表 1 に示す．今回記載しているものは

CPU 時間である．パターン 4 の DNF は，12 時間以内に処理が終了しなかったことを表す．時間平均はパターン１から３を用いて算出している．
表1
パターン 1

図 10

充足不能なパターン 1

実行結果
パターン 2 パターン 3

パターン 4

平均

提案手法

0.00000.00000.00000.00000.0000パターン 10000

0.09400.06300.0620DNF

0.0730パターン 50000

0.10900.04700.0780DNF

0.07804. 3 考察

前節の結果を見ると，考案アルゴリズムによってサイズの小さな ShEx を元にしたグラフを探索させることで，パターン問
合せが充足不能であった場合，パターン問合せに要する時間を大幅に短縮することが可能となる．
また，部分グラフ同型問題と同様，マッチングを行うノードの順によって実行時間に差が出ることが判明した．マッチン
図 11

充足不能なパターン 2

グ不能なノードがマッチングを行う順の先頭に近ければ近いほどに充足不能であると判明するまでの時間は短くなる．さらに，マッチング不能なことが判明し，一段階マッチングする
ノードを戻した場合の候補集合が大きければ大きいほど，再探索に時間がかかることも判明した．マッチング済のものが変われば充足可能になる可能性があると期待され，探索するものの，いずれの場合も充足不可とされ戻されることが影響していると考えられる．パターンのノードが少ない場合，マッチする可能性の高いものが多々存在するため，この場合も実行時間は増える．例えば，図 13 のパターンで問合せを行った場合は，
dc:creatorn0 −−−−−−−→ n1 は充足可能であり，RDF データグラフ中に該当する部分が多くあるが，n1 とマッチングする可能性のあるノードは存在しないため，探索時間が長くなっていると考えられる．

5 む す び
本稿では，まず ShEx をグラフ化する手法を示し，それに基づいて ShEx の下でのパターン問合せの充足可能性判定を行う
アルゴリズムを提案した．具体的には，選言「|」を用いる RBEを使用する ShEx に対するパターン問合せを可能にするために
選言「|」に対応させた．また，評価実験として，RDF データ
グラフと ShEx を元に作成したグラフに対して，Ruby 言語を用いて実装した提案アルゴリズムを用いて実行時間を計測し，比較を行った．その結果，複数の充足不可能なパターン問合せ
において，RDF データグラフを探索するよりも ShEx を探索する時間が短く済むことを確認した．部分グラフ同型問題と同様，探索するグラフが大きくなると実行時間は指数関数的に増加するが，充足不能性の判定を行うことでパターン問合せの実
行時間にほぼ影響を与えずに充足可能性判定を行えることも確認した．
今後の課題として，本稿では single type semantics でのみ検討したため，multi type semansics にも対応させること，単一のパターングラフのラベル以外にも対応させること，アルゴリズムの改良が挙げられる．アルゴリズムの改良の具体案としては，部分グラフ同型問題にもある通り，高速化や効率化がある．今後は，これらの課題を解決したよりよいアルゴリズムを考案予定である．

文

献[1] World Wide Web Consortium (W3C). ”RDF Schema 1.1”.
https://www.w3.org/TR/rdf-schema/. (accessed 2018-1202).
[2] World Wide Web Consortium (W3C). ”Shape Expressions (ShEx) Primer”. http://shex.io/shex-primer/. (accessed 2018-12-02).
[3] ] J. R. Ullmann. An algorithm for subgraph isomorphism.
J.ACM, 23:3142, January 1976.
[4] Jinsoo Lee, Romans Kasperovics, Wook-Shin Han, JeongHoon Lee. ”An In-depth Comparison of Subgraph Isomorphism Algorithms in Graph Databases”. Proceedings of the
VLDB Endowment. 2012, 6, 2, 133-144.
[5] Michael Schmidt, Thomas Hornung, Georg Lausen, andChristoph Pinkel, ”SP2Bench: a SPARQL Performance
Benchmark,” Proc. ICDE, 2009, pp. 371-393.