@techreport{TD:101576,
	att_abstract={{Functional dependencies (FDs) have recently been extended for data quality purposes with various notions of similarity instead of strict equality. We study these extensions in this paper. We begin by constructing a hierarchy of dependencies, showing which dependencies generalize others. We then focus on an extension of FDs that we call Antecedent Metric Functional Dependencies (AMFDs). An AMFD asserts that if two tuples have similar but not necessarily equal values of the antecedent attributes, then their consequent values must be equal. We present a theoretical foundation for AMFDs, including a sound and complete axiomatization as well as an inference algorithm. We compare the axiomatization of AMFDs to those of the other dependencies, and we show that while the complexity of inference for some FD extensions is quadratic or even co-NP complete, the inference problem for AMFDs remains linear, as in traditional FDs. We implemented our inference procedure and experimentally verified its efficiency.}},
	att_authors={ds8961},
	att_categories={C_NSS.2, C_IIS.6},
	att_copyright={{}},
	att_copyright_notice={{}},
	att_donotupload={},
	att_private={false},
	att_projects={},
	att_tags={},
	att_techdoc={true},
	att_techdoc_key={TD:101576},
	att_url={http://web1.research.att.com:81/techdocs_downloads/TD:101576_DS1_2015-02-17T23:05:57.770Z.pdf},
	author={Divesh Srivastava and Jaroslaw Szlichta and Lukasz Golab},
	institution={{Alberto Mendelzon International Workshop on Foundations of Data Management}},
	month={May},
	title={{On Axiomatization and Inference Complexity over a Hierarchy of Functional Dependencies}},
	year=2015,
}