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

Структурной части.

Целостной части.

Манипуляционной части.

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

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

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

В данной главе рассматривается структурная часть реляционной модели.

Типы данных

Любые данные, используемые в программировании, имеют свои типы данных.

Важно! Реляционная модель требует, чтобы типы используемых данных были простыми .

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

Простые типы данных.

Структурированные типы данных.

Ссылочные типы данных.

Простые типы данных

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

Логический.

Строковый.

Численный.

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

• Вещественный.

• Денежный.

  Перечислимый.

  Интервальный.

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

Структурированные типы данных

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

• Записи (Структуры)

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

называемое множеством индексов. Отображение

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

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

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

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

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

Ссылочные типы данных

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

Типы данных, используемые в реляционной модели

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

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

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

Домены

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

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

Домен имеет уникальное имя (в пределах базы данных).

Домен определен на некотором простом типе данных или на другом домене.

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

Домен несет определенную смысловую нагрузку .

Например, домен , имеющий смысл "возраст сотрудника" можно описать как следующее подмножество множества натуральных чисел:

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

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

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

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

Замечание . Не всегда очевидно, как задать логическое условие, ограничивающее возможные значения домена. Я буду благодарен тому, кто приведет мне условие на строковый тип данных, задающий домен "Фамилия сотрудника". Ясно, что строки, являющиеся фамилиями не должны начинаться с цифр, служебных символов, с мягкого знака и т.д. Но вот является ли допустимой фамилия "Ггггггыыыыы"? Почему бы нет? Очевидно, нет! А может кто-то назло так себя назовет. Трудности такого рода возникают потому, что смысл реальных явлений далеко не всегда можно формально описать. Просто мы, как все люди, интуитивно понимаем, что такое фамилия, но никто не может дать такое формальное определение, которое отличало бы фамилии от строк, фамилиями не являющимися. Выход из этой ситуации простой - положиться на разум сотрудника, вводящего фамилии в компьютер.

Отношения, атрибуты, кортежи отношения

Определения и примеры

Фундаментальным понятием реляционной модели данных является понятие отношения . В определении понятия отношения будем следовать книге К. Дейта .

Определение 1. Атрибут отношения есть пара вида <Имя_атрибута: Имя_домена>.

Имена атрибутов должны быть уникальны в пределах отношения. Часто имена атрибутов отношения совпадают с именами соответствующих доменов.

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

Заголовок отношения содержит фиксированное количество атрибутов отношения:

Тело отношения содержит множество кортежей отношения. Каждый кортеж отношения представляет собой множество пар вида <Имя_атрибута: Значение_атрибута>:

таких что значение атрибута принадлежит домену

Отношение обычно записывается в виде:

или короче

,

или просто

Число атрибутов в отношении называют степенью (или -арностью ) отношения.

Мощность множества кортежей отношения называют мощностью отношения.

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

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

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

Пример 1 . Рассмотрим отношение "Сотрудники" заданное на доменах "Номер_сотрудника", "Фамилия", "Зарплата", "Номер_отдела". Т.к. все домены различны, то имена атрибутов отношения удобно назвать так же, как и соответствующие домены. Заголовок отношения имеет вид.

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

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

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

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

Атрибуты – свойства, характеризующие сущность (столбцы). Степень отношения – количество столбцов.

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

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

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

Ограниченность: домен имеет границу, данные делятся на возможные и невозможные. Как и для множества, это не означает, что количество элементов конечное.

Уникальность: можно сравнить одни элементы с другими и избежать дубликатов. Для одного отдельного домена это само собой разумеется.

Понятие домена помогает правильно моделировать предметную область

Домен и атрибуты. А трибуты должны быть увязаны с доменами, или, «определены на некоем домене». На одном домене могут быть заданы несколько атрибутов.

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

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

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

Ограничить излишние сравнения между атрибутами – основное назначение доменов.

Кортеж – строка таблицы.

Кардинальность (мощность) – количество строк в таблице.

	Фамилия, имя, отчество	Год рождения	Должность	Код кафедры
	Иванов И.И.
	Петров П.П.		профессор
	Сидоров С.С.
	Васильев В.В.
	Вовкин В.В.		преподаватель
	Степанов С.С.		профессор

Рис 17. Элементы реляционной модели

Понятие базы данных тесно связано с такими понятиями структурных элементов, как поле, запись, файл (таблица) ,

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

и м я , например. Фамилия, Имя, Отчество, Дата рождения;

т и п , например, символьный, числовой, календарный;

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

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

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

Файл (таблица) - совокупность экземпляров записей одной структуры.

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

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

Типы данных, допустимые в реляционной модели данных.

Основные типы данны, используемые в моделях данных:

Short Integer – короткое целое число;

Long Integer – длинное целое число;

Float – вещественное число (число с плавающей десятичной точкой);

Double – вещественное число (число с плавающей десятичной точкой) двойной точности;

Text – текстовый тип данных;

Logical - логический (да/нет);

Data - временной. Значение определяется как дата с установленным разделителем в установленном формате;

Blob – большие бинарные объекты (binary large object - BLOB), которые могут хранить данные неограниченного размера. Поля этого типа позволяют хранить безразмерную произвольную двоичную информацию.

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

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

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

Ключи, которые можно использовать в качестве первичных, называются потенциальными илиальтернативными ключами .

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

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

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

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

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

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

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

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

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