Edinburgh Research Explorer

Detecting Inconsistencies in Distributed Data

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

Related Edinburgh Organisations

Documents

Original languageEnglish
Title of host publication26TH INTERNATIONAL CONFERENCE ON DATA ENGINEERING ICDE 2010
EditorsF Li
Place of PublicationLOS ALAMITOS
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Pages64-75
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

Conference

Conference26th IEEE International Conference on Data Engineering (ICDE 2010)
CityLong Beach
Period1/03/106/03/10

Abstract

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.

Event

26th IEEE International Conference on Data Engineering (ICDE 2010)

1/03/106/03/10

Long Beach

Event: Conference

Download statistics

No data available

ID: 3169368