Кафедра ИУ5 МГТУ им. Н.Э.Баумана, студенческое сообщество - Вклад [ru]

ТОРА (9) - Лекция №2 - Функциональные зависимости

2013-01-15T10:05:02Z

195.38.23.97: /* Алгоритм построения */

Функциональные зависимости, замыкание множества функциональных зависимостей, атрибутов.

== Функциональные зависимости ==

Пусть {{Формула|f=R=(A_1 ... A_n)}} является функциональной схемой отношения и {{Формула|f=X}}, {{Формула|f=Y}} - некоторые подмножества атрибутов этой схемы. Говорят, что {{Формула|f=X}} функционально определяет {{Формула|f=Y}} ({{Формула|f=X\rightarrow Y}}), если в любом экземпляре отношения со схемой {{Формула|f=R}} не существует двух кортежей, совпадающих по подмножеству {{Формула|f=X}} и не совпадающих по подмножеству {{Формула|f=Y}}

Иначе говоря, если два кортежа совпадают по {{Формула|f=x}}, то они должны совпадать и по {{Формула|f=y}}

Например, {{Формула|f=R=(A_1, A_2, A_3, A_4)}}, есть зависимости:
* {{Формула|f=A_1\rightarrow A_2}} (1)
* {{Формула|f=A_1A_3\rightarrow A_4}} (2)

Предположим, что имеет место один экземпляр отношения со схемой {{Формула|f=R}}

{| class="wikitable"
! !! {{Формула|f=A_1}} !! {{Формула|f=A_2}} !! {{Формула|f=A_3}} !! {{Формула|f=A_4}}
|- align="center"
| rowspan="3" | {{Формула|f=R}} || фирма X || улица Ленина, д.1 || сахар || 40
|- align="center"
| фирма X || улица Ленина, д.1 || карамель || 50
|- align="center"
| фирма X || улица Ленина, д.1 || пастила || 90
|}

Вторая ФЗ (2) имеет место быть, так как нет двух кортежей, совпадающих по этой паре. А первая ФЗ (1) не имеет место быть.

== Замыкание множества функциональных зависимостей ==

Пусть {{Формула|f=R}} - универсальная схема отношения, а {{Формула|f=F}} - исходное множество функциональной зависимости на этой схеме. Замыканием {{Формула|f=F}} называется всё множество функциональной зависимости, которое логически следует из {{Формула|f=F}} - обозначается как {{Формула|f=F^+}}

Функциональная зависимость логически следует из {{Формула|f=F}}, если её можно вывести (получить) с помощью аксиом Армстронга.

=== Аксиомы Армстронга ===

Или правила вывода функциональной зависимости. Существуют различные интерпретации аксиом, но все эквивалентны. Потому приведём только один вариант.

Аксиомы Армстронга являются надёжными и полными.

'''Надёжность''' - если ФЗ выводится с помощью аксиом Армстронга, то она справедлива во всех экземплярах отношения, где справедливы исходные ФЗ {{Формула|f=F}}

'''Полнота''' - если имеет место какая-либо ФЗ, то она обязательно может быть выведена с помощью аксиом Армстронга.

==== Рефлексивность ====

Если {{Формула|f=Y \subseteq X \subseteq R}}

то {{Формула|f=X\rightarrow Y}}. Тривиальная аксиома.

==== Дополнение ====

Если {{Формула|f=X\rightarrow Y}},

{{Формула|f=Z \subseteq R}} ({{Формула|f=Z}} может быть пустым),

тогда {{Формула|f=X\bigcup Y\rightarrow Y\bigcup Z}} или {{Формула|f=XZ\rightarrow YZ}}

==== Транзитивность ====

Если {{Формула|f=X\rightarrow Y}}

а {{Формула|f=Y\rightarrow Z}}

то {{Формула|f=X\rightarrow Z}}

=== Пример построения множества ФЗ ===

Пусть задана УСО (универсальная схема отношения) {{Формула|f=R=(A, B, C)}} и зависимости {{Формула|f=F=(A\rightarrow B, B\rightarrow C)}}

# {{Формула|f=A\rightarrow A}}, {{Формула|f=B\rightarrow B}}, {{Формула|f=C\rightarrow C}}, {{Формула|f=AB\rightarrow A}}, {{Формула|f=AB\rightarrow B}}, {{Формула|f=AC\rightarrow A}}, {{Формула|f=AC\rightarrow C}}, {{Формула|f=BC\rightarrow B}}, {{Формула|f=BC\rightarrow C}}, {{Формула|f=ABC\rightarrow A}}, {{Формула|f=ABC\rightarrow C}}, {{Формула|f=AB\rightarrow AB}}, {{Формула|f=AC\rightarrow AC}}, {{Формула|f=BC\rightarrow BC}}, {{Формула|f=ABC\rightarrow AB}}, {{Формула|f=ABC\rightarrow AC}}, {{Формула|f=ABC\rightarrow BC}}, {{Формула|f=ABC\rightarrow ABC}} 
# {{Формула|f=A\rightarrow AB}} (1ФЗ и пополняем A), {{Формула|f=AC\rightarrow BC}}, {{Формула|f=B\rightarrow BC}} (2 ФЗ и пополняем B), {{Формула|f=AB\rightarrow AC}}, {{Формула|f=AC\rightarrow ABC}}, {{Формула|f=AB\rightarrow ABC}}, {{Формула|f=AB\rightarrow BC}}, {{Формула|f=A\rightarrow AC}} 
# {{Формула|f=A\rightarrow C}} (1 и 2 ФЗ), {{Формула|f=A\rightarrow ABC}}

Всё, замыкание ({{Формула|f=F^+}}) построено. Все перечисленные зависимости образуют замыкание.

=== Лемма ===

Справедливы следующие правила. Для их доказательства необходимо пополнить ФЗ так, чтобы можно было использовать аксиомы.

==== Правило объединения ====

Если {{Формула|f=X\rightarrow Y}} и {{Формула|f=X\rightarrow Z}}, то {{Формула|f=X\rightarrow YZ}}

Доказательство:
# {{Формула|f=X\rightarrow XY}} (1 ФЗ и пополняем X);
# {{Формула|f=XY\rightarrow YZ}} (2 ФЗ и пополняем Y);
# {{Формула|f=X\rightarrow YZ}} (по аксиоме транзитивности).

==== Правило декомпозиции ====

Если {{Формула|f=X\rightarrow Y}}, а {{Формула|f=Z \subseteq Y}}, то {{Формула|f=X\rightarrow Z}}

Доказательство:
# {{Формула|f=X\rightarrow Y}} (по условию);
# {{Формула|f=Y\rightarrow Z}} (по аксиоме рефлексивности);
# {{Формула|f=X\rightarrow Z}} (по аксиоме транзитивности).

==== Правило псевдотранзитивности ====

Если {{Формула|f=X\rightarrow Y}} и {{Формула|f=WY\rightarrow Z}}, то {{Формула|f=WX\rightarrow Z}}

Доказательство:
# {{Формула|f=WX\rightarrow WY}} (1 ФЗ и пополняем W);
# {{Формула|f=WY\rightarrow Z}} (по условию);
# {{Формула|f=WX\rightarrow Z}} (по аксиоме транзитивности).

== Замыкание множества атрибутов ==

Замыкание {{Формула|f=F^+}} может включать в себя очень большое количество ФЗ. Например:

$F=(X\rightarrow A_1, X\rightarrow A_2 ... X\rightarrow A_n)$

{{Формула|f=X\rightarrow Y \subseteq F^+}}

{{Формула|f=Y \subseteq (A_1, A_2 ... A_n)}} и таких подмножеств может быть {{Формула|f=2^n}}

Поэтому "в лоб" замыкание {{Формула|f=F^+}} никто не строит. Но необходимо найти какой-то метод, который достаточно просто позволял бы выяснять, принадлежит ли произвольная ФЗ {{Формула|f=X\rightarrow Y}} к {{Формула|f=F^+}}

Для этого применяется ''замыкание множества атрибутов''. Пусть {{Формула|f=R}} - универсальная схема отношения, а {{Формула|f=X}} - некоторое подмножество атрибутов. Тогда замыканием множества атрибутов {{Формула|f=X^+}} называется совокупность атрибутов {{Формула|f=A_{i1}, A_{i2} ... A_{ik} }} таких, что {{Формула|f=X\rightarrow A_{i1}, X\rightarrow A_{i2} ... X\rightarrow A_{ik} }}

=== Алгоритм построения ===

Алгоритм является итерационной процедурой.

# полагаем {{Формула|f=i = 0}} и {{Формула|f=X_0^+=X}}, а {{Формула|f=X_i^+}} - замыкание множества атрибутов на i-том шаге;
# {{Формула|f=X _{i+1} ^+ = X _i ^+ \bigcup V}}, где V - такое множество атрибутов в F, что существует ФЗ {{Формула|f=Y\rightarrow Z}}, где {{Формула|f=Y \subseteq X _i ^+}}, {{Формула|f=V \subseteq Z}};
# если {{Формула|f=X_{i+1}^+ = X_i^+}}, то {{Формула|f=X^+ = X_i^+}}, иначе {{Формула|f=i = i + 1}} и возвращаемся в пункт 2.

==== Пример построения ====

Пусть {{Формула|f=R=(A, B, C, D, E, G)}}

{{Формула|f=F=(AB\rightarrow C, C\rightarrow A, BC\rightarrow D, ACD\rightarrow B, D\rightarrow EG, BE\rightarrow C, CG\rightarrow BD, CE\rightarrow AG)}}

{{Формула|f=X = BD}}

Надо построить {{Формула|f=X^+}}:

1) {{Формула|f=i = 0}}, {{Формула|f=X _0 ^+ = BD}}

2)

{| class="wikitable"
! {{Формула|f=i}} !! {{Формула|f=Y\rightarrow Z}}, для которых {{Формула|f=Y \subseteq X_i^+}} !! {{Формула|f=V\subseteq Z}} !! {{Формула|f=X_{i+1}^+ = X_i^+\bigcup V}}
|- align="center"
| 0 || {{Формула|f=D\rightarrow EG}} || {{Формула|f=EG}} || {{Формула|f=BDEG}}
|- align="center"
| 1 || {{Формула|f=BE\rightarrow C}} || {{Формула|f=C}} || {{Формула|f=BDEGC}}
|- align="center"
| 2 || {{Формула|f=C\rightarrow A}} {{Формула|f=BC\rightarrow D}} {{Формула|f=CG\rightarrow BD}} {{Формула|f=CE\rightarrow AG}} || {{Формула|f=A}} || {{Формула|f=BDEGCA}}
|- align="center"
| 3 || {{Формула|f=AB\rightarrow C}} {{Формула|f=ACD\rightarrow B}} || - || {{Формула|f=BDEGCA}}
|}

Получили, что {{Формула|f=X_4^+ = X_3^+}}, а значит {{Формула|f=X^+ = X_3^+ = BDEGCA}}

Это означает, что имеют место следующие ФЗ: $BD\rightarrow B$, {{Формула|f=BD\rightarrow D}}, {{Формула|f=BD\rightarrow E}}, {{Формула|f=BD\rightarrow G}}, {{Формула|f=BD\rightarrow C}}, {{Формула|f=BD\rightarrow A}}, и все они {{Формула|f=\subseteq F^+}}

Короче, чтобы проверить {{Формула|f=X\rightarrow Y \subseteq F^+}}, необходимо построить {{Формула|f=X^+}}

[[Категория:Теоретические основы реляционной алгебры (9 семестр)]]
[[Категория:Конспекты лекций и семинаров]]

ТОРА (9) - Лекция №2 - Функциональные зависимости

2013-01-15T10:04:40Z

195.38.23.97: /* Алгоритм построения */

Функциональные зависимости, замыкание множества функциональных зависимостей, атрибутов.

== Функциональные зависимости ==

Пусть {{Формула|f=R=(A_1 ... A_n)}} является функциональной схемой отношения и {{Формула|f=X}}, {{Формула|f=Y}} - некоторые подмножества атрибутов этой схемы. Говорят, что {{Формула|f=X}} функционально определяет {{Формула|f=Y}} ({{Формула|f=X\rightarrow Y}}), если в любом экземпляре отношения со схемой {{Формула|f=R}} не существует двух кортежей, совпадающих по подмножеству {{Формула|f=X}} и не совпадающих по подмножеству {{Формула|f=Y}}

Иначе говоря, если два кортежа совпадают по {{Формула|f=x}}, то они должны совпадать и по {{Формула|f=y}}

Например, {{Формула|f=R=(A_1, A_2, A_3, A_4)}}, есть зависимости:
* {{Формула|f=A_1\rightarrow A_2}} (1)
* {{Формула|f=A_1A_3\rightarrow A_4}} (2)

Предположим, что имеет место один экземпляр отношения со схемой {{Формула|f=R}}

{| class="wikitable"
! !! {{Формула|f=A_1}} !! {{Формула|f=A_2}} !! {{Формула|f=A_3}} !! {{Формула|f=A_4}}
|- align="center"
| rowspan="3" | {{Формула|f=R}} || фирма X || улица Ленина, д.1 || сахар || 40
|- align="center"
| фирма X || улица Ленина, д.1 || карамель || 50
|- align="center"
| фирма X || улица Ленина, д.1 || пастила || 90
|}

Вторая ФЗ (2) имеет место быть, так как нет двух кортежей, совпадающих по этой паре. А первая ФЗ (1) не имеет место быть.

== Замыкание множества функциональных зависимостей ==

Пусть {{Формула|f=R}} - универсальная схема отношения, а {{Формула|f=F}} - исходное множество функциональной зависимости на этой схеме. Замыканием {{Формула|f=F}} называется всё множество функциональной зависимости, которое логически следует из {{Формула|f=F}} - обозначается как {{Формула|f=F^+}}

Функциональная зависимость логически следует из {{Формула|f=F}}, если её можно вывести (получить) с помощью аксиом Армстронга.

=== Аксиомы Армстронга ===

Или правила вывода функциональной зависимости. Существуют различные интерпретации аксиом, но все эквивалентны. Потому приведём только один вариант.

Аксиомы Армстронга являются надёжными и полными.

'''Надёжность''' - если ФЗ выводится с помощью аксиом Армстронга, то она справедлива во всех экземплярах отношения, где справедливы исходные ФЗ {{Формула|f=F}}

'''Полнота''' - если имеет место какая-либо ФЗ, то она обязательно может быть выведена с помощью аксиом Армстронга.

==== Рефлексивность ====

Если {{Формула|f=Y \subseteq X \subseteq R}}

то {{Формула|f=X\rightarrow Y}}. Тривиальная аксиома.

==== Дополнение ====

Если {{Формула|f=X\rightarrow Y}},

{{Формула|f=Z \subseteq R}} ({{Формула|f=Z}} может быть пустым),

тогда {{Формула|f=X\bigcup Y\rightarrow Y\bigcup Z}} или {{Формула|f=XZ\rightarrow YZ}}

==== Транзитивность ====

Если {{Формула|f=X\rightarrow Y}}

а {{Формула|f=Y\rightarrow Z}}

то {{Формула|f=X\rightarrow Z}}

=== Пример построения множества ФЗ ===

Пусть задана УСО (универсальная схема отношения) {{Формула|f=R=(A, B, C)}} и зависимости {{Формула|f=F=(A\rightarrow B, B\rightarrow C)}}

# {{Формула|f=A\rightarrow A}}, {{Формула|f=B\rightarrow B}}, {{Формула|f=C\rightarrow C}}, {{Формула|f=AB\rightarrow A}}, {{Формула|f=AB\rightarrow B}}, {{Формула|f=AC\rightarrow A}}, {{Формула|f=AC\rightarrow C}}, {{Формула|f=BC\rightarrow B}}, {{Формула|f=BC\rightarrow C}}, {{Формула|f=ABC\rightarrow A}}, {{Формула|f=ABC\rightarrow C}}, {{Формула|f=AB\rightarrow AB}}, {{Формула|f=AC\rightarrow AC}}, {{Формула|f=BC\rightarrow BC}}, {{Формула|f=ABC\rightarrow AB}}, {{Формула|f=ABC\rightarrow AC}}, {{Формула|f=ABC\rightarrow BC}}, {{Формула|f=ABC\rightarrow ABC}} 
# {{Формула|f=A\rightarrow AB}} (1ФЗ и пополняем A), {{Формула|f=AC\rightarrow BC}}, {{Формула|f=B\rightarrow BC}} (2 ФЗ и пополняем B), {{Формула|f=AB\rightarrow AC}}, {{Формула|f=AC\rightarrow ABC}}, {{Формула|f=AB\rightarrow ABC}}, {{Формула|f=AB\rightarrow BC}}, {{Формула|f=A\rightarrow AC}} 
# {{Формула|f=A\rightarrow C}} (1 и 2 ФЗ), {{Формула|f=A\rightarrow ABC}}

Всё, замыкание ({{Формула|f=F^+}}) построено. Все перечисленные зависимости образуют замыкание.

=== Лемма ===

Справедливы следующие правила. Для их доказательства необходимо пополнить ФЗ так, чтобы можно было использовать аксиомы.

==== Правило объединения ====

Если {{Формула|f=X\rightarrow Y}} и {{Формула|f=X\rightarrow Z}}, то {{Формула|f=X\rightarrow YZ}}

Доказательство:
# {{Формула|f=X\rightarrow XY}} (1 ФЗ и пополняем X);
# {{Формула|f=XY\rightarrow YZ}} (2 ФЗ и пополняем Y);
# {{Формула|f=X\rightarrow YZ}} (по аксиоме транзитивности).

==== Правило декомпозиции ====

Если {{Формула|f=X\rightarrow Y}}, а {{Формула|f=Z \subseteq Y}}, то {{Формула|f=X\rightarrow Z}}

Доказательство:
# {{Формула|f=X\rightarrow Y}} (по условию);
# {{Формула|f=Y\rightarrow Z}} (по аксиоме рефлексивности);
# {{Формула|f=X\rightarrow Z}} (по аксиоме транзитивности).

==== Правило псевдотранзитивности ====

Если {{Формула|f=X\rightarrow Y}} и {{Формула|f=WY\rightarrow Z}}, то {{Формула|f=WX\rightarrow Z}}

Доказательство:
# {{Формула|f=WX\rightarrow WY}} (1 ФЗ и пополняем W);
# {{Формула|f=WY\rightarrow Z}} (по условию);
# {{Формула|f=WX\rightarrow Z}} (по аксиоме транзитивности).

== Замыкание множества атрибутов ==

Замыкание {{Формула|f=F^+}} может включать в себя очень большое количество ФЗ. Например:

$F=(X\rightarrow A_1, X\rightarrow A_2 ... X\rightarrow A_n)$

{{Формула|f=X\rightarrow Y \subseteq F^+}}

{{Формула|f=Y \subseteq (A_1, A_2 ... A_n)}} и таких подмножеств может быть {{Формула|f=2^n}}

Поэтому "в лоб" замыкание {{Формула|f=F^+}} никто не строит. Но необходимо найти какой-то метод, который достаточно просто позволял бы выяснять, принадлежит ли произвольная ФЗ {{Формула|f=X\rightarrow Y}} к {{Формула|f=F^+}}

Для этого применяется ''замыкание множества атрибутов''. Пусть {{Формула|f=R}} - универсальная схема отношения, а {{Формула|f=X}} - некоторое подмножество атрибутов. Тогда замыканием множества атрибутов {{Формула|f=X^+}} называется совокупность атрибутов {{Формула|f=A_{i1}, A_{i2} ... A_{ik} }} таких, что {{Формула|f=X\rightarrow A_{i1}, X\rightarrow A_{i2} ... X\rightarrow A_{ik} }}

=== Алгоритм построения ===

Алгоритм является итерационной процедурой.

# полагаем {{Формула|f=i = 0}} и {{Формула|f=X_0^+=X}}, а {{Формула|f=X_i^+}} - замыкание множества атрибутов на i-том шаге;
# {{Формула|f=X _{i+1} ^+ = X _i ^+ \bigcup V}}, где V - такое множество атрибутов в F, что существует ФЗ {{Формула|f=Y\rightarrow Z}}, {{Формула|f=Y \subseteq X _i ^+}}, {{Формула|f=V \subseteq Z}};
# если {{Формула|f=X_{i+1}^+ = X_i^+}}, то {{Формула|f=X^+ = X_i^+}}, иначе {{Формула|f=i = i + 1}} и возвращаемся в пункт 2.

==== Пример построения ====

Пусть {{Формула|f=R=(A, B, C, D, E, G)}}

{{Формула|f=F=(AB\rightarrow C, C\rightarrow A, BC\rightarrow D, ACD\rightarrow B, D\rightarrow EG, BE\rightarrow C, CG\rightarrow BD, CE\rightarrow AG)}}

{{Формула|f=X = BD}}

Надо построить {{Формула|f=X^+}}:

1) {{Формула|f=i = 0}}, {{Формула|f=X _0 ^+ = BD}}

2)

{| class="wikitable"
! {{Формула|f=i}} !! {{Формула|f=Y\rightarrow Z}}, для которых {{Формула|f=Y \subseteq X_i^+}} !! {{Формула|f=V\subseteq Z}} !! {{Формула|f=X_{i+1}^+ = X_i^+\bigcup V}}
|- align="center"
| 0 || {{Формула|f=D\rightarrow EG}} || {{Формула|f=EG}} || {{Формула|f=BDEG}}
|- align="center"
| 1 || {{Формула|f=BE\rightarrow C}} || {{Формула|f=C}} || {{Формула|f=BDEGC}}
|- align="center"
| 2 || {{Формула|f=C\rightarrow A}} {{Формула|f=BC\rightarrow D}} {{Формула|f=CG\rightarrow BD}} {{Формула|f=CE\rightarrow AG}} || {{Формула|f=A}} || {{Формула|f=BDEGCA}}
|- align="center"
| 3 || {{Формула|f=AB\rightarrow C}} {{Формула|f=ACD\rightarrow B}} || - || {{Формула|f=BDEGCA}}
|}

Получили, что {{Формула|f=X_4^+ = X_3^+}}, а значит {{Формула|f=X^+ = X_3^+ = BDEGCA}}

Это означает, что имеют место следующие ФЗ: $BD\rightarrow B$, {{Формула|f=BD\rightarrow D}}, {{Формула|f=BD\rightarrow E}}, {{Формула|f=BD\rightarrow G}}, {{Формула|f=BD\rightarrow C}}, {{Формула|f=BD\rightarrow A}}, и все они {{Формула|f=\subseteq F^+}}

Короче, чтобы проверить {{Формула|f=X\rightarrow Y \subseteq F^+}}, необходимо построить {{Формула|f=X^+}}

[[Категория:Теоретические основы реляционной алгебры (9 семестр)]]
[[Категория:Конспекты лекций и семинаров]]

ТОРА (9) - Лекция №1 - Операции реляционной алгебры

2013-01-15T08:32:42Z

195.38.23.97: /* Естественное соединение */

== Определения ==

=== Схема отношения ===

Это поименованная совокупность атрибутов.

{{Формула|f=R = (A_1, ..., A_n)}}, где {{Формула|f=A_i}} - некоторый атрибут из домена отношения.

{{Формула|f=R = (}}идентификатор поставщика, адрес, товар, цена{{Формула|f=)=(A_1, A_2, A_3, A_4)}}.

Здесь {{Формула|f=(A_1, A_3)}} - ключ, определяющий запись.

=== Степень схемы отношения ===

Это количество атрибутов в схеме.

Для {{Формула|f=R = (A_1, A_2, A_3, A_4)}} степень равна 4.

=== Экземпляр отношения ===

Это конкретная таблица с данной схемой отношения.

{{Формула|f=R = (}}идентификатор поставщика, адрес, товар, цена{{Формула|f=)}}.

{| class="wikitable"
! Идентификатор !! Адрес !! Товар !! Цена
|- align="center"
| ОАО "Х" || Ленина, 2 || сахар || 40
|- align="center"
| ОАО "У" || Комсомола, 25 || соль || 5
|}

=== Кортеж ===

Любая одна строка в таблице экземпляра отношения.

=== Схема БД ===

{{Формула|f=A}} - множество всех атрибутов некоторой предметной области (универсальная схема отношения).

{{Формула|f=R_1, ..., R_n}} - совокупность атрибутов.

Тогда {{Формула|f=\rho=(R_1, ..., R_n)}} называется схемой БД.

Пример:

{{Формула|f=A = (A_1, A_2, 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=A = (}}идентификатор поставщика, адрес, товар, цена{{Формула|f=)}}

и есть одна схема {{Формула|f=\rho = R_1 = A}}

Данная схема БД обладает следующими недостатками (аномалиями):
* избыточность. Адрес поставщика повторяется для каждого поставляемого им товара;
* потенциальная противоречивость. Если у поставщика меняется адрес, то его необходимо изменить во всех кортежах, в которые он входит;
* аномалия включения кортежа. В выбранном отношении {{Формула|f=R_1}} пара атрибутов идентификатор-товар является ключом. При включении новой записи, атрибуты ключа не должны быть пустыми, поэтому в БД нельзя включить поставщика, если он в данный момент не поставляет товар;
* аномалия удаления. При удалении всех товаров, поставляемых поставщиком, теряется информация о самом поставщике.
Первопричиной этих недостатков является то, что {{Формула|f=R_1}} не находится в {{Википедия|Третья_нормальная_форма|3НФ}}

=== Пример "хорошей" схемы БД ===

Пусть {{Формула|f=A = (}}идентификатор поставщика, адрес, товар, цена{{Формула|f=)}}

{{Формула|f=R_1 = (}}идентификатор, адрес{{Формула|f=)}}

{{Формула|f=R_2 = (}}товар, цена{{Формула|f=)}}

Схема {{Формула|f=\rho = (R_1, R_2)}} находится в 3НФ и не обладает перечисленными выше недостатками.

== Основные операции реляционной алгебры ==

=== Объединение отношений ===

{{Формула|f=R=R_1\bigcup R_2}}

Объединение отношений - это отношение, каждый кортеж которого принадлежит либо {{Формула|f=R_1}}, либо {{Формула|f=R_2}}.
{|
|
{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_2}}
|- align="center"
! rowspan="2" | {{Формула|f=R_1}}
| 1 || 2
|- align="center"
| 3 || 4
|}
|
{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_2}}
|- align="center"
! rowspan="2" | {{Формула|f=R_2}}
| 5 || 6
|- align="center"
| 1 || 2
|}
|}

{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_2}}
|- align="center"
! rowspan="3" | {{Формула|f=R}}
| 1 || 2
|- align="center"
| 3 || 4
|- align="center"
| 5 || 6
|}

Дублирование кортежей не допускается.

=== Пересечение отношений ===

{{Формула|f=R = R_1\bigcap R_2}}

Пересечение отношений - это отношение, каждый кортеж которого принадлежит и {{Формула|f=R_1}}, и {{Формула|f=R_2}}

{|
|
{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_2}}
|- align="center"
! rowspan="2" | {{Формула|f=R_1}}
| 1 || 2
|- align="center"
| 3 || 4
|}
|
{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_2}}
|- align="center"
! rowspan="2" | {{Формула|f=R_2}}
| 5 || 6
|- align="center"
| 1 || 2
|}
|}

{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_2}}
|- align="center"
! {{Формула|f=R}}
| 1 || 2
|}

=== Разность отношений ===

{{Формула|f=R = R_1 - R_2}}

Разность отношений - это отношение, кортежи которого принадлежат {{Формула|f=R_1}} и не принадлежат {{Формула|f=R_2}}

{|
|
{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_2}}
|- align="center"
! rowspan="2" | {{Формула|f=R_1}}
| 1 || 2
|- align="center"
| 3 || 4
|}
|
{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_2}}
|- align="center"
! rowspan="2" | {{Формула|f=R_2}}
| 5 || 6
|- align="center"
| 1 || 2
|}
|}

{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_2}}
|- align="center"
! {{Формула|f=R}}
| 3 || 4
|}

=== Декартово произведение ===

{{Формула|f=R, S}} - две схемы отношения со степенями {{Формула|f=k_1}} и {{Формула|f=k_2}}

{{Формула|f=t = R \times S}}

Декартово произведение - это отношение {{Формула|f=t}} со степенью {{Формула|f=k_1 + k_2}}, кортежи которого получаются {{Википедия|Конкатенация|конкатенацией}} кортежей из отношений {{Формула|f=R}} и {{Формула|f=S}}.

{|
|
{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_2}}
|- align="center"
! rowspan="2" | {{Формула|f=R}}
| 1 || 2
|- align="center"
| 3 || 4
|}
|
{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_3}}
|- align="center"
! rowspan="2" | {{Формула|f=S}}
| 5 || 6
|- align="center"
| 7 || 8
|}
|}

{| class="wikitable"
! !!{{Формула|f=R.A_2}} !! {{Формула|f=A_2}} !! {{Формула|f=S.A_1}} !! {{Формула|f=A_3}}
|- align="center"
! rowspan="4" | {{Формула|f=t}}
| 1 || 2 || 5 || 6
|- align="center"
| 1 || 2 || 7 || 8
|- align="center"
| 3 || 4 || 5 || 6
|- align="center"
| 3 || 4 || 7 || 8
|}

=== Проекция ===

{{Формула|f=t=\Pi_{A_{i1} ... A_{ik} }(R) }}

Проекция - это отношение, каждый кортеж которого состоит из значений атрибутов {{Формула|f=A_{i1} ... A_{ik} }} исходного отношения {{Формула|f=R}}.

{| class="wikitable"
! !! {{Формула|f=A_1}} !! {{Формула|f=A_2}} !! {{Формула|f=A_3}} !! {{Формула|f=A_4}}
|- align="center"
! rowspan="4" | {{Формула|f=R}}
| 1 || 2 || 3 || 4
|- align="center"
| 7 || 8 || 9 || 10
|- align="center"
| 3 || 4 || 5 || 6
|- align="center"
| 3 || 4 || 7 || 6
|}

{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_4}}
|- align="center"
! rowspan="3" | {{Формула|f=t = \Pi_{A_1, A_4}(R)}}
| 1 || 4
|- align="center"
| 7 || 10
|- align="center"
| 3 || 6
|}

=== Селекция ===

{{Формула|f=t = \sigma_F(R)}}

Селекция - это отношение, каждый кортеж которого принадлежит исходному отношению {{Формула|f=R}} и удовлетворяет логическому условию {{Формула|f=F}}.

{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_2}}
|- align="center"
! rowspan="3" | {{Формула|f=R}}
| 1 || 2
|- align="center"
| 9 || 8
|- align="center"
| 3 || 3
|}

{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_2}}
|- align="center"
! rowspan="2" | {{Формула|f=t = \sigma_{A_1\leq A_2}(R)}}
| 1 || 2
|- align="center"
| 3 || 3
|}

=== Естественное соединение ===

{{Формула|f=t = R\bowtie S}}

Определение этой операции следует из способа построения естественного соединения.

{|
| valign="top" |
{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_2}} !! {{Формула|f=A_3}}
|- align="center"
! rowspan="2" | {{Формула|f=R}}
| 1 || 2 || 3
|- align="center"
| 4 || 6 || 7
|}
| valign="top" |
{| class="wikitable" valign="top"
! !! {{Формула|f=A_1}} !! {{Формула|f=A_2}} !! {{Формула|f=A_4}} !! {{Формула|f=A_5}}
|- align="center"
! rowspan="3" | {{Формула|f=S}}
| 1 || 2 || 7 || 8
|- align="center"
| 8 || 9 || 10 || 11
|- align="center"
| 5 || 6 || 9 || 16
|}
|}

Построение естественного соединения:

:1) построить декартово произведение {{Формула|f=R\times S}}

{| class="wikitable"
! !! {{Формула|f=R.A_1}} !! {{Формула|f=R.A_2}} !! {{Формула|f=A_3}} !! {{Формула|f=S.A_1}} !! {{Формула|f=S.A_2}}!! {{Формула|f=A_4}} !! {{Формула|f=A_5}}
|- align="center"
! rowspan="6" | {{Формула|f=t_1}}
| 1 || 2 || 3 || 1 || 2 || 7 || 8
|- align="center"
| 1 || 2 || 3 || 8 || 9 || 10 || 11
|- align="center"
| 1 || 2 || 3 || 4 || 6 || 9 || 16
|- align="center"
| 4 || 6 || 7 || 1 || 2 || 7 || 8
|- align="center"
| 4 || 6 || 7 || 8 || 9 || 10 || 11
|- align="center"
| 4 || 6 || 7 || 4 || 6 || 9 || 16
|}

: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"
! !! {{Формула|f=R.A_1}} !! {{Формула|f=R.A_2}} !! {{Формула|f=A_3}} !! {{Формула|f=S.A_1}} !! {{Формула|f=S.A_2}}!! {{Формула|f=A_4}} !! {{Формула|f=A_5}}
|- align="center"
! rowspan="2" | {{Формула|f=t_2}}
| 1 || 2 || 3 || 1 || 2 || 7 || 8
|- align="center"
| 4 || 6 || 7 || 4 || 6 || 9 || 16
|}

:3) удалить из полученного отношения {{Формула|f=S.A_{i1} ... S.A_{ik} }}, потому что они будут дублирующими.

{| class="wikitable"
! !! {{Формула|f=R.A_1}} !! {{Формула|f=R.A_2}} !! {{Формула|f=A_3}} !! {{Формула|f=A_4}} !! {{Формула|f=A_5}}
|- align="center"
! rowspan="2" | {{Формула|f=t_3}}
| 1 || 2 || 3 || 7 || 8
|- align="center"
| 4 || 6 || 7 || 9 || 16
|}

[[Категория:Теоретические основы реляционной алгебры (9 семестр)]]
[[Категория:Конспекты лекций и семинаров]]

ТОРА (9) - Лекция №1 - Операции реляционной алгебры

2013-01-15T08:32:12Z

195.38.23.97: /* Естественное соединение */

== Определения ==

=== Схема отношения ===

Это поименованная совокупность атрибутов.

{{Формула|f=R = (A_1, ..., A_n)}}, где {{Формула|f=A_i}} - некоторый атрибут из домена отношения.

{{Формула|f=R = (}}идентификатор поставщика, адрес, товар, цена{{Формула|f=)=(A_1, A_2, A_3, A_4)}}.

Здесь {{Формула|f=(A_1, A_3)}} - ключ, определяющий запись.

=== Степень схемы отношения ===

Это количество атрибутов в схеме.

Для {{Формула|f=R = (A_1, A_2, A_3, A_4)}} степень равна 4.

=== Экземпляр отношения ===

Это конкретная таблица с данной схемой отношения.

{{Формула|f=R = (}}идентификатор поставщика, адрес, товар, цена{{Формула|f=)}}.

{| class="wikitable"
! Идентификатор !! Адрес !! Товар !! Цена
|- align="center"
| ОАО "Х" || Ленина, 2 || сахар || 40
|- align="center"
| ОАО "У" || Комсомола, 25 || соль || 5
|}

=== Кортеж ===

Любая одна строка в таблице экземпляра отношения.

=== Схема БД ===

{{Формула|f=A}} - множество всех атрибутов некоторой предметной области (универсальная схема отношения).

{{Формула|f=R_1, ..., R_n}} - совокупность атрибутов.

Тогда {{Формула|f=\rho=(R_1, ..., R_n)}} называется схемой БД.

Пример:

{{Формула|f=A = (A_1, A_2, 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=A = (}}идентификатор поставщика, адрес, товар, цена{{Формула|f=)}}

и есть одна схема {{Формула|f=\rho = R_1 = A}}

Данная схема БД обладает следующими недостатками (аномалиями):
* избыточность. Адрес поставщика повторяется для каждого поставляемого им товара;
* потенциальная противоречивость. Если у поставщика меняется адрес, то его необходимо изменить во всех кортежах, в которые он входит;
* аномалия включения кортежа. В выбранном отношении {{Формула|f=R_1}} пара атрибутов идентификатор-товар является ключом. При включении новой записи, атрибуты ключа не должны быть пустыми, поэтому в БД нельзя включить поставщика, если он в данный момент не поставляет товар;
* аномалия удаления. При удалении всех товаров, поставляемых поставщиком, теряется информация о самом поставщике.
Первопричиной этих недостатков является то, что {{Формула|f=R_1}} не находится в {{Википедия|Третья_нормальная_форма|3НФ}}

=== Пример "хорошей" схемы БД ===

Пусть {{Формула|f=A = (}}идентификатор поставщика, адрес, товар, цена{{Формула|f=)}}

{{Формула|f=R_1 = (}}идентификатор, адрес{{Формула|f=)}}

{{Формула|f=R_2 = (}}товар, цена{{Формула|f=)}}

Схема {{Формула|f=\rho = (R_1, R_2)}} находится в 3НФ и не обладает перечисленными выше недостатками.

== Основные операции реляционной алгебры ==

=== Объединение отношений ===

{{Формула|f=R=R_1\bigcup R_2}}

Объединение отношений - это отношение, каждый кортеж которого принадлежит либо {{Формула|f=R_1}}, либо {{Формула|f=R_2}}.
{|
|
{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_2}}
|- align="center"
! rowspan="2" | {{Формула|f=R_1}}
| 1 || 2
|- align="center"
| 3 || 4
|}
|
{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_2}}
|- align="center"
! rowspan="2" | {{Формула|f=R_2}}
| 5 || 6
|- align="center"
| 1 || 2
|}
|}

{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_2}}
|- align="center"
! rowspan="3" | {{Формула|f=R}}
| 1 || 2
|- align="center"
| 3 || 4
|- align="center"
| 5 || 6
|}

Дублирование кортежей не допускается.

=== Пересечение отношений ===

{{Формула|f=R = R_1\bigcap R_2}}

Пересечение отношений - это отношение, каждый кортеж которого принадлежит и {{Формула|f=R_1}}, и {{Формула|f=R_2}}

{|
|
{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_2}}
|- align="center"
! rowspan="2" | {{Формула|f=R_1}}
| 1 || 2
|- align="center"
| 3 || 4
|}
|
{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_2}}
|- align="center"
! rowspan="2" | {{Формула|f=R_2}}
| 5 || 6
|- align="center"
| 1 || 2
|}
|}

{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_2}}
|- align="center"
! {{Формула|f=R}}
| 1 || 2
|}

=== Разность отношений ===

{{Формула|f=R = R_1 - R_2}}

Разность отношений - это отношение, кортежи которого принадлежат {{Формула|f=R_1}} и не принадлежат {{Формула|f=R_2}}

{|
|
{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_2}}
|- align="center"
! rowspan="2" | {{Формула|f=R_1}}
| 1 || 2
|- align="center"
| 3 || 4
|}
|
{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_2}}
|- align="center"
! rowspan="2" | {{Формула|f=R_2}}
| 5 || 6
|- align="center"
| 1 || 2
|}
|}

{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_2}}
|- align="center"
! {{Формула|f=R}}
| 3 || 4
|}

=== Декартово произведение ===

{{Формула|f=R, S}} - две схемы отношения со степенями {{Формула|f=k_1}} и {{Формула|f=k_2}}

{{Формула|f=t = R \times S}}

Декартово произведение - это отношение {{Формула|f=t}} со степенью {{Формула|f=k_1 + k_2}}, кортежи которого получаются {{Википедия|Конкатенация|конкатенацией}} кортежей из отношений {{Формула|f=R}} и {{Формула|f=S}}.

{|
|
{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_2}}
|- align="center"
! rowspan="2" | {{Формула|f=R}}
| 1 || 2
|- align="center"
| 3 || 4
|}
|
{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_3}}
|- align="center"
! rowspan="2" | {{Формула|f=S}}
| 5 || 6
|- align="center"
| 7 || 8
|}
|}

{| class="wikitable"
! !!{{Формула|f=R.A_2}} !! {{Формула|f=A_2}} !! {{Формула|f=S.A_1}} !! {{Формула|f=A_3}}
|- align="center"
! rowspan="4" | {{Формула|f=t}}
| 1 || 2 || 5 || 6
|- align="center"
| 1 || 2 || 7 || 8
|- align="center"
| 3 || 4 || 5 || 6
|- align="center"
| 3 || 4 || 7 || 8
|}

=== Проекция ===

{{Формула|f=t=\Pi_{A_{i1} ... A_{ik} }(R) }}

Проекция - это отношение, каждый кортеж которого состоит из значений атрибутов {{Формула|f=A_{i1} ... A_{ik} }} исходного отношения {{Формула|f=R}}.

{| class="wikitable"
! !! {{Формула|f=A_1}} !! {{Формула|f=A_2}} !! {{Формула|f=A_3}} !! {{Формула|f=A_4}}
|- align="center"
! rowspan="4" | {{Формула|f=R}}
| 1 || 2 || 3 || 4
|- align="center"
| 7 || 8 || 9 || 10
|- align="center"
| 3 || 4 || 5 || 6
|- align="center"
| 3 || 4 || 7 || 6
|}

{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_4}}
|- align="center"
! rowspan="3" | {{Формула|f=t = \Pi_{A_1, A_4}(R)}}
| 1 || 4
|- align="center"
| 7 || 10
|- align="center"
| 3 || 6
|}

=== Селекция ===

{{Формула|f=t = \sigma_F(R)}}

Селекция - это отношение, каждый кортеж которого принадлежит исходному отношению {{Формула|f=R}} и удовлетворяет логическому условию {{Формула|f=F}}.

{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_2}}
|- align="center"
! rowspan="3" | {{Формула|f=R}}
| 1 || 2
|- align="center"
| 9 || 8
|- align="center"
| 3 || 3
|}

{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_2}}
|- align="center"
! rowspan="2" | {{Формула|f=t = \sigma_{A_1\leq A_2}(R)}}
| 1 || 2
|- align="center"
| 3 || 3
|}

=== Естественное соединение ===

{{Формула|f=t = R\bowtie S}}

Определение этой операции следует из способа построения естественного соединения.

{|
| valign="top" |
{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_2}} !! {{Формула|f=A_3}}
|- align="center"
! rowspan="2" | {{Формула|f=R}}
| 1 || 2 || 3
|- align="center"
| 4 || 6 || 7
|}
| valign="top" |
{| class="wikitable" valign="top"
! !! {{Формула|f=A_1}} !! {{Формула|f=A_2}} !! {{Формула|f=A_4}} !! {{Формула|f=A_5}}
|- align="center"
! rowspan="3" | {{Формула|f=S}}
| 1 || 2 || 7 || 8
|- align="center"
| 8 || 9 || 10 || 11
|- align="center"
| 5 || 6 || 9 || 16
|}
|}

Построение естественного соединения:

:1) построить декартово произведение {{Формула|f=R\times S}}

{| class="wikitable"
! !! {{Формула|f=R.A_1}} !! {{Формула|f=R.A_2}} !! {{Формула|f=A_3}} !! {{Формула|f=S.A_1}} !! {{Формула|f=S.A_2}}!! {{Формула|f=A_4}} !! {{Формула|f=A_5}}
|- align="center"
! rowspan="6" | {{Формула|f=t_1}}
| 1 || 2 || 3 || 1 || 2 || 7 || 8
|- align="center"
| 1 || 2 || 3 || 8 || 9 || 10 || 11
|- align="center"
| 1 || 2 || 3 || 4 || 6 || 9 || 16
|- align="center"
| 4 || 6 || 7 || 1 || 2 || 7 || 8
|- align="center"
| 4 || 6 || 7 || 8 || 9 || 10 || 11
|- align="center"
| 4 || 6 || 7 || 4 || 6 || 9 || 16
|}

:2) выбрать из этого произведения кортежи по условию {{Формула|f=R.A_{i1} = S.A_{i1} ... R.A_{ik} = S.A_{ik} }}, где {{Формула|f=A_{i1} ... A_{ik}}} - общие атрибуты в схемах отношений {{Формула|f=R}} и {{Формула|f=S}} (предполагается, что эти атрибуты занимают одинаковое положение в отношениях. Хотя не обязательно)

{| class="wikitable"
! !! {{Формула|f=R.A_1}} !! {{Формула|f=R.A_2}} !! {{Формула|f=A_3}} !! {{Формула|f=S.A_1}} !! {{Формула|f=S.A_2}}!! {{Формула|f=A_4}} !! {{Формула|f=A_5}}
|- align="center"
! rowspan="2" | {{Формула|f=t_2}}
| 1 || 2 || 3 || 1 || 2 || 7 || 8
|- align="center"
| 4 || 6 || 7 || 4 || 6 || 9 || 16
|}

:3) удалить из полученного отношения {{Формула|f=S.A_{i1} ... S.A_{ik} }}, потому что они будут дублирующими.

{| class="wikitable"
! !! {{Формула|f=R.A_1}} !! {{Формула|f=R.A_2}} !! {{Формула|f=A_3}} !! {{Формула|f=A_4}} !! {{Формула|f=A_5}}
|- align="center"
! rowspan="2" | {{Формула|f=t_3}}
| 1 || 2 || 3 || 7 || 8
|- align="center"
| 4 || 6 || 7 || 9 || 16
|}

[[Категория:Теоретические основы реляционной алгебры (9 семестр)]]
[[Категория:Конспекты лекций и семинаров]]

ТОРА (9) - Лекция №1 - Операции реляционной алгебры

2013-01-15T08:31:28Z

195.38.23.97: /* Естественное соединение */

== Определения ==

=== Схема отношения ===

Это поименованная совокупность атрибутов.

{{Формула|f=R = (A_1, ..., A_n)}}, где {{Формула|f=A_i}} - некоторый атрибут из домена отношения.

{{Формула|f=R = (}}идентификатор поставщика, адрес, товар, цена{{Формула|f=)=(A_1, A_2, A_3, A_4)}}.

Здесь {{Формула|f=(A_1, A_3)}} - ключ, определяющий запись.

=== Степень схемы отношения ===

Это количество атрибутов в схеме.

Для {{Формула|f=R = (A_1, A_2, A_3, A_4)}} степень равна 4.

=== Экземпляр отношения ===

Это конкретная таблица с данной схемой отношения.

{{Формула|f=R = (}}идентификатор поставщика, адрес, товар, цена{{Формула|f=)}}.

{| class="wikitable"
! Идентификатор !! Адрес !! Товар !! Цена
|- align="center"
| ОАО "Х" || Ленина, 2 || сахар || 40
|- align="center"
| ОАО "У" || Комсомола, 25 || соль || 5
|}

=== Кортеж ===

Любая одна строка в таблице экземпляра отношения.

=== Схема БД ===

{{Формула|f=A}} - множество всех атрибутов некоторой предметной области (универсальная схема отношения).

{{Формула|f=R_1, ..., R_n}} - совокупность атрибутов.

Тогда {{Формула|f=\rho=(R_1, ..., R_n)}} называется схемой БД.

Пример:

{{Формула|f=A = (A_1, A_2, 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=A = (}}идентификатор поставщика, адрес, товар, цена{{Формула|f=)}}

и есть одна схема {{Формула|f=\rho = R_1 = A}}

Данная схема БД обладает следующими недостатками (аномалиями):
* избыточность. Адрес поставщика повторяется для каждого поставляемого им товара;
* потенциальная противоречивость. Если у поставщика меняется адрес, то его необходимо изменить во всех кортежах, в которые он входит;
* аномалия включения кортежа. В выбранном отношении {{Формула|f=R_1}} пара атрибутов идентификатор-товар является ключом. При включении новой записи, атрибуты ключа не должны быть пустыми, поэтому в БД нельзя включить поставщика, если он в данный момент не поставляет товар;
* аномалия удаления. При удалении всех товаров, поставляемых поставщиком, теряется информация о самом поставщике.
Первопричиной этих недостатков является то, что {{Формула|f=R_1}} не находится в {{Википедия|Третья_нормальная_форма|3НФ}}

=== Пример "хорошей" схемы БД ===

Пусть {{Формула|f=A = (}}идентификатор поставщика, адрес, товар, цена{{Формула|f=)}}

{{Формула|f=R_1 = (}}идентификатор, адрес{{Формула|f=)}}

{{Формула|f=R_2 = (}}товар, цена{{Формула|f=)}}

Схема {{Формула|f=\rho = (R_1, R_2)}} находится в 3НФ и не обладает перечисленными выше недостатками.

== Основные операции реляционной алгебры ==

=== Объединение отношений ===

{{Формула|f=R=R_1\bigcup R_2}}

Объединение отношений - это отношение, каждый кортеж которого принадлежит либо {{Формула|f=R_1}}, либо {{Формула|f=R_2}}.
{|
|
{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_2}}
|- align="center"
! rowspan="2" | {{Формула|f=R_1}}
| 1 || 2
|- align="center"
| 3 || 4
|}
|
{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_2}}
|- align="center"
! rowspan="2" | {{Формула|f=R_2}}
| 5 || 6
|- align="center"
| 1 || 2
|}
|}

{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_2}}
|- align="center"
! rowspan="3" | {{Формула|f=R}}
| 1 || 2
|- align="center"
| 3 || 4
|- align="center"
| 5 || 6
|}

Дублирование кортежей не допускается.

=== Пересечение отношений ===

{{Формула|f=R = R_1\bigcap R_2}}

Пересечение отношений - это отношение, каждый кортеж которого принадлежит и {{Формула|f=R_1}}, и {{Формула|f=R_2}}

{|
|
{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_2}}
|- align="center"
! rowspan="2" | {{Формула|f=R_1}}
| 1 || 2
|- align="center"
| 3 || 4
|}
|
{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_2}}
|- align="center"
! rowspan="2" | {{Формула|f=R_2}}
| 5 || 6
|- align="center"
| 1 || 2
|}
|}

{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_2}}
|- align="center"
! {{Формула|f=R}}
| 1 || 2
|}

=== Разность отношений ===

{{Формула|f=R = R_1 - R_2}}

Разность отношений - это отношение, кортежи которого принадлежат {{Формула|f=R_1}} и не принадлежат {{Формула|f=R_2}}

{|
|
{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_2}}
|- align="center"
! rowspan="2" | {{Формула|f=R_1}}
| 1 || 2
|- align="center"
| 3 || 4
|}
|
{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_2}}
|- align="center"
! rowspan="2" | {{Формула|f=R_2}}
| 5 || 6
|- align="center"
| 1 || 2
|}
|}

{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_2}}
|- align="center"
! {{Формула|f=R}}
| 3 || 4
|}

=== Декартово произведение ===

{{Формула|f=R, S}} - две схемы отношения со степенями {{Формула|f=k_1}} и {{Формула|f=k_2}}

{{Формула|f=t = R \times S}}

Декартово произведение - это отношение {{Формула|f=t}} со степенью {{Формула|f=k_1 + k_2}}, кортежи которого получаются {{Википедия|Конкатенация|конкатенацией}} кортежей из отношений {{Формула|f=R}} и {{Формула|f=S}}.

{|
|
{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_2}}
|- align="center"
! rowspan="2" | {{Формула|f=R}}
| 1 || 2
|- align="center"
| 3 || 4
|}
|
{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_3}}
|- align="center"
! rowspan="2" | {{Формула|f=S}}
| 5 || 6
|- align="center"
| 7 || 8
|}
|}

{| class="wikitable"
! !!{{Формула|f=R.A_2}} !! {{Формула|f=A_2}} !! {{Формула|f=S.A_1}} !! {{Формула|f=A_3}}
|- align="center"
! rowspan="4" | {{Формула|f=t}}
| 1 || 2 || 5 || 6
|- align="center"
| 1 || 2 || 7 || 8
|- align="center"
| 3 || 4 || 5 || 6
|- align="center"
| 3 || 4 || 7 || 8
|}

=== Проекция ===

{{Формула|f=t=\Pi_{A_{i1} ... A_{ik} }(R) }}

Проекция - это отношение, каждый кортеж которого состоит из значений атрибутов {{Формула|f=A_{i1} ... A_{ik} }} исходного отношения {{Формула|f=R}}.

{| class="wikitable"
! !! {{Формула|f=A_1}} !! {{Формула|f=A_2}} !! {{Формула|f=A_3}} !! {{Формула|f=A_4}}
|- align="center"
! rowspan="4" | {{Формула|f=R}}
| 1 || 2 || 3 || 4
|- align="center"
| 7 || 8 || 9 || 10
|- align="center"
| 3 || 4 || 5 || 6
|- align="center"
| 3 || 4 || 7 || 6
|}

{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_4}}
|- align="center"
! rowspan="3" | {{Формула|f=t = \Pi_{A_1, A_4}(R)}}
| 1 || 4
|- align="center"
| 7 || 10
|- align="center"
| 3 || 6
|}

=== Селекция ===

{{Формула|f=t = \sigma_F(R)}}

Селекция - это отношение, каждый кортеж которого принадлежит исходному отношению {{Формула|f=R}} и удовлетворяет логическому условию {{Формула|f=F}}.

{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_2}}
|- align="center"
! rowspan="3" | {{Формула|f=R}}
| 1 || 2
|- align="center"
| 9 || 8
|- align="center"
| 3 || 3
|}

{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_2}}
|- align="center"
! rowspan="2" | {{Формула|f=t = \sigma_{A_1\leq A_2}(R)}}
| 1 || 2
|- align="center"
| 3 || 3
|}

=== Естественное соединение ===

{{Формула|f=t = R\bowtie S}}

Определение этой операции следует из способа построения естественного соединения.

{|
| valign="top" |
{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_2}} !! {{Формула|f=A_3}}
|- align="center"
! rowspan="2" | {{Формула|f=R}}
| 1 || 2 || 3
|- align="center"
| 4 || 6 || 7
|}
| valign="top" |
{| class="wikitable" valign="top"
! !! {{Формула|f=A_1}} !! {{Формула|f=A_2}} !! {{Формула|f=A_4}} !! {{Формула|f=A_5}}
|- align="center"
! rowspan="3" | {{Формула|f=S}}
| 1 || 2 || 7 || 8
|- align="center"
| 8 || 9 || 10 || 11
|- align="center"
| 5 || 6 || 9 || 16
|}
|}

Построение естественного соединения:

:1) построить декартово произведение {{Формула|f=R\times S}}

{| class="wikitable"
! !! {{Формула|f=R.A_1}} !! {{Формула|f=R.A_2}} !! {{Формула|f=A_3}} !! {{Формула|f=S.A_1}} !! {{Формула|f=S.A_2}}!! {{Формула|f=A_4}} !! {{Формула|f=A_5}}
|- align="center"
! rowspan="6" | {{Формула|f=t_1}}
| 1 || 2 || 3 || 1 || 2 || 7 || 8
|- align="center"
| 1 || 2 || 3 || 8 || 9 || 10 || 11
|- align="center"
| 1 || 2 || 3 || 4 || 6 || 9 || 16
|- align="center"
| 4 || 6 || 7 || 1 || 2 || 7 || 8
|- align="center"
| 4 || 6 || 7 || 8 || 9 || 10 || 11
|- align="center"
| 4 || 6 || 7 || 4 || 6 || 9 || 16
|}

:2) выбрать из этого произведения кортежи по условию {{Формула|f=R.A_{i1} = S.A_{i1} ... R.A_{ik} = S.A_{ik} }}, где {{Формула|f=A_i = A_i}} - общие атрибуты в схемах отношений {{Формула|f=R}} и {{Формула|f=S}} (предполагается, что эти атрибуты занимают одинаковое положение в отношениях. Хотя не обязательно)

{| class="wikitable"
! !! {{Формула|f=R.A_1}} !! {{Формула|f=R.A_2}} !! {{Формула|f=A_3}} !! {{Формула|f=S.A_1}} !! {{Формула|f=S.A_2}}!! {{Формула|f=A_4}} !! {{Формула|f=A_5}}
|- align="center"
! rowspan="2" | {{Формула|f=t_2}}
| 1 || 2 || 3 || 1 || 2 || 7 || 8
|- align="center"
| 4 || 6 || 7 || 4 || 6 || 9 || 16
|}

:3) удалить из полученного отношения {{Формула|f=S.A_{i1} ... S.A_{ik} }}, потому что они будут дублирующими.

{| class="wikitable"
! !! {{Формула|f=R.A_1}} !! {{Формула|f=R.A_2}} !! {{Формула|f=A_3}} !! {{Формула|f=A_4}} !! {{Формула|f=A_5}}
|- align="center"
! rowspan="2" | {{Формула|f=t_3}}
| 1 || 2 || 3 || 7 || 8
|- align="center"
| 4 || 6 || 7 || 9 || 16
|}

[[Категория:Теоретические основы реляционной алгебры (9 семестр)]]
[[Категория:Конспекты лекций и семинаров]]

ТОРА (9) - Лекция №1 - Операции реляционной алгебры

2013-01-15T08:29:33Z

195.38.23.97: /* Естественное соединение */

== Определения ==

=== Схема отношения ===

Это поименованная совокупность атрибутов.

{{Формула|f=R = (A_1, ..., A_n)}}, где {{Формула|f=A_i}} - некоторый атрибут из домена отношения.

{{Формула|f=R = (}}идентификатор поставщика, адрес, товар, цена{{Формула|f=)=(A_1, A_2, A_3, A_4)}}.

Здесь {{Формула|f=(A_1, A_3)}} - ключ, определяющий запись.

=== Степень схемы отношения ===

Это количество атрибутов в схеме.

Для {{Формула|f=R = (A_1, A_2, A_3, A_4)}} степень равна 4.

=== Экземпляр отношения ===

Это конкретная таблица с данной схемой отношения.

{{Формула|f=R = (}}идентификатор поставщика, адрес, товар, цена{{Формула|f=)}}.

{| class="wikitable"
! Идентификатор !! Адрес !! Товар !! Цена
|- align="center"
| ОАО "Х" || Ленина, 2 || сахар || 40
|- align="center"
| ОАО "У" || Комсомола, 25 || соль || 5
|}

=== Кортеж ===

Любая одна строка в таблице экземпляра отношения.

=== Схема БД ===

{{Формула|f=A}} - множество всех атрибутов некоторой предметной области (универсальная схема отношения).

{{Формула|f=R_1, ..., R_n}} - совокупность атрибутов.

Тогда {{Формула|f=\rho=(R_1, ..., R_n)}} называется схемой БД.

Пример:

{{Формула|f=A = (A_1, A_2, 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=A = (}}идентификатор поставщика, адрес, товар, цена{{Формула|f=)}}

и есть одна схема {{Формула|f=\rho = R_1 = A}}

Данная схема БД обладает следующими недостатками (аномалиями):
* избыточность. Адрес поставщика повторяется для каждого поставляемого им товара;
* потенциальная противоречивость. Если у поставщика меняется адрес, то его необходимо изменить во всех кортежах, в которые он входит;
* аномалия включения кортежа. В выбранном отношении {{Формула|f=R_1}} пара атрибутов идентификатор-товар является ключом. При включении новой записи, атрибуты ключа не должны быть пустыми, поэтому в БД нельзя включить поставщика, если он в данный момент не поставляет товар;
* аномалия удаления. При удалении всех товаров, поставляемых поставщиком, теряется информация о самом поставщике.
Первопричиной этих недостатков является то, что {{Формула|f=R_1}} не находится в {{Википедия|Третья_нормальная_форма|3НФ}}

=== Пример "хорошей" схемы БД ===

Пусть {{Формула|f=A = (}}идентификатор поставщика, адрес, товар, цена{{Формула|f=)}}

{{Формула|f=R_1 = (}}идентификатор, адрес{{Формула|f=)}}

{{Формула|f=R_2 = (}}товар, цена{{Формула|f=)}}

Схема {{Формула|f=\rho = (R_1, R_2)}} находится в 3НФ и не обладает перечисленными выше недостатками.

== Основные операции реляционной алгебры ==

=== Объединение отношений ===

{{Формула|f=R=R_1\bigcup R_2}}

Объединение отношений - это отношение, каждый кортеж которого принадлежит либо {{Формула|f=R_1}}, либо {{Формула|f=R_2}}.
{|
|
{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_2}}
|- align="center"
! rowspan="2" | {{Формула|f=R_1}}
| 1 || 2
|- align="center"
| 3 || 4
|}
|
{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_2}}
|- align="center"
! rowspan="2" | {{Формула|f=R_2}}
| 5 || 6
|- align="center"
| 1 || 2
|}
|}

{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_2}}
|- align="center"
! rowspan="3" | {{Формула|f=R}}
| 1 || 2
|- align="center"
| 3 || 4
|- align="center"
| 5 || 6
|}

Дублирование кортежей не допускается.

=== Пересечение отношений ===

{{Формула|f=R = R_1\bigcap R_2}}

Пересечение отношений - это отношение, каждый кортеж которого принадлежит и {{Формула|f=R_1}}, и {{Формула|f=R_2}}

{|
|
{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_2}}
|- align="center"
! rowspan="2" | {{Формула|f=R_1}}
| 1 || 2
|- align="center"
| 3 || 4
|}
|
{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_2}}
|- align="center"
! rowspan="2" | {{Формула|f=R_2}}
| 5 || 6
|- align="center"
| 1 || 2
|}
|}

{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_2}}
|- align="center"
! {{Формула|f=R}}
| 1 || 2
|}

=== Разность отношений ===

{{Формула|f=R = R_1 - R_2}}

Разность отношений - это отношение, кортежи которого принадлежат {{Формула|f=R_1}} и не принадлежат {{Формула|f=R_2}}

{|
|
{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_2}}
|- align="center"
! rowspan="2" | {{Формула|f=R_1}}
| 1 || 2
|- align="center"
| 3 || 4
|}
|
{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_2}}
|- align="center"
! rowspan="2" | {{Формула|f=R_2}}
| 5 || 6
|- align="center"
| 1 || 2
|}
|}

{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_2}}
|- align="center"
! {{Формула|f=R}}
| 3 || 4
|}

=== Декартово произведение ===

{{Формула|f=R, S}} - две схемы отношения со степенями {{Формула|f=k_1}} и {{Формула|f=k_2}}

{{Формула|f=t = R \times S}}

Декартово произведение - это отношение {{Формула|f=t}} со степенью {{Формула|f=k_1 + k_2}}, кортежи которого получаются {{Википедия|Конкатенация|конкатенацией}} кортежей из отношений {{Формула|f=R}} и {{Формула|f=S}}.

{|
|
{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_2}}
|- align="center"
! rowspan="2" | {{Формула|f=R}}
| 1 || 2
|- align="center"
| 3 || 4
|}
|
{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_3}}
|- align="center"
! rowspan="2" | {{Формула|f=S}}
| 5 || 6
|- align="center"
| 7 || 8
|}
|}

{| class="wikitable"
! !!{{Формула|f=R.A_2}} !! {{Формула|f=A_2}} !! {{Формула|f=S.A_1}} !! {{Формула|f=A_3}}
|- align="center"
! rowspan="4" | {{Формула|f=t}}
| 1 || 2 || 5 || 6
|- align="center"
| 1 || 2 || 7 || 8
|- align="center"
| 3 || 4 || 5 || 6
|- align="center"
| 3 || 4 || 7 || 8
|}

=== Проекция ===

{{Формула|f=t=\Pi_{A_{i1} ... A_{ik} }(R) }}

Проекция - это отношение, каждый кортеж которого состоит из значений атрибутов {{Формула|f=A_{i1} ... A_{ik} }} исходного отношения {{Формула|f=R}}.

{| class="wikitable"
! !! {{Формула|f=A_1}} !! {{Формула|f=A_2}} !! {{Формула|f=A_3}} !! {{Формула|f=A_4}}
|- align="center"
! rowspan="4" | {{Формула|f=R}}
| 1 || 2 || 3 || 4
|- align="center"
| 7 || 8 || 9 || 10
|- align="center"
| 3 || 4 || 5 || 6
|- align="center"
| 3 || 4 || 7 || 6
|}

{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_4}}
|- align="center"
! rowspan="3" | {{Формула|f=t = \Pi_{A_1, A_4}(R)}}
| 1 || 4
|- align="center"
| 7 || 10
|- align="center"
| 3 || 6
|}

=== Селекция ===

{{Формула|f=t = \sigma_F(R)}}

Селекция - это отношение, каждый кортеж которого принадлежит исходному отношению {{Формула|f=R}} и удовлетворяет логическому условию {{Формула|f=F}}.

{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_2}}
|- align="center"
! rowspan="3" | {{Формула|f=R}}
| 1 || 2
|- align="center"
| 9 || 8
|- align="center"
| 3 || 3
|}

{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_2}}
|- align="center"
! rowspan="2" | {{Формула|f=t = \sigma_{A_1\leq A_2}(R)}}
| 1 || 2
|- align="center"
| 3 || 3
|}

=== Естественное соединение ===

{{Формула|f=t = R\bowtie S}}

Определение этой операции следует из способа построения естественного соединения.

{|
| valign="top" |
{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_2}} !! {{Формула|f=A_3}}
|- align="center"
! rowspan="2" | {{Формула|f=R}}
| 1 || 2 || 3
|- align="center"
| 4 || 6 || 7
|}
| valign="top" |
{| class="wikitable" valign="top"
! !! {{Формула|f=A_1}} !! {{Формула|f=A_2}} !! {{Формула|f=A_4}} !! {{Формула|f=A_5}}
|- align="center"
! rowspan="3" | {{Формула|f=S}}
| 1 || 2 || 7 || 8
|- align="center"
| 8 || 9 || 10 || 11
|- align="center"
| 5 || 6 || 9 || 16
|}
|}

Построение естественного соединения:

:1) построить декартово произведение {{Формула|f=R\times S}}

{| class="wikitable"
! !! {{Формула|f=R.A_1}} !! {{Формула|f=R.A_2}} !! {{Формула|f=A_3}} !! {{Формула|f=S.A_1}} !! {{Формула|f=S.A_2}}!! {{Формула|f=A_4}} !! {{Формула|f=A_5}}
|- align="center"
! rowspan="6" | {{Формула|f=t_1}}
| 1 || 2 || 3 || 1 || 2 || 7 || 8
|- align="center"
| 1 || 2 || 3 || 8 || 9 || 10 || 11
|- align="center"
| 1 || 2 || 3 || 4 || 6 || 9 || 16
|- align="center"
| 4 || 6 || 7 || 1 || 2 || 7 || 8
|- align="center"
| 4 || 6 || 7 || 8 || 9 || 10 || 11
|- align="center"
| 4 || 6 || 7 || 4 || 6 || 9 || 16
|}

:2) выбрать из этого произведения кортежи по условию {{Формула|f=R.A_{i1} = S.A_{i1} ... R.A_{ik} = S.A_{ik} }}, где {{Формула|f=A_{i1} = A_{ik}}} - общие атрибуты в схемах отношений {{Формула|f=R}} и {{Формула|f=S}} (предполагается, что эти атрибуты занимают одинаковое положение в отношениях. Хотя не обязательно)

{| class="wikitable"
! !! {{Формула|f=R.A_1}} !! {{Формула|f=R.A_2}} !! {{Формула|f=A_3}} !! {{Формула|f=S.A_1}} !! {{Формула|f=S.A_2}}!! {{Формула|f=A_4}} !! {{Формула|f=A_5}}
|- align="center"
! rowspan="2" | {{Формула|f=t_2}}
| 1 || 2 || 3 || 1 || 2 || 7 || 8
|- align="center"
| 4 || 6 || 7 || 4 || 6 || 9 || 16
|}

:3) удалить из полученного отношения {{Формула|f=S.A_{i1} ... S.A_{ik} }}, потому что они будут дублирующими.

{| class="wikitable"
! !! {{Формула|f=R.A_1}} !! {{Формула|f=R.A_2}} !! {{Формула|f=A_3}} !! {{Формула|f=A_4}} !! {{Формула|f=A_5}}
|- align="center"
! rowspan="2" | {{Формула|f=t_3}}
| 1 || 2 || 3 || 7 || 8
|- align="center"
| 4 || 6 || 7 || 9 || 16
|}

[[Категория:Теоретические основы реляционной алгебры (9 семестр)]]
[[Категория:Конспекты лекций и семинаров]]

ТОРА (9) - Лекция №1 - Операции реляционной алгебры

2013-01-15T08:29:04Z

195.38.23.97: /* Естественное соединение */

== Определения ==

=== Схема отношения ===

Это поименованная совокупность атрибутов.

{{Формула|f=R = (A_1, ..., A_n)}}, где {{Формула|f=A_i}} - некоторый атрибут из домена отношения.

{{Формула|f=R = (}}идентификатор поставщика, адрес, товар, цена{{Формула|f=)=(A_1, A_2, A_3, A_4)}}.

Здесь {{Формула|f=(A_1, A_3)}} - ключ, определяющий запись.

=== Степень схемы отношения ===

Это количество атрибутов в схеме.

Для {{Формула|f=R = (A_1, A_2, A_3, A_4)}} степень равна 4.

=== Экземпляр отношения ===

Это конкретная таблица с данной схемой отношения.

{{Формула|f=R = (}}идентификатор поставщика, адрес, товар, цена{{Формула|f=)}}.

{| class="wikitable"
! Идентификатор !! Адрес !! Товар !! Цена
|- align="center"
| ОАО "Х" || Ленина, 2 || сахар || 40
|- align="center"
| ОАО "У" || Комсомола, 25 || соль || 5
|}

=== Кортеж ===

Любая одна строка в таблице экземпляра отношения.

=== Схема БД ===

{{Формула|f=A}} - множество всех атрибутов некоторой предметной области (универсальная схема отношения).

{{Формула|f=R_1, ..., R_n}} - совокупность атрибутов.

Тогда {{Формула|f=\rho=(R_1, ..., R_n)}} называется схемой БД.

Пример:

{{Формула|f=A = (A_1, A_2, 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=A = (}}идентификатор поставщика, адрес, товар, цена{{Формула|f=)}}

и есть одна схема {{Формула|f=\rho = R_1 = A}}

Данная схема БД обладает следующими недостатками (аномалиями):
* избыточность. Адрес поставщика повторяется для каждого поставляемого им товара;
* потенциальная противоречивость. Если у поставщика меняется адрес, то его необходимо изменить во всех кортежах, в которые он входит;
* аномалия включения кортежа. В выбранном отношении {{Формула|f=R_1}} пара атрибутов идентификатор-товар является ключом. При включении новой записи, атрибуты ключа не должны быть пустыми, поэтому в БД нельзя включить поставщика, если он в данный момент не поставляет товар;
* аномалия удаления. При удалении всех товаров, поставляемых поставщиком, теряется информация о самом поставщике.
Первопричиной этих недостатков является то, что {{Формула|f=R_1}} не находится в {{Википедия|Третья_нормальная_форма|3НФ}}

=== Пример "хорошей" схемы БД ===

Пусть {{Формула|f=A = (}}идентификатор поставщика, адрес, товар, цена{{Формула|f=)}}

{{Формула|f=R_1 = (}}идентификатор, адрес{{Формула|f=)}}

{{Формула|f=R_2 = (}}товар, цена{{Формула|f=)}}

Схема {{Формула|f=\rho = (R_1, R_2)}} находится в 3НФ и не обладает перечисленными выше недостатками.

== Основные операции реляционной алгебры ==

=== Объединение отношений ===

{{Формула|f=R=R_1\bigcup R_2}}

Объединение отношений - это отношение, каждый кортеж которого принадлежит либо {{Формула|f=R_1}}, либо {{Формула|f=R_2}}.
{|
|
{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_2}}
|- align="center"
! rowspan="2" | {{Формула|f=R_1}}
| 1 || 2
|- align="center"
| 3 || 4
|}
|
{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_2}}
|- align="center"
! rowspan="2" | {{Формула|f=R_2}}
| 5 || 6
|- align="center"
| 1 || 2
|}
|}

{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_2}}
|- align="center"
! rowspan="3" | {{Формула|f=R}}
| 1 || 2
|- align="center"
| 3 || 4
|- align="center"
| 5 || 6
|}

Дублирование кортежей не допускается.

=== Пересечение отношений ===

{{Формула|f=R = R_1\bigcap R_2}}

Пересечение отношений - это отношение, каждый кортеж которого принадлежит и {{Формула|f=R_1}}, и {{Формула|f=R_2}}

{|
|
{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_2}}
|- align="center"
! rowspan="2" | {{Формула|f=R_1}}
| 1 || 2
|- align="center"
| 3 || 4
|}
|
{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_2}}
|- align="center"
! rowspan="2" | {{Формула|f=R_2}}
| 5 || 6
|- align="center"
| 1 || 2
|}
|}

{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_2}}
|- align="center"
! {{Формула|f=R}}
| 1 || 2
|}

=== Разность отношений ===

{{Формула|f=R = R_1 - R_2}}

Разность отношений - это отношение, кортежи которого принадлежат {{Формула|f=R_1}} и не принадлежат {{Формула|f=R_2}}

{|
|
{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_2}}
|- align="center"
! rowspan="2" | {{Формула|f=R_1}}
| 1 || 2
|- align="center"
| 3 || 4
|}
|
{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_2}}
|- align="center"
! rowspan="2" | {{Формула|f=R_2}}
| 5 || 6
|- align="center"
| 1 || 2
|}
|}

{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_2}}
|- align="center"
! {{Формула|f=R}}
| 3 || 4
|}

=== Декартово произведение ===

{{Формула|f=R, S}} - две схемы отношения со степенями {{Формула|f=k_1}} и {{Формула|f=k_2}}

{{Формула|f=t = R \times S}}

Декартово произведение - это отношение {{Формула|f=t}} со степенью {{Формула|f=k_1 + k_2}}, кортежи которого получаются {{Википедия|Конкатенация|конкатенацией}} кортежей из отношений {{Формула|f=R}} и {{Формула|f=S}}.

{|
|
{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_2}}
|- align="center"
! rowspan="2" | {{Формула|f=R}}
| 1 || 2
|- align="center"
| 3 || 4
|}
|
{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_3}}
|- align="center"
! rowspan="2" | {{Формула|f=S}}
| 5 || 6
|- align="center"
| 7 || 8
|}
|}

{| class="wikitable"
! !!{{Формула|f=R.A_2}} !! {{Формула|f=A_2}} !! {{Формула|f=S.A_1}} !! {{Формула|f=A_3}}
|- align="center"
! rowspan="4" | {{Формула|f=t}}
| 1 || 2 || 5 || 6
|- align="center"
| 1 || 2 || 7 || 8
|- align="center"
| 3 || 4 || 5 || 6
|- align="center"
| 3 || 4 || 7 || 8
|}

=== Проекция ===

{{Формула|f=t=\Pi_{A_{i1} ... A_{ik} }(R) }}

Проекция - это отношение, каждый кортеж которого состоит из значений атрибутов {{Формула|f=A_{i1} ... A_{ik} }} исходного отношения {{Формула|f=R}}.

{| class="wikitable"
! !! {{Формула|f=A_1}} !! {{Формула|f=A_2}} !! {{Формула|f=A_3}} !! {{Формула|f=A_4}}
|- align="center"
! rowspan="4" | {{Формула|f=R}}
| 1 || 2 || 3 || 4
|- align="center"
| 7 || 8 || 9 || 10
|- align="center"
| 3 || 4 || 5 || 6
|- align="center"
| 3 || 4 || 7 || 6
|}

{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_4}}
|- align="center"
! rowspan="3" | {{Формула|f=t = \Pi_{A_1, A_4}(R)}}
| 1 || 4
|- align="center"
| 7 || 10
|- align="center"
| 3 || 6
|}

=== Селекция ===

{{Формула|f=t = \sigma_F(R)}}

Селекция - это отношение, каждый кортеж которого принадлежит исходному отношению {{Формула|f=R}} и удовлетворяет логическому условию {{Формула|f=F}}.

{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_2}}
|- align="center"
! rowspan="3" | {{Формула|f=R}}
| 1 || 2
|- align="center"
| 9 || 8
|- align="center"
| 3 || 3
|}

{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_2}}
|- align="center"
! rowspan="2" | {{Формула|f=t = \sigma_{A_1\leq A_2}(R)}}
| 1 || 2
|- align="center"
| 3 || 3
|}

=== Естественное соединение ===

{{Формула|f=t = R\bowtie S}}

Определение этой операции следует из способа построения естественного соединения.

{|
| valign="top" |
{| class="wikitable"
! !!{{Формула|f=A_1}} !! {{Формула|f=A_2}} !! {{Формула|f=A_3}}
|- align="center"
! rowspan="2" | {{Формула|f=R}}
| 1 || 2 || 3
|- align="center"
| 4 || 6 || 7
|}
| valign="top" |
{| class="wikitable" valign="top"
! !! {{Формула|f=A_1}} !! {{Формула|f=A_2}} !! {{Формула|f=A_4}} !! {{Формула|f=A_5}}
|- align="center"
! rowspan="3" | {{Формула|f=S}}
| 1 || 2 || 7 || 8
|- align="center"
| 8 || 9 || 10 || 11
|- align="center"
| 5 || 6 || 9 || 16
|}
|}

Построение естественного соединения:

:1) построить декартово произведение {{Формула|f=R\times S}}

{| class="wikitable"
! !! {{Формула|f=R.A_1}} !! {{Формула|f=R.A_2}} !! {{Формула|f=A_3}} !! {{Формула|f=S.A_1}} !! {{Формула|f=S.A_2}}!! {{Формула|f=A_4}} !! {{Формула|f=A_5}}
|- align="center"
! rowspan="6" | {{Формула|f=t_1}}
| 1 || 2 || 3 || 1 || 2 || 7 || 8
|- align="center"
| 1 || 2 || 3 || 8 || 9 || 10 || 11
|- align="center"
| 1 || 2 || 3 || 4 || 6 || 9 || 16
|- align="center"
| 4 || 6 || 7 || 1 || 2 || 7 || 8
|- align="center"
| 4 || 6 || 7 || 8 || 9 || 10 || 11
|- align="center"
| 4 || 6 || 7 || 4 || 6 || 9 || 16
|}

:2) выбрать из этого произведения кортежи по условию {{Формула|f=R.A_{i1} = S.A_{i1} ... R.A_{ik} = S.A_{ik} }}, где {{Формула|f=A_i1 = A_ik}} - общие атрибуты в схемах отношений {{Формула|f=R}} и {{Формула|f=S}} (предполагается, что эти атрибуты занимают одинаковое положение в отношениях. Хотя не обязательно)

{| class="wikitable"
! !! {{Формула|f=R.A_1}} !! {{Формула|f=R.A_2}} !! {{Формула|f=A_3}} !! {{Формула|f=S.A_1}} !! {{Формула|f=S.A_2}}!! {{Формула|f=A_4}} !! {{Формула|f=A_5}}
|- align="center"
! rowspan="2" | {{Формула|f=t_2}}
| 1 || 2 || 3 || 1 || 2 || 7 || 8
|- align="center"
| 4 || 6 || 7 || 4 || 6 || 9 || 16
|}

:3) удалить из полученного отношения {{Формула|f=S.A_{i1} ... S.A_{ik} }}, потому что они будут дублирующими.

{| class="wikitable"
! !! {{Формула|f=R.A_1}} !! {{Формула|f=R.A_2}} !! {{Формула|f=A_3}} !! {{Формула|f=A_4}} !! {{Формула|f=A_5}}
|- align="center"
! rowspan="2" | {{Формула|f=t_3}}
| 1 || 2 || 3 || 7 || 8
|- align="center"
| 4 || 6 || 7 || 9 || 16
|}

[[Категория:Теоретические основы реляционной алгебры (9 семестр)]]
[[Категория:Конспекты лекций и семинаров]]