E1-3

セル単位のデータ来歴—データ引用に向けて
朴 柱英†

吉川 正俊 ††

加藤 弘之 †††† †† 京都大学 情報学研究科 社会情報学専攻 〒 606-8501 京都市左京区吉田本町††† 国立情報学研究所 コンテンツ科学研究系 〒 101-8430 東京都千代田区一ツ橋 2-1-2 学術総合センタービル内
E-mail: †pjy953@db.soc.i.kyoto-u.ac.jp, ††yoshikawa@i.kyoto-u.ac.jp, †††kato@nii.ac.jp
あらまし 最近，データの公開，共有，再利用の重要性が高くなっている．データの公開，共有，再利用を通じて我々
は研究過程の透明性を高めることと同時に，複数のデータの統合やデータの再解釈による新しい研究結果を得ることもできる．データの公開，共有，再利用が重要になることによって，データ引用の重要性も高くなっている．データ引
用は自分が使ったデータを正しく引用するために必要なものである．データ引用は，従来の論文引用とは引用方法が異なる．従来の論文引用では一つの論文が引用の単位であったのに対して，データ引用では，様々な部分データが引用の単位となっている．また，引用をすることによってデータを提供した人に対して正しく貢献を与えなければならないが，その方法はまだ提案されていない．本研究では，データ引用に問合せを用い，データ作成者への貢献にデー
タ来歴 (Data Provenance) を使うことを提案する．そのために，関係データベースのタプル単位のデータ来歴をセル
単位のデータ来歴に変換し，セル単位のデータ来歴を用いて貢献評価まで拡張する．また，セル単位のデータ来歴には表れない作成者にも貢献を与えるために，潜在関係 (Latent Relation) を定義し，潜在データ来歴を計算する．そして，求められた潜在データ来歴からセル単位データ来歴の計算，貢献評価ができることも示す．本研究の結果，引用から正しい貢献を計算できるようになり，データ作成者は正しい貢献を受けると同時に，高品質のデータを提供する
動機付けを与えると期待する．
キーワード

1. 序

データ引用，セル単位のデータ来歴

論文の被引用に該当するものがまだ存在しない．その原因はデー
タの粒度 (granularity) にある．このデータの粒度が原因になる

最近，データの公開，共有，再利用の重要性が高くなっている．

理由は論文引用とデータ引用の引用対象が違うからである．論

データの公開，共有，再利用を通じて我々は研究過程の透明性

文引用の引用対象は論文自体である．すなわち，論文の一部をを高めることと同時に，複数のデータの統合やデータの再解釈使っても，すべてを使っても，引用対象は論文自体になる．しによる新しい研究結果を得ることもできる．2016 年度に開かれかし，データ引用の引用対象はすべてのデータではなく，実際た G7 の科学部長官会議の声明書 (G7 Science and Technologyに使ったデータである．従って，データの一部を使ったか，すMeeting) ではデータ，結果の共有に関するオープ

べてを使ったによって，引用対象が変わる．例えば，図 1 は京ンサイエンス (Open Science) の話題もあった [1]．また，ホワ

都と大阪の 11 月と 12 月の気温と降水量に関する情報であり，

イトハウス科学技術政策局でも研究開発支出が年間 1 億ドル

インタネット上で公開されて誰でも使えるとする．その時，(1)以上の政府機関に対しては，その研究成果と研究成果に使われある人は京都のデータのみを使い，(2) ある人は京都の気温のたデータを公開させようとしている [9]．また，RDA(Research

データのみを使い，(3) ある人は京都と大阪の降水量のデータ

Ministers

Data Alliance) のような研究データの共有，再利用の研究を行のみを使った場合，(1)，(2)，(3) のデータ使用者が同じ引用方

うための研究団体も登場した (https://rd-alliance.org/)．

法を使ってしまうとデータ作成者に対して正しく貢献を与える

このようなデータの公開，共有，再利用が行われる時，論文ことができなくなるはずだ．なぜかというと，気温と降水量のの場合と同様に，研究者が自らが利用したデータを正しく引用

データの作成者が異なる可能性があるからである．すなわち，することが重要である．従って，したデータを正しく引用する

作成者 A が気温のデータを計り，作成者 B が降水量のデータ方法が活発に研究されており，代表的な研究として [3]，[8] 等がある．自分が使ったデータを正しく引用することにより得られ

都市名

日付

平均気温 (°C)

ることの一つとしてデータを提供したデータ作成者に対して正

降水量の

タプル

月合計値 (mm)タグ

しく貢献を与えられることがある．貢献を与えるために利用で京都 (c11 )2016.11(c12 ) 12.5(c13 )82.0(c14 )t1

きる引用の例として論文の引用がある．論文引用では自分の論

京都 (c21 )2016.12(c22 ) 8.2(c23 )92.0(c24 )t2

文で参考にした論文を引用し，それぞれの論文は “被引用” と大阪 (c31 )2016.12(c32 ) 9.4(c33 )104.0(c34 )t3

いう形で評価される．従って，高い被引用を持つ論文はその分野で重要な論文として認められる．しかし，データの場合は論図 1: 都市ごとの気温，降水量 (S)を計った場合は，(2) は A のみに貢献を与え，(3) は B のみに

t1 が結果になっている．それに比べて，セル単位データ来歴で貢献を与えるべきである．

は使ったセルである c11 ，c13 のみを正しい結果として出す．

本研究ではこのように公開されている任意のデータベース
から問合せにより求められたデータだけを使う場合，自分が使ったデータの作成者に正しく貢献を与えることを目標にしている．貢献を正しく与えるための方法として本研究ではデータ来歴を使う．データ来歴は結果がどのようなデータから起因してきたかに関する情報である．従って，問合せにより求められたデータを使う場合は，そのデータのデータ来歴を計算することで，自分の使ったデータを提供した作成者を正しく探すことができる．その結果，データ来歴を計算することで結果を出すために使われたソースデータのデータ作成者が分かるよ
うになる．また，データ来歴の情報の詳しさによってデータ来歴は幾つかの種類が存在する．それぞれ Why Provenance [4]，How Provenance [7]，Where Provenance [4] 等である．また，
このすべてを一つの代数構造として統合したものが，Buneman
ら [7] の来歴半環 (Provenance Semirings) である．来歴半環は数学の半環構造を使ってデータ来歴を表したものである．
例えば，ある人が図 1 のようなデータベースに対して

Q “SELECT 都市名, 平均気温 FROM S WHERE 都
市名=‘京都”’
により求められたデータを使った場合，貢献を受ける対象は京都の 11 月，12 月の気温データの作成者である．しかし，従来のデータ来歴ではタプル単位のデータ来歴であったから，気温と降水量のデータを作った人がそれぞれ異なる場合は，正しく貢献を与えることができなかった．従って，正しく貢献を与えるための方法として本研究では，従来のデータ来歴を細分化したセル単位のデータ来歴を提案する．ここでのセルはタプルより小さい単位で，タプルと属性で決まるものである．
タプル単位とセル単位のデータ来歴の違いを例１で説明する．

Q で得られる結果レコード毎のデータ来歴は図 2 に表れている通りである．Q は都市名でデータをフィルタリングし，図 1 の都市名と平均気温のみを出力する．すなわち，元の図 1 のデー
タの中で降水量に関する情報はどこでも使われていない．それにもかかわらず，従来のデータ来歴のリニエッジ (Lineage) による結果は降水量の情報を含むタプル t1 で結果レコードのデー
タ来歴を表現している (他の種類のデータ来歴も同様)．それに比べて本研究で提案するセル単位データ来歴はタプルのどの属性が関与しているをピンポイントで表す．その結果，気温デー
タの作成者のみに正しく貢献を与えることができる．

以降，３節では問合せを用いたデータ引用において，使われたデータに関するより詳細なセル単位の情報を得るために，
データ来歴をセル単位で定義する．これは，既存のタプル単位のデータ来歴の定義 [7] をセル単位に拡張したものとなっている．４節では，３節で定義したセル単位のデータ来歴だけでは表現できない貢献度を計算するために，各関係演算子のファク
タを考慮した潜在関係を定義する．これにより，直接結果に出現するデータだけでなく，結果を得るために用いられたデータをセル単位で特定可能となり，よりきめ細かい貢献度の計算が可能となる．

2. 関 連 研 究
本研究の目標はデータの作成者に正しく貢献を与えることであるが，本研究は二つの研究分野，“引用分野”と “データ来歴”の融合である．引用に関する従来の研究は主に引用文の生成，引用文からデータを特定，引用文の参照などであり，データ作
成者への貢献評価はまだできていない．本研究では貢献評価のためにデータ来歴を使っている．その理由は，データ来歴の本
来の目標と貢献評価の目標が一致するところがあるからである．
データ来歴の目標は自分が使ったデータの来歴を探すことであり，貢献評価での目標は自分が使ったデータの作成者を探すことである．従って，データ来歴の方法を貢献評価のために拡張できる．本研究で仮定している引用方法は，問合せによる引用である．問合せによる引用方法はデータベースからある問合せで求められたデータを使い，その情報を引用することを意味する．これに関しては，[3] で定義している引用方法をそのまま使うことにする．[3] ではデータ引用を問合せとデータベースから一意に決まるものとして定義している．すなわち，データベースに対して問合せが計算されたことが分かっているならその計算結果によるデータ引用文の自動生成ができる．また，その自動生成の具体的な方法まで提案されている．
また，本研究で貢献評価のために使っている方法論である“データ来歴” は最近活発に研究されている分野である．データの来歴はデータの起源とデータの生涯中 (Life Span) の歴史を記述するためのものである．伝統的にデータベースのデータはどんな疑問もなく真 (True) と信じられてきた．しかし，最近，オンラインてデータが収集されたり，いろいろなソースからデータが収集されたりするので，データベースのデータをその例 1. 従来のデータ来歴 (例 : リニエッジ [6]) とセル単位デー

まま信じることはリスクが高い．従って，自分が使ったデータ

タ来歴の比較

がどこから起因してきたのかが分かることは最近のデータベー

t1 は c11 ，c12 ，c13 ，c14 を全部含む．従って，従来のデータ来歴スを扱う上で大事なことである．これを解決するために来歴にをによると Q では c12 ，c14 を使っていないのにその情報を含む関する研究がいろいろなところで行なわれている．来歴の研究成果のサーベイ [5] によると来歴研究は大きく三つの分野に

都市名

平均気温 (°C)

リニエッジ セル単位データ来歴分かれる．各々Why，How，Where Provenance である．Why

京都

12.5

{t1 }

c11 · c13

Provenance は “結果がなぜ出たのか？” [4]，How Provenance

京都

8.2

{t2 }

c21 · c23

は “結果がどうして出たのか？” [7]，Where Provenance は “結図 2: 図の関係に対する Q の結果

果がどこから出たのか？” [4] を表現するためのものである．その中で本研究では [7] の来歴半環 (provenance semirings) をセル単位に変換したものをデータ来歴として使う．

3. セル単位データ来歴

ただし，これ以降曖昧性が生じない場合は，TAG((t,A)) を

TAG(t,A) のように表記する．関数 TAG は U -Cell の各々の要
素を C の要素に写像する．本研究では C の値をタグとも呼ぶ．
すなわち，(t,A) で表現されるある c は TAG により C の要素

c この節では従来のデータ来歴を貢献評価で使えない理由と，である値を持つことになる．U -Cell と同様に U -Tup の各々のその問題点を克服するためにデータ来歴をより細分化したセル要素も C に写像する．また，U -Tup の有限部分集合である関単位データ来歴を定義し，セル単位データ来歴による貢献評価

係上の関係代数演算に対応して，U -Tup から写像された C のについて述べる．セル単位データ来歴を使って貢献評価するこ集合上の代数操作を定義する．

とで我々はより正解な貢献評価ができるようになる．
従来のデータ来歴はデータ来歴がタプルに付けられているタグの組み合わせによって表現された．しかし，最近のデータは定義 3. 属性の有限集合 U に対する C-relation は関数 R :U -Tup → C である．

複数の作成者が作ったデータを一つのタプルに統合して提供すC-relation では U -Tup の要素を C に写像している．しかし，る場合も多く，複数の観測装置から集まったデータを一つのタ本研究では U -Tup から得られる C の値は TAG(U -Cell) の要

プルとして統合して提供する場合も少なくない．この時，従来素から決まるものとする．正確には，U -Tup のある要素を t とのデータ来歴を使うと，タプル単位の演算になり，属性に関すした時，C-relation 上での R(t) は TAG(U -Cell) の要素の · 演

る情報がなくなってしまう．従って，本研究ではこの問題を解算でできるものである．また，その具体的な値は次のように定決するためにタプル単位のデータ来歴をより細分化したセル単義される．

位のデータ来歴を使う．セル単位のデータ来歴でのセルは直観的に関係データベースがタプルの行と属性の列により構成されていると見なした時，一つの行の一つの列に該当するものである (例 : 図 1 の c11 等)．セルを定義するためにまずタプルを定

定義 4. タプルのタグあるタプル t(∈ U -Tup) の C-relation 上での R(t) の値は次のように定義される．

義する．本研究ではタプルの定義として関係モデルの named

R(t) =∏A∈U

TAG(t,A)

perspective [2] を使う．named perspective は属性の有限集合
U と値のドメイン D を用いてタプルを写像 t : U → D で表現

定義４により得られる結果は，タプルのタグとも呼び，そのする．また，ある時刻で D を固定し，その時可能なすべてのタ

タプルのタグ上での代数演算を行う．タプルのタグ上での代数

プルの集合を U -Tup と表現する．U に対する関係は U -Tup の演算のために本研究では C-relation に対して関係代数演算を定部分集合である．

義する．すなわち，タプルのタグ上での代数演算は C-relation
に対する関係代数演算で計算される．また，C-relation 上での定義 1. U -Cell とセル関係代数演算は [7] の来歴半環をベースにしている．従って，属性の有限集合 U が与えられたとき，U-Cell を次のように定C-relation での関係代数演算は K-relation [7] での関係代数演義する．

算のように，選択，射影，集合和，結合を表すために “足し算”

U -Cell = {(t,A) | t ∈ U -Tup , A ∈ U }と呼ばれる 2 項演算 “+” と “掛け算” と呼ばれる 2 項演算 “·”を使う．このように，C-relation の演算は基本的に K-relation

セルは U -Cell の一つの要素であり，c で表現する．
本研究では同じ値を持つセルでも違うものとして区別して使っている．従って，各々のセルにはタグが付けられていると仮定する．そのために，U -Cell に含まれているすべてのセルと同じ計算方法を使うが，射影だけは違う．属性情報を表すた
めに，C-relation の射影は射影に使われなかった属性のセルのタグを１に変換する．C-relation に対する関係代数演算の定義は以下のようである．

にタグを付ける必要がある．元のデータベースから求められる

定義 5. (C,+,·,0,1) を二つの演算と二つの区別される原子を

U -Cell にタグ付ける関数を本研究では TAG とする．

持つ代数構造だとすると，集合差を除いた関係代数演算は次の定義 2. C は区別される要素 0 を持つ集合である．U -Cell を

C に写像する関数 TAG は次のように定義される．
TAG : U -Cell → C
また，U -Cell のすべての要素に TAG を計算し，その結果の集合を TAG(U -Cell) と表現し，次のように定義される．

TAG(U -Cell) = {TAG((t,A)) | (t,A) ∈ U -Cell}
また，集合 C に対して，単位元 0 を持つ+演算と，単位元 1 を持つ · 演算が定義されていることにする．

ように定義される
空関係 (empry relation) 任意の属性集合 U に対して，∅(t)= 0 を満足する ∅ : U -Tup → C がある．
集合和 (union) もし，R1 , R2 : U -Tup → C であると，R1 ∪R2: U -Tup → C は次のように定義される．
(R1 ∪ R2 )(t) = R1 (t) + R2 (t)射影 (projection) もし，R : U -Tup → C であり，V ⊂=Uであると，πV R : V -Tup → C は次のように定義される．

(πV R)(t) =∑′V の上で t=t′ ∧R(t′ )=0| (PROJ(R(t ))PROJ(R(t’)) は C から C ′ への写像で，セルのタグを変換す

都市名

日付

平均気温 (°C)

るための関数である．C ′ は以下のようになる．

C ′ = {TAG(c) | c ∈ C}
TAG(c), att(c) ∈ V.
TAG(c) =1,
それ以外の場合.
この C ′ を用いて，PROJ は次のように表現される．PROJ :C → C ′.
ただし，V の上で t=t’ は V により制限され属性 V 上でのタプ
ル t になる属性 U 上でのタプル t’ を意味する．
選択 (selection) もし，R : U -Tup → C であり，選択述語 Pが各々の U -tuple を 0 か 1 に写像すると，σP R : U -Tup → C
は次のように定義される．

(σP R)(t) = R(t) · P(t)
1,
P(t) =
0,t ∈ σP R.

降水量の

セル単位

月合計値 (mm)

データ来歴

京都

2016.11 12.5

82.0

c11 · c12 · c13 · c14

京都2016.12 8.2

92.0

c21 · c22 · c23 · c24

大阪

2016.12 9.4

104.0

c31 · c32 · c33 · c34

3. 選択を計算する．
元のテーブルから選択演算を計算する．σ都市名=‘京都′ (S) の結果，‘京都’ の値を持つものは残るが，大阪のデータはなくなる．定義５に従うと選択演算は，(σP R)(t) = R(t) · P(t) なので，Qによるセル単位データ来歴は次のようになる．しかし，セル単位データ来歴が 0 であることはレコードが存在しないことを意味するので，選択された結果残るのは１行目と２行目の ‘京都’のデータのみである．Q’ も同様に計算すると，Q’ の場合は１
行目が c11 · c12 · c13 · c14 · 0 になる．他は Q と同じデータ来歴を持つ．

その以外の場合.

自然結合 (natural join) もし， Ri : Ui -Tup → C, i = 1,2であると，U1 ∪ U2 に対する R1 ⋉⋊ R2 は次のように定義される．

(R1 ⋉⋊ R2 )(t) = R1 (t1 )·R2 (t2 )

都市名

日付

平均

降水量の

セル単位

京都

2016.11 12.5

気温 (°C)

月合計値 (mm)

データ来歴

82.0

京都

c11 · c12 · c13 · c14 · 1

2016.12 8.2

92.0

大阪

c21 · c22 · c23 · c24 · 1

2016.12 9.4

104.0

c31 · c32 · c33 · c34 · 0

t1 は U1 の上で t1 = t 同様に t2 は U2 の上で t2 = t
セル単位データ来歴の値は可換半環 (commutative semir-ings) である．定義４により得られるタプルのタグは · 演算の上で可換，結合である．また，集合和，自然結合，選択の場合

4. 射影を計算する．
選択された結果から射影演算を計算する．射影演算は (πV R)(t)∑′= V の上で t=t′ ∧R(t′ )=0| (PROJ(R(t )) であり，PROJ から日は [7] の定義と同様なのでそれらの演算による結果は可換半環

付，降水量の属性のセルのタグを 1 に変更した関係代数式が得に従う．定義５の射影による結果も可換半環になる．なぜかとられる．従って，セル単位データ来歴は日付，降水量のタグをいうと，可換半環である入力タグの一部を · 演算の単位元であ１に変更したものになる．Q’ も同様に計算すると，Q’ の場合

る 1 に変更しても可換半環であり，それらの足し算も可換半環

は 2 行だけが結果になる．

であるからである．従って，定義 5 により求められるセル単位
データ来歴は可換半環構造である．その結果，我々はタグに具体的な代入することで，信頼度計算等ができるようになる [7]．

都市名

平均気温 (°C)

セル単位データ来歴

京都

12.5

c11 · 1 · c13 · 1

京都

8.2

c21 · 1 · c23 · 1

例 2 では定義５に従って，図１のデータと問合せからセル単位データ来歴がどう求められるかを示す．例 2 の結果から我々は “問合せ Q と Q’ により求められたデータを使った場合は，

c11 ，c13 ，c21 ，c23 の作成者に貢献を与えるべきである” という5. 集合和を計算する．
集合和は同じ値を持つものを+演算で結合して表現する．

ことが分かる．また，セル c11 ，c13 がセル c21 ，c23 より多く使

都市名

平均気温 (°C)

セル単位データ来歴

われているので，c11 ，c13 の作成者は c21 ，c23 の作成者より多

京都

12.5

c11 · c13 +c11 · c13 ( = 2 c11 · c13 )い貢献を受けると思われる．

京都

8.2

c21 · c23

例 2. Q，Q’ と図 1 から結果のレコードに対するセル単位デー

本研究ではセル単位データ来歴をタプルのタグとも呼ぶ．そタ来歴を計算する過程の理由は，関係代数演算の計算で得られる結果タプルのタグがQ’ : SELECT 都市名, 平均気温 FROM S WHERE 都市

セル単位データ来歴で表現されるからである．

名=‘京都’ AND 降水量 > 90

1. 問合せを関係代数で表す．
Q UNION Q’ = π都市名，平均気温 (σ都市名=‘京都′ (S)) ∪4. データ作成者への貢献評価
この節ではセル単位データ来歴だけには表現できない貢献を

π都市名，平均気温 (σ都市名=‘京都′ ∧降水量>90 (S))

与えるための方法を扱う．セル単位データ来歴は基本的に結果

2. タプル毎のタグの来歴であるので，結果には現れないが演算などで使われた

定義 4 に従って，タプルのタグを U -Cell のタグを用いて計算データを取れない．しかし，結果には現れていなくても，演算する．

などで使われたデータの作成者は貢献を受けるべきであると考える．従って，本研究では隠れている作成者にも貢献を与える

データベースで重要なものは観測値のみであり，他の属性は観ために潜在関係を定義し，潜在関係の関係代数演算から計算さ測値を説明するためなものである．すなわち，観測値を説明す

れる潜在データ来歴からの貢献評価方法を提案する．

るためのものはその属性の値が重複していたり，観測値から自データ作成者が貢献を受けるためには，次のような過程が要求される．まず，データ使用者は公開されているデータを使い然に与えられたりする場合が多い．従って，観測値データベー
スでは観測値の作成者のみに貢献を与える．

論文等を書く．その次，論文等が評価されて，論文の中で使わ本研究での貢献評価の対象は大きく二つに分類できる．一つ

れたデータの作成者にも論文の評価に従って貢献が与えられる．

は結果に現れているものへの貢献評価と，もう一つは結果に現データ使用者がどのデータを使ったかは分かるために，データれていないものへの貢献評価である．前者の場合はセル単位

使用者は自分の使ったデータを正しく引用すべきである．本研

データ来歴を用いて計算し，後者の場合は潜在データ来歴を用

究では引用方法として [3] の引用方法と同じものを使う．デー

いて計算する．

タベースと問合せにより求められた結果を自分が使ったデータ

4. 1 セル単位データ来歴による貢献評価

として見なし，引用の対象だと仮定する．例えば，ある人が問

セル単位データ来歴による貢献評価は基本的には結果に現れ合せにより求められた結果データを使うと，結果に含まれていているものだけである．しかし，セル単位データ来歴を計算するデータの生成に影響を与えているソースデータの作成者に貢るために使われた問合せを一部変更した問合せを用い，隠れて献を与える．しかし，セル単位データ来歴だけには正しく貢献いる作成者まで貢献を与えることもできる．セル単位データ来を与えることができない．なぜかというと，結果には現れてい歴を用いた貢献評価は次のようである．

ないが問合せの計算には使われる情報もあるからである．例えば，例 2 では c11 ，c13 ，c21 ，c23 の作成者に貢献を与えている．
しかし，実際は c31 の作成者にも貢献を与えなければならない．
なぜなら，c31 の作成者が都市名が ‘大阪’ だと正しく値を提供したからである．すなわち，c31 の作成者には ‘NOT 京都’ という値を提供したことに対して貢献を与える．
従って，本研究ではセル単位データ来歴をベースにして，貢定義 6. セル単位データ来歴からの貢献評価
問合せ Q，関係 R : U -Tup → C があり，Q(R) のレコードの集合を T ，属性集合を att(Q(R)) とする．

U -Cell(={(t,A) | t ∈ T , A ∈ att(Q(R))}) の要素 c に貢献しているセルを CNTRB(c) とし，CNTRB(c) は次のように計算される．

献評価，また観測データベースの貢献評価までの方法を提案す

CNTRB(c) = σc[t] (πc[a] (Q(R)))

る．その方法としてセル単位データ来歴と貢献評価を含む潜在データ来歴を定義する．潜在はセル毎に付けられる変数で，潜在に値を代入することでセル単位データ来歴になったり，貢献評価になったりする．

ただし，σc[t] は c のタプルを選択し，πc[a] は c の属性で射影する．
定義６はセル単位データ来歴に選択と射影をすることで，結図 3 では，セル単位データ来歴，貢献評価，観測データベー

果に含まれているセル毎の貢献評価を行っている．このように

スの貢献評価で必要なセルをベンダイアグラムで表現している．

セル毎に貢献評価することで我々はセル毎に違う貢献評価がでセル単位データ来歴によると貢献を受ける作成者は c11 ，c13 ，c21

きるようになる．例３は，セル単位データ来歴を用いた貢献評，c23 の作成者である．しかし，c31 が ‘NOT 京都’ という情報価を計算する過程である．

を提供しているので，貢献評価ではセル単位データ来歴に c31を加えてその作成者に貢献を与える．また，観測データベースの貢献評価ではキーの情報 (都市名と日付がキー) を除いた c13

例 3. セル単位データ来歴からの貢献評価
都市名

平均気温 (°C)，c23 の作成者に貢献を与える．観測データベースでキーの情報

京都 (c11 · 1 · 1 · 1)

12.5(1 · 1 · c13 · 1) c11 · 1 · c13 · 1

セル単位データ来歴を除く理由は，観測データベースが持つ特徴に起因する．観測京都 (c21 · 1 · 1 · 1)

8.2(1 · 1 · c23 · 1)

c21 · 1 · c23 · 1

セル単位データ来歴に，選択と射影演算をすることでセル毎の貢献評価ができる．平均気温 12.5 のセルを c だとすると，

CNTRB(c) = σ(京都，12.5) (π平均気温 (Q(S))) である．ただし，Q= π都市名，平均気温 (σ都市名=‘京都′ (S))
セル単位データ来歴を使って貢献評価を行うことで，我々はセル毎に貢献している作成者を求められる．その結果，属性毎に違う貢献を与えることができるようになる．例えば，‘都市名’ より ‘平均気温’ の方に貢献を与えるときは，c13 ，c23 の作成
者が c11 ，c21 の作成者より高い貢献を受けることになる．
図 3: セル単位データ来歴，貢献評価，観測データベースの貢献評価

また，セル単位データ来歴を求める過程で使った問合せから射影演算を変更した新しい問合せを作る．その問合せからできるセル単位データ来歴の貢献評価は隠れている情報の一部を取集合である C を用いてタプルを関数 tc : U → C で表現する．

ることができるものである．新しい問合せを作る方法は，元のその時，可能なすべてのタプルの集合を UC -Tup と表現する．

問合せに含まれている射影演算をより大きい属性による射影演

潜在関係は元のドメインからできるタプルをタグによるタプル

算に書き換えることである．また，射影演算を書き換えてできに写像したものであり，次のように定義される．

た問合せを QbigP で表し，次のように定義する．
定義 7. 元の問合せ Q があり，Q のすべての選択で一回でも使われた属性の集合を S，すべての自然結合で一回でも使われた
属性の集合を J，すべての射影で一回でも使われた属性の集合
を V だとし，att(Q) = S ∪ J ∪ V にする．

QbigP は元の問合せ Q にあるすべての射影演算をそれぞれ
πV (R) → πatt(R)∩att(Q) (R) に書き換えた問合せである．
例 4 は問合せ Q′ と Q′ bigP によるセル単位データ来歴であり，それぞれの違いを表している．

定義 8. 潜在関係は関数 RL : U -Tup → UC -Tup である．ただし，tc ∈ UC -Tup に対して，RL (t) = tc である．
我々は潜在関係上でタグを計算する関係代数演算の定義ができるようになる．例 5 は図 1 のセルのタグ付けと潜在関係を表している．潜在関係の各々のセルの値がタグであることを確認できる．
例 5. セルのタグ付けと潜在関係

1. 定義 2 によるセルのタグ付け
各々のセル毎に cij が付けられているとする．ただし，cij はセルを区別するためのタグでもある．

例 4. Q’ と Q’bigP からの貢献評価

Q’ = π都市名，平均気温 (σ都市名=‘京都′ ∧降水量>90 (S))

都市名

日付

平均気温 (°C)

京都 (c11 )2016.11(c12 ) 12.5(c13 )82.0(c14 )京都 (c21 )2016.12(c22 ) 8.2(c23 )92.0(c24 )大阪 (c31 )2016.12(c32 ) 9.4(c33 )104.0(c34 )Q’bigP = π都市名，平均気温，降水量 (σ都市名=‘京都′ ∧降水量>90 (S))
都市名

平均気温 (°C)

セル単位データ来歴

京都 (c21 )8.2(c23 )c21 · c23

降水量の月合計値 (mm)

図 4: Q’ のセル単位データ来歴

都市名

平均気温 (°C)

降水量のセル単位データ来歴

月合計値 (mm)京都 (c21 )8.2(c23 )92.0(c24 )c21 · c23 · c24

図 5: Q’bigP のセル単位データ来歴ある問合せ Q を QbigP に書き換えることで，結合や，選択で使われたか結果には現れていない情報の一部を取ることができる．しかし，それだけでは図 3 の c31 のような情報を取ることはできない．従って，次の節ではすべての隠れている情報を

2. 潜在関係
潜在関係は元の関係の値をすべてタグに入れ替えたものである
ので，同じ値を持つもの (例 : c11 と c21 ) も違うものとして扱
われる．
都市名

日付

平均気温 (°C)

降水量の月合計値 (mm)

c11

c12

c13

c14

c21

c22

c23

c24

c31

c32

c33

c34

取るために潜在関係を定義し，潜在データ来歴を求める．

4. 2 潜在関係と関係代数演算

潜在関係は関係代数演算により変化していく．そのために，潜在関係はタプルを構成するすべての値を U -Cell のタグで一般的な関係代数演算とは多少違う演算方法を使う．潜在関係

表現したタプルでできる関係である．潜在関係の上で関係代数

での集合和は重複を許している．重複を許すことで同じ値を持演算を計算することで，潜在データ来歴を得ることができ，セつものも違うものとして扱うことができるようになり，セル毎

ル毎に違う貢献を与えることができるようになる．

の潜在が計算ができる．また，潜在関係での自然結合は直積で潜在データ来歴ではセル毎に潜在が付けられている．例えば，計算する．その結果潜在関係の上での自然結合でできる関係は

例３で ‘都市名’ と ‘平均気温’ が同じ貢献を受けるなら，それぞ

同じ名前の属性を持つことになり，それぞれを区別して扱える．

れのセルに付けられている潜在は一緒である．しかし，‘都市セルの貢献評価はセルのタグに付けられる潜在により行われ名’ より ‘平均気温’ の方が価値が高い（より貢献を受ける）なる．従って，本研究では潜在の値を先に計算し，最後にその潜ら，‘平均気温’ のセルが ‘都市名’ のセルより高い潜在を持つこ在の値をタグに付けることにする．そのためには，元の潜在関とになる．また，結果には含まれていないが選択，結合などで係のタプルを潜在とタグの対で表現する必要がある．

使われたものは，結果に現れているセルよりは小さく貢献して

定義 9. 潜在とタグの対によるタプル

いるので小さい貢献を持ち，どこでも使われなかったものはそれよりも小さい貢献を持つ．

潜在関係上でのあるタプル tc (=(c1 , . . . , cn )) は以下のようにも表現される．

潜在データ来歴を求めるための関係代数演算は従来の関係代数演算の計算方法とは違う．その違う関係代数演算が成立す

tc = ((L1 , . . . , Ln )◦·c (c1 , . . . , cn ))る関係が潜在関係である．まず，潜在関係を定義するために，

また，潜在とタグの対によるタプルを明示的に表す時は，タプUC -Tup を定義する．属性の有限集合 U とタグ集合 C の有限

ルを (L◦·c c) で表現し，Li をセル ci の潜在とも呼ぶ．

定義９のようにタプルを表現できる理由は，セルのタグが C

定義 10 に従うと，自然結合，射影，選択の場合は計算の段の要素であるからである．C の要素は半環構造に従うので，·階でそれぞれの L が与えられ，L 同士で計算される．また，演算が定義されている．また，例 5 の潜在関係はすべての潜在

この ·L に適切な演算子とそれぞれの L に値を代入することが 1 である特殊な場合である．

で，貢献評価ができるようになる．例６は潜在関係による関係

定義 10. 潜在関係での関係代数演算

代数演算である．

潜在関係での自然結合は直積と同じ役割をし，⋉⋊L で表す．

例 6. 潜在関係による関係代数演算

集合和 (union) 潜在関係上での集合和は重複を許す多重集合

Q” = πAC (σA=a (R) ⋉⋊L S)

での演算である．潜在関係上での関係 R と S があり，R ∪ S

Rは，次のように定義される関係である．

A B

B C

a

b

b

c

d

e

f

g

R∪S=R⊎S

S

ただし，⊎ は多重集合での足し算を意味する．例えば，{1} ⊎{1} = {1,1}

1. U -Cell のすべての要素に対して，TAG を適用することで自然結合 (natural join) 潜在関係上での関係 R と S があり，すべての要素のタグを求められる．その結果セル毎にタグが付

R⋉⋊L S は，次のように定義される関係である．

けられる．
R

R⋉
⋊L S = R × S
R × S = { L ◦·L (Lr1 , Lr2 , . . . , Lrn ,Ls1 , Ls2 , . . . , Lsm )◦·c(r1 , r2 , . . . , rn , s1 , s2 , . . . , sm )(=w) |((Lr1 , Lr2 , . . . , Lrn )◦·c (r1 , r2 , . . . , rn )(=r)) ∈ R ∧((Ls1 , Ls2 , . . . , Lsm )◦·c (s1 , s2 , . . . , sm )(=s)) ∈ S }
た だ し ，◦·L は 潜 在 同 士 の 演 算 ，L =(L1 , L2 , . . . , Ln+m )，ATT = att(R) ∪ att(S) である．
−1
LJP , t−1
⋉R−1(s) ∈ R−1
(R)⋊
⋉R−1
(S).

c (wi )∈ATT AND RL (r)⋊
L
L
L




LJP - , t−1 (wi )∈ATT/
AND R−1(r)⋊⋉R−1(s) ∈ R−1
(R)⋊
⋉R−1
(S).
c
L
L
L
L
Li =

−1
−1
−1
−1
LJN , t−1⋉RL (s) ∈/ RL (R)⋊⋉RL (S).
c (wi )∈ATT AND RL (r)⋊
LJN - , t−1 (wi )∈ATT/
AND R−1
(r)⋊
⋉R−1
(s) ∈
/ R−1
(R)⋊
⋉R−1
(S).
c
L
L
L
L

S

A(タグ) B(タグ)

B(タグ) C(タグ)a(r11 )b(r12 )b(s11 )c(s12 )d(r21 )e(r22 )f(s21 )g(s22 )

2. 潜在関係に従う関係を作る．その結果セルそれぞれを違うタ
グで区別することができるようになる．
R

S

A

B

B

C

1 ·c r11

1 ·c r12

1 ·c s11

1 ·c s12

1 ·c r21

1 ·c r22

1 ·c s21

1 ·c s22

3. σA=a (R) を計算する．
R

また，t−1: C → U で，C に含まれるあるセルは属性が優一なcので，そのセルからの t−1
はいつも一意に決まる．
cAB

射影 (projection) 潜在関係上での関係 R があり，πV (R) は，

LSP ·c r11

LSP - ·c r12

LSN ·c r21

LSN - ·c r22

次のように定義される関係である．

πV (R) = {L ◦·L (Lr1 , Lr2 , . . . , Lrn )◦·c (r1 , r2 , . . . , rn ) |((Lr1 , Lr2 , . . . , Lrn )◦·c (r1 , r2 , . . . , rn )(=r)) ∈ R }ただし, L = (L1 , L2 , . . . , Ln ) である．
LP P , t−1
c (ri ) ∈ att(R).
Li =L , t−1 (r ) ∈PN
i / att(R).
c

4. σA=a (R) ⋉⋊L S を計算する．
A

B

B

C

LJP - ·L LSP ·c r11

LJP ·L LSP - ·c r12

LJP ·c s11

LJP - ·c s12

LJN - ·L LSP ·c r11

LJN ·L LSP - ·c r12

LJN ·c s21

LJN - ·c s22

LJN - ·L LSN ·c r21

LJN ·L LSN - ·c r22

LJN ·c s11

LJN - ·c s12

LJN - ·L LSN ·c r21

LJN ·L LSN - ·c r22

LJN ·c s21

LJN - ·c s22

選択 (selection) 潜在関係上での関係 R があり，σP (R) は，次のように定義される関係である．

σP (R) = {L ◦·L (Lr1 , Lr2 , . . . , Lrn )◦·c (r1 , r2 , . . . , rn )(=r) |((Lr1 , Lr2 , . . . , Lrn )◦·c (r1 , r2 , . . . , rn )(=r)) ∈ R }ただし，L = (L1 , L2 , . . . , Ln ) であり，選択条件 P で使われた属性の集合を
att(P) とする．

LSP , t−1c (ri ) ∈ att(P) AND P(r) = TRUE.
LSP - , t−1/ att(P) AND P(r) = TRUE.
c (ri ) ∈
Li =

−1

LSN , tc (ri ) ∈ att(P) AND P(r) = FALSE.





LSN - , t−1/ att(P) AND P(r) = FALSE.
c (ri ) ∈5. πAC (σA=a (R) ⋉⋊L S) を計算する．
A

B

B

C

LP P ·L LJP - ·L

LP N ·L LJP ·L

LP N ·L

LP P ·L

LSP ·c r11

LSP - ·c r12

LJP ·c s11

LJP - ·c s12

LP P ·L LJN - ·L

LP N ·L LJN ·L

LP N ·L

LP P ·L

LSP ·c r11

LSP - ·c r12

LJN ·c s21

LJN - ·c s22

LP P ·L LJN - ·L

LP N ·L LJN ·L

LP N ·L

LP P ·L

LSN ·c r21

LSN - ·c r22

LJN ·c s11

LJN - ·c s12

LP P ·L LJN - ·L

LP N ·L LJN ·L

LP N ·L

LP P ·L

LSN ·c r21

LSN - ·c r22

LJN ·c s21

LJN - ·c s22

潜在関係上での関係代数演算の結果，セル毎にあるタグに

A

B

B

C

潜在が付けられる． 例６の最終結果に対して，·L に掛け算を

3 · r112 · r122 · s112 · s12意味する ·，L∗P , L∗P - に１，L∗N , L∗N - に０を代入し，潜在

3 · r11

1 · r121 · s212 · s22が 1 であるものは残して，0 であるものを消すと，最終に残る

2 · r21

1 · r221 · s112 · s12のは r11 と s12 だけである．これは潜在関係ではない関係での

2 · r21

1 · r221 · s212 · s22πAC (σA=a (R) ⋉⋊ S) の結果と一致する．

図 6: 潜在による貢献評価

4. 3 潜在データ来歴
潜在データ来歴というのは例６の最終結果のようなものであに現れていなくても貢献している対象の貢献まで計算できる．

る．すなわち，潜在関係上での関係代数演算の結果を潜在デー

データ作成者の貢献を正しく評価することで，データ作成者のタ来歴と呼ぶ．例６の最終結果は Q” の潜在データ来歴である．

功績を認めることができる．

この潜在データ来歴の潜在をどう計算するかによって，潜在本研究では結果に現れているセルの貢献を計算するためにセ

データ来歴からセル毎の貢献評価になったり，貢献評価になっ

ル単位データ来歴を用いた．しかし，セル単位データ来歴は信たり，観測データベースの貢献評価になったりする．

頼度の計算にも使われる．信頼度は結果の信頼度とセルの信頼定理 1. 潜在データ来歴と潜在

1. セル毎の貢献評価
潜在データ来歴からセル毎の貢献評価までの計算は次のように行われる．

1) ·L に ·，L∗P , L∗P - に 1，L∗N , L∗N - に 0 を代入し，0 の値を持つものは消す．

2) 同じ属性名の要素をお互いに · で結合する．
3) R−1
L により同じ値を持つタプルをお互いに+で結合する．
2. 貢献評価
潜在データ来歴から貢献評価までの計算は次のように行われる．

1) ·L に+，それぞれの潜在に適当な値を代入する．ただし，潜度に分かれる．結果の信頼度はタプル単位のタグを持つセル単位データ来歴を用いて計算され，セルの信頼度はセル単位のタ
グを持つセル単位データ来歴による貢献評価を用いて計算される．この時，我々は潜在データ来歴だけで両方を計算できる．
そのためには，セル単位データ来歴による貢献評価からセル単位データ来歴を復元する必要がある．その理由は，潜在データ
来歴から計算できるのがセル単位データ来歴による貢献評価だ
けであるからだ．セル単位データ来歴による貢献評価からセル
単位データ来歴への復元ができるなら，潜在データ来歴だけで貢献度と（結果，セル) 信頼度を計算できる．その復元に必要な構造を探すことは今後の課題である．

在はパラメーターである．

2) 属性毎の重み (Lw ) をセルの L に掛ける．
3. 観測データベースの貢献評価
潜在データ来歴から観測データベースの貢献評価までの計算は次のように行われる．

1) ·L に+，それぞれの潜在に適当な値を代入する．ただし，潜在はパラメーターである．

2) キー属性のセルの L には (Lk =0) をキーではに属性のセルには (Lnk =1) を掛ける．

3) 属性毎の重み (Lw ) をセルの L に掛ける．
貢献評価で結果には現れないが貢献を受けなければならない対象は，選択と結合で使われたセルである．その時，潜在の値では LJP > LJN > LJP - ，LSP > LSN > LSP - ，

LP P > LP N が 成 り 立 つ ．こ の 潜 在 値 に 従って Q” の 潜
在 デ ー タ 来 歴 に LJP , LSP に 2 を ，LP P , LJN , LSN に 1を，LJP - , LSP - ,LP N に 0 を代入すると，図 6 のようになる．図 6 の結果をそれぞれのタグ毎に潜在を足し算すると，

6r11 ,4r21 ,4s12 ,4s22 ,3r12 ,3s11 ,2s21 ,2r22 になる．この潜在値の順序は，現実の貢献とは異なるが，潜在の値ををよく調整することで現実的な結果が得られると期待する．

5. 結

論

本研究ではデータ作成者への貢献を与えるための方法として
セル単位データ来歴と潜在データ来歴を提案した．潜在データ
来歴はセル単位データ来歴による貢献評価の一般化で，結果

文

献[1] Communique of the g7 science and technology ministers’
meeting in tsukuba, ibaraki (http://www8.cao.go.jp/cstp/english/others/20160517communique.pdf), May 2016.
[2] Serge Abiteboul, Richard Hull, and Victor Vianu, editors.
Foundations of Databases: The Logical Level. AddisonWesley Longman Publishing Co., Inc., Boston, MA, USA,
1st edition, 1995.
[3] Peter Buneman, Susan Davidson, and James Frew. Whydata citation is a computational problem. Commun. ACM,
59(9):50–57, August 2016.
[4] Peter Buneman, Sanjeev Khanna, and Wang Chiew Tan.
Why and where: A characterization of data provenance.
In Proceedings of the 8th International Conference on
Database Theory, ICDT ’01, pages 316–330, London, UK,
UK, 2001. Springer-Verlag.
[5] James Cheney, Laura Chiticariu, and Wang-Chiew Tan.
Provenance in databases: Why, how, and where. Found.
Trends databases, 1(4):379–474, April 2009.
[6] Yingwei Cui, Jennifer Widom, and Janet L. Wiener. Tracing the lineage of view data in a warehousing environment.
ACM Trans. Database Syst., 25(2):179–227, June 2000.
[7] 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, PODS ’07, pages 31–40, New
York, NY, USA, 2007. ACM.
[8] Data Citation Synthesis Group. Joint Declaration of Data
Citation Principles. Martone M. (ed.) San Diego CA:
FORCE11, 2014.
[9] John P. Holdren. Increasing Access to the Results of Federally Funded Scientific Research. Oﬃce of Science andTechnology Policy, February 2013.