- •Шехтман в. Е.
- •1. Базы данных и модели данных
- •1.1. Введение.
- •1.2. Файлы операционной системы
- •1.3. Пример базы данных.
- •1.4. Иерархическая модель данных
- •1.5. Сетевая модель данных
- •1.6. Инвертированные списки.
- •2. Введение в реляционную модель данных.
- •1.7. Реляционная модель данных
- •3. Реляционная алгебра
- •3.1. Теоретико-множественные операции.
- •3.2. Специальные операции ra
- •4. Нормализация данных
- •4.1. Полная декомпозиция.
- •Магазин товар ндс
- •Товар ндс
- •Магазин ндс
- •Товар ндс
- •Магазин товар ндс
- •4.2. Проблема дублирования данных.
- •1 Глобус 33-33-33
- •2 Глобус 33-33-33
- •4 Океан 77-77-77
- •4.3. Висячие записи.
- •Поставщик Тел
- •4.4. Проблемы, возникающие из-за неудачной структуры данных.
- •4.5. Пятая нормальная форма (5нф).
- •4.6. Функциональная зависимость.
- •4.7. Связь между фз и полной декомпозицией отношения.
- •4.8. Первая нормальная форма (1нф).
- •4.9. Вторая нормальная форма (2нф).
- •4.10. Третья нормальная форма (3нф).
- •4.11. Нормальная форма Бойса-Кодда (нфбк).
- •4.12. Многозначная зависимость.
- •4.13. Четвертая нормальная форма (4нф).
- •4.14. Пример нормализации.
- •4.15. Резюме. Нормальные формы.
- •5. Инфологическое моделирование.
- •5.1. Сущность и набор сущностей
- •5.2. Связи между сущностями.
- •5.3. Рекурсивная связь. Роли.
- •5.4. Множественные связи.
- •5.5. Суперсущности и производные сущности
- •5.6. Слабые наборы сущностей
- •5.7. Борьба с избыточнотью
- •5.8. Преобразование инфологической модели в физическую модель.
- •5.9. Пример инфологического моделирования.
- •6. Язык sql
- •6.1. История sql.
- •6.2. Структура sql.
- •6.3. Язык запросов
- •6.4. Простые запросы на выборку данных.
- •6.5. Агрегатные (групповые) функции.
- •6.6. Вложенные запросы
- •6.7. Внешние объединения
- •6.8. Изменение данных
- •Insert into r1 (o, fio, d) values (5, ‘Иванов’, ’бд’)
- •7. Представления.
- •8. Определение схемы базы данных и ограничений целостности
- •9. Транзакции
- •9.1. Свойства транзакций
- •9.2. Надежное хранение данных
- •9.3. Параллельное выполнение транзакций
- •9.3.1. Коллизия “пропавшие изменения” - lost update problem
- •9.3.2. Коллизия “промежуточные данные” - dirty read
- •9.3.3. Коллизия “Несогласованные данные” - unrepeatable read, inconsistent analysis
- •9.3.4. Коллизия “фантом” - phantom
- •9.4. Уровни изолированности
- •9.5. Тупики
- •10. Ограничение прав доступа в целях обеспечения безопасности
- •11. Физическая организация баз данных
- •11.1. Организация размещения данных.
- •11.2. Организация индексов
- •11.2.1. Поиск в бд.
- •11.2.2. Плотный индекс (индексно-прямые файлы).
- •11.2.3. Неплотный индекс (индексно-последовательные файлы).
- •11.2.4. Сбалансированные деревья.
- •11.2.5. Инвертированные списки.
- •12. Архитектура субд. Методы оптимизации запросов.
- •Логические преобразования запросов.
- •Преобразования запросов с изменением порядка реляционных операций.
- •13. Аналитические системы.
- •Анализ данных.
- •Хранилища данных
- •Типы ошибок
- •Способы реализации olap.
- •Требования к средствам реализации систем оперативной и аналитической обработки данных
- •Многомерная модель данных.
- •Разработка данных
- •14. Загружаемые процедуры.
- •In pr double precision)
- •If eof then leave Cl end if;
- •Insert into providers(code, name)
- •Values (nr.Codec, ‘*** новый поставщик ***’);
- •15.4. Модель сервера приложений (трёхзвенная архитектура, “тонкий клиент”)
- •Список литературы
- •15. Модели совместного доступа к бд
- •15.1. Файл-серверная модель.
- •15.2. Модель клиент-сервер с бизнес-логикой на клиенте.
- •15.3. Модель клиент-сервер с бизнес-логикой на сервере субд (хранимые процедуры и триггеры) и частично на клиенте.
Логические преобразования запросов.
Прежде всего это относится к преобразованию предикатов, входящих в условие выборки. Предикаты, содержанию операции сравнения простых значений. Такой предикат имеет вид арифметическое выражение ОС арифметическое выражение, где ОС — операция сравнения, а арифметические выражения левой и правой частей в общем случае содержат имена полей отношений и константы (в языке SQL среди констант могут встречаться и имена переменных объемлющей программы, значения которых становятся известными только при реальном выполнении запроса). Канонические представления могут быть различными для предикатов разных типов. Если предикат включает только одно имя поля, то его каноническое представление может, например, иметь вид имя поля ОС константное арифметическое выражение (эта форма предиката — простой предикат селекции -очень полезна при выполнении следующего этапа оптимизации). Если начальное представление предиката имеет вид
(n+12)*R.B f 100
здесь n - переменная языка, R.B — имя столбца В отношения R, f - допустимая операция сравнения.
Каноническим представлением такого предиката может быть
(n+12)*R.B f 100 -> R.B f 100/(n+12)
В этом случае мы один раз для заданного значения переменной п вычисляем выражение в скобках и правую часть операции сравнения 100/(n +12), а потом каждую строку можем сравнивать с полученным значением.
Если предикат включает в точности два имени поля разных отношений (или двух разных вхождений одного отношения), то его каноническое представление может иметь вид имя поля ОС арифметическое выражение, где арифметическое выражение в правой части включает только константы и второе имя поля
2*(R1.A)-n*(R2.B) f m -> R1.A f (m+n*(R2.B))/12
общем случае желательно приведение предикат к каноническому представлению вида
арифметическое выражение f константное арифметическое выражение
где выражения правой и левой частей также приведены к каноническому представлению. В дальнейшем можно произвести поиск общих арифметических выражений в разных предикатах запроса. Это важно, т. к. при выполнении запроса вычисление арифметических выражений будет производится при выборке каждого очередного кортежа, то есть потенциально много раз.
При приведении предикатов к каноническому представлению можно вычислять константные выражения и избавляться от логических отрицаний.
При приведении логического условия к каноническому виду можно производить поиск общих предикатов (они могут существовать изначально, могут появиться после приведения предикатов к каноническому виду, могут появиться в процессе нормализации логического условия) и упрощать логические выражение за счет, например, выявления конъюнкции взаимно противоречащих предикатов.
Преобразования запросов с изменением порядка реляционных операций.
R1 NATURAL JOIN R2 WHERE R1.A … a AND R2.B … b ->
Сначала выполняются выборки по условиям в обоих отношениях а потом соединение.
Приведение запросов с вложенными подзапросами к запросам с соединениями. Основным отличием языка SQL от языка реляционной алгебры является возможность использовать в логическом условии выборки предикаты, содержащие вложенные подзапросы. Глубина вложенности не ограничиваема языком, то есть, вообще говоря, может быть произвольной. Предикаты с вложенными подзапросами при наличии общего синтаксиса могут обладать весьма различной семантикой. Единственным общим для всех возможных семантик вложенных подзапросов алгоритмом выполнения запроса является исчисление вложенного подзапроса всякий раз при вычислении значения предиката. Поэтому естественно стремиться к такому преобразованию запроса, содержащего предикаты со вложенными подзапросами, которое сделает семантику подзапроса более явной, предоставив тем самым в дальнейшем оптимизатору возможность выбрать способ выполнения запроса, наиболее точно соответствующий семантике подзапроса.
Каноническим представлением запроса на n отношениях называется запрос, содержащий n-1 предикатов соединения и не содержащий предикатов с вложенными подзапросами. Фактически, каноническая форма – это алгебраическое представление запроса.
Если есть подзапросы, то обычно единственный способ их выполнить – выполнять вложенный подзапрос всякий раз, когда вычисляется значение предиката. В частных случаях этого можно избежать и оптимизатор стремится этому.
Примеры:
SELECT R1.A FROM R1 WHERE R1.B IN (SELECT R2.B FROM R2 WHERE R1.C=R2.D)
->
SELECT R1.A FROM R1, R2 WHERE R1.B=R2.B AND R1.C=R2.D
SELECT R1.A FROM R1 WHERE R1.K=(SELECT AVG(R2.B) FROM R2 WHERE R1.C=R2.D)
->
R3 = (SELECT R2.D, AVG(R2.B) AS L FROM R2 GROUP BY R2.D)
SELECT R1.A FROM R1, R3 WHERE R1.C=R3.D AND R1.K=R3.L
Методы семантической оптимизации запросов
Если запрос над представлением, (а представление – само запрос), то выполняться должно 2 запроса: сначала запрос, на котором основано представление, а потом сам запрос над представлением. Но оптимизация сливает их в один запрос.
Учет ограничений целостности. Мы можем искать значение поля, которое не входит в набор возможных значений. Тогда ясно, что запрос пуст и без выполнения!
Иногда встречаются случаи, когда оптимизатор не способен выполнить оптимизацию запроса. Это может быть обусловлено его сложностью.
Пример. Пусть имеется две таблицы:
GOODS ((IDENT, INTEGER), (NAME, CHAR(50)), (PRICE, CURRENCY),…)
и
OPERATIONS ( (IDENT,CHAR(15), (DISCOUNT, FLOAT), (QUANT,INTEGER), (DAT,DATE),…).
Таблица GOODS – множество товаров на складе, таблица OPERATIONS – строки счетов-фактур, соответствующих операций продажи товаров. При этом поле OPERATIONS.IDENT – строкового типа, но хранит идентификатор товара, соответствующий GOODS.IDENT.
Тогда оптимизатор СУБД Interbase не справится с запросом (он будет выполнен, но неоптимально):
SELECT GOODS.PRICE, GOODS.NAME, OPERATIONS.QUANT, OPERATIONS.DISCOUNT
FROM OPERATIONS LEFT JOIN GOODS
ON OPERATIONS.IDENT = CAST(GOODS.IDENT AS CHAR(15) )
WHERE OPERATIONS.DAT>=’01.01.2003’ AND OPERATIONS.DAT<=’31.03.2003’
Но тот же оптимизатор прекрасно справится с таким запросом:
SELECT GOODS.PRICE, GOODS.NAME, OPERATIONS.QUANT, OPERATIONS.DISCOUNT
FROM OPERATIONS LEFT JOIN GOODS
ON CAST(OPERATIONS.IDENT AS INTEGER) = GOODS.IDENT
WHERE OPERATIONS.DAT>=’01.01.2003’ AND OPERATIONS.DAT<=’31.03.2003’
Разница во времени (в таблицах GOODS и OPERATIONS около 100 000 записей) может составить 20 раз! Разумеется, эта конкретная проблема обусловлена хранением идентификатора товара, который по своей природе целого типа, в поле строкового типа.
После оптимизации запрос приводится к непроцедурному виду (Что? а не Как?). Далее строятся планы выполнения запросов. Они основаны на статистическом анализе объемов данных. Для каждого из них производятся стоимостные оценки. Оценка планов выполнения запроса основана на анализе текущих объемов данных, хранящихся в отношениях БД, и на статистическом анализе хранимой информации. В большинстве СУБД ведется учет диапазона значений отдельного столбца с указанием процентного содержания для каждого диапазона. Поэтому при построении плана запроса СУБД может оценить объем промежуточных отношений и построить план таким образом, чтобы на наиболее ранних этапах выполнения запроса минимизировать количество строк, включаемых в промежуточные отношения.
Кроме ядра СУБД каждый поставщик обеспечивает специальные инструментальные средства, облегчающие администрирование БД и разработку новых проектов БД и пользовательских приложений для данного сервера. В последнее время практически все утилиты и инструментальные средства имеют развитый графический интерфейс.
