Den funktionella beroende inference problem är följande. Med tanke på ett förhållande Y, hitta en uppsättning funktionella beroenden som är likvärdiga med uppsättningen av alla funktionella beroenden som innehar i r. Alla kända algoritmer för denna uppgift har körtider som i värsta fall kan vara exponentiellt i storleken på den minsta omslaget av beroendeuppsättningen. Vi anser att man kan dra en ungefärlig slutsats om beroende. Vi definierar olika åtgärder för fel i ett beroendeförhållande. Dessa felmått har värdet 0 om beroendet håller och ett värde nära 1 om beroendet uppenbarligen inte håller. Beroende på vilken åtgärd som används, kan alla beroenden med fel minst E i Y detekteras med hög sannolikhet genom att endast överväga 0( 11~) eller 0( jrj" / ~) slumpmässiga tuples av Y. Vi visar också hur en maskin lär algoritm på grund av Angluin et al. kan appliceras för att ge i output-polynom tid ett ungefär korrekt skydd för uppsättningen beroenden som håller i Y.
Kivinen och Mannila föreslår tre åtgärder, G1, G2 och G3, för att mäta felet i ett funktionellt beroende REF.
Approximate inference of functional dependencies from relations
{'venue': 'Theor. Comput. Sci.', 'journal': 'Theor. Comput. Sci.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}