文献

J-GLOBAL ID：202102237617406795   整理番号：21A0132148

関数依存性を持つリレーショナルスキーママッピングの絶対一貫性問題

The Absolute Consistency Problem for Relational Schema Mappings with Functional Dependencies

著者 (3件)： ISHIHARA Yasunori (Nanzan University) ,  HAYATA Takashi (Osaka University) ,  FUJIWARA Toru (Osaka University)
資料名： IEICE Transactions on Information and Systems (Web)  (IEICE Transactions on Information and Systems (Web))
巻： E103.D  号： 11  ページ： 2278-2288(J-STAGE)  発行年： 2020年 
JST資料番号： U0469A  ISSN： 1745-1361  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： 本論文では,リレーショナルスキーママッピングのための絶対一貫性問題と呼ばれる静的解析問題について議論した。与えられたスキーママッピングは,すべてのソースインスタンスが対応するターゲットインスタンスを持つ場合,絶対一貫性があると言われている。絶対一貫性は,任意のソースインスタンスに対するデータ交換が失敗しないことを保証するため,重要な特性である。もともと,XMLスキーママッピングのために,天野らによって絶対一貫性問題が定義され,その複雑さが検討された。しかし,筆者らの知る限り,リレーショナルスキーママッピングの既知の結果がない。本論文では,マッピングルールが,定数フリーのタップル生成依存性によって定義されるという仮定の下で,ソーススキーマとターゲットスキーマの両方が関数依存性を持つようなリレーショナルスキーママッピングに焦点を当てた。この設定では,筆者らは,絶対一貫性問題がcoNPにあることを示した。また,筆者らは,タップル生成依存性が完全であり,各関数依存性の左辺のサイズがある定数で制限されている場合,多項式時間で解けることも示した。最後に,ソーススキーマが関数依存性を持たず,ターゲットスキーマが1つの関数依存性しか持たない場合,あるいは,ソーススキーマとターゲットスキーマのそれぞれが関数依存性の左辺のサイズが最大でも2であるような,関数依存性を1つだけ持つ場合,絶対一貫性問題はcoNP困難であることを示した。(翻訳著者抄録)

シソーラス用語： *写像 ,  データ構造 ,  *関数従属 ,  *一貫性 ,  情報交換 ,  プログラム解析 ,  計算理論 ,  時間 ,  NP困難
準シソーラス用語： XMLスキーマ ,  *スキーママッピング ,  データ交換 ,  *関数依存性 ,  静的解析 ,  多項式時間

著者キーワード (4件)： データ交換 ,  関係スキーママッピング ,  絶対一貫性 ,  機能依存性

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

引用文献 (23件)：

• [1] T. Hayata, Y. Ishihara, and T. Fujiwara, “The absolute consistency problem of graph schema mappings with uniqueness constraints,” Proc. 9th Int. Conf. Advances in Databases, Knowledge, and Data Applications, pp.103-110, 2017.
• [2] G. Karvounarakis, T.J. Green, Z.G. Ives, and V. Tannen, “Collaborative data sharing via update exchange and provenance,” ACM Trans. Database Systems, vol.38, no.3, pp.1-42, 2013. 10.1145/2500127
• [3] M. Arenas and L. Libkin, “XML data exchange: Consistency and query answering,” J. ACM, vol.55, no.2, pp.1-72, 2008. 10.1145/1346330.1346332
• [4] S. Amano, L. Libkin, and F. Murlak, “XML schema mappings,” Proc. Twenty-Eigth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, pp.33-42, 2009. 10.1145/1559795.1559801
• [5] M. Bojańczyk, L.A. Kołodziejczyk, and F. Murlak, “Solutions in XML data exchange,” Proc. 14th Int. Conf. Database Theory, pp.102-113, 2011. 10.1145/1938551.1938567

タイトルに関連する用語 (2件)： 関数依存性 ,  スキーママッピング