Metric Functional Dependencies

Authors:
  • NKNick Koudas
    Nick Koudas
  • ASAvishek Saha
    Avishek Saha
  • DSDivesh Srivastava
    Divesh Srivastava
  • SVSuresh Venkatasubramanian
    Suresh Venkatasubramanian

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.

This publication has 12 references indexed in Scilit: