The search functionality is under construction.

The search functionality is under construction.

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.

- Publication
- IEICE TRANSACTIONS on Information Vol.E103-D No.11 pp.2278-2288

- Publication Date
- 2020/11/01

- Publicized
- 2020/08/06

- Online ISSN
- 1745-1361

- DOI
- 10.1587/transinf.2020EDP7102

- Type of Manuscript
- PAPER

- Category
- Data Engineering, Web Information Systems

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.

Copy

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

Copy

@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},}

Copy

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 -