Как на самом деле выполняется оператор select

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

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

Схематично работу оптимизатора можно представить в виде последовательности нескольких шагов:

Шаг 1 (Синтаксический анализ). Поступивший запрос подвергается синтаксическому анализу. На этом шаге определяется, правильно ли вообще (с точки зрения синтаксиса SQL) сформулирован запрос. В ходе синтаксического анализа вырабатывается некоторое внутренне представление запроса, используемое на последующих шагах.

Шаг 2 (Преобразование в каноническую форму). Запрос во внутреннем представлении подвергается преобразованию в некоторую каноническую форму. При преобразовании к канонической форме используются как синтаксические, так и семантические преобразования. Синтаксические преобразования (например, приведения логических выражений к конъюнктивной или дизъюнктивной нормальной форме, замена выражений "x AND NOT x" на "FALSE", и т.п.) позволяют получить новое внутренне представление запроса, синтаксически эквивалентное исходному, но стандартное в некотором смысле. Семантические преобразования используют дополнительные знания, которыми владеет система, например, ограничения целостности. В результате семантических преобразований получается запрос, синтаксически не эквивалентный исходному, но дающий тот же самый результат.

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

Шаг 4. (Выполнение плана запроса). На этом шаге план, выбранный на предыдущем шаге, передается на реальное выполнение.

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

Реализация реляционной алгебры средствами оператора SELECT (Реляционная полнота SQL)

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

Оператор декартового произведения A TIMES B

Оператор SQL:

SELECT * FROM A, B;

или (по столбцу)

SELECT * FROM A JOIN B ON A.id_city = B.id_city

Оператор проекции: A[X,Y,…Z]

Оператор SQL:

SELECT DISTINCT X, Y, …, Z FROM A;

Оператор выборки: A WHERE c

Оператор SQL:

SELECT * FROM A WHERE c;

Оператор объединения: A UNION B

Оператор SQL:

SELECT * FROM A UNION SELECT * FROM B;

Оператор вычитания: A MINUS B

Оператор SQL:

SELECT * FROM A EXCEPT SELECT * FROM B

Реляционный оператор переименования RENAME выражается при помощи ключевого слова AS в списке отбираемых полей оператора SELECT. Таким образом, язык SQL является реляционно-полным.

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

Оператор соединения: (A TIMES B) WHERE c

Оператор SQL:

SELECT * FROM A, B WHERE c;

или

SELECT * FROM A CROSS JOIN B WHERE c;

Оператор пересечения: A INTERSECT B

Оператор SQL:

SELECT * FROM a WHERE EXISTS (SELECT * FROM b)

Оператор деления: A(X, Y) DEVIDEBY B(Y)

Оператор SQL:

SELECT DISTINCT A.zap FROM A WHERE NOT EXISTS (SELECT * FROM B WHERE NOT EXISTS (SELECT * FROM A A1 WHERE A1.fam = A.fam AND A1.zap =

Объекты и концепции базы данных

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

6.4.1 Таблицы (Tables)

6.4.2 Столбцы (Columns)

6.4.3 Типы данных (Data types)

6.4.4 Домены (Domains)

6.4.5 Справочные ограничения целостности (Referential integrity constraints)

6.4.6 Индексы (Indexes)

6.4.7 Виды (Views)

6.4.8. Сохраненные процедуры (Stored procedures)

6.4.9 Триггеры (Triggers)

6.4.10 Генераторы (Generators)

6.4.11 Защита (Security)

Таблицы (Tables)

Реляционные базы данных хранят все данные в таблицах. Таблица это структура, состоящая из множества неупорядоченных горизонтальных строк (rows), каждая из которых содержит одинаковое количество вертикальных столбцов (colums). Пересечение отдельной строки и столбца называеися полем (field), которое содержит специфическую информацию. Многие принципы работы реляционной базы данных взяты из определений отношений (relations) между таблицами.

InterBase хранит информацию о метаданных в специальных таблицах, которые называются системными таблицами (system tables). Системные таблицы имеют специальные столбцы, которые содержат информацию о типе метаданных в этой таблице. Имена всех системных таблиц начинаются с "RDB$". Пример системной таблицы - RDB$RELATIONS, которая содержит информацию о каждой таблице в базе данных.

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

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

Столбцы (Columns)

Создание таблицы главным образом подразумевает определение столбцов таблицы. Главные атрибуты столбца включают:

· Имя столбца;

· Тип данных столбца или домен на котором он базируется;

· Может или нет поле столбца принимать значение NULL;

· Факультативно справочные ограничения целостности (referential integrity constraints).

Типы данных (Data types)

Данные сохранены в определенном формате, который называется типом данных (data type). Типы данных могут быть классифицированы по четырем категориям: числовые (numeric), символьные (character), даты (date) и BLOB. Числовые данные включают в себя все числа, начиная с целых вплоть до чисел двойной точности с плавающей точкой. Символьные данные содержат строки текста. Даты используются для хранения дат и времени.

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

Тип данных BLOB

InterBase поддерживает такой тип данных, как большие бинарные объекты (binary large object - BLOB), которые могут хранить данные неограниченного размера. Тип BLOB это расширение стандартной реляционной модели, которая обычно обеспечивает только типы данных фиксированной длины.

Тип данных BLOB аналогичен последовательному файлу (flat file), BLOB данные могут быть сохранены в любом формате (к примеру, бинарном или ASCII). BLOB, однако, это не отдельный файл. BLOB данные хранятся в базе данных наряду со всеми другими данными. Так как BLOB столбцы часто содержат большие и переменные объемы данных, BLOB столбцы хранятся в отдельных сегментах.

InterBase не поддерживает непосредственно преобразование BLOB данных в другие форматы, но на некоторых платформах, BLOB фильтры могут транслировать BLOB данные из одного формата в другой.

Домены (Domains)

В добавление к явному определению типа данных столбцов, InterBase обеспечивает глобальные определения столбцов или домены (domains), на которых могут базироваться определения столбцов. Домен содержит информацию о тип данных, устанавливает атрибуты и ограничения целостности столбцов. В последующем при создании таблиц возможно использовать домены для определения столбцов.