рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

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

Общая стратегия оптимизации определяется на втором и третьем этапах. Рассмотрим их подробнее. - раздел Программирование, Среда Delphi широко известна и не вызывает дополнительных трудностей при изучении и использовании При Классическом Подходе К Организации Оптимизаторов Запросов На Этапе Логиче...

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

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

При приведении логического условия к каноническому представлению можно производить поиск общих предикатов (они могут существовать изначально, могут появиться после приведения предикатов к каноническому виду или в процессе нормализации логического условия) и упрощать логическое выражение. Например, фрагмент логического выражения (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. Где применяются законы эквивалентности выражений реляционной алгебры?

 

– Конец работы –

Эта тема принадлежит разделу:

Среда Delphi широко известна и не вызывает дополнительных трудностей при изучении и использовании

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

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

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

История создания баз данных
  Существуют различные определения базы данных. Обычно они либо неполны, либо слишком громоздки. Дадим простое определение, расширяя его по мере появления новых понятий.

Модели данных СУБД
  Коцептуальной моделью данных в БД называют глобальное логическое описание данных. Структуры данных коцептуальной модели влияют на все характеристики СУБД, охватывая · языки

Двенадцать правил Кодда для реляционных СУБД
В статье, опубликованной в 1985 году [3], Э. Кодд сформулировал двенадцать правил, которым должна соответствовать настоящая реляционная БД. Они являются полуофициальным определением понятия

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

Нормальная форма Бойса-Кодда
  Пусть в определенном выше отношении SP присутствует еще и имя поставщика Sname. Будем для удобства считать, что имя однозначно определяет поставщика. Тогда в отношении SP (Sn, Sname

Четвертая нормальная форма
  Рассмотрим таблицу R (Subj, Teach, Book), где Subj – учебный предмет, Teach- преподаватель по этому предмету, Book – книга, рекомендуемая преподавателем Teach для изучения предмета

Семантическое моделирование данных.
Элементы модели "сущность-связь" Семантическое моделирование данных на основе ER-диаграмм компактно и доступно изложено в [5], и мы будем следовать этому источни

В реляционной СУБД
  Одним из главных достоинств иерархических и сетевых СУБД считают естественность представления данных иерархической и сетевой природы. А как представлять такие данные в реляционных С

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

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

Общая характеристика и стандарты языка SQL
  Язык SQL (Structered Query Language) впервые появился в рамках проекта разработки экспериментальной реляционной СУБД System R в исследовательской лаборатории фирмы IBM в 1975-1979 г

Многотабличные запросы SQL. Соединения таблиц. Самосоединения. Псевдонимы
  Запросы могут выбирать данные изнескольких таблиц. Эти таблицы должны быть перечислены после слова FROM. Если таблицы не связаны между собой, то результатом запроса будут всевозможн

Внешнее соединение таблиц
  Рассмотренные соединения называют внутренними (INNER JOIN). В некоторых случаях требуются соединения другого вида – внешние соединения (OUTER JOIN). Рассмотрим две таблицы A (Stud,

Для реализации итоговых запросов в SQL имеются следующие стандартные функции, которые называют агрегатными
· MAX (поле) – максимальное значение поля; · MIN (поле) – минимальное значение поля; · AVG (поле) – среднее значение поля; · SUM (поле) – сумма значений поля; ·

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

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

Триггеры и хранимые процедуры
  Как уже говорилось, целостность данных часто связана с порядками и правилами в конкретной организации. Например: · клиенты не могут размещать заказы на сумму, превышающую и

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

Представления и работа с ними
  Представлением (VIEW) называется SQL-запрос на чтение, которому присвоили имя и сохранили в БД. Представление является виртуальной таблицей, то есть обеспечивает доступ к результата

Обеспечение безопасности баз данных в SQL
  Под безопасностью БД понимают защиту данных от несанкционированного чтения, изменения или уничтожения. Язык SQL позволяет индивидуально защищать как целые таблицы, так и отдельные и

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

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

Элементы языка QBE
  Язык QBE (Query By Example – запрос по образцу) был разработан в компании IBM в 1975 году. Это язык реляционного исчисления с переменными на доменах, рассчитанный на работу в интера

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

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги