Глушаков С.В., Ломотько Д.В. Базы данных

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

Часть I. Теория баз данных

ношение SP в силу каких-либо причин необходимо разделить на

два - SPO и SPP, что приведено на рис. 1.23.

SN |

SPO

! OCENKA

SPP

PN NAME

Рис. 1.23. Структура отношений SPO и SPP

Понятно, что соединение полученных отношений воссоздаст от-

ношение SP. Следовательно, для дальнейшей работы можно создать

представление SP, а значит у пользователя стожится впечатление,

что никакой реструктуризации просто не производилось:

СОЗДАТЬ ПРЕДСТАВЛЕНИЕ SP

SPP СОЕДИНИТЬ С SPO

Любая пользовательская программа после этого вместо отно-

шения SP будет использовать созданное представление для ма-

нипуляции с данными.

Помимо решения проблемы реструктуризации БД, представ-

ление можно использовать для возможности просмотра одних и

тех же данных разными пользователями, да еще в различных ва-

риантах. Кроме того, теперь пользователю можно не работать с

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

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

ний, он имеет возможность ограничить объем данных для удоб-

ства работы. Пример такого представления для успевающих сту-

дентов приведен выше.

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

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

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

теля не представляет, однако он служит для обеспечения связи

отношений в БД. Можно' создать представление, где вместо но-

меров студенческих билетов будут подставлены фамилии студен-

тов из другого отношения. Очевидно, такое представление более

удобно в использовании.

Часто представление используется для выборки данных. Об

этой операция мы уже говорили выше, однако имеет смысл сде-

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

реализуется непосредственно на отношениях и хранится в виде

функции. Материализация представления-выборки осуществля-

Глава 1.5. Дополнительные аспекты реляционной технологии

ется непосредственно при реализации соответствующего дейст-

вия пользователя, до этого момента материализованных данных

представления в БД не хранится.

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

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

ношения БД обновленные данные так, чтобы в результате полу-

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

Обновляемость (или необновляемость) представления не

должна зависеть от его формы записи. Кроме того, должна

соблюдаться симметричность обновления, то есть исключена

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

обновления. Так, скажем, обновление представления, постро-

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

чтобы манипуляция с данными осуществлялось в обоих отно-

шениях. При этом должны учитываться правила - триггеры

контроля целостности данных. Эти триггеры никогда не запус-

каются внутри операции обновления (UPDATE) по той причи-

не, что во время обновления вообще говоря может существо-

вать нарушение целостности данных. Однако полностью вы-

полненная операция обновления, как уже было сказано, цело-

стность данных нарушать не должна.

Операция обновления обычно реализуется при помощи более

мелких однотипных конструкций типа УДАЛИТЬ (DELETE) и

ВСТАВИТЬ (INSERT) на исходных отношениях, после чего осу-

ществляется проверка целостности. Очевидно, что использование

и корректная работа этих операторов должны быть возможны и в

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

чаях это может приводить к неожиданным для пользователя ре-

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

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

сразу с несколькими кортежами.

Рассмотрим выполнение операции ВСТАВИТЬ для представ-

ления вида А СОЕДИНИТЬ Б, то есть для представления, полу-

ченного с помощью операции объединения. Необходимо иметь в

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

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

вие кортежа хотя бы в одном из исходных отношений (предика-

ту). Если новый кортеж удовлетворяет предикату А, то он встав-

ляется в А, если он удовлетворяет предикату Б - то в Б. Возможна

ситуация, когда кортеж вставляется и в А и в Б. Вставку можно

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

денных на рис. 1.23. Предположим, что представление определе-

но следующим образом:

Часть I. Теория баз данных

СОЗДАТЬ ПРЕДСТАВЛЕНИЕ VIEW2

SPP (ДЛЯ SPP.PN = "Физика") СОЕДИНИТЬ

С SPO (ДЛЯ SPO.OCENKA>=3)

В результате чего будет получено представление VIEW2,

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

3412

3413

3414

NAME

Физика I Поляков

Физика

Старова

Физика Гриценко

OCENKA

Рис. 1.24. Структура и пример данных для представления VIEW2

При попытке выполнить вставку кортежа (3415. Математика.

Сурядный. 5) имеем, что этот кортеж удовлетворяет предикату

SPO.OCENKA>=3. но не удовлетворяет предикату SPP.PN = "Фи-

зика". Значит, новый кортеж будет вставлен в отношение, удов-

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

щее информацию об оценках.

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

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

ляемый кортеж принадлежит А, то он удаляется из А. Если после

удаления кортежа из А этот кортеж имеет место в Б, то он также

удаляется и из Б. Например, при попытке удалить из VIEW2 кор-

теж (3413, Физика. Гриценко, 3), удаляется кортеж из отношения,

удовлетворяющего предикату SPP.PN = "Физика", а затем - из

отношения, удовлетворяющего предикату SPO.OCENKA>=3.

Процесс обновления происходит так,, чтобы текущий кортеж

удовлетворял одному или обоим предикатам. Например, если

обновляемый кортеж принадлежит А, то он удаляется из А Если

измененная версия кортежа удовлетворяет предикату А. то он

вставляется в А. При этом, если измененная версия кортежа

удовлетворяет предикату Б. то он вставляется и в Б. Например,

при попытке обновления кортежа (3413, Физика, Старова, 4) на

(3413, Физика. Старова. 5) обновление будет произведено в обоих

отношениях.

Теперь более кратко рассмотрим выполнение аналогичных

операций для представления вида А ПЕРЕСЕКАЕТ Б. то есть для

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

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

предикату А и предикату Б. Если новый кортеж не входит в А. то

Глава 1.5. Дополнительные аспекты реляционной технолоаии 63

этот кортеж вставляется в А. Если новый кортеж не входит в Б, то

он будет вставлен и в Б.

При удалении кортежа из представления, он удаляется из А.

если он не удален из Б, то он удаляется и из Б. При выполнении

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

предикату А и предикату Б. Кортеж удаляется из А и из Б. Затем,

если обновленный кортеж отсутствует в А, он вставляется в А,

если он отсутствует в Б, то вставляется и в Б.

Если же представление получено при помощи операции вычи-

тания, то есть А ВЫЧИТАЕТСЯ ИЗ Б, то выполнение операций

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

должен удовлетворять предикату А и не должен удовлетворять

предикату Б. Следовательно, новый кортеж вставляется в А. При

удалении кортежа, последний удаляется из А. В случае обновле-

ния кортеж должен удовлетворять предикату А "и не удовлетво-

рять предикату Б. Кортеж удаляется из А. а затем его обновлен-

ный вариант вставляется в А.

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

зовано путем выполнения операции А ДЛЯ <условие>. Таким

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

удовлетворять как предикату А, так и условию. При выполнении

операции вставки новый кортеж вставляется в А. При выполне-

нии удаления кортеж удаляется го А. При выполнении обновле-

ния кортеж удаляется из А. Обновленная версия, удовлетворяю-

щая предикату А и условию, вставляется в А.

Предположим, что представление определено следующим

образом:

СОЗДАТЬ ПРЕДСТАВЛЕНИЕ VIEW3

SPP ДЛЯ SPP.PN = "Физика")

В результате выполнения получим представление V1EW3,

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

3412

3413

3414

Физика

NAME

Поляков

Старова

Гриценко

Рис. 1.25. Структура и пример данных для представления VIEW3

Часть I. Теория баз данных

Попытка осуществить вставку в такое представление кортежа

(3416, Физика, Бычкова) закончится успешно, а кортежа (3417.

Математика, Котенко) - неудачей, так как последний кортеж не

удовлетворяет условию. Попытка обновить кортеж (3412, Физи-

ка, Поляков) на (3412, Химия, Поляков) закончится неудачей, так

как обновленный кортеж не удовлетворяет условию.

Для представления, полученного при помощи проекции, сле-

дует иметь в виду, что кортеж будет включен только в том слу-

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

в заданное множество А. Это условие будет являться предикатом

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

для отношения А в том случае, если кортеж удовлетворяет пре-

дикату. При попытке удаления из А удаляются все кортежи, в

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

при выполнении обновления кортежа сначала из отношения А

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

вставлены обновленные варианты кортежа, удовлетворяющие

предикату А.

В качестве примера рассмотрим представление, полученное как

СОЗДАТЬ ПРЕДСТАВЛЕНИЕ VIEW4 (SPP.SN, SPP.PN)

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

приведен на рис. 1.26.

Глава 1.5. Дополнительные аспекты реляционной технологии

3412

3413

3414

Физика

Химия

Физика

Рис. 1.26. Структура и пример данных для представления V1EW4

Вставка в VIEW4 кортеж (3419, Математика) закончится успеш-

но. В результате этого в отношение SPP будет вставлен кортеж

(3419, Математика, X). где X - значение атрибута NAME, исполь-

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

(3412, Химия) закончится неудачей, так как нарушается условие

уникальности ключа SN. Попытка обновить кортеж (3412, Физика)

на (3412. Математика) приведет к тому, что успешно произойдет

изменение кортежа (3412, Физика. Поляков) на (3412. Математика.

Поляков) в отношении SPP (данные взяты согласно рис. 1.25).

Рассмотрим теперь представление, полученное как расшире-

ние отношения А. Такое представление можно получить как

СОЗДАТЬ ПРЕДСТАВЛЕНИЕ VIEW ДОБАВИТЬ К А

<выражение> КАК X

Предикат имеет такой вид, что в расширенном варианте каж-

дый кортеж представления а является порождением кортежа от-

ношения при помощи проекции, исключающей значение X от

кортежа а из кортежа отношения, и, кроме того, удовлетворяет

предикату А. Правило обновления такого представления при

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

удовлетворять предикату представления. При этом в отношение

А вставляется кортеж, исключающий значение X от кортежа от-

ношения А. При удалении из А удаляется кортеж, исключающий

значение X от кортежа отношения А. Наконец, при обновлении

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

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

представления, причем из модифицированного кортеж исключа-

ется значение X от кортежа отношения А.

Рассмотрим теперь представление, полученное как расшире-

ние отношения А. Такое представление можно получить как

СОЗДАТЬ ПРЕДСТАВЛЕНИЕ VIEW5

ДОБАВИТЬ К SPO (ЕСЛИ OCENKA>=3 TO

"Зачет" ИНАЧЕ "Не&ачет") КАК ZACHET

В результате получим представление, приведенное на рис. 1.27.

••'• "•; ;.V

"-.\fflEWI5---;

;;

-;-^.y-v:

3412

3413

3414

OCENKA

ZACHET

Зачет

Незачет

Зачет

Рис. 1.27. Структура и пример данных для представления VIEW5

Вставка в V1EW5 кортежа (3419, 4, Зачет) будет завершена

успешно и приведет к добавлению в отношение SPO кортежа

(3419, 4). Неудачу потерпит попытка вставки кортежа (3418, 2,

Зачет), как неудовлетворяющего предикату. Обновление кортежа

(3414, 3, Зачет) на (3414, 4, Зачет) завершится успешно и в отно-

шении SPO обновится кортеж (3414, 3) на (3414, 4).

И, наконец, рассмотрим представление, полученное как ре-

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

СОЗДАТЬ ПРЕДСТАВЛЕНИЕ VIEW А ПРИСОЕДИНИТЬ Б

3 «Базы данных:

Часть I. Теория баз данных

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

предикат А, для части представления, полученного от отношения

А, и предикат Б, для части представления, полученного из Б. При

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

представления. Если часть представления, полученная от отно-

шения А, в А отсутствует, то эта часть вставляется в А. Если

часть представления, полученная от отношения Б, в Б отсутству-

ет, то эта часть вставляется в Б. При удалении кортежа удаляются

соответствующие части представления из отношений А и Б. И.

наконец, при обновлении кортежа, его обновленная версия долж-

на удовлетворять предикату представления. Из отношения А уда-

ляется часть кортежа, полученная из А. из отношения Б - полу-

ченная из Б. После этого осуществляется вставка обновленного

кортежа по правилу, изложенному выше.

Рассмотрим пример представления, полученного соединением

отношений SPP и SPO:

СОЗДАТЬ ПРЕДСТАВЛЕНИЕ VXEW6 SPP ПРИСОЕДИНИТЬ SPO

Как результат получим представление, приведенное на рис. 1.28.

3412

3413

3414

3412

Физика

Химия

Физика

Математика

NAME

Поляков

Старова

Гриценко

Поляков

OCENKA

Рис. 1.28. Структура и пример данных для представления VIEW6

Приведем несколько примеров работы с этим представлением.

Вставка в VIEW6 кортежа (3412. Математика, Поляков, 5) будет

завершена успешно, при этом в отношение SPO будет добавлен

кортеж (3412. 5). Удаление кортежа (3413, Химия. Старова, 4)

будет завершено успешно: из отношения SPP будет удален кор-

теж (3413, Химия, Старова) и из отношения SPO - (3413, 4). Уда-

ление кортежа (3412, Математика, Поляков, 4) завершится ус-

пешно, при этом из отношения SPO будет удален кортеж (3412.

4). Попытка обновить кортеж (3414, Физика, Гриценко, 3) на

(3414, Физика, Гриценко, 5) завершится успешно, а в отношении

SPO кортеж (3414, 3) будет заменен кортежем (3414, 5).

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

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

их обновления позволяет расширить возможности СУБД при

Глава 1.5. Дополнительные аспекты реляционной технологии

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

Близки к представлениям так называемые снимки, которые

фиксируют состояние БД в определенный момент времени - их

часто используют в системах, где требуются данные на задан-

ный момент времени.

Повышение производительности

с помощью оптимизации

Проблема оптимизации структуры БД связана с проектиро-

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

мотно построенная БД позволяет повысить производительность

всей системы. Другая сторона этой проблемы связана с тем. что

некоторые СУБД для нормального функционирования требуют

оптимизации.

Многие современные СУБД обладают встроенными система-

ми автоматической оптимизации: в частности, это выражается в

том, что конечному пользователю уже не нужно задумываться

над оптимальным выражением запросов - в этом случае сама

СУБД построит запрос наилучшим образом.

Говоря про оптимизацию запросов в реляционных СУБД, обыч-

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

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

вается некий план его выполнения, наиболее приемлемый при суще-

ствующих в БД управляющих структурах. Соответствующие преоб-

разования начального представления запроса выполняются специ-

альным компонентом СУБД - оптимизатором, и оптимальность про-

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

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

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

состоит из фаз, изображенных на рис. 1.29.

На первом этапе запрос, заданный на языке запросов, подверга-

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

вается его внутреннее представление, отражающее структуру запро-

са и содержащее информацию, которая характеризует объекты БД,

упомянутые в запросе (отношения, атрибуты и константы). Инфор-

мация о хранимых в БД объектах выбирается из соответствующих

каталогов. Внутреннее представление запроса используется и пре-

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

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

последующих оптимизационных преобразований.

На втором этапе запрос во внутреннем представлении подвер-

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

Часть I. Теория баз данных

преобразования, "улучшающие" начальное представление запро-

са. Среди преобразований могут быть эквивалентные, после про-

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

чески эквивалентное начальному, например, приведение запроса

к некоторой канонической форме. Преобразования могут быть и

семантическими: получаемое представление не является семан-

тически эквивалентным начальному, но гарантируется, что ре-

зультат выполнения преобразованного запроса совпадает с ре-

зультатом запроса в начальной форме при соблюдении ограниче-

ний целостности, существующих в БД. После выполнения второ-

го этапа обработки запроса его внутреннее представление стано-

вится более эффективным, чем начальное.

Запрос

Лексический и синтаксический

анализ

Логическая оптимизация

Идентификация оптимального

плана обработки

x o.

Генерация выполняемого плана

обработки

Выполнение запроса

Рис. 1.29. Структура обработки запроса в СУБД

Третий этап обработки запроса состоит в том, что реализуется

выбор альтернативных процедурных планов выполнения данного

запроса в соответствии с его внутреннем представлением на ос-

нове информации, которой располагает оптимизатор. При этом

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

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

информации о состоянии БД. Из полученных альтернативных

планов выбирается наиболее выгодный, и его внутреннее пред-

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

Глава 1.5. Дополнительные аспекты реляционной технологии

На четвертом этапе по внутреннему представлению наиболее

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

няемое представление плана. Выполняемое представление плана

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

машинно-независимым. Однако, стоит заметить, что четвертый

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

На последнем этапе обработки запроса происходит его реаль-

ное выполнение. Это либо выполнение соответствующей подпро-

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

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

В традиционном подходе к организации оптимизаторов за-

просов на этапе логической оптимизации производятся эквива-

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

которые "улучшают" начальное внутреннее представление в со-

ответствии со стратегиями оптимизатора. Характер "улучшений"

связан со спецификой общей организации оптимизатора, в част-

ности, с особенностями процедуры поиска возможных процедур-

ных планов запросов, выполняемой на третьем этапе обработки

запроса. Именно по этой причине трудно привести полную ха-

рактеристику и классификацию методов логической оптимиза-

ции, поэтому ограничимся несколькими примерами.

Очевидный класс логических преобразований запроса состав-

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

каноническому представлению. Имеются в визу предикаты, со-

держащие операции сравнения простых значений. Такой преди-

кат имеет вид

арифметическое_выражение1 OPERATOR

арифметическое_выражение2,

где OPERATOR - некая операция сравнения;

арифметическое_выражение1 и арифметиче-

ское_выражение2 - выражения, содержащие имена

атрибутов отношений и константы.

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

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

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

мер, иметь вид

имя_атрибута OPERATOR константа

Эта форма предиката очень полезна при выполнении следую-

щего этапа оптимизации.

Если предикат включает два имени атрибутов разных отно-

шений, то его каноническое представление имеет вид

Часть 1. Теория баз данных

имя_атрибу>га OPERATOR

арифметическое_выражение,

где арифмеч»1чеекое_выражение - включает только

константы и имя второго атрибута.

И, наконец, для рассматриваемых предикатов более общего

вида имеет смысл приведение предиката к каноническому пред-

ставлению вида

арифметическое_выражение OPERATOR

константное арифметическое выражение

Здесь выражения в правой и левой части также должны

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

выражениях должны быть полностью раскрыты скобки. В

дальнейшем можно произвести поиск общих арифметических

выражений в разных предикатах запроса. Это оправдано, по-

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

выражений будет производиться при выборке каждого очеред-

ного кортежа, т.е. потенциально большое число раз. Кроме

того, при приведении предикатов к каноническому представ-

лению желательно вычислять константные выражения и из-

бавляться от логических отрицаний.

Следующий класс логических преобразований связан с приведе-

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

условие выборки запроса. Как правило, используются либо дизъ-

юнктивная, либо конъюнктивная нормальные формы. Выбор кано-

нической формы зависит от общей организации оптимизатора.

При приведении логического условия к каноническому пред-

ставлению производят поиск общих предикатов и упрощают ло-

гическое выражение за счет, например, выявления конъюнкции

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

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

что ускоряет его выполнение.

Необходимо обратить внимание и на тот факт, что в традици-

онных оптимизаторах распространены логические преобразова-

ния, связанные с изменением порядка выполнения реляционных

операций. Хотя немногие реляционные системы имеют языки

запросов, основанные в чистом виде на реляционной алгебре,

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

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

используется в качестве основы внутреннего представления за-

проса, как более универсальное и простое средство. Кроме того,

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

Глава 1.5. Дополнительные аспекты реляционной технологии 71

шло сокращает пространство поиска планов выполнения запроса

с гарантией того, что оптимальные планы не будут потеряны.

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

нием запросов с вложенными запросами. Основным отличием

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

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

жащие вложенные подзапросы. Глубина вложенности не ограни-

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

В этом случае стремятся к такому преобразованию запроса, со-

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

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

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

рый способ выполнения запроса.

Поэтому в общем случае каноническим представлением за-

проса на п отношениях называется запрос, содержащий п-1 пре-

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

подзапросами. Для пояснения этого предлагаем следующий при-

мер, основанный на отношениях, приведенных на рис. 1.23:

ВЫБРАТЬ SPO.OCENKA ИЗ SPO ДЛЯ SPO.SN(ВЫБРАТЬ

SPP.PN ИЗ SPP ДЛЯ SPP.PN="Физика")

преобразуется в эквивалент

ВЫБРАТЬ SPO.OCENKA ИЗ SPO, SPP ДЛЯ SPO.SN =

SPP.PN И SPP.PN="Физика"

Важность таких преобразований обосновывается тем, что оп-

тимизатор получает возможность выбора из большего числа спо-

собов выполнения запросов и способы их выполнения более эф-

фективны. При использовании в оптимизаторе запросов подобно-

го подхода не обязательно производить формальные преобразо-

вания запросов - оптимизатор должен в большей степени исполь-

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

будет распознаваться - это вопрос самой СУБД.

Рассмотренные преобразования запросов основывались на се-

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

БД, к которой адресуется запрос. Любое преобразование может

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

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

БД хранится и некоторая семантическая информация, например,

определяющая целостность данных, что было рассмотрено выше.

Семантическая оптимизация запросов основана на наличии в

БД семантической информации, которую не обязательно

использовать при обработке запроса, но использование которой

Часть I. Теория баз данных

может привести к его оптимальному выполнению. Если семанти-

ческая оптимизация имеет дело только со знаниями, представ-

ленными в виде ограничений целостности БД, то при семантиче-

ской оптимизации производятся преобразования внутренних

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

ется некоторый набор ограничений целостности. Поясним это

примером

Напомним уже рассмотренное выше ограничение целостности

для отношения SP, приведенного на рис. 1.11, которое сформули-

ровано как

СОЗДАТЬ ОГРАНИЧЕНИЕ ЦЕЛОСТНОСТИ RULE

ДЛЯ ВСЕХ SP(SP.OCENKAX) И SP.OCENKA<6)

Если, например, в отношении SP определены эти ограничения

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

PN=2101, то есть

ВЫБРАТЬ SP.OCENKA ИЗ SP ДЛЯ SP.PN=2101

то в ходе семантической оптимизации будут получены внутрен-

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

прос примет вид:

ВЫБРАТЬ SP.OCENKA ИЗ SP ДЛЯ SP.PN=2101 И

(SP.OCENKAX) И SP.OCENKA<6)

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

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

выбор оптимального плана выполнения; из полученных планов

выбирается наиболее дешевый, который и становится реаль-

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

виду, что после преобразования запроса в соответствии с не-

которым правилом к полученному представлению может ока-

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

циклов преобразований. Проблема построения полного набора

семантически эквивалентных представлений запроса на основе

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

сложной. Точное решение этой проблемы может потребовать

вычислительных затрат, соизмеримых с затратами на выпол-

нение запроса по наиболее оптимальному плат'. Поэтому час-

то необходимо применение эвристических алгоритмов, сокра-

щающих пространство поиска, т.е. задающих условие прекра-

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

Глава 1.5. Дополнительные аспекты реляционной технологии 73

Таким образом, одной из сторон повышения производитель-

ности БД есть оптимизация запросов, выполняемая самой СУБД

путем их декомпозиции и преобразования во внутреннее пред-

ставление в несколько этапов с оценкой скорости выполнения.

Домены, отношения и типы данных

Выше уже шел разговор о том, что домены и отношения не

просто набор неких данных, а структуры, имеющие строго опре-

деленный характер (тип) данных. Это выражается, например, в

том, что для выполнения таких операций над отношениями, как

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

надлежащими одному домену, но и совместимы по типу.

Для пояснения рассмотрим следующий пример, основанный на

отношениях, приведенных на рис. 1.23: пользователь может осуще-

ствить запрос, основанный на операции сравнения SPO.SN =

SPP.SN, так как атрибут SN в отношениях принадлежит одному до-

мену и имеет один тип. Однако запрос, предполагающий сравнение

SPO.OCENKA = SPP.PN, не является корректным - атрибуты при-

надлежат разным доменам и СУБД не должна его выполнять.

Иногда проверку соответствия доменов необходимо отключать -

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

торых в БД информация отсутствует. Примером такого вполне кор-

ректного запроса (с предметной точки зрения) может служить вы-

борка данных о студентах по номеру студенческого билета в отно-

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

в принципе, студент может учиться и работать в ВУЗе. Однако в

СУБД, для выполнения такого запроса, система проверки доменов

должна быть неактивна - ведь табельный номер сотрудника и номер

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

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

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

случаях, например, при выборке данных по условию SPO.OCENKA

=5. Атрибут SPO.OCENKA принадлежит домену оценок, а 5 - это

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

менам. По этой причине в СУБД в неявном виде происходит преоб-

разование данных одного типа к одному домену, а значит, в нашем

примере целое число преобразуется к домену оценок и только после

этого происходят дальнейшие действия. Для этих целей в СУБД

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

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

для отмены проверки доменов.

Часть I. Теория баз данных

Таким образом, для упрощения работы СУБД на данные на-

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

домену, а на принадлежность соответствующему типу данных.

При этом система либо проверяет соответствие типов, либо ищет

такую функцию преобразования, чтобы данные стали принадле-

жащими одному типу.

При этом возникает еще одна сторона проблемы использова-

ния типов данных и поддержки в полном смысле понятия домена:

при манипуляциях с доменами ряд операций имеют смысл в

предметной области, а некоторые операции бессмысленны. На-

пример, выборки данных по условиям SPP.PN = "Физика" и

SPP.PN > "Физика" с учетом вышесказанного корректны, но вто-

рой случай смысла в предметной области не имеет.

Поэтому СУБД должно быть известно, какие выражения и

операции являются корректными, а какие - нет, а множество всех

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

домену отнести те или иные данные. Из этого следует, что рас-

смотренное выше требование скалярности данных в домене за-

ключается в том, что они могут иметь достаточно сложную

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

С аналогичной точки зрения рассмотрим теперь отношения.

Заметим, что в реляционной модели отношения являются как бы

конструкторами типов данных: ведь при создании отношения в

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

множеством кортежей, определяемый заголовком. Поэтому, на-

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

шения имели одинаковые наборы имен атрибутов и, кроме того,

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

другом по типу.

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

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

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

выполнением основных операций над отношениями, однако при

изложении в учет не брался тот факт, что заголовок включает в себя

помимо имени атрибута еще и имя домена. Из вышеизложенного

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

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

ляется обязательной, т. к. СУБД производит неявное преобразование

типов доменов.

Следовательно, операция соединения отношений А{А.Х, A.Y}

и B{B.Y, B.Z} является вполне корректной, несмотря на то, что

атрибуты Y имеют одинаковое имя и тип в обоих отношениях, но

определены на различных доменах. При этом возникает интерес-

Глава 1.5. Дополнительные аспекты реляционной технологии 75

ный момент - в полученном в результате выполнения операции

отношении С{С.Х, C.Y, C.Z} неясно, на каком домене определен

атрибут Y. Из совместимости по типу доменов отношений А и В.

на которых определен атрибут Y, следует, что их можно преобра-

зовать один к другому, а в СУБД предусматривают домены с

большим приоритетом.

Атрибуты отношения, как уже упоминалось, состоят из кор-

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

атрибута и его значение, а следовательно, имеющих свой заголо-

вок. Отсюда вытекает, что вопросы совместимости по типу каса-

ются и кортежей при выполнении таких операций, как сравнение,

присваивание и т. д.

Здесь необходимо еще раз остановиться на вопросах, связан-

ных с наследованием типов, которые уже были рассмотрены вы-

ше. Эти вопросы тесно связаны с понятиями подтипа и суперти-

па. Тип X является подтипом типа Y, если каждый экземпляр

типа X обязательно принадлежит типу Y. Соответственно, тип Y

будет являться супертипом для типа X. Например, тип СТУ-

ДЕНТ является подтипом типа УЧАЩИЙСЯ, а тип УЧАЩИЙСЯ

является супертипом для типа СТУДЕНТ.

Эти понятия важны со следующей точки зрения: если СУБД

знает, что экземпляр типа X является подтипом типа Y, то свой-

ства Y. присущи X. В таком случае говорят, что тип X наследует

свойства типа Y, а пользователь имеет возможность применять

данные типа X там, где можно применять данные типа Y - это

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

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

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

либо доработок.

Использование этих принципов для доменов связано с тем.

что, несмотря на наследование свойств, внутренняя структура

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

можно привести к другому. Например, тип СТУДЕНТ можно

привести к типу УЧАЩИЙСЯ, но при обратном преобразовании

может возникнуть потеря информации - у типа СТУДЕНТ может

существовать ряд специфических свойств (например, НАЙМЕ-

НОВАНИЕВУЗА), которых в супертипе может и не быть.

Кроме того, рассматриваемые домены можно представить в

виде простейшей иерархии типов, поскольку супертип есть

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

автоматически при создании наследует все свойства своего су-

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

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

Часть I Теория баз данных

пифические. Возможность применения некой одной функции к

данным различного типа часто называют полиморфизмом. И, на-

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

то в случае доменов в их качестве выступают операторы и функ-

ции - присвоение, сравнение и т. д. в отличие от отношений, где

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

Для пояснения концепции наследования типов применительно

к отношениям рассмотрим пример, приведенный на рис. 1.30.

SPP

NAME

T~PN~T

OCENKA

SPF

NAME

Рис. 1.30. Наследование типов в отношениях

В примере рассмотрено отношение SPP{SN, PN, NAME}, на

основе которого создано отношение SPF{SN, PN, NAME,

OCENKA}, содержащее информацию об успеваемости по физи-

ке. При этом SPF от своего родителя унаследовало атрибуты SN,

PN, NAME, а атрибут OCENKA добавлен при создании. Таким

образом, полученное отношение SPF можно рассматривать как

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

(атрибутом) OCENKA, причем над SPF можно вьшолнять те же

операции и функции, что и над его супертипом.

Неопределенные значения и трехзначная логика

При работе с данными достаточно часто сталкиваются с пробле-

мой недостатка информации, для решения которой в СУБД часто

применяют неопределенные (NULL) значения и трехзначную логи-

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

оценка неизвестна или не выставлена - в этом случае точное обосно-

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

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

Глава 1.5. Дополнительные аспекты реляционной технологии

В связи с этимможет возникнуть вопрос, связанный с тем, что

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

несколько операндов имеют значение NULL, а следовательно

будет получено неизвестное значение в качестве результата. По-

этому, например, при сравнении X и Y, если значение X неопре-

деленное, будет получено значение НЕИЗВЕСТНОЕ, а не ИС-

ТИНА или ЛОЖЬ. Более того, если X и Y приняли неопределен-

ное значение, то выполнение сравнения X и Y также даст в каче-

стве результата значение НЕИЗВЕСТНОЕ, так как оба значения

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

Для идентификации подобных значений требуются специаль-

ные средства СУБД, важнейшим из которых есть оператор ЕС-

ЛИ НЕОПРЕДЕЛЕННОЕ, определяющий, является ли значение-

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

го оператора над неопределенными значениями дает значение

ИСТИНА или ЛОЖЬ; в качестве результата выполнения других

операторов будет получено значение НЕИЗВЕСТНОЕ.

Это свойство можно использовать, скажем, для контроля це-

лостности данных, если значение атрибута не должно принимать

неопределенных значений, например

СОЗДАТЬ ОГРАНИЧЕНИЕ ЦЕЛОСТНОСТИ RULEб

ДЛЯ ВСЕХ 8РР(ЕСЛИ_НЕОПРЕДЕЛЕННОЕ(8РР.Р»))

НЕ ВЫПОЛНЯТЬ ПРИ НАРУШЕНИИ ПРАВИЛА

позволяющее избежать неопределенных значений наименова-

ния предмета в отношении SPP. Приведем таблицы, содержа-

щие возможные значения наиболее важных логических функ-

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

обозначено как "Н" - очевидно, что неопределенное значение

NULL и неизвестное значение, как результат выполнения опе-

рации - это разные вещи).

Таблица 1.1

Возможные значения логической функций И

ИСТИНА

ЛОЖЬ

NULL

ИСТИНА

ЛОЖЬ

ложь

NULL

ЛОЖЬ

Часть I. Теория баз данных

Таблица 1.2

Возможные значения логической функций ИЛИ

ИЛИ

ИСТИНА

ЛОЖЬ

NULL

ИСТИНА

ЛОЖЬ

ИСТИНА

ЛОЖЬ

ИСТИНА

Таблица 1.3

Возможные значения логической функций НЕ

НЕ

ИСТИНА

ЛОЖЬ

NULL

ЛОЖЬ

ИСТИНА

Необходимо обратить внимание на то, что домены неопреде-

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

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

всегда получаться значение ИСТИНА или НЕИЗВЕСТНОЕ.

Введение неопределенного значения, естественно, влияет на

реляционные выражения. Например, операция выборки модифи-

цируется таким образом, чтобы в качестве результата возвраща-

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

только значение ИСТИНА, а для значений ЛОЖЬ или НЕИЗ-

ВЕСТНОЕ не включаются.

Распределенные базы данных

Основная задача систем управления распределенными базами

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

БД, располагающихся в узлах вычислительной сети, с тем, чтобы

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

всем частям, как к единой БД. При этом должны обеспечиваться:

• простота использования системы;

• возможности автономного функционирования при на-

рушениях целостности сети или при административ-

ных потребностях;

• высокая степень эффективности.

Глава 1.5. Дополнительные аспекты реляционной технологии

Традиционно выделяют однородные и неоднородные распре-

деленные БД. В однородных распределенных БД каждая локаль-

ная БД управляется одной и той же СУБД. В отличие от этого, в

неоднородной системе локальные БД могут относиться к разным

моделям данных, поэтому сетевая интеграция неоднородных БД -

это актуальная, но очень сложная проблема. Многие решения

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

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

рированных систем. Более успешно практически решается про-

межуточная задача - интеграция неоднородных SQL-

ориентированных систем. Понятно, что этому в большой степени

способствует стандартизация языка SQL и общее следование

производителей СУБД принципам открытых систем.

Необходимость в распределенных БД возникла в связи с тем,

что современные предприятия могут географически охватывать

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

каждом подразделении и на определенном уровне. Распределение

данных позволяет эффективно использовать имеющееся обору-

дование, рационально загрузить вычислительную сеть и повы-

сить доступность БД.

Реализация распределенных БД преследует ряд целей, пере-

численных ниже. В первую очередь при проектировании распре-

деленной СУБД узлы системы следует делать в максимальной

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

большей степени не должна зависеть от успешного или неуспеш-

ного выполнения какой-либо операции в другом узле.

С другой стороны, все узлы распределенной БД должны рас-

сматриваться системой как равноправные. Зависимость всей сис-

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

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

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

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

ность и доступность.

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

система исправна и работает в заданный момент. Это реализуется

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

ограниченными возможностями) даже если имеет место сбой от-

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

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

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

Распределенная БД должна удовлетворять условию независимо-

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

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