Unika kolumnkombinationer av en relationsdatabastabell är grupper av kolumner som endast innehåller unika värden. Att upptäcka sådana kombinationer är ett grundläggande forskningsproblem och har många olika tillämpningar för datahantering och kunskapsupptäckt. Befintliga upptäcktalgoritmer är antingen brute force eller har en hög minnesbelastning och kan därför endast tillämpas på små datauppsättningar eller prover. I denna artikel jämförs och analyseras den välkända gordiska algoritmen [9] och "Aprioribaserade" algoritmer [4] för ytterligare optimering. Vi förbättrar Apriori-algoritmerna avsevärt genom effektiv kandidatgenerering och statistikbaserade beskärningsmetoder. En hybridlösning HCA-Gordian kombinerar fördelarna med Gordian och vår nya algoritm HCA, och den överträffar allt tidigare arbete i många situationer.  Unik upptäckt har stor betydelse i flera datahanteringsapplikationer, såsom datamodellering, anomalidetektering, frågeoptimering och indexering. Upptäckta unika är bra kandidater för primära nycklar i en tabell. Därför hänvisar viss litteratur till dem som "candidate keys" [8]. Den * En fullständig version av detta papper finns på [1] Tillstånd att göra digitala eller hårda kopior av hela eller delar av detta arbete för personligt eller klassrum användning beviljas utan avgift, förutsatt att kopior inte görs eller distribueras för vinst eller kommersiella fördelar och att kopior bär detta meddelande och den fullständiga hänvisning på första sidan. För att kopiera på annat sätt, för att återpublicera, för att posta på servrar eller för att omfördela till listor, krävs tidigare specifik behörighet och/eller avgift. Termen "kompositnyckel" används också för att belysa det faktum att de omfattar flera kolumner [9]. Vi vill betona att upptäckten av unika saker är ett problem som kan lösas exakt, medan upptäckten av nycklar bara kan lösas heuritiskt. Unikhet är en nödvändig förutsättning för en nyckel, men endast en mänsklig expert kan "främja" en unik till en nyckel, eftersom unika kan visas av en slump för ett visst tillstånd av data. I kontrast, nycklar anges medvetet och betecknar en schema begränsning. En viktig egenskap hos unika och nycklar är deras minimalitet. Minimala unika är unika av vilka inga strikta undergrupper håller den unika egenskapen: I princip, för att identifiera en kolumn kombination K av fast storlek som en unik, måste alla tuples ti skannas. En scan har en körtid av O(n) i antalet n av rader. För att upptäcka dubbla värden behöver man antingen en sorts O(n log n) eller en hashingalgoritm som behöver O(n) utrymme. Icke-unioner definieras enligt följande: Definition 3. En kolumnkombination K som inte är unik kallas icke-unik. Upptäcka alla unika i en tabell eller relationell instans kan reduceras till problemet med att upptäcka alla minimala unika. Varje superset av en minimal unik är också en unik. Därför, i resten av detta papper upptäckten av alla unika används synonymt för att upptäcka alla minimala unika. Den exponentiella komplexiteten orsakas av det faktum att för en relations schema R = {C1,. .., Cm}, det finns 2 m − 1 undergrupper K  på R som kan vara unika. Faktum är att till och med problemets storlek kan vara exponentiellt. I värsta fall kan det finnas 1. Vi analyserar, diskuterar och kategoriserar befintliga algoritmer och deras styrkor och svagheter. 2. Utgångspunkten är följande: Vi introducerar den nya algoritmen HCA och visar hur en bottom-up algoritm kan optimeras genom att tillämpa konceptet apriori kandidatgenerering, statistikdriven beskärning, och ad-hoc inference av FDs. 3. Vad är det som händer? Dessutom presenterar vi en elegant kombination av HCA med den välkända gordiska algoritmen [9], HCA-Gordian, som ger ännu mer effektivitet. Även om ämnet att hitta eller sluta sammansatta nycklar och funktionella beroenden dök upp ända sedan det finns 1565
Dessutom, generera minimala unika från maximal icke-uniques kan vara en allvarlig flaskhals när antalet maximal icke-uniques är stor REF.
Advancing the discovery of unique column combinations
{'venue': "CIKM '11", 'journal': None, 'mag_field_of_study': ['Computer Science']}