Hitting set enumeration with partial information for unique column combination discovery
- 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.
Verfasserangaben: | Johann Birnick, Thomas BläsiusGND, Tobias FriedrichORCiDGND, Felix NaumannORCiDGND, Thorsten PapenbrockORCiDGND, Friedrich Martin SchirneckORCiDGND |
---|---|
DOI: | https://doi.org/10.14778/3407790.3407824 |
ISSN: | 2150-8097 |
Titel des übergeordneten Werks (Englisch): | Proceedings of the VLDB Endowment |
Verlag: | Association for Computing Machinery |
Verlagsort: | [New York, NY] |
Publikationstyp: | Wissenschaftlicher Artikel |
Sprache: | Englisch |
Datum der Erstveröffentlichung: | 01.07.2020 |
Erscheinungsjahr: | 2020 |
Datum der Freischaltung: | 19.04.2023 |
Band: | 13 |
Ausgabe: | 11 |
Seitenanzahl: | 14 |
Erste Seite: | 2270 |
Letzte Seite: | 2283 |
Organisationseinheiten: | An-Institute / Hasso-Plattner-Institut für Digital Engineering gGmbH |
DDC-Klassifikation: | 0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 000 Informatik, Informationswissenschaft, allgemeine Werke |
Peer Review: | Referiert |
Lizenz (Deutsch): | CC-BY-NC-ND - Namensnennung, nicht kommerziell, keine Bearbeitungen 4.0 International |