[ Top page ]

« データ・ストリーム管理システムの実例 | メイン | IPv6 概要 »

データ・ストリーム管理システム

データ・ストリーム管理システムのクエリ機能

データ・ストリーム管理システム (DSMS) においては,Tapestry [Ter 92] 以来,継続的クエリが重視されてきている. そこで,ここで もまず継続的クエリについて説明 する.

DSMS においては到着したデータを未来永劫,保存することはできない. そのため,実行可能なクエリの対象は比較的最近到着したデータだけを対象とする必要がある. このような限定のための方法がスライディング・ウィンドウ [Bab 02] である. DSMS においてあつかうデータの種類としてストリーム関係 (relation) とがあるが,スライディング・ウィンドウはストリームを入力して関係 をかえすオペレータである. データ・ストリーム管理システム STREAM [Ara 09] のといあわせ言語である CQL (Continuous Query Language) においては,つぎのような種類のスライディング・ウィンドウが定義されている [Ara 09].

要素にもとづくスライディング・ウィンドウ
スライディング・ウィンドウ [Rows N] はストリームの要素のうち最新の N 個を抽出する. また,[Rows Unbounded] は範囲を限定しない (無限の過去からの) 要素を意味する.
時間にもとづくスライディング・ウィンドウ
スライディング・ウィンドウ [Range t] はある時間 t だけ過去から現在までのあいだに到着した ストリーム要素を抽出する. たとえば,[Range 2 Minutes] は 2 分前から現在までに到着した要素 を抽出する. また,[Now] は最新の要素だけを抽出する.
分割されたスライディング・ウィンドウ
スライディング・ウィンドウ [Partition By A1, …, Ak Rows N] は,最近の N 個の要素について ストリームのフィールド A1, …, Ak の値がひとしいものどうしをまとめて,このストリームをサブストリームに分割する.

スライディング・ウィンドウがストリームから関係へのオペレータだったのに対して,CQL はつぎのような関係からストリームへのオペレータももっている.

Istream
Istream (insert stream) は時刻 t における関係 R(t) と時刻 t–1 における関係 R(t–1)をもとに して,時刻 t において関係 R に追加された要素すなわち R(t) – R(t–1) を時刻 t における要素と するストリームをもとめる.
Dstream
Dstream (delete stream) は時刻 t において関係 R から削除された要素すなわち R(t–1) – R(t) を時刻 t における要素とするストリームをもとめる.
Rstream
Rstream (relation stream) は時刻 t において関係 R がふくむ要素すべてを時刻 t における要素 とするストリームをもとめる.

CQL や Tapestry のといあわせ言語 TQL (Tapestry Query Language) をはじめとして,おおくの DSMS の継続的クエリ記述言語は関係データベースのための クエリ記述言語 (といあわせ言語) SQL (Structured Query Language) にもとづいている. ここでは CQL によるクエリの例を列挙する.

第 1 の例は 2 つのストリーム S1, S2 を join する単純なものである.

SELECT * FROM S1 [Rows 1000], S2 [Range 2 Minutes]
WHERE S1.A = S2.A and S1.A > 10

ここでは 2 つのストリームからそれぞれスライディング・ウィンドウによって関係がもとめられ, それらを join した関係が結果としてもとめられている. この例は Arasu [Ara 09] から引用した.

第 2 の例はバックボーン B のトラフィックのうち顧客のネットワーク C に帰するものがどれだけのわりあいをしめるのかをもとめるクエリ Q3 である:

(SELECT count(*) FROM C, B
    WHERE C.src = B.src and C.dest = B.dest and C.id = B.id)  /
(SELECT count(*) FROM B)

この例は Babcock ら [Bab 02] から引用した. ここではスライディング・ウィンドウが指定されていないので,ウィンドウ・サイズはシステムにまかされている. このようなあいまいさを許容しているのは,CQL の設計において厳密さよりもつかいやすさを重視しているからだとかんがえられる.

最後に Istream と Rstream に関する例を 1 個ずつあげる. これらも Arasu [Ara 09] から引用した.

SELECT Istream(*) FROM S [Rows Unbounded] WHERE S.A > 10
SELECT Rstream(S.A, R.B) FROM S [Now], R WHERE S.A = R.A

いずれも比較的単純なフィルタリングをおこなっている. Istream や Dstream を使用すればストリームにふくまれるデータを全体として関係に変換してあつかうことになるが,Rstream を使用すれば要素ごとに関係に変換してあつかうことになる. このように,CQL においては単純なフィルタリングをおこなうためにも,いったんストリームを関係に変換する必要がある.

参考文献

  • [Ara 09] Arasu, A., Babcock, B., Babu, S., Cieslewicz, J., Datar, M., Ito, K., Motwani, R., Srivastava, U., and Widom, J., “STREAM: The Stanford Data Stream Management System”, in Garofalakis, M., Ge-hrke, J., Rastogi, R., ed., “Data Stream Management: Processing High-speed Data Streams (Data-Centric Systems and Applications)”, Springer-Verlag New York, 2009, http://dbpubs.stanford.edu:8090/pub/2004-20.
  • [Bab 02] Babcock, B., Babu, S., Datar, M., Motwani, R., and Widom, J., “Models and Issues in Data Stream Systems”, 21st ACM Symposium on Principles of Database Systems (PODS 2002), 2002.
  • [Ter 92] Terry, D., Goldberg, D., Nichols, D., and Oki, B., “Continuous Queries over Append-Only Da-tabases”, 1992 ACM SIGMOD Int’l Conference on Management of Data, pp. 321-330, 1992.
Keywords:

コメントを投稿

Powered by
Movable Type 3.36