Сибилев В.Д. Модели и проектирование баз данных

Подождите немного. Документ загружается.

S#  Sn; P#  Pn; J#  Jn; A  SСi; A  Co; A Qt.

S#  St; P#  We; J#  JCi; A  St; A  PCi; A Sn,

S#  SСi; P#  Co; A  Pn; A  Jn; A  St;

SCi  St; P#  PCi; A  We; A  JCi;

Здесь обозначено A = {S#, P#, J#, Dt} и исключены

тривиальные зависимости типа A  S#.

Единственным потенциальным ключом этого отношения

является подмножество А. От потенциального ключа неприводимо

зависит единственный атрибут – Qt. Все прочие атрибуты зависят еще

и от различных подмножеств потенциального ключа. Кроме того, есть

ФЗ между неключевыми атрибутами (SCi  St). Зависимости от

подмножеств потенциального ключа обусловливают отмеченные в

реализации группы повторения вида (P1, гайка, К, 10, Ош). Группы

повторения вида (50, Яя) обусловлены наличием ФЗ SCi  St.

Декомпозиция универсального отношения. Очевидный выход,

избавляющий от избыточного дублирования данных, состоит в

расщеплении (декомпозиции) отношения USPJ на четыре

взаимосвязанных отношения – S, P, J, SPJ. Каждое из этих

отношений является проекцией USPJ на соответствующие группы

атрибутов

S = (USPJ[S#, Sn, St, Sci]) RENAME SCi AS Ci;

P = (USPJ[P#, Pn, Co, We, PCi]) RENAME Pci AS Ci;

J = (USPJ[J#, Jn, Jci]) RENAME Jci AS Ci;

SPJ = USPJ[S#, P#, J#, Dt, Qt];

Ниже приведены значения этих отношений для

рассматриваемого примера.

S P

S# Sn St Ci P# Pn Co We Ci

S1 Иван 50 Яя P3 шайба Ж 20 Ош

S2 Петр 100 Ош , P1 гайка К 10 Яя ,

S3 Джон 50 Яя P8 болт Ч 30 Яя

S8 Боб 50 Томск P2 винт С 40 Ош

Легко заметить, что эти отношения соответствуют интуитивно выделяемым

объектам ПО.

103

J SPJ

J# ... S# P# J# Qt Dt

J1 ... , S1 P3 J1 1000...

J2 ... S1 P1 J1 1000...

S1 P8 J1 500...

S2 P3 J2 1000... ,

S3 P2 J2 2000...

S3 P1 J2 1000...

S8 P8 J2 500…

Нетрудно убедиться в том, что в этих отношениях сохранены

все отмеченные ФЗ. Естественное соединение этих проекций

USPJ = (((((SPJ JOIN S) RENAME Ci AS Sci)

JOIN P) RENAME Ci AS Pci)

JOIN J) RENAME Ci AS Jci;

восстановит универсальное отношение без всяких потерь информации.

Кроме того, в этой структуре объявлены все ФЗ, за исключением S.Ci 

St.

Здесь нет аномалий удаления. Из отношения SPJ можно

удалять кортежи без проблем. При удалении кортежей других

отношений достаточно соблюдать правила ссылочной целостности,

которые объявлены определениями отношений (см. п. 2.4.2). Нет

также аномалий вставки типа б). Сведения о непоставлявших

поставщиках, непоставлявшихся деталях и о не получавших поставок

изделиях можно заносить в соответствующие отношения.

Аномалии вставки типа а) и обновления значений сохраняются

для отношения S. Это обусловлено наличием необъявленной ФЗ

между неключевыми атрибутами S.Ci  St.

Можно попытаться избавиться от цепочки транзитивных

зависимостей S#  Ci  St, заменив S его проекциями. При этом не

должны быть потеряны ФЗ, и естественное соединение проекций

должно восстанавливать исходное отношение. Для иллюстрации

проблем, которые здесь могут возникнуть, рассмотрим возможные

варианты декомпозиции.

104

Вариант 1.

SST= S[S#, Sn, St]; CS=S[S#, Ci];

Эти проекции для реализации USPJ, приведенной в п. 3.1.2,

имеют вид:

SST CS

S# Sn St S# Ci

S1 Иван 50

;

S1 Яя

S2 Петр 100 S2 Ош

S3 Джон 50 S3 Яя

S8 Боб 50 S8 Томск

Их естественное соединение по атрибуту S#:

SST JOIN CS

S# Sn St Ci

S1 Иван 50 Яя

S2 Петр 100 Ош

S3 Джон 50 Яя

S8 Боб 50 Томск

совпадает с отношением S.

Здесь сохранены ФЗ S#  Сi, S#  St, S#  Sn. Однако

зависимость Ci  St утрачена. Значения атрибутов Ci и St в проекциях

можно менять независимо.

Вариант 2.

SST = S[S#, Sn, St]; STC = S[St, Ci];

Это плохой вариант. Здесь утеряна зависимость S#  Ci.

Поэтому возможна потеря информации при восстановлении исходного

отношения. В самом деле, эти проекции имеют вид:

SST STC

S# Sn St St Ci

S1 Иван 50 50 Яя

S2 Петр 100 100 Ош

S3 Джон 50 50 Томск

S8 Боб 50

Естественное соединение этих отношений будет содержать

105

лишние кортежи:

SST JOIN STC

S# Sn St Ci

S1 Иван 50 Яя

S2 Петр 100 Ош

S3 Джон 50 Яя

S1 Иван 50 Томск

S3 Джон 50 Томск

Это совсем не похоже на исходное отношение. Мало того, что в

нем появились ложные кортежи. Атрибут S# утратил свойство

потенциального ключа. Это следствие того, что общие атрибуты

отношений STS, STC не являются их потенциальными ключами.

Вариант 3.

SC = S[S#, Sn, Ci]; CS=S[Ci, St];

Эти проекции имеют вид:

SC CS

S# Sn Ci St Ci

S1 Иван Яя 50 Яя

S2 Петр Ош 100 Ош

S3 Джон Яя 50 Томск

S8 Боб Томск

Здесь не потеряна ни одна из ФЗ, существующих в исходном

отношении. В самом деле, S#  Sn и S#  Сi, так как S# – первичный

ключ отношения SC. Зависимость S#  St также неявно существует.

Каждому конкретному значению S# соответствует единственное значение

Ci, которому в свою очередь соответствует единственное значение St.

Следовательно, конкретному значению S# соответствует единственное

значение St.

Естественное соединение SC и CS будет происходить без

потерь информации, то есть в результате соединения не появятся

кортежи, которых не было в исходном отношении. Это следствие того,

что Ci – общий атрибут SC и CS, является потенциальным ключом

CS. Каждому значению Ci соответствует единственный кортеж CS,

106

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

кортежами SC и образовывать, таким образом, только те кортежи,

которые его породили при выполнении проекции S[Ci, St].

ФЗ в декомпозированной структуре. В структуре БД,

состоящей из отношений SC, P, J, SPJ, CS объявлены

следующие ФЗ:

S#  Sn; P#  Pn; J#  Jn; A  Qt; S.Ci  St.

S#  St; P#  We; J#  J.Ci;

S#  S.Сi; P#  Co;

P#  P.Ci;

Из них выводятся все остальные ФЗ, указанные в п.11.3.1.

Например, поскольку атрибут S# принадлежит множеству A и

является детерминантом ФЗ S#  S.Сi, то A  S.Ci.

Во всех отношениях этой структуры имеются только

объявленные ФЗ. Именно, каждый неключевой атрибут любого

отношения функционально зависит только от полного возможного

ключа. Аномалии обновления данных в этой структуре невозможны.

3.3 Нормальные формы отношений

То, что мы проделали с отношением USPJ, называется

процедурой нормализации. Цель нормализации – преобразовать

универсальное отношение в систему отношений, удовлетворяющих

определенным формальным требованиям. При обновлении данных,

хранящихся в такой системе отношений, не возникают аномальные

ситуации, и РСУБД в состоянии поддерживать целостность данных.

Требования к базовым отношениям и алгоритмы нормализации

без потерь информации составляют предмет математической теории

нормальных форм отношений. Мы не будем здесь углубляться в эту

теорию. Сформулируем лишь определения важнейших с практической

точки зрения нормальных форм для того, чтобы точно определить цель

проектирования логической структуры БД. Более подробное

изложение теории нормальных форм можно найти, например, в [1].

 3.3.1 Первая нормальная форма (1НФ). Говорят,

что отношение находится в первой нормальной форме, если и только

если все домены его атрибутов содержат скалярные значения.

Через посредство первичных ключей соответствующих отношений.

107

Любое отношение РМД находится в 1НФ по определению

(см. пп. 2.2.1, 2.2.3).

Рассмотренное выше отношение USPJ находится в 1НФ. Как

мы видели, в таком отношении возможно избыточное дублирование

данных и аномалии обновления. Некоторые его атрибуты могут

функционально зависеть от части возможного ключа. Могут

существовать ФЗ между атрибутами, не входящими в состав

возможного ключа.

3.3.2 Вторая нормальная форма (2НФ). Приводя отношение

USPJ к системе отношений S, P, J, SPJ, мы выделили в отдельные

отношения группы атрибутов, зависящих от части возможного ключа

USPJ. Все неключевые атрибуты этих отношений функционально

зависят от полных возможных ключей. При этом оказалось, что

отношение SPJ содержит ссылки на отношения S, P и J – внешние

ключи.

 Первый шаг процедуры нормализации состоит в

выделении в отдельные отношения групп атрибутов, зависящих от

части возможного ключа отношения 1НФ.

Этот шаг всегда может быть выполнен без потерь информации.

Естественное соединение полученных в результате отношений будет

эквивалентно исходному отношению

 Говорят, что отношение находится во второй

нормальной форме, если и только если каждый его неключевой

атрибут неприводимо зависит от первичного ключа.

Первый шаг процедуры нормализации приводит нормализуемое

отношение к системе отношений, находящихся в 2НФ. Действительно,

отношения S, P, J, SPJ, полученные нами после первого шага,

удовлетворяют требованиям 2НФ.

3.3.3 Третья нормальная форма (3НФ). Однако оказывается,

что в такой системе отношений еще возможны аномалии обновления.

Так, в отношении S возможно избыточное дублирование данных и

связанные с этим аномалии вставки кортежей и обновления значений

атрибутов. Это следствие наличия транзитивной ФЗ S#  SСi  St.

Здесь имеются в виду значения отношений.

108

 Говорят, что отношение находится в третьей

нормальной форме, если и только если оно находится в 2НФ и нет

транзитивных зависимостей.

Можно дать альтернативное определение 3НФ, используя

понятия неприводимой ФЗ и взаимной независимости атрибутов.

 Отношение находится в третьей нормальной форме,

если и только если каждый его неключевой атрибут неприводимо

зависит только от первичного ключа и все неключевые атрибуты

взаимно независимы.

Второй шаг процедуры нормализации направлен на устранение

транзитивных зависимостей. Он, как и первый шаг, всегда может быть

выполнен без потерь информации.

В нашем примере на втором шаге мы привели отношение S,

содержащее цепочку транзитивных зависимостей, к паре отношений

SC и CS, находящихся в 3НФ.

Определения 1НФ и 2НФ предполагают, что отношение имеет

единственный потенциальный ключ. Посмотрим теперь, какие

ситуации могут возникать, если отношение имеет несколько

потенциальных ключей. Оказывается, что в этом случае нормализация

до 3НФ может оказаться недостаточной для устранения аномалий

обновления.

3.3.4 Нормальная форма Бойса – Кодда (НФБК).

Предположим, что в нашей ПО не может быть двух поставщиков с

одинаковыми именами, и представим себе, что «учебную» БД

проектировал малоопытный проектировщик, создавший отношение со

схемой SSPJ(S#, Sn, P#, J#, Dt, Qt). Оно имеет два потенциальных

ключа: {S#, P#, J#, Dt} и {Sn, P#, J#, Dt} и находится в 3НФ, так как

единственный неключевой атрибут неприводимо зависит от каждого

из них. Тем не менее, возможно избыточное дублирование данных.

S# Sn P# J# Dt Qt

S1 Иван P1 J1 ... 1000

S1 Иван P2 J1 ... 1000

S1 Иван P3 J1 ... 2000

S2 Петр P8 J4 ... 1000

Для того чтобы изменить имя поставщика S1 нужно перебрать

109

все кортежи со значением S# = S1. Если мы удалим кортеж S2, то

потеряем информацию об имени поставщика. Это следствие наличия

ФЗ S#  Sn между атрибутами, входящими в состав различных

потенциальных ключей. Отношение имеет детерминанты, не

являющиеся потенциальными ключами. Для устранения аномалий

следует декомпозировать отношение SSPJ. Возможны два варианта

декомпозиции без потерь информации:

1) SS(S#, Sn) SPJ(S#, P#, J#, Dt, Qt);

2) SS(S#, Sn) SNPJ(Sn, P#, J#, Dt, Qt).

Отметим, что отношение SS в обоих вариантах имеет два

возможных ключа, но при его обновлении не могут возникать

аномалии.

 Говорят, что отношение находится в нормальной

форме Бойса – Кодда, если и только если каждый его детерминант

является потенциальным ключом

Если отношение не находится в НФБК, то его всегда можно

представить в виде набора проекций, находящихся в НФБК. Но эта

декомпозиция не всегда может быть выполнена без потерь

информации. Проекции могут оказаться зависимыми в том смысле,

что при обновлении одной из них придется обновить и другую.

Пример.

Пусть в отношении СДП(студент, дисциплина, профессор)

существуют следующие ФЗ:

профессор  дисциплина,

{студент, дисциплина}  профессор,

{студент, профессор}  дисциплина.

Отношение находится в 3НФ, но не в НФБК, так как имеет три

детерминанта: {студент, дисциплина}, {студент, профессор},

{профессор}, а потенциальными ключами являются только два

первых.

Возможны три варианта декомпозиции отношения СДП.

Вариант 1.

НФБК есть 3НФ для отношений с несколькими потенциальными ключами.

Поэтому ее называют еще усиленной 3НФ.

110

СП(студент, профессор); ПД(профессор, дисциплина).

Первичными ключами проекций являются подмножества

{студент, профессор} и {профессор}. Существует ФЗ профессор

 дисциплина и выводимая из нее ФЗ {студент, профессор} 

дисциплина. Тело естественного соединения проекций СП и ПД

всегда будет эквивалентно исходному отношению СДП, т.к. общий

атрибут проекций является первичным ключом отношения ПД. Однако

существующая в исходном отношении ФЗ {студент, дисциплина} 

профессор не следует из существующих в этой декомпозиции.

Поэтому независимое обновление проекций невозможно. В самом

деле, пусть имеется следующее значение отношения СДП:

СДП

студент дисциплина профессор

Иванов математика Комов

Иванов физика Липов

Петров математика Комов

Петров физика Дубов

Его проекции таковы:

СП ПД

студент профессор профессор дисциплина

Иванов Комов Комов математика

Иванов Липов Липов физика

Петров Комов Дубов физика

Петров Дубов

Если мы попытаемся добавить в СП кортеж {Петров, Липов},

то будет нарушено требование целостности сущности для отношения

СПД. Петров уже изучает физику у Комова. Таким образом, при

обновлении СП мы должны выяснить, что преподает новый (для

Петрова) профессор Липов, а что преподают Дубов и Комов,

встречающиеся в СП вместе с Петровым. Если Липов преподает одну

из дисциплин, преподаваемых Дубовым или Комовым, то новый

кортеж должен быть отвергнут.

Вариант 2.

СД(студент, дисциплина); ПД(профессор, дисциплина).

Вариант 3.

111

СП(студент, профессор); СД(студент, дисциплина).

В каждой декомпозиции утеряна одна из ФЗ, существующих в

исходном отношении. Кроме того, восстановить исходное отношение

посредством естественного соединения проекций невозможно.

Убедитесь в этом сами.

3.4 Резюме

Неразумно создавать БД, состоящую из единственного

универсального отношения. В такой БД неизбежно избыточное

дублирование данных и аномалии обновления. В ней невозможно

поддерживать целостность данных.

Проблема аномалий обновления универсального отношения

порождается тем, что в нем представлены все ФЗ, обусловленные

требованиями ПО, но средствами РМД можно объявить только те из

них, в которых детерминантом является возможный ключ отношения.

Для того чтобы в БД не было аномалий обновления данных,

следует хранить данные не в одном отношении, а в нескольких

взаимосвязанных. Эти отношения должны быть проекциями

универсального отношения, находящимися, по крайней мере, в 3НФ.

Естественное соединение всех проекций должно восстанавливать

универсальное отношение без потерь информации.

Проецирование универсального отношения должно выполняться

с сохранением ФЗ. Из существующих (и объявленных!) в проекциях

ФЗ должны выводиться все ФЗ, существующие в универсальном

отношении.

Любое отношение 1НФ может быть приведено к системе

независимо обновляемых отношений 3НФ без потерь информации.

Отношение, не находящееся в НФБК, может быть

декомпозировано без потерь информации на два отношения в НФБК,

но эти отношения необязательно будут независимо обновляемыми.

Процесс преобразования универсального отношения к системе

отношений, не обладающей аномалиями обновления данных,

называется нормализацией. В качестве методики проектирования

логического макета БД нормализация мало пригодна, однако

концепция нормализации и связанные с ней понятия ФЗ и нормальных

форм определяют цели проектирования и критерии их достижения.

Цель проектирования – создание структуры данных,

112