文献

J-GLOBAL ID：200902285393795324   整理番号：08A0605714

XMLデータ交換: 一貫性および質問応答

XML Data Exchange: Consistency and Query Answering

著者 (2件)： ARENAS Marcelo (Pontificia Universidad Catolica de Chile, Santiago, CHL) ,  LIBKIN Leonid (Univ. Edinburgh, Edinburgh, GBR)
資料名： Journal of the ACM (Association for Computing Machinery)  (Journal of the ACM (Association for Computing Machinery))
巻： 55  号： 2  ページ： ARTICLE7,1-72  発行年： 2008年05月 
JST資料番号： C0267A  ISSN： 0004-5411  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： データ交換は,ソーススキーマのインスタンスと,ソースとターゲット間の関係の規定とを与えられて,ターゲットスキーマのインスタンスを見つけるという問題である。このようなターゲットインスタンスはターゲットスキーマにより課せられた制約の下でソースインスタンスからの情報を正しく表現しなければならず,また,ソースデータと意味的に一貫性ある方法でターゲットインスタンス上の質問を評価可能にしなければならない。データ交換の理論的基礎はリレーショナルデータに対しては研究されてきた。本稿では以下を目標とした。1)XMLデータ交換の状況に対する形式論を提案し,その基本的特性を調査する。2)XMLデータ交換の状況における質問応答の問題を検討し,その計算量を解析し,そして,質問評価アルゴリズムを開発する。まず,XMLデータ交換の基本的特性,すなわち,ターゲットDTDの下でソースDTDに適合するXML文書の再編成,および,ターゲットスキーマ上に書かれた質問への応答を調査した。そして,ソース・ツー・ターゲット依存関係がデータの階層的構造に関係するようなXMLデータ交換の状況を定義した。DTDと依存関係の結びつけは,あるXMLデータ交換の状況を非一貫的にすることがある。一貫性の問題を調査し,その厳密な計算量を決定した。次に,データ交換状況を,質問応答が扱いやすい状況と,質問応答がco-NP完全である状況とに,DTDで用いられている正規表現のクラスにしたがって,分類する二分法定理を証明した。さらに,すべての扱いやすいケースに対して,質問が応答されうるようなターゲットXML文書を計算する多項式時間アルゴリズムを与えた。

シソーラス用語： *データ変換 ,  *XML【マークアップ言語】 ,  文書 ,  一貫性 ,  コンシステンシー【計算機】 ,  形式的手法【計算機】 ,  *質問処理 ,  計算量 ,  階層構造 ,  ツリー構造 ,  *データベース管理システム ,  データ転送 ,  データベーススキーマ ,  データベース
準シソーラス用語： XML文書 ,  *データ交換【データベース】

分類 (1件)： データベースシステム  (JD03030U)

タイトルに関連する用語 (2件)： XMLデータ ,  質問応答