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
Este artigo discute um problema de análise estática, denominado problema de consistência absoluta, para mapeamentos de esquemas relacionais. Um determinado mapeamento de esquema é considerado absolutamente consistente se cada instância de origem tiver uma instância de destino correspondente. A consistência absoluta é uma propriedade importante porque garante que a troca de dados nunca falhe para qualquer instância de origem. Originalmente, para mapeamentos de esquemas XML, o problema de consistência absoluta foi definido e sua complexidade foi investigada por Amano et al. No entanto, até onde os autores sabem, não há resultados conhecidos para mapeamentos de esquemas relacionais. Neste artigo, nos concentramos em mapeamentos de esquemas relacionais de modo que tanto o esquema de origem quanto o de destino tenham dependências funcionais, sob a suposição de que as regras de mapeamento são definidas por dependências geradoras de tuplas livres de constantes. Neste cenário, mostramos que o problema de consistência absoluta está em coNP. Mostramos também que é solucionável em tempo polinomial se as dependências geradoras de tuplas estiverem cheias e o tamanho do lado esquerdo de cada dependência funcional for limitado por alguma constante. Finalmente, mostramos que o problema de consistência absoluta é difícil para coNP mesmo se o esquema de origem não tiver nenhuma dependência funcional e o esquema de destino tiver apenas uma; ou cada um dos esquemas de origem e de destino tem apenas uma dependência funcional, de modo que o tamanho do lado esquerdo da dependência funcional seja no máximo dois.
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.
Copiar
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
Copiar
@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},}
Copiar
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 -