Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Общая стратегия оптимизации определяется на втором и третьем этапах. Рассмотрим их подробнее

Подходы к оптимизации запросов

 

Говоря про оптимизацию запросов в реляционных СУБД, обычно имеют в виду такой способ обработки, когда по начальному представлению запроса путем преобразований вырабатывается процедурный план его выполнения. Как правило, невозможно добиться точной оптимизации запроса. Речь идет скорее о рационализации, улучшении запроса. Разные способы реализации запроса могут отличаться в десятки раз по времени выполнения. Соответствующие преобразования начального представления запроса выполняются специальным компонентом СУБД – оптимизатором. Обработка поступившего в систему запроса состоит из пяти этапов.

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

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

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

На четвертом этапе по внутреннему представлению выбранного плана выполнения запроса формируется выполняемое представление плана.

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

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

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

При приведении логического условия к каноническому представлению можно производить поиск общих предикатов (они могут существовать изначально, могут появиться после приведения предикатов к каноническому виду или в процессе нормализации логического условия) и упрощать логическое выражение. Например, фрагмент логического выражения (A>B) AND (B=5) можно заменить единственным условием (A>5). Такие упрощения могут оказаться существенными для дальнейшей обработки запроса. Запрос с логическим условием первого вида мог потребовать соединения отношений, а после преобразования соединение уже не требуется.

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

Приведем простой пример. Пусть представление определено как

DEFINE VIEW V (C2) AS

SELECT C1 FROM R WHERE C1 > 6

Запрос формулируется следующим образом:

SELECT C2 FROM V WHERE C2 < 6

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

SELECT C1 FROM R WHERE C1 < 6 AND C1 >6

Уже на фазе логической оптимизации можно было бы установить, что он эквивалентен запросу

SELECT C1 FROM R WHERE FALSE

из чего следовало бы, что результат запроса пуст.

Другой класс методов логической оптимизации связан с законами эквивалентности выражений реляционной алгебры. Рассмотрим следующий пример. Пусть имеются два отношения R (A, B) и S (C, D), где значения атрибутов B и C выбираются из одного и того же домена. Имеется вложенный запрос

SELECT X.A FROM R X WHERE EXISTS

(SELECT * FROM S Y WHERE (X.B=Y.C) AND (Y.D=100))

Результат запроса дает выражение реляционной алгебры

πA (B=C) and (D=100) (R ´ S))

Операция декартово произведение двух отношений дает все пары записей из R и S, поэтому требует большого объема вычислений. Легко заметить, что приведенное выражение эквивалентно выражению

πA (R σ D=100 (S)),

B=C

которое вычисляется быстрее. Действительно, операция σ D=100 (S) может быть реализована путем индексации отношения S по атрибуту D и способна выделить только небольшое число записей из S. Для каждой из них можно найти все записи, удовлетворяющие условию B=C, реализовав тем самым операцию эквисоединения. Эта операция может быть выполнена с помощью индексации отношения R по атрибуту B либо на основе сортировки отношений R и σD=100 (S) по атрибутам B и C соответственно. Последнюю операцию проекции πA целесообразно выполнять немедленно, а не при повторном просмотре.

Этот пример иллюстрирует общую стратегию оптимизации выражений реляционной алгебры, выражаемую следующими правилами [8]:

1. Выполнять операции селекции как можно раньше.

2. Комбинировать селекции с предшествующим декартовым произведением, получая соединение.

3. Использовать индексацию или сортировку для реализации соединений.

4. Комбинировать проекции с предшествующими или последующими двуместными операциями.

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

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

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

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

 

КОНТРОЛЬНЫЕ ВОПРОСЫ

 

1. Что такое логическая и физическая независимость данных? Проиллюстрировать эти понятия на примерах Турбо Паскаля и Delphi c BDE.

2. Пояснить на примерах понятие централизации данных.

3. Какие функции имеет администратор базы данных?

4. Какие требования к СУБД являются противоречивыми?

5. В чем отличие архитектур файл-сервер и клиент-сервер?

6. Почему иерархические и сетевые СУБД были созданы раньше реляционных?

7. Какие типы ключей Вы знаете?

8. Может ли ключ состоять из всех атрибутов отношения?

9. Что является операндами и результатом операций реляционной алгебры?

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

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

12. Что такое полная функциональная зависимость?

13. Какие недостатки имеют отношения, не находящиеся во второй нормальной форме? В третьей нормальной форме?

14. Приведите примеры приведения ко второй и третьей нормальным формам.

15. Приведите примеры отношений, находящихся в первой, но не во второй нормальных формах.

16. Приведите примеры отношений, находящихся во второй, но не в третьей нормальных формах.

17. Какие недостатки имеют отношения, не находящиеся в нормальной форме Бойса-Кодда?

18. Какие недостатки могут проявиться после приведения отношений к нормальной форме Бойса-Кодда?

19. Что такое многозначная зависимость?

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

21. Как практически определяется наличие многозначной зависимости?

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

23. Что такое семантическое моделирование данных?

24. Какие проблемы вызывает проектирование структуры БД на основе нормальных форм?

25. Какие связи наиболее характерны в конечных ER-диаграммах?

26. Как преобразуются связи M:M в ER-диаграммах?

27. Как ER-диаграмма преобразуется в набор таблиц БД? Какой при этом уровень нормализации обеспечивается?

28. Приведите примеры представления графов и деревьев с помощью таблиц.

29. Что такое реляционное исчисление?

30. Каким образом связаны реляционные исчисления на кортежах и доменах?

31. Выразить базовые операции реляционной алгебры формулами реляционного исчисления.

32. Являются ли процедурными языки запросов, основанные на реляционном исчислении?

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

34. Раскройте понятие целостности базы данных.

35. Какие виды условий целостности существуют?

36. Почему любая новая реляционная СУБД всегда включает SQL?

37. Можно ли запросы SQL переносить без изменения из одной СУБД в другую?

38. Укажите основные возможности языка SQL.

39. Что такое NULL-значения?

40. Каким образом определяется истинность логического выражения, которое включает поля, принимающие NULL-значения?

41. Приведите примеры условной выборки данных из одной таблицы с помощью оператора SELECT.

42. Какие типы условий могут быть заданы после ключевого слова WHERE?

43. Что такое внутреннее соединение таблиц?

44. Приведите пример самосоединения.

45. Чем внешнее соединение отличается от внутреннего?

46. Приведите примеры, когда требуются левое и правое внешнее соединения.

47. Приведите примеры запросов с группировкой.

48. Перечислите функции, которые могут быть указаны в условии HAVING запроса с группировкой.

49. Какие типы вложенных запросов на чтение Вы знаете?

50. Когда в операторе SELECT необходимо указывать псевдонимы?

51. Приведите примеры операторов INSERT, DELETE, UPDATE с вложенными подзапросами.

52. Приведите примеры нарушения условий целостности.

53. Что такое ссылочная целостность?

54. Какие изменения базы данных могут нарушить ссылочную целостность?

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

56. Что такое каскадные удаления и обновления? Какие проблемы они вызывают?

57. Что такое триггеры и хранимые процедуры? Почему триггеры и хранимые процедуры сохраняются совместно с БД?

58. Что такое транзакция?

59. Какие проблемы возникают при обработке транзакций в многопользовательском режиме?

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

61. Опишите средства определения таблиц SQL.

62. Как изменить структуру существующей таблицы?

63. Как организовать индекс таблицы? Какие преимущества и недостатки он несет?

64. Какие представления могут обновляться?

65. Какие принципы защиты данных используются в SQL?

66. Как выполняются предоставление и отмена привилегий?

67. Какие проблемы возникают в случаях передачи привилегий?

68. Что такое встроенный SQL? Каковы основные концепции встроенного SQL?

69. Что такое курсор?

70. Чем динамический SQL отличается от статического?

71. Назовите основные операторы динамического SQL в стандарте SQL92.

72. Поясните смысл переменных в языке QBE.

73. Приведите примеры запросов QBE, которые используют данные из двух таблиц.

74. Чем в языке QBE отличается операция отрицания, относящаяся к некоторому атрибуту, от этой операции, относящейся ко всему кортежу?

75. Назовите этапы реализации запроса в языке реляционного исчисления.

76. Приведите пример оптимизации выражения реляционной алгебры.

77. Где применяются законы эквивалентности выражений реляционной алгебры?

 

Литература

 

1. Мартин Д. Организация баз данных в вычислительных системах. - М.: Мир, 1980.

2. Дейт К. Дж. Введение в системы баз данных, 7-е издание. – М.: Издат. дом “Вильямс”, 2002. – 1072 с.

3. Codd E.F. Is Your DBMS Really Relational and Does Your DBMS Run by the Rules? - Computerword, Octouber, 1985. - № 14, № 21.

4. Мейер Д. Теория реляционных баз данных. - М.: Мир, 1987. – 608 с.

5. Пушников А.Ю. Введение в системы управления базами данных: Учебное пособие в двух частях. – Уфа: Издательство Башкирского университета, 1999. -246 с.

6. Джеймс Р. Грофф, Пол Н. Вайнберг. SQL: полное руководство. - К.: Издательская группа BHV, 2000. - 608 с.

7. Форта Б. Освой самостоятельно SQL. 10 минут на урок. – М.: Издат. дом “Вильямс”, 2006. – 288 с.

8. Ульман Дж. Основы систем баз данных. – М.: Финансы и статистикаб 1983 – 334 с.


Содержание

Введение  
1. История создания баз данных  
2. Модели данных СУБД  
3. Основные понятия реляционной модели данных  
4. Двенадцать правил Кодда для реляционных СУБД  
5. Нормализация таблиц базы данных. Первая, ворая и третья нормальные формы  
6. Нормальная форма Бойса-Кодда  
7. Четвертая нормальная форма  
8. Семантическая модель данных. Элементы модели “сущность-связь”  
9. Представление деревьев и графов в реляционной СУБД  
10. Основы реляционной алгебры  
11. Основы реляционного исчисления  
12. Общая характеристика и стандарты языка SQL  
13. Оператор SELECT языка SQL. Запросы на чтение из одной таблицы. NULL-значения  
14. Многотабличные запросы SQL. Соединение таблиц. Самосоединения. Псевдонимы  
15. Внешнее соединение таблиц  
16. Итоговые запросы. Запросы с группировкой  
17. Вложенные запросы на чтение  
18. Изменение баз данных  
19. Целостность данных  
20. Триггеры и хранимые процедуры  
21. Обработка транзакций  
22. Операторы создания БД  
23. Представления и работа с ними  
24. Обеспечение безопасности баз данных в SQL  
25. Курсоры  
26. Динамический SQL  
27. Элементы языка QBE  
28. Подходы к оптимизации запросов  
Литература  

 

<== предыдущая лекция | следующая лекция ==>
Элементы языка QBE | 
Поделиться с друзьями:


Дата добавления: 2014-01-07; Просмотров: 352; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.054 сек.