Never Stop Questioning

CQL

最終更新：2011年06月12日 01:18

t-style

- view

メンバー限定登録/ログイン

CQL(Continuous Query Language)

DSMS(Data Stream Management System)またはSPE(Stream Processing Engine)と呼ばれるストリーム処理に特化したデータ管理システムで使われる継続的クエリ(Continuous Query)の一種。StanfordのStream向けに実装された。詳細ははここを参考するとよい（抽象言語を説明してから具体言語を説明しているのがおもしろい）。RDBMS(Relational Data Base Management System)で用いられるSQLを自然に拡張していることもあってかIBMをはじめ、Oracleや日立のミドルウェア製品で採用されている。

コンセプト

先の通り、よく知られたSQLフォームをとっていることをはじめ、簡単かつわかりやすい記述であり、計算（演算、要約）のプランや実行モデルが一般的な考え*に基づいているおり(*はCQLの抽象言語で表現されるものと個人的には理解)、異なる実行戦略を簡単に実行できることなどが論文冒頭で主張されている。

ストリームとリレーション

DSMSはその名の通りストリームを扱う。CQLの文脈においてストリームとリレーションは区別される。それぞれの定義を述べる。

ストリーム

ストリームは、タイムスタンプとタプルのペアとして構成される無限個の要素を持つ多重集合(bag/multiset)である（ここで多重集合とは単に重複を許すと認識すればよさそう）。

リレーション

リレーションは、タイムスタンプから有限の（しかし制限のない）タプルへの写像(map)である。いわゆるリレーションとは異なる定義なのは注意が必要（さらにいうと関係代数が定義するリレーションとRDBMSのリレーションも順序に関して異なる）。

3つの演算

CQLは、Stream-To-Relation、Relation-To-Relation、Relation-To-Streamという3タイプの演算から構成される。つまり、代表的なDBMSの役割はストリームを入力としてストリームを出力することなわけだが、それを実現するために、次の手順を踏む。

受け付けたストリームをリレーションに変換する
リレーションを別のリレーションに変換（調理）する
リレーションをストリームに変換してエミットする

Stream-To-Relation

おそらく一番特徴的なのがこの演算。ウィンドウ演算と呼ばれ、無限に続くストリームから有限のリレーションを切り出す。その切り出し方が3つ定義されている。

タイムベース

τ時刻前までのデータを得る。

タプルベース

最新N個のデータを得る。

分割ウィンドウ

SQLのGroup Byのようにタプル中の特定の属性に応じてサブストリームに分けたのち、前記のウィンドウ演算を実行する。

Relation-To-Relation

SQLそのまま。

Relation-To-Stream

演算結果の出力タイミングに応じて3タイプ定義されている。

Istream

演算した結果(R)、新たな要素が生まれたとき、その要素をストリームに出力する。つまり、R(τ)からR(τ)∧R(τ-1)を除いた要素を出力する。なお、τ＝0のときはR(τ)が出力される。

Dstream

演算した結果(R)、今まであった要素が消えたとき、その要素をストリームを出力する。つまり、R(τ-1)からR(τ)∧R(τ-1)を除いた要素を出力する。

Rstream

演算したらそのまま結果(R)を出力する。ある意味一番シンプル。

クエリの実行タイミング

イベントドリブンとタイムドリブンに分けられる。

技術課題（調査不足）

継続的クエリ

ここで取り上げたCQL以外にもいろいろな継続的クエリが提案されている。基本的に言語は宗教論争になるのでなんとも言えない。ただ、Relation-Relationの自由度はSQL同様に悩ましいと思われる。

順序の逆転

たとえば、伝送路で一部のデータパケットが消失した場合、その部分だけが再送されるため、タイムスタンプがあべこべになる可能性がある。また、複数の伝送路を使っている場合にも同様である。こういった状況で何の工夫もなしに上述の演算を行うと、10分前までのデータをすべて指定したつもりが指定しきれないといった厄介な問題を生む。この解決方法としては、演算の実行をぎりぎりまで待ってみたり、制御コードを使って逆転が起きていないことを保証してみたりする手があるらしい。