ТОРА (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</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</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</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>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>
Определение этой операции следует из способа построения естественного соединения.
|
|
Построение естественного соединения:
- 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_{i1} = S.A_{i1} ... R.A_{ik} = S.A_{ik}</math>, где <math>A_1 = A_k</math> - общие атрибуты в схемах отношений <math>R</math> и <math>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_2</math> | 1 | 2 | 3 | 1 | 2 | 7 | 8 |
| 4 | 6 | 7 | 4 | 6 | 9 | 16 |
- 3) удалить из полученного отношения <math>S.A_{i1} ... S.A_{ik}</math>, потому что они будут дублирующими.
| <math>R.A_1</math> | <math>R.A_2</math> | <math>A_3</math> | <math>A_4</math> | <math>A_5</math> | |
|---|---|---|---|---|---|
| <math>t_3</math> | 1 | 2 | 3 | 7 | 8 |
| 4 | 6 | 7 | 9 | 16 |