文献

J-GLOBAL ID：201102276300356112   整理番号：11A0119231

スキーママッピングにおける逆の構造

The Structure of Inverses in Schema Mappings

著者 (2件)： FAGIN Ronald (IBM Almaden Res. Center) ,  NASH Alan (IBM Almaden Res. Center)
資料名： Journal of the ACM (Association for Computing Machinery)  (Journal of the ACM (Association for Computing Machinery))
巻： 57  号： 6  ページ： 31:1-31:57  発行年： 2010年10月 
JST資料番号： C0267A  ISSN： 0004-5411  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： スキーママッピングは,あるスキーマ下のデータ構造を,異なるスキーマ下のデータ構造に変換する高水準仕様である。スキーママッピングは,M=(S,T,Σ)の3つ組みで定義される。Sはソーススキーマ,Tは目標スキーマ,Σは両者のインスタンス間の相関を記述するデータベース依存性の集合である。Faginは,s-t tgd(ソースから目標への3つ組み生成依存性)により記述される,実用上普通に生じるスキーママッピングに関連してその逆の観念を定義した。本論文は,Σが有限集合である場合のs-t tgdスキーママッピングについて未解決課題となっていた,可逆性の決定に要する計算量はcoNP完全であることを示した。また逆の構造,逆の一意性の条件,逆の逆が存在する条件,などの問題も考察した。完全s-t tgdにより記述されるスキーママッピングMに対し,もしMが逆を持てば,それは多項式サイズであり,生成する多項式時間アルゴリズムが存在することを示した。

シソーラス用語： 関係データベース ,  *データベーススキーマ ,  写像 ,  データ構造 ,  *データ変換 ,  相関 ,  依存性 ,  逆変換 ,  有限性 ,  計算量 ,  NP完全問題 ,  一意性 ,  存在性 ,  アルゴリズム ,  性質 ,  データベース管理システム ,  要求仕様 ,  可逆性
準シソーラス用語： 多項式時間アルゴリズム

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

タイトルに関連する用語 (1件)： スキーママッピング