On Concise Set of Relative Candidate Keys

Matching keys, specifying what attributes to compare and how to compare them for identifying the same real-world entities, are found to be useful in applications like record matching, blocking and windowing [7]. Owing to the com-plex redundant semantics among matching keys, capturing a proper set of matching keys is highly non-trivial. Anal-ogous to minimal/candidate keys w.r.t. functional depen-dencies, relative candidate keys (rcks [7], with a minimal number of compared attributes, see a more formal definition in Section 2) can clear up redundant semantics w.r.t. “what attributes to compare”. However, we note that redundancy issues may still exist among rcks on the same attributes about “how to compare them”. In this paper, we propose to find a concise set of matching keys, which has less redun-dancy and can still meet the requirements on coverage and validity. Specifically, we study approximation algorithms to efficiently discover a near optimal set. To ensure the quality of matching keys, the returned results are guaranteed to be rcks (minimal on compared attributes), and most impor-tantly, minimal w.r.t. distance restrictions (i.e., redundancy free w.r.t. “how to compare the attributes”). The exper-imental evaluation demonstrates that our concise rck set is more effective than the existing rck choosing method. Moreover, the proposed pruning methods show up to 2 or-ders of magnitude improvement w.r.t. time costs on concise rck set discovery. 1