Трехуровневая система организации БД

В 1978 году учеными была принята трехуровневая система организации данных, предложенная Национальным Институтом стандартизации – ANSI (American National Standards Institute) и Комитетом по планированию выпуска стандартов и технических условий – SPARC Соединенных штатов Америки. В соответствии с принятой концепцией предлагается выделять три уровня абстракции представления данных: внешний, концептуальный и внутренний.

Основное внимание в этом подходе сконцентрировано на необходимости воплощения независимости каждого уровня для изоляции программ от особенностей представления данных на более низком уровне

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

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

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

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

Прохождение запроса в СУБД. Этапы обработки запроса.
Оптимизация запросов к СУБД

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

Язык SQL является декларативным языком. В его командах отсутствует информация о том, как выполнить запрос, какие методы доступа к данным использовать. А почти каждая команда SQL из подмножества языка манипулирования данными (DML) может быть выполнена разными способами. Рассмотрим следующий запрос:

Пример. Список сотрудников 4-го отдела не старше 25 лет с «чистой» зарплатой не менее 30000 рублей" («чистой» называется зарплата после уплаты подоходного налога, в настоящее время – 13%).

SELECT *FROM EmpWHERE depNo=4 AND born> '1985/01/01'AND salary*0.87> =30000;

В этом запросе к таблице Emp (Сотрудники) указаны условия на поля depNo (Номер отдела), born (Дата рождения) и salary (Зарплата). Если по этим полям есть индексы, то способы выполнения этого запроса могут быть такими:

1. Найти по индексу INDEX(depNo) записи, удовлетворяющие первому условию, и проверить для найденных записей второе условие.

2. Найти по индексу INDEX(born) записи, удовлетворяющие второму усло-вию, и проверить для найденных записей первое условие.

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

Индексом по полю salary система воспользоваться не может, т.к. это поле находится внутри выражения.

Цель СУБД – выполнить запрос, причём сделать это как можно более эффективным способом. Итак, под оптимизацией понимается построение квазиоптимального процедурного плана выполнения декларативного запроса.

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

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

Обработка запроса, поступившего в РСУБД и представленного на декларативном языке запросов, состоит из этапов (фаз), представленных на рис. 7.1.

Рис. 7.1. Последовательность выполнения запросов в реляционных СУБД

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

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

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

(CHECK (salary> 9500 AND salary< 80000),

то система к запросу из примера 7.1 могла бы добавить эти условия в часть WHERE, чтобы иметь возможность использовать индекс по полю salary.

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

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

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

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

Наконец, на последнем, пятом этапе обработки запроса происходит его реальное выполнение в соответствии с процедурным планом выполнения за-проса. Результат помещается в специальную область ОП (т.н. курсор).