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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Часть 2. Реляционная модель данных

Реляционная модель является удобной и наиболее привыч­ной формой представления данных в виде таблицы.

В отличие от иерархической и сетевой моделей, такой способ представления:

1. понятен пользователю-непрограммисту;

2. позволяет легко изменять схему - присоединять новые элементы данных и запи­си без изменения соответствующих подсхем;

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

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

Пользо­ватель модели сам должен для себя решить вопрос, обладают ли соответствующие сущности реального мира однородностью. Этим самым решается проблема пригодности модели для пред­полагаемого применения.

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

1. домен,

2. отношение,

3. кортеж,

4. кардинальность,

5. атрибуты,

6. степень,

7. первичный ключ.

Соотношение этих понятий иллюстрируется рисунок 7.

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

Таблица 7.

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

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

В математических дисциплинах понятию «таблица» соответствует понятие «отношение» (relation). Отсюда и произошло название модели - реляционная. То есть, применительно к базам данных понятия «реляци­онная БД» и «табличная БД» по существу являются синонимами.

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

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

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

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

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

Модель предъявляет к таблицам следующие требования:

1. данные в ячейках таблицы должны быть структурно неде­лимыми 1 ;

2. данные в одном столбце должны быть одного типа;

3. каждый столбец должен быть уникальным (недопустимо дублирование столбцов);

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

5. строки размещаются в таблице также в произвольном по­рядке;

6. столбцы имеют уникальные наименования.

В целом концепция реляционной модели определяется сле­дующими двенадцатью правилами Кодда (в лекции правила приводятся по ).

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

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

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

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

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

Определение данных;

Определение представлений;

Обработку данных (интерактивную и программную);

Условия целостности;

Идентификацию прав доступа;

Границы транзакций (начало, завершение и отмена).

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

7. Правило добавления, обновления и удаления. Возможность работать с отношением как с одним операндом должна сущест­вовать не только при чтении данных, но и при добавлении, об­новлении и удалении данных.

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

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

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

11. Правило независимости распространения. Реляционная СУБД не должна зависеть от потребностей конкретного клиента.

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

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

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

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

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

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

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

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

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

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

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

Литература

1. Дейт К. Введение в системы баз данных: Пер. с англ. - М.: Наука, 1980.- 463 с.

2. Грофф Дж., Ваинберг П. SQL: полное руководство / Пер. с англ. 2-е изд. К.: BHV, 2001.

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

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

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

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

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

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

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

Реляционная модель данных

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

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

Атрибут (или данное) - это некоторый показатель, который характеризует некий объект и принимает для конкретного экземпляра объекта некоторое чис­ловое, текстовое или иное значение. Информационная система оперирует на­борами объектов, спроектированными применительно к данной предметной области, используя при этом конкретные значения атрибутов (данных) тех или иных объектах. Например, возьмем в качестве набора объектов классы в школе. Число учеников в классе - это данное, которое принимает числовое значение (у одного класса 28, у другого- 32). Название класса - это данное, принимающее текстовое значение (у одного - 10А, у другого - 9Б и т. д.).

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

Основоположником теории реляционных баз данных считается сотрудник фирмы IBM доктор Э. Кодд, опубликовавший 6 (июня 1970 г. статью A Relational Model of Data for Large-Shared Data Banks (Реляционная модель данных для больших коллективных банков данных). В этой статье впервые был использован термин «реляционная модель данных. Теория реляционных баз данных, разработанная в 70-х годах в США докто­ром Э. Коддом, имеет под собой мощную математическую основу, описывающую правила эффективной организации данных. Разработанная Э. Коддом теорети­ческая база стала основой для разработки теории проектирования баз данных.

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

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

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

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

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

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

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

Так как строки в таблице не упорядочены, невозможно выбрать строку по ее позиции - среди них не существует «первой», «второй», «последней». Любая таблица имеет один или несколько столбцов, значения в которых однозначно идентифицируют каждую ее строку. Такой столбец (или комбинация столбцов) называется первичным ключом (primary key) . Часто вводят искусственное поле, предназначенное для нумерации за­писей в таблице. Таким полем, например, может быть его порядковый, который сможет обеспечить уникальность каж­дой записи в таблице. Ключ должен обладать следующими свойствами.

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

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

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

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

Взаимосвязь таблиц является важнейшим элементом реляционной модели данных. Она поддерживается внешними ключами (foreign key).

При описании модели реляционной базы данных для одного и того же поня­тия часто употребляют различные термины, что зависит от уровня описания (теория или практика) и системы (Access, SQL Server, dBase). В табл. 2.3 приве­дена сводная информация об используемых терминах.

Таблица 2.3. Терминология баз данных

Теория БД____________ Реляционные БД_________ SQL Server __________

Отношение (Relation) Таблица (Table) Таблица (Table)

Кортеж (Tuple) Запись (Record) Строка (Row)

Атрибут (Attribute)Поле (Field)_______________ Столбец или колонка (Column)

Реляционные базы данных

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Связи

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Деталь /Е2

Постащик/Е1

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

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

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

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

Деталь /Е2

выполняет

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

Количество

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

множество 1

множество 2

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

г = г,иг 3 = { , }

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Проекция

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Соединение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

^ 71 р#(р)) 8)-

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Таблица 5.1

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

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

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

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

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

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

= ‘РГ л и = 1)}.

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

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

такие, что

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

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

Ули = 1))}.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

{t(SNAME) | 3u(S) 3v(SP) (S(u) л SP(v) л u л u}