Advancing the discovery of unique column combinations

  • Unique column combinations of a relational database table are sets of columns that contain only unique values. Discovering such combinations is a fundamental research problem and has many different data management and knowledge discovery applications. Existing discovery algorithms are either brute force or have a high memory load and can thus be applied only to small datasets or samples. In this paper, the wellknown GORDIAN algorithm and "Apriori-based" algorithms are compared and analyzed for further optimization. We greatly improve the Apriori algorithms through efficient candidate generation and statistics-based pruning methods. A hybrid solution HCAGORDIAN combines the advantages of GORDIAN and our new algorithm HCA, and it significantly outperforms all previous work in many situations.
  • Unique-Spaltenkombinationen sind Spaltenkombinationen einer Datenbanktabelle, die nur einzigartige Werte beinhalten. Das Finden von Unique-Spaltenkombinationen spielt sowohl eine wichtige Rolle im Bereich der Grundlagenforschung von Informationssystemen als auch in Anwendungsgebieten wie dem Datenmanagement und der Erkenntnisgewinnung aus Datenbeständen. Vorhandene Algorithmen, die dieses Problem angehen, sind entweder Brute-Force oder benötigen zu viel Hauptspeicher. Deshalb können diese Algorithmen nur auf kleine Datenmengen angewendet werden. In dieser Arbeit werden der bekannte GORDIAN-Algorithmus und Apriori-basierte Algorithmen zum Zwecke weiterer Optimierung analysiert. Wir verbessern die Apriori Algorithmen durch eine effiziente Kandidatengenerierung und Heuristikbasierten Kandidatenfilter. Eine Hybride Lösung, HCA-GORDIAN, kombiniert die Vorteile von GORDIAN und unserem neuen Algorithmus HCA, welche die bisherigen Algorithmen hinsichtlich der Effizienz in vielen Situationen übertrifft.

Download full text files

Export metadata

Additional Services

Search Google Scholar Statistics
Metadaten
Author details:Ziawasch AbedjanORCiDGND, Felix NaumannORCiDGND
URN:urn:nbn:de:kobv:517-opus-53564
ISBN:978-3-86956-148-6
ISSN:1613-5652
ISSN:2191-1665
Publication series (Volume number):Technische Berichte des Hasso-Plattner-Instituts für Digital Engineering an der Universität Potsdam (51)
Publisher:Universitätsverlag Potsdam
Place of publishing:Potsdam
Publication type:Monograph/Edited Volume
Language:English
Year of first publication:2011
Publication year:2011
Publishing institution:Universität Potsdam
Release date:2011/09/28
Tag:Apriori; Data Profiling; Schlüsselentdeckung; eindeutig; funktionale Abhängigkeit
apriori; data profiling; functional dependency; key discovery; unique
Number of pages:25
RVK - Regensburg classification:ST 230
Organizational units:An-Institute / Hasso-Plattner-Institut für Digital Engineering gGmbH
DDC classification:0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik
Publishing method:Universitätsverlag Potsdam
License (German):License LogoKeine öffentliche Lizenz: Unter Urheberrechtsschutz
Accept ✔
This website uses technically necessary session cookies. By continuing to use the website, you agree to this. You can find our privacy policy here.