Правила вывода

Определения транзитивной зависимости и концепции добавления, данные выше, касаются двух правил вы­вода из имеющихся шести. Эти правила могут быть использованы для уменьшения, модификации исходного набора ФЗ и получения другого, эквивалентного ему набора ФЗ. Еще три правила вкратце рассматри­ваются ниже. Полное описание всех правил можно найти в большинстве более фундаментальных книг ('' Полное множество правил вывода состоит из трех аксиом Армстронга - рефлексивности (для любого множества атрибутов А и X АХ -> X) и уже обсуждавшихся транзитивности и дополнения, а также трех следующих из этих аксиом правил объединения, декомпозиции и псевдотранзитивности, которые обсуждаются ниже. Более подробную информацию о свойствах правил вывода можно найти, например, в книге Дж. Ульмана "Основы систем баз дан­ных" - М., Финансы и статистика, 1983, с. 156-164.)

Два наиболее простых для понимания правила вы­вода связаны с объединением и декомпозицией ФЗ, которые определяются следующим образом:

Объединение ФЗ: если А -> В и А -> С, то А -> В,С

Декомпозиция ФЗ: если А->В,С то А->В и А->С

На рис. 31 дается графическое представление каждого утверждения, рис. 32 иллюстрирует способы преобразования исходного набора ФЗ в менее слож­ный набор неизбыточных ФЗ с помощью процедур объединения, декомпозиции и добавления.

Последнее из обещанных правил вывода называет­ся псевдотранзитивностью.

Если X -> Y и Y,W -> Z, то X,W -> Z является избыточной в силу псевдотранзитивности.

Графический пример на псевдотранзитивность при­веден на рис.33. Этот тип избыточности возникает в тех случаях, когда в получаемых ФЗ обнаруживаются составные детерминанты. Конкретный пример, иллюст­рирующий данную ситуацию, будет приведен в следу­ющей главе при рассмотрении учебной БД.

Для большинства людей графические формы диаг­рамм зависимостей упрощают выявление избыточных ФЗ; однако в тех случаях, когда число атрибутов и ФЗ достаточно велико, графический подход может оказаться слишком громоздким. В этом случае можно воспользоваться каким-либо известным математиче­ским алгоритмом поиска избыточных зависимостей. Эти алгоритмы не слишком сложны для применения.

Рис. 31. Примеры на объединение и декомпозицию

Минимальное покрытие

Набор неизбыточных ФЗ, полученный путем удаления всех избыточных ФЗ из исходного набора с помощью 6 правил вывода, называется минимальным покрытием.

К сожалению, минимальное покрытие не всегда явля­ется уникальным, поскольку поря­док, в котором осу­ществля­ется процедура удаления из­быточных ФЗ, может оказать влияние на полученное мини­мальное по­крытие. Чтобы убедиться в этом, читателю достаточ­но обратиться к рис. 3.2 и проверить, что в пред­ставленном случае проекти­рования существуют два ми­нимальных покрытия. Первое минимальное покры­тие получается при удалении из исходного набора за­висимости Сном -> Тном, а второе - при удалении Сном -> Кном. Использование этих двух минималь­ных покрытий ведет к построению тех же самых двух БД, проектирование которых обсуждалось выше. В заклю­чение следует подчеркнуть один важный мо­мент, связанный с удалением избыточных ФЗ из ис­ходного набора: избыточные ФЗ следует удалять по одной, каждый раз заново анализируя новый набор на предмет присутствия в нем избыточных ФЗ.

Рис. 32. Упрощение диаграммы ФЗ с помощью пра­вил вывода

Рис. 33. Графические примеры на псевдотранзитивность  

Алгоритм проектирования БД методом декомпозиции (восходящий метод)

Следующий обобщенный алгоритм декомпозиции будет использоваться:

1. Построение универсального отношения для БД.

2. Определение всех ФЗ, существующих между атрибутами универсального отношения.

3. Удаление всех избыточных ФЗ из исходного набора ФЗ с целью получения минимального покрытия. Эта процедура проводится путем поочередного удале­ния избыточных ФЗ с последующей проверкой получаемого на каждом шаге набора ФЗ на наличие хотя бы одной избыточной ФЗ.

4. Использование ФЗ из минимального покрытия для декомпозиции универсального отношения в набор НФБК-отношений.

5. Если может быть получено более чем одно минимальное покрытие, осуществляется сравнение результатов, полученных на основе различных минимальных покрытий, с целью определения варианта, лучше других отвечающего требованиям предприятия.

При использовании алгоритма декомпозиции (Шаг 4) следует помнить о нежелательности проекции, порождаемой ФЗ, у которой зависимостная часть является детерминантом другой ФЗ; также повышенное внимание требуется в тех случаях, когда зависимостная часть ФЗ зависит более чем от одного детерминанта. В любом из этих случаев может быть утеряна ФЗ из БД. Если в процессе декомпозиции достигнуто состояние, в котором проецирование, невлекущее за собой потерь ФЗ, становится невозможным, проектировщик должен будет сделать выбор из двух альтернатив: (1) выбор оставшихся ФЗ и создание одного отношения для каждых детерминанта и набора зависящих от него атрибутов; (2) изменение порядка ранее проведенных декомпозиций, ведь алгоритм проектирования не ведет к единственному решению.

Дата добавления: 2015-07-08