close

Вход

Забыли?

вход по аккаунту

?

Galanina

код для вставкиСкачать
Федеральное агенТство по образованию
Государственное образовательное учреждение
высшего профессионального образования
Санкт-петербургский государственный университет
аэрокосмического приборостроения
В. А. Галанина
БАЗЫ ДАННЫХ
ВВЕДЕНИЕ В ТЕОРИЮ
РЕЛЯЦИОННЫХ БАЗ ДАННЫХ
Учебное пособие
Санкт-Петербург
2008
1
УДК 004.6
ББК 32.973
Г15
Рецензенты:
кафедра вычислительных систем и программирования
Санкт-Петербургского государственного экономического университета;
доктор технических наук, профессор Ю. И. Яременко
Утверждено
редакционно-издательским советом университета
в качестве учебного пособия
Галанина В. А.
Г15 Базы данных: введение в теорию реляционных баз данных: учеб. пособие / В. А. Галанина. – СПб.: ГУАП, 2008. –
108 с.: ил.
ISBN 978-5-8088-0396-1
Рассмотрены основные вопросы организации баз данных и их архитектура. Изложены основные понятия теории реляционных баз
данных и приведены описания основных операций реляционной
алгебры. Рассмотрены вопросы нормализации отношений в реляционной модели данных. Описан альтернативный способ разработки
таблиц в нормальной форме с использованием ER-диаграмм для моделей типа «сущность – связь».
Пособие предназначено для студентов всех форм обучения по
направлению 230100 «Информатика и вычислительная техника».
Также может быть полезно для студентов других специальностей,
изучающих дисциплину «Базы данных».
УДК 004.6
ББК 32.97
ISBN 978-5-8088-0396-1
© ГУАП, 2008
© В. А. Галанина, 2008
ВВЕДЕНИЕ
Основное назначение данного учебного пособия – дать систематическое введение в основы реляционной модели данных и принципы функционирования реляционных баз данных (БД).
Реляционная модель описывает, какие данные могут храниться в реляционных БД, а также способы манипулирования такими
данными. В упрощенном виде основная идея реляционной модели
состоит в том, что данные должны храниться в таблицах и только в
таблицах. Эта, кажущаяся тривиальной, идея оказывается вовсе не
простой при рассмотрении вопроса, а что, собственно, представляет собой таблица? В данный момент существует много различных
систем обработки данных, оперирующих понятием «таблица», например всем известные электронные таблицы, таблицы текстового
редактора MS Word и т. п. Ячейки электронной таблицы могут хранить разнотипные данные, например числа, строки текста, формулы, ссылающиеся на другие ячейки. На одном листе электронной
таблицы можно разместить несколько совершенно независимых
таблиц, если под таблицей понимать прямоугольную область, расчерченную на клеточки и заполненную данными. Таблицы текстовых редакторов могут иметь совершенно произвольную структуру.
Несомненно, и электронные таблицы, и текстовые редакторы
позволяют хранить и обрабатывать данные очень гибко, но как
быть, если требуется хранить информацию обо всех сотрудниках
большого предприятия и периодически выдавать ответы на запросы типа «представить список всех сотрудников, принятых на работу не позднее трех лет назад, имеющих по крайней мере одного
ребенка, не имеющих взысканий и имеющих высшее образование,
полученное в Петербурге или Москве». Получить ответ на такой запрос средствами, имеющимися в MS Excel или MS Word, весьма проблематично.
Для получения ответов на подобные запросы и предназначены
базы данных (БД) и программы управления ими, называемые системами управления базами данных (СУБД).
Классическая реляционная модель данных требует, чтобы данные хранились в так называемых плоских таблицах. Более точно,
пользователи и приложения, обращающиеся к данным, должны
работать с ними так, как если бы они размещались в таких таблицах. В упрощенном виде плоская таблица – это таблица, каждая
ячейка которой может быть однозначно идентифицирована указанием строки и столбца таблицы. Кроме того, в одном столбце все
ячейки должны содержать данные одного простого типа.
3
Реляционная модель основана на теории множеств и математической логике. Такой фундамент обеспечивает ее математическую
строгость.
В свою очередь, на основе реляционной модели разработаны
различные языки для доступа к реляционным данным, такие как
SEQUEL, SQL, QUEL и др. Фактическим промышленным стандартом в
настоящее время стал язык SQL (Structured Query Language – язык
структурированных запросов).
Различные фирмы, производители СУБД, предлагают свои реализации языка SQL. Эти реализации отличаются как друг от друга, так
и от стандартизованного языка SQL. Это и хорошо, и плохо. Хорошо
это тем, что конкретная реализация языка может включать в себя
более широкие возможности по сравнению со стандартизованными
SQL, например большее количество типов данных, команд и дополнительных опций. Такие возможности делают работу с конкретной
СУБД весьма эффективной. Кроме того, такие нестандартные возможности языка проходят практическую апробацию и со временем
могут быть включены в стандарт. Плохо же это тем, что различия
в синтаксисе реализаций SQL затрудняют перенос приложений из
одной системы в другую. Например, если приложение было написано для БД MS SQL Server с использованием своего диалекта SQL – языка
Transact-SQL, то при переносе системы в БД ORACLE, не все конструкции языка будут понятны соответствующему диалекту SQL – языку
PL/SQL.
Взаимосвязь реляционной модели данных, стандарта языка SQL
и различных его реализаций можно условно изобразить в виде следующей пирамиды:
ORACLE, MS SQL
Server и др.
Стандарт SQL
Реляционная модель данных
Теория множеств. Математическая логика
Каждый более высокий уровень основывается на понятиях, определенных на более низком уровне. На каждом из уровней используется своя терминология. Например, на уровне теории множеств мы
4
говорим «множество», «подмножество декартова произведения»,
«кортеж». На уровне реляционной модели используем термины
«домен», «отношение», «кортеж». На уровне стандарта SQL и конкретных реализаций используем термины «тип данных», «таблица»,
«строка таблицы». И каждый раз речь идет об одном и том же.
Учебное пособие, охватывающее круг вопросов, относящихся непосредственно к теории реляционных БД, имеет следующую
структуру.
Первая глава содержит описание общих вопросов организации
БД, в ней рассматриваются три уровня архитектуры БД, приводится
описание логических моделей данных.
Вторая глава содержит описание собственно реляционной модели данных. В ней вводятся базовые понятия реляционной модели
данных, такие как «домен», «отношение», «атрибут», «кортеж»,
«ключ», «внешний ключ» и т. п. Вводится понятие целостности реляционных данных. Обсуждается проблема, связанная с использованием null-значений.
В третьей главе описывается язык доступа к реляционным данным – реляционная алгебра и реляционное исчисление.
Четвертая глава посвящена важным вопросам правильного проектирования отношений. В этой главе вводится понятие нормальных форм отношений, необходимое для проектирования непротиворечивых и неизбыточных таблиц БД.
В пятой главе описывается альтернативный способ разработки
таблиц в нормальной форме – семантическое моделирование с использованием ER-диаграмм для моделей типа «сущность – связь».
5
1. Основные понятия теории баз данных
1.1. Три уровня архитектуры баз данных
Существует очень простое понятие БД как большого по объему
хранилища, в которое организация помещает все используемые ею
данные и из которого различные пользователи могут их получать с
помощью различных приложений. Такая единая БД представляется идеальным вариантом, хотя на практике это решение труднодостижимо. Поэтому чаще всего под БД понимают любой набор хранящихся в компьютере взаимосвязанных данных.
С развитием информационных технологий возрастает объем
взаимосвязанных данных, необходимых для решения различных
задач. Взаимосвязанные данные определяются конкретной предметной областью.
Предметная область – это часть реального мира, данные о которой мы хотим отразить в БД. Например, в качестве предметной
области можно выбрать бухгалтерию какого-либо предприятия,
отдел кадров, банк, магазин и т. д. Предметная область бесконечна и содержит как существенно важные понятия и данные, так и
малозначащие или вообще незначащие данные. Так, если в качестве предметной области выбрать учет товаров на складе, то понятия
«накладная» и «счет-фактура» являются существенно важными
понятиями, а то, что сотрудница, принимающая накладные, имеет
двоих детей – это для учета товаров неважно. Однако, с точки зрения отдела кадров, данные о наличии детей являются существенно важными. Таким образом, важность данных зависит от выбора
предметной области.
Основным вопросом, который приходится решать при автоматизации процесса обработки данных, является вопрос организации
данных. Для понимания организации данных вводится понятие
информационной модели, или модели предметной области.
Модель предметной области – это наши знания о предметной
области. Знания могут быть как в виде неформальных знаний в
«мозгу» эксперта, так и выражены формально при помощи какихлибо средств. В качестве таких средств могут выступать текстовые
описания предметной области, наборы должностных инструкций,
правила ведения дел в компании и т. п. Опыт показывает, что текстовый способ представления модели предметной области крайне
неэффективен.
Гораздо более информативными и полезными при разработке БД
являются описания предметной области, выполненные при помо6
щи специализированных графических нотаций. Имеется большое
количество методик описания предметной области. Из наиболее известных можно назвать методику структурного анализа SADT и основанную на нем IDEF0, диаграммы потоков данных Гейна – Сарсона,
методику объектно-ориентированного анализа UML, и др. Модель
предметной области описывает скорее процессы, происходящие в
предметной области, и данные, используемые этими процессами.
От того, насколько правильно смоделирована предметная область,
зависит успех дальнейшей разработки приложений.
Реализация такой модели в первую очередь призвана облегчить
труд человека, но для этого она должна как можно лучше соответствовать очень сложной модели реального мира.
Процесс создания информационной модели начинается с определения а р х и т е к т у р ы БД. Различают три уровня архитектуры:
− внешний;
− концептуальный;
− внутренний.
В н е ш н и й уровень связан с индивидуальными представлениями пользователей о предметной области. В соответствии с терминологией ANSI/SPARC представление отдельного пользователя называется внешним представлением.
Таким образом, внешнее представление – это содержимое базы
данных, каким видит его определенный пользователь (т. е. для
этого пользователя внешнее представление и есть БД). Например,
пользователь из отдела кадров может рассматривать БД как набор
записей с информацией о сотрудниках и ничего не знать о деталях
и поставщиках, с которыми работает пользователь в отделе обеспечения.
К о н ц е п т у а л ь н ы й уровень – это представления отдельных
пользователей, интегрируемые в едином «обобщенном представлении». Последнее называют концептуальной моделью предметной области. Вообще говоря, концептуальное представление – это
представление данных такими, какие «они есть на самом деле»,
а не такими, какими вынужден их видеть пользователь в рамках
своего представления. Концептуальное представление состоит из
множества экземпляров каждого типа концептуальной записи.
Например, оно может состоять из набора экземпляров записей, содержащих информацию об отделах, плюс набор экземпляров, содержащих информацию о деталях, и т. д. Концептуальная запись
не обязательно должна совпадать (чаще всего именно так и бывает)
с внешней записью, с одной стороны, и с хранимой (физической)
записью – с другой.
7
Для того чтобы концептуальная модель была реализована в
конкретной БД, она должна отвечать определенным требованиям и
правилам ее организации. В соответствии с этими правилами на
основании концептуальной модели строится логическая модель
данных.
Логическая модель строится в терминах информационных единиц, но без привязки к конкретной СУБД. Более того, логическая
модель данных необязательно должна быть выражена средствами
именно реляционной модели данных.
Основным средством разработки логической модели данных
в настоящий момент являются различные варианты ER-диаграмм
(Entity-Relationship, диаграммы «сущность – связь»). Одну и ту же
ER-диаграмму можно преобразовать как в реляционную модель
данных, так и в другие их виды. Но поскольку мы рассматриваем
именно реляционные СУБД, то можно считать, что логическая модель данных для нас формулируется в терминах реляционной модели данных.
Можно заметить, что концептуальная модель может включать
и такие понятия, которые относятся к обеспечению безопасности
и целостности данных. Более того, некоторые авторитетные специалисты предполагают в качестве конечной цели концептуальной
модели – описание всего предприятия – не только сами данные, но
также и то, как эти данные используются: как они перемещаются
внутри предприятия, для чего используются в каждом конкретном
месте, как контролируются и т. п. Однако необходимо подчеркнуть,
что ни одна сегодняшняя система реально не поддерживает такой
концептуальный уровень, который хотя бы немного приблизился
к этой степени развитости. В большинстве существующих систем
(например, 1С-Бухгалтерия) концептуальная модель представляет собой немного больше, чем простое объединение всех внешних
схем с дополнительными средствами безопасности и правилами
обеспечения целостности. Таким образом, понятия «концептуальная модель» и «логическая модель», хотя и относятся к одному
уровню архитектуры БД, но являются не вполне тождественными
понятиями.
В н у т р е н н и й уровень – это внутреннее представление нижнего уровня всей БД; оно состоит из многочисленных экземпляров
каждого типа внутренней записи. Термин «внутренняя запись»
принадлежит терминологии ANSI/SPARC и означает конструкцию,
называемую хранимой записью.
Внутреннее представление описывается с помощью внутренней
модели (или схемы), которая определяет не только различные типы
8
хранимых записей, но также существующие индексы, способы
представления хранимых полей, последовательность хранимых записей. Внутреннее представление данных описывает данные средствами конкретной СУБД. Мы будем считать, что внутренняя модель
данных реализована средствами именно р е л я ц и о н н о й СУБД,
хотя, как уже сказано выше, это необязательно. Отношения, разработанные на стадии формирования логической модели данных,
преобразуются в таблицы, атрибуты становятся столбцами таблиц,
для ключевых атрибутов создаются уникальные индексы, домены
преображаются в типы данных, принятые в конкретной СУБД.
Ограничения, имеющиеся в логической модели данных, реализуются различными средствами СУБД, например при помощи индексов, декларативных ограничений целостности, триггеров, хранимых процедур. При этом опять-таки решения, принятые на уровне
логического моделирования, определяют некоторые границы, в
пределах которых можно развивать внутреннюю модель данных.
Точно так же в пределах этих границ можно принимать различные
решения. Например, отношения, содержащиеся в логической модели данных, должны быть преобразованы в таблицы, но для каждой таблицы можно дополнительно объявить различные индексы,
повышающие скорость обращения к данным. Многое тут зависит
от конкретной СУБД.
При разработке внутренней модели данных возникают вопросы: хорошо ли спроектированы таблицы? Правильно ли выбраны
индексы? Насколько много программного кода в виде триггеров и
хранимых процедур необходимо разработать для поддержания целостности данных?
Внутреннее представление, так же как внешнее и концептуальное, не связано с физическим уровнем, поскольку в нем не рассматриваются физические записи, также называемые блоками или
страницами, и не рассматриваются физические области устройства
хранения, такие как цилиндры и дорожки. В связи с этим необходимо заметить, что термин «физическая модель данных», широко
используемый в современной литературе, не вполне корректен в
данном контексте. Внутреннее представление предполагает бесконечное линейное адресное пространство. Подробности того, как адресное пространство отображено на физическое устройство хранения, очень зависят от системы и умышленно не включены в общую
архитектуру.
З а м е ч а н и е . Вместо терминов «внутреннее представление» и
«внутренняя модель» получили распространение интуитивно более понятные термины «хранимая база данных» и «определение
9
А1
Базовый язык
+ подъязык
Внешняя
схема А
А2
Пользователи
Б1
Внешнее
представление А
Отображение
«внешний – концептуальный А»
Б2
Внешнее
представление Б
Б3
Внешняя
схема Б
Отображение
«внешний – концептуальный Б»
СУБД
Концептуальное
представление
Отображение «концептуальный – внутренний»
АБД
Хранимая база
Рис. 1.1. Три уровня архитектуры базы данных
структуры хранения» соответственно. Будем пользоваться также и
этими определениями.
Схематично все три уровня архитектуры данных можно изобразить следующим образом (рис. 1.1).
Для каждого уровня архитектуры БД предусмотрен свой язык общения. Все эти языки составляют подъязык данных, т. е. подмножество операторов какого-либо языка программирования (базового
языка), связанное только с объектами и операциями БД.
Хотя с точки зрения архитектуры удобно различать подъязык
данных и включающий его базовый язык, на практике они могут
быть неразличимы настолько, насколько это имеет отношение к
пользователю. Безусловно, с точки зрения пользователя, предпочтительнее, чтобы они были неразличимы. Если они неразличимы
или трудноразличимы, их называют сильно связанными. В противном случае имеем слабо связанные языки.
В принципе любой подъязык данных является на самом деле
комбинацией, по крайней мере, двух подчиненных языков – языка определения данных (data definition language – DDL), который
поддерживает определения или объявления объектов БД, и языка
обработки данных (data manipulation language – DML), который поддерживает операции с такими объектами или их обработку.
10
Внешняя схема данных описывается с помощью внешнего языка DDL из пользовательского подъязыка данных.
Например, тип внешней записи можно определить как шестисимвольное поле с номером служащего плюс числовое поле (5 символов) для его зарплаты.
Концептуальная модель (схема) использует свой язык определения данных – концептуальный. Определения концептуального
языка должны относиться только к содержанию информации. Это
означает, что в концептуальной схеме не должно быть никакого
упоминания о представлении хранимого файла, последовательности хранимых записей, индексировании, указателях и т. п.
внутренняя схема пишется с использованием еще одного языка
определения данных – внутреннего.
Рассмотрим еще одну важную составляющую архитектуры БД –
систему СУБД.
СУБД представляет собой программное обеспечение, которое управляет доступом к БД. Это происходит следующим образом.
1. Пользователь выдает запрос на доступ, применяя определенный подъязык данных.
2. СУБД перехватывает этот запрос и анализирует его.
3. Затем СУБД просматривает внешнюю схему этого пользователя, соответствующее отображение (внешний – концептуальный)
концептуальную схему, отображение «концептуальный – внутренний» и определение структуры хранения.
4. И, наконец, СУБД выполняет необходимые операции над хранимой БД.
В качестве примера предположим, что рассматривается выборка определенного экземпляра внешней записи. В общем случае
поля будут использоваться из нескольких экземпляров концептуальных записей, которые, в свою очередь, будут запрашивать поля
из нескольких экземпляров хранимых записей. СУБД должна сначала выбрать все требуемые экземпляры хранимых записей, затем
построить требуемые экземпляры концептуальных записей и после
этого сформировать экземпляр внешней записи.
Приведенный пример является упрощенным, предполагается,
что весь процесс является интерпретируемым, т. е. анализ запроса, проверка различных схем и другие процедуры осуществляются
во время выполнения. На практике, однако, имеется возможность
скомпилировать запрос перед его выполнением, что значительно
производительнее. Современные СУБД используют именно такой
подход.
Таким образом, СУБД должна:
11
− включать в себя компонент языкового процессора для различных языков определения данных;
− уметь обрабатывать запросы пользователей на выборку, изменение или удаление существующих в базе данных или на добавление новых. Другими словами, СУБД должна включать в себя компонент процессора языка обработки данных.
И последняя составляющая, имеющая непосредственное отношение к работе БД, – это администратор базы данных (АБД).
Функции АБД следующие:
− определение концептуальной схемы;
− администратор данных (человек, отвечающий за стратегию и
политику принятия решений на предприятии) определяет, какие
именно данные необходимо сохранять в БД, т. е. определяет объекты, в которых заинтересовано предприятие, а также информацию,
которую необходимо записывать об объектах. Этот процесс обычно
называют концептуальным или логическим проектированием БД.
После того как содержимое БД определено, АБД создает соответствующую концептуальную модель с помощью концептуального языка
определения данных;
− определение внутренней модели данных;
− АБД должен также решить, как данные должны быть представлены в хранимой БД. Этот процесс обычно называют физическим
проектированием БД. После завершения физического проектирования АБД с помощью внутреннего языка определения данных должен
создать соответствующую структуру хранения (т. е. описать внутреннюю схему). Кроме того, он должен определить соответствующее отображение между внутренней и концептуальной схемами;
− взаимодействие с пользователями;
− определение правил безопасности и целостности данных;
− определение процедур резервного копирования и восстановления;
− управление производительностью и реагирование на изменяющиеся требования.
При рассмотрении требований конечных пользователей необходимо принимать во внимание, что БД должна:
− удовлетворять актуальным информационным потребностям
организации т. е. получаемая информация по структуре и содержанию должна соответствовать решаемым задачам;
− обеспечивать получение требуемых данных за приемлемое время, т. е. отвечать заданным требованиям производительности;
12
− удовлетворять выявленным и вновь возникающим требованиям конечных пользователей;
− легко расширяться при реорганизации и расширении предметной области;
− легко изменяться при изменении программной и аппаратной
сред;
− содержать корректные данные;
− до включения в нее данных проверять их на корректность;
− предоставлять доступ к размещаемым данным только лицам с
соответствующими полномочиями.
Сформулируем основные требования, предъявляемые к БД.
Минимальная избыточность. Данные, хранящиеся в памяти
ЭВМ, могут содержать как полезную, так и вредную избыточность.
Последняя всегда имела место до появления концепции БД, когда
каждый пользователь создавал для своих приложений отдельный
набор данных. Если нескольким пользователям требовались одни и
те же данные, то они повторялись в каждом наборе. Такая избыточность в литературе часто называется неконтролируемой, поскольку о ее существовании пользователи могут и не подозревать.
К полезной избыточности можно отнести периодические копии
данных, хранящихся в БД. Эта избыточность легко контролируется, и, кроме того, она является необходимой.
Таким образом, требование минимальной избыточности следует
понимать как устранение неконтролируемой избыточности.
Целостность данных. Она состоит в поддержании правильности данных. Обеспечивается восстановлением данных после разрушения в результате случайных сбоев ЭВМ, а также устранением
противоречивости данных, которая заключается в появлении различных значений для какого-либо элемента данных. Противоречивость может появиться при обновлении данных, если оно будет выполнено только на части данных (нарушен принцип минимальной
избыточности данных)
Безопасность и секретность. Они обеспечивают защиту данных
от аппаратных и программных сбоев, от катастрофических и криминальных ситуаций, а также от некомпетентного или несанкционированного доступа к данным.
Независимость данных. Одно из самых важных условий эффективной работы БД, обеспечивающее возможность изменения структуры БД без изменения прикладных программ пользователей (приложений). Для работы БД крайне нежелательно, чтобы приложения
зависели от данных, и тому есть, по меньшей мере, две причины:
13
– для разных приложений требуются разные представления одних и тех же данных. Например, пусть приложения А и Б используют один и тот же набор данных. Причем, приложение А использует
данные в десятичном формате, а приложение Б – в двоичном. Пусть
данные на физическом носителе записаны в двоичном формате.
Тогда все необходимые преобразования, в частности для приложения А двоичных чисел в десятичные и обратно, должны выполняться не прикладной программой пользователя А, а программным обеспечением системы БД;
– администратор БД должен иметь возможность при необходимости изменять структуру хранения или метод доступа к данным
без изменения приложений. Например, к БД могут быть добавлены
новые виды данных; могут быть изменены приоритеты приложений
и т. д. Если приложения зависят от данных, то перечисленные изменения потребуют изменения программ и усилий программистов, которые могли бы быть направлены на создание новых приложений.
Обеспечение независимости данных представляет собой основную
цель, преследуемую при разработке БД. К. Дж. Дейт [7] определил
независимость данных как « иммунитет приложений к изменениям
в структуре хранения данных и в методах доступа к данным».
1.2. Логические модели данных
Современные СУБД поддерживают три основные модели данных:
− иерархическую;
− сетевую;
− реляционную.
Коротко рассмотрим особенности каждой модели.
Иерархическая модель. Иерархическая модель данных строится по принципу иерархии типов объектов, т. е. один тип объекта
является главным, а остальные, находящиеся на низших уровнях
иерархии, подчиненными. Между главным и подчиненными объектами устанавливается взаимосвязь «один-ко-многим» (1:М).
Иными словами, для данного главного типа объекта существует несколько подчиненных типов объектов. В то же время для каждого
экземпляра главного объекта может быть несколько экземпляров
подчиненных типов объектов.
Иерархическая структура всегда удовлетворяет следующим требованиям.
1. Она всегда начинается с корневого узла.
2. Каждый ее узел состоит из одного или нескольких атрибутов,
которые описывают объект в данном узле.
14
3. На ее нижних уровнях могут находиться зависимые узлы.
Узел предшествующего уровня для новых зависимых узлов является исходным. Зависимые узлы могут добавляться и по горизонтали, и по вертикали.
4. Каждый зависимый узел имеет только один исходный. (Дуга
на схеме только одна.)
5. Исходный узел может иметь в качестве зависимого один или
несколько узлов. Если узел не имеет зависимых, он не является исходным.
6. Доступ к каждому узлу происходит через его исходный узел.
7. Возможно существование любого числа экземпляров узлов
каждого уровня.
Включение и удаление данных в иерархической модели происходит в соответствии со следующим правилом:
– при включении данных экземпляр порожденного узла не может существовать в отсутствие исходного;
– при удалении данных: если удаляется исходный узел, то удаляются и все порожденные.
Д о с т о и н с т в а иерархической модели данных:
– механизм работы с иерархическим представлением данных
изучен, разработаны соответствующие СУБД;
– простота понимания и использования;
– обеспечивает независимость данных;
– легко можно оценить операционные характеристики.
Недостатки:
– избыточность;
– трудность выполнения операции удаления и включения из-за
фиксированной упорядоченности;
– удаление порожденных узлов вследствие удаления исходных;
– отсутствие связи «многие-ко-многим»;
– доступ к любому узлу только через главный.
Сетевая модель. Если мы дополним иерархическую модель связями «многие-ко-многим» М:М, то получим сетевую модель данных. В основе сетевой модели лежит понятие сети, изображаемой
в виде ориентированного графа. Понятие в сетевой модели может
быть одновременно и главным и подчиненным (в сетевой модели
главный объект обозначается термином «владелец набора», а подчиненный – термином «член набора»). Один и тот же объект может
одновременно выступать и в роли владельца, и в роли члена набора.
Это означает, что каждый объект может участвовать в любом числе
взаимосвязей.
15
Д о с т о и н с т в о м сетевой модели является осуществление быстрого доступа к данным, н е д о с т а т о к о м – отсутствие наглядности и в связи с этим трудности решения задач анализа и организации данных.
Обычно сетевые модели служат для первоначального построения
информационной модели предметной области. Затем эта модель упрощается заменой связей «многие-ко-многим» связями «один-комногим».
Реляционная модель. В данной модели объекты и взаимосвязи
между ними представляются с помощью таблиц. Взаимосвязи рассматриваются также в качестве объектов. Каждая таблица представляет один объект и состоит из строк и столбцов. Благодаря своей простоте и естественности представления реляционная модель
получила наибольшее распространение в СУБД для персональных
компьютеров.
Все дальнейшее изложение материала относится именно к реляционной модели данных.
1.3. Собственно база данных и приложения
Результатом реализации трехуровневой архитектуры БД является собственно сама БД. База данных реализована на конкретной
программно-аппаратной основе, и выбор этой основы позволяет существенно повысить скорость работы с БД. Например, можно выбирать различные типы компьютеров, менять количество процессоров, объем оперативной памяти, дисковые подсистемы и т. п. Очень
большое значение имеет также настройка СУБД в пределах выбранной программно-аппаратной платформы.
Но опять решения, принятые на предыдущих уровнях проектирования, определяют границы, в пределах которых можно принимать решения по выбору программно-аппаратной платформы и
настройки СУБД.
Таким образом ясно, что решения, принятые на каждом этапе
моделирования и разработки БД, будут сказываться на дальнейших
этапах. Поэтому особую роль играет принятие правильных решений на ранних этапах моделирования.
Для того чтобы оценить качество принимаемых решений на
уровне логической модели данных, необходимо сформулировать
некоторые критерии качества в терминах внутренней модели и
конкретной реализации и посмотреть, как различные решения,
принятые в процессе логического моделирования, влияют на качество внутренней модели и на скорость работы БД.
16
Таких критериев может быть очень много, и выбор их в достаточной степени произволен. Мы рассмотрим некоторые из таких
критериев, которые являются, безусловно, важными с точки зрения получения качественной БД:
– адекватность БД предметной области;
– легкость разработки и сопровождения БД;
– скорость выполнения операций обновления данных (вставка,
обновление, удаление кортежей);
– скорость выполнения операций выборки данных.
Адекватность базы данных предметной области. База данных
должна адекватно отражать предметную область. Это означает, что
должны выполняться следующие условия:
1. Состояние БД в каждый момент времени должно соответствовать состоянию предметной области.
2. Изменение состояния предметной области должно приводить
к соответствующему изменению состояния БД.
3. Ограничения предметной области, отраженные в модели предметной области, должны некоторым образом отражаться и учитываться БД.
Легкость разработки и сопровождения базы данных. Практически любая БД, за исключением совершенно элементарных, содержит некоторое количество программного кода в виде триггеров и
хранимых процедур.
Хранимые процедуры – это процедуры и функции, хранящиеся
непосредственно в БД в откомпилированном виде и которые могут
запускаться пользователями или приложениями, работающими
с БД. Хранимые процедуры обычно пишутся либо на специальном
процедурном расширении языка SQL (например, PL/SQL для ORACLE
или Transact-SQL для MS SQL Server), или на некотором универсальном языке программирования, например C++, с включением в код
операторов SQL в соответствии со специальными правилами такого
включения. Основное назначение хранимых процедур – реализация бизнес-процессов предметной области.
Триггеры – это хранимые процедуры, связанные с некоторыми
событиями, происходящими во время работы БД. В качестве таких
событий выступают операции вставки, обновления и удаления
строк таблиц. Если в БД определен некоторый триггер, то он запускается а в т о м а т и ч е с к и всегда при возникновении события,
с которым этот триггер связан. Очень важным является то, что
пользователь не может обойти триггер. Триггер срабатывает независимо от того, кто из пользователей и каким способом инициировал событие, вызвавшее запуск триггера. Таким образом, основное
17
назначение триггеров – автоматическая поддержка целостности
БД. Триггеры могут быть как достаточно простыми, например поддерживающими ссылочную целостность, так и довольно сложными, реализующими какие-либо сложные ограничения предметной
области или сложные действия, которые должны произойти при
наступлении некоторых событий. Например, с операцией вставки
нового товара в накладную может быть связан триггер, который
выполняет следующие действия: проверяет, есть ли необходимое
количество товара, при наличии товара добавляет его в накладную
и уменьшает данные о наличии товара на складе, при отсутствии
товара формирует заказ на поставку недостающего товара и тут же
посылает заказ по электронной почте поставщику.
Очевидно, что чем больше программного кода в виде триггеров
и хранимых процедур содержит БД, тем сложнее ее разработка и
дальнейшее сопровождение.
Скорость операций обновления данных (вставка, обновление,
удаление). На уровне логического моделирования мы определяем
реляционные отношения и атрибуты этих отношений. При этом
хорошо бы попытаться ответить на вопрос, влияет ли количество
отношений и количество атрибутов в отношениях на скорость выполнения операций обновления данных. Вопрос недостаточно корректен, так как скорость выполнения операций с БД сильно зависит
от ее физической реализации. Тем не менее можно попытаться качественно оценить это влияние при одинаковых подходах к физическому моделированию.
В базах данных, требующих постоянных изменений (складской
учет, система продажи билетов и т. п.), производительность определяется скоростью выполнения большого количества небольших
операций вставки, обновления и удаления.
Если в таблице имеются индексы, то при выполнении операции
вставки записи индексы должны быть перестроены. Таким образом, скорость выполнения операции вставки уменьшается при увеличении количества индексов у таблицы и мало зависит от числа
строк в таблице.
Рассмотрим операции обновления и удаления записей из таблицы. Прежде чем обновить или удалить запись, ее необходимо
найти. Если таблица не индексирована, то единственным способом
поиска является последовательное сканирование таблицы в поиске
нужной записи. В этом случае скорость операций обновления и удаления существенно увеличивается с увеличением количества записей в таблице и не зависит от количества атрибутов. Но на самом
деле неиндексированные таблицы практически никогда не исполь18
зуются. Для каждой таблицы обычно объявляется один или несколько индексов, соответствующих потенциальным ключам. При
помощи этих индексов поиск записи производится очень быстро и
практически не зависит от количества строк и атрибутов в таблице
(хотя, некоторая зависимость имеется). Если для таблицы объявлено несколько индексов, то при выполнении операций обновления и
удаления эти индексы должны быть перестроены, на что тратится
дополнительное время. Таким образом, скорость выполнения операций обновления и удаления также уменьшается при увеличении
количества индексов у таблицы и мало зависит от числа строк в
таблице.
Можно предположить, что чем больше атрибутов имеет таблица, тем больше для нее будет объявлено индексов. Эта зависимость
не прямая, но при одинаковых подходах к физическому моделированию обычно так и происходит. Таким образом, можно принять
допущение, что чем больше атрибутов имеют отношения, разработанные в ходе логического моделирования, тем медленнее будут
выполняться операции обновления данных, за счет затраты времени на перестройку большего количества индексов.
Дополнительные соображения в пользу приведенного тезиса о
замедлении выполнения операций обновления данных (влияние
журнализации, длины строк таблиц) приведены в работе А. Прохорова [18].
Скорость операций выборки данных. Одно из назначений базы
данных – предоставление информации пользователям. Информация извлекается из реляционной БД при помощи оператора SQL –
SELECT. Одной из наиболее дорогостоящих операций при выполнении оператора SELECT является операция соединение таблиц. Таким
образом, чем больше взаимосвязанных отношений было создано в
ходе логического моделирования, тем больше вероятность того, что
при выполнении запросов эти отношения будут соединяться и, следовательно, тем медленнее будут выполняться запросы. Таким образом, увеличение количества отношений приводит к замедлению
выполнения операций выборки данных, особенно если запросы заранее неизвестны.
19
2. ВВЕДЕНИЕ В РЕЛЯЦИОННЫЕ БАЗЫ ДАННЫХ
2.1. Основные понятия и определения
Основой современной технологии БД, без сомнения, является реляционная модель данных. Для реляционной модели характерны
три основных момента:
− данные воспринимаются пользователем как таблицы и никак
иначе. Таблицы в реляционной системе являются логическими,
а не физическими структурами (внешний и концептуальный уровень представления данных);
− в распоряжении пользователя имеются операторы, которые
генерируют новые таблицы из старых и среди которых есть по
крайней мере такие операторы как: выборка строк, столбцов и объединение;
− все информационное содержимое БД представлено одним и
только одним способом, а именно: явным заданием значений данных. В частности, нет никаких указателей, связывающих одну
таблицу с другой. (Напомним, что речь идет о логическом уровне
представления данных. На физическом уровне они, наверняка,
есть.)
Если реляционная база данных – это БД, в которой данные представлены в виде таблиц, то почему не «табличная» БД? Потому что
термин relation (отношение) – это математическое название определенного вида таблицы. Принципы реляционной модели были изначально заложены в 1969–70-х годах доктором Эдгаром Фрэнком
Коддом, в то время работавшим в корпорации IBM. В конце 1968
года Кодд, математик по образованию, впервые осознал, что математику можно использовать для внесения в область управления БД
строгих принципов и точности, т. е. формализовать этот процесс.
Трудность заключалась в том, что многие распространенные термины были очень нечеткими, например понятие «запись». Это и
экземпляр записи, и тип переменных, физические записи, логические записи и возможно что-то еще. Поэтому в формальной реляционной модели не используется термин «запись», вместо него
используется термин «кортеж».
В реляционной модели рассматриваются три аспекта данных:
− структура данных;
− целостность данных;
− обработка данных.
С т р у к т у р н ы й аспект описывает, какие объекты рассматриваются реляционной моделью. Постулируется, что единственной
20
структурой данных, используемой в реляционной модели, являются нормализованные n-арные отношения.
Ц е л о с т н ы й аспект описывает ограничения специального
вида, которые должны выполняться для любых отношений в любых реляционных БД.
М а н и п у л я ц и о н н ы й аспект описывает два эквивалентных
способа манипулирования реляционными данными – реляционную алгебру и реляционное исчисление.
Рассмотрим структурную часть реляционной модели.
Поскольку реляционная модель является теорией, а большинство теорий сопровождается специальной терминологией, то мы
будет использовать ту терминологию, которая может показаться
неудобной, но к этому необходимо привыкнуть. В каждом из перечисленных аспектов есть своя терминология.
Сначала неформально определим основные термины, используя
для примера табл. 1.1.
S#
Таблица 1.1
SNAME
STATUS
CITY
Кортежи
Кардинальное число
Атрибуты
Отношение соответствует тому, что мы до сих пор называли таблицей.
Кортеж соответствует строке таблицы.
Атрибут соответствует столбцу таблицы.
Кардинальное число определяется количеством кортежей в таблице.
Степень определяется количеством атрибутов.
Первичный ключ – это уникальный идентификатор для таблицы, т. е. столбец или такая комбинация столбцов, что в любой момент времени не существует двух строк, содержащих одинаковое
значение в этом столбце или комбинации столбцов.
21
Домен – это общая совокупность значений, из которой берутся
настоящие значения для определенных атрибутов определенного
отношения.
Рассмотрим введенные понятия более подробно.
Для этого используем классический пример из теории БД, известный как БД Поставщиков и Деталей. Имеем три таблицы: «Поставщики» (рис. 2.1), «Детали» (рис. 2.2), «Поставки» (рис. 2.3) и соответственно имеем три отношения S,P и SP.
В качестве отправной точки возьмем наименьшую семантическую единицу данных – скаляр. Скалярные значения представляют
собой наименьшую семантическую единицу в том смысле, что они
атомарны: у них нет внутренней структуры, т. е. они не разложимы
в реляционной модели. Это не значит, что они не имеют внутренней
структуры вообще: фамилия состоит из букв, но каждая буква в отдельности не имеет содержательного значения для данной реляционной модели.
S#
SNAME
STATUS
CITY
S1
S2
S3
S4
S5
Смит
Джонс
Блэйк
Кларк
Адамс
20
10
30
20
30
Лондон
Париж
Париж
Лондон
Рим
S
Рис. 2.1. Отношение S
P#
PNAME
COLOR
WEIGHT
CITY
P1
P2
P3
P4
P5
Гайка
Болт
Винт
Винт
Подшипник
Красный
Зеленый
Голубой
Красный
Черный
12
17
17
14
22
Лондон
Париж
Париж
Лондон
Рим
Рис. 2.2. Отношение P
S#
P#
QTY
S1
S2
S3
S4
S5
P1
P2
P3
P4
P5
200
100
300
200
300
Рис. 2.3. Отношение SP
22
SP
P
Домены. Используя введенное понятие, дадим следующее определение домену. Домен – это поименованное множество скалярных
значений одного типа. Домен – это семантическое понятие. Домен
можно рассматривать как подмножество значений некоторого типа
данных, имеющих определенный смысл. Домен характеризуется
следующими свойствами:
– имеет уникальное имя (в пределах БД);
– определен на некотором простом типе данных или на другом
домене;
– может иметь некоторое логическое условие, позволяющее описать подмножество данных, допустимых для данного домена;
– несет определенную смысловую нагрузку.
Например, домен D, имеющий смысл «возраст сотрудника»,
можно описать как следующее подмножество множества натуральных чисел:
D = {n € N: n ≥ 18 and n ≤ 60}
Если тип данных можно считать множеством всех возможных
значений данного типа, то домен напоминает подмножество в этом
множестве.
Отличие домена от понятия подмножества состоит именно в том,
что домен о т р а ж а е т с е м а н т и к у , определенную предметной
областью. Может быть несколько доменов, совпадающих как подмножества, но несущие различный смысл. Например, домены «Вес
детали» и «Имеющееся количество» можно одинаково описать, как
множество неотрицательных целых чисел, но смысл этих доменов
будет различным, и это будут различные домены.
Основное значение доменов состоит в том, что домены о г р а н и ч и в а ю т с р а в н е н и я . Некорректно, с логической точки зрения,
сравнивать значения из различных доменов, даже если они имеют
одинаковый тип. В этом проявляется смысловое ограничение доменов. Синтаксически правильный запрос «выдать список всех деталей, у которых вес детали больше имеющегося количества» не
соответствует смыслу понятий «количество» и «вес».
Таким образом, если значения двух атрибутов взяты из одного
и того же домена, тогда сравнения, а отсюда и соединения, объединения и многие другие операции, использующие эти два атрибута,
будут иметь смысл. И наоборот, если значения двух атрибутов взяты из различных доменов, тогда перечисленные выше операции не
будут иметь смысла. Поэтому преимущество системы поддержки
доменов заключается в том, что такая система способна предотвратить грубые ошибки. Понятие домена помогает правильно моде23
лировать предметную область. При работе с реальной системой в
принципе возможна ситуация, когда требуется ответить на запрос,
приведенный выше. Система даст ответ, но, вероятно, он будет бессмысленным.
Не всегда очевидно, как задать логическое условие, ограничивающее возможные значения домена. Как, например, задать условие на строковый тип данных, задающий домен «Фамилия сотрудника». Ясно, что строки, являющиеся фамилиями, не должны начинаться с цифр, служебных символов, мягкого знака и т. д. Но
вот является ли допустимой фамилия «Ггггггыыыыы»? Почему
бы нет? Очевидно, нет! А, может, кто-то назло так себя назовет.
Трудности такого рода возникают потому, что смысл реальных
явлений далеко не всегда можно формально описать. Просто мы
интуитивно понимаем, что такое фамилия, но никто не может дать
такое формальное определение, которое отличало бы фамилии
от строк, фамилиями не являющимися. Выход из этой ситуации
простой – положиться на разум сотрудника, вводящего фамилии
в компьютер.
З а м е ч а н и е . Язык SQL не осуществляет поддержку доменов в
указанном выше смысле. Поэтому на приведенный выше запрос будет получен формальный ответ, который не имеет смысла.
Чтобы конкретизировать идеи реляционной модели, мы будем
использовать г и п о т е т и ч е с к и й реляционный язык для иллюстрации этих идей. Обращаем внимание на то, что вводимые операторы являются операторами языка реляционной алгебры, а не операторами какой-либо версии языка SQL, хотя и имеют с ним много
общего.
Операторы будем вводить по ходу изложения. В первую очередь
нам нужен способ задания нового домена:
CREATE DOMAIN domain data-type;
Пример:
CREATE DOMAIN S# CHAR(5);
CREATE DOMAIN NAME CHAR(20);
и т. д.
При создании нового домена с помощью оператора CREATE DOMANE
СУБД создает запись в каталоге с описанием этого нового домена.
Атрибут может иметь имя, как совпадающее с именем соответствующего домена, так и отличное от него. Чтобы избежать двусмысленности, рекомендуется использовать разные, но похожие
имена (например, отличающиеся первой буквой).
24
Удалить домен можно с помощью следующего оператора:
DESTROY DOMAIN domain;
С помощью этого оператора удаляется элемент каталога, описывающий домен, поэтому такой домен становится неизвестным для
системы.
Рассмотрим запрос, который формулируется так: «Какие отношения в базе данных включают атрибут, который определен на
домене поставщика?»
В системе, поддерживающей понятие домена, такой запрос
транслируется в простой запрос к каталогу. В системе, которая не
поддерживает домены, очевидно, невозможно обратиться с запросом к каталогу относительно доменов. Можно обратиться только
через атрибуты.
Отношения, атрибуты, кортежи отношения. А теперь выясним,
что же такое отношение.
Есть два понятия – переменная отношения и значение отношения.
Переменная отношения – это обычная переменная, такая же,
как и в языках программирования, т. е. именованный объект, значения которого могут меняться со временем.
Значение переменной в любой момент времени – значение отношения.
Поэтому далее, говорять об «отношении», мы будем иметь в виду
значение отношения.
Отношение задается следующим образом:
CREATE BASE RELATION relation (задание базовой таблицы)
Пример:
CREATE BASE RELATION P
(P# DOMAIN (P#),
SNAME DOMAIN (NAME),
COLOR DOMAIN (COLOR)) и т. д.
О п р е д е л е н и е 1. Атрибут отношения есть пара вида <Имя_атрибута: Имя_домена>.
Имена атрибутов должны быть уникальны в пределах отношения. Часто имена атрибутов отношения совпадают с именами соответствующих доменов.
О п р е д е л е н и е 2. Отношение R, определенное на множестве
доменов (не обязательно различных), содержит две части: заголовок и тело.
25
З а г о л о в о к отношения содержит фиксированное количество
атрибутов отношения:
{ <A1:D1>, <A2:D2>, …, <An:Dn>}
Т е л о отношения содержит множество кортежей отношения.
Каждый кортеж отношения представляет собой множество пар
вида <Имя_атрибута: Значение_атрибута>:
{ <A1:ai1>, <A2:ai2>, …, <An:ain>}
Для любой пары <Aj: aij >, aij является значением из уникального домена Dj, который связан с атрибутом Aj; i = 1…m – кардинальное число; j = 1…n – степень отношения R.
Отношение обычно записывается в виде:
R{ <A1:D1>, <A2:D2>, …, <An:Dn>}
или короче
R{ A1,A2, …,An>},
или просто R.
Подытоживая сказанное об отношениях, можно сделать следующие выводы:
1. Заголовок отношения описывает декартово произведение доменов, на котором задано отношение. Заголовок статичен, он не
меняется во время работы с БД. Если в отношении изменены, добавлены или удалены атрибуты, то в результате получим уже другое
отношение (пусть даже с прежним именем).
2. Тело отношения представляет собой набор кортежей, т. е. подмножество декартова произведения доменов. Таким образом, тело
отношения, собственно, и является отношением (значением отношения) в математическом смысле слова.
О п р е д е л е н и е 3. Реляционной БД называется набор отношений.
О п р е д е л е н и е 4. Схемой реляционной БД называется набор
входящих в нее заголовков отношений.
Хотя любое отношение можно изобразить в виде таблицы, нужно четко понимать, что отношения не являются таблицами. Это
близкие, но не совпадающие понятия.
Сформулируем, в каком же случае таблицу можно рассматривать как изображение отношения.
Для этого необходимо, чтобы соблюдались следующие условия:
− мы должны условиться, что есть некоторые лежащие в основе
таблицы домены;
26
− каждый столбец соответствует только одному из этих доменов;
− каждая строка представляет собой кортеж;
− каждое значение атрибута принадлежит соответствующему
домену.
Если принять эти правила интерпретации, то тогда, и только
тогда можно говорить, что таблица – это приемлемое изображение
отношения.
Другими словами – таблица и отношение – это не одно и то же.
Отношение – это абстрактный вид объекта, а таблица – его конкретное изображение. Конечно, они близки и в формальном контексте их обычно отождествляют. Но когда мы хотим говорить более
формально и точно, то должны признать, что эти два понятия не
являются идентичными.
Переменная отношения задается следующим образом:
CREATE BASE RELATION S
Это выражение определяет переменную с именем S, значение
которой в любой момент времени является, как уже было сказано,
отношением. Однако это значение изменяется во времени, так как
могут появиться новые кортежи поставщиков и/или существующие кортежи могут модифицироваться. Отсюда, как следствие –
кардинальное число также будет изменяться со временем.
«Изменяющийся со временем» – не очень удачный термин. В
языках программирования имеется аналог – «переменная целого
типа», поэтому и будем называть ее переменной отношения.
Теперь, пусть R – переменная отношения; переменная R будет
иметь разные значения, однако все возможные значения переменной R будут иметь одинаковые заголовки (схему отношения).
Удаление базовых отношений. Синтаксис оператора удаления
следующий:
DESTROY BASE RELATION <имя отношения>;
Эта операция предназначена для удаления всех кортежей указанного базового отношения с последующим удалением всех записей в каталоге об этом отношении. После этого отношение больше
не известно системе.
Свойства отношений. Свойства отношений непосредственно следуют из приведенного выше определения отношения. В этих свойствах в основном и состоят различия между отношениями и таблицами.
1. В отношении нет одинаковых кортежей – свойство следует
из того факта, что тело отношения – это математическое множество
27
(кортежей), а множества, по определению, не содержат одинаковых элементов. (Отличие от таблицы: таблица м о ж е т содержать
одинаковые строки. Поэтому отношение, содержащее одинаковые
кортежи, не будет отношением по определению.)
З а м е ч а н и е . К сожалению, стандарт языка SQL допускает,
чтобы таблицы содержали одинаковые строки.
Важным следствием требования к отсутствию одинаковых строк
является возможность введения первичных ключей. (Об этом будет
сказано ниже.)
2. Кортежи не упорядочены сверху вниз, что также следует из
определения тела отношения как множества. Простые множества
не упорядочены. Поэтому в отношении нет понятий «первый кортеж», «пятый кортеж», «десятый кортеж» и т. д., т. е. нет понятия
позиционной адресации и понятия «последовательности».
3. Атрибуты не упорядочены слева направо – свойство следует
из того факта, что заголовок отношения также определен как множество (множество атрибутов). В приведенном примере атрибуты
могли располагаться в другом порядке. Это было бы то же самое
отношение. Поэтому здесь также нет понятия «первый атрибут»,
«пятый атрибут», «следующий атрибут» и т. д. Иначе говоря, атрибут всегда определяется по имени, а не по расположению.
4. Все значения атрибутов атомарные – последнее свойство
вытекает из того, что все лежащие в основе отношения домены атомарные.
Виды отношений. В реляционных системах встречаются следующие виды отношений:
Именованное отношение – это переменная отношения, определенная в СУБД посредством оператора CREATE BASE RELETION и некоторых других, о которых речь пойдет ниже.
Базовое отношение – именованное отношение, являющееся частью БД в отличие от отношений, являющихся результатами, например, запроса к базе.
Производное отношение – отношение, определенное посредством реляционного выражения через другие именованные отношения и в конечном итоге – через базовые отношения.
Выражаемое отношение – отношение, которое можно получить из набора именованных отношений посредством некоторого
реляционного выражения. Базовые отношения, промежуточные и
окончательные результаты отчетов – все это выражаемые отношения. Иначе говоря, множество всех выражаемых отношений – это
есть множество всех базовых и всех производных отношений (неко28
торые авторы понимают под «производными» отношениями «выражаемые».
Представлением называется именованное производное отношение. Представления, как и базовые отношения, являются переменными отношений. Представления виртуальны – они представлены
в системе исключительно через определения в терминах других
именованных отношений.
Снимки (snapshot) – это именованные производные отношения,
такие же, как представления. Однако в отличие от представлений
снимки реальны. Создание снимка похоже на выполнение запроса, за исключением того, что результат такого запроса сохраняется
в БД под определенным именем как отношение, доступное только
для чтения, и периодически снимок обновляется, т. е. его текущее
значение сбрасывается, запрос выполняется снова и его результат
становится новым значением снимка.
Пример:
CREATE SNAPSHOT SC AS
((S JOIN SP) WHERE P# = ‘P2’) [S#, CITY]
REFRESH EVERY DAY);
2.2. Целостность реляционных данных
Вопросы, связанные с обеспечением целостности данных, имеют наименее твердую научную основу. Именно в этой области несколько раз менялись некоторые основные определения. Поэтому
остановимся на самых важных правилах, относящихся к любой БД.
Среди них два особых правила, относящиеся к п о т е н ц и а л ь н ы м (и первичным) ключам и к в н е ш н и м ключам.
Хотя основная идея потенциальных и внешних ключей довольно проста, имеется, к сожалению, один осложняющий фактор – это
null-значения (неопределенные значения). Возможность того, что
внешний ключ может допускать null-значения, портит всю картину. Поэтому, прежде чем переходить к определению потенциальных и внешних ключей, остановимся на описании null-значений.
2.2.1. Null-значения
Основное назначение БД состоит в том, чтобы хранить и предоставлять информацию о реальном мире. Для представления этой
информации в БД используются привычные для программистов
типы данных – строковые, численные, логические и т. п. Однако в
реальном мире часто встречается ситуация, когда данные неизвестны или не полны. Например, место жительства или дата рождения
29
человека могут быть неизвестны (БД разыскиваемых преступников).
Если вместо неизвестного адреса уместно было бы вводить пустую
строку, то что вводить вместо неизвестной даты? Ответ – пустую
дату – не вполне удовлетворителен, так как простейший запрос
«выдать список людей в порядке возрастания дат рождения» даст
заведомо неправильный ответ.
Для того чтобы обойти проблему неполных или неизвестных
данных, в БД могут использоваться типы данных, дополненные
null-значением, собственно, не значением, а неким маркером, показывающим, что значение неизвестно.
Таким образом, в ситуации, когда возможно появление неизвестных или неполных данных, разработчик имеет на выбор два варианта.
П е р в ы й вариант состоит в том, чтобы ограничиться использованием обычных типов данных и не использовать null-значения, а
вместо неизвестных данных вводить либо нулевые значения, либо
значения специального вида: например, договориться, что строка
«АДРЕС НЕИЗВЕСТЕН» и есть те данные, которые нужно вводить вместо
неизвестного адреса. В любом случае на пользователя (или на разработчика) ложится ответственность за правильную трактовку таких
данных. В частности, может потребоваться написание специального программного кода, который в нужных случаях «вылавливал»
бы такие данные. Проблемы, возникающие при этом, очевидны: не
все данные становятся равноправны, требуется дополнительный
программный код, «отслеживающий» эту неравноправность, в результате чего усложняется разработка и сопровождение приложений.
В т о р о й вариант состоит в использовании null-значений вместо неизвестных данных. За кажущейся естественностью такого
подхода скрываются менее очевидные и более глубокие проблемы.
Наиболее бросающейся в глаза проблемой является необходимость
использования трехзначной логики при оперировании с данными,
которые могут содержать null-значения. В этом случае при неаккуратном формулировании запросов даже самые естественные запросы могут давать неправильные ответы. Есть более фундаментальные проблемы, связанные с теоретическим обоснованием корректности введения null-значений: например, непонятно, входят ли
null-значения в домены или нет.
Практически все реализации современных реляционных СУБД
позволяют использовать null-значения, несмотря на их недостаточную теоретическую обоснованность. Такую ситуацию можно срав30
нить с ситуацией, сложившейся в начале века с теорией множеств.
Почти сразу после создания Кантором теории множеств, в ней были
обнаружены внутренние противоречия (антиномии). Были разработаны более строгие теории, позволяющие избежать этих противоречий (конструктивная теория множеств). Однако в реальной
работе большинство математиков пользуется классической теорией множеств, так как более строгие теории ограничены и негибки в
применении именно из-за своей большей строгости.
Приведем описание трехзначной логики, необходимой для работы с null-значениями.
2.2.2. Трехзначная логика (3VL)
Так как null-значение обозначает на самом деле тот факт, что
значение неизвестно, то любые алгебраические операции (сложение, умножение, конкатенация строк и т. д.) должны давать также
неизвестное значение, т. е. null. Действительно, если, например,
вес детали неизвестен, то неизвестно также, сколько весят 10 таких деталей.
При сравнении выражений, содержащих null-значения, результат также может быть неизвестен. например, значение истинности
для выражения a = b есть null, если один или оба аргумента есть
null. Таким образом, определение истинности логических выражений базируется на трехзначной логике (three-valued logic, 3VL),
в которой кроме значений T – ИСТИНА и F – ЛОЖЬ, введено значение
U – НЕИЗВЕСТНО. Логическое значение U – это то же самое, что и nullзначение. Трехзначная логика базируется на следующих таблицах
истинности (рис. 2.4–2.6):
Имеется несколько парадоксальных следствий применения
трехзначной логики.
П а р а д о к с 1. Null-значение не равно самому себе. Действительно, выражение null = null дает значение не ИСТИНА, а НЕИЗВЕСТНО.
Значит, выражение x = x не обязательно ИСТИНА!
AND
F
T
U
OR
F
T
U
NOT
F
T
F
F
F
T
F
U
U
F
U
U
F
T
U
F
T
U
T
T
T
U
T
U
F
T
U
Рис. 2.4. Таблица
истинности AND
Рис. 2.5. Таблица
истинности OR
T
F
U
Рис. 2.6. Таблица
истинности NOT
31
П а р а д о к с 2. Неверно также, что null-значение не равно самому себе! Действительно, выражение null null также принимает
значение не ИСТИНА, а НЕИЗВЕСТНО! Значит, так же как и выражение
x ≠ x, тоже не обязательно ЛОЖЬ!
П а р а д о к с 3. Выражение a or not(a) не обязательно ИСТИНА.
Значит, в трехзначной логике не работает принцип исключенного
третьего (любое высказывание либо истинно, либо ложно).
Таких парадоксов можно построить сколько угодно. Конечно,
это на самом деле не парадоксы, а просто следствия из аксиом трехзначной логики.
А теперь вернемся к рассмотрению потенциальных и внешних
ключей.
2.2.3. Потенциальные ключи
Первичный ключ, который ранее уже упоминался как уникальный идентификатор, является частным случаем более общего понятия – потенциального ключа.
Пусть R – некоторая переменная отношения. Тогда потенциальный ключ, скажем, K для R – это подмножество множества атрибутов R, всегда обладающее следующими свойствами:
Свойство у н и к а л ь н о с т и : нет двух различных кортежей в
текущем значении переменной R с одинаковым значением K.
Свойство н е и з б ы т о ч н о с т и : никакое из подмножеств K не
обладает свойством уникальности. Поскольку каждое отношение
не содержит одинаковых кортежей, то оно имеет по крайней мере
один потенциальный ключ, состоящий из комбинации всех атрибутов.
Синтаксис операторов определения потенциального ключа:
CANDIDATE KEY ( список атрибутов, входящих в потенциальный
ключ).
З а м е ч а н и е . Потенциальный ключ определен на множестве атрибутов. Поэтому правильнее было бы записать {S#}. Однако обычно скобки опускают, если потенциальный ключ содержит
один атрибут.
Если потенциальный ключ состоит из нескольких атрибутов,
его называют составным, иначе – простым.
Возможен вариант, когда в отношении имеется несколько потенциальных ключей. Например, таблица химических элементов,
описываемая отношением ЭЛЕМЕНТ. У каждого элемента этой таблицы есть уникальный номер, обозначение и атомное число. Таким
образом, имеем три потенциальных ключа:
32
CANDIDATE KEY (NAME)
CANDIDATE KEY (SYMBOL)
CANDIDATE KEY (NUMBER)
По традиции в реляционной модели один из потенциальных
ключей должен быть выбран в качестве первичного ключа. Если же
есть всего один потенциальный ключ, то именно он должен быть
выбран в качестве первичного ключа. Остальные потенциальные
ключи будут называться альтернативными.
Пример:
CREATE BASE RELATION P
(P# DOMAIN (P#),
SNAME DOMAIN (NAME),
COLOR DOMAIN (COLOR))
PRIMARY KEY (P#)
2.2.4. Внешние ключи
Обратимся к БД поставщиков и деталей и рассмотрим атрибут
S# отношения SP (см. рис. 2.3). Ясно, что значение этого атрибута
должно совпадать с соответствующим значением первичного ключа S# отношения S (см. рис. 2.2). Аналогично, значение атрибута
P# отношения SP должно совпадать с соответствующим значением
первичного ключа P# (см. рис. 2.1).
А теперь определим, что же такое внешний ключ.
Пусть R2 – базовое отношение. Тогда внешний ключ, скажем, FK, в
отношении R2 – это подмножество множества атрибутов, такое что:
а) существует базовое отношение R1 с первичным ключом PK;
б) каждое значение FK в текущем значении R2 всегда совпадает с
первичным ключом PK в текущем значении R1.
Отношение, которое содержит внешний ключ, называется ссылающимся отношением.
Отношение, содержащее соответствующий первичный ключ,
называется ссылочным, или целевым, отношением.
Для нашего примера с с ы л о ч н а я диаграмма будет иметь следующий вид:
S
SP
P
Отношение R1 иногда называют родительским отношением, а
отношение R2 – дочерним отношением.
Для внешнего ключа не требуется, чтобы он был компонентом
первичного ключа или какого-либо потенциального ключа в содержащем его отношении. В нашем примере оба внешних ключа S# и
P# вместе составляют первичный ключ отношения SP.
33
Внешний ключ, как правило, не обладает свойством уникальности. Так и должно быть, поскольку в дочернем отношении может
быть несколько кортежей, ссылающихся на один и тот же кортеж
родительского отношения. Это, собственно, и дает тип отношения
«один-ко-многим».
Если внешний ключ все-таки обладает свойством уникальности,
то связь между отношениями имеет тип «один-к-одному». Чаще
всего такие отношения объединяются в одно отношение, но это не
обязательно.
З а м е ч а н и е . Хотя каждое значение внешнего ключа обязано
совпадать со значениями потенциального ключа в некотором кортеже родительского отношения, то обратное, вообще говоря, неверно. Например, могут существовать поставщики, не поставляющие
никаких деталей.
Синтаксис определения внешнего ключа
Внешний ключ задается следующим образом:
FOREIGN KEY (список атрибутов)
REFERENCES (имя базового отношения)
Пример:
CREATE BASE RELATION SP
(P# DOMAIN (P#),
S# DOMAN (S#)
QTY DOMAIN (QTY))
PRIMARY KEY (P#, S#)
FOREIGN KEY (P#) REFERENCES P
FOREIGN KEY (S#) REFERENCES S
2.2.5. Правило ссылочной целостности
Вместе с понятием внешнего ключа реляционная модель включает следующее правило, называемое правилом ссылочной целостности.
База данных не должна содержать несогласованных значений
внешних ключей, т. е. таких значений внешних ключей, для которых не существует соответствующих значений потенциального
(первичного) ключа в соответствующем отношении.
Любое состояние БД, не удовлетворяющее этому правилу, некорректно.
Как избежать этой некорректности?
Одна из возможностей состоит в том, чтобы запретить любые
операции, приводящие к некорректности. Однако предпочтитель34
нее допускать такую операцию, выполняя некоторые компенсирующие действия, такие, чтобы в результате система оставалась в
корректном состоянии.
Например, если пользователь пытается удалить поставщика S1
из отношения S, система сама может удалить поставки этого поставщика из отношения SP без каких-либо действий со стороны
пользователя (каскадное обновление записей). Правда, если предположить, что пользователь ожидает такого результата.
Следовательно, у пользователя должна быть возможность определить, какие операции должны быть разрешены, а какие запрещены.
(Здесь мы немного отвлечемся от рассмотрения самой реляционной модели.)
Рассмотрим операции, приводящие к нарушению ссылочной целостности БД.
Ссылочная целостность может нарушиться в результате операций, изменяющих состояние БД. Таких операций три – вставка, обновление и удаление кортежей в отношениях. Так как в определении ссылочной целостности участвуют два отношения – родительское и дочернее, а в каждом из них возможны три операции – вставка, обновление, удаление, то нужно рассмотреть шесть различных
вариантов.
Для родительского отношения:
– в с т а в к а кортежа – возникает новое значение потенциального ключа. Так как допустимо существование кортежей в родительском отношении, на которые нет ссылок из дочернего отношения,
то вставка кортежей в родительское отношение не нарушает ссылочной целостности.
– о б н о в л е н и е кортежа – может измениться значение потенциального ключа. Если есть кортежи в дочернем отношении,
ссылающиеся на обновляемый кортеж, то значения их внешних
ключей станут некорректными. Обновление кортежа в родительском отношении может привести к нарушению ссылочной целостности, если это обновление затрагивает значение потенциального
ключа.
– у д а л е н и е кортежа – удаляется значение потенциального
ключа. Если есть кортежи в дочернем отношении, ссылающиеся на
удаляемый кортеж, то значения их внешних ключей станут некорректными. Удаление кортежей в родительском отношении может
привести к нарушению ссылочной целостности.
35
Для дочернего отношения:
– в с т а в к а кортежа – нельзя вставить кортеж в дочернее отношение, если вставляемое значение внешнего ключа некорректно,
поскольку она может привести к нарушению ссылочной целостности.
– о б н о в л е н и е кортежа – можно попытаться некорректно изменить значение внешнего ключа, обновление кортежа может привести к нарушению ссылочной целостности.
– у д а л е н и е кортежа – ссылочная целостность не нарушается.
Таким образом, ссылочная целостность в принципе может быть
нарушена при выполнении одной из четырех операций:
– обновление кортежа в родительском отношении;
– удаление кортежа в родительском отношении;
– вставка кортежа в дочернее отношение;
– обновление кортежа в дочернем отношении.
Стратегии поддержания ссылочной целостности
Существуют две основные стратегии поддержания ссылочной
целостности:
– RESTRICT (ОГРАНИЧИТЬ) – не разрешать выполнение операции,
приводящей к нарушению ссылочной целостности. Это самая простая стратегия, требующая только проверки, имеются ли кортежи
в дочернем отношении, связанные с некоторым кортежем в родительском отношении.
– CASCADE (КАСКАДИРОВАТЬ) – разрешить выполнение требуемой
операции, но внести при этом необходимые поправки в других отношениях так, чтобы не допустить нарушения ссылочной целостности и сохранить все имеющиеся связи. Изменение начинается
в родительском отношении и каскадно выполняется в дочернем
отношении. В реализации этой стратегии имеется одна тонкость,
заключающаяся в том, что дочернее отношение само может быть
родительским для некоторого третьего отношения. При этом может дополнительно потребоваться выполнение какой-либо стратегии и для этой связи и т. д. Если при этом какая-либо из каскадных
операций (любого уровня) не может быть выполнена, то необходимо отказаться от первоначальной операции и вернуть БД в исходное
состояние. Это самая сложная стратегия, но она хороша тем, что
при этом не нарушается связь между кортежами родительского и
дочернего отношений.
Эти стратегии являются стандартными и присутствуют во всех
СУБД, в которых имеется поддержка ссылочной целостности.
36
В связи с этим расширим синтаксис определения внешнего
ключа:
FOREIGN KEY (…) REFRENCES <имя базового отношения>
DELETE option
UPDATE option
Здесь параметр option может принимать значение RESTRICT (ограничивать) или CASCADE (каскадировать).
Кроме приведенных стратегий существуют дополнительные
стратегии поддержания ссылочной целостности:
– SET NULL (УСТАНОВИТЬ В NULL) – разрешить выполнение требуемой операции, но все возникающие некорректные значения внешних ключей изменять на null-значения. Эта стратегия имеет два недостатка. Во-первых, для нее требуется допустить использование
null-значений. Во-вторых, кортежи дочернего отношения теряют
всякую связь с кортежами родительского отношения. Установить,
с каким кортежем родительского отношения были связаны измененные кортежи дочернего отношения, после выполнения операции уже нельзя.
– SET DEFAULT (УСТАНОВИТЬ ПО УМОЛЧАНИЮ) – разрешить выполнение
требуемой операции, но все возникающие некорректные значения
внешних ключей изменять на некоторое значение, принятое по
умолчанию. Достоинство этой стратегии по сравнению с предыдущей в том, что она позволяет не пользоваться null-значениями. Недостатки заключаются в следующем. Во-первых, в родительском
отношении должен быть некий кортеж, потенциальный ключ которого принят как значение по умолчанию для внешних ключей.
В качестве такого «кортежа по умолчанию» обычно принимают
специальный кортеж, заполненный нулевыми значениями (не
null-значениями!). Этот кортеж нельзя удалять из родительского
отношения, и в этом кортеже нельзя изменять значение потенциального ключа. Таким образом, не все кортежи родительского отношения становятся равнозначными, поэтому приходится прилагать
дополнительные усилия для отслеживания этой неравнозначности. Это плата за отказ от использования null-значений. Во-вторых,
как и в предыдущем случае, кортежи дочернего отношения теряют
всякую связь с кортежами родительского отношения. Установить,
с каким кортежем родительского отношения были связаны измененные кортежи дочернего отношения, после выполнения операции уже нельзя.
В некоторых реализациях СУБД рассматривается еще одна стратегия поддержания ссылочной целостности:
37
– IGNORE (ИГНОРИРОВАТЬ) – выполнять операции, не обращая внимания на нарушения ссылочной целостности.
Конечно, это не стратегия, а отказ от поддержки ссылочной целостности. В этом случае в дочернем отношении могут появляться
некорректные значения внешних ключей, и вся ответственность за
целостность БД ложится на пользователя.
Очевидно, что нелогично ограничивать возможности пользователя только рассмотренными возможностями. Поэтому в общем
случае параметр option должен включать возможность вызова определенной процедуры БД (иногда называемой «хранимой процедурой», или «процедурой триггеров») с помощью которой, например,
может быть организован диалог с пользователем.
Рассмотрим, как применяются стратегии поддержания ссылочной целостности при выполнении операций модификации БД.
При обновлении кортежа в родительском отношении допустимы
стратегии:
– RESTRICT (ОГРАНИЧИТЬ) – не разрешать обновление, если имеется
хотя бы один кортеж в дочернем отношении, ссылающийся на обновляемый кортеж;
– CASCADE (КАСКАДИРОВАТЬ) – выполнить обновление и каскадно
изменить значения внешних ключей во всех кортежах дочернего
отношения, ссылающихся на обновляемый кортеж;
– SET NULL (УСТАНОВИТЬ В NULL) – выполнить обновление и во всех
кортежах дочернего отношения, ссылающихся на обновляемый
кортеж, изменить значения внешних ключей на null-значение;
– SET DEFAULT (УСТАНОВИТЬ ПО УМОЛЧАНИЮ) – выполнить обновление
и во всех кортежах дочернего отношения, ссылающихся на обновляемый кортеж, изменить значения внешних ключей на некоторое
значение, принятое по умолчанию;
– IGNORE (ИГНОРИРОВАТЬ) – выполнить обновление, не обращая
внимания на нарушения ссылочной целостности.
При удалении кортежа в родительском отношении допустимы
стратегии:
– RESTRICT (ОГРАНИЧИТЬ) – не разрешать удаление, если имеется
хотя бы один кортеж в дочернем отношении, ссылающийся на удаляемый кортеж;
– CASCADE (КАСКАДИРОВАТЬ) – выполнить удаление и каскадно удалить кортежи в дочернем отношении, ссылающиеся на удаляемый
кортеж;
– SET NULL (УСТАНОВИТЬ В NULL) – выполнить удаление и во всех
кортежах дочернего отношения, ссылающихся на удаляемый кортеж, изменить значения внешних ключей на null-значение;
38
– SET DEFAULT (УСТАНОВИТЬ ПО УМОЛЧАНИЮ) – выполнить удаление
и во всех кортежах дочернего отношения, ссылающихся на удаляемый кортеж, изменить значения внешних ключей на некоторое
значение, принятое по умолчанию;
– IGNORE (ИГНОРИРОВАТЬ) – выполнить удаление, не обращая внимания на нарушения ссылочной целостности;
При вставке кортежа в дочернее отношение допустимы стратегии:
– RESTRICT (ОГРАНИЧИТЬ) – не разрешать вставку, если внешний
ключ во вставляемом кортеже не соответствует ни одному значению потенциального ключа родительского отношения;
– SET NULL (УСТАНОВИТЬ В NULL) – вставить кортеж, но в качестве
значения внешнего ключа занести не предлагаемое пользователем
некорректное значение, а null-значение;
– SET DEFAULT (УСТАНОВИТЬ ПО УМОЛЧАНИЮ) – вставить кортеж, но в
качестве значения внешнего ключа занести не предлагаемое пользователем некорректное значение, а некоторое значение, принятое
по умолчанию;
– IGNORE (ИГНОРИРОВАТЬ) – вставить кортеж, не обращая внимания
на нарушения ссылочной целостности.
При обновлении кортежа в дочернем отношении допустимы
стратегии:
– RESTRICT (ОГРАНИЧИТЬ) – не разрешать обновление, если внешний ключ в обновляемом кортеже становится не соответствующим
ни одному значению потенциального ключа родительского отношения;
– SET NULL (УСТАНОВИТЬ В NULL) – обновить кортеж, но в качестве
значения внешнего ключа занести не предлагаемое пользователем
некорректное значение, а null-значение;
– SET DEFAULT (УСТАНОВИТЬ ПО УМОЛЧАНИЮ) – обновить кортеж, но в
качестве значения внешнего ключа занести не предлагаемое пользователем некорректное значение, а некоторое значение, принятое
по умолчанию;
– IGNORE (ИГНОРИРОВАТЬ) – обновить кортеж, не обращая внимания
на нарушения ссылочной целостности.
2.2.6. Потенциальные ключи и null-значения
Вместе с понятием первичного ключа реляционная модель включает правило целостности объектов: ни один элемент первичного
ключа базового отношения не может быть null-значением.
39
З а м е ч а н и е . Иногда под правилом целостности понимают
требование к тому, чтобы первичные ключи были уникальны. Но
это не правило целостности, а определение первичного ключа.
На самом деле приведенное правило прямо следует из определений понятий «потенциальный ключ» и «внешний ключ».
Действительно, в определении потенциального ключа требуется,
чтобы он обладал свойством уникальности. Это фактически означает, что следует различать значения потенциальных ключей, т. е.
при сравнении двух значений потенциального ключа мы в с е г д а
должны получать значения либо ИСТИНА, либо ЛОЖЬ. Но любое сравнение, в которое входит null-значение, принимает значение U – НЕИЗВЕСТНО, откуда следует, что атрибуты потенциального ключа не
могут содержать null-значений.
Таким образом, с точки зрения реляционной теории, явная
формулировка правил целостности является излишней – они автоматически вытекают из определений понятий ключа и внешнего
ключа.
Тем не менее явная формулировка правил целостности имеет
определенный практический смысл. В большинстве серьезных СУБД
за выполнением этих ограничений следит сама СУБД, если, конечно, пользователь явно объявил потенциальные и внешние ключи.
Но, во-первых, для некоторых систем можно допустить, чтобы эти
ограничения не выполнялись, а во-вторых, некоторые системы
просто не поддерживают понятия целостности, например некоторые «настольные» СУБД типа FoxPro. В этих случаях за целостностью
данных должен следить сам пользователь или программист, разрабатывающий приложение для пользователя.
Явная формулировка правил целостности помогает четко понять, какие опасности несет в себе пренебрежение этими правилами.
Объяснение тому, что первичный ключ не должен включать
null-значение, таково – объект с отсутствующей идентичностью не
существует. Например, пусть одно из S# является null-значением.
Это может означать, что:
– свойство не применяется, тогда такой кортеж не имеет смысла;
– неизвестное значение, тогда на вопрос, сколько поставщиков,
должен следовать ответ – «не знаем», что абсурдно.
Поэтому правило целостности можно сформулировать следующим образом: в реляционной БД мы никогда не записываем информацию о чем-то, чего мы не можем идентифицировать.
Какой же выход?
40
Один из путей – применять значение по умолчанию для первичных ключей. Пусть в качестве первичного ключа используется дата
рождения. И есть тот, кто не захотел ее указать. Тогда соответствующее значение первичного ключа может быть присвоено по умолчанию, например «!!!!!!».
Впрочем на этом пути также возможны проблемы. Так, например, какой ответ мы получим на вопрос обо всех датах рождения?
2.2.7. Внешние ключи и null-значения
Реляционная модель традиционно разрешает появление nullзначений в позициях внешних ключей.
З а м е ч а н и е . Не лишне будет напомнить, что null-значение означает «значение не существует», а не «значение неизвестно».
Дополнительно к введенным ранее правилам для внешних ключей добавим правило null-значений. При этом разработчик БД должен решить, может или нет внешний ключ использовать null-значение.
Для атрибута должно быть указано явно, разрешено или не разрешено ему иметь null-значения. Для этого синтаксис определения
отношения должен быть расширен до включения в него спецификации вида:
NULLS ALLOWED (null-значения допустимы)
NULLS NOT ALLOWED (null-значения не допустимы)
Если null-значения не допустимы для данного атрибута, система будет отвергать любые попытки занести туда это значение.
Таким образом, имеем следующее определения внешних ключей:
FOREING KEY (…) REFERENCES base-relatin
DELETE option
UPDATE option
NULLS null-option,
где параметр null-option может принимать значения ALLOWED (РАЗРЕШЕНО) или NOT ALLOWED (НЕ РАЗРЕШЕНО)
Резюме по поводу внешних ключей и null-значений
Существуют различные мнения по поводу целесообразности использования null-значений во внешних ключах. Тому есть несколько причин. Некоторые из них следующие:
– проблема составных внешних ключей. Если внешний ключ
составной, то можно ли разрешать ему иметь в качестве одной из
составляющих null-значение? Или необходимо потребовать, чтобы
41
каждое значение составного ключа было полностью null-значением
либо полностью не null-значением.
– что должно случиться при попытке удаления (или обновления) первичного ключа, на который ссылается внешний ключ, в
котором разрешены null-значения.
Во втором случае иногда поступают следующим образом: вводится еще одно значение для параметра option – NULLIFIES, означающее «аннулировать».
В соответствии с этим значением внешний ключ устанавливается равным null-значению, а соответствующий кортеж удаляется
(или соответствующий первичный ключ обновляется).
Подробное обсуждение проблем использования null-значений
выходит за пределы данного пособия. Можно только сказать о том,
что этот вопрос в теории реляционных БД окончательно не решен.
Основоположник реляционного подхода Э. К. Кодд считал nullзначения неотъемлемой частью реляционной модели. К. Дж. Дейт,
один из крупнейших теоретиков реляционной модели выступает
категорически против null-значений. Вот что он пишет по этому поводу: «...null-значения не желательны и не стоит разрушать всю реляционную модель просто из-за того, что иногда соответствующий
целевой кортеж не существует для некоторого определенного внешнего ключа. Вместо null-значений лучше использовать значения по
умолчанию для представления отсутствующей информации. Тогда, очевидно, можно создать «целевой кортеж по умолчанию» со
значениями по умолчанию для соответствующего потенциального
ключа и при необходимости использовать эти же значения для соответствующих внешних ключей. Этот подход не очень элегантен,
но он имеет существенное преимущество, поскольку не разрушает
логические основы реляционной модели…»
Обсуждение проблем, возникающих при использовании nullзначений, можно найти в книге [7].
42
3. РЕЛЯЦИОННЫЕ ОПЕРАТОРЫ
3.1. Реляционная алгебра
3.1.1. Традиционные операции над множествами
Как уже отмечалось выше, реляционная модель включает три
аспекта данных:
– структуру данных,
– целостность данных,
– обработку данных.
Первые два аспекта мы уже рассмотрели. Перейдем к третьему.
Здесь мы коснемся двух моментов: реляционной алгебры и реляционного исчисления. Для этого введем несколько понятий.
Замкнутость реляционной алгебры. Реляционная алгебра
представляет собой набор операторов, использующих отношения
в качестве аргументов, и возвращающих отношения в качестве результата. Таким образом, реляционный оператор f выглядит как
функция с отношениями в качестве аргументов:
R = f(R1, R2, …, Rn)
Реляционная алгебра является замкнутой. Это означает, что
результат каждой операции над отношением также является отношением. Из свойства замкнутости следует, что результат одной
операции над отношением может быть использован в качестве исходной посылки для других операций, т. е. в качестве аргументов
в реляционные операторы можно подставлять другие реляционные
операторы, подходящие по типу:
R = f(f1 (R11, R12, …), f2 (R21, R22, …), …)
Таким образом, в реляционных выражениях можно использовать вложенные выражения сколь угодно сложной структуры.
Реляционная алгебра, определенная Э. К. Коддом, состоит из
восьми операторов, составляющих две группы, по четыре оператора в каждой.
Теоретико-множественные операторы:
– объединение,
– пересечение,
– вычитание,
– декартово произведение.
Специальные реляционные операторы:
– выборка,
– проекция,
– соединение,
43
– деление.
Не все они являются независимыми, т. е. некоторые из этих
операторов могут быть выражены через другие реляционные операторы.
Отношения, совместимые по типу. Некоторые реляционные
операторы (например, объединение) требуют, чтобы отношения
имели одинаковые заголовки. Действительно, отношения состоят
из заголовка и тела. Операция объединения двух отношений есть
просто объединение двух множеств кортежей, взятых из тел соответствующих отношений. Но будет ли результат отношением?
Во-первых, если исходные отношения имеют разное количество
атрибутов, то, очевидно, что множество, являющееся объединением таких разнотипных кортежей, нельзя представить в виде отношения.
Во-вторых, пусть даже отношения имеют одинаковое количество атрибутов, но атрибуты имеют различные наименования. Как
тогда определить заголовок отношения, полученного в результате
объединения множеств кортежей?
В-третьих, пусть отношения имеют одинаковое количество атрибутов, атрибуты имеют одинаковые наименования, но определены на различных доменах. И в этом случае объединение кортежей
не будет образовывать отношение.
О п р е д е л е н и е 1. Будем называть отношения совместимыми
по типу, если они имеют идентичные заголовки, а именно:
– отношения имеют одно и то же множество имен атрибутов, т. е.
для любого атрибута в одном отношении найдется атрибут с таким
же наименованием в другом отношении;
– атрибуты с одинаковыми именами определены на одних и тех
же доменах.
Некоторые отношения не являются совместимыми по типу, но
становятся таковыми после некоторого переименования атрибутов. Для того чтобы такие отношения можно было использовать в
реляционных операторах, вводится вспомогательный оператор переименования атрибутов, который имеет следующий синтаксис:
R RENAME Atr1, Atr2 AS New Atr1, New Atr2
где R – отношение; Atr1, Atr2,… – исходные имена атрибутов; New
Atr1, New Atr2… – новые имена атрибутов.
В результате применения оператора переименования атрибутов
получаем новое отношение с измененными именами атрибутов.
А теперь перейдем непосредственно к рассмотрению реляционных операторов.
44
Традиционные операции над множествами модифицированы с
учетом того, что их операндами являются отношения, а не произвольные множества.
Дадим определение первым четырем традиционным операциям.
Объединение. Если А и В – отношения со схемой R, то объединение этих отношений А ∪ В является также отношением со схемой R,
содержащим все кортежи, которые принадлежат или А, или В.
Cинтаксис операции объединения:
A UNION B
З а м е ч а н и е . Объединение, как и любое отношение, не может
содержать одинаковых кортежей. Поэтому, если некоторый кортеж входит и в отношение A, и в отношение B, то в объединение он
входит один раз.
Пример
Пусть даны два отношения A и B с информацией о сотрудниках
(рис. 3.1–3.3):
Табельный номер
Фамилия
1
2
3
Иванов
Петров
Сидоров
A
1000
2000
3000
Рис. 3.1. Отношение А
Табельный номер
Фамилия
1
2
4
Иванов
Пушников
Сидоров
B
1000
2500
3000
Рис. 3.2. Отношение В
Объединение отношений A и B будет иметь вид
Табельный номер
Фамилия
1
2
3
2
4
Иванов
Петров
Сидоров
Пушников
Сидоров
1000
2000
3000
2500
3000
A UNION B
Рис. 3.3. Объединение отношений A и В
З а м е ч а н и е . Как видно из приведенного примера, потенциальные ключи, которые были в отношениях A и B, не наследуются
объединением этих отношений. Поэтому в объединении отношений
A и B атрибут «Табельный номер» может содержать дубликаты значе45
ний. Если бы это было не так, и ключи наследовались, то это противоречило бы понятию объединения как «объединение множеств».
Конечно, объединение отношений A и B имеет, как и любое отношение, потенциальный ключ, например, состоящий из всех атрибутов.
Пересечение. Если A и B – отношения со схемой R, то пересечение
этих отношений A ∩ B является также отношением со схемой R, содержащим все кортежи, принадлежащие одновременно и A, и B.
Синтаксис операции пересечения:
A INTERSECT B
Пример
Для тех же отношений A и B, что и в предыдущем примере, пересечение имеет вид (рис. 3.4):
Табельный номер
Фамилия
1
Иванов
1000
A INTERSECT B
Рис. 3.4. Пересечение отношение A и B
З а м е ч а н и е . Казалось бы, что в отличие от операции объединения, потенциальные ключи могли бы наследоваться пересечением отношений. Однако это не так. Вообще, никакие реляционные
операторы не передают результирующему отношению никаких
данных о потенциальных ключах. В качестве причины этого можно было бы привести тривиальное соображение, что так получается
более просто и симметрично – все операторы устроены одинаково.
На самом деле причина более глубока, и заключается она в том, что
потенциальный ключ – семантическое понятие, отражающее различимость объектов предметной области. Наличие потенциальных
ключей не выводится из структуры отношения, а явно задается для
каждого отношения исходя из его смысла. Реляционные же операторы являются формальными операциями над отношениями и
выполняются одинаково, независимо от смысла данных, содержащихся в отношениях. Поэтому реляционные операторы ничего не
могут «знать» о смысле данных. Трактовка результата реляционных операций – дело пользователя.
Вычитание. Если A и B – отношения со схемой R, то вычитание
этих отношений A–B является также отношение со схемой R, содержащее кортежи, принадлежащие A и не принадлежащие B.
Синтаксис операции вычитания:
A MINUS B
46
Пример
Для тех же отношений A и B, что и в предыдущем примере, вычитание имеет вид (рис. 3.5):
Табельный номер
Фамилия
2
3
Петров
Сидоров
A MINUS B
2000
3000
Рис. 3.5. Вычитание отношений A и B
Декартово произведение. Декартовым произведением двух отношений A(A1,A2, …, An) и B(B1,B2, …, Bm) называется отношение,
заголовок которого является сцеплением заголовков отношений
A и B:
(A1,A2, …, An, B1,B2, …, Bm)
а тело состоит из кортежей, являющихся сцеплением кортежей отношений A и B:
(a1,a2, …, an, b1,b2, …, bm)
таких, что (a1,a2, …, an) ∈ A, (b1,b2, …, bm) ∈ B.
Синтаксис операции декартова произведения:
A TIMES B
Мощность произведения A TIMES B равна произведению мощностей отношений A и B, так как каждый кортеж отношения A соединяется с каждым кортежем отношения B.
Если в отношениях A и B имеются атрибуты с одинаковыми наименованиями, то перед выполнением операции декартова произведения такие атрибуты необходимо переименовать.
Для операции декартова произведения характерно то, что перемножать можно любые два отношения, совместимость по типу при
этом не требуется.
Пример
Декартово произведение отношений S (см. рис. 2.1) и SP (см.
рис. 2.3) будет иметь следующий вид (рис. 3.6):
S#
SNAME
STATUS
CITY
S#
P#
QTY
S1
S1
S1
S1
S1
S2
Смит
Смит
Смит
Смит
Смит
Джонс
20
20
20
20
20
10
Лондон
Лондон
Лондон
Лондон
Лондон
Париж
S1
S2
S3
S4
S5
S1
P1
P2
P3
P4
P5
P1
200
100
300
200
300
200
47
S2
S2
S2
S2
S3
S3
S3
S3
S3
Джонс
Джонс
Джонс
Джонс
Блэйк
Блэйк
Блэйк
Блэйк
Блэйк
10
10
10
10
30
30
30
30
30
Париж
Париж
Париж
Париж
Париж
Париж
Париж
Париж
Париж
S2
S3
S4
S5
S1
S2
S3
S4
S5
P2
P3
P4
P5
P1
P2
P3
P4
P5
100
300
200
300
200
100
300
200
300
….. и т. д.
Рис. 3.6. Декартово произведение отношений A и B
З а м е ч а н и е . Сама по себе операция декартова произведения
не очень важна, так как она не дает никакой новой информации по
сравнению с исходными отношениями. Для реальных запросов эта
операция почти никогда не используется. Однако операция декартова произведения важна для выполнения специальных реляционных операций, о которых речь пойдет ниже.
3.1.2. Специальные реляционные операции
Выборка. Выборка возвращает отношение, содержащее все кортежи из определенного отношения, которые удовлетворяют определенным условиям. Операция выборки изначально называлась операцией ограничения (restrict), но теперь ее чаще называют select
(выборка), что не совсем удачно, поскольку ее легко перепутать с
оператором SELECT в SQL, что далеко не одно и то же. Оператор SELECT
в SQL гораздо мощнее алгебраической операции restrict (select) –
он включает функциональные возможности всех первоначальных
восьми операций и еще кое-что.
Выборка – это сокращенное название θ-выборки, где θ означает
любой скалярный оператор сравнения ( =, =, >, < и т. д.).
θ-выборкой из отношения А по атрибутам X и Y
A WHERE X θ Y
называется отношение, имеющее тот же заголовок, что и отношение А, и тело, содержащее множество всех кортежей t в отношении
A, для которых проверка условия «X θ Y» дает значение истина.
Пример
Пусть дано отношение А с информацией о сотрудниках (рис.
3.7):
48
Табельный номер
Фамилия
Зарплата
1
2
3
Иванов
Петров
Сидоров
1000
2000
3000
Рис. 3.7. Отношение A
Результат выборки A WHERE Зарплата < 3000 будет иметь вид, показанный на рис. 3.8.
Смысл операции выборки очевиден – выбрать кортежи отношения, удовлетворяющие некоторому условию. Таким образом, операция выборки дает «горизонтальный срез» отношения по некоторому условию.
Табельный номер
Фамилия
Зарплата
1
2
Иванов
Петров
1000
2000
Рис. 3.8. Отношение A WHERE Зарплата < 3000.
Проекция. Проекцией отношения A по атрибутам X,Y, …, Z, где
каждый из атрибутов принадлежит отношению A, называется отношение с заголовком X,Y, …, Z и телом, содержащим множество кортежей вида (x,y, …, z), таких, для которых в отношении A найдутся
кортежи со значением атрибута X, равным x, значением атрибута Y,
равным y, …, значением атрибута Z, равным z.
Синтаксис операции проекции:
A[X,Y, …, Z]
Операция проекции дает «вертикальный срез» отношения, в котором удалены все возникшие при таком срезе дубликаты кортежей.
Пример
Проекция отношения S (см. рис. 2.1) по атрибутам S# и STATUS будет иметь следующий вид (рис. 3.9):
S#
STATUS
S1
S2
S3
S4
S5
20
10
30
20
30
Рис. 3.9. Проекция S[S#, STATUS]
49
Соединение. Операция соединения отношений, наряду с операциями выборки и проекции, является одной из наиболее важных
реляционных операций.
Обычно рассматривается несколько разновидностей операции
соединения:
− общая операция соединения;
− θ-соединение (тэта-соединение);
− экви-соединение;
− естественное соединение.
Наиболее важным из этих частных случаев является операция
естественного соединения. Все разновидности соединения являются частными случаями общей операции соединения.
Общая операция соединения. Соединением отношений A и B по
условию c называется отношение
(A TIMES B) WHERE c
где c представляет собой логическое выражение, в которое могут
входить атрибуты отношений A и B и (или) скалярные выражения.
Таким образом, операция соединения есть результат последовательного применения операций декартова произведения и выборки. Если в отношениях A и B имеются атрибуты с одинаковыми наименованиями, то перед выполнением соединения такие атрибуты
необходимо переименовать.
θ-соединение. Пусть отношения A и B не имеют общих имен атрибутов и отношение A содержит атрибут X, отношение B содержит
атрибут Y, а θ – один из операторов сравнения ( =, ≠, ≤, ≥ и т. д.).
Тогда θ-соединением отношения A по атрибуту X с отношением B по
атрибуту Y называют отношение
(A TIMES B) WHERE X θ Y
Это частный случай операции общего соединения.
Иногда, для операции θ-соединения применяют следующий, более короткий, синтаксис:
A[X θ Y]B
Другими словами, θ-соединение – это отношение с тем же заголовком, что и при декартовом произведении А и В, и с телом, содержащим множество кортежей t, таких, что t принадлежит этому декартову произведению и вычисление условия «X θ Y» дает значение
истина для этого кортежа.
Атрибуты X и Y должны быть определены на одном и том же домене, а операция должна иметь смысл для этого домена.
50
Пример
Вычислить «больше-соединение» отношения S по атрибуту CITY
с отношением P по атрибуту CITY (« > » имеется в виду далее по алфавиту). Но поскольку в отношениях имеются одинаковые атрибуты,
то требуется сначала переименовать атрибуты, а потом выполнить
соединение. Запись становится более громоздкой. Соответствующие выражения реляционной алгебры будут иметь вид
((S RENAME CITY AS SCITY)
TIMES
(P RENAME CITY AS PCITY))
WHERE SCITY > PCITY
В результате получим (рис. 3.10):
S#
SNAME
STATUS
SCITY
P#
PNAME
COLOR
WEIGHT
PCITY
S2
S2
S3
S3
Джонс
Джонс
Блэйк
Блэйк
10
10
30
30
Париж
Париж
Париж
Париж
P1
P4
P1
P4
Гайка
Винт
Гайка
Винт
Красный
Красный
Красный
Красный
12
14
12
14
Лондон
Лондон
Лондон
Лондон
Рис. 3.10. «Больше-соединение» отношений S и P по атрибуту CITY
Экви-соединение. Наиболее важным частным случаем θ-соединения является случай, когда θ есть просто равенство.
Синтаксис экви-соединения:
A[X = Y]B
Пример
Ответ на вопрос, какие детали поставляются поставщиками,
дает экви-соединение P[P# = P#]SP. Сначала необходимо переименовать атрибуты (можно только в одном отношении), а потом выполнить экви-соединение (рис. 3.11).
((S RENAME P# AS P1#)[P1# = P#]SP
S#
P1#
P#
PNAME
QTY
S1
S2
S3
S4
S5
P1
P2
P3
P4
P5
P1
P2
P3
P4
P5
Гайка
Болт
Винт
Винт
Подшипник
100
200
300
150
250
Рис. 3.11. Экви-соединение отношений S и P
51
Если θ-соединение является «равно-соединением», то результатом будет отношение, в которое включаются два атрибута с равными значениями. Если один из таких атрибутов исключается, например, операцией проекции, то получим простое (естественное)
соединение (см. выше).
Отсюда следует, что простое соединение – это тоже не примитивная операция, она является проекцией выборки из произведения.
Например, выражение, представляющее естественное соединение отношений S и P по атрибуту города:
S JOIN P
эквивалентно следующему выражению:
((S TIMES (P RENAME CITY AS PCITY)) WHERE CITY CITY = PCITY)[ S#,
SNAME, STATUS, CITY, P#, PNAME, COLOR, WEIGHT].
Деление. Для начала рассмотрим пример.
Пусть имеем в качестве делимого проекцию отношения SP (см.
рис. 2.3) по S# и P# (рис. 3.12), а в качестве делителя – три варианта
выборки из проекции отношения SP по P# (рис. 3.13).
S#
P#
S1
S1
S1
S1
S1
S1
….
S2
S2
S3
S4
S4
S4
P1
P2
P3
P4
P5
P6
….
P1
P2
P2
P2
P4
P5
Рис. 3.12. Проекция SP [S#,P#] – DEND (делимое)
В результате получим соответственно три варианта частного (а,
b, с на рис. 3.14).
Последним делителем является отношение, содержащее все известные на настоящий момент номера атрибутов.
52
В результате получим номер поставщика, поставляющего в с е
детали. В нашем примере это S1.
а
P#
P1
b
P#
P2
P4
с
P#
P1
P2
P3
P4
P5
P6
Рис. 3.13. Варианты выборки из проекции отношения SP [P#] –
DOR (делитель)
а
S#
S1
S2
b
S#
S1
S4
с
S#
S1
Рис. 3.14. Деление отношения DEND на варианты а, b и с отношения
DOR – DEND DIVIDE BY DOR
Как было сказано в начале главы, не все операторы реляционной
алгебры являются независимыми – некоторые из них выражаются
через другие реляционные операторы.
К з а в и с и м ы м реляционным операторам относятся следующие:
– оператор соединения – определяется через операторы декартова произведения и выборки. Для оператора естественного соединения добавляется оператор проекции;
– оператор пересечения – выражается через вычитание следующим образом:
A INTERSECT B = A MINUS (A MINUS B)
– оператор деления – выражается через операторы вычитания,
декартова произведения и проекции следующим образом:
A DIVIDE B = A[X] MINUS ((A[X] TIMES B) MINUS A) [X]
Таким образом, операторы соединения, пересечения и деления
можно выразить через другие реляционные операторы, т. е. эти
операторы не являются примитивными.
Оставшиеся реляционные операторы (объединение, вычитание,
декартово произведение, выборка, проекция) являются п р и м и т и в н ы м и операторами – их нельзя выразить друг через друга:
53
– оператор декартова произведения – единственный оператор,
увеличивающий количество атрибутов, поэтому его нельзя выразить через объединение, вычитание, выборку, проекцию;
– оператор проекции – единственный оператор, уменьшающий
количество атрибутов, поэтому его нельзя выразить через объединение, вычитание, декартово произведение, выборку;
– оператор выборки – единственный оператор, позволяющий
проводить сравнения по атрибутам отношения, поэтому его нельзя
выразить через объединение, вычитание, декартово произведение,
проекцию;
– операторы объединения и вычитания – (доказательство примитивности операторов объединения и вычитания более сложны
и выходит за рамки данного пособия, поэтому здесь оно не приводится).
Несмотря на мощь языка реляционной алгебры, имеется ряд типов запросов, которые принципиально нельзя выразить только при
помощи операторов реляционной алгебры. В этом случае для получения ответов на подобные запросы приходится применять процедурные расширения реляционных операций.
К первоначальным восьми операциям впоследствии были добавлены еще несколько. Остановимся на самых важных из них.
Операция расширения. В рассмотренной выше алгебре нет
средств для скалярных вычислений. Для расширения таких возможностей и предназначена операция расширения.
С помощью этой операции из определенного отношения создается новое отношение; оно похоже на исходное, но содержит дополнительный атрибут, значения которого получены посредством некоторых скалярных вычислений.
Пример:
EXTEND P ADD (WEIGHT * 454) AS GMWT
С помощью этого выражения создается новое отношение с таким
же заголовком, как и у отношения P, за исключением дополнительного атрибута GMWT, означающего вес детали, выраженный в граммах (рис. 3.15).
P#
PNAME
COLOR
WEIGHT
GMWT
CITY
P1
P2
P3
P4
Гайка
Болт
Винт
Винт
Красный
Зеленый
Голубой
Красный
12
17
17
14
5448
7718
7718
6356
Лондон
Париж
Париж
Лондон
Рис. 3.15. Результат применения операции расширения
54
Теперь можно использовать атрибут GMWT в операциях проекции,
выборки и т. д.
(EXTEND P ADD (WEIGHT *454) AS GMWT) WHERE GMWT > 1000
В общем виде синтаксис операции расширения следующий:
EXTEND A ADD exp AS Z
Результатом этого выражения будет отношение с заголовком,
эквивалентным заголовку отношения A, расширенному новым
атрибутом Z, который подсчитывается вычислением скалярного
выражения exp для кортежа отношения А.
Операция подведения итогов. Можно заметить, что операция
расширения обеспечивает возможность «горизонтального» или
«построчного» вычисления в алгебре.
Операция SUMMARIZE выполняет аналогичную функцию для «вертикальных» вычислений.
Пример:
SUMMARIZE SP BY (P#) ADD SUM (QTY) AS TOTQTY
Вычисляется отношение с заголовком {P#, TOTQTY}, в котором
существует один кортеж для каждого значения P# в отношении SP;
в этом кортеже содержится значение P# и соответствующее общее
количество деталей (рис. 3.16).
P#
TOTQTY
P1
600
P2
1000
P3
400
P4
500
P5
500
Рис. 3.16. Результат применения операции подведения итогов
В общем виде синтаксис операции подведения итогов следующий:
SUMMARIZE A BY (A1, A2, …, An) ADD exp AS Z
Здесь A1,A2, …, An – отдельные атрибуты отношения A. Результатом этого выражения будет отношение с заголовком { A1, A2, …, An,
Z} и с телом, содержащим все кортежи t, которые являются кортежами проекции отношения A по атрибутам A1,A2, …, An, расширен55
ного значениями для нового атрибута Z. Такое новое значение атрибута Z определяется выражением exp по всем кортежам отношения
A, которые имеют те же самые значения атрибутов A1,A2, …, An, что
и кортеж t.
Операция обновления. Реализуется с помощью операторов
INSERT (вставка), UPDATE (редактирование), DELETE (удаление).
Синтаксис оператора вставки следующий:
INSERT sourse INTO target ;
Здесь sourse и target – реляционные выражения.
Пример:
INSERT (S WHERE CITY = ‘London’) INTO TEMP ;
В результате будет образовано отношение TEMP с кортежами из
отношения S, в которых значение атрибута CITY = ‘London’.
Операция редактирования. основана на операции р е л я ц и о н ного присваивания.
Синтаксис операции присваивания следующий:
target := sourse;
Здесь target и sourse – реляционные выражения, представляющие совмес-тимые по типу отношения.
Синтаксис оператора редактирования будет иметь вид:
UPDATE target assignment-commalist;
Каждое присвоение (assignment) имеет форму
attribute:= scalar-expression
Здесь target – реляционное выражение, а каждый атрибут
attribute принадлежит отношению, которое является результатом
вычисления указанного выражения.
Пример:
UPDATE P WHERE COLOR = ‘Red’
CITY:= ‘Paris’
В результате в отношении P в тех кортежах, в которых значение
атрибута COLOR = ‘Red’ будет изменено значение атрибута CITY на
‘Paris’.
Операция удаления. реализуется с помощью оператора DELETE.
Синтаксис этой операции следующий:
DELETE target;
56
Здесь target реляционное выражение. Все кортежи в результирующем отношении удаляются.
Пример:
DELETE S WHERE STATUS < 20;
В результате в отношении S будут удалены все кортежи, в которых значение атрибута STATUS < 20.
3.1.3. Назначение реляционной алгебры
Как уже отмечалось выше, восемь рассмотренных операторов
Кодда, не являются примитивными в том смысле, что некоторые из
них можно определить в терминах других (например, естественное
соединение – это проекция выборки произведения).
Минимальный набор состоит из пяти операций:
– выборка,
– проекция,
– произведение,
– объединение,
– вычитание.
Основная цель алгебры – обеспечить запись выражений.
Применения этих выражений следующие:
– определение области выборки, т. е. определение данных для
выборки как результата операции выборки;
– определение области обновления, т. е. определение данных
для их вставки, изменения или удаления как результата операции
обновления;
– определение именованных (виртуальных) отношений;
– определение «снимка», т. е. определение данных для сохранения в виде «мгновенного снимка» отношения;
– определение правил безопасности, т. е. определение данных,
для которых осуществляется контроль доступа;
– определение требования устойчивости, т. е. определение данных которые входят в область для операций управления одновременным доступом;
– определение правил целостности, т. е. некоторых особых правил, которым должна удовлетворять БД наряду с общими правилами.
В общем случае выражения служат для символического высокоуровневого представления намерений пользователя.
Этими выражениями можно манипулировать с многочисленными правилами преобразования, например выражение
57
((SP JOIN S) WHERE P# = “P2”) [SNAME]
можно преобразовать в логически эквивалентное
((SP WHERE P# = ‘P2’) JOIN S) [SNAME]
Таким образом, алгебра служит хорошим базисом для оптимизации, т. е. если пользователь выразил свой запрос с помощью первого выражения, то оптимизатор должен его преобразовать во второе
перед выполнением.
Любой язык (например, SQL) будет реляционно полным, если его
возможности по крайней мере соответствуют возможностям, обеспечиваемым алгебраическими операциями.
3.2. Реляционное исчисление
В реляционной модели определяются два базовых механизма
манипулирования данными:
– основанная на теории множеств реляционная алгебра;
– основанное на математической логике реляционное исчисление.
Так же как и выражения реляционной алгебры, формулы реляционного исчисления определяются над отношениями реляционных БД, и результатом вычисления также является отношение.
Эти механизмы манипулирования данными различаются уровнем процедурности:
– запрос, представленный на языке реляционной алгебры, может быть вычислен на основе вычисления элементарных алгебраических операций с учетом их старшинства и возможных скобок;
– формула реляционного исчисления только устанавливает условия, которым должны удовлетворять кортежи результирующего
отношения. Поэтому языки реляционного исчисления являются
более непроцедурными или декларативными.
Рассмотрим пример, чтобы почувствовать разницу.
Пусть имеем запрос: «Получить номера и города поставщиков,
поставляющих деталь Р2».
Алгебраическая версия этого запроса будет выглядеть следующим образом:
((SP JOIN S) WHERE P# = “P2”) [S#,CITY]
т. е. сначала образовать естественное соединение отношений S и SP
по атрибуту S#; далее выбрать из результата этого соединения кортежи детали Р2 и спроецировать результат этой выборки (выполнить проекцию) по атрибутам S# и CITY.
58
Сформулировать этот запрос в терминах реляционного исчисления можно следующим образом: получить атрибуты S# и CITY для
таких поставщиков, для которых существует поставка в отношении SP с тем же значением атрибута S# и со значением Р2 атрибута
P#. При этом пользователь лишь устанавливает определенные характеристики необходимого отношения, оставляя системе решать,
что соединять, проецировать и т. д., чтобы получить требуемый результат.
Итак, можно сказать, что формулировка запроса в терминах реляционного исчисления носит о п и с а т е л ь н ы й характер, а алгебраическая формулировка – п р е д п и с ы в а ю щ и й .
Приведенные различия существуют только внешне. На самом
деле алгебра и исчисление э к в и в а л е н т н ы . Каждому выражению в алгебре существует эквивалентное выражение в исчислении и
наоборот. То есть, можно сказать, что реляционная алгебра и реляционное исчисление имеют одинаковую выражающую мощность:
все запросы, которые можно сформулировать с помощью реляционной алгебры, могут быть также сформулированы с помощью реляционного исчисления и наоборот. Первым это доказал Э. Ф.Кодд
в 1972 году. Это доказательство основано на алгоритме («алгоритм
редукции Кодда») по которому произвольное выражение реляционного исчисления может быть сокращено до семантически эквивалентного выражения реляционной алгебры. (Более подробно об
этом см. в [9]).
Реляционное исчисление основано на разделе математической
логики, которая называется исчислением предикатов. Коддом был
построен язык, непосредственно основанный на использовании исчисления предикатов в реляционных БД и названный «Подъязык
данных ALPHA». Сам язык ALPHA никогда не был реализован, однако язык QUEL, одно время конкурирующий с SQL, очень походил на
язык ALPHA.
Основными понятиями исчисления являются понятие переменной с некоторой областью допустимых значений и понятие правильно построенной формулы (ППФ), или в английской транскрипции – well formulated formula (WFF), опирающейся на предикаты,
переменные и кванторы.
В зависимости от области определения переменной различают
исчисление кортежей и исчисление доменов.
В исчислении кортежей областью определения переменных являются отношения БД, т. е. допустимым значением каждой переменной является кортеж некоторого отношения.
59
В исчислении доменов областью определения переменных являются домены, на которых определены атрибуты отношений БД, т. е.
допустимым значением каждой переменной является значение некоторого домена.
Переменная кортежа (или области значений) определяется с помощью синтаксиса, являющегося синтаксисом языка QUEL, следующим образом:
RANGE OF T IS X1, X2, …, Xn
где Т – определяемая переменная кортежа, а Xi (i = 1,2, …, n) –
либо имя отношения, либо выражение исчисления кортежей.
Пусть Xi является отношением Ri (i = 1, 2, …, n). Отношения R1,
R2, …, Rn должны быть совместимы по типу, т. е. иметь идентичные
заголовки. Тогда переменная кортежа Т изменяется на объединении этих отношений, т. е. ее значение в любое заданное время будет некоторым текущим кортежем по крайней мере одного из этих
отношений. Конечно, если список идентификаторов выражений
будет просто одним именованным отношением R (это обычный случай), то переменная кортежа будет принимать значения текущих
кортежей одного такого отношения R.
При использовании кортежных переменных в формулах можно
ссылаться на значение атрибута переменной (это аналогично тому,
как, например, при программировании на языке Pascal можно сослаться на значение поля переменной типа записи). Например, для
того чтобы сослаться на значение атрибута A отношения, значения
которого принимает переменная T, нужно употребить конструкцию
T.A.
Если компоненты кортежа могут быть идентифицированы по их
порядковой позиции, то можно ссылаться на них с помощью индексной ссылки T[i]. Правильно построенная формула WFF служит для
выражения условий, накладываемых на кортежные переменные.
WFF состоит из простых сравнений скалярных значений (значений
атрибутов переменных или литерально заданных констант). Более
сложные варианты WFF строятся с помощью логических операций
NOT, AND, OR, IF…THEN и двух служебных слов – EXISTS и FORALL. EXISTS
соответствует квантору существования в исчислении предикатов, а
FORALL – квантору общности.
Если f – формула WFF, в которой участвует переменная x, то
EXISTS x(f)
и
FORALL x(f)
60
являются допустимыми формулами WFF. Первая формула означает: «Существует по крайней мере одно значение переменной x, что
вычисление формулы f для этого x дает значение истина». Вторая
формула означает: «Для всех значений переменной x вычисление
формулы f дает значение истина».
Пример:
EXISTS SPX (SPX.S# = SX.S# AND SPX.P# = P# (‘P2’))
Эта формула WFF может быть прочитана следующим образом: «В
текущем значении отношения SP существует кортеж (скажем, SPX)
такой, для которого значение атрибута S# в этом кортеже равно значению атрибута SX.S# (какое бы оно ни было), а значение атрибута
P# в кортеже SPX равно ‘P2’».
Рассмотрим в качестве примера отношение R, содержащее следующие кортежи (рис. 3.17):
A
B
C
1
2
3
1
2
4
1
3
4
Рис. 3.17. Отношение R
Для этого отношения можно записать:
EXISTS V (V.C>1): true
EXISTS V (V.B>3): false
EXISTS V (V.A>1 OR V.C = 4): true
Теперь рассмотрим квантор общности FORALL.
Пример:
FORALL PX (PX.COLOR = COLOR (‘Red’))
Эта формула WFF может быть прочитана следующим образом: «В текущем значении отношения P для всех кортежей (скажем, PX) значение их атрибута COLOR равно ‘Red’».
Обе ссылки на переменную PX в этом примере связаны.
В качестве примера рассмотрим отношение R, содержащее те же
кортежи, что и в предыдущем примере. Тогда приведённые ниже
выражения будут иметь указанные значения:
FORALL V (V.A>1): false
FORALL V (V.B>1): true
FORALL V (V.A = 1 and V.C>2): true
61
Переменные, входящие в WFF, могут быть свободными или связанными. Все переменные, входящие в WFF, при построении которой не
использовались кванторы, являются свободными. Фактически, это
означает, что если для какого-то набора значений свободных кортежных переменных при вычислении WFF получено значение true,
то эти значения кортежных переменных могут входить в результирующее отношение. Пусть f – формула WFF, в которой переменная x свободна. Если имя переменной x использовано сразу после
квантора при построении WFF вида EXISTS x(f) или FORALL x(f), то в
этой WFF и во всех WFF, построенных с ее участием, x – это связанная
переменная. Это означает, что такая переменная не видна за пределами минимальной WFF, связавшей эту переменную. При вычислении значения такой WFF используется не одно значение связанной
переменной, а вся ее область определения.
Пусть T и K – две кортежные переменные, определенные на отношении R. Тогда, WFF EXISTS K(T.A > K.A) для текущего кортежа переменной T принимает значение true в том и только в том случае, если
во всем отношении R найдется кортеж (связанный с переменной K)
такой, что значение его атрибута A удовлетворяет внутреннему условию сравнения. Формула WFF FORALL K(T.A > K.A) для текущего
кортежа переменной T принимает значение true в том и только в
том случае, если для всех кортежей отношения R (связанных с переменной K) значения атрибута A удовлетворяют условию сравнения.
Таким образом, кванторы в реляционном исчислении играют ту
же роль, что и декларации в языке программирования. Понятие
с в о б о д н о й переменной аналогично понятию глобальной переменной, описанной вне текущей процедуры. Понятие с в я з а н н о й
переменной аналогично понятию локальной переменной, описанной в текущей процедуре.
Реляционное исчисление, о р и е н т и р о в а н н о е н а д о м е н ы (или исчисление доменов), отличается от исчисления кортежей
тем, что в нем используются переменные доменов вместо переменных кортежей, т. е. переменные, принимающие свои значения в
пределах домена, а не отношения.
Основным формальным отличием исчисления доменов от исчисления кортежей является наличие дополнительного набора предикатов, позволяющих выражать так называемые условия членства.
Если R – это n-арное отношение с атрибутами t1, t2,..., tn, то условие членства имеет вид
R (pair, pair,…),
62
где каждая пара pair имеет вид t:v, при этом v – это либо литерально задаваемая константа, либо имя доменной переменной. Условие
членства принимает значение true в том и только в том случае, если
в отношении R существует кортеж, содержащий значения указанных атрибутов. Если v – константа, то на атрибут t задается жесткое условие, не зависящее от текущих значений доменных переменных; если же v – имя доменной переменной, то условие членства может принимать разные значения при разных значениях
этой переменной. Например, вычисление выражения
SP(S#:’S1’, P#:’P1’)
дает значение true, если и только если в отношении SP существует кортеж со значением S#, равным S1, и значением P#, равным P1.
Аналогично, условие членства
SP(S#:NS, P#:NP)
принимает значение true, если и только если в отношении SP существует кортеж со значением S#, эквивалентным текущему значению переменной NS домена S# (какому бы то ни было), и значением
P#, эквивалентным текущему значению переменной NP домена P#
(опять же какому бы то ни было). (В этом случае имя домена совпадает с именем соответствующего атрибута.)
Во всех остальных отношениях формулы и выражения исчисления доменов выглядят похожими на формулы и выражения исчисления кортежей. В частности, различаются свободные и связанные
вхождения доменных переменных.
Реляционное исчисление доменов является основой большинства языков запросов, основанных на использовании форм. Например, на этом исчислении базируется известный язык QBE (Query-byExample), который был первым (и наиболее интересным) языком в
семействе языков, основанных на табличных формах.
63
4. НОРМАЛЬНЫЕ ФОРМЫ БАЗ ДАННЫХ
Особое место в теории реляционных БД занимает вопрос нормализации отношений.
Нормализация отношений – это процесс построения оптимальной структуры таблиц и связей в реляционной БД.
В процессе нормализации элементы данных группируются в
таблицы, представляющие объекты и их взаимосвязи. Теория нормализации основана на том, что определенный набор таблиц обладает лучшими свойствами при включении, модификации и удалении данных, чем все остальные наборы таблиц, с помощью которых
могут быть представлены те же самые данные.
Вообще говоря, нормализация – это набор стандартов проектирования данных, называемых нормальными формами (normal forms).
Общепринятыми считаются пять нормальных форм, хотя их было
предложено значительно больше. Создание таблиц в соответствии с
этими стандартами называется нормализацией. Нормальные формы изменяются в порядке от первой до пятой. Каждая последующая форма удовлетворяет требования предыдущей. Если следовать
первому правилу нормализации, то данные будут представлены в
первой нормальной форме. Если данные удовлетворяют третьему
правилу нормализации, они будут находиться в третьей нормальной форме (а также в первой и второй).
Выполнение правил нормализации обычно приводит к разделению таблиц на две или больше таблиц с меньшим числом столбцов,
выделению отношений «первичный ключ – внешний ключ» в меньшие таблицы, которые снова могут быть соединены с помощью операции объединения.
Одним из основных результатов разделения таблиц в соответствии с правилами нормализации является уменьшение избыточности данных в таблицах. При этом в БД возможно возникновение одинаковых столбцов первичных и внешних ключей. Такое
преднамеренное дублирование – это не то же, что избыточность.
На самом деле поддержка непротиворечивости между первичными и внешними ключами связана с понятием целостности данных.
Правила нормализации, подобно принципам объектного моделирования, развивались в рамках теории БД. Большинство разработчиков БД признают, что представление данных в третьей и четвертой нормальных формах полностью удовлетворяет все их потребности.
64
4.1. Первая нормальная форма
Труднее всего дать определение вещей, которые всем понятны.
Если давать не строгое, описательное определение, то всегда остается возможность неправильной его трактовки. Если дать строгое
формальное определение, то оно, как правило, или тривиально,
или слишком громоздко. Именно такая ситуация наблюдается с
определением отношения в первой нормальной форме (1НФ). Совсем
не говорить об этом нельзя, так как на основе 1НФ строятся более высокие нормальные формы, которые рассматриваются далее. Дать
определение 1НФ сложно ввиду его тривиальности. Поэтому, дадим
просто несколько объяснений.
О п р е д е л е н и е 1. Говорят, что отношение R находится в 1НФ,
если оно удовлетворяет определению 2, приведенному на с. 25.
Это, собственно, тавтология, ведь из определения 2 следует, что
других отношений не бывает. Действительно, определение 2 описывает, что является отношением, а что – нет, следовательно, отношений не в 1НФ просто нет.
О п р е д е л е н и е 2. Говорят, что отношение R находится в 1НФ,
если его атрибуты содержат только скалярные (атомарные) значения.
Опять же, определение 2 опирается на понятие домена, а домены
определены на простых типах данных.
Непервую нормальную форму можно получить, если допустить,
что атрибуты отношения могут быть определены на сложных типах
данных – массивах, структурах, или даже на других отношениях.
Легко себе представить таблицу, у которой в некоторых ячейках
содержатся массивы, в других ячейках – определенные пользователями сложные структуры, а в третьих – целые реляционные таблицы, которые в свою очередь могут содержать такие же сложные
объекты. Именно такие возможности предоставляются некоторыми современными постреляционными и объектными СУБД.
Требование, что отношения должны содержать только данные
простых типов, объясняет, почему отношения иногда называют
плоскими таблицами (plain table). Действительно, таблицы, задающие отношения, двумерны. Одно измерение задается списком
столбцов, второе измерение – списком строк. Пара координат (Номер строки, Номер столбца) однозначно идентифицирует ячейку
таблицы и содержащееся в ней значение. Если же допустить, что
в ячейке таблицы могут содержаться данные сложных типов (массивы, структуры, другие таблицы), то такая таблица будет уже не
плоской. Например, если в ячейке таблицы содержится массив, то
65
для обращения к элементу массива нужно знать три параметра (Номер строки, Номер столбца, номер элемента в массиве).
Таким образом появляется третье объяснение 1НФ.
О п р е д е л е н и е 3. Отношение R находится в 1НФ, если оно является плоской таблицей.
Мы сознательно ограничиваемся рассмотрением только классической реляционной теории, в которой все отношения имеют только атомарные атрибуты и заведомо находятся в 1НФ.
Прежде чем переходить к рассмотрению остальных нормальных
форм БД, остановимся на некоторых моментах, касающихся адекватности логической модели предметной области, для которой она
разрабатывается.
4.2. Аномалии редактирования
Предположим, что мы проектируем логическую модель БД, в
которой должны храниться сведения о сотрудниках какого-либо
предприятия и о проектах, в которых эти сотрудники участвуют.
На первом шаге логического моделирования можно хранить
данные в одном отношении, имеющем следующие атрибуты:
СОТРУДНИКИ_ОТДЕЛЫ_ПРОЕКТЫ (Н_СОТР, ФАМ, Н_ОТД, ТЕЛ,
Н_ПРО, ПРОЕКТ, Н_ЗАДАН)
где Н_СОТР – табельный номер сотрудника; ФАМ – фамилия сотрудника; Н_ОТД – номер отдела, в котором числится сотрудник; ТЕЛ – телефон сотрудника; Н_ПРО – номер проекта, над которым работает
сотрудник; ПРОЕКТ – наименование проекта, над которым работает
сотрудник; Н_ЗАДАН – номер задания, над которым работает сотрудник.
Так как каждый сотрудник в каждом проекте выполняет ровно
одно задание, то в качестве потенциального ключа отношения необходимо взять пару атрибутов {Н_СОТР, Н_ПРО }. Пусть в текущий
момент состояние предметной области отражается следующими
фактами, приведенными на рис. 4.1 (курсивом выделены ключевые атрибуты):
Н_СОТР
ФАМ
Н_ОТД
ТЕЛ
Н_ПРО
ПРОЕКТ
Н_ЗАДАН
1
1
2
3
3
Иванов
Иванов
Петров
Сидоров
Сидоров
1
1
1
2
2
11-22-33
11-22-33
11-22-33
33-22-11
33-22-11
1
2
1
1
2
Космос
Климат
Космос
Космос
Климат
1
1
2
3
2
Рис. 4.1. Отношение СОТРУДНИКИ_ОТДЕЛЫ_ПРОЕКТЫ
66
Даже одного взгляда на таблицу отношения СОТРУДНИКИ_ОТДЕЛЫ_ПРОЕКТЫ достаточно, чтобы увидеть, что данные хранятся в ней
с большой избыточностью. Во многих строках повторяются фамилии сотрудников, номера телефонов, наименования проектов. Кроме того, в данном отношении хранятся вместе независимые друг
от друга данные: о сотрудниках, отделах, проектах и работах по
проектам. Пока никаких действий с отношением не производится,
проблем не возникает. Но как только состояние предметной области изменяется, то при попытках соответствующим образом изменить состояние БД возникает большое количество проблем.
Исторически эти проблемы получили название аномалии редактирования. В литературе приводится несколько точек зрения на
определение понятия аномалии в БД. Обсуждение данного вопроса
выходит за рамки данного пособия и здесь не приводится. Мы будем придерживаться интуитивного понятия аномалии как неадекватности модели данных предметной области (что говорит на самом
деле о том, что логическая модель данных попросту неверна!) или
как необходимости дополнительных усилий для реализации всех
ограничений, определенных в предметной области (дополнительный программный код в виде триггеров или хранимых процедур).
Так как аномалии проявляют себя при выполнении операций,
изменяющих состояние БД, то различают следующие их виды:
– аномалии вставки (INSERT),
– аномалии обновления (UPDATE),
– аномалии удаления (DELETE).
В отношении СОТРУДНИКИ_ОТДЕЛЫ_ПРОЕКТЫ можно привести примеры следующих аномалий:
Аномалии вставки (INSERT). В отношение СОТРУДНИКИ_ОТДЕЛЫ_ПРОЕКТЫ нельзя вставить данные о сотруднике, который пока не участвует ни в одном проекте. Действительно, если, например, во втором отделе появляется новый сотрудник, скажем Пушников, и он
пока не участвует ни в одном проекте, то мы должны вставить в отношение кортеж (4,Пушников,2,33-22-11,null,null,null). Это сделать
невозможно, поскольку атрибут Н_ПРО (номер проекта) входит в состав потенциального ключа и, следовательно, не может содержать
null-значений.
Точно так же нельзя вставить данные о проекте, над которым
пока не работает ни один сотрудник.
Причина аномалии вставки – хранение в одном отношении разнородной информации (и о сотрудниках, и о проектах, и о работах
по проекту).
67
Следовательно, логическая модель данных неадекватна модели
предметной области. База данных, основанная на такой модели, будет работать неправильно.
Аномалии обновления (UPDATE). Фамилии сотрудников, наименования проектов, номера телефонов повторяются во многих
кортежах отношения. Поэтому если сотрудник меняет фамилию
или проект меняет наименование, или меняется номер телефона,
то такие изменения необходимо одновременно выполнить во всех
местах, где эта фамилия, наименование или номер телефона встречаются, иначе отношение станет некорректным (например, один и
тот же проект в разных кортежах будет называться по-разному).
Таким образом, обновление БД одним действием реализовать невозможно. Для поддержания отношения в целостном состоянии необходимо написать триггер, который при обновлении одной записи
корректно исправлял бы данные и в других местах.
Причина аномалии обновления – избыточность данных, также
порожденная тем, что в одном отношении хранится разнородная
информация.
База данных, основанная на такой модели, будет работать правильно только при наличии дополнительного программного кода в
виде триггеров.
Аномалии удаления (DELETE). При удалении некоторых данных
может произойти потеря другой информации. Например, если закрыть проект «Космос» и удалить все строки, в которых он встречается, то будут потеряны все данные о сотруднике Петрове. Если
удалить сотрудника Сидорова, то будет потеряна информация о том,
что в отделе номер 2 находится телефон 33-22-11. Если по проекту
временно прекращены работы, то при удалении данных о работах
по этому проекту будут удалены и данные о самом проекте (наименование проекта). При этом если был сотрудник, который работал
только над этим проектом, то будут потеряны и данные об этом сотруднике.
Причина аномалии удаления все та же – хранение в одном отношении разнородной информации (и о сотрудниках, и о проектах, и
о работах по проекту). И последствия этой аномалии аналогичны –
БД, основанная на такой модели, будет работать неправильно.
Вместе с тем очевидно, что отношение СОТРУДНИКИ_ОТДЕЛЫ_ПРОЕКТЫ находится в 1НФ. Но при этом, как было показано выше, логическая модель данных не адекватна модели предметной области.
Таким образом, 1НФ недостаточно для правильного моделирования
данных.
68
4.3. Функциональные зависимости
Для устранения указанных аномалий и для правильного проектирования модели данных применяется метод нормализации
отношений. Нормализация основана на понятии функциональной
зависимости атрибутов отношения.
О п р е д е л е н и е 4. Пусть R – отношение. Множество атрибутов
Y функционально зависимо от множества атрибутов X (X функционально определяет Y) тогда и только тогда, когда для любого состояния отношения R для любых кортежей r1,r2 ∈ R из того, что r1X =
r2X, следует: r1Y = r2Y (т. е. во всех кортежах, имеющих одинаковые значения атрибутов X, значения атрибутов Y также совпадают
в любом состоянии отношения R). Символически функциональная
зависимость записывается следующим образом:
X → Y
Множество атрибутов X называется детерминантом функциональной зависимости, а множество атрибутов Y – зависимой частью.
З а м е ч а н и е . Если атрибуты X составляют потенциальный
ключ отношения R, то любой атрибут отношения R функционально
зависит от X.
В отношении СОТРУДНИКИ_ОТДЕЛЫ_ПРОЕКТЫ можно привести следующие примеры функциональных зависимостей:
– зависимость атрибутов от ключа отношения:
{Н_СОТР, Н_ПРО} → ФАМ
{Н_СОТР, Н_ПРО} → Н_ОТД
{Н_СОТР, Н_ПРО} → ТЕЛ
{Н_СОТР, Н_ПРО} ПРОЕКТ
{Н_СОТР, Н_ПРО} → Н_ЗАДАН
– зависимость атрибутов, характеризующих сотрудника от табельного номера сотрудника:
Н_СОТР → ФАМ
Н_СОТР → Н_ОТД
Н_СОТР → ТЕЛ
– зависимость наименования проекта от номера проекта:
Н_ПРО → ПРОЕКТ
– зависимость номера телефона от номера отдела:
Н_ОТД → ТЕЛ
Необходимо заметить, что приведенные функциональные зависимости не выведены из внешнего вида отношения, приведенного
69
на рис. 4.1. Эти зависимости отражают взаимосвязи, обнаруженные между объектами предметной области, и являются дополнительными ограничениями, определяемыми предметной областью.
Таким образом, функциональная зависимость – семантическое понятие. Она возникает, когда по значениям одних данных в предметной области можно определить значения других данных. Например, зная табельный номер сотрудника, можно определить его
фамилию, по номеру отдела – номер телефона. Функциональная
зависимость задает дополнительные ограничения на данные, которые могут храниться в отношениях. Для корректности БД (адекватности предметной области) необходимо при выполнении операций
модификации БД проверять все ограничения, определенные функциональными зависимостями.
Функциональная зависимость атрибутов отношения напоминает понятие функциональной зависимости в математике. Но это не
одно и то же. Для сравнения напомним математическое понятие
функциональной зависимости.
О п р е д е л е н и е 5. Функциональная зависимость (функция) –
это тройка объектов X,Y,Z, где:
– X – множество (область определения),
– Y – множество (множество значений),
– f – правило, согласно которому каждому элементу x∈ X ставится в соответствие один и только один элемент y∈ Y (правило функциональной зависимости).
Функциональная зависимость обычно обозначается как f:X → Y
или y = f(x).
Правило f может быть задано любым способом – в виде формулы
(чаще всего), при помощи таблицы значений, при помощи графика, текстовым описанием и т. д.
Функциональная зависимость атрибутов отношения тоже напоминает это определение. Действительно:
– в качестве области определения выступает домен, на котором
определен атрибут X (или декартово произведение доменов, если X
является множеством атрибутов);
– в качестве множества значений выступает домен, на котором
определен атрибут Y (или декартово произведение доменов);
– правило f реализуется следующим алгоритмом:
1) по данному значению атрибута X найти л ю б о й кортеж отношения, содержащий это значение,
2) значение атрибута Y в этом кортеже и будет значением функциональной зависимости, соответствующим данному X. Определение функциональной зависимости в отношении гарантирует, что
70
найденное значение Y н е з а в и с и т от выбора кортежа, поэтому
правило f определено корректно.
Отличие от математического понятия отношения состоит в том,
что если рассматривать математическое понятие функции, то для
фиксированного значения x∈ X соответствующее значение функции
y = f(x) в с е г д а одно и то же. Например, если задана функция y
= x2, то для значения x = 2 соответствующее значение y в с е г д а
будет равно 4. В противоположность этому в отношениях значение зависимого атрибута может принимать различные значения в
различных состояниях БД. Например, атрибут ФАМ функционально
зависит от атрибута Н_СОТР. Предположим, что сейчас сотрудник с
табельным номером 1 имеет фамилию Иванов, т. е. при значении детерминанта, равного 1, значение зависимого аргумента равно «Иванов». Но сотрудник может сменить фамилию, например на «Сидоров». Теперь при том же значении детерминанта, равного 1, значение зависимого аргумента равно «Сидоров».
Таким образом, понятие функциональной зависимости атрибутов нельзя считать полностью эквивалентным математическому
понятию функциональной зависимости, так как значения этой зависимости различны при разных состояниях отношения и, самое
главное, они могут меняться н е п р е д с к а з у е м о .
Функциональная зависимость атрибутов утверждает лишь то,
что для каждого конкретного состояния БД по значению одного
атрибута (детерминанта) можно однозначно определить значение
другого атрибута (зависимой части). Но конкретные значения зависимой части могут быть различны в различных состояниях БД.
4.4. Вторая нормальная форма
О п р е д е л е н и е 6. Отношение R находится во второй нормальной форме (2НФ) тогда и только тогда, когда отношение находится
в 1НФ и нет неключевых атрибутов, зависящих от части сложного
ключа. (Неключевой атрибут – это атрибут, не входящий в состав
никакого потенциального ключа.)
Очевидно, что если потенциальный ключ отношения является
простым, то отношение автоматически находится в 2НФ.
Отношение СОТРУДНИКИ_ОТДЕЛЫ_ПРОЕКТЫ не находится в 2НФ, так как
есть атрибуты, зависящие от части сложного ключа, а именно:
– зависимость атрибутов, характеризующих сотрудника от табельного номера сотрудника, является зависимостью от части
сложного ключа:
Н_СОТР → ФАМ
71
Н_СОТР → Н_ОТД
Н_СОТР → ТЕЛ
– зависимость наименования проекта от номера проекта является зависимостью от части сложного ключа:
Н_ПРО
ПРОЕКТ
Для того чтобы устранить зависимость атрибутов от части сложного ключа, нужно произвести декомпозицию отношения на несколько отношений. При этом те атрибуты, которые зависят от части сложного ключа, выносятся в отдельное отношение.
Отношения СОТРУДНИКИ_ОТДЕЛЫ_ПРОЕКТЫ декомпозируем на три отношения – СОТРУДНИКИ_ОТДЕЛЫ, ПРОЕКТЫ, ЗАДАНИЯ.
Функциональные зависимости:
– для отношения СОТРУДНИКИ_ОТДЕЛЫ(Н_СОТР,ФАМ,Н_ОТД,ТЕЛ) (рис.
4.2):
– зависимость атрибутов, характеризующих сотрудника от табельного номера сотрудника:
Н_СОТР → ФАМ
Н_СОТР → Н_ОТД
Н_СОТР → ТЕЛ
– зависимость номера телефона от номера отдела:
Н_ОТД → ТЕЛ
Н_СОТР
ФАМ
Н_ОТД
ТЕЛ
1
2
3
Иванов
Петров
Сидоров
1
1
2
11-22-33
11-22-33
33-22-11
Рис. 4.2. Отношение СОТРУДНИКИ_ОТДЕЛЫ
– для отношения ПРОЕКТЫ(Н_ПРО ,ПРОЕКТ) (рис. 4.3):
Н_ПРО → ПРОЕКТ
Н_ПРО
ПРОЕКТ
1
2
Космос
Климат
Рис. 4.3. Отношение ПРОЕКТЫ
Функциональные зависимости: отношения ЗАДАНИЯ (Н_СОТР, Н_
ПРО , Н_ЗАДАН) (рис. 4.4):
{Н_СОТР, Н_ПРО}
Н_ЗАДАН
72
Н_СОТР
Н_ПРО
Н_ЗАДАН
1
1
2
3
3
1
2
1
1
2
1
1
2
3
2
Рис. 4.4. Отношение ЗАДАНИЯ
Проанализируем полученные отношения с точки зрения рассмотренных выше аномалий.
Отношения, полученные в результате декомпозиции, находятся
в 2НФ. Действительно, отношения СОТРУДНИКИ_ОТДЕЛЫ и ПРОЕКТЫ имеют
простые ключи, следовательно, автоматически находятся в 2НФ, отношение ЗАДАНИЯ имеет сложный ключ, но единственный неключевой атрибут Н_ЗАДАН функционально зависит от всего ключа {Н_СОТР,
Н_ПРО}.
Часть аномалий обновления устранена. Так, данные о сотрудниках и проектах теперь хранятся в различных отношениях, поэтому
при появлении сотрудников, не участвующих ни в одном проекте,
добавляются кортежи в отношение СОТРУДНИКИ_ОТДЕЛЫ. Точно так же
при появлении проекта, над которым не работает ни один сотрудник, вставляется кортеж в отношение ПРОЕКТЫ.
Фамилии сотрудников и наименования проектов теперь хранятся без избыточности. Если сотрудник сменит фамилию или проект
сменит наименование, то такое обновление будет произведено в одном месте.
Если по проекту временно прекращены работы, но требуется,
чтобы сам проект сохранился, то для этого проекта удаляются соответствующие кортежи в отношении ЗАДАНИЯ, а данные о самом проекте и данные о сотрудниках, участвовавших в проекте, остаются в
отношениях ПРОЕКТЫ и СОТРУДНИКИ_ОТДЕЛЫ.
Тем не менее часть аномалий разрешить не удалось.
В отношение СОТРУДНИКИ_ОТДЕЛЫ нельзя вставить кортеж, например, такой (4,Пушников,1,33-22-11), так как при этом получится, что
два сотрудника из 1-го отдела (Иванов и Пушников) имеют разные
номера телефонов, а это противоречит модели предметной области.
В этой ситуации можно предложить два решения, в зависимости
от того, что реально произошло в предметной области. Другой номер телефона может быть введен по двум причинам – по ошибке
человека, вводящего данные о новом сотруднике, или потому, что
номер в отделе действительно изменился. Тогда можно написать
73
триггер, который при вставке записи о сотруднике проверяет, совпадает ли телефон с уже имеющимся телефоном у другого сотрудника этого же отдела. Если номера отличаются, то система должна
задать вопрос, оставить ли старый номер в отделе или заменить его
новым. Если нужно оставить старый номер (новый номер введен
ошибочно), то кортеж с данными о новом сотруднике будет вставлен, но номер телефона будет у него тот, который уже есть в отделе
(в данном случае, 11-22-33). Если же номер в отделе действительно
изменился, то кортеж будет вставлен с новым номером и одновременно будут изменены номера телефонов у всех сотрудников этого
же отдела. И в том и в другом случае не обойтись без разработки
громоздкого триггера.
Причина данной аномалии так же состоит в том, что после проведенных преобразований сохранилась избыточность данных, порожденная тем, что в одном отношении хранится разнородная информация (о сотрудниках и об отделах). Чтобы БД, основанная на
такой модели, работала правильно, необходима разработка дополнительного программного кода в виде триггеров.
Кроме того, можно заметить, что в полученных отношениях
одни и те же номера телефонов повторяются во многих кортежах
отношения. Поэтому если в отделе меняется номер телефона, то такие изменения необходимо одновременно выполнить во всех местах, где этот номер телефона встречается, иначе отношение станет
некорректным. Таким образом, обновление БД одним действием
реализовать невозможно. Необходимо снова написать триггер, который при обновлении одной записи корректно исправит номера
телефонов в других местах.
И, наконец, при удалении некоторых данных по-прежнему может произойти потеря другой информации. Например, если удалить сотрудника Сидорова, то будет потеряна информация о том, что
в отделе номер 2 находится телефон 33-22-11.
Таким образом, можно сделать следующий вывод: при переходе
к 2НФ отношения стали почти адекватными предметной области. Остались трудности в разработке БД, связанные с необходимостью написания триггеров, поддерживающих ее целостность. Эти трудности теперь связаны только с одним отношением СОТРУДНИКИ_ОТДЕЛЫ.
4.5. Третья нормальная форма
О п р е д е л е н и е 7. Атрибуты называются взаимно независимыми, если ни один из них не является функционально зависимым
от другого.
74
О п р е д е л е н и е 8. Отношение R находится в третьей нормальной форме (3НФ) тогда и только тогда, когда отношение находится в
2НФ и все неключевые атрибуты взаимно независимы.
Отношение СОТРУДНИКИ_ОТДЕЛЫ не находится в 3НФ, так как имеется
функциональная зависимость неключевых атрибутов (зависимость
номера телефона от номера отдела):
Н_ОТД → ТЕЛ
Для того чтобы устранить зависимость неключевых атрибутов,
нужно произвести декомпозицию отношения на несколько отношений. При этом те неключевые атрибуты, которые являются зависимыми, выносятся в отдельное отношение.
Отношение СОТРУДНИКИ_ОТДЕЛЫ декомпозируем на два отношения – СОТРУДНИКИ, ОТДЕЛЫ.
Функциональные зависимости:
– для отношения СОТРУДНИКИ (Н_СОТР, ФАМ, Н_ОТД) (рис. 4.5) зависимость атрибутов, характеризующих сотрудника от табельного
номера сотрудника:
Н_СОТР → ФАМ
Н_СОТР → Н_ОТД
Н_СОТР → ТЕЛ
Н_СОТР
ФАМ
Н_ОТД
1
Иванов
1
2
Петров
1
3
Сидоров
2
Рис. 4.5. Отношение СОТРУДНИКИ
– для отношения ОТДЕЛЫ (Н_ОТД, ТЕЛ) (рис. 4.6) зависимость номера телефона от номера отдела:
Н_ОТД → ТЕЛ
Н_ОТД
ТЕЛ
1
11-22-33
2
33-22-11
Рис. 4.6. Отношение ОТДЕЛЫ
Обратим внимание на то, что атрибут Н_ОТД, не являвшийся ключевым в отношении СОТРУДНИКИ_ОТДЕЛЫ, становится потенциальным
ключом в отношении ОТДЕЛЫ. Именно за счет этого устраняется из75
быточность, связанная с многократным хранением одних и тех же
номеров телефонов.
Проанализировав полученные отношения, можно сделать вывод
о том, что все обнаруженные аномалии обновления устранены. Реляционная модель, состоящая из четырех отношений СОТРУДНИКИ,
ОТДЕЛЫ, ПРОЕКТЫ, ЗАДАНИЯ, находящихся в 3НФ, является адекватной
описанной модели предметной области и требует наличия только
тех триггеров, которые поддерживают ссылочную целостность. Такие триггеры являются стандартными и не требуют больших усилий в разработке.
4.6. Алгоритм нормализации (приведение к 3НФ)
Итак, алгоритм нормализации (т. е. алгоритм приведения отношений к 3НФ) описывается следующим образом.
Шаг 1 (приведение к 1НФ). На первом шаге задается одно или несколько отношений, отображающих понятия предметной области.
По модели предметной области (не по внешнему виду полученных
отношений!) выписываются обнаруженные функциональные зависимости. Все отношения автоматически находятся в 1НФ.
Шаг 2 (приведение к 2НФ). Если в некоторых отношениях обнаружена зависимость атрибутов от части сложного ключа, то проводим декомпозицию этих отношений на несколько отношений следующим образом: те атрибуты, которые зависят от части сложного
ключа выносятся в отдельное отношение вместе с этой частью ключа. В и с х о д н о м отношении остаются все ключевые атрибуты:
– исходное отношение: R(K1,K2,A1, …, An,B1, …, Bm); ключ: K1,K2 –
сложный.
Функциональные зависимости:
– (K1,K2) → (A1, …, An,B1, …, Bm) зависимость всех атрибутов от
ключа отношения;
– (K1) → (A1, …, An) – зависимость некоторых атрибутов от части
сложного ключа.
Декомпозированные отношения:
– R1(K1,K2,B1, …, Bm) – остаток от исходного отношения;
ключ:K1,K2;
– R2(K1,A1, …, An) – атрибуты, вынесенные из исходного отношения вместе с частью сложного ключа; ключ: K1.
Шаг 3 (приведение к 3НФ). Если в некоторых отношениях обнаружена зависимость некоторых неключевых атрибутов от других неключевых атрибутов, то проводим декомпозицию этих отношений
следующим образом: те неключевые атрибуты, которые зависят от
76
других неключевых атрибутов выносятся в отдельное отношение.
В н о в о м отношении ключом становится детерминант функциональной зависимости:
– исходное отношение: R(K,A1, …, An,B1, …, Bm); ключ: K.
Функциональные зависимости:
– K → (A1, …, An,B1, …, Bm) – зависимость всех атрибутов от ключа
отношения;
– (A1, …, An) → (B1, …, Bm) – зависимость некоторых неключевых
атрибутов других неключевых атрибутов.
Декомпозированные отношения:
– R1(K,A1, …, An) – остаток от исходного отношения; ключ: K.
– R2(A1, …, An,B1, …, Bm) – атрибуты, вынесенные из исходного
отношения вместе с детерминантом функциональной зависимости;
ключ: A1, …, An.
З а м е ч а н и е . На практике при создании логической модели
данных, как правило, не следуют прямо приведенному алгоритму
нормализации. Опытные разработчики обычно сразу строят отношения в 3НФ. Кроме того, основным средством разработки логических моделей данных являются различные варианты ER-диаграмм.
Особенность этих диаграмм в том, что они сразу позволяют создавать отношения в 3НФ. Тем не менее приведенный алгоритм важен
по двум причинам.
Во-первых, этот алгоритм показывает, какие проблемы возникают при разработке слабо нормализованных отношений.
Во-вторых, как правило, модель предметной области никогда
не бывает корректно разработана с первого шага. Эксперты предметной области могут забыть о чем-либо упомянуть, разработчик
может неправильно понять эксперта, во время разработки могут
измениться правила, принятые в предметной области, и т. д. Все
это может привести к появлению новых зависимостей, которые отсутствовали в первоначальной модели предметной области. В этом
случае необходимо использовать алгоритм нормализации хотя бы
для того, чтобы убедиться, что отношения остались в 3НФ и логическая модель не ухудшилась.
Если говорить о практическом использовании нормальных форм
БД, то можно заметить следующее: выбор степени нормализации
отношений зависит от характера запросов, с которыми чаще всего
обращаются к БД.
Результаты анализа критериев, по которым можно оценить влияние логического моделирования на качество БД и ее производительность приведены в табл. 4.1. Как видно из таблицы, более сильно
нормализованные отношения оказываются лучше спроектированы
77
(три плюса, один минус). Они больше соответствуют предметной
области, легче в разработке, для них быстрее выполняются операции модификации БД. Правда, это достигается ценой некоторого замедления выполнения операций выборки данных.
Таблица 4.1
Критерий
Отношения слабо Отношения сильно
нормализованы
нормализованы
(1НФ, 2НФ)
(3НФ)
ХУЖЕ (–)
ЛУЧШЕ (+)
Легкость разработки и сопровождения БД
СЛОЖНЕЕ (–)
ЛЕГЧЕ (+)
Скорость выполнения вставки,
обновления, удаления
МЕДЛЕННЕЕ
(–)
БЫСТРЕЕ (+)
Скорость выполнения выборки
данных
БЫСТРЕЕ (+)
МЕДЛЕННЕЕ
(–)
Адекватность БД предметной области
У слабо нормализованных отношений единственное преимущество – если к БД обращаться только с запросами на выборку данных,
то для слабо нормализованных отношений такие запросы выполняются быстрее. Это связано с тем, что в таких отношениях уже как
бы произведено соединение отношений и на это не тратится время
при выборке данных.
Можно выделить некоторые классы систем, для которых больше подходят сильно или слабо нормализованные модели данных.
Сильно нормализованные модели данных хорошо подходят для
так называемых OLTP-приложений (On-Line Transaction Processing
(OLTP) – оперативная обработка транзакций). Типичными примерами OLTP-приложений являются системы складского учета, системы заказов билетов, банковские системы, выполняющие операции
по переводу денег, и т. п. Основная функция подобных систем заключается в выполнении большого количества коротких транзакций. Сами транзакции выглядят относительно просто, например:
«снять сумму денег со счета А, добавить эту сумму на счет В».
Проблема заключается в том, что, во-первых, транзакций очень
много, во-вторых, выполняются они одновременно (к системе может быть подключено несколько тысяч одновременно работающих
пользователей), в-третьих, при возникновении ошибки, транзакция должна целиком «откатиться» и вернуть систему к состоянию,
которое было до начала транзакции (не должно быть ситуации, когда деньги сняты со счета А, но не поступили на счет В). Практически
78
все запросы к БД в OLTP-приложениях состоят из команд вставки,
обновления, удаления. Запросы на выборку в основном предназначены для предоставления пользователям возможности выбора из
различных справочников. Большая часть запросов, таким образом,
известна заранее еще на этапе проектирования системы. Таким образом, критическим для OLTP-приложений является скорость и надежность выполнения коротких операций обновления данных. Чем
выше уровень нормализации данных в OLTP-приложении, тем оно,
как правило, быстрее и надежнее. Отступления от этого правила
могут происходить тогда, когда уже на этапе разработки известны
некоторые часто возникающие запросы, требующие соединения отношений и от скорости выполнения которых существенно зависит
работа приложений. В этом случае можно пожертвовать нормализацией для ускорения выполнения подобных запросов.
Другим типом приложений являются так называемые OLAP-приложения (On-Line Analitical Processing (OLAP) – оперативная аналитическая обработка данных). Это обобщенный термин, характеризующий принципы построения систем поддержки принятия
решений (Decision Support System – DSS), хранилищ данных (Data
Warehouse), систем интеллектуального анализа данных (Data Mining).
Такие системы предназначены для нахождения зависимостей между данными (например, можно попытаться определить, как связан
объем продаж товаров с характеристиками потенциальных покупателей), для проведения анализа «что если…». OLAP-приложения
оперируют с большими массивами данных, уже накопленными в
OLTP-приложениях, взятыми из электронных таблиц или из других
источников данных. Такие системы характеризуются следующими
признаками:
– добавление в систему новых данных происходит относительно
редко крупными блоками (например, раз в квартал загружаются
данные по итогам квартальных продаж из OLTP-приложения);
– данные, добавленные в систему, обычно никогда не удаляются;
– перед загрузкой данные проходят различные процедуры «очистки», связанные с тем, что в одну систему могут поступать данные
из многих источников, имеющих различные форматы представления для одних и тех же понятий, данные могут быть некорректны,
ошибочны;
– запросы к системе являются нерегламентированными и, как
правило, достаточно сложными. Очень часто новый запрос формулируется аналитиком для уточнения результата, полученного в результате предыдущего запроса;
79
– скорость выполнения запросов важна, но не критична.
Данные OLAP-приложений обычно представлены в виде одного
или нескольких гиперкубов, измерения которого представляют
собой справочные данные, а в ячейках самого гиперкуба хранятся
собственно данные. Например, можно построить гиперкуб, измерениями которого являются: время (в кварталах, годах), тип товара и
отделения компании, а в ячейках хранятся объемы продаж. Такой
гиперкуб будет содержать данные о продажах различных типов товаров по кварталам и подразделениям. Основываясь на этих данных, можно отвечать на вопросы вроде «у какого подразделения
самые лучшие объемы продаж в текущем году?» или «каковы тенденции продаж отделений Юго-Западного региона в текущем году
по сравнению с предыдущим годом?»
Возвращаясь к проблеме нормализации данных, можно сказать,
что в системах OLAP, использующих реляционную модель данных
(ROLAP), данные целесообразно хранить в виде слабо нормализованных отношений, содержащих заранее вычисленные основные итоговые данные. Большая избыточность и связанные с ней проблемы
тут не играют роли, так как обновление происходит только в момент загрузки новой порции данных. При этом происходит как добавление новых данных, так и пересчет итогов.
4.7. Корректность процедуры нормализации.
Теорема Хеза
Как было показано выше, алгоритм нормализации состоит в
выявлении функциональных зависимостей предметной области и
соответствующей декомпозиции отношений. Предположим, что
мы уже имеем работающую систему, в которой накоплены данные.
Пусть данные корректны в текущий момент, т. е. факты предметной области правильно отражаются текущим состоянием БД. Если
в предметной области обнаружена новая функциональная зависимость (либо она была пропущена на этапе моделирования предметной области, либо просто изменилась предметная область), то
возникает необходимость заново нормализовать данные. При этом
некоторые отношения придется декомпозировать в соответствии с
алгоритмом нормализации. Возникают естественные вопросы: что
произойдет с уже накопленными данными? не будут ли данные
потеряны в ходе декомпозиции? можно ли вернуться обратно к исходным отношениям, если будет принято решение отказаться от
декомпозиции, восстановятся ли при этом данные?
80
Для ответов на эти вопросы нужно ответить на вопрос: что же
представляет собой декомпозиция отношений с точки зрения операций реляционной алгебры? При декомпозиции мы из одного отношения получаем два или более отношений, каждое из которых
содержит часть атрибутов исходного отношения. В полученных новых отношениях необходимо удалить дубликаты строк, если таковые возникли. Это в точности означает, что декомпозиция отношения есть не что иное, как взятие одной или нескольких проекций
исходного отношения так, чтобы эти проекции в совокупности содержали (возможно, с повторениями) все атрибуты исходного отношения, т. е. при декомпозиции не должны теряться атрибуты отношений. Но при декомпозиции также не должны потеряться и сами
данные. Данные можно считать не потерянными в том случае, если
возможна обратная операция – по декомпозированным отношениям можно восстановить исходное отношение в точности в прежнем
виде. Операцией, обратной операции проекции, является операция
соединения отношений. Так как при восстановлении исходного отношения путем соединения проекций не должны появиться новые
атрибуты, то необходимо использовать естественное соединение.
О п р е д е л е н и е 9. Проекция R[X] отношения R на множество
атрибутов X называется собственной, если множество атрибутов X
является собственным подмножеством множества атрибутов отношения R (т. е. множество атрибутов X не совпадает с множеством
всех атрибутов отношения R).
О п р е д е л е н и е 10. Собственные проекции R1 и R2 отношения
R называются декомпозицией без потерь, если отношение R точно
восстанавливается из них при помощи естественного соединения
для любого состояния отношения R:
R1 JOIN R2 = R
Рассмотрим пример, показывающий, что декомпозиция без потерь происходит не всегда.
Пример
Пусть дано отношение R (рис. 4.7):
НОМЕР
ФАМИЛИЯ
ЗАРПЛАТА
1
Иванов
1000
2
Петров
1000
Рис. 4.7. Отношение R
81
Рассмотрим первый вариант декомпозиции отношения R на два
отношения (рис. 4.8, а, б):
а)
б)
ФАМИЛИЯ
ЗАРПЛАТА
1000
Иванов
1000
1000
Петров
1000
НОМЕР
ЗАРПЛАТА
1
2
Рис. 4.8. Отношение R1и R2
Естественное соединение этих проекций, имеющих общий атрибут «ЗАРПЛАТА», очевидно, будет следующим (рис. 4.9) (каждая
строка одной проекции соединится с каждой строкой другой проекции):
НОМЕР
ФАМИЛИЯ
ЗАРПЛАТА
1
Иванов
1000
2
Петров
1000
Рис. 4.9. Отношение R1 JOIN R2
Как легко видеть, R1 JOIN R2 ≠ R. Итак, данная декомпозиция не
является декомпозицией без потерь, так как исходное отношение
не восстанавливается в точном виде по проекциям (серым цветом
выделены лишние кортежи).
Рассмотрим другой вариант декомпозиции (рис. 4.10, а, б,):
а)
б)
НОМЕР
ФАМИЛИЯ
НОМЕР
ЗАРПЛАТА
1
Иванов
1
1000
2
Петров
2
1000
Рис. 4.10. Отношение R1 и R2
По данным проекциям, имеющим общий атрибут «НОМЕР», исходное отношение восстанавливается в точном виде. Тем не менее
нельзя сказать, что данная декомпозиция является декомпозицией
без потерь, так как мы рассмотрели только одно конкретное состояние отношения R и не можем сказать, будет ли и в других состояниях отношение R восстанавливаться точно. Например, предположим, что отношение R перешло в состояние (рис. 4.11):
82
НОМЕР
ФАМИЛИЯ
ЗАРПЛАТА
1
2
2
Иванов
Петров
Сидоров
1000
1000
2000
Рис. 4.11. Отношение R
Кажется, что этого не может быть, так как значения в атрибуте
«НОМЕР» повторяются. Но мы же ничего не говорили о ключе этого
отношения! Итак, проекции будут иметь следующий вид (рис. 4.12,
4.13):
НОМЕР
ФАМИЛИЯ
НОМЕР
ЗАРПЛАТА
1
2
2
Иванов
Петров
Сидоров
1
2
2
1000
1000
2000
Рис. 4.12. Отношение R1
Рис. 4.13. Отношение R2
Естественное соединение этих проекций вновь будет содержать
лишние кортежи (рис. 4.14):
НОМЕР
ФАМИЛИЯ
ЗАРПЛАТА
1
2
2
Иванов
Петров
Сидоров
1000
1000
2000
Рис. 4.14. Отношение R1 JOIN R2
Получаем, что R1 JOIN R2 ≠ R, т. е. без дополнительных ограничений на отношение R нельзя говорить о декомпозиции без потерь.
Такими дополнительными ограничениями и являются функциональные зависимости.
Имеет место следующая т е о р е м а Х е з а .
Пусть R(A,B,C) является отношением и A,B,C – атрибуты или множества атрибутов этого отношения. Если имеется функциональная
зависимость и A → B, то проекции R1 = R[A,B] и R2 = R[A,C] образуют
декомпозицию без потерь.
Доказательство теоремы Хеза можно найти в [19].
З а м е ч а н и е . Основной смысл теоремы Хеза заключается в доказательстве того, что при декомпозиции н е п о я в я т с я новые
кортежи, отсутствовавшие в исходном отношении.
Так как алгоритм нормализации (приведения отношений к 3НФ)
основан на имеющихся в отношениях функциональных зависи83
мостях, то теорема Хеза показывает, что алгоритм нормализации
является корректным, т. е. в ходе нормализации не происходит потери информации.
4.8. Нормальные формы высших порядков
4.8.1. Нормальная форма Бойса – Кодда
В большинстве случаев вполне достаточно второй и третьей нормальных форм, чтобы разрабатывать работоспособные БД. Но на
самом деле существуют еще нормальные формы более высоких порядков, а именно нормальная форма Бойса – Кодда (НФБК), четвертая нормальная форма (4НФ), пятая нормальная форма (5НФ).
О п р е д е л е н и е 11. Отношение R находится в НФБК тогда и только тогда, когда детерминанты всех функциональных зависимостей
являются потенциальными ключами.
Пример
Пусть требуется хранить данные о поставках деталей некоторыми поставщиками. Предположим, что наименования поставщиков
являются уникальными. Кроме того, каждый поставщик имеет
свой уникальный номер. Данные о поставках можно хранить в отношении, приведенном на рис. 4.15. Оно содержит два потенциальных ключа – {PNUM, DNUM} и {PNAME, DNUM}. Видно, что данные хранятся в отношении с избыточностью: при изменении наименования
поставщика это наименование нужно изменить во всех кортежах,
где оно встречается. Можно ли эту аномалию устранить при помощи алгоритма нормализации, описанного в 4.6? Для этого нужно
выявить имеющиеся функциональные зависимости (как обычно,
курсивом выделены ключевые атрибуты):
Номер поставщика
PNUM
Наименование
поставщика
PNAME
Номер детали
DNUM
Поставляемое количество
VOLUME
1
Фирма 1
1
100
1
Фирма 1
2
200
1
Фирма 1
3
300
2
Фирма 2
1
150
2
Фирма 2
2
250
3
Фирма 3
1
1000
Рис. 4.15. Отношение поставки
84
– PNUM → PNAME – наименование поставщика зависит от номера поставщика;
– PNAME → PNUM – номер поставщика зависит от наименования поставщика;
– {PNUM, DNUM} → VOLUME – поставляемое количество зависит от
первого ключа отношения;
– {PNUM, DNUM} → PNAME – наименование поставщика зависит от
первого ключа отношения;
– {PNAME, DNUM} → VOLUME – поставляемое количество зависит от
второго ключа отношения;
– {PNAME, DNUM} → PNUM – номер поставщика зависит от второго
ключа отношения.
Данное отношение не содержит неключевых атрибутов, зависящих от части сложного ключа (см. определение 2НФ). Действительно,
от части сложного ключа зависят атрибуты PNAME и PNUM, но они сами
являются ключевыми. Таким образом, отношение находится в 2НФ.
Кроме того, отношение не содержит зависимых друг от друга
неключевых атрибутов, так как неключевой атрибут всего один –
VOLUME (см. определение 3НФ). Таким образом, отношение Поставки
находится в 3НФ.
Следовательно, описанный ранее алгоритм нормализации неприменим к данному отношению. Очевидно, однако, что аномалия
данного отношения устраняется путем декомпозиции его на два
следующих отношения (рис. 4.16, 4.17):
Номер поставщика
PNUM
Наименование поставщика
PNAME
1
2
3
Фирма 1
Фирма 2
Фирма 3
Рис. 4.16. Отношение Поставщики
Номер поставщика
PNUM
Номер детали
DNUM
Поставляемое количество
VOLUME
1
1
1
2
2
3
1
2
3
1
2
1
100
200
300
150
250
1000
Рис. 4.17. Отношение Поставки-2
85
Отношение Поставки не находится в НФБК, так как имеются зависимости (PNUM → PNAME и PNAME → PNUM), детерминанты которых не
являются потенциальными ключами.
Для того чтобы устранить зависимость от детерминантов, не
являющихся потенциальными ключами, необходимо провести декомпозицию, вынося эти детерминанты и зависимые от них части в
отдельное отношение. Отношения Поставщики и Поставки-2, полученные в результате декомпозиции, находятся в НФБК.
4.6.2. Четвертая нормальная форма
Рассмотрим пример 4НФ. Пусть требуется учитывать данные об
абитуриентах, поступающих в вуз. При анализе предметной области были выделены следующие требования:
1. Каждый абитуриент имеет право сдавать экзамены на несколько факультетов одновременно.
2. Каждый факультет имеет свой список сдаваемых предметов.
3. Один и тот же предмет может сдаваться на нескольких факультетах.
4. Абитуриент обязан сдавать все предметы, указанные для факультета, на который он поступает, несмотря на то, что он, может
быть, уже сдавал такие же предметы на другом факультете.
Предположим, что нам требуется хранить данные о том, какие
предметы должен сдавать каждый абитуриент. Попытаемся хранить данные в одном отношении Абитуриенты_Факультеты_Предметы
(рис. 4.18):
Абитуриент
Факультет
Предмет
Иванов
Иванов
Иванов
Иванов
Петров
Петров
Математический
Математический
Физический
Физический
Математический
Математический
Математика
Информатика
Математика
Физика
Математика
Информатика
Рис. 4.18. Отношение Абитуриенты_Факультеты_Предметы
В отношении имеется аномалия обновления, связанная с тем,
что дублируются фамилии абитуриентов, наименования факультетов и наименования предметов. Однако эта аномалия легко устраняется стандартным способом – вынесением всех наименований в
отдельные отношения, оставляя в исходном отношении только соответствующие номера (рис. 4.19–4.22):
86
Номер
Абитуриента
Номер
Факультета
Номер
Предмета
1
1
1
1
2
2
1
1
2
2
1
1
1
2
1
3
1
2
Рис. 4.19. Модифицированное отношение
Абитуриенты_Факультеты_Предметы
Номер
Абитуриента
Абитуриент
1
2
Иванов
Петров
Рис. 4.20. Отношение Абитуриенты
Номер
Факультета
Факультет
1
2
Математический
Физический
Рис. 4.21. Отношение Факультеты
Номер
Предмета
Предмет
1
2
3
Математика
Информатика
Физика
Рис. 4.22. Отношение Предметы
Теперь каждое наименование встречается только в одном месте.
И все-таки как в исходном, так и в модифицированном отношении имеются аномалии обновления, возникающие при попытке
вставить или удалить кортежи. Это вызвано тем обстоятельством,
что вставка и удаление кортежей не может быть выполнена независимо от других кортежей отношения. Так, например, при попытке
удалить кортеж (Иванов, Математический, Математика), мы обязаны
удалить также и кортеж (Иванов, Математический, Информатика).
Декомпозиция отношения Абитуриенты_Факультеты_Предметы для
устранения указанных аномалий не может быть выполнена на
основе функциональных зависимостей, так как это отношение не
87
содержит никаких функциональных зависимостей. Это отношение
является полностью ключевым, т. е. ключом отношения является
все множество атрибутов. Но ясно, что какая-то взаимосвязь между атрибутами имеется. Эта взаимосвязь описывается понятием
многозначной зависимости.
О п р е д е л е н и е 12. Пусть R – отношение и X,Y,Z – некоторые
из его атрибутов (или непересекающиеся множества атрибутов).
Тогда атрибуты Y и Z многозначно зависят от X (обозначается:
X → → Y|Z), тогда и только тогда, когда из того, что в отношении R
содержатся кортежи r1 = (x,y,z1) и r2 = (x,y1,z) следует, что в отношении R содержится также и кортеж r3 = (x,y,z).
В отношении Абитуриенты_Факультеты_Предметы имеется многозначная зависимость Факультет → → Абитуриент|Предмет.
Словами это можно выразить так: для каждого факультета (для
каждого значения из X) каждый поступающий на него абитуриент
(значение из Y) сдает один и тот же список предметов (набор значений из Z), и для каждого факультета (для каждого значения из X)
каждый сдаваемый на факультете экзамен (значение из Z) сдается
одним и тем же списком абитуриентов (набор значений из Y).
Именно наличие этой зависимости не позволяет независимо
вставлять и удалять кортежи. Кортежи обязаны вставляться и удаляться одновременно целыми наборами.
Понятие многозначной зависимости является обобщением понятия функциональной зависимости.
О п р е д е л е н и е 13. Многозначная зависимость X → → Y|Z называется нетривиальной, если не существует функциональных зависимостей X → Y и X → Z.
В отношении Абитуриенты_Факультеты_Предметы имеется именно нетривиальная многозначная зависимость Факультет → →
Абитуриент|Предмет.
Введя понятие нетривиальной многозначной зависимости, дадим определение (4НФ).
О п р е д е л е н и е 14. Отношение R находится в 4НФ тогда и только тогда, когда отношение находится в НФБК и не содержит нетривиальных многозначных зависимостей.
В силу нетривиальности этой зависимости мы не можем воспользоваться теоремой Хеза для декомпозиции отношения. Однако
Р. Фейджином [28] доказана следующая т е о р е м а :
Пусть X,Y,Z – непересекающиеся множества атрибутов отношения R(X,Y,Z). Декомпозиция отношения R на проекции R1 = R[X,Y]
и R2 = R[X,Y] будет декомпозицией без потерь тогда и только тогда,
когда имеется многозначная зависимость X → → Y|Z.
88
Доказательство теоремы Фейджина можно найти в [14].
З а м е ч а н и е . Если зависимость X → → Y|Z является тривиальной, т. е. существует одна из функциональных зависимостей X → Y
или X → Z, то получаем теорему Хеза.
Отношение Абитуриенты_Факультеты_Предметы находится в НФБК, но
не в 4НФ. Согласно теореме Фейджина это отношение можно без потерь декомпозировать на следующие отношения (рис. 4.23):
Факультет
Абитуриент
Математический
Иванов
Физический
Иванов
Математический
Петров
Рис. 4.23. Отношение Факультеты_Абитуриенты
Факультет
Предмет
Математический
Математика
Математический
Информатика
Физический
Математика
Физический
Физика
Рис. 4.24. Отношение Факультеты_Предметы
В полученных отношениях устранены аномалии вставки и удаления, характерные для отношения Абитуриенты_Факультеты_Предметы.
Заметим, что полученные отношения остались полностью ключевыми, и в них по-прежнему нет функциональных зависимостей.
Отношения с нетривиальными многозначными зависимостями
возникают, как правило, в результате естественного соединения
двух отношений по общему полю, которое н е я в л я е т с я ключевым ни в одном из отношений. Фактически это приводит к попытке
хранить в одном отношении информацию о двух н е з а в и с и м ы х
сущностях.
4.6.3. Пятая нормальная форма
Функциональные и многозначные зависимости позволяют произвести декомпозицию исходного отношения без потерь на д в е
проекции. Можно, однако, привести примеры отношений, которые
нельзя декомпозировать без потерь ни на какие две проекции.
89
Пример
Рассмотрим следующее отношение R (рис. 4.25):
X
Y
Z
1
1
2
1
1
2
1
1
2
1
1
1
Рис. 4.25. Отношение R
Всевозможные проекции отношения R, включающие по два
атрибута, имеют вид (рис. 4.26–4.28):
X
Y
X
Z
Y
Z
1
1
2
1
2
1
1
1
2
2
1
1
1
2
1
2
1
1
Рис. 4.26. Проекция
R1 = R[X,Y]
Рис. 4.27. Проекция
R2 = R[X,Z]
Рис. 4.28. Проекция
R3 = R[Y,Z]
Как легко заметить, отношение не восстанавливается ни по одному из попарных соединений: R1 JOIN R2, R1 JOIN R3 или R2 JOIN R3.
Однако отношение R восстанавливается соединением в с е х
т р е х проекций:
R1 JOIN R2 JOIN R3.
Это говорит о том, что между атрибутами этого отношения также имеется некоторая зависимость, но она не является ни функциональной, ни многозначной. Данная зависимость относится к более
общему понятию «зависимость соединения» [19].
О п р е д е л е н и е 15. Пусть R является отношением, а (A,B, …,
Z) произвольными (возможно пересекающимися) подмножествами
множества атрибутов отношения R. Тогда отношение R удовлетворяет зависимости соединения
*(A,B, …, Z)
тогда и только тогда, когда оно равносильно соединению всех своих
проекций с подмножествами атрибутов A,B, …, Z, т. е.
R = R[A] JOIN R[B] JOIN... R[Z].
О п р е д е л е н и е 16. Зависимость соединения *(A,B, …, Z) называется тривиальной зависимостью соединения, если выполняется
одно из условий:
90
– либо все множества атрибутов A,B, …, Z содержат потенциальный ключ отношения R;
– либо одно из множеств атрибутов совпадает со всем множеством атрибутов отношения R.
О п р е д е л е н и е 17. Отношение R находится в 5НФ тогда и только тогда, когда любая имеющаяся зависимость соединения является тривиальной.
Определения 5НФ может стать более понятным, если сформулировать его в отрицательной форме.
О п р е д е л е н и е 18. Отношение R не находится в 5НФ, если в отношении найдется нетривиальная зависимость соединения.
Возвращаясь к примеру (см. рис. 4.25), становится понятно, что
не зная ничего о том, какие потенциальные ключи имеются в отношении и как взаимосвязаны атрибуты, нельзя делать выводы о том,
находится ли данное отношение в 5НФ (как, впрочем, и в других нормальных формах). Для определения нормальной формы необходим
анализ предметной области и выявление зависимости атрибутов.
Познакомившись с нормальными формами высоких порядков,
мы можем продолжить алгоритм приведения отношений к 3НФ, доведя его до алгоритма приведения к 5НФ.
Шаг 4 (приведение к НФБК). Если имеются отношения, содержащие несколько потенциальных ключей, то необходимо проверить,
имеются ли функциональные зависимости, детерминанты которых
не являются потенциальными ключами. Если такие функциональные зависимости имеются, то необходимо провести дальнейшую
декомпозицию отношений. Те атрибуты, которые зависят от детерминантов, не являющихся потенциальными ключами, выносятся в
отдельное отношение вместе с детерминантами.
Шаг 5 (приведение к 4НФ). Если в отношениях обнаружены нетривиальные многозначные зависимости, то необходимо провести
декомпозицию для исключения таких зависимостей.
Шаг 6 (приведение к 5НФ). Если в отношениях обнаружены нетривиальные зависимости соединения, то необходимо провести декомпозицию для исключения и таких зависимостей.
91
5. ПРОЕКТИРОВАНИЕ БАЗ ДАННЫХ
НА ОСНОВЕ СЕМАНТИЧЕСКОГО МОДЕЛИРОВАНИЯ
Моделирование структуры БД при помощи алгоритма нормализации, описанного в предыдущих разделах, имеет следующие серьезные недостатки:
1. Первоначальное размещение всех атрибутов в одном отношении является очень неестественной операцией. Интуитивно разработчик сразу проектирует несколько отношений в соответствии с
обнаруженными сущностями. Даже если совершить насилие над
собой и создать одно или несколько отношений, включив в них все
предполагаемые атрибуты, то совершенно неясен смысл полученного отношения.
2. Невозможно сразу определить полный список атрибутов.
Пользователи имеют привычку называть разными именами одни и
те же вещи или, наоборот, называть одними именами разные вещи.
3. Для проведения процедуры нормализации необходимо выделить зависимости атрибутов, что тоже очень нелегко, так как необходимо явно выписать все зависимости, даже те, которые являются
очевидными.
В реальном проектировании структуры БД применяется другой
метод – так называемое семантическое моделирование. Семантическое моделирование представляет собой моделирование структуры данных на основе смысла этих данных. В качестве инструмента
семантического моделирования используются различные варианты диаграмм «сущность – связь» (ER – Entity-Relationship).
Первый вариант модели «сущность – связь» был предложен
в 1976 г. Питером Пин-Шэн Ченом [26]. В дальнейшем многими авторами были разработаны свои варианты подобных моделей (нотация Мартина, нотация IDEF1X, нотация Баркера и др.). Кроме того,
различные программные средства, реализующие одну и ту же нотацию, могут отличаться своими возможностями. По сути, все варианты диаграмм «сущность – связь» исходят из одной идеи – рисунок всегда нагляднее текстового описания. Все такие диаграммы
используют графическое изображение сущностей предметной области, их свойств (атрибутов) и взаимосвязей между сущностями.
Мы опишем работу с ER-диаграммами близко к нотации Баркера, как довольно легкой в понимании основных идей.
5.1. Основные понятия ER-диаграмм
О п р е д е л е н и е 1. Сущность – это класс однотипных объектов,
информация о которых должна быть учтена в модели.
92
Каждая сущность должна иметь наименование, выраженное существительным в единственном числе.
Примерами сущностей могут быть такие классы объектов, как
Поставщик, Сотрудник, Накладная.
Каждая сущность в модели изображается в виде прямоугольника с наименованием (рис. 5.1):
Сотрудник
Рис. 5.1. Сущность Сотрудник
О п р е д е л е н и е 2. Экземпляр сущности – это конкретный
представитель данной сущности.
Например, представителем сущности Сотрудник может быть «Сотрудник Иванов».
Экземпляры сущностей должны быть различимы, т. е. сущности должны иметь некоторые свойства, уникальные для каждого
экземпляра этой сущности.
О п р е д е л е н и е 3. Атрибут сущности – это именованная характеристика, являющаяся некоторым свойством сущности.
Наименование атрибута должно быть выражено существительным в единственном числе (возможно, с характеризующими прилагательными).
Примерами атрибутов сущности Сотрудник могут быть такие
атрибуты как «Табельный номер», «Фамилия», «Имя», «Отчество», «Должность», «Зарплата» и т. п.
Атрибуты изображаются в пределах прямоугольника, определяющего сущность (рис. 5.2):
СОТРУДНИК
Табельный номер
Фамилия
Имя
Отчество
Должность
Зарплата
Рис. 5.2. Атрибуты сущности СОТРУДНИК
О п р е д е л е н и е 4. Ключ сущности – это неизбыточный набор
атрибутов, значения которых в совокупности являются уникальными для каждого экземпляра сущности.
93
Таким образом, «ключ сущности» есть не что иное, как «потенциальный ключ» в реляционной модели данных. Сущность может
иметь несколько различных ключей.
Ключевые атрибуты изображаются на диаграмме подчеркиванием.
О п р е д е л е н и е 5. Связь – это некоторая ассоциация между
двумя сущностями. Одна сущность может быть связана с другой
сущностью или сама с собою.
Связи позволяют по одной сущности находить другие сущности,
связанные с нею.
Например, связи между сущностями могут выражаться следующими фразами – «СОТРУДНИК может иметь несколько ДЕТЕЙ», «каждый СОТРУДНИК обязан числиться ровно в одном ОТДЕЛЕ».
Графически связь изображается линией, соединяющей две сущности:
СОТРУДНИК
Иметь
РЕБЕНОК
Принадлежать
Рис. 5.3. Связь СОТРУДНИК – РЕБЕНОК
Каждая связь имеет два конца и одно или два наименования.
Наименование обычно выражается в неопределенной глагольной
форме: «иметь», «принадлежать» и т. п. Каждое из наименований
относится к своему концу связи. Иногда наименования не пишутся
ввиду их очевидности.
Каждая связь может иметь один из следующих т и п о в с в я зи:
одинкоодному
одинкомногим
многокомногим
Связь типа «один-к-одному» означает, что один экземпляр первой сущности (левой) связан с одним экземпляром второй сущности (правой). Связь «один-к-одному» чаще всего свидетельствует о
94
том, что на самом деле мы имеем всего одну сущность, неправильно
разделенную на две.
Связь типа «один-ко-многим» означает, что один экземпляр
первой сущности (левой) связан с несколькими экземплярами второй сущности (правой). Это наиболее часто используемый тип связи. Левая сущность (со стороны «один») называется родительской,
правая (со стороны «много») – дочерней. Характерный пример такой связи приведен на рис. 5.3.
Связь типа «много-ко-многим» означает, что каждый экземпляр первой сущности может быть связан с несколькими экземплярами второй сущности, и каждый экземпляр второй сущности
может быть связан с несколькими экземплярами первой сущности.
Тип связи «много-ко-многим» является временным типом связи,
допустимым на ранних этапах разработки модели. В дальнейшем
этот тип связи должен быть заменен двумя связями типа «один-комногим» путем создания промежуточной сущности.
Каждая связь может иметь одну из двух м о д а л ь н о с т е й связи:
может
должен
Модальность «может» означает, что экземпляр одной сущности
может быть связан с одним или несколькими экземплярами другой
сущности, а может быть и не связан ни с одним экземпляром.
Модальность «должен» означает, что экземпляр одной сущности обязан быть связан не менее чем с одним экземпляром другой
сущности.
Связь может иметь разную модальность с разных концов (как на
рис. 5.3).
Описанный графический синтаксис позволяет однозначно читать диаграммы, пользуясь следующей схемой построения фраз:
<Каждый экземпляр СУЩНОСТИ 1> <МОДАЛЬНОСТЬ СВЯЗИ> <НАИМЕНОВАНИЕ СВЯЗИ> <ТИП СВЯЗИ> <экземпляр СУЩНОСТИ 2>.
Каждая связь может быть прочитана как слева направо, так и
справа налево. Связь, показанная на рис. 5.3, читается так:
– слева направо: «каждый сотрудник может иметь несколько
детей»;
– справа налево: «каждый ребенок обязан принадлежать ровно
одному сотруднику».
95
5.2. Пример разработки простой ER-модели
При разработке ER-моделей мы должны получить следующую
информацию о предметной области:
– список сущностей предметной области;
– список атрибутов сущностей;
– описание взаимосвязей между сущностями.
ER-диаграммы удобны тем, что процесс выделения сущностей,
атрибутов и связей является итерационным. Разработав первый
приближенный вариант диаграмм, мы уточняем их, опрашивая экспертов предметной области. При этом документацией, в которой
фиксируются результаты бесед, являются сами ER-диаграммы.
Предположим, что перед нами стоит задача разработать информационную систему по заказу некоторой оптовой торговой фирмы. В
первую очередь мы должны изучить предметную область и процессы,
происходящие в ней. Для этого мы опрашиваем сотрудников фирмы,
читаем документацию, изучаем формы заказов, накладных и т. п.
Например, в ходе беседы с менеджером по продажам выяснилось, что он (менеджер) считает, что проектируемая система должна выполнять следующие действия:
– хранить информацию о покупателях,
– печатать накладные на отпущенные товары,
– следить за наличием товаров на складе.
Выделим все существительные в этих предложениях – это будут
потенциальные кандидаты на сущности и атрибуты, и проанализируем их (непонятные термины будем выделять знаком вопроса):
– покупатель – сущность;
– накладная – сущность;
– товар – сущность;
– (?)склад – а вообще, сколько складов имеет фирма? Если несколько, то это будет кандидатом на новую сущность;
– (?)наличие товара – это, скорее всего, атрибут, но атрибут какой
сущности?
Сразу возникает очевидная связь между сущностями – «покупатели могут покупать много товаров» и «товары могут продаваться многим покупателям». Первый вариант диаграммы выглядит так:
ПОКУПАТЕЛЬ Покупать
ТОВАР
Быть проданным
Рис. 5.4. Связь ПОКУПАТЕЛЬ – ТОВАР
96
Задав дополнительные вопросы менеджеру, мы выяснили, что
фирма имеет несколько складов. Причем каждый товар может храниться на нескольких складах и быть проданным с любого склада.
Куда поместить сущности Накладная и Склад и с чем их связать?
Как связаны эти сущности между собой и с сущностями Покупатель
и Товар? Покупатели покупают товары, получая при этом накладные, в которые внесены данные о количестве и цене купленного товара. Каждый покупатель может получить несколько накладных.
Каждая накладная обязана выписываться на одного покупателя.
Каждая накладная обязана содержать несколько товаров (не бывает пустых накладных). Каждый товар, в свою очередь, может быть
продан нескольким покупателям через несколько накладных. Кроме того, каждая накладная должна быть выписана с определенного
склада и с любого склада может быть выписано много накладных.
Таким образом, после уточнения диаграмма будет выглядеть следующим образом (рис. 5.5):
ПОКУПАТЕЛЬ
НАКЛАДНАЯ
ТОВАР
СКЛАД
Рис 5.5. Диаграмма СУЩНОСТЬ – СВЯЗЬ
Следующим шагом к построению ER-диаграммы является определение атрибутов выделенных сущностей.
Проведя опрос сотрудников фирмы, было выяснено следующее:
– каждый покупатель является юридическим лицом и имеет наименование, адрес, банковские реквизиты;
– каждый товар имеет наименование, цену, а также характеризуется единицами измерения;
97
– каждая накладная имеет уникальный номер, дату выписки,
список товаров с количествами и ценами, а также общую сумму
накладной. Накладная выписывается с определенного склада и на
определенного покупателя;
– каждый склад имеет свое наименование.
Снова выпишем все существительные, которые будут потенциальными атрибутами, и проанализируем их:
– юридическое лицо – термин риторический, мы не работаем с физическими лицами. Не обращаем внимания;
– наименование покупателя – явная характеристика покупателя;
– адрес – явная характеристика покупателя;
– банковские реквизиты – явная характеристика покупателя;
– наименование товара – явная характеристика товара;
– (?)цена товара – похоже, что это характеристика товара (Отличается ли эта характеристика от цены в накладной?)
– единица измерения – явная характеристика товара;
– номер накладной – явная уникальная характеристика накладной;
– дата накладной – явная характеристика накладной;
– (?)список товаров в накладной – список не может быть атрибутом. Вероятно, нужно выделить этот список в отдельную сущность;
– (?)количество товара в накладной – это явная характеристика,
но характеристика чего? Это характеристика не просто «товара», а
«товара в накладной»;
– (?)цена товара в накладной – опять же это должна быть не просто характеристика товара, а характеристика товара в накладной
(Но цена товара уже встречалась выше – это одно и то же?)
– сумма накладной – явная характеристика накладной. Эта характеристика не является независимой. Сумма накладной равна сумме
стоимостей всех товаров, входящих в накладную;
– наименование склада – явная характеристика склада.
В ходе дополнительной беседы с менеджером удалось выяснить
различия в понимании цены. Оказалось, что каждый товар имеет некоторую текущую цену. Эта цена, по которой товар продается в данный момент. Естественно, что эта цена может меняться
со временем. Цена одного и того же товара в разных накладных,
выписанных в разное время, может быть различной. Таким образом, имеется две цены – цена товара в накладной и текущая цена
товара.
С возникающим понятием «Список товаров в накладной» все довольно ясно. Сущности Накладная и Товар связаны друг с другом отноше98
нием типа «много-ко-многим». Такая связь, как мы отмечали ранее, должна быть расщеплена на две связи типа «один-ко-многим».
Для этого требуется дополнительная сущность. Этой сущностью и
будет сущность Список товаров в накладной. Связь ее с сущностями
Накладная и Товар характеризуется следующими фразами: «каждая
накладная обязана иметь несколько записей из списка товаров в
накладной», «каждая запись из списка товаров в накладной обязана включаться ровно в одну накладную», «каждый товар может
включаться в несколько записей из списка товаров в накладной»,
« каждая запись из списка товаров в накладной обязана быть связана ровно с одним товаром». Атрибуты «Количество товара в накладной» и «Цена товара в накладной» являются атрибутами сущности
Список товаров в накладной.
Точно также поступим со связью, соединяющей сущности Склад
и Товар. Введем дополнительную сущность «Товар на складе». Атрибутом этой сущности будет «Количество товара на складе». Таким
образом, товар будет числиться на любом складе и количество его
на каждом складе будет свое.
Теперь можно внести все это в диаграмму (рис. 5.6):
ПОКУПАТЕЛЬ
Номер покупателя
Наименование
покупателя
НАКЛАДНАЯ
Адрес
Номер
накладной
Банковские
Дата накладной
реквизиты
Выписывать на Сумма накладной
Выписывать со
Выписывать
ТОВАР
Номер товара
Наименование товара
Единица измерения
Текущая цена
Содержаться в
СКЛАД
Номер склада
Наименование склада
Связываться с
Хранить
Принадлежать
ЗАПИСЬ СПИСКА
Количество товара
Цена товара
ТОВАР НА СКЛАДЕ
Храниться на
Количество товара на
складе
Связываться с
Рис. 5.6. ER-диаграмма (логический уровень)
99
Разработанный выше пример ER-диаграммы является примером
к о н ц е п т у а л ь н о й диаграммы. Это означает, что диаграмма не
учитывает особенности конкретной СУБД. По данной концептуальной диаграмме можно построить ф и з и ч е с к у ю диаграмму, которая уже будет учитывать такие особенности СУБД, как допустимые
типы и наименования полей и таблиц, ограничения целостности и
т. п. Физический вариант диаграммы, приведенной на рис. 5.6, может выглядеть, например, следующим образом (рис. 5.7).
На данной диаграмме каждая сущность представляет собой таблицу БД, каждый атрибут становится колонкой соответствующей
таблицы. Обращаем внимание на то, что во многих таблицах, например «CUST_DETAIL» и «PROD_IN_SKLAD», соответствующих сущностям Запись списка и Товар на складе, появились новые атрибуты,
которых не было в концептуальной модели – это ключевые атрибуты родительских таблиц, мигрировавших в дочерние таблицы для
того, чтобы обеспечить связь между таблицами посредством внешних ключей.
CUSTOMER_ID-CUSTOMER_ID
CUSTOMER
CUSTOMER_ID INTEGER
CUSTOMER_NAME CHAR(50)
ADDRESS CHAR(100)
BANK CHAR(100)
SKLAD_IDCUST
SKLAD_ID
CUST_ID
CUST_ID
INTEGER
CUSTOMER_ID INTEGER
CAST_DATE DATE
CAST_SUMMA NUMBER(10,2)
SKLAD_ID
INTEGER
SKLAD
SKLAD_ID
INTEGER
SKLAD_NAME CHAR(10)
SKLAD_ID – SKLAD_ID
PRODUCT
PRODUCT_ID
INTEGER
PRODUCT_NAME CHAR(10)
UNIT
CHAR(10)
CUR_PRICE
NUMBER(10)
– CUST_ID
CAST _DETAIL
CUST_ID
INTEGER
PRODUCT_ID INTEGER
KOL
NUMBER(10)
PRICE
NUMBER(10)
PRODUCT_ID-RODUCT_ID
PROD_IN_SKLAD
SKLAD_ID
INTEGER
PRODUCT_ID INTEGER
CUR_KOL
NUMBER(10)
Рис. 5.7. ER-диаграмма [физический (внутренний) уровень]
При правильном определении сущностей полученные таблицы
будут сразу находиться в 3НФ. Основное достоинство метода состоит
в том, что модель строится методом последовательных уточнений
первоначальных диаграмм.
Наиболее часто на практике семантическое моделирование используется на первой стадии проектирования БД. При этом в терминах семантической модели производится концептуальная схема БД,
100
которая затем вручную преобразуется к реляционной (или какойлибо другой) схеме данных. Этот процесс выполняется под управлением методик, в которых достаточно четко оговорены все этапы
такого преобразования.
Менее часто реализуется автоматизированная компиляция концептуальной схемы в реляционную. При этом известны два подхода:
– на основе явного представления концептуальной схемы как
исходной информации для компилятора;
– на основе построения интегрированных систем проектирования с автоматизированным созданием концептуальной схемы на
основе интервью с экспертами предметной области.
И в том и в другом случае в результате производится реляционная схема БД в 3НФ.
Наконец, третья возможность, которая еще не вышла (или только выходит) за пределы исследовательских и экспериментальных
проектов, – это работа с БД в семантической модели, т. е. СУБД, основанные на семантических моделях данных. При этом снова рассматриваются два варианта: обеспечение пользовательского интерфейса на основе семантической модели данных с автоматическим
отображением конструкций в реляционную модель данных (это
задача примерно такого же уровня сложности, как автоматическая компиляция концептуальной схемы БД в реляционную схему)
и прямая реализация СУБД, основанная на какой-либо семантической модели данных. Наиболее близко ко второму подходу находятся современные объектно-ориентированные СУБД, модели данных
которых по многим параметрам близки к семантическим моделям
(хотя в некоторых аспектах они более мощны, а в некоторых – более слабы).
5.3. Схема данных в СУБД Access
В СУБД Access процесс создания реляционной БД включает создание схемы данных. Схема данных наглядно отображает таблицы и
связи между ними, а также обеспечивает использование связей при
обработке данных.
Основное отличие схемы данных от ER-диаграммы состоит в том,
что в схеме данных устанавливаются параметры обеспечения целостности связей в БД.
Таким образом, осуществляется неразрывная связь внемашинного проектирования БД с этапом ее создания с помощью СУБД.
В схеме данных, построенной по нормализованной модели данных
101
(например, с использованием семантического моделирования с помощью ER-диаграмм), могут быть установлены одно-однозначные
и одно-многозначные связи по конкретным полям связываемых
таблиц (а не связи между сущностями, как в ER-диаграммах). Для
таких связей обеспечивается поддержание целостности взаимосвязанных данных, при которой не допускается наличия в БД подчиненной записи без связанной с ней главной, при первоначальной
загрузке БД и ее корректировках. Связи, определенные в схеме
данных, используются автоматически при разработке многотабличных форм, запросов, отчетов, существенно упрощая процесс их
конструирования.
При создании в Access схемы данных в ней определяются и запоминаются связи между таблицами. Это позволяет системе автоматически использовать связи, один раз определенные в схеме
данных, при создании форм, запросов, отчетов на основе взаимосвязанных таблиц, а пользователь освобождается от необходимости указывать эти связи при конструировании этих объектов. Схема данных базы графически отображается в своем окне, где таблицы представлены списками полей, а связи – линиями между полями разных таблиц.
Для рассмотренного выше примера схема данных в Access будет
иметь вид, показанный на рис. 5.8.
Рис. 5.8. Схема данных в СУБД Access
102
При создании схемы данных пользователь включает в неё таблицы и устанавливает связи между ними. Для связей типа 1:1 и 1:М
можно задать параметр обеспечения связной целостности данных,
а также автоматическое каскадное обновление и удаление связанных записей.
З а м е ч а н и е . Связь типа 1:1 обычно удаляется путем объединения двух таблиц по ключевому полю.
Обеспечение связной целостности данных означает, что Access
при корректировке БД обеспечивает для связанных таблиц контроль за соблюдением следующих условий:
– в подчиненную таблицу не может быть добавлена запись с несуществующим в главной таблице значением ключа связи;
– в главной таблице нельзя удалить запись, если не удалены связанные с ней записи в подчиненной таблице;
– изменение значений ключа связи в записи главной таблицы
невозможно, если в подчиненной таблице имеются связанные с ней
записи.
При попытке пользователя нарушить эти условия в операциях
добавления и удаления записей или обновления ключевых данных
в связанных таблицах Access выводит соответствующее сообщение
и не допускает выполнения операции.
Установление между двумя таблицами связи типа 1:М или 1:1 и
задание для нее параметров целостности данных возможно только
при следующих условиях:
– связываемые поля имеют одинаковый тип данных, причем
имена полей могут быть различными;
– обе таблицы сохраняются в одной БД Access;
– главная таблица связывается с подчиненной по первичному
простому или составному ключу (уникальному индексу) главной
таблицы.
Access автоматически отслеживает целостность связей при добавлении и удалении записей и изменении значений ключевых полей, если между таблицами в схеме данных установлена связь с параметрами обеспечения целостности. При действиях, нарушающих
целостность связей таблиц, выводится сообщение. Access не позволяет установить параметр целостности для связи таблиц, если ранее введенные в таблицы данные не отвечают требованиям целостности.
Если для выбранной связи обеспечивается поддержание целостности, можно задать режим каскадного обновления связанных полей и режим каскадного удаления связанных записей. В режиме
каскадного о б н о в л е н и я связанных полей при изменении зна103
чения поля связи в записи главной таблицы, Access автоматически
изменит значения в соответствующем поле в подчиненных записях.
В режиме каскадного у д а л е н и я связанных записей при удалении записи из главной таблицы будут автоматически удаляться
все связанные записи в подчиненных таблицах. При удалении записи из главной таблицы выполняется каскадное удаление подчиненных записей на всех уровнях, если этот режим задан на каждом
уровне.
При удалении записей непосредственно в таблице или через форму выводится предупреждение о возможности удаления связанных
записей.
104
Библиографический список
1. Атре Ш. Структурный подход к организации баз данных. М.:
Финансы и статистика, 1983. 320 с.
2. Бойко В. В., Савинков В. М. Проектирование баз данных информационных систем. М.: Финансы и статистика, 1989. 351 с.
3. Вейнеров О. М., Самохвалов Э. Н. Проектирование баз данных
САПР. М.: Высш. школа, 1990. 114 с.
4. Гилуа М. М. Множественная модель данных в информационных системах. М.: Наука, 1992.
5. Голосов А. О. Аномалии в реляционных базах данных//СУБД.
1986. № 3. С. 23–28.
6. Дейт К. Руководство по реляционной СУБД DB2. М.: Финансы и статистика, 1988. 320 с.
7. Дейт К. Введение в системы баз данных. 6-е изд. Киев: Диалектика, 1998. 784 с.
8. Диго С. М. Проектирование и использование баз данных. М.:
Финансы и статистика, 1995. 208 с.
9. Кодд Е. Ф. Реляционная модель данных для больших совместно используемых банков данных. СУБД № 1, 1995.
10. Кузнецов С. Д. Введение в системы управления базами данных//СУБД. 1995. № 1–4; 1996. № 1–5.
11. Кузнецов С. Д. Неопределенная информация и трехзначная
логика//СУБД. 1997. № 5. С. 65–67.
12. Ладыженский Г. М. Системы управления базами данных –
коротко о главном//СУБД. 1995. № 1–4.
13. Мартин Д. Планирование развития автоматизированных
систем. М.: Финансы и статистика, 1984. 196 с.
14. Мейер М. Теория реляционных баз данных. М.: Мир, 1987.
608 с.
15. Оззу М. Т., Валдуриз П. Распределенные и параллельные
системы баз данных//СУБД. 1996. № 4. С. 4–26.
16. Озкарахан Э. Машины баз данных и управление базами данных. М.: Мир, 1989.
17. Пржиялковский В. В. Абстракции в проектировании БД//
СУБД. 1998. № 1. С. 90–97.
18. Прохоров А. Определение оптимальной структуры базы данных//Informix magazine. Русское издание. 1998. Апрель.
19. Пушников А. Ю. Введение в системы управления базами данных. Ч. 2. Нормальные формы отношений и транзакции: Учеб. пособие/Изд-во БГУ. Уфа, 1999. 138 с.
105
20. Нагао М., Катаяма Т., Уэмура С. Структуры и базы данных.
М.: Мир, 1986. 197 с.
21. Тиори Т., Фрай Д. Проектирование структур баз данных:
В 2 кн. М.: Мир, 1985. Кн. 1. 287 с.; Кн. 2. 320 с.
22. Ульман Д. Основы систем баз данных. М.: Финансы и статистика, 1983. 334 с.
23. Хаббард Д. Автоматизированное проектирование баз данных. М.: Мир, 1984. 294 с.
24. Цаленко М. Ш. Моделирование семантики в базах данных.
М.: Наука, 1988.
25. Цикритизис Д., Лоховски Ф. Модели данных. М.: Финансы
и статистика, 1985. 344 с.
26. Чен П. Модель «сущность – связь» – шаг к единому представлению о данных//СУБД. 1995. № 3. С. 137–158.
27. Codd E. F. Recent Investigation in Relational Data Base
Systems//Information Processing-74. North-Holland, 1974. P. 1017–
1021.
28. Fagin R. A. Normal Form for Relational Databases That is Based
of Domains and Keys//ACM Trans. On Database Systems. 1981. Vol. 6.
№ 3. P. 387–415.
106
Содержание
Введение.......................................................................... 3
1. Основные понятия теории баз данных............................... 6
1.1. Три уровня архитектуры баз данных......................... 6
1.2. Логические модели данных...................................... 14
1.3. Собственно база данных и приложения...................... 16
2. Введение в реляционные базы данных.............................. 20
2.1. Основные понятия и определения.............................. 20
2.2. Целостность реляционных данных............................ 29
2.2.1. Null-значения...................................................... 29
2.2.2. Трехзначная логика (3VL)..................................... 31
2.2.3. Потенциальные ключи.......................................... 32
2.2.4. Внешние ключи................................................... 33
2.2.5. Правило ссылочной целостности............................ 34
2.2.6. Потенциальные ключи и null-значения .................. 39
2.2.7. Внешние ключи и null-значения............................. 41
3. Реляционные операторы................................................. 43
3.1. Реляционная алгебра.............................................. 43
3.1.1. Традиционные операции над множествами ............. 43
3.1.2. Специальные реляционные операции...................... 48
3.1.3. Назначение реляционной алгебры.......................... 57
3.2. Реляционное исчисление......................................... 58
4. Нормальные формы баз данных....................................... 64
4.1. Первая нормальная форма....................................... 65
4.2. Аномалии редактирования....................................... 66
4.3. Функциональные зависимости................................. 69
4.4. Вторая нормальная форма ....................................... 71
4.5. Третья нормальная форма........................................ 74
4.6. Алгоритм нормализации (приведение к 3НФ)............. 76
4.7. Корректность процедуры нормализации.
Теорема Хеза................................................................ 80
4.8. Нормальные формы высших порядков....................... 84
4.8.1. Нормальная форма Бойса – Кодда .......................... 84
4.6.2. Четвертая нормальная форма ................................ 86
4.6.3. Пятая нормальная форма . .................................... 89
5. Проектирование баз данных на основе семантического
моделирования................................................................. 92
5.1. Основные понятия ER-диаграмм............................... 92
5.2. Пример разработки простой ER-модели..................... 96
5.3. Схема данных в СУБД Access.................................... 101
Библиографический список ............................................... 105
107
Учебное издание
Галанина Валентина Александровна
БАЗЫ ДАННЫХ
ВВЕДЕНИЕ В ТЕОРИЮ
РЕЛЯЦИОННЫХ БАЗ ДАННЫХ
Учебное пособие
Редактор Г. Д. Бакастова
Верстальщик С. Б. Мацапура
Сдано в набор 22.10.08. Подписано к печати 28.11.08.
Формат 60×84 1/16. Бумага офсетная. Печать офсетная.
Усл.-печ. л. 6,28. Уч.-изд. л. 7,03. Тираж 100 экз. Заказ № 618
Редакционно-издательский центр ГУАП
190000, Санкт-Петербург, Б. Морская ул., 67
Документ
Категория
Без категории
Просмотров
8
Размер файла
1 043 Кб
Теги
galanin
1/--страниц
Пожаловаться на содержимое документа