ТОРА (9) - Лекция №1 - Операции реляционной алгебры

Определения

Схема отношения

Это поименованная совокупность атрибутов.

<math>R = (A_1, ..., A_n)</math>, где <math>A_i</math> - некоторый атрибут из домена отношения.

<math>R = (</math>идентификатор поставщика, адрес, товар, цена<math>)=(A_1, A_2, A_3, A_4)</math>.

Здесь <math>(A_1, A_3)</math> - ключ, определяющий запись.

Степень схемы отношения

Это количество атрибутов в схеме.

Для <math>R = (A_1, A_2, A_3, A_4)</math> степень равна 4.

Экземпляр отношения

Это конкретная таблица с данной схемой отношения.

<math>R = (</math>идентификатор поставщика, адрес, товар, цена<math>)</math>.

Идентификатор	Адрес	Товар	Цена
ОАО "Х"	Ленина, 2	сахар	40
ОАО "У"	Комсомола, 25	соль	5

Кортеж

Любая одна строка в таблице экземпляра отношения.

Схема БД.

<math>A</math> - множество всех атрибутов некоторой предметной области (универсальная схема отношения).

<math>R_1, ..., R_n</math> - совокупность атрибутов.

Тогда <math>\rho=(R_1, ..., R_n)</math> называется схемой БД.

Пример:

<math>A = (A_1, A_2, A_3, A_4)</math>

и две схемы: <math>R_1 = (A_1, A_2)</math> и <math>R_2 = (A_1, A_3, A_4)</math>

Так как <math>R_1\bigcup R_2 = A</math>, то <math>\rho = (R_1, R_2)</math>.

Примеры схем БД

Пример "плохой" схемы БД

Пусть <math>A = (</math>идентификатор поставщика, адрес, товар, цена<math>)</math>

и есть одна схема <math>\rho = R_1 = A</math>

Данная схема БД обладает следующими недостатками (аномалиями):

• избыточность. Адрес поставщика повторяется для каждого поставляемого им товара;
• потенциальная противоречивость. Если у поставщика меняется адрес, то его необходимо изменить во всех кортежах, в которые он входит;
• аномалия включения кортежа. В выбранном отношении <math>R</math> пара атрибутов идентификатор-товар является ключом. При включении новой записи, атрибуты ключа не должны быть пустыми, поэтому в БД нельзя включить поставщика, если он в данный момент не поставляет товар;
• аномалия удаления. При удалении всех товаров, поставляемых поставщиком, теряется информация о самом поставщике.

Первопричиной этих недостатков является то, что <math>R_1</math> не находится в 3НФ

Пример "хорошей" схемы БД

Пусть <math>A = (</math>идентификатор поставщика, адрес, товар, цена<math>)</math>

<math>R_1 = (</math>идентификатор, адрес<math>)</math>

<math>R_2 = (</math>товар, цена<math>)</math>

Схема <math>\rho = (R_1, R_2)</math> находится в 3НФ и не обладает перечисленными выше недостатками.

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

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

<math>R=R_1\bigcup R_2</math>

Объединение отношений - это отношение, каждый кортеж которого принадлежит либо <math>R_1</math>, либо <math>R_2</math>.

<math>A_1</math> <math>A_2</math> <math>R_1</math> 1 2 3 4

<math>A_1</math> <math>A_2</math> <math>R_2</math> 5 6 1 2

	<math>A_1</math>	<math>A_2</math>
<math>R</math>	1	2
	3	4
	5	6

Дублирование кортежей не допускается.

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

<math>R = R_1\bigcap R_2</math>

Пересечение отношений - это отношение, каждый кортеж которого принадлежит и <math>R_1</math>, и <math>R_2</math>

<math>A_1</math> <math>A_2</math> <math>R_1</math> 1 2 3 4

<math>A_1</math> <math>A_2</math> <math>R_2</math> 5 6 1 2

	<math>A_1</math>	<math>A_2</math>
<math>R</math>	1	2

Разность отношений

<math>R = R_1 - R_2</math>

Разность отношений - это отношение, кортежи которого принадлежат <math>R_1</math> и не принадлежат <math>R_2</math>

<math>A_1</math> <math>A_2</math> <math>R_1</math> 1 2 3 4

<math>A_1</math> <math>A_2</math> <math>R_2</math> 5 6 1 2

	<math>A_1</math>	<math>A_2</math>
<math>R</math>	3	4

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

<math>R, S</math> - две схемы отношения со степенями <math>k_1</math> и <math>k_2</math>

<math>t = R \times S</math>

Декартово произведение - это отношение <math>t</math> со степенью <math>k_1 + k_2</math>, кортежи которого получаются конкатенацией кортежей из отношений <math>R</math> и <math>S</math>.

<math>A_1</math> <math>A_2</math> <math>R</math> 1 2 3 4

<math>A_1</math> <math>A_3</math> <math>S</math> 5 6 7 8

	<math>R.A_2</math>	<math>A_2</math>	<math>S.A_1</math>	<math>A_3</math>
<math>t</math>	1	2	5	6
	1	2	7	8
	3	4	5	6
	3	4	7	8

Проекция

<math>t = \Pi_{A_{i1} ... A_{ik}}(R)</math>

Проекция - это отношение, каждый кортеж которого состоит из значений атрибутов <math>A_{i1} ... A_{ik}</math> исходного отношения <math>R</math>.

	<math>A_1</math>	<math>A_2</math>	<math>A_3</math>	<math>A_4</math>
<math>R</math>	1	2	3	4
	7	8	9	10
	3	4	5	6
	3	4	7	6

	<math>A_1</math>	<math>A_4</math>
<math>t = \Pi_{A_1, A_4}(R)</math>	1	4
	7	10
	3	6

Селекция

<math>t = \sigma_F(R)</math>

Селекция - это отношение, каждый кортеж которого принадлежит исходному отношению <math>R</math> и удовлетворяет логическому условию <math>F</math>.

	<math>A_1</math>	<math>A_2</math>
<math>R</math>	1	2
	9	8
	3	3

	<math>A_1</math>	<math>A_4</math>
<math>t = \sigma_{A_1\leq A_2}(R)</math>	1	2
	3	3

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

<math>t = R\vartriangleright\vartriangleleft S</math>

Определение этой операции следует из способа построения естественного соединения.

<math>A_1</math> <math>A_2</math> <math>A_3</math> <math>R</math> 1 2 3 4 6 7

<math>A_1</math> <math>A_2</math> <math>A_4</math> <math>A_5</math> <math>S</math> 1 2 7 8 8 9 10 11 5 6 9 16

Построение естественного соединения:

1) построить декартово произведение <math>R\times S</math>

	<math>R.A_1</math>	<math>R.A_2</math>	<math>A_3</math>	<math>S.A_1</math>	<math>S.A_2</math>	<math>A_4</math>	<math>A_5</math>
<math>t_1</math>	1	2	3	1	2	7	8
	1	2	3	8	9	10	11
	1	2	3	4	6	9	16
	4	6	7	1	2	7	8
	4	6	7	8	9	10	11
4	6	7	4	6	9	16

2) выбрать из этого произведения кортежи по условию <math>R.A_1 = S.A_{i1} ... R.A_k = S.A_{ik}</math>, где <math>A_1 = A_k</math> - общие атрибуты в схема отношений <math>R</math> и <math>S</math> (предполагается, что эти атрибуты занимают одинаковое положение в отношениях. Хотя не обязательно)

     R.A_1 R.A_2 A_3 S.A_1 S.A_2 A_4 A_5

t_2 = 1 2 3 1 2 7 8

      4     6     7    4     6    9   16

3) удалить из полученного отношения S.A_i1 ... S.A_ik, потому что они будут дублирующими

     A_1 A_2 A_3 A_4 A_5

t_3 = 1 2 3 7 8

      4   6   7   9   16