Редактирование: Базы Данных, 08 лекция (от 29 сентября)
Материал из eSyr's wiki.
Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
| Текущая версия | Ваш текст | ||
| Строка 1: | Строка 1: | ||
[[Базы Данных, 07 лекция (от 28 сентября)|Предыдущая лекция]] | [[Базы Данных, 09 лекция (от 05 октября)|Следующая лекция]] | [[Базы Данных, 07 лекция (от 28 сентября)|Предыдущая лекция]] | [[Базы Данных, 09 лекция (от 05 октября)|Следующая лекция]] | ||
| - | <div class="comment">Биологи работают для того, чтобы обогощать результатами математику,... Программирование же помогает другим людям со своими задачами. Это очень прикладная | + | <div class="comment">Биологи работают для того, чтобы обогощать результатами математику,... Программирование же помогает другим людям со своими задачами. Это очень прикладная обцласть, не смотря на все фундаментальные вещи Так что это скорее, не раздел науки, а раздел инжинерии (ударение на предпоследний слог). И некоторые люди очень стесняются слова инжинерия, инжинер. Инжинерия требует практического созидания. Очень трудно жить с таким мировоззрением, так как денег не дают.</div> |
<div class="comment">Лектор любит, когда определения говорят лаконично</div> | <div class="comment">Лектор любит, когда определения говорят лаконично</div> | ||
| Строка 9: | Строка 9: | ||
Это очень фундаментальное определние, но оно очень не конструктивно. | Это очень фундаментальное определние, но оно очень не конструктивно. | ||
| - | В нашей области мы можем говорить про некоторые циклы. Ввёл это понятие (...), который ввёл цикл FOR EACH, который выдаёт каждый элемент, пока они не кончатся. В отличие от математических множеств, множества | + | В нашей области мы можем говорить про некоторые циклы. Ввёл это понятие (...), который ввёл цикл FOR EACH, который выдаёт каждый элемент, пока они не кончатся. В отличие от математических множеств, множества хронимы, и в каком-то порядке элементы лежат, поэтому нет такого множества, для которого нельзя перебрать элементы в том порядке, в котором они лежат в памяти. Если бы не |
| + | это, то вообще нельзя было бы работать с мультимножествами. | ||
| - | Для theta-сооединения существует только один алгоритм, достаточно известный, | + | Для theta-сооединения существует только один алгоритм, достаточно известный, которы йназывается nested loops. Пусть нужно реализовать операцию расшир дек произведи, имея foreach. Решение – сделать два вложенных цикла, снаружи обходить первое |
множество, внутри второе, и наружу выдаются пары. Для случая соединения это единственный алгоритм. Недостатки – очень | множество, внутри второе, и наружу выдаются пары. Для случая соединения это единственный алгоритм. Недостатки – очень | ||
большая операция. | большая операция. | ||
| Строка 21: | Строка 22: | ||
# Nested loops. Хорошо работает, когда один из операндов имеет небольшую мощность. Если он помещается в память, то по нему пускается внутренний цикл. В тех случаях, когда одно из отношний имеет небольшую можность, его пытаются использовать | # Nested loops. Хорошо работает, когда один из операндов имеет небольшую мощность. Если он помещается в память, то по нему пускается внутренний цикл. В тех случаях, когда одно из отношний имеет небольшую можность, его пытаются использовать | ||
# Sort-merge. Позаимствован из алгоритмов внешней сортировки. На первом шаге оба отношения сортируютсся по атрибуту, по которому они соединяются. Предположим, образовалось два списка. Работает только на отношении равно. Плох тем, что работает только на сортированных списках.Выбирается, как правило, в тех случаях, когда к моменту сеодинения мы имеем отсортированный список. | # Sort-merge. Позаимствован из алгоритмов внешней сортировки. На первом шаге оба отношения сортируютсся по атрибуту, по которому они соединяются. Предположим, образовалось два списка. Работает только на отношении равно. Плох тем, что работает только на сортированных списках.Выбирается, как правило, в тех случаях, когда к моменту сеодинения мы имеем отсортированный список. | ||
| - | # Hashjoin. Для потроения таблиц в основной памяти. Нужно организовать данные таким образом, чтобы, зная ключ, получить доступ к данным за одно обращение. Каждая запись имеет вид ключ-данные. Выбирается функция, называющаяся хэш-функция. Единственное требование к ней — генерировать ключи не длиннее длины ключа. Идея хеширования состоит в том, что по ключу делаем его свёртку. Есть хэш-таблица, в которой для каждого ключа есть значение хэш-функция. Если плотность таблицы маленькая, то мы действительно получаем доступ ха одно обращение. Если таблица заполнена, то возникают коллизии. Как ни странно, есть много людей, которые не могут сказать ни одну хорошую хэш-функцию, а может этому мешает наш любимый перл, в котором есть много полуфабрикатов. Наиболее | + | # Hashjoin. Для потроения таблиц в основной памяти. Нужно организовать данные таким образом, чтобы, зная ключ, получить доступ к данным за одно обращение. Каждая запись имеет вид ключ-данные. Выбирается функция, называющаяся хэш-функция. Единственное требование к ней — генерировать ключи не длиннее длины ключа. Идея хеширования состоит в том, что по ключу делаем его свёртку. Есть хэш-таблица, в которой для каждого ключа есть значение хэш-функция. Если плотность таблицы маленькая, то мы действительно получаем доступ ха одно обращение. Если таблица заполнена, то возникают коллизии. Как ни странно, есть много людей, которые не могут сказать ни одну хорошую хэш-функцию, а может этому мешает наш любимый перл, в котором есть много полуфабрикатов. Наиболее чатсо используемая функция — получающая от деления на простое число. Множество остатков от деления на простые числа — поле. Хорошее хэширование — когда элементы разразываются равномерно по области. Идея hashjoin: выбирается хэш-функция, ктороая работтает для обоих отношений, применяется к атрибуту а, и все полученные значения помещаются в bucketы, они попадают в кортежи, лдля которых свётрка даёт одно и то же значение. Пусть у R1 образовалось n bucket'ов (p<sub>1</sub>, …, p<sub>n</sub>), у R2 — m (q<sub>1</sub>...q<sub>m</sub>). Кортежи смогут соединится только тогда, когда значения хэш-функции совпадают. Чем хорош алгоритм — дешёвая операция, если есть ;l bucketов первого и второго отношения, которе образуются, которые соединяются, то их можно запустить параллельно. А если хорошо выбравна hash-функция, то bucket'ы могут быть маленькими. Алгоритм придумал Дэвид Де Вито. |
<div class="comment">Естественное соединение стоит того, чтобы перед ним покурить.</div> | <div class="comment">Естественное соединение стоит того, чтобы перед ним покурить.</div> | ||
