DEIM Forum 2013 C9-2構造/テキスト Web データを対象とした
Pay-as-You-Go スタイルの問合せ構築支援手法
安永

ゆい†

森嶋

厚行††,†††

袖山 広輝†† 筑波大学大学院 図書館情報メディア研究科 〒 305–8550 茨城県つくば市春日 1–2†† 筑波大学 図書館情報メディア系/知的コミュニティ基盤研究センター 〒 305–8550 茨城県つくば市春日 1–2††† JST さきがけ
E-mail: yui@slis.tsukuba.ac.jp, mori@slis.tsukuba.ac.jp, hiroki.sodeyama.2009b@mlab.info
あらまし近年，テキストデータとそれと並存する構造データから構成された Web データが広く普及しつつある．

このような Web データの具体例として，Wikipedia と DBpedia データの組が挙げられる．我々は，このような Web
データに対する問合せ言語として Gradation 問合せ言語を提案してきた．Gradation とは，キーワード問合せをベースとし，簡単な追加記述によって構造データに対する問合せ条件を表現することで，キーワード問合せと構造化問合せのシームレスな融合を実現する言語である．本稿では，Gradation の特徴に着目して，Gradation でより精確 (precise)
な問合せを作成することを支援する手法を提案する．これにより，完全な構造化問合せやハイブリッド問合せの記述が容易になる．実データを用いた実験では，本手法を利用することで SQL を知らない被験者の多くが精確な問合せを記述することができた．
キーワード

問合せ構築支援，構造化問合せ，キーワード問合せ，Web 検索，構造データ

1. は じ め に大きく，また，問合せ対象のデータに関する知識も必要となるため，カジュアルユーザが習得・利用することは難しい．した

近年，テキストデータとそれと並存する構造データから構がって，ユーザにとっては，テキストデータを対象としたキー成された Web データが広く普及しつつある．このような Web

ワード問合せを行うか，構造データを対象とした構造化問合せ

データの例として，Wikipedia のページとそれと並存する DB-を行うか，という二者択一の状況であった．

pedia [1] のデータ の組が挙げられる．DBpedia は Wikipedia

我々は，この問題に対する新しいアプローチとして，テキスの各記事に関する様々な情報を RDF 形式の構造データとして提トページ (本稿では，テキストを含む Web ページなどをテキス供している．もう 1 つの例としては，ACM Digital Library [2]トページと呼ぶ) とグラフデータ (本稿では，主に RDF データのページと，DBLP RKB Explorer [3] のデータとの組が挙げを指す) の組からなる Web データに対する問合せ言語である

られる．ACM Digital Library はコンピュータサイエンス分

Gradation 問合せ言語 (Gradation Query Language. 以下，

野の論文の書誌情報をテキストページで提供しており，DBLP

Gradation) を提案してきた [5] [6]．Gradation の設計目標は，

RKB Explorer は，コンピュータサイエンス分野の論文書誌

キーワード問合せと構造化問合せの溝を埋めることによって，データベースである DBLP のデータを RDF 形式で持っている．

高度な問合せ能力をカジュアルユーザにとって身近なものにす

各書誌情報のページと RDF データ間の関係は論文に付与されることである．Gradation は，キーワード問合せと構造化問合た DOI で表される．SemanticWeb ビジョンにおける Linked

せとのシームレスな融合を実現するために，キーワード問合せOpen Data の取り組み [4] 等と相まって，テキストデータとそをベースとし，簡単な追加記述によって構造データに対する問れと並存する構造データから構成された Web データは今後ま合せ条件を表現する．Gradation においては，キーワードのみ

すます一般的に利用されると考えられる．

を使った問合せは通常のキーワード問合せのように動作し，構

これまで，先述のような Web データに問合せを行う方法に

造データに対する問合せ条件のみを使った問合せは完全な構造

は，2 つの選択肢しか存在しなかった．すなわち，キーワード

化問合せとなり，キーワードと構造データに対する問合せ条件

問合せ (本稿では，一つ以上のキーワードと，それらをつなぐを混在させた問合せはテキストとグラフデータに対するハイブ

論理演算子，及び括弧で記述された問合せをキーワード問合せ

リッド問合せとなる．このような問合せ記述方法を採用すること呼ぶ) を用いるか，もしくは構造化問合せ (SPARQL などのとにより，Gradation は単純なキーワード問合せから高度な構構造化問合せ言語に従った問合せ) を用いるか，のどちらかで造化問合せまでを広くカバーするとともに，“pay-as-you-go”

ある．キーワード問合せは，カジュアルユーザに普及しているスタイルの問合せを実現する．すなわち，問合せ記述にかけるコが，表現力が低く，Web データのセマンティクスを利用したストや問合せ条件の精確さを，ユーザが自身の要求やスキルに問合せを記述することができない．一方，構造化問合せは，表応じて選択し，利用することを可能にする．しかし，Gradation

現力が高く高度な問合せが可能であるが，言語の学習コストがで構造データに対する問合せ条件を記述する（つまりハイブ

リッド問合せや完全な構造化問合せを記述する）ためには，検索対象データのクラス名や属性名などのスキーマレベルの情報が必要であるため，SQL や SPARQL といった他の構造化問合せ言語を使用する場合と同じだけの知識が求められる．

2. 関 連 研 究
本研究は，キーワード問合せと構造化問合せをシームレスに融合した問合せ言語を利用して，ユーザによる構造化問合せの本稿では，Gradation 問合せ作成を支援する手法 Morphin-

記述を支援する研究である．構造化問合せの記述を支援するシ

gAssist を提案する．この提案手法は，Gradation の「キーワー

ステムは数多く存在し，大きく次の 2 つに分類される．(1) ユー

ド問合せから構造化問合せまでを同一の言語でシームレスに記

ザに構造化問合せを入力させ，よりユーザの意図に合致すると述できる」という特徴に着目した，より精確 (precise) な問合

思われる構造化問合せを構築していく支援方法．(2) ユーザにせの作成支援手法である．本支援手法の目標は，ユーザがキー

キーワードや自然言語文を入力させ，それを基に構造化問合せ

ワード問合せによる問合せから始め，その結果を見ながらキーを構築する支援方法．

ワードを変更したり MorphingAssist が提示するヒントを見な(1) の例としては，ユーザの書いた SQL 問合せを基に，別のがら徐々に問合せを「必要な範囲で」「出来る範囲で」詳細化す

SQL 問合せを推薦する研究 [8] が存在する．[8] では，ユーザはることを支援することである．本支援手法により，ユーザは完

初めから構造化問合せを記述する必要がある．これに対して，

全な構造化問合せやハイブリッド問合せを容易に記述できる．

我々の手法は，構造化問合せが記述できないユーザが構造化問

MorphingAssist の開発にあたっては，自明でない 3 つの問合せを記述することを支援することを目的としており，ユーザ

題に取り組む必要がある．(1) 表示するヒント: どのようなヒは初めにキーワード問合せを入力するだけでよい．

ントを提示すればよいのか．(2) ヒントの計算方法: どのよう

(2) の例としては IQP [7] がある．IQP は最初にユーザに問にしてそのヒントを求めるか．(3) ヒントの提示方法: どのよ合せを表すキーワードを入力させ，次にユーザに質問を行い，うに求めたヒントをユーザに見せるべきか．詳細は 4. 節で説明

最終的にユーザの意図を反映した構造化問合せを出力する．本するが，MorphingAssist の開発にあたり，我々は，(1) に関し研究との違いは次の 2 点である．第 1 に，IQP は最終的な構造ては，一般的なキーワード検索の Suggest 機能と同様に，「もし化問合せが出力するまで，ユーザが問合せを実行することが出かしたら，この (構造データに関する) 問合せ構成要素を使いた

来ない．これに対して，Gradation では，完全な構造化問合せかったのかもしれない」という問合せ改訂案を見せるというアでないキーワード問合せやハイブリッド問合せであっても実行

プローチを採用する．(2) に関しては，ユーザが文書検索を意することができる．これにより，ユーザが自身の要求やスキル

図して入力したキーワードをあえて構造データとマッチさせ，に応じた程度の問合せを記述し実行可能である．第 2 に，IQPユーザが使用する可能性のある問合せ構成要素を計算するといでは，最初に入力されたキーワードが，最終的に出力される構うアプローチを採用する．(3) に関しては，ヒントの組み合わ

造化問合せに大きく影響する．したがって，最初に適切なキー

せ爆発を避けつつ，ユーザが問合せの書き直しをしやすいと考

ワードを入力できなければ，生成される問合せはユーザの意図

えられる手法を採用する．実験の結果，提案アプローチは容易を反映しなくなる可能性が高い．しかし，我々の経験から言うに実現可能であるにも関わらず効果的であることがわかった．

と，ユーザが最初から適切なキーワードを選ぶことは困難であ

本稿の貢献は次の通りである．

ることが多い．これに対して，Gradation を利用すれば，最初(1) 二択でない構造化問合せの作成支援. 「完全な構造化問にキーワード問合せを実行したときから検索結果がその場で表合せを出力できるか，そもそも問合せが出来ないかの二択」で示されるので，記述したキーワード問合せが不適切だと気付けあった既存の SQL 言語等の構造化問合せ作成支援ツールと異ば，その場で簡単にキーワードを変更することができる．

なり，Gradation 問合せ言語を利用する事によって，キーワー
ド問合せから徐々に「必要な範囲で」「出来る範囲で」問合せの3. Gradation 問合せ言語

詳細化を支援するという，新規性の高いアプローチを提案する．

Gradation は，テキストページと構造データから構成された(2) 実データによる評価実験. Wikipedia/DBpedia を用いてWeb データを検索対象としたハイブリッド問合せ言語である．

被験者を用いた評価実験を行った結果を示す．実験では，Gra-

Gradation は，キーワード問合せをベースとし，簡単な追加記

dation 言語と MorphingAssist を利用する事により，SQL 言

述によって構造データに対する問合せ条件を表現する言語であ語等の構造化問合せを書けない，もしくは書いたことがない被り，キーワード問合せと構造化問合せとのシームレスな融合を験者の多くが精確な問合せを記述することができた．

実現している言語である．

本稿の構成は次の通りである．2 節では，関連研究について

Gradation は，キーワード問合せのみを利用するようなユー

述べる．3 節では，キーワード問合せと構造化問合せをシーム

ザであっても，キーワードに加えて簡単な検索オプションをしレスに融合した問合せ言語 Gradation の概要を説明する．4 節

ばしば利用することに着目して設計されている．例えば，Web

で，Gradation を用いた構造問合せ作成支援 MorphingAssist

検索エンジンのユーザは，指定したサイトのみを検索対象とすを提案する．5 節では評価実験について述べる．6 節にまとめるオプション (site:ac.jp など) を記述して検索することがあと今後の課題を示す．

る．実際，[9] によると，25%のユーザが検索オプションを使用したことがあると言われている．

Gradation でも，キーワードに加えて検索オプションのよう“attr1 θ attr2 ” が成り立つ．θ には，等号・不等号の記号が使える．例えば，名前 (name) が Tom である俳優のテキストページを取得する問合せは次のようになる．
name==Tom type==Actor(C3) path traversal: RDF データ中のノード間の関係 (p)を表すための構成要素．q1 .p.q2 のように記述する．q1 と q2 には任意の構成要素を記述することができ，q1 と q2 を満たしか
つ p の関係にあるテキストページの組を探すための構成要素で
図 1 問合せ対象データ n の例ある．例えば，名前が Tom である俳優と，彼が主演を務めた(starringOf) 映画のテキストページの組を取得する問合せは次の通りである．
(name==Tom type==Actor).starringOf.type==Film(C4) projection: 検索結果のリレーションのスキーマを指定するための構成要素．q [attr1 , . . . , attrn ] のように記述する．qには任意の構成要素を記述することができる．attri には RDF
図 2 問合せ処理モデル

データ中のエッジの他，テキストページの URI を表す t uriと RDF データのリソースノードを表す r uri が記述できる．

な簡単な追加記述を利用することができる．この簡単な追加記

例えば，俳優を取得し，その俳優のテキストページ (t uri) と述によって構造化問合せの問合せ条件を表現する．例えば，グ

名前 (name) を表示する問合せは次の通りである．
(type==Actor)[t uri, name]

ラフデータに各人物の年齢 (age) を表すデータが含まれる場合，

40 歳以上の Tom という人物のテキストページを取得する問合
せは，追加記述 age>=40 を用いて Tom age>=40 と記述する.

(C5) and, or, not, *, (): 任意の構成要素に対して，and,

Gradation は単なるキーワード問合せや構造化問合せが記述

or, not, *(直積), グルーピングを行うことができる．例えば，できるだけでなく，ハイブリッドな問合せを記述することがで

俳優 (Actor) である人物のテキストページで，かつ Tom とい

きる．ハイブリッドな問合せというのは，テキストデータの問

う文字列を含むテキストページを取得する問合せは次の通りで合せ条件と構造データの問合せ条件を混合して記述している問ある (and は省略可能である)．この問合せは，キーワード問合合せである．

せの条件と構造化問合せの条件が混在した問合せである．
Tom and type==Actor

3. 1 問合せ対象データ
Gradation の問合せ対象データ D は，テキストページ T と以上の問合せ例のように，Gradation を用いると，キーワー

それと並存するグラフデータ (RDF データ) G の組である．図

ド問合せの条件と構造化問合せの条件を混在させ，簡易なレベ

1 は問合せ対象データの一例である．図 1 中の点線は，テキス

ルの問合せから高度な問合せまでが表現可能である．

トページとノードの対応関係を表す関数 f : T → G を表す．

3. 2 問合せ処理モデル

4. MorphingAssist

Gradation の問合せ処理モデルを図 2 に示す．入力は Gra-

3 節で述べたように，Gradation を利用すれば，キーワード

dation で記述した問合せ q (図 2 左上)，問合せ対象データは問合せから構造化問合せまでを同一の言語でシームレスに記述

3. 1 節で説明した問合せ対象データ D (図 2 右)，出力は，特別できる．しかし，構造データに関する問合せ条件 (すなわち構な指定がなければ，q にマッチするテキストページの URI の集

成要素 C2 から C4) を記述するためには，対象データのクラ合を表すリレーション R (図 2 左下) である．

ス名や属性名などのスキーマレベルの情報が必要であるため，

3. 3 Gradation の問合せ構成要素と問合せ例

SQL や SPARQL といった他の構造化問合せ言語を使用する場

Gradation の問合せ構成要素 (C1 から C5) とそれを使った合と同じだけの知識が求められる．

問合せ例を説明する．下記問合せ例では，図 1 を問合せ対象

本節では，Gradation での精確な問合せ作成を支援する手法

データとする．

MorphingAssist を提案する．これは，Gradation の「キー(C1) keyword: あるキーワードを含むテキストページを探す

ワード問合せから構造化問合せまでを同一の言語でシームレための構成要素．例えば，Tom と Actor という文字列を含む

スに記述できる」という特徴に着目した，精確な問合せの作

テキストページを取得する問合せは次のようになる．
Tom Actor

成支援手法である．MorphingAssist のユーザはキーワード問(C2) selection: 次の条件を満たす RDF データと対応するMorphingAssist の支援によって徐々に問合せを「必要な範囲

テキストページを探すための構成要素．RDF データ中のノーで」「出来る範囲で」詳細化する．例えば，「俳優のトムという人

ド (value) とエッジ (attr) の間に， “attr θ value” もしくは物を全員知りたい」と思ったユーザが最初に問合せ (QI) “Tom合せから始め，その結果を見ながらキーワードを変更したり，

Actor” を記述したとする．もし MorphingAssist が適切な支援を行えば，ユーザは徐々に問合せをより精確な問合せに書き直して，(QII) “Tom type==Actor” や (QIII) “name==Tom

type==Actor” を記述できる．MorphingAssist はこのような問合せの変更を支援するためのヒントを提示する．

MorphingAssist の開発にあたっては，自明でない 3 つの問図 3 検索結果とヒントの例

題に取り組む必要がある．(1) 表示するヒント: どのようなヒントを提示すればよいのか．(2) ヒントの計算方法: どのようタプル毎にヒントが作成される．例えば，ユーザが問合せ QIにしてそのヒントを求めるか．(3) ヒントの提示方法: どのよを図 1 のデータに対して投げると，図 3 のように検索結果とうに求めたヒントをユーザに見せるべきか．

ヒントが表示される．我々のユーザインタフェースでは，ユー(1) 表示するヒント. キーワード検索システムの問合せ推薦機

ザは各タプルの隣にあるボタンをクリックするとそのタプルに能の一般的なアプローチは，「もしかしたら，このキーワードを関連するヒントが表示されるようにしている．これは，ユー

使いたかったのかもしれない」と考えられる新しいキーワード

ザの関心のない検索結果 (タプル) に関連するヒントはユーザ

を次の問合せのために推薦する，というアプローチである．我々に必要ないと考えたためである．図 3 の検索結果と hint を見はこのアプローチを我々の文脈に適用し，「もしかしたら，このたユーザは，1 行目のヒントを見れば問合せ QII が書けるし，(構造データに関する) 問合せ要素を使いたかったのかもしれな

1 行目と 2 行目のヒントを組み合わせて使えば問合せ QIII がい」と考えられる問合せ要素を次の問合せのために推薦すると書ける．なぜなら，1 行目と 2 行目のヒントは元の問合せのいうアプローチを採用する．構造データに関する問合せ要素を“Tom” は “name==Tom” に置き換えることができて， “Actor”

推薦するので，元の問合せをより精確な問合せに書き直すことは “type==Actor” に置き換えることができることを示していを支援できる．問合せの構成要素の例としては，“name==Tom”

るからである．

や “type==Actor” がある．この構成要素を使うと，QI を書き

さらに，適切そうなヒントを選び出すために，我々はこの提直して QII や QIII を書くことができる．

案手法を次の単純な手法と組み合わせる．まず，ユーザに，情(2) ヒントの計算方法. ヒントを求めるために，我々はユーザ

報要求にマッチしているタプルを選ばせる．次に，それらのタが書いた元のキーワード (テキストデータとマッチすることをプルと関連するヒントの積集合を計算し，ユーザに見せる．こ意図して書かれてたキーワード) をあえてそれと並存する構造

うすることで，ユーザの情報要求を問合せで表現する際に重要データにマッチさせ，ユーザが使う可能性のある問合せ構成要

なヒントがこの中に含まれることになると考えられる．

素を計算する．この手法は単純であり，同時に，効果的である

4. 1 ヒントの生成ことが実験 (5 節参照) によって示されている．

ヒントの生成は次の 2 段階からなる．
【Phase1】使われる可(3) ヒントの提示方法. ヒントの単純な提示方法の 1 つは，元能性のある全ての問合せ構成要素を求める．
【Phase2】問合せの問合せを書き換えるのに使うことのできる問合せの構成要素

構成要素を使ってヒントを生成する．

を並べて提示することである．しかし，これではユーザは提示【Phase1】使われる可能性のある全ての問合せ構成要素を求めされた構成要素をどのように使えばいいか思いつくことができる．Gradation 問合せ処理システムによって求めた qi の検索

ない．別の単純な方法としては，元の問合せと求めた構成要素

結果を R とする．
【Phase1】では，検索結果 1 件 r (r ∈ R) 毎

を使って作成可能なより詳細な問合せへの改訂案 (以下，問合に，問合せ改訂案 qi+1 で使われる可能性のある構成要素を求せ改訂案) を全て提示することである．しかし，これでは提示

める．すなわち，図 3 で言うと，各タプル毎に構成要素は求めされる問合せ改訂案の数は膨大になり，容易に組合せ爆発を起られる．具体的には，【Phase1】は次の 2 ステップからなる．

こしてしまう．

Step 1: 検索結果 1 件 r (r ∈ R) に含まれるテキストページ t

そこで，我々はヒントの組み合わせ爆発を避けつつ，ユーザの URI(検索結果のうち属性 t uri) の集合を U とする．このが問合せの書き直しをしやすいと考えられる提示方法を提案す

とき， V = {f (t)|t ∈ U } となるような URI の集合 V を求める．その方法とは，元の問合せと 1 カ所だけ異なる問合せ改訂る．ここで，関数 f (t) は t と対応する RDF ノードを返す関数

案を全て列挙することである．こうすることにより，ヒントのである (3 節参照)．

数は求めた構成要素の数と同じになり，かつユーザは提示されStep 2: V 中の RDF ノードから距離 h 以内にある RDF ノー

たヒントを組み合わせることで 2 つ以上の構成要素を合わせてドの集合を V ′ とする．また，V ′ を求める際にトラバースした

使った新たな問合せを簡単に思いつくことができる．例えば，

エッジのエッジラベルの集合を L とする．このとき，次のルー

元の問合せが “Actor Film Star” であり，求めた構成要素がルに基づいて構成要素を生成する．

“type==Actor”，“type==Film”，“[star]”，“.star.” の 4 つRule1: 問合せ qi 中のキーワード 1 つが V ′ 中のノードのノードだったとする．この時，MorphingAssist は次の 4 つのヒントをラベルとマッチしたら，selection 構成要素 (C2) “attr = value”

提示する． “type==Actor Film Star”， “Actor type==Filmを生成する．ここで， value はマッチしたノードラベルの値でStar”，“(Actor Film)[star]”，“(Actor Film).star.(*)”． あり，attr はそのノードから出ているエッジのエッジラベルである．もしマッチしたノードに対してそのノードから出ている
MorphingAssist では，直前に投げた問合せの検索結果の 1

エッジが複数存在したら，それぞれのエッジに対して 1 つ構成

要件

情報要求の例

要素を生成する．加えて，もし value が数字であった場合は，物事の「属性」を使う「芥川賞を受賞した」作家を全員知りたい.

不等号記号を使った selection 構成要素 (“attr <= value” な

複数の物事間の「関係」を使

お笑い芸人と東京都に本社がある事務所の組

う

み合わせ（「その芸人はその事務所に所属してど) も生成する．

いる」）全てが知りたい．

Rule2: 問合せ qi 中のキーワード 1 つが L 中のエッジラベルとマッチしたら， projection の構成要素 (C4) “[l]” と path-traversal の構成要素 (C3) “.l.” を生成する．ここで， l はマッチしたラベルである．

物事の「属性」を表示する

日本にある全ての動物園と「その開園年」が知りたい.

図 4 情報要求作成に係る 3 つの要件と情報要求の例

被験者に情報要求 (Wikipedia や DBpedia に載っている情報

例えば，図 3 の 1 タプル目の検索結果 (Tom t) に対応するに対する情報要求) を考えてもらった．この情報要求の集合を構成要素は次のようにして求める．qi は “Tom Actor” で，ヒN とする．次に，我々がそれぞれの情報要求 ni ∈ N を満たすントを求めたい検索結果 (1 タプル目) は t uri 属性に Tom t

ような正解 Gradation 問合せ cqi を作成した．正解 Gradation

を持っている．このとき，図 1 では f (Tom t) = Tom r が成問合せの集合を CQ とする．

り立つ．図 1 では，Tom r の隣接ノードでキーワード “Tom”(2) 正解問合せの構成要素を求める: それぞれの正解 Gradationとマッチするノード (“name” エッジで繋がっているノード) と問合せ cqi ∈ CQ ごとに，その問合せの構成要素の集合 Ci を求キーワード “Actor” とマッチするノード (“type” エッジで繋めた．例えば，cqi = “name==tom type==actor” のとき，Ci

がっているノード) がある (ここで，“Tom” と “Actor” は問合= {name==tom, type==actor} である．

せ qi に含まれているキーワードである)．従って，図 3 中の 1 タ(3) 情報要求から Gradation 問合せを記述: グループ B の被

プル目の検索結果 (Tom t) に対応する構成要素は “name==Tom”

験者に情報要求を提示し，MorphingAssist システムを使用しと “type==Actor” の 2 つとなる．

て Gradation 問合せを記述してもらう．ここで，問合せ qi,j,k【Phase2】問合せ構成要素を使ってヒントを生成する．ここでは，情報要求 ni ∈ N を見た被験者 sj が書いた k 番目の問合は，(1) で生成した問合せ構成要素の 1 つと qi 中のキーワード

せを表すこととする．Qi,j は， qi,j,k を k を 1 から並べたリス

1 つを置き換えることでヒントを生成する．例えば，qi が Tomトとする. 以降，Qi,j を，問合せ記述プロセス と呼ぶ．qi,j,k

Actor で 1 件目の検索結果に対して生成された問合せ構成要素

は，Qi,j の k 番目の問合せとなる．また，問合せ qi,j,k の結果

が “name==Tom” と “type==Actor” の 2 つだった場合，(2) でと共に被験者 j に提示したヒントの集合を Hi,j,k で表現する．

生成するヒントは “name==Tom Actor” と “Tom type==Actor”(4) ヒントの質と MorphingAssist の効果から Morphin-の 2 つである．

gAssist を評価: 4. 節に示したように， MorphingAssist は，

5. 評 価 実 験

ユーザに再検索で使われる可能性のある問合せ構成要素を含む問合せをヒントとして提示する．本実験では，次の 2 つの

本節では MorphingAssist の評価実験について述べる．本実

観点で MorphingAssist を評価する．(1) 生成したヒントの験では次の 2 つの観点から評価を行った．(1) 生成したヒント

質：ユーザに提示したヒントの表示数 |Hi,j,k |，ヒントの再現の質．(2) MorphingAssist の効果．本実験では，Gradation と率 (正解問合せの構成要素 Ci をどれだけ再現できたか)．(2)MorphingAssist の組合せは効果的であった．また，本実験でMorphingAssist の効果：被験者が記述した問合せの実行結果

は SQL を知らない被験者の多くが精確な問合せを記述できた．

の再現率と精度，被験者が記述した問合せと正解問合せの比較．

5. 1 設定

本 実 験 で 使 用 し た デ ー タ は ，Wikipedia [10] と DBpedia

Japanese [11] のダンプデータである．

5. 2. 1 情報要求と正解問合せの作成
まず，グループ A の被験者それぞれに情報要求 (Wikipedia
や DBpedia に載っている情報に対する情報要求) を 3 つ自然言本実験では，2 つのグループの被験者に別々の作業をしても語で記述してもらった．このとき，各情報要求が図 4 に書いてらい実験を行う．グループ A：実験で使用する情報要求を作成

ある要件 3 つのうち少なくとも 1 つを満たし，「○○なものを全する学生 (7 名)．グループ B：MorphingAssist システムを使っ部知りたい」という形の情報要求になるように指示をした．こて Gradation 問合せを記述する学生 (10 名)．さらにグループ

れは，Gradation における構造化問合せ構成要素のうち，基本B は，グループ B1 とグループ B2 に分けることができる．グ的な構成要素が次の 3 つであるためである．(1) 属性を指定すループ B1 は DB 言語 (例えば SQL や XQuery，SPARQL な

る構成要素 (C2)，(2) 関係を指定する構成要素 (C3)，(3) 検索

ど) をある程度使うことができる学生 (5 人) であり，グループ

結果に表示する属性名を指定する構成要素 (C4)．情報要求をB2 は DB 言語を 1 つも知らない，もしくはかつて習ったこと作成してもらうにあたって，被験者には情報要求のサンプルとがあるが忘れてしまった学生 (5 人) である．グループ B 全員

して図 4 の情報要求の例を示した．

は Gradation の文法に関する知識がなかったため，実験前に文法の説明を行った．

5. 2 方法

本実験は次の手順で行った．

(1) 情報要求と正解問合せの作成: まず，グループ A の 7 人の次に，集めた情報要求の中から，DBpedia 中に情報がないために調べることができない情報要求を排除した．その結果，10個の情報要求が得られた (つまり，|N | = 10).
最後に，我々がそれぞれの情報要求 ni ∈ N を満たすようなGradation 正解問合せ cqi ∈ CQ を記述した．各 cqi の実行結

果を，情報要求 ni を記述した被験者に見せ，その結果が ni を満たしているかどうか確認してもらった．満たさない，と判断された場合は，満たすと判断されるまで cqi を書き直した（本実験では，満たさない，と判断されることはなかった）．付録 1.
に，本実験で使用した情報要求とそれを満たす正解 Gradation
問合せを示す．

5. 2. 2 正解問合せの構成要素の作成
まず，各正解問合せ cqi ∈ CQ から問合せの構成要素を抽

図5

提案手法による構成要素の再現率とヒントの表示数

出して，Ci (Ci = components(cqi )) を作成する．次に，Ciから，単純な問合せ構成要素を削除する．単純な問合せ構成
要素とは，RDF データ中のデータ (エッジラベル，ノードラベル) を含まないような構成要素である．具体的には，(C5)の “and”, “or”, “not”, “*” である．これらを削除した理由
は，MorphingAssist は，RDF データ中のデータに関する情報をヒントとして提示するシステムであり，これらの構成要
素が MorphingAssist によって提示されないからである．例えば，cqi が “(name==Tom or name==Thomas)” であったとき，

図 6 ヒントを減らす工夫をした時のヒントの再現率とヒントの精度

Ci は {name==Tom, name==Thomas} となる.

少したにもかかわらず，再現率が下がったものは 1 つもなかっ5. 2. 3 被験者による問合せ記述

た (再現率の平均は 0.65)．

それぞれの情報要求をグループ B の被験者 3 人に見せ，Mor-

被験者がヒントを減らす仕組みを使うということは，被験phingAssist システムを使って Gradation 問合せを記述しても者の意図を表しているので，ここで精度を求めることは意らった．各被験者 sj は 3 つの情報要求に対して Gradation 問

味がある．図 6 は，ヒントを減らす仕組みを使用した後に合せを記述した．各被験者は，自分が書いた問合せ qi,j,k が情表示されたヒントの再現率と精度である．ヒントの精度は，

報要求 ni を満たすと判断するまで問合せを書き直すことがで|Ci ∩ ∪k Hi,j,k |/| ∪k Hi,j,k | によって求められる．ヒントの精度きる．被験者が自分で情報要求を満たすと判断した問合せを確の平均は 0.16 であった．これは，表示されたヒント平均 9.71

定問合せと呼び，dqi,j と表す．被験者が 15 分以内に確定問合個のうち 1.55 個は正解構成要素を含んでいることを示す．

せを作成することができなかった場合は，確定問合せはなしとする．全ての被験者について最後の問合せ qi,j,|Qi,j | は存在し，確定問合せが存在する場合は，dqi,j = qi,j,|Qi,j | となる．

5. 3 実験結果 1：表示したヒントの質

以上の結果から， MorphingAssist は適切なヒントを表示することに関してよいはたらきをしていることが分かる．

5. 4 実験結果 2： MorphingAssist の効果
本節では， MorphingAssist の効果について次の 2 つの観図 5 中の 1 つの点は問合せ記述プロセス 1 つ Qi,j を表す．

点から評価する．(1) 確定問合せの検索結果の再現率と精度．

ただし，ユーザが全くヒントを見なかった 2 プロセスは除く．y(2)MorphingAssist の支援によりユーザが書き直した問合せが軸は | ∪k Hi,j,k |/|Qi,j |，つまり各問合せ記述プロセス内で表示

より精確なものになっているか．

したヒントの数 (被験者がヒントを表示しなかった場合は除く)

5. 4. 1 確定問合せの検索結果の再現率と精度の平均を表す．∪k は bug-union を求める記号を表し，∪k Hi,j,k

図 7 に ，正 解 問 合 せ の 検 索 結 果 に 対 す る 確 定 問 合 せ のは多重集合である．x 軸は Ci に対する ヒントの再現率を表す．

検索結果の再現率と精度を示す．再現率は |Result(dqi,j ) ∩ヒントの再現率とは，問合せ記述プロセス中で正解構成要素がResult(cqi )|/|Result(cqi )| で あ り，精 度 は |Result(dqi,j ) ∩どれだけ表示されたかを表すもので，|Ci ∩ ∪k Hi,j,k |/|Ci | にResult(cqi )|/|Result(dqi,j )| である．図 7 より多くの被験者よって求められる．ヒントの再現率の平均は 0.71 であり，ヒンは正しい問合せを記述することができたことが分かる．着目す

トの表示数の平均は 25.76 であった．本評価観点で精度を求めべき点は，被験者のうちの半分は SQL を書くことができない

ないのは，確定問合せでない問合せが書かれた意図は一般的に人であったことである．

不明であり，特定の意図をもって書かれた正解問合せに対する5. 4. 2 記述した問合せの変化精度を求めることは意味をなさないからである．図 5 の全 28

次に，本節では確定問合せに向けて問合せがどのようにプロセス中，4 プロセスで，再現率は 0.4 以下であった．しか変化したかを評価する．これは，前節で示した結果が本当にし，これは被験者が MorphingAssist システムを使わなかったMorphingAssist によるものかどうかを確認するためである．

ことが原因であった．

問合せのスコア．同じ問合せ記述プロセス内の問合せであって本実験では，30 問合せプロセス中，10 プロセスで，積集合をも，問合せ qi,j,k 同士を比較することは難しい．なぜなら，各問用いてヒントの表示数を減らす仕組み (4 節参照) が使われた．

合せの検索結果は異なるスキーマ構造を持っており，再現率とこの 10 プロセスにおいて，ヒントの表示数を減らす仕組みを精度を計算することが困難であるからである. 従って，我々は各使う前と後で，ヒントの表示数の平均は 43.22 から 9.71 に減

qi,j,k 毎に，その問合せがどれだけ正解問合せ cqi と違っている

図 9 最後の問合せのスコアの分布

図 7 確定問合せの検索結果の再現率と精度せを入力したユーザに対して，そのキーワード問合せを構造化
問合せに変更するためのヒントを提示する．評価実験により，支援手法を使ったユーザはより精確な問合せが記述できることを示した．今後の課題としては，Gradation の検索結果およびヒントのランキング手法の開発が挙げられる．

謝

辞ゼミなどにおいてコメントいただきました，筑波大学 杉本重雄教授，阪口哲男准教授，永森光晴講師に感謝いたします．本
研究の一部は JST さきがけ「情報環境と人」の支援による．
図 8 確定問合せのスコアの分布かを表すスコア (diﬀerence score) を付けることを考えた．このスコアは関数 dscq (q) で表す．このスコアは問合せ間の違いが小さいほど値が小さい．すなわち，q = cq の時，dscq (q) = 0
であり，q と cq の違いが大きければ大きいほど dscq (q) は大

文
[1]
[2]
[3]
[4]
[5]

きくなる．スコアの求め方の詳細は付録 2. に示す．
問合せ記述プロセス毎に，被験者が最初に書いた問合せ，確
定問合せ，最後の問合せのスコアを求めた．最初に書いた問合[6]

せのスコアが 1 になるように正規化すると，23 個の確定問合せのスコアの平均は 0.199 であった．最後の問合せにおいても，
スコアの平均は 0.310 であった．このことから，各被験者は最[7]

終的には正解問合せに近い問合せを記述できたことが分かる．
図 8 と 9 にスコアの詳細を示す．この図は，確定問合せ (図8) と最後の問合せ (図 9) のスコアのヒストグラムと累積度数[8]分布である．確定問合せのうち 82%はスコアが 0.2 以下であった．また，SQL を使うことができない被験者によって書かれた
確定問合せのうち 70%はスコアが 0.2 以下であった．更に確定[9]

問合せでないものも含む全ての最後の問合せに関しても，その70%はスコアが 0.2 以下であった．まとめると，これらの実験
結果は，平均的には，MorphingAssist がユーザがより精確な問合せ (正解問合せに近い問合せ) を記述することの支援に成功していることを示している．図 9 では，最後の問合せに対するスコアを示したが，実際には，ユーザが書き直した問合せが適切でないと感じた場合は，ユーザは検索の際には元の問合せを使えばよく，最後の問合せを使う必要はない．

[10]
[11]

献

DBpedia: wiki.dbpedia.org : About, http://www.dbpedia.org/.
ACM DIGITAL LIBRARY，http://dl.acm.org/.
dblp.rkbexplorer.com，http://dblp.rkbexplorer.com/.
W3C: LinkingOpenData, http://www.w3.org/wiki/SweoIG/
TaskForces/CommunityProjects/LinkingOpenData.
袖山広輝， 只石正輝， 安永ゆい， 品川徳秀， 森嶋厚行．“構造/テキスト Web データのためのハイブリッド問合せ言語”．Webとデータベースに関するフォーラム 2011，9 pages，(2011)．
Yui Yasunaga, Atsuyuki Morishima, Hiroki Sodeyama andMasateru Tadaishi. “Gradation: A Pay-as-You-Go Style
Hybrid Query Language for Structured and Text Data”,
Proceedings of the 2013 iConference (iConference 2013),
pp.209-220, (2013).
Demidova, E., Zhou, X. and Nejdl, W. “IQP: Incremental
query construction, a probabilistic approach”, 26th IEEE
International Conference on Data Engineering (ICDE 2010),
pp.349-352, (2010).
Chaitanya Mishra and Nick Koudas. “Interactive Query Refinement”, Proceedings of the 12th International Conference
on Extending Database Technology (EDBT 2009), pp.862873, (2009).
internet.com K.K. (Japan) “An article from internet.com
K.K.(Japan)”, http://japan.internet.com/wmnews/20090908/
5.html(2009).
Wikimedia Downloads, http://dumps.wikimedia.org/jawiki/20120603/.
DBpedia Japanese, http://ja.dbpedia.org/dumps/20120629/.

付

録

1. 実験で用いた情報要求と正解問合せ
実験で使用した情報要求とそれと対応する Gradation 問合せのリストは表 A· 1 の通りである．

2. スコア dscq (q) の求め方

6. まとめと今後の課題
本稿では，キーワード問合せと構造化問合せをシームレスに

本付録では，ユーザが書いた問合せ q と正解問合せ cq が与えられた時に，q と cq の違いを表すスコア (diﬀerence score)

融合した問合せ言語を利用して，ユーザによる構造化問合せのを計算するための関数 dscq (q) について説明する．この関数は記述を支援する手法を提案した．具体的には，キーワード問合5.4.2 節の評価で利用したものであり，q と cq の違いが小さい表 A· 2 c-penalty の値

表 A· 1 情報要求とそれと対応する Gradation 問合せのリスト
ID
n1
n2

n3

n4
n5
n6

n7

n8
n9
n10

Information Needs
Correct Gradation Query
神奈川にある公園を全て知りたい
dcterms:subject == “category-ja:神奈川県の公園”
東京都内にある医療機関全てと, その医療機関の所在地が知りたい(dcterms:subject == “category-ja:東 京 都 の 医 療 機 関” )[t uri,dbpprop-ja:所在地]
ロンドンがホームタウンであるサッカークラブとそのクラブのホームスタジアムが知りたい(dbpprop-ja:ホームタウン == “dbpedia-ja:ロンドン”) [t uri, dbppropja:スタジアム]
日本にある灯台を全て知りたい
dcterms:subject == “category-ja:日本の灯台”
日本にある女子高を全て知りたい
dcterms:subject == “category-ja:日本の女子高等学校”
日本のロックバンドと，そのバンドが所属しているレコード会社が知りたい(dcterms:subject == “category-ja:日本のロック・バンド”) . dbppropja:label . (dcterms:subject == “category-ja:日本のレコード会社”)
1990 年生まれのタレントを全員知りたい
dcterms:subject == “category-ja:日本のタレント” dbpprop-ja:生年== 1990
日本にある保守政党全てと，その政党の成立年が知りたい(dcterms:subject == “category-ja:日本の保守政党”)[t uri, dbppropja:成立年月日]
つくば市にある研究所を全て知りたい
dcterms:subject == “category-ja:つくば市の研究所”
イタリアセリエ A に所属するサッカークラブ全てと，その監督名が知りたい(dbpprop-ja:リ ー グ == “dbpedia-ja:セ リ エ A (サッカ ー)”)[t uri,dbpprop-ja:監督]

INPUT: query q, correct query cq
OUTPUT: diﬀference score score1: score = 0;
2: rest = components(cq);
3: // penalty for each components を計算
4: FOREACH ci ∈ components(q)5: cci = counterpartq,cq (ci )6: score = score + c-penalty(ci , cci );7: rest = rest - cci
8: ENDFOR
9: // penalty for missing components を計算
10: score = score + m-penalty * |rest|

図 A· 1 dscq (q) の計算

ほど値は小さくなる．すなわち，q = cq の時，dscq (q) = 0 であり，q と cq の違いが大きければ大きいほど dscq (q) は大き
くなる．
スコア dscq (q) は 図 A· 1 で求められる．具体的には，まず q
中の問合せ構成要素 ci ∈ components(q) に対して，それと対応する正解 cq 中の構成要素 ccj ∈ components(cq) を見つけ，
その 2 つがどれぐらい異なるかによってペナルティ(c-penalty)を加点する．次に，cq 中の構成要素 ccj ∈ components(cq)のうち，先の作業で使われなかった要素の数だけペナルティ(m-penalty) を加点する．図 A· 1 の 4-8 行目で，c-penalty を加点している．ここで，5 行目の counterpartq,cq (ci ) は，ci に対応する cq 中の構成要素を求める関数である．この詳細は下記 2. 1 節で述べる．また，6 行目の c-penalty(ci , ccj ) は構成要素の差異に応じた c-penalty を求める関数である．c-penalty の点数については下記 2. 2 節で述べる．2,7,10 行目で m-penalty
を加点している．10 行目の m-penalty は定数であり，今回は5 としているが，この点数についても下記 2. 2 節で述べる．
2. 1 構成要素の対応付け関数
counterpartq,cq は，ユーザが記述した問合せ q と 正解問合せ cq のペアがある時に，q 中の構成要素 ci が，cq 中のどの構
成要素の書き換えであるか（どの構成要素を意図して書いたか）を表す関数である．例えば，情報要求が「トムという俳優を全員知りたい」だった場合に，q = “tom actor”, cq = “name==tom

type==actor”, c1 = “tom”, cc1 = “name==tom” がある時，type of ci

keywordnon-keyword
component

relation between ci
cci

and

match(ci , cci )match(similar(ci ), cci )otherwise (cci = nil)
result(ci ) = result(cci )result(ci ) ⊃ result(cci )result(ci ) ⊂ result(cci )otherwise (cci = nil)∃cj∈
components(q)s.t. cj = cci
1
2
5
0
1
3
5

otherwise

3
4
5
0
2
3
5

counterpartq,cq (c1 ) = cc1 が成り立つ．関数 counterpartq,cq
は，q の構成要素の集合 components(q) を定義域とし，cq の構
成要素 components(cq) と nill からなる集合を値域とする．一般には，問合せ作成者の意図をくんで counterpartq,cq を計算するのは困難であるが，上記のように定義域と値域を限定する事により，「ccj が ci の類義語を含む」時に counterpartq,cq (ci ) = ccjが成立し，そうでない場合は counterpartq,cq (ci ) = nil が成立する，というヒューリスティクスが利用可能な場合がある．今回の実験で利用した全ての問合せは，このヒューリスティクスが適用可能なケースであったため，これを利用して counterpartq,cqを計算した．

2. 2 ペナルティの値の決定
c-penalty(ci , cci ) および m-penalty の値は次の原則に従い，それぞれ c-penalty を表 A· 2，m-penalty=5 とした．
原則： ci の存在によって q の検索結果が cq の検索結果により近くなる場合にペナルティの値はより小さくなるべきである．
「検索結果に近い」ということを定めるために次の 3 つのヒュー
リスティクス (H1,H2,H3) を用いる．表 A· 2 の行の場合分け
に H1 と H2 を用い，列の場合分けに H3 を用いている．

(H1) ci がキーワードであるとき，(a)cci がその一部に文字列
ci を含む場合，(b)cci がその一部に文字列 ci の類義語を含む場
合，(c)cci が nil である場合，の順に q の検索結果は cq の検索結果に近くなる．例えば，q の構成要素 ci が thomas であるときよりも，tom であるときの方が，q の検索結果は name==tomを含む正解問合せ cq の検索結果に近くなると考えられる．

(H2) ci が キ ー ワ ー ド 以 外 の 構 成 要 素 で あ る 場 合 は ，(a)result(ci ) = result(cci )，(b) result(ci ) ⊃ result(cci ), (c)result(ci ) ⊂ result(cci )，(d)cci = nil の順に q の検索結果
は cq の 検 索 結 果 に 近 く な る (こ こ で result(ci ) は ci 単 体の検索結果を表す)．例えば，type==japaneseActor よりも

type==allActor が問合せに含まれる方が，type==asiaActorを含む問合せの検索結果に近くなると考えられる．

(H3) ∃cj ∈ components(q) s.t. cj = counterpartq,cq (ci ) が成立するとし (ci と cj は異なってもよい)，q ′ を q − {cj } とする．この時，result(q) の方が result(q ′ ) よりも result(cq) に近くなる．例えば，q = “tom name==tom actor”， c1 = “tom”，

cq = “name==tom type==actor”，cc1 = “name==tom” である
場合を考える．この時，q は c2 = cc1 であるような c2 (つまり “name==tom”) を含む．更に，q ′ = “tom actor”， c′1 =“tom” であるとする．この時，result(q) の方が result(q ′ ) よ
りも result(cq) に近くなる．