Гайдамакин Н.А. Автоматизированные информационные системы, базы и банки данных. Вводный курс Учебное пособие

Подождите немного. Документ загружается.

'4.3. Обработка

даиии х

В следующем примере на рис. 4.25 по таблицам, представ-

ленным на рис. 4.24, иллюстрируется запрос по отбору запи-

сей сотрудников, премированных хотя бы один раз, т. е. таких,

у которых существует запись в списке премированных.

Прмлроваины

сотруд1ш.го1

ЗЕ1ЕСТ'

Я?ОМ

Р«6огнит

№ИЕКЕ(<^^х1Лг(8В1ЕСТ*К0

ЯгОЛ^Премиршани е

»'ЯЕйЕПремирсе^ние.ФИ0-Ра6м•1Iики.ФИа))<>^^'а(^в)) ;

ФИО

Грозный ИИ.

Гуманный А.А

Иванов И.И.

Петров П.П.

Почтенная О.П.

Сидоров

С.С.

Тишайшая ТТ.

Подразделение

1-й отдел

Отдел кадров

Производственный отдел

Секретариат

Бухгалтерия

Секретариат

Деланност ь

Начальник

Инженер-ионструкго р

Инженер-техноло г

Секретарь

Экономист

Делопроизводитель

Оклад

100р.

93р.

70р.

60р.

90Р.

80р.

28р.

Рис. 4.25. Пример с

подчиненным

зстросол1

на основе предиката

ЕХ18Т8

Следует заметить, что использование предиката

КОТ

ЕХ15Т5 сформирует список ни разу не премированных сотруд-

ников. В последнем примере можно также увидеть, что альтер-

нативным решением для реализации такого запроса является

использование запроса на внутреннее соединение

{ШМЕК

ЮЩ.

Внутренняя инструкция

^У^^^СГможет

также использо-

ваться в качестве выражения для вычисляемого поля внешней

8Р^-инструкции.

Конструкция запроса в этом случае может

выглядеть следующим образом:

8Е1ЕСТ....

{ЗЕЬЕСТ..

)А8ШляВъхчПотРКОМ...

]УНЕКЕ

. .. ,

Обязательным условием при этом является то, чтобы внут-

ренняя инструкция

ЗЕЕЕСТдля

каждой отбираемой по внеш-

ней

5р/.-инструкции

записи возвращала не более чем одну за-

пись по не более чем одному полю.

Приведем пример подобного запроса, отбирающего все за-

писи по полю «Марка» из таблицы «Товары», с формировани-

171

4. Ввод, обработка

вывод данных в фактографических АИС

ем дополнительного поля «Категория», значения которого воз-

вращаются внутренней инструкцией

ЗЕЬЕСТиз

таблицы «Ти-

пыТоваров» при условии совпадения значения поля «КодТипа»

из таблицы «Товары» для текущей записи внешней

ЗрЬ-инст-

рукции

с аналогичным полем «КодТипа» в записях таблицы «Ти-

пыТоваров»:

8Е1ЕСТ

Товары.Марка,

(^Е^оБСГТипыТоваров.Катего-

рия

ЕЯ

ОМ Типы

И^ЯЕЛЕ'(Товары.КодТипа=ТипыТоваров.

КодТипа);)

/45

Категория

ЕКОМТоъары;

Нетрудно заметить, что целью использования в данном при-

мере внутренней инструкции ЗЕЬЕСТявпяегтся формирование

в наборе данных, отбираемых из таблицы на стороне «Мно-

гие», дополнительного поля по значению какого-либо поля из

связанной таблицы на стороне «Один». Исходя из этого, аль-

тернативным способом решения данной задачи может быть ис-

пользование запроса на внутреннее соединение:

5'^1оЕ'СГТовары.Марка,ТипыТоваров.Категория

ЕЯОМ Товары

INNЕЯ^ОINТипьП'о^тровОNТовары.Код.-

Типа = ТипыТоваров.КодТипа;

В тех случаях, когда отбор данных внешней

ЗрЬ-инструк-

цией осуществляется из таблицы на стороне «Один», внутрен-

няя инструкция ЗЕЬЕСТможет использоваться для дополни-

тельного поля, формируемого на основе групповой операции

по группам соответствующих связанных записей в таблице на

стороне «Многие». Приведем пример отбора записей по полю

«Категория» из таблицы «ТипыТоваров» с дополнительным

полем

«СредняяЦена»,

формируемым на основе статистичес-

кой функции А УС по полю «Цена» для групп связанных запи-

сей в таблице «Товары»;

8ЕЬЕСТ

ТипыТоваров.Категория,

{8ЕЬЕСТ

АУё(То-

вары.Цена)

172

4.3. Обработка данных

А 8 СредняяЦена

РКОМТовары

ОКОиРВУТотры.КодТит

НА

Р77^С(ТипыТоваров.КодТипа

Товары.КодТипа);)

.45

Сред-

няяЦена

Т^КОМТипыТоваров;

Опять-таки отметим, что альтернативным решением по

данному примеру может быть использование следующего зап-

роса на внутреннее соединение:

5'^^^СГТипыТоваров.Категория,

Ау§(Товары.Цена)

А8

СредняяЦена

7^/?(9МТипыТоваров ШЫЕК 7(9/7^Товары

ОТ^ТипыТоваро-

в.КодТипа

= Товары.КодТипа

СЛООТ'ЛУТипыТоваров.Категория;

4.3.2.5. Оптимизация запросов

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

ми по обработке данных, интерпретируются (или компилиру-

ются, т. е. переводятся) машиной данных СУБД в машинные

коды и выполняются. При этом, однако, декларативный харак-

тер языка

Зр//

(«что сделать») приводит к неоднозначности в

определении конкретной схемы и конкретного порядка обра-

ботки данных (наличию нескольких вариантов «как сделать»).

Под оптимизацией запросов понимается такой способ обра-

ботки запросов, когда по начальному представлению запроса

вырабатывается процедурный план его выполнения, наиболее

опт1шалы1ый

при существующих в базе данных управляющих

структурах".

Оптимизация осуществляется в соответствии с

критериями, заложенными в оптилшзатор процессора зстро-

сов СУБД (см. рис. 2.1).

В общей схеме обработки запроса выделяют:

• лексический и синтаксический разбор запроса;

• логическую оптимизацию;

• семантическую оптимизацию;

" Кузнецов С.Д. Введение в СУБД. // СУБД. — № 4. — 1995. — С. 98.

173

4. Ввод, обработка и вывод данных в фактографических АИС

• построение процедурных планов выполнения запросов и

выбор оптимального;

• непосредственное выполнение запроса.

Лексический

синтаксический разбор запроса формиру-

ют внутреннее представление запроса, содержащее вместо

имен таблиц, полей и связей базы данных их истинные внут-

ренние идентификаторы и указатели, находящиеся в систем-

ном каталоге базы данных.

Логическая оптимизация запроса может включать различ-

ные эквивстептпые преобразования, «улучшающие» представ-

ление запроса. Такие преобразования можно разбить на три

группы:

• преобразования предикатов сравнения;

• преобразования порядка реляционных операций (соеди-

нения, объединения, выборки);

• приведение

запросов с подчиненными запросами к зап-

росам на соединение

{101М).

Преобразования предикатов сравнения, улучшающие в

целях оптимизации представление запроса, в свою очередь,

разделяются на:

• приведение

предикатов сравнения к каноническому виду;

• приведение

логического условия сравнения к каноничес-

кому виду.

Каноническим называется такой вид предикатов сравнения,

который содержит сравнение простых

выраэ/сений.

Можно

выделить три типа такихсравнений:

• Имя

поля Операиия сравнения Константное арифмети-

ческое выраэ/сение;

•Имя

поля Операиия сравнения Арифметическое выраэ/се-

ние;

• Арифметическое

выражение Операиия сравнения Кон-

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

В первом типе под «Константным арифметическим вы-

раэюеиием»

понимается такое выражение, которое содержит

константы

так называемые объемлющие переменные, в лю-

бой момент имеющие одинаковое значение в отношении всех

174

4.3. Обработка данных

кортежей таблицы (базы данных). Примером приведения пре-

диката сравнения к первому оптимизируемому каноническому

виду является следующее выражение (сотрудники, у которых

оклад в десять раз превышает величину минимального размера

оплаты труда):

{

Исходное

выражение

Каноническое представление

С6труд»1ию1

Ок;1гит/10-МРОТ>0

Сотруднии1.0клад

> 10*МРОТ

где

МРОТ—объемлющая

переменная,

определяющая

величи-

ну минимального размера оплаты труда.

На этом примере легко понять суть

последующей

оптими-

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

сравнения одинакова для всех просматриваемых записей-кор-

тежей и определяется (вычисляется) один раз для всех. В ис-

ходном выражении помимо собственно операции сравнения не-

обходимо при выборке каждого кортежа производить арифме-

тические вычисления, что существенно увеличивает количество

операций при выполнении соответствующего запроса.

Во втором типе под

«Арифметическим

выраэюеиием»

по-

нимается такое выражение, в котором может присутствовать

имя поля другой таблицы, полностью раскрыты скобки, произ-

ведено приведение и упорядочение членов. Примером приве-

дения предиката сравнения ко второму оптимизируемому ка-

ноническому виду является следующее выражение (сотрудни-

ки, оклад которых с учетом вычетов по болезни больше

величины минимальной оплаты труда):

11сход11ое

выражение

.Согруди11Ю1.0клад-(Софул1тки.Ок.ч;1.'1/КолД11см)*

а..

1^ЭТруД0С110С0б1КК1

ь.

Дт

I-МЮТН)

Каноническое представление

;

Сотрудиики.Оклад>М1-'ОТ/(1-

Нсфудоспособиосгь.

Дпп/КолДией)

где КолДней — переменная, равная количеству рабочих дней в

данном месяце.

175

4. Ввод, обработка

вывод данных в фактографических АИС

Примером приведения предиката сравнения к третьему оп-

тимизируемому каноническому виду является следующее вы-

ражение (сотрудники, чей оклад после вычета подоходного на-

лога с учетом

льгот

на иждивенцев в десять раз превышает ве-

личину минимальной оплаты труда):

Исходное выражение

.Оклад-0,12

(.Оклад-МРОР'.

IГ/ВД)-1 О*

МРОТ>0

Каноническое представление

.Оклад

-Ю,136МРО'Р.ИЖД

>11,36МРОТ

где

.ИЖД

— имя

поля

той же таблицы «Сотрудники», с данны-

ми по количеству иждивенцев для конкретного сотрудника; на-

звания таблицы «Сотрудники» для краткости опущены.

Приведение логических условий сравнения к каноническо-

му виду преследует ту же цель снижения числа операций при

выполнении запроса на основе поиска общих предикатов и раз-

личных упрощений логических выражений. Для примера мож-

но привести следующее оптимизируемое логическое выраже-

ние (научные работы, которые вышли после защиты их автора-

ми диссертаций, защищенными в 1995 г.):

Исходное выражение

(На>ч_Работ1.1.Го;иИыход:1>Согрул1111ки.Го;(_За11Щты)

А\'Р

(Сотруд1и1К11.Год_3:шипы=

1995)

Каноническое

представление

(№1уч_Работы.Год_Выхода>1995)

АЫО

(Сотрудники.Год_Зашиты=1995)

Преобразования порядка реляционных операций также на-

правлены на сокращение возможного количества операций при

обработке запросов. Одними из наиболее частых реляционных

операций в запросах являются операции соединения

^01М)

операции ограничения

(УИНЕКЕ

ге81;гюиоп).

В этом отношении

общим правилом оптимизирующего преобразования запросов

будет замена последовательности операции соединения с пос-

176

4.3. Обработка данных

ледующими ограничениями на предварительные

ограничения

с последующим соединением:

Шхолнын

порядок

(Л

^01N

В)

\УЫЕ1и:

ге5{гк;ио1>-01ьА

.ЛМП

гсхГпсиоп-оп-В

•к^йж

111тжжж^11й>

ж\/ицЬ'V

шж1гЧ'\л\^шгЛЛ\МОЛПшЖК

(А

\У1-ШаЕ

гезйтсйоп-оп-Л)

^ОIN

(В

^/НЕКЕ

гезШсйоп-оп-В)

где А и В — имена таблиц.

Очевидно, что в большинстве случаев количество опера-

ций по реализации наиболее затратной операции соединения

таблиц будет меньше после предварительно проведенных опе-

раций ограничения по отбору записей из исходных таблиц. Осо-

бенно данное правило актуально при

н^шичии

ограничений на

отбор полей при соединении таблиц, связанных отношений

«Один-ко-многим». В этом случае перенос

ограничений

в ус-

ловиях отбора на таблицу, находящуюся на стороне «многие»

до операции

70Ш

может существенно ускорить выполнение

запроса.

Одним из проявлений вариантности языка

8^^

является

эквивалентность

выраэ/сепия

некоторых подчиненных и слож-

ных запросов с соединениями. При выполнении запросов с под-

чиненными запросами для каждого кортежа-записи в исходном

наборе внешнего запроса выполняется подчиненный запрос.

Иначе говоря, всякий раз при вычислении предиката внешнего

запроса вычисляется подчиненный запрос. Поэтому резервом

для оптимизации подобных запросов является поиск возмож-

ных путей сокращения количества операций за счет эквивален-

тных преобразований, приводящих к совмещению операций

формирования набора кортежей-записей внешнего и внутрен-

него (подчиненного) запроса.

Каноническил1

представлением запроса по данным из п

таблиц называется запрос, содержащий

п-1

предикат соедине-

ния и не содержащий предикатов с подчиненными запросами.

Если вернуться к примеру подчиненного запроса с предикатом

177

4. Ввод, обработка и вывод данных в

фактографических

АИС

1п

на рис. 4.24, то его

эквив^шентным

оптимизируемым выра-

жением будет следующее:

1ки>;и1(к-

ирскмап.'имтс

(Со1р\;1]111кн

\м

сииск»

ирс.мнрикиииых

на

1(Ю

Гю-и-с

ироиенгои)

М1КТ*

П<1;\11ог|'.;111!1П!

\М11.К1-.1(Со1р>.Ч1И!1и1'11())

|1цМ"1

1.Г|

[||ч\«,1|ч

ьлшс'МК)

ГКоМ

111\-

М.'1>.|:.1'мк'

'Л

III

|<|.

I"I|^^!.1|•••

[...ММ.- 11р-'.!11 I •- ; I

Оптимизированное представление

ВЕЬЕСТ

Сотруднию!.*

РЯОМ

Сотрудники,

Премироваиие

^VНЕКЕ

(Сотрудиию1.ФИО=Премировапие.ФИО)

А>ГО

(Премирова-

ние.Ц-кмия >= 1);

Логическая оптимизация запросов не учитывает семанти-

ки конкретной базы данных, проявляемой в ограничениях це-

лостности на значения полей таблиц и связей между ними. В

результате ядро СУБД всякий раз при выполнении логически

оптимизированного запроса еще и проверяет ограничения це-

лостности. Часть записей-кортежей, сформированных по резуль-

татам операций запроса, при этом может быть отвергнута имен-

но по ограничениям целостности.

Семантич^еская

оптимиза-

ция запросов основывается на слиянии внутреннего

представления запроса и ограничений целостности конкрет-

ной базы данных до непосредственного выполнения запроса и

призвана за счет совместной проверки ограничений целостно-

сти и условий запроса сократить количество выполняемых опе-

раций.

Для примера предположим, что в таблице «Сотрудники»

по полю «Оклад» наложено ограничение целостности, заклю-

чающееся в том, что оклад не может быть меньшим величины

минимального размера оплаты труда МРОТ, равного 84 руб.

Предположим также, что нужно сформировать список сотруд-

ников, чей оклад меньше 50 руб. Соответствующий запрос име-

ет вид:

178

4.3. Обработка данных

'(Сотрулники с

ок.1а,'10м,

меньшим 50

1»'б.)

5ЕЬЕСТ*

'ИЮМ

Стру/ишки

\\'НЕ№

{Со]рул11ми1.Ок;1;и'1<50 р.);

Без семантической оптимизации данный запрос будет вы-

полняться следующим образом — будет последовательно из-

влекаться каждая запись в таблице «Сотрудники» и проверять-

ся на выполнение условия отбора. Результатом выполнения зап-

роса будет пустое множество записей. С учетом внутренней

семантической оптимизации в ответ на запрос без последова-

тельного перебора всех записей сразу будет выдано пустое мно-

жество записей.

После логической и семантической оптимизации строится

процедурный план выполнения запросов. Процедурным пла-

ном запроса называется детализироваппый порядок выполне-

ния операций доступа к базе даппых физического уровня. Уже

упоминавшаяся многовариантность способов

выполнения

8^^-

инструкций соответственно приводит к набору альтернативных

процедурных планов

выполнения

запросов, среди которых оп-

тимизатор запросов ядра СУБД должен выбрать оптимальный

в соответствии с определенными

критериялт.

Общепринятым критерием оптимальности процедурных

планов является минимизация

стонмости

выполнения

запро-

сов. При этом под стоимостью выполнения запроса понимают-

ся вычислительные ресурсы (ресурсы процессора и ресурсы

дисковой и оперативной памяти), необходимые для выполне-

ния запросов.

Для иллюстрации вариантности процедурных планов рас-

смотрим запрос по выборке записей из таблицы «Сотрудники»

по возрасту не старше 30 лет и с должностным окладом более

100 руб.:

(Сшрулпикп

ПС

сшрпн:

лег

и с

()кл:1;1(>м

не

.менее

100руб.)

*;г.1.1С1*

Д-КОМ

1.\Ч|Г.".1.1!М1

Л\111:.и1:и.\'1р;..-:11П1.Л1::1.1''--.^Ч

•'"."I.'Ч.'^^^•.•)

.\М)

(Со!]!;..:!:!!!

1:.1)и1.1.',""1!|"|- >;

179

4. Ввод, обработка

вывод данных в фактографических АИС

Если по полям «Дата_Рожд» и «Оклад» таблицы «Сотруд-

ники» существуют индексы, то возможны три варианта плана

выполнения запроса:

1) последовательно без учета индексации просматривать

(сканировать) записи таблицы «Сотрудники» и отбирать запи-

си при выполнении требуемых условий;

2) сканировать индекс поля «Дата_Рожд» с условием вы-

борки «>= #01/01/68#», выбирать соответствующие записи из

таблицы «Сотрудники» и среди них отбирать те, которые удов-

летворяют условию по полю «Оклад»;

3) сканировать индекс поля «Оклад» с условием выборки

«>100 руб.», выбирать соответствующие записи из таблицы

«Сотрудники» и среди них отбирать те, которые удовлетворя-

ют условию по полю «Дата_Рожд».

Стоимость каждого варианта в конечном счете определя-

ется главным образом количеством пересылаемых страниц (бло-

ков) из файла данных в буферы оперативной памяти ввиду того,

что, как уже отмечалось, время операций доступа к конкрет-

ным записям в оперативной памяти на несколько порядков мень-

ше времени процессов обмена между внешней и оперативной

памятью, и тем самым основные затраты приходятся именно

на эту операцию.

Если количество записей в таблице «Сотрудники» невели-

ко и все они умещаются в одной странице (в одном блоке) фай-

ла базы данных, то наименее затратным будет первый вариант.

Если записи таблицы «Сотрудники» распределены по множе-

ству страниц, менее затратными являются 2-й и 3-й варианты.

При этом различия между ними будут определяться так назы-

ваемой селективностью значений по полям «Дата_Рожд» и

«Оклад».

Селективность определяется главным

обрсоом

характером

статистического распределения значений по соответствующим

полям. Исходя из мощности (количества записей), вида (равно-

мерное, нормальное) и параметров распределения (среднее зна-

чение, максимальное и минимальное значение) можно полу-

чить приблизительные оценки количества страниц (блоков)

180