The chase is a well-known algorithm with a wide range ofapplications in data exchange, data cleaning, data integration, query optimization, and ontological reasoning. Sincethe chase evaluation might not terminate and it is undecidable whether it terminates, the problem of defining (decidable) sufficient conditions ensuring termination has receiveda great deal of interest in recent years. In this regard, severaltermination criteria have been proposed. One of the mainweaknesses of current approaches is the limited analysis theyperform onequality generating dependencies(EGDs).In this paper, we propose sufficient conditions ensuringthat a set of dependencies has at least one terminating chasesequence. We propose novel criteria which are able to perform a more accurate analysis of EGDs. Specifically, wepropose a new stratification criterion and an adornment algorithm. The latter can both be used as a termination criterion and be combined with current techniques to make themmore effective, in that strictly more sets of dependencies areidentified. Our techniques identify sets of dependencies thatare not recognized by any of the current criteria.

Exploiting Equality Generating Dependencies in Checking Chase Termination / Calautti, Marco; Greco, Sergio; Molinaro, Cristian; Trubitsyna, Irina. - In: PROCEEDINGS OF THE VLDB ENDOWMENT. - ISSN 2150-8097. - 9:5(2016), pp. 396-407. [10.14778/2876473.2876475]

Exploiting Equality Generating Dependencies in Checking Chase Termination

Marco Calautti;
2016-01-01

Abstract

The chase is a well-known algorithm with a wide range ofapplications in data exchange, data cleaning, data integration, query optimization, and ontological reasoning. Sincethe chase evaluation might not terminate and it is undecidable whether it terminates, the problem of defining (decidable) sufficient conditions ensuring termination has receiveda great deal of interest in recent years. In this regard, severaltermination criteria have been proposed. One of the mainweaknesses of current approaches is the limited analysis theyperform onequality generating dependencies(EGDs).In this paper, we propose sufficient conditions ensuringthat a set of dependencies has at least one terminating chasesequence. We propose novel criteria which are able to perform a more accurate analysis of EGDs. Specifically, wepropose a new stratification criterion and an adornment algorithm. The latter can both be used as a termination criterion and be combined with current techniques to make themmore effective, in that strictly more sets of dependencies areidentified. Our techniques identify sets of dependencies thatare not recognized by any of the current criteria.
2016
5
Calautti, Marco; Greco, Sergio; Molinaro, Cristian; Trubitsyna, Irina
Exploiting Equality Generating Dependencies in Checking Chase Termination / Calautti, Marco; Greco, Sergio; Molinaro, Cristian; Trubitsyna, Irina. - In: PROCEEDINGS OF THE VLDB ENDOWMENT. - ISSN 2150-8097. - 9:5(2016), pp. 396-407. [10.14778/2876473.2876475]
File in questo prodotto:
File Dimensione Formato  
p396-calautti.pdf

accesso aperto

Tipologia: Versione editoriale (Publisher’s layout)
Licenza: Creative commons
Dimensione 480.74 kB
Formato Adobe PDF
480.74 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11572/260183
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 22
  • ???jsp.display-item.citation.isi??? 12
social impact