Edinburgh Research Explorer

Incremental Detection of Inconsistencies in Distributed Data

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Related Edinburgh Organisations

Documents

http://dx.doi.org/10.1109/ICDE.2012.82
Original languageEnglish
Title of host publicationIEEE 28th International Conference on Data Engineering (ICDE 2012), Washington, DC, USA (Arlington, Virginia), 1-5 April, 2012
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Pages318-329
Number of pages12
ISBN (Print)978-1-4673-0042-1
DOIs
Publication statusPublished - 2012

Abstract

This paper investigates the problem of incremental detection of errors in distributed data. Given a distributed database D, a set Sigma of conditional functional dependencies (CFDs), the set V of violations of the CFDs in D, and updates Delta D to D, it is to find, with minimum data shipment, changes Delta V to V in response to Delta D. The need for the study is evident since real-life data is often dirty, distributed and is frequently updated. It is often prohibitively expensive to recompute the entire set of violations when D is updated. We show that the incremental detection problem is NP-complete for D partitioned either vertically or horizontally, even when Sigma and D are fixed. Nevertheless, we show that it is bounded and better still, actually optimal: there exist algorithms to detect errors such that their computational cost and data shipment are both linear in the size of Delta D and Delta V, independent of the size of the database D. We provide such incremental algorithms for vertically partitioned data, and show that the algorithms are optimal. We further propose optimization techniques for the incremental algorithm over vertical partitions to reduce data shipment. We verify experimentally, using real-life data on Amazon Elastic Compute Cloud (EC2), that our algorithms substantially outperform their batch counterparts even when Delta V is reasonably large.

Download statistics

No data available

ID: 17627458