Реляционная модель данных (РМД) была разработана сотрудником 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

							5 = Г 1 и Г 2

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

• коммутативна - г 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(Я), Б = | ^ ? Г, И ^

								8 = Г 1 П Г 2

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

• коммутативна - г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:)

							Ь = Г 1 XI Г 2

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

Результат операции левого внешнего соединения г, х] г 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), и все атрибуты определены на числовых доменах. Тогда можно получить соединение по условию:

С = Г М у ъ 1 1 В

Если в качестве операции 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

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

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

Выражение реляционной алгебры	Выражение реляционного исчисления с переменны ми-кортежами
Объединение: г, и г, г,(К), г 9 (К)	(х(Я) | Г,(х) V г 2 (х)}
Разность: г, - г, г,(К), г 2 (Я)	(х(Я) I Г,(х) А -іГ 2 (х)}
Пересечение: г 1 п г 2 , г^Я), г 7 (К)	{х(Я)|г,(х)лг 2 (х)}
Декартово произведение: г, х г., гДЯ,), г 2 (Я 2)	(х(Я,Я,) 1 Эи(Я,) Эу(Я 2) (г,(и) л г 2 (у) л х[Я,] = И{г1]лх[Я 2 1=у[Я 2 ])}
Проекция: Д ь (г), г(Я), ЬсЯ	{ДО | Эи(Я) (г(и) л и[Ц = ДЬ]}
Выбор: а р (г), г(Я)	Д(Я) | г(1) л Я’)}
Естественное соединение: г,мг, г,(АВ), г 2 (ВС)	{ДАВС) | Эи(АВ) Эу(ВС) (г,(и) л г 2 (у) л и[В] = = у[В] л ДАВ] = и [ А В ] л Т[С] = у[С])}
Деление: г, н- г 2 , г,(АВ), г 2 (В)	{ДА) | Ух(В) (г 2 (х) л Эу(АВ) (г,(у) л у[В] = Х[В]лу[А]=ДА]}

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

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

• 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{<Список кортежей >}. (1.2)

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

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

Рис. 1.13. Пример отношения "Сотрудники"

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

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

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

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

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

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

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

Данное свойство следует из того, что тело отношения представляется

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

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

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

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

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

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

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

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

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

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

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

Таблица 13

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

Вид представления	Используемая терминология	Назначение
Модель с отражением наименования отношения, атрибутивного состава, связей	Сущность Тип данных	Используется для моделирования логической структуры данных для последующего перехода на физический уровень
Модель с отражением заголовка и тела с возможными данными	Отношение Заголовок Атрибут/Домен Тип данных	Используется для представления с указанием возможных значений данных и применения при необходимости анализа возможных операций над отношениями и данными в отношениях
Модель с отображением структур физического представления данных в СУБД	Атрибут/11оле/Колонка Тип данных	Используется для отображения варианта представления структуры, которая будет реализована на физическом уровне в СУБД

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

• Бойко В. В.. Савинков В. М. Проектирование баз ланных информационных систем.
• Типы данных будут рассматриваться в рамках последующих глав.
• Термин "Нормализация" и нормальные формы будут рассматриваться в гл. 2.