Объясните в чем разница между детерминантом и возможным ключом отношения
Методы проектирования логических моделей реляционных баз данных. Декомпозиция и синтез отношений
Методы проектирования на основе декомпозиции отношений
Понятие о методах декомпозиции отношений
Предположим, что схема базы данных содержит F-зависимости. Из положений теории о F-зависимостях следует, что если отношения базы данных находятся в нормальной форме Бойса-Кодда (НФБК), то проектирование логической модели базы данных можно считать завершенным в этом классе зависимостей. Как видно, теория дает полезный (!) критерий останова проектирования.
Сформулируем наглядный критерий, позволяющий определить, находится ли отношение в НФБК. Для этого введем следующее вспомогательное понятие.
Определение 3. Пусть дана ФЗ:
и В функционально не зависит от любого подмножества А, тогда А называется детерминантом В.
и В функционально не зависит от любого подмножества А, тогда А называется детерминантом В.Детерминантами в отношениях являются атрибуты левых частей ФЗ. Возможные ключи (см. учебный элемент » Реляционная модель данных «) идентифицируются путем нахождения минимального множества значений атрибутов, которые определяют значения всех остальных атрибутов в отношении. Напомним понятие возможного ключа отношения как атрибута или атрибутов данного отношения, который (-ые) могут быть в данном отношении выбраны в качестве первичного.
Тогда критерий Кодда, позволяющий определить, находится ли отношение в НФБК, может быть сформулирован следующим образом:
Таким образом, при декомпозиции отношений необходимо строить списки возможных ключей и детерминантов и сравнивать их на совпадение. Устранив таким образом большинство потенциальных аномалий, проектирование можно завершить.
Алгоритм метода декомпозиции отношений
Алгоритм метода декомпозиции отношений
Уточним некоторые аспекты метода декомпозиции.
Если
то в качестве ФЗ для осуществления проекции используется крайняя правая зависимость или «конец цепочки» 
Методы проектирования на основе синтеза отношений
Некоторые проблемы метода декомпозиции
Первая ситуация: в процессе декомпозиции потеряна ФЗ 
и если отношения R1 и R2 будут использованы для создания базы данных, то нельзя гарантировать, что связи между этими атрибутами будут внесены в БД корректно. Отсюда вытекает второе эмпирическое правило выбора ФЗ для выполнения проекции: не следует использовать ФЗ в качестве ФЗ для осуществления проекции, если ее левая часть является детерминантом другой ФЗ. Эта проблема разрешается путем применения правила цепочки.
Прежде чем перейти к изучению метода синтеза, рассмотрим использование элементов синтеза в декомпозиции. Как можно было заметить, декомпозиция осложняется при наличии транзитивных ФЗ. Особенностью транзитивной ФЗ является ее избыточность. ФЗ принято считать избыточной, если она содержит в себе информацию, которая может быть получена из других ФЗ базы данных. Исключение избыточной транзитивной ФЗ из базы данных может быть выполнено без отрицательного воздействия на ее результаты. Избыточность присуща не только транзитивным ФЗ и, следовательно, избыточные ФЗ желательно исключать до применения алгоритма декомпозиции.
Понятие о методах синтеза отношений
Исключить избыточность в исходном наборе ФЗ можно путем применения правил вывода ФЗ (См. учебный элемент » Функциональные зависимости «). Как известно, для класса F-зависимостей достаточно использовать шесть таких правил. При этом критерием останова процедуры исключения может служить получение минимального покрытия исходного набора ФЗ.
Неединственность минимальных покрытий указывает на то, что порядок исключения избыточных ФЗ может оказать влияние на полученные результаты. Отсюда следует эмпирическое правило:
Избыточные ФЗ следует удалять по одной, каждый раз проводя анализ полученного набора ФЗ на избыточность.
Первое. Если универсальное отношение содержит большое количество атрибутов, например более трех десятков, то ручное проектирование становится трудоемким и может, с одной стороны, привести к большим временным затратам, а с другой стороны, породить недопустимое для практики число отношений в базе данных. Поэтому в данном случае следует подумать об автоматизации процесса проектирования, т.е. создать программу проектирования схем баз данных.
Кроме того, задача приведения исходных отношений к НФБК может оказаться невыполнимой. Такой факт имел место в практике проектирования. Поскольку НФБК может не существовать на заданном наборе ФЗ, то логичным было бы отказаться от требования приведения отношений базы данных к этой форме. Эта ситуация подкрепляется и теоретически: при любом заданном множестве F-зависимостей над схемой r БД можно построить схему БД в 3НФ.
Таким образом, ограничимся поиском 3НФ в ходе применения метода синтеза, при этом остаются проблемы, связанные с выполнением операций над данными.
Методы проектирования логических моделей реляционных баз данных. Декомпозиция и синтез отношений
Методы проектирования на основе декомпозиции отношений
Понятие о методах декомпозиции отношений
Предположим, что схема базы данных содержит F-зависимости. Из положений теории о F-зависимостях следует, что если отношения базы данных находятся в нормальной форме Бойса-Кодда (НФБК), то проектирование логической модели базы данных можно считать завершенным в этом классе зависимостей. Как видно, теория дает полезный (!) критерий останова проектирования.
Сформулируем наглядный критерий, позволяющий определить, находится ли отношение в НФБК. Для этого введем следующее вспомогательное понятие.
Определение 3. Пусть дана ФЗ:
Детерминантами в отношениях являются атрибуты левых частей ФЗ. Возможные ключи (см. учебный элемент » Реляционная модель данных «) идентифицируются путем нахождения минимального множества значений атрибутов, которые определяют значения всех остальных атрибутов в отношении. Напомним понятие возможного ключа отношения как атрибута или атрибутов данного отношения, который (-ые) могут быть в данном отношении выбраны в качестве первичного.
Тогда критерий Кодда, позволяющий определить, находится ли отношение в НФБК, может быть сформулирован следующим образом:
Таким образом, при декомпозиции отношений необходимо строить списки возможных ключей и детерминантов и сравнивать их на совпадение. Устранив таким образом большинство потенциальных аномалий, проектирование можно завершить.
Алгоритм метода декомпозиции отношений
Алгоритм метода декомпозиции отношений
Уточним некоторые аспекты метода декомпозиции.
Если
Методы проектирования на основе синтеза отношений
Некоторые проблемы метода декомпозиции
Первая ситуация: в процессе декомпозиции потеряна ФЗ и если отношения R1 и R2 будут использованы для создания базы данных, то нельзя гарантировать, что связи между этими атрибутами будут внесены в БД корректно. Отсюда вытекает второе эмпирическое правило выбора ФЗ для выполнения проекции: не следует использовать ФЗ в качестве ФЗ для осуществления проекции, если ее левая часть является детерминантом другой ФЗ. Эта проблема разрешается путем применения правила цепочки.
Прежде чем перейти к изучению метода синтеза, рассмотрим использование элементов синтеза в декомпозиции. Как можно было заметить, декомпозиция осложняется при наличии транзитивных ФЗ. Особенностью транзитивной ФЗ является ее избыточность. ФЗ принято считать избыточной, если она содержит в себе информацию, которая может быть получена из других ФЗ базы данных. Исключение избыточной транзитивной ФЗ из базы данных может быть выполнено без отрицательного воздействия на ее результаты. Избыточность присуща не только транзитивным ФЗ и, следовательно, избыточные ФЗ желательно исключать до применения алгоритма декомпозиции.
Понятие о методах синтеза отношений
Исключить избыточность в исходном наборе ФЗ можно путем применения правил вывода ФЗ (См. учебный элемент » Функциональные зависимости «). Как известно, для класса F-зависимостей достаточно использовать шесть таких правил. При этом критерием останова процедуры исключения может служить получение минимального покрытия исходного набора ФЗ.
Неединственность минимальных покрытий указывает на то, что порядок исключения избыточных ФЗ может оказать влияние на полученные результаты. Отсюда следует эмпирическое правило:
Избыточные ФЗ следует удалять по одной, каждый раз проводя анализ полученного набора ФЗ на избыточность.
Первое. Если универсальное отношение содержит большое количество атрибутов, например более трех десятков, то ручное проектирование становится трудоемким и может, с одной стороны, привести к большим временным затратам, а с другой стороны, породить недопустимое для практики число отношений в базе данных. Поэтому в данном случае следует подумать об автоматизации процесса проектирования, т.е. создать программу проектирования схем баз данных.
Кроме того, задача приведения исходных отношений к НФБК может оказаться невыполнимой. Такой факт имел место в практике проектирования. Поскольку НФБК может не существовать на заданном наборе ФЗ, то логичным было бы отказаться от требования приведения отношений базы данных к этой форме. Эта ситуация подкрепляется и теоретически: при любом заданном множестве F-зависимостей над схемой r БД можно построить схему БД в 3НФ.
Таким образом, ограничимся поиском 3НФ в ходе применения метода синтеза, при этом остаются проблемы, связанные с выполнением операций над данными.
Детерминанты и их роль в базе данных
Детерминанты определяют значения, присвоенные другим атрибутам
Определитель в таблице базы данных – это атрибут, который можно использовать для определения значений, присвоенных другим атрибутам в той же строке. По этому определению любой первичный ключ или ключ-кандидат является определителем, но могут быть детерминанты, которые не являются первичными или потенциальными ключами.
Например, компания может использовать таблицу с атрибутами, и.
| Меган | Коричневый | 01/29/1979 | ||||||||||||||||||||||||
| 234 | Бен | Уайлдером | 02/14/1985 | |||||||||||||||||||||||
| 345 | Меган | Chowdery | 2/14/1985 | |||||||||||||||||||||||
| 456 | Charles | Коричневый | 07/19/1984 В этом случае поле определяет оставшиеся три поля. Поля имени не определяют, потому что у фирмы могут быть сотрудники, которые имеют то же самое имя или фамилию. Точно так же поле не определяет поля или названия, потому что сотрудники могут иметь один и тот же день рождения. Детерминантные отношения с ключами базы данных В этом примере это определитель, ключ-кандидат, а также первичный ключ. Это ключ-кандидат, потому что при поиске 234 во всей базе данных появляется строка, содержащая информацию о Бене Уайлдере, и другие записи не отображаются. Другой ключ-кандидат возникает при поиске в базе данных по информации в трех столбцах; и, который также получает тот же результат. Это первичный ключ из-за всех комбинаций столбцов, которые можно использовать в качестве ключа-кандидата, это самый простой столбец для использования в качестве основной ссылки на эту таблицу. Кроме того, она гарантированно уникальна для этой таблицы, независимо от количества других сотрудников, в отличие от информации в других столбцах. Возможный ключ и детерминантВозможный ключ. Возможный ключ представляет собой атрибут или набор атрибутов, который может быть использован для данного отношения в качестве первичного ключа. Первичный ключ всегда является возможным ключом; однако не исключено наличие других возможных ключей, которые могли бы быть, но не были использованы в качестве первичного ключа. Таким образом, если известны значения атрибутов данного возможного ключа, то значения всех других атрибутов кортежа, содержащего указанный возможный ключ, будут однозначно определены. Детерминанты заключены в угловые скобки для того, чтобы в данном случае выделить четыре различных детерминанта. Следует заметить, что взаимные зависимости дают два детерминанта. Коддом доказано, что большинство потенциальных аномалий в БД будет устранено в случае должной декомпозиции каждого отношения в нормальную форму Бойса-Кодда (НФБК), которая определяется следующим образом: Отношение находится в НФБК, если каждый детерминант отношения является возможным ключом. Отношение УСПЕВАЕМОСТЬ не находится в НФБК. Это легко обнаружить, если расположить рядом перечень всех детерминантов и перечень всех возможных ключей и посмотреть, является ли каждый детерминант возможным ключом. Возможные ключи Детерминанты Поскольку не каждый детерминант в отношении УСПЕВАЕМОСТЬ является возможным ключом, следовательно оно не находится в НФБК и его необходимо подвергнуть декомпозиции. Общий подход к декомпозиции В общем виде алгоритм проектирования БД может выглядеть следующим образом: 1. Разработка универсального отношения для БД. 2. Определение всех ФЗ между атрибутами отношения. 3. Определение того, находится ли отношение в НФБК. Если да, проектирование завершается; если нет, отношение должно быть разложено на два отношения. 4. Повторение шагов 2 и 3 для каждого нового отношения, полученного в результате декомпозиции. Проектирование завершается, когда все отношения будут находится в НФБК. Предложенный алгоритм не определяет, как осуществлять декомпозицию отношения, не приведенного к НФБК, на два отношения. Это осуществляется с помощью ФЗ следующим образом. Создается два новых отношения: R1(A,B,C,E. ) и R2(C,D), где зависимостная часть ФЗ была выделена из R и опущена при формировании отношения R1 и ФЗ была использована полностью при формировании отношения R2. Теперь необходимо проверить, находятся ли в НФБК отношения R1 и R2. Про отношение R2(C,D) говорят, что одно является проекцией отношения R. Этот тип декомпозиции называется декомпозицией без потерь при естественном соединении. Указанный метод декомпозиции может быть использован на шаге 3 приведенного выше алгоритма проектирования. На этом этапе должно быть принято решение, какую ФЗ следует выбрать для проведения первой проекции. Не исключено, что в итоге выбора той или иной начальной проекции будут получены различные БД. Если это именно так, то каждая из получившихся БД должна быть подвергнута анализу с целью выбора наиболее полно отвечающей требованиям и условиям пользователя. R1(Cном, Дисц, Семестр, Сфам, Кном, Оценка) Возможные ключи Детерминанты Возможные ключи Детерминанты Рис.11. Отношения R1 и R2 получены в результате проекции Кном Тном из отношения УСПЕВАЕМОСТЬ. Отношение R2(Кном, Тном) находится в НФБК, поскольку все его детерминанты являются возможными ключами и оно не нуждается более в декомпозиции. Первичным ключом отношения R2 могут быть как Кном, так и Тном. Отношение R1 не находится в НФБК, т.к. детерминант не является возможным ключом. Следовательно отношение R1 необходимо подвергнуть дальнейшей декомпозиции. Проекция отношения R1, порождаемая этой ФЗ приводит к получению отношений R3 и R4, показанных на рис.12. Эти два отношения находятся в НФБК и вместе с отношением R2 могут использоваться при формировании БД для учета успеваемости. Возможные ключи Детерминанты Возможные ключи Детерминанты Рис.12. Отношение R3 и R4 полученные в результате проекции На рис.13 представлен окончательный вид отношений для такой БД (названной УСПЕХИ), а также экземпляры каждого отношения с данными, совпадающими с использованными для исходного отношения УСПЕВАЕМОСТЬ. Заметим, в частности, что в процессе декомпозиции автоматически произошло разбиение исходного отношения УСПЕВАЕМОСТЬ на три логических компонента: R2, в котором содержится информация о комнатах и телефонах; R3, в котором содержится информация об учебных дисциплинах и полученных студентами оценках; R4, в котором содержится информация о студентах. Такое логическое разбиение является прямым результатом использования в процессе декомпозиции заложенной в ФЗ информации, детализирующей то, как различные атрибуты в исходном отношении соотносятся друг с другом.
Анализ исходных аномалий Зададимся вопросом: присутствует ли в БД УСПЕХИ те же аномалии, которые характеризовали отношение УСПЕВАЕМОСТЬ, или декомпозиция автоматически привела к их устранению? Для того, чтобы подтвердить устранение аномалий, а именно эта цель ставилась в первую очередь при осуществлении декомпозиции, рассмотрим, опираясь на приведенную на рис.13 БД УСПЕХИ, проблемы вставки, удаления и обновления. Вставка. Когда отношение УСПЕВАЕМОСТЬ служило основой БД, новый студент не мог быть в нее включен до действительного завершения им хотя бы одного семестра. В БД УСПЕХИ информация общего характера о студентах хранится в отношении R4. Как только новый студент принимается в институт и ему отводится комната, так этот студент может быть включен в БД (в R4). Студенту даже нет необходимости просто приступить к посещению занятий для того, чтобы быть включенным в БД. Таким образом, исходная аномалия вставки исключена с помощью декомпозиции. Обновление. В исходном отношении УСПЕВАЕМОСТЬ попытка изменить номер телефона Серова, проживающего в комнате 120 может привести к тому, что в БД появится два различных телефонных номера, установленного в комнате 120. В БД УСПЕХИ телефонные номера располагаются в отношении R2 и каждая комната может иметь только один телефонный номер. Следует помнить, что Кном является первичным ключом отношения R2, а значения первичного ключа по определению должны быть уникальными. Для изменения телефонного номера Серова следует в кортеже отношения R2, в котором Кном=120, изменить номер Тном. При этом будет изменен номер телефона для всех студентов, живущих в этой комнате. Таким образом, исходная аномалия обновления устраняется с помощью НФБК-проектирования. Необходимо еще раз подчеркнуть, что устранение аномалии обновления базируется на том положении, что СУБД, в среде которой будет создаваться БД, не допускает дублирования значений первичных ключей. Ключ отношенияПерви́чный ключ (англ. primary key ) — понятие теории реляционных баз данных, минимальное множество атрибутов, являющееся подмножеством заголовка данного отношения, составное значение которых уникально определяет кортеж отношения. На практике термин первичный ключ обозначает поле (столбец) или группу полей таблицы базы данных, значение которого (или комбинация значений которых) используется в качестве уникального идентификатора записи (строки) этой таблицы. СодержаниеСмыслВ теории реляционных баз данных таблица представляет собой изначально неупорядоченный набор записей. Единственный способ идентифицировать определённую запись в этой таблице — это указать набор значений одного или нескольких полей, который был бы уникальным для этой записи. Отсюда и происходит понятие первичного ключа — набора полей (атрибутов, столбцов) таблицы, совокупность значений которых определена для любой записи (строки) этой таблицы и различна для любых двух записей. ИспользованиеПервичный ключ в таблице является базовым уникальным идентификатором для записей. Значение первичного ключа используется везде, где нужно указать на конкретную запись. На использовании первичных ключей основана организация связей между таблицами реляционной БД. Чтобы организовать между двумя таблицами связь типа «один к одному» или «один ко многим(многие к одному)» в одну из связываемых таблиц добавляют поле (поля), содержащее(ие) значение первичного ключа записи в связанной таблице (такое поле называют внешним ключом). Для организации связи типа «многие ко многим» создают отдельную таблицу (так называемую «таблицу связи» или «таблицу ассоциации»), каждая запись которой содержит первичные ключи двух связанных записей в разных таблицах. КлассификацияПростые и составные ключиПервичный ключ может состоять из единственного поля таблицы, значения которого уникальны для каждой записи. Так, например, на предприятии не может быть двух работников с одинаковыми табельными номерами, поэтому в таблице, содержащей записи о работниках, табельный номер может быть первичным ключом. Такой первичный ключ называют простым ключом. Естественные и суррогатные ключиПервичный ключ может состоять из информационных полей таблицы (то есть полей, содержащих полезную информацию об описываемых объектах). Такой первичный ключ называют естественным ключом. Теоретически, естественный ключ всегда можно сформировать, в этом случае мы получим т. н. интеллектуальный ключ. На практике, однако, использование естественных ключей наталкивается на определённые сложности: Вследствие этих и других соображений в практике проектирования БД чаще используют т. н. синтетические (суррогатные) ключи — искусственно созданные технические ключевые поля, не несущие информации об объектах.
|