Cтраница 2
Алгоритм имеет полиномиальную временную сложность. Вывод и доказательство корректности алгоритма AVOID опускаются ( см. упр. Алгоритм AVOID ( R, В, F) применяется для каждого атрибута В из R. Если выход не пуст, множество выделенных ключей R заменяется на альтернативное множество, полученное алгоритмом AVOID. Известно, что если такое множество ключей существует, то при его использовании атрибут В удалим. Из R - В - В можно вывести новое множество F-зависимостей, представленных в R, так как для R должен существовать новый выделенный ключ К, для которого К - - В ( К есть один из замененных ключей, найденных AVOID; см. упр. [16]
Следствие 3 утверждает, что п должно быть простым или степенью простого числа. Но вторая возможность отсекается первым пунктом алгоритма. Это завершает доказательство корректности алгоритма. [17]