Funktionella beroenden är viktiga metadata som används för normalisering av schema, datarensning och många andra uppgifter. Den effektiva upptäckten av funktionella beroenden i tabeller är en välkänd utmaning inom databasforskningen och har sett flera tillvägagångssätt. Eftersom det inte finns någon heltäckande jämförelse mellan dessa algoritmer vid den tidpunkten, är det svårt att välja den bästa algoritmen för en given datauppsättning. I denna experimentella uppsats beskriver, utvärderar och jämför vi de sju mest citerade och viktigaste algoritmerna, alla löser samma problem. Först klassificerar vi algoritmerna i tre olika kategorier och förklarar deras likheter. Vi beskriver sedan alla algoritmer med deras huvudidéer. Beskrivningarna ger ytterligare detaljer där de ursprungliga dokumenten var tvetydiga eller ofullständiga. Vår utvärdering av noggranna re-implementeringar av alla algoritmer spänner över ett brett testutrymme inklusive syntetiska och verkliga data. Vi visar att alla funktionella beroendealgoritmer optimerar för vissa dataegenskaper och ger tips om när man ska välja vilken algoritm. Sammanfattningsvis ska dock alla nuvarande strategier skala förvånansvärt dåligt, visar potential för framtida forskning. Funktionella beroenden uttrycker samband mellan attribut för en databasrelation. En FD X → A anger att värdena för attributuppsättningen X unikt bestämmer värdena för egenskapen A. Till exempel, zipcode attribut i en adress relation vanligtvis bestämmer staden attribut: zipcode → stad. På grund av denna egenskap tjänar funktionella beroenden ett brett spektrum av dataanalys, dataintegration och datarensningsuppgifter. I synnerhet används de ofta för schema normalisering och databas (re-) design. Liu m.fl. ge en utmärkt undersökning av litteraturen, analysera många algoritmer för funktionell beroende upptäckt. Medan alla algoritmer har samma mål, nämligen upptäckten av alla minimala, icke-triviala funktionella beroenden i en given datauppsättning, skiljer de sig åt i sitt tillvägagångssätt. Befintliga utvärderingar och jämförelser av undergrupper av algoritmerna visar inte väl hur tillvägagångssätten skiljer sig i sin körtid och minne beteende, och det har inte gjorts någon jämförande studie av denna omfattande uppsättning algoritmer i det förflutna. Därför är det nästan omöjligt för utvecklare att hitta rätt algoritm för sina behov. I den här artikeln analyserar och jämför vi FD-algoritmerna i detalj. Vi mäter deras exekveringstid och minnesförbrukning på syntetiska och verkliga datauppsättningar och förklarar algoritmernas beteende i olika scenarier. Dessutom ger vi tips om vilken algoritm som ska användas för vilka datauppsättningar. Sammantaget kan vi bekräfta ursprungliga experimentella resultat, där det finns tillgängliga. Bidrag. Vi klassificerar sju FD-algoritmer med deras huvudkoncept som ger en översikt över den senaste utvecklingen. Vi ser över alla algoritmer och ger ytterligare beskrivningar för deras praktiska genomförande där deras ursprungliga publikationer är glesa. Vi jämför algoritmerna på olika datauppsättningar och utvärderar både körning och minnesanvändning. Utifrån våra experimentella resultat får vi konkreta förslag på när vi ska använda vilken algoritm. Vi gör också alla implementeringar, data och utvärderingsramen tillgängliga online 1. Struktur. Avsnitt 2 ger en översikt över FD upptäckt i allmänhet, diskuterar gemensamma begrepp, alternativa tillvägagångssätt, och vår klassificering av upptäckt algoritmer. I avsnitt 3 beskrivs genomförandet av algoritmerna. I avsnitt 4 presenteras våra utvärderingsresultat och i avsnitt 5 dras slutsatsen om fördelarna och nackdelarna med varje upptäcktalgoritm. Vi definierar först formellt funktionella beroenden efter noteringen av [7] och klassificerar sedan de sju FD-algoritmerna efter deras tekniska och logiska gemensamma egenskaper för att ge en översikt över toppmoderna FD-upptäcktsmetoder.
Den effektiva upptäckten av exakta FDs har fått särskilt intresse REF.
Functional Dependency Discovery: An Experimental Evaluation of Seven Algorithms
{'venue': 'PVLDB', 'journal': 'PVLDB', 'mag_field_of_study': ['Computer Science']}