異種情報源の統合を支援するシステムの実現

DEIM Forum 2016 E6-2
異種情報源の統合を支援するシステムの実現
寺川 文乃
宝珍 輝尚
野宮 浩輝
京都工芸繊維大学 〒606-8585 京都府京都市左京区松ヶ崎橋上町
E-mail: {hochin, nomiya}@kit.ac.jp
あらまし これまでに，異種情報源の統合を目的として，異種情報源統合システムを試作してきた．このシステ
ムにはメモリ使用量が多いことと，GUI も含めたシステムになっており汎用性が高くない，という問題があった．
本論文では，メモリ使用量の問題を，結合結果のサイズ推定式を用いて適切な結合順序を決定することによりメモ
リ使用量を削減し解決する．そして，GUI も含めたシステムになっており汎用性が高くないという問題を，異種情
報源の統合機能を持つ Java Database Connectivity(JDBC)を作成し，GUI 部分と分離することで解決する．実機による
評価の結果，結合操作の実行時間を増やすことなく，メモリ使用量の大幅な削減ができることを示す．
キーワード 異種情報源，JDBC，統合処理
1. は じ め に
コンピュータ技術の発展と普及により，自身の所持
するデータを電子媒体としてコンピュータ上で取り扱
実 現 し た [3]．し か し ，こ の シ ス テ ム に は メ モ リ 使 用 量
が 多 い こ と と ， GUI も 含 め た シ ス テ ム に な っ て お り 汎
用性が高くない，という問題があった．
うユーザが増えてきた．考古学者もその内の 1 人であ
そこで本論文では，このシステムのメモリ使用量の
る．彼らも自身の所持する考古学データを電子媒体と
問題を，結合結果のサイズ推定式を用いて適切な結合
し ，コ ン ピ ュ ー タ 上 で 取 り 扱 う よ う に な っ て き て い る ．
順序を決定することによりメモリ使用量を削減し解決
多くの場合，考古学者は自らの判断でどのデータベ
す る ． ま た ， GUI も 含 め た シ ス テ ム に な っ て お り 汎 用
ースまたはファイルにデータを蓄積するかを決定する．
性が高くないという問題を，異種情報源の統合機能を
従 っ て ，デ ー タ は 統 一 の シ ス テ ム に 蓄 積 さ れ て い な い ．
持 つ JDBC を 作 成 し ， GUI 部 分 と 分 離 す る こ と で 解 決
このようにして格納されたデータは異種情報源となる．
する．また，実機による評価の結果，結合操作の実行
異種情報源を統合利用する一つの方法は，データベ
時間を増やすことなく，メモリ使用量の大幅な削減が
ースのデータを別のデータベースに変換する方法であ
る ．し か し ，デ ー タ 変 換 は 変 換 の 手 間 が か か る ．ま た ，
できることを示す．
以 降 ， 2.で 筆 者 ら が 以 前 作 成 し た 異 種 情 報 源 統 合 シ
データ変換は，元データが頻繁に変更される場合，整
ス テ ム に つ い て 述 べ ， 3.で 今 回 作 成 し た 統 合 支 援 シ ス
合性の維持が困難である．
テ ム に つ い て 述 べ る ． 次 に ， 4.で メ モ リ 使 用 量 の 計 測
ラ ッ パ ー と メ デ ィ エ ー タ に 基 づ く シ ス テ ム [1]は ，デ
実 験 と そ の 結 果 に つ い て 述 べ ， 最 後 に 5.で ま と め る ．
ータを変換することなく異種情報源の統合を可能にす
る．ラッパーはアプリケーション固有のクエリをソー
2. 異 種 情 報 源 統 合 シ ス テ ム
ス特有のコマンドやクエリに変換することで異種情報
著 者 ら は Java と JDBC を 使 用 し ， 3 種 類 の デ ー タ ベ
源へのアクセスを供給する．メディエータは異種情報
ー ス MySQL， PostgreSQL， SQLite， 2 種 類 の フ ァ イ ル
源を統合するために使われる．この方法はネットワー
Excel，CSV へ の 同 時 接 続 を 行 い ，テ ー ブ ル の 等 結 合 お
ク上に分散している異種情報源を前提としている．そ
よび射影を行う異種情報源統合システムを実現した
のため，異種情報源はサーバコンピュータ上にある必
[3]． こ の シ ス テ ム で は ， JDBC を 用 い て デ ー タ ベ ー ス
要 が あ る ． し か し ， 考 古 学 者 に は PC の サ ー バ 化 は 困
や フ ァ イ ル へ の 接 続 を 行 う た め に 必 要 な 情 報 ，お よ び ，
難 な こ と が 多 い ． ま た ， 行 い た い の は ， 一 台 の PC 中
結合条件の入力，実行結果の出力を全て 1 つのウィン
の異種情報を扱うことである．
ドウで行う．このウィンドウを図 1 に示す．
王 ら [2] は ユ ー ザ の デ ー タ を サ ー バ に コ ピ ー す る こ
処理の流れを図 2 に示す．まず初めに入力された結
と な く ，様 々 な 情 報 源 を 使 う こ と が で き る よ う に し た ．
合条件を分解し，各データベースやファイルに合わせ
MySQL， PostgreSQL， SQLite， Excel フ ァ イ ル ， CSV
たクエリに変更する．次に，各データベースやファイ
フ ァ イ ル を Java Database Connectivity(JDBC)を 通 し て
ルへの接続を行い，テーブルのスキーマ情報の取得を
コネクションを作ることで，データベースとファイル
行った後，使用するテーブル，カラムがあるかの照合
を統一の方法で使うことができる．
を行う．そして，結合に必要なデータの取得を行う．
筆者らはデータの変換，計算機のサーバ化，統合サ
次に，どのテーブルのカラムかを判別できるよう，テ
ーバへのコピーを行わない異種情報源統合システムを
ーブル名を付与する．そして，結合操作を行う．結合
図 1
情報入出力ウィンドウ
3. 統 合 支 援 シ ス テ ム
2.で 述 べ た 異 種 情 報 源 統 合 シ ス テ ム に お け る ， メ モ
リ使用量が多いという問題を，結合結果のサイズ推定
と left-deep tree[5]を 用 い て ， メ モ リ 使 用 量 を 削 減 し 解
決 す る ． こ れ ら に つ い て は 付 録 で 概 説 す る ． ま た ， 2.
で 述 べ た 異 種 情 報 源 統 合 シ ス テ ム は GUI も 含 め た シ ス
テムになっており汎用性が高くない．そこで，異種情
報 源 の 統 合 機 能 を 持 つ JDBC を 作 成 し ， GUI 部 分 と 分
離することとする．
3.1. データ操 作 処 理
3.1.1. 設 計
(1)
結合処理
以前のシステムではユーザから入力されたクエリ
を前から順になぞり結合操作を行うものであった．ま
た ，全 テ ー ブ ル デ ー タ を ArrayList に 格 納 し ，シ ス テ ム
内部で保持していた．この中には一度結合操作に使用
図 2
異種情報源統合システムにおける処理の流れ
し，二度と参照されないデータも含まれていた．ユー
ザが必要としているのは全ての結合操作が完了した最
操 作 に は ソ ー ト・マ ー ジ 結 合 [4]を 使 用 し ，結 合 後 の サ
イズが分からないことから，データの管理には
ArrayList を 用 い て い る ．最 後 に ，射 影 を 行 う 場 合 は 射
影をし，結果をウィンドウに出力する．
実 機 に よ る 性 能 評 価 を 行 い ， 100,000 行 の 3 テ ー ブ
ルの結合は実用上問題ない時間で処理できることを確
認した．
し か し ， メ モ リ 使 用 量 が 多 い こ と と ， GUI も 含 め た
システムになっており汎用性が高くないという問題が
残った．
終結果である．
そ こ で ， 本 シ ス テ ム で は left-deep tree を 採 用 す る こ
とにより，結合操作に使用するテーブルを 1 度の参照
で済ませる．また，結合操作の過程でできるリレーシ
ョン（中間リレーション）のサイズを抑えるため，式
（ A.1）を 用 い て ，中 間 リ レ ー シ ョ ン の サ イ ズ が 最 小 に
なる結合順序を導き出す．
システム内部の処理の流れは図 2 に上記の操作を加
えたものであり，図 3 に示す．
テ ー ブ ル の 情 報 を あ ら か じ め ArrayList に 保 持 す る 必
要がなくなった．本システムではソート・マージ結合
を採用しているため，初めに結合操作で使用する結合
列 で ORDER BY す る こ と に よ り ， 直 接 ResultSet か ら
情報を抽出できる．しかし，本システムで採用してい
る Excel， CSV の JDBC は ORDER BY 句 に 対 応 し て い
な い た め ，Excel，CSV フ ァ イ ル の 場 合 は ，ソ ー ト す る
た め に ResultSet か ら ArrayList に デ ー タ を 取 り 出 す 必
要がある．
3.2. JDBC 化
3.2.1. 設 計
本 JDBC で は 複 数 デ ー タ ベ ー ス へ の コ ネ ク シ ョ ン を
持つ必要があり，そのためには複数データベースへの
接続情報を登録・保持するクラスが必要である．その
た め ，JDBC の 基 本 ク ラ ス [7]で あ る Connection ク ラ ス ，
Statement ク ラ ス ，ResultSet ク ラ ス の 他 に ，接 続 情 報 を
保 持 す る JDBC ク ラ ス を 作 成 す る ．
ま た ，各 デ ー タ ベ ー ス へ の 接 続 情 報 に alias を 設 定 す
ることで，同じ種類のデータベースでも複数登録がで
き る よ う に す る ．ユ ー ザ は 登 録 し た alias を 用 い て 問 い
図 3
統合支援システムにおける処理の流れ
合わせを行うことになる．
JDBC ク ラ ス が 持 つ public な メ ソ ッ ド を 表 1 に 示 す ．
(2)
集合演算処理
次に，集合演算を行うためにはあらかじめタプルが
ソ ー ト さ れ て い る と 都 合 が 良 い [6]．ま た ，集 合 演 算 に
おいて，最大で両リレーションのタプル数の和の結果
を 保 持 す る 必 要 が あ り ，メ モ リ 量 の 不 足 が 考 え ら れ る ．
そこで，集合演算を実行するためには，以下の条件を
設ける．
条 件 1.
接 続 情 報 を 複 数 登 録 ・ 保 持 す る JDBC ク ラ ス を 実 装
す る ．表 1 に 示 し た 各 接 続 情 報 を 登 録・削 除 す る public
メソッドを実装する．ユーザは上記のメソッドで登録
し た alias を 用 い て 問 い 合 わ せ を 行 う こ と に な る ．シ ス
テ ム は こ れ 以 降 の 全 て の 動 作 に お い て ，alias を 用 い て
各データベースを判断する．そのため，同じインスタ
複数データベースの等結合を行うクエリ同
士の集合演算の実行は不可とする．
条 件 2.
3.2.2. 実 装
Excel， CSV フ ァ イ ル に 関 し て は ， あ ら か じ
め集合演算を行うカラムの順にソートしている
ものとする．
条 件 3.
ク エ リ を ()で く く る こ と は 不 可 と す る ．
条 件 4.
集合演算子の混合は不可とする．
条件 1 は複数データベースの等結合を行った最終結果
を複数持つことで，メモリ使用量が増大してしまうこ
とを防ぐためである．条件 2 は，システム内部で使用
し て い る Excel と CSV の JDBC が ソ ー ト に 対 応 し て い
ないためである．条件 3 は，クエリの構文に制約を加
えることで，クエリ分解時の処理数を減らすためであ
る．条件 4 は，条件 3 より集合演算の優先順位を指定
することができないためである．
3.1.2. 実 装
本 シ ス テ ム に お い て ， left-deep tree を 採 用 す る こ と
で，結合操作に使用するテーブルは 1 度参照するだけ
で済むようになった．そのため，結合操作に使用する
ン ス 内 で は 同 じ alias 名 を 登 録 す る こ と は で き な い ．
ま た ， 本 JDBC で は 問 い 合 わ せ を 行 う 場 合 ，
「 <Alias>:<TableName>.<ColumnName>」の 形 式 で 入 力
す る 必 要 が あ る ． 各 要 素 を 区 分 す る た め に “:”を 用 い
て い る た め ， alias に は “:”を 使 用 で き な い ．
3.2.3. 使 用 例
(1) で は JDBC を 使 用 す る 際 の 接 続 情 報 の 登 録 ・
Statement の 作 成 ，Connection の 作 成 例 を 示 し ，(2)で は
結 合 を 行 う 場 合 の 使 用 例 ，(3)で は 集 合 演 算 を 行 う 場 合
の仕様例を示す．
(1)
JDBC の 使 用 例
本 JDBC の 使 用 例 を 図 4 に 示 す ．図 4 で は ，1 行 目 で ，
JDBC ク ラ ス の イ ン ス タ ン ス を 作 成 し て い る ． 2 ~ 4 行
目で接続情報を登録している．これによりインスタン
ス jdbc は alias が “M1”， “S1”， “S2”で あ る 接 続 情 報
を 保 持 す る ． 5 行 目 で 登 録 し た 接 続 先 へ の connection
を 持 つ Connection ク ラ ス の イ ン ス タ ン ス を 作 成 し て い
る ．6 行 目 で Statement ク ラ ス の イ ン ス タ ン ス を 作 成 し
ている．
表 1
JDBC ク ラ ス の 持 つ public な メ ソ ッ ド
メソッドの概要
返り値
説明
boolean
set_MySQL(String dbname, String host, String username, String pass, String alias)
指 定 さ れ た デ ー タ ベ ー ス ，ホ ス ト ，ユ ー ザ 名 ，パ ス ワ ー ド ，alias で MySQL の 接 続 情 報 を 登 録 す
る メ ソ ッ ド ． 接 続 で き な い 場 合 ， SQLException を 返 す ． ま た ， alias が 既 に 登 録 さ れ て い る も の
と 同 じ 場 合 は SQLException を ， 未 登 録 の 場 合 true を 返 す ．
boolean
set_PostgreSQL(String dbname, String host, String username, String pass, String alias)
指 定 さ れ た デ ー タ ベ ー ス ， ホ ス ト ， ユ ー ザ 名 ， パ ス ワ ー ド ， alias で PostgreSQL の 接 続 情 報 を 登
録 す る メ ソ ッ ド ． 接 続 で き な い 場 合 ， SQLException を 返 す ． ま た ， alias が 既 に 登 録 さ れ て い る
も の と 同 じ 場 合 は SQLException を ， 未 登 録 の 場 合 true を 返 す ．
boolean
set_SQLite(String dbname, String location, String alias)
指 定 さ れ た デ ー タ ベ ー ス ，位 置 ，alias で SQLite の 接 続 情 報 を 登 録 す る メ ソ ッ ド ．alias が 既 に 登
録 さ れ て い る も の と 同 じ 場 合 は SQLException を ， 未 登 録 の 場 合 true を 返 す ．
boolean
set_DB2(String dbname, String host, int port, String username, String pass, String alias)
指 定 さ れ た デ ー タ ベ ー ス ， ホ ス ト ， ポ ー ト 番 号 ， ユ ー ザ 名 ， パ ス ワ ー ド ， alias で DB2 の 接 続 情
報 を 登 録 す る メ ソ ッ ド ． 接 続 で き な い 場 合 ， SQLException を 返 す ． ま た ， alias が 既 に 登 録 さ れ
て い る も の と 同 じ 場 合 は SQLException を ， 未 登 録 の 場 合 true を 返 す ．
boolean
set_Excel(String filename, String location, String alias)
指 定 さ れ た フ ァ イ ル 名 ，位 置 ，alias で Excel の 接 続 情 報 を 登 録 す る メ ソ ッ ド ．alias が 既 に 登 録 さ
れ て い る も の と 同 じ 場 合 は SQLException を ， 未 登 録 の 場 合 true を 返 す ．
boolean
set_CSV(String location, String alias)
指 定 さ れ た 位 置 ，alias で CSV の 接 続 情 報 を 登 録 す る メ ソ ッ ド ．alias が 既 に 登 録 さ れ て い る も の
と 同 じ 場 合 は SQLException を ， 未 登 録 の 場 合 true を 返 す ．
boolean
remove_DB(String alias)
指 定 さ れ た alias で 登 録 さ れ た 接 続 情 報 を 探 し ， 登 録 情 報 か ら 削 除 す る メ ソ ッ ド ．
接 続 情 報 が 存 在 す る 場 合 は true， 存 在 し な い 場 合 は SQLException を 返 す ．
Connection createConnection()
上 記 の メ ソ ッ ド で 事 前 に 設 定 し た 接 続 情 報 を 用 い て ， 各 RDBMS・ フ ァ イ ル へ の 接 続 を 行 う メ ソ
ッ ド ． 接 続 で き た 場 合 ， Connection オ ブ ジ ェ ク ト ， 接 続 で き な い 場 合 ， SQLException を 返 す ．
1:
JDBC jdbc = new JDBC();
2:
jdbc.set_MySQL(“testdb”, “localhost”, “testuser”, “test”, “M1”);
3:
jdbc.set_SQLite(“testdb”, “/Users/Test”, “S1”);
4:
jdbc.set_SQLite(“testdb2”, “/Users/Test/Document”, “S2”);
5:
Connection con = jdbc.createConnection();
6:
Statement stmt = con.createStatement();
7:
jdbc.remove_DB(“S1”);
8:
jdbc.set_Excel(“test.xlsx”, “/Users/Test/Desktop”, “E1”);
9:
Connection con2 = jdbc.createConnection();
10:
Statement stmt2 = con2.createStatement();
11:
ResultSet rs1 = stmt.executeQuery(“select * from M1:test, S1:test where M1:test.id = S1:test.id”);
12:
ResultSet rs2 = stmt2.executeQuery(“select S2:test.tid, S2:test.tname from S2:test UNION select M1:test.id,
M1:test.name from M1:test);
図 4
JDBC の 使 用 例
結 合 演 算 の 問 い 合 わ せ 文 … 「 select <SELECT_LIST> from <TABLE_LIST> where <WHERE>」 —①
<SELECT_LIST>… 「 <Alias>:<TableName>.<ColumnName>, <Alias>:<TableName>.<ColumnName>, …」 or「 *」
<TABLE_LIST>… 「 <Alias>:<TableName>, <Alias>:<TableName>,…」
<WHERE>… 「 <Alias>:<TableName>.<ColumnName> = <Alias>:<TableName>.<ColumnName> (AND ...)」
※ 複 数 条 件 の 場 合 AND で 条 件 を 繋 ぐ ．
図 5
結合演算を行う場合の問い合わせ構文
集 合 演 算 ・ 和 の 問 い 合 わ せ 文 … 図 5 の ① UNION 図 5 の ① UNION …
集 合 演 算 ・ 積 の 問 い 合 わ せ 文 … 図 5 の ① INTERSECT 図 5 の ① INTERSECT 図 5 の ① INTERSECT …
図 6
集合演算を行う場合の問い合わせ構文
また，接続情報を削除する例を続いて示す．7 行目
カ ラ ム loc に は 長 さ 40 の ラ ン ダ ム な 文 字 列 が 入 る ．
5)
Excel の シ ー ト の 仕 様 を 以 下 に 示 す ．
の よ う に remove_DB()メ ソ ッ ド を 使 用 し 接 続 情 報 を 削
除 し て い る ．こ れ に よ り ，イ ン ス タ ン ス jdbc か ら alias
1)
行数は 5 行．
が “S1”で あ る 接 続 情 報 が 除 去 さ れ る ． 次 に ， 8 行 目 で
2)
カ ラ ム は id， evaluate， test を 持 つ ．
alias が “E1”で あ る 接 続 情 報 を 新 た に 追 加 し て い る ．こ
3)
カ ラ ム id に は 1 か ら 5 の 数 が 昇 順 に 入 る ．
れ に よ り ， イ ン ス タ ン ス jdbc は alias が “M1”， “S2”，
4)
カ ラ ム evaluate に は 長 さ 3 も し く は 4 の 文 字 列 が
入る．
“E1”で あ る 接 続 情 報 を 保 持 す る ． 9 行 目 で 登 録 し た 接
続 先 へ の connection を 持 つ Connection ク ラ ス の イ ン ス
タンスを作成している．
(2)
結合
カ ラ ム test に は 2， 3， 5 の 整 数 が 1 つ 入 る ．
5)
CSV フ ァ イ ル は ， Excel の カ ラ ム test を 除 い た も の
で構成される．全テーブルはインデックス付けを行っ
結合演算を行う場合の問い合わせ文の形式を図 5 に示
て い な い ．MySQL，PostgreSQL，SQLite の テ ー ブ ル は
す ．<Alias>は 事 前 に 登 録 し た alias，<TableName>は テ
プログラムで作成した．
ー ブ ル 名 ， <ColumnName> は カ ラ ム 名 を 表 す ． 結 合 演
結 合 条 件 は 前 か ら 順 に MySQL，PostgreSQL，SQLite，
算 を 行 う 場 合 の 例 を 図 4 の 11 行 目 に 示 す ．こ こ で は 事
Excel，CSV の 順 に 結 合 す る よ う に 書 く こ と と し ，カ ラ
前 に 登 録 し た alias が M1 で あ る MySQL と S1 で あ る
ム id で 等 結 合 を 行 う も の と す る ．こ れ に よ り ，旧 シ ス
SQLite の 等 結 合 を 行 っ て い る ．
テ ム で は 結 合 条 件 を 前 か ら 順 に 実 行 す る た め ，MySQL
(3)
集合演算
（ 10,000 行 ） と PostgreSQL（ 10,000 行 ）， そ の 結 果 と
集合演算を行う場合の問い合わせ文の形式を図 6 に示
SQLite（ 10,000 行 ），そ の 結 果 と Excel（ 5 行 ），そ の 結
す．和集合を求める場合は図 5 で示した問い合わせ文
果 と CSV（ 5 行 ） の 順 に 結 合 を 行 う ． つ ま り ， 中 間 リ
を 「 UNION 」 で 繋 ぎ ， 積 集 合 を 求 め る 場 合 は
レ ー シ ョ ン の サ イ ズ 推 移 は 10,000 行 ，10,000 行 ，5 行 ，
「 INTERSECT」 で 繋 ぐ ． 和 集 合 を 求 め る 例 を 図 4 の
5 行となる．新システムでは中間リレーションが小さ
12 行 目 に 示 す ．こ こ で は 事 前 に 登 録 し た alias が S2 で
くなるような結合順序で結合を行うため，中間リレー
あ る SQLite の テ ー ブ ル test の カ ラ ム tid，tname と alias
ションのサイズ推移は 5 行，5 行，5 行，5 行となる．
が M1 で あ る MySQL の テ ー ブ ル test の カ ラ ム id，name
実 験 1.
システムの結合操作実行時間を計測する．
の和集合を求めている．
実 験 2.
結合操作終了時点でのシステム全体で使用
するメモリ使用量を計測する．
4. 実 験
筆者らが以前作成した異種情報源統合システムと，
4.2. 実 験 結 果
実 験 1.
図 7 に シ ス テ ム の 実 行 時 間 を 示 す ．全 て の 回
今回作成したシステムのメモリ使用量を比較する．以
に お い て ，新 シ ス テ ム の 実 行 時 間 が ，旧 シ ス テ ム
降，以前作成したシステムを旧システム，今回作成し
よりも短くなっている．
たシステムを新システムと記す．
実 験 2.
全 体 で 使 用 し て い る メ モ リ 使 用 量 を 示 す ．全 て の
4.1. 実 験 方 法
回 に お い て ，新 シ ス テ ム の メ モ リ 使 用 量 が ，旧 シ
メモリ使用量とシステム実行時間を 6 回，実機
ステムよりも少なくなっている．
（ Windows 8.1 Pro ， 2.93GHz Intel Core 2 Duo, 4GB
Memory） に て 計 測 す る ． 結 果 の 単 位 は KB と msec で
ある．
実 験 に 用 い た MySQL，PostgreSQL，SQLite の テ ー ブ
ルの仕様を以下に示す．
図 8 に結合操作が終了した時点でのシステム
4.3. 考 察
A)
結合操作実行時間
結合操作実行時間の平均は旧システムでは
91.6[msec]で あ り ，新 シ ス テ ム で は 6[msec]で あ
1)
行 数 は 10,000 行 ．
る ． 旧 シ ス テ ム で は 10,000 行 と 10,000 行 の 結
2)
カ ラ ム は id， name， loc を 持 つ ．
合 操 作 が 2 回 あ る の に 対 し ，新 シ ス テ ム で は そ
3)
カ ラ ム id に は 1 か ら 10,000 の 数 が 昇 順 に 入 る ．
の 部 分 が 5 行 と 10,000 行 の 結 合 操 作 に な っ て
カ ラ ム name に は 長 さ 20 の ラ ン ダ ム な 文 字 列 が 入
い る ．比 較 す る 行 数 が 少 な い ほ ど ，結 合 操 作 に
る．
か か る 時 間 は 短 く な る と 考 え ら れ る ．結 合 す る
4)
で解決した．実機による評価の結果，結合操作の実行
120
時間を増やすことなく，メモリ使用量の大幅な削減が
実行時間(msec)
100
できることを示した．
旧シ
ステ
ム
80
60
現 在 の JDBC で は MySQL，PostgreSQL，SQLite，DB2，
Excel，CSV の 利 用 に 限 ら れ て い る ．ま た ，集 合 演 算 に
お い て ()を 使 用 で き ず ， 集 合 演 算 子 は 1 種 類 の み の 使
40
新シ
ステ
ム
20
用に制限されている．この制限を取り払うことで，よ
り様々な用途に利用してもらえると考えている．その
ため，この制限を取り払うことが今後の課題である．
0
1
2
3
4
5
6
実行回数（回目）
参
図 7 システムの実行時間
27000
メモリ使用量(KB)
25000
23000
旧シ
ステ
ム
21000
19000
新シ
ステ
ム
17000
15000
1
2
3
4
5
6
実行回数（回目）
図 8
システムのメモリ使用量
リ レ ー シ ョ ン の タ プ ル 数 を S， T と す る と ， ソ
ー ト ・ マ ー ジ 結 合 の 時 間 計 算 量 は
O((S+T)log(S+T))で 表 さ れ る ． 旧 シ ス テ ム で の
時 間 計 算 量 は ܱ(20,000݈‫(݃݋‬20,000ሻ ∗ 2 +
10,005݈‫(݃݋‬10,005ሻ + 10 log(10ሻሻで あ る の に 対 し ，
新 シ ス テ ム で は ܱ(10,005݈‫(݃݋‬10,005ሻ ∗ 3 +
考
文
献
[1] H. Garcia-Molina, Y. Papakonstantinou, D. Quass, A.
Rajaraman, Y. Sagiv, J. Ullman, V. Vassalos and J.
Widom, “The TSIMMIS Approach to Mediation: Data
Models and Languages”, Journal of Intelligent
Information Systems, vol8, no.2, pp,117-132, 1997.
[2] X. Wang, T. Hochin and H. Nomiya, “Feasibility of
Unified Usage of Heterogeneous Databases Storing
Private Information”, Proc. of 1 st ACIS International
Symposium on Applied Computing & Information
Technology (ACIT 2013), pp.337-342, 2013.
[3] A. Terakawa, T. Hochin and H. Nomiya, “Integrated
Usage of Heterogeneous Databases for Novice Users”,
Proc. of International Conference on Software
Engineering
Research,
Management,
and
Applications (SERA2014), pp. 705-710, 2014.
[4] DK. Shin and AC. Meltzer, “A New Join Algorithm”,
ACM SIGMOD Record, vol.23, no.4, pp.13-20, 1994.
[5] H. Garcia-Molina, J. Ullman and J. Widom,
“Database Systems The Complete Book”, Pearson
Education, pp. 826-832, 847-856, 862-864, 2002.
[6] A. Silberschatz, H. Korth and S. Sudarshan,
“Database system concepts 4 t h edition”, McGraw-Hill
Education, pp.515-516, 2002.
[7] Lance Andersen and Specification Lead, “JDBC T M
4.2 Specification”, 2014.
10݈‫(݃݋‬10ሻሻで あ る ． そ の た め ， 結 合 操 作 自 体 に
かかる時間は削減できていると考えられる．
B)
メモリ使用量
A. 付 録
A.1. 結 合 結 果 の サ イ ズ 推 定
属 性 X,Y を 持 つ リ レ ー シ ョ ン R を R(X,Y)と 表 し ，
図 8 よ り ，新 シ ス テ ム の メ モ リ 使 用 量 が 旧 シ ス
テ ム よ り 大 幅 に 少 な く な っ て い る ．こ れ は ，旧
リ レ ー シ ョ ン の タ プ ル 数 を T(R)，R の 属 性 X の distinct
シ ス テ ム で は 全 リ レ ー シ ョ ン の デ ー タ ，お よ び ，
値 を V(R,Y)と 表 す [5]．
R(X,Y)と S(Y,Z)を 属 性 Y で 等 結 合 し た サ イ ズ は 以 下
中間リレーションのデータを全て保持してい
る の に 対 し ，新 シ ス テ ム で は 使 用 し た デ ー タ を
全て破棄していることから大幅に下がったと
考えられる．
のようにして推定することができる．
ܸ(ܴ, ܻሻ ≤ ܸ(ܵ, ܻሻと 仮 定 す る .
1.
R の 全 タ プ ル が ，与 え ら れ た S の タ プ ル と 結 合 す
る 確 率 は 1/ܸ(ܵ, ܻሻ.
5. ま と め
2.
本論文では，これまでに試作してきた異種情報源統
合 シ ス テ ム に お い て ， メ モ リ 使 用 量 が 多 い こ と ， GUI
も含めたシステムになっており汎用性が高くないこと，
S は T(S)タ プ ル あ る た め ，結 合 さ れ る タ プ ル 数 の
期 待 値 は ܶ(ܵሻ/ܸ(ܵ, ܻሻ.
3.
R は T(R)タ プ ル あ る た め ，R と S を 等 結 合 し た 時
の 結 合 推 定 サ イ ズ は ܶ(ܴሻܶ(ܵሻ/ܸ(ܵ, ܻሻ.
という２つの問題点を結合結果のサイズ推定式を用い
一 般 的 に は V(R,Y)と V(S,Y)の 大 き い 方 で 割 る こ と で
て適切な結合順序を決定すること，異種情報源の統合
推 定 サ イ ズ を 求 め る た め ，一 般 式 は 以 下 の よ う に な る ．
機 能 を 持 つ JDBC を 作 成 し ， GUI 部 分 と 分 離 す る こ と
ܶ(ܴ ⋈ ܵሻ = ܶ(ܴሻܶ(ܵሻ/ max൫ܸ(ܴ, ܻሻ, ܸ(ܵ, ܻሻ൯
(‫ܣ‬. 1ሻ
Y が い く つ か の 属 性 を 表 す と 仮 定 す る ． R(x, y1, y2)と
S(y1, y2, z)の 結 合 サ イ ズ は 以 下 の よ う に し て 推 定 す る ．
ܶ(ܴሻܶ(ܵሻ
max൫ܸ(ܴ, ‫ݕ‬1ሻ, ܸ(ܵ, ‫ݕ‬1ሻ൯ max൫ܸ(ܴ, ‫ݕ‬2ሻ, ܸ(ܵ, ‫ݕ‬2ሻ൯
(‫ܣ‬. 2ሻ
A.2. Left-deep tree
木 の 形 は 図 A.1 に 示 す よ う に 3 種 類 あ る [5]．
図 A.1 木 の 形
(a)を left-deep tree，(b)を bushy tree，(c)を right-deep
tree と 呼 ぶ ． 結 合 順 序 を left-deep tree に 制 限 す る こ と
で次のような利点がある．
1.
2.
木の形を制限することで探索数が減る．
一 般 的 な 結 合 ア ル ゴ リ ズ ム (特 に nested-loop join,
one-pass join)で は 非 left-deep tree を 使 っ た 同 じ ア
ル ゴ リ ズ ム よ り も ， left-deep tree を 使 っ た 方 が ，
効率が良い傾向にある．