Базы данных (стр. 6 )

Добавление осуществляется с помощью префикса Add., удаление – Del., обновление – Upd..

Запрос 19. Добавить для Курска детали с номером 323 в количестве 100 штук.

Наличие ЧН А К Add. 323 Курск 100

 

Запрос 20. Удалить информацию о деталях 247 для города Тула

Наличие ЧН А К Del. 247 Тула

 

Запрос 21. Изменить количество деталей с номером 323 в Курске на 134

Наличие ЧН А К 323 Курск Upd.134

 

Обработка запросов

Обработка запросов – действия, необходимые для извлечения требуемой информации из базы данных. Целью процедуры обработки запросов является преобразование запроса, написанного на языке высокого уровня (обычно SQL), в корректную и эффективную последовательность операций (план запроса), записанную на языке низкого уровня, реализующего операции РА. Далее подготовленный план запроса выполняется с целью выборки требуемых данных.

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

Процесс обработки запроса может быть разделен на четыре основных этапа:

·  Декомпозицию (включает процедуры сканирования и проверки).

·  Оптимизацию.

·  Генерацию кода.

·  Выполнение.

 

Существует два варианта выполнения первых трех этапов процесса оптимизации запросов. В первом случае декомпозиция и оптимизация выполняются динамически, при каждом вызове запроса. Преимущество динамической оптимизации запросов состоит в том, что вся используемая в процессе выбора оптимальной стратегии информация является актуальной именно на текущий момент времени. Основной недостаток динамической оптимизации состоит в относительном снижении эффективности обработки запросов, поскольку этапы сканирования, проверки и оптимизации выполняются при обработке каждого из запросов.

Альтернативным вариантом является статическая оптимизация запроса, предусматривающая однократное выполнение этапов, сканирования, проверки и оптимизации. Этот подход подобен использованию компиляторов для обработки программ. Основное преимущество статической оптимизации состоит в устранении дополнительной нагрузки из-за выполнения процедур оптимизации в процессе выполнения запроса. Основной недостаток этого метода состоит в том, что выбранная стратегия выполнения запроса, которая была оптимальной при компиляции запроса, в момент выполнения запроса может оказаться уже не самой оптимальной.

Декомпозиция запросов

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

Анализ.

На этой стадии выполняется лексический и синтаксический анализ запросов с использованием методов, применяемых в компиляторах языков высокого уровня (Ахо и Ульман). Уточняется присутствуют ли в системном каталоге определения для указанных в запросе отношений и атрибутов. Кроме того контролируется могут ли затребованные операции над различными операторами БД быть применимыми к объектам соответствующего типа.

После завершения данной стадии декомпозиции запрос на языке высокого уровня преобразуется к некоторому внутреннему представлению, более удобному для последующей обработки. Как правило, для внутреннего представления запроса вбирается та или иная форма дерева запроса. Дерево запроса конструируется следующим образом:

1.  Листовые узлы задаются для каждого используемого в запросе базового отношения.

2.  Нелистовые узлы задаются для каждого промежуточного отношения, создаваемого в результате выполнения некоторой операции реляционной алгебры.

3.  Корень дерева представляет результирующий набор данных запроса.

4.  Запросы выполняются от листовых узлов к корню дерева.

Пример реализации запроса в РА. О. студентов и группы, в которых они учатся, имеющих задолженности по курсу «Базы данных».

Выполним запрос в несколько этапов:

1.Определим коды предметов, имеющих наименование «Базы данных».

.

2.Найдем ведомости по этим предметам.

3.Найдем результаты экзамена в этих ведомостях.

4.Определим результаты, соответствующие задолженностям.

5.Определим, имеющих эти результаты.

6.Окончательный результат.

 

Нормализация

При оптимизации запросов стадия нормализации служит для преобразования запроса в нормализованную форму, что выполняется с целью упрощения манипулирования им. На этой стадии предикаты, входящие в предложение SQL Where, преобразуются в одну из двух форм (КНФ или ДНФ).

Семантический анализ

Целью проведения семантического анализа является отклонение нормализованных запросов, которые некорректно сформулированы или содержат противоречивые требования. Запрос считается некорректно сформулированным, если его выполнение никогда не сможет привести к созданию результирующего набора данных. Чаще всего такая ситуация возникает тогда, когда в предикате отсутствует определение необходимых операций соединения. Запрос считается противоречивым, если его предикат никогда не сможет удовлетворить каким-либо кортежам. Например, запрос Select FIOS From Student Where Nzach = “АП2001/43” And Nzach = “АП2200/43” является противоречивым, поскольку в таблице Student не может быть студента с разными номерами зачетки. Аналогично, запрос Select FIOS From Student Where (Nzach = “АП2001/43” And Nzach = “АП2200/43”) Or YearEnter > 2000 может быть заменен на запрос Select FIOS From Student Where YearEnter > 2000, поскольку его противоречивую фразу можно заменить на логическое значение False.

Алгоритм определения корректности существует только для подмножества запросов, не содержащих операций дизъюнкции и отрицания. По отношению к этому множеству запросов могут применяться следующие проверки.

1.Построение графа соединения отношений. Если элементы графа оказываются разъединенными, формулировка запроса является неверной. При построени графа соединения отношений сначала создается отдельный узел для каждого используемого в запросе отношения, а также для результирующей таблицы запроса. Затем между парами узлов проводятся дуги, представляющие операции соединения, и дуги вокруг отдельных узлов, представляющие проекции исходных таблиц. Пусть запрос «О. студентов и группы, в которых они учатся, имеющих задолженности по курсу «Базы данных».» записан следующим образом Select Student.FIOS, Student.Sgroup From Student, Vedom, Ekzamen, Predmet Where Ekzamen.CodOcen > 3 And Predmet.Predm = “Базы данных” And Vedom.Nved = Ekzamen.Nved And Predmet.CodPredm = Vedom.CodPredm And Ekzamen.CodOcen <=2.

Построим для него граф соединения отношения.

 

В этом графе есть не соединенные между собой отношения. Это указывает на то, что данный запрос сформулирован неверно. Ошибка состоит в том, что в предложении Where пропущено соединение Ekzamen.Nzach = Student.Nzach.

2.Построение графа соединений нормализованных атрибутов. Если граф включает петлю, для которой сумма оценок является отрицательной, то запрос содержит противоречивые условия. При построении графа соединений нормализованных атрибутов сначала создаются отдельные узлы для каждой ссылки на атрибут и константы 0. Затем проводятся направленные дуги между узлами, представляющие операции соединения, а также направленные дуги между узлами атрибутов и констант 0, которые представляют операции выборки. Далее каждому ребру a ® b присваивается весовое значение c, если оно представляет условие, записанное в виде неравенства (a £ b + c), а каждому ребру 0 ® a значение –c, если оно представляет условие типа (a ³ c).

Select Student.FIOS, Student.Sgroup From Student, Vedom, Ekzamen, Predmet Where Ekzamen.CodOcen > 3 And Predmet.Predm = “Базы данных” And Vedom.Nved = Ekzamen.Nved And Predmet.CodPredm = Vedom.CodPredm And Ekzamen.CodOcen <=2 And Ekzamen.Nzach = Student.Nzach

 

Этот граф включает петлю между узлами Ekzamen. CodOcen и 0, для которой сумма весовых значений является отрицательной, и, следовательно, не может быть студента, получившего оценку по «Базам данных» равную или большую четырех, и одновременно быть задолжником по этому предмету.

Упрощение

Целью выполнения операции упрощения является выявление избыточных классификаторов, исключение общих подвыражений и преобразование запроса в семантически эквивалентную форму, позволяющую упростить требуемые вычисления или повысить эффективность их выполнения. На этой же стадии рассматриваются существующие ограничения доступа, раскрываются определения используемых представлений и учитываются требования поддержки целостности данных – то есть выполняются те процедуры, которые могут стать источником избыточности данных. Если пользователь не имеет необходимых прав доступа ко всем компонентам запроса, выполнение этого запроса отменяется. После получения подтверждения того, что пользователь обладает всеми правами доступа, текст запроса подвергается предварительной обработке на основе хорошо известных правил логики:

p Ù p = p pÚp=p pÚtrue=true и т. д.

Реструктуризация запроса

На последней стадии запрос преобразуется таким образом, чтобы обеспечить наиболее эффективное его выполнение.

Опираясь не правила преобразования операций, оптимизатор получает возможность преобразовать некоторое выражение реляционной алгебры к некоторому эквивалентному ему выражению, обработка которого будет заведомо более эффективной. Данные правила будем использовать для реструктуризации дерева реляционной алгебры, построенного в процессе декомпозиции запроса. Для представления формул этих правил воспользуемся тремя отношениями R, S и T, причем в отношении R определен набор атрибутов , а в отношении S – набор атрибутов . Обозначения p, q и t будут использоваться для обозначения предикатов, а обозначения - для представления выборки атрибутов.

1.Операция выборки с конъюнктивным предикатом может быть преобразована в последовательность операций выборки по элементам конъюнкции и наоборот.

.

Этот метод преобразования называют каскадной выборкой. Например:

.

2.Правило коммутативности операции выборки.

.

Например:

.

3.В последовательности операций проекций необходима только последняя из этих операций.

.

Например:

.

4.Правила коммутативности операций выборки и проекции.

Если предикат p включает только атрибуты, входящие в список проекции, то операции выборки и проекции будут обладать свойством коммутативности.

, где .

Например:

.

5.Правило коммутативности операции q - соединения и декартового произведения.

.

Операции соединения по эквивалентности и натурального соединения можно считать особыми случаями операции q - соединения, поэтому приведенное правило справедливо и для этих двух операций. Например:

.

Здесь следует отметить, что эти правила справедливы, если не учитывается порядок столбцов.

6.Правило коммутативности операций выборки и q-соединения или декартового произведения.

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

.

В альтернативном случае, когда предикат операции выборки представляет собой конъюнкцию предикатов вида pÙq, где предикат p включает только атрибуты отношения R, а предикат q включает атрибуты только отношения S, операции выборки и q-соединения будут обладать следующим вариантом коммутативности:

.

Например:

.

7.Правило коммутативности операций проекции и q - соединения или декартового произведения.

Если список атрибутов операции проекции имеет вид , где в первый подсписок входят атрибуты только отношения R, а во второй атрибуты – только отношения S, то в том случае, когда условие соединения содержит только атрибуты из L, операция проекции и q - соединения будут обладать следующим вариантом свойства коммутативности:

.

Если условие соединения содержит дополнительные атрибуты, не входящие в отношение L, например, атрибуты , где первый список содержит только отношение R, а второй – только отношение S, то дополнительно придется выполнить выверяющую операцию проекции:

.

Например:

.

Вариант с использованием второго варианта правила:

.

8.Правило коммутативности операций объединения и пересечения, но не вычитания множеств.

RÈS=SÈR,

RÇS=SÇR.

9.Правило коммутативности операции выборки и операций над множествами (объединение, пересечение и вычитание).

.

10.Правило коммутативности операций проекции и объединения.

.

11.Правило ассоциативности операции q - соединения (и декартового произведения).

Операции декартового произведения и естественного соединения всегда ассоциативны:

.

Если условие соединения q включает атрибуты только из отношений S и T, то операция q - соединения обладает следующим свойством ассоциативности:

.

12.Правило ассоциативности операции объединения и пересечения (но не операции разности множеств).

.

Определить студентов группы «АП-71», сдававших экзамен по «Базам данных» после 12.01.2003

Select Student. Nzach, Student. FIOS From Student, Predmet, Vedom Where Student. Sgroup = “АП-71” And Student. Sgroup = Vedom. Sgroup And Predmet. Predm = “ Базы данных” And Predmet. CodePredm = Vedom. CodePredm And Vedom. DateEkzam > #12.01.03

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

Данное выражение представим в виде дерева запроса и для повышения эффективности обработки данного запроса применим следующие правила преобразования выражений реляционной алгебры.

 

1.  Применяем правило 1, позволяющее преобразовать операцию выборки по конъюнкции условий в последовательность операций выборки по отдельным условиям, входящим в конъюнкцию. Применяем правило 2 и 6, позволяющие переупорядочить последовательность операций выборки и декартового произведения.

 

2.  Применяем правило, согласно которому операция выборки по предикату, включающему соединение по эквивалентности и декартово произведение, может быть преобразовано в операцию соединения по эквивалентности.

.

Применим это правило во всех подходящих случаях.

 

3.  На следующем шаге обычно применяется правило 11, в соответствии с которым мы преобразуем операцию соединения по эквивалентности так, чтобы более ограничивающая операция выборки выполнялась первой. Для этого необходима статистика базы данных.

4.  Правила 4 и 7, позволяющие переместить операции проекции так, чтобы они выполнялись до операций соединения по эквивалентности, а также создать новые полезные операции проекции.

Могут обнаруживаться и дополнительные возможности для оптимизации, например, когда две разных операции выборки оказываются идентичными (два потенциальных ключа).

Таким образом, можно сформулировать правила для оптимизации запросов следующим образом:

1.  Выполнение операций выборки на самых ранних этапах. Выполнение операций выборки сокращает кардинальность отношения и сокращает время последующих операций обработки запроса. Следовательно, целесообразно начинать оптимизацию с использования правила 1 для формирования каскадной последовательности операций выборки, после чего следует применять правила 2, 4, 6 и 9. Цель этих действий состоит в том, чтобы переместить операцию выборки в дереве как можно ниже. Дополнительно полезно сохранить вместе все предикаты, касающиеся одного и того же отношения.

2.  Объединение в одну операцию соединения операции декартового произведения и следующей за ней операции выборки, предикат которой представляет условие соединения. Здесь необходимо воспользоваться формулой:

.

 

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

.

В этом случае можно воспользоваться правилами 11 и 12, задающими ассоциативные свойства операций тета – соединения (а также объединения и пересечения). Цель состоит в переупорядочивании операций таким образом, чтобы первым выполнялось соединение, в результате которого будет получено меньшее по размеру отношение. Это позволит выполнить второе соединение с меньшим по размеру исходным отношением.

4.  Как можно более раннее выполнение операций проекции. Операция проекции уменьшает кардинальность отношения, что приводит к сокращению объемов данных, подлежащих дальнейшей обработке. Следовательно, целесообразно сначала использовать правило 3 для построения исходной последовательности проекций, после чего применять к ним правила 4, 5 и 10, задающие свойства коммутативности операций проекции с бинарными отношениями. Целью данной процедуры является перемещение операций проекции вниз по дереву (насколько это возможно). Дополнительно рекомендуется объединять операции проекции, выполняемые над одним отношением.

5.  Однократное вычисление общих выражений. Если одно и то же выражение встречается в дереве несколько раз и результат его вычислений не слишком велик, целесообразно сохранить этот результат после его первого выполнения с целью повторного использования по мере необходимости.