DEIM Forum 2019 I4-3

データベース問合せ結果の差分に基づくセルの価値付けに関する研究鍋谷 優斗†

吉川 正俊††† 京都大学大学院情報学研究科 〒 606-8501 京都府京都市左京区吉田本町†† 京都大学大学院情報学研究科 〒 606-8501 京都府京都市左京区吉田本町
E-mail: †ynabetani@db.soc.i.kyoto-u.ac.jp, ††yoshikawa@i.kyoto-u.ac.jp

Cheney らはサーベイ [2] で三つの起源 “Where-Provenance”,“How-Provenance”, “Why-Provenance” を紹介している．

data provider

そこで本研究では，2. で上記の研究について説明した後，4. でcontribution
data registrar

その研究を拡張し，各セルごとにデータの起源を示す直接来歴
注釈と，そのデータがどのデータの貢献で存在しているかを示💰data creator

💰 ,q

💰

buyer

q(D)

💰

q(D)

database D

す間接来歴注釈を定義し，直接来歴注釈及び間接来歴注釈の与えられた関係データベースに対して演算 (選択，射影，和，自然
結合，集約関数) の実行結果の関係における各セルの直接来歴
注釈と間接来歴注釈の定義を与える．これを定義することで結図 1 利益分配のイメージ

果のデータを提供した人物および結果のデータを得るために貢献した人物を特定することができると考える．次に 5. で，デー
タベースの差分に基づいたデータの価値の定義を行い，6. では

1. は じ め に
日本は海外に比べてデータを活用したビジネス展開があまり進んでいない状況であり，情報銀行 [9] という事業が考案されている．情報銀行とは，個人とのデータ活用に関する契約等に基づき，PDS(Personal Data Store) と呼ばれる，他社保有デー
タの集約を含め，個人が自らの意思で自らのデータを蓄積・管理するための仕組みを活用して，個人のデータを管理すると共に，個人の支持またはあらかじめ指定した条件に基づき個人に変わり妥当性を判断の上，データを第三者 (他の事業者) に提供する事業のことである．このような，個人情報を含めた多種多様で大量のデータの円滑な流通を実現するために個人の関与のもとでデータ流通・活用を進める仕組みが有効だと考えられている [7]．
情報銀行を実現に近づけるため，パーソナルデータの価値付けを行うことは必要不可欠である．パーソナルデータの価値を考える研究は [6], [8] でも行われている．本研究は [10] に続いて，データの価値づけにおける尺度および価値付けの手法の開発を目指す．そもそも情報は他人に利用されて初めて価値があるとわかるものなので，実際に使われたデータから起源をたどり提供者に報酬を与える，という形が適していると考える．図 1 は，問合せを行う者 data buyer が，その問合せ q とデータに対する報酬$をデータベース D に送り，データベース D は受け取った問合せに対する結果 q(D) を data buyer に返し，その結果のデータを提供した人物である，データ登録者やデータ作成者のようなデータ提供者に報酬を分配する流れを示す．
データの起源を考えるという研究は [2] すでに多くのものがあり，さらに，4. で定義した注釈付きの問合せ演算を利用して，5. での差分計算の効率化が可能となる差分等価性について証明を行
い．最後に，7. で，注釈に分配した報酬を，さらにデータ提供
者へと還元する手法について考える．以上の流れで，データに与えられた報酬を，データ提供者に適切に分配する考えを提案する．

2. 関 連 研 究
文献 [2] では，データ起源について “Where-Provenance”,“How-Provenance”, “Why-Provenance” の三つの考え方を紹介している．

“Where-Provenance” は，ある関係に対する問合せの結果得られたデータのセルが元の関係のどのセルからきたものなのかを考えるもので，問合せ前の各セルそれぞれにラベル付けを行なっておくことで，問合せ結果の関係のセルが問合せ前の関係のどのセルから得られたものかを考えるものである．例えば図2 のように二つの関係 R1 , R2 を用意し，この二つの関係を自然結合した結果 R1 ▷◁ R2 について “Where-Provenance” を考えると，まずはじめに自然結合を行う前の二つの関係のセルにそれぞれ a1 , a2 , ... のようにラベルづけを行なっている．そして自然結合の結果の関係のセルが，元の二つの関係のどのセルから得られたものなのかを見て，そのセルのラベルを結果のセルに付与している．結果の関係の (1, 1) 成分のセル 1 は，R1 の(1, 1) 成分 1 と R2 の (1, 1) 成分 1 が結合してできたものなので，元の二つのセルのラベル a1 と a5 を結果のセルの 1 に付与している．“Where-Provenance” は等価な問合せに対して違う結果を返してしまう場合もあり，[2] では等価な問合せの結
—1—

A

B

t1

1

2

t1

1

2

t2

2

3

t2

2

3

A B

図 2 “Where-Provenance” におけるラベルづけ

図4 R

図 5 πA R

図 6 πB (R1 ▷◁ R2 )表す．ここで，条件式 c については，最小の条件式を二項演算子 ∧(AND),∨(OR) で繋いだ条件式として捉える．最小の条件
式とは，（ 1 ） 属性と属性
図 3 “How-Provenance” におけるタグづけ

果のラベルを全て含んだ結果を返すことで等価性を保つことができるということを紹介している．
次に，“How-Provenance” はある関係に対する問合せの結果得られたデータの組が，どのようにして得られたのかを考えている．結果の組がどのような演算の結果により得られたのかを“provenance semiring” と呼ばれる，可換半環 (K, 0, 1, +, ·) による多項式で表現する．ここで可換半環 K は，区別された値0 を含む，要素の集合である．これを利用して，関係代数演算
を可換半環の演算に写像する．写像モデルを “K -relation” としている．“K -relation” は，任意の組に対する関数 R として定義する．ここで関数 R とは，関係における組を K の 0 以外の要素へ写像するものである．先ほどの関係 R1 , R2 を自然結合した例で “How-Provenance” について考えると，図 3 で表される通り，まず二つの関係 R1 , R2 の各組に t1 , t2 , t3 , t4 のようにタグづけをして自然結合を行う．結果の関係の各組のタグは，その組の元となった組のタグ同士の積 (AND) で表現される．これはその二つのタグの両方が存在して初めて結果の関係が得られるということを意味している．“Why-Provenance” では，“How-Provenance” よりも簡略的に起源を考えるもので，演算式ではなく集合でそれを表現する．図 3 において一つ目の組の “ Why-Provenance” は {t1 , t3 }, 二つ目の組は {t2 , t3 } となる．

Green ら [4] はデータ起源に関する種々の定義の関係についてまとめている．また，起源の情報自体を対象にする問合せ言語 [5] に関しても考えられている．

3. 準

備

本研究で利用する用語についてここで定義しておく．
ある関係 R における組 t の属性 A のセルを (t, A) で表し，関係 R が含む属性集合を att(R) と表すものとする．
本研究で対象とする問合せは，関係代数演算として選択 (selec-tion)，射影 (projection)，自然結合 (natural join)，和 (union)
を許す SPJU 問合せと，平均 (average)，総数 (sum)，最大(max)，最小 (minimum)，カウント (count) の五つの集約関数から成り立つ任意の問合せとする．ただし，選択条件に集約関数は含まないものとする．またある関係 R,S において，条件式
を c としてこの条件式を満たす組の集合を関係として返す演算
を選択と言い，関係 R についてこの演算を行う場合，σc R と（ 2 ） 属性と値のどちらかの間に等号または不等号のみが入る条件式のことである．最小の条件式に ¬(NOT) が付いている場合はその条件式の余事象の条件式に置き換える．例えば，条件式

c = (A = B) ∧ ¬(C = D) は，¬(C = D) を (C = D) の余事
象 (C =| D) に置き換えると，最小の条件式 (A = B),(C =| D)
を二項演算子 ∧ で繋いだ条件式と捉えることができる．
関係 R を属性 A 上に射影する演算を πA R と表す．関係 R, S の和演算を R∪S と表す．関係 R, S の自然結合演算を R ▷◁ S と表す．関係 R の属性 A について，平均，総数，最大，最小を取る演
算をそれぞれ，avrA R, sumA R, maxA R, minA R と表す．関係

R の属性 A について，カウントを取る演算を，DISTINCT を指定しない場合は countA R，指定する場合は count distinctA Rと表す．

4. 直接来歴注釈，間接来歴注釈の定義と計算
本研究では，問合せ結果のデータの起源を辿り，元となっているセルに価値を与えたい．そのため Green ら [3] の，可換半環による多項式で結果を表現する “How-Provenance” の考え
をセル単位で適用する．組単位ではなくセル単位で考える理由
としては，組ごとでは最終結果に残っておらず，演算にも使用されていないデータにまで価値を与える可能性があるからである．また，セル単位で考えると組単位で考えるよりもより詳細にデータに価値を与えることができる．例えば，図 4 のように組にタグ t1 , t2 が与えられた関係 R の属性 A の上に射影演算を行った結果は図 5 のようになるが，組ごとに価値を与えると，

t1 , t2 が結果に残っていない属性 B の値 2,3 も含んでいるため，これらの値にも価値を与えることになる．
ここで，問合せによって得られたそのセルが元のどのセルから得られたものなのかを考えるために，問合せによって演算が行われる前のデータのセルにそれぞれデータの起源を示す直接来歴注釈を与える．さらに，問合せによって得られたそのセルは，どのセルの貢献によって得られたものなのかも考えるため，間接来歴注釈も与える．間接来歴注釈を考える理由としては，起源そのものを考えるだけでは，そのデータを得るために貢献したデータには価値を与えることができない可能性があるからである．例えば，図 2 の結果の関係を属性 B の上に射影する演算を行なった場合，図 6 のような結果が得られるが，この二つのセルの値 2,3 が存在するのは図 2 で関係 R1 の属性 A における二つの値 1 と，関係 R2 の属性 A における値 1 が同じ値を取っ—2—

ており，自然結合することができたからである．そのため問合name

せ結果には残っていないが関係 R1 の属性 A における二つの値

BayTours

1 と，関係 R2 の属性 A における値 1 にも報酬を与えるべきである．

based inphone

San Francisco 415-1200(s11 , l11 )(s12 , l12 )(s13 , l13 )HarborCruz

Santa Cruz831-3000(s21 , l21 )(s22 , l22 )(s23 , l23 )図 7 Agencies

つまり，演算において注目しているセルが存在しているのはどのデータの貢献によるのかを知るために間接来歴注釈を考えて
name

いる．

destination

type

BayTours San Francisco cable car

Green ら [3] の “How-Provenance” は，“provenance semiring”′ )(s′11 , l11′ )(s′12 , l12と呼ばれる，可換半環 (K, 0, 1, +, ·) による多項式で表すと定BayTours

Santa Cruz

bus

′ )
(s′21 , l21′ )(s′22 , l22′ )(s′23 , l23

BayTours

Santa Cruz

boat

′ )
(s′31 , l31′ )(s′32 , l32′ )(s′33 , l33

BayTours

Montereyboat′ )(s′41 , l41′ )(s′42 , l42′ )(s′43 , l43

義している．そのため “How-Provenance” をセル単位に拡張した直接来歴注釈に関しては，直接来歴注釈のみの集合 Ks とし，
可換半環 (Ks , 0, 1, +, ·) による多項式と定義する．また，間接
来歴注釈に関しても，間接来歴注釈のみの集合 Kl とし，可換′ )(s′13 , l13

図 8 ExternalT ours

半環 (Kl , 0, 1, +, ·) による多項式と定義する．[3] では関係代数
name

演算を可換半環の演算に写像するモデルを “K -relation” として定義し，関係における組を可換半環の要素 K へ写像する関数を R としていた．本研究では，このモデルに関してもセル単n位に拡張し，“K -relation” とする．

K n -relation： 関係における列数を n とする．関係におけるセルごとの直接来歴注釈の要素の集合を Ks とする．関係における写像モデル Ksn -relation とは，任意の組に対する関数

Rsn のことである．ここで関数 Rsn とは，関係における組の，n個のセルそれぞれを Ks の 0 以外の要素へ写像するもので，ここでのセルは特殊な要素 0 への関係をもたないものである．
次に，間接来歴注釈の集合を Kl とし，関係における写像モデ
ル Kln -relation についても同様に定義する．
写像モデル Ksn -relation および，Kln -relation をまとめて，写像モデル K n -relation とする．

K n -relation を持つ K を定義し，可換半環 (K, 0, 1, +, ·) による多項式で表した直接来歴注釈および，間接来歴注釈を問合せ
前の関係の各セルに追加し，問合せによる演算の結果得られたデータの各セルの直接来歴注釈，間接来歴注釈はどのようにな

destination

BayTours

type

San Francisco cable car′′(s′′
11 , l11 )′′(s′′
12 , l12 )HarborCruz

Santa Cruz′′(s′′
13 , l13 )

bus

′′
(s′′
21 , l21 )′′(s′′
22 , l22 )′′(s′′
23 , l23 )図 9 OriExternalT ours

意の問合せについては，定義した注釈演算を再帰的に利用すれば良い．

4. 1. 1 選

択

関係 R に対してある選択条件 c による選択を行った結果の関係 σc R の中のあるセル (ta , A) の直接来歴注釈，間接来歴注釈を考える．ここで，ta , A は関係 R のある組，および属性を表す．
ここで，選択条件 c は最小の条件式集合と ∧ (AND), ∨ (OR),¬(NOT) の 3 つの記号で構成されているものとする．最小の条件式に ¬ が付いている場合は 3. の ¬ に対する操作をあらかじ
め行っておく．
演算の結果の関係のセルが元の関係のセル (t, A) から得られたものとする．この時，セル (ta , A) の直接来歴注釈 source(ta , A)
および間接来歴注釈 lineage(t, A) を以下のように定義する．

るかを考える．Buneman ら [1] もデータを木構造として捉え，

source(ta , A) = source(t, A)

独自の問合せ言語を用いて広い範囲で起源を考える方法を示しているが，本研究では関係代数演算を前提とする．選択，射影，lineage(ta , A) = lineage(t, A) · lsub

和，自然結合および平均と総数，最大と最小，カウントから成ここで，lsub は選択条件 c によって決定される，間接来歴注釈

り立つ問合せ演算を行った場合に，結果の関係の各セルの直接の多項式である．

来歴注釈，間接来歴注釈成分の計算方法を以下で定義する．

選択条件 c が，その全体を二分する記号によって，c = C1 ∧ C2

セ ル (t, A) の 直 接 来 歴 注 釈 ，間 接 来 歴 注 釈 を そ れ ぞ れまたは c = C1 ∨ C2 で構成されている場合，lsub は C1 及び C2

source(t, A)， lineage(t, A) で表すものとする．

の間接来歴注釈成分をそれぞれ lC1 , lC2 とすると，以下のよう

また，具体例として図 7,8,9 のデータベースを用いることとすに計算される．

る． 図 7,8,9 の各セルの成分は第一成分が直接来歴注釈，第二（ 1 ） c = C1 ∧ C2 の場合成分が間接来歴注釈を表す．例では予め上記の直接来歴注釈，
間接来歴注釈を持っているものとする．

4. 1 演算ごとの注釈演算の定義
選択，射影，和，自然結合および，平均と総数，最大と最小，

lsub = lC1 · lC2（ 2 ） c = C1 ∨ C2 の場合

lsub = lC1 + lC2

カウントの，それぞれの演算について注釈演算を定義する．任—3—

条件式 C1 , C2 の間接来歴注釈成分 lC1 , lC2 に対して上記の操とすると、作を，条件式が最小の条件式になるまで再帰的に利用する．そ直接来歴注釈：の後，各最小の条件式についての間接来歴注釈成分は以下で求める．ある最小の条件式を csub とし，csub を満たす属性集合

source(ta , AJ ) = source(tR , AJ ) · source(tS , AJ )を B とすると，それぞれの間接来歴注釈成分 lc は以下である．

lc =

∏

source(ta , AR ) = source(tR , AR )source(ta , AS ) = source(tS , AS )lineage(t, b)b∈B

間接来歴注釈：以上の手順によって得られた lsub を代入することで求めたい間
接来歴注釈が得られる．なお ¬(NOT) に関しては，ド・モルガ

lineage(ta , AJ )ンの法則によって最小の条件式の否定にできるため，上記の手

=

∏

AJ

(lineage(tR , AJ ) · lineage(tS , AJ ))順で計算可能である．

4. 1. 2 射影

lineage(ta , AR )関係 R を属性集合 X 上に射影した結果の関係 πX R の中の= lineage(tR , AR )あるセル (ta , A) の直接来歴注釈，間接来歴注釈を考える．こ

·

∏

AJ

れらは，それぞれ，元の関係 R の組で X 上に射影すると ta に(lineage(tR , AJ ) · lineage(tS , AJ ))なるものを t とすると t の直接来歴注釈，間接来歴注釈の和とlineage(ta , AS )する．すなわち，∑

source(ta , A) == lineage(tR , AS )source(t, A)·t∈R,πX t=ta∑

lineage(ta , A) =lineage(t, A)t∈R,πX t=ta∏

AJ(lineage(tR , AJ ) · lineage(tS , AJ ))4. 1. 5 平均，総数
平均と総数の二つの演算については，結果として得られたその値を出すのに関わった全ての値が，その値を出すために必要

4. 1. 3 和関係 R, S の和演算による結果の関係 R ∪ S の中のあるセル(ta , A) の直接来歴注釈，間接来歴注釈を考える．結果の関係の組 ta が，それぞれもとの関係 R と関係 S に存在する同一の組

tR , tS に対応する場合，ta のすべての属性 A に対し，
source(ta , A) = source(tR , A) + source(tS , A)lineage(ta , A) = lineage(tR , A) + lineage(tS , A)だったと考える．そのため直接来歴注釈については結果として得られたその値を出すのに関わった全ての値の直接来歴注釈の積で表される．間接来歴注釈についても，同様に結果として得られたその値を出すのに関わった全ての値の間接来歴注釈の積で表される．
関係 R の属性集合 X について平均，または総数をとった場合の結果の関係 avrX R，sumX R の中のセル (ta , X) の直接来歴注釈および間接来歴注釈を以下のように定義する．

結果の関係の組 ta がもとの関係 R の組 tR のみに対応する場

source(ta , X) =合，ta のすべての属性 A に対し，∏

source(t, X)t∈R

source(ta , A) = source(tR , A)lineage(ta , X) =合，ta のすべての属性 A に対し，

source(ta , A) = source(tS , A)lineage(t, X)t∈R

lineage(ta , A) = lineage(tR , A)
結果の関係の組 ta がもとの関係 S の組 tS のみに対応する場∏

4. 1. 6 最大，最小最大と最小の二つの演算については，結果として得られたその値の元となった全セルの直接来歴注釈および間接来歴注釈の和が，それぞれ結果の値の直接来歴注釈および間接来歴注釈として表される．その値が最大または最小となるためには，比べlineage(ta , A) = lineage(tS , A)

た他の値がその値よりも小さかった，または大きかった必要が

4. 1. 4 自 然 結 合ある，という考えもあるが，仮に最大，最小以外の値が存在し関係 R, S の自然結合による結果の関係 R ▷◁ S の中のあるセなかったとしても最大，最小の値は変化しないため，それらのル (ta , A) の直接来歴注釈，間接来歴注釈を考える．結果の関値の間接来歴注釈は無視することとする．

係の組 ta が元の関係 R と関係 S の組 tR , tS の自然結合に対応

関係 R の属性集合 X について最大，または最小をとった場合

する場合，ta の属性のうちの結果の関係 maxX R，minX R の中のセル (ta , X) の直接来（ 1 ） AJ ∈ att(R) ∩ att(S)

歴注釈および間接来歴注釈を以下のように定義する．

（ 2 ） AR ∈ att(R) − att(AJ )maxX R：（ 3 ） AS ∈ att(S) − att(AJ )

—4—

∑

source(ta , X) =source(t, X)

t∈R,(t,X)=M AX(X)∑

lineage(ta , X) =lineage(t, X)

t∈R,(t,X)=M AX(X)minX R：

図 11 図 10 の問合せによる結果∑

source(ta , X) =source(t, X)

destinationt∈R,(t,X)=M IN (X)San Francisco 415-1200∑

lineage(ta , X) =phone

lineage(t, X)

t∈R,(t,X)=M IN (X)

4. 1. 7 カ ウ ン ト

Santa Cruz831-3000

Santa Cruz415-1200

Monterey

415-1200

図 12 q(D)

カウントについては，レコードの数を数えるので，指定した属性集合の全セルの直接来歴注釈および間接来歴注釈の積を，
結果のセルの直接来歴注釈および間接来歴注釈として表す．重
複する行はカウントに含まない DISTINCT を指定する場合もdestination

phone

Santa Cruz831-3000

図 13 q(D⊥c )1

あるが，注釈付き演算においてはその場合，予め重複している
行の直接来歴注釈および間接来歴注釈の和をとっておき，その注釈と他の行の注釈との積を結果のセルの直接来歴注釈および間接来歴注釈として表す．そのため DISTINCT を指定しない
場合と指定する場合に分けて定義する．

D⊥c ，問合せ結果を q(D⊥c ) とすると，contribution(q(D), c)は以下の式で定義する．

contribution(q(D), c) = dif f erence(q(D), q(D⊥c ))DISTINCT を指定しない場合：関係 R の属性集合 X についてカ

こ こ で dif f erence(q(D), q(D⊥c )) は ，問 合 せ 結 果 q(D) とウントをとった場合の結果の関係 countX R の中のセル (ta , X)q(D⊥c ) との差である．

の直接来歴注釈および間接来歴注釈を以下のように定義する．

また，注目しているセルが存在しない場合の問合せ結果 q(D⊥c )source(ta , X) =∏を，問合せ前のセル c の直接来歴注釈および間接来歴注釈 (s, l)source(t, X)t∈R

lineage(ta , X) =∏を (0, 0) とした場合の問合せ結果としているが，これは [2] にあるように，組単位の provenance が 0 であるとは，その組がlineage(t, X)

t∈R

存在しないことであると定義されていることから，[2] の “How-

Provenance” をセル単位に拡張した本研究の直接来歴注釈およDISTINCT を指定する場合：DISTINCT を指定する場合，予び間接来歴注釈が 0 であるとは，そのセルが存在しないことでめ重複する行の注釈についてはそれぞれ和をとっておき，そのあると定義できるからである．

後行ごとの注釈の積を結果のセルの注釈とする．これは予め射

5. 1 例

影演算を行い，その結果について積を取る演算と同じである．

文献 [2] の第 3 章 “How-Provenance” で使用されている例でしたがって，集約関数 countd istinctX R を以下のように変換

は，図 7,8 に対して以下の問合せを実行している．

し，注釈演算を行う．

count distinctX R = countX (πX R)

5. 差分に基づくセルの価値付け
データベースのあるセルが価値を持つかどうかを考える手法
を定義する．考え方として，注目しているセルがある場合の問合せ結果と，注目しているセルが存在していない場合の問合せ
結果との差を取り，その差を注目しているセルの価値とする方
法がある．

図 10

[2] 第 3 章 “How-Provenance” p418 の例

あるデータベース D のあるセルの値を c とする．このデータベースに対してある問合せ q を行なった際，その問合せ結果を q(D)

この問合せを行った結果は図 11 のようになる．この例におと表し，q(D) におけるセル c の価値を contribution(q(D), c)

ける問合せを q として，dif f erence を考える．

と表す．また，セル c の直接来歴注釈および間接来歴注釈を

図 7 の (1,1) 成分 “BayTours” に注目し，これをセル c1 とする．

(s, l) とした時，この (s, l) を (0, 0) で置き換えたデータベースを

このとき，q(D) は，図 12 になり，q(D⊥c1 ) は図 13 になる．

—5—

destinationphone

6. 注釈付き問合せ演算における差分等価性

San Francisco 415-1200
Santa Cruz831-3000

5. では，データの価値を差分を用いて定義した．ここで，注Santa Cruz415-1200

釈付き問合せ演算においては，はじめに注目しているデータのMonterey

415-1200

注釈を 0 に置き換えて演算を行なった場合の問合せ結果と，問図 14 q(D⊥c )合せを行なった後，注目しているデータの注釈を 0 にした場合

2の問い合わせ結果とが，等価になる．
destination

phone

San Francisco

415-1200′ ) · (l′′(s12 + s′12 , l11 · (l11 + l11
12 + l12 )) (s13 , l11 · l13 · (l11 + l11 ))

注釈付き問合せ演算における差分等価性： あるデータベース

Santa Cruz831-3000(s22 , l21 · l22 )(s23 , l21 · l23 )D のあるセルを c とし，その直接来歴および間接来歴注釈をSanta Cruz415-1200(s, l) とする．このデータベースに対して，集約関数を含まな′ + l′ ) · (l′ + l′ )) (s , l′′(s′22 + s′32 , l11 · (l2213 11 · l13 · (l21 + l31 ))
32
21
31

Monterey

415-1200′ · l′ )(s′42 , l11 · l4142′ )(s13 , l11 · l13 · l41

図 15 q(D)(来歴注釈付き)
destination

phone

San Francisco

415-1200(s12 + s′12 , 0)(s13 , 0)Santa Cruz831-3000(s22 , l21 · l22 )(s23 , l21 · l23 )Santa Cruz415-1200(s′22 + s′32 , 0)(s13 , 0)Monterey

415-1200(s′42 , 0)(s13 , 0)

図 16 q(D)(c1 の注釈を 0 にした場合)
destination

phone

Santa Cruz831-3000(s22 , l21 · l22 ) (s23 , l21 · l23 )図 17 q(D)⊥c

いある問合せ q を行なった際，その問合せ結果 q(D) とし，セル c の (s, l) を (0, 0) で置き換えたデータベースを D⊥c ，問合せ結果を q(D⊥c ) とする．また，問合せ結果 q(D) において s, lに 0 を代入した結果を q(D)⊥c とする．このとき，

q(D⊥c ) = q(D)⊥cが成り立つ．
（略証）.

左辺について，演算の流れを考えると以下のようになる．
（ 1 ） セル c の注釈成分 (s, l) に 0 を代入する．
（ 2 ） 問合せ q による注釈付き問合せ演算（この時点で注釈による消去は行わない）を行う．
（ 3 ） 仮の問合せ結果 q(D⊥c ) に対して，注釈による消去を

1

二つの図を見ると，セル c1 の有無でかなり結果が違っていることがわかる．この差が dif f erence になる．
次に，図 8 の (1,3) 成分 “cable car” に注目し，これをセル c2とする．このとき，q(D⊥c2 ) は図 14 になる．図 12 と図 14 を見ると，セル c2 の有無で結果は同じになっている．この場合

dif f erence は 0 であると考えることができる．
ここで，q(D) を，来歴注釈付きで演算した結果について考えると，図 15 のようになり，この結果において，セル c1 の注釈(s11 , l11 ) を (0, 0) にすると，図 16 になる．そもそも，間接来行う．
（ 4 ） 消去後の q(D⊥c ) が左辺となる．
手順（２）の時点では，注釈成分が (0, 0) のセルをヌル値 ⊥ にしたり，組全ての間接来歴注釈が 0 の組を見つけて消去する操作は行わず，この操作は手順（３）で行う．さらに，注釈はそれぞれ可換半環 (Ks , 0, 1, +, ·) または (Kl , 0, 1, +, ·) による多項式であると定義している．これは演算の過程でセル内の注釈がなくなることがないことを保証する．従って，左辺の演算方
法はは右辺において問合せ演算 q を行なった後に，注釈 s, l に0 を代入する方法と同じであり，

歴注釈は注釈のついているセルが存在するために必要な要素であるので，間接来歴注釈が 0 であるということは，そのセルは存在できないということになる．そのため間接来歴注釈成分が0 のセルはデータが存在しないということになり，組全ての間
接来歴注釈成分が 0 である組は消去できる．従って，図 16 は
図 17 のように書き換えることができ，図 13 と同じであることがわかる． これを q(D)⊥c1 とおくと，q(D⊥c ) = q(D)⊥cが成り立つ．

7. データ提供者と報酬分配[10] では，直接来歴注釈および，間接来歴注釈を以下のように定義した．

q(D⊥c1 ) = q(D)⊥c1

直接来歴注釈・間接来歴注釈： 問合せによって得られたそのとなる．任意のセルについてこの式が成り立つことが証明でき

セルが元のどのセルから得られたものなのかを考えるために，

れば，図 18 のように，一つ一つのセルについてそれを ⊥ に置

問合せによって演算が行われる前のデータのセルにそれぞれき換えて問合せ演算を行い dif f erence を考える，という手順

データの起源を示す直接来歴注釈を与える．さらに，問合せにを，注目しているセルの注釈成分を (0,0) にして，問合せ結果

よって得られたそのセルは，どのセルの貢献によって得られたに代入するだけにでき，効率化を測ることが可能となる．

ものなのかも考えるため，間接来歴注釈も与える．

—6—

s → 0, l → 0

q(D)

D

A

A
q

a

(s, l)

a…

(s′, l′)q(D)⊥aAdifference(q(D), q(D)⊥a)

…

⊥

…

c.nameattributes

difference(q(D), q(D⊥a))s → 0, l → 0q(D⊥a)

D⊥a

A

A
q

a

(0,0)

⊥

…

…

図 18 q(D⊥a ) と q(D)⊥apaperid

papertitle

year

p352

”OASSIS...”2014(s11 , l11 )(s12 , l12 )(s13 , l13 )

p352

1

Tova M.

[papertitle]

p353“Monitoring...”

2007

p352

2

Susan D.

[papertitle](s21 , l21 )(s22 , l22 )(s23 , l23 )

p352

3

Slava N.

[papertitle]1

Tova M.

[papertitle]

paperid a.order

図 19 P apers P

p353

図 20 Creators C

実際，元となったセルにはそのデータの提供者が存在する．デー
タの提供者とは，そのデータを記録したデータ記録者および，

r.nameattributes

場合によってはそのデータ自体を生み出したデータ作成者のこ

paperid r.orderp352

1Michael S.

[*]とだと考えられる．[10] では注釈自体に報酬を分配するところ

p353

1

Michael S. [paperid, papertitle]

までで話を終えていたが，その先を考える．

p353

2

Alex M.

[year]

図 21 Registrars R

改めて，データ提供者を以下のように定義する．
データ提供者： データの提供者とは，そのデータを記録した

成するという方法をとる．データ提供者データベースは例え

データ記録者および，場合によってはそのデータ自体を生み出ば図 20, 21 のような例が考えられる． ここで，attributes は，したデータ作成者のことである．

Creators の場合，c.name に該当する人物が作成したデータの属性の配列が入り，Registrars の場合，r.name に該当する人物

注釈に与えられた報酬は，次にデータ提供者に分配される．例

が記録したデータの属性の配列が入る．例えば，図 21 におい

えば図 19 において “OASSIS...” と入力した人物が Michael S.

て一列目の Michael S. の attributes は [∗] となっている．これだった場合，データ提供者は，そのデータを記録したデータ記

は，Michael S. が paperid “p352” の全ての属性のデータを記録者である Michael S. および，論文 “OASSIS...” そのものを録したということを意味する．また，二列目は，Michael S. が生み出したデータ作成者 Tova M., Susan D., Slava N. があげ

paperid “p353” の属性のうち，paperid と papertitle の属性のられる．したがって，“OASSIS...” の直接来歴注釈 s12 に与えデータを記録したということを意味する．

られた報酬の分配先はこの場合 Michael S. と Tova M., Susan

例えば直接来歴注釈 s12 の分配先として，記録者および作成者

D., Slava N. である．

の双方に分配をするのであれば，また，“p352” については，p352 そのものを生み出した人はいないので，この場合はデータ提供者はデータ記録者 Michael S.
のみである．
次に，両者に報酬を分配する方法は様々なものが考えられる．
決め方の一つとしては，直接来歴注釈の分配先を，問合せで表現しておくと言う方法が考えられる．予めデータ提供者のデータベースを用意しておき，分配手法によって問合せを作

s12 → δc.name→provider (πc.name ((σpid=p352 P ) ▷◁ (σ”papertitle” in attributes C))∪
δr.name→provider (πr.name ((σpid=p352 P ) ▷◁ (σ”papertitle” in attributes R))—7—

provider

9. 終 わ り にTova M.
Susan D.

本研究では，[10] に引き続き，データの起源および貢献度にSlava N.

基づいてデータベースに対する問合せ結果に与えられた利益をMichael S.

分配する方法について議論を進めた．[10] で定義した直接来歴

図 22 providers P ro1

注釈および間接来歴注釈を改めて 4. で定義し，5. では新たにセルの価値を決定する尺度として，注目しているセルが存在しproviderTova M.
Susan D.
Slava N.
図 23 providers P ro2ている場合の問合せ結果と，注目しているセルが存在していない場合の問合せ結果との差分を用いることを提案した．6. では差分の計算において等価であるものを証明し，差分計算の効率化が可能であることを示した．また，7. では，データ提供者を改めて定義し，注釈に分配された報酬を，さらにデータ提供者のように表現できる．図 22 のような結果が得られる．
また，作成者のみに分配をするのであれば，

s12 → δc.name→provider (πc.name ((σpid=p352 P ) ▷◁ (σ”papertitle” in attributes C))のように表現できる．図 23 のような結果が得られる．問合せとして考えられるのは例えば以上のような例である．
この問合せはさらに以下のように一般化することができる．
問合せ一般化： あるキー key を持つテーブル T において，(キー) = ID，(属性) = A であるセルの直接来歴注釈 s に与えられた報酬の分配先を考える．属性 “key”, “c.order”,“c.name”, “attributes” を持つテーブル C と，属性 “key”,“r.order”, “r.name”, “attributes” を持つテーブル R をあらかじめ用意しておく．
直接来歴注釈 s に与えられた報酬の分配先は以下のような問合せで表現することができる．

s → δc.name→provider (πc.name ((σkey=ID T ) ▷◁ (σA in attributes C))∪
δr.name→provider (πr.name ((σkey=ID T ) ▷◁ (σA in attributes R))

8. 考

察

本研究の 5. で提案した差分に基づくセルの価値付けにおいて，差分が具体的にどのようなものかは定義していないため，
より具体的に考える必要がある．
また，6. で証明した定理は，集約関数を含まない問合せのみをに分配する方法の一つを述べた．最後に 8. で今後の課題を述
べた．

10. 謝

辞

本研究は JSPS 科研費基盤研究 (S) No. 17H06099, (A) No.

18H04093 の助成を受けたものです．
文

献[1] Peter Buneman, Sanjeev Khanna, and Tan Wang-Chiew.
Why and where: A characterization of data provenance. In
International conference on database theory, pp. 316–330.
Springer, 2001.
[2] James Cheney, Laura Chiticariu, and Wang-Chiew Tan.
Provenance in Databases: Why, How, and Where. Found.
Trends databases, Vol. 1, No. 4, pp. 379–474, April 2009.
[3] Todd J Green, Grigoris Karvounarakis, and Val Tannen.
Provenance semirings. In Proceedings of the twenty-sixth
ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pp. 31–40. ACM, 2007.
[4] Todd J. Green and Val Tannen. The Semiring Framework for Database Provenance. In Proceedings of the 36th
ACM SIGMOD-SIGACT-SIGAI Symposium on Principles
of Database Systems, PODS ’17, pp. 93–99, New York, NY,
USA, 2017. ACM.
[5] Grigoris Karvounarakis, Zachary G Ives, and Val Tannen.
Querying data provenance. In Proceedings of the 2010
ACM SIGMOD International Conference on Managementof data, pp. 951–962. ACM, 2010.
[6] Chao Li, Daniel Yang Li, Gerome Miklau, and Dan Suciu.
A Theory of Pricing Private Data. Commun. ACM, Vol. 60,
No. 12, pp. 79–86, November 2017.
[7] OECD. Exploring the Economics of Personal Data. OECD
Digital Economy Papers, Organisation for Economic Cooperation and Development, Paris, April 2013.
[8] Aaron Roth. Technical Perspective: Pricing Information(and Its Implications). Commun. ACM, Vol. 60, No. 12,
pp. 78–78, November 2017.
[9] 内閣官房 IT 総合戦略室. AI、IoT 時代におけるデータ活用ワー
キンググループ中間とりまとめの概要, 3 月 2017 年.
[10] 鍋谷優斗, 吉川正俊. データベース問合せ結果販売利益の分配に関する研究. 第 10 回データ工学と情報マネジメントに関するフォーラム （DEIM2018）, pp. G1–6, 2018.

考えている．将来的に集約関数を含む任意の問い合わせについて定理が成り立つことを証明していく．
そして実データに対する問合せの例を使用して，実際に提案した手法を用いて報酬の分配をする実験をする必要もある．

—8—