ТОРА (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$ ($\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 | 2 |
| 3 | 4 | |
| 5 | 6 |
Дублирование кортежей не допускается.
Пересечение отношений
$R = R_1\bigcap R_2$
Пересечение отношений - это отношение, каждый кортеж которого принадлежит и $R_1$, и $R_2$
|
|
| $A_1$ | $A_2$ | |
|---|---|---|
| $R$ | 1 | 2 |
Разность отношений
$R = R_1 - R_2$
Разность отношений - это отношение, кортежи которого принадлежат $R_1$ и не принадлежат $R_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$.
|
|
| $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$
Определение этой операции следует из способа построения естественного соединения.
|
|
Построение естественного соединения:
- 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 |