ТОРА (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