Здесь можно найти учебные материалы, которые помогут вам в написании курсовых работ, дипломов, контрольных работ и рефератов. Так же вы мажете самостоятельно повысить уникальность своей работы для прохождения проверки на плагиат всего за несколько минут.
Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение оригинальности любого файла в формате MS Word. После такого повышения оригинальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, РУКОНТЕКСТ, etxt.ru. Программа «StudentHelp» работает по уникальной технологии так, что на внешний вид, файл с повышенной оригинальностью не отличается от исходного.
Работа № 115878
Наименование:
Лекции по теоретическим основам реляционной алгебры
Информация:
Тип работы: Лекции.
Предмет: Математика.
Добавлен: 01.04.2019.
Год: 2014.
Страниц: 81.
Уникальность по antiplagiat.ru: < 30%
Описание (план):
Оглавление
Лекция №1 - Операции реляционной алгебры 4 Определения 4 Схема отношения 4 Степень схемы отношения 4 Экземпляр отношения 4 Кортеж 4 Схема БД 4 Примеры схем БД 5 Пример "плохой" схемы БД 5 Пример "хорошей" схемы БД 5 Основные операции реляционной алгебры 5 Объединение отношений 5 Пересечение отношений 6 Декартово произведение 6 Проекция 7 Селекция 7 Естественное соединение 8 Лекция №2 - Функциональные зависимости 10 Функциональные зависимости 10 Замыкание множества функциональных зависимостей 10 Аксиомы Армстронга 11 Пример построения множества ФЗ 11 Лемма 12 Замыкание множества атрибутов 12 Алгоритм построения 13 Лекция №3 - Хорошая схема БД - Соединение без потерь 15 Алгоритм построения условно-неизбыточног покрытия 15 Доказательство 15 Пример 16 Свойства "хорошей" схемы БД 16 Соединение без потерь 16 Лекция №4 - Хорошая схема БД - Сохранение ФЗ 21 Свойства "хорошей" схемы БД 21 Соединение без потерь 21 Свойство сохранения ФЗ 23 Лекция №5 - Третья нормальная форма 26 Свойства "хорошей" схемы БД 26 Свойство сохранения ФЗ 26 Ключ схемы отношения 27 Алгоритм построения ключа 27 Пример построения ключа 28 Третья нормальная форма 29 Пример 1 29 Пример 2 31 Лекция №6 - Алгоритм построения хорошей БД 33 Третья нормальная форма 33 Пример аномалий у 3НФ 33 Нормальная форма Бойса-Кодда 34 Алгоритм синтеза "хорошей" БД 34 Пример 35 Лекция №7 - Алгоритм (продолжение) 37 Алгоритм синтеза "хорошей" БД 37 Пример 37 Преимущество и недостатки алгоритма 39 Практические приёмы нормализации 39 Нормальные формы 39 Пример 1 41 Лекция №8 - Алгоритм (продолжение) 43 Практические приёмы нормализации 43 Пример 1 43 Пример 2 44 Лекция №9 - Оптимизация запросов 48 Оптимизация SQL-запросов 48 Законы реляционной алгебры 48 Оптимизация формул реляционной алгебры 50 Логический план 50 Лекция №10 - Логический и физический план запроса 54 Оптимизация SQL-запросов 54 Логический план 54 Физический план 55 Отличие физического плана от логического 57 Лекция №11 - Оценки 60 Оптимизация SQL-запросов 60 Физический план 60 Лекция №12 - Оценки (продолжение) 64 Оптимизация SQL-запросов 64 Физический план 64 Лекция №13 - Оценки (продолжение) 68 Оптимизация SQL-запросов 68 Физический план 68 Лекция №14 - Оценки (продолжение) 72 Оптимизация SQL-запросов 72 Физический план 72 Лекция №15 - Пример оценки 78 Оптимизация SQL-запросов 78 Методы соединения таблиц 78
? Лекция №1 - Операции реляционной алгебры Определения Схема отношения Это поименованная совокупность атрибутов. R=(A1,...,An), где Ai - некоторый атрибут из домена отношения. R=(идентификатор поставщика, адрес, товар, цена)=(A1,A2,A3,A4). Здесь (A1,A3) - ключ, определяющий запись. Степень схемы отношения Это количество атрибутов в схеме. Для R=(A1,A2,A3,A4) степень равна 4. Экземпляр отношения Это конкретная таблица с данной схемой отношения. R=(идентификатор поставщика, адрес, товар, цена).
Кортеж Любая одна строка в таблице экземпляра отношения. Схема БД A - множество всех атрибутов некоторой предметной области (универсальная схема отношения). R1,...,Rn - совокупность атрибутов. Тогда ?=(R1,...,Rn) называется схемой БД. Пример: A=(A1,A2,A3,A4) и две схемы: R1=(A1,A2) и R2=(A1,A3,A4) Так как R1?R2=A, то ?=(R1,R2). Примеры схем БД Пример "плохой" схемы БД Пусть A=(идентификатор поставщика, адрес, товар, цена) и есть одна схема ?=R1=A Данная схема БД обладает следующими недостатками (аномалиями): • избыточность. Адрес поставщика повторяется для каждого поставляемого им товара; • потенциальная противоречивость. Если у поставщика меняется адрес, то его необходимо изменить во всех кортежах, в которые он входит; • аномалия включения кортежа. В выбранном отношении R1 пара атрибутов идентификатор-товар является ключом. При включении новой записи, атрибуты ключа не должны быть пустыми, поэтому в БД нельзя включить поставщика, если он в данный момент не поставляет товар; • аномалия удаления. При удалении всех товаров, поставляемых поставщиком, теряется информация о самом поставщике. Первопричиной этих недостатков является то, что R1 не находится в 3НФ Пример "хорошей" схемы БД Пусть A=(идентификатор поставщика, адрес, товар, цена) R1=(идентификатор, адрес) R2=(товар, цена) Схема ?=(R1,R2) находится в 3НФ и не обладает перечисленными выше недостатками. Основные операции реляционной алгебры Объединение отношений R=R1?R2 Объединение отношений - это отношение, каждый кортеж которого принадлежит либо R1, либо R2.
Дублирование кортежей не допускается. Пересечение отношений R=R1?R2 Пересечение отношений - это отношение, каждый кортеж которого принадлежит и R1, и R2
Декартово произведение R,S - две схемы отношения со степенями k1 и k2 t=R?S Декартово произведение - это отношение t со степенью k1+k2, кортежи которого получаются конкатенацией кортежей из отношений R и S.
Проекция t=?Ai1...Aik(R) Проекция - это отношение, каждый кортеж которого состоит из значений атрибутов Ai1...Aik исходного отношения R.
Селекция t=?F(R) Селекция - это отношение, каждый кортеж которого принадлежит исходному отношению R и удовлетворяет логическому условию F.
Естественное соединение t=R?S Определение этой операции следует из способа построения естественного соединения.
Построение естественного соединения: 1) построить декартово произведение R?S
2) выбрать из этого произведения кортежи по условию R.Ai1=S.Ai1...R.Aik=S. ik, где Ai...Ak - общие атрибуты в схемах отношений R и S (предполагается, что эти атрибуты занимают одинаковое положение в отношениях. Хотя не обязательно)
3) удалить из полученного отношения S.Ai1...S.Aik, потому что они будут дублирующими.
? Лекция №2 - Функциональные зависимости
Функциональные зависимости, замыкание множества функциональных зависимостей, атрибутов.
Функциональные зависимости Пусть R=(A1...An) является функциональной схемой отношения и X, Y - некоторые подмножества атрибутов этой схемы. Говорят, что X функционально определяет Y (X›Y), если в любом экземпляре отношения со схемой R не существует двух кортежей, совпадающих по подмножеству X и не совпадающих по подмножеству Y Иначе говоря, если два кортежа совпадают по X, то они должны совпадать и по Y Например, R=(A1,A2,A3,A4), есть зависимости: • A1›A2 (1) • A1A3›A4 (2) Предположим, что имеет место один экземпляр отношения со схемой R
Вторая ФЗ (2) имеет место быть, так как нет двух кортежей, совпадающих по этой паре (по крайней мере, в приведённом экземпляре схемы отношения, а других мы не знаем). А первая ФЗ (1) не имеет место быть (в третьей строке другой номер дома портит всю картину). Замыкание множества функциональных зависимостей Пусть R - универсальная схема отношения, а F - исходное множество функциональных зависимостей на этой схеме. Замыканием F называется всё множество функциональных зависимостей, которое логически следует из F - обозначается как F+ Функциональная зависимость логически следует из F, если её можно вывести (получить) с помощью аксиом Армстронга. Аксиомы Армстронга Или правила вывода функциональной зависимости. Существуют различные интерпретации аксиом, но все эквивалентны. Потому приведём только один вариант. Аксиомы Армстронга являются надёжными и полными. Надёжность - если ФЗ выводится с помощью аксиом Армстронга, то она справедлива во всех экземплярах отношения, где справедливы исходные ФЗ F Полнота - если имеет место какая-либо ФЗ, то она обязательно может быть выведена с помощью аксиом Армстронга. Рефлексивность Если Y?X?R то X›Y. Тривиальная аксиома. Дополнение Если X›Y и Z?R (Z может быть пустым), тогда X?Z›Y?Z или XZ›YZ Транзитивность Если X›Y, а Y›Z, то X›Z Пример построения множества ФЗ Пусть задана УСО (универсальная схема отношения) R=(A,B,C) и зависимости F=(A›B,B›C) 1. A›A, B›B, C›C, AB›A, AB›B, AC›A, AC›C, BC›B, BC›C, ABC›A, ABC›C, AB›AB, AC›AC, BC›BC, ABC›AB, ABC›AC, ABC›BC, ABC›ABC 2. A›AB (1ФЗ и пополняем A), AC›BC, B›BC (2 ФЗ и пополняем B), AB›AC, AC›ABC, AB›ABC, AB›BC, A›AC 3. A›C (1 и 2 ФЗ), A›ABC Всё, замыкание (F+) построено. Все перечисленные зависимости образуют замыкание. Лемма Справедливы следующие правила. Для их доказательства необходимо пополнить ФЗ так, чтобы можно было использовать аксиомы. Правило объединения Если X›Y и X›Z, то X›YZ Доказательство: 1. X›XY (1 ФЗ и пополняем X); 2. XY›YZ (2 ФЗ и пополняем Y); 3. X›YZ (по аксиоме транзитивности). Правило декомпозиции Если X›Y, а Z?Y, то X›Z Доказательство: 1. X›Y (по условию); 2. Y›Z (по аксиоме рефлексивности); 3. X›Z (по аксиоме транзитивности). Правило псевдотранзитивности Если X›Y и WY›Z, то WX›Z Доказательство: 1. WX›WY (1 ФЗ и пополняем W); 2. WY›Z (по условию); 3. WX›Z (по аксиоме транзитивности). Замыкание множества атрибутов Замыкание F+ может включать в себя очень большое количество ФЗ. Например: F=(X›A1,X›A2...X›An) X›Y?F+ Y?(A1,A2...An) и таких подмножеств может быть 2n Поэтому "в лоб" замыкание F+ никто не строит. Но необходимо найти какой-то метод, который достаточно просто позволял бы выяснять, принадлежит ли произвольная ФЗ X›Y к F+ Для этого применяется замыкание множества атрибутов. Пусть R - универсальная схема отношения, а X - некоторое подмножество атрибутов. Тогда замыканием множества атрибутов X+ называется совокупность атрибутов Ai1,Ai2...Aik таких, что X›Ai1,X›Ai2...X›Aik Алгоритм построения Алгоритм является итерационной процедурой. 1. полагаем i=0 и X+0=X, а X+i - замыкание множества атрибутов на i-том шаге; 2. X+i+1=X+i?V, где V - такое множество атрибутов в F, что существует ФЗ Y›Z, где Y?X+i, V?Z; 3. если X+i+1=X+i, то X+=X+i, иначе i=i+1 и возвращаемся в пункт 2. Пример построения Пусть R=(A,B,C,D,E,G) F=(AB›C,C›A,BC›D,ACD›B,D›EG,BE›C,CG›BD,CE›AG) X=BD Надо построить X+: 1) i=0, X+0=BD 2)
Получили, что X+4=X+3, а значит X+=X+3=BDEGCA Это означает, что имеют место следующие ФЗ: BD›B, BD›D, BD›E, BD›G, BD›C, BD›A, и все они ?F+ Короче, чтобы проверить X›Y?F+, необходимо построить X+ ? Лекция №3 - Хорошая схема БД - Соединение без потерь Пусть F и G - два множества ФЗ. G называется покрытием F, если имеет место равенство G+=F+ Существуют различные виды покрытий. Но мы рассмотрим только один - условно-неизбыточное покрытие. Алгоритм построения условно-неизбыточног покрытия 1) если в множестве ФЗ F встречаются ФЗ с одинаковой левой частью X, то следует объединить эти ФЗ в одну ФЗ. Это следует из леммы объединения. Получившееся множество ФЗ обозначим G; 2) для каждой ФЗ X›Y из G заменить её на X›X+?X; После выполнения 1) и 2) получаем замыкание G+=F+ Доказательство 1) Докажем, что если ФЗ X›Y?F (из этого следует, что Y?X+ (1) по определению замыкания множества аттрибутов), то эта ФЗ принадежит G+ По построению G имеет место ФЗ: X›X+?X (2) Пополним эту ФЗ: X›(X+?X)?X, получится, что X›X+ (3) Теперь по первой аксиоме Армстронга из (1) имеем X+›Y (4) Значит, X›Y?G+, по третьей аксиоме Армстронга, исходя из (3) и (4). 2) Докажем обратное, что если X›Y?G, то X›Y?F+ По построению G имеем: Y=X+?X (5) Для F имеем: X›X+ (по определению) (6) X+›X+?X (1 аксиома Армстронга, так как X+?X?X+) (7) X›X+?X=Y (3 аксимома Армстронга из (6)и (7), и по равенству (5)) В итоге получили X›Y?F+. Теорема доказана. Пример УСО: R=(A,B,C) Множество ФЗ: F=(A›B,B›A,C›A,A›C,B›C) 1) G=(A›BC,B›AC,C›A) 2) A+=ABC, A+?A=BC B+=BAC, B+?B=AC C+=CAB, C+?C=AB
Тогда G=(A›BC,B›AC,C›AB) будет являться УНП. Свойства "хорошей" схемы БД "Хорошая", но не оптимальная. Должна обладать следующими свойствами: • соединение без потерь; • сохранение ФЗ; • каждая схема отношений в этой БД находится в 3НФ. Наличие этого свойства обеспечивает отсутствие в схемах отношений следующих аномалий: o избыточность; o потенциальная противоречивсть; o аномалия обновления; o аномалия удаления. Соединение без потерь Чтобы схема БД обладала свойством соединения без потерь, необходимо, чтобы хотя бы одна из таблиц содержала ключ универсальной схемы отношений. Пусть ?=(R1...Rn) - схема БД. Она будет обладать свойством соединения без потерь, если для любого экземпляра отношения r из R справедливо равенство: r=?R1(r)??R2(r)?...??Rn( ), где ?Ri(r) - это проекция экземпляра отношения r на множество атрибутов Ri Пример БД, не обладающей свойством соединения без потерь R=(A,B,C) ?=(AB,BC)=(R1,R2) F=(A›B) Достаточно привести пример экземпляра r, для которого равенство не выполняется:
Полученное соединение не будет равняться r:
Этот пример показывает, что при неправильном построении БД запросы могут выдавать неправильный результат. Пример БД, обладающей свойством соединения без потерь R=(A,B,C) ?=(AB,AC)=(R1,R2) F=(A›B) Возьмём тот же экземпляр:
Полученное соединение будет равняться r:
Но это не доказательство, а только один пример, просто чтобы показать, в чём разница. Алгоритм проверки схемы БД на свойство соединения без потерь ?=(R1...Rn) R=(A1...An) 1) построить таблицу T:
И заполнить таблицу T по правилу: если Aj?Ri, то Tij=a, иначе Tij=bi 2) изменить таблицу T - циклически просматривать ФЗ из F в любом порядке, и для очередной ФЗ X›Y?F выполнить следующие действия: • найти в таблице T строки, совпадающие по атрибутам X (по левой части); • если хотя бы в одной такой строке значение атрибута Am?Y=a, то во всех найденных строках присвоить Am=a, иначе присвоить Am=bi (i - номер одной из найденных строк), bi должно быть одинаково во всех указанных строках); • выполнить предыдущие два пункта для всех атрибутов Al?Y; • выполнить предыдущие три пункта для всех ФЗ из F, циклически их просматривая. 3) алгоритм останавливается, если при очередном просмотре ФЗ из F: • не произошло никаких изменений в таблице T; • какая-нибудь строка в T не стала состоять сплошь из символов a (наличие такой строки и говорит о выполнении свойства соединения без потерь). Пример Пусть R=(A,B,C) ?=(AB,AC)=(R1,R2) F=(A›B) Доказать, что ? обладает свойством соединения без потерь. 1)
2)
Получили строку, сплошь состоящую из a. Значит ? обладает свойством соединения без потерь. Другой пример Пусть R=(A,B,C,D,E,F,P,S) ?=(AB,ACDPS,BCPS,DEF =(R1,R2,R3,R4) F=(B›C,D›EF,B›PS,A›CDPS,AP›S) Доказать, что ? обладает свойством соединения без потерь. 1)
2) первый просмотр:
второй просмотр:
Вот и получили строку, сплошь состоящую из a. Значит ? обладает свойством соединения без потерь. ? Лекция №4 - Хорошая схема БД - Сохранение ФЗ
Свойства "хорошей" схемы БД Соединение без потерь Теорема о свойстве соединения без потерь Пусть ?=(R1,R2) и F - множество ФЗ. ? обладает свойством соединения без потерь тогда и только тогда, когда выполняется хотя бы одно из: • R1?R2›R1?R2 (1) • R1?R2›R2?R1 (2) Доказательство 1)
Получили строку, сплошь состоящую из a. 2) Теперь докажем обратное, что если ? обладает соединением без потерь, то имеет место одна из ФЗ: (1) или (2). r=?R1(r)??R2(r) (3) r - это R1?R2 (экземпляр универсальной схемы отношений)
Если выполняется равенство (3), то возможны два варианта: 1) bi?bj, i?j; 2) некоторые bi совпадают, b1=b2. Тогда для выполнения равенства (3) необходимо, чтобы выполнялось одно из двух: • a1=a2; • c1=c2.
2 и 3 кортежи - лишние. Чтобы они не были лишними, они должны совпадать с одним из других кортежей, чтобы их можно было вычеркнуть. Предположим, a1=a2, тогда что-то там насовпадало и 2 и 3 кортежи можно вычеркнуть. Аналогичные рассуждения можно провести для случая, когда c1=c2, но тогда получаем: • для варианта bi?bj имеют место обе ФЗ : (1) и (2); • для варианта с некоторыми совпадающими bi работает либо (1), либо (2). Всё, теорема доказана. Следствие из теоремы Пусть R1 и R2 - это сущности БД и они связаны между собой. Тогда схема БД обладает соединением без потерь, если общий атрибут R1 и R2 содержит ключ одной из этих схем отношений. R1?R2=A R1?R2=B R1?R2›R1?R2, потому что A›B, так как является ключом. Свойство сохранения ФЗ Пусть дана схема БД ?=(R1...Rn) и F - множество ФЗ. Проекцией F на Ri называется такое множество ФЗ, принадлежащее F+, что XY?Ri, ?Ri(F) Схема ? обладает свойством сохранения ФЗ, если: (?ni=1?Ri(F))+=F+ - ФЗ могут быть декомпозированны по схеме отношений (тогда проверку надо будет выполнять только в рамках отдельных таблиц при включении новой записи). Пример схемы БД без свойства сохранения ФЗ R=(A,B,C) - универсальная схема отношений. F=(A›B,B›C) ?=(AB,AC)=(R1,R2) Надо доказать, что ? не обладает свойством сохранения ФЗ. Первая проекция: ?R1(F)=F1=(A›A,B›B,AB›A,AB›B,AB›AB,A›B,A›AB) Вторая проекция: ?R2(F)=F2=(A›A,C›C,AC›A,AC›C,AC›AC,A›C,A›AC) B›C?F+ по определению. B›C?(F1?F2)+ - не работает, так что эта БД не обладает свойством сохранения ФЗ. B+=B, C?B+ Пример схемы БД со свойством сохранения ФЗ R=(A,B,C) - универсальная схема отношений. F=(A›B,B›C) ?=(AB,BC)=(R1,R2) Надо доказать, что ? обладает свойством сохранения ФЗ. Первая проекция: ?R1(F)=F1=(тривиальн е ФЗ, A›B,A›AB) Вторая проекция: ?R2(F)=F2=(тривиальн е ФЗ, B›C,B›BC) (F1?F2)+=(тривиальны ФЗ, A›B,A›AB,B›C,B›BC,A›C,A›AC), а это и есть по определению само F+, что и доказывает, что данная схема БД обладает свойством сохранения ФЗ. Алгоритм проверки схемы БД на обладание свойством сохранения ФЗ ?=(R1...Rn) Алгоритм: 1) построить условно-неизбыточное покрытие (УНП), взять H=?; 2) каждую ФЗ из УНП разбить на совокупность ФЗ с одним атрибутом в правой части, то есть заменить X›A1A2...Ak на X›A1, X›A2, ..., X›Ak. Обозначить полученную ФЗ как G; 3) выбрать очередную ФЗ из G. Найти такую схему отношения Ri, для которой справедливо включение XA?Ri. Если такой схемы отношений не существует, то поместить ФЗ X›A в множество H; 4) если все ФЗ из G рассмотрены, то перейти к следующему пункту, иначе к предыдущему; 5) если H пусто, то завершить алгоритм. ? обладает свойством сохранения ФЗ. Иначе перейти к следующему пункту; 6) просмотреть все ФЗ из H. Если какая-либо ФЗ X›A?H не выводится из множества G?H, то завершить алгоритм. ? не обладает свойством сохранения ФЗ. Иначе завершить алгоритм, и тогда ? обладает свойством сохранения ФЗ. ? Лекция №5 - Третья нормальная форма
Свойства "хорошей" схемы БД Свойство сохранения ФЗ Алгоритм проверки схемы БД на обладание свойством сохранения ФЗ Пример 1 Пусть R=(A,B,C), ?=(AB,BC)=(R1,R2) и F=(A›B,B›C) Обладает ли ? сохранением ФЗ? Смотрим: 1) H=?, УНП=(A›BC,B›C) 2) G=(A›B,A›C,B›C) 3) A›B, AB?R1 A›C, AC?R2, H=(A›C) B›C, BC?R2 4) пропускаем, так как не выполнилось условие в 3) 5) H не пустое. 6) выполняется ли A›C?(G?H)+=(A›B,B›C)+ A+=ABC, C?A+, значит ? обладает сохранением ФЗ. Пример 2 Пусть R=(A,B,C), ?=(AB,AC)=(R1,R2) и F=(A›B,B›C) Обладает ли ? сохранением ФЗ? 1-4) H=?, УНП=(A›BC,B›C) H=(B›C)) 5) H не пустое. 6) выполняется ли B›C?(G?H)+=(A›BC)+ B+=B, C?B+, значит ? не обладает сохранением ФЗ. Ключ схемы отношения Ключ схемы отношения – это подмножество исходной схемы, состоящая из одного или нескольких атрибутов, которые задают уникальность значений в кортежах отношений. Если атрибут Ai?R входит в какой-либо ключ схемы отношения R, то он называется первичным. А если не входит ни в один, то называется непервичным. Пусть R=(A1...An) - некоторая схема отношения. F - множество ФЗ. Тогда X?R называется ключом схемы, если выполняются: • X›A1...An?F+ • ?Z?X, Z›A1...An?F+. То есть X содержит минимальное число атрибутов, для которых выполняется предыдущее свойство. Алгоритм построения ключа Базируется на определении ключа. Позволяет построить только один ключ. 1) i=0, X0=A1...An 2) цикл по атрибутам Aj в Xi Если (Xi?Aj)+=R, то Xi+1=Xi?Aj, i=i+1 и выйти из цикла; иначе продолжить цикл 3) если i возросло, то перейти к шагу 2); иначе X=Xi - это найденный ключ. Пример построения ключа Пусть R=(A,B,C,D), F=(AB›DC,BC›AD) Надо построить ключ. 1) i=0, X0=ABCD 2) (X0?A)+=(BCD)+=BCDA= , значит X1=BCD, i=1 3) i, как видим, возросло, значит опять 2) 2) (CD)+=CD?R (BD)+=BD?R (BC)+=BCAD=R, X2=BC, i=2 3) i, как видим, возросло, значит опять 2) 2) C+=C?R B+=B?R 3) i, как видим, не возросло. Значит, X=BC - ключ. Но не единственный, X=AB - тоже ключ, просто у нас получился сначала этот. Значит, A,B,C - первичные атрибуты, а D - непервичный. Третья нормальная форма Отношение находится в 3НФ, если не существует тройки: • ключа X, • Y?R, • непервичного атрибута H?Y, для которой выполняются: • X›Y?F+; • Y›H?F+; • Y›X?F+. Если такую тройку можно найти, то схема не находится в 3НФ. Если схема отношения находится в 3НФ, то в большинстве случаев эта схема отношения не обладает аномалиями. Но существуют условия, когда схема в 3НФ обладает этими аномалиями. Хотя, встречаются они редко. Вот они: • схема отношения имеет 2 или больше ключей, o и любые 2 из них являются составными, § и имеют общий атрибут. Пример 1 Пусть R=(A,B,C,D), F=(A›B,AC›D) и ?=R Доказать, что это отношение не находится в 3НФ. Доказываем: 1) i=0, X0=ABCD 2) (BCD)+=BCD?R (ACD)+=ACDB=R, X=ACD, i=1 3) i, как видим, возросло, значит опять 2) 2) (CD)+=CD?R (AD)+=ADB?R (AC)+=ACBD=R, X2=AC, i=2 3) i, как видим, возросло, значит опять 2) 2) C+=C?R A+=AB?R 3) i не возросло, значит X=X2=AC - это ключ. Причём, можно показать, что он единственный. Теперь предполагаем тройку: • X=AC • Y=A?R • H=B - непервичный атрибут, B?X Проверям три условия для неё: 1) X›Y, так как AC›A по 1 аксиоме Армстронга; 2) Y›H, A›B по условию; 3) Y?X, A?AC A+=AB, AC?A+ Таким образом, найдена тройка, для которой выполняются все три условия, а значит отношение не находится в 3НФ. Пример 2 Декомпозируем эту схему отношения R на две схему отношений. R=(A,B,C,D) F=(A›B,AC›D) ?=(AB,ACD)=(R1,R2) Если R1 и R2 находятся в 3НФ, то значит всё ? будет в 3НФ. Сначала покажем 3НФ у R1=(AB), F=(A›B): • X=A - выберем ключом • Y, X›Y, Y?X Y=B, A›B, B?A • невозможно подобрать непервичный атрибут H?Y, потому что непервичным может быть только B. Таким образом, нельзя подобрать необходимую тройку. Значит, R1 находится в 3НФ. Теперь покажем 3НФ у R2=(ACD), F=(AC›D): • X=AC - выберем ключом • Y, X›Y, Y?X а) A - что-то как-то не выполняется; б) C - что-то как-то не выполняется; в) D - что-то как-то не выполняется; г) AD - что-то как-то не выполняется; д) CD - что-то как-то не выполняется. • H?Y, H=D а) Y=A, Y?H б) Y=C, Y?H в-д) H?Y Не удалось подобрать нужную тройку, так что R2 тоже находится в 3НФ. ? Лекция №6 - Алгоритм построения хорошей БД
Третья нормальная форма Пример аномалий у 3НФ R=(A,B,C,D) и F=(A›B,B›A,AC›D) Два ключа: первый - AC: (AC)+=ACBD=R A+=AB?R C+=C?R второй - BC: (BC)+=BCAD=R B+=BA?R Покажем, что в этом случае R находится в 3НФ: 1) неключевой атрибут H, H=D 2) Y›H, H?Y, Y=AC 3) X=BC, X=AC Нельзя подобрать нужную тройку, потому R находится в 3НФ. Однако, отношение всё равно обладает аномалиями: • избыточности: наименование поставщика повторяется для каждой поставляемой делали; • противоречивости при изменении наименования поставщика надо изменить его во всех записях, куда оно входит; • включения: нельзя включить информацию о поставщике, если он ничего не поставляет; • удаления: при удалении детали удаляется информация о поставщике. Для устранения этого вводится усиленная 3НФ - Бойса-Кодда. Нормальная форма Бойса-Кодда ФЗ X›Y является неприводимой, если для любого подмножества Z?X выполняется Z?Y или Z›Y?F+ Пусть есть отношение R и F включает в себя нетривиальные неприводимые ФЗ. Тогда отношение R находится в нормальной форме Бойса-Кодда, если для любого X›Y?F =› X - ключ. Пример: R1=AB, F1=(A›B,B›A), A - ключ, B - ключ. или R2=ACD, F2=(AC›D), AC - ключ. Алгоритм синтеза "хорошей" БД Пусть U - универсальная схема отношения (множество всех атрибутов предметной области) и F - множество ФЗ. Перед выполнением алгоритма можно привести все ФЗ к одному атрибуту в правой части (по свойству декомпозиции) и удалить лишние ФЗ. Но это не обязательно. Алгоритм: 1. построить УНП для F; 2. если среди ФЗ в УНП нет ФЗ, включающей все атрибуты из U, то добавить в УНП тривиальную ФЗ U›?. Выполнение этого шага почти всегда обеспечивает свойство соединения без потерь будущей схемы БД; 3. привести все нетривиальные ФЗ из УНП к неприводимому виду (удалить лишние атрибуты в левых частях ФЗ); 4. разбить полученное множество ФЗ УНП на классы эквивалентности. Две зависимости Xi›Yi и Xj›Yj будем называть эквивалентными, если XiYi=XjYj. Далее введём обозначение Kr=XiYi - множество атрибутов в левой и правой частях ФЗ r-того класса эквивалентности; 5. построить граф иерархии полученных на предыдущем шаге классов эквивалентности (если это возможно). Правило построения: j-ый узел соединяем снизу с i-ым узлом, если Kj?Ki. В каждом узле записываются все ФЗ, соответствующего класса эквивалентности; 6. из каждого класса эквивалентности в графе иерархии оставить только одну ФЗ. Правила выбора: 1. удалить из класса эквивалентности лишние ФЗ; 2. если в классе эквивалентности осталось больше одной ФЗ, то выбрать ФЗ с меньшим числом атрибутов в левой части; 3. если у оставшихся ФЗ число атрибутов в левой части одинаково, то выбрать ту ФЗ, которая позволит редуцировать (вычеркнуть) атрибуты справа у ФЗ, расположенных выше в графе иерархии; 4. если в результате не удалось выбрать ни одной, то выбрать произвольную; 7. редуцировать атрибуты справа в оставшихся ФЗ. Для этого просмотреть каждый путь снизу вверх в графе иерархии. Двигаясь по выбранному пути, выполнить следующие действия в каждом узле пути: 1. пусть X›Y - это ФЗ, записанная в данном узле. Каждый атрибут, принадлежащий правой части, вычеркнуть в правых частях ФЗ, расположенных в узлах этого пути по иерархии выше; 2. для тривиальной ФЗ U›? атрибуты вычёркиваются слева; 8. исключить из рассмотрения ФЗ с пустой правой частью (кроме редуцированной ФЗ U›?). Исключённые на этом шаге ФЗ являются лишними и выводятся из оставшихся; 9. каждую оставшуюся в графе иерархий ФЗ V›W заменить на множество VW. Получившееся множество схем отношений обозначить как ?; 10. для полученной на предыдущем шаге схемы БД проверить: 1. обладает ли она свойством соединия без потерь. Если не обладает, то добавить ключ универсальной схемы U в эту схему; 2. обладает ли ? свойством сохранения ФЗ. Если нет, то, использовать зависимости, не вошедшие в проекцию X›Y??Ri(F), для построения новых схем отношений, то есть добавить в ? XY. После выполнения всех шагов полученная схема ?: • обладает свойством соединения без потерь; • обладает свойством сохранения ФЗ; • находится в 3НФ или НФБК; • содержит минимальное число схем отношений. Пример U=(поставщик,фирма,д таль,количество)=(A, ,C,D) F=(A›B,B›A,AC›D,BC›D) Строим ?: 1) УНП=(A›B,B›A,AC›BD,BC›AD) 2) пропускаем этот шаг, так как есть ФЗ (даже не одна), включающая все атрибуты из U 3) уменьшить число атрибутов не удаётся 4) 1 класс: A›B, B›A, K1=AB 2 класс: AC›BD, BC›AD, K2=ABCD 5)
6) для K2: способ 1 - как во втором семинаре можно ли вывести AC›BD?(BC›AD)+? (AC)+=AC, BD?(AC)+, значит нельзя можно ли вывести BC›AD?(AC›BD)+? (BC)+=BC, AD?(BC)+, значит нельзя способ 2 - вычеркнуть из правых частей ФЗ рассматриваемых классов эквивалентностей общие атрибуты. Если получаются ФЗ с пустой правой частью, то они являются лишними. AC›B BC›A выше по иерархии ничего нет, выбираем BC›AD нет лишних ФЗ, потому... ? Лекция №7 - Алгоритм (продолжение)
Алгоритм синтеза "хорошей" БД Пример 7) редуцирование атрибутов справа ФЗ, расположенной по иерархии выше вычёркиваем в графе A
8) нет ФЗ с пустой правой частью, потому шаг пропускаем. 9) ?=(AB,BCD)=(R1,R2) 10) проверяем • соединение без потерь F=(A›B,B›A,AC›D,BC›D)
Значит, ? обладает сохранением без потерь. • сохранение ФЗ 1-4) H=?, УНП=(A›B,B›A,AC›BD,BC›AD) H=(AC›BD,BC›A) 5) H?? 6) выполняется ли AC›BD?(A›B,B›A,BC›D)+? (AC)+=ACBD, BD?(AC)+ выполняется ли BC›A?(A›B,B›A,BC›D)+? (BC)+=BCAD, A?(BC)+ значит, ? обладает сохранением ФЗ. На практике, частно пренебрегают свойством сохранения ФЗ, если в БД вводятся правильные данные - не надо проверять, противоречат ли эти данные исходной ФЗ. Таким образом, ? обладает: • обладает соединением без потерь; • обладает сохранением ФЗ; • точно находится в 3НФ. Но мы всё равно проверим, находятся ли R1 и R2 в 3НФ Бойса-Кодда: R1=AB: A›B, B›A здесь A - ключ и B - ключ. значит, находится в НФ. R2=BCD: BC›D BC - ключ. значит, находится в НФ. Преимущество и недостатки алгоритма Преимущество Алгоритм определяет стандартную (математическую) процедуру построения схемы БД. Недостатки • очень трудно определить всё множество ФЗ, а алгоритм критичен к набору этих ФЗ. В приципе, надо строить абстрактный экземпляр отношений (семинар №2), но надо знать и предметную область; • при увеличении числа ФЗ возможно увеличение сложности вычисления алгоритма. Эти недостатки сдерживают применение алгоритма на практике. Практические приёмы нормализации Кроме алгоритма есть практические приёмы нормализации схемы отношений. Нормальные формы 1НФ Отношение находится в 1НФ, если все его атрибуты атомарны, то есть ни один из его атрибутов нельзя разделить на более простые атрибуты, которые соответствуют каким-то другим свойствам описываемой сущности. Также схема отношений находится в 1НФ, если не содержит таблицу или вектор в явном виде. Поэтому, если таблица скрыта в объекте, то схема будет в 1НФ. Ясно, что отношение, находящееся в 1НФ, также может обладать избыточностью. Для её устранения предназначена вторая нормальная форма. 2НФ Отношение находится во второй нормальной форме (сокращённо 2НФ) тогда и только тогда, когда оно находится в первой нормальной форме и каждый его неключевой атрибут неприводимо зависим от первичного ключа. Схема отношений находится в 2НФ, если не существует ключа X, подмножества атрибутов Y?X и непервичного атрибута H, для которых выполняются условия: • X›Y; • Y›H; • Y?X.
A1›Ai...Aj X=A1A2, Y=A1?X, H?(Ai...Aj): 1) X›Y, так как A1A2›A1 2) Y›H, так как A1›Ai...Aj 3) Y?X, так как A+1=A1Ai...Aj, X?Y+ 3НФ Подробнее на лекции №5.
A2›Ai...Aj X=A1, Y=A2, H?(Ai...Aj): 1) X›Y, так как A1›A2 2) Y›H, так как A2›Ai...Aj 3) Y?X, так как A+2=A2Ai...Aj, X=A1?Y+ Пример 1 R - схема отношения "Сотрудники".
ФЗ: A1A5›A2A3A4 A1›A2A3A4 A3›A4 Покажем, что эта схема не находится в 2НФ: Можно найти ключ X=A1A5, Y=A1?X, H?Y, H?(A2,A3,A4): 1) X›Y 2) Y›H 3) Y?X
R1 тоже не находится во 2НФ, потому что X=A1, Y=A3, H=A4: 1) X›Y 2) Y›H 3) Y?X
Предположим, вдруг оказалось, что сотрудник может занимать несколько должностей, и ещё теперь в таблице надо хранить сведения о заказе. В этом случае схема преобразуется к следующему виду:
Но анализ показывает, что в этом случае таблицы R1 и R2 не находятся в 2НФ: R1: A1›A2, X=A1A3, Y=A1?X, H=A2 1) X›Y, так как A1A3›A1 2) Y›H, так как A1›A2 3) Y?X, так как Y+=A1A2, X?Y+ R2: A5›A6, X=A1A3A5, Y=A5?X, H=A6 1) X›Y, так как A1A3A5›A5 2) Y›H, так как A5›A6 3) Y?X, так как Y+=A5A6, X=A1A3A5?Y+ ? Лекция №8 - Алгоритм (продолжение)
Практические приёмы нормализации Пример 1 Поэтому вновь перестроим схему:
Указанная схема имеет два недостатка: 1. в ключи R3, R1 и R4 входят атрибуты предметной области. При изменении формата табельного номера придётся обновить его в R1 и через CASCADE в R3 и R4. Поэтому всегда желательно иметь синтетические ключи - не связанные с предметной областью (ID); 2. в сущностях R2 и R5 ключи составные. Это увеличивает размер индекса и время поиска по этому индексу. В силу этого, схему БД предлагается реорганизовать следующим образом (ввести синтетические ключи):
Пример 2 Разработать схему БД для предыдущего примера с применением алгоритма синтеза. U = (табельный номер, ФИО, должность, оклад, номер заказа, сведения о заказе) = (A1,A2,A3,A4,A5,A6) F=(A1›A2,A3›A4,A5›A6) Синтез: 1) УНП=(A1›A2,A3›A4,A5›A6) 2) U›? в УНП нет ФЗ, включающей все атрибуты из U. Поэтому добавляем в УНП тривиальную ФЗ: УНП=(A1›A2,A3›A4,A5›A6,A1A2A3A4A5A6›?) 3) все нетривиальные ФЗ в УНП являются неприводимыми (в левой части один атрибут). Поэтому шаг пропускаем. 4) разбиваем УНП на классы ФЗ: 1. A1›A2, K1=A1A2 2. A3›A4, K2=A3A4 3. A5›A6, K3=A5A6 4. A1A2A3A4A5A6›?, K4=A1A2A3A4A5A6 5) строим граф иерархии:
6) пропускаем, так как в каждом классе только одна ФЗ. 7) выполняем редуцирование атрибутов ФЗ:
8) пропускаем, так как в графе иерархии нет ФЗ, кроме U›? 9) ?=(A1A3A5,A1A2,A3A4, 5A6) 10) 1) соединение без потерь
Получили строку, сплошь состоящую из a. Значит, есть соединение без потерь. Запрос на соединение всех четырёх таблиц будет выполняться правильно. 2) сохранение ФЗ: 1-4) H=?, УНП=(A1›A2,A3›A4,A5›A6) 5) H - пусто. 6) обладает сохранением ФЗ. При включении новой записи в таблицу достаточно проверять справедливость тех ФЗ, которые связаны с этой таблицей. 3) каждая схема отношения находится в 3НФ. Вот так. А находятся ли схемы отношений R1,R2,R3,R4 в нормальной форме Бойса-Кодда? R1: R1=A1A3A5, A1A3A5 - ключ, значит находится в НФБК. R2: R2=A1A2, A1›A2, A1 - ключ, значит находится в НФБК. R3: R4=A3A4, A3›A4, A3 - ключ, значит находится в НФБК. R4: R4=A5A6, A5›A6, A5 - ключ, значит находится в НФБК. В конце концов, получаем такую схему БД:
Но у неё тоже есть недостатки: 1. ключ в R1 составной; 2. в ключах R2,R3,R4 используются атрибуты предметной области. Перестроим схему с синтетическими ключами:
Сравнивая результаты Примера 1 и Примера 2, видим, что алгоритм синтеза даёт меньшее число схем отношений. ? Лекция №9 - Оптимизация запросов
Оригинал всего раздела, посвящённого оптимизации SQL-запросов, от самого Григорьева можно загрузить здесь.
Оптимизация SQL-запросов Запрос, поступающий в СУБД, подвергается оптимизации с целью уменьшения времени его выполнения. Шаги оптимизатора: 1. строится логический план выполнения запроса (дерево логических операций); 2. на основе логического плана строится физический план выполнения запроса (дерево физических операций); 3. реализация этого физического плана. Законы реляционной алгебры Закон коммутативности декартова произведения отношений R1?R2=R2?R1, здесь и далее R1 и R2 - экземпляры отношений. Закон ассоциативности декартова произведения (R1?R2)?R3=R1?(R2?R3 Закон каскада проекций Допустим, (a1...an)?(b1...bn), ai, bi - это атрибуты отношения R тогда ?a1...an(?b1...bn(R))=?a1 ..an(R) Закон каскада селекций Допустим, F=f1?f2 тогда ?F(R)=?f1(?f2(R)) Закон перестановки проекции и селекции 1) Допустим, в условия поиска F входят атрибуты только из множества a1...an тогда ?a1...an(?F(R))=?F(?a1. .an(R)) 2) Допустим, в условия поиска F входят атрибуты не только из множества a1...an, но и из b1...bn тогда ?a1...an(?F(R))=?a1...an( F(?a1...an,b1...bn(R))) Селекция декартова произведения Отношение f1 содержит атрибуты только из отношения R1 тогда ?f1(R1?R2)=?f1(R1)?R Следствие: пусть F=f1?f2 и в f1 входят атрибуты R1, а в f2 входят из R2, тогда ?F(R1?R2)=?f1(R1)??f2 R2) Доказательство: ?f1?f2(R1?R2)=?f1(?f (R1?R2))=?f1(?f2(R2?R ))= =?f1(R1??f2(R2))=?f1(R )??f2(R2) Закон перестановки селекции и объединения ?F(R1?R2)=?F(R1)??F(R ) Закон перестановки селекции и разности отношений ?F(R1?R2)=?F(R1)??F(R ) Закон перестановки проекции и декартова произведения b1...bn - это атрибуты отношения R1 c1...ck - это атрибуты отношения R2 ?b1...bn,c1...ck(R1?R2) = ?b1...bn(R1)??c1...ck(R2) Закон перестановки проекции и объединения ?a1...an(R1?R2)=?a1...an R1)??a1...an(R2) Оптимизация формул реляционной алгебры Пусть условие F=f1?...?fn Правила: 1. переместить каждую селекцию внутрь декартова произведения, используя законы 1, 4, 6, 7, 8; 2. переместить каждую проекцию внутрь декартова произведения, используя законы 1, 3, 5, 9, 10; 3. по возможности скомбинировать каждый каскад селекции в одиночную селекцию и каждый каскад проекции в одиночную проекцию. Тогда всё можно будет сделать за один проход. После выполнения этих трёх правил выражение ?A(?F(R1?...?Rn)) преобразуется к виду: ?A(?F(?A1(?f1(R1))?...? An(?fn(Rn))), здесь каждый ?Ai(?fi(Ri)) - это подзапрос. Суть в том, что сначала выполняются подзапросы, а они имеют намного меньшую размерность, чем исходная таблица, и время выполнения будет меньше, чем по исходной формуле ?A(?F(R1?...?Rn)). Логический план Построение логического плана Порядок построения: 1. запрос преобразуется в формулу реляционной алгебры; 2. выполняется преобразование (оптимизация) этой формулы. Оператор SELECT (без агрегирования, группирования и удаления дубликатов) может быть представлен так: ?A(?F(R1?...?Rn)), где от R1 до Rn - это декартово произведение отношений (таблиц), указанных за ключевым словом FROM; ?F - это селекция кортежей декартова произведения в соответствии с условием, указанным за ключевым словом WHERE; ?A - это проекция селекции на множество атрибутов A, указанных за ключевым словом SELECT В чём суть такой логической оптимизации? Сначала надо выполнить декартово произведение, потом селекцию, потом проекцию - всё по порядку скобок в этом выражении. Потому что если таблица имеет большой размер, то это выражение будет выполняться очень долго. Пример: найти фамилии поставщиков, поставляющих детали с названием "винт". ?=(S,P,SP) SELECT фамилия FROM S, P, SP WHERE P.название = винт AND S.номер_поставки = SP.номер_поставки AND SP.номер_детали = P.номер_детали; ?фамилия(?P.н="винт" S.н?п=SP.н?п?SP.н?д= .н?д(S?P?SP ) После преобразования и выделения подзапросов (как в описании, приведённом выше) получится выражение ?A(?F(?Ai(?f2(R1))?...? An(?fn(Rn))), которое можно представить в графическом виде - это и будет логический план выполнения запроса:
Получается, подзапросы можно выполнять параллельно, а это тоже уменьшает время выполнения всего запроса. Пример:
Запрос найти значение остатков больше 1500 на счетах пользователя с кодом 3: SELECT остаток FROM R2 WHERE остаток › 1500 AND номер_счёта IN( SELECT номер_счёта FROM R1 WHERE код_пользователя = 3 ); Этот запрос преобразуется сервером в неявном виде в формулу реляционной алгебры: ?остаток(?R2.о›1500?R1.к?п=3?R1.н?c= 2.н?с(R1?R2)) Теперь оптимизируем: =4?остаток(?R1.н?c=R .н?с(?R2.о›1500?R1.к?п=3(R1?R2)))= =?остаток(?R1.н?c=R2 н?с(?R1.к?п=3(R1)??R2 о›1500(R2)=5,2 =?остаток(?R1.н?c=R2 н?с(?остаток,R1.н?с, 2.н?с(?R1.к п=3(R1)??R2.о›1500(R2))=9 =?остаток(?R1.н?c=R2 н?с(?R1.н?с(?R1.к?п= (R1))??R2.н с,остаток(?R2.о›1500(R2))) Полученное выражение - результат оптимизации. Можно построить логический план выполнения запроса.
? Лекция №10 - Логический и физический план запроса
Оптимизация SQL-запросов Логический план Порядок выполнения запроса на логическом уровне Пример с предыдущей лекции: ?остаток(?R1.н?c=R2. ?с(?R1.н?с(?R1.к?п=3 R1))??R2.н? ,остаток(?R2.о›1500(R2))) Каждый из подзапросов - это промежуточные таблицы Q1 и Q2. 1)
2) соединение Q1 и Q2 (естественное соединение):
Вот этот результат и передаётся от СУБД на рабочую станцию. А теперь предположим, что таблицы R1 и R2 находятся на разных серверах. В этом случае, подзапросы Q1 и Q2 после оптимизации на сервере-оптимизаторе преобразуются в SELECT. Q1: SELECT R1.ном.сч FROM R1 WHERE R1.код.польз = 3; Q2: SELECT R2.ном.сч, R2.ост FROM R2 WHERE R2.ост › 1500; Эти подзапросы направляются на сервера, где хранятся соответствующие таблицы, там они параллельно выполняются, результаты возвращаются серверу-оптимизатору а от него - пользователю. Физический план Построение физического плана При построении оптимального физического плана СУБД выполняет следующие действия: 1. Последовательно строится множество физических планов на основе логического плана. Эти физические планы отличаются следующим: 1. методом выбора записей из исходных таблиц (методом реализации подзапросов); 2. порядком соединения промежуточных таблиц Qi (комбинация вариантов соединения нескольких таблиц); 3. методом соединения таблиц (вложенными циклами, сортировкой слияния или ещё как); 2. Для каждого физического плана оценивается его стоимость и выбирается план с наименьшей. В стоимости учитывается и процессорная составляющая, и составляющая времени ввода/вывода. Методы выбора записей из исходной таблицы Чтение всех записей и фильтрация TableScan + Filter
Формула стоимости: Cost?=CCPU+CIO CCPU=T(R)?Cfilter CIO=B(R)?CB здесь: T(R) - общее количество записей в таблице R; B(R) - число физических блоков в таблице R; Cfilter - среднее время фильтрации одной записи; CB - время чтения/записи одного блока на диск. Чтение записей из индекса и фильтрация IndexScan + Filter
Формула стоимости: Cost?=CCPU+CIO CCPU=T(R)I(R,a)?Cfilt r CIO - как и в предыдущем методе, умножаем время чтения/записи на число записей в блоке индекса. Но тут два варианта: 1. для кластеризованного: CIO=B(Index(R,a))I(R, )?CB+B(R)?kI(R,a)?CB В кластеризованном индексе последовательность значений в индексе и в таблице совпадает; 2. для индекса без кластеризации CIO=B(Index(R,a))I(R, )?CB+T(R)?kI(R,a)?CB Последовательность в индексе и таблице не совпадает. Число в этом случае читаемых записей равно числу блоков. Или наоборот. здесь: T(R) - общее количество записей в таблице R; B(R) - число физических блоков в таблице R; I(R,a) - мощность индексируемого атрибута a таблицы R (число разных значений, исключая пустое множество); B(Index(R,a)) - число блоков на листовом уровне индекса по атрибуту a; Cfilter - среднее время фильтрации одной записи; CB - время чтения/записи одного блока на диск; k - мощность атрибута a в запросе (число разных значений, указанных в подзапросе y). Определение k: • k=1, если y: a=const; • k=n, если y: a IN (C1...Cn), Ci=const; • k= диапазон значений, если y: a›=C1 AND a‹=C2; • k= число атрибутов, удовлетворяющих образцу, если y: a LIKE чтонить. Отличие физического плана от логического Логический план не указывает, как реализуются операции реляционной алгебры, а физический определяет, как они будут реализованы. Пример логического плана
Пример физического плана
Данный физический план реализуется следующим образом; 1. для реализации подзапроса к R1 читается вся таблица, записи фильтруются по f1 и получаемая таблица является правым аргументов в операции соединения; 2. из таблицы R2 выделяется подусловие y для индексируемого атрибута, а потом выполняется чтение записей, удовлетворяющих этому условию. Полученные записи фильтруются по f2 и получаемая таблица является левым аргументом в операции соединения. Как мы уже знаем, оптимизатор для каждого физического плана рассчитывает стоимость. Рассмотрим этот расчёт для данного примера: Cost?=Cost(TableScan R1),Filter(f1,?A1))+C st(IndexSc n(R2,y),Filter(f2,?A ))+Cost(?) Каждая из Cost() учитывает и процессорную составляющую, и временную составляющую ввода-вывода. ? Лекция №11 - Оценки
Оптимизация SQL-запросов Физический план Методы выбора записей из исходной таблицы Оценка числа кортежей в промежуточной таблице В таблице Q. Вычисляется по формуле: Q=?A(?f(R)) T(Q)=T(R)?p здесь: Q - промежуточная таблица; T(Q) - число кортежей в промежуточной таблице; T(R) - число записей в исходной таблице R; p - вероятность того, запись из таблицы R удовлетворяет условию F. Расчёт p: 1. если f=F1?F2, то p=p1?p2; 2. если f=F1?F2, то p=p1+p2?p1?p2; 3. если f=F1???, то p=1?p1. Для i-ой вероятности: pi=kI(R,a) здесь: k - мощность атрибута a в запросе; I(R,a) - мощность атрибута a в таблице R. Пример Допустим, T(R)=1000, I(R,a)=5, I(R,b)=10, I(R,c)=2, где a,b,c - положительные натуральные числа. И f=(a‹3 OR b?5) AND c=2 Найти T(Q). Обозначим: • a‹3 как F1; • b?5 как F2; • f=(a‹3 OR b?5) как F3; • c=2 как F4. 1) F1?F2=F3 p3=p1+p2?p1?p2=25+61 ?25?610=0.76 2) f=F3?F4 p=p3?p4=0.76?12=0.38 - это вероятность того, что запись из R удовлетворяет условию f. 3) T(Q)=1000?0.38=380 Оценка количества блоков Q=?A(?f(R)) B(Q)=[T(Q)LB] - скобки обзначают, что огругление с избытком. здесь: T(Q) - прогнозируемое число записей в подзапросе; LB - длина блока (число записей в блоке) с учётом ?A. Порядок соединения промежуточных таблиц Деревья соединения Используются деревья соединения, которые бывают трёх видов: • левостороннее; • кустовое, ветвящееся; • правостороннее. Левостороннее Предположим, соединяются таблицы R,S,T,U:
В каждом соединении правым аргументом является одна из таблиц. Преимущества: • число перебора вариантов меньше, чем для произвольного варианта соединения (если количество соединений n, то вариантов перебора будет n!); • достаточно просто организивать каналы обработки - возможность передачи результата выполнения одной операции на вход другой через оперативную память (без сохранения на диск); В канале левый аргумент называется опорным и он должен храниться в оперативной памяти. Правый аргумент называется тестируемым и он может храниться и на диске. При хранении в оперативной памяти не надо читать с диска, потому всё можно выполнить за один проход. Недостатки: • путём перебора порядков соединения можно выбрать квазиоптимальный план (потому что на самом деле вариантов перебора больше, чем n!, потому что правый аргумент - всегда таблица). Кустовое Тут таблицы могут соединяться в любом порядке.
Так что перебираются все возможные варианты соединения. Преимущества: • всегда выбирается оптимальный план. Недостатки: • если количество соединяемых таблиц велико, то перебор всех деревьев может занять много времени; • могут возникнуть сложности в организации канала обработки, так как возрастают требования к объёму оперативной памяти. Чтобы реализовать соединение за один проход, в памяти должно храниться слишком много таблиц. Правостороннее При таком порядке левым аргументом каждого соединения является исходная таблица.
Такой способ практически не используется, потому что для него требуется, чтобы каждая из исходных таблиц и промежуточные результаты могли уместиться в оперативной памяти. Методы соединения таблиц Методы реализации естественного соединения ?. Три метода: • вложенных циклов (NLJ - Nested Loop Join); • сортировки слияния (SMJ - Sort Merge Join); • хэшированных соединений (Hash Join). ? Лекция №12 - Оценки (продолжение)
Оптимизация SQL-запросов Физический план Методы соединения таблиц Метод вложенных циклов (NLJ, Nested Loop Join) Каждая запись первой соединяемой таблицы сравнивается с каждой записью второй соединяемой таблицы. В общем случае, условие сравнения может быть произвольным.
Зависит от: • используемого дерева соединения (но мы в дальнейшем всегда будем использовать левосторонние); • назначения буферов ввода/вывода.
Если на 3 операции блоков будет больше b, то лишние сохраняются на диск. Формулы оценки стоимости соединения NLJ CJOIN=CCPU+CI/O CCPU=T(Q1)?T(Q2)?Ccom CI/O=CI/O(Q2)??B(Q1)b здесь: T(Q1), T(Q2) оценка числа записей в таблицах подзапросов Q1 и Q2; B(Q1) - число блоков ввода/вывода для получения таблицы Q1; CI/O(Q2) - время ввода/вывода для получения таблицы Q2; b - число блоков в буферах 1 и 3 (из рисунка выше); Ccomp - время сравнения двух кортежей из Q1 и Q2 в оперативной памяти; неполные квадратные скобки означают округление с недостатком, так как одно чтение с диска учитывается в стоимости выбора записей из исходных таблиц. Метод сортировки слияния (SMJ, Sort Merge Join) Соединение двух таблиц этим методом выполняется по следующим шагам: 1. соединяемые таблицы сортируются по атрибуту соединения, будем обозначать его через a; 2. организуется вложенный цикл, где выполняется сравнение значения атрибута соединения в записях таблиц Q1 и Q2. Условием соединения может быть только равенство атрибутов соединения. Рассмотрим пример реализации второго шага. Выполняется сравнение записей в таблицах Q1 и Q2, на которые указывают указатели. Перемещение указателей выполняется следующим образом: • если выполняется условие ‹, то указатель перемещается в таблицу Q1; • если выполняется условие ›, то указатель перемещается в таблицу Q2; • если выполняется условие =, то результат соединения перемещается в выходной буфер, указатели не перемещаются и выполняется сравнение со следующей записью из таблицы Q2.
Результат соединения Q1 и Q2 получается уже отсортированным. Формулы оценки стоимости соединения SMJ CCPU=[CSORTCPU(Q1)]+[ SORTCPU(Q2)]+CJOINCP (Q1,Q2) CI/O=[CSORTI/O(Q1)]+ CSORTI/O(Q2)]+CJOINI O(Q1,Q2) CSORTCPU(R)=T(R)?log (T(R)?B(R)/b?)?(Ccom +Cmove)+(lo bB(R)?1)?T(R)?(b?Cco p+Cmove) CSORTI/O(R)=2?B(R)?C Далее возможны варианты: • CJOINCPU(Q1,Q2)=((T Q1)I(Q1,a)+2)?T(Q2)+ (Q1)?(1?I( 2,a)I(Q1,a)))?Ccomp, если I(Q1,a)›I(Q2,a); • CJOINCPU(Q1,Q2)=((T Q2)I(Q2,a)+2)?T(Q1)+ (Q2)?(1?I( 1,a)I(Q2,a)))?Ccomp, если I(Q2,a)›I(Q1,a). CJOINI/O=[B(Q1)]+[B( 2)]+(T(Q1)Q2,a??B(Q1) (Q2,a)?b?? ?min(I(Q1,a),I(Q2,a) ?CB здесь: T(Q1), T(Q2) - оценка числа записей в таблицах Q1 и Q2; B(Q1), B(Q2) - оценка числа блоков в этих же таблицах; I(Q1,a), I(Q2,a) - мощности атрибутов в соединении a тех же таблиц; b - число блоков в оперативной памяти, отводимое под сортировку этих таблиц, а также для выполнения соединения; Ccomp - среднее время соединения двух кортежей из записей этих таблиц в оперативной памяти; Cmove - время перемещения одной записи в оперативной памяти при сортировке; CB - время чтения/записи одного блока на диск; верхние неполные квадратные скобки - округление с избытком; нижние неполные квадратные скобки - округление с недостатком; обычные квадратные скобки - необязательность, значит уже отсортировано. Механизм сортировки таблиц Механизм сортировки таблиц Q1 и Q2: 1. блоки таблицы R читаются в буфер и там сортируются. Получается файл, который сохраняется на диск; 2. в буфер читаются ещё блоки. Таким образом, на диске будет сохранено несколько файлов, и в каждом записи будут отсортированы. Эти файлы образуют первый уровень. Каждый файл можно рассматривать как стек записей. В буфере из b блоков сравниваются первые записи сохранённых на предыдущем этапе файлов (то есть, b файлов, если все сразу сравнивать не можем, потому что их сильно много). Минимальное среди сравниваемых записей значение пишется в файл следующего уровня, а стек, из которого это значение взяли, поднимается. На следующем уровне история повторяется, и так до тех пор, пока не получится один итоговый файл. Записи в нём будут идеально отсортированы. T(R)?B(R)/b? - оценка числа записей в одном файле первого уровня. T(R)?B(R)/b??log2T(R) B(R)/b? - число операций сравнений и перемещений записей при сортировке одного файла первого уровня. Но таких файлов B(R)b. Перемножая их, получаем общее число операций. ? Лекция №13 - Оценки (продолжение)
Оптимизация SQL-запросов Физический план Методы соединения таблиц Метод сортировки слияния (SMJ, Sort Merge Join) Формулы оценки стоимости соединения Расчёт числа формул: l=B(R)bl=1, отсюда l=logbB(R) T(R)=logbB(R)?1 Для каждой записи нужно выполнить b?CCOMP+Cmove - это объясняет второе слагаемое. Число уровней: logBb(R) Число блоков: B(R). Так как пишем и читаем, то B(R)?2 Теперь разбираемся со следующей формулой: I(Q1,a)›I(Q2,a) - мощность у первого больше. Смотрим первое слагаемое: (T(Q1)I(Q2,a)+2)?T(Q ) - происходит соединение каждой записи из Q2 с каждой из Q1 Смотрим второе слагаемое: T(Q1)I(Q2,ar)?(I(Q1, )?I(Q2,a)) Следующая формула: [B(Q1)] ... T(Q1)I(Q1,a)??B(Q1)I( 2,a)?b??b?min(I(Q1,a) I(Q2,a)) На каждую запись нужно выполнить такое число операций чтения и записи в буфер. Метод хешированных соединений (Hash Join) Осуществляется по следующим шагам: 1. Выполняется хеш-функция, где a - атрибут соединяемых таблиц; 2. Записи соединяемых таблицы хешируются, то есть создаются разделы (Ri и Si); 3. Выполняется соединение соответствующих разделов (Ri?Si) по алгоритму NLJ или SMJ. Пример хешированного соединения Предположим, заданы две таблицы (после выполнения подзапросов).
По шагам: 1) в качестве хеш-функции выберем остаток от деления на 10: h(a)=a mod 10 2) Ri - подмножество номеров счетов из таблицы R, у которых значение хэш-функции равно i=0..9 Si - подмножество номеров счетов из таблицы S, у которых значение хэш-функции равно i=0..9 представим эти разделы в виде таблицы. Будет 9 разделов.
Разделы соединяются по диагонали. Потому что если остатки от деления разные, то и номера счетов разные. Остальные смотреть не смысла, потому что разные остатки. При значительных объёмах таблиц выигрыш от использования соединения методом хэширования может быть очень значительным, так как соединяемые разделы имеют намного меньшую размерность, чем сами таблицы. Реализация метода может быть различной. Однопроходной вариант реализации Разделы опорной таблицы R хранятся в оперативной памяти. Алгоритм: 1. читаются блоки таблицы S из внешней записи; 2. для каждой записи из S выполняется хеширование атрибута соединения (i); 3. значение атрибута a сравниваются со значениями атрибута соединения в разделе Ri. Двухпроходной вариант реализации Оперативной памяти может не хватать. Число размеров (точнее, хеш-функция) подбирается так, чтобы максимальный раздел таблицы R помещался в оперативной памяти. При таком подходе после хеширования таблиц R и S все разделы сохраняются на диске. Алгоритм: 1. подбирается хеш-функция; 2. хеширование таблицы; 3. раздел R0 целиком читается в оперативную память; 4. в оперативную память поблочно читается раздел S0; 5. для каждой записи раздела S0 значение атрибута a сравнивается со значением атрибута соединения в разделе R0; 6. считываются следующие разделы (R1, R2 и так далее). Отличие от методов NLJ и SMJ Метод хешированного соединения имеет важную особенность. В методах NLJ или SMJ соединяемые таблицы должны уже храниться на сервере перед выполнением соединения. А в этом методе соединение таблиц может выполняться асинхронно, по мере поступления записей с других серверов.
На серверах 1 и 2 выполняются подзапросы, а на сервере 0 выполняется соединение. Предположим, с сервера 2 на сервер 0 поступила очередная запись из таблицы S. При этом СУБД на сервере 0 выполняет следующие действия: 1. вычисляется хеш-функция для атрибута соединения; 2. значение атрибута соединения сравнивается со значениями атрибутов соединения из раздела R1. Если есть совпадения, то выводятся результаты соединения; 3. запись сохраняется в разделе Si. 4. и так далее. ? Лекция №14 - Оценки (продолжение) Оптимизация SQL-запросов Физический план Методы соединения таблиц Число кортежей, блоков и мощности атрибутов в соединениях Справедливы для NLJ, SMJ и HJ. 1) количество кортежей в соединении: T(Q1?Q2)=T(Q1)?T(Q2) ax(I(Q1,a),I(Q2,a)) 2) числов блоков: B(Q1?Q2)=?T(Q1?Q2)JO N? - верхние неполные квадратные скобки означают округление с избытком; 3) мощности атрибутов: • атрибутов (a) в результирующей таблице: I(Q1?Q2,a)=min(I(Q1, ),I(Q2,a)) • остальных атрибутов (b): два варианта: • I(Q1?Q2,b)=min(T(Q ?Q2,I(Q1,b)), если b - атрибут таблицы Q1; • I(Q1?Q2,b)=min(T(Q ?Q2,I(Q2,b)), если b - атрибут таблицы Q2. Алгоритмы для поиска физического плана Алгоритмы описываются на псевдоязыке с заимствованиями из C++: • комментарии обозначаются косыми: // камент • обращение к полям структуры через точку: структура.поле Алгоритм поиска физического плана с минимальной стоимостью (для левостороннего дерева) Вход: логический план выполнения запроса с таблицами R1..Rn (декартово соединение таблиц). Выход: квазиоптимальный (потому что рассматриваем левосторонние деревья) план выполнения запроса. @НАЧАЛО АЛГОРИТМА ДЛЯ i=1,n AccessPlan(Ri); // определение параметров подзапроса Qi=?Ai(?fi(Ri)). КОНЕЦ ДЛЯ // поиск оптимального плана ДЛЯ i=2,n ДЛЯ всех подмножеств P?Q1..Qn, // для i=2 // P=(Q1,Q2), P=(Q2,Q3), P=(Q1,Q3) // для i=3 // P=(Q1,Q2,Q3) и так же все варианты комбинаций ДЛЯ всех таблиц Qj?P JoinPlan(P?Qj,Qj) // (P?Qj)?Qj КОНЕЦ ДЛЯ КОНЕЦ ДЛЯ КОНЕЦ ДЛЯ // вывод оптимального плана OptPlanReturn(Q1..Qn) @КОНЕЦ АЛГОРИТМА Массив структур Процедуры из алгоритма выше: • AccessPlan(); • JoinPlan(); • OptPlanReturn(). Процедуры алгоритма работают с массивом структур. Формат экземпляра структуры: W X Y Z ZIO V W: если мощность W›1, то W?Qi, W=X?Y; если мощность W=1, то W - это имя таблицы {Q_i}}}. X: X?Qi, которые были использованы в качестве левого аргумента соединения. Y: имя таблицы Qi, которая была использована в качестве правого аргумента соединения. Если мощность W=1, то X и Y пустые. Z: если W›1, Z - текущая стоимость выполнения плана, включающая стоимость выполнения подзапросов и промежуточных соединений; если W=1, Z - оценка времени выполнения(?) Qi. ZIO: составляющая Z, касающаяся ввода/вывода. V: опции. Включает в себя: 1) число записей: • если мощность W›1, то T(W) - число прогнозируемых записей; • если мощность W=1, то T(Qi) - оценка числа записей в подзапросе; 2) B(W) - прогнозируемое число блоков; 3) I(W,Ai) - мощности атрибутов, по которым было выполнено или выполняется соединение; 4) идентификатор: • если мощность W›1, то k - идентификатор метода соединения таблиц; • если мощность W=1, то k - идентификатор метода выбора записей из исходных таблиц. AccessPlan() Вход: Ri - имя исходной таблицы. Выход: str[i] - заполненный экземпляр структуры (описанной выше). @НАЧАЛО АЛГОРИТМА // оценка стоимости выбора записей из Ri для различных методов // j=1 - TableScan // j=2 - IndexScan ДЛЯ i=1,2 Cj=CCPU+CI/O // для разных j разные формулы из прошлых лекций КОНЕЦ ДЛЯ // определение оптимального метода выбора записей из Ri С=min(C1,C2) // здесь C=Ck // заполнение экземпляра str[i] str[i]= { Qi, ?, ? // W, X, Y C, CI/Ok // Z, ZIO T(Qi),B(Qi),min(T(Qi ,I(Ri,Ai)),k // V } @КОНЕЦ АЛГОРИТМА JoinPlan() Вход: R=(P?Qj), S=Q. Выход: str[n]. @НАЧАЛО АЛГОРИТМА 1) // поиск в массиве структур str[] номеров экземпляров m1 и m2, для которых str[m1].W=R и str[m2].W=S // оценка стоимости соединения для различных методов // если i=1, то NLJ // если i=2, то SMJ // если i=3, то HJ // k - выбор оптимального из этих трёх 2) ДЛЯ i=1,3 Ci=CCPUi+CI/Oi // для разных i разные формулы из предыдущих лекций КОНЕЦ ДЛЯ C=min(C1,C2) // стоимость соединения R и S C=str[m1].Z+str[m2]. +C 3) // поиск str[n].W=P // а) если такого экземпляра не существует, то заполнить очередной пустой экземпляр n. // б) если такой экземпляр найден, то сравнить стоимость выполнения плана. И если str[n].Z›C, то перезаписать экземпляр n. str[n]= { P, R, S // W, X, Y C, CI/Ok // Z, ZIO T(P),B(P),I(P,Ai)i,k // V } @КОНЕЦ АЛГОРИТМА OptPlanReturn() Вход: список таблиц Qi=Q1..Qn Выход: вывод оптимального плана. @НАЧАЛО АЛГОРИТМА 1) // поиск в массиме структур str[] экземпляра, который str[i].W=Q печать(Q, " = ", str[i].X, " ? ", str[y].Y, " метод ", str[i].V.k) 2) // если поле str[i].X пусто, то выйти из алгоритма // иначе рекурсивно вызываем сами себя, OptPlanReturn(str[i] X) // вывод оптимального плана для левого аргумента соединения 3) OptPlanReturn(str[i] Y) // вывод метода выбора записей из правого аргумента соединения @КОНЕЦ АЛГОРИТМА ? Лекция №15 - Пример оценки Оптимизация SQL-запросов Методы соединения таблиц Алгоритмы для поиска физического плана Пример оценки физического плана Исходные данные: 1) количество записей в таблице T(R1) = 1000, количество записей в таблице T(R2) = 1000; 2) количество записей в одном блоке таблицы L(R1)=L(R2) = 100, количество записей в соединении LJOIN = 1000; 3) количество записей в блоке индекса код_пользователя {{Формула|f=L} = 200, количество записей в блоке индекса номер_счёта {{Формула|f=L} = 200; Примечание: записи исходных таблиц могут читаться в сортированном виде по своим индексированным атрибутам. Записи в таблице R1 сгруппированы по атрибуту код_пользователя (кластеризованный индекс), а в таблице R2 не сгруппированы. 4) мощность атрибутов: • R1, код_пользователя 5000; • R1, номер_счёта 1000; • R2, номер_счёта 1000 • R2, остаток - неизвестно. 5) тут почему-то пусто 6) b = 10, CCOMP=CMOVE=Cfilter=0 01 мс, CB=10 мс. Для построение оптимального физического плана используется алгоритм динамического программирования (из предыдущей лекции). Алгоритм: 1) AccessPlan а) R1 - таблица пользователи; j=1, чтение всей таблицы C1=CCPU1+CI/O1=T(R1)? filter+B(R1)?CB=1000?0 01+1000 100?10=1100 мс j=2 - индекс по атрибуту код_пользователя C2=CCPU2+CI/O2=T(R1)? I(R1,a)?Cfilter+B(In ex(a))?kI( 1,a)?Cb+B(R2)?kI(R1, )= =1000?15000?0.01+(1000/200) 15000?10+1000/100?1500 ?10=0.02+0.3=0.32 мс С=min(С1,С2)=0.32 мс СI/O=CI/O2=0.3 мс T(Q1)=T(R2)?Pкод_пол зователя=3=T(R2)?kI( 1,a)=1000? /5000=2 B(Q1)=?T(Q1)L(R1)?10 =?2100?10?=1 str[1]={{Q1},?,?,0.32 0.3,{2,1,{2},2}} б) R2 - таблица счёт. j=1 C1=1000?0.01+1000100?10=1 000 мс j=2 C=C1=11000 мс CI/O=CI/O1=1000 мс T(Q2)=T(R2)?PR2.оста ок›1500=1000?1/3=33000, вероятность принята равной 1/3, так как по условию эта мощность неизвестна B(Q2)=?T(Q2)L(R2)?10 =?33000100?10?=33 str[2]={{Q2},?,?,11000,1 00,{33000,33,{33000},1}} 2) JoinPlan m1=1, m2=2 - номера экземпляров структур, таких, что str[m1].W=Q1 и str[m2].W=Q2 а) i=1, NLJ C1=CCPU1+CI/O1=T(Q1)? (Q2)?CCOMP+?B(Q1)b??CI O(Q2)=2? 3000?0.01+?110??1000=660 мс i=2, SMJ таблица Q2 уже отсортирована по номер_счёта, так как имеется индекс по номеру счёта С2=СCPU2+CI/O2=CSORT PU(Q1)+СJOINCPU(Q1,Q )+CSORTI/O( 1)+CJOINI/O(Q1,Q2)= =2?log22?1/10??(0.01+0 01)+(log101?1)?2?(10 0.01+0.01 +((3300033000+2?2+ +33000?(1?233000))?0.01+(2? ?log10?1)?10+(1+0)?1 =340 мс C=min(C1,C2)=340 C=str[1].Z+str[2].Z+ =0.32+11000+340=11340.32 мс CI/O=str[1].ZIO+str[ ].ZIO+CI/O2=0.3+1000+1 =10010.3 мс T(Q1?Q2)=T(Q1)?T(Q2) ax(I(Q1,a),I(Q2,a))=2 33000max(2 33000)=2 B(Q1?Q2)=?21000?=1 I(Q1?Q2,a)=min(I(Q1, ),I(Q2,a))=min(2,33000)= str[3]={{Q1,Q2},{Q1}, Q2},11340,10010,{2,1,{ },2}} б) структура остаётся такая же 3) OptPlanReturn - вывод оптимального плана и представление этого плана в графическом виде. 1) (Q1,Q2)=Q1?Q2 2) Q1=(IndexScan()+Filt r()) 3) Q2=(TableScan()+Filt r())
