Метод анализа плана выполнения SQL-запроса, используя свойства O-большое асимптотик для оценки стоимости тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат технических наук Борчук, Леонид Евгеньевич

• Борчук, Леонид Евгеньевич
• кандидат технических наук
• 2010

Оглавление диссертации кандидат технических наук Борчук, Леонид Евгеньевич

Перечень условных сокращений.

Перечень условных обозначений.б

Введение.

Глава 1. Анализ факторов, обуславливающих необходимость совершенствования процесса анализа плана выполнения запроса пользователя.

1.1 Задача настройки плана выполнения БСХЪ-запроса.

1.1.1 Самонастраиваемые базы данных.

1.1.2 Метод локальной настройки запросов пользователей.

1.2 Методы анализа плана выполнения запроса.

1.2.1 Методы анализа запросов пользователей на основе моделей плана выполнения.

1.2.3 Имитационные методы анализа запросов пользователей.

1.3 Задачи, решение которых существующими методами затруднено.

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

Выводы по главе.

Глава 2. Разработка способа оценки стоимости выполнения запроса пользователя.

2.1 Ограничение синтаксиса анализируемых запросов пользователей.

2.2 Обоснование общих требований к модели, выбор вида модели.

2.3 Формализация способа оценки стоимости выполнения реляционного запроса пользователя.

2.3.1 Выявление свойств и обоснование положений по оценке стоимости выполнения запроса пользователя.

2.3.2 Определение отношения эквивалентности на множестве запросов пользователей.

2.4 Необходимое и достаточное условия адекватности модели стоимости выполнения запроса пользователя.

Выводы по главе.

Глава 3. Разработка методики построения и анализа модели стоимости выполнения запроса пользователя.

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

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

3.2.1 Разработка методики построения функций асимптотической оценки.

3.2.2 Разработка методики расчета коэффициентов при непредельных значениях параметров.

3.2.3 Расчет коэффициентов и определение области адекватности модели на примере простейших операций на выборку данных. Гипотеза о стабильности поведения системы.

3.3 Разработка математической модели анализа стоимости выполнения запроса.

3.3.1 Выбор методов решения задачи анализа возможности дальнейшей оптимизации запроса.

3.3.2 Определение методов прогнозирования стоимости при изменении объемов данных.

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

Выводы по главе.

Глава 4. Проектирование системы анализа запросов пользователей на основе модели стоимости. Дальнейшие перспективы метода.

4.1 Разработка системы анализа SQL запросов.

4.1.1 Структурная схема системы анализа запросов пользователей на основе модели стоимости.

4.1.2 Разработка алгоритмов сбора информации о параметрах функционирования.

4.1.3 Особенности построения модели запросов пользователей.

4.1.4 Разработка алгоритмов анализа модели стоимости.

4.2 Результаты экспериментальной проверки способа.

4.2.1 Общая характеристика автоматизированной банковской системы

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

4.2.3 Оценка возможности сокращения сроков настройки запросов пользователей.

4.3 Использование полученных результатов в других областях и дальнейшие перспективы способа.

Выводы по главе.

Введение диссертации (часть автореферата) на тему «Метод анализа плана выполнения SQL-запроса, используя свойства O-большое асимптотик для оценки стоимости»

Большинство информационных систем строится на основе реляционных СУБД [98, 99, 122], общение с которыми производится на декларативном языке запросов SQL [1-6]. Объемы хранимой информации ежегодно возрастают (по оценкам экспертов в среднем в два раза) [123,124]. На 2009 год более трети хранилищ систем по объему данных превысили один терабайт. К СУБД, а отсюда и к запросам, предъявляются требования не только реализации функциональных возможностей, но и достаточной производительности (характеризуемой временем ответа). Постоянный рост объема обрабатываемых данных, изменения реляционной модели данных, аппаратного и программного обеспечения, возрастающие требования пользователей к времени ответа системы ставят задачи повышения эффективности обработки данных и своевременных внесений изменений в систему с целью обеспечения требуемого времени ответа.

В 1970-х годах в работах М. Stonebraker, W. Kim, S. Christodoulakis, P. Seiinger, M. Astrahan, D. Chamberlm, S. Finkelstein, M. Blasgen и многих других задача выбора эффективного способа выполнения запроса была рассмотрена в виде задачи комбинаторной оптимизации [64, 97, 105, 135, 150]. Результаты прошли апробацию в рамках проекта по реализации экспериментальной реляционной СУБД System R компании IBM, явившейся прототипом большинства современных коммерческих реляционных СУБД.

Как было отмечено в работах Y. Ioannidis и S. Christodoulakis [175], одной из основных проблем выбора оптимального способа выполнения является обеспечение адекватности оценок стоимости выполнения запроса вследствие так называемого эффекта распространения ошибки. Работы по уточнению оценок стоимости ведутся и по сей день (здесь можно выделить работы V. Markl и Y. Ioannidis [176,177,180,185]), однако универсальность реляционных СУБД и эффект распространения ошибки не позволяет надеяться на всеобъемлющее решение проблемы.

В работах Т. Sellis, U. Chakravarthy, J. Minker, К. Satoh, M. Jarke и др. [70,107,111,121,126,129,131,136,137] была отмечена возможность увеличения эффективности выполнения набора запросов за счет поиска глобального оптимума. Стратегия» поиска может учитывать как историю выполнения запросов (статическая глобальная оптимизация), так и факт их одновременного выполнения (оптимизация набора запросов).

Автоматическая реализация стратегии поиска была положена в основу самонастраиваемых баз данных - развитой системе средств автоматической настройки компонент и структур базы данных, создание которых, в первую очередь, связано с работами М. Stonebraker, S. Chaudhuri, G. Shapiro и V. Markl [187,188,196,197,199]. На сегодняшний день самонастраиваемые базы данных содержат инфраструктуру средств автоматической настройки, средства записи и воспроизведения рабочей нагрузки, средства выработки рекомендаций по построению индексов, материализованных представлений и разбиению на секции по известной рабочей нагрузке, средства автоматического управления сбором статистики и самонастраиваемые гистограммы (оптимизаторы).

Несмотря на то, что удалось достичь значительных результатов с использованием средств автоматической настройки, исчерпывающе решить задачу настройки, как отмечают в своих работах Волкер Маркл и Сураджит Чаудхури, одними автоматическими средствами на сегодняшний день не представляется возможным, так что задача совершенствования неавтоматических средств настройки по-прежнему остается актуальной.

Разработка новых средств настройки осложнена постоянным совершенствованием модели стоимостного оптимизатора путем учета новых параметров, что ведет к усложнению методов анализа модели и появлению новых ограничений на исследуемое поведение системы. В этой связи снова становится актуальным предложенный в 1974 году М. Stonebaker [197] подход использования для настройки внешней по отношению к оптимизатору модели стоимости, позволяющей за счет новых свойств усовершенствовать процесс настройки.

В 2005 году Б. Новиков предложил производить настройку методом локальной настройки запросов, учитывая историю выполнения запросов [50].

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

Цели анализа плана выполнения запроса на каждом из этапов различны.

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

Во-вторых, план выполнения может анализироваться на предмет соответствия его стоимости требованиям при некоторых (возможно, прогнозируемых) объемах данных. В настоящее время такая оценка выполняется на основе отечественных практик тестовых аттестационных испытаний ГОСТ [12-16] или зарубежных рекомендаций проведения нагрузочного тестирования [1-12]. Основной сложностью использования методов тестирования является необходимость получения набора данных для теста. Как правило, в момент анализа запроса требуемых данных в системе нет - они появятся в процессе дальнейшей эксплуатации системы.

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

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

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

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

Таким образом, научная задача состоит в разработке метода анализа стоимости выполнения запроса, позволяющего повысить оперативность настройки с обеспечением требуемого качества показателей выполнения 8С>Ь-запросов пользователей.

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

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

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

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

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

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

- построение и анализ свойств модели исполнения системы запросов с учетом статистической информации;

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

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

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

- разработан способ построения математической модели на основе свойств 0-болыпое асимптотик стоимости выполнения» SQL запросов в зависимости от значимых параметров системы;

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

Практическая ценность диссертационной работы состоит в том, что:

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

- разработана методика построения с использованием свойств О-болыпое асимптотик и анализа модели стоимости выполнения SQL запроса и даны практические рекомендации по расчету коэффициентов модели;

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

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

ОАО КБ «СЕВЕРГАЗБАНК», а результаты модернизации- внедрены в эксплуатацию.

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

Достоверность полученных результатов обеспечивается корректным использованием математического аппарата, а также современных методов и алгоритмов, что подтверждается практическими испытаниями. На примере автоматизированной банковской системы (АБС)

ОАО КБ «СЕВЕРГАЗБАНК» усовершенствован процесс настройки системы баз данных путем модернизации подсистемы тестирования запросов, используя предложенный способ оценки стоимости и гипотезу о стабильности поведения системы. Результаты усовершенствования внедрены в рабочую эксплуатацию в АБС ОАО КБ «СЕВЕРГАЗБАНК».

Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на конференциях:

- 9-й международной конференции "Интеллектуальные системы и компьютерные науки" (Москва, МГУ, 23-27 октября 2006 г.);

- 7-ой международной научно - технической конференции «Кибернетика и высокие технологии XXI века» С&Т^ООб. (Воронеж, 16-18 мая 2006 г.); ^

- 6-ой международной научно - практической конференции "Моделирование. Теория, методы и средства ". (Новочеркасск, ЮРГТУ, 7 апреля 2006 г.);

- 10-ой международной научно - технической конференции "Системный анализ в проектировании и управлении". (Санкт-Петербург, СПбГПУ, 28 июня - 10 июля 2006 г.).

Основные положения диссертации опубликованы в двух научных журналах, рекомендованных ВАК к публикации:

- Борчук J1.E., Кузьмин A.A. Оценка времени выполнения запроса в реляционной СУБД на основе асимптотических моделей затрат ресурсов// Наукоемкие технологии. - 2008. - №4. - С. 61-64.;

- Борчук JI.E. Совершенствование процесса настройки запросов пользователей на основе асимптотических оценок затрат ресурсов// Информационные технологии. - 2008. - №6. - С. 6-11. Публикации. По теме диссертации опубликовано 10 печатных работ, в том числе 6 статей и 4 тезиса докладов. На защиту выносится:

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

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

Структура и объем диссертации. Диссертационная работа состоит из списка сокращений, введения, четырех глав, заключения, библиографического списка из 195 наименований и приложений. Общий объем диссертации - 274 страницы машинописного текста, в том числе: 182 страницы основного текста и 92 страницы приложений, 35 рисунков, 11 таблиц.

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

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

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

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

В четвертой главе изложены принципы построения системы анализа SQL запросов на основе предложенного метода анализа плана выполнения. В зависимости от характера нагрузки СУБД для анализа могут быть использованы разные показатели в соответствии с приведенным в тексте алгоритмом. Для систем класса OLTP в качестве основного способа выбора запроса для настройки может быть использовано свойство затратной неизменности. Для систем класса OLAP в качестве основного способа выбора запроса для настройки могут быть использованы критерии значимых параметров и отношений. Приведена схема построения программного комплекса нагрузочного тестирования SQL запросов на основе предложенного метода анализа плана выполнения и результаты экспериментального исследования модернизированной подсистемы нагрузочного тестирования АБС ОАО КБ «СЕВЕРГАЗБАНК».

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

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

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Борчук, Леонид Евгеньевич

Выводы по главе

В главе изложены основные принципы построения системы анализа SQL запросов на основе моделей стоимости, используя свойства О-болымос асимптотик. В зависимости от характера нагрузки СУБД для анализа могут быть использованы разные показатели в соответствии с приведенным в тексте алгоритмом. Для систем класса OLTP в качестве основного способа выбора запроса для настройки может быть использовано свойство затратной неизменности. Для систем класса OLAP в качестве основного способа выбора запроса для настройки могут быть использованы критерии значимых параметров и отношений.

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

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

ЗАКЛЮЧЕНИЕ

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

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

Для решения названных задач были предложены и обоснованы следующие положения:

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

2. Стоимость выполнения операции плана выполнения запроса функционально зависят от количественных характеристик объемов обрабатываемых данных. Для вычисления функции зависимости используются свойства О-болыпое асимптотик и статистика выполнения запроса.

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

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

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

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

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

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

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

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

4. Разработаны алгоритмы выбора показателя для анализа SQL-запроса, особенностями которых является учет характера нагрузки СУБД: для запросов систем класса OLTP показатель строится на основе параметрических моделей и свойств затратной неизменности, для запросов систем класса OLAP используется показатель значимых отношений.

5. Предложена и внедрена в рабочую эксплуатацию подсистема тестирования запросов АБС ОАО КБ «СЕВЕРГАЗБАНК» на основе предложенного метода оценок стоимости выполнения SQL-запросов и гипотезу о стабильности поведения системы, позволившая за счет совершенствования этапа реализации теста сократить время проведения процедуры тестирования на 42% при сохранении качества оценки соответствия запроса требованиям.

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

Список литературы диссертационного исследования кандидат технических наук Борчук, Леонид Евгеньевич, 2010 год

1. 1.O/IEC 9075-1:2008 Information technology - Database languages -SQL - Part 1: Framework (SQL/Framework) Электронный ресурс. // URL: http://www.iso.org (дата обращения: 01.12.2008)

2. ISO/IEC 9075-2:2008 Information technology Database languages -SQL - Part 2: Foundation (SQL/Foundation) Электронный ресурс. // URL: http://www.iso.org (дата обращения: 01.12.2008)

3. ISO/IEC 9075-4:2008 Information technology Database languages -SQL - Part 4: Persistent Stored Modules (SQL/PSM) Электронный ресурс. // URL: http://www.iso.org (дата обращения: 01.12.2008)

4. ISO/IEC 9075-10:2008 Information technology Database languages -SQL - Part 10: Object Language Bindings (SQL/OLB) Электронный ресурс. // URL: http://www.iso.org (дата обращения: 01.12.2008)

5. ISO/IEC 9075-11:2008 Information technology Database languages -SQL - Part 11: Information and Definition Schemas (SQL/Schemata) Электронный ресурс. // URL: http://www.iso.org (дата обращения: 01.12.2008)

6. ISO/IEC 9075-14:2008 Information technology Database languages -SQL - Part 14: XML-Related Specifications (SQL/XML) Электронный ресурс. // URL: http://www.iso.org (дата обращения: 01.12.2008)

7. ТРС Benchmark С Электронный ресурс. // URL: http://www.tpc.org (дата обращения: 01.12.2008)

8. ТРС Benchmark H Электронный ресурс. // URL: http://www.tpc.org (дата обращения: 01.12.2008)

9. BS 7925-1:1998 Software testing. Vocabulary Электронный ресурс. // URL: http://www.testingstandards.co.uk/ (дата обращения: 01.12.2008)

10. BS 7925-2:1998 Software testing. Software component testing Электронный ресурс. // URL: http://www.testingstandards.co.uk/ (дата обращения: 01.12.2008)

11. IEEE 829-1998 standard for software test documentation Электронный ресурс. // URL: http://www.ieee.org / (дата обращения: 01.12.2008)

12. ГОСТ P ИСО/МЭК 9594-8-98 Информационная технология. Взаимосвязь открытых систем. Справочник. Часть 8. Основы аутентификации. М.: Изд-во стандартов, 1998.

13. ГОСТ Р ИСО'МЭК 9646-1-93 Информационная технология. Взаимосвязь открытых систем. Методология и основы аттестационного тестирования. Часть 1. Общие положения. М.: Изд-во стандартов, 1998.

14. ГОСТ Р ИСО'МЭК 9646-2-93 Информационная технология. Взаимосвязь открытых систем. Методология и основы аттестационного тестирования. Часть 2. Спецификация комплекта абстрактных тестов. -М.: Изд-во стандартов, 1998.

15. ГОСТ Р ИСО'МЭК 9646-4-93 Информационная технология. Взаимосвязь открытых систем. Методология и основы аттестационного тестирования. Часть 4. Реализация тестов. — М.: Изд-во стандартов, 1998.

16. Современные проблемы вычислительной математики и математического моделирования: в 2 т. / Ин-т вычисл. математики. -М.: Наука, 2005. Т. 1. : Вычислительная математика / отв. ред. Н.С. Бахвалов, В.В. Воеводин. - 343 с.

17. Аткинсон, М. Манифест систем объектно-ориентированных баз данных / М. Аткинсон и др. // Системы управления базами данных. -1995. №4.

18. Борчук, JI.E. Анализ адекватности одной математической модели реляционного запроса / JI.E. Борчук // Моделирование. Теория, методы и средства: Материалы VI международной научно -практической конференции. Новочеркасск: ЮРГТУ, 2006. - С. 5054.

19. Борчук, JI.E. Анализ методов решения задач оптимизации выполнения запросов в реляционных СУБД / J1.E. Борчук // Сборник трудов участников V межвузовской конференции молодых ученых. -Череповец: ЧГУ, 2004. С. 51-55.

20. Борчук, J1.E. Математическая формализация глобального плана выполнения запросов реляционной СУБД / JI.E. Борчук // Вестник ЧГУ. Череповец, 2004. - С. 84-89.

21. Борчук, JI.E. Оценка времени выполнения запроса в реляционной СУБД на основе асимптотических моделей затрат ресурсов / JI.E. Борчук, A.A. Кузьмин // Наукоемкие технологии. 2008. - №4. - С. 61-64.

22. Борчук, JI.E. Совершенствование процесса настройки запросов пользователей на основе асимптотических оценок затрат ресурсов / JI.E. Борчук // Информационные технологии. 2008. - №6. - С. 6-11.

23. Воеводин, В.В. Параллельные вычисления / В.В. Воеводин, Вл.В. Воеводин. СПб.: БХВ-Петербург, 2002. - 520 с.

24. Вьейра, P. SQL Server 2000. Программирование / P. Вьейра: в 2 т. -M: Бином, 2004. 1544 с.

25. Гарсия, М. Ф. Microsoft SQL Server 2000. Справочник администратора / M. Ф. Гарсия, Дж. Рединг, Э. Уолен, С. А. ДеЛюк. -М: Эком, 2001.-976 с.

26. Гарсиа-Молина, Г. Системы баз данных. Полный курс / Г. Гарсиа-Молина, Д. Ульман, Д. Уидом: пер. с англ. М.: Издательский дом "Вильяме", 2004.

27. Гэри, М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон. М.: Мир, 1982.

28. Дейт, К. Дж. Введение в системы баз данных, 8-е издание / К. Дж. Дейт: пер. с англ. М.: Издательский дом "Вильяме", 2005. — 1327 с.

29. Диго, С. М. Базы данных: проектирование и использование. Учебник / С. М. Диго. М.: Финансы и статистика, 2005.

30. Кайт, Т. Оракл для профессионалов / Т. Кайт: пер. с англ.: в 2 т. -СПб.: ООО "ДиасофтЮП", 2003. 1230 с.

31. Конноли, Т. Базы данных: проектирование, реализация и сопровождение. Теория и практика, 2-е изд / Т. Конноли и др. М.: Издательский дом "Вильяме", 2000. - 1221 с.

32. Кормен, Т. Алгоритмы: построение и анализ / Т. Кормен. М.: МЦНМО, 2004.

33. Кузнецов, С.Д. Базы данных: языки и модели. Учебник / С.Д. Кузнецов. М.: ООО "Бином-Пресс", 2008. - 720 с.

34. Кузнецов, С.Д. Введение в СУБД / С.Д. Кузнецов // Системы управления базами данных. 1995. - №1. - С. 119-127.

35. Кузнецов, С.Д. Введение в СУБД / С.Д. Кузнецов // Системы управления базами данных. 1995. - №1. - С. 116-124.

36. Кузнецов, С.Д. Введение в СУБД / С.Д. Кузнецов // Системы управления базами данных. 1996. - №4. - С. 98-119.

37. Линзенбардт, M. А. Администрирование SQL Server 2000. Полное руководство / M. А. Линзенбардт, М. Ш. Стиглер. М: Издательская группа BHV, 2000. - 400 с.

38. Марков, А.С. Базы данных. Введение в теорию и методологию / А.С. Марков, К.Ю. Лисовский. М.: Финансы и статистика, 2004.

39. Мамаев, Е. Microsoft SQL Server 7 / Е. Мамаев, А. Вишневский. -СПб: Питер, 2000. 896 с.

40. Миллсап, К. Oracle. Оптимизация производительности / К. Миллсап, Д. Хольт: пер. с англ. СПб.: Символ-Плюс, 2006. -464 с.

41. Моисеенко, С.И. Трансляция операторов реляционной алгебры в SQL-операторы / С.И. Моисеенко, В.А. Левченко // Вестник ДГУ. -2005. -№1(23).

42. Новиков, Б.А. Настройка приложений баз данных / Б.А. Новиков, Г.Р. Домбровская. СПб: БХВ-Петербург, 2006. - 240 с.

43. Смирнов, С.Н. Работаем с Oracle: Учебное пособие / С.Н. Смирнов, И.С. Задворьев М.: Гелиос АРВ, 2002. - 496 с.

44. Спирли, Э. Корпоративные хранилища данных. Планирование, разработка, реализация. / Э. Спирли: пер. с англ.: Т. 1. М.: Издательский дом "Вильяме", 2001.

45. Стулов, А. Особенности построения информационных хранилищ / А. Стулов // Открытые системы. 2003. - №4.

46. Тоу, Д. Настройка SQL. Для профессионалов / Д. Тоу. СПб.: Питер, 2004. - 333 с.

47. Хоббс, Л. Oracle 9iR2: Разработка и эксплуатация хранилищ баз данных / Л. Хоббс, С. Хилсон, Ш. Лоуенд: пер. с англ. М.: КУДИЦ-ОБРАЗ, 2004. - 592 с.

48. Чаудхари, С. Методы оптимизации запросов в реляционных системах / С. Чаудхари // Системы управления базами данных. -1998. -№3.

49. Чемберлин, Д. Анатомия объектно-реляционных баз данных / Д.

50. Чемберлин // Системы управления базами данных. 1998. - №1. 58.Чемберлин, Д. Анатомия объектно-реляционных баз данных / Д.

51. Чемберлин // Системы управления базами данных. 1998. - №2. 59.Чен, П.П. Модель 'сущность-связь' - шаг к единому представлению данных / П.П. Чен // Системы управления базами данных. - 1995. -№3.

52. Шнайдер, Роберт Д. Microsoft SQL Server. Проектирование высокопроизводительных баз данных / Роберт Д. Шнайдер. М: Лори, 1998. - 366 с.

53. Шнитман, В.З. Серверы баз данных: проблемы оценки конфигурации системы / В.З. Шнитман // Системы управления базами данных. 1996. — №5.

54. Шнитман, В.З. Серверы баз данных: проблемы оценки конфигурации системы / В.З. Шнитман // Системы управления базами данных. 1996. - №6.

55. Abitboul, S. DBMSs for Supporting New Applications / S. Abitboul, M. Scholl, G. Gardarin, Simon E. Towards // Proc. 12th Int. Conf. Very Large Data Bases, Kyoto, Japan, Aug. 25-28, 1986. Los Altos, Calif., 1986. pp. 423-435.

56. Astrahan, M.M. Implementation of a structured English query language / M.M. Astrahan, D.S. Chamberlin // Commun. ACM 1975, 10 (Oct.), pp. 580-588.

57. Astrahan, M.M. Counting Unique Values of an Attribute without Sorting / M.M. Astrahan, M. Schkolnick, K.Y. Whang // Inf. Syst.1987. 12, N 1. pp. 11-16.

58. Bell, D.A. Clustering Related Tuples in Databases / D.A. Bell, F.J. McErlean, P.M. Stewart, W.A. Arbuckle // Comput. J. 1988.31, N 3. pp. 253-257.

59. Bergamaschi, S. Choice of the Optimal Number of Blocks for Data Access by an Index / S. Bergamaschi, M.R. Scales // Inf. Syst.1986. 11, N 3. pp. 199-209.

60. Bloom, B.H. Space/Time Trade-offs in Hash Coding with Allowable Errors / B.H. Bloom // Commun. ACM, 1970, 13, N 7, pp. 422-426.

61. Chacravarthy, U.S. Multiple Query Processing in Deductive Databases Using Query Graphs / U.S. Chacravarthy, J. Minker // Proc. 12th Int. Conf. Very Large Data Bases, Kyoto, Japan, Aug. 1986. Los Altos, Calif., 1986. pp. 384-394.

62. Chacravarthy, U.S. Semantic Query Optimization in Expert Systems and Database Systems / U.S. Chakravarthy, D.H. Fishman, J. Minker // Expert Database Syst.: Proc. 1st Int. Workshop, Menlo Park, Calif., Feb. 1986. New York, 1986. pp. 326-341.

63. Chacravarthy, U.S. Semantic Query Optimization: Additional Constraints / U.S. Chacravarthy, J. Grant, J. Minker // Proc. 1st Int. Conf. Expert Database Syst., Charleston, S.C., Apr. 1986. New York, 1986. pp. 259270.

64. Cheiney, J.-P. A Functional Clustering Method for Optimal Access to Complex Domains in a Relational DBMS / J.-P. Cheiney, G. Kierman // Proc. 4th Int. Conf. Data Eng., Los Angeles, Calif., Feb. 1988. Washington, D.C., 1988. pp. 394-401.

65. Christodoulakis, S. Estimating Record Selectivities / S. Christodoulakis // Inf. Syst. 1983. 8, N 2. pp. 105-115.

66. Christodoulakis, S. Estimating Block Selectivities / S. Christodoulakis // Inf. Syst. 1984. 9, N 1. pp. 69-79.

67. Christodoulakis, S. Implication of Certain Assumtions in Database Performance Evaluation / S. Christodoulakis // ACM Trans. Database Syst. 1984. 9, N 2. pp. 163-186.

68. Codd, E.F. Extending the Relational Database Model to Capture More Meaning / E.F. Codd // IBM Research Report RJ2599 (August 6th, 1979). Republished in ACM Transactions on Database Systems 4(4), December 1979.

69. Codd, E.F. A Data Sublanguage Founded on the Relational Calculus / E.F. Codd // IBM Research Report RJ893 (July 26th, 1971). -Republished in Proc. 1971 ACM SIGFIDET Workshop on Data Description, Access and Control, San Diego, November 1971.

70. Codd, E.F. Recent Investigations into Relational Data Base Systems / E.F. Codd // IBM Research Report RJ1385 (April 13rd, 1974). -Republished in Proc. 1974 Congress (Stockholm, 1974). New York, N.Y.: North-Holland, 1974.

71. Codd, E.F. Relational Database: A Practical Foundation for Productivity / E.F. Codd // IBM Research Report RJ3339 (December 21st, 1981). -Republished in CACM 25(2), February 1982.

72. Codd, E.F. A Relational Model of Data for Large Shared Data Banks / E.F. Codd // CACM 13(6), June 1970. Republished in Milestones of Research Selected Papers 1958-1982 (CACM 25th Anniversary Issue), CACM 26(1), January 1983.

73. Codd, E.F. Is Your DBMS Really Relational?; Does Your DBMS Run By The Rules? / E.F. Codd // Computerworld (October 14th, 1985; October 21st, 1985).

74. Codd, E.F. The Relational Model For Database Management Version 2 / E.F. Codd. Reading, Mass.: Addison-Wesley, 1990.

75. Date, C.J. Foundation for Object/Relational Databases: The Third Manifesto (2d edition) / C.J. Date, H. Darwen Reading, Mass.: Addis on-Wesley, 2000.

76. Date, C.J. A Critique of the SQL Database Language / C.J. Date // ACM SIGMOD Record 14, No. 3 (November 1984).

77. Date, C.J. A Guide to the SQL Standard. Fourth edition / C.J. Date, H. Darwen. Addison-Wesley Longman, 1997.

78. Demolombe, R. Estimation of the Number of Tuples Satisfying a Query Expressed in Preducate Calculus Language / R. Demolombe // Proc. 6th Int. Conf. Very Large Data Bases, Montreal, Oct. 1980. New York, 1980. pp. 55-63.

79. Desai, B.C. Composite Index in DDBMS / B.C. Desai, P. Goyal, F. Sardi //J. of Syst. and Software. 1988. 8, N 2. pp. 105-120.

80. DeWitt, D.J. Implementation Techniques for Main Memory Database Systems / D.J. DeWitt, R.H. Katz, F. Olken, L.D. Shapiro, M.R. Stonebraker, D. Wood // Proc. ACM SIGMOD Int. Conf. Manag. Data, Boston, Mass., June 18-21, 1984. New York, 1984, pp. 1-8.

81. DeWitt, D. Multiprocessor Hash-Based Join Algorithms / D. DeWitt, R. Gerber // Proc. 11th Int. Conf. Very Large Data Bases, Stockholm, Sweden, Aug. 1985. Palo Alto, Calif., 1985. pp. 151-164.

82. Fang, M.T. The Idea of De-Clustering and Its Applications / M.T. Fang, R.C.T. Lee, C.C. Chang // Proc. 12th Int. Conf. Very Large Data Bases, Kyoto, Japan, Aug. 25-28, 1986. Los Altos, Calif., 1986. pp. 181-188.

83. Finkelstein, S. Physical Database Design for Relational Databases / S. Finkelstein, M. Schkolnick, P. Tiberio // ACM Trans. Database Syst. 1988. 13, N l.pp. 91-128.

84. Freeze, Wayne S. The SQL Programmer's Reference / Wayne S. Freeze.- Ventana Communications Group Inc., 1998. 298 S.

85. Gotlieb, L. R. Computing joins of relations / L.R. Gotlieb // In Proceedings of the ACM-SIGMOD International Conference on Management of Data (San Jose, Calif., May 14-16). ACM, New York, pp. 55-63.

86. Gray, J. Scientific Data Management in the Coming Decade / Jim Gray, David T. Liu, Maria Nieto-Santisteban h ap. // SIGMOD Record. 2005.- Vol. 34, №4.

87. Gray, J. The Lowell Report / Jim Gray, Hans Schek, Michael Stonebraker, Jeff Ullman // Proceedings of the 2003 ACM SIGMOD International Conference on Management Of Data.

88. Grazzini, E. A Physical Structure for Efficient Processing of Relational Queries / E. Grazzini, R. Pinzani, F. Pippolini // Found. Data Organ. Proc. Int. Conf., Kyoto, May 22-24, 1985. New York; London, 1987. pp. 501-514.

89. Hagmann, R.B. An Observation on Database Buffering Performance Metrics / R.B. Hagmann // Proc. 12th Int.Conf. Very Large Data Bases, Kyoto, Japan, Aug. 1986. Los Altos, Calif., 1986. pp. 289-293.

90. Hsu, M. Concurrent Operations in Extendible Hashing / M. Hsu, W.-P. Yang // Proc. 12th Int. Conf. Very Large Data Bases, Kyoto, Japan, Aug. 25-28, 1986. Los Altos, Calif., 1986. pp. 241-247.

91. Inmon, W. Building the Data Warehouse / W. Inmon. John Willey & Sons, New York, 1992.

92. Ioannidis, Y. The History of Histograms (abridged) / Y. Ioannidis // Proceedings of 29th International Conference on Very Large Data Bases, September 9-12, 2003, Berlin, Germany.

93. Jarke, M. Query Optimization in Database Systems / M. Jarke, J. Koch//Computing Surveys, Vol. 16, No. 2, June 1984.

94. Jarke, M. Range Nesting: A Fast Method to Evaluate Quantified Queries / M. Jarke, J. Koch // Proc. ACM SIGMOD Int. Conf. Manag. Data, San Jose, Calif., May 23-26, 1983. New York, 1983. pp. 198-206.

95. Jarke, M. Common Subexpression Isolation in Multiple Query Optimization / M. Jarke // Query Processing in Database Systems. New York: Springer. 1985. pp. 191-205.

96. Kiessling, W. Access Path Selection in Databases with Intelligent Disc Subsystems / W. Kiessling // Comput. J. 1988. 31, N 1. pp. 41-50.

97. King, J.J. QUIST: A System for Semantic Query Optimization in Relational Databases / J.J. King // Proc. 7th Int. Conf. Very Large Data Bases, Cannes, France, Sept. 3-11, 1981. New York, 1981. pp. 510-517.

98. Kim, W. A New Way to Compute the Product and Join of Relations / W. Kim // Proc. ACM SIGMOD Int. Conf. Manag. Data, New Work, May 1980. New York, 1980, pp. 178-187.

99. Kim, W. Global Optimization of Relational Queries: A First Step / W. Kim // Query Processing in Database Systems. New York: Springer. 1985. pp. 206-216.

100. Kim, W. On Optimizing an SQL-Like Nested Query / W. Kim // ACM Trans. Database Syst. 7, No. 3 (1982).

101. Kim W. Architecture of the ORION Next-Generation Database System / W. Kim, J.F. Garza, N. Ballou, D. Woelk // TKDE 2, No.l (1990).

102. Lee, S. Semantic Query Optimization in Recursive Databases / S. Lee, J. Han // 4th Int. Conf. Data Eng., West Berlin, Sept. 13-15, 1988. New York, 1988. pp. 444-451.

103. Lewis, J. Cost-Based Oracle Fundamentals / J. Lewis Apress, 2006. - 506 S.

104. Lorie, R.A. Supporting Complex Objects in a Relational System for Engineering Databases / R.A. Lorie, W. Kim, D. McNabb, W. Plouffe, A. Meier // Query Processing in Database Systems. New York e.a.: Springer (1985).

105. Luk, W.S. On Estimating Block Accesses in Database Organization / W.S. Luk// Commun. ACM. 1983. 26, N 11. pp. 945-947.

106. Makinouchi, A. The Optimization Strategy for Query Evaluation in RDB/V1 / A. Makinouchi, M. Tezuka, H. Kitakami, S. Adachi // Proc. 7th Int. Conf. Very Large Data Bases, Cannes, France, Sept. 3-11, 1981. New York, 1981. pp. 518-529.

107. Merrett, T.H. Why Sort/Merge Gives the Best Implementation of the Natural Join / T.H. Merrett // ACM SIGMOD Record. 1983, 13, N 2, pp. 40-51.

108. Miyao, J. Optimization of Multiple Queries in Relational Database Systems / J. Miyao, K. Tominaga, T. Kikuno, N. Yoshida // Syst. and Comput. in Japan. 1988. 19, N 4. pp. 56-65.

109. Olofson, Carl W. Worldwide RDBMS Software 2006-2010 Forecast / Carl W. Olofson // Отчеты IDC (International Data Corporation),- W201777.

110. Olofson, Carl W. Worldwide RDBMS 2005 Vendor Shares: Preliminary Results for the Top 5 Vendors Show Continued Growth / Carl W. Olofson // Отчеты IDC (International Data Corporation), W201692

111. Olofson, Carl W. Worldwide Relational Database Management Systems 2005-2009 Forecast: An Initial View / Carl W. Olofson // Отчеты ЮС (International Data Corporation), W33078.

112. Ong, J. Implementation of Data Abstraction in the Relational Database System Ingres / J. Ong, D. Fogg, M. Stonebraker // ACM SIGMOD Record 14, No. 1 (March 1984).

113. Park, J. Using Common Subexpressions to Optimize Multiple Queries / J. Park, A. Segev // 4th Int. Conf. Data Eng., West Berlin, Sept. 13-15, 1988. New York, 1988. pp. 311-319.

114. Piatetski-Shapiro, G. Accurate Estimation of the Number of Tuples Satisfying a Condition / G. Piatetski-Shapiro, C. Connel // ACM SIGMOD Record. 1984. 19, N 2. pp. 256-276.

115. Pramanik, S. Optimizing the Cost of Relational Queries Using Partial Relation Schemes / S. Pramanik, F. Fotouhi // Inf. Syst. 1988. 13, N 1. pp. 71-79.

116. Rosental, A. Anatomy of a Modular Multiple Query Optimizer / A. Rosental, U. Chakravarthy // Proc. 14th Int. Conf. Very Large Data Bases, Los Angeles, Calif., Aug.-Sept. 1988. Los Altos, Calif., 1988. pp. 230-239.

117. Rowe, N.C. Absolute Bounds on Set Intersection and Union Sizes from Distribution Information / N.C. Rowe // IEEE Trans. Software Eng. 1988. 14, N 7. pp. 1033-1048.

118. Satoh, K. Local and Global Query Optimization Mechanisms for Relational Databases / K. Satoh, M. Tsuchida, F. Nakamura, K. Oomachi // Proc. 11th Int. Conf. Very Large Databases, Stockholm, Sweden, Aug. 1985. Los Altos, Calif., 1985. pp. 405-417.

119. Shee, R. Oracle Wait Interface: A Practical Guide to Performance Diagnostics & Tuning / R. Shee, K. Deshpande, K. Gopalakrishnan. -McGraw-Hill/Osborne, 2004. 350 S.

120. Shenoy, S.T. A System for Senantic Query Optimization / S.T. Shenoy, Z.M. Ozsoyoglu // Proc. ACM SIGMOD Int. Conf. Manag. Data, San Francisco, Calif., May 1987. New York, 1987. pp. 181-195.

121. Seiinger, P.G. Access Path Selection in a Relational Database Management System / P.G. Seiinger, M.M. Astrahan, D.D. Chamberlin, R.A. Lorie, T. G. Price. // SIGMOD. 1979. pp. 23-34.

122. Sellis, T. Global Query Optimization / T. Sellis // Proc. ACM SIGMOD Int. Conf. Manag. Data, Washington, D.C., May 28-30, 1986. New York, 1986. pp. 191-205.

123. Sellis, T. Multiple-Query Optimization / T. Sellis // ACM Trans. Database Syst. 1988. 13, N 1. pp. 23-52.

124. Shasha, D. Database tuning: principles, experiments and troubleshooting techniques / D. Shasha, P. Bonnet. Morgan-Kaufmann, San Francisco, CA, 2002.

125. Stockmeyer, L.H. On the Number of Comparisons to Find the Intersection of Two Relations / L.H. Stockmeyer, C.K. Wong // SIAM J. of Comput. 1979.- 8, N 3. pp. 388-404.

126. Stonebraker, M. A Distributed Data Base Version of INGRES / M. Stonebraker, E. Neuhold // Proc. 2nd Berkley Workshop Distrib. Data

127. Manag, and Comput. Networks, Berkley, Calif., May 1977. Berkley, Calif., 1977. pp. 19-36.

128. Stonebraker, M. Introduction to Chapter 1 ("The Roots") Readings in Database Systems (2nd edition) / M. Stonebraker // San Mateo, Calif.: Morgan Kaufmann, 1994.

129. Thom, J.A. A Supeqoin Algorithm for Deductive Databases / J.A. Thom, K. Ramamohanarao, L. Naish // Proc. 12th Int. Conf. Very Large Data Bases, Kyoto, Japan, Aug. 25-28, 1986. Los Altos, Calif., 1986. pp. 189-196.

130. Tindall, P. Developing enterprise applications an impurist's view: Using VB, MTS, IIS, SQL Server, and XML / P. Tindall. - Que, 1999.406 S.

131. Ullmann, J.R. Fast Implementation of Relational Operations Via Inverse Projections / J.R. Ullmann // Comput. J. 1988. 31, N 2. pp. 147154.

132. Valduriez, P. Join Indexes / P. Valduriez // ACM Trans. Database Syst. 1987. 12, N 2. pp. 218-246.

133. Vander Zanden, B.T. Estimating Block Accesses When Attributes Are Correlated / B.T. Vander Zanden, H.M. Taylor, D. Bitton // Proc. 12th Int.Conf. Very Large Data Bases, Kyoto, Japan, Aug. 1986. Los Altos, Calif., 1986. pp. 119-127.

134. Whalen, E. Oracle Performance Tuning and Optimization / Whalen E. Sams Publishing, 2003. - 670 S.

135. Whang, K. Estimating Block Accesses in Database Organizations A Closed Noniterative Formula / K. Whang, G. Wiederhold, D. Sagalowicz // Commun. ACM. 1983. 26, N 11. pp. 940-944.

136. Whang, K.-Y. Index Selection in Relational Databases / K.-Y. Whang // Found. Data Organ. Proc. Int. Conf., Kyoto, Japan, May 22-24, 1985. New York; London, 1987. pp. 487-500.

137. Wong, E. Decomposition A strategy for query processing / E. Wong, K. Youssefi // ACM Trans. Database Syst. 1976, 3 (Sept.), pp. 223-241.

138. Yao, S.B. An Attribute Based Model for Database Access Cost Analyses / S.B. Yao // ACM Trans. Database Syst. 1977. 2, N 1. pp. 4567.

139. Yao, S.B. Approximating Block Acess in Database Organizations / S.B. Yao // Commun. ACM. 1977. 20, N 4. pp. 260-261.

140. Yu, C.T. Adaptive Algorithms for Balanced Multidimensional Clustering / C.T. Yu, T.M. Jiang // Proc. 4th Int. Conf. Data Eng., Los Angeles, Calif., Feb. 1988. Washington, D.C., 1988. pp. 386-391.

141. Zahorjan, J. Estimating Block Transfers When Record Access Probabilities Are Non-Uniform / J. Zahorjan, B.J. Bell, K.C. Sevcik // Inf. Process. Lett. 1983. 16, N 5. pp. 249-252.

142. Cary, M. Why You Should Focus on LIOs Instead of PIOs Электронный ресурс. // URL: http://www.hotsos.com/e-library/ (дата обращения: 01.01.2009)

143. Shallahamer, С. Forecasting Oracle Perfomance / Shallahamer C. -Apress, 2007. 296 S.

144. Mistry, H. Materialized view selection and maintenance using multi-query optimization / Hoshi Mistry , Prasan Roy , S. Sudarshan , Krithi Ramamritham // ACM SIGMOD Record, v.30 n.2, p.307-318, June 2001

145. Kossmann, D. Cache investment: integrating query optimization and distributed data placement / Donald Kossmann, Michael J. Franklin, Gerhard Drasch, Wig Ag // ACM Transactions on Database Systems (TODS), v.25 n.4, p.517-558, Dec. 2000

146. Chen, M. Optimization of Parallel Execution for Multi-Join Queries / Ming-Syan Chen, Philip S. Yu, Kun-Lung Wu // IEEE Transactions on Knowledge and Data Engineering, v.8 n.3, p.416-428, June 1996

147. Dalvi, N. Pipelining in multi-query optimization / Nilesh N. Dalvi, Sumit K. Sanghai, Prasan Roy, S. Sudarshan // Journal of Computer and System Sciences, v.66 n.4, p.728-762, 1 June 2003

148. Theodoratos, D. Constructing search spaces for materialized view selection / Dimitri Theodoratos, Wugang Xu // Proceedings of the 7th ACM international workshop on Data warehousing and OLAP, November 12-13, 2004, Washington, DC, USA

149. Bodorik, P. Correcting execution of distributed queries / P. Bodorik, J. Pyra, J. S. Riordon // Proceedings of the second international symposium on Databases in parallel and distributed systems, p. 192-201, July 02-04, 1990, Dublin, Ireland

150. Bodorik, P. Deciding to Correct Distributed Query Processing / P. Bodorik, J. S. Riordan, J. S. Pyra // IEEE Transactions on Knowledge and Data Engineering, v.4 n.3, p.253-265, June 1992

151. Gupta, H. Selection of Views to Materialize in a Data Warehouse / Himanshu Gupta, Inderpal Singh Mumick // IEEE Transactions on Knowledge and Data Engineering, v. 17 n.l, p.24-43, January 2005

152. Rao, J. Reusing invariants: a new strategy for correlated queries / Jun Rao, Kenneth A. Ross // ACM SIGMOD Record, v.27 n.2, p.37-48, June 1998

153. Subramanian, S. Cost-based optimization of decision support queries using transient-views / Subbu N. Subramanian, Shivakumar Venkataraman // ACM SIGMOD Record, v.27 n.2, p.319-330, June 1998

154. Sellis, T. Coupling Production Systems and Database Systems: A Homogeneous Approach / T. Sellis, C.-C. Lin, L. Raschid // IEEE Transactions on Knowledge and Data Engineering, v.5 n.2, p.240-256, April 1993

155. Kotidis, Y. A case for dynamic view management / Yannis Kotidis, Nick Roussopoulos // ACM Transactions on Database Systems (TODS), v.26 n.4, p.388-423, December 2001

156. Sellis, T. Query Optimization for Nontraditional Database Applications / Timos K. Sellis, Leonard Shapiro // IEEE Transactions on Software Engineering, v. 17 n.l, p.77-86, January 1991

157. Sharaf, M. Algorithms and metrics for processing multiple heterogeneous continuous queries / Mohamed A. Sharaf, Panos K. Chrysanthis, Alexandras Labrinidis, Kirk Pruhs // ACM Transactions on Database Systems (TODS), v.33 n.l, p. 1-44, March 2008

158. Ioannidis, Y. Optimal histograms for limiting worst-case error propagation in the size of join results / Yannis E. Ioannidis, Stavros

159. Christodoulakis // ACM Transactions on Database Systems (TODS), v.18 n.4, p.709-748, Dec. 1993

160. Ioannidis, Y. Balancing histogram optimality and practicality for query result size estimation / Yannis E. Ioannidis, Viswanath Poosala // ACM SIGMOD Record, v.24 n.2, p.233-244, May 1995

161. Cole, R. Optimization of dynamic query evaluation plans / Richard L. Cole, Goetz Graefe // ACM SIGMOD Record, v.23 n.2, p. 150-160, June 1994

162. Poosala, V. Improved histograms for selectivity estimation of range predicates / Viswanath Poosala, Peter J. Haas, Yannis E. Ioannidis, Eugene J. Shekita // ACM SIGMOD Record, v.25 n.2, p.294-305, June 1996

163. Schnaitter, K. Depth estimation for ranking query optimization / Karl Schnaitter, Joshua Spiegel, Neoklis Polyzotis // Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria

164. Fuchs, D. Compressed histograms with arbitrary bucket layouts for selectivity estimation / Dennis Fuchs, Zhen He, Byung Suk Lee, // Information Sciences: an International Journal, v. 177 n.3, p.680-702, February, 2007

165. Markl, V. Consistent selectivity estimation via maximum entropy / V. Markl, P. J. Haas, M. Kutsch, N. Megiddo, U. Srivastava, T. M. Tran // The VLDB Journal — The International Journal on Very Large Data Bases, v.16 n.l, p.55-76, January 2007

166. Schnaitter, K. Depth estimation for ranking query optimization / Karl Schnaitter, Joshua Spiegel, Neoklis Polyzotis // The VLDB Journal — The International Journal on Very Large Data Bases, v.18 n.2, p.521-542, April 2009

167. Markl, V. LEO: An autonomic query optimizer for DB2 / V. Markl, G. M. Lohman, V. Raman // IBM Systems Journal, v.42 n.l, p.98-106, January 2003

168. Stillger, M. LEO DB2's LEarning Optimizer / Michael Stillger, Guy M. Lohman, Volker Markl, Mokhtar Kandil // Proceedings of the 27th International Conference on Very Large Data Bases, p. 19-28, September 11-14, 2001

169. Chen, C. Adaptive selectivity estimation using query feedback / Chungmin Melvin Chen, Nick Roussopoulos // ACM SIGMOD Record, v.23 n.2, p.161-172, June 1994

170. Ziauddin, M. Optimizer plan change management: improved stability and performance in Oracle llg / Mohamed Ziauddin, Dinesh Das, Hong Su, Yali Zhu, Khaled Yagoub // Proceedings of the VLDB Endowment, v. 1 n.2, August 2008

171. Herodotou, H. Automated SQL tuning through trial and (sometimes) error / Herodotos Herodotou, Shivnath Babu // Proceedings of the Second International Workshop on Testing Database Systems, June 29-29, 2009, Providence, Rhode Island

172. Bruno, N. Configuration-parametric query optimization for physical design tuning / Nicolas Bruno, Rimma V. Nehme // Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada

173. Gosalia, A. Automatic plan choice validation using performance statistics / Ashit Gosalia, Xin (Shin) Zhang // Proceedings of the 1st international workshop on Testing database systems, June 13-13, 2008, Vancouver, British Columbia, Canada

174. Benoit, D. Automatic Diagnosis of Performance Problems in Database Management Systems / Darcy G. Benoit // Proceedings of the Second International Conference on Automatic Computing, p.326-327, June 1316, 2005

175. Chaudhuri, S. Self-Tuning Database Systems: A Decade of Progress / Surajit Chaudhuri, Vivek Narasayya // Proceedings of the Second International Conference on Automatic Computing, p.326-327, June 1316, 2005

176. Stonebraker, M. The Choice of Partial Inversions and Combined Indices / M. Stonebraker // International Journal of Computer and Information Sciences, 3(2), June 1974

177. Finkelstein, S. Physical Database Design for Relational Databases / Finkelstein, S., Schkolnick, M., and Tiberio, P. // ACM Trans. On Database Systems, Vol 13, No 1, March 1988

178. Shapiro, G. The Optimal Selection of Secondary Indices is NP-Complete / Shapiro, G.P. // SIGMOD Record 13(2): 72-75 (1983)

179. Agrawal, R. Fast Algorithms for Mining Association Rules in Large Databases / Agrawal, R., Ramakrishnan, S. // In Proceedings of VLDB, 1994

180. Agrawal, S. Automated Selection of Materialized Views and Indexes for SQL Databases / Agrawal, S., Chaudhuri, S., Narasayya, V. // In Proceedings of VLDB, Cairo, Egypt, 2000

181. Bruno, N. Physical Design Refinement. The Merge-Reduce Approach / Bruno, N., Chaudhuri, S. // In Proceedings of ACM SIGMOD conference, 2002

182. Papadomanolakis, S. Autopart: Automating Schema Design for Large Scientific Databases Using Data Partioning / Papadomanolakis, S., Ailamaki, A. //InProceedings of SSDBM, 2004

183. Zilio, S. DB2 Design Advisor: Integrated Automatic Physical Database Design / Zilio et al. // In Proceedings of the VLDB, Toronto, Canada, 2004

184. Dageville, B. Automatic SQL Tuning in Oracle lOg / Dageville, B., Das, D., Dias, K., Yagoub, K., Zait, M., Ziauddin, M. // In Proc. Of the 30 International Conference of VLDB, 2004

185. Lee, A. Closing the query processing loop in Oracle llg / Allison W.Lee, Mohamed Zait // In Proceedings of the VLDB Endowment, 2008

186. El-Helw, A. Collecting and Maintaining just-in-time statistics / El-Helw, A., Ilyas, I., Lau, W., Markl, V., Zusarte, C. // In Proceedings of ICDE, 2007