Реферат: Лекции по теории проектирования баз данных (БД)
Проективность: X -> YZ влечет за собой X -> Z.
Транзитивность: X -> Y и Y -> Z влечет за собой X -> Z.
Псевдотранзитивность: X -> Y и YZ -> W влечет за собой XZ -> W.
Пример.
Пусть дано отношение R , а X , Y и Z подмножества R . Предположим, что отношению удовлетворяет XY -> Z и X -> Y . Согласно аксиоме псевдотранзитивности получим XX -> Z или X -> Z.
Если даны аксиомы рефлексивности, пополнения и псевдотранзитивности, то из них можно вывести все остальные. Иногда их называют аксиомами Армстронга.
Пусть F-множество F-зависимостей для отношения R . Замыкание F , обозначаемое F+ , - это наименьшее содержащее F множество, такое что при применении к нему аксиом Армстронга нельзя получить ни одной F - зависимости, не принадлежащей F.
Пример.
Пусть F = {AB -> C, C -> B } - множество F-зависимостей на R(ABC). F+ = {A -> A, AB -> A, AC -> A, ABC -> A, B -> B, AB -> B, BC -> B, ABC -> B, C -> C, AC -> C, BC -> C, ABC -> C, AB -> AB, ABC -> AB, AC -> AC, ABC -> AC, BC -> BC, ABC -> BC, ABC -> ABC, AB -> C, AB -> AC, AB -> BC, AB -> ABC, C -> B, C -> BC, AC -> B, AC -> AB}
Таким образом, если известно множество F-зависимостей удовлетворяющих отношению R, можно найти все F- зависимости, удовлетворяющие этому отношению. Говорят, что F = X -> Y ,если X -> Y F+ .
Лекция 3
Получение замыкания F+ не обязательно для установления F = X -> Y.
Для этого достаточно воспользоваться алгоритмом MEMBER .
Алгоритм MEMBER.
Вход: Множество F-зависимостей F и F-зависимость X -> Y.
Выход: истина, если F = F = X -> Y, ложь в противном случае.
MEMBER(F, X -> Y)
begin
if Y CLOSURE(X,F) then return (истина)
else return(ложь)
end
Здесь CLOSURE алгоритм, позволяющий выявить список атрибутов входящих в множество F, который имеет вид.
Алгоритм CLOSURE.
Вход: Множество атрибутов Х и множество F-зависимостей F.
Выход: Замыкание Х над F.
CLOSURE(X,F)
begin
OLDDEP = 0; NEWDEP = X
while NEWDEP OLDDEP do begin
OLDDEP = NEWDEP
for каждая F- зависимость W -> Z в F do
if NEWDEP W then
NEWDEP = NEWDEP Z