半永続データのモデル化及び自己組織化管理の諸問題の考察
5
0
0
全文
(2) 寿命付きデータはキャッシュデータだけでなく、検. のモデル化と寿命を管理する手法について述べる。続. 索エンジンが集めてきたデータは時間が経つことにつ. いて 3 節では、構造化程度から見た半永続データのモ. れ古くなっていくため、寿命付きるデータと考えられ. デル化に解決する必要な問題を検討し、半永続データ. る 。ま た 、個 人 や 組 織 内 部 が 日 常 に 扱 う デ ー タ の う ち 、. 管 理 シ ス テ ム SPDMS の 実 現 方 法 を 提 案 す る 。. 一生保存するべきものが少なく、ほとんど年月が経つ ことにより価値がなくなるデータである。更に、会議. 2. デ ー タ の 寿 命 と そ の モ デ ル 化. 期間中に出された機密データは一定の期限に限って見. 半永続データをモデル化するために最も重要なの. られるが、期限が過ぎると自動的に消えると望まれて. は「寿命」のモデル化と考えられる。. いる。. 2.1. データの寿 命. これより更に拡大していくと、すべてのデータはラ. 寿 命 と は 「 1． 生 命 の 存 続 す る 期 間 。 特 に 、 あ ら か. イフサイクルがある。データの量が膨大化になってい. じ め 決 め ら れ た も の と し て 考 え ら れ る 命 の 長 さ 。2．物. く に つ れ 、そ の ラ イ フ サ イ ク ル の 管 理 は 重 要 性 が 増 す 。. の使用に耐える期間。また、その限界」である。デー. しかし、データ工学でこれまで扱われてきた主なデ. タの寿命は以下のように定義できる。. ータは永続データであり、明示的に削除・変更しない. 1.. 存 続 す る 期 間（ L 寿 命 ） ：デ ー タ の あ ら か じ め 決. 限りそのまま永続的に保存し続ける。永続性を維持す. め ら れ た 存 続 す る 期 間 。 期 間 を 超 え る と 、デ ー. る た め に 、バ ッ ク ア ッ プ /リ カ バ リ ー を は じ め 、様 々 な. タ が 自 動 的 に 消 え る 。例 え ば 、 秘 密 デ ー タ の 寿. 技術の開発を積み重ねてきた。そして、つい最近、ネ. 命 。 Lifetime の 意 味 か ら 、 こ の よ う な 寿 命 を L. ットワーク利用関連のデータ、センサーデータ、サー. 寿命という。. バアクセスログ、電話接続記録など、大量で高速に到. 2.. 使 え る 期 間 （ V 寿 命 ）： 有 効 に 使 え る 期 間 。 そ. 来し続けるストリームデータに注目が急速に高まっ. の 期 間 を 超 え る と 、デ ー タ が 無 効 に な り 使 え な. ている。ストリームデータは永続データと違い、一般. く な る 。デ ー タ 自 体 は 消 え る か ど う か 、他 の 条. に全て保存する必要がなく、一度処理が済むと二度と. 件と 合 わ せて 決定 す る。例 えば 、検索 エ ンジ ン. アクセスすることができない。. デ ー タ の 寿 命 。 Validation の 意 味 か ら 、 こ の よ. ストリームデータの寿命は 0 であれば、永続データ. うな寿命を V 寿命という。. の 寿 命 は 無 限 大 (∞)と 考 え ら れ る 。寿 命 ∞の 永 続 デ ー タ. 一 般 に 、各 デ ー タ に L と V の 二 種 類 の 寿 命 が 同 時. に対して、データベースを中心とした技術は盛んに研. に 持 つ ．（ L， V） の よ う に 表 わ せ る 。 ま た 、 寿 命 は. 究をおこなってきた。寿命 0 のストリームデータに対. 期 間 で 表 現 す る こ と も で き る し 、例 え ば 、「 1 ヶ 月 」、. する研究もつい最近ホットなトピックとなっており、. と 期 限 で 表 現 す る こ と も で き る 、 例 え ば 、「 2040 年. 様 々 な 研 究 開 発 を 展 開 し て い る ［ 2］。 し か し な が ら 、. 10 月 1 日 ま で 」. 寿 命 (0, ∞)の デ ー タ を 対 象 と し た 研 究 は 著 者 ら の 知 る 限りまだ体系的に行っていない。 データ 定 義 明示的に変更・削除しな 永続データ い 限 り そ の ま ま 保 存 し 続 けるデータ ストリーム 高 速 に 到 達 し 一 度 し か 見 データ られないデータの流れ 明示的或は暗黙的に寿命 半永続 が付けられ、期限内のみ データ 保存されるデータ. 2.2. 寿 命 の種 類 寿命は以下の種類ある。それぞれの決め方も異なる。. 寿命. まず、寿命とデータの構造との関連の有無によって絶 対寿命と相対寿命に分類できる。. ∞. -. 絶 対 寿 命 (mandatory)： ほ か の デ ー タ に 依 存 せ ず 、 自 ら の 決 め ら れ る 寿 命 。例 え ば 、 秘 密 デ ー タ は 受. 0. け取った後 3 時間以内に消すと寿命を設定すると、 システムが自動的に消してくれる。. (0, ∞). -. 相 対 寿 命 (reciprocal)： 他 の デ ー タ の 存 続 に よ り 、 自らの存続が決める。例えば、退社、退学した人. 表 1． 各 種 デ ー タ と そ の 寿 命. のデータはその人のアカウントデータの存続に よって、消すか消さないかを判断する。. 本 研 究 で は 、明 示 的・暗 黙 的 に (0, ∞)の 寿 命 が 付 け ら. そして、寿命の長さが変更できるかどうかによって、. れ、寿命期限内に限って保存するデータを半永続デー タと呼び、それぞれのデータの関連と違いを表 1 にま. 固定型寿命と適応型寿命と分けられる。. とめた。. -. 固 定 型 寿 命 (fixed)： あ ら か じ め 決 め ら れ 自 動 的 に. -. 適 応 型 寿 命 (adaptable)： 利 用 パ タ ー ン 等 に よ っ て 、. 変 更 し な い 寿 命 。 例 え ば 、 10 年 間 、 1 週 間 。. 本 論 文 で は 、 半 永 続 デ ー タ 管 理 シ ス テ ム SPDMS （ Semi-Persistent Data Management System）の 開 発 を 目 指して、半永続データの性質の解明とモデル化にかか. 寿命 が 適 応し てい く 。例え ば、利 用 状況 によ っ て. わる諸問題と可能な解決方法を検討する。2 節は寿命. 寿 命 が 長 く な っ た り 、 短 く な っ た り 。あ る い は 逆. −308−.
(3) に利 用 さ れな いと 寿 命 が長 くな る 。例え ば、未 読. ル（ OORDB）が し ら れ て い る 。SQL は 標 準 的 問 合 せ 言. み の メ ー ル は 消 さ な い ほ う が よ い の で 、寿 命 が 長. 語である。. くするべきである。. 3.1.2. 半 構 造 永 続 デ ー タ. 上記の分類を組み合わせて、固定型絶対寿命、適応. 半構造データでは、構造自体は持っているものの、. 型相対寿命のように、寿命の種類を記述することもで. RDB モ デ ル の よ う に あ ら か じ め 定 め た レ イ ア ウ ト に. きる。前者の意味は「他のデータと独立して決められ. 拘 束 さ れ な い 可 変 的 な デ ー タ の こ と を い う 。XML で 記. た適応しない寿命」であり、後者は「ほかのデータに. 述した半構造データに関する研究は最も代表的である. 依存しながらも状況によって適応的に変更も可能な寿. 半 構 造 永 続 デ ー タ を 管 理 す る た め の シ ス テ ム は DBMS. 命」である。. のような既存のデータベースシステムを利用するのは. また、寿命の付け方によって、各々のデータにそれ ぞれ寿命を付けるか、それとも多くのデータをまとめ. 一 般 的 で あ る 。問 合 せ 言 語 に 、XQL、XQuery 等 が 知 ら れている。. て寿命を付けるか、という選択もある。一般にまとめ 付けは基本として、個別（例外）を指定できるように したほうがよい。例えば、すべてのメールは５年有効 と し 、「 重 要 メ ー ル 」 フ ォ ル ダ の メ ー ル だ け 、 20 年 有 効とする。. 永 続 性. 2.3. データのライフサイクル 寿命と関連するデータのライフサイクルを考える。 あるデータ管理システムにおいて、データのライフサ イクルは次のようになる。. 表 2． デ ー タ の 種 類 と デ ー タ 管 理 技 術 構造化程度 構造化 半構造化 非構造化 DBMS XML DB IR 永続 DSMS XML-DSMS ストリーム 時系列 SPDMS XML-SPDMS SPDFS 半永続. 3.1.3. 非 構 造 永 続 デ ー タ データにはっきりした構造のない文書型情報に対 し て 、情 報 検 索 技 術 IR（ Information Retrieval）を 利 用. 発生：データが始めてシステムに入る. するのは一般的である。中でも、ハイパーテキストの. 変更：新しいバージョンが発生する. リンク関係や、文の構造を利用した検索精度を高める. 移動：サブシステム間に移動する. 技術も知られているが、構造化データの意味上の「構. 合併：他のデータと合併する。. 造」は持っていないため、より高度な問合せが. 消滅・削除：システムから消える・消す. 3.2. ストリームデータ管 理 3.2.1. デ ー タ ・ ス ト リ ー ム. 変更 旧. ストリームデータはタイムスタンプ付きのタプル. 新. の集合である。個々のテータは構造をもっている。複 削除. 数 の ス ト リ ー ム の 間 や 、ス ト リ ー ム と RDB の 表 の 間 を ジョインして問合せを行うこともある。ただし、デー タにタイムスタンプが付いているため、問合せを実行. 発生. 寿命. す る と き に 、 Sliding Window で 参 加 す る タ プ ル を 最 近. 消滅. の部分だけに限定する。データ・ストリーム管理シス テ ム (Data Stream Management Systems)と い う よ う な ソ. 図 4． 寿 命 と デ ー タ の ラ イ フ サ イ ク ル. フトを中心に行う。. 3.2.2. 半 構 造 デ ー タ ・ ス ト リ ー ム. 3. デ ー タ の 構 造 化 と 半 永 続 デ ー タ 管 理 データの構造化程度によって、半永続データ管理の 方法も異なる。表 2 では、データの構造化程度と永続 性種類により、異なるデータ管理技術をまとめた。. 半 構 造 文 書 の 時 系 列 或 は 更 新 し 続 け る XML 文 書 に 対 し て 、 連 続 問 合 せ や オ ン ラ イ ン 予 測 [1,4]に つ い て 、 Sliding Window に お け る XQuery の 実 現 を 目 指 し て い る。. 3.3. 半 永 続 データ管 理. 3.1. 永 続 データ管 理. 半 永 続 デ ー タ も 、構 造 化 、半 構 造 化 、非 構 造 デ ー タ に. 3.1.1. 構 造 化 永 続 デ ー タ 構造化永続データは従来のデータベースシステム で 扱 う 対 象 で あ り 、 DBMS （ Database Management Systems）を 代 表 と す る ソ フ ト ウ ェ ア に よ り 、デ ー タ 管. 分けられる。それぞれのデータの特徴に応じたデータ 管理仕組みを開発する必要がある。 3.3.1. 構 造 化 半 永 続 デ ー タ 管 理 シ ス テ ム. 構 造 化 デ ー タ に 対 し て 、そ れ ぞ れ の デ ー タ モ. 理を実現している。データモデルはリレーショナルデ ー タ モ デ ル（ RDB）、オ ブ ジ ェ ク ト リ レ ー シ ョ ナ ル モ デ. デルに寿命を組み組む拡張をする必要がある。. −309−.
(4) リレーショナルデータモデルでデータを構造. したデータの自己組織化管理が可能になる。さらに利. 化 す る 場 合 、デ ー タ の 寿 命 付 け 方 は 次 の よ う に. 用パターンを反映した情報提供システムとして、実用 化も期待できる。. 考えている。 -. 4.1. 利 用 パターンの維 持. スキーマレベルの寿命 スキーマレベルの寿命とは、リレーショ ン ス キ ー マ の 寿 命 の こ と で あ る 。例 え ば 、 一時表は寿命 1 時間とする。. -. チャレンジ的な問題は利用パターンの情報を孤立 的 に 維 持 、提 供 す る た め の ア ル ゴ リ ズ ム の 開 発 で あ る 。 こ れ を 実 現 す る た め に 、 Bloom Filters の よ う な 非 常 に アクセスの時間上でも、維持に必要なメモリ空間上で. タプルレベルの寿命. も 、ス ケ ー ラ ブ ル で 、有 力 の 候 補 で あ る 。[10]で は 我 々. タプルレベルの寿命とは、ある条件を満. は図 2 のようなデータ構造を提案した。複数のハッシ. たすタプルのみに適用する寿命である。. ュ 関 数 で 、デ ー タ を 一 定 の 数 の カ ウ ン タ ー に 射 影 す る 。. 例えば、学生の学習出席状況は卒業から. 当たったカウンターだけ増やす。カウンターの値は増. 5 年間まで保存する。そのような条件を. える一方ではなく、ある一定の時間 T が経過すると、. 満たすタプルに 5 年間の寿命を付けるこ とになる。. カ ウ ン タ ー の 値 は Decaying 関 数 に 従 い 、一 定 の 量 を 減 らす。. 構 造 化 半 永 続 デ ー タ 管 理 シ ス テ ム SPDMS. B. （ Semi-Persistent Data Management Systems） に. h0. お い て 、普 段 の DBMS 機 能 の ほ か 、寿 命 に 巡 る. h0. 以下のよう新しい機能を実現する必要がある。 -. 寿命の定義. -. 寿命の変更. -. 寿命に関する問合せ. -. 適応型寿命の維持. -. LT. TBF 1 0. 0 h1 h1. 0 0. 1 0 0. 0 0 0. 0 h0. 0. h1. 0 0. 0. 寿命に関わるデータ整合性. 1. 図 2． TBF（ Time-Decaying Bloom Filters）. 3.3.2. 半 構 造 半 永 続 デ ー タ 半 永 続 XML デ ー タ を 代 表 と す る 半 構 造 半 永 続 デ ー. 4.2. 半 永 続 データの問 合 せ 半永続データへの問合せは一般の構造化データや. タ を 中 心 に SPDMS を 構 築 す る 。XML デ ー タ の 寿 命 に は DTD レ ベ ル の 寿 命 と XML 文 書 レ ベ ル の 寿 命 が あ る 。. XML デ ー タ へ と 同 じ 問 合 せ を サ ポ ー ト す る と 共 に 、下. DTD レ ベ ル の 寿 命 は DTD に 関 連 す る す べ て の XML. 記のような利用パターンを反映した問合せもできる。. 文 書 の 寿 命 と す る 。XML 文 書 レ ベ ル の 寿 命 は 、個 々 の. Q1:Data Stream に 関 す る 研 究 論 文 の う ち 、よ く 読 ま れ. XML 文 書 、或 は 文 書 集 合 の 寿 命 を 指 定 す る 。あ る 特 定. る ベ ス ト 10 の 一 覧. の文書に対して、両方の寿命に一致しないときには、. SELECT Top 10. 短い方が優先とする。. FROM ResearchPapers. *. WHERE title LIKE ‘%Data Stream%’ ORDER BY #References DESC. 3.3.3. 非 構 造 半 永 続 デ ー タ 非構造データはファイルとして扱うので、ファイル システムレベルの半永続化を求められる。半永続デー. Q2:. 著 者 は Michael Franklin で あ る レ ポ ー ト の う ち 、. 一番最近よばれた５つの一覧. タ の た め の フ ァ イ ル シ ス テ ム は SPDFS（ File Systems. SELECT Top 5. *. for Semi-Persistent Data）と す る 。キ ャ ッ シ ュ フ ァ イ ル. FROM Report. シ ス テ ム [5] に フ ァ イ ル の 利 用 パ タ ー ン や 有 効 期 限 を. WHERE author=’Michael Franklin’. 加 え て 、 SPDFS の 基 本 的 機 能 に 備 え る こ と に な る 。. ORDER BY #LastReferedTime ASC. 5. ス ト レ ー ジ 管 理 半永続データ管理システムが相応しい物理的デー. 4. 半 永 続 デ ー タ の 自 己 組 織 化 管 理 適応型寿命を維持するために、データの利用パター. タ管理サブシステムはデータのライフサイクル管理が. ン (ア ク セ ス 頻 度 、 最 近 の ア ク セ ス 時 間 )に 関 す る 情 報. で き る シ ス テ ム で あ る 。 M. Stonebraker ら [3]は 、 永 続. を管理する必要がある。これにより、利用状況を考慮. データのための多階層オブジェクトストアシステムを. −310−.
(5) 提案している。その特徴は. 分大きくなっていくにつれ、半永続データの滞在時間. 1.. ストレージ・デバイスの階層化. (寿 命 )が 十 分 長 く な り 、 デ ー タ の 明 示 的 な 利 用 も 可 能. 2.. ポリシー設定による階層間マイグレーション. になる。. 3.. 論理データによるポリシー設定. 例 え ば 、職 員 の デ ー タ に 対 し て 、次 の よ う な ポ リ シ ー. 7. 終 わ り に. を適用すると、パフォーマンスとストレージ・デバイ スの利用に適切である。. 半 永 続 デ ー タ に は 寿 命 や 、 利 用 状 況 (利 用 頻 度 な ど ). main memory representation:. に時間的属性がもたれているため、モデル化には時間. EMP where age >= 30 and age < 60. のモデリングが重要である。ストリームデータの寿命. disk representation: age < 30. を０とし、永続データの寿命を∞とすれば、半永続デ. archive representation: age >= 60. ー タ は 寿 命 (0, ∞ )と な る 。 こ の よ う に 、 ス ト リ ー ム デ. つまり、メイン・メモリに置くべきデータは最もよ. ータ、半永続データ、永続データを統一した見方で扱. く 使 わ れ る 30 才 ～ 60 才 の 職 員 デ ー タ で あ る 。 60 才 以. うことによって、関連分野の研究への貢献も期待でき. 上は退職するので、アカイブに入れてもいい。. る。. このようなポリシーに寿命付きデータの処理を加 えることができる。. 半永続データの研究は構造化データ、半構造データ において、展開できるが、非構造化データとして、フ. main memory representation:. ァイルシステムレベルの研究課題が残っている。今後. EMP where age >= 30 and age < 60. の研究として、オブジェクトリレーショナルデータと. disk representation: age < 30. 半 構 造 XML デ ー タ に 絞 っ て 研 究 を 深 め て 活 き た い 。. archive representation: age >= 60 and age < 100. とりわけ、以下の問題を優先的に解明していきたい。. drop away: age >= 100 つ ま り 、退 職 か ら 40 年 を 経 つ と 、そ の デ ー タ を 完 全 に廃棄する。. 6. 討. -. 寿命のモデル化と寿命管理機能. -. SPDMS シ ス テ ム に お け る 時 間 管 理 機 能. -. 半永続化データのインデックス. -. 半永続データの問合せ処理. 論 文. 半永続化データはアクセスパターンやデータの寿 命を考慮したディスク・キャッシュの一般化であり、 ハードウェア技術の更なる進展に伴い、ディスク容量 の制限が大幅に緩和されると想定しながら提案したも のである。従来のメモリキャッシュでは、データの量 が比較的少なく、データがメモリに滞在する時間もわ ずかで、データベースのような永続的データとして扱 うことができなかった。キャッシュに対する評価もヒ ット率とバイトヒット率などに限られている。 我々はウェブキャッシュに関する研究の中で、キャ ッシュデータの利用状況を分析した結果、ほとんどの キ ャ ッ シ ュ デ ー タ (60%以 上 ) が キ ャ ッ シ ュ さ れ た 期 間 に あ ま り 利 用 さ れ て い な い (20% 前 後 の ヒ ッ ト し か 得 ら れ て い な い )こ と が わ か っ た 。 こ の 事 実 に ふ ま え て 、 ヒット率と別にキャッシュコンテンツの利用率の観点 から、キャッシュの仕組みを考え直す必要があると考 え始めた。利用率を向上するためには、キャッシュコ ンテンツを直接利用者に提供できるようにモデル化す る 必 要 が あ る ［ 8］。 このように一度アクセスしたらすぐ消えるデータ に対して、キャッシュコンテンツは一定の期間データ をディスクに保存するので、永続データに対して、半 永続データとして扱うべきである。ディスク容量が十. [1]. 献. Sujoe Bose, Leonidas Fegaras, Data stream management for historical XML data. SIGMOD Conference 2004, pp. 239-250 [2] Lukasz Golab and M. Tamer Ozsu. Issues in Data Stream Management. In SIGMOD Record, vol. 32, no. 2 , pp. 5-14, June 2003 [3] Michael Stonebraker: Managing Persistent Objects in a Multi-Level Store. SIGMOD Conference 1991 pp.2-11 [4] 河野正太郎 有村博紀 有川節夫, 半構造データ 系 列 の オ ン ラ イ ン 予 測 と XML デ ー タ 圧 縮 へ の 応 用 ， DEWS 2003 [5] Jonathan Ledlie and Matthew McCormick. A Fast File System for Caching Web Objects, University of Wisconsin - Madison, Research Report, May 2000 [6] B. Babcock, S. Babu, M. Datar, R. Motwani, and J. Widom. Models and issues in data stream systems. PODS 2002, pp. 1–12, June 2002 [7] Y. Kambayashi and K. Cheng. Capacity bound-free web warehouse. CIDR 2003, pp. 47–57, 2003.. [8] E. A. M. Shriver, E. Gabber, L. Huang, and C. A. Stein. Storage management for Web proxies. In USENIX Annual Technical Conference, General Track, pp.203–216, 2001. [9] M. Rabinovich and O. Spatscheck. Web Caching and Replication. Addison-Wesley, 2002. [10] K. Cheng, et al. Efficient Web Profiling by Time-Decaying Bloom Filters, DBSJ Letters vol.4 no. 1.. −311−.
(6)
関連したドキュメント
以上の結果について、キーワード全体の関連 を図に示したのが図８および図９である。図８
• また， C が二次錐や半正定値行列錐のときは，それぞれ二次錐 相補性問題 (Second-Order Cone Complementarity Problem) ，半正定値 相補性問題 (Semi-definite
(2003) A universal approach to self-referential para- doxes, incompleteness and fixed points... (1991) Algebraically
Correspondence should be addressed to Salah Badraoui, [email protected] Received 11 July 2009; Accepted 5 January 2010.. Academic Editor:
In this paper, we will be concerned with a degenerate nonlinear system of diffusion-convection equations in a periodic domain modeling the flow and trans- port of
— We give a new proof for microlocal resolvent estimates for semi-classical Schr¨ odinger operators, extending the known results to potentials with local singularity and to
In Section 3, we construct a semi-graph with p-rank from a vertical fiber of a G-stable covering in a natural way and apply the results of Section 2 to prove Theorem 1.5 and
In our previous papers, we used the theorems in finite operator calculus to count the number of ballot paths avoiding a given pattern.. From the above example, we see that we have
