Colección SciELO Chile

Departamento Gestión de Conocimiento, Monitoreo y Prospección
Consultas o comentarios: productividad@anid.cl
Búsqueda Publicación
Búsqueda por Tema Título, Abstract y Keywords



Extending inclusion dependencies with conditions
Indexado
WoS WOS:000330913500004
Scopus SCOPUS_ID:84890119754
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


Abstract



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.

Métricas Externas



PlumX Altmetric Dimensions

Muestra métricas de impacto externas asociadas a la publicación. Para mayor detalle:

Disciplinas de Investigación



WOS
Computer Science, Theory & Methods
Scopus
Computer Science (All)
Theoretical Computer Science
SciELO
Sin Disciplinas

Muestra la distribución de disciplinas para esta publicación.

Publicaciones WoS (Ediciones: ISSHP, ISTP, AHCI, SSCI, SCI), Scopus, SciELO Chile.

Colaboración Institucional



Muestra la distribución de colaboración, tanto nacional como extranjera, generada en esta publicación.


Autores - Afiliación



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

Muestra la afiliación y género (detectado) para los co-autores de la publicación.

Financiamiento



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

Muestra la fuente de financiamiento declarada en la publicación.

Agradecimientos



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

Muestra la fuente de financiamiento declarada en la publicación.