Избыточность
Необходимо различать избыточность во множестве именованных отношений и избыточность в хранимом множестве представлений. Здесь мы будем касаться в основном первого вида избыточности. Для начала нам необходимо точное понятие порождаемости для отношений.
Предположим, что θ – это набор операций над отношениями, и каждая операция обладает тем свойством, что вырабатывает единственное отношение из своих операндов (т.е. естественное соединение допустимо, а соединение нет). Отношение R является θ-выводимым из множества отношений S, если существует последовательность операций из набора θ, которая "в любой момент времени" производит R из элементов S. Фраза "в любой момент времени" присутствует потому, что мы рассматриваем изменяющиеся во времени отношения, и для нас представляет интерес свойство порождаемости, сохраняющееся в течение длительного периода времени. Для набора именованных связей в системах без логического вывода достаточный набор θ1 содержит следующие операции: проекция, естественное соединение, связывание и ограничение. Перестановка неуместна, а естественную композицию включать не требуется, т.к. ее можно получить путем естественного соединения с последующей проекцией. Для хранимого множества представлений достаточный набор θ2 должен включать перестановку и дополнительные операции, связанные с получением подмножеств и слиянием отношений, упорядочиванием и связыванием их элементов.
2.2.1. Сильная избыточность. Множество отношений является сильно избыточным, если оно содержит по меньшей мере одно отношение, некоторая проекция которого может быть порождена из других проекций отношений этого множества. Следующие два примера приведены для того, чтобы объяснить, почему сильная избыточность определяется таким образом, а также для демонстрации ее практического использования. В первом примере набор отношений состоит из одного следующего отношения:
служащий (номер, имя, номер_менеджера, имя_менеджера)
где номер является первичным ключом, и номер_менеджера
является внешним ключом. Обозначим активный домен через Δt
и предположим, что
Δt (номер_менеджера) ⊂ Δt
(номер)
и
Δt (имя_менеджера) ⊂ Δt
(имя)
в любой момент времени t. В этом случае избыточность очевидна: домен имя_менеджера не является необходимым. Чтобы убедиться в том, что эта избыточность является сильной избыточностью в соответствии с приведенным выше определением, заметим, что
π34 (служащий) = π12
(служащий)1|1π3(служащий).
Во втором примере набор отношений включает описывающее поставщиков отношение S с первичным ключом s#, описывающее отделы отношение D с первичным ключом d# и описывающее проекты отношение J с первичным ключом j#, а также следующие отношения:
P(s#, d#,...), Q(s#, j#,...), R(d#, j#,...),
где в каждом случае многоточие означает домены, отличающиеся от s#, d#, j#. Предположим, что удовлетворяется следующее не зависящее от времени условие C: поставщик s обслуживает отдел d (отношение P) тогда и только тогда, когда поставщик s обслуживает некоторый проект j# (отношение Q), который выполняется отделом d# (отношение R). Тогда мы можем записать соотношение
π12(P) = π12
(Q) · π21 (R)
и таким образом показать наличие сильной избыточности.
Важная причина существования сильной избыточности в множестве именованных связей заключается в удобстве для пользователя. Частным случаем ее применения является сохранение во множестве именованных связей полуустаревших связей для того, чтобы старые программы, ссылающиеся на них по имени, могли правильно выполняться. Наличие знаний о существовании сильной избыточности во множестве именованных отношений предоставляет администратору системы или базы данных большую свободу в выборе внутреннего представления для более эффективного управления текущей нагрузкой. Если сильная избыточность во множестве именованных отношений непосредственно отражается в сильной избыточности во множестве хранимых представлений (или если во множество хранимых представлений внесена дополнительная сильная избыточность), то, вообще говоря, могут потребоваться дополнительные внешняя память и время для выполнения операций обновления, с возможным замедлением выполнения некоторых запросов и увеличением нагрузки на центральный процессор.
2.2.2. Слабая избыточность. Может существовать другой тип избыточности. В отличие от сильной избыточности она не описывается каким-либо соотношением. Набор отношений является слабо избыточным, если в него входит отношение, которое содержит проекцию, не порождаемую из других отношений набора, но в любой момент времени совпадающую с проекцией некоторого
соединения проекций отношений из этого набора.
Мы можем проиллюстрировать слабую избыточность, рассмотрев второй пример сильной избыточности (из приведенных выше) и предположив, что условие C в некоторые моменты времени не выполняется. Отношения π12(P), π12(Q), π12(R) являются сложными отношениями с возможным существованием точек неоднозначности, появляющихся иногда в потенциальных соединениях каких-либо двух отношений. При этих условиях ни одно из них не порождается из двух других. Однако между ними существует зависимость, поскольку каждое из них является проекцией некоторого циклического соединения трех отношений. Один из видов слабой избыточности может быть охарактеризован следующим утверждением: в любой момент времени π12(P) является некоторой композицией π12(Q) и π21(R). Эта композиция может быть естественной при одних обстоятельствах и может не являться таковой при других.
Вообще говоря, слабые избыточности являются неотъемлемой частью логических потребностей сообщества пользователей. Они не могут быть устранены администратором системы или базы данных. Если они все-таки возникают, они возникают и во множестве именованных отношений, и во множестве хранимых представлений.
