[ トップページ ]

« Perl による関係データベースのクエリのシミュレーション | メイン | 開催中のオークションをもとめるクエリの実行法 »

ストリームデータ処理

DSMS によって開催中のオークションをもとめる問題の解法

データストリーム管理システム (DSMS) の例題として,STREAM (Stanford Stream Data Manager) や ATLaS (Aggregate & Table Language and System) などにおいて,オンライン・オークションに関するものがとりあげられている. オークションの例題のひとつとして,「現在開催されているオークションをもとめる」 というものがある. STREAM,ATLaS の両方でとりあげられているが,どちらの記述も問題がおおいとおもわれる. この例題について,かんがえてみる.

オンライン・オークションの例題記述

オンライン・オークションの例題は “Stream Query Repository: Online Auctions” (例題 4) に記述されている.

STREAM における解法

STREAM の CQL (Continuous Query Language) によるその記述は “Stream Query Repository: Online Auctions (CQL Queries)” にある. そこにしめされた CQL による記述はつぎのとおりである.

Select * 
From   OpenAuction 
Where  itemID Not In (Select itemID 
                      From   ClosedAuction)

OpenAuction はオークションが開始されるごとにレコードが生成されるストリームであり,ClosedAuction はオークションが終了するごとにレコードが生成されるストリームである. したがって,かんたんにいえばそれらの差をとれば,現在開催されているオークションがもとめられることになる. しかし,上記のプログラムがどのように実行されて現在開催されているオークションがもとめられるのか,私には理解できない.

ATLaS によるオンライン・オークションの例題は “Online Auction system on ATLaS” に記述されているが,そこでは上記の CQL による記述に対する疑問がしめされている. すなわち,この CQL による記述からえられる結果 (開催中のオークション) はストリームだが,これは関係であるべきだというのである.

ATLaS における解法

ATLaS による記述はつぎのとおりである.

aggregate deleteClose(d_id int):int
{
initialize:iterate:
{
	delete from CurrentOpen
		where itemID = d_id;
}
};

// 一部省略
insert into CurrentOpen
	select itemID, sellerID
	from OpenAuction;
select deleteClose(itemID)
from ClosedAuction;

しかし,このプログラムは CQL による記述とくらべるとはるかに複雑であるばかりでなく,重大な問題をふくんでいるとかんがえられる. insert 文によって開催中のオークション (CurrentOpen) がもとめられているが,この文はテーブルに要素 (オークション) を追加していくだけである. 終了したオークションをそこから削除するためにつぎの select 文があるのだが,この文が CurrentOpen に作用しているということは,deleteClose というユーザ定義関数のなかをみなければわからない. つまり,この関数の副作用を利用している. SQL や CQL は本来は宣言的な言語のはずだが,この例においてはその性質が破壊されている. このような記述が妥当なものだとはいえないだろう.

よりよい解法をもとめて

このように,STREAM における記述も ATLaS における記述も満足できるものではないので,「現在開催されているオークションをもとめる」 という問題をとくためのもっとよい方法をみつける必要がある. かんがえられるひとつの方法はつぎのようなものである.

Select rstream(*)
From (Select itemID
      From OpenAuction [range .. now])
     Minus 
     (Select itemID
      From ClosedAuction [range .. now]);

ここで OpenAuction [range .. now] は過去のすべてのオークション開始に関するレコードからなる関係をあらわし,ClosedAuction [range .. now] は過去のすべてのオークション終了に関するレコードからなる関係をあらわす. それらから同一形式のレコードをもとめるため,itemID だけを抽出している (ここでは itemID がオークションを識別できることを仮定している). その差をもとめれば,現在開催中のオークションをもとめることができる. rstream(*) によって,つねに最新の情報が報告される.

実際にこれらを関係としてもとめるとストリームを関係に変換するときにデータ量が膨大になって計算できなくなる可能性がある. しかし,このように表現すればプログラムは簡潔になる.

“rstream(*)” のかわりに “*” をつかうと,結果はストリームではなく関係になる. 時間がたつと “now” つまり現在はかわっていくので,計算結果もかわっていく. このように時間とともに変化するものは本来,ストリームとして表現されるべきだとかんがえられるので,上記のプログラムにおいては rstream をつかった.

2009-1-2 追記:
上記の 「よりよい解法」 はもとのプログラムにスライディング・ウィンドウを指定したつぎのプログラムと等価だとかんがえられる.

Select * 
From   OpenAuction [range .. now] 
Where  itemID Not In (Select itemID 
                      From   ClosedAuction [range .. now])

したがって,もしもとのプログラムがこのように解釈されるのだとすれば,もとのプログラムはただしいことになる.

Keywords:

トラックバック

このエントリーのトラックバックURL:
http://www.kanadas.com/mt/mt-tb.cgi/3444

コメントを投稿

このページについて

2008-12-31 22:50 に投稿されたエントリーのページです。

他にも多くのエントリーがあります。メインページアーカイブページも見てください。

Creative Commons License
このブログは、次のライセンスで保護されています。 クリエイティブ・コモンズ・ライセンス.
Powered by
Movable Type 3.36