кардинальное число отношения полученного в результате декартово произведение равно

Кардинальное число отношения полученного в результате декартово произведение равно

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

Рис. 1. Операции реляционной алгебры

Нужно объединить два отношения Физ_лица и Юр_лица.

Отношение Физ_лица

ФИО	Адр_регистрации	Факт_адр
Иванов Ю.М.	Москва, Тверская 2	С.-Петербург,Садовая ул. 12
Сергеев И.А.	С.-Петербург, Седова 23	С.-Петербург, Гороховая ул. 34
.	.	.

Отношение Юр_лица

Наим	Адр_регистрации	Адр_офиса
Альфа	Новгород, Садовая ул. 2	С.-Петербург,Садовая ул. 42
Бета.	С.-Петербург, Московский пр. 23	Гатчина, Лесная ул. 34
.	.	.

Результат запроса:

ИМЯ	Адр_официальный	Фактический_адр
Иванов Ю.М.	Москва, Тверская 2	С.-Петербург,Садовая ул. 12
Сергеев И.А.	С.-Петербург, Седова 23	С.-Петербург, Гороховая ул. 34
Альфа	Новгород, Садовая ул. 2	С.-Петербург,Садовая ул. 42
Бета.	С.-Петербург, Московский пр. 23	Гатчина, Лесная ул. 34
.	.	.

Операции объединения, пересечения и разности имеют следующие особенности:

Из отношения Жители нужно выбрать жителей, младше 30 лет

Отношение Жители

ФИО	Возраст
Андреев	31
Иванов	21
Перов	40
Яковлев	27

На языке SQL запрос запрос выглядит так:

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

ФИО	Возраст
Андреев	31
Перов	40

Из отношения Жители нужно выбрать только фамилии жителей

Отношение Жители

Имя	ФИО	Возраст
Юрий	Иванов	31
Сергей	Иванов	21
Владимир	Перов	40
Игорь	Перов	27

На языке SQL запрос запрос выглядит так:

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

ФИО
Иванов
Перов

Язык SQL предназначен для работы с реальными таблицами и допускает несколько одинаковых строк в таблице с результатами запроса. Для исключения одинаковых строк служит служебное слово DISTINCT

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

Даны два отношения Рабочие и Инструменты

Рабочие ТабНомер ФИО Должность 1 Андреев Слесарь 2 Иванов Слесарь 3 Перов Токарь 4 Яковлев Фрезеровщик

Инструменты ТабНомер Инструмент 1 Штангельциркуль 1 Микрометр 1 Линейка 2 Штангельциркуль 2 Скоба

ТабНомер	ФИО	Должность	Инструмент
1	Андреев	Слесарь	Штангельциркул
1	Андреев	Слесарь	Микрометр
1	Андреев	Слесарь	Линейка
2	Иванов	Слесарь	Штангельциркул
2	Иванов	Слесарь	Скоба

Если в запросе не указать общий атрибут, то получится декартово произведение, состоящее из 4*5=20 кортежей.

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

Выполнение этого запроса состоит из двух реляционных операций: выборки и проекции.

Источник

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

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

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

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

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

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

таблица PRODUCTS

ID	NAME	COMPANY	PRICE
123	Печеньки	ООО ”Темная сторона”	190
156	Чай	ООО ”Темная сторона”	60
235	Ананасы	ОАО ”Фрукты”	100
623	Томаты	ООО ”Овощи”	130

Таблица состоит из 4х строк, строка в таблице является кортежем в реляционной теории. Множество упорядоченных кортежей называется отношением.
Перед тем как дать определение отношения, введем еще один термин — домен. Домены применительно к таблице это столбцы.

Для ясности, теперь введем строгое определение отношения.

Ключи в отношениях

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

COMPANY	DRIVER
ООО ”Темная сторона”	Владимир
ООО ”Темная сторона”	Михаил
ОАО ”Фрукты”	Руслан
ООО ”Овощи”	Владимир

Видно, что в организации может быть несколько водителей, и чтобы однозначно идентифицировать водителя необходимо и значение из столбца “Название организации” и из “Имя водителя”. Такой ключ называется составным.

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

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

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

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

ID	SELLER
123	OOO “Дарт”
156	ОАО ”Ведро”
235	ЗАО “Овоще База”
623	ОАО ”Фирма”

Условимся, что в этой таблице ID это внешний ключ, связанный с первичным ключом таблицы PRODUCTS.

Для начала рассмотрим самую простую операцию — имя отношения. Её результатом будет такое же отношение, то есть выполнив операцию PRODUCTS, мы получим копию отношения PRODUCTS.

Проекция

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

Синтаксис операции:
π _{(ID, PRICE)} PRODUCTS

В результате этой операции получим отношение:

ID	PRICE
123	190
156	60
235	100
623	130

Выборка

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

Синтаксис операции:
σ _(PRICE>90) PRODUCTS

ID	NAME	COMPANY	PRICE
123	Печеньки	ООО ”Темная сторона”	190
235	Ананасы	ОАО ”Фрукты”	100
623	Томаты	ООО ”Овощи”	130

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

σ _{(PRICE>90 ^ ID π COMPANY σ (PRICE 123ПеченькиООО ”Темная сторона”190123OOO “Дарт”156ЧайООО ”Темная сторона”60156ОАО ”Ведро”123ПеченькиООО ”Темная сторона”190156ОАО ”Ведро”156ЧайООО ”Темная сторона”60123OOO “Дарт”}

Для примера использования этой операции представим себе необходимость выбрать продавцов с ценами меньше 90. Без произведения необходимо было бы сначала получить ID продуктов из первой таблицы, потом по этим ID из второй таблицы получить нужные имена SELLER, а с использованием произведения будет такой запрос:

Источник

Кардинальное число отношения полученного в результате декартово произведение равно

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

— отношение,

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

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

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

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

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

Объединение

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

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

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

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

Табельный номер	Фамилия	Зарплата
1	Иванов	1000
2	Петров	2000
3	Сидоров	3000

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

Табельный номер	Фамилия	Зарплата
1	Иванов	1000
2	Пушников	2500
4	Сидоров	3000

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

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

Табельный номер	Фамилия	Зарплата
1	Иванов	1000
2	Петров	2000
3	Сидоров	3000
2	Пушников	2500
4	Сидоров	3000

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

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

Пересечение

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

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

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

Табельный номер	Фамилия	Зарплата
1	Иванов	1000

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

Вычитание

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

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

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

Табельный номер	Фамилия	Зарплата
2	Петров	2000
3	Сидоров	3000

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

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

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

,

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

,

таких, что , .

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

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

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

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

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

Номер поставщика	Наименование поставщика
1	Иванов
2	Петров
3	Сидоров

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

Номер детали	Наименование детали
1	Болт
2	Гайка
3	Винт

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

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

Номер поставщика	Наименование поставщика	Номер детали	Наименование детали
1	Иванов	1	Болт
1	Иванов	2	Гайка
1	Иванов	3	Винт
2	Петров	1	Болт
2	Петров	2	Гайка
2	Петров	3	Винт
3	Сидоров	1	Болт
3	Сидоров	2	Гайка
3	Сидоров	3	Винт

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

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

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

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

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

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

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

,

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

Табельный номер	Фамилия	Зарплата
1	Иванов	1000
2	Петров	2000
3	Сидоров	3000

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

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

Табельный номер	Фамилия	Зарплата
1	Иванов	1000
2	Петров	2000

НОМ_ВЕЩЕСТВА	ВЕЩЕСТВО
1	Дезоксирибонуклеиновая кислота
2	Бензин

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

НОМ_ЭЛЕМЕНТА	ЭЛЕМЕНТ
1	Водород
2	Гелий
…	…
105	…

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

НОМ_ВЕЩЕСТВА	НОМ_ЭЛЕМЕНТА	ПРОЦЕНТ
1	1	5
1	2	3
1	105	0.01
2	1	50

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

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

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

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

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

ТАБ_НОМ	ФАМИЛИЯ	ДОЛЖНОСТЬ	ТАБ_НОМ_РУК
1	Иванов	Директор	1
2	Петров	Глав.бухгалтер	1
3	Сидоров	Бухгалтер	2
4	Васильев	Начальник цеха	1
5	Сухов	Мастер	4
6	Шарипов	Рабочий	5
…	…	…	…

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

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

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

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

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

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

Товар	Месяц	Количество
Компьютеры	Январь	100
Принтеры	Январь	200
Сканеры	Январь	300
Компьютеры	Февраль	150
Принтеры	Февраль	250
Сканеры	Февраль	350
…	…	…

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

Товар	Январь	Февраль	…
Компьютеры	100	150	…
Принтеры	200	250	…
Сканеры	300	350	…

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

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

Выводы

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

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

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

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

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

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

Источник