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

データストリーム管理システム（データストリームかんりシステム、DSMS）は、連続したデータの流れを管理するコンピュータプログラムである。DSMSはデータベース管理システム（DBMS）と似ているが、データベース管理システムは通常のデータベースに格納された静的なデータを扱うように設計されている。DSMSは柔軟なクエリ処理も実現し、クエリでどのような情報が必要かを表現できるようになっている。しかし、DBMSと比較するとDSMSはクエリを1度だけ実行するのではなく、インストールされている限り連続的に永久に実行し続ける。したがって、クエリは明示的にアンインストールされるまで継続して実行される。ほとんどのDSMSはデータ駆動型なので、システムにデータが取り込まれる限り、連続的なクエリは新たな結果を生成し続ける。この基本概念は複合イベント処理(CEP、en)と似ており、双方の技術は部分的に融合している。

機能原理

DSMSで最も重要な機能は、メインメモリ容量などリリソースの制限はあるものの、潜在的に無限で素早く変化するデータストリームに、柔軟な処理と操作を同時に行うことである。次の表はDSMSの機能を伝統的なDBMSと比較している。

データベース管理システム (DBMS)	データストリーム管理システム (DSMS)
永続データ (関係)	揮発データストリーム
ランダムアクセス	シーケンシャルアクセス
1度きりのクエリ	連続的クエリ
(理論的に) 無制限の2次記憶	制限のあるメインメモリ
現在の状態に関連	入力順序に依存
比較的少ない更新頻度	潜在的に非常に高い更新頻度
処理時間への要求は少ないか無い	リアルタイム処理が必要
正確なデータを前提とする	古い/不正確なデータを前提とする
計画可能なクエリ処理	変動するデータ到着頻度やデータの性質

処理とストリーミングのモデル

DSMSでの大きな課題は、決められた量のメモリとデータへのランダムアクセスなしで、潜在的に無限量のデータストリームを処理することである。1回のパスで取り込むデータを制限する手法にはいくつかあり、大きく二つの種類に分けることができる。一つにはデータをサマライズしようとする圧縮技術があり、もう一つにはデータを（有限な）部分に分割しようとするウィンドウ技術がある。

概略

圧縮技術の背景にある考え方は、データストリームの全ての（生）データポイントではなく、データの概略だけを保つというものである。アルゴリズムとしてはランダムにデータポイントを選択するサンプリング手法から、ヒストグラムやウェーブレット、スケッチングなどの手法を用いるものまである。一つの単純な圧縮技術の例としては連続的に平均を計算するというものがある。それぞれのデータポイントを記録するのではなく、サマリーといくつかのデータのみを保持する。しかし、概略はデータを正確に反映するものではないことに注意する必要がある。従って概略による処理は不正確な結果をもたらす可能性がある。

ウィンドウ

ウィンドウ技術では、データの概略を使用して全てのデータストリームの特徴を圧縮するのではなく、データの一部分だけを扱う。このアプローチは一番直近のデータのみが関連しているという考え方に基づいている。ウィンドウによりデータストリームは連続的に切り出される。例えば最後のデータ要素を10個だけ取り出し、処理にはそれらだけを考慮する。ウィンドウには他にFIFOリストに似たスライディングウィンドや、直近の10秒のデータだけを考慮するような時間ベースのウィンドウなどがある。ウィンドウの実装方法にもいろいろなアプローチがある。例えば、システム全体のウィンドウにはタイムスタンプや時間隔を使用し、単一処理のステップにはバッファベースのウィンドウをするというものがある。

クエリ処理

たくさんのプロトタイプがあり、標準となるアーキテクチャはない。しかし、ほとんどのDSMSはDBMSのクエリ処理を基にしたクエリ記述をしており、それは演算子の計画に変換される。これらの計画は最適化することができ実行される。クエリ処理には下記のようなステップがある。

連続的クエリの式

クエリの式はDBMSにおけるSQLのような宣言的言語を使用して実行される。連続的クエリを表現する式にはまだ標準が存在しないので、多くの言語とその派生形が存在する。しかし、 Continuous Query Language (CQL), StreamSQL or EPLなどはSQLを基にしている。他には処理ステップを箱で表現し箱を矢印で接続して流れを表現するグラフィカルなアプローチも存在する。

言語は処理モデルに強く依存する。たとえば、処理にウィンドウを使用するならウィンドウの定義が式に必要である。StreamSQLでは直近10個の要素に対するスライディングウィンドウへのクエリは下記のようになる。

SELECT AVG(price) FROM examplestream [SIZE 10 ADVANCE 1 TUPLES] WHERE value > 100.0

This stream continuously calculates the average value of "price" of the last 10 tuples, but only considers those tuples for the average calculation where price is greater than 100.0. このストリームは"price"にある最後の10個のタプルをの平均計算するが、priceが100.0を超えるタプルのみを対象とする。

次のステップでは宣言的なクエリは論理的クエリ計画に変換される。クエリ計画は有向グラフでありノードが演算子でエッジが処理フローを表現する。クエリ計画にある個々の演算子はフィルタリングや集計などの特定の処理に関する意味をカプセル化する。DSMSではリレーショナルデータストリームの処理を行い、演算子は関係代数の処理そのものであるか似たものであり、選択、射影、結合、セットなどの処理がある。この演算子の概念はDSMSによる処理の柔軟性と網羅性を実現する。

クエリの最適化

論理クエリ計画は最適化することができるが、これはストリーミング計画に強く依存する。連続的なクエリの最適化の基本的概念は関係データベースシステムのものと同じである。もしリレーショナルデーターストリームがあり、論理クエリ計画が関係代数からの関係演算子に基づいているならば、クエリオプティマイザは同じ代数処理でクエリを最適化するであろう。たとえば、選択演算子は結合演算子ほどには計算処理を必要としないので、ソースにまで落とし込む。

さらに、DBMSのようなコストベースの最適化技術もあり、同等のいくつかのクエリ計画の中からコストが最低のものが選択される。一つの例は二つの連続した結合演算子の順序を選択するものである。DBMSではこの選択は対象となるデータベースの統計情報に基づいて決定される。しかし、データストリームのデータは前もって知ることができないため、DBMSのような統計は存在しない。だが、データストリームを観察することによって何らかの統計を得ることはできる。この統計を使用してその後でのクエリを最適化することができる。したがってDSMSには実行されているクエリ計画を新しいものに置き換える、計画移行戦略が必要である。

クエリの変換

論理演算子は処理の意味にだけかかわり、何のアルゴリズムも含んでいないので、論理クエリ計画は対応する実行形式に変換されなければならない。これを物理クエリ計画と言う。論理演算子と物理演算子を区別することにより、一つの論理演算子に複数の実装を行うことができる。例えば結合では入れ子ループ結合やソートマージ結合などのアルゴリズムを実装することができる。これらのアルゴリズムは使用するストリームと処理モデルに強く依存する。最後に、クエリは物理クエリ計画として使用できるようになる。

クエリの実行

物理クエリ計画には実行可能なアルゴリズムが含まれるので直接実行することができる。このために物理クエリ計画はシステムにインストールされる。（クエリ計画の）グラフの底はコネクターからセンサまで全ての入力されるソースに接続されている。グラフの頂上はデータの視覚化などの出力シンクに接続されている。ほとんどのDSMSはデータ駆動型なので、ソースからの入力されてくるデータソースをクエリ計画からシンクに押し出すことでクエリが実行される。データ要素が演算子を通過するたびに、演算子はデータ要素に対して特定の演算を実行し、結果を全ての後続する演算子に渡す。