Пример нормализации схемы базы данных

ПРИМЕР НОРМАЛИЗАЦИЯСХЕМЫ БАЗЫ ДАННЫХ На рис. приведено иерархическое (т.е. ненормализованное) представление информации, которая должна храниться в базе данных о персонале некоторой компании. В компании есть несколько отделов. В каждом отделе (Department) есть несколько сотрудников (Employee), несколько проектов (Project) и несколько кабинетов (Office). Каждый сотрудник имеет план работы (Job), т.е. несколько заданий, которые он должен выполнить. Для каждой такой работы существует ведомость (Salary history), т.е. перечень денежных сумм, полученных сотрудником за выполнение данной работы. В каждом кабинете есть несколько телефонов (Phone). В базе данных должна храниться следующая информация: Для каждого отдела: DEPT# - номер отдела (уникальный), DBUDGET - бюджет и MGR# -номер сотрудника, который возглавляет этот отдел (уникальный). Для каждого сотрудника: EMP# - номер сотрудника (уникальный), PROJ# - номер текущего проекта, OFF# - номер кабинета, PHONE# номер телефона, а также JOBTILE - название выполняемой работы вместе с DATE - датами и SALARY размерами всех оплат, полученных за выполнение данной работы. Для каждого проекта: PROJ# - номер проекта (уникальный) и PBUDGET - бюджет. Для каждого кабинета: OFF# - номер кабинета (уникальный), AREA - площадь в квадратных футах, PHONE# - номера (уникальные) всех телефонов, установленных в этом кабинете. Составьте соответствующее множество нормализованных отношений для представления этой информации, а также семантические утверждения на основе заданных ФЗ. Логические ограничения 1) Ни один сотрудник не является одновременно руководителем нескольких отделов. 2) Ни один отдел не имеет одновременно нескольких руководителей. 3) Для каждого отдела номер отдела уникальный. 4) Ни один сотрудник не работает более чем в одном отделе. 5) Ни один сотрудник не работает более чем с одним проектом. 6) Каждый сотрудник находится в одном кабинете. 7) За каждым сотрудником закреплен только один номер телефона 8) Ни один сотрудник не имеет одновременно более одного задания. 9) Оплата начисляется сотруднику ежедневно, в зависимости от выполненной работы. 10) Ни один проект не выдается более чем одному отделу. 11) Для каждого проекта номер проекта уникальный. 12) Ни один кабинет не относится одновременно более чем к одному отделу. 13) Для каждого кабинета номер кабинета уникальный. 14) В каждом кабинете есть несколько телефонов, номера которых уникальные. Построение функциональных зависимостей Для каждого отдела: DEPT# - номер отдела (уникальный), DBUDGET - бюджет и MGR# -номер сотрудника, который возглавляет этот отдел (уникальный). Логические ограничения 1) Ни один сотрудник не является одновременно руководителем нескольких отделов. 2) Ни один отдел не имеет одновременно нескольких руководителей. 3) Для каждого отдела номер отдела уникальный. Функциональные зависимости MGR#DEPT# DEPT#MGR# DEPT#DBUDGET Для каждого сотрудника: EMP# - номер сотрудника (уникальный), PROJ# - номер текущего проекта, OFF# - номер кабинета, PHONE# номер телефона, а также JOBTILE - название выполняемой работы вместе с DATE - датами и SALARY размерами всех оплат, полученных за выполнение данной работы. Логические ограничения 4) Ни один сотрудник не работает более чем в одном отделе. 5) Ни один сотрудник не работает более чем с одним проектом. 6) Каждый сотрудник находится в одном кабинете. 7) За каждым сотрудником закреплен только один номер телефона 8) Ни один сотрудник не имеет одновременно более одного задания. 9) Оплата начисляется сотруднику ежедневно, в зависимости от выполненной работы. Функциональные зависимости EMP#DEPT# EMP#PROJ# EMP#OFF# EMP#PHONE# {EMP#,DATE}JOBTITLE {EMP#,DATE}SALARY Для каждого проекта: PROJ# - номер проекта (уникальный) и PBUDGET - бюджет. Логические ограничения 10) Ни один проект не выдается более чем одному отделу. 11) Для каждого проекта номер проекта уникальный. Функциональные зависимости PROJ#DEPT# PROJ#PBUDGET Для каждого кабинета: OFF# - номер кабинета (уникальный), AREA - площадь в квадратных футах, PHONE# - номера (уникальные) всех телефонов, установленных в этом кабинете. Логические ограничения 12) Ни один кабинет не относится одновременно более чем к одному отделу. 13) Для каждого кабинета номер кабинета уникальный. 14) В каждом кабинете есть несколько телефонов, номера которых уникальные. Функциональные зависимости OFF#DEPT# OFF#AREA PHONE#OFF# Основные функциональные зависимости Логическое ограничение Ни один сотрудник не является одновременно руководителем нескольких отделов. Ни один отдел не имеет одновременно нескольких руководителей. Для каждого отдела номер отдела уникальный. Ни один сотрудник не работает более чем в одном отделе. Ни один сотрудник не работает более чем с одним проектом. Каждый сотрудник находится в одном кабинете За каждым сотрудником закреплен только один номер телефона Ни один сотрудник не имеет одновременно более одного задания. Оплата начисляется сотруднику ежедневно, в зависимости от выполненной работы. Ни один проект не выдается более чем одному отделу. Для каждого проекта номер проекта уникальный. Ни один кабинет не относится одновременно более чем к одному отделу. Для каждого кабинета номер кабинета уникальный. В каждом кабинете есть несколько телефонов, номера которых уникальные. Функциональная зависимость MGR#DEPT# DEPT#MGR# DEPT#DBUDGET EMP#DEPT# EMP#PROJ# EMP#OFF# EMP#PHONE# {EMP#,DATE}JOBTITLE {EMP#,DATE}SALARY PROJ#DEPT# PROJ#PBUDGET OFF#DEPT# OFF#AREA PHONE#OFF# F=( MGR#DEPT#, DEPT#MGR#, DEPT#DBUDGET, EMP#DEPT#, EMP#PROJ#, EMP#OFF#, EMP#PHONE#, {EMP#,DATE}JOBTITLE, {EMP#,DATE}SALARY, PROJ#DEPT#, PROJ#PBUDGET, OFF#DEPT#, OFF#AREA, PHONE#OFF# ) Этап 0. Прежде всего отметим, что исходную иерархическую структуру можно рассматривать как ненормализованное отношение DEPT0: DEPT0( DEPT#, DBUDGET, MGR#, XEMP0, XPROJ0, XOFFICE0 ) KDEPT0=({DEPT#}, {MGR#}) – возможные ключи. Отношение DEPT0( DEPT#, DBUDGET, MGR#, XEMP0, XPROJ0, XOFFICE0 ) Здесь смысл атрибутов DEPT#, DBUDGET, MGR# ясен из сокращенных названий, а домены, соответствующие атрибутам XEMP0 (сотрудник), XPROJ0 (проект), XOFFICE0 (кабинет), состоят из значений-отношений и для них требуется дополнительное разъяснение. Для начала рассмотрим домен значений-отношений, соответствующий атрибуту XPROJ0. Пусть PB является множеством всех возможных пар PROJ#-PBUDGET (т.е. декартовым произведением доменов для атрибутов PROJ# и PBUDGET). Тогда значение атрибута XPROJ0, соответствующее любому заданному значению DEPT#, является некоторым подмножеством множества пар в PB. Таким образом, соответствующий атрибуту XPROJ0 домен значений-отношений является множеством всех возможных подмножеств множества PB. (Попросту говоря здесь игнорируется тот факт, что существует ФЗ PROJ#PBUDGET; на практике это означает, что некоторые подмножества множества PB не являются допустимыми значениями для атрибута XPROJ0.) Аналогичные замечания можно привести для атрибутов XEMP0, XOFFICE0 и действительно для всех атрибутов данного примера, домены которых представляют значения-отношения. В каждом таком случае домен является мощным множеством множества всех возможных кортежей некоторого частного типа (эти кортежи необязательно нормализованы, т.е. они могут содержать повторяющиеся группы). Обозначим каждый такой атрибут значений-отношений приставкой “X”. Таким образом заданная иерархия может быть представлена следующим “вложением” нормализованных и ненормализованных отношений. (Здесь подчеркнуты атрибуты, которые являются “уникальными внутри родительских отношений” или глобально уникальными, если таких родителей не существует.) DEPT0( DEPT#, DBUDGET, MGR#, XEMP0( EMP#, PROJ#, OFF#, PHONE#, XJOB0( JOBTITLE, XSALHIST0( DATE, SALARY ))), XPROJ0( PROJ#, PBUDGET ), XOFICE0( OFF#, AREA, XPHONE0( PHONE# ) ) ) Этап 1. Для простоты предположим, что каждое отношение имеет первичный ключ, т.е. всегда можно задать один потенциальный ключ в качестве первичного. В частности, для DEPT0 в качестве первичного ключа выберем DEPT# (таким образом MGR# становится альтернативным ключом). Теперь можно привести данное отношение к набору отношений в 1 НФ. DEPT0( DEPT#, DBUDGET, MGR#, XEMP0( EMP#, PROJ#, OFF#, PHONE#, XJOB0( JOBTITLE, XSALHIST0( DATE, SALARY ))), XPROJ0( PROJ#, PBUDGET ), XOFICE0( OFF#, AREA, XPHONE0( PHONE# ) ) ) Предварительный процесс приведения, предложенный Коддом, выглядит следующим образом: 1) Начиная с отношения, находящегося на вершине этой иерархии, следует расширить каждое непосредственно подчиненное отношение с помощью вставки первичного ключа. Первичным ключом каждого расширенного отношения будет комбинация атрибута, который являлся “уникальным” до расширения, с первичным ключом, скопированным из родительского отношения. 2) Затем необходимо удалить из родительского отношения все атрибуты значений-отношений (т.е. атрибуты, заданные на доменах значений-отношений), удалить корневую вершину иерархии и повторить ту же последовательность действий для каждой из оставшихся подчиненных иерархий. DEPT0( DEPT#, DBUDGET, MGR#, XEMP0( EMP#, PROJ#, OFF#, PHONE#, XJOB0( JOBTITLE, XSALHIST0( DATE, SALARY ))), XPROJ0( PROJ#, PBUDGET ), XOFICE0( OFF#, AREA, XPHONE0( PHONE# ) ) ) Начиная с отношения DEPT0 расширим каждое непосредственно подчиненное отношение XEMP0, XPROJ0, XOFICE0 первичным ключом DEPT# : 1) DEPT1( DEPT#, DBUDGET, MGR#) 2) EMP0(DEPT#, EMP#, PROJ#, OFF#, PHONE#, XJOB0( JOBTITLE, XSALHIST0( DATE, SALARY ))) 3) PROJ1(DEPT#, PROJ#, PBUDGET ) 4) OFICE0(DEPT#, OFF#, AREA, XPHONE0( PHONE# ) ) EMP0(DEPT#, EMP#, PROJ#, OFF#, PHONE#, XJOB0( JOBTITLE, XSALHIST0( DATE, SALARY ))) Начиная с отношения EMP0 расширим каждое непосредственно подчиненное отношение XJOB0 первичным ключом DEPT#, EMP# : 2.1) EMP1(DEPT#, EMP#, PROJ#, OFF#, PHONE#) 2.2) JOB0(DEPT#, EMP#, JOBTITLE, XSALHIST0( DATE, SALARY )) Начиная с непосредственно отношения JOB0 расширим каждое подчиненное отношение XSALHIST0 первичным ключом DEPT#, EMP#, JOBTITLE: 2.2.1) JOB1(DEPT#, EMP#, JOBTITLE) 2.2.2) SALHIST1(DEPT#, EMP#, JOBTITLE, DATE, SALARY ) OFICE0(DEPT#, OFF#, AREA, XPHONE0( PHONE# ) ) Начиная с отношения OFICE0 расширим каждое непосредственно подчиненное отношение XPHONE0 первичным ключом DEPT#, OFF#: 4.1) OFICE1(DEPT#, OFF#, AREA) 4.2) PHONE1(DEPT#, OFF#,PHONE# ) После выполнения этих действий будет получен приведенный ниже набор отношений в 1НФ. Обратите внимание, что при этом будут утрачены все атрибуты значений-отношений. DEPT1( DEPT#, DBUDGET, MGR# ) EMP1( DEPT#, EMP#, PROJ#, OFF#, PHONE# ) JOB1( DEPT#, EMP#, JOBTITLE ) SALHIST1( DEPT#, EMP#, JOBTITLE, DATE, SALARY ) PROJ1( DEPT#, PROJ#, PBUDGET ) OFFICE1( DEPT#, OFF#, AREA ) PHONE1( DEPT#, OFF#, PHONE# ) Этап 2. Теперь можно привести отношения, находящиеся в 1НФ, к эквивалентной совокупности отношений в 2НФ, исключая неприводимые зависимости. Ниже все отношения в 1НФ рассматриваются последовательно одно за другим. DEPT1( DEPT#, DBUDGET, MGR# ) Это отношение уже находится в 2НФ. DEPT2( DEPT#, DBUDGET, MGR# ) EMP1( DEPT#, EMP#, PROJ#, OFF#, PHONE# ) F=( MGR#DEPT#, DEPT#DBUDGET, EMP#PROJ#, EMP#PHONE#, {EMP#,DATE}SALARY, PROJ#PBUDGET, OFF#AREA, DEPT#MGR#, EMP#DEPT#, EMP#OFF#, {EMP#,DATE}JOBTITLE, PROJ#DEPT#, OFF#DEPT#, PHONE#OFF# ) Прежде всего следует отметить, что DEPT# является избыточным компонентом первичного ключа данного отношения. В качестве первичного ключа здесь можно принять атрибут EMP# ( это основано на заданной ФЗ EMP#DEPT#), и в таком виде данное отношение уже будет находиться в 2НФ. EMP2( EMP#, DEPT#, PROJ#, OFF#, PHONE# ) JOB1( DEPT#, EMP#, JOBTITLE ) F=( MGR#DEPT#, DEPT#DBUDGET, EMP#PROJ#, EMP#PHONE#, {EMP#,DATE}SALARY, PROJ#PBUDGET, OFF#AREA, DEPT#MGR#, EMP#DEPT#, EMP#OFF#, {EMP#,DATE}JOBTITLE, PROJ#DEPT#, OFF#DEPT#, PHONE#OFF# ) JOB1: Опять отметим, что необязательно использовать DEPT# в качестве компонента первичного ключа. В качестве первичного ключа отношения JOB1 выбираем {EMP#, JOBTITLE}. Поскольку EMP#DEPT# , то имеется неключевой атрибут DEPT#, который не находится в полной функциональной зависимости от первичного ключа., и, следовательно, JOB1 не находится в 2НФ. Это отношение можно заменить двумя другими: JOB2A( EMP#, JOBTITLE ) и JOB2B( EMP#, DEPT# ) Однако, JOB2B является проекцией EMP2( EMP#, DEPT#, PROJ#, OFF#, PHONE# ), следовательно его можно удалить. SALHIST1( DEPT#, EMP#, JOBTITLE, DATE, SALARY ) F=( MGR#DEPT#, DEPT#DBUDGET, EMP#PROJ#, EMP#PHONE#, {EMP#,DATE}SALARY, PROJ#PBUDGET, OFF#AREA, DEPT#MGR#, EMP#DEPT#, EMP#OFF#, {EMP#,DATE}JOBTITLE, PROJ#DEPT#, OFF#DEPT#, PHONE#OFF# ) SALHIST1: SALHIST1( DEPT#, EMP#, JOBTITLE, DATE, SALARY ) EMP2( EMP#, DEPT#, PROJ#, OFF#, PHONE# ) Можно полностью удалить атрибут DEPT# (т.к. отношение SALHIST будет связано с отношением EMP по его первичному ключу - EMP#): SALHIST1(EMP#, JOBTITLE, DATE, SALARY ) Более того, JOBTITLE не требуется в качестве компонента первичного ключа. В качестве первичного ключа можно использовать комбинацию {EMP#, DATE} (это основано на заданных ФЗ {EMP#,DATE}JOBTITLE, {EMP#,DATE}SALARY), чтобы получить следующее отношение в 2 НФ: SALHIST2( EMP#, DATE, JOBTITLE, SALARY ) Причем, отношение JOB2A, полученное выше, является проекцией SALHIST2, поэтому его можно удалить. JOB2A( EMP#, JOBTITLE ) PROJ1( DEPT#, PROJ#, PBUDGET ) F=( MGR#DEPT#, DEPT#DBUDGET, EMP#PROJ#, EMP#PHONE#, {EMP#,DATE}SALARY, PROJ#PBUDGET, OFF#AREA, DEPT#MGR#, EMP#DEPT#, EMP#OFF#, {EMP#,DATE}JOBTITLE, PROJ#DEPT#, OFF#DEPT#, PHONE#OFF# ) PROJ1: Так же, как и в случае с EMP1, можно рассматривать DEPT# как неключевой атрибут, тогда данное отношение находится в 2НФ: PROJ2( PROJ#, DEPT#, PBUDGET ) OFFICE1( DEPT#, OFF#, AREA ) F=( MGR#DEPT#, DEPT#DBUDGET, EMP#PROJ#, EMP#PHONE#, {EMP#,DATE}SALARY, PROJ#PBUDGET, OFF#AREA, DEPT#MGR#, EMP#DEPT#, EMP#OFF#, {EMP#,DATE}JOBTITLE, PROJ#DEPT#, OFF#DEPT#, PHONE#OFF# ) OFFICE1: Здесь можно привести аналогичное рассуждение. OFFICE2( OFF#, DEPT#, AREA) PHONE1( DEPT#, OFF#, PHONE# ) F=( MGR#DEPT#, DEPT#DBUDGET, EMP#PROJ#, EMP#PHONE#, {EMP#,DATE}SALARY, PROJ#PBUDGET, OFF#AREA, DEPT#MGR#, EMP#DEPT#, EMP#OFF#, {EMP#,DATE}JOBTITLE, PROJ#DEPT#, OFF#DEPT#, PHONE#OFF# ) PHONE1: PHONE1( DEPT#, OFF#, PHONE# ) DEPT# можно удалить совсем, поскольку отношение (DEPT#, OFF#) является проекцией отношения OFFICE2: OFFICE2( OFF#, DEPT#, AREA) PHONE1( OFF#, PHONE# ) Кроме того, PHONE#OFF#, поэтому в качестве первичного ключа можно принять только PHONE# с получением приведенного ниже отношения в 2НФ: PHONE2( PHONE#, OFF# ) PHONE2( PHONE#, OFF# ) EMP2( EMP#, DEPT#, PROJ#, OFF#, PHONE# ) Обратите внимание, что это отношение не обязательно является проекцией EMP2 (телефоны и кабинеты могут существовать и без соотнесения их с конкретными сотрудниками), поэтому его нельзя удалить. Таким образом, может быть получен следующий набор отношений в 2НФ: DEPT2( DEPT#, DBUDGET, MGR# ) EMP2( EMP#, DEPT#, PROJ#, OFF#, PHONE# ) SALHIST2( EMP#, DATE, JOBTITLE, SALARY ) PROJ2( PROJ#, DEPT#, PBUDGET ) OFFICE2( OFF#, DEPT#, AREA) PHONE2( PHONE#, OFF# ) Этап 3. Теперь, исключая транзитивные зависимости непервичных атрибутов, можно привести отношения, находящиеся в 2НФ, к эквивалентной совокупности отношений в 3НФ. (Какие отношения не находятся в 3НФ?) DEPT2( DEPT#, DBUDGET, MGR# ) EMP2( EMP#, DEPT#, PROJ#, OFF#, PHONE# ) SALHIST2( EMP#, DATE, JOBTITLE, SALARY ) PROJ2( PROJ#, DEPT#, PBUDGET ) OFFICE2( OFF#, DEPT#, AREA) PHONE2( PHONE#, OFF# ) F=( MGR#DEPT#, DEPT#DBUDGET, EMP#PROJ#, EMP#PHONE#, {EMP#,DATE}SALARY, PROJ#PBUDGET, OFF#AREA, DEPT#MGR#, EMP#DEPT#, EMP#OFF#, {EMP#,DATE}JOBTITLE, PROJ#DEPT#, OFF#DEPT#, PHONE#OFF# ) Единственным отношением, которое находится в 2НФ и не находится в 3НФ, является отношение EMP2 EMP2( EMP#, DEPT#, PROJ#, OFF#, PHONE# ) В нем существуют следующие транзитивные зависимости: 1) EMP#PHONE# PHONE#OFF# 2) EMP#PROJ# PROJ#DEPT# Приведем отношение EMP2 в 3НФ: Сначала удалим транзитивную зависимость OFF# от EMP# через PHONE# разложением EMP2 на два отношения: EMP21=(EMP#, DEPT#, PROJ#, PHONE#) с выделенным кдючом K1=(EMP#) EMP22=(PHONE#, OFF#) с выделенным ключом K2=(PHONE#) Схема EMP22 находится в 3НФ, а схема EMP21 – нет, так как атрибут DEPT# транзитивно зависит от EMP# через PROJ#. Разлагаем EMP21 на две следующие схемы: EMP211=(EMP#,PROJ#, PHONE#) с выделенным кдючом K11=(EMP#) EMP212=(DEPT#, PROJ#) с выделенным кдючом K12=(PROJ#) Теперь все схемы отношений находятся в следовательно, подсхема базы данных EMP3={ EMP211, EMP212, EMP22} также находится в 3НФ. EMP211=(EMP#,PROJ#, PHONE#) EMP212=(DEPT#, PROJ#) EMP22=(PHONE#, OFF#) 3НФ и, Однако отношение EMP22 – это аналог отношения PHONE2, EMP22=(PHONE#, OFF#) PHONE2( PHONE#, OFF# ) EMP212 – проекции PROJ2. EMP212=(DEPT#, PROJ#) PROJ2( PROJ#, DEPT#, PBUDGET ) Следовательно, их можно удалить, и данная совокупность отношений в 3НФ будет выглядеть следующим образом: DEPT3( DEPT#, DBUDGET, MGR# ) EMP3( EMP#,PROJ#, PHONE# ) SALHIST3( EMP#, DATE, JOBTITLE, SALARY ) PROJ3( PROJ#, DEPT#, PBUDGET ) OFFICE3( OFF#, DEPT#, AREA) PHONE3( PHONE#, OFF# ) Схема базы данных в 3НФ DEPT3( DEPT#, DBUDGET, MGR# ) EMP3( EMP#,PROJ#, PHONE# ) SALHIST3( EMP#, DATE, JOBTITLE, SALARY ) PROJ3( PROJ#, DEPT#, PBUDGET ) OFFICE3( OFF#, DEPT#, AREA) PHONE3( PHONE#, OFF# ) Наконец, каждое из этих отношений уже находится в НФБК. Следует отметить, что при некоторых (разумных) дополнительных семантических ограничениях этот набор отношений становится сильно избыточным, так как проекция отношения PROJ3 с комбинацией {PROJ#, DEPT#} является проекцией соединения отношений EMP3, PHONE3, OFFICE3. Синтез B-схемы базы данных Определение. Пусть   { R , R ,  , R } - декомпозиция схемы R. Отношение r(R) удовлетворяет зависимости соединения (J– зависимости) * [ R1 , R 2 ,  , R m ] , если r разлагается без потерь на R 1 , R 2 ,  , R m , то есть r   R1 (r )   R2 (r )     Rm (r ) . Вместо * [ R 1 , R 2 ,  , R m ] принято также писать * [  ] . Следует отметить, что в общем случае 1 r ( R )   2 m i  1 m  (r) R . i Пусть F – множество ФЗ, заданных на атрибутах схемы R, и   { R 1 , R 2 ,  , R m } - декомпозиция схемы R. Определение. Говорят, что декомпозиция  удовлетворяет J – зависимости относительно F, если зависимость * [  ] имеет место для любого отношения r(R), удовлетворяющего всем ФЗ из F. Это свойство декомпозиции принято также называть свойством соединения без потерь информации относительно F и обозначать так: F  * [  ] .  Определение . Декомпозиция схемы отношения R сохраняет множество ФЗ F, если   R ( F )  F . Если полагать, что R – множество имен всех атрибутов, значения которых подлежат хранению в базе данных, то любая   { R i , i  1,..., m } множества R декомпозиция определяет некоторую схему реляционной БД. m i 1 i Определение. Схема   { R i , i  1,..., m } реляционной БД называется эффективной относительно F, если она находится в НФБК, обладает свойством соединения без потерь и сохраняет F. Свойства эффективной схемы БД являются формализованным представлением критериев качества схемы БД, обеспечивающих выполнение таких требований к БД, как непротиворечивость, неизбыточность данных, простота актуализации. Однако при заданном множестве ФЗ F над R не всегда можно найти декомпозицию в НФБК, сохраняющую зависимости из F. Это возможно только для 3НФ, о чем свидетельствует следующая теорема. Теорема 5. Для любого множества ФЗ F  {X  Y / X Y  R, i  1, 2,, m}, заданного на конечном множестве атрибутов R  {A , A ,, A } , всегда существует декомпозиция   { R , R , , R /  R  R} , обладающая свойством соединения без потерь относительно F, сохраняющая все ФЗ из F (   ( F )  F ) и находящаяся в 3НФ относительно F. i i 1 i i 2 n m 1 2 m i 1 i m i 1 Ri Определение. Схему БД, удовлетворяющую условиям теоремы 5, называют B-схемой. Суть методов синтеза схемы БД сводится к следующим основным действиям. Вначале выполняются эквивалентные преобразования заданного множества F (удаление избыточных ФЗ, редуцирование и тому подобное). Затем осуществляется синтаксическое разложение R согласно структуре множества F, то есть каждой схеме из  ставится в соответствие одна или несколько ФЗ из F . Рассмотрим теоремы, указывающие пути проверки для заданной декомпозиции   { R i , i  1,..., m } свойства F  * [  ] . Теорема 6. Для   { R1 , R 2 } свойство F  * [ R1 , R 2 ] имеет место тогда и только тогда, когда выполнено одно из следующих условий F  R1  R 2  R1 или F  R1  R 2  R 2 . Теорема 7. Если декомпозиция   { R i , i  1,..., m } сохраняет F, то F  * [  ] тогда и только тогда, когда существует хотя бы одна схема R i   такая, что R i  K , где K - ключ схемы R относительно F. Область применения теорем 6, 7 весьма ограничена, поскольку теорема 6 применима лишь для случая, когда   { R1 , R 2 } , а теорема 7, когда  сохраняет F. В теории реляционных БД известен универсальный метод проверки для   { R i , i  1,..., m } свойства F  * [  ] , который носит название метод прогонки табло. Суть метода заключается и следующем. Пусть заданы: R  { A , A ,..., A n } - конечное множество имён атрибутов; 1 2   { R i , i  1,..., m } - декомпозиция схемы; F - множество ФЗ, заданных на атрибутах схемы R. Вначале строится табло T  {t ij } ( таблица с m строками и n столбцами) по следующим правилам: 1) столбец j соответствует атрибуту A j  R , а строка i – схеме Ri   ; , если Ai  R i . В противном случае t ij  b ij . Символы a j называются выделенными, а b ij невыделенными переменными. Далее осуществляются преобразования T согласно зависимостям { X  Y }  F до тех пор, пока они не перестанут изменять T. Преобразование T согласно X  Y заключается в следующем: 1) выполняется поиск строк, которые совпадают по всем столбцам, соответствующим атрибутам из X; 2) при обнаружении двух таких строк осуществляется отождествление их символов, находящихся в столбцах Y. Если при этом один из отождествляемых символов равен a j , то и 2) t ij  a j другой приравнивается a j . В том случае, когда они равны b ij и b ( i  l ) , то blj заменяется на b . lj ij Пусть charse F (T ) - результат преобразования T указанным выше способом. Справедлива следующая теорема. Теорема 8. Для заданных R,  и F свойство F  * [  ] имеет место тогда и только тогда, когда charse (T ) содержит строку a , a ,..., a n (выделенных переменных). 1 2 F Алгоритм синтеза В – схемы По теореме 5 для любого множества ФЗ F, заданного на конечном множестве атрибутов R, всегда существует В–схема – декомпозиция   { R i , i  1,..., m } , обладающая свойствами: 1) соединения без потерь информации относительно F ( F  * [  ]) ; m 2) сохранения всех ФЗ из F  i  1  (F )  F R i  F . 3) ЗНФ относительно F. Эта декомпозиция может быть построена с помощью алгоритма SYNTES. Алгоритм SYNTES(R, F) . Вход: R – множество атрибутов; F - множество ФЗ над R. Выход:   { R i , i  1,..., m } - искомая В-схема. Описание алгоритма 1. Редуцирование F. Этот шаг гарантирует ЗНФ для  . Пусть F '  { X i  Yi X i , Yi  R , i  1,..., m} - результат редуцирования. 2. Проверка условия: существует X i  Y i  F ' такая, что X i  Yi  R ? 3. Если да, то процесс построения искомой В – схемы завершён и она имеет вид:   {R } , т.е. множество R не подлежит разложению на две и более схемы. 4. Если нет, то выполняется синтаксическое разложение R по F’ (разложение по ФЗ из F’) следующим образом:  '  { R1 ( X 1Y1 ),..., R m ( X m Y m ) } , т.е. каждой ФЗ X i  Y i  F ' соответствует схема Ri с атрибутами X i  Y i (i  1,..., m ) . Этот шаг гарантирует выполнение выводимости 5. Проверка свойства выводимость F '  * [  ' ] поскольку F '  F . m  R i 1 (F ')  F i F '  *[ '] (сохранение всех ФЗ из F). методом прогонки табло. Здесь эквивалентна выводимости F  * [  ' ] , 6. Если метод прогонки табло завершился успешно, то по теореме 8 F '  * [  ' ] и искомая В – схема определяется как:   '. 7. Если нет, то выполняется поиск K–ключа множества R относительно F’ с использованием алгоритмов редуцирования. 8. Искомая В – схема определяется так    '{ R m  1 ( K )} , т.е. к  ' добавляется схема, содержащая все атрибуты найденного ключа. Это гарантирует (согласно теореме 7) выполнение свойства F '  * [  ] . Примечание к шагу 7. Алгоритмы редуцирования применяются к множеству F ' { R  C } , где R  C есть фиктивная ФЗ и C  R . После редуцирования ФЗ R  C преобразуется в зависимость K  C , где K – ключ множества R относительно F’. Алгоритм SYNTHES имеет конечное число шагов все они выполняются с полиномиальной сложностью. Пример: R=ABCD, F  { AD  C , CD  A, B  D} Описание алгоритма 1. Редуцирование F: F  {AD  C, CD  A, B  D} 2. Проверка условия: существует X i  Y i  F ' такая, что X i  Yi  R ? 4. Если нет, то выполняется синтаксическое разложение R по F’ (разложение по ФЗ из F’) следующим образом:  '  { R1 ( X 1Y1 ),..., R m ( X m Y m ) } , т.е. каждой ФЗ X i  Y i  F ' соответствует схема R i с атрибутами X i  Y i ( i  1,..., m ) . После разложения:   {R ( ACD), R (BD)} 1 2 5. Проверка свойства F '  *[ '] методом прогонки табло. F  { AD  C , CD  A, B  D} A B C D R1 a1 b12 a3 a4 R2 b21 a2 b23 a4 Метод прогонки табло неуспешен. 7. F '  { AD  C , CD  A, B  D}  { ABCD  E } После редуцирования получаем K={BC} Следовательно, схема базы данных в НФБК   {R1 ( ACD), R2 ( BD), R3 ( BC )} Примеры для самостоятельной проработки Номер Примера 1 2 3 4 5 6 Исходные данные: R – множество атрибутов, F – неизбыточное множество ФЗ Результат В – схема R=ABCD,   {R( ABCD)} F  { AB  CD, C  B} . 3НФ R=ABCD,   {R1 ( AB), R2 ( BC ), R3 ( AD)} F  { A  B, B  C} . НФБК R=ABCD,   {R1 ( ABC ), R2 (CD)} F  { A  B, A  CD, C  D} . НФБК R=ABCD,   {R1 ( ACD), R2 ( BD), R3 ( BC )} НФ F  { AD  C , CD  A, B  D} . БК R=ABCD,   {R1 ( ABC ), R2 ( BCD)} F  { A  BC , BC  D, D  C} . 3НФ R=ABCD,   {R ( ABCD )} F  { A  BD, AB  CD} . НФБК Задания для самостоятельной проработки 1. В базе данных системы учета заказов содержится информация о клиентах, товарах и заказах согласно приведенному ниже плану. Для каждого клиента: номер клиента (уникальный); адрес доставки (несколько для каждого клиента); баланс; максимальный размер кредита; скидка. Для каждого заказа: информация заголовка: номер клиента, адрес доставки, дата выполнения заказа; строки данных (несколько для каждого заказа): номер товара, количество данного товара. Для каждого товара: номер товара (уникальный); заводыизготовители; количество товара на каждом заводе;максимальное количество хранимого товара на каждом заводе; описание товара. Для внутреннего учета также вводится величина “количество для доставки”, связанная с каждой строкой каждого заказа. Эта величина сначала устанавливается равной количеству заказанного товара, а после выполнения поставки обнуляется. Составьте макет такой базы данных, а также, как и в предыдущем упражнении, укажите семантические утверждения на основе заданных ФЗ. 2. Предположим, что в упражнении 1 только очень малая часть клиентов, например процент или даже меньше, имеют больше одного адреса доставки. Каковы в таком случае недостатки решения, предложенного для упражнения 1 ? Какие усовершенствования можно внести для их устранения. 3. (Модифицированная версия) Отношение TIMEPLANE определется следующими атрибутами: D – день недели (1-5); P – период времени в течении дня (1-8); C – номер аудитории; T – имя преподавателя; S – имя студента; L – название урока; Кортеж {d, p, c, t, l} является элементом этого отношения тогда и только тогда, огда в момент времени {d, p} некоторый студент s посещает урок l, который преподается учителем t в аудитории c. Можно предположить, что урок имеет длительность одного периода, а каждый урок имеет название, уникальное по отношению ко всем другим урокам данной недели. Сведите отношение TIMEPLANE к более приемлимой структуре. 4. (Модифицированная версия) Дано отношение NADDR с атрибутами NAME (уникальное имя), STREET, CITY, STATE и ZIP. Причем каждому почтовому индексу соответствует толко один город и штат, каждой улице, городу и штату – только один почтовый индекс. Находится ли отношение NADDR в НФБК, ЗНФ, 2НФ? Можно ли создать для этого отношения улучшенный макет?