The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Cet article traite d'un problème d'analyse statique, appelé problème de cohérence absolue, pour les mappages de schémas relationnels. Un mappage de schéma donné est dit absolument cohérent si chaque instance source a une instance cible correspondante. La cohérence absolue est une propriété importante car elle garantit que l'échange de données n'échoue jamais pour aucune instance source. À l'origine, pour les mappages de schémas XML, le problème de cohérence absolue a été défini et sa complexité a été étudiée par Amano et al. Cependant, à la connaissance des auteurs, il n’existe aucun résultat connu concernant les mappages de schémas relationnels. Dans cet article, nous nous concentrons sur les mappages de schémas relationnels tels que les schémas source et cible ont des dépendances fonctionnelles, en supposant que les règles de mappage sont définies par des dépendances génératrices de tuples libres et constantes. Dans ce cadre, nous montrons que le problème de cohérence absolue est dans coNP. Nous montrons également qu'il est résoluble en temps polynomial si les dépendances génératrices de tuples sont pleines et que la taille du côté gauche de chaque dépendance fonctionnelle est limitée par une constante. Enfin, nous montrons que le problème de cohérence absolue est coNP-difficile même si le schéma source n’a aucune dépendance fonctionnelle et que le schéma cible n’en a qu’une ; ou chacun des schémas source et cible n'a qu'une seule dépendance fonctionnelle de telle sorte que la taille du côté gauche de la dépendance fonctionnelle soit d'au plus deux.
Yasunori ISHIHARA
Nanzan University
Takashi HAYATA
Osaka University
Toru FUJIWARA
Osaka University
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copier
Yasunori ISHIHARA, Takashi HAYATA, Toru FUJIWARA, "The Absolute Consistency Problem for Relational Schema Mappings with Functional Dependencies" in IEICE TRANSACTIONS on Information,
vol. E103-D, no. 11, pp. 2278-2288, November 2020, doi: 10.1587/transinf.2020EDP7102.
Abstract: This paper discusses a static analysis problem, called absolute consistency problem, for relational schema mappings. A given schema mapping is said to be absolutely consistent if every source instance has a corresponding target instance. Absolute consistency is an important property because it guarantees that data exchange never fails for any source instance. Originally, for XML schema mappings, the absolute consistency problem was defined and its complexity was investigated by Amano et al. However, as far as the authors know, there are no known results for relational schema mappings. In this paper, we focus on relational schema mappings such that both the source and the target schemas have functional dependencies, under the assumption that mapping rules are defined by constant-free tuple-generating dependencies. In this setting, we show that the absolute consistency problem is in coNP. We also show that it is solvable in polynomial time if the tuple-generating dependencies are full and the size of the left-hand side of each functional dependency is bounded by some constant. Finally, we show that the absolute consistency problem is coNP-hard even if the source schema has no functional dependency and the target schema has only one; or each of the source and the target schemas has only one functional dependency such that the size of the left-hand side of the functional dependency is at most two.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2020EDP7102/_p
Copier
@ARTICLE{e103-d_11_2278,
author={Yasunori ISHIHARA, Takashi HAYATA, Toru FUJIWARA, },
journal={IEICE TRANSACTIONS on Information},
title={The Absolute Consistency Problem for Relational Schema Mappings with Functional Dependencies},
year={2020},
volume={E103-D},
number={11},
pages={2278-2288},
abstract={This paper discusses a static analysis problem, called absolute consistency problem, for relational schema mappings. A given schema mapping is said to be absolutely consistent if every source instance has a corresponding target instance. Absolute consistency is an important property because it guarantees that data exchange never fails for any source instance. Originally, for XML schema mappings, the absolute consistency problem was defined and its complexity was investigated by Amano et al. However, as far as the authors know, there are no known results for relational schema mappings. In this paper, we focus on relational schema mappings such that both the source and the target schemas have functional dependencies, under the assumption that mapping rules are defined by constant-free tuple-generating dependencies. In this setting, we show that the absolute consistency problem is in coNP. We also show that it is solvable in polynomial time if the tuple-generating dependencies are full and the size of the left-hand side of each functional dependency is bounded by some constant. Finally, we show that the absolute consistency problem is coNP-hard even if the source schema has no functional dependency and the target schema has only one; or each of the source and the target schemas has only one functional dependency such that the size of the left-hand side of the functional dependency is at most two.},
keywords={},
doi={10.1587/transinf.2020EDP7102},
ISSN={1745-1361},
month={November},}
Copier
TY - JOUR
TI - The Absolute Consistency Problem for Relational Schema Mappings with Functional Dependencies
T2 - IEICE TRANSACTIONS on Information
SP - 2278
EP - 2288
AU - Yasunori ISHIHARA
AU - Takashi HAYATA
AU - Toru FUJIWARA
PY - 2020
DO - 10.1587/transinf.2020EDP7102
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E103-D
IS - 11
JA - IEICE TRANSACTIONS on Information
Y1 - November 2020
AB - This paper discusses a static analysis problem, called absolute consistency problem, for relational schema mappings. A given schema mapping is said to be absolutely consistent if every source instance has a corresponding target instance. Absolute consistency is an important property because it guarantees that data exchange never fails for any source instance. Originally, for XML schema mappings, the absolute consistency problem was defined and its complexity was investigated by Amano et al. However, as far as the authors know, there are no known results for relational schema mappings. In this paper, we focus on relational schema mappings such that both the source and the target schemas have functional dependencies, under the assumption that mapping rules are defined by constant-free tuple-generating dependencies. In this setting, we show that the absolute consistency problem is in coNP. We also show that it is solvable in polynomial time if the tuple-generating dependencies are full and the size of the left-hand side of each functional dependency is bounded by some constant. Finally, we show that the absolute consistency problem is coNP-hard even if the source schema has no functional dependency and the target schema has only one; or each of the source and the target schemas has only one functional dependency such that the size of the left-hand side of the functional dependency is at most two.
ER -