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

Материал из Кафедра ИУ5 МГТУ им. Н.Э.Баумана, студенческое сообщество
Перейти к навигации Перейти к поиску

Определения

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

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

$$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$$ ($$\bigcup\limits^{n}_{i=1} {R_i} = A$$), то $$\rho = (R_1, R_2)$$.

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

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

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

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

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

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

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

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

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

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

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

Во второй схеме отношений атрибут Имя необходиим для поддержания ссылочной целостности. Для ее поддержания в пакете ERWin используется макрос PARENT UPDATE CASCADE. В то же время, желательно от ссылочной целостности избавляться. Это реализуется при помощи синтетических ключей.

Схема $$\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_1$$ $$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_2$$
$$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
4 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_i ... 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