Курсовая работа: Реляционная модель данных. Реляционные базы данных Какая модель данных называется реляционной

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

На реляционной модели данных строятся реляционные базы данных .

Реляционная модель данных включает следующие компоненты:

• Структурный аспект (составляющая) - данные в базе данных представляют собой набор отношений .
• Аспект (составляющая) целостности - отношения (таблицы) отвечают определенным условиям целостности . РМД поддерживает декларативные ограничения целостности уровня домена (типа данных), уровня отношения и уровня базы данных.
• Аспект (составляющая) обработки (манипулирования) - РМД поддерживает операторы манипулирования отношениями (реляционная алгебра , реляционное исчисление).

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

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

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

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

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

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

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

3) однозначные и многозначные. Атрибуты могут иметь соответственно одно или много значений для каждого экземпляра сущности;

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

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

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

Схема отношения (заголовок отношения) представляет собой список имен атрибутов с указанием имен доменов.

Кортеж, соответствующий данной схеме отношения, представляет собой множество пар (имя атрибута, значение}, которое содержит одно вхождение каждого имени атрибута. Аргумент “значение” является допустимым значением домена данного атрибута.

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

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

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

Внешний ключ – это набор атрибутов одного отношения, являющийся возможным ключом другого отношения.

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

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

Реляционная модель данных (РМД) была разработана сотрудником IBM Э.Ф. Коддом (Edgar Frank Codd) еще в 1969-1970 гг. на основе математической теории отношений . В настоящее время это наиболее распространенная модель данных, используемая коммерческими СУБД.

Реляционная модель данных имеет свои достоинства и недостатки. К достоинствам модели можно отнести следующее:

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

Недостатками модели являются:

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

Как и любая другая, реляционная модель данных определяет структурную и целостную части. Лежащий в основе РМД математический аппарат позволил определить и манипуляционную часть. Соответственно, для описания структуры и ограничений, накладываемых на структуру, используется язык описания данных (ЯОД); для манипуляций с данными используется язык манипулирования данными (ЯМД).

Особенности реляционной модели данных, отличающие ее от моделей «сущность-связь»:

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

БАЗОВЫЕ СТРУКТУРНЫЕ КОМПОНЕНТЫ РЕЛЯЦИОННОЙ МОДЕЛИ ДАННЫХ

Базовыми структурными компонентами РМД являются:

• домены и атрибуты;
• отношения;
• связи.

Домены, атрибуты и отношения

Определение.Домен - множество элементов одного типа.

Э.Ф. Кодд определил простой домен, элементы которого имеют простые (атомарные) значения, и составной домен, элементы которого представляют собой отношения, построенные на простых доменах.

Примеры простых доменов:

ГОД = {1985, 2003, 2000};

ДЕНЬГИ = {500, 1000,850}.

Пример составного домена, построенного на простых доменах ГОД и ДЕНЬГИ:

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

Отношение реляционной модели определяется в соответствии с его определением в теории множеств.

Определение. Пусть дана совокупность множеств О р Э 2 , ..., Э п, не обязательно различных. Тогда отношение К, определенное на этих множествах, есть множество упорядоченных кортежей, таких, что

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

Пример: даны два домена Э, = {а, Ь, с} и Э 2 = {1,2}. Отношением, построенным на данных доменах, может быть = {, }. Другое отношение, построенное на этих же доменах: Я 2 = {, }.

Свойства отношения:

• кортежи отношения не упорядочены;
• домены внутри кортежей упорядочены.

Определение. Атрибуты задают способ использования домена внутри отношения.

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

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

Схема отношения представляет собой интенсионал отношения.

Рассмотрим пример. Пусть даны два домена: ЧИСЛО и СТРОКА. В отношении ОТДЕЛ домен ЧИСЛО используется для задания номера отдела - вводим атрибут Номер отдела, а домен СТРОКА используется для задания названия отдела - атрибут Название. Тогда отношению ОТДЕЛ соответствует следующая схема отношения:

ОТДЕЛ {Номер отдела: ЧИСЛО, Название: СТРОКА).

В общем случае, как упоминалось выше, может существовать составной домен. В соответствии со своим определением составной домен представляет собой отношение, построенное также на простых доменах. Но в таком отношении не появляются атрибуты. Вернемся к домену ИСТОРИЯ ЗАРПЛАТЫ. Он построен на простых доменах ГОД и ДЕНЬГИ и может быть задан следующим образом:

ИСТОРИЯ ЗАРПЛАТЫ (ГОД, ДЕНЬГИ).

В задании схемы отношения могут использоваться и составные домены. Рассмотрим отношение СОТРУДНИК. Его атрибутами могут быть Номер сотрудника (определен на домене ЧИСЛО), Имя (на домене СТРОКА) и Зарплата , определенный на домене ИСТОРИЯ ЗАРПЛАТЫ:

СОТРУДНИК {Номер сотрудника: ЧИСЛО, Имя: СТРОКА, Зарплата: ИСТОРИЯ ЗАРПЛАТЫ).

Конкретная реализация (экстенсионал) данного отношения может иметь вид, представленный на рис. 5.1.

Рис. 5.1. Пример представления отношения СОТРУДНИК

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

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

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

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

Рис. 5.2. Нормализованное отношение СОТРУДНИК

Свойства отношения реляционной модели данных.

• 1. Каждый атрибут отношения имеет уникальное в данном отношении имя.
• 2. Каждый атрибут определен на каком-то одном домене.
• 3. На одном и том же домене может быть определено несколько атрибутов.
• 4. Имя атрибута может совпадать с именем домена.
• 5. Порядок следования атрибутов не устанавливается (атрибуты в определении схемы отношения не упорядочены).
• 6. В отношении нет совпадающих кортежей (каждый кортеж уникален).
• 7. Порядок следования кортежей не устанавливается (кортежи в отношении не упорядочены).
• 8. Отношение имеет имя, которое в схеме базы данных отличается от имен всех других отношений.

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

ОТДЕЛ (Номер отдела , Название).

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

Представление сущности

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

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

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

Определение. Первичный ключ (РК - Primary Key) - неизбыточный набор атрибутов, значения которых однозначно определяют кортеж отношения.

Первичный ключ неизбыточен, если:

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

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

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

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

КАФЕДРА (Номер кафедры , Название)

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

В схеме отношения первичный ключ будем подчеркивать, а после альтернативных ключей добавлять аббревиатуру АК:

КАФЕДРА (Номер кафедры. Название (АК)).

Связи

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

Определение. Внешний ключ (FK - Foreign Key) - это атрибут или некоторое множество атрибутов отношения R1, которые не являются собственными атрибутами отношения R1, но их значение совпадает со значениями первичного ключа некоторого отношения R2 (возможность идентичности R1 и R2 не исключается).

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

Основными типами связей между сущностями являются связи 1:п и п:п. Рассмотрим представление этих связей. Начнем со связи типа 1:п.

Рассмотрим следующие отношения:

• СОТРУДНИК с атрибутами Номер сотрудника (первичный ключ), Имя и Год рождения ;
• ОТДЕЛ с атрибутами Номер отдела (первичный ключ) и Название.

Между этими отношениями определена связь типа 1:п - каждый сотрудник работает в одном определенном отделе, и в каждом отделе работают много сотрудников. На рис. 5.3 приведена соответствующая диаграмма «сущность-связь» в нотации, предложенной П. Ченом.

Эта связь определяется атрибутом внешнего ключа в отношении СОТРУДНИК: в это отношение включается внешний ключ Номер отдела , значения которого совпадают со значениями первичного ключа Номер отдела отношения ОТДЕЛ. В схеме отношения атрибуты внешнего ключа будем помечать аббревиатурой FK. Схемы отношений будут выглядеть следующим образом:

ОТДЕЛ (Номер отдела. Название (АК));

СОТРУДНИК (Номер сотрудника. Имя , Год рождения,

Номер отдела (FK)).

Рис. 5.3. Представление связи типа 1: п в диаграмме П. Чена

Реализации, удовлетворяющие этим схемам отношений, приведены на рис. 5.4.

Рис. 5.4. Пример представления связи типа 1: п в РМД

В данном примере в отношении СОТРУДНИК может появиться кортеж, но не может появиться кортеж, так как в этом кортеже значению «5» внешнего ключа отношения СОТРУДНИК не соответствует никакое значение первичного ключа отношения ОТДЕЛ.

Таким образом, связи типа 1:п никак специально не представляются, только в отношении на стороне «много» появляются атрибуты внешнего ключа.

Следует отметить, что нотация IDEFlx полностью соответствует представлению связи в РМД (рис. 5.5).

Отдел / Е1 Сотрудник / Е2

Рис. 5.5. Представление связи типа 1: п в нотации IDEF1 х

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

Рис. 5.6. Представление связи типа п: п в диаграмме П. Чена

В этом случае в РМД связь ПОСТАВКА (ПОСТАВЩИК, ДЕТАЛЬ) представляется собственным отношением, в котором будут атрибуты внешних ключей, ссылающиеся на отношения ПОСТАВЩИК и ДЕТАЛЬ. Эти атрибуты могут войти в состав первичного ключа отношения связи. Кроме того, отношение связи может иметь собственный атрибут. Схемы отношений будут выглядеть следующим образом:

ПОСТАВЩИК (Номер поставщика. Имя, Адрес)",

ДЕТАЛЬ (Номер детали. Название, Цена)",

ПОСТАВКА (Номер поставщика (ЬКИ. Номер детали (ЬК2).

Количество).

Пример реализации этих отношений приведен на рис. 5.7.

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

Рис. 5.7. Пример представления связи типа п: п в РМД

Деталь /Е2

Постащик/Е1

Поставляет/_

поставляется

а) неопределенная связь

Поставщик / Е1

Деталь /Е2

выполняет

Номер детали (ЕК2)

Количество

• -участвует в- 1
• б) преобразование в определенную связь

Рис. 5.8. Преобразование связи типа п:п в связьтипа 1: п в нотации ЮЕР1х

ЦЕЛОСТНАЯ ЧАСТЬ РЕЛЯЦИОННОЙ МОДЕЛИ ДАННЫХ

Реляционная модель данных определяет два базовых требования целостности, которые поддерживаются любой реляционной СУБД:

• требование целостности сущностей;
• требование целостности по ссылкам, или ссылочной целостности.

Целостность сущностей

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

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

Кроме этого, могут быть установлены и следующие ограничения:

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

Ссылочная целостность

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

ОТДЕЛ (Номер отдела. Название (АК));

СОТРУДНИК (Номер сотрудника. Имя , Год рождения ,

Номер отдела (ЕК)).

Атрибут внешнего ключа Номер отдела в отношении СОТРУДНИК позволяет получить полную информацию о том конкретном отделе, в котором работает конкретный сотрудник.

Обычно отношение, в котором определяется внешний ключ, называется дочерним отношением, а отношение, на которое ссылается внешний ключ, - родительским отношением. Так, в нашем примере отношение СОТРУДНИК - дочернее, а отношение ОТДЕЛ - родительское.

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

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

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

Родительское отношение Дочернее отношение

• - вставка - вставка
• - удаление - удаление
• - модификация РК - модификация РК

Рис. 5.9. Операции модификации родительского и дочернего отношений

Рассмотрим особенности выполнения этих операций.

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

МАНИПУЛЯЦИОННАЯ ЧАСТЬ РЕЛЯЦИОННОЙ МОДЕЛИ ДАННЫХ

Общая характеристика

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

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

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

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

Из приведенного определения следует:

• языки реляционной алгебры показывают, как получить результат;
• языки реляционного исчисления показывают, что должно быть получено.

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

Таким образом, подводя итог сказанному выше, можно определить три вида языков запросов:

• языки реляционной алгебры;
• языки реляционного исчисления с переменными - кортежами;
• языки реляционного исчисления с переменными на доменах.

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

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

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

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

Реляционная алгебра. Общая характеристика

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

Я опц И. дает И..

Э.Ф. Кодд определил минимальный набор операций над отношениями; все операции, входящие в этот набор, можно разбить на две группы.

• 1. Теоретико-множественные операции - традиционные операции над множествами, определяемые теорией множеств; к ним относятся:
  • объединение;
  • вычитание;
  • пересечение;
• 2. Специальные реляционные операции; к ним относятся:
  • выбор (селекция);
  • проекция;
  • соединение;
  • деление.

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

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

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

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

К, опц ] Я 2 опц 2 ...

• 2. Используя термин отношение, следует помнить, что на самом деле мы имеем дело с двумя понятиями:
  • схема отношения (интенсионал);
  • экземпляр (реализация) отношения (экстенсионал).

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

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

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

Рассмотрим пример. Пусть имеется отношение со схемой 8(А, В, С) и некоторой реализацией:

Можно использовать, например, следующую операцию переименования:

Б: переименовать С в 8С.

В результате получим отношение со следующей схемой 81 (А, В, 8С) и той же реализацией:

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

Теоретико-множественные операции

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

• объединение;
• вычитание;
• пересечение;
• прямое (декартово) произведение.

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

Рассмотрим это отличие на примере операции объединения. Операция объединения в теории множеств определяется следующим образом.

Определение. Даны два множества - 81 и 82. Объединением этих множеств является множество 8, элементы которого принадлежат первому множеству 81 и (или) второму множеству 82:

8 = 81и82 = {5|5е 81 и/или бе 82}.

Графически это можно представить так (рис. 5.10).

множество 1

множество 2

объединение множеств

Рис. 5.10. Объединение множеств

В реляционной модели данных рассматривается объединение множеств - доменов и/или отношений.

Объединение доменов. В реляционной модели данных домен представляет собой множество элементов одного типа. Объединение до

менов должно создать новый домен. Пусть даны следующие домены:

О, = {1, 3, 5, 7, 9}; В 2 = {‘а’, Ъ ‘с’}; О, = {2, 4, 6, 8}. Тогда в теории множеств определено новое множество:

Б = Э, и Э 2 = {1, 3, 5, 7, 9, ‘а’, ‘Ь ‘с’}.

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

С другой стороны, новое множество

0 = 0,и0 3 = {1,3, 5,7,9, 2,4, 6, 8}

содержит элементы одного типа, т.е. является доменом. Следовательно, в данном случае, для данных операндов операция объединения определена.

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

Пусть определены следующие схемы отношений, определенные на приведенных выше доменах:

Реализации данных отношений могут иметь следующий вид: г, = { , }; г2 = { , }; г 3 = { , }.

Тогда в теории множеств определено новое множество: г = г, и г 2 = { , }.

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

г = г,иг 3 = { , }

является отношением, хотя схемы исходных отношений Я, И Я 3 и разные.

В связи с этим в реляционной алгебре рассматривается свойство совместимости по объединению.

Определение. Простые домены считаются совместимыми по объединению , если они состоят из элементов одного типа.

Для приведенных выше примеров домены и несовместимы по объединению, а О, и Э 3 - совместимы по объединению.

Определение. Два отношения считаются совместимыми по объединению, если:

• оба отношения имеют одно и то же множество атрибутов;
• одноименные атрибуты двух отношений определены на совместимых по объединению доменах.

Так, в приведенных выше примерах отношения Я, и Я 3 совместимы по объединению, так как их одноименные атрибуты определены на совместимых по объединению доменах.

Если нужно проверить совместимость по объединению отношений, использующих в своих схемах разные имена атрибутов, тогда в соответствии с семантикой атрибутов можно переименовать их, используя операцию переименования. После этого полученные отношения проверяются на совместимость по объединению. Например, пусть дано еще одно отношение Я 4 (ВрО р В 2:0 3) и надо проверить, совместимо ли по объединению данное отношение с отношением Яр Сначала, используя операцию переименования, получаем новое отношение Я 4 (АрОр А 2:0 3):

Я 4: переименовать В, в А р В 2 в А 2 .

После этого можно проверить отношения Я! и Я 4 на совместимость по объединению. С таким же успехом можно использовать операцию переименования:

Яр переименовать А [ в В р А 2 в В г

Рассмотрим теперь все операции реляционной алгебры. В определении операций и примерах строчными буквами обозначены реализации отношений, прописными - схемы отношений; запись вида г(Я) означает: реализация отношения г, удовлетворяющая схеме Я.

Объединение отношений

Определение. Объединением двух отношений г^Я,) и г 2 (Я 2), совместимых по объединению, называется отношение б = г, и г 2 , для которого:

• а) схема отношения совпадает с И., или Я 2 ;
• б) реализация отношения представляет множество кортежей, принадлежащих реализации г (и (или) г 2 .

Формальная запись:

даны г/К,), г 2 (Я 2), г 1 = ад, г 2 = ад, Я, = Я, Я 2 = Я;

Б = Г и Г 2 = 8 (Я), Б = | ^ ? Г 1 И/ИЛИ V

Свойства операции:

• коммутативна - г 1 и г 2 = г 2 и г.;
• ассоциативна - г ] и (г 2 и г 3) = (г 1 и г 2) и г 3 = г ] и г 2 и г 3 .

Вычитание отношений

Определение. Вычитанием двух отношений гДЯ^ и г 2 (Я 2), совместимых по объединению, называется отношение б = г, - г 2 , для которого:

• б) реализация отношения представляет множество кортежей, принадлежащих реализации г р за исключением тех, которые имеются в г 2 .

Формальная запись:

даны г,(Я,), г 2 (Я 2), г, = ад, г 2 = ад, Я, = Я, Я 2 = Я;

8 = г, - г 2 = 8(Я), Б = I ^ € г, И г.

Свойства операции:

• не коммутативна;
• не ассоциативна.

Пересечение отношений

Определение. Пересечением двух отношений г^И^) и г 2 (11 2), совместимых по объединению, называется отношение б = п г 7 , для которого:

• а) схема отношения совпадает с Я, или Я 2 ;
• б) реализация отношения представляет множество кортежей, содержащихся и в г р и в г 2 .

Формальная запись:

даны г,(К,), г 2 (Я 2), г, = {г и }, г 2 = Я, = Я, Я 2 = Я;

Б = Г! П Г 2 = 8(Я), Б = | ^ ? Г, И ^

Свойства операции:

• коммутативна - г1 п г2 = г2 п г1;
• ассоциативна - г1 п (г2 п гЗ) = (г1 п г2) п гЗ = г1 п г2 п гЗ. Операцию пересечения можно выразить через операцию вычитания:

Г 1 ПГ 2 = Г 1 - (Г 1 _Г 2)-

Декартово произведение отношений

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

Определение. Декартовым произведением двух отношений гДЯ^ и г 2 (Я 2), схемы отношений которых не имеют одноименных атрибутов, т.е. Я 1 п Я 2 = 0, называется отношение б = г ] х г 2 , для которого:

• а) схема отношения определяется сцеплением (объединением) схем Я, и Я 2 ;
• б) реализация отношения представляет множество кортежей, которое получается путем сцепления каждого кортежа из г 1 с каждым кортежем из г 2 .

Формальная запись:

даны г,(Я,), Я,(А р А 2 ,..., А т), г 2 (Я 2), Я 2 (В р В 2 ,..., В п),

Г 1 = и и }, г 2 = {^}, Я,пЯ 2 = 0;

б = г 1 х г 2 = б(Я), Я(А р А 2 , А т, В р В 2 ,..., В п),

в = {и.у.|и.е Гр у.е г 2 }.

Свойства операции:

• коммутативна - г, х г 2 = г 2 х Гр
• ассоциативна - г ] х (г 2 х г 3) = (г! х г 2) х г 3 = ^ х г 2 х г 3 .

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

Специальные операции

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

• проекция;
• выбор (или селекция);
• соединение;
• деление.

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

Проекция

Данная операция является унарной операцией на отношениях, т.е. в этой операции участвует только одно отношение.

Определение. Проекцией отношения г(Л), Л = {А (}, на некоторый список имен атрибутов (подмножество атрибутов) Ь из Л, Ь с Л, называется отношение Б = 71 ь (г), ДЛЯ КОТОРОГО!

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

Формальная запись:

даны г(Л), Л(А, А 2 ,..., А т), г = {};

5(Ь) = 71 ь (г), ЦВр в 2 ,..., в к), В; с Л, б = {

таких, что а = I, если В 1 = А^}.

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

Свойство проекции:

если У с X с Л, то тс у (л: х (г)) = л; у (г).

Данную операцию называют еще ограничением и селекцией. Также является унарной операцией над отношением.

Определение. Выбором из отношения г(Л) по условию Л называется отношение Б = Ор(г), для которого:

• схема отношения совпадает со схемой Л;
• реализация отношения есть множество кортежей из г, удовлетворяющих условию К

Формальная запись: даны г(Л), г= {1;};

Л) = о н (г), б = {и, | и |

Условие (предикат) Я записывается в соответствии со следующими правилами:

• в качестве операндов могут быть указаны атрибуты отношения и/или константы;
• в качестве операций могут быть использованы операции отношения (=, ф и т.д.) и логические операции (л, V, -н).

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

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

Свойства операции:

• коммутативна - а Р1 (Ор 2 (г)) = Ор 2 (а п (г)) = о Р1л Р2 (г);
• дистрибутивна относительно операций у = (п, и, -):

^р(гуз) = Ор(г) уар(5).

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

Соединение

В реляционной алгебре рассматриваются две модификации данной операции: естественное соединение и соединение по условию (или 0-соединение).

Естественное соединение

Определение. Естественным соединением отношений г,(Я,), Я, = ХУ, и г 2 (Я 2), Я 2 = где У - общее подмножество атрибутов из Я, и Я 2 , определенных на одних и тех же доменах, называется отношение б(Я) = г (М г 2 , для которого:

• схема отношения Я = Я, и Я 2 = ХУ7;
• реализация отношения есть множество кортежей {1}, для которых тт^уО) е г 1 и 71у 2 (0 е г 2-

Формальная запись:

даны г^Я^, Я, = ХУ, и г 2 (Я 2), Я 2 =

б(Я) = г, г 2 , Я = Я, и Я 2 = XYZ, э = {I | таких, что 71 ху (1:)

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

Результат операции левого внешнего соединения г, х] г 2 включает результат операции естественного соединения, дополненный и теми кортежами из г, для которых нет соответствующих кортежей из г 7 ; для таких кортежей значения атрибутов, унаследованных от г 7 , устанавливаются как пустые значения.

Результат операции правого внешнего соединения г 1 х г 2 включает результат операции естественного соединения, дополненный и теми кортежами из г 7 , для которых нет соответствующих кортежей из г,; для таких кортежей значения атрибутов, унаследованных от г р устанавливаются как пустые значения.

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

Соединение по условию

Определение. Даны два отношения r^Rj) и r 2 (R 2), для которых в R, и R 2 нет атрибутов с одинаковыми именами, т.е. R, n R 2 = 0. Пусть атрибут А е Rj сравним по условию 0 с атрибутом В e R, (условие 0 определяется так же, как предикат F в операции выбора). Тогда соединением отношений гj(Rj) и r 2 (R 2) по условию 0 называется отношение s(R) = г, г 2 , для которого:

• схема отношения R = R, u R 2:
• реализация отношения есть множество кортежей, полученных сцеплением кортежей из г, и г 2 , удовлетворяющих условию А0В.

Формальная запись:

даны rj(Rj) и r 2 (R 2), R, n R 2 = 0;

s(R) = r t r 2 , R = R, u R 2 , s = {uv | таких, что u e r p v

и v выполняется условие 0}.

Атрибуты А и В могут быть составными, т.е. А = {А р А 2 , ..., А п }, В = {Вр В 2 , ..., В п }.Тогда А0В = [А,0,Вр А 2 0 9 В 2 , ..., A n 0 n BJ. Операции 0j могут быть разными. Например, пусть даны г,(Ар А 2 , АД и г 2 (Вр В 2 , В 3), и все атрибуты определены на числовых доменах. Тогда можно получить соединение по условию:

Если в качестве операции 0 используется операция =, такое соединение по условию называется эквисоединением.

Определение. Даны два отношения гДИ^) и г 2 (11 2), для которых 11 2 с Я! и Я 2 не пусто. Частным отделения отношения г, на отношение г 2 называется отношение 8(Я) = г ] -н г 2 , для которого:

• схема отношения Я = Я, - Я 2 ,
• реализация отношения есть множество кортежей I таких, что для всех и. е г 2 существует V. 6 г 1 такой, что у.(Я 1 - Я 2) = I и у/Я 2) = и.

Формальная запись:

даны г,(Я,), г 2 (Я 2), Я 2 с К, Я 2 ^ 0;

8(Я) = Г 1 -5- Г 2 , Я = Я, - Я 2 , Б = {Е | V и е Г 2 (Ей е г^}.

Другими словами, 8хг 2 е г р

Действительно, кортежи, и есть в отношении Кортеж есть в отношении г р но кортежа нет, поэтому в б нет кортежа.

Можно написать выражение реляционной алгебры, эквивалентное операции деления:

Г! + Г 2 = Л К,-Я, - ,1 К | -Я,«%,-Я 2 Х Г 2> - Г!>-

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

Пусть дана следующая схема базы данных:

• 8(8#, 814, 8С) - ПОСТАВЩИК (Номер поставщика. Имя, Город)", Р(?#, Р1Ч, РС) - ДЕТАЛЬ (Номер детали, Название, Цена)", 8Р(8#, Р#, ОТУ) - ПОСТАВКА (Номер поставщика, Номер детали. Количество).
• 1. Получить имена поставщиков, поставляющих деталь с номером Рр

%^ а Р#=’Р,’(8 М 8Р))‘

2. Получить имена поставщиков, не поставляющих деталь с номером Рр

^Б!^ 8) - ^Б^^Р# =‘РГ^ 8 8Р))-

3. Получить имена поставщиков, поставляющих только деталь с номером Р (:

тс 8Н (а р# =Т1 ,(8 8Р))-л: 8М (а р# ^ Р1 ,(8 М 8Р)).

4. Получить имена поставщиков, поставляющих все детали:

^ 71 р#(р)) 8)-

5.3.5. Реляционное исчисление Общие определения

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

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

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

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

Понятие предиката

Даны некоторые попарно не пересекающиеся произвольные множества Э, ..., Э п, п Е = 0 для любых Ф), и переменные х р

х 2 , ..., х, принимающие значения из соответствующих множеств: ж ^ для любых г

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

Переменные х р х 2 , х п называются предикатными переменными. Множества D p D 2 , ..., D n образуют область интерпретации предиката.

В записи предиката наряду с логическими операциями л, v, смысл и использование которых традиционные используются специальные операции - кванторы: всеобщности V и существования 3. Смысл использования кванторов следующий:

• Vx (f(x)) означает, что для всех значений «х» из области интерпретации формула f(x) имеет значение «истина»;
• Зх (f(x)) означает, что существует по крайней мере одно значение «х» из области интерпретации, для которого формула f(x) имеет значение «истина».

Примеры. Пусть переменная «х» определена на множестве «учебная группа»; f(t) - утверждение «t получает стипендию»; тогда предикат Зх (f(x)) имеет значение «истина», если хотя бы один член группы (неважно, кто именно) получает стипендию, и ложь, если никто в группе не получает стипендию.

Пусть переменная «х» определена на множестве «учебная группа»; f(t) - утверждение «t не имеет задолженностей в сессию»; тогда предикат Vx (f(x)) имеет значение «истина», если все члены группы не имеют задолженностей в сессию, и ложь, если хотя бы один член группы имеет задолженность.

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

Вхождение переменной t в формулу |/связано, если переменная t находится в формуле ц/ в подформуле, начинающейся кванторами V или 3, за которыми непосредственно следует переменная t; тогда о кванторе говорят, что он связывает переменную t. В остальных случаях t ВХОДИТ В 1|/ свободно.

Рассмотрим следующий пример:

• (Vx(R(x,y)v3y(U(x,y,z)AQ(x,y))))v(Vx(3r(U(x,y,r)A(3x(F(x)))).
• 112 3 134 13 56 576 88

В примере пронумеровано использование переменных в связи с их появлением в кванторах и в формуле. В соответствии с этим в первой подформуле все вхождения «х» (помеченные цифрой 1) связаны квантором V; первое вхождение «у» (помеченное цифрой 2) свободно; следующие вхождения «у» (помеченные цифрой 3) связаны квантором 3; вхождение переменной «г» (помеченное цифрой 4) свободно. Во второй подформуле все вхождения переменной «х» (помеченные цифрами 5 и 8) связаны кванторами V и 3 соответственно;

вхождение «у» (помеченное цифрой 7) свободно; и наконец, вхождение переменной г (помеченное цифрой 6) связано квантором 3.

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

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

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

Рассмотрим пример. Пусть дано множество десятичных цифр Э = {О, 1,2, 3, 4, 5, 6, 7, 8, 9}; тогда подмножество, состоящее из четных цифр, можно определить следующим образом: множество всех значений у, таких, для которых выполняется условие:

Зх (х ^ О л х -г- 2 = 0 л у = х).

Приведенный предикат интерпретируется следующим образом: существует хотя бы одно значение «х» е О, которое четно и совпадает со значением некоторой свободной переменной «у». Следовательно, если свободная переменная у имеет конкретное значение, например, 6, приведенный предикат будет иметь значение «истина», и данное значение переменной у входит в результат. Если же переменная «у» будет иметь значение 7 или 12, тогда предикат будет иметь значение «ложь» и данное значение у не войдет в результат.

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

Если Р(а р а 2 ,..., а) = 1, то есть выборка отношения г(А р А 2 ,..., А п),т.е.

Если Р(Ь р Ь 2 ,..., Ь) = 0, то ё г.

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

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

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

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

Реляционное исчисление с переменными-кортежами

Как уже говорилось, в данном случае областью определения переменных являются отношения. Переменные-кортежи должны удовлетворять определенной схеме отношения R. Правильно построенная формула (wff - well formulated formula) определяет результаты отбора: выбираются те кортежи, для которых wff дает значение 1.

Обозначим правильно построенную формулу (предикат, значения которого 0 или 1) через |/(t).

Рассмотрим правила построения (/(t).

I. Основой формулы являются атомы, которые могут иметь значения 0 или 1.

Существует три типа атомов формулы vj/(t).

• 1. Пусть r(R) - некоторая реализация отношения, удовлетворяющая схеме R; t - некоторая переменная-кортеж, удовлетворяющая схеме R. Тогда r(t) - атом; означает, что t есть кортеж в отношении г (т.е. формула истинна, если t е г).
• 2. Пусть r(R) - некоторая реализация отношения, удовлетворяющая схеме R; и и v - переменные-кортежи из отношения r(R) (т.е. u е г, v , >, Ф,
• 3. Пусть и - переменная-кортеж из отношения r(R) (т.е. и е г); 0 - арифметическая операция сравнения (, >, Ф,

В приведенных выше условиях запись и[А] означает «значение переменной-кортежа и по атрибуту А».

II. Формула реляционного исчисления (/(t), а также свободные и связанные вхождения переменных определяются по следующим рекурсивным правилам.

• 1. Каждый атом есть формула. Все вхождения переменных-кортежей, упомянутых в атоме, являются свободными. Например, формула г(0 утверждает, что переменная-кортеж I является кортежем отношения г(Я).
• 2. Если х(И.) - переменная-кортеж из отношения г со схемой Я; |/(х) - формула, в которой переменная «х» имеет свободное вхождение; тогда Зх(Л) (|/(х)) - формула, в которой вхождение переменной «х» становится связанным квантором 3. Данная формула утверждает, что существует хотя бы один кортеж «х» в отношении г(Я), такой, что при подстановке его в формулу {/(х) вместо всех свободных вхождений «х» получим значение «истина». Например, формула Зх(Я) (г(х)) утверждает, что отношение г не пусто (т.е. существует хотя бы один кортеж х, принадлежащий г).
• 3. Если х(И.) - переменная-кортеж из отношения г со схемой Я; |/(х) - формула, в которой переменная «х» имеет свободное вхождение; тогда /х(Я) (ц/(х)) - формула, в которой вхождение переменной «х» становится связанным квантором V. Данная формула утверждает, что для всех кортежей «х» из отношения г(Я) при подстановке их в формулу 1|/(х) вместо всех свободных вхождений «х» получим значение «истина». Например, формула /х(Я) (х[А] Ф 0) утверждает, что для всех кортежей значение атрибута А не пусто, т.е. атрибут А является обязательным.
• 4. Если |/(х) и ф(х) - формулы, тогда -|)/(х), |/(х) л ф(х), ц/(х) V ф(х) - тоже формулы. Вхождения переменной «х» в эти формулы остаются свободными или связанными - такими, какими были в ц/(х) или ф(х) соответственно. Например, если переменная «х» имела в ф(х) свободное вхождение, а в ф(х) - связанное, то в этих функциях сохраняется тип вхождения переменных.
• 5. Если ф(х) - формула, то (ф(х)) - тоже формула; вхождение переменной «х» остается свободным или связанным - таким, каким оно было в ф(х).
• 6. Ничто иное не является формулой.

При вычислении формул используется порядок старшинства операций, определяемый правилами построения формулы:

• а) атомы, в которых могут быть использованы арифметические операции сравнения;
• б) кванторы;
• в) отрицание (-|)
• г) операция «И» (л)
• д) операция «ИЛИ» (V)

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

Определение. Выражение реляционного исчисления с переменными-кортежами имеет вид: {1:(11) 11|/(1:)}, где I - переменная-кортеж, удовлетворяющая схеме отношения Я; единственная переменная, имеющая свободное вхождение в формулу 1|/(1:); ц/Д) - правильно построенная формула.

Интерпретация выражения реляционного исчисления: множество кортежей 1:, удовлетворяющих схеме отношения Я, таких, для которых правильно построенная формула уД) истинна.

Пример. Пусть есть отношение К(Имя, Стипендия ); атрибут Стипендия определен на домене О = {«да», «нет»}. Тогда выражение

{{(Имя) | Зх(Я) (г(х) л х[Стипендия ] = «да» л х[Имя] = {[Имя]}

позволит получить из отношения имена всех студентов, получающих стипендию.

Безопасные выражения

Выражение вида {I | -1 гД)} в общем случае определяет бесконечное отношение, что недопустимо. Поэтому в реляционном исчислении ограничиваются рассмотрением так называемых безопасных выражений вида {I | |/(1:)}, которые гарантированно дают ограниченное множество кортежей. В таких выражениях значения атрибутов кортежей I являются элементами некоторого ограниченного универсального множества - ООМ((/). Здесь ООМ(1|/) - унарное отношение, элементами которого являются символы, которые либо явно появляются в 1|/, либо служат компонентами какого-либо кортежа в некотором отношении Я, упоминаемом В 1|/.

В книге Дж. Ульмана приведено следующее определение: «Выражение {I | |/(1:)} реляционного исчисления с переменными-кортежами назовем безопасным , если выполняются следующие условия:

• 1. Всякий раз, когда I удовлетворяет ц/Д), каждый компонент I есть элемент ООМ()/).
• 2. Для любого подвыражения |/ вида (Зи) (со(и)) каждый компонент и принадлежит ООМ(со), если и удовлетворяет со.
• 3. Если для любого подвыражения |/ вида (/и) (со(и)) каждый компонент и не принадлежит ООМ(со), то и не удовлетворяет со. Условия 2 и 3 позволяют устанавливать истинность квалифицированной формулы (Зи) (со(и)) или (Уи) (со(и)), рассматривая только и, составленные из принадлежащих ООМ(со) символов. Например, любая формула (3 и) (Щи) л...) удовлетворяет условию 2, а любая формула (Уи) (-.Щи) V ...) - условию 3.

Хотя условие 3 может показаться неинтуитивным, мы должны заметить, что формула (Уи) (со(и)) логически эквивалентна формуле -п(Зи) (-|Со(и)). Последняя не является безопасной, если и только если существует некоторое и 0 , ДЛЯ которого ИСТИННО -1СО(и 0) и и 0 не принадлежит домену формулы -нсо(и). Так как домены со и ->со одни и те же, условие 3 устанавливает, что формула (/и) (со(и)) безопасна, когда безопасна формула -ДЗи) (-.со(и))...».

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

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

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

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

В табл. 5.1 приводятся некоторые эквивалентности.

Таблица 5.1

Эквивалентности для реляционной алгебры и реляционного исчисления

с переменными кортежами

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

Дана та же схема базы данных:

• 8(8#. 814, 8С) - ПОСТАВЩИК (Номер поставщика. Имя, Город)", Р(Р#. РЇ4, РС) - ДЕТАЛЬ (Номер детали. Название, Цена)", 8Р(8#. Р#. ОТУ) - ПОСТАВКА (Номер поставщика. Номер детали. Количество).
• 1. Получить имена поставщиков, поставляющих деталь с номером Р1.

{1(814) | Зи(8)Зу(8Р)(8(и) а 8Р(у) а и = у а у[Р#] =

= ‘РГ л и = 1)}.

Пояснение: результат запроса - множество кортежей і, имеющих только один атрибут 814, таких, что:

• - существует, по крайней мере один кортеж из отношения 8 (Зи(8)... (8(и)...) и
• - существует, по крайней мере один кортеж из отношения БР (...Зу(8Р)(... 8Р(у) ...),

такие, что

• - значения этих кортежей по атрибуту Э# совпадают (и),
• - значение кортежа V по атрибуту Р# определяет интересующую нас деталь Р1 (у{Р#{ = ‘РГ) и
• - кортеж и определяет результат запроса (и = 1:).
• 2. Получить имена поставщиков, не поставляющих деталь с номером Р1:

{1(814) | Зи(8)(8(и) л-Зу(8Р) (8Р(у) л у[Р#] = ‘РГ л и =

Ули = 1))}.

То есть для кортежа из отношения 8, определяющего результат запроса, не найдется кортеж из отношения 8Р, имеющий такое же значение по атрибуту 8# и определяющий деталь Р1.

3. Получить имена поставщиков, поставляющих только деталь с номером Р1.

Этот запрос, по сути, объединяет два предыдущих: т.е. определяются кортежи, соответствующие поставляемой детали Р1, и из этих кортежей удаляются те, которые соответствуют поставке других деталей:

{1(814) | Зи(8)Зу(8Р)(8(и) л 8Р(у) л и = у л у[Р#] =

= ‘РГ л и = Ц8Г^] л -.3у(8Р)(8Р(у) л у =

И л у[Р#] Ф ‘РГ))}.

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

{1(8#) | Уш(Р)Зи(8Р)(Р(ш) д 8Р(у) д у[Р#| = у[Р#] д П8#] = у18#])}.

Теперь добавим в этот запрос конструкции, необходимые для получения имени поставщика из отношения 8:

{1(814) | Зи(8)/у(Р)Зи(8Р)(8(и) л Р(у) л 8Р(у) л w =

У[Р#] л и = у л t = u)}.

Реляционное исчисление с переменными на доменах

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

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

I. Атомы имеют следующий вид:

• а) г(х, х 2 ,..., х), где г - отношение, удовлетворяющее схеме R(A p А 2 ,..., А), и каждое х. есть константа или переменная на домене;
• б) и 0 v, где и и v - константы или переменные, определенные на доменах, совместимых по операции 0,0 - арифметическая операция сравнения (, >, Ф,

И. Формула реляционного исчисления j/(t), а также свободные и связанные вхождения переменных определяются так же, как и для исчисления с переменными-кортежами.

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

Выражение исчисления с переменными на доменах, эквивалентное выражению исчисления с переменными-кортежами {t | i|/(t)}, конструируется в соответствии со следующими правилами.

Пусть есть переменная-кортеж t(R), где R = (А р А 2 , ..., А п) имеет арность п. Тогда вместо переменной-кортежа t вводятся п новых переменных на доменах t, t 2 ,..., t , и заданное выражение исчисления с переменными-кортежами заменяется выражением {t, t 2 , ..., t |

• любой атом r(t) заменяется атомом r(t p t 2 ,..., t);
• каждое свободное вхождение t заменено переменной t,;
• для каждого квантора Зи или Vu вводится ш новых переменных и, и 2 , ..., и, где m - арность и. Кванторы Зи (или V(u)) заменяются кванторами Зи, Зи 2 ... 3u m (Vu, Vu 2 ... Vu m , соответственно), и в подчиненных кванторам выражениях и[А,] заменяются и, a r(u) - r(Up u 2 ,..., u m).

Теорема. Для каждого безопасного выражения с переменными-кортежами существует эквивалентное безопасное выражение с переменными на доменах.

Пример. Даны отношения со схемами:

S(S#. SNAME, CITY) - поставщик;

Р(Р#. PNAME, PRICE) - деталь;

SP(S#. Р#. QTY) - поставка.

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

а) выражение исчисления с переменными-кортежами:

{t(SNAME) | 3u(S) 3v(SP) (S(u) л SP(v) л u л u, где X – объединение атрибутов из левой и правой частей функциональной зависимостей.

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

БКНФ (Бойса-Кодда)

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

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

5НФ . Отношение R находится в пятой нормальной форме (5НФ ) тогда и только тогда, когда любая имеющаяся зависимость соединения является тривиальной .

Зависимость соединения называется нетривиальной зависимостью соединения , если выполняется два условия:

11.​ Операции над отношениями: объединение, пересечение, разность, декартово произведение.

Отношения

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

· объединение

· пересечение

· разность

· декартово произведение

· деление

· проекция

· соединение

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

Степенью отношения называется число входящих в него атрибутов.

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

ОБЪЕДИНЕНИЕ (R U S) отношений R и S представляет собой множество кортежей, которые принадлежат R или S, либо им обоим. Операция объединения выполняется над двумя совместимыми отношениями.

ПЕРЕСЕЧЕНИЕ. Результат пересечения R и S содержит только те кортежи первого отношения R, которое есть во втором S.

РАЗНОСТЬ. Результат вычитания (R-S) включает только те кортежи первого отношения R, которых нет во втором S.

ДЕКАРТОВО ПРОИЗВЕДЕНИЕ (R x T). Здесь операнды-отношения R и T могут иметь разные схемы: Степень результирующего отношения (R x T) равна сумме степеней отношений операндов (R и T), а мощность - произведение их мощностей.

12.​ Операции над отношениями: деление.

ДЕЛЕНИЕ (R / T). Операция в некотором смысле обратна операции "декартово произведение". Отношение "делимое" (R) должно содержать подмножество атрибутов отношения "делитель" (T). Результирующее отношение (R / T) содержит только те атрибуты делимого, которых нет в делителе. В него включают только те кортежи, декартово произведение которых с делителем содержатся в делимом.

13.​ Операции над отношениями: проекция, выборка, соединение.

ПРОЕКЦИЯ. Эта операция в отличие от всех предыдущих является унарной, т.е. выполняется над одним отношением (R). Результирующее отношение П (R) включает часть атрибутов исходного, на которые выполняется проекция. Кортежи-дубликаты отсутствуют.

Где X – список атрибутов в схеме отношения.

СОЕДИНЕНИЕ. Операция соединения выполняется над двумя отношениями (R и S). В каждом отношении выделяется атрибут, по которому будет производиться соединение. В качестве атрибута для соединения выберем атрибут B. Результирующее отношение включает все атрибуты первого отношения (R) и второго отношения (S):

ВЫБОР. Операция выполняется над одним отношением (R). Результирующее отношение (OB=b(R)) содержит подмножества кортежей, выбранных по некоторому условию (B = b).

14.​ Проектирование БД (архитектура ANSI / SPARC)

Архитектура ANSI-SPARC (также 3х-уровневая архитектура ) определяет принцип, согласно которому рекомендуется строить системы управления базами данных(СУБД).

Проект архитектуры был выдвинут в 1975 году подкомитетом SPARC ANSI.

3 уровня СУБД:

1. внешний (пользовательский)
2. промежуточный (концептуальный )
3. внутренний (физический)

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

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

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

15.​ Инфологическое моделирование. Модель «сущность-связь» (ER-модель)

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

ER-модель (Entity-Relationship Model – модель «сущность-связь») - представление ИМ, основывающееся на структурных элементах «сущность», «свойство», «связь».

Сущности и свойства

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

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

Идентификатор ‐ одно или несколько свойств, по значениям которых однозначно различаются все экземпляры сущности (объекта).

Простое свойство - состоит из одного компонента с независимым существованием.

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

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

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

Связь - описание связанности двух сущностей и их экземпляров.

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

1. отношение “один к одному” (1:1) означает, что каждая запись одной таблицы соответствует только одной записи в другой таблице;

2. отношение “один ко многим” (1:М) возникает, когда одна запись взаимосвязана со многими другими;

3. отношение “многие к одному” означает, что многие записи связаны с одной (М:1);

4. отношение “многие ко многим” (M:N) возникает между двумя таблицами в тех случаях, когда:

· одна запись из первой таблицы может быть связана более чем с одной записью из второй таблицы;

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

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

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

Ассоциация может использоваться для:

· Реализации связи М:М

· Связывания трех и более сущностей

· Хранения дополнительной информации о связи

· Последовательность инфологического проектирования:

· Определение сущностей

· Установление подчиненности сущностей и формирование сложных

объектов

· Установление связей и определение ассоциаций

· Определение свойств сущностей

· Определение идентификаторов

16.​ Критерии оценки качества логической модели данных. Переход к реляционной модели данных (6 правил)

Критерии оценки качества логической модели данных

Адекватность базы данных предметной области
База данных должна адекватно отражать предметную область. Это означает, что должны выполняться следующие условия:
1. Состояние базы данных в каждый момент времени должно соответствовать состоянию предметной области.
2. Изменение состояния предметной области должно приводить к соответствующему изменению состояния базы данных
3. Ограничения предметной области, отраженные в модели предметной области, должны некоторым образом отражаться и учитываться базе данных.
Легкость разработки и сопровождения базы данных
Практически любая база данных, за исключением совершенно элементарных, содержит некоторое количество программного кода в виде триггеров и хранимых процедур.
Хранимые процедуры - это процедуры и функции, хранящиеся непосредственно в базе данных в откомпилированном виде и которые могут запускаться пользователями или приложения-ми, работающими с базой данных.
Триггеры - это хранимые процедуры, связанные с некоторыми событиями, происходящими во время работы базы данных. В качестве таких событий выступают операции вставки, обновления и удаления строк таблиц. Если в базе данных определен некоторый триггер, то он запускается автоматически всегда при возникновении события, с которым этот триггер связан.
Скорость операций обновления данных (вставка, обновление, удаление)
На уровне логического моделирования мы определяем реляционные отношения и атрибуты этих отношений. На этом уровне мы не можем определять какие-либо физические структуры хранения (индексы, хеширование и т.п.). Единственное, чем мы можем управлять - это распределением атрибутов по различным отношениям. Можно описать мало отношений с большим количеством атрибутов, или много отношений, каждое из которых содержит мало атрибутов. Таким образом, необходимо попытаться ответить на вопрос - влияет ли количество отношений и количество атрибутов в отношениях на скорость выполнения операций обновления данных. Такой вопрос, конечно, не является достаточно корректным, т.к. скорость выполнения операций с базой данных сильно зависит от физической реализации базы данных. Тем не менее, попытаемся качественно оценить это влияние при одинаковых подходах к физическому моделированию.
Таким образом, можно принять допущение, что чем больше атрибутов имеют отношения, разработанные в ходе логического моделирования, тем медленнее будут выполняться операции обновления данных, за счет затраты времени на перестройку большего количества индексов.
Скорость операций выборки данных
Одно из назначений базы данных - предоставление информации пользователям. Информация извлекается из реляционной базы данных при помощи оператора SQL - SELECT. Одной из наиболее дорогостоящих операций при выполнении оператора SELECT является операция соединение таблиц. Таким образом, чем больше взаимосвязанных отношений было создано в ходе логического моделирования, тем больше вероятность того, что при выполнении запросов эти отношения будут соединяться, и, следовательно, тем медленнее будут выполняться запросы. Таким образом, увеличение количества отношений приводит к замедлению выполнения операций выборки данных, особенно, если запросы заранее неизвестны.

Т.к. в реляционной модели данных между отношениями поддерживаются только связи типа «один ко многим», а в ER-модели допустимы связи «многие ко многим», то необходим специальный механизм преобразования, который позволит отразить множественные связи, неспецифические для реляционной модели, с помощью недопустимых для неё категорий. Для построения логических моделей, реляционных баз данных, методом декомпозиции, сформулирован ряд правил, получивших название «правила преобразования ER-диаграмм в отношениях БД». Правила позволяют привести схемы отношений БД к нормальным формам. Если степень связи между сущностями определена, то предварительное отношения могут быть получены путём просмотра нескольких альтернатив и выбора варианта, наиболее подходящего с точки зрения правил предметной области. Определяющими признаками выбора одного из альтернативных вариантов представления отношения и класс принадлежности сущности.

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

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

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

Правило 4 . Если степень бинарной связи 1:N, и класс принадлежности n-связной сущности является обязательным, то достаточно построить два отношения - по одному на каждую сущность. При этом ключ каждой сущности является первичным ключом соответствующего отношения, а ключ 1-связной сущности добавляется в отношение для n -связной сущности в качестве атрибута.

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

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

Если степень бинарной связи N:M, то во избежание дублирования и нуль-значений необходимо всегда строить три отношения. Сформулируем шестое правило.

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

17.​ Принципы поддержки целостности в реляционных моделях данных. Структурная целостность. Проблема Null значений.

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

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

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

<имя атрибута>IS NULL и <имя атрибута> IS NOT NULL.

Если в данном кортеже (в данной строке) указанный атрибут имеет неопределенное значение, то предикат IS NULL принимает значение TRUE (Истина), а предикат IS NOT NULL - FALSE(Ложь), в противном случае предикат IS NULL принимает значение FALSE, а предикат IS NOT NULL принимает значение TRUE. Ведение Null значений вызвало необходимость модификации классической двузначной логики и превращения ее в трехзначную. Все логические операции, производимые с неопределенными значениями, подчиняются этой логике в соответствии с заданной таблицей истинности.

Таблица 8.1.Таблица истинности для логических операций с неопределенными значениями

В стандарте SQL2 появилась возможность сравнивать не только конкретные значения атрибутов с неопределенным значением, но и результаты логических выражений сравнивать с неопределенным значением, для этого введена специальная логическая константа UNKNOWN. В этом случае операция сравнения выглядит как:

Логическое выражение > IS {TRUE | FALSE | UNKNOWN}

18.​ Принципы поддержки целостности в реляционных моделях данных. Языковая целостность. Ссылочная целостность. (продолжение 17 вопроса)

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

В-третьих , это поддержка ссылочной целостности (Declarative Referential Integrity, DRI), означает обеспечение одного из заданных принципов взаимосвязи между экземплярами кортежей взаимосвязанных отношений:

• кортежи подчиненного отношения уничтожаются при удалении кортежа основного отношения, связанного с ними.
• кортежи основного отношения модифицируются при удалении кортежа основного отношения, связанного с ними, при этом на месте ключа родительского отношения ставится неопределенное Null значение.

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

19.​ Семантическая поддержка целостности. Виды декларативных ограничений целостности

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

1. В библиотеке должны быть записаны читатели не моложе 17 лет.
2. В библиотеке присутствуют книги, изданные начиная с 1960 по текущий год.
3. Каждый читатель может держать на руках не более 5 книг.
4. Каждый читатель при регистрации в библиотеке должен дать телефон для связи: он может быть рабочим или домашним.

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

Выделяются следующие виды декларативных ограничений целостности:

§ Ограничения целостности атрибута: значение по умолчанию, задание обязательности или необязательности значений (Null), задание условий на значения атрибутов.

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

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

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

Декларативные ограничения целостности относятся к ограничениям, которые являются немедленно проверяемыми. Есть ограничения целостности, которые являются откладываемыми. Эти ограничения целостности поддерживаются механизмом транзакций и триггеров.

20.​ Транзакции. Триггеры и хранимые процедуры.

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

Транзакция обладает четырьмя важными свойствами, известными как свойства А СИД:

(А) Атомарность. Транзакция выполняется как атомарная операция - либо выполняется вся транзакция целиком, либо она целиком не выполняется.

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

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

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

Набор примитивов

- BEGIN_TRANSACTION ; границы

- END_TRANSACTION ; транзакции

- ABORT_TRANSACTION;

- WRITE.

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

Подана команда BEGIN TRANSACTION;

Подана команда ABORT_TRANSACTION (откатить транзакцию);

Произошло отсоединение пользователя от СУБД;

Произошел сбой системы.

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

Триггеры позволяют:

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

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

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

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

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

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

SQL для триггеров и хранимых процедур содержит множество операторов императивного программирования:

Конкатенацию строк,

Арифметические операции,

Операции сравнения,

Логические (not, and, or),

Операторы структурного программирования (IF, FOR, WHILE),

Объявление переменных (DECLARE),

Эти операторы используются совместно с операторами декларативного программирования INSERT, UPDATE, DELETE и SELECT.

В современных СУБД код хранимых процедур и триггеров может писаться на смеси диалектов SQL и языков высокого уровня, например, в Oracle – на PL/SQL или Java. Фактически запросы, написанные на декларативном языке, вкладываются в процедуры, написанные на императивном языке

Основной структурой данных в реляционной модели (РМД) является отношение, поэтому модель получила название реляционная (relation – отношение).

В РМД данные организованы в таблицы , которые должны удовлетворять определенным ограничениям, и могут рассматриваться как отношения .

Табличное представление было предложено американским математиком Э.Ф. Коддом в начале 70-х годов и реализовано фирмой IBM в начале 80-х. Двумерная таблица – это один из самых простых способов представления данных для пользователя или программиста.

Табличное представление отношения «Служащие» приведено в табл.1.

Табл.1. Отношение «Служащие» – таблица «Служащие»

В РМД используются формальные реляционные термины, которые могут заменяться неформальными. Соответствие формальных и неформальных терминов представлено в табл.2.

Табл.2. Соответствие неформальных и формальных терминов РМД

Модель имеет серьезную теоретическую основу – теория множеств и математическая логика.

Основные понятия реляционной модели:

- тип данных, значение;

- домен;

- атрибут;

- кортеж;

- ключ;

- отношение.

Понятие типа данных эквивалентно понятию типа данных в алгоритмических языках. Атомарное значение данных – это наименьшая неделимая единица данных в РМД.

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

Атрибут – это именованный столбец отношения, значения элементов столбца должны быть из одного домена.

Пусть дана совокупность доменов D 1 , D 2 ,…,D N (не обязательно различных).

Кортеж отношения – это набор из N значений, расположенных в строго определенном порядке (d 1 , d 2 ,…,d N), таких, что d 1 принадлежит D 1 , d 2 принадлежит D 2 , а d N принадлежит D N . Количество элементов в кортеже называется арностью.

Полное декартово произведение доменов D 1 x D 2 x…x D N – это множество всевозможных различных кортежей арности N, где каждый элемент кортежа берется из своего домена (пример: D1(№гр), D2(Фам_студ), D3(Стип)).

Отношение R , определенное на этих N доменах, является подмножеством полного декартового произведения исходных доменов.

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

Кортеж, соответствующий данной схеме отношения, представляет собой множество пар {имя атрибута, значение}, которое содержит одно вхождение каждого имени атрибута, принадлежащего схеме отношения.

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

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

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

Ограничения реляционной модели (свойства таблиц):

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

2. Каждый элемент таблицы должен быть атомарным , т.е. неделимым.

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

4. Каждому столбцу присвоено уникальное имя. Элементы одного столбца должны быть однородными, извлечены из одного домена.

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

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

Более короткая форма записи таблицы «Служащие» или схема отношения «Служащие» (первичный ключ отношения подчеркнут):

Служащие(Таб_номер , Фамилия, Отдел, Дата_рожд, Должность, Зарплата)

В общем виде схема отношения записывается как

R(a 1 , a 2 , ..., a N), где а i – имя i-ого атрибута отношения R.

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

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

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

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

Особенность РМД в том, что и объекты, и связи между ними представляются в единой форме, в виде таблиц.

В отличие от иерархической и сетевой моделей связи между отношениями поддерживаются неявно . В РМД поддерживаются бинарные связи типа «1:1», «1:M», «M:1». В каждой связи одно отношение выступает как основное (со стороны 1), а другое как подчиненное (со стороны М). Это означает, что один кортеж основного отношения может быть связан с несколькими кортежами подчиненного отношения.

Связь поддерживается связующим набором атрибутов, в основном отношении это первичный ключ (primary key) , который должен присутствовать в подчиненном отношении, как вторичный ключ. Этот набор атрибутов в подчиненном отношении называют внешним ключом (foreign key) .

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

Рассмотрим пример поддержания связи типа «1:М» между отношениями «Группа» и «Студенты». Основным отношением является отношение «Группа», первичный ключ отношения - атрибут «Номер_группы». Подчиненным отношением является отношение «Студенты», первичный ключ отношения – «Номер_зачетной_книжки». В отношении «Студенты» должен присутствовать атрибут «Номер_группы», как внешний ключ для связи с основным отношением. Именно этот атрибут и позволяет определить информацию о группе, в которой студент обучается.

Схема основного отношения «Группа»:

Группа (№_группы , Специальность)

Схема подчиненного отношения «Студенты»:

Студенты (№_зачетной_книжки , Фамилия, Дата_рождения, №_группы )

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

Примеры СУБД РМД: DBase, FoxPro, Clipper, Paradox, MS Access, Informix, Oracle и др.

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

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

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

Служащие (Таб_номер , Фамилия, Зарплата, Номер_отдела )

Трудовая_деятельность (Номер_приказа , Содержание_приказа, Таб_номер )

Дети (Имя_ребенка, Таб_номер , Дата_рождения)

Работы (Шифр_работы , Наименование, Дата_завершения, Номер_отдела )

Достоинства реляционной модели:

– простота и наглядность модели;

– однородность структур для представления объектов и связей;

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

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

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

В иерархической и сетевой модели связи физические, данные взаимосвязаны физическими указателями. Это достоинство и недостаток. Хорошо реализуются предусмотренные физические связи, а другие отношения трудно извлекать. В реляционной модели связи логические.

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

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

Элементы реляционной модели

Реляционная модель данных (РМД) некоторой предметной области представляет собой набор отношений, изменяющихся во времени. При создании информационной системы совокупность отношений позволяет хранить данные об объектах предметной области и моделировать связи между ними. Элементы РМД и формы их представления приведены в табл. 19.1.

Таблица 19.1

Элементы реляционной модели

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

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

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

Математически отношение можно описать следующим образом. Пусть даны n множеств D1, D2, D3, ... Dn, тогда отношение R есть множество упорядоченных кортежей ,гдеdk ∈ Dk, a D1, D2, D3,... Dn - домены отношения R.

На рис. 19.2 приведен пример представления отношения СОТРУДНИК.

Множество всех значений каждого атрибута отношения образует домен. Отношение СОТРУДНИК включает 4 домена. Домен 1 содержит фамилии всех сотрудников,домен 2 - номера всех отделов фирмы,домен 3 - название всех должностей,домен 4 - даты рождения всех сотрудников. Каждый домен образует значения одного типа, например, числовые или символьные.

Отношение СОТРУДНИК содержит 3 кортежа. Кортеж рассматриваемого отношения состоит из 4-х элементов, каждый из которых выбирается из соответствующего домена. Каждому кортежу соответствует строка таблицы.

Схема отношения представляет собой список имен атрибутов. Например, для приведенного примера схема отношения имеет вид СОТРУДНИК(ФИО, Отдел, Должность, Д_Рождения).

Рис. 19.2. Представление отношения СОТРУДНИК

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

Существует также понятие внешнего ключа. С помощью внешних ключей устанавливаются связи между отношениями. Например, имеются два отношения СТУДЕНТ (ФИО. Группа, Специальность) и ПРЕДМЕТ(Назв.Пр. Часы), которые связаны отношением СТУДЕНТ_ПРЕДМЕТ(ФИО. Назв.Пр. Оценка) (рис. 19.3). В связующем отношении атрибуты ФИО и Назв.пр образуют составной ключ. Эти атрибуты представляют собойвнешние ключи, являющиеся первичными ключами других отношений.

Рис. 19.3. Связь отношений

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

Наиболее часто таблица с отношением размещается в отдельном файле. В некоторых СУБД, например, Microsoft Access, в одном фарше размещается полностью база данных.

Ограничения и операции над отношениями

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

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

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

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

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

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

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

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

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

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

Вторую группу составляют специальные операции над отношениями, к которым относятся операции: проекции, соединения, выбора.

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

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

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

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

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