Analysis of Candidate Keys in Relational Databases

Discovery algorithms in data profiling return an effective representation of all constraints from a given class, such as uniqueness constraints, that hold on the given dataset. Most of the results, however, do not express meaningful business rules but simply hold incidentally. Incomplete and inconsistent data makes the identification of business rules even harder, leading to approximate algorithms with huge computational complexity and few meaningful constraints among many incidental ones. Research is missing a methodology for analyzing the output of discovery algorithms. In response, we propose a framework for identifying and analyzing candidate keys in relational databases with incomplete or inconsistent data. The approach leverages uniqueness and completeness ratios, threshold-based key filtering, and counter-example analysis to identify meaningful keys, and incorporates specialization techniques and pruning strategies to ensure minimality and efficiency. Experiments demonstrate that key analysis improves F1 measures from state-of-the-art key mining between 36-99%, highlighting the necessity of humans-in-the-loop for decision making. Our pruning strategies yield up to 60% reduction in runtime for key analysis, lowering computational overheads while maintaining result quality.