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

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

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

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

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

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

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

Лекция 2. Инфологическая модель данных «Сущность-связь»

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

Рис. 2.1. Уровни моделей данных

Такая человеко-ориентированная модель полностью независима от физических параметров среды хранения данных. В конце концов этой средой может быть память человека, а не ЭВМ. Поэтому инфологическая модель не должна изменяться до тех пор, пока какие-то изменения в реальном мире не потребуют изменения в ней некоторого определения, чтобы эта модель продолжала отражать предметную область.

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

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

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

Инфологическая модель отображает реальный мир в некоторые понятные человеку концепции, полностью независимые от параметров среды хранения данных. Существует множество подходов к построению таких моделей: графовые модели, семантические сети, модель "сущность-связь" и т.д. Наиболее популярной из них оказалась модель "сущность-связь".

В реальном проектировании структуры базы данных применяется другой метод - так называемое, семантическое моделирование. Семантическое моделирование представляет собой моделирование структуры данных, опираясь на смысл этих данных. В качестве инструмента семантического моделирования используются различные варианты диаграмм сущность-связь (ER - Entity-Relationship).

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

2.2 Основные понятия

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

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

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

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

Сущность - любой различимый объект или класс однотипных различимых объектов (объект, который мы можем отличить от другого), информацию о котором необходимо хранить в базе данных. Сущностями могут быть люди, места, самолеты, рейсы, вкус, цвет и т.д. Необходимо различать такие понятия, как тип сущности и экземпляр сущности. Понятие тип сущности относится к набору однородных объектов выступающих как целое. Экземпляр сущности относится к конкретной вещи в наборе. Например, типом сущности может быть ГОРОД, а экземпляром - Москва, Киев и т.д. То есть, понятие - тип сущности.

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

Каждый объект в конкретный момент времени характеризуется определенным состоянием. Это состояние описывается с помощью ограниченного набора свойств и связей (отношений) с другими объектами.

Свойства объекта могут .не зависеть от его связей (объектных отношений) с другими объектами, т. е. являются локальными. Если свойства объекта зависят от связей с другими объектами, то называются реляционными.

Атрибут - поименованная характеристика сущности. Его наименование должно быть уникальным для конкретного типа сущности, но может быть одинаковым для различного типа сущностей (например, ЦВЕТ может быть определен для многих сущностей: СОБАКА, АВТОМОБИЛЬ, ДЫМ и т.д.). Атрибуты используются для определения того, какая информация должна быть собрана о сущности. Примерами атрибутов для сущности АВТОМОБИЛЬ являются ТИП, МАРКА, НОМЕРНОЙ ЗНАК, ЦВЕТ и т.д. Здесь также существует различие между типом и экземпляром. Тип атрибута ЦВЕТ имеет много экземпляров или значений:

Красный, Синий, Банановый, Белая ночь и т.д.,

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

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

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

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

Ассоциация - логическая операция, которая устанавливает связи между конкретными сущностями разных понятий. Например: студент, преподаватель, дисциплина - это понятия, которые ассоциируются с понятием - чтение лекций.

1.3 Характеристика связей и язык моделирования

При построении инфологических моделей можно использовать язык ER-диаграмм (от англ. Entity-Relationship, т.е. сущность-связь). В них сущности изображаются помеченными прямоугольниками, ассоциации - помеченными ромбами или шестиугольниками, атрибуты - помеченными овалами, а связи между ними - ненаправленными ребрами, над которыми может проставляться степень связи (1 или буква, заменяющая слово "много") и необходимое пояснение.

Между двумя сущностям, например, А и В возможны четыре вида связей.

Первый тип - связь ОДИН-К-ОДНОМУ (1:1): в каждый момент времени каждому представителю (экземпляру) сущности А соответствует 1 или 0 представителей сущности В:

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

Второй тип - связь ОДИН-КО-МНОГИМ (1:М): одному представителю сущности А соответствуют 0, 1 или несколько представителей сущности В.

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

Так как между двумя сущностями возможны связи в обоих направлениях, то существует еще два типа связи МНОГИЕ-К-ОДНОМУ (М:1) и МНОГИЕ-КО-МНОГИМ (М:N).

Пример 2.1. Если связь между сущностями МУЖЧИНЫ и ЖЕНЩИНЫ называется БРАК, то существует четыре возможных представления такой связи:



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

множество связей между одними и теми же сущностями

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

тренарные связи

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

связи более высоких порядков, семантика (смысл) которых иногда очень сложна.

В приведенных примерах для повышения иллюстративности рассматриваемых связей не показаны атрибуты сущностей и ассоциаций во всех ER-диаграммах. Так, ввод лишь нескольких основных атрибутов в описание брачных связей значительно усложнит ER-диаграмму (рис. 2.2,а). В связи с этим язык ER-диаграмм используется для построении небольших моделей и иллюстрации отдельных фрагментов больших. Чаще же применяется менее наглядный, но более содержательный язык инфологического моделирования (ЯИМ), в котором сущности и ассоциации представляются предложениями вида:

СУЩНОСТЬ (атрибут 1, атрибут 2 , ..., атрибут n)

АССОЦИАЦИЯ [СУЩНОСТЬ S1, СУЩНОСТЬ S2, ...]

(атрибут 1, атрибут 2, ..., атрибут n)

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

Так, рассмотренный выше пример множества связей между сущностями, может быть описан на ЯИМ следующим образом:

Врач (Номер_врача, Фамилия, Имя, Отчество, Специальность)

Пациент (Регистрационный_номер, Номер койки, Фамилия,

Имя, Отчество, Адрес, Дата рождения, Пол)

Лечащий_врач [Врач 1, Пациент M]

(Номер_врача, Регистрационный_номер)

Консультант [Врач M, Пациент N]

(Номер_врача, Регистрационный_номер).

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

Брак (Номер_свидетельства, Фамилия_мужа, Имя_мужа,

Отчество_мужа, Дата_рождения_мужа, Фамилия_жены,

... , Дата_регистрации, Место_регистрации, ...),

ER-диаграмма которой приведена на рис. 2.2,б.



Рис. 2.2. Примеры ER-диаграмм

Пример 2.3. Теперь рассмотрим ситуацию, когда отдел ЗАГС расположен в стране, допускающей многоженство. Если для регистрации браков использовать сущность "Брак" примера 2.2, то будут дублироваться сведения о мужьях, имеющих несколько жен (см. табл. 2.2).

Дублирование можно исключить созданием дополнительной сущности "Мужья"

Таблица 2.3

Номер свидетельства	Фамилия мужа	...	Фамилия жены	...	Дата регистрации
1-ЮБ 154745	Петухов	...	Курочкина	...	06/03/1991
1-ЮБ 163489	Петухов	...	Пеструшкина	...	11/08/1991
1-ЮБ 169887	Петухов	...	Рябова	...	12/12/1992
1-ЮБ 169878	Селезнев	...	Уточкина	...	12/12/1992
1-ЮБ 154746	Парасюк	...	Свинюшкина	...	06/03/1991
1-ЮБ 169879	Парасюк	...	Хаврония	...	12/12/1992
...	...	...	...	...	...

Мужья (Код_М, Фамилия, Имя, Отчество, Дата рождения, Место рождения) и заменой сущности "Брак" характеристикой со ссылкой на соответствующее описание в сущности "Мужья".

Брак (Номер свидетельства, Код_М, Фамилия жены, ...,

Дата регистрации, ...){Мужья}.

ER-диаграмма связи этих сущностей показана на рис. 2.2,в, а пример их экземпляров в табл. 2.2 и 2.3.

Таблица 2.2

Код_М	Фамилия	Имя	Отчество	Год/р.	Место рожд.
111	Петухов	Альфред	Остапович	1971	г. Цапелька
112	Селезнев	Вавила	Абрамович	1973	г. Гусев
113	Парасюк	Гораций	Федулович	1972	г. Свиньин
...	...	...	...	...	...

Таблица 2.3

Номер свидетельства	Код_М	Фамилия жены	Имя жены	Дата регистрации	...
1-ЮБ 154745	111	Курочкина	Августина	06/03/1991	...
1-ЮБ 163489	111	Пеструшкина	Мариана	11/08/1991	...
1-ЮБ 169877	111	Рябова	Милана	12/12/1992	...
1-ЮБ 169878	112	Уточкина	Вероника	12/12/1992	...
1-ЮБ 154746	113	Свинюшкина	Эльвира	06/03/1991	...
1_ЮБ 169879	113	Хаврония	Руфина	12/12/1992	...
...	...	...	...	...	...

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

Сотрудники (Табельный_номер, Фамилия, Имя, ...).

Использование, рассмотренной в примере 2.2, сущности "Брак" нецелесообразно: в "Сотрудники" уже есть фамилии, имена, отчества супругов. Поэтому создадим ассоциацию

Брак [Сотрудник 1, Сотрудник 1]

(Табельный_номер_мужа, Табельный_номер_жены, ...),

связывающую между собой определенные экземпляры сущности "Сотрудники" (рис. 2.2,г).

Таким образом, при разработке ER-моделей мы должны получитьследующую информацию о предметной области:

1) Список сущностей предметной области;

2) Список атрибутов сущностей;

3) Описание взаимосвязей между сущностями.

В заключение отметим, что ER-диаграмма рис. 2.1,а описывает структуру размещения данных о браках в отделах ЗАГС стран, допускающих групповые браки, а ER-диаграммы примера 2.2, описания любых видов браков в организациях, где есть сущности "мужчины" и "женщины", включающие холостых и незамужних.

Что же такое "связь"? В ER-диаграммах это линия, соединяющая геометрические фигуры, изображающие сущности, атрибуты, ассоциации и другие информационные объекты. В тексте же этот термин используется для указания на взаимозависимость сущностей. Если эта взаимозависимость имеет атрибуты, то она называется ассоциацией.

2.3 Классификация сущностей

К. Дейт определяет три основные класса сущностей: стержневые, ассоциативные и характеристические, а также подкласс ассоциативных сущностей - обозначения.

Стержневая сущность (стержень) - это независимая сущность (несколько подробнее она будет определена ниже).

В рассмотренных ранее примерах стержни - это "Студент", "Квартира", "Мужчины", "Врач", "Брак" (из примера 2.2) и другие, названия которых помещены в прямоугольники.

Ассоциативная сущность (ассоциация) - это связь вида "многие-ко-многим" ("-ко-многим" и т.д.) между двумя или более сущностями или экземплярами сущности (как в примере 2.4). Ассоциации рассматриваются как полноправные сущности:

- они могут участвовать в других ассоциациях и обозначениях точно так же, как стержневые сущности;

- могут обладать свойствами, т.е. иметь не только набор ключевых атрибутов, необходимых для указания связей, но и любое число других атрибутов, характеризующих связь. Например, ассоциации "Брак" из примеров 2.1 и 2.4 содержат ключевые атрибуты "Код_М", "Код_Ж" и "Табельный номер мужа", "Табельный номер жены", а также уточняющие атрибуты "Номер свидетельства", "Дата регистрации", "Место_регистрации", "Номер записи в книгу ЗАГС" и т.д.

Характеристическая сущность (характеристика) - это связь вида "многие-к-одной" или "одна-к-одной" между двумя сущностями (частный случай ассоциации). Единственная цель характеристики в рамках рассматриваемой предметной области состоит в описании или уточнении некоторой другой сущности. Необходимость в них возникает в связи с тем, что сущности реального мира имеют иногда многозначные свойства. Муж может иметь несколько жен (пример 2.3), книга - несколько характеристик переиздания (исправленное, дополненное, переработанное, ...) и т.д.

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

Для описания характеристики используется новое предложение ЯИМ, имеющее в общем случае вид:

Характеристика (атрибут 1, атрибут 2, ...)

{Список характеризуемых сущностей}.

Расширим также язык ER-диаграмм, введя для изображения характеристики трапецию (рис. 2.3).

Рис. 2.3. Элементы расширенного языка ER-диаграмм

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

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

При отсутствии жестких правил (сотрудник может одновременно зачисляться в несколько отделов или не зачисляться ни в один отдел) необходимо создать описание с ассоциацией Зачисление:

Отделы (Номер отдела, Название отдела, ...)

Служащие (Табельный номер, Фамилия, ...)

Зачисление [Отделы M, Служащие N]

(Номер отдела, Табельный номер, Дата зачисления).

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

Отделы (Номер отдела, Название отдела, ...)

Служащие (Табельный номер, Фамилия, ... , Номер отдела,

Дата зачисления)[Отделы]

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

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

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

Обозначение (атрибут 1, атрибут 2, ...)[Список обозначаемых сущностей].

Как правило, обозначения не рассматриваются как полноправные сущности, хотя это не привело бы к какой-либо ошибке.

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

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

2.4 О первичных и внешних ключах

Напомним, что ключ или возможный ключ - это минимальный набор атрибутов, по значениям которых можно однозначно найти требуемый экземпляр сущности. Минимальность означает, что исключение из набора любого атрибута не позволяет идентифицировать сущность по оставшимся. Каждая сущность обладает хотя бы одним возможным ключом. Один из них принимается за первичный ключ. При выборе первичного ключа следует отдавать предпочтение несоставным ключам или ключам, составленным из минимального числа атрибутов. Нецелесообразно также использовать ключи с длинными текстовыми значениями (предпочтительнее использовать целочисленные атрибуты). Так, для идентификации студента можно использовать либо уникальный номер зачетной книжки, либо набор из фамилии, имени, отчества, номера группы и может быть дополнительных атрибутов, так как не исключено появление в группе двух студентов с одинаковыми фамилиями, именами и отчествами.

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

Теперь о внешних ключах:

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

Если сущность В обозначает сущность А, то она должна включать внешний ключ, соответствующий первичному ключу сущности А.

В п. 2.3 рассматривался пример, где "Служащие" обозначали "Отделы" и включали внешний ключ "Номер отдела", соответствующий первичному ключу сущности "Отделы".

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

Рис. 2.6. Структуры: а - ассоциации; б - обозначения (характеристики)

Здесь для обозначения любой из ассоциируемых сущностей (стержней, характеристик, обозначений или даже ассоциаций) используется новый обобщающий термин "Цель" или "Целевая сущность".

Таким образом, при рассмотрении проблемы выбора способа представления ассоциаций и обозначений в базе данных основной вопрос, на который следует получить ответ: "Каковы внешние ключи?". И далее, для каждого внешнего ключа необходимо решить три вопроса:

1. Может ли данный внешний ключ принимать неопределенные значения (NULL-значения)? Иначе говоря, может ли существовать некоторый экземпляр сущности данного типа, для которого неизвестна целевая сущность, указываемая внешним ключом? В случае поставок это, вероятно, невозможно - поставка, осуществляемая неизвестным поставщиком, или поставка неизвестного продукта не имеют смысла. Но в случае с сотрудниками такая ситуация однако могла бы иметь смысл - вполне возможно, что какой-либо сотрудник в данный момент не зачислен вообще ни в какой отдел. Заметим, что ответ на данный вопрос не зависит от прихоти проектировщика базы данных, а определяется фактическим образом действий, принятым в той части реального мира, которая должна быть представлена в рассматриваемой базе данных. Подобные замечания имеют отношение и к вопросам, обсуждаемым ниже.

2. Что должно случиться при попытке Удаления целевой сущности, на которую ссылается внешний ключ? Например, при удалении поставщика, который осуществил по крайней мере одну поставку. Существует три возможности:

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

3. Что должно происходить при попытке Обновления первичного ключа целевой сущности, на которую ссылается некоторый внешний ключ? Например, может быть предпринята попытка обновить номер такого поставщика, для которого имеется по крайней мере одна соответствующая поставка. Этот случай для определенности снова рассмотрим подробнее. Имеются те же три возможности, как и при удалении:

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

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

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

NULL-значения не допустимы

Удаление из (цель) каскадируется

Обновление (первичный ключ цели) Каскадируется

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

2.5 Ограничения целостности

Целостность (от англ. integrity - нетронутость, неприкосновенность, сохранность, целостность) - понимается как правильность данных в любой момент времени. Но эта цель может быть достигнута лишь в определенных пределах: СУБД не может контролировать правильность каждого отдельного значения, вводимого в базу данных (хотя каждое значение можно проверить на правдоподобность). Например, нельзя обнаружить, что вводимое значение 5 (представляющее номер дня недели) в действительности должно быть равно 3. С другой стороны, значение 9 явно будет ошибочным и СУБД должна его отвергнуть. Однако для этого ей следует сообщить, что номера дней недели должны принадлежать набору (1,2,3,4,5,6,7).

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

Выделяют три группы правил целостности:

1. Целостность по сущностям.

2. Целостность по ссылкам.

3. Целостность, определяемая пользователем.

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

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

2. Значение внешнего ключа должно либо:

1. быть равным значению первичного ключа цели;

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

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

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

диапазон значений (экзаменационная оценка от 2 до 5),

принадлежность набору значений (пол "М" или "Ж").

Лекция 3. Ранние подходы к организации БД. Иерархические и сетевые СУБД.

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

Заметим, что в этой лекции мы ограничиваемся рассмотрением только общих подходов к организации трех типов ранних систем, а именно, систем, основанных на инвертированных списках, иерархических и сетевых систем управления базами данных. Мы не будем касаться особенностей каких-либо конкретных систем; это привело бы к изложению многих технических деталей, которые, хотя и интересны, находятся несколько в стороне от основной цели нашего курса. Детали можно найти в рекомендованной литературе.

Начнем с некоторых наиболее общих характеристик ранних систем:

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

b. Все ранние системы не основывались на каких-либо абстрактных моделях. Как мы упоминали, понятие модели данных фактически вошло в обиход специалистов в области БД только вместе с реляционным подходом. Абстрактные представления ранних систем появились позже на основе анализа и выявления общих признаков у различных конкретных систем.

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

d. Можно считать, что уровень средств ранних СУБД соотносится с уровнем файловых систем примерно так же, как уровень языка Кобол соотносится с уровнем языка Ассемблера. Заметим, что при таком взгляде уровень реляционных систем соответствует уровню языков Ада или APL.

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

f. После появления реляционных систем большинство ранних систем было оснащено "реляционными" интерфейсами. Однако в большинстве случаев это не сделало их по-настоящему реляционными системами, поскольку оставалась возможность манипулировать данными в естественном для них режиме.

3.1 Иерархические системы

Типичным представителем (наиболее известным и распространенным) является Information Management System (IMS) фирмы IBM. Первая версия появилась в 1968 г. До сих пор поддерживается много баз данных, что создает существенные проблемы с переходом как на новую технологию БД, так и на новую технику.

3.1.1 Иерархические структуры данных

Иерархическая БД состоит из упорядоченного набора деревьев; более точно, из упорядоченного набора нескольких экземпляров одного типа дерева.

Тип дерева состоит из одного "корневого" типа записи и упорядоченного набора из нуля или более типов поддеревьев (каждое из которых является некоторым типом дерева). Тип дерева в целом представляет собой иерархически организованный набор типов записи.

Пример типа дерева (схемы иерархической БД):

Рис. 3.1

Здесь Отдел является предком для Начальник и Сотрудники, а Начальник и Сотрудники - потомки Отдел. Между типами записи поддерживаются связи.

База данных с такой схемой могла бы выглядеть следующим образом (мы показываем один экземпляр дерева):

Рис. 3.2

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

В IMS использовалась оригинальная и нестандартная терминология: "сегмент" вместо "запись", а под "записью БД" понималось все дерево сегментов.

3.1.2 Манипулирование данными

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

Найти указанное дерево БД (например, отдел 310);

Перейти от одного дерева к другому;

Перейти от одной записи к другой внутри дерева (например, от отдела - к первому сотруднику);

Перейти от одной записи к другой в порядке обхода иерархии;

Вставить новую запись в указанную позицию;

Удалить текущую запись.

3.1.3 Ограничения целостности

Автоматически поддерживается целостность ссылок между предками и потомками. Основное правило: никакой потомок не может существовать без своего родителя. Заметим, что аналогичное поддержание целостности по ссылкам между записями, не входящими в одну иерархию, не поддерживается (примером такой "внешней" ссылки может быть содержимое поля Каф_Номер в экземпляре типа записи Куратор).

Рис. 3.3

В иерархических системах поддерживалась некоторая форма представлений БД на основе ограничения иерархии. Примером представления приведенной выше БД может быть иерархия рис. 3.3

3.2 Сетевые системы

Типичным представителем является Integrated Database Management System (IDMS) компании Cullinet Software, Inc., предназначенная для использования на машинах основного класса фирмы IBM под управлением большинства операционных систем. Архитектура системы основана на предложениях Data Base Task Group (DBTG) Комитета по языкам программирования Conference on Data Systems Languages (CODASYL), организации, ответственной за определение языка программирования Кобол. Отчет DBTG был опубликован в 1971 г., а в 70-х годах появилось несколько систем, среди которых IDMS.

3.2.1 Сетевые структуры данных

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

Сетевая БД состоит из набора записей и набора связей между этими записями, а если говорить более точно, из набора экземпляров каждого типа из заданного в схеме БД набора типов записи и набора экземпляров каждого типа из заданного набора типов связи.

Тип связи определяется для двух типов записи: предка и потомка. Экземпляр типа связи состоит из одного экземпляра типа записи предка и упорядоченного набора экземпляров типа записи потомка. Для данного типа связи L с типом записи предка P и типом записи потомка C должны выполняться следующие два условия:

Каждый экземпляр типа P является предком только в одном экземпляре L;

Каждый экземпляр C является потомком не более, чем в одном экземпляре L.

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

a. Тип записи потомка в одном типе связи L1 может быть типом записи предка в другом типе связи L2 (как в иерархии).

b. Данный тип записи P может быть типом записи предка в любом числе типов связи.

c. Данный тип записи P может быть типом записи потомка в любом числе типов связи.

d. Может существовать любое число типов связи с одним и тем же типом записи предка и одним и тем же типом записи потомка; и если L1 и L2 - два типа связи с одним и тем же типом записи предка P и одним и тем же типом записи потомка C, то правила, по которым образуется родство, в разных связях могут различаться.

e. Типы записи X и Y могут быть предком и потомком в одной связи и потомком и предком - в другой.

f. Предок и потомок могут быть одного типа записи.

Простой пример сетевой схемы БД:

Рис. 3.3

3.2.2 Манипулирование данными

Примерный набор операций может быть следующим:

Найти конкретную запись в наборе однотипных записей (инженера Сидорова);

Перейти от предка к первому потомку по некоторой связи (к первому сотруднику отдела 310);

Перейти к следующему потомку в некоторой связи (от Сидорова к Иванову);

Перейти от потомка к предку по некоторой связи (найти отдел Сидорова);

Создать новую запись;

Уничтожить запись;

Модифицировать запись;

Включить в связь;

Исключить из связи;

Переставить в другую связь и т.д.

3.2.3 Ограничения целостности

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

3.3 Достоинства и недостатки

Сильные места ранних СУБД:

Развитые средства управления данными во внешней памяти на низком уровне;

Возможность построения вручную эффективных прикладных систем;

Возможность экономии памяти за счет разделения подобъектов (в сетевых системах).

Недостатки:

Слишком сложно пользоваться;

Фактически необходимы знания о физической организации;

Прикладные системы зависят от этой организации;

Их логика перегружена деталями организации доступа к БД.

Лекция 4. Реляционная структура данных. Общие понятия реляционного подхода к организации БД. Основные концепции и термины

4.1 Базовые понятия реляционных баз данных

В конце 60-х годов появились работы, в которых обсуждались возможности применения различных табличных даталогических моделей данных, т.е. возможности использования привычных и естественных способов представления данных. Наиболее значительной из них была статья сотрудника фирмы IBM д-ра Э.Кодда (Codd E.F., A Relational Model of Data for Large Shared Data Banks. CACM 13: 6, June 1970), где, вероятно, впервые был применен термин "реляционная модель данных".

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

Наименьшая единица данных реляционной модели - это отдельное атомарное (неразложимое) для данной модели значение данных. Так, в одной предметной области фамилия, имя и отчество могут рассматриваться как единое значение, а в другой - как три различных значения.

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

Для начала покажем смысл этих понятий на примере отношения сотрудники, содержащего информацию о сотрудниках некоторой организации:



Рис. 4.1

4.1.1 Тип данных

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

4.1.2 Домен

Доменом называется множество атомарных значений одного и того же типа.

Понятие домена более специфично для баз данных, хотя и имеет некоторые аналогии с подтипами в некоторых языках программирования. В самом общем виде домен определяется заданием некоторого базового типа данных, к которому относятся элементы домена, и произвольного логического выражения, применяемого к элементу типа данных. Если вычисление этого логического выражения дает результат "истина", то элемент данных является элементом домена.

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

Смысл доменов состоит в следующем: данные считаются сравнимыми только в том случае, когда они относятся к одному домену. В нашем примере значения доменов "Номера пропусков" и "Номера групп" относятся к типу целых чисел, но не являются сравнимыми. Заметим, что в большинстве реляционных СУБД понятие домена не используется, хотя в Oracle V.7 оно уже поддерживается.

4.1.3 Схема отношения, схема базы данных

Схема отношения - это именованное множество пар {имя атрибута, имя домена (или типа, если понятие домена не поддерживается)}.

Степень отношения - это число его атрибутов. Отношение степени один называют унарным, степени два - бинарным, степени три - тернарным, ..., а степени n - n-арным. Степень отношения СОТРУДНИКИ равна четырем, то есть оно является 4-арным. Если все атрибуты одного отношения определены на разных доменах, осмысленно использовать для именования атрибутов имена соответствующих доменов (не забывая, конечно, о том, что это является всего лишь удобным способом именования и не устраняет различия между понятиями домена и атрибута).

Схема БД (в структурном смысле) - это набор именованных схем отношений.

4.1.4 Кортеж, отношение

Кортеж, соответствующий данной схеме отношения, - это множество пар {имя атрибута, значение}, которое содержит одно вхождение каждого имени атрибута, принадлежащего схеме отношения. "Значение" является допустимым значением домена данного атрибута (или типа данных, если понятие домена не поддерживается). Тем самым, степень или "арность" кортежа, т.е. число элементов в нем, совпадает с "арностью" соответствующей схемы отношения. Попросту говоря, кортеж - это набор именованных значений заданного типа.

Отношение - это множество кортежей, соответствующих одной схеме отношения.

Кардинальное число или мощность отношения - это число его кортежей. Кардинальное число отношения изменяется во времени в отличие от его степени.

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

Рис. 4.2

Отношение на доменах D1, D2, ..., Dn (не обязательно, чтобы все они были различны) состоит из заголовка и тела.

Заголовок состоит из такого фиксированного множества атрибутов A1, A2, ..., An, что существует взаимно однозначное соответствие между этими атрибутами Ai и определяющими их доменами Di (i=1,2,...,n).

Тело состоит из меняющегося во времени множества кортежей, где каждый кортеж состоит в свою очередь из множества пар атрибут-значение (Ai:Vi), (i=1,2,...,n), по одной такой паре для каждого атрибута Ai в заголовке. Для любой заданной пары атрибут-значение (Ai:Vi) Vi является значением из единственного домена Di, который связан с атрибутом Ai.

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

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

Однако в реляционных базах данных это не принято. Имя схемы отношения в таких базах данных всегда совпадает с именем соответствующего отношения-экземпляра. В классических реляционных базах данных после определения схемы базы данных изменяются только отношения-экземпляры. В них могут появляться новые и удаляться или модифицироваться существующие кортежи. Однако во многих реализациях допускается и изменение схемы базы данных: определение новых и изменение существующих схем отношения. Это принято называть эволюцией схемы базы данных.

Реляционная база данных - это набор отношений, имена которых совпадают с именами схем отношений в схеме БД.

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

Отношение - Таблица (иногда Файл),

Кортеж - Строка (иногда Запись),

Атрибут - Столбец, Поле.

При этом принимается, что "запись" означает "экземпляр записи", а "поле" означает "имя и тип поля".

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

4.2 Фундаментальные свойства отношений

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

4.2.1 Отсутствие кортежей-дубликатов

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

Из этого свойства вытекает наличие у каждого отношения так называемого первичного ключа - набора атрибутов, значения которых однозначно определяют кортеж отношения.

Пусть R - отношение с атрибутами A1, A2, ..., An. Говорят, что множество атрибутов K=(Ai, Aj, ..., Ak) отношения R является возможным ключом R тогда и только тогда, когда удовлетворяются два независимых от времени условия:

1. Уникальность: в произвольный заданный момент времени никакие два различных кортежа R не имеют одного и того же значения для Ai, Aj, ..., Ak.

2. Минимальность: ни один из атрибутов Ai, Aj, ..., Ak не может быть исключен из K без нарушения уникальности.

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

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

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

4.2.2 Отсутствие упорядоченности кортежей

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

4.2.3 Отсутствие упорядоченности атрибутов

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