Name
Abstract | ||
|---|---|---|
The aim of this paper is to present more general criteria and techniques for chase termination. We first present extensions of the well-known stratification criterion and introduce a new criterion, called local stratification, which generalizes both super-weak acyclicity and stratification-based criteria (including the class of constraints which are inductively restricted). Next, the paper presents a rewriting algorithm transforming the original set of constraints Σ into an “equivalent” set Σα and verifying the structural properties for chase termination on Σα. The rewriting of constraints allows us to recognize larger classes of constraints for which chase termination is guaranteed. In particular, we show that if Σ satisfies chase termination conditions T, then the rewritten set Σα satisfies T as well, but the vice versa is not true, that is there are significant classes of constraints for which Σα satisfies T and Σ does not. A more general rewriting algorithm producing as output an equivalent set of dependencies and a Boolean value stating whether a sort of cyclicity has been detected is also proposed. The new rewriting technique and the checking of acyclicity allow us to introduce the class of acyclic constraints, which generalizes local stratification and guarantees that all chase sequences are finite with a length polynomial in the size of the input database. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1109/TKDE.2014.2339816 | Knowledge and Data Engineering, IEEE Transactions |
Keywords | Field | DocType |
boolean functions,rewriting systems,boolean value,chase termination,cyclicity analysis,general rewriting algorithm,local stratification,data exchange,chase algorithm,data integration,null value,polynomials,algorithm design and analysis,databases | Boolean function,Discrete mathematics,Algorithm design,Polynomial,sort,Rewriting,Sigma,Boolean data type,Null (SQL),Mathematics | Journal |
Volume | Issue | ISSN |
27 | 3 | 1041-4347 |
Citations | PageRank | References |
5 | 0.41 | 26 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sergio Greco | 1 | 1249 | 265.35 |
| Francesca Spezzano | 2 | 80 | 19.08 |
| Irina Trubitsyna | 3 | 119 | 24.66 |