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

Иерархические модели

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Сетевые модели

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Недостатки:

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

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

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

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

РЕЛЯЦИОННАЯ МОДЕЛЬ ДАННЫХ

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

Базовые понятия

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

Для начала покажем смысл этих понятий на примере отношения СОТРУДНИКИ, содержащего информацию о сотрудниках некоторой организации:

Тип данных

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

Домен

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

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

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

Кортеж, отношение-экземпляр

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

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

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

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

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

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

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

Иерархические модели

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

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

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

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

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

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

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

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

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

Сетевые модели

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Недостатки:

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

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

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

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

РЕЛЯЦИОННАЯ МОДЕЛЬ ДАННЫХ

Базовые понятия

Тип данных

Домен

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

Схема отношения R – это именованное множество пар (имя атрибута, имя домена):

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

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

Схемы двух отношений S_R и S_Q называют эквивалентными (S_R ~ S_Q), если:

- степени отношений R и Q одинаковы;

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

Схема БД – это набор именованных схем отношений.

Кортеж, отношение-экземпляр

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