TY  - JOUR
A1  - Birnick, Johann
A1  - Bläsius, Thomas
A1  - Friedrich, Tobias
A1  - Naumann, Felix
A1  - Papenbrock, Thorsten
A1  - Schirneck, Friedrich Martin
T1  - Hitting set enumeration with partial information for unique column combination discovery
T2  - Proceedings of the VLDB Endowment
N2  - Unique column combinations (UCCs) are a fundamental concept in relational databases. They identify entities in the data and support various data management activities. Still, UCCs are usually not explicitly defined and need to be discovered. State-of-the-art data profiling algorithms are able to efficiently discover UCCs in moderately sized datasets, but they tend to fail on large and, in particular, on wide datasets due to run time and memory limitations. <br /> In this paper, we introduce HPIValid, a novel UCC discovery algorithm that implements a faster and more resource-saving search strategy. HPIValid models the metadata discovery as a hitting set enumeration problem in hypergraphs. In this way, it combines efficient discovery techniques from data profiling research with the most recent theoretical insights into enumeration algorithms. Our evaluation shows that HPIValid is not only orders of magnitude faster than related work, it also has a much smaller memory footprint.
Y1  - 2020
UR  - https://publishup.uni-potsdam.de/frontdoor/index/index/docId/58772
SN  - 2150-8097
VL  - 13
IS  - 11
SP  - 2270
EP  - 2283
PB  - Association for Computing Machinery
CY  - [New York, NY]
ER  -