Лекция понятие субд. Функции субд - страница 8


Литература:


  1. Дейт К.Дж. Введение в системы баз данных. –Пер. с англ. –6-е изд. –К. Диалектика, 1998. Стр. 394 – 410.

  2. Джеймс Р. Грофф, Пол Н. Вайнберг. SQL: полное управление: пер.с англ. –К.: Издательская группа BHV, 2000.–608с Лекция понятие субд. Функции субд - страница 8. Стр. 329–368.

  1. Физическая организация БД: структуры хранения и способы доступа


13.1 Доступ к базе данных

13.2 Кластеризация

13.3 Индексирование

13.4 Структуры типа Б-дерева

13.5 Хеширование


    1. Доступ к базе данных


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

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

Как упоминалось ранее, хоть какое упорядочение (размещение) данных Лекция понятие субд. Функции субд - страница 8 на диске именуется структурой хранения. Можно организовать самые различные структуры хранения, владеющие различной производительностью и рациональные для разных методов использования. Но не существует безупречной структуры хранения, которая была бы оптимальна для Лекция понятие субд. Функции субд - страница 8 всех задач. Исходя из этого, можно заключить, что совершенная СУБД должна содержать несколько различных структур хранения для разных частей системы. Не считая того, следует также предугадать возможность конфигурации структуры хранения по мере конфигурации Лекция понятие субд. Функции субд - страница 8 требований к производительности системы.

Работа СУБД построена последующим образом и включает три главных шага (рис. 17.2).


рис. 17.2 Схема взаимодействия СУБД, диспетчера файлов и диспетчера дисков.


  1. Поначалу в СУБД определяется разыскиваемая запись, а Лекция понятие субд. Функции субд - страница 8 потом для ее извлечения запрашивается диспетчер файлов.

  2. Диспетчер файлов определяет страничку, на которой находится разыскиваемая запись, а потом для извлечения этой странички запрашивает диспетчер дисков.

  3. 3. В конце концов, диспетчер дисков определяет физическое Лекция понятие субд. Функции субд - страница 8 положение разыскиваемой странички на диске и отправляет соответственный запрос на ввод-вывод данных.

^ Диспетчер дисков. Диспетчер дисков является компонентом применяемой операционной системы, при помощи которого производятся все дисковые операции ввода-вывода (в Лекция понятие субд. Функции субд - страница 8 неких операционных системах он именуется компонентом базисной системы ввода-вывода).

Для выполнения этих операций следует знать значения физических адресов на диске. К примеру, если диспетчер файлов запрашивает некую страничку диспетчеру дисков Лекция понятие субд. Функции субд - страница 8 следует знать, где непосредственно находится страничка на физическом диске. Но "юзеру" диспетчера дисков, т.е. диспетчеру файлов, не непременно знать физические адреса. Заместо этого диспетчеру файлов довольно рассматривать диск как набор страничек фиксированного размера Лекция понятие субд. Функции субд - страница 8 (т.е. набор "ячеек" памяти схожего размера) с уникальным идентификационным номером набора страничек. Любая страничка, в свою очередь, обладает уникальным снутри данного набора идентификационным номером странички, при этом наборы не имеют общих Лекция понятие субд. Функции субд - страница 8 страничек. Соответствие физических адресов на диске и номеров страничек достигается при помощи диспетчера дисков. Основным (и не единственным) преимуществом таковой организации является изоляция программного кода, зависящего от определенного устройства диска Лекция понятие субд. Функции субд - страница 8, снутри 1-го из компонент системы, а конкретно снутри диспетчера дисков. В таком случае все составляющие высочайшего уровня, а именно диспетчера файлов, могут быть аппаратно независящими.

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

Каждый хранимый Лекция понятие субд. Функции субд - страница 8 файл имеет имя (file name) либо идентификационный номер (file ID), уникальные в данном наборе страничек. А любая хранимая запись, в свою очередь, обладает идентификационным номером записи (record number либо record ID), уникальным Лекция понятие субд. Функции субд - страница 8, по последней мере, в границах данного хранимого файла.

    1. Кластеризация


Нельзя окончить этот лаконичный обзор без упоминания технологии кластеризации данных. В ее базе лежит принцип как можно более близкого физического размещения на диске логически связанных меж собой Лекция понятие субд. Функции субд - страница 8 и нередко применяемых данных. Физическая кластеризация данных – очень принципиальное условие высочайшей производительности, что можно показать последующим примером. Допустим, что более нередко употребляется хранимая запись r1 странички p1, для работы Лекция понятие субд. Функции субд - страница 8 с которой также требуется вызывать хранимую запись r2 странички p2. Тогда может быть появление последующих ситуаций:

  1. Если странички р1 и р2 совпадают, то для доступа к записи r2 не будет нужно делать Лекция понятие субд. Функции субд - страница 8 еще одну физическую операцию ввода-вывода, так как подходящая страничка уже будет находиться в оперативки.

  2. Если странички р1 и р2 не совпадают, но на физическом уровне располагаются довольно близко, к примеру смежные странички Лекция понятие субд. Функции субд - страница 8, то для доступа к записи r2 будет нужно выполнить еще одну физическую операцию ввода-вывода (если, естественно, страничка p2 еще не находится в оперативки). Но, так как головка чтения/записи уже будет Лекция понятие субд. Функции субд - страница 8 находиться в конкретной близости от подходящего положения, время поиска будет очень малым. А если странички р1 и р2 находятся на одном цилиндре, время поиска вообщем будет равно нулю.

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

Кластеризация снутри СУБД вероятна исключительно в том случае, если админ Лекция понятие субд. Функции субд - страница 8 базы данных организует ее. В совершенных СУБД нередко предвидено задание нескольких разных типов кластеризации данных из различных файлов.

    1. Индексирование

Разглядим в качестве примера таблицу с данными о студентах, также нередко применяемый и поэтому очень принципиальный запрос Лекция понятие субд. Функции субд - страница 8 типа "Отыскать всех студентов учащихся в группе X", где X – некоторый параметр. При таких критериях админ базы данных может избрать метод сохранения данных, схематически показанный на рис. 17.2. Он основан на 2-ух хранимых Лекция понятие субд. Функции субд - страница 8 файлах: файле с данными о студентах и файле с данными о группах; файлы могут располагаться в разных наборах страничек. Подразумевается, что в файле групп употребляется упорядочение по алфавитному перечню Лекция понятие субд. Функции субд - страница 8 их заглавий, т.е. по главному полю GrName (заглавие группы) с указателями на надлежащие записи в файле поставщиков.


рис. 17.2 Индексирование файла поставщиков по полю CITY файла городов.


Для поиска всех студентов из группы Б Лекция понятие субд. Функции субд - страница 8-99-51 можно применить последующую стратегию: отыскать в файле групп группу Б-99-51, а потом согласно указателям извлечь все надлежащие записи из файла студентов.

Такая стратегия будет более действенной по сопоставлению с поиском в файле Лекция понятие субд. Функции субд - страница 8 с данными студентов, так как, СУБД известна физическая последовательность записей в файле групп (поиск будет прекращен после извлечения последующей за Б-98-51 наименования группы в алфавитном порядке). Не считая того, даже если придется Лекция понятие субд. Функции субд - страница 8 просмотреть файл групп на сто процентов, для такового поиска будет нужно еще меньше операций ввода-вывода, так как физический размер файла групп меньше, чем размер файла с данными студентов из-за наименьшего Лекция понятие субд. Функции субд - страница 8 размера записей.

В рассматриваемом примере файл групп именуется индексным файлом либо индексом по отношению к файлу студентов, и напротив, файл студентов индексирован (именуется индексированным файлом) по отношению к файлу групп.

^ Индексный Лекция понятие субд. Функции субд - страница 8 файл – это хранимый файл особенного типа, в каком любая запись состоит из 2-ух значений, а конкретно данных и указателя. Данные соответствуют некому полю (индексному полю) из индексированного файла, а указатель служит Лекция понятие субд. Функции субд - страница 8 для связывания с соответственной записью индексированного файла. Индексное поле также именуется индексным ключом (index key).

Индекс можно сопоставить с предметным указателем обыкновенной книжки, который состоит из перечня слов с "указателями" (номерами страничек) для упрощения поиска Лекция понятие субд. Функции субд - страница 8 связанной с этими словами инфы из "индексированного файла" (т.е. из содержимого книжки).

Главным преимуществом использования индексов является существенное ускорение процесса подборки либо извлечения данных, а главным недочетом – замедление процесса обновления Лекция понятие субд. Функции субд - страница 8 данных, так как при каждом добавлении новейшей записи в индексированный файл будет нужно также добавить новый индекс в индексный файл.

Хранимый файл может иметь несколько индексов, которые могут как раздельно, так и вместе Лекция понятие субд. Функции субд - страница 8 употребляться для более действенного доступа к записям о поставщиках.

Индексы нередко именуют инвертированными перечнями. Дело в том, что если файл студентов (см. рис. 17.2) имеет классическую структуру перечня набора значений Лекция понятие субд. Функции субд - страница 8 полей для каждой записи, то индекс содержит перечень набора записей для каждого значения индексированного поля.

Индекс можно также сделать на базе композиции 2-ух либо более полей. К примеру, на рис. 17.2 показана схема Лекция понятие субд. Функции субд - страница 8 индексирования файла студентов на базе композиции полей GrName и City. При таковой организации в СУБД можно выполнить запрос типа "Отыскать студентов учащихся в группе Б-98-51 живущих в г. Кривой Рог" на базе однократного просмотра при Лекция понятие субд. Функции субд - страница 8 помощи 1-го индекса.


рис. 17.2 Индексирование файла поставщиков на базе композиции полей GrName и City


Направьте внимание, что комбинированный индекс GrName/City может также служить индексом по одному полю GrName, так как все Лекция понятие субд. Функции субд - страница 8 записи в комбинированном индексе размещены поочередно.


      1. ^ Плотное и неплотное индексирование

Основной целью использования индекса является ускорение процесса извлечения данных, поточнее, уменьшение числа дисковых операций ввода-вывода, нужных для извлечения требуемой записи. В главном Лекция понятие субд. Функции субд - страница 8 это достигается благодаря использованию указателей. Хотя до сего времени предполагалось, что в этом качестве употребляются указатели записей, по сути для этого довольно было бы указателей страничек (т.е. номеров страничек). Естественно, для Лекция понятие субд. Функции субд - страница 8 следующего поиска записи снутри данной странички придется выполнить еще одну операцию извлечения записи, но сейчас она будет производиться в оперативки и для этого не придется наращивать число дисковых операций ввода-вывода Лекция понятие субд. Функции субд - страница 8.

Эту идею можно развить далее, если вспомнить, что данные в каждом хранимом файле находятся в единой "физической" последовательности на базе композиции последовательности хранимых записей снутри каждой странички и последовательности страничек снутри Лекция понятие субд. Функции субд - страница 8 каждого набора страничек. Представим, что физическая последовательность файла студентов соответствует логической последовательности, данной на базе некого поля, к примеру номера студента. По другому говоря, в этом файле выполнена кластеризация по данному полю. Допустим, что Лекция понятие субд. Функции субд - страница 8 по этому же полю осуществляется индексирование; тогда нет необходимости в данном индексе хранить указатели для каждой записи индексируемого файла (в этом случае для файла студентов). Все, что требуется, – это указатель для Лекция понятие субд. Функции субд - страница 8 каждой странички, состоящий из наибольшего номера студента для данной странички и соответственного номера странички. Схематически такая структура показана на , где для простоты подразумевается, что на каждой страничке может располагаться максимум две записи Лекция понятие субд. Функции субд - страница 8.




рис. 17.2 Рис. А. 12 Пример использования неплотного индекса.


В качестве примера разглядим процесс извлечения записи с номером 3 при помощи такового индекса. Поначалу в СУБД проводится поиск индекса для записи с номером, огромным либо равным 3. При Лекция понятие субд. Функции субд - страница 8 всем этом будет найдено поле с номером 4, которое содержит указатель на страничку p. Страничка p извлекается, помещается в оперативку и просматривается для поиска данной хранимой записи (которая в данном Лекция понятие субд. Функции субд - страница 8 примере будет найдена очень стремительно).

Индекс с описанной структурой именуется неплотным (либо разряженным), так как в нем не содержатся указатели на все записи индексированного файла. Схематически пример такового индекса показан на . (Все Лекция понятие субд. Функции субд - страница 8 описанные выше индексы, напротив, именуются плотными.) Одним из преимуществ неплотных индексов является их малый размер по сопоставлению с плотными индексами, потому что они содержат наименьшее число записей. Это нередко позволяет просматривать содержимое базы данных Лекция понятие субд. Функции субд - страница 8 с большей скоростью. Но при помощи 1-го только неплотного индекса нельзя выполнить проверку наличия некого значения.

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


    1. ^ Структуры типа Б-дерева


Одним из более принципиальных и всераспространенных индексов является структура типа Лекция понятие субд. Функции субд - страница 8 Б-дерева (B-tree).

Причина необходимости сотворения структуры типа Б-дерева заключается в желании избежать неотклонимого просмотра всего содержимого индексированного файла согласно его физической последовательности. Дело в том, что если индексированный файл имеет большой размер Лекция понятие субд. Функции субд - страница 8, то и его индекс также очень велик. Потому поочередный просмотр даже 1-го только индекса просит огромных издержек времени. Разрешить эту делему можно этим же методом, что и ранее: разглядеть индексный Лекция понятие субд. Функции субд - страница 8 файл как обыденный хранимый файл и сделать для него очередной индекс. Эту операцию можно производить повторно необходимое количество раз (обычно она применяется три раза, так как создание огромного количества иерархических уровней индексирования требуется для Лекция понятие субд. Функции субд - страница 8 очень огромных файлов). При всем этом индекс на каждом из уровней будет неплотным по отношению к нижнему индексируемому уровню (он непременно должен быть неплотным, по другому такая структура глупа, потому что Лекция понятие субд. Функции субд - страница 8 уровень n содержал бы такое же количество записей, что и уровень n+1, а для просмотра потребовалось бы такое же долгое время).

Структура типа Б-дерева является личным случаем индекса древовидного типа Лекция понятие субд. Функции субд - страница 8 и в первый раз описана в статье Байера (Вауег) и Мак-Крайта (McCreight) в 1972 году. С того времени Байером и другими исследователями было предложено огромное количество вариантов реализации этой идеи. В итоге бинарные индексы Лекция понятие субд. Функции субд - страница 8 разных типов стали обширно употребляться во всех современных СУБД.

В варианте Кнута индекс состоит из 2-ух частей:

  1. Набор последовательностей включает одноуровневый индекс для реальных данных, который обычно является плотным Лекция понятие субд. Функции субд - страница 8, но может быть и неплотным, если в индексированном файле проведена кластеризация на базе индекса

  2. Набор индексов, в свою очередь, обеспечивает резвый конкретный доступ к набору последовательностей (а означает, и к данным). На самом деле Лекция понятие субд. Функции субд - страница 8, набор индексов является древовидным индексным файлом для набора последовательностей либо, строго говоря, индексом со структурой Б-дерева. Композиция набора индексов и набора последовательностей именуется структурой типа Б-плюс-дерева (B-plus Лекция понятие субд. Функции субд - страница 8 tree либо B-tree). На рис. 17.2 показан обычной пример таковой структуры.

Числа 6, 8, 12, ... 97, 99 являются значениями индексированного поля F. Корневой элемент содержит два значения поля F (50 и 82) и три указателя (номера страничек). Данные со Лекция понятие субд. Функции субд - страница 8 значением поля F, равным либо наименьшим 50, могут быть найдены при помощи левого указателя; данные со значением поля F, огромным 50 и равным либо наименьшим 82, – при помощи среднего указателя; в конце концов, данные со значением Лекция понятие субд. Функции субд - страница 8 поля F, огромным 82, – при помощи правого указателя. Другие элементы набора индексов следует интерпретировать схожим образом. Направьте внимание, что благодаря переходу на 2-ой уровень по левому указателю в предстоящем поиск по правому Лекция понятие субд. Функции субд - страница 8 указателю будет осуществляться ко всем записям со значением поля F, огромным 32 и равным либо наименьшим 50.

Вообщем, Б-дерево порядка п содержит более п и менее 2п записей с данными в каждом из Лекция понятие субд. Функции субд - страница 8 частей структуры (для каждых k записей требуется также k+1 указателей). Не считая того, ни одна из записей не может употребляться 2-мя различными элементами.

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

Преимуществом структуры типа Б-дерева является возможность равновесной Лекция понятие субд. Функции субд - страница 8 вставки либо удаления значений. (Вот почему для британского написания такового индекса, "B-tree", время от времени употребляют заместо знака "В" эпитет от "равновесный" (balanced).) Ниже приводится лаконичный метод вставки нового значения V в структуру типа Лекция понятие субд. Функции субд - страница 8 Б-дерева порядка п. Он рассчитан на вставку значения только только в набор индексов, но может быть довольно легко расширен для вставки записи с данными в набор последовательностей.

  1. На самом малом Лекция понятие субд. Функции субд - страница 8 уровне набора индексов следует отыскать элемент (допустим, что это элемент N), с которым логически связано вставляемое значение V. Если элемент N содержит свободное место, то значение V вставляется в него и на этом Лекция понятие субд. Функции субд - страница 8 процесс заканчивается.

  2. В неприятном случае (если свободного места нет, т.е. придется сделать очередной уровень) элемент N (допустим, что он содержит 2n индексных записей) делится на два элемента – N1 и N Лекция понятие субд. Функции субд - страница 82. Обозначим эмблемой 5 огромное количество из 2n+1 значений, в каком 2n начальных значений и одно новое значение V. Тогда n первых значений этой логической (уже упорядоченной) последовательности нужно поместить в элемент Лекция понятие субд. Функции субд - страница 8 N1, n последних – в элемент N2, а среднее меж ними значение W– в родительский элемент Р на более высочайшем структурном уровне. Потом, при осуществлении поиска значения U и достижении элемента P, поиск будет перенаправлен в Лекция понятие субд. Функции субд - страница 8 сторону элемента N1, если V W.

  3. Дальше этот процесс следует повторить для вставки среднего значения W в родительский элемент Р на более высочайшем структурном уровне.

В худшем случае процесс разделения частей Лекция понятие субд. Функции субд - страница 8 структуры может продлиться прямо до корневого элемента всей структуры с образованием нового иерархического уровня.

Для удаления некого значения следует применить аналогичный метод, но исключительно в оборотном порядке. А для конфигурации значения его Лекция понятие субд. Функции субд - страница 8 можно удалить, а потом воткнуть новое.


рис. 17.2 Пример структуры типа Б-дерева


    1. Хеширование


Хешированием, хеш-адресацией либо хеш-индексированием именуется разработка резвого прямого доступа к хранимой записи на базе данного значения некого Лекция понятие субд. Функции субд - страница 8 поля. При всем этом не непременно, чтоб поле было главным.

Ниже перечислены главные черты этой технологии:

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

  2. для сохранения записи в СУБД поначалу рассчитывается хеш-адрес новейшей записи, а потом диспетчер Лекция понятие субд. Функции субд - страница 8 файлов помещает эту запись по вычисленному адресу.

  3. Для извлечения подходящей записи по данному значению хеш-поля в СУБД поначалу рассчитывается хеш-адрес, а потом диспетчеру файлов посылается запрос для извлечения записи по вычисленному адресу Лекция понятие субд. Функции субд - страница 8.

В качестве обычной иллюстрации представим, что у нас есть записи с данными о студентах с кодами 100, 200, 300, 400, 500, а в качестве хеш-функции h употребляется последующая: h = StNo mod 13, где h – хеш Лекция понятие субд. Функции субд - страница 8-адрес, StNo – код студента.

Это простой пример общего класса хеш-функций типа деление/остаток. (В качестве делителя следует выбирать обычное натуральное число). В этом примере хеш-адресами для данных записей будут 9, 5, 1, 10 и 6 соответственно. Схематически Лекция понятие субд. Функции субд - страница 8 обоюдное размещение записей на страничках показано на .


0




1

Иванов





2




3




4










300




























5

Петров





6

Сидоров





7




8




9

Стрельцов





200










500






















100










10

Кузнецов





11




12







400




























рис. 17.2 Пример использования хеширования.


Недочетом хеширования является возможность появления коллизий, т.е. ситуаций, когда две либо более разных записи имеют схожие адреса. Допустим, что файл Лекция понятие субд. Функции субд - страница 8 студентов из предшествующего примера (с записями 100, 200 и т.д.) содержит также запись с номером 1400. При использовании хеш-функции h = StNo mod 13 возникнет коллизия (по адресу 9) с записью 100.

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

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

Существует ряд модификаций метода хеширования Лекция понятие субд. Функции субд - страница 8, к примеру, расширяемое хеширование и др., используемые для оптимизации операций обновления и поиска в БД.


Литература:


  1. Дейт К.Дж. Введение в системы баз данных. –Пер. с англ. –6-е изд. –К. Диалектика, 1998. Стр. 674–696.

  1. Оптимизация запросов


14.1 Оптимизация Лекция понятие субд. Функции субд - страница 8 в реляционных СУБД.

14.2 Пример оптимизации реляционного выражения

14.3 Обзор процесса оптимизации

14.4 Преобразование выражений

    1. Оптимизация в реляционных СУБД.


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

Преимущество автоматической оптимизации состоит в том, что юзер может не думать над лучшим Лекция понятие субд. Функции субд - страница 8 методом выражения собственных запросов (т.е. над тем, как сконструировать запрос, чтоб система выполнила его с очень вероятной производительностью). Но это далековато не все. Существует настоящая возможность, что оптимизатор Лекция понятие субд. Функции субд - страница 8 определит запрос лучше, чем программист-пользователь. Для подобного утверждения есть ряд обстоятельств. Ниже приведены только некие из их:

  1. Неплохой оптимизатор – направьте внимание на слово "неплохой" – обладает достаточным количеством инфы, которой юзер может не иметь Лекция понятие субд. Функции субд - страница 8. Поточнее, оптимизатор должен владеть некими статистическими данными, такими как кардинальное число каждого базисного дела, количество различающихся значений для каждого атрибута в отношении, количество вхождений каждого значения в атрибутах и т Лекция понятие субд. Функции субд - страница 8.п. Благодаря наличию этих данных оптимизатор способен более точно оценивать эффективность хоть какой стратегии реализации определенного запроса. Потому оптимизатор сумеет избрать лучшую стратегию реализации запроса.

  2. Если со временем статистика базы данных существенно Лекция понятие субд. Функции субд - страница 8 поменяется (к примеру, база данных будет на физическом уровне реорганизована), то для реализации запроса может потребоваться совершенно другая стратегия, чем до реорганизации. Другими словами, может пригодиться повторная оптимизация, либо реоптимизация. В реляционных системах процесс реоптимизации Лекция понятие субд. Функции субд - страница 8 довольно банален – это просто повторная обработка начального запроса системным оптимизатором. С другой стороны, в нереляционных системах реоптимизация просит переписывания программки, и, может быть, неосуществима вообщем.

  3. Оптимизатор – это программка, потому Лекция понятие субд. Функции субд - страница 8 он более "настойчив" по сопоставлению с человеком. Оптимизатор полностью способен рассматривать практически сотки разных стратегий реализации данного запроса, в то время как программер навряд ли изучает более трех-четырех стратегий (по последней мере Лекция понятие субд. Функции субд - страница 8, довольно глубоко).

  4. В оптимизатор интегрированы познания и опыт "наилучших из наилучших" программистов, что делает эти познания и опыт доступными для всех. Естественно, в неприятном случае широкому кругу юзеров будет предоставлен очевидно недостающий набор Лекция понятие субд. Функции субд - страница 8 дешевеньких и неэффективных способностей.




    1. ^ Пример оптимизации реляционного выражения


Начнем изложение с обычного примера, дающего представление о результатах, которые можно получить при помощи оптимизации. Разглядим запрос "Получить перечень фамилий студентов, учащихся в группе А-98-51". Алгебраическая Лекция понятие субд. Функции субд - страница 8 запись этого запроса такая:

((Students JOIN Groups) WHERE GrName = 'А-98-51') [StName]

Представим, что база данных содержит информацию о 100 группах и 10000 студентов, только 30 из которых учатся в группе А-98-51. В таком случае Лекция понятие субд. Функции субд - страница 8, если система будет вычислять выражение прямо (т.е. вообщем без оптимизации), то последовательность выполняемых действий будет смотреться так:

  1. ^ Соединение отношений Students и Groups (по атрибуту GrNo). На этом шаге считывается информация о Лекция понятие субд. Функции субд - страница 8 10000 студентов и 10000 раз считывается информация о 100 группах (один раз для каждого студента). После чего создается промежный итог, состоящий из 10000 соединенных кортежей.

  2. Подборка кортежей с данными только о группе А-98-51 из результата, приобретенного на Лекция понятие субд. Функции субд - страница 8 шаге 1. На этом шаге создается новое отношение, которое состоит из 30 кортежей.

  3. Проекция результата, приобретенного на шаге 2, по атрибуту StName. На этом шаге создается требуемый итог, состоящий из 30 кортежей.

Показанная ниже процедура Лекция понятие субд. Функции субд - страница 8 эквивалентна описанной в том смысле, что непременно создаст тот же конечный итог, но более действенным методом:

  1. ^ Подборка кортежей с данными только о группе А-98-51 из дела Groups. На этом шаге производится чтение 100 кортежей Лекция понятие субд. Функции субд - страница 8 и создается итог, состоящий только из 1 кортежа.

  2. ^ Соединение результата, приобретенного на шаге 1, с отношением Students (по атрибуту GrNo). На этом шаге производится считывание данных о 10000 студентов и 10000 раз считывается информация о Лекция понятие субд. Функции субд - страница 8 группе А-98-51, приобретенная на 1 шаге. Итог содержит 30 кортежей.

  3. ^ Проецирование результата, приобретенного на шаге 2, по атрибуту StName (аналогично шагу 3 предшествующей последовательности действий). Требуемый итог содержит 30 кортежей.

1-ая из показанных процедур делает в Лекция понятие субд. Функции субд - страница 8 общем 1010000 операций ввода-вывода кортежа, в то время как 2-ая процедура делает только 20000 операции ввода-вывода. Как следует, если принять "количество операции ввода-вывода кортежа" в качестве меры производительности, то 2-ая процедура Лекция понятие субд. Функции субд - страница 8 в 50 раз эффективнее первой. (На практике мерой производительности служит количество операций ввода-вывода странички, а не 1-го кортежа, но для данного примера эту поправку можно игнорировать.)


    1. Обзор процесса оптимизации




      1. Стадия 1. Преобразование запроса Лекция понятие субд. Функции субд - страница 8 во внутреннюю форму

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

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

К примеру, на рисунке показано дерево рассматриваемого выше в этой главе Лекция понятие субд. Функции субд - страница 8 запроса ("Получить перечень фамилий студентов, учащихся в группе А-98-51").


рис. 17.2. Дерево запроса "Получить перечень фамилий студентов, учащихся в группеА-98-51"


      1. Стадия 2. Преобразование в каноническую форму

На этой стадии оптимизатор делает несколько операций оптимизации Лекция понятие субд. Функции субд - страница 8, которые "гарантированно являются неплохими" независимо от реальных данных, хранящихся в базе данных, и путей доступа к ним. Сущность в том, что все запросы (кроме простых) реляционные языки обычно позволяют выразить несколькими различными (по Лекция понятие субд. Функции субд - страница 8 последней мере, снаружи) методами.

^ Замечание о канонической форме. Понятие канонической формы употребляется, в почти всех разделах арифметики и связанных с ней дисциплин. Каноническая форма может быть определена последующим образом. Пусть Q Лекция понятие субд. Функции субд - страница 8 – огромное количество объектов (запросов), и пусть существует понятие об эквивалентности этих объектов (а конкретно: запросы q1 и q2 эквивалентны и тогда только тогда, когда дают схожие результаты) Молвят, что подмножество C огромного количества Q является Лекция понятие субд. Функции субд - страница 8 подмножеством канонических форм для запросов из Q в смысле определенной выше эквивалентности и тогда только тогда, когда каждому объекту q из Q соответствует только один объект c из C. Тогда молвят Лекция понятие субд. Функции субд - страница 8, что объект с является канонической формой объекта q. Все "интересующие" характеристики, которыми обладает объект q, также присущи и объекту с. Потому, чтоб обосновать разные "интересующие" результаты, довольно изучить наименее массивное огромное количество объектов Лекция понятие субд. Функции субд - страница 8 C, а менее массивное огромное количество Q.

Чтоб конвертировать результаты стадии 1 в некую эквивалентную, но более эффективную форму, оптимизатор употребляет определенные и отлично известные правила преобразования, либо законы.


      1. ^ Стадия 3. Выбор возможных низкоуровневых Лекция понятие субд. Функции субд - страница 8 процедур


После преобразования внутренней формы запроса в более подходящую (каноническую) форму оптимизатор должен решить, как делать запрос, представленный в канонической форме. На этой стадии принимается во внимание наличие индексов и других путей Лекция понятие субд. Функции субд - страница 8 доступа, рассредотачивание хранимых значений данных, физическая кластеризация хранимых данных и т.п. Заметьте, что на стадиях 1 и 2 этим вопросам совершенно не уделялось внимания

Для каждой низкоуровневой операции оптимизатор обладает набором низкоуровневых Лекция понятие субд. Функции субд - страница 8 процедур реализации.

Замечание. С каждой процедурой также связана стоимостная формула, которая показывает "цена" выполнения процедуры (т.е. уровень требуемых издержек на ее выполнение). Обычно цена рассчитывается в контексте операций ввода-вывода с диска, но некие Лекция понятие субд. Функции субд - страница 8 системы учитывают также время использования микропроцессора и другие причины. Эти стоимостные формулы употребляются на стадии 4.

Как следует, дальше при помощи инфы из каталога о состоянии базы данных (имеющиеся индексы, катигоричные числа отношений Лекция понятие субд. Функции субд - страница 8 и т.п.) и данных о зависимостях, обрисованных выше, оптимизатор изберет одну либо несколько процедур-кандидатов для каждой низкоуровневой операции в запросе. Этот процесс обычно именуют выбором пути доступа.

      1. ^ Стадия 4. Генерация Лекция понятие субд. Функции субд - страница 8 планов вычисления запроса и выбор плана с меньшей ценой

На последней стадии процесса оптимизации конструируются потенциальные планы запросов, после этого следует выбор наилучшего (т.е. менее дорогого) плана выполнения запроса. Каждый план выполнения строится Лекция понятие субд. Функции субд - страница 8 как композиция набора процедур реализации, при всем этом каждой низкоуровневой операции в запросе соответствует одна процедура.

Для выбора плана с меньшей ценой нужен способ привязки цены к данному плану. В главном цена Лекция понятие субд. Функции субд - страница 8 плана – это просто сумма стоимостей отдельных процедур, которые применены для его выполнения. Таким макаром, работа оптимизатора сводится к вычислению стоимостных формул для каждой таковой процедуры. Неувязка заключается в том, что цена Лекция понятие субд. Функции субд - страница 8 выполнения процедуры находится в зависимости от размера дела (либо отношений), которое избранная процедура обрабатывает.


    1. Преобразование выражений




      1. Подборки и проекции

  1. Последовательность выборок данного дела может быть преобразована в одну (объединенную операцией AND) подборку этого Лекция понятие субд. Функции субд - страница 8 дела. К примеру, выражение

(A WHERE выборка_1) WHERE выборка_2

эквивалентно выражению

A WHERE выборка_1 AND выборка_2

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

(А [проекция_1]) [проекция_2]

эквивалентно Лекция понятие субд. Функции субд - страница 8 выражению

А [Проекция_2]

Естественно, чтоб 1-ое выражение имело смысл, каждый атрибут, применяемый в проекции_2, должен находиться и в проекции_1.

  1. Подборку проекции можно трансформировать в проекцию подборки. К примеру, выражение

(А [проекция]) WHERE подборка

эквивалентно выражению

(A WHERE Лекция понятие субд. Функции субд - страница 8 подборка) [проекция]

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


      1. ^ Распределительный закон

Молвят, что унарный оператор распределяется по бинарной операции О, если для всех А и В производится условие

F (А О В Лекция понятие субд. Функции субд - страница 8) º f (А) О f (В).

В реляционной алгебре операция подборки распределяется по операциям объединения, скрещения и вычитания. Операция подборки также распределяется по oneрации соединения, но только тогда, когда условие подборки состоит Лекция понятие субд. Функции субд - страница 8 (в самом сложном случае) из объединенных операцией AND 2-ух отдельных критерий подборки – по одному для каждого операнда операции соединения. Для рассматриваемого выше в этой главе примера сформулированное условие соблюдено (условие Лекция понятие субд. Функции субд - страница 8 подборки очень обычное и относится только к одному операнду), и можно использовать распределительный закон для подмены рассматриваемого в примере выражения его более действенным эквивалентом. Незапятнанный эффект этого закона заключается в том, что Лекция понятие субд. Функции субд - страница 8 можно делать "раннюю подборку". Выполнение ранешней подборки практически всегда себя оправдывает, потому что приводит к значительному уменьшению количества кортежей, которые необходимо рассматривать в последующей операции. Не считая того, ранешняя подборка может привести Лекция понятие субд. Функции субд - страница 8 к уменьшению количества кортежей и на выходе последующей операции.

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

(A JOIN В) [проекция]

эквивалентно выражению

(А Лекция понятие субд. Функции субд - страница 8 [А_проекция]) JOIN (В [В_проекция])

и тогда только тогда, когда огромное количество использованных в проекции атрибутов приравнивается объединению множеств атрибутов в А_проекции и В_проекции и включает атрибуты, по которым выполнено Лекция понятие субд. Функции субд - страница 8 соединение. Этот закон можно использовать для выполнения ранешних "проекций", которые обычно себя оправдывают по этим же причинам, что и операции подборки.


      1. ^ Коммутативность и ассоциативность

Законы коммутативности и ассоциативности – это еще два общих правила преобразования. Молвят Лекция понятие субд. Функции субд - страница 8, что бинарная операция О является коммутативной, если для всех А и В поистине равенство

А О В º В О А

К примеру, в обыкновенной математике операции умножения и сложения являются коммутативными, а операции Лекция понятие субд. Функции субд - страница 8 деления и вычитания – нет. В реляционной алгебре коммутативными являются операции объединения, скрещения и соединения, а операции вычитания и деления такими не являются.

Перейдем к ассоциативности. Принято считать, что бинарная операция О является Лекция понятие субд. Функции субд - страница 8 ассоциативной, если для всех А, В и С поистине равенство

А О (В О С) º (А О В) О С.

К примеру, в обыкновенной математике произведение и сложение – ассоциативные операции, деление и вычитание Лекция понятие субд. Функции субд - страница 8 – нет. В реляционной алгебре ассоциативными являются операции объединения, скрещения и соединения, а операции вычитания и деления такими не являются. Так, к примеру, если в запросе употребляется соединение 3-х отношений, А, В Лекция понятие субд. Функции субд - страница 8 и С, то из законов коммутативности и ассоциативности


      1. Идемпотентность

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

A О А = А.

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


      1. ^ Вычисляемые скалярные выражения

Предметом внедрения законов трансформации являются Лекция понятие субд. Функции субд - страница 8 не только лишь реляционные выражения. К примеру, уже было показано, что некие законы трансформации применимы и к арифметическим выражениям. Ниже приведен пример. Выражение

А * В + А * С

можно трансформировать в выражение

А * (В Лекция понятие субд. Функции субд - страница 8 + С)

вследствие того, что операция умножения "*" распределяется по операции сложения "+". Оптимизатор реляционных выражений должен владеть информацией о схожих преобразованиях, потому что он учитывает вычисляемые скалярные выражения в контексте операций EXTEND и Лекция понятие субд. Функции субд - страница 8 SUMMARIZE.

Молвят, что бинарная операция ^ О распределяется по бинарной операции О, если для всех А, В и С поистине равенство

A Ъ (B О C) = (A Ъ B) O ( A Ъ C )

(для приведенного выше Лекция понятие субд. Функции субд - страница 8 арифметического примера поменяйте Ъ на "*", а О на "+").


      1. ^ Условия

Перейдем к дискуссии критерий либо выражений, плодами которых могут быть правда либо ересь. Представим, что А и В – атрибуты 2-ух разных отношений, тогда условие

А Лекция понятие субд. Функции субд - страница 8>В AND В>3

(которое может быть частью запроса) полностью эквивалентно выражению

А > В AND В > 3 AND A > 3

и поэтому может быть преобразовано в это выражение.

Данная эквивалентность базируется на том, что операция ">" является Лекция понятие субд. Функции субд - страница 8 транзитивной. Заметьте, что выполнение подобного преобразования очень полезно, потому что позволяет системе сделать дополнительную подборку (при помощи условия "А > З") перед выполнением соединения "больше чем", требуемого условием "А > В".

Замечание Лекция понятие субд. Функции субд - страница 8. Этот прием реализован в разных коммерческих продуктах, включая систему DB2, в какой его именуют транзитивным замыканием предикатов. А вот другой пример. Условие

А > В OR (С = D AND Е < F)

можно конвертировать в условие

(A Лекция понятие субд. Функции субд - страница 8 > B OR С = D) AND (А > В OR Е < F)

вследствие того, что операция OR распределяется по операции AND. Этот пример показывает другой общий закон: "Хоть какое условие может быть преобразовано в эквивалентное Лекция понятие субд. Функции субд - страница 8 условие, называемое конъюнктивной обычной формой (КНФ)". КНФ-выражение имеет вид:

C1 AND C2 AND … AND Cn,

где С1, C2, ..., Cn – условия (именуемые частичная конъюнкция), в каких не употребляется операция AND Лекция понятие субд. Функции субд - страница 8. Преимущество КНФ заключается в том, что КНФ-выражение поистине, только если истинны все его частичные конъюнкции. Аналогично, КНФ выражение неверно, если ересь является результатом хотя бы одной частичной конъюнкции. Потому что операция Лекция понятие субд. Функции субд - страница 8 AND коммутативна (A AND В равно В AND А), то оптимизатор может вычислять отдельные частичные конъюнкции в любом порядке, а именно по возрастанию трудности (поначалу обыкновенные). И как найдена частичная конъюнкция, результатом которой Лекция понятие субд. Функции субд - страница 8 является ересь, весь процесс вычисления КНФ-выражения можно останавливать.

Более того, в среде параллельных вычислений может быть параллельное вычисление всех частичных конъюнкций. Снова же, как найдена 1-ая частичная конъюнкция, результатом которой Лекция понятие субд. Функции субд - страница 8 является ересь, весь процесс вычисления КНФ-выражения можно останавливать.


      1. ^ Семантические преобразования

Разглядим последующее выражение:

(Students JOIN Groups) [StName]

Данное соединение относится к соединениям типа внешниий-к-согласованному-потенциалъному-ключу. В этом соединении наружному ключу в отношении Лекция понятие субд. Функции субд - страница 8 Students ставится в соответствие возможный ключ дела Groups. Как следует, кортеж в отношении Students связан с определенным кортежем в отношении Groups. Таким макаром, из каждого кортежа в отношении Students Лекция понятие субд. Функции субд - страница 8 в общий итог поступает только значение атрибута StName. Другими словами, соединение можно не делать! Рассматриваемое выражение можно поменять выражением

Students [StName]

Преобразование, корректное в силу определенного условия целостности, именуют семантическим преобразованием, а оптимизацию Лекция понятие субд. Функции субд - страница 8, полученную в итоге схожих преобразований, – семантической оптимизацией. Семантическую оптимизацию можно найти как процесс преобразования запроса в другой, отменно хороший запрос, который, все же, дает итог, схожий результату начального запроса, благодаря тому что данные удовлетворяют Лекция понятие субд. Функции субд - страница 8 определенному условию целостности.

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


      1. ^ Статистики Лекция понятие субд. Функции субд - страница 8 базы данных

На стадиях 3 и 4 общего процесса оптимизации (они именуются стадиями "выбора пути доступа") употребляются так именуемые статистики базы данных, которые хранятся в каталоге.



lekciya-obshie-podhodi-k-obucheniyu-i-koncepcii-obucheniya-odarennih-detej.html
lekciya-ocenka-effektivnosti-lecheniya-zolotoj-standart.html
lekciya-opisaniya-bazovie-strukturi-i-etapi-analiza-sistem.html