Metric Functional Dependencies
Authors:
- Nick KoudasNKNick Koudas
- Avishek SahaASAvishek Saha
- Divesh SrivastavaDSDivesh Srivastava
- Suresh VenkatasubramanianSVSuresh Venkatasubramanian
- 1 March 2009
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE) in International Conference on Data Engineering
- No. 10636382,p. 1275-1278
Abstract
When merging data from various sources, it is often the case that small variations in data format and interpretation cause traditional functional dependencies (FDs) to be violated, without there being an intrinsic violation of semantics. Examples include differing address formats, or different reported latitude/longitudes for a given address. In this paper, we define metric functional dependencies, which strictly generalize traditional FDs by allowing small differences (controlled by a metric) in values of the consequent attribute of an FD. We present efficient algorithms for the verification problem: determining whether a given metric FD holds for a given relation. We experimentally demonstrate the validity and efficiency of our approach on various data sets that lie in multidimensional spaces.Keywords
This publication has 12 references indexed in Scilit:
- Dependencies revisited for improving data quality2008
- First-order query rewriting for inconsistent databasesJournal of Computer and System Sciences, 2007
- Conditional Functional Dependencies for Data Cleaning2007
- Approximating extent measures of pointsJournal of the ACM, 2004
- Practical methods for shape fitting and kinetic data structures using core sets2004
- An Axiomatic Approach to Defining Approximation Measures for Functional Dependencies2002
- Deterministic algorithms for 3-D diameter and some 2-D lower envelopes2000
- Sublinear time algorithms for metric space problems1999
- The quickhull algorithm for convex hullsACM Transactions on Mathematical Software, 1996
- Approximate inference of functional dependencies from relationsTheoretical Computer Science, 1995