インクリメンタルに更新可能なXPushマシン

情報処理学会 Web Site Web Site Web Site 被引用文献3件 参考文献25件

書誌事項

タイトル別名
  • インクリメンタル ニ コウシン カノウ ナ XPush マシン
  • An Incrementally Updatable XPush Machine

この論文をさがす

抄録

コンテンツベースに処理するXML システムはフィルタ条件をXML データごとに数多く評価する必要がある．そのためGupta らは複数のフィルタをボトムアップに結合し，フィルタ条件の数に影響を受けないオートマトン，XPush マシンを提案した．しかしXPush マシンは更新ができない．そのため1 つのフィルタを削除することであってもXPush マシン全体の再計算が必要となる．初期状態の非決定性有限オートマトンに戻ったXPush マシンは決定性有限オートマトンへの変換を実行する際に時間がかかるため，システムのスループットを低下させる．この問題を解決するために，問合せごとに構築したサブXPush マシンの集合から全体のオートマトンを構築する方式を提案する．Gupta らの方式はXPath 用に拡張したAFA（Alternating Finite Automaton）からXPush 状態を見つけ出す．一方，本方式はこのXPush 状態にキーを追加し，XPush 状態を結合することができる．また，サブXPush マシン単位の分割管理構造では，このキーを用いて状態間に世代関係を表現できる．本方式ではこの関係を使ってインクリメンタルな更新が可能となる．

Content-based XML processing systems need to evaluate many filter conditions for every XML data. Therefore, Gupta et. al. proposed the automaton called XPush machine which is independent of the number of filter conditions by combining two or more filters in a bottom up fashion. However, an updating of the XPush machine is impossible. Therefore, even if it is deleting only one filter, the re-calculation of the whole XPush machine is necessary. The XPush machine which returned to an NFA (Non-deterministic Finite Automaton) of an initial state decreases the throughput of the system because of translation to a DFA (Deterministic Finite Automaton). In order to solve this problem, we proposed a method which constructs the whole automaton from a set of sub-XPush machines for each query. Gupta et. al. ’s method creates joint states from a set of extended AFAs (Alternating Finite Automaton) for XPath. On the other hand, we realize a further join function to combine two XPush states by a supplementary key for each state. Moreover, in the divided management structure of sub-XPush machines, generation relationships between states can be represented by these keys. We realize incremental updating further by these relationships.

収録刊行物

被引用文献 (3)*注記

もっと見る

参考文献 (25)*注記

もっと見る

関連プロジェクト

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ