Уточнение базы данных - минимальное покрытие F (посторонние атрибуты)
Схема R = (A, B, C, D, E, F)
FD F = {ABC -> D, CD -> B, BCF -> D, CDF -> BE, BCDF -> E}
Найдите Fc, минимальное покрытие (он же каноническое покрытие) F.
Этот метод используется в моей книге:
Пример: abc -> xyz
a является избыточным (посторонним), если (bc) + ⊇ a; x является избыточным, если (abc)+ ⊇ x.
ПРИМЕЧАНИЕ. Здесь замыкания вычисляются с использованием F, а a или x удаляются из abc -> xyz соответственно.
Я не понимаю последнее смелое предложение.
Одним из решений является:
Рассмотрим CDF -> BE
B является избыточным: (CDF) + = (CDFBE) ⊇ (B)
F становится {ABC -> D, CD -> B, BCF -> D, CDF -> E }
но я не понимаю
согласно этой логике:
E тоже может быть избыточным,
сог:
Рассмотрим CDF -> BE
E является избыточным: (CDF) + = (CDFBE) ⊇ (E)
F становится {ABC -> D, CD -> B, BCF -> D, CDF -> B }
Я знаю, что должен пропустить некоторые важные критерии. Кто-нибудь может сказать мне, что это?
1 ответ
Если r(R) является реляционной схемой, для которой определен набор функциональных зависимостей F, то атрибут A в R не имеет отношения к функциональной зависимости x->Y
if A belongs to X and A is extraneous then
(F - {X->Y}) U {(X-A) -> Y} is equivalent to F
if A belongs to Y and A is extraneous then
F is equivalent to (F - {X->Y}) U {X -> (Y-A)}
Вычислить, если A посторонний по отношению к X
1. Find (X-A)+ under F
2. If Y is a subset of (X-A)+ under F then A is extraneous
Идея состоит в том, чтобы проверить, можем ли мы получить удаленный атрибут в левой части этой функциональной зависимости и все же иметь возможность получить его с другими функциональными зависимостями внутри F. Если да, то A является избыточным, так как он может быть выведен из других ФД.
Вычислить, если A посторонний по отношению к Y
1. Find F' = (F - {X->Y}) U {X -> (Y-A)}
2. Find X+ under F'
3. Если X+ под F'содержит A, то A посторонний по отношению к Y
Здесь мы удаляем A с левой стороны и проверяем, может ли выводимый атрибут быть выведен из набора FD, для которых A удален из этого. Вид симуляции, если у нас есть FD {X -> (YA)} и с другими FS в наборе F, и найти замыкание X под этим симулированным FD. Если мы видим, что X+ содержит удаленный атрибут из исходного, тогда он был избыточен в исходном наборе, и, таким образом, мы объявляем A посторонним для Y и сохраняем набор с удаленным A, который мы называем F', потому что F' имеет такое же закрытие, как у F.
Обратите внимание, что мы не вычисляем F'с удаленным A, как в случае секунд. Это потому, что (XA) является подмножеством X и, таким образом, (XA)+ под F всегда будет (XA) U Y на некотором этапе вычисления закрытия атрибута. Это так же, как если бы мы построили F' = (F - {X->Y}) U {(XA) -> Y} и вычислили замыкание (XA) под этим F', поскольку (XA) является подмножеством к себе, и модифицированный FD в F'также будет вычисляться в (XA) U Y. Это причина, если A принадлежит X, мы не вычисляем F'. Хотя мы могли бы, но это не имеет значения в вычислении замыкания.
С другой стороны, когда A принадлежит Y, мы должны вычислить F'с A, удаленным из Y, это потому, что когда мы находим X+ под F', мы получаем X U (YA) в шаге, и если мы находим замыкание X под F мы получаем X U Y, что не имеет смысла, так как он просто вычисляет замыкание X по его первоначальному набору, из которого мы не можем сказать, является ли какой-то атрибут посторонним.
Просто убедитесь, что удаленный атрибут может быть выведен из других FD в наборе. Удалите целевой FD из исходного набора и проверьте, можете ли вы логически вывести удаленный атрибут удаленного FD из другого атрибута. Аксиомы Армстронга также могут быть применены.
Обратите внимание, что если два атрибута являются посторонними для FD слева или справа, вы не можете удалить оба. В этом случае создаются два FD, каждый с одним удаленным лишним атрибутом. Как в вашем примере
F = {ABC -> D, CD -> B, BCF -> D, CDF -> BE, BCDF -> E}потому что CDF->BE, B является посторонним, а также E посторонний. Так что это создает две возможности:F1 = {ABC -> D, CD -> B, BCF -> D, CDF -> B, BCDF -> E}F2 = {ABC -> D, CD -> B, BCF -> D, CDF -> E, BCDF -> E} (здесь вы можете удалить CDF->E также, поскольку BCDF->E подразумевает CDF->E)
Вы можете найти более одного Canonical Cover/Minimal Cover из набора функциональных зависимостей. Так что это не уникально. Вам не нужно отслеживать все возможности, которые генерируются подобным образом. Просто выберите один.
КАК для быстрого вычисления вот что я нашел, поскольку он каноническое покрытие / минимальное покрытие:
Fc = {AC->D, CD->B, CF->DE}
Дайте нам знать, если есть еще проблемы.
EDIT1:
Рассматривать
r(A, B, C)
и набор FDs
F = {A->BC, B->AC, C->AB}
Здесь вы видите, что под F, B чуждо A->BC, Также "С" является посторонним для A->BC под F, Но вы не можете удалить оба, потому что, когда вы найдете B чуждо A->BC Вы уже удалили Bи что приводит к A->Cи теперь у вас есть новый набор функциональных зависимостей: F1 = {A->C, B->AC, C->AB} где C в не постороннем для A->C под набором F1, Каждый шаг удаления дает вам новый набор FD, в соответствии с которым вы обнаруживаете, является ли следующий выбранный атрибут посторонним или нет.
Приведенный выше пример очень интересен, так как вы можете получить 4 канонических обложки из него, как показано ниже.
A->BC
B->AC
C->AB
|
+-----------------+-----------------+
| |
A->C A->B
B->AC B->AC
C->AB C->AB
| |
+--------+--------+ +--------+--------+
| | | |
A->C +---+---+ +---+---+ A->B
B->A | A->C | | A->B | B->AC
C->AB | B->C | | B->AC | C->A
| | C->AB | | C->B | |
+ +-------+ +-------+ +---+---+
| | Fc2 | | Fc3 | | A->B |
+---+---+ +-------+ +-------+ | B->C |
| A->C | | C->A |
| B->A | +-------+
| C->B | | Fc4 |
+-------+ +-------+
| Fc1 |
+-------+
Обратите внимание на то, как формируется дерево, благодаря различным возможностям удаления и вычислению посторонних атрибутов относительно последнего FD, в котором оно находится. Я имею в виду, что вы не можете удалить FD A->BC так как B а также C чуждо A->BC под F, потому что удаление B генерирует еще один FD с A->C (одна ветка) и удаление C от A->BC образует другой набор FD, который имеет A->B (другая ветка).