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

ТОРА (9) - Лекция №12 - Оценки (продолжение)

2013-01-08T13:36:40Z

94.79.44.124: /* Формулы оценки стоимости соединения NLJ */

{{Tabli4ka warning undone summary|text=   - схемы [[#Механизм сортировки таблиц | образования файлов со второго уровня и до последнего]]. А также не все [[#Формулы оценки стоимости соединения SMJ | формулы из раздела оценки SMJ]] верные.}}
{{Backward|l=ТОРА (9) - Лекция №11 - Оценки}}
Оригинал всего раздела, посвящённого оптимизации SQL-запросов, от самого [[Григорьев Ю.А. | Григорьева]] можно загрузить [http://yadi.sk/d/VjjMs6ww1HH2D здесь].
__TOC__
== Оптимизация SQL-запросов ==

=== Методы соединения таблиц ===

==== Метод вложенных циклов (NLJ, Nested Loop Join) ====

Каждая запись первой соединяемой таблицы сравнивается с каждой записью второй соединяемой таблицы. В общем случае, условие сравнения может быть произвольным.

[[Файл:9sTORAl11pic4.png|500px|center]]

Зависит от:

* используемого дерева соединения (но мы в дальнейшем всегда будем использовать левосторонние);
* назначения буферов ввода/вывода.

[[Файл:9sTORAl12pic1.png|600px|center]]

Если на 3 операции блоков будет больше {{Формула|f=b}}, то лишние сохраняются на диск.

===== Формулы оценки стоимости соединения NLJ =====

{{Формула|f=C^{JOIN} = C_{CPU} + C_{I/O} }}

{{Формула|f=C_{CPU}=T (Q_1)\cdot T(Q_2)\cdot C_{comp} }}

{{Формула|f=C_{I/O} = C_{I/O}(Q_2)\cdot\Bigl\lfloor\frac{B(Q_1)}{b}\Bigr\rfloor}}

здесь:

:{{Формула|f=T(Q_1)}}, {{Формула|f=T(Q_2)}} оценка числа записей в таблицах подзапросов {{Формула|f=Q_1}} и {{Формула|f=Q_2}};
:{{Формула|f=B(Q_1)}} - число блоков ввода/вывода для получения таблицы {{Формула|f=Q_1}};
:{{Формула|f=C_{I/O}(Q_2)}} - время ввода/вывода для получения таблицы {{Формула|f=Q_2}};
:{{Формула|f=b}} - число блоков в буферах 1 и 3 (''из рисунка выше'');
:{{Формула|f=C_{comp} }} - время сравнения двух кортежей из {{Формула|f=Q_1}} и {{Формула|f=Q_2}} в оперативной памяти;

:неполные квадратные скобки означают округление с недостатком, так как одно чтение с диска учитывается в стоимости выбора записей из исходных таблиц.

==== Метод сортировки слияния (SMJ, Sort Merge Join) ====

Соединение двух таблиц этим методом выполняется по следующим шагам:

# соединяемые таблицы сортируются по атрибуту соединения, будем обозначать его через {{Формула|f=a}};
# организуется вложенный цикл, где выполняется сравнение значения атрибута соединения в записях таблиц {{Формула|f=Q_1}} и {{Формула|f=Q_2}}. Условием соединения может быть только равенство атрибутов соединения.

Рассмотрим пример реализации второго шага.

Выполняется сравнение записей в таблицах {{Формула|f=Q_1}} и {{Формула|f=Q_2}}, на которые указывают указатели. Перемещение указателей выполняется следующим образом:

* если выполняется условие {{Формула|f=<}}, то указатель перемещается в таблицу {{Формула|f=Q_1}};
* если выполняется условие {{Формула|f=>}}, то указатель перемещается в таблицу {{Формула|f=Q_2}};
* если выполняется условие {{Формула|f==}}, то результат соединения перемещается в выходной буфер, указатели не перемещаются и выполняется сравнение со следующей записью из таблицы {{Формула|f=Q_2}}.

[[Файл:9sTORAl12pic2.png|500px|center]]

Результат соединения {{Формула|f=Q_1}} и {{Формула|f=Q_2}} получается уже отсортированным.

===== Формулы оценки стоимости соединения SMJ =====

{{Формула|f=C_{CPU} = [C^{SORT}_{CPU}(Q_1)] + [C^{SORT}_{CPU}(Q_2)] + C^{JOIN}_{CPU}(Q_1, Q_2)}}

{{Формула|f=C_{I/O} = [C^{SORT}_{I/O}(Q_1)] + [C^{SORT}_{I/O}(Q_2)] + C^{JOIN}_{I/O}(Q_1, Q_2)}}

{{Формула|f=C^{SORT}_{CPU}(R) = T(R)\cdot\log_b\Bigl(\frac{T(R)}{\lceil B(R)/b\rceil}\Bigr)\cdot (C_{comp} + C_{move}) + \Bigl(\log_b B(R) - 1\Bigr)\cdot T(R)\cdot (b\cdot C_{comp} + C_{move}) }}

{{Формула|f=C^{SORT}_{I/O}(R) = 2\cdot B(R)\cdot C_B}}

Далее возможны варианты:

* {{Формула|f=C^{JOIN}_{CPU}(Q_1, Q_2) = \Bigl(\Bigl(\frac{T(Q_2)}{Q_1, a} + 2\Bigr)\cdot T(Q_2) + T(Q_1)\cdot \Bigl(1 - \frac{I(Q_2, a)}{I(Q_1, a)}\Bigr)\Bigr)\cdot C_{comp} }}, если {{Формула|f=I(Q_1, a) > I(Q_2, a)}};

* {{Формула|f=C^{JOIN}_{CPU}(Q_1, Q_2) = \Bigl(\Bigl(\frac{T(Q_1)}{Q_2, a} + 2\Bigr)\cdot T(Q_1) + T(Q_2)\cdot \Bigl(1 - \frac{I(Q_1, a)}{I(Q_2, a)}\Bigr)\Bigr)\cdot C_{comp} }}, если {{Формула|f=I(Q_2, a) > I(Q_1, a)}}.

{{Формула|f=C^{JOIN}_{I/O} = [B(Q_1)] + [B(Q_2)] + \Bigl(\frac{T(Q_1)}{Q_2, a}\cdot \Bigl\lfloor \frac{B(Q_1)}{I(Q_2, a)\cdot b}\Bigr\rfloor\cdot b\cdot min(I(Q_1, a), I(Q_2, a)\Bigr)\cdot C_B}}

здесь:

:{{Формула|f=T(Q_1)}}, {{Формула|f=T(Q_2)}} - оценка числа записей в таблицах {{Формула|f=Q_1}} и {{Формула|f=Q_2}};
:{{Формула|f=B(Q_1)}}, {{Формула|f=B(Q_2)}} - оценка числа блоков в этих же таблицах;
:{{Формула|f=I(Q_1, a)}}, {{Формула|f=I(Q_2, a)}} - мощности атрибутов в соединении {{Формула|f=a}} тех же таблиц;
:{{Формула|f=b}} - число блоков в оперативной памяти, отводимое под сортировку этих таблиц, а также для выполнения соединения;
:{{Формула|f=C_{comp} }} - среднее время соединения двух кортежей из записей этих таблиц в оперативной памяти;
:{{Формула|f=C_{move} }} - время перемещения одной записи в оперативной памяти при сортировке;
:{{Формула|f=C_B}} - время чтения/записи одного блока на диск;
:верхние неполные квадратные скобки - округление с избытком;
:нижние неполные квадратные скобки - округление с недостатком;
:обычные квадратные скобки - необязательность, значит уже отсортировано.

===== Механизм сортировки таблиц =====

Механизм сортировки таблиц {{Формула|f=Q_1}} и {{Формула|f=Q_2}}:
# блоки таблицы {{Формула|f=R}} читаются в буфер и там сортируются. Получается файл, который сохраняется на диск;
# в буфер читаются ещё блоки.

Таким образом, на диске будет сохранено несколько файлов, и в каждом записи будут отсортированы. Эти файлы образуют первый уровень.

{{Формула|f=\frac{T(R)}{\lceil B(R) / b\rceil} }} - оценка числа записей в одном файле первого уровня.

{{Формула|f=\frac{T(R)}{\lceil B(R) / b\rceil}\cdot log_2\frac{T(R)}{\lceil B(R) / b\rceil} }} - число операций сравнений и перемещений записей при сортировке одного файла первого уровня. Но таких файлов {{Формула|f=\frac{B(R)}{b} }}. Перемножая их, получаем общее число операций.

В конце концов всё сложится в один файл.

{{Forward|l=ТОРА (9) - Лекция №13 - Оценки (продолжение)}}

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

ТОРА (9) - Лекция №12 - Оценки (продолжение)

2013-01-08T13:36:15Z

94.79.44.124: /* Формулы оценки стоимости соединения NLJ */

{{Tabli4ka warning undone summary|text=   - схемы [[#Механизм сортировки таблиц | образования файлов со второго уровня и до последнего]]. А также не все [[#Формулы оценки стоимости соединения SMJ | формулы из раздела оценки SMJ]] верные.}}
{{Backward|l=ТОРА (9) - Лекция №11 - Оценки}}
Оригинал всего раздела, посвящённого оптимизации SQL-запросов, от самого [[Григорьев Ю.А. | Григорьева]] можно загрузить [http://yadi.sk/d/VjjMs6ww1HH2D здесь].
__TOC__
== Оптимизация SQL-запросов ==

=== Методы соединения таблиц ===

==== Метод вложенных циклов (NLJ, Nested Loop Join) ====

Каждая запись первой соединяемой таблицы сравнивается с каждой записью второй соединяемой таблицы. В общем случае, условие сравнения может быть произвольным.

[[Файл:9sTORAl11pic4.png|500px|center]]

Зависит от:

* используемого дерева соединения (но мы в дальнейшем всегда будем использовать левосторонние);
* назначения буферов ввода/вывода.

[[Файл:9sTORAl12pic1.png|600px|center]]

Если на 3 операции блоков будет больше {{Формула|f=b}}, то лишние сохраняются на диск.

===== Формулы оценки стоимости соединения NLJ =====

{{Формула|f=C^{JOIN} = C_{CPU} + C_{I/O} }}

{{Формула|f=C_{CPU}=T {Q_1}\cdot T(Q_2)\cdot C_{comp} }}

{{Формула|f=C_{I/O} = C_{I/O}(Q_2)\cdot\Bigl\lfloor\frac{B(Q_1)}{b}\Bigr\rfloor}}

здесь:

:{{Формула|f=T(Q_1)}}, {{Формула|f=T(Q_2)}} оценка числа записей в таблицах подзапросов {{Формула|f=Q_1}} и {{Формула|f=Q_2}};
:{{Формула|f=B(Q_1)}} - число блоков ввода/вывода для получения таблицы {{Формула|f=Q_1}};
:{{Формула|f=C_{I/O}(Q_2)}} - время ввода/вывода для получения таблицы {{Формула|f=Q_2}};
:{{Формула|f=b}} - число блоков в буферах 1 и 3 (''из рисунка выше'');
:{{Формула|f=C_{comp} }} - время сравнения двух кортежей из {{Формула|f=Q_1}} и {{Формула|f=Q_2}} в оперативной памяти;

:неполные квадратные скобки означают округление с недостатком, так как одно чтение с диска учитывается в стоимости выбора записей из исходных таблиц.

==== Метод сортировки слияния (SMJ, Sort Merge Join) ====

Соединение двух таблиц этим методом выполняется по следующим шагам:

# соединяемые таблицы сортируются по атрибуту соединения, будем обозначать его через {{Формула|f=a}};
# организуется вложенный цикл, где выполняется сравнение значения атрибута соединения в записях таблиц {{Формула|f=Q_1}} и {{Формула|f=Q_2}}. Условием соединения может быть только равенство атрибутов соединения.

Рассмотрим пример реализации второго шага.

Выполняется сравнение записей в таблицах {{Формула|f=Q_1}} и {{Формула|f=Q_2}}, на которые указывают указатели. Перемещение указателей выполняется следующим образом:

* если выполняется условие {{Формула|f=<}}, то указатель перемещается в таблицу {{Формула|f=Q_1}};
* если выполняется условие {{Формула|f=>}}, то указатель перемещается в таблицу {{Формула|f=Q_2}};
* если выполняется условие {{Формула|f==}}, то результат соединения перемещается в выходной буфер, указатели не перемещаются и выполняется сравнение со следующей записью из таблицы {{Формула|f=Q_2}}.

[[Файл:9sTORAl12pic2.png|500px|center]]

Результат соединения {{Формула|f=Q_1}} и {{Формула|f=Q_2}} получается уже отсортированным.

===== Формулы оценки стоимости соединения SMJ =====

{{Формула|f=C_{CPU} = [C^{SORT}_{CPU}(Q_1)] + [C^{SORT}_{CPU}(Q_2)] + C^{JOIN}_{CPU}(Q_1, Q_2)}}

{{Формула|f=C_{I/O} = [C^{SORT}_{I/O}(Q_1)] + [C^{SORT}_{I/O}(Q_2)] + C^{JOIN}_{I/O}(Q_1, Q_2)}}

{{Формула|f=C^{SORT}_{CPU}(R) = T(R)\cdot\log_b\Bigl(\frac{T(R)}{\lceil B(R)/b\rceil}\Bigr)\cdot (C_{comp} + C_{move}) + \Bigl(\log_b B(R) - 1\Bigr)\cdot T(R)\cdot (b\cdot C_{comp} + C_{move}) }}

{{Формула|f=C^{SORT}_{I/O}(R) = 2\cdot B(R)\cdot C_B}}

Далее возможны варианты:

* {{Формула|f=C^{JOIN}_{CPU}(Q_1, Q_2) = \Bigl(\Bigl(\frac{T(Q_2)}{Q_1, a} + 2\Bigr)\cdot T(Q_2) + T(Q_1)\cdot \Bigl(1 - \frac{I(Q_2, a)}{I(Q_1, a)}\Bigr)\Bigr)\cdot C_{comp} }}, если {{Формула|f=I(Q_1, a) > I(Q_2, a)}};

* {{Формула|f=C^{JOIN}_{CPU}(Q_1, Q_2) = \Bigl(\Bigl(\frac{T(Q_1)}{Q_2, a} + 2\Bigr)\cdot T(Q_1) + T(Q_2)\cdot \Bigl(1 - \frac{I(Q_1, a)}{I(Q_2, a)}\Bigr)\Bigr)\cdot C_{comp} }}, если {{Формула|f=I(Q_2, a) > I(Q_1, a)}}.

{{Формула|f=C^{JOIN}_{I/O} = [B(Q_1)] + [B(Q_2)] + \Bigl(\frac{T(Q_1)}{Q_2, a}\cdot \Bigl\lfloor \frac{B(Q_1)}{I(Q_2, a)\cdot b}\Bigr\rfloor\cdot b\cdot min(I(Q_1, a), I(Q_2, a)\Bigr)\cdot C_B}}

здесь:

:{{Формула|f=T(Q_1)}}, {{Формула|f=T(Q_2)}} - оценка числа записей в таблицах {{Формула|f=Q_1}} и {{Формула|f=Q_2}};
:{{Формула|f=B(Q_1)}}, {{Формула|f=B(Q_2)}} - оценка числа блоков в этих же таблицах;
:{{Формула|f=I(Q_1, a)}}, {{Формула|f=I(Q_2, a)}} - мощности атрибутов в соединении {{Формула|f=a}} тех же таблиц;
:{{Формула|f=b}} - число блоков в оперативной памяти, отводимое под сортировку этих таблиц, а также для выполнения соединения;
:{{Формула|f=C_{comp} }} - среднее время соединения двух кортежей из записей этих таблиц в оперативной памяти;
:{{Формула|f=C_{move} }} - время перемещения одной записи в оперативной памяти при сортировке;
:{{Формула|f=C_B}} - время чтения/записи одного блока на диск;
:верхние неполные квадратные скобки - округление с избытком;
:нижние неполные квадратные скобки - округление с недостатком;
:обычные квадратные скобки - необязательность, значит уже отсортировано.

===== Механизм сортировки таблиц =====

Механизм сортировки таблиц {{Формула|f=Q_1}} и {{Формула|f=Q_2}}:
# блоки таблицы {{Формула|f=R}} читаются в буфер и там сортируются. Получается файл, который сохраняется на диск;
# в буфер читаются ещё блоки.

Таким образом, на диске будет сохранено несколько файлов, и в каждом записи будут отсортированы. Эти файлы образуют первый уровень.

{{Формула|f=\frac{T(R)}{\lceil B(R) / b\rceil} }} - оценка числа записей в одном файле первого уровня.

{{Формула|f=\frac{T(R)}{\lceil B(R) / b\rceil}\cdot log_2\frac{T(R)}{\lceil B(R) / b\rceil} }} - число операций сравнений и перемещений записей при сортировке одного файла первого уровня. Но таких файлов {{Формула|f=\frac{B(R)}{b} }}. Перемножая их, получаем общее число операций.

В конце концов всё сложится в один файл.

{{Forward|l=ТОРА (9) - Лекция №13 - Оценки (продолжение)}}

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

ТОРА (9) - Лекция №12 - Оценки (продолжение)

2013-01-08T13:35:43Z

94.79.44.124: /* Формулы оценки стоимости соединения NLJ */

{{Tabli4ka warning undone summary|text=   - схемы [[#Механизм сортировки таблиц | образования файлов со второго уровня и до последнего]]. А также не все [[#Формулы оценки стоимости соединения SMJ | формулы из раздела оценки SMJ]] верные.}}
{{Backward|l=ТОРА (9) - Лекция №11 - Оценки}}
Оригинал всего раздела, посвящённого оптимизации SQL-запросов, от самого [[Григорьев Ю.А. | Григорьева]] можно загрузить [http://yadi.sk/d/VjjMs6ww1HH2D здесь].
__TOC__
== Оптимизация SQL-запросов ==

=== Методы соединения таблиц ===

==== Метод вложенных циклов (NLJ, Nested Loop Join) ====

Каждая запись первой соединяемой таблицы сравнивается с каждой записью второй соединяемой таблицы. В общем случае, условие сравнения может быть произвольным.

[[Файл:9sTORAl11pic4.png|500px|center]]

Зависит от:

* используемого дерева соединения (но мы в дальнейшем всегда будем использовать левосторонние);
* назначения буферов ввода/вывода.

[[Файл:9sTORAl12pic1.png|600px|center]]

Если на 3 операции блоков будет больше {{Формула|f=b}}, то лишние сохраняются на диск.

===== Формулы оценки стоимости соединения NLJ =====

{{Формула|f=C^{JOIN} = C_{CPU} + C_{I/O} }}

{{Формула|f=C_{CPU}=C_{CPU}\cdot T(Q_2)\cdot C_{comp} }}

{{Формула|f=C_{I/O} = C_{I/O}(Q_2)\cdot\Bigl\lfloor\frac{B(Q_1)}{b}\Bigr\rfloor}}

здесь:

:{{Формула|f=T(Q_1)}}, {{Формула|f=T(Q_2)}} оценка числа записей в таблицах подзапросов {{Формула|f=Q_1}} и {{Формула|f=Q_2}};
:{{Формула|f=B(Q_1)}} - число блоков ввода/вывода для получения таблицы {{Формула|f=Q_1}};
:{{Формула|f=C_{I/O}(Q_2)}} - время ввода/вывода для получения таблицы {{Формула|f=Q_2}};
:{{Формула|f=b}} - число блоков в буферах 1 и 3 (''из рисунка выше'');
:{{Формула|f=C_{comp} }} - время сравнения двух кортежей из {{Формула|f=Q_1}} и {{Формула|f=Q_2}} в оперативной памяти;

:неполные квадратные скобки означают округление с недостатком, так как одно чтение с диска учитывается в стоимости выбора записей из исходных таблиц.

==== Метод сортировки слияния (SMJ, Sort Merge Join) ====

Соединение двух таблиц этим методом выполняется по следующим шагам:

# соединяемые таблицы сортируются по атрибуту соединения, будем обозначать его через {{Формула|f=a}};
# организуется вложенный цикл, где выполняется сравнение значения атрибута соединения в записях таблиц {{Формула|f=Q_1}} и {{Формула|f=Q_2}}. Условием соединения может быть только равенство атрибутов соединения.

Рассмотрим пример реализации второго шага.

Выполняется сравнение записей в таблицах {{Формула|f=Q_1}} и {{Формула|f=Q_2}}, на которые указывают указатели. Перемещение указателей выполняется следующим образом:

* если выполняется условие {{Формула|f=<}}, то указатель перемещается в таблицу {{Формула|f=Q_1}};
* если выполняется условие {{Формула|f=>}}, то указатель перемещается в таблицу {{Формула|f=Q_2}};
* если выполняется условие {{Формула|f==}}, то результат соединения перемещается в выходной буфер, указатели не перемещаются и выполняется сравнение со следующей записью из таблицы {{Формула|f=Q_2}}.

[[Файл:9sTORAl12pic2.png|500px|center]]

Результат соединения {{Формула|f=Q_1}} и {{Формула|f=Q_2}} получается уже отсортированным.

===== Формулы оценки стоимости соединения SMJ =====

{{Формула|f=C_{CPU} = [C^{SORT}_{CPU}(Q_1)] + [C^{SORT}_{CPU}(Q_2)] + C^{JOIN}_{CPU}(Q_1, Q_2)}}

{{Формула|f=C_{I/O} = [C^{SORT}_{I/O}(Q_1)] + [C^{SORT}_{I/O}(Q_2)] + C^{JOIN}_{I/O}(Q_1, Q_2)}}

{{Формула|f=C^{SORT}_{CPU}(R) = T(R)\cdot\log_b\Bigl(\frac{T(R)}{\lceil B(R)/b\rceil}\Bigr)\cdot (C_{comp} + C_{move}) + \Bigl(\log_b B(R) - 1\Bigr)\cdot T(R)\cdot (b\cdot C_{comp} + C_{move}) }}

{{Формула|f=C^{SORT}_{I/O}(R) = 2\cdot B(R)\cdot C_B}}

Далее возможны варианты:

* {{Формула|f=C^{JOIN}_{CPU}(Q_1, Q_2) = \Bigl(\Bigl(\frac{T(Q_2)}{Q_1, a} + 2\Bigr)\cdot T(Q_2) + T(Q_1)\cdot \Bigl(1 - \frac{I(Q_2, a)}{I(Q_1, a)}\Bigr)\Bigr)\cdot C_{comp} }}, если {{Формула|f=I(Q_1, a) > I(Q_2, a)}};

* {{Формула|f=C^{JOIN}_{CPU}(Q_1, Q_2) = \Bigl(\Bigl(\frac{T(Q_1)}{Q_2, a} + 2\Bigr)\cdot T(Q_1) + T(Q_2)\cdot \Bigl(1 - \frac{I(Q_1, a)}{I(Q_2, a)}\Bigr)\Bigr)\cdot C_{comp} }}, если {{Формула|f=I(Q_2, a) > I(Q_1, a)}}.

{{Формула|f=C^{JOIN}_{I/O} = [B(Q_1)] + [B(Q_2)] + \Bigl(\frac{T(Q_1)}{Q_2, a}\cdot \Bigl\lfloor \frac{B(Q_1)}{I(Q_2, a)\cdot b}\Bigr\rfloor\cdot b\cdot min(I(Q_1, a), I(Q_2, a)\Bigr)\cdot C_B}}

здесь:

:{{Формула|f=T(Q_1)}}, {{Формула|f=T(Q_2)}} - оценка числа записей в таблицах {{Формула|f=Q_1}} и {{Формула|f=Q_2}};
:{{Формула|f=B(Q_1)}}, {{Формула|f=B(Q_2)}} - оценка числа блоков в этих же таблицах;
:{{Формула|f=I(Q_1, a)}}, {{Формула|f=I(Q_2, a)}} - мощности атрибутов в соединении {{Формула|f=a}} тех же таблиц;
:{{Формула|f=b}} - число блоков в оперативной памяти, отводимое под сортировку этих таблиц, а также для выполнения соединения;
:{{Формула|f=C_{comp} }} - среднее время соединения двух кортежей из записей этих таблиц в оперативной памяти;
:{{Формула|f=C_{move} }} - время перемещения одной записи в оперативной памяти при сортировке;
:{{Формула|f=C_B}} - время чтения/записи одного блока на диск;
:верхние неполные квадратные скобки - округление с избытком;
:нижние неполные квадратные скобки - округление с недостатком;
:обычные квадратные скобки - необязательность, значит уже отсортировано.

===== Механизм сортировки таблиц =====

Механизм сортировки таблиц {{Формула|f=Q_1}} и {{Формула|f=Q_2}}:
# блоки таблицы {{Формула|f=R}} читаются в буфер и там сортируются. Получается файл, который сохраняется на диск;
# в буфер читаются ещё блоки.

Таким образом, на диске будет сохранено несколько файлов, и в каждом записи будут отсортированы. Эти файлы образуют первый уровень.

{{Формула|f=\frac{T(R)}{\lceil B(R) / b\rceil} }} - оценка числа записей в одном файле первого уровня.

{{Формула|f=\frac{T(R)}{\lceil B(R) / b\rceil}\cdot log_2\frac{T(R)}{\lceil B(R) / b\rceil} }} - число операций сравнений и перемещений записей при сортировке одного файла первого уровня. Но таких файлов {{Формула|f=\frac{B(R)}{b} }}. Перемножая их, получаем общее число операций.

В конце концов всё сложится в один файл.

{{Forward|l=ТОРА (9) - Лекция №13 - Оценки (продолжение)}}

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

ТОРА (9) - Лекция №6 - Алгоритм построения хорошей БД

2013-01-08T13:11:56Z

94.79.44.124: /* Нормальная форма Бойса-Кодда */

== Третья нормальная форма ==

=== Пример аномалий у 3НФ ===

{{Формула|f=R = (A, B, C, D)}} и {{Формула|f=F = (A\rightarrow B, B\rightarrow A, AC\rightarrow D)}}

Два ключа: {{Формула|f=AC}} и {{Формула|f=BC}}

{{Формула|f=(AC)^+=ACBD}}, {{Формула|f=(BC)^+=BCAD}}

{{Формула|f=A^+=AB}}, {{Формула|f=C^+ = C}}, {{Формула|f=B^+ = BA}}

Покажем, что в этом случае {{Формула|f=R}} находится в 3НФ:

1)

:неключевой атрибут {{Формула|f=H}}, {{Формула|f=H = D}}

2)

:{{Формула|f=Y\rightarrow H}}, {{Формула|f=H\notin Y}}, {{Формула|f=Y = AC}}

3)

:{{Формула|f=X = BC}}, {{Формула|f=X = AC}}

Нельзя подобрать нужную тройку, потому {{Формула|f=R}} находится в 3НФ. Однако, отношение всё равно обладает аномалиями:
* избыточности: наименование поставщика повторяется для каждой поставляемой делали;
* противоречивости при изменении наименования поставщика надо изменить его во всех записях, куда оно входит;
* включения: нельзя включить информацию о поставщике, если он ничего не поставляет;
* удаления: при удалении детали удаляется информация о поставщике.

Для устранения этого вводится усиленная 3НФ - Бойса-Кодда.

=== Нормальная форма Бойса-Кодда ===

ФЗ {{Формула|f=X\rightarrow Y}} является неприводимой, если для любого подмножества {{Формула|f=Z\subset X}} выполняется {{Формула|f=Z\nrightarrow Y}} или {{Формула|f=Z\rightarrow Y\notin F^+}}

Пусть есть отношение {{Формула|f=R}} и {{Формула|f=F}} включает в себя нетривиальные неприводимые ФЗ. Тогда отношение {{Формула|f=R}} находится в нормальной форме Бойса-Кодда, если для любого {{Формула|f=X\rightarrow Y\in F}} => {{Формула|f=X}} - ключ.

Пример:

{{Формула|f=R_1 = AB}}, {{Формула|f=F_1 = (A\rightarrow B, B\rightarrow A)}}, {{Формула|f=A}} - ключ, {{Формула|f=B}} - ключ.

или

{{Формула|f=R_2 = ACD}}, {{Формула|f=F_2 = (AC\rightarrow D)}}, {{Формула|f=AC}} - ключ.

== Алгоритм синтеза "хорошей" БД ==

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

Перед выполнением алгоритма можно привести все ФЗ к одному атрибуту в правой части (по свойству декомпозиции) и удалить лишние ФЗ. Но это не обязательно.

Алгоритм:

# построить УНП для {{Формула|f=F}};
# если среди ФЗ в УНП нет ФЗ, включающей все атрибуты из {{Формула|f=U}}, то добавить в УНП тривиальную ФЗ {{Формула|f=U\rightarrow\varnothing}}. Выполнение этого шага почти всегда обеспечивает свойство соединения без потерь будущей схемы БД;
# привести все нетривиальные ФЗ из УНП к неприводимому виду (удалить лишние атрибуты в левых частях ФЗ);
# разбить полученное множество ФЗ УНП на классы эквивалентности. Две зависимости {{Формула|f=X_i\rightarrow Y_i}} и {{Формула|f=X_j\rightarrow Y_j}} будем называть эквивалентными, если {{Формула|f=X_iY_i = X_jY_j}}. Далее введём обозначение {{Формула|f=K_r = X_iY_i}} - множество атрибутов в левой и правой частях ФЗ {{Формула|f=r}}-того класса эквивалентности;
# построить граф иерархии полученных на предыдущем шаге классов эквивалентности (если это возможно). Правило построения: {{Формула|f=j}}-ый узел соединяем снизу с {{Формула|f=i}}-ым узлом, если {{Формула|f=K_j\subset K_i}}. В каждом узле записываются все ФЗ, соответствующего класса эквивалентности;
# из каждого класса эквивалентности в графе иерархии оставить только одну ФЗ. Правила выбора:
## удалить из класса эквивалентности лишние ФЗ;
## если в классе эквивалентности осталось больше одной ФЗ, то выбрать ФЗ с меньшим числом атрибутов в левой части;
## если у оставшихся ФЗ число атрибутов в левой части одинаково, то выбрать ту ФЗ, которая позволит редуцировать (вычеркнуть) число атрибутов справа у ФЗ, расположенных выше в графе иерархии;
## если в результате не удалось выбрать ни одной, то выбрать произвольную;
# редуцировать атрибуты справа в оставшихся ФЗ. Для этого просмотреть каждый путь снизу вверх в графе иерархии. Двигаясь по выбранному пути, выполнить следующие действия в каждом узле пути:
## пусть {{Формула|f=X\rightarrow Y}} - это ФЗ, записанная в данном узле. Каждый атрибут, принадлежащий правой части, вычеркнуть в правых частях ФЗ, расположенных в узлах этого пути по иерархии выше;
## для тривиальной ФЗ {{Формула|f=U\rightarrow\varnothing}} атрибуты вычёркиваются слева;
# исключить из рассмотрения ФЗ с пустой правой частью (кроме редуцированной ФЗ {{Формула|f=U\rightarrow\varnothing}}). Исключённые на этом шаге ФЗ являются лишними и выводятся из оставшихся;
# каждую оставшуюся в графе иерархий ФЗ {{Формула|f=V\rightarrow W}} заменить на множество {{Формула|f=VW}}. Получившееся множество схем отношений обозначить как {{Формула|f=\rho}};
# для полученной на предыдущем шаге схемы БД проверить:
## обладает ли она свойством соединия без потерь. Если не обладает, то добавить ключ универсальной схемы {{Формула|f=U}} в эту схему;
## обладает ли {{Формула|f=\rho}} свойством сохранения ФЗ. Если нет, то, использовать зависимости, не вошедшие в проекцию {{Формула|f=X\rightarrow Y\notin\Pi_{R_i}(F)}}, для построения новых схем отношений, то есть добавить в {{Формула|f=\rho}} {{Формула|f=XY}}.

После выполнения всех шагов полученная схема {{Формула|f=\rho}}:
* обладает свойством соединения без потерь;
* обладает свойством сохранения ФЗ;
* находится в 3НФ или [[#Нормальная форма Бойса-Кодда | НФБК]];
* содержит минимальное число схем отношений.

=== Пример ===

{{Формула|f=U = (поставщик, фирма, деталь, количество) = (A, B, C, D)}}

{{Формула|f=F = (A\rightarrow B, B\rightarrow A, AC\rightarrow D, BC\rightarrow D)}}

Строим {{Формула|f=\rho}}:

1)

:{{Формула|f=УНП = (A\rightarrow B, B\rightarrow A, AC\rightarrow BD, BC\rightarrow AD)}}

2)

:пропускаем этот шаг, так как есть ФЗ (даже не одна), включающая все атрибуты из {{Формула|f=U}}

3)

:уменьшить число атрибутов не удаётся

4)

:1 класс: {{Формула|f=A\rightarrow B}}, {{Формула|f=B\rightarrow A}}, {{Формула|f=K_1 = AB}}
:2 класс: {{Формула|f=AC\rightarrow BD}}, {{Формула|f=BC\rightarrow AD}}, {{Формула|f=K_2 = ABCD}}

5)

:[[Файл:9sTORAl6pic1.png|link=Файл:9sTORAl6pic1.svg]]

6)

:для {{Формула|f=K_2}}:

::способ 1 - как во [[ТОРА_(9)_-_Семинар_№2_-_Функциональные_зависимости#Выявление лишних ФЗ | втором семинаре]]
:::можно ли вывести {{Формула|f=AC\rightarrow BD\in(BC\rightarrow AD)^+}}?
:::{{Формула|f=(AC)^+=AC}}, {{Формула|f=BD\nsubseteq(AC)^+}}, значит нельзя
:::можно ли вывести {{Формула|f=BC\rightarrow AD\in(AC\rightarrow BD)^+}}?
:::{{Формула|f=(BC)^+=BC}}, {{Формула|f=AD\nsubseteq(BC)^+}}, значит нельзя

::способ 2 - вычеркнуть из правых частей ФЗ рассматриваемых классов эквивалентностей общие атрибуты. Если получаются ФЗ с пустой правой частью, то они являются лишними.
:::{{Формула|f=AC\rightarrow B}}
:::{{Формула|f=BC\rightarrow A}}
:::выше по иерархии ничего нет, выбираем {{Формула|f=BC\rightarrow AD}}

::нет лишних ФЗ, потому...

:для {{Формула|f=K_1}}:

{{Forward|l=ТОРА (9) - Лекция №7 - Алгоритм (продолжение)}}

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

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

2013-01-08T12:08:44Z

94.79.44.124: /* Селекция */

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

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

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

{{Формула|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}} пара атрибутов идентификатор-товар является ключом. При включении новой записи, атрибуты ключа не должны быть пустыми, поэтому в БД нельзя включить поставщика, если он в данный момент не поставляет товар;
* аномалия удаления. При удалении всех товаров, поставляемых поставщиком, теряется информация о самом поставщике.
Первопричиной этих недостатков является то, что {{Формула|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_1 = 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 семестр)]]
[[Категория:Конспекты лекций и семинаров]]