какой операции нет в реляционной алгебре

МИГКУ ИТ-51вс

Метки

Добавить страницу

Реляционная алгебра — формальная система манипулирования отношениями в реляционной модели данных. [1]

Выборка

Операция выборки — унарный оператор, записываемый как σ_aθb(R) или σ_aθv(R), где:

Выборка σ_aθb(R) (или σ_aθv(R)) выбирает все наборы значений R, для которых функция a θ b (или a θ v) будет истинна.

Пример

Пусть даны следующие соотношения:

Имя	Возраст	Вес
Harry	34	80
Sally	28	64
George	29	70
Helena	54	54
Peter	34	80

Тогда результаты выборок будут следующими:

Имя	Возраст	Вес
Harry	34	80
Helena	54	54
Peter	34	80

Имя	Возраст	Вес
Helena	54	54

Проекция

Операция выборки — унарный оператор, записываемый как π_a1,…,an(R) где a₁,…,a_n — спиоск полей, подлежащих выборке. Результатом такой выборки будет набор последовательностей значений отношения R, в котором будут присутствовать только поля, перечисленные в списке a₁,…,a_n с естественным уничтожением потенциально возникающих кортежей-дубликатов[4].

Пример

Пусть даны следующие соотношения:

Имя	Возраст	Вес
Harry	34	80
Sally	28	64
George	29	70
Helena	54	54
Peter	34	80

Возраст	Вес
28	64
29	70
54	54
34	80

Объединение

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

Пример

Пусть даны следующие соотношения:

Имя	Возраст	Вес
Harry	34	80
Sally	28	64
George	29	70
Helena	54	54
Peter	34	80

Имя	Возраст	Вес
Daffy	24	19
Donald	25	23
Scrooge	81	27

Имя	Возраст	Вес
Harry	34	80
Sally	28	64
George	29	70
Helena	54	54
Peter	34	80
Daffy	24	19
Donald	25	23
Scrooge	81	27

Пересечение

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

Пример

Пусть даны следующие соотношения:

Имя	Возраст	Вес
Harry	34	80
Sally	28	64
George	29	70
Helena	54	54
Peter	34	80

Имя	Возраст	Вес
Daffy	24	19
George	29	70
Donald	25	23
Scrooge	81	27
Sally	28	64

Имя	Возраст	Вес
George	29	70
Sally	28	64

Разность

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

Пример

Пусть даны следующие соотношения:

Имя	Возраст	Вес
Harry	34	80
Sally	28	64
George	29	70
Helena	54	54
Peter	34	80

Имя	Возраст	Вес
Daffy	24	19
George	29	70
Donald	25	23
Scrooge	81	27
Sally	28	64

Имя	Возраст	Вес
Harry	34	80
Helena	54	54
Peter	34	80

Произведение

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

Пример

Пусть даны следующие соотношения:

Код_мульта	Название_мульта
0	The Simpsons
1	Family Guy
2	Duck Tales

Код_канала	Название_канала
0	СТС
1	2х2

Код_мульта	Название_мульта	Код_канала	Название_канала
0	The Simpsons	0	СТС
0	The Simpsons	1	2х2
1	Family Guy	0	СТС
1	Family Guy	1	2х2
2	Duck Tales	0	СТС
2	Duck Tales	1	2х2

Деление

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

Пример

Пусть даны следующие соотношения:

Код_мульта	Название_мульта	Название_канала
0	The Simpsons	RenTV
0	The Simpsons	2х2
0	The Simpsons	CTC
1	Family Guy	RenTV
1	Family Guy	2х2
2	Duck Tales	СТС
2	Duck Tales	2×2

Тогда при делении на таблицу каналов:

Название_канала
RenTV
2х2

Код_мульта	Название_мульта
0	The Simpsons
1	Family Guy

Family Guy и The Simpsons — мультфильмы, которые показывались и на RenTV и на 2×2 (условие во второй таблице). При этом Duck Tales не показывалось по RenTV, потому был исключён из результирующей таблицы.

Эквивалентный SQL-запрос привести затрудняюсь

Соединение

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

Пример

Код_мульта	Название_мульта	Название_канала
0	The Simpsons	2х2
1	Family Guy	2х2
2	Duck Tales	RenTV

Код_канала	Частота
RenTV	3,1415
2х2	783,25

Соединим их с выборкой σ_{Название_канала = Код_канала}(Произведение)
Первый этап, произведение:

Код_мульта	Название_мульта	Название_канала	Код_канала	Частота
0	The Simpsons	2х2	RenTV	3,1415
0	The Simpsons	2х2	2х2	783,25
1	Family Guy	2х2	RenTV	3,1415
1	Family Guy	2х2	2х2	783,25
2	Duck Tales	RenTV	RenTV	3,1415
2	Duck Tales	RenTV	2х2	783,25

Второй этап, выборка σ_{Название_канала = Код_канала}(Произведение):

Источник

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

Реляционная алгебра базируется на теории множеств и является основой логики работы баз данных.
Когда я только изучал устройство баз данных и 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 Печеньки ООО ”Темная сторона” 190 123 OOO “Дарт” 156 Чай ООО ”Темная сторона” 60 156 ОАО ”Ведро” 123 Печеньки ООО ”Темная сторона” 190 156 ОАО ”Ведро” 156 Чай ООО ”Темная сторона” 60 123 OOO “Дарт”}

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

Источник

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

Что такое реляционная алгебра

Операция выборки

,

Запрос SQL

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

R3
A1	A2	A3	A4
3	hh	yl	ms
4	pp	a1	sr
1	rr	yl	ms

Просматриваем столбец А3 и устанавливаем, что предикату A3>’d0′ удовлетворяют записи в первой и третьей строках исходного отношения (так как номер буквы y в алфавите больше номера буквы d). В результате получаем следующее новое отношение, в котором две строки:

R
A1	A2	A3	A4
3	hh	yl	ms
1	rr	yl	ms

Комбинировать всевозможные логические условия для выборок Вам поможет материал «Булева алгебра (алгебра логики)».

А в материалах раздела «Программирование PHP/MySQL» Вы найдёт немало примеров комбинаций различных логических условий для выборок из базы данных.

Операция проекции

Запрос SQL

Пусть вновь дано то же отношение R3 :

R3
A1	A2	A3	A4
3	hh	yl	ms
4	pp	a1	sr
1	rr	yl	ms

R
A4	A3
ms	yl
sr	a1

Операция объединения

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

Запрос SQL

R1			R2
A1	A2	A3	A1	A2	A3
Z7	aa	w11	X8	pp	k21
B7	hh	h15	Q2	ee	h15
X8	pp	w11	X8	pp	w11

R
A1	A2	A3
Z7	aa	w11
B7	hh	h15
X8	pp	w11
X8	pp	k21
Q2	ee	h15

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

Операция пересечения

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

Запрос SQL

В некоторых диалектах SQL отсутствует ключевое слово INTERSECT. Поэтому, например, в MySQL и других, операция пересечения множеств может реализована с применением предиката EXISTS.

Теперь посмотрим, что получится в результате выполнения этой операции реляционной алгебры и соответствующего ей запроса SQL. Вновь даны два отношения R1 и R2:

R1			R2
A1	A2	A3	A1	A2	A3
Z7	aa	w11	X8	pp	k21
B7	hh	h15	Q2	ee	h15
X8	pp	w11	X8	pp	w11

R
A1	A2	A3
X8	pp	w11

Операция разности

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

Запрос SQL

Установим, что получится в результате выполнения этой операции реляционной алгебры и соответствующего ей запроса SQL. Вновь даны два отношения R1 и R2:

R1			R2
A1	A2	A3	A1	A2	A3
Z7	aa	w11	X8	pp	k21
B7	hh	h15	Q2	ee	h15
X8	pp	w11	X8	pp	w11

R
A1	A2	A3
X8	pp	w11
Q2	ee	h15

В некоторых диалектах SQL отсутствует ключевое слово EXCEPT. Поэтому, например, в MySQL и других, операция пересечения множеств может реализована с применением предиката NOT EXISTS.

Операция декартова произведения

Операция декартова произведения () определяет новое отношение R, которое является результатом конкатенации каждого кортежа отношения R1 с каждым кортежем отношения R2.

Запрос SQL

Установим, что получится в результате выполнения этой операции реляционной алгебры и соответствующего ей запроса SQL. Даны два отношения R3 и R4:

R3				R4
A1	A2	A3	A4	A5	A6
3	hh	yl	ms	3	hh
4	pp	a1	sr	4	pp
1	rr	yl	ms

В новом отношении должны присутствовать все атрибуты (столбцы) двух отношений. Сначала первая строка отношения R3 сцепляется с каждой из двух строк отношения R4, затем вторая строка отношения R3, затем третья. В результате должно получиться 3 Х 2 = 6 кортежей (строк). Получаем такое новое отношение:

R
A1	A2	A3	A4	A5	A6
3	hh	yl	ms	3	hh
3	hh	yl	ms	4	pp
4	pp	a1	sr	3	hh
4	pp	a1	sr	4	pp
1	rr	yl	ms	3	hh
1	rr	yl	ms	4	pp

Операция деления

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

Запрос SQL

Давайте посмотрим, что получится в результате выполнения этой операции реляционной алгебры и соответствующего ей запроса SQL. Даны два отношения R5 и R6:

R5				R6
A1	A2	A3	A4	A2	A3
2	S3	4	sun	R4	8
3	X8	7	kab	X8	7
3	R4	8	kab

Комбинации всех кортежей отношения R6 соответствуют вторая и третья строки отношения R5. Но после исключения атрибутов (столбцов) А2 и А3 эти строки становятся идентичными. Поэтому в новом отношении присутствует эта строка один раз. Новое отношение:

Операция тета-соединения

Запрос SQL

Посмотрим, что получится в результате выполнения этой операции реляционной алгебры и соответствующего ей запроса SQL. Даны два отношения R3 и R4:

R3				R4
A1	A2	A3	A4	A5	A6
3	hh	yl	ms	3	hh
4	pp	a1	sr	4	pp
1	rr	yl	ms

Источник