O metodă de construire a tuturor acoperirilor neredundante existente de dependenţe funcţionale

Abstract

În articol este abordată problema construirii tuturor acoperirilor neredundante existente ale unei mulţimii de dependenţe funcţionale. Aceasta este posibil, utilizînd ca bază un algoritm procedural conventional, prin permutarea dependenţelor în mulţimea initială şi calcularea acoperirii pentru fiecare mulţime nou formată. Însăpentru o mulţime cu n dependenţe numărul permutărilor pesibile este n!, ceea ce ar duce la creşterea enormă a timpului de calcul. A fost propusă o metodă de a minimiza numărul permutărilor, care constă în eliminarea din lista permutărilor a dependenţelor neesenţiale. Au fost propuse criteriile pentru determinarea dependenţelor neesenţiale, formulate în baza noţiunilor de atribute neesenţiale şi recuperabile. A fost arătată eficienţa metodei propuse în baza unor exemple. A fost realizat algoritmul de căutare a tuturor acoperirilor neredundante existente într-un limbaj procedural şi estimat timpul de calcul.