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

Определения

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

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

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

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

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

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

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

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

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

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

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

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

Кортеж

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

Схема БД

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

$$R_1, ..., R_n$$ - совокупность атрибутов.

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

Пример:

$$A = (A_1, A_2, A_3, A_4)$$

и две схемы: $$R_1 = (A_1, A_2)$ и $R_2 = (A_1, A_3, A_4)$$

Так как $$R_1\bigcup R_2 = A$$, то $$\rho = (R_1, R_2)$$.

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

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

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

и есть одна схема $$\rho = R_1 = A$$

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

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

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

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

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

$$R_1 = ($$идентификатор, адрес$$)$$

$$R_2 = ($$товар, цена$$)$$

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

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

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

$$R=R_1\bigcup R_2$$

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

$$A_1$$ $$A_2$$ $$R_1$$ 1 2 3 4

$$A_1$$ $$A_2$$ $$R_2$$ 5 6 1 2

	$$A_1$$	$$A_2$$
$$R$$	1	2
	3	4
	5	6

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

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

$$R = R_1\bigcap R_2$$

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

$$A_1$$ $$A_2$$ $$R_1$$ 1 2 3 4

$$A_1$$ $$A_2$$ $$R_2$$ 5 6 1 2

	$$A_1$$	$$A_2$$
$$R$$	1	2

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

$$R = R_1 - R_2$$

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

$$A_1$$ $$A_2$$ $$R_1$$ 1 2 3 4

$$A_1$$ $$A_2$$ $$R_2$$ 5 6 1 2

	$$A_1$$	$$A_2$$
$$R$$	3	4

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

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

$$t = R \times S$$

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

$$A_1$$ $$A_2$$ $$R$$ 1 2 3 4

$$A_1$$ $$A_3$$ $$S$$ 5 6 7 8

	$$R.A_2$$	$$A_2$$	$$S.A_1$$	$$A_3$$
$$t$$	1	2	5	6
	1	2	7	8
	3	4	5	6
	3	4	7	8

Проекция

$$t=\Pi_{A_{i1} ... A_{ik} }(R)$$

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

	$$A_1$$	$$A_2$$	$$A_3$$	$$A_4$$
$$R$$	1	2	3	4
	7	8	9	10
	3	4	5	6
	3	4	7	6

	$$A_1$$	$$A_4$$
$$t = \Pi_{A_1, A_4}(R)$$	1	4
	7	10
	3	6

Селекция

$$t = \sigma_F(R)$$

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

	$$A_1$$	$$A_2$$
$$R$$	1	2
	9	8
	3	3

	$$A_1$$	$$A_4$$
$$t = \sigma_{A_1\leq A_2}(R)$$	1	2
	3	3

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

$$t = R\bowtie S$$

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

$$A_1$$ $$A_2$$ $$A_3$$ $$R$$ 1 2 3 4 6 7

$$A_1$$ $$A_2$$ $$A_4$$ $$A_5$$ $$S$$ 1 2 7 8 8 9 10 11 5 6 9 16

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

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

	$$R.A_1$$	$$R.A_2$$	$$A_3$$	$$S.A_1$$	$$S.A_2$$	$$A_4$$	$$A_5$$
$$t_1$$	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) выбрать из этого произведения кортежи по условию $$R.A_{i1} = S.A_{i1} ... R.A_{ik} = S.A_{ik}$$, где $$A_1 = A_k$$ - общие атрибуты в схемах отношений $$R$$ и $$S$$ (предполагается, что эти атрибуты занимают одинаковое положение в отношениях. Хотя не обязательно)

	$$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}$$, потому что они будут дублирующими.

	$$R.A_1$$	$$R.A_2$$	$$A_3$$	$$A_4$$	$$A_5$$
$$t_3$$	1	2	3	7	8
	4	6	7	9	16