DBSJ Journal, Vol.8, No.1
June 2009

一般論文

スト リーム処理エンジンにおける効率的な来歴管理するセンサデータはその目的を達成する為に使用される．センサ
データの特徴は，短周期で継続的に生成されることである．この特徴より，センサデータはストリーム処理されることが多い．そEﬃcient Lineage Management on Stream
Processing Engines

れに従い，本論文ではセンサデータにはストリーム処理が施されることを想定する．ストリーム処理の内容として STREAM[10]が規定する演算の一部を想定する．

♥

センサデータがスト リーム処理されて得られた出力について，

♦

川島 英之
北川 博之 ♠

寺島 裕貴

Hideyuki Kawashima
Hiroyuki Kitagawa

Yuki Terajima

その来歴 (Provenance) を知りたい欲求は自然に生まれる．例えばアプリケーションは受信した配信結果が異常であった場合，その結果が得られた原因について知りたくなることがある．原因の一つには，結果の源である入力データストリームがある．これは結果の来歴と呼ばれる．来歴が保存されていれば ，アプ リケー
ションは配信結果に疑念を持った場合に，その源を調べることができる．しかしながら，SPE は入力データスト リームを保存し本論文は，データスト リームにおける来歴管理技法を示す．スない．なぜなら処理コストが大きいからである．

ト リーム処理エンジンの出力を受け取ったアプリケーションからそこで本研究では，スト リーム処理エンジンにおいて，来歴の根拠を問い合せる要求に応えるため，スト リーム処理エンジン

データを永続化する基本方式を 2 つ述べる．第一の方式は，実に到着したタプルスト リームの内，その出力の全来歴を永続化す

行木への入力タプル全てを永続化する．第二の方式は，実行木

る．プロト タイプ SPE を作成して，ウィンド ウ演算と選択演算(Operator Tree) の根に到着したタプルの来歴タプルを永続化すから構成される実行木について，ウィンド ウ幅を変えて来歴タプる手法である．そして，標本乱択を用いる投機的永続化方式を提ル永続化に関する処理時間を計測した．実験の結果，来歴タプル

案する．提案方式は窓演算子の出力を標本乱択し，それを実行木

永続化処理には多大な時間を要すること，およびその原因はディに投入し，各切断集合における来歴数を数え上げる．この来歴数

スクアクセス回数であることを示す．

が最小になる切断集合において，来歴永続化を実行することで高速化を実現する．

In this paper, we present a method to provide
persistence to provenance on stream processing environment. In order to meet the requirement ofapplications, we provide persistence to provinces ofthe output of SPE. We implemented our proposal
and evaluated it on experiments. The result of experiments showed that the provenance transferring
cost is dependent to the location of operator tree.
In case selectivity is 0 (empty result), the transferring should be conducted at the root of the operator
tree. In case selectivity is 1 (full result) and operator tree includes multi-way cartesian products, then
the transferring should be conducted at the leavesof the operator tree.

本論文の構成は次の通りである．2 節で関連研究について述べる．3 節で本研究のモデルを述べる．4 節でシステムの設計と実装について述べる．5 節で実験の評価について述べる．最後に 6
節では本研究をまとめ，今後の課題を述べる．

2.

関連研究

2.1

スト リーム処理エンジン

データスト リーム研究はおおまかに 3 世代に分けることができる．第一世代 SPE に関する研究では，関係データモデルを拡張して，ストリームを扱うためのデータモデルが提案された．そして同モデル上における性能向上とメモリ使用量の制御が研究された．このようなモデル化が行われた理由は，汎用的である関係
データモデルを拡張することで，データストリーム処理の汎用的なモデルを構築しようとしたからである [3, 1, 6]．第二世代 SPEに関する研究では，第一世代 SPE で提案されたデータモデルに

1.

対して，分散処理を導入することで，高性能化および耐故障化にはじめに関する研究が推進された．この研究動向は現在もまだ継続されて近年のセンサデバイス技術の進展に伴い，センサデータの生成いる [11]．そして第三世代 SPE に関する研究では，第一世代，

量ならびにその利用例は増加の一途を辿っている．センサデバイ

第二世代とは一線を画し ，明確なアプ リケーションを想定した，

スは実世界の状況を検知するために設置される為，それらが出力専門用途システムの構築が研究されている．用途例には，RFID，
ネットワークトラフィック，そして動物の監視など ，幅広いアプ♥

正会員 筑波大学大学院システム情報工学研究科・同大学計算科学研究センター kawasima@cs.tsukuba.ac.jp♦
学生会員 筑波大学大学院シ ステ ム情報工学研究科在学中♠

リケーションが含まれる [8, 5, 9]．
本論文では，第一世代の SPE である STREAM システムのモ
デル [2] を基礎とする．

yterajima@kde.cs.tsukuba.ac.jp
正会員 筑波大学大学院システム情報工学研究科・計算科学研究センター kitagawa@cs.tsukuba.ac.jp1

日本データベース学会論文誌 Vol.8, No.1

2009 年 6 月

DBSJ Journal, Vol.8, No.1
June 2009

一般論文
2.2

RESULT(Root)

来歴

データ来歴とはデータの由来を表す．データ来歴は 2 種類に大別される．デ ータがど こから来たかを表す起源来歴 (Where

Provenance) と，ど のような処理を経て来たかを表す処理来歴(Why Provenance) である．本研究では起源来歴のみを対象とする．本論文の残りでは，起源来歴を略して来歴と記す．
来歴に関する研究には，データウェアハウスでのビュー構築にσ

関する来歴を扱う研究 [7] や，確率的データベースにおける計算σσの安全性と効率的を満たすために来歴を用いる研究 [4, 13]，科学

BASE(Leaf)

ワークフローにおけるユーザ指向の問合せを来歴を利用することW

で実行ログから便利な問合せを提供したり，来歴によりデータ依WW

存関係の軌跡を取ることで回答の正確性を向上させる研究 [15]，データセットの管理に来歴を用いることでその検索、解析、計算

図1

方式概略

結果のアクセスを行えるようにする研究 [16]，センサデータのイ
ンデックス化とその探索に来歴を用いる研究 [17]，来歴をそのま

果タプルは出力されてはならないことである．なぜなら，永続化

ま保存すると保存する量が増えすぎてしまうので，来歴保存を効

前のタプルが人目に触れたとして，その来歴タプルを求められた率的に行う研究 [18] がある．文献 [18] は少ないコストで保存す

ときに，突発的事故等により来歴タプルが失われることで検索不る来歴のサイズを最大 20 倍減少させることに成功した．

能になる事態を防ぐ ためである．文献 [14] においても，そのよ

本研究の来歴モデルは ULDB[4, 13] における来歴データベー

うな方式は高速であるものの無意味であると触れられている．

ス (LDB) に基づく．LDB では，各タプルに識別子 (ID) 及び来3.2

歴関数 λ が与えられる．λ は入力をタプル ID とし ，出力を来歴

本論文では下記の前提を設定する．第一の前提とし て，入力であるタプルの多重集合とする．

2.3

ノード であるウィンド ウ演算の出力タプルが実行木を上って全て

高速データ永続化の終点ノードから出力されるまで，次のウィンド ウ演算は実行さDBMS におけるトランザクション処理の高性能化のため，高速データ永続化には多くの研究がされてきた．文献 [12] では 2

れないと定める．第二の前提として，実行木の終点ノード には必ず新規増分タプルストリーム出力演算子1が置かれると定める．

台のリモート メモリを永続的デバイスとみなすことで高速化を実第三の前提として，来歴タプル集合はウィンド ウ演算の入力タ現している．リモート メモリとはリモートホストのメモリのことであり，頻繁に到着するトランザクションを処理する場合には，
デ ィスク帯域よりも TCP を用いたネットワーク帯域の方が広い

3.3

SPE におけるデータスト リームの高速永続化技法としては文献 [14] がある．この研究では，実行木の根ノード の入力キュー内

は実行木の葉でタプルを永続化する方式である．二つ目の方式は実行木の根でタプルを永続化する方式である．これらを図 1 に示している．この研究は実行木の出力結果を永続化することを対象にしており，その来歴を永続化することは考えていない．また，
実験内容として単純な選択演算のみを対象にしている．

研究課題

永続化技法

来歴を永続化するための技法を二方式提案する．一つ目の方式のリレーションを一括書込処理により，高いスループットを実現

3.1

算子は行数ウィンド ウ (tuple based window) のみ有すると定め
果タプル集合を出力しないと定める．

高速化するが，ストリームデータに着目した技法ではなかった．

課題と提案

プル集合に含まれると定める．第四の前提として，ウィンド ウ演る．第五の前提として，来歴の永続化が終了する迄，実行木は結ことに着目した技法である．この技法はトランザクション処理を

3.

前提

す．いずれの方式にも長短があるため，実行木の形態および入力
タプルに応じて有利な方式は変わる．いずれにせよ，処理時間が長くなりすぎると，ストリームが頻繁に大量のタプルを流す場合に，要求性能を実現できず，SPE がその目的を果たせない場合が生じ うる．そして三つ目が，標本乱択を用いてコスト推定を行い，最小コストになる切断集合において永続化を実行する方式で通常の DBMS はデータ永続化処理をトランザクショナルに行ある．

う．つまり INSERT 命令毎に永続化処理を行う．一方 SPE の場

各方式について説明する前に，全方式に共通の部分を記してお合には，全ての入力タプルを永続化する必要はない．なぜなら，
結果として出ていったタプルだけが人間の目に触れる可能性があく．システムにデータが到着すると，同じタプルが二つ生成される．ひとつは実行木へ投入され，もうひとつは起源タプルとしてるからであり，結果として出ていかないタプルは，ユーザあるい保持される．起源タプルの永続化を実行木の処理のどの時点で行はアプリケーションにとっては存在しないと見なされ得るからでうかにより，二方式は分けられる．永続化処理の実行は実行木をある．そこで本研究では，結果として出ていくタプルの来歴タプ処理するスレッド と別のスレッド で実行される．即ちマルチコア

ルを全て永続化することを研究課題と設定する．このとき注意さ環境において，永続化実行中も問合せ処理は実行される．実行木

れなければならないことは，来歴タプルが永続化されるまで，結1

2

STREAM における ISTREAM 演算子
日本データベース学会論文誌 Vol.8, No.1

2009 年 6 月

DBSJ Journal, Vol.8, No.1
June 2009

一般論文
用スレッド は処理を終えても，永続化スレッド の処理が終わるまでは，結果を出力しない．ウィンド ウ結合を含め，あるタプルが実行木で使われているかど うかは，ウィンド ウ演算のセマンティ
クスにより判定される．各ノード のシノプシスが保存するタプル
長はユーザからの問合せにより自動的に決定するため，この管理は容易である．ウィンド ウ演算の入力タプルは，その結果タプルが実行木で使われているか，あるいは，それが永続化されるまでは破棄されない．

3.3.1

葉タプル永続化方式

図 2 葉タプル永続化方式

図 3 根タプル永続化方式

本方式は，起源タプルのコピーを即座に永続化する．同時に，起源タプルのオリジナルを実行木スレッドが処理する．この処理はマルチコア環境において並列に実行される．なお，出力に使用化を行うため，根で永続化を必ず待つ時間が発生することであされないタプルの起源タプルは，後で非同期的にデ ィスクから削る．特に，永続化するタプルの数が多い場合には，デ ィスク書込

除される．

時間および書込確認時間が長くなるため，待ち時間が延びる．

図 2 はこの方式の例を示している．スト リームからウィンド
ウ演算が入力を受けて，その後，選択演算と結合演算が実行される．ウィンド ウ演算の入力を起源タプルとし，すぐ さま永続化を行っている．

4.

設計と実装

4.1

設計

提案手法を評価するために，プ ロトタイプ SPE を作成し た．

本方式の利点は，実行木のコストが高い場合には，最速となる

この SPE は代数式を入力し ，その代数式から実行木 (Operator

ことである．なぜなら，永続化処理と実行木処理が並列に行われTree) を作成する．

るからである．実行木のコストが高い場合は，直積が複数ある場

実行木の入力はタプルストリームであり，これはウィンド ウ演合，あるいは選択演算・結合演算によるタプル数の減衰率が低い

算子によりリレーションに変換される．ウィンド ウ演算子は必ず場合である．

実行木の葉に置かれるため，実行木内にはスト リームは存在せ

本方式の欠点は，実行木からの出力が少ない場合には，大量のず，データは全てリレーションとして扱われる．オペレータの実

不要なタプルを永続化してし まうことである．このような場合，

行順序は，下から上である．同じ高さに存在する演算子について

それらの大量の不要なタプルを削除する必要がある．削除に際しは，それらの間に実行順序の優先度は存在しない．即ちどの順序てはシステムに負荷をかけない為に非同期的な実行方式が用いらで実行されても構わない．この規則に従ってオペレータ実行順序

れる．

3.3.2

を定める．実行順序は実行キューにより管理され，連続的問合せ

根タプル永続化方式が終了するまで順序が変わることはない．実行木の出力はタプル

本方式は，実行木が出力する全てのタプルの来歴タプル集合をストリームになる．

永続化する．すなわち，実行木へ投入されたタプルの内，根まで各ストリーム生成処理，実行木処理，そして永続化処理は全て残ったタプルの来歴である起源タプルのみが永続化のためにデ ィ

異なるスレッド により実現される．それゆえこれら複数のスレッ

スクへ書き込まれる．残りのタプルの内，ウィンド ウ結合で用い

ド は並行/並列処理される．

られる可能性があるタプル以外は破棄される．

4.2

実装

この方式は，処理が根に到達するまで永続化スレッド は永続化

実装は C 言語により行った．排他制御のために pthread ライ処理を行わない．処理が 根に到達すると，実行木スレッド は永ブラリの mutex を使用した．総行数は 3000 行程度である．タ

続化スレッド に対して，タプル群を渡す．永続化スレッド は受け

プル形式はスキーマにより決定されるため，データ領域は void

取ったタプル群の来歴タプルを起源タプル内から同定して，それ型とし，全属性のサイズの総和長の連続領域により実現した．同らをマーシャリングして永続化を実行する．

連続領域は属性サイズにより区切られる．

図 3 は本方式の挙動を示している．図 2 と同様に実行木の演

来歴はモデル的にはタプル ID の集合だが，本実装では各導出算は行われていくが，起源タプルの永続化は出力が決定した後にタプルから基底タプルへのポインタ配列により来歴を実装した．

行われる．

来歴の永続化処理に際してはマーシャリングを行い高速化を実本方式の利点は，実行木からの出力が一つもない場合には，永現した．すなわち，結果集合中の各タプルについて，ポインタ配

続化作業を行わなくてよい為に最速になることである，あるい

列中のポインタを辿り，来歴タプルを発見する．そしてその来歴

は，実行木において相当数のタプルが減らされる場合には，高いタプルの ID とデータを連続領域にコピーする．この作業を全て性能を示すことである．それに加えて，不要なタプルが永続化の来歴タプルについて実行し ，write および fsync システムコー

されることがないために，デ ィスクへの書き込み量には無駄がな

ルを一度だけ呼び出してデ ィスクに書込みを行った．デ ィスクアい．それゆえ葉タプル永続化方式のように，後で非同期的にデ ィ

クセスコストは高価であるため，このような方式を採用した．

スクアクセスをする必要がない．

結合演算の結果，複数の導出タプルが同一の起源タプルを来歴

本方式の欠点は，実行木の出力が決定してから来歴タプル永続

タプルとすることがある．この場合，同一タプルが二度以上は永3

日本データベース学会論文誌 Vol.8, No.1

2009 年 6 月

DBSJ Journal, Vol.8, No.1
June 2009

一般論文
600000表 1 実験条件

Without Persistentce

550000

条件値

10000

sleep 時間

なし

入力データ

全て同じ

500000[Throughput(tps]

条件内容
入力タプルストリーム数

450000400000350000300000250000表 2 実験環境

200000

1

10

100

1000

[# of tuples (window size)]

環境内容

条件値

CPU

Intel(R) Core(TM)2 Quad CPU
4
2.66 GHz
4GB

コア数
コア周波数

RAM 容量

図6

スループット5.2 実験結果
5.2.1 来歴永続化のコスト
図 4 に実験結果を示す．図 4 は横軸 (対数) にウィンド ウサイ

5000

4000

8000

3500

7000

3000

6000

2500
2000

が見て取れる．

4000
3000

1000

2000

500

• 来歴を行わない場合 (“Without Persistence”)，スループッ
トは 56 万タプル /秒である．
• 来歴永続化のコストは大きい．
• 行数ウィンド ウ幅が 1 の場合，“With Persistence” の性能

5000

1500

0

With Persistentce

9000[# of fsync][msec]

10000

With Persistence
Without Persistence

4500

ズ（ 行数ウィンド ウ ），縦軸に処理時間を表す．図より次のこと

1000

1

10

100
[# of tuples (window size)]

1000

0

1

10

100

1000

[# of tuples (window size)]は悪い．
来歴永続化については，行数ウィンド ウ幅と性能の間に密接な

図4

処理時間の比較

図 5 同期書込回数

関係があるように見える．この関係は，デ ィスクへの同期書込回
数によりもたらされる．
図 5 にウィンド ウサイズと同期書込回数の関係を示す．ディス
クへの書き込みはコストが高いため，この回数が多い程，性能続化処理をされてはならない．換言すれば ，永続化処理は冪等

は大きく下落する．特にウィンド ウサイズが 1 の場合，多くの(idempotent) である必要がある．そこで，永続化処理したタプ

タプルが到着していようとも，必ず一つずつしか処理されない

ルのメモリ番地を保存しておき，永続化処理前にそれを参照する

ために，デ ィスク書き込み回数が極めて多くなり，そのために性ことで冪等化を実現した．

能が極めて悪化する．ウィンド ウサイズが 1 である場合，処理

5.

評価

5.1

実験内容

実態は通常のトランザクションと類似する．即ち，通常のトランザクション処理を用いると，非常に性能が劣化することが推察される．

提案手法の葉タプル永続化方式と根タプル永続化方式の性能を本研究では対象外としたが，ログファイルのデータからデータ実験により測定した．来歴永続化を行わない場合の処理時間を測ベースのデータを再構築する処理が通常は必要になる．この処理

定し，根タプル永続化方式との比較を行った．また，葉タプル永は別スレッドにより実現され，他のデ ィスク領域へのアクセスを続化方式と根タプル永続化方式の比較を行った．

行うため，排他制御処理とランダムデ ィスクアクセスを引き起こ

実験条件を表 1 に示す．我々の実験環境においては fsync シス

し，更に性能を劣化させる可能性がある．

5.2.2

テムコールの処理時間が速い場合には僅か数百マイクロ秒と非常

プロト タイプ SPE の基本性能に高速だったため，永続化に伴うコストを明確するために，スト

上記のスキーマ，問合せに関するプロトタイプ SPE のスルー

リームを生成するスレッド を含め，全スレッド の sleep 時間を零

プットを測定し た．これを図 6 に示す．ウィンド ウ演算と選択に設定した．実際には全スレッド における sleep 関数をコメント

演算により構成される単純な実行木の場合には，プ ロトタイプ

SPE は最大で 56 万 TPS 程度の性能を達成している．一方，来アウトして実験を行った．

歴を永続化する場合，最悪の場合には 2000TPS まで性能が下落

選 択 演 算 に 関 し て 実 験 に 用 い た 問 合 せ はS[test1.v < 1000](W[test1,100]) と し ，ス ト リ ー ム

する．すなわち 280 倍程度の性能差がある．

のスキーマは test1 (id int) (v double) とした．S は選択5.2.3

演算を表し ，この場合 1000 以下の値のみを通過させる．W はウィンド ウ演算を表し，この場合タプル幅が 100 である．test1

2 つの提案手法である，葉方式と根方式を実験条件を変えて比較した．以降の図において，RESULT は根方式を表し ，BASE

は integer 型属性の id と double 型属性の v を有する．

は葉方式を表す．選択率の変動は，選択条件の指定により実現し4葉方式と根方式の比較

日本データベース学会論文誌 Vol.8, No.1

2009 年 6 月

DBSJ Journal, Vol.8, No.1
June 2009

一般論文
8000

RESULT
BASE

7000

7000

6000

6000

5000

5000
[msec][msec]

8000

4000

3000

2000

2000

1000

1000

1

10

知されないタプルは意味を持たない．意味を持たないタプルを形成するタプルもやはり意味を持たない．本論文ではそのように考

4000

3000

0

い．ユーザに提供されないタプルは，ユーザに感知されない．感

RESULT
BASE

0

100

えた．
来歴を永続化する技法として，根タプル永続化方式と葉タプル
永続化方式を提案し た．次に，頻繁に到着するデータスト リー
1

10[# of tuples (window size)][# of tuples (window size)]

100

ムを一括してデ ィスクに転送する方式を提案した．結果集合を成すタプルの全来歴タプルを連続領域にマーシャリングし，それを図 7 1 回の選択演算 (選択率=0)

図 8 1 回の選択演算 (選択率デ ィスクへ一括転送することで，処理時間の長いデ ィスクアクセ=1.0)

スを減らすことができた．
そして，プロトタイプ SPE を作成して，ウィンド ウ演算と選

9000

600

RESULT
BASE

択演算から構成される実行木について，ウィンド ウ幅を変えて来RESULT
BASE

8000
500

歴タプル永続化に関する処理時間を計測した．実験の結果，来歴

400

タプル永続化処理には多大な時間を要すること，およびその原因

300

はデ ィスクアクセス回数であることがわかった．

200

6.2

7000

[Processing Time(Sec)][msec]

6000
5000
4000
3000
2000

100

0

1

10

100

0

課題

今後の課題は二つある．まず，演算子の多様化を行う．次に，

1000

10

20

30

[# of tuples (window size)]

40

50
60
[# of tuples (window size)]

70

80

90

100

効率化を行う．本論文で述べた技法は，来歴タプルの永続化を実現するものの，基本的 な方式であり効率の悪いものであった．来

図 9 300 回の選択演算 (選択図 10

歴タプル永続化により，最悪で 280 倍程度の性能劣化が生じるこ

2 つの直積とを 5.2.2 節で述べた．また，永続化されるタプル集合を圧縮化

率=1.0)

後，一括してデ ィスクへ転送することでデ ィスク帯域の効率化を図る．
た．入力データストリームにはデータとして 100 の値を持たせ，選択率を 0%，10%, 100% にするために，選択条件をそれぞれ

v > 1000，v < 100，v < 1000 とした．
図 7,8 より，実行木中に選択演算が 1 つしか存在しない場合
は，選択率が 1.0 であろうとも根方式は葉方式を上回る性能を示

[文献]

した．
一方，図 9,10 に示すように，実行木のコストが高い場合には，
葉方式は根方式を上回る性能を示した．図 9 はウィンド ウ演算後に選択演算が 300 個設置された場合であり，図 10 は直積が二つあるような場合である．この場合には 3 つのウィンド ウ演算子があるため，ウィンド ウ演算子のタプル数が 10 であれば ，永続化すべきタプル数は 30 であるのに根では 10000 のタプルが生成されてしまい，永続化必要性確認処理の為に長い時間が必要とされる．
本研究では永続化処理をデ ィスクへの書き込みとした．デ ィス
クへの書き込みコストは高いため，基底法は特殊な条件でしか高い性能を示さなかった．しかし今後 MRAM を代表とする不揮発高速メモリが使用可能になった場合，両者の関係は変わると考え
られる．

6.

まとめと課題6.1

まとめ

謝辞本研究の一部は科学研究費補助金基盤研究 (#18200005,#20700078)，筑波大学 VBL 研究プロジェクトによる．

本研究の目的は，データストリームにおける効率的な来歴管理技法を示すことであった．
まず，データストリームの来歴となりうるデータは，実行木の出力タプルの来歴タプルであることを示した．ストリーム処理環[1] Daniel J. Abadi, Donald Carney, Ugur Cetintemel,
Mitch Cherniack, Christian Convey, Sangdon Lee,
Michael Stonebraker, Nesime Tatbul, and Stanley B.
Zdonik. Aurora: a new model and architecture for data
stream management. VLDB Journal, Vol. 12, No. 2, pp.
120-139, 2003.
[2] Arvind Arasu, Shivnath Babu, and Jennifer Widom.
The cql continuous query language: Semantic foundations and query execution. VLDB Journal, Vol. 15, No.
2, pp. 121-142, 2006.
[3] Brian Babcock, Shivnath Babu, Mayur Datar, Rajeev
Motwani, and Jennifer Widom. Models and Issues in
Data Stream Systems. In ACM Symposium on Principles of Database Systems, 2002.
[4] O. Benjelloun, A. Das Sarma, A. Halevy, and J. Widom.
Uldbs: Databases with uncertainty and lineage. In Proc.
of International Conference of Very Large Databases,
pp. 953–964, 2006.
[5] Lars Brenna, Alan Demers, Johannes Gehrke, Mingsheng Hong, Joel Ossher, Biswanath Panda, Mirek
Riedewald, Mohit Thatte, and Walker White. Cayuga:
a high-performance event processing engine. In Proc. of

境では，実行木の出力タプル以外のデータはユーザに提供されな

5

日本データベース学会論文誌 Vol.8, No.1

2009 年 6 月

DBSJ Journal, Vol.8, No.1
June 2009

一般論文

and Generate Dataset Provenance. In Proc. SIGSOFT
2008/FSE-16, 2008.
[17] Jonathan Ledlie, Chaki Ng, David A. Holland, KiranKumar Muniswamy-Reddy, Uri Braun, and Margo
Seltzer. Provenance-Aware Sensor Data Storage In
Proc. icdew,pp.1189, 21st International Conference on
Data Engineering Workshops (ICDEW’05), 2005.
[18] Adriane P. Chapman, H.V. Jagadish, and Prakash Ramanan. Eﬃcient Provenance Storage. In Proc. SIGMOD’08, 2008.

the 2007 ACM SIGMOD International Conference on
Management of Data, pp. 1100–1102, 2007.
[6] Sirish Chandrasekaran, Owen Cooper, Amol Deshpande, Michael J. Franklin, Joseph M. Hellestein,
Wei Hong, Sailesh Krishnamurthy, Sam Madden, Vijayshankar Raman, Fred Reiss, and Mehul Shah. TelegraphCQ: Continuous Dataﬂow Processing for an Uncertain World. In Proc. of the Conference on Innovative
Data Systems Research, 2003.
[7] Yingwei Cui, Jennifer Widom, and Janet L. Wiener.
Tracing the lineage of view data in a warehousing environment. ACM Transactions on Database Systems, Vol.
25, pp. 179–227, 2000.
[8] Yanlei Diao, Neil Immerman, and Daniel Gyllstrom.
Sase+: An agile language for kleene closure over event
streams. In UMass Technical Report 07-03, 2007.
[9] Lewis Girod, Yuan Mei, Ryan Newton, Stanislav Rost,
Arvind Thiagarajan, Hari Balakrishnan, and Samuel
Madden. The case for a signal-oriented data stream
management system. In Proc. of the Conference on Innovative Data Systems Research, pp. 397–406, 2007.
[10] The STREAM Group. Stream: The stanford stream
data manager. IEEE Data Engineering Bulletin, Vol.
26, No. 1, 2003.
[11] Jeong-Hyon Hwang, Magdalena Balazinska, Alexander
Rasin, Ugur Cetintemel, Michael Stonebraker, and Stan
Zdonik. High-availability algorithms for distributed
stream processing. In Prof. of the 21st International
Conference on Data Engineering, 2005[12] Hideyuki Kawashima, Michita Imai, and Yuichiro Anzai. Providing persistence for sensor data streams byremote wal. In Proc. DAWAK, pp. 524–533, 2006.
[13] A. Das Sarma, M. Theobald, and J. Widom. Exploiting lineage for conﬁdence computation in uncertain andprobabilistic databases. In Proc. of IEEE International
Conference on Data Engineering, 2008.
[14] 樫山俊彦, 花井知広, 田中美智子, 今木常之, 西澤格. スト

川島 英之 Hideyuki Kawashima2005 年慶應義塾大学大学院理工学研究科後期博士課程修了．同年，慶應義塾大学理工学部助手．2007 年筑波大学大学院システ
ム情報工学研究科講師，ならびに計算科学研究センター講師．博士 (工学)．センサデータ管理に関する研究に従事．情報処理学
会，ACM，日本データベース学会，各会員．

寺島 裕貴 Yuki Terajima
筑波大学大学院システム情報工学研究科在学中．日本データベース学会学生会員．

北川 博之 Hiroyuki Kitagawa
1978 年東京大学理学部物理学科卒業．1980 年同大学理学系研究科修士課程修了．日本電気（ 株）勤務の後，1988 年筑波大学
電子・情報工学系講師．同助教授を経て，現在，筑波大学大学院
システム情報工学研究科教授，ならびに計算科学研究センター
教授．理学博士（ 東京大学 ）．異種情報源統合，XML とデ ー
タベース，データマイニング，センサーデータベース，WWW
データ管理等の研究に従事．著書「データベースシステム」（昭晃堂）「，The Unnormalized Relational Data

Model 」
（ 共著，
Springer-Verlag ）等．日本データベース学会理事，情報処理学会フェロー，電子情報通信学会フェロー，ACM，IEEE-CS，日
本ソフトウェア科学会，各会員．

リームデータ処理におけるデータベースアーカイブ 処理高速化の提案と評価. 日本データベース学会 Letters, Vol. 6,

No. 2, pp.37–40, 2007.
[15] Shawn Bowers, Timothy McPhillips, Bertram Lud¨ascher, Shirley Cohen, and Susan B. Davidson. A Modelfor User-Oriented Data Provenance in Pipelined Scientiﬁc Workﬂows. Lecture Notes in Computer Science,
Volume 4145, Provenance and Annotation of Data,
2006, pp. 133-147.
[16] Leon J. Osterweil, Lori A. Clarke, Aaron M. Ellison, Rodion Podorozhny, Rodion Podorozhny, Alexander Wise,
Emery Boose, and Julian Hadley. Experience in Using a Process Language to Deﬁne Scientiﬁc Workﬂow

6

日本データベース学会論文誌 Vol.8, No.1

2009 年 6 月