[ トップページ ]

« DSMS によって開催中のオークションをもとめる問題の解法 | メイン | ストリーム・データ処理によるオンライン・オークションのシミュレーション (非構造化版) »

ストリームデータ処理

開催中のオークションをもとめるクエリの実行法

DSMS によって開催中のオークションをもとめる問題の解法」 に書いたプログラムの実行法についてかんがえる.

上記の項目にはつぎのようなプログラムをしめした.

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

このプログラムを最適化せずに実行すると,(離散的な) 時刻がすすむたびに関係 OpenAuction [range .. now] と ClosedAuction [range .. now] とを更新して Minus の計算を実行することになる. しかし,これはいちじるしく非効率である.

効率を改善するひとつの方法は,直前の時刻における差 (Minus の結果) を保持して,それを更新して現在の差をえる方法である. 時刻がすすむことによっておこりうることは,OpenAuction のレコードが追加されること,ClosedAuction のレコードが追加されること,またはそれら両方が一度におこること (さらに,レコードが一度に複数個追加されることもおこりうる) である.

OpenAuction のレコードが追加されたときは,その itemID が ClosedAuction [range .. now] にふくまれるかどうか検索する必要がある (ここでは itemID がオークションを識別できることを仮定している). もしふくまれれば差を更新する必要はないが,ふくまれなければ差にそのレコードを追加する.

ClosedAuction のレコードが追加されたときは,その itemID が差にふくまれていればそこからそのレコードを削除する.

これらの検索はハッシュ表をつかえば効率的に実行することができる.

Keywords:

トラックバック

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

コメントを投稿

このページについて

2009-01-01 00:37 に投稿されたエントリーのページです。

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

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