[論文] Incremental Computation of Complex Object Queries
http://portal.acm.org/citation.cfm?id=504294&dl=GUIDE&coll=GUIDE&CFID=65531524&CFTOKEN=43210749
IBMのTRLの人が書いたらしい．
2. Comprehension Query Notation
Comprehenstion て List Comprehension の Comprehension のこと．SQLのクエリを内包表記に直して議論しますよー，という下準備
{e | v<- e' }
{x | f(x) } ( f: X->bool )
前回に引き続き，ここでもbagだのsetなどが登場．
3. Problems with Incremental Computation
基本アイデアは
- f(E) = {x*x| x<-E }
として，
- E={1,2}
だったときに
- E'={1,2,3}
となったら
- ΔE={3}
として，f(ΔE) を再計算して，もとのf(E)にくっつけちゃえ，というもの
でも，この方式はEがbagやsetでないと使えない．primitiveな値の場合はどうしよう，
あと，
- E={-4,1,4}
- f(E)={16,1}
のとき，4を削除してもやっぱり
- f(E)={16,1}
なので，削除や追加などの変更捜査と，実際のクエリの変動は一致しないから面倒．
という問題提起．
4．Translation Into Collection
上の1個めの問題に対応するために，primitiveな値もむりやりbagにおきかえてしまえ，という変換をかます
- x を {x} に変換
- {x}+{y} を {x'+y'| x'<-x, y'<-y }に変換．なんかリストモナドぽい
あと，オブジェクト {name:"John", age:32} は[ (name, {"John"}) , (age ,{32}) ] だそうだ．
この場合，32 を 33にしたければ，32をbag(set)から削除して，33 を追加しなおすという操作をすることになる．
5. Incremental Computation of Comprehension Instances
さっきの
- E={-4,1,4}
- f(E)={16,1}
の問題を何とかする方法．
内包表記の式にもとづき依存関係のツリーを作っておいて，変更があったときはツリーをたどる，というオーソドックスな？やりかた．
6. Update Propagations
- Strict Update (自分自身を更新-> 自分に依存している値(dependents)をたどって更新させる）
- Lazy Update(自分の分はフラグを立てるだけでおいといて，dependentsから先に更新を依頼．自分自身は最後に更新．ただし更新の過程でdependents によって自分自身が先に更新されるかも）
- Hybrid Update （両者のいいとこどり？）
8． Evaluation
日本人の論文なのでEvaluationがしっかり．というか他国の論文てEvaluationないのに通っているのが多いので不思議．
- 自分で書いたIncremental Evaluationによるクエリ更新のプログラムと，自動生成したものとを比較．
- ある程度の規模のOODBに対して，データを追加削除変更した場合のビューの再計算速度を測定
- で，提案手法のほうが数倍遅い．
うーん，たぶん提案手法のほうが楽にかけるから，ちょっと遅くても楽できるでしょ，といわなきゃいけないんだろうけど，コード量とかに関する議論がない．
