Число функциональных зависимостей

Question

Найдите количество функциональных зависимостей в отношении, имеющем n атрибутов?

При первой же мысли я выясню, что левая сторона может иметь N + 1 возможности (также может быть и нуль). Аналогично N + 1 возможность для правой стороны.
Поэтому не составит не ФД должно быть
(п + 1) * (п + 1) - 1

Но анс данные есть 2^(п + 1).

При анализе ответа мы видим, что они не включают тривиальные, такие как ABC -> A и т. Д.

Итак, что должно быть правильным?

Answer 1

Я думаю, 2^n * 2 - это ответ, потому что он включает в себя все базовые минимальные FD, а остальные могут быть получены из аксиом или тривиальны. A -> BC будет иметь A -> B, A -> C и т. Д. ABC -> A и т. Д. Тривиальны.

Хотя неясно, включать ли все тривиальные случаи. В этом случае ответ будет 2^n * 2^n. Потому что мы можем выбрать 2^n для LHS и RHS.

Answer 2

2^n возможных наборов атрибутов на LHS, и снова 2^n возможных наборов атрибутов на RHS. Оба подсчета включают пустой набор.

Число возможных различимых пар между ними равно 2^n * 2^n.

В то время как это технически правильно, этот ответ также подразумевает, что также рассматриваются FD, такие как {AB} -> {}. Сколько из них есть? Для каждой мощности l LHS существует 2^l возможных подмножеств, каждый из которых дает тривиальный FD, если он появляется на RHS. Таким образом, число тривиальных FDs равно 2^0 + 2^1 + 2^2 + ... + 2^n = 2^(n + 1) - 1. Оставляя в сумме 2^(2 * n) + 1 - 2^(п + 1).

Но теперь мы исключили только {AB} -> {A} и т.п., а не {AB} -> {AC}. Если мы хотим, чтобы RHS указывал только атрибуты, которые не упоминаются в LHS, то для каждой мощности l LHS существует 2^(nl) -1 возможных подмножеств на RHS (требуется дополнительный минус один, потому что пустой набор должен быть исключен). Суммируя до 2^0 - 1 + 2^1 - 1 + 2^2 - 1 + ... + 2^n - 1 = 2^(n + 1) - 1 - (n + 1).

Все еще отличается от ответа. И, во всяком случае, вопрос был сформулирован безнадежно плохо. Вопрос НЕ ГОСУДАРСТВЕННЫЙ, что тривиальные FD должны быть исключены. Вопрос НЕ ГОСУДАРСТВЕННЫЙ, что «частично тривиальные» FD должны быть исключены.

BTW давайте ответим на тест. Выберем отношение степени 1, {A}. Есть четыре возможных ФД:

{} -> {} тривиальна, РИТ подмножество LHS
{} -> {A}
{А} -> {} тривиальна, РИТ подмножество LHS
{A } -> {A} тривиальное, RHS подмножество LHS.

Правильный ответ, если тривиальные FD должны быть исключены, является «одним». В вашем учебнике сказано, что это «четыре».