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

• Item type: Trans(1)
• 公開日: 2005-12-15
• タイトル: インクリメンタルに更新可能なXPushマシン
• タイトル / 言語: en
• タイトル: An Incrementally Updatable XPush Machine
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 事例・実践論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 職業能力開発総合大学校情報工学科
• 著者所属: 首都大学東京システムデザイン学部 東京都立大学大学院工学研究科
• 著者所属: 首都大学東京システムデザイン学部 東京都立大学大学院工学研究科
• 著者所属(英): en
• 著者所属(英): Department of Information and Computer Science Polytechnic University
• 著者所属(英): en
• 著者所属(英): Faculty of System Design Tokyo Metropolitan University,Graduate School of Engineering Tokyo Metropolitan University
• 著者所属(英): en
• 著者所属(英): Faculty of System Design Tokyo Metropolitan University,Graduate School of Engineering Tokyo Metropolitan University
• 著者名: 武川, 肇; 片山, 薫; 石川, 博
• 著者名(英): Hajime, Takekawa; Kaoru, Katayama; Hiroshi, Ishikawa
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: コンテンツベースに処理するXML システムはフィルタ条件をXML データごとに数多く評価する必要がある．そのためGupta らは複数のフィルタをボトムアップに結合し，フィルタ条件の数に影響を受けないオートマトン，XPush マシンを提案した．しかしXPush マシンは更新ができない．そのため1 つのフィルタを削除することであってもXPush マシン全体の再計算が必要となる．初期状態の非決定性有限オートマトンに戻ったXPush マシンは決定性有限オートマトンへの変換を実行する際に時間がかかるため，システムのスループットを低下させる．この問題を解決するために，問合せごとに構築したサブXPush マシンの集合から全体のオートマトンを構築する方式を提案する．Gupta らの方式はXPath 用に拡張したAFA（Alternating Finite Automaton）からXPush 状態を見つけ出す．一方，本方式はこのXPush 状態にキーを追加し，XPush 状態を結合することができる．また，サブXPush マシン単位の分割管理構造では，このキーを用いて状態間に世代関係を表現できる．本方式ではこの関係を使ってインクリメンタルな更新が可能となる．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464847
• 書誌情報: 情報処理学会論文誌データベース（TOD）; 巻 46, 号 SIG18(TOD28), p. 116-128, 発行日 2005-12-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7799
• 出版者 / 言語: ja
• 出版者: 情報処理学会