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

Учитывая таблицу с десятками столбцов, многими тысячами строк и неизвестными функциональными зависимостями между столбцами, существует ли какой-либо алгоритм для автоматического поиска ключа-кандидата для этой таблицы, который быстрее или эффективнее этого:

  1. Проверьте, является ли какой-либо отдельный столбец ключом-кандидатом

  2. Проверьте, являются ли какие-либо 2 столбца ключом-кандидатом

  3. Проверьте, являются ли какие-либо 3 столбца ключом-кандидатом

... и так далее, пока ключ не будет найден?


sql algorithm candidate-key
person Marco    schedule 29.06.2017    source источник
comment
Что вы имеете в виду, нет известных функциональных зависимостей? Этого не может быть, всегда есть тривиальные FD. Вы имеете в виду, что никакие нетривиальные FD не выполняются? Почему ты это сказал? Что именно вам дано? (Вы уверены? Это означает отсутствие заданных суперключей, CK, PK или UNIQUE, потому что они подразумевают, что определенные FD удерживаются и не удерживаются.) Тогда его единственный CK — это набор всех атрибутов. Вы имеете в виду, что они могут держаться, но вы не знаете? Вы должны быть в состоянии определить набор всех FD, которые существуют, чтобы найти CK. Набор всех атрибутов всегда является суперключом. Что значит, проверить? Как вы собираетесь это сделать?   -  person philipxy    schedule 29.04.2021

Ответы (1)


arrow_upward
0
arrow_downward

Первичный ключ таблицы должен быть уникальным. Если ваш набор данных со временем растет, недостаточно проверить, уникальны ли теперь столбцы. Они должны быть уникальными навсегда. Так что в этом случае я бы избегал естественного ПК и выбрал суррогатный ключ.

Если вы на 100% уверены, что должен быть естественный ключ, но вы просто не знаете столбцы, с которых вы начинаете, определяя различную кардинальность столбцов:

SELECT COUNT(*),
       COUNT(DISTINCT column1),
       COUNT(DISTINCT column3),
       ...
FROM table

Если для любого столбца уникальное количество значений равно общему количеству строк, вы нашли ключ. Если это несколько столбцов, вам нужно использовать метод проб и ошибок. Вы знаете, что произведение отдельных значений столбцов ваших ключевых кандидатов должно быть больше или равно общему количеству строк.

COUNT(DISTINCT key_column1) * COUNT(DISTINCT key_column2) * COUNT(DISTINCT key_column3) >=  COUNT(*)

Зная это, вы можете искать правдоподобные комбинации, например

SELECT COUNT(DISTINCT key_column1 || key_column2 || key_column3), COUNT(*)
FROM table

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

Я думаю, вы можете сделать это полностью автоматическим, используя словарь данных, но у меня нет под рукой решения.

person fhossfel    schedule 29.06.2017
comment
Спасибо за ответ. Чтобы уточнить: набор данных не растет, и я уверен, что есть естественный ключ, но не знаю, какой. Я знаю всю проверку, если нет. различных значений в наборе столбцов равно нету. различных строк в таблице и оптимизации с помощью критерия умножения, но количество комбинаций растет по мере проверки больших подмножеств. Кроме того, хотя я не упомянул об этом, я хочу сделать это на нескольких таблицах (около 100), поэтому нужен алгоритм, который находит ключ более эффективно, чем метод грубой силы, который я описал, без необходимости проверять отдельные таблицы. . - person Marco; 30.06.2017