DEIM Forum 2016 D7-2

集合差演算を含む問合せに対する why-not provenance
朴

柱英†

吉川

正俊††

† 京都大学 情報学研究科 社会情報学専攻 〒 606-8501 京都市左京区吉田本町†† 京都大学 情報学研究科 社会情報学専攻 〒 606-8501 京都市左京区吉田本町
E-mail: †pjy953@db.soc.i.kyoto-u.ac.jp, ††yoshikawa@i.kyoto-u.ac.jp
あらまし

why-not provenance は問合せの結果に対する利用者の「なぜ、このレコードは結果に含まれていないのか？」という疑問に答えるためのものである。結果と利用者の知識が一致しない時は、(1) 利用者の知識が間違っている、または、(2) 問合せ結果が実世界のデータを反映していない、のいずれかが理由である。また、(2) は (2a) 利用者が与えた問合せが間違っている、(2b) データベースに対象とするデータが存在しない、の二通りに分けることができる。今回、我々は問合せとレコードの条件（これを Why-not question と呼ぶ）が与えられたときに，そのレコードが問合せ結果に含まれない原因になる部分を探すことを目的にする。その結果、上述の (1) と (2) の状況に対応することができる。状況 (1) と (2) はアルゴリズムの前で与えられる外部条件により決まる。従来の研究では問合せとして

SPJUA(Selection, Projection, Join, Union, Aggregation) を対象とするものはあるが，問合せに複数個以上の集合差を含むものはない。我々は SPJU に加え集合差を含めた問合せを対象とする why-not provenance アルゴリズムを提案する。このアルゴリズムで一番重要な考え方は why-not question と問合せのどこが衝突しているかを探すことである。衝突しているところを探すために、元の問合せに why-not question の条件を追加した問合せを求め、元の問合せの一部を削除する方法で原因を探す。これは元のデータベースに why-not question が対象にするデータが含まれている限り、結果は必ず得られる。また、100MB 以下のデータベースに対して実時間で答を求めることができることを示す。問合せの修正やインスタンス修正は今後の課題である。
キーワード

データベース理論、問合せ処理、問合せ言語、データの provenance、why-not provenance

1. 序

論

Provenance の研究は Why(結果がなぜ出たのか？), How(結果がどうして出たのか？), Where(結果がどこから出たのか？)などに始まり最近は Why-not(結果がなぜ出ていないのか？)に関する研究も行われている。結果に対して provenance を知ることでシステム管理者はデバッギングやシステムメインテナ
ンスが楽になり、利用者はシステムへの理解度を高めると同時に、自分の間違った知識を修正できるようになる。これらいずれの場合でも、利用者が結果を詳しく理解できるようになることを意味する。
我々の論文は provenance の中で Why-not に関するものを扱っている。Why-not に関する研究は [12] を始め、最近活発に行われている。Why-not Provenance に関する研究は大きく

図 1 データと SQL 問合せの例、および SQL 問合せの木構造、■は [5]、▲ は [3]、• は [9] のアルゴリズムで計算される原因である

二つの分野に分けることができる。一つ目の分野は Why-not

Provenance を求めることを重点にする研究分野で、もう一つの分野 [13] は Why-not Provenance が利用者にどのような影響を与えるかに関する研究分野である。本論文は前者に含まれる。前者の研究分野で行われている研究は多様な SQL 文に対して Why-not Provenance を求めること、Why-not Provenanceの計算を高速化すること、及びそれらの応用を含む。
対象とする問合せの表現力を増強する研究は [12] の SPJ を最初とし、[10] の SPJUA まで研究され、最近は計算速度高速化の研究も行われている。[9] で集合差演算を含む問合せを対象としているが、ただ一つの集合差演算を含む問合せに限られる。
それゆえ、まだ複数個以上の集合差演算 (Set Diﬀerence) を含
む問合せを対象とした研究はない。そこで、我々は今回複数個以上の集合差演算を含む問合せに対応するための Why-not

Provenance アルゴリズムを提案する。また、従来のアルゴリ
ズムが持っている問題点としては問合せを処理する時、与えられた問合せの処理順序を木構造で表現することである。その結果、Why-not Provenance を計算するアルゴリズムは作られる木の形に影響を受けてしまう。その点を指摘し、解決す修正したり、新しい Instance を挿入したりする。[12], [11], [14]るためのアルゴリズムを提案した論文が [4] であるが、そこでが Instance-based explanations の研究で、[12] は SPJ, [11] はもまだ集合差を含む問合せは対象としてしていない。木の形

SPJUA, [14] は conjunctive queries を対象にしている。Query-に依存する従来の研究の問題点は図 1 に例示される。図 1 のbased explanations と同様に、集合差に関する研究はまだ行

Tree1 と Tree2 は与えられた SQL Query の異なる二つの処理

われていない。最後は Modification-based explanations であ法を表す木構造の一部である。しかし、従来のアルゴリズムにる。Modification-based explanations は問合せが間違ったといよると、“なぜ、名前が alice である人は結果に含まれていな

う仮定で問題になる問合せの部分を探し、それを修正すること

い の Why-not Question に対して Tree1 と Tree2 で計算されで、Why-not Question を答に含めさせるためのアルゴリズム

る Why-not Answer は異なる。Tree2 の場合は、[3], [5], [9] がを提案する。例えば、実世界ではシステムのエラーにより利用“student.age>25” を原因として指摘している。それに比べて、者の入力がそのまま問合せとして使われず他の値が問合せに

Tree1 の場合は [3], [5] は “student.lab = lab.prof” を原因とし使われる場合もあり、利用者が自分の入力として期待しているて指摘し、[9] は両方を原因として指摘している。それは木構造

答が結果に現れない可能性もある。そこで、問題になる問合せと [5] で定義された Successor(結果から逆にトレースして得らを見つけて修正をする。[16], [8], [17], [7] が Modification-based

れる関係）に依存する既存アルゴリズムの問題である。しかし、

explanations の研究で、[16] は SPJA, [8] は Top-k 問合せ、[17]我々が提案するアルゴリズムを用いると、木構造に依存せず両は Reverse Skyline 問合せ [7] は Reverse Top-k 問合せを対象

方を原因として得ることができる。

にしている。Query-based と Instance-based は互いに独立な以降、2 章で関連研究についてまとめ、3 章で理論的な背景をアプローチであるが、これらを統合するための研究もある。そ説明し、4 章ではアルゴリズムを提案する。また 5 章では 4 章の例としては [9] があり、hybrid explanation と呼ばれる方法で提案したアルゴリズムの実験結果とその考察を扱う。最後にを提案している。

6 章では結論とこれからの課題について述べる。

また、Why-not Provenance の技術的な研究ではないが、Why-

2. 関 連 研 究

not を知ることにより利用者のシステムへの理解度を高めることができるという研究も [13] で行なわれている。[13] の結果に

Why-not Provenance の最初の研究は Huang ら [12] によるよると、利用者は Why と How と Where より Why-not を知とされている。また、“Why-not” という単語は [5] で始めて使ることがシステムへの理解度が高くなるという実験結果を示われた。Why-not Provenance の研究の動機として言われるのしている。また、Why-not の応用研究もいくつか行われていはシステムと問合せ結果に対する利用者の疑問である。疑問はる。[2] では画像検索で Why-not の概念を使い、[6] では地理検利用者が持っている知識と問合せ結果が一致しないため発生す

索で Why-not の概念を使っている。また、SQL のみの説明にる。疑問の原因として言われるのは二つ存在する。一つは問合限定せず ontology を使った説明に関する研究 [15] も行なわれせの中身で、もう一つは問合せの対象になるデータベースでている。

ある。そのため、Why-not Provenance に関する研究も各々のケースに分けて行われている。

3. 基本的事項

まず、Why-not Provenance の研究は技術的に三つに分かれる。

本論文では datalog を使って理論的な説明を行う。再帰問合

一番目は、Query-based explanations である。Query-based

せを使わない限り SQL 問合せと datalog 問合せは相互に変換すexplanations は利用者の疑問の原因になる問合せの一部を探することができ、同じ結果を出す。第 3 章では我々らのアルゴリことを目的にする。問合せやデータベースが間違っているのでズムの説明のために必要な基本的な datalog の概念や Why-not

はなく、ただ問合せの一部が原因になって、利用者が期待する答の概念について書く。

が結果に現れないということを意味する。この、Query-based

3. 1 Datalog

explanations はただ探すだけで、修正のための方法は提案しdatalog のルールは head と body で構成されている。また、ていない。[5], [4], [3] が Query-based explanations の研究であbody は一つ以上の原子 (atom) で構成される。head は body

り、[5] は SPJU、[3] は SPJUA、[4] は数学の多項式を基盤にしを構成するすべての原子が真実 (true) であった時、答として出て why-not provenance を計算している。その結果木構造に依力すべきデータを指定する。その時、答がないというのは body

存しない計算結果を与えている。しかし、いずれの研究でも集を構成する原子の間で互いに衝突があることを意味する。衝合差は対象にしていない。二番目は、Instance-based explana-

突というのは、互いに矛盾な状態を意味する (e.g. A>50 と A

tions である。Instance-based explanations は問合せの原因が<30)。body を構成するのは EDB(Extensional database) や

Instance、すなわちデータベースにあると仮定する。実世界ではIDB(Intensional database) や条件文である。EDB は SQL 文

いろいろなデータがインタネット上に存在する。そのデータをの FROM に該当するもので、データベースを意味し、datalog

集めてデータベースに保存しておく時もある。その場合、データ

ではいつも事実として認められるものである。IDB は幾つかのが事実でない場合もあり得る。従って、利用者が正しい問合せをEDB や IDB や条件文で構成される relation である。条件文は入力しても利用者が期待している結果が得られない可能せもあSQL の WHERE に現れるものである (e.g. A>100, A=B)。理る。そこで、その考え方に基づいて問題になる Instance を探し

論的には body にある IDB が head にも現れることもあるが、今回は再帰の問合せは扱っていないのでその可能性は排除する。

Definition 3. 集合和と集合差を含まない datalog 問合せの答

また、本研究では body の中は IDB のみを含むか、EDB や条元の集合和と集合差を含まない datalog 問合せ q を

件文のみを含むかのいずれかとする。前者は集合和や集合差がresult(x1 , . . . , xn ) :- a1 , . . . , amある場合で、その IDB をそれぞれの原子として扱うことができる。後者は集合和や集合差がない問合せである。先のようなとする。この時、すべての EDB や条件文である al ∈ A(=∪m
i=1 ai ) により result は計算される。t ∈ result(x1 , . . . , xn )制約を使うと datalog で表現できるすべての問合せを扱えないに対して t のすべての集合 T を答、あるいは結果とする。

が、SPJUD に該当する SQL 問合せで扱う問合せはすべて扱える。次に、datalog の形式的な定義を [1] に基づいて与える。

Definition 4. datalog の中での衝突元の集合和と集合差を含まない datalog 問合せ q を

result(x1 , . . . , xn ) :- a1 , . . . , am

Definition 1. Syntax of datalog
本論文で使う datalog のルールは以下のようなものである。

とする。result(x1 , . . . , xn ) :-R1 (u1 ) :- R2 (u2 ), ... , Rn (un ), C1 , C2 , ... Cm .
n>
= 1 に対して、 R1 ,R2 ,...,Rn は関係名で、u1 ,...un は適切な大いような新しい ax があるとする。空集合ではない C ⊂ A(=∪m
i=1 ai ) に対して、AC = A\C を定義する。result(x1 , . . . , xn )きさの組を意味する。また、u1 に含まれる変数は必ず u2 , . . . , un:- AC , am が解を持つ時、C と am は互いに衝突している。

の中に含まれている。m >= 0 に対して、 C1 ,C2 ,...,Cm は条件文を意味する。条件文は u2 から un のいずれかに現れる二つのa1 , . . . , am , ax が解を持たな

3. 2 Why-not Question
Why-not Question は利用者の疑問である。利用者がデータ

変数を x,y とすると、x と y 、x と定数で作られる比較文であベースへの問合せ結果を見て、自分の知識と間違っている結る。

果があるとデータベースあるいは結果そのものに疑問を持つ。

R1 は datlaog ルールの head で、R2 , . . . , Rn , C1 , . . . , Cm は

その疑問が Why-not Question である。Why-not Question はdatalog のルールの body である。

[属性 op 値] の集合から成る。属性は datalog 問合せの結果にdatalog 問合せは、ルールの有限集合で表される。datalog の表れている属性で、op は=,>,>=,<,<=のいずれかの比較演算

問合せが集合和と集合差を含まない場合は、問合せを一つの子、値は演算子の対象になる変数や定数を意味する。例えば、ルールで表現できる。そのため、一つのルールにより構成され[A>100] というのは「属性 A の値が 100 より大きいものがな

る問合せは “conjunctive query” である。また、集合和と集合ぜないか」という Why-not Question を意味する。

差がある場合は、最終結果を表す関係（本論文では result) を

この場合、属性は結果に含まれる属性のいずれかである。こIDB のみで表現しそれぞれの IDB を集合和と集合差が含まれこで重要な点は同じ EDB でも違う属性名を持つことができるていない問合せと見なして問合せを作成する。

ということである。例えば、result(A, B) には a(A, B, C) がDefinition 2. EDB, IDB, 条件文
Extensional relation は body の中にしか存在しない関係で、Intensional relation は head に 存 在 す る 関 係 を 意 味 す る 。
EDB(Extensional database) はすべての Extensional relationの集合である。IDB(Intensional database) はすべての Inten-

sional relation の集合である。条件文は、EDB でも IDB でもない、属性と属性あるいは属性と定数間の比較文である。

あるが、result2(C, D) には a(C, D, E) が存在するかも知れな
い。しかし、本論文では同じ EDB には、同じ名前の属性名を使う。もし、ルールの中で同じ EDB が２回以上使われる場合
は、“a(A, B, C), a(D, E, F )” のようにすべての属性名に違う名前を付け、同じ物理データを参照にする二つの EDB と見なす。
また、利用者の疑問である Why-not Question を既存の問合せに追加できるように問合せ形に変更したのが Why-not Pred-

Example 1. datalog ルール

icate である、[A>100] という Why-not Question は datalog

result(A, B) :- a(A, B, C), b(D, E, F ), A = D, C>500, F =で使うために A>100 という Why-not Predicate になり、その“park′′ .

まま既存の問合せルールの body に追加することができる。こresult(A, B) は head であり、a(A, B, C) と b(D, E, F ) は各々の場合、Why-not Predicate が追加された新しい問合せはどんテーブル a の属性を順番に (A,B,C) とする、テーブル b のな場合でも結果は出て来ない。その理由は Why-not Predicate

属 性 を 順 番 に (D,E,F) と す る と い う こ と を 意 味 し 、A=Dが既存の問合せと衝突しているからである。例えば、結果にはや C>500,F=“parkは条件文である。ここで a(A, B, C) と“A>100” を満足するレコードがないのに、問合せに “A>100”b(D, E, F ) は（データベースにある）テーブルなので EDB でを追加すると、元の結果から “A>100” で絞り込むことを意味ある。

するので結果は空集合になる。

Example 2. datalog 問合せ

Definition 5. Why-not Question

result(A, B) :- result2(A, B), ¬result3(A, B).

Why-not Question は利用者の疑問であり、Why-not Ques-

result2(A, B) :- a(A, B, C), C = “CS .

tion を満足する答は結果に含まれていない。Why-not Ques-

result3(A, B) :- a(A, B, C), C = “EE .

tion は [属 性 op 値] の 集 合 で あ る 。op に 該 当 す る も の は

result2(A, B) と result3(A, B) は IDB であり、¬ は否定を意=,!=,>,>=,<,<=である。値に該当するものは “属性”、“定味する (SQL の集合差に対応する)

数” である。

Definition 6. Why-not Predicate

対して解を持つ。

Why-not Predicate は Why-not Question であるものを、dat-

9. result と result max の差分を計算する。その差分になる条

alog に条件として追加するための条件文の形である。

件文は Why-not Question が答にならなかった原因である。

属性 op 値, ... , 属性 op 値

である。

3. 3 Why-not Answer

10. この条件文の集合は、既存の Why-not Answer の定義と一致する。

Why-not Answer は問合せの中で Why-not Question と衝

証明 1 により、データベースに Why-not Question が含まれ突しているところである。すなわち、Why-not Answer を修正ている限り Why-not Answer を求めることができるというこあるいは削除することで我々は Why-not Question に該当するとが証明された。この証明を使うためにデータベースはいつも答を結果から得ることができる。Why-not Answer を求めるこ事実である（利用者の知識、あるいは問合せが間違っている）とが本論文の目標である。利用者あるいは管理者は Why-notと仮定をする。

Answer を見ることで問合せの問題か利用者の知識の問題かが
名前

専門

性別

年齢

James

EE

M

25

名前

専門

性別

Definition 7. 集合和と集合差を含まない問合せの Why-not

Alice

EE

W

35

James

EE

M

Answer

Bob

CS

M

33

わかるようになる。

表 1 Table

元の集合和と集合差を含まない datalog 問合せ q を

表 2 Table

年齢

25
B

A

result(x1 , . . . , xn ) :- a1 , . . . , amとする．x は属性を表し、a は EDB や条件文を表す。ここで一般性を失うことなく，このルールの body に現れる原子のうち

a1 , . . . , al (l <= m) を条件文とする．また，Why-not predicate
wを
w 1 , . . . , wkと す る ．こ の と き ，q に 対 す る w の Why-not Answer は ，{a1 , . . . , al } の部分集合で w と衝突する部分である．

Example 3. Why-not Question と Why-not Answer
SQL Queryselect * from a where 専門=‘EE

AND 年齢<34 AND 性別=‘M .
Datalog Query
result(A, B, C, D) :- a(A, B, C, D), B = ‘EE , C = ‘M
, D<34.

Proposition 1. (Why-not Answer の存在条件)

Table A に上記の問合せを適用すると Table B のような結果がWhy-not Question を満足するレコードが問合せの答には含ま出る。この結果から利用者は次のような疑問を持つ。

れていなく問合せの対象になるデータベースには含まれている

どうして Bob は結果に含まれていないのか？”時は、必ず Why-not Answer が存在する。

Proof 1. Why-not Answer の存在
1. [属性 op 値] の集合として与えられた Why-not Question が与えられたとする。

2. Why-not Question から Why-not predicate を求めることができる。

3. 利用者が持っている知識が真実である限り、Why-not Question はデータベースに含まれている。
4. 元の集合和と集合差を含まない問合せは result(x1 , …, xn ):- a1 , …, an であり、x は属性を表し、a は EDB や条件文を表す。一般には a に IDB も含まれているが、集合和と集合差がない限りは IDB は存在しない。

5.

条 件 文 が な い EDB の み で 構 成 さ れ る 新 し い 問 合 せresult2(x1 , …, xm ) :- a1 , …, al を定義する。∀i, ai ∈ EDB
6. ３が成立する限り、result2 は Why-not Question に対してこれが利用者の Why-not Question である。
証 明 １ の ５ に よ る と 、result2 は result2(A, B, C, D) :-a(A, B, C, D) で あ る 。こ の result2(A, B, C, D) に よ る と 、
利 用 者 が 疑 問 と し て い る Bob は result2(A, B, C, D) に 表
れ て い る 。result3 の 候 補 と し て は result3(A, B, C, D) :-a(A, B, C, D), C = ‘M .、result3(A, B, C, D) :- a(A, B, C,
D), D<34.、 result3(A, B, C, D) :- a(A, B, C, D), C = ‘M
, D<34. がある。この三つの候補の中で一番条件が多く追加されているものは result3(A, B, C, D) :- a(A, B, C, D), C = ‘M

, D<34 である。result3 と result の差分は B=‘EE である。
したがって、我々は B=‘EE が Bob を結果の中に含まらないようにした原因であることを分かった。すなわち、B=‘EE が

Why-not Answer である。実際に我々は B=‘EE を削除する
か、B=‘CSにすることで Bob を結果に出すことができる。

今までの定義は Negation 含まれていない問合せに対する定解を持つ。

義であった。Negation が含まれていない問合せは単純に利用

7. この時、result2 に条件文を追加した result3 を定義する。

者の Why-not Question と衝突しているところを見つけるこ

result3 は result2 に既存の問合せである result にある条件文とで Why-not Answer を求められた。しかし、我々の論文でを追加したものであり、Why-not Question に対して解を持つは Negation も扱っている。Negation がある場合の Why-not

問合せである。

Answer は既存の定義とは異なるところがある。また、集合和

8. result3 の中で一番、多くの条件文が追加されたものらをの場合と同様に集合差が含まれている問合せは最終結果を表す

result max と定義する。result max は Why-not Question に関係 (result) が IDB のみで構成されることにする。これから、Negation と Negation が含まれている問合せに対する Why-notと、集合差が含まれている問合せは部分問合せが互いに違う

Answer を定義する。

役割をするからである。例えば、A except B の時、A と B はDefinition 8. datalog の中の Negation
Negation は relation の前に not あるいは ¬ をつけて表現する。
それがつけられている時の解釈は [1] の通りに以下のようである。

datalog の Stratified Semantics を使い、¬R(x) は “x はすべての可能なドメイン集合 (Active domain) に含まれ、x∈/Rを満足すること” を意味する。

Definition 9. 集合和と集合差を含む datalog 問合せの答
元の集合和と集合差を含む datalog 問合せ q を

result(x1 , . . . , xn ) :- I1 , . . . , Imとする。また、Ik はIk (xk1 , . . . , xkn ) :- ak1 , . . . , akmとする。この時、すべての EDB や条件文である akl ∈ A(=∪m
i=1 aki ) により Ik は計算されて、それらにより result が計算される。t ∈ result(x1 , . . . , xn ) に対して t のすべての集合 T
を答、あるいは結果とする。

Why-not Provenance を同じ方法で求めることができないし、それが従来のアルゴリズムの問題であった。今回、我々のアルゴリズムで使う方法は B が持つ特徴に起因する。A except Bの問合せにより、利用者が期待する答が結果に含まれていない
時は、A に答が含まれていないか、B に答が含まれているか、
いずれかも成立するかである。A に答が含まれていない時は、
今までの方法とおなじ方法で Why-not Answer を計算することができる。しかし、B に答が含まれているのは違う方法を使
わないといけない。その理由を証明３で示す。

Proof 3. 集合差の場合
1. 集合差が含まれている問合せを result とする。result(x1 , …
, xn ) :- I1 (x1 , …, xn ), ¬ I2 (x1 , …, xn ). I が三つ以上の場合でも 2 と 3 を繰り返すことで求められる。

2. I1 に答が含まれていない場合は証明１で証明できる。
3. I2 に答が含まれている場合は、I1 のように原因を特定することができない。なぜかというと、I2 の中にあるすべての条件
文が Why-not Question と衝突しないからである。これは、I2

Definition 10. Why-not Answerの中にあるすべての条件文が原因になる可能性があることを意

元の集合和と集合差を含む datalog 問合せ q を味する。

result(x1 , . . . , xn ) :- I1 , . . . , Imとする。また、Ik はIk (xk1 , . . . , xkn ) :- ak1 , . . . , akmとする。a は EDB や条件文を表し、x は属性を表し、I は IDBを表す。その中で、¬ が付けられていない P1 , . . . , Po ∈ I(=∪m<
i=1 Ii ) (o = m) を肯定 IDB とする。また、¬ が付けられて∪いる N1 , . . . , Nk ∈ I(= mi=1 Ii ) (k<m) を否定 IDB とする。
このとき、利用者の疑問である Why-not Question に対する答
えが肯定 IDB の結果に含まれていないときは、定義７のように

Why-not Answer の定義に従う。また、Why-not Question に対する答えが否定 IDB の結果に含まれているときは、否定 IDBの中にあるすべての条件文の組み合わせが Why-not Answerになる可能性を持つ。

4. したがって、I2 で答が含まれている場合は、I2 の中にあるすべての条件文が Why-not Provenance の原因になる。
そのゆえ、集合和と集合差のいずれかにも問題がある場合は、証明１と証明３で Why-not Answer を探すことができる。

4. アルゴリズム
我々のアルゴリズムはデータベースの上での計算を繰り返す。アルゴリズム 1 では Why-not Question が条件文の形である Why-not Predicate で問合せに追加され、元の問合せの条件の一部が削除されたものが解を持っているかどうか確認する。
集合和と集合差がない問合せはアルゴリズム１で計算できる。

combination 関数は A の集合から i 個の combination を計算する関数である。もし、1 個の場合で解が存在したら、2 個の

3. 4 集合和と集合差

場合は計算せずに終わる。

集合和と集合差が問合せに含まれている場合でも証明１を応

アルゴリズム２は問合せがあった時、それを部分問合せに分解用することで証明できる。ここでは、集合和と集合差があったするためのアルゴリズムである。自然結合で繋がっている条件

場合に、どう証明するかとそれが事実であることを示す。まず、

文と EDB(SQL 文の FROM のところ) で構成される小さい問

集合和の場合は証明１を繰り返すことで証明できる。

合せを作ってそれを部分問合せとしてする。このアルゴリズム

Proof 2. 集合和の場合
1. 集合和が含まれている問合せを result とする。result(x1 , …
, xn ) :- I1 (x1 , …, xn ),…,In (x1 , …, xn )., ∀m, Im (x1 , …, xn ) :−a1 , …, al
2. 各々の ∀m, Im (x1 , …, xn ) は、証明１に表れている問合せと同じ形である。したがって、それぞれの問合せにに対して証明１を適用することで証明できる。

を使うことで、直積集合 (Cartesian product) を早く計算できるようになる。大量のデータを使う時は、自然結合がないとデータベースでの計算が遅くなる。それを防ぐためには自然結合で繋がっていないものを独立的に計算する必要性がある。
集合和と集合差が含まれている場合はアルゴリズム３を使う。
アルゴリズム３ではまず原因になる IDB を探す。not が付いていない部分問合せは Why-not Question を追加した問合せが答を出さない時、原因の可能性が有る。逆に、not が付いている

集合和の場合は集合和で繋がっているいずれかの部分問合

問合せは Why-not Question を追加した問合せが答を出す時、せも対等である。しかし、集合差の場合は違う。なぜかという原因の可能性が有る。アルゴリズム３により、原因の可能性があると判断された IDB はアルゴリズム１を使って細かい条件

ずそのまま使っている。しかし、Why の質問はそのまま使わず、文を探す。not が付いていない問合せはアルゴリズム１により‘not’ を付けて Why-not Predicate を表現する。例えば、Why特定できるが、not が付いている場合は、アルゴリズム１によand Why-not predicate “A=‘Bob , not A = ‘Alice

る特定ができない。したがって、証明３により not がついていするのは Alice は結果に含まれているが Bob は結果に含まれてる問合せが原因になった時は、その問合せのすべての条件文をいない理由を出力するために使われる。もし、原因になる部分

Why-not Answer とする。

が ‘not’ が付いていない問合せであれば Why-not predicate とresult true は Why-not Answer の可能性がない条件文である。

同様に計算できる。。しかし、‘not’ が付いている部分問合せがが意味

これを使う理由は、集合和と集合差がある場合、すべての部分原因であれば、すべての条件文が原因ではなくアルゴリズム 3

問合せが満足する Why-not Answer を保証するためである。し2 で原因になる条件文を探す。
の⃝たがって、最後の結果は Why-not Answer から result true を

Algorithm 2

除いた条件文の集合になる。

1: input : 条件文 A, EDB F

Algorithm 1

2: output : subQueries Qs

1 は、アルゴリズム 3 の 9 行目と 16 行目に該当する。⃝
2 は, アル
1: ⃝3: if F が全て natural join で繋がっている then4:

Q = A と F により構成される SQL 文

2: input : why-not Question Wq , Query Q

5:

Qs = Qs + Q

3: output : Why-not Answer Wa

6:

return Qs

4: A = Q の条件文の集合, F = Q の EDB

7: else if F の一部が natural join で繋がっている then

5: for i = 1 to len(A) do

8:

ゴリズム 3 の 12 行目に該当する。

6:
7:
8:

for i=1 to len(A) do
if A[i] が natural join で繋がっている F の一部に含まれ9:

ConArr = combination(A,i)

る thenfor j = 1 to len(ConArr) do

A = A + A[i]A1 = A - ConArr[j], result = [] ,result true = []10:

end if9:

Wp = Wq の Why-not Predicate. A1 =A1 + Wp

11:

10:

SubQueries = アルゴリズム 2(A1 ,F)

12:

Q = A と F の一部により構成される SQL 文

11:for j = 1 to len(SubQueries) do

13:

Qs = Qs + Q

if SubQueries[i] then14:

A = []

condition = True

15:

for i=1 to len(F) do

12:
13:

else

14:
15:
16:

condition = False

17:

break

18:

for j=1 to len(A) do
if A[j] が F[i] の演算である thenA = A + A[j]19:

end if17:

if F[i] が natural join で繋がっていない then16:

end if18:

end for20:

19:

if condition then21:

end for

1 result =result + subset⃝

22:

Q = F[i] と A により構成される SQL 文

2 result true = result true + ConArr[j]⃝23:Qs = Qs + Q

20:
21:
22:

1 result true = result true + ConArr[j]⃝23:

end if

24:

else

end for25:
26:

end forend for27:

return Qs

26:

2 break⃝

28: else if 全ての EDB が natural join で繋がっていない then27:

if result then

29:

break

30:

A = []

31:

for j=1 to len(A) do

24:
25:

28:
29:

end ifend iffor i=1 to len(F) do

if A[j] が F[i] の演算 then32:

30: end for

A = A + A[j]33:

end if34:

4. 1 Why と Why-not

35:

end for

この節では Why と Why-not 質問が同時にあった時、対応

36:

Q = F[i] と A で構成される SQL 文
Qs = Qs + Q

できることを示す。Why は答に対して “どうして答が出たか

37:について理由を説明する。Why-not は疑問に対して “どうして38:

end for39:

return Qs

疑問に該当する答が出てこないかについて理由を説明する。

すなわち、互いに逆のことを説明している。datalog を使うとnegation を意味する ‘not’ を使って集合差を表現することができる。アルゴリズム 1 では Why-not Predicate を ‘not’ をつけ

40: end if表 3 SQL 問合せ

Algorithm 3
1 why-not Ques1: Wq が Why and Why-not Question の場合は⃝,

問合せ

Q1

2
tion の場合は⃝= co.code and c.population >10000000

3: output : 原因である IDB 集合, Why-not Answer Wa

Q2

7:
8:

*

from

city

as

c,country

as

co

where

except select * from city as c,country as co whereWp = Wq の Why-not Predicate, result = [],result true =[]selectc.countrycode = co.code and c.population>9000000

5: for i=1 to len(I) do
6:

select * from city as c,country as co,countrylanguage
as cl where c.countrycode = co.code and cl.countrycode

2: input : why-not Question Wq , Query Q

4: I = Q の IDB の集合

表現

c.countrycode = co.code and c.population<90000

Q3
if I[i] に’not’ が付いている thenselect

*

from

city

as

c,country

as

co

where

c.countrycode = co.code and c.population>9000000

if I[i] + Wp が結果を出す thenexcept select * from city as c,country as co where9:

1 アルゴリズム 1(I[i], not Wq )⃝c.countrycode = co.code and c.population<90000 and

10:

2 Wa = Wa + I[i] のすべての条件文⃝

c.country=’China’

11:

13:

Q4

else

and ol.orderid = o.orderid and p.prod id = ol.prod id

end if

14:

else if I[i] に’not’ が付いていない then15:

if I[i] + Wp が結果を出さない then

17:

20:

and ol.quantity>4 union select * from orders aso,customers as c,orderlines as ol,products as p
where o.customerid = c.customerid and ol.orderid

else

=

result true = result true + I[i] のすべての条件文

18:
19:

and c.income >= 100000 and c.country = ’China’

アルゴリズム 1(I[i], Wq )16:

select * from orders as o,customers as c,orderlines asol,products as p where o.customerid = c.customerid

アルゴリズム 1(l[i], Wq )12:

end ifo.orderidandp.prod id=

ol.prod id

ando.totalamount >432 and p<10

Q5

select * from customer as c,orders as o,lineitem as lwhere o.orderdate<’1998-07-21’ and l.shipdate>’1998-

end if

21: end for

07-21’ and c.custkey=o.custkey and o.orderkey=

22: Wa =Wa - result truel.orderkey

表4

5. 実

験

本章では 4 章で表れているアルゴリズムの実験評価を行う。実験で使うデータとして、“http://pgfoundry.org/projects/dbsam

ples/” に公開されている “World” と “dellstore2” を使う。それぞれの容量は 81KB と 2.16MB であり、現実の状況を反映し問合せ

Why-not Question

World1

Q1

c.name=’China’

World2

Q2

c.name=’China’

World3Q3co.name=’China’ and co.name!=’South Korea’(Why and Why-not)dellstore1

Q4

仮想 1

Q5

ている。また、仮想のデータ (TPC-H) を容量ごとに用意し、1MB から 10GB までのデータへの実験を行った。実験で使われ

シナリオ

シナリオ

c.country=’China’o.orderdate<’1996-01-01’ and l.extendedprice>50000

仮想 2

る計算機ーの仕様は MAC OS X10.10.5, 8GB RAM, 1.7 GHzQ5l.extendedprice>100000 and o.orderdate =l.commitdate and c.nationkey=4

Intel Core i7 でデータベースは PostgreSQL を使う。
表 5 Why-not Answer

実験の手順は “1. 問合せを作る.2. 結果を見て Why-not Ques-

tion をする。3. アルゴリズムに入力し Why-not Answer を求める” である。まず、表４に示す問合せに対してシナリオを設定し実験を行う。それぞれのシナリオは Why-not Question とシナリオ

Why-not Answer

World1’c.countrycode = co.code’, ’c.population>10000000’

World2’c.population<90000’

World3(’c.countrycode = co.code’, ’co.name = ’China”),

問合せが実行されるデータベースが与えられる。実験で使うシ
ナリオは表 5 のようである。

(’c.population<90000’, ’co.name = ’China’)dellstore1 ’ol.quantity>4’ , ’o.totalamount >432’, ’p.price<10’

それぞれのシナリオに対する実験結果を図２と図３に与える。

仮想 1’l.shipdate>’1998-07-21’, ’o.orderkey=l.orderkey’

図２は World1、World2、World3、dellstore1 の実行時間であ仮想 2’o.orderkey=l.orderkey’

る。World1、World2、World3 は同じデータベースに対して異なる問合せと異なる Why-not Question であるが、実行時間はている。また、[4] は仮想１ (simple query) が仮想 2(complex

あまり変わらないことが分かる。dellstore1 は World データにquery) より早く計算されるが、我々のアルゴリズムは逆であ比べて容量が大きいデータベースを対象にしている。したがっる。その理由は我々のアルゴリズムはデータベースを使って計て、実行時間も容量に比例し増加することを確認できる。仮想算しているからである。データベースはデータベースの中にあ

1 と仮想 2 は [4] のアルゴリズムとの時間比較のためのシナリオ

る最適機により自然結合などの演算を処理する前に処理されるである。同じ実験環境ではないので、正確な比較は不可能であ

データを絞り込むことが出来るなら、先に絞り込んでから演算るが、仮想 2 の質問に対しては 10GB で 10 倍以上早く計算しを行う。したがって、相対的に条件文が多い complex query の方が simple query の方より早く処理される。また、仮想デー
タの場合は実験ではインデックスを使っていないがインデックスを使うことで、より早く Why-not Answer を計算できると期待している。最後に、今回の実験では集合和と集合差の両方を使う問合せは対象にしていないが、その場合でもアルゴリズ
ム 1 をもう一回使うだけで Why-not Answer を求めることが
出来る。

図2

実データのアルゴリズムの処理時間

図 3 仮想データのアルゴリズムの処理時間

6. 結

論

本論文では集合差を含む問合せに対応する Why-not アルゴリ
ズムを提案した。Why-not 技術は利用者の疑問を入力として、疑問を解決するための解決案を提案するものである。Why-not
技術を利用することで、利用者はデータベースへの信頼度を高められる。また、管理者はディバギングやシステムメインテナ
ンスが楽になる。本論文で提案されたアルゴリズムはデータベースのでの計算を繰り返すことで Why-not Answer を計算する。その結果、疑問が詳しいければ詳しいほど実行時間が短くなることも分かった。しかし、疑問の原因になる条件文を見つけるだけではなく、疑問を解決するための問合せやデータベースの修正は今後の課題である。
文

献[1] Serge Abiteboul, Richard Hull, and Victor Vianu. Foundations of Databases. Addison-Wesley, 1995.
[2] Sourav S. Bhowmick, Aixin Sun, and Ba Quan Truong. Why
not, wine?: Towards answering why-not questions in social
image search. In Proceedings of the 21st ACM International Conference on Multimedia, MM ’13, pages 917–926,

New York, NY, USA, 2013. ACM.
[3] Nicole Bidoit, Melanie Herschel, and Katerina Tzompanaki.
Query-based why-not provenance with nedexplain. In Proceedings of the 17th International Conference on Extending
Database Technology, EDBT 2014, Athens, Greece, March
24-28, 2014., pages 145–156, 2014.
[4] Nicole Bidoit, Melanie Herschel, and Katerina Tzompanaki.
Eﬃciently and Eﬀectively Answering Why-Not Questions
based on Provenance Polynomials. Research Report RR8697, OAK team, Inria Saclay ; INRIA, March 2015.
[5] Adriane Chapman and H. V. Jagadish. Why not? In Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data, SIGMOD ’09, pages 523–534,
New York, NY, USA, 2009. ACM.
[6] Lei Chen, Xin Lin, Haibo Hu, Christian S Jensen, and Jianliang Xu. Answering why-not questions on spatial keyword
top-k queries. In Data Engineering (ICDE), 2015 IEEE
31st International Conference on, pages 279–290. IEEE,2015.
[7] Yunjun Gao, Qing Liu, Gang Chen, Baihua Zheng, and Linlin Zhou. Answering why-not questions on reverse top-k
queries. Proc. VLDB Endow., 8(7):738–749, February 2015.
[8] Zhian He and Eric Lo. Answering why-not questions on topk queries. Knowledge and Data Engineering, IEEE Transactions on, 26(6):1300–1315, 2014.
[9] Melanie Herschel. Wondering why data are missing fromquery results?: ask conseil why-not. In Proceedings of the
22nd ACM international conference on Conference on information &#38; knowledge management, CIKM ’13, pages
2213–2218, New York, NY, USA, 2013. ACM.
[10] Melanie Herschel and Mauricio A. Hernández. Explaining
missing answers to spjua queries. Proc. VLDB Endow., 3(12):185–196, September 2010.
[11] Melanie Herschel, Mauricio A. Hernández, and Wang-Chiew
Tan. Artemis: A system for analyzing missing answers.
Proc. VLDB Endow., 2(2):1550–1553, August 2009.
[12] Jiansheng Huang, Ting Chen, AnHai Doan, and Jeﬀrey F.
Naughton. On the provenance of non-answers to queries
over extracted data. Proc. VLDB Endow., 1(1):736–747,
August 2008.
[13] Brian Y. Lim, Anind K. Dey, and Daniel Avrahami. Why
and why not explanations improve the intelligibility ofcontext-aware intelligent systems. In Proceedings of the
SIGCHI Conference on Human Factors in Computing Systems, CHI ’09, pages 2119–2128, New York, NY, USA, 2009.
ACM.
[14] Alexandra Meliou, Wolfgang Gatterbauer, Katherine F.
Moore, and Dan Suciu. The complexity of causality andresponsibility for query answers and non-answers. Proc.
VLDB Endow., 4(1):34–45, October 2010.
[15] Balder ten Cate, Cristina Civili, Evgeny Sherkhonov, and
Wang-Chiew Tan. High-level why-not explanations using
ontologies. In Proceedings of the 34th ACM Symposium on
Principles of Database Systems, PODS ’15, pages 31–43,
New York, NY, USA, 2015. ACM.
[16] Quoc Trung Tran and Chee-Yong Chan. How to conquer
why-not questions. In Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data,
SIGMOD ’10, pages 15–26, New York, NY, USA, 2010.
ACM.
[17] Rui Zhou, Chengfei Liu, and Md. Saiful Islam. On answering why-not questions in reverse skyline queries. In
Proceedings of the 2013 IEEE International Conference on
Data Engineering (ICDE 2013), ICDE ’13, pages 973–984,
Washington, DC, USA, 2013. IEEE Computer Society.