Введение в Алгебраическую теорию информации - Гоппа В.Д.
Скачать (прямая ссылка):
Имя Возраст
010 Петров H.JI. Инженер 10 016 Саша 6
Игорь 4
Вова 2
102 Иванов А.И. Зав. лаб. 20 010 Аня 10
Игорь 8
080 Сергеев С.Н. Ст. инженер 10 016 Вова 6
Каждому атрибуту X. ставится в соответствие множество его
значений D. (домен атрибута). Сложный признак К =
= Xi <8> Х2 <8>.. .<8> X называется возможным ключом, если он
однозначно определяет все остальные значения признаков. Другими словами,
не существует двух строк, имеющих одно и то же значение на всех атрибутах
из К, так что имеет место функциональная зависимость
К
для любого атрибута У. и данного отношения.
Кроме того, предполагается, что ни один атрибут X. не
может быть удален без нарушения этого свойства. Другими словами,
возможный ключ-это минимальный сложный признак, полностью раскрывающий
неопределенность относительно других признаков.
45
Обычно один из возможных ключей фиксируется: значения его атрибутов
остаются неизменными. Такой ключ используется в качестве идентификатора
объекта при поиске информации и называется первичным ключом.
Состояние отношения изменяется во времени. Прежде всего, может
добавляться новая строка (операция "Вставка"). Кроме того, некоторая
строка может стираться (операция "Удаление"). Можно изменять лишь часть
строки. Модификация достигается с помощью операции "Изменение".
База данных должна реагировать на запросы. Выбор-это элементарная
операция над отношением. Результатом ее применения является другое
отношение, которое представляет собой подмножество строк с определенными
значениями в выделенных атрибутах.
Можно выбрать также подмножество столбцов (атрибутов). Такая операция
называется "Проекцией". При создании базы данных стремятся избегать
аномалий при обновлении данных и избавиться от информационной
избыточности в отношениях.
Обратимся к примеру 3.1 [3]. Предположим, что у комнаты 10 изменился
номер телефона. При обновлении базы данных потребовалось бы найти все
строки, у которых соответствующий атрибут принимает значение 016
(аномалия изменения). Кроме того, здесь наблюдается избыточность в
хранении информации, поскольку номер телефона 016 дублируется во многих
строках. Возникает желание заменить отношение "Сотрудники отдела" на два
отношения:
Отношение "Сотрудники"
Табельный номер Ф.И.О. Должность Номер комнаты Дети
Имя Возраст
010 Петров Н.Л. 10
102 Иванов А.И. 20
080 Сергеев С.Н. 10
Отношение "Комнаты"
Номер комнаты Телефон
6 004
7 001
8 007
10 016
20 010
Представление исходного отношения в виде пары отношений называется
декомпозицией.
Восстановить первоначальное отношение можно с помощью операции
"Соединение": в обоих отношениях должен присутствовать общий атрибут (в
данном случае "номер комнаты"). Находим строки с одним и тем же значением
этого атрибута в 46
обоих отношениях и расширяем первое отношение, добавляя новый атрибут
"Телефон".
Любое априорное знание о различного рода зависимостях между атрибутами
может принести большую пользу для оптимального выбора схемы отношений.
3.2. Функциональные зависимости
Функциональная зависимость (/'-зависимость) X -* У была определена в гл.
2 для двух слов X и У посредством равенства Iq(Y/X) = 0. Если известны
некоторые /'-зависимости для атрибутов, то можно вывести остальные,
используя некоторые правила вывода, которые являются следствиями
предложений 1.3-1.7.
F1. Рефлексивность: X -* X.
Доказательство.
10(Х/Х) = 0.
F2. Пополнение: Х -* У влечет за собой
X 0 Z -* У.
Доказательство.
I0(Y/X<8> Z) < I0(Y/X) = 0.
F3. Аддитивность: X -* У и X -* Z влечет за собой X -*
-* У 0 Z.
Доказательство.
Iq(Y 0 Z/X) = 10(У/X) + IQ(Z/X 0 Y) =
= I0(Z/X 0 Y) <IQ(Z/X) =0.
F4. Проективность: X -* У 0 Z влечет за собой X -* У. Доказательство.
0 = /д(У (r) Z/X) = /0(У/Х) + /0(Z/X 0 У),
так что
Iq(Y /X) = 0, I0(z/X 0 У) = 0.
F5. Транзитивность: X -* У и У -* Z влечет за собой
x-*z.
Доказательство.
I0(Z/X) < Iq(Z/ У) + /0(УАХ) = 0.
F6. Псевдотранзитивность: X -*¦ У и F0Z-* Ж влечет за собой X <8> Z -* W.
47
Доказательство.
IQ(W/X <g> Z) < Iq(W/ Y(r)Z) + Iq(Y<g> Z/X <g> Z) =
Iq(Y(r) Z/X <g> Z) = Iq(Y/X (r) Z) + 70(Z/ Y(r)X(r)Z)<
< Iq(Y/X) + Iq(Z/Z) = 0.
Выше приведенные правила позволяют строить новое множество, отправляясь
от некоторого множества /'-зависимостей и добавляя новые /'-зависимости.
Пусть, например,
F={X-*Y, X&Y-Z&U, U-V}.
Используя пополнение, получаем
Z <8> U-V.
Используя транзитивность, имеем
X (r) Y -* V.
Из рефлексивности
X <g> У X (r) У
следует
X<8>Y-*X(r)Y(r)V.
Наконец, применяя аддитивность, получаем
X<8>Y->X<8>Y<8>V(r)Z(r)U.
Обозначим через А множество правил
А = {Fl, F2, ..., Л)}.
Применяя эти правила к некоторому множеству /'-зависимостей несколько
раз, получаем расширенное множество зависимостей, которое стабилизируется
на некотором шаге. Назовем его замыканием множества F и обозначим F*.
Очевидно
{П)' = П-
Добавим к множеству А некоторое новое правило. В результате получаем
множество В 2 А. Применяя правила из В к множеству F несколько раз,
