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

Пример:

Подсистема П	Подпрограмма S	Параметр Р
А	SUB 1	P1
В	SUB 1	P1
В	SUB 2	P2
С	SUB 1	P1

ПS ® P P ® S

F = {

1) В подсистеме каждая подпрограмма вычисляет только один параметр;

2) Каждый параметр вычисляется только одной подпрограммой.

 

Данное отношение находится в 3-ей НФ, так как в нем отсутствуют непервичные атрибуты.

Ключи = { ПS, ПP }

Можно выявить следующие особенности этого отношения:

- имеется избыточность информации из-за дублирования пар S и P;

- кроме того, имеется такая аномалия, что нельзя записать информацию о параметре, вычисляемом в некоторой подсистеме, если пока неизвестна подпрограмма, которая вычисляет этот параметр.

Таким образом, 3 НФ может обладать подобными нежелательными свойствами. Чтобы избавиться от них, необходимо использовать так называемую нормальную форму Бойса-Кодда.

· Схема отношений R находится в нормальной форме Бойса-Кодда (НФБК) относительно множества ФЗ-тей F, если она находится в 1-ой НФ и всякий раз, когда в F⁺ имеет место зависимость Х®А, где А¢Ï Х и Х включает в себя некоторый ключ отношения R.

Иными словами, допускаются только такие нетривиальные зависимости (не типа Х®Х), в которых ключ функционально определяет 1 или более атрибутов. Отношение может быть в 3 НФ, но не быть в НФБК.

В рассмотренном примере имеется нетривиальная зависимость P®S и в то же время Р не является ключом.

Теорема: Любая схема отношения, находящаяся в НФБК относительно F, находится и во в 3-ей НФ.

Пример:

Приведение к НФБК превращает одно отношение в два.

Первое ПР с ключом {ПР}, второе SP с ключом Р.

Подпрограмма S Параметр Р SUB 1 P1 SUB 2 P2   Подсистема П	Параметр Р
А	P1
В	P1
В	P2
НФБК С	P1

Проблемы НФБК:

· Схема БД находится в некоторой НФ, если каждое отношение этой БД находится в этой НФ.

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

Для НФБК подобное утверждение уже неверно, так как не всегда можно найти схему БД, полностью характеризующую множество ФЗ-тей F.

Многозначные зависимости. Четвертая нормальная форма

Рассмотренные три вида НФ и НФБК обеспечивают целостность данных в БД по отношению к приписанным ФЗ -м. Однако ФЗ-ти не являются единственно возможным видом зависимостей для отношений. Существуют и другие виды зависимостей.

Пример:

Отношение “Испытательный комплекс”

Комплекс К	Испытатель И	время В	№ стенда N	Тип Т	Условия У
КА	Иванов	ПН	Ст 1	Т 1	НД
КА	Иванов	СР	Ст 2	Т 1	НД
КА	Иванов	ПТ	Ст 1	Т 1	НД
КА	Иванов	ПН	Ст 1	Т 2	ВД
КА	Иванов	СР	Ст 2	Т 2	ВД
КА	Иванов	ПТ	Ст 1	Т 2	ВД
КВ	Петров	ВТ	Ст 3	Т 3	Норм
КВ	Петров	ВТ	Ст 4	Т 4	ВД

 

 

 

К®И: каждый комплекс обслуживает один испытатель С®К: каждый стенд принадлежит одному комплексу ВС®И: одновременно может проводить испытания только один комплекс ВИ®С: испытатель может находиться только на одном стенде ВС®Т: на стенде одновременно производится испытание только одного типа ВС®У: одновременно на стенде только одно условие проведения испытаний

 

Ключом является ВТ.

Кроме указанных ФЗ-тей можно заметить, что каждый тип испытания на каждом комплексе проводится с одним и тем же расписанием:

Комплекс А:Комплекс В:

Т1 - (пн, ср, пт);Т3 - (вт);

Т2 - (пн, ср, пт);Т4 - (вт).

С практической точки зрения такая зависимость может оказаться значимой, так как будет отражать реальные зависимости между данными, вытекающими из анализа предметной области.

Ясно. что подмеченная зависимость не является функциональной. Среди такого рода нефункциональных зависимостей различают определенный вид зависимостей. называемых многозначными зависимостями.

· Пусть имеется отношение r со схемой R.

X, Y - подмножества R.

Z = R - (XY).

Говорят, что отношение r(R) удовлетворяет многозначной зависимости (MV-зависимости) X®>Y, если для любых двух кортежей t₁ и t₂ из r, для которых t₁ (Х) = t₂ (Х) существует кортеж t₃ такой, что t₃ (Х) = t₁ (Х), t₃ (Y) = t₁ (Y), t₃ (Z) = t₂ (Z).

Аксиомы вывода для mv - зависимостей

Пусть r(R) - отношение со схемой R.

X, Y, Z, W Í R

M1. Рефлексивность Х®>Х

М2. Пополнение: если r удовлетворяет MV-ти X ®> Y, то оно удовлетворяет и MV-ти XZ ®> Y.

М3. Аддитивность: если в отношении r заданы MV-ти X ®> Y и X®>Z, то существует MV-ть X ®> YZ.

М4. Проективность: если в отношении r задана MV-ть X ®>Y & X ®>Z, то существует MV-ть X ®> YÇZ (X ®> Y - Z).

М5. Транзитивность: если в отношении r заданы MV-ти X ®> Y и Y®>Z, то существует MV-ть X ®> Z - Y.

М6. Псевдотранзитивность: если в отношении r заданы MV-ти X®>Y и YW®> Z, то существует MV-ть XW ®>Z - (YW).

М7. Дополнение: если в отношении r заданы MV-ти X®>Y и Z=R-XY, то существует MV-ть X ®>Z.

Аксиомы связи f- и mv - зависимостей

С1. Копирование: если Х®Y, то Х®>Y

С2. Объединение: если r удовлетворяет MV-ти X ®> Y и Z®W, где W Í Y, YÇZ = Æ, то оно удовлетворяет и MV-ти X®>W.

 

Для отношений, в которых имеются многозначные зависимости существует нормальный вид, который называется 4 НФ. 4 НФ является обобщением НФБК для отношениями с многозначными зависимостями.

· MV-зависимость и Х в Y (X ®> Y) называется тривиальной для произвольной схемы R, где X, YÌ R, если YÍX или XY=R.

· MV-зависимость и Х в Y (X ®> Y) называется приложимой к произвольной схеме R, если XY Í R.

Пример:

R=ABCD

AB ®> D- приложима к R

ACF ®> BF- неприложима.

· Пусть D - множество F- и MV-зависимостей для схемы R. Схема отношения R находится в 4 НФ относительно D, если она находится в 1 НФ и для каждой MV-зависимости X ®> Y, выводимой из D и приложимой к R, либо эта зависимость будет тривиальной, либо Х - есть суперключ.

Замечание: Приведение схемы с MV-зависимостями к 4 НФ преследует те же цели, что и приведение отношений с F-зависимостями к НФБК, то есть устранение информационной избыточности и аномалии данных.

Декомпозиция схем отношений

Одним из способов приведения произвольного отношения к виду нормальных форм (кроме 1 НФ) является декомпозиция отношений.

· Декомпозицией схемы отношений R называется замена ее совокупностью схем r=(R₁, R₂,..., R_K), где R_i Ì R и R_i такие, что R₁ÈR₂ È... ÈR_K = R, при этом не требуется, чтобы R_i Ç R_j =Æ, хотя и допустимо.

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

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

Целостность данных

Проектирование БД включает в себя построение концептуальной и логической схем, а также решение ряда проблем, наиболее важной из которых является проблема, связанная с отображением и корректным поддержанием семантической БД (проблема целостности).

Проблема целостности связана с обеспечением надежности данных в условиях возможных аварийных ситуаций и рационального использования вычислительных ресурсов для обеспечения высокой эффективности взаимодействия с БД.. Эффективность подразумевает обеспечение необходимого объема хранения информации и времени взаимодействия с БД.

Целостность в БД отражается путем построения логической схемы.

Логическая схема выражается в терминах объектов или сущностей и связей между ними. Связи также можно трактовать как объекты иной природы и в этом плане и сущности и связи в реляционных моделях выражаются одинаково в виде отношений. В этом случае говорят об объектах - сущностях и объектах - связей. Совокупность отношений, составляющих БД и зависящих друг от друга, отражает семантику (смысл) данных в предметной области.

· Если состояние БД не соответствует семантике связей между данными, то такое явление называют нарушением целостности данных или БД.

Для обеспечения целостности данных необходимо обеспечивать целостность объектов и целостность ссылок на эти объекты. Кроме того, объекты в БД должны быть уникальными (неповторяющимися) и распознаваемыми, а также ссылки на объекты не должны существовать без объектов.

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

Ограничения приложений делятся на:

- статические ограничения и ограничения перехода;

- ограничения для кортежей и множеств;

- отложенные и безотлагательные ограничения целостности.

· Статические ограничения - те ограничения, которые выполняются независимо от состояния БД.

· Ограничения, устанавливаемые между старым и новым значением атрибута, называется ограничениями перехода.

Пример: при обновлении значения атрибута “давление” новое значение не должно отличаться от старого более чем на 20 %.

· Ограничения для кортежей - те ограничения, для которых проверку их выполнения осуществляют, используя только один кортеж отношения.

· Частным случаем такого ограничения является ограничение атрибута.

· Ограничение для множеств - если они представляют собой ограничение на некоторое итоговое значение, полученное в результате использования совокупности кортежей.

Пример: при измерении температуры очередное значение не должно отличаться от скользящего среднего Mx (текущего математического ожидания) на некоторую величину e. Все значения не попавшие в диапазон [ M_x - e, M_x + e] отбрасывают.

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

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

Для отложенного ограничения имеет значение следующее понятие:

· Логический элемент работы - непрерывное управление данными, при котором БД из одного целостного состояния переводится в другое целостное состояние. Этот прием еще называют транзакцией.

Понятие транзакции тесно связано с надежностью данных. При выполнении транзакции могут происходить аппаратные или программные сбои. Если транзакция в результате сбоев не доведена до конца, то целостность БД нарушается. Для обеспечения целостности БД при отложенных ограничениях используют методы отката. Их суть состоит в том, что начатая, но незавершенная транзакция аннулируется, при этом БД переводится в исходное состояние, с которого начиналась транзакция (таким образом происходит откат).

Системы управления базами данных (СУБД)

Функции СУБД

· СУБД - специальный комплекс программ, с помощью которого реализуется централизованное управление базой данных и обеспечивается доступ к данным.

Системы управления базами данных делятся на две категории:

а) имеющие язык программирования и системы меню, написанные на этом языке программирования, что позволяет конечному пользователю и разработчикам информационных систем создавать сложные системы;

б) не имеющие языка программирования, что обеспечивает скорость обработки информации, экономичность и легкость в использовании.

Основными функциями СУБД являются:

1. Непосредственное управление данными во внешней памяти;

2. Управление буферами оперативной памяти;

3. Управление транзакциями;

4. Журнализация и восстановление БД после сбоев;

5. Поддержание языков БД.

Непосредственное управление данными во внешней памяти

Эта функция включает обеспечение необходимых структур внешней памяти как для хранения данных, непосредственно входящих в БД, так и для служебных целей, например, для ускорения доступа к данным (обычно для этого используются индексы). В некоторых реализациях СУБД активно используются возможности существующих файловых систем, в других работа производится вплоть до уровня устройств внешней памяти. Однако пользователи, работающие с развитыми СУБД, не обязаны знать, использует ли СУБД файловую систему, и если использует, то как организованы файлы.

Управление буферами оперативной памяти

СУБД обычно работают с БД значительного размера, обычно существенно больше доступного объема оперативной памяти. Понятно, что если при обращении к любому элементу данных будет производиться обмен с внешней памятью, то вся система будет работать со скоростью устройства внешней памяти. Практически единственным способом реального увеличения этой скорости является буферизация данных в оперативной памяти. При этом, даже если операционная система производит общесистемную буферизацию (как в случае ОС UNIX), этого недостаточно для целей СУБД, которая располагает гораздо большей информацией о полезности буферизации той или иной части БД. Поэтому в развитых СУБД поддерживается собственный набор буферов оперативной памяти с собственной дисциплиной замены буферов.

Существует отдельное направление СУБД, которое ориентировано на постоянное присутствие в оперативной памяти всей БД. Это направление основывается на предположении, что в будущем объем оперативной памяти компьютеров будет настолько велик, что позволит не беспокоиться о буферизации. Пока эти работы находятся в стадии исследований.

Управление транзакциями

· Транзакция - это последовательность операций над БД, рассматриваемых СУБД как единое целое и переводящее БД из одного целостного состояния в другое.

Либо транзакция успешно выполняется, и СУБД фиксирует изменения БД, произведенные этой транзакцией, во внешней памяти, либо ни одно из этих изменений никак не отражается на состоянии БД. Понятие транзакции необходимо для поддержания логической целостности БД (даже для однопользовательских СУБД).

Понятие транзакции гораздо более важно в многопользовательских СУБД. То свойство, что каждая транзакция начинается при целостном состоянии БД и оставляет это состояние целостным после своего завершения, делает очень удобным использование понятия транзакции как единицы активности пользователя по отношению к БД. При соответствующем управлении параллельно выполняющимися транзакциями со стороны СУБД каждый из пользователей может в принципе ощущать себя единственным пользователем СУБД.

С управлением транзакциями в многопользовательской СУБД связаны важные понятия сериализации транзакций и сериального плана выполнения смеси транзакций. Под сериализаций параллельно выполняющихся транзакций понимается такой порядок планирования их работы, при котором суммарный эффект смеси транзакций эквивалентен эффекту их некоторого последовательного выполнения. Сериальный план выполнения смеси транзакций - это такой план, который приводит к сериализации транзакций. Понятно, что если удается добиться действительно сериального выполнения смеси транзакций, то для каждого пользователя, по инициативе которого образована транзакция, присутствие других транзакций будет незаметно (если не считать некоторого замедления работы по сравнению с однопользовательским режимом).

Существует несколько базовых алгоритмов сериализации транзакций. В централизованных СУБД наиболее распространены алгоритмы, основанные на синхронизационных захватах объектов БД. При использовании любого алгоритма сериализации возможны ситуации конфликтов между двумя или более транзакциями по доступу к объектам БД. В этом случае для поддержания сериализации необходимо выполнить откат (ликвидировать все изменения, произведенные в БД) одной или более транзакций. Это один из случаев, когда пользователь многопользовательской СУБД может реально (и достаточно неприятно) ощутить присутствие в системе транзакций других пользователей.

Журнализация

Одним из основных требований к СУБД является надежность хранения данных во внешней памяти. Под надежностью хранения понимается то, что СУБД должна быть в состоянии восстановить последнее согласованное состояние БД после любого аппаратного или программного сбоя. Обычно рассматриваются два возможных вида аппаратных сбоев: так называемые мягкие сбои, которые можно трактовать как внезапную остановку работы компьютера (например, аварийное выключение питания), и жесткие сбои, характеризуемые потерей информации на носителях внешней памяти. Примерами программных сбоев могут быть: аварийное завершение работы СУБД (по причине ошибки в программе или в результате некоторого аппаратного сбоя) или аварийное завершение пользовательской программы, в результате чего некоторая транзакция остается незавершенной. Первую ситуацию можно рассматривать как особый вид мягкого аппаратного сбоя; при возникновении последней требуется ликвидировать последствия только одной транзакции.

В любом случае для восстановления БД нужно располагать некоторой дополнительной информацией. Другими словами, поддержание надежности хранения данных в БД требует избыточности хранения данных, причем та часть данных, которая используется для восстановления, должна храниться особо надежно. Наиболее распространенным методом поддержания такой избыточной информации является ведение журнала изменений БД.

· Журнал - это особая часть БД, недоступная пользователям СУБД и поддерживаемая с особой тщательностью (иногда поддерживаются две копии журнала, располагаемые на разных физических дисках), в которую поступают записи обо всех изменениях основной части БД.

Структура журнала является сугубо частным делом конкретной СУБД.

Обычно журнал представляет собой последовательный файл с записями переменного размера, которые можно просматривать в прямом или обратном порядке. Обмены производятся стандартными порциями (страницами) с использованием буфера оперативной памяти. В грамотно организованных системах структура (и тем более, смысл) журнальных записей известна только компонентам СУБД, ответственным за журнализацию и восстановление.

В разных СУБД изменения БД отражаются на разных уровнях: иногда запись в журнале соответствует некоторой логической операции изменения БД (например, операции удаления строки из таблицы реляционной БД), иногда - минимальной внутренней операции модификации страницы внешней памяти; в некоторых системах одновременно используются оба подхода.

Во всех случаях придерживаются стратегии "упреждающей" записи в журнал (так называемого протокола Write Ahead Log - WAL). Грубо говоря, эта стратегия заключается в том, что запись об изменении любого объекта БД должна попасть во внешнюю память журнала раньше, чем измененный объект попадет во внешнюю память основной части БД. Известно, что если в СУБД корректно соблюдается протокол WAL, то с помощью журнала можно решить все проблемы восстановления БД после любого сбоя.

Самая простая ситуация восстановления - индивидуальный откат транзакции. Строго говоря, для этого не требуется общесистемный журнал изменений БД. Достаточно для каждой транзакции поддерживать локальный журнал операций модификации БД, выполненных в этой транзакции, и производить откат транзакции путем выполнения обратных операций, следуя от конца локального журнала. В некоторых СУБД так и делают, но в большинстве систем локальные журналы не поддерживают, а индивидуальный откат транзакции выполняют по общесистемному журналу, для чего все записи от одной транзакции связывают обратным списком (от конца к началу).

При мягком сбое во внешней памяти основной части БД могут находиться объекты, модифицированные транзакциями, не закончившимися к моменту сбоя, и могут отсутствовать объекты, модифицированные транзакциями, которые к моменту сбоя успешно завершились (по причине использования буферов оперативной памяти, содержимое которых при мягком сбое пропадает). При соблюдении протокола WAL во внешней памяти журнала должны гарантированно находиться записи, относящиеся к операциям модификации обоих видов объектов. Целью процесса восстановления после мягкого сбоя является состояние внешней памяти основной части БД, которое возникло бы при фиксации во внешней памяти изменений всех завершившихся транзакций и которое не содержало бы никаких следов незаконченных транзакций. Для того, чтобы этого добиться, сначала производят откат незавершенных транзакций (undo), а потом повторно воспроизводят (redo) те операции завершенных транзакций, результаты которых не отображены во внешней памяти.

Для восстановления БД после жесткого сбоя используют журнал и архивную копию БД. Как правило, архивная копия - это полная копия БД к моменту начала заполнения журнала. Конечно, для нормального восстановления БД после жесткого сбоя необходимо, чтобы журнал не пропал. Как уже отмечалось, к сохранности журнала во внешней памяти в СУБД предъявляются особо повышенные требования. Тогда восстановление БД состоит в том, что исходя из архивной копии по журналу воспроизводится работа всех транзакций, которые закончились к моменту сбоя. В принципе, можно даже воспроизвести работу незавершенных транзакций и продолжить их работу после завершения восстановления. Однако в реальных системах это обычно не делается, поскольку процесс восстановления после жесткого сбоя является достаточно длительным.

Языки баз данных

Языки баз данных делятся на процедурные и непроцедурные. Процедурные языки требуют от конечного пользователя знания синтаксиса, но их плюс в том, что на них можно написать стандартные программы и они гибки в использовании. Непроцедурные языки предлагают пользователю шаблоны запросов или систему меню, из которых пользователь выбирает нужные ему вопросы. Поэтому они хороши и удобны для профессиональных пользователей. СУБД также может иметь библиотеки программ, позволяющие делать вызовы из языков высокого уровня типа С и может вызывать внешние программы на языках высокого уровня или макроассемблер.

Интерфейс пользователя обеспечивает взаимодействие с конечным пользователем. Различают шесть видов интерфейсов:

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

- структурированный язык запросов для баз данных. Это тоже команды, но ближе к естественному языку;

- язык запросов, встроенный в стандартный язык программирования высокого уровня;

- язык запросов на основе меню. Для более сложных функций можно организовать меню по иерархическому принципу;

- язык запросов в виде форм или бланков. Формы можно строить по иерархическому принципу;

- диалоговые языки запросов, близкие к естественным.

Первые три типа интерфейса предназначены в основном для программистов, остальные - для конечного пользователя.

В ранних СУБД поддерживалось несколько специализированных по своим функциям языков. Чаще всего выделялись два языка - язык определения схемы БД (SDL - Schema Definition Language) и язык манипулирования данными (DML - Data Manipulation Language). SDL служил главным образом для определения логической структуры БД, т.е. той структуры БД, какой она представляется пользователям. DML содержал набор операторов манипулирования данными, т.е. операторов, позволяющих заносить данные в БД, удалять, модифицировать или выбирать существующие данные.

В современных СУБД обычно поддерживается единый интегрированный язык, содержащий все необходимые средства для работы с БД, начиная от ее создания, и обеспечивающий базовый пользовательский интерфейс с базами данных. Стандартным языком наиболее распространенных в настоящее время реляционных СУБД является язык SQL (Structured Query Language).

Прежде всего, язык SQL сочетает средства SDL и DML, т.е. позволяет определять схему реляционной БД и манипулировать данными. При этом именование объектов БД (для реляционной БД - именование таблиц и их столбцов) поддерживается на языковом уровне в том смысле, что компилятор языка SQL производит преобразование имен объектов в их внутренние идентификаторы на основании специально поддерживаемых служебных таблиц-каталогов. Внутренняя часть СУБД (ядро) вообще не работает с именами таблиц и их столбцов.

Язык SQL содержит специальные средства определения ограничений целостности БД. Опять же, ограничения целостности хранятся в специальных таблицах-каталогах, и обеспечение контроля целостности БД производится на языковом уровне, т.е. при компиляции операторов модификации БД компилятор SQL на основании имеющихся в БД ограничений целостности генерирует соответствующий программный код.

Специальные операторы языка SQL позволяют определять так называемые представления БД, фактически являющиеся хранимыми в БД запросами (результатом любого запроса к реляционной БД является таблица) с именованными столбцами. Для пользователя представление является такой же таблицей, как любая базовая таблица, хранимая в БД, но с помощью представлений можно ограничить или наоборот расширить видимость БД для конкретного пользователя. Поддержание представлений производится также на языковом уровне.

Наконец, авторизация доступа к объектам БД производится также на основе специального набора операторов SQL. Идея состоит в том, что для выполнения операторов SQL разного вида пользователь должен обладать различными полномочиями. Пользователь, создавший таблицу БД, обладает полным набором полномочий для работы с этой таблицей. В число этих полномочий входит полномочие на передачу всех или части полномочий другим пользователям, включая полномочие на передачу полномочий. Полномочия пользователей описываются в специальных таблицах-каталогах, контроль полномочий поддерживается на языковом уровне.