Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Базы данных Шехтман.doc
Скачиваний:
2
Добавлен:
01.04.2025
Размер:
3 Мб
Скачать
☆
  1. Логические преобразования запросов.

Прежде всего это относится к преоб­разованию предикатов, входящих в условие выборки. Предикаты, содержа­нию операции сравнения простых значений. Такой предикат имеет вид ариф­метическое выражение ОС арифметическое выражение, где ОС — операция сравнения, а арифметические выражения левой и правой частей в общем случае содер­жат имена полей отношений и константы (в языке SQL среди констант мо­гут встречаться и имена переменных объемлющей программы, значения которых становятся известными только при реальном выполнении запроса). Канонические представления могут быть различными для предикатов раз­ных типов. Если предикат включает только одно имя поля, то его канониче­ское представление может, например, иметь вид имя поля ОС константное ариф­метическое выражение (эта форма предиката — простой предикат селекции -очень полезна при выполнении следующего этапа оптимизации). Если на­чальное представление предиката имеет вид

(n+12)*R.B f 100

здесь n - переменная языка, R.B — имя столбца В отношения R, f - допустимая операция сравнения.

Каноническим представлением такого предиката может быть

(n+12)*R.B f 100 -> R.B f 100/(n+12)

В этом случае мы один раз для заданного значения переменной п вычисляем выражение в скобках и правую часть операции сравнения 100/(n +12), а потом каждую строку можем сравнивать с полученным значением.

Если предикат включает в точности два имени поля разных отношений (или двух разных вхождений одного отношения), то его каноническое представление может иметь вид имя поля ОС арифметическое выражение, где арифметическое выражение в правой части включает только константы и второе имя поля

2*(R1.A)-n*(R2.B) f m -> R1.A f (m+n*(R2.B))/12

общем случае желательно приведение предикат к каноническому представлению вида

арифметическое выражение f константное арифметическое выражение

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

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

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

  1. Преобразования запросов с изменением порядка реляционных операций.

R1 NATURAL JOIN R2 WHERE R1.A … a AND R2.B … b ->

Сначала выполняются выборки по условиям в обоих отношениях а потом соединение.

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

Каноническим представлением запроса на n отношениях называется запрос, содержащий n-1 предикатов соединения и не содержащий предикатов с вложенными подзапросами. Фактически, каноническая форма – это алгебраическое представление запроса.

Если есть подзапросы, то обычно единственный способ их выполнить – выполнять вложенный подзапрос всякий раз, когда вычисляется значение предиката. В частных случаях этого можно избежать и оптимизатор стремится этому.

Примеры:

SELECT R1.A FROM R1 WHERE R1.B IN (SELECT R2.B FROM R2 WHERE R1.C=R2.D)

->

SELECT R1.A FROM R1, R2 WHERE R1.B=R2.B AND R1.C=R2.D

SELECT R1.A FROM R1 WHERE R1.K=(SELECT AVG(R2.B) FROM R2 WHERE R1.C=R2.D)

->

R3 = (SELECT R2.D, AVG(R2.B) AS L FROM R2 GROUP BY R2.D)

SELECT R1.A FROM R1, R3 WHERE R1.C=R3.D AND R1.K=R3.L

Методы семантической оптимизации запросов

  1. Если запрос над представлением, (а представление – само запрос), то выполняться должно 2 запроса: сначала запрос, на котором основано представление, а потом сам запрос над представлением. Но оптимизация сливает их в один запрос.

  2. Учет ограничений целостности. Мы можем искать значение поля, которое не входит в набор возможных значений. Тогда ясно, что запрос пуст и без выполнения!

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

Пример. Пусть имеется две таблицы:

GOODS ((IDENT, INTEGER), (NAME, CHAR(50)), (PRICE, CURRENCY),…)

и

OPERATIONS ( (IDENT,CHAR(15), (DISCOUNT, FLOAT), (QUANT,INTEGER), (DAT,DATE),…).

Таблица GOODS – множество товаров на складе, таблица OPERATIONS – строки счетов-фактур, соответствующих операций продажи товаров. При этом поле OPERATIONS.IDENT – строкового типа, но хранит идентификатор товара, соответствующий GOODS.IDENT.

Тогда оптимизатор СУБД Interbase не справится с запросом (он будет выполнен, но неоптимально):

SELECT GOODS.PRICE, GOODS.NAME, OPERATIONS.QUANT, OPERATIONS.DISCOUNT

FROM OPERATIONS LEFT JOIN GOODS

ON OPERATIONS.IDENT = CAST(GOODS.IDENT AS CHAR(15) )

WHERE OPERATIONS.DAT>=’01.01.2003’ AND OPERATIONS.DAT<=’31.03.2003’

Но тот же оптимизатор прекрасно справится с таким запросом:

SELECT GOODS.PRICE, GOODS.NAME, OPERATIONS.QUANT, OPERATIONS.DISCOUNT

FROM OPERATIONS LEFT JOIN GOODS

ON CAST(OPERATIONS.IDENT AS INTEGER) = GOODS.IDENT

WHERE OPERATIONS.DAT>=’01.01.2003’ AND OPERATIONS.DAT<=’31.03.2003’

Разница во времени (в таблицах GOODS и OPERATIONS около 100 000 записей) может составить 20 раз! Разумеется, эта конкретная проблема обусловлена хранением идентификатора товара, который по своей природе целого типа, в поле строкового типа.

После оптимизации запрос приводится к непроцедурному виду (Что? а не Как?). Далее строятся планы выполнения запросов. Они основаны на статистическом анализе объемов данных. Для каждого из них производятся стоимостные оценки. Оценка планов выполнения запроса основана на анализе текущих объемов данных, хранящихся в отношениях БД, и на статистическом анализе хранимой информации. В боль­шинстве СУБД ведется учет диапазона значений отдельного столбца с указани­ем процентного содержания для каждого диапазона. Поэтому при построении плана запроса СУБД может оценить объем промежуточных отношений и по­строить план таким образом, чтобы на наиболее ранних этапах выполнения за­проса минимизировать количество строк, включаемых в промежуточные отно­шения.

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