Muestra métricas de impacto externas asociadas a la publicación. Para mayor detalle:
| Indexado |
|
||||
| DOI | 10.1016/J.TCS.2013.11.002 | ||||
| Año | 2014 | ||||
| Tipo | artículo de investigación |
Citas Totales
Autores Afiliación Chile
Instituciones Chile
% Participación
Internacional
Autores
Afiliación Extranjera
Instituciones
Extranjeras
This paper introduces a class of conditional inclusion dependencies (CINDs), which extends inclusion dependencies (INDs) by enforcing patterns of semantically related data values. We show that CINDs are useful not only in data cleaning, but also in contextual schema matching. We give a full treatment of the static analysis of CINDs, and show that CINDs retain most desired properties of traditional INDs: (a) CINDs are always satisfiable; (b) CINDs are finitely axiomatizable, i.e., there exists a sound and complete inference system for the implication analysis of CINDs; and (c) the implication problem for CINDs has the same complexity as its traditional counterpart, namely, PSPACE-complete, in the absence of attributes with a finite domain; but it is EXPTIME-complete in the general setting. In addition, we investigate the interaction between CINDs and conditional functional dependencies (CFDs), as well as two practical fragments of CINDs, namely acyclic CINDs and unary CINDs. We show the following: (d) the satisfiability problem for the combination of CINDs and CFDs becomes undecidable, even in the absence of finite-domain attributes; (e) in the absence of finite-domain attributes, the implication problem for acyclic CINDs and for unary CINDs retains the same complexity as its traditional counterpart, namely, NP-complete and PTIME, respectively; but in the general setting, it becomes PSPACE-complete and coNP-complete, respectively; and (f) the implication problem for acyclic unary CINDs remains in PTIME in the absence of finite-domain attributes and coNP-complete in the general setting. (C) 2013 Elsevier B.V. All rights reserved.
| Ord. | Autor | Género | Institución - País |
|---|---|---|---|
| 1 | Ma, Shuai | - |
Beihang Univ - China
Beihang University - China |
| 2 | Fan, Wenfei | - |
Beihang Univ - China
UNIV EDINBURGH - Reino Unido Beihang University - China University of Edinburgh - Reino Unido The University of Edinburgh - Reino Unido |
| 3 | BRAVO-CELEDON, MARIA LORETO | Mujer |
Universidad de Concepción - Chile
|
| Fuente |
|---|
| National Natural Science Foundation of China |
| Ministry of Science and Technology of the People's Republic of China |
| EPSRC |
| Engineering and Physical Sciences Research Council |
| Guangdong Innovative and Entrepreneurial Research Team Program |
| NSFC 61133002 |
| Agradecimiento |
|---|
| Ma is supported in part by NSFC grant 61322207 , NGFR 973 grant 2014CB340304 and MOST grant 2012BAH46B04 . Fan is supported in part by 973 Programs 2012CB316200 and 2014CB340302 , NSFC 61133002 , Guangdong Innovative Research Team Program 2011D005 and Shenzhen Peacock Program 1105100030834361 of China, as well as EPSRC EP/J015377/1 , UK. Appendix A |