Что называется реляционной алгеброй

Реляционная алгебра

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

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

Содержание

Замкнутость реляционной алгебры

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

Операции над одним отношением называются унарными, над двумя отношениями — бинарными, над тремя — тернарными (таковые практически неизвестны).

Пример унарной операции — проекция, пример бинарной операции — объединение.

N-арную реляционную операцию f можно представить функцией, возвращающей отношение и имеющей n отношений в качестве аргументов:

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

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

Ограничения на операции

Некоторые реляционные операции, в частности, операции объединения, пересечения и вычитания, требуют, чтобы отношения имели совпадающие (одинаковые) заголовки (схемы). Это означает, что совпадают количество атрибутов, названия атрибутов и тип (домен) одноимённых атрибутов.

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

Операции реляционной алгебры

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

Переименование

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

R — отношение
Atr₁, Atr₂, … — исходные имена атрибутов
NewAtr₁, NewAtr₂, … — новые имена атрибутов

Объединение

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

Пересечение

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

Вычитание

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

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

Отношение (A₁, A₂, …, A_m, B₁, B₂, …, B_m), заголовок которого является сцеплением заголовков отношений A(A₁, A₂, …, A_m) и B(B₁, B₂, …, B_m), а тело состоит из кортежей, являющихся сцеплением кортежей отношений A и B:

Выборка (ограничение)

Отношение с тем же заголовком, что и у отношения A, и телом, состоящим из кортежей, значения атрибутов которых при подстановке в условие c дают значение ИСТИНА. c представляет собой логическое выражение, в которое могут входить атрибуты отношения A и/или скалярные выражения.
Синтаксис:

Проекция

Отношение с заголовком (X, Y, …, Z) и телом, содержащим множество кортежей вида (x, y, …, z), таких, для которых в отношении A найдутся кортежи со значением атрибута X равным x, значением атрибута Y равным y, …, значением атрибута Z равным z. При выполнении проекции выделяется «вертикальная» вырезка отношения-операнда с естественным уничтожением потенциально возникающих кортежей-дубликатов.
Синтаксис:

Соединение

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

Деление

Примечания

Литература

Ссылки

Полезное

Смотреть что такое «Реляционная алгебра» в других словарях:

Реляционная алгебра — формальная система манипулирования отношениями, основными операциями которой являются: проекция, соединение, пересечение и объединение. См. также: Реляционная модель данных Финансовый словарь Финам … Финансовый словарь

реляционная алгебра — — [http://www.iks media.ru/glossary/index.html?glossid=2400324] Тематики электросвязь, основные понятия EN relational algebra … Справочник технического переводчика

реляционная алгебра — saryšių algebra statusas T sritis automatika atitikmenys: angl. relational algebra vok. Relationsalgebra, f rus. алгебра отношений, f; реляционная алгебра, f pranc. algèbre des relations, f … Automatikos terminų žodynas

Проекция (реляционная алгебра) — У этого термина существуют и другие значения, см. Проекция. Проекция в реляционной алгебре унарная операция, которая позволяет получить «вертикальное» подмножество данного отношения, или таблицы, то есть такое подмножество, которое… … Википедия

Реляционная модель данных — (РМД) логическая модель данных, прикладная теория построения баз данных, которая является приложением к задачам обработки данных таких разделов математики как теории множеств и логика первого порядка. На реляционной модели данных строятся… … Википедия

Алгебра (значения) — Алгебра раздел математики либо математическая структура специального вида (см. Алгебраическая система) Как раздел математики Абстрактная алгебра Алгебра логики раздел математической логики. Коммутативная алгебра Линейная алгебра… … Википедия

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

алгебра отношений — saryšių algebra statusas T sritis automatika atitikmenys: angl. relational algebra vok. Relationsalgebra, f rus. алгебра отношений, f; реляционная алгебра, f pranc. algèbre des relations, f … Automatikos terminų žodynas

Реляционная СУБД — (РСУБД; иначе Система управления реляционными базами данных, СУРБД) СУБД, управляющая реляционными базами данных. Понятие реляционный (англ. relation отношение) связано с разработками известного английского специалиста в области… … Википедия

Реляционная база данных — Реляционная база данных база данных, основанная на реляционной модели данных. Слово «реляционный» происходит от англ. relation (отношение[1]). Для работы с реляционными БД применяют реляционные СУБД. Использование реляционных баз… … Википедия

Источник

Что называется реляционной алгеброй

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

В реализациях конкретных реляционных СУБД сейчас не используется в чистом виде ни реляционная алгебра, ни реляционное исчисление. Фактическим стандартом доступа к реляционным данным стал язык SQL (Structured Query Language). Язык SQL представляет собой смесь операторов реляционной алгебры и выражений реляционного исчисления, использующий синтаксис, близкий к фразам английского языка и расширенный дополнительными возможностями, отсутствующими в реляционной алгебре и реляционном исчислении. Вообще, язык доступа к данным называется реляционно полным, если он по выразительной силе не уступает реляционной алгебре (или, что то же самое, реляционному исчислению), т.е. любой оператор реляционной алгебры может быть выражен средствами этого языка. Именно таким и является язык SQL.

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

Замкнутость реляционной алгебры

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

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

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

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

Традиционно, вслед за Коддом [43], определяют восемь реляционных операторов, объединенных в две группы.

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

Отношения, совместимые по типу

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

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

Оператор переименования атрибутов

Оператор переименования атрибутов имеет следующий синтаксис:

— отношение,

— исходные имена атрибутов,

— новые имена атрибутов.

В результате применения оператора переименования атрибутов получаем новое отношение, с измененными именами атрибутов.

Следующий оператор возвращает неименованное отношение, в котором атрибут переименован в :

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

Объединение

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

Синтаксис операции объединения:

Замечание. Объединение, как и любое отношение, не может содержать одинаковых кортежей. Поэтому, если некоторый кортеж входит и в отношение , и отношение , то в объединение он входит один раз.

Пример 2. Пусть даны два отношения и с информацией о сотрудниках:

Таблица 1 Отношение A

Таблица 2 Отношение B

Объединение отношений и будет иметь вид:

Таблица 3 Отношение A UNION B

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

Пересечение

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

Синтаксис операции пересечения:

Пример 3. Для тех же отношений и , что и в предыдущем примере пересечение имеет вид:

Таблица 4 Отношение A INTERSECT B

Вычитание

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

Синтаксис операции вычитания:

Пример 4. Для тех же отношений и , что и в предыдущем примере вычитание имеет вид:

Таблица 5 Отношение A MINUS B

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

Определение 5. Декартовым произведением двух отношений и называется отношение, заголовок которого является сцеплением заголовков отношений и :

,

а тело состоит из кортежей, являющихся сцеплением кортежей отношений и :

,

таких, что , .

Синтаксис операции декартового произведения:

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

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

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

Пример 5. Пусть даны два отношения и с информацией о поставщиках и деталях:

Таблица 6 Отношение A (Поставщики)

Таблица 7 Отношение B (Детали)

Декартово произведение отношений и будет иметь вид:

Таблица 8 Отношение A TIMES B

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

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

Выборка (ограничение, селекция)

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

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

Синтаксис операции выборки:

,

Пример 6. Пусть дано отношение с информацией о сотрудниках:

Таблица 9 Отношение A

Результат выборки будет иметь вид:

Таблица 25 Отношение ВЕЩЕСТВО

Таблица 26 Отношение ЭЛЕМЕНТЫ

Таблица 27 Отношение ХИМИЧЕСКИЙ_СОСТАВ_ВЕЩЕСТВ

На языке SQL такой запрос реализуется одной командой:

Невыразимость транзитивного замыкания реляционными операторами

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

Пример 17. Рассмотрим отношение, описывающее сотрудников некоего предприятия. Отношение содержит данные о табельном номере сотрудника, фамилии, должности и табельном номере руководителя сотрудника – СОТРУДНИКИ ( ТАБ_НОМ, ФАМИЛИЯ, ДОЛЖНОСТЬ, ТАБ_НОМ_РУК):

Таблица 28 Отношение СОТРУДНИКИ

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

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

Кросс-таблицы

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

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

Таблица 29 Данные о продажах

Таблица 30 Кросс-таблица

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

Выводы

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

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

Теоретико-множественные операторы: объединение, пересечение, вычитание, декартово произведение.

Специальные реляционные операторы: выборка, проекция, соединение, деление.

Для выполнения некоторых реляционных операторов требуется, чтобы отношения были совместимы по типу.

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

Источник