Upptäckten av funktionella beroenden från relationer är en viktig databasanalysteknik. Vi presenterar TANE, en effektiv algoritm för att hitta funktionella beroenden från stora databaser. TANE är baserat på partitionering av raderna med avseende på deras attributvärden, vilket gör det snabbt att testa giltigheten av funktionella beroenden även för ett stort antal tuples. Användningen av partitioner gör också upptäckten av ungefärliga funktionella beroenden enkel och effektiv och de felaktiga eller exceptionella raderna kan lätt identifieras. Experiment visar att TANE är snabbt i praktiken. För referensdatabaser förbättras drifttiderna av flera storleksordningar jämfört med tidigare publicerade resultat. Algoritmen är också tillämplig på mycket större datauppsättningar än de tidigare metoderna. Mottaget den 17 september 1998; reviderat den 31 mars 1999 Funktionella beroenden är samband mellan attribut i en databasrelation: ett funktionellt beroende anger att värdet av ett attribut bestäms unikt av värdena för vissa andra attribut. Till exempel, i en adressdatabas, zip-kod bestäms av stad och gata adress. Upptäckten av funktionella beroenden från relationer har fått stort intresse (t.ex. [1, 2, 3, 4, 5, 6, 7, 8] ). Automatiserad databasanalys är naturligtvis intressant för kunskapssökning och datautvinning (KDD). Tänk till exempel på en databas över kemiska föreningar och deras resultat på olika bioassayer. Upptäcka att en väsentlig kvalitet, såsom carcinogenicitet, av en förening beror funktionellt från vissa strukturella attribut kan vara ovärderlig. Funktionella beroenden har också välkända tillämpningar inom databashantering, omvänd teknik [9] och frågeoptimering [10]. Formellt, ett funktionellt beroende över en relation schema R är ett uttryck X → A, där X  på R och A på R. Beroendet innehar eller är giltigt i en given relation r över R om för alla par av tuples t, u / r vi har: (vi säger också att t och u enas om X och A). Ett funktionellt beroende X → A är minimalt (i r ) om A inte är funktionellt beroende av någon lämplig delmängd av X, d.v.s. om Y → A inte håller i r för något Y  på X. Beroendet X → A är trivialt om A  på X. Den centrala uppgiften vi anser är följande: med tanke på en relation r, hitta alla minimala icke-triviala beroenden som håller i r. Ett ungefärligt funktionellt beroende är ett funktionellt beroende som nästan håller. Till exempel är kön ungefär bestämt med förnamn. Sådana beroenden uppstår i många databaser när det finns ett naturligt beroende mellan attribut, men vissa tuples innehåller fel eller utgör undantag från regeln. Upptäckten av oväntade men meningsfulla ungefärliga beroenden verkar vara ett intressant och realistiskt mål i många tillämpningar för datautvinning. Tänk återigen på en databas över kemiska föreningar. Ett ungefärligt beroende från en uppsättning strukturella egenskaper till cancerogeniteten kan vara lika värdefullt som ett funktionellt beroende: båda kan ge värdefulla tips till biokemister för potentiella orsaker till cancer men inte heller kan tas som ett faktum utan ytterligare analys av domän specialister. Ungefärliga funktionella beroenden har också tillämpningar i databasdesign [11]. Det finns många möjliga sätt att definiera ungefärligheten av ett beroende X → A. Definitionen vi använder är baserad på det minsta antalet tupler som måste tas bort från relationen r för X → A för att hålla i r : felet e(X → A) definieras som e(X → A) = min~~~POS=TRUNC r och X → A håller i r\ s}/. Åtgärden e har en naturlig tolkning som den del av tuples med undantag eller fel som påverkar beroendet. Med tanke på feltröskeln ε, 0 ≤ ε ≤ 1, säger vi att X → A är ett ungefärligt (funktionellt) beroende om och endast om e(X → A) är som mest ε. I detta dokument överväger vi också den ungefärliga beroendeinferensuppgiften: med tanke på ett förhållande r och en tröskel ε, hitta alla minimala icke-triviala ungefärliga beroenden.
För att hitta ungefärliga FD:er som håller i ett förhållande, TANE REF partitioner tuples i grupper baserat på deras attributvärden.
TANE: An Efficient Algorithm for Discovering Functional and Approximate Dependencies
{'venue': 'Comput. J.', 'journal': 'Comput. J.', 'mag_field_of_study': ['Computer Science']}