- •Шехтман в. Е.
- •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. Модель клиент-сервер с бизнес-логикой на сервере субд (хранимые процедуры и триггеры) и частично на клиенте.
11.2. Организация индексов
11.2.1. Поиск в бд.
Файлы с прямым доступом, хэш-функции. Индексы.
11.2.2. Плотный индекс (индексно-прямые файлы).
Только первичные ключи. Ключ, № записи; записи упорядочены по значению ключа – можно применить бинарный поиск.
Важно не количество записей а количество блоков, которые надо просмотреть. Пусть длина записи – 128б, длина первичного ключа – 12б, количество записей – 100 000. Если длина блока – 1024б, то при 100 000 записей потребуется 3б, примем 4б. Длина записи индекса – 12+4, для этого требуется 100 000 / (1024/16) = 1563 блока. Максимальное количество обращений к диску – log21563=11, + 1 для доступа к записи данных.
Без индекса – 100000 / (1024 / 128) = 12500 блоков просмотреть в худшем случае. Для хранения индексов требуется выделить блоки в расчете на расширение данных.
При добавлении записи происходит запись в конец области данных. В индексной области необходимо записать новый элемент в конкретное место чтобы не нарушить упорядоченности. Эта область разбивается на блоки и при начальном заполнении каждый блок имеет резерв свободного места. После определения блока, в который надо занести элемнт, он копируется в ОЗУ, модифицируется, и записывается на диск. Резерв постоянно уменьшается. Когда он исчерпывается, надо либо перестроить всю индексную область, либо выделить область переполнения.
При удалении записи, область данных помечается как удаленная, элемент индекса уничтожается физически (т.е. элементы, следующие за ним, перемещаются на его место и блок записывается на диск).
11.2.3. Неплотный индекс (индексно-последовательные файлы).
Если хранить основные данные в упорядоченном виде, то это позволит существенно сэкономить на поиске:
Log212500 = 14 - только для упорядоченных данных. Но поддержание данных в упорядоченном виде – сложная операция. Неплотный индекс – только для упорядоченного файла (кластерный индекс по терминологии MS SQL).
Ключ первой записи блока, № блока с записью
(теперь не 100000 записей, а 12500 блоков – 2 байта, длина индексной записи 12+2, количество инд. записей в блоке 1024 / 14 =73, количество блоков для хранения индекса – 12500 / 73 = 172, количество чтений диска при поиске – log 2172 = 8 + 1 для чтения данных.)
Ввод новой записи – в упорядоченную основную область, в ней – место для расширения.
Удаление записи происходит физически, т.е. на ее место записываются последующие записи, индексная область в большинстве случаев не корректируется.
11.2.4. Сбалансированные деревья.
B-tree (balanced tree) – идея построения индекса для уже построенного индекса.
Если построить неплотный индекс, то индексную область можно рассматривать как область данных, для которой можно построить неплотный индекс и т. д. В результате получим дерево, каждый родительский блок которого связан с одинаковым количеством подчиненных блоков, количество которых равно количеству индексных записей, размещаемых в одном блоке. Количество обращений к диску при этом для поиска любой записи одинаково и равно количеству уровней в построенном дереве – сбалансированном дереве. Сбалансированное дерево потому, что путь от корня до любого листа в этом дереве одинаков по длине.
1 уровень – 12500 блоков
2 уровень – 172 блока неплотного индекса
3 уровень – 172 / 73 = 3 блока
4 уровень – 1 блок
Число уровней – 4, число обращений к диску тоже. Это всегда, а не максимум.
Удаление и добавление записей такие же как для случая неплотного индекса.