ТОРА (9) - Лекция №1 - Операции реляционной алгебры: различия между версиями
м (переименовал ТОРА (9) - Лекция №1 в ТОРА (9) - Лекция №1 - Операции реляционной алгебры) |
ILobster (обсуждение | вклад) Нет описания правки |
||
Строка 1: | Строка 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. | |||
=== Экземпляр отношения === | |||
Конкретная таблица с данной схемой отношения. | |||
{| class="wikitable" | |||
! Идентификатор !! Адрес !! Товар !! Цена | |||
|- align="center" | |||
| ОАО "Х" || Ленина, 2 || сахар || 40 | |||
|- align="center" | |||
| ОАО "У" || Комсомола, 25 || соль || 5 | |||
|} | |||
=== Кортеж === | |||
Любая одна строка в таблице экземпляра отношения. | |||
=== Схема БД.=== | |||
<math>А</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><br> | |||
и две схемы: <math>R_1 = (A_1, A_2)</math> и <math>R_2 = (A_1, A_3, A_4)</math><br> | |||
Так как <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> | |||
Данная схема БД обладает следующими недостатками (аномалиями): | |||
* избыточность. Адрес поставщика повторяется для каждого поставляемого им товара; | |||
* потенциальная противоречивость. Если у поставщика меняется адрес, то его необходимо изменить во всех кортежах, в которые он входит; | |||
* аномалия включения кортежа. В выбранном отношении R пара атрибутов идентификатор-товар является ключом. При включении новой записи, атрибуты ключа не должны быть пустыми, поэтому в БД нельзя включить поставщика, если он в данный момент не поставляет товар; | |||
* аномалия удаления. При удалении всех товаров, поставляемых поставщиком, теряется информация о самом поставщике. | |||
Первопричиной этих недостатков является то, что R_1 не находится в 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НФ и не обладает перечисленными выше недостатками. | |||
== Основные операции реляционной алгебры == | |||
=== Объединение отношений === | |||
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= 1 2 | |||
3 4 | |||
5 6 | |||
=== Пересечение отношений === | |||
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= 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 \x 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_2 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=\заглавнаяпи_{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=\заглавнаяпи_{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 <= A_2} (R) = 1 2 | |||
3 3 | |||
=== Естественное соединение === | |||
t = R \|><| 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 | |||
Правило построения естественного соединения: | |||
* построить декартово произведение R \x 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 | |||
* выбрать из этого произведения кортежи по условию R.A_1=S.A_i1 ... R.A_k=S.A_ik, где A_1=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 | |||
* удалить из полученного отношения S.A_i1 ... S.A_ik, потому что они будут дублирующими | |||
A_1 A_2 A_3 A_4 A_5 | |||
t_3 = 1 2 3 7 8 | |||
4 6 7 9 16 | |||
[[Категория:Теоретические основы реляционной алгебры (9 семестр)|Л]] | [[Категория:Теоретические основы реляционной алгебры (9 семестр)|Л]] | ||
[[Категория:Конспекты лекций и семинаров]] | [[Категория:Конспекты лекций и семинаров]] |
Версия от 14:08, 3 сентября 2012
Определения
Схема отношения
Это поименованная совокупность атрибутов.
<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.
Экземпляр отношения
Конкретная таблица с данной схемой отношения.
Идентификатор | Адрес | Товар | Цена |
---|---|---|---|
ОАО "Х" | Ленина, 2 | сахар | 40 |
ОАО "У" | Комсомола, 25 | соль | 5 |
Кортеж
Любая одна строка в таблице экземпляра отношения.
Схема БД.
<math>А</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>
Данная схема БД обладает следующими недостатками (аномалиями):
- избыточность. Адрес поставщика повторяется для каждого поставляемого им товара;
- потенциальная противоречивость. Если у поставщика меняется адрес, то его необходимо изменить во всех кортежах, в которые он входит;
- аномалия включения кортежа. В выбранном отношении R пара атрибутов идентификатор-товар является ключом. При включении новой записи, атрибуты ключа не должны быть пустыми, поэтому в БД нельзя включить поставщика, если он в данный момент не поставляет товар;
- аномалия удаления. При удалении всех товаров, поставляемых поставщиком, теряется информация о самом поставщике.
Первопричиной этих недостатков является то, что R_1 не находится в 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НФ и не обладает перечисленными выше недостатками.
Основные операции реляционной алгебры
Объединение отношений
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= 1 2
3 4 5 6
Пересечение отношений
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= 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 \x 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_2 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=\заглавнаяпи_{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=\заглавнаяпи_{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 <= A_2} (R) = 1 2
3 3
Естественное соединение
t = R \|><| 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
Правило построения естественного соединения:
- построить декартово произведение R \x 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
- выбрать из этого произведения кортежи по условию R.A_1=S.A_i1 ... R.A_k=S.A_ik, где A_1=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
- удалить из полученного отношения S.A_i1 ... S.A_ik, потому что они будут дублирующими
A_1 A_2 A_3 A_4 A_5
t_3 = 1 2 3 7 8
4 6 7 9 16