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

Question

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

Например:

Если у вас есть: Таблица = (A, B, C) <- это столбцы: A, B, C </p>

И зависимости:

A → BC

B → C

A → B

AB → C

Каноническое покрытие (или минимальное количество зависимостей):

A → B

B → C

Есть ли программа, которая может это сделать? Если нет, то любой код / ​​псевдокод, который поможет мне написать один, будет оценен. Предпочитаю в Python или Java.

Answer 1

Похоже, вы можете изменить любые правила вида:

   A ->  BC

в

 A -> B

и

  A -> C

и любые правила вида:

  AB -> C

в

  A -> C

и

  B -> C

После этого рефакторинга у вас должен быть набор правил для одиночных пар:

  X -> Y

(Вероятно, с большим количеством избыточных копий вы можете немедленно удалить). Это формирует частичный порядок, на который, похоже, ссылался rlotun.

Например, в результате вы получите:

 A -> B
 B -> C
 A -> C

Если вы затем минимизируете частичный порядок (например, удалите все лишние ссылки, любые книги структуры данных по частичному должны сказать вам, как это сделать), вы будете иметь минимальный частичный заказ, и я думаю, что это ответ, который вы хотите. Минимизируя частичный порядок в примере, вы удалили A -> C из частичный заказ, заканчивающийся вашим ответом.

Answer 2

Глядя на ваши зависимости, похоже, что вы можете просматривать их как частичный заказ на A, B, C. То, что вы хотите, звучит очень похоже (но не полностью) на топологическую сортировку (частичная сортировка порядка на направленном ациклическом графе).