Detecting Inconsistencies in Distributed Data

Wenfei Fan, Floris Geerts, Shuai Ma, Heiko Mueller

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

Abstract / Description of output

One of the central problems for data quality is inconsistency detection. Given a database D and a set Sigma of dependencies as data quality rules, we want to identify tuples in D that violate some rules in Sigma. When D is a centralized database, there have been effective SQL-based techniques for finding violations. It is, however, far more challenging when data in D is distributed, in which inconsistency detection often necessarily requires shipping data from one site to another.

This paper develops techniques for detecting violations of conditional functional dependencies (CFDs) in relations that are fragmented and distributed across different sites. (1) We formulate the detection problem in various distributed settings as optimization problems, measured by either network traffic or response time. (2) We show that it is beyond reach in practice to find optimal detection methods: the detection problem is NP-complete when the data is partitioned either horizontally or vertically, and when we aim to minimize either data shipment or response time. (3) For data that is horizontally partitioned, we provide several algorithms to find violations of a set of CFDs, leveraging the structure of CFDs to reduce data shipment or increase parallelism. (4) We verify experimentally that our algorithms are scalable on large relations and complex CFDs. (5) For data that is vertically partitioned, we provide a characterization for CFDs to be checked locally without requiring data shipment, in terms of dependency preservation. We show that it is intractable to minimally refine a partition and make it dependency preserving.

Original languageEnglish
EditorsF Li
Place of PublicationLOS ALAMITOS
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Number of pages12
ISBN (Print)978-1-4244-5444-0
Publication statusPublished - 2010
Event26th IEEE International Conference on Data Engineering (ICDE 2010) - Long Beach
Duration: 1 Mar 20106 Mar 2010


Conference26th IEEE International Conference on Data Engineering (ICDE 2010)
CityLong Beach


Dive into the research topics of 'Detecting Inconsistencies in Distributed Data'. Together they form a unique fingerprint.

Cite this