No.1	 学位論文紹介	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  PhD	  	  	 Thesis	  	  	  	 Review,	 制約つきグラフ探索を実現する異種データベース統合技術に関する研究Heterogeneous Database Integration
MethodforConstrained
GraphSearch	 鈴木 源吾♥Gengo Suzuki	 	  本 研 究 で は ， 異 種 デ ー タ ベ ー ス 統 合 技 術 を グ ラ フ デ ー タ操 作 に 拡 張 し ，グ ラ フ 探 索 と ノ ー ド ・エ ッ ジ の プ ロ パ テ ィ に 対する制約条件とを組み合わせる，制約つきグラフ探索を可能とする手法を提案する．グラフデータベースを含む複数のデータベーススキーマを統合し，対応関係のメタデ ータを構築する．検索要求時にそのメタデータを探索し，情報源に対する問合せの組合せを決定する動的な側面と，情報源の能力に応じてグラフ探索を最適化できる点に特長がある．グラフデータベースへの探索の一部を，情報源側に適切にプッシュダウンすることで高速化することが可能である．
時間が限定されたサービスが実施されているノードを経由する最短経路問題の一種である，時間制約つき寄り道経路探索に本手法を適用し有効性を示した．

索サービス，Google	 Mapによる道路網のナビゲーションサービス等がWeb上で容易に利用可能となっている．また，最近公開されたFacebookのグラフ検索では，人の属性や関係性（例：サイクリングが好きで近くに住んでいる友達）を表す問合せによってSNSグラフを検索することができる．これらのサービスは，グラフ情報を扱う専用のデータベースであるグラフデータベースによって実現されるようになりつつある．グラフデータベースでは，情報はノードとそれをつなぐエッジ，それぞれに付与されるプロパティでモデル化され，最短経路探索等のグラフ探索，SPARQLによる知識検索，パターンマッチ等のグラフ独自処理を高速に実行することができる．	 
現在のグラフ情報利用サービスは，最短経路探索等の比較的単純なグラフ探索技術を利用することが多いが，今後はグラフに対して様々な条件を指定した経路探索の必要性が増えると考えられる．図1は，SNSに対する条件探索の例であり，「ある人と，2ホップ以内のつながりで趣味が音楽の人」までの経路を求める探索である．この場合，ノードのプロパティである「趣味」に対して，制約条件をつけて探索を行なっている．図2は，交通網と店とのつながりに関するグラフの探索であり，ノードのプロパティに対する条件として，店のカテゴリを指定しており，店の開店時間に対する時間制約も指定している（この例は，時間制約つき寄り道探索と呼んでおり，本研究の主要な応用として後に詳述する）．	
 	 
Information services using graph data havewidely been developed and used. In near futureintegrated search, which uses graph databasesand exiting databases will get more importance.
In this paper, we propose a new integrationsearch method, we call it "conditional graphsearch", which is combination of graph searchand constraint conditions on properties of nodesand edges in graphs. Our method has two merits.
First merit is a dynamic determination ofdatabases to retrieve when retrieves arerequested. Second merit is graph searchoptimization adapting abilities of information
sources. Graph search is separated to integrationside operations and information source sideoperations, and maximal operations are pusheddown to information source, and it improvessystem performance. We adapted this method to"time constrained trip planning search" andshowedefficiency under distributed graphdatabases.	 

1. はじめに交通検索・地図検索・SNS検索等でグラフ情報を活用するサービスが，近年多く開発され実用化されている．交通・地図検索としては駅探のような鉄道路線検索やバス路線の検図 1 制約つきグラフ探索：SNS の条件探索Fig.1 Graph Search Example: SNS search図 2 制約つきグラフ探索：時間制約つき寄り道探索
Fig.2 Graph Search Example: trip planningsearchこのような，グラフのノードとエッジのプロパティに対して条件を指定するグラフ経路探索を，「制約つきグラフ探索」会員	  NTT ソフトウェアイノベーションセンタsuzuki.gengo@lab.ntt.co.jp♥1-1	 日本データベース学会	  	  	  	  	  	  	 	 	 	 	 	 	 	 	 学位論文紹介	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  PhD	  	  	 Thesis	  	  	  	 Review,	  	  	  No.1と呼ぶこととする．制約つきグラフ探索は，本論文で定義した用語であり，過去に一般的に用いられているものではない．
その定義は次章で示しているが，その基本的特徴は以下の3つである．
!
対象データはグラフ：座標の集まりではなく，ノードとエッジであり，軌跡探索などの地理情報的なモデルではない．
!
グラフ上のコストで評価：エッジのプロパティとしてコスト（時間・距離等）を与える．ユークリッド距離（座標間の距離）による評価ではない．
!
探索は経路探索：プロパティで指定した制約を満たす「経路」を求める．グラフのパターンによる探索（例：化学構造探索）は対象外である．
制約つきグラフ探索では，グラフのノード・エッジ情報と制約条件のプロパティは，複数の情報源にまたがることが多い．例えば，レストラン情報と交通情報，SNSのつながりとレビューサイトのカテゴリ情報，ネット上のRDF情報と社内DB等があげられる．これらの情報源を組み合わせることによって，制約つきグラフ探索を実現する必要があるが，既存次世代のグラフデータベース活用サービスの確立に向けた，制約つきグラフ探索の異種分散データベース環境での実現の情報源とグラフデータベースは，そもそも組み合わせて連携することを前提に設計されていない．よって，これらの情報源・データベースは分散して様々な異種性を持っていることがほとんどである．
そこで本研究では以下を研究目標とし，そのイメージを図3 に示す．

この研究目標を実現するために，以下の2つの課題がある．	 
[課題1：スキーマ間の異種性解消と統合]	 独立して設計された情報源には，情報の構造・表現形式・命名に違い（異種性）がある．その違いを解消しつつデータ統合検索を実現する必要がある．その異種性を解消するための，複数の情報源の突き合わせ（スキーマ統合）には多大な稼働がかかり，完全自動化が困難であることが知られている[1]．その稼働削減には，適切なモデル化・支援方式・ツールがあることが望ましい．しかし，グラフデータベースは新しい情報源であり，そのスキーマ統合手法は未確立である．	 
[課題2：情報源能力のばらつきに対応した問い合わせ処理]	 グラフ利用サービスが発展途上であるため，グラフデータベースの機能はまだ確立しておらず流動的である．よって，グラフデータベースには，RDBにおけるSQLのような標準言語が存在しない，また，Web経由でサービスが提供されるケースが多いため，そのポリシーによってすべてのグラフ探索APIが公開されるとも限らない．これらの理由から，グラフデータベースを利用する情報源には，グラフ探索できる能力にばらつきがある．よって，制約つきグラフ探索システムは，このようなばらつきを考慮しつつユーザからの要求を適切に，情報源による探索処理（情報源側処理）と制約つきグラフ探索システム内部の処理（データ統合側処理）に分解して，処理する必要がある．グラフ探索処理は，頻繁にノード・エッジにアクセスすることが一般的であるために，できるだけ情報源側へ処理を移譲するような最適化が望ましい，今後，グラフ探索処理の分担を説明するときに，この「情報源側」「データ統合側」という用語を用いることとする．また，グラフ利用サービスは，探索サービスの内容や利用する項目の頻繁な変更が多いため，その能力のばらつきも変化が大きい．
よって，スキーマ変更への追随が容易な方式が望ましい．	 	
 3. 提案手法図 3 本研究の目標Fig.3 This research’s goal様々なグラフデータと既存情報源が分散して存在するときに，それらを統合検索できる制約つきグラフ探索システムが，ユーザからのSNS条件探索，寄り道探索等の様々な問い合わせ要求に対し，探索結果を求めることができる．制約つきグラフ探索システムは，ユーザ要求から探索できる情報源を探して特定し（問い合わせ変換機能），問い合わせを分解して，様々なグラフ情報と非グラフ情報に対して探索・問い合わせ要求を発行し，その結果を組み合わせ，情報の違いを統一しユーザに返却する（問い合わせ実行機能）．

2. 研究の課題これらの課題の解決のために，本論文では，2 つの手法を提案する．
まず，データ統合に必要な，データ項目と概念の対応関係・概念同士のつながり・概念とデータ項目の表現形式対応のメタデータを効率的に構築するために，概念グラフを用いたスキーマ統合技術[2][3]を確立した（手法 1）．このスキーマ統合技術は，グラフデータベースを含む様々な情報源スキーマを「概念グラフ」と呼ばれるモデルに変換して異種性を解消することが特徴である．概念グラフは，ER モデル等と比較して，データモデル構成要素が少ないため，同じ意味を異なる構造で表現する異種性である構造異種性を回避しやすいことが特長である．また，データ項目が一定のルールで標準的に構造化されている場合に，データ項目を複数の概念に分解し，マッチングを増すことができる．概念間の類似度計算法を組み込んだスキーマ統合支援ツールを実現することにより，スキーマ統合稼働の削減の可能性を示し，課題 1を解決した．
次に，動的に異種性解消するデータ統合検索技術（手法 2）[4][5]を確立した．利用側の要求とデータベースの構造を事前に SQL 等の言語によって固定的に結びつけるのではなく，検索要求時に情報源の所在や表現形式等のメタデータを探索して，検索要求に答えることのできる情報源への問合せの組合せ（問合せ候補と呼ぶ）を生成し，動的に命名・構造・表現の異種性を解消する．そのイメージを図 4 に示す．メタ1-2	 日本データベース学会	  	  	  	  	  	  	 	 	 	 	 	 	 	 	 学位論文紹介	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  PhD	  	  	 Thesis	  	  	  	 Review,	  	  	  No.1データ層で情報源を抽象化することによって動的な検索を実現ため，サービス変更に柔軟な動的な特性を持つ．問合せ候補生成には，既存の情報源のスキーマを統合した統合概念グラフを利用する．ユーザの要求を，統合概念グラフのどの概念に対応するかを特定し，その概念間のつながりを探索する．探索結果と概念とデータベースの対応情報を利用することによって情報源への問合せを生成することができる．

囲が動的導出法に比べて広いことを示した[8]．

図 4 動的なデータ統合検索のイメージ図 5 データの分散パターンFig.4 Dynamic data integration retrievalFig.5 Patterns of data distributionさらに，このデータ統合検索技術では，制約つきグラフ探索の能力を階層的にモデル化することにより，ばらつきのある情報源が処理できる能力を考慮し，情報源側に適切なプッシュダウンを行うことが可能である．制約つきグラフ探索の複雑さが増すほど，多くのデータ項目を利用する点に着目し，適切な検索候補の生成法を明らかにした．この技術により課題 2 が解決できる．
これら 2 つの提案手法の有効性を示すために，制約つきグラフ探索の一例として時間制約つき寄り道探索を提案・定式化し，提案手法を適用した．時間制約つき寄り道探索は，利用者の時間制約（例：門限）とサービス側の時間制約（例：開店時間）を満たす条件で，指定したサービス（例：店の開店）を持つノードを経由する最短経路を求める探索である[6][7]，道路・鉄道等の交通路に関するデータベースと，店・開店時間等のサービスに関するデータベースは分散し独立して構築されている場合が多く，また，交通路情報が比較的安定であることに比べ，サービス情報は追加や変更が多いという特長を持つために，提案手法が有効な典型的な例となっている．
まず，単一データベースにおける探索結果の導出手法を明らかにした．時間制約のない寄り道探索結果を求める既存手法である逐次拡大法の結果に対して，制約条件をチェックする手法である基本導出法と，制約条件のチェックをできるだけ早期に行い，探索の枝刈りを行う動的導出法を確立した．
さらに単一グラフデータベース構成における評価を行い，動的導出法が有利であることを示した．
異種分散データベース環境に拡張するために，時間制約つき寄り道探索の処理を分解し，情報源の能力のバリエーションを定義した（レベル 1 からレベル 3）．交通情報とサービス情報のデータ分散形態を整理し（図 5），基本導出法・動的導出法を用いた場合，本手法を適用してプッシュダウンを含む問合せ戦略を得ることができる（図 6，図 7）．その問合せ戦略（図 8）を，分散グラフデータベース環境における実験で評価し，プッシュダウンが有効になる基本導出法の有効範図 6 情報源側への処理プッシュダウン：基本導出法Fig.6 Push down of basic method図 7 情報源側への処理プッシュダウン：動的導出法Fig.7 Push down of dynamic method1-3	 日本データベース学会	  	  	  	  	  	  	 	 	 	 	 	 	 	 	 学位論文紹介	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  PhD	  	  	 Thesis	  	  	  	 Review,	  	  	  No.1図 8 最適化観点の組み合わせと情報源側の処理Fig.8 Combination of viewpoints and informationsource side processing4. おわりに本手法の適用範囲について考察する．本手法は，グラフ探索処理を Web インターフェースとして仮想化されている場合に，一般的に利用できると言える．本論文では，寄り道探索の POI は一箇所という仮定であったが，それが複数箇所になった場合でも適用は可能である．グラフ探索は，そのパラメータ指定はノードやそのプロパティであることが多いため，適用範囲は広い．また，処理のプッシュダウン制御によって，仮に情報源側で高度な能力を持っていない場合でも，基本能力が公開されていれば，基本能力を利用して，データ統合側で高度な能力を使うことによって，論理的にはすべてのグラフ処理を行うことが可能になる（グラフ探索は基本能力の組み合わせで実現できる）．ただし，実験結果に示したように実用的な性能を得ることは難しい．
ただし，本手法は情報源の仮想化は関係モデルによっている．寄り道探索の返却結果は，経路情報を JSON 等の文字列で返却されることが想定されている．この文字列を分解し，必要な情報を取り出す処理は利用者（データ統合検索の開発者）側で実施する必要がある．経路情報の表現形式変換関数も利用者責任で作成する必要がある．また，グラフ類似検索・軌跡検索のようにグラフをパラメータとして渡す場合，それらを文字列等に変換して情報源側に渡せば適用は可能であるが，項目の対応を基礎としている本手法のメリットは必ずしも生かせない．
また，本手法は，情報源を跨るグラフ探索には対応できていない．情報源を跨るデータ統合処理は，関係演算である結合と和に限られている．例えば，鉄道網の最短経路探索が各鉄道会社毎に構築されているとき，それぞれの路線に閉じた最短経路を求め和として返却することは可能であるが，両社の路線を辿って検索する結果を求めることができない．このような分散的なグラフ探索は問題としては難しく，個別の探索毎に有効な手法も異なるため，一般的な異種分散データベースのフレームワーク内で整理するのは，今後の課題である．
本手法は，例えば，情報源にない階層カテゴリを付加して寄り道探索を行うなど，単一情報源では実現できないデータ統合検索を容易に実現することができる有用な手法であって，最適化制御の考え方も導入したグラフデータベースを統合検索するための基本的ではあるが重要な一歩である．

schema integration, ACM Computing Survey, Vol.18, No.
4, pp.323-364 (1986).
[2] 山室雅司，鈴木源吾：データ標準化と概念グラフへの変換を利用したスキーマ統合支援法，電子情報通信学会論文誌 D-1 Vol.J79-D-I No.11 pp.966-974 (1996).
[3] Suzuki, G. , Yamamuro, M. : Schema IntegrationMethodology Including Structural Conflict Resolutionand Checking Conceptual Similarity - ConceptualGraphs Approach - , International Workshop onDatabaseReengineeringandInteroperability,pp.229-242 (1995).
[4] Honishi, T. , Suzuki, G. , Kobayashi, N. , Konishi, K. :A Mediation System Based on Universal RelationModeling, 20th International Conference on ConceptualModeling Proceedings (ER2001), SE3, pp.1-4 (2001).
[5] Suzuki, G. , IIzuka, Y. , Kasuga, S. : Integration ofKeyword Bases Source Search and Structure BasesInformation Retrieval, 7th International CODATAConference, pp.149-158 (2000).[6] 鈴木源吾，榎本俊文，小林伸幸，山室雅司，鬼塚真：時間制約をもつ寄り道経路探索システムの実現と評価，情報処理学会論文誌 Vol.53 No.2 pp.857-867(2012).
[7] 大沢裕，藤野和久：前処理を必要としない道路ネットワーク上での最短寄り道経路探索アルゴリズム，電子情報通信学会論文誌 D， Vol.J93-D, No.3, pp. 203--210 (2010).
[8] 鈴木源吾，鬼塚真，榎本俊文，小林伸幸：制約つきグラフ探索を実現する異種データベース統合技術，情報処理学会研究報告 2013-DPS-154 (2013).

鈴 木 源 吾 Suzuki GENGO1990 年東北大学大学院理学研究科修士課程修了．同年日本電信電話株式会社入社．データベース設計，マルチデータベースシステム，XML データ管理，グラフデータ管理等の研究開発に従事．電子情報通信学会，日本データベース学会各会員．

[文 献 ][1] Batini, C. , Lenzarini, M. , Navathe, S.B. : AComparative analysis of methodologies for database1-4	 日本データベース学会