Аттестационная работа (ИАР/ВАР) на тему Восстановление и оптимизация запросов

Содержание:

ВВЕДЕНИЕ 4

1. Проблема оптимизации запросов 7

1.1 Запросы 7

1.2 Цели оптимизации 8

1.3 Нисходящий подход к оптимизации запросов 12

2. Представление запросов 14

2.1 Реляционное исчисление 14

2.2 Реляционная алгебра 16

2.3 Графы запросов 18

2.4 Табло 20

3. Преобразование запросов 23

3.2 Упрощение 25

3.3 Улучшение 27

4. Вычисление запросов 33

4.1 Выражения с одной переменной 33

4.2 Выражения с двумя переменными 35

4.3 Выражения с несколькими переменными 39

5. Планы доступа 43

5.1 Генерация планов доступа 46

5.2 Анализ стоимости планов доступа 47

5.3 Выбор путей доступа 50

5.4 Поддержка нескольких запросов 51

6. Нестандартная оптимизация запросов 53

6.1 Запросы более высокого уровня 53

6.2 Распределенные базы данных 55

6.2.1 Соотношение между стоимостями коммникаций и локальной обработки 57

6.2.2 Структура сети 57

6.2.3 Стратегия распределения данных 58

6.3 Машины баз данных 60

7 Расчет экономической части 63

7.1. Расчет себестоимости 63

7.1.2. Определение трудоемкости 63

7.2. Расчет затрат на материалы 65

7.3. Расчет расходов на заработную плату 65

7.4. Расчет начислений на заработную плату 65

7.5. Расчет себестоимости и цены разработки программного продукта 66

7.6. Расчет экономического эффекта 66

ЗАКЛЮЧЕНИЕ 67

СПИСОК ЛИТЕРАТУРЫ 68

Введение:

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

Существуют две основные области исследований в области систем баз дан-ных. Одним из них является анализ моделей данных, на основе которых может быть отображен реальный мир и на основе которых могут быть построены инте-ресы для различных типов пользователей. К таким концептуальным моделям от-носятся иерархическая, сетевая, реляционная и ряд семантически-ориентированных моделей, рассмотренных в большом количестве книг и обзоров [Brodie et al. 1984].

Вторая область интересов касается безопасной и эффективной реализации СУБД. Компьютеризированные данные становятся центральным ресурсом боль-шинства организаций. Это следует учитывать в каждой реализации, предназна-ченной для производственного использования, путем обеспечения безопасности данных в случаях одновременного доступа [Bernstein and Goodman 1981c], вос-становления [Verhofstad 1978] и реорганизации [Sockut and Goldberg 1979]. Од-ним из основных критических замечаний по отношению ко многим ранним СУБД была их недостаточная эффективность при обработке мощных операций, которые они предлагали, особенно при доступе к данным на основе их содержимого с по-мощью запросов. Оптимизация запросов предназначена для решения этой про-блемы путем интеграции большого количества методов и стратегий, начиная от логических преобразований запросов и заканчивая хранением данных на уровне файловой системы и оптимизацией путей доступа.

Традиционно в каждом из этих подходов использовался отдельный язык. Вероятно, это одна из причин, по которой всесторонний обзор методов оптими-зации запросов до сих пор не представлен. Цель этой статьи — представить ме-тоды оптимизации запросов в общей структуре реляционного исчисления. Пока-зано, что реляционное исчисление технически эквивалентно представлению реля-ционной алгебры [Codd 1972; Klug 1982a] и поддается расширениям для реали-зации сетевых СУБД [Dayal and Goodman 1982]. Более того, многие популярные языки запросов, такие как SQL [Astrahan and Chamberlin 1975] и QUEL [Stonebraker et al. 1976] легко сопоставляются с реляционным исчислением.

Для экономии места в этой статье мы сосредоточимся в первую очередь на проблеме оптимизации запросов в централизованной СУБД. Централизованная оптимизация запросов важна не только во многих базах данных мэйнфреймов, а в последнее время и в СУБД на основе микропроцессоров, но также является под-задачей оптимизации запросов в распределенных системах. Сама оптимизация распределенных запросов [Bayer et al. 1984 год; Сакко и Яо, 1982 г.; Ullman 1982] затрагивается лишь вскользь, и мы вообще не касаемся следующих двух связанных областей:

Пользовательская оптимизация. Общая стоимость информационной систе-мы складывается из стоимости СУБД и стоимости усилий пользователей по рабо-те с системой. Границей между этими двумя областями является функциональ-ность и удобство использования языка запросов [Vassiliou and Jarke 1984], а наиболее важной характеристикой является время отклика системы. Если пред-положить, что язык запросов имеет предполагаемую функциональность, а мини-мизация времени отклика является целью системы выполнения запросов, то оп-тимизацию запросов можно рассматривать как отдельную подзадачу пользова-тельской оптимизации.

файловые структуры. Алгоритм оптимизации запроса должен выбирать между несколькими путями доступа для выполнения запроса. Внутренние детали реализации таких путей доступа и получения соответствующих форм вычислений (см., например, Theorey and Fry [1982]) выходят за рамки этой статьи.

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

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

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

Заключение:

В статье представлен обзор методов логических преобразований и физиче-ского выполнения запросов к базе данных с использованием фреймворка реляци-онного исчисления. Показано, что накоплен большой объем знаний для решения проблемы эффективной обработки запросов в традиционных централизованных и распределенных системах баз данных.

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

 

Фрагмент текста работы:

1. Проблема оптимизации запросов

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

1.1 Запросы

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

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