Определение всех ключей-кандидатов с учетом универсального набора атрибутов и списка функциональных зависимостей

Question

Теперь я реализовал следующий алгоритм в java для определения всех возможных ключей-кандидатов, которые работают нормально. Ссылка ниже: -

http://shubhamshoundic.blogspot.com/2012/08/an-algorithm-to-find-all-possible.html

Но в худшем случае, то есть, если все атрибуты присутствуют на обеих сторонах FD (как в случае M определено в приведенной выше ссылке), количество ФД, который могут быть обработаны до 12 или 13.

Причина ограничена кучей пространства в java. Ошибка Ниже броска: -

OutOfMemoryError

Моя просьба помочь мне в реализации такого алгоритма, который будет иметь более простую сложность (Сейчас ее экспоненциальной) улучшить количество FD обрабатываемых по крайней мере, 20.

Должен ли я попытаться вычислить его с использованием многопроцессорности или мне нужно перейти на другой язык, а не в java.

Answer 1

Известно с 1978 года и представлено во всех хороших книгах по базам данных, что проблема нахождения всех ключей требует алгоритма, который имеет экспоненциальную сложность в худшем случае (см., Например: Lucchesi, C. and Osborn, S. (1978). Candidate keys for relations. Journal of Computer and System Sciences, 17(2):270–280). Более того, проблема поиска, если атрибут является простым, - NP Complete.

Это связано с тем, что число возможных ключей само по себе является экспоненциальным с количеством атрибутов или factorial с количеством функциональных зависимостей.

Таким образом, невозможно найти алгоритм полинома с количеством атрибутов или функциональных зависимостей.