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

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

2) (JX, JnX) WHERE

J(J# : JX, Jn : JnX, Ci : ‘Томск’);

3) SX WHERE SPJ(J# : ‘J1’);

4) SX WHERE SPJ(J# : ‘J1’, P# = ‘P1’);

5) JnX WHERE EXISTS JX (SPJ (S# : ‘S1’, J# : JX)

AND J(J# : JX, Jn : JnX));

6) CoX WHERE EXISTS PX

(SPJ(S# : ‘S1’, P# : PX) AND

P(P# : PX, Co : CoX));

7) SX WHERE SPJ(S# : SX, J# : ‘J1’) AND

SPJ(S# : SX, J# : ‘J2’);

Заметьте, что (в отличие от формулы исчисления кортежей)

здесь не нужен квантор существования.

8) SX WHERE EXISTS PX

(SPJ(S# : SX, P# : PX, J# : ‘J1’) AND

P(P# : PX, Co : ‘красный’));

9) PX WHERE FORALL JX (IF J(J# : JX, Ci : ‘Томск’)

THEN SPJ(P# : PX, J# : JX));

Другая формулировка этого запроса, не использующая квантора

всеобщности:

PX WHERE NOT EXISTS JX (J(J# : JX, Ci : ‘Томск’) AND

NOT SPJ(P# : PX, J# : JX));

Сравните эти формулировки с приведенными в пп. 2.5.4, 2.6.2.

Большое количество задач такого типа приведено в [1], [7].

2.6.4 Резюме. Все три механизма манипулирования данными

составляют основу реализаций реляционных ЯМД. Это непроцедурные

языки. Они не предназначены для записи алгоритмов. Они

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

Самый распространенный язык запросов SQL основывается на

смеси алгебраических и логических конструкций. Человек

формулирует запрос в виде предиката, а система строит

соответствующую процедуру вычисления требуемого результата.

3 ПРОЕКТИРОВАНИЕ БАЗЫ ДАННЫХ

3.1 Цели проектирования

3.1.1 Характеристика процесса проектирования. Процесс

проектирования БД включает три основных этапа:

 проектирование концептуальной модели (логического макета

БД);

 проектирование внутренней модели (физического макета);

 проектирование внешних моделей (локальных представлений

данных для различных конечных пользователей).

Проектированию предшествует этап анализа ПО. Цель анализа –

установить, какие данные должны храниться в БД, как эти данные

взаимосвязаны и какие ограничения на них накладываются правилами

бизнеса.

На первом этапе выбирается подходящая логическая структура

для некоторого набора данных, которые должны храниться в БД. Здесь

принимаются решения о том, какие базовые отношения и с какими

атрибутами (схемами) следует создать и поддерживать. При этом

учитываются только требования ПО. Никакие соображения реализации

и аспекты использования данных не принимаются во внимание.

На втором этапе проектируются хранимые файлы, в которых

будут размещаться базовые отношения, процедуры поддержания

целостности, принимаются решения о том, какие нужно создать

индексы, на каких носителях какие файлы следует разместить и т.п.

Другими словами, на этом этапе выполняется отображение

концептуальной модели на структуры хранимых данных.

Все принимаемые здесь решения зависят от конкретной СУБД,

которая будет контролировать базу. Абсолютно точная реализация

логического макета БД средствами этой СУБД может оказаться

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

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

несколько итераций проектирования логического и физического

макетов.

На третьем этапе определяются подмножества данных,

необходимых конкретным КП, и проектируются отображения

концептуального макета БД на макеты КП. Кроме того, проектируются

интерфейсы КП.

Требования конечных пользователей меняются со временем.

Может возникнуть потребность в данных, хранение которых не

предусмотрено. Может исчезнуть необходимость хранения каких-то

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

или правила бизнеса. Все это приводит к необходимости изменения

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

условно изображенный на рис. 3.1, продолжается в течение всего

периода жизни системы.

Ï ðî åêòèðî âàí èå

ÊÌ Ä

Ï ðî åêòèðî âàí èå

ÂÌ Ä

Ï ðî åêòèðî âàí èå

Âí Ì Ä

Рис. 3.1Этапы проектирования БД

 Для того чтобы получить качественную БД, нужно в

первую очередь создать концептуальную модель данных. Интерес при

этом представляют сами данные как таковые и правила целостности,

обусловленные бизнес-правилами и смыслом данных. Только после

того, как создан логический макет, можно приступать к анализу

аспектов реализации структур хранения и приложений.

Здесь мы будем обсуждать только проблемы проектирования

концептуальной модели. Будем иметь в виду реляционный макет, хотя

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

проектировании нереляционных баз данных. Иначе говоря, проектируя

нереляционную (например, сетевую) БД, следует прежде всего создать

реляционный макет, а затем отобразить его на нереляционные

структуры, поддерживаемые целевой СУБД.

Проектирование БД – это скорее искусство, чем наука. Тем не

менее, существуют некоторые принципы проектирования, которых

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

Существуют строгие доказательства того, что логический макет

данных, построенный в соответствии с ними, обладает определенными

«хорошими» свойствами. Мы познакомимся здесь с этими

принципами, но не с их формальными обоснованиями.

Поскольку при реальном проектировании всегда возникают

проблемы, не охватываемые этими принципами, существует очень

много различных методик проектирования. Не существует критериев

предпочтения для какой-либо конкретной методики. Однако есть два

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

макета.

С одним из них – формальным – мы познакомимся лишь

поверхностно, исключительно для того, чтобы понять суть общих

проблем, возникающих при проектировании концептуальной модели, и

выяснить, какие основные формальные требования предъявляются к

«хорошим» структурам БД.

Второй подход – семантический – изучим достаточно подробно.

Его рекомендуется использовать для выполнения курсовых проектов.

3.1.2 Универсальное отношение и аномалии обновления.

Создать логический макет БД, – значит определить набор базовых

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

Зачем нужен какой-то набор отношений? Почему бы не хранить

все данные в одном отношении?

Для того чтобы ответить на эти вопросы, вернемся к нашей

«учебной» БД ПОСТАВЩИК–ДЕТАЛЬ– ИЗДЕЛИЕ (см. п. 2.3.2). Она

состоит из четырех базовых отношений. Чтобы поддерживать в ней

порядок, необходимо следить за соблюдением требования внешнего

ключа. Вставляя кортеж в SPJ, мы должны проверить:

 есть ли добавляемое значение S# среди значений этого

атрибута в текущем значении отношения S;

 есть ли добавляемое значение P# среди значений этого

атрибута в текущем значении отношения P;

 есть ли добавляемое значение J# среди значений этого

атрибута в текущем значении отношения J;

 уникален ли новый набор значений {S#, P#, J#, Dt} в

отношении SPJ.

При удалении кортежа из какого-либо родительского отношения

возникнет вопрос: что делать с потомками удаляемого кортежа в

отношении SPJ?

Если же мы создадим единственное (универсальное) отношение

USPJ со схемой {S#, Sn, St, Sci, P#, PN, Co, We, Pci, J#, Jn, Jci,

Qt}, то никаких проблем ссылочной целостности нет, потому что нет

ссылок. Все связи между данными хранятся в одном месте,

выражаются как связи между атрибутами одного отношения, а не как

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

проверить уникальность значения подмножества атрибутов {S#, P#,

J#, Dt}. При удалении кортежа проблемы «отцов и детей» не

возникает. Да и места на диске, кажется, потребуется меньше. В

универсальном отношении нужно хранить значения всего тринадцати

атрибутов, а в структуре, содержащей четыре отношения, – значения

шестнадцати.

На первый взгляд – хорошо. На самом деле – очень плохо.

Рассмотрим проблемы, возникающие при хранении данных в

универсальном отношении.

Избыточность. Будем считать, что в нашей ПО действует, в

дополнение к перечисленным в п. 2.3.2, следующее правило:

 статус поставщика однозначно определяется городом его

размещения.

Для иллюстрации выпишем фрагмент возможного значения

нашего универсального отношения:

S# Sn St Sci P# Pn Co We Pci J# Qt ...

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

S1 Иван 50 Яя P1 гайка К 10 Яя J1 1000 ...

S1 Иван 50 Яя P8 болт Ч 30 Яя J1 500 ...

S2 Петр 100 Ош P3 шайба Ж 20 Яя J2 1000 ...

S3 Джон 50 Яя P2 винт С 40 Ош J2 2000 ...

S3 Джон 50 Яя P1 гайка К 10 Ош J2 1000 ...

S8 Боб 50 Томск P8 болт Ч 30 Яя J2 500 ...

Очевидно, группы вида {S1, Иван, 50, Яя} встретятся столько

раз, сколько поставок этот поставщик выполнил. Встреченная в

первый раз такая группа сообщает нам сведения о конкретном

поставщике. Встреченная вторично, она не содержит новой

информации.

 В универсальном отношении возможно

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

Аномалия вставки типа а). Универсальное отношение не

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

структура еще заставляет нас фиксировать один и тот же факт

многократно. Поэтому вполне возможно появление кортежей {‘S1’,

‘Иван’, 100, ‘Яя’, ...}, {‘S1’, ‘Петр’, 50, ‘Ош’, ...}. Каковы имя, статус и

город размещения поставщика S1? Эта информация утеряна. Контроль

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

 При добавлении новых кортежей в универсальное

отношение возможен ввод противоречивых данных.

Аномалия вставки типа б). В универсальное отношение

невозможно вставить данные, например, о некотором поставщике,

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

единственным возможным ключом этого отношения является

подмножество атрибутов {S#, P#, J#, Dt}. Если новый поставщик еще

не выполнил ни одной поставки, то значение подмножества {P#, J#,

Dt} в соответствующем кортеже не определено. Кортеж не имеет

идентификатора. Либо мы не можем его вставить, либо должны

нарушить требование целостности сущности.

 В универсальное отношение невозможно добавить

кортеж, содержащий сведения о части объектов ПО.

Аномалия удаления. Аналогичное ограничение существует и на

операцию удаления. Пусть нам нужно удалить сведения о поставке

детали P3 поставщиком S2. Она зарегистрирована ошибочно. Удалить

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

сведения, либо заменив в нем значения атрибутов, характеризующих

поставку, NULL-значениями. В последнем случае будет нарушено

требование целостности сущности. Кортеж отношения можно удалить

только полностью. Однако запись о поставке детали P3 поставщиком

S2 – единственный кортеж в нашей БД, содержащий сведения о

поставщике S2. Удалив его, мы утратим эти сведения.

 При попытке удаления сведений о части объектов ПО

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

объектах.

Аномалия обновления значений. Пусть мы решили поднять

статус поставщиков из Яи до 100. При этом нам придется отыскать все

кортежи со значением Sci = ‘Яя’ и изменить в них значение St. Если

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

информация будет утеряна.

 При обновлении значений атрибутов универсального

отношения существует возможность утери информации.

Перечисленные выше аномалии обновления данных

обусловлены сложными структурами межатрибутных зависимостей в

схеме универсального отношения. Можно сформулировать вполне

определенные требования к этим структурам. Если все отношения в

БД удовлетворяют им, то никаких аномалий обновления данных нет.

Существуют некоторые (более или менее формальные)

процедуры построения таких структур, основанные на теории

функциональных зависимостей и нормальных форм отношений. В

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

этой теории для того, чтобы уяснить к какой цели нужно стремиться,

проектируя логический макет БД.

3.2 Функциональная зависимость атрибутов

3.2.1 Основные определения.

 Определение 1. Пусть R некоторое отношение, А, В –

подмножества его атрибутов. Говорят, что А функционально

определяет В (или В функционально зависит от А), если и только

если для любого допустимого значения R каждому значению А

соответствует точно одно значение В. Функциональную зависимость

(ФЗ) принято обозначать А  В.

Иными словами, если А  В, то для любого допустимого

значения R два кортежа, совпадающие по значению А, совпадают

также и по значению В. Обратное, вообще говоря, неверно.

Подмножество А называют детерминантом зависимости,

подмножество В – зависимой частью.

 Функциональные зависимости есть связи типа 1:М

между подмножествами атрибутов. Они определяются смыслом

данных и правилами бизнеса. Наличие ФЗ невозможно установить по

результатам анализа значения отношения.

Так, в приведенном выше примере (см. п. 3.1.2) дважды

встречающемуся значению P# = ‘P1’ соответствует одно и то же

значение Qt = 1000. Аналогичное соответствие наблюдается и

для P# = ‘P3’и P# = ‘P8’. Однако из этих фактов нельзя сделать

вывод о существовании ФЗ {P#}  {Qt}

. Возможно, это случайность.

Однако, если ПО действительно накладывает ограничения на разовые

объемы поставок конкретных видов деталей, то есть и отмеченная ФЗ.

Зависимости S#  St, S#  Sci, Sci  St действительно

существуют. По правилам ПО конкретный поставщик расположен в

единственном городе, имеет единственный статус, и всем

поставщикам, расположенным в одном городе, присваивается один и

тот же статус.

 Определение 2. Атрибуты А

, А

, ... , А

называются

взаимно независимыми, если ни один из них не зависит

функционально от какого-либо подмножества остальных.

Например, атрибуты We, Qt, S#, Jn взаимно независимы.

Правила бизнеса не обусловливают каких-либо зависимостей между

ними или их комбинациями.

Пусть R – некоторое отношение, А, В, С – подмножества его

атрибутов. Если А  В, В  С, то А  С. В таком случае говорят, что

существует транзитивная функциональная зависимость (С

транзитивно зависит от А, А  В  С).

В универсальном отношении USPJ существует транзитивная

ФЗ S#  SСi  St, следующая из S#  SCi, SСi  St.

 Определение 3. Пусть A и B – подмножества

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

одноэлементных множеств.

100

атрибутов и A – детерминант B. Говорят, что ФЗ A  B неприводима,

если не существует такого подмножества C  A, что C  B.

Например, существующая в USPJ ФЗ {S#, P#, J#, Dt}  Qt

неприводима, а зависимость {S#, P#, J#, Dt}  Jn следует из J#  Jn,

т.е. неприводимой не является.

3.2.2 Причины аномалий обновления данных. Поскольку ФЗ

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

целостности. Для того чтобы система могла поддерживать эти ОЦ, они

должны быть объявлены. В РМД имеется единственный способ

объявления ФЗ между атрибутами отношения – указание возможного

(первичного) ключа. Все не входящие в состав этого ключа атрибуты

функционально зависят от него. Какие-либо ФЗ между неключевыми

атрибутами невозможно объявить, оставаясь в рамках РМД.

Схема универсального отношения содержит все атрибуты всех

объектов ПО. Поэтому в нем представлено все множество ФЗ. Однако

в силу указанной выше причины объявить можно только те ФЗ,

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

Поэтому при обновлении универсального отношения РСУБД не может

выполнить необходимые проверки ограничений целостности данных.

 Аномалии обновления данных обусловлены

невозможностью объявления всех ФЗ между атрибутами

универсального отношения средствами РМД.

Для того чтобы вполне понять смысл этого утверждения,

проанализируем причины аномалий, обнаруженных в примере (см. п.

3.1.2).

Аномалия вставки типа а). Если А  В, то всякий раз, как

встретится конкретное значение А, должно встретиться

соответствующее ему значение В. Если при этом А не является

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

кортежей с конкретным значением А и соответствующим ему

значением В. Этим и обусловлено избыточное дублирование.

Для того чтобы система могла блокировать ввод ошибочных

значений B, она должна знать о наличии ФЗ А  В. Но если A не

является возможным ключом, мы не можем объявить ФЗ А  В.

101

Поэтому система не может запретить ввод значения B, не

соответствующего этой ФЗ.

В нашем примере универсального отношения атрибут S# не

является возможным ключом. Связанная с этим аномалия вставки типа

а) обусловлена тем, что нет никакой возможности объявить ФЗ S# 

Sn, S#  St, S#  Sci, Sci  St.

Аномалия вставки типа б). Она обусловлена тем, что

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

ключа (ПК).

Для того чтобы добавить в БД сведения о новом поставщике,

достаточно указать значение S# и проверить ФЗ S#  Sn, S#  St,

S#  Sci, Sci  St. Но S# – только часть ПК универсального

отношения и эти ФЗ мы не можем объявить. Вставляя кортеж в

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

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

образом ФЗ. Однако среди них нет интересующих нас зависимостей S#

 Sn, S#  St, S#  Sci, Sci  St. Поэтому, даже если мы

присвоим атрибутам P#, J#, Dt какие-то значения «по умолчанию» и

формально обеспечим возможность вставки кортежа, целостность

данных не гарантирована.

Таким образом, аномалии обновления типа б) обусловлены тем,

что в схеме отношения имеются атрибуты, функционально зависящие

от части первичного ключа.

Аномалия обновления значений. Если обновляются значения

атрибутов, функционально зависящих от части ПК или от неключевых

атрибутов, то система не может проверить эти ФЗ, так как их

невозможно объявить. Поэтому она не заметит, что поставщик из Яи

«приобрел» запрещенный статус. Будут пропущены также ошибки при

обновлении значений поля Jn или Sn и т.п.

3.2.3 Устранение аномалий (пример). Вернемся к нашему

универсальному отношению USPJ(S#, Sn, St, SCi, P#, Pn, We, Co,

PCi, J#, Jn, JCi, Dt, Qt). Посмотрим, какие ФЗ между его атрибутами

существуют. Для этого обратимся к правилам, сформулированным в

пп. 2.3, 3.1.2. Из них следуют такие ФЗ:

102