Диссертация (Оптимизация обработки вложенных запросов в многопроцессорной базе данных), страница 2

723.4.Численные результаты ................................................................................................................................. 733.4.1.Вложенные запросы для таблиц с параметрами, соответствующими геометрической прогрессии 743.4.1.1.Несовместное выполнение вложенных запросов ......................................................................... 743.4.1.2.Совместное выполнение вложенного запроса .............................................................................. 803.4.2.Вложенные запросы для таблиц с параметрами, соответствующими арифметической прогрессии883.4.2.1.Несовместное выполнение вложенных запросов ......................................................................... 883.4.2.2.Совместное выполнение вложенного запроса ..............................................................................

94Выводы по главе 3 ................................................................................................................................................... 103Литература ...............................................................................................................................................................

105ВведениеТипичная БД – это организованный набор связанной информации, котораяхранится в виде «записей», которые разделены на «поля» (области информации).Например, БД работников предприятия может иметь запись о каждом работнике, и каждаязапись имеет поля, где указаны специфические данные в отношении работника – фамилия,домашний адрес, размер зарплаты и т.д.Между действительной физической БД (т.е. данными хранящимися на носителехранимой информации) и пользователями системой находится СУБД (система управлениябазами данных) как слой или средства программного обеспечения (ПО).

СУБД позволяетпользователю не интересоваться и не заботиться о деталях аппаратного обеспечения, осхемах, обеспечивающих использование БД. Обычно все запросы пользователей вотношении доступа к БД обрабатываются СУБД. Например, данные могут добавлятьсяили удаляться из файлов данных, информация в файлах данных может бытьвосстановлена или обновлена и т.д., а пользователь при этом может и не знать осоответствующем, обеспечивающим эти операции функционировании системы.Одновременно с этим пользователи ожидают от применения СУБД высокойпроизводительности и надежности.Задача оптимизации вложенных запросов в базах данных заключается в созданиитакой надстройки над какой-либо СУБД (например, MySQL Server, T-SQL или Oracle),которая способна последовательно выполнять действия, необходимые для выборанаиболее эффективного плана выполнения запроса, также осуществляя минимизациюнакладных расходов.Входными данными в данной задаче является некоторая формулировка запроса кБД.

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

В качестве критерия оптимизациивложенных запросов обычно используют время выполнения запроса, при этомподразделяют время, затрачиваемое на работу с данными, находящимися в оперативной,буферной и внешней памяти. Дополнительными условиями являются объем памятей,число процессоров и др., которые часто задают в виде стоимостных ограничений.Проблемами создания и оценки качества ООЗ занимались ряд российских изарубежныхисследователей:ГригорьевЮ.А,КузнецовС.Д,AmolDeshpande,ZaccharyIves, VijayshankarRaman, SelingerP.G, AstrahanM.M, ChamberlinD.D и др.В данной работе развита методика формирования плана оптимизации обработкивложенных запросов многопроцессорными базами данных, что наиболее соответствуетбортовым базам данных перспективных авиационных систем, таким как базы данных длясистем управления полетом.Цель диссертационной работыОптимизации по времени выполнения вложенных запросов при обращении кмногопроцессорной базе данных на основе упорядочивания элементарных запросов.Методы исследованияМатематическое моделирование.

Компьютерное моделирование. Современнаяметодология организации баз данных.Научная новизнаРазработана методика оптимизации по времени выполнения конъюнктивныхвложенных запросов при обращении к многопроцессорной базе данных на основеупорядочивания элементарных запросов.Определены соотношения времени выполнения запроса в многопроцессорнойбазеданных для естественного и квазиоптимального порядка их распределения.Доказана эффективность квазиоптимального распределения на основе абсолютного иотносительного уменьшения границ времени выполнения запросов при использованииквазиоптимального распределения вместо естественного распределения.Определено минимальное время выполнения вложенного запроса для упорядоченныхили неупорядоченных данных таблиц при совместной обработке процессорами данныхобъединенногомножестваэлементарныхзапросоввсехтаблиц,образующихвложенные запросы.Определено минимальное число процессоров, при котором достигается минимальноевремя выполнения вложенного запроса, что является важным решением дляоптимизации многопроцессорных баз данных авиационно-космических систем.Достоверность полученных в диссертационной работе результатов подтверждается:Применяемымматематическимиимитационнымаппаратом.Подобиемполученных результатов аналитического и имитационного моделирования.

Соответствиемполученных и известных результатов.Практическая значимостьРазработан модуль формирования плана выполнения вложенных запросов и оценкивремени его выполнения.Реализация результатов работыРезультаты диссертационной работы используются в учебном процессе кафедры«Вычислительныемашиныисистемы»Московскогоавиационногоинститута(государственного технического университета) в форме информационного обеспеченияблока дисциплин, а так же в лекционном курсе «Моделирование».На защиту выносятся следующие положения:Методика оптимизации по времени выполнения конъюнктивных вложенных запросовпри обращении к многопроцессорной базе данных на основе упорядочиванияэлементарных запросов.Соотношения времени выполнения запроса в многопроцессорнойбазе данных дляестественного и квазиоптимального порядка их распределения.Утверждениеэффективностиквазиоптимальногораспределениянаосновеабсолютного и относительного уменьшения границ времени выполнения запросов прииспользованииквазиоптимальногораспределениявместоестественногораспределения.Соотношения дляминимального времени выполнения вложенного запросадляупорядоченных или неупорядоченных данных таблиц при совместной обработкепроцессорами объединенного множества элементарных запросов всех таблиц,образующих вложенные запросы.Апробация работыОсновные положения и результаты диссертационного исследования докладывалисьавтором и обсуждались: на 11-я Международная конференция МАИ «Авиацияикосмонавтика-2012», 13-15 ноября 2012г года МАИ, Москва, 13-я Международнаяконференция МАИ «Авиация и космонавтика-2013»,12–15 ноября 2013 года, Московскаямолодежная конференция «Инновации в авиации и космонавтике», Москва.22–24 апреля2014года.ПубликацииОсновные материалы диссертационной работы опубликованы в 3 печатных работахиз перечня ВАК.Структура и объем диссертацииДиссертация состоит из введения, четырѐх глав, заключения, библиографическогосписка из 154 наименований.

Работа изложена на 114 страницах, содержит 37 таблиц и 32рисунка.1. Вложенные запросы (подзапросы) в MySQL Server, T-SQL или SQLOracle1.1. Теоретические основыЗапрос – это операция, которая позволяет отыскивать данные из одной илинесколько таблиц. При наличии вложенных запросов запрос верхнего уровня называетсяпредложением SELECT, а запрос, вложенный в предложение SELECT называетсяподзапросом. Таким образом, подзапрос (вложенный запрос) – это запрос, результаткоторого передается в качестве аргумента в другой запрос.

Подзапросы позволяютсвязывать в единое целое несколько запросов.Подзапросы используются для:Определения множества строк, который должны быть вставлены в целевую таблицу впредложениях INSERT или CREATE TABLE;Определения одного или более значений, присваиваемых существующим строка впредложении UPDATE;Получения значений для фраз WHERE, HAVING или START WITH в предложенияхSELECT, UPDATE, и DELETE;Определения значений указанного столбца в списке INSERT ...

VALUES;Определения таблицы, которая используются соответствующим запросом.Это производится путем размещения подзапроса во фразе FROM соответствующегозапроса как если бы это было именем таблицы. Вы можете также использовать такимобразом подзапросы вместо таблиц в предложениях INSERT, UDPATE и DELETE.Используемые таким образом подзапросы могут использовать переменныесвязывания (correlation variables), однако только такие, которые определены только всамом подзапросе, ссылки на внешние переменные не допустимы. Внешние ссылки(подзапросы с левой корреляцией - left-correlated subqueries) допустимы только во фразеFROM предложения SELECT .Подзапрос дает ответ на содержательные запросы, имеющие сложную структуру.Например, для определения, кто работает на кафедре Иванова, вы сначала используетеподзапрос для определения кафедры, на которой работает Иванов, а затем отвечаете наосновной запрос путем формулировки предложения SELECT.Подзапрос может содержать другие подзапросы.

Oracle не ограничивает глубинувложенности подзапросов.Если таблица в подзапросе имеет такое же имя, что и таблица внешнего запроса, тодля ссылки на столбцы внешнего запроса их необходимо уточнять именем таблицы илиалиасом таблицы. Чтобы ваши запросы было легче воспринимать, всегда квалифицируйтестолбцы в подзапросе именем или алиасом таблицы.MySQL Server, T-SQL, SQL Oracle или выполняет корреляционные (связанный)подзапрос, когда подзапрос ссылается на столбец таблицы внешнего запроса. Связанныйподзапрос вычисляется для каждой строки, обрабатываемой внешним предложением.Внешним предложением может быть SELECT, UPDATE или DELETE.Связанный подзапрос дает ответы на такие содержательные запросы, ответыкоторых требуют вычисления подзапросов для каждой строки внешнего запроса.Например, связанный подзапрос используется для определения преподавателей, которыезарабатывают больше, чем средняя зарплата по кафедре.