ТОРА (9) - Лекция №1 - Операции реляционной алгебры: различия между версиями
(не показано 8 промежуточных версий 5 участников) | |||
Строка 34: | Строка 34: | ||
Любая одна строка в таблице экземпляра отношения. | Любая одна строка в таблице экземпляра отношения. | ||
Не допускается наличие двух одинаковых кортежей. | |||
=== Схема БД === | === Схема БД === | ||
Строка 49: | Строка 50: | ||
и две схемы: {{Формула|f=R_1 = (A_1, A_2)$ и $R_2 = (A_1, A_3, A_4)}} | и две схемы: {{Формула|f=R_1 = (A_1, A_2)$ и $R_2 = (A_1, A_3, A_4)}} | ||
Так как {{Формула|f=R_1\bigcup R_2 = A}}, то {{Формула|f=\rho = (R_1, R_2)}}. | Так как {{Формула|f=R_1\bigcup R_2 = A}} ({{Формула|f=\bigcup\limits^{n}_{i=1} {R_i} = A}}), то {{Формула|f=\rho = (R_1, R_2)}}. | ||
== Примеры схем БД == | == Примеры схем БД == | ||
Строка 72: | Строка 73: | ||
{{Формула|f=R_1 = (}}идентификатор, адрес{{Формула|f=)}} | {{Формула|f=R_1 = (}}идентификатор, адрес{{Формула|f=)}} | ||
{{Формула|f=R_2 = (}}товар, цена{{Формула|f=)}} | {{Формула|f=R_2 = (}}имя, товар, цена{{Формула|f=)}} | ||
Во второй схеме отношений атрибут Имя необходиим для поддержания ссылочной целостности. Для ее поддержания в пакете ERWin используется макрос PARENT UPDATE CASCADE. В то же время, желательно от ссылочной целостности избавляться. Это реализуется при помощи синтетических ключей. | |||
Схема {{Формула|f=\rho = (R_1, R_2)}} находится в 3НФ и не обладает перечисленными выше недостатками. | Схема {{Формула|f=\rho = (R_1, R_2)}} находится в 3НФ и не обладает перечисленными выше недостатками. | ||
Строка 215: | Строка 218: | ||
{| class="wikitable" | {| class="wikitable" | ||
! !!{{Формула|f=R. | ! !!{{Формула|f=R.A_1}} !! {{Формула|f=A_2}} !! {{Формула|f=S.A_1}} !! {{Формула|f=A_3}} | ||
|- align="center" | |- align="center" | ||
! rowspan="4" | {{Формула|f=t}} | ! rowspan="4" | {{Формула|f=t}} | ||
Строка 308: | Строка 311: | ||
| 8 || 9 || 10 || 11 | | 8 || 9 || 10 || 11 | ||
|- align="center" | |- align="center" | ||
| | | 4 || 6 || 9 || 16 | ||
|} | |} | ||
|} | |} | ||
Строка 333: | Строка 336: | ||
|} | |} | ||
:2) выбрать из этого произведения кортежи по условию {{Формула|f=R.A_{i1} = S.A_{i1} ... R.A_{ik} = S.A_{ik} }}, где {{Формула|f= | :2) выбрать из этого произведения кортежи по условию {{Формула|f=R.A_{i1} = S.A_{i1} ... R.A_{ik} = S.A_{ik} }}, где {{Формула|f=A_i ... A_k}} - общие атрибуты в схемах отношений {{Формула|f=R}} и {{Формула|f=S}} (предполагается, что эти атрибуты занимают одинаковое положение в отношениях. Хотя не обязательно) | ||
{| class="wikitable" | {| class="wikitable" |
Текущая версия от 16:56, 7 сентября 2017
Определения
Схема отношения
Это поименованная совокупность атрибутов.
$$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 |