- •Общие сведения Сведения об эумк
- •Методические рекомендации по изучению дисциплины
- •Рабочая учебная программа
- •Учреждение образования
- •«Белорусский государственный университет
- •Информатики и радиоэлектроники»
- •Пояснительная записка
- •Содержание дисциплины
- •1. Название тем лекционных занятий, их содержание, объем в часах.
- •2 Перечень тем ипр их наименование и объем в часах
- •3 Перечень тем контрольных работ их наименование и объем в часах
- •4. Курсовая работа, ее характеристика
- •Перечень тем курсовых работ
- •5. Литература
- •5.1 Основная
- •5.2 Дополнительная
- •6. Перечень компьютерных программ, наглядных и других пособий, методических указаний и материалов и технических средств обучения
- •7. Учебно-методическая карта дисциплины
- •1.1.3. Способы организации знаний в базах знаний
- •1.1.4. Применение баз знаний
- •1.1.5. Виды моделей баз данных
- •2. Теория баз данных
- •2.1. История развития представлений о базах данных
- •2.1.1. Области применения вычислительной техники
- •2.1.2. Базы данных и информационные системы
- •2.1.3. История развития баз данных
- •2.1.4. Этапы развития баз данных
- •2.2. Основные термины и определения теории бд, виды бд и их отличия
- •2.2.1. Классификация бд
- •2.3. Реляционные бд, понятие сущности и связи
- •2.3.1. Общие определения
- •2.3.2. Факты о реляционной модели данных
- •2.3.3. Достоинства реляционной модели данных
- •2.3.4. Недостатки реляционной модели данных
- •2.3.5. Целостность бд
- •2.3.6. Отношения
- •2.3.7. Кортежи и отношения
- •2.3.8. Связи
- •2.3.9. Ключи отношений
- •2.3.10. Ссылочная целостность
- •2.3.11. Консистентность данных
- •2.4. Многоуровневая архитектура баз данных, понятие физического и логического уровней баз данных
- •2.4.1. Определения
- •2.4.2. Многоуровневая структура баз данных
- •Indexed р#
- •2.4.3. Постоянная и переменная длина записи
- •2.4.4. Способы представления данных
- •2.4.5. Простейший вариант – плоский файл
- •2.4.6. Факторизация по значениям поля
- •2.4.7. Индексирование по полям
- •2.4.8. Комбинация простых представлений
- •2.4.9. Использование цепочек указателей
- •2.4.10. Многосписочные структуры
- •2.4.11. Инвертированная организация
- •2.4.12. Иерархическая организация
- •2.4.14. Промежуточный итог
- •2.4.15. Методы индексирования
- •2.4.16. Индексирование по комбинации полей
- •2.4.17. Селективный индекс
- •2.4.18. Индексация по методу сжатия
- •2.4.19. Фронтальное сжатие
- •2.4.20. Сжатие окончания
- •2.4.21. Символьные указатели
- •2.4.23. Индексно-последовательная организация
- •2.4.24. Сбалансированные деревья
- •2.4.25. Ведение файла
- •2.4.26. Хэширование
- •2.5.2. Факторы эффективности хэширования
- •2.5.3. Размер участка памяти
- •2.5.4. Плотность заполнения
- •2.5.5. Алгоритмы хэширования
- •2.5.6. Размещение записей в области переполнения
- •2.5.7. Итог
- •2.6. Механизмы обработки и хранения данных в бд
- •2.6.1. Введение
- •2.6.2. Механизмы обработки и хранения данных в ms-sql 6.0-6.5
- •2.6.3. Механизмы обработки и хранения данных в ms-sql 7.0 и более поздних версиях
- •2.6.4. Метод доступа isam
- •2.6.5. Метод доспута MyIsam
- •2.6.6. Метод доступа vsam
- •2.6.7. Включение записей в *sam-файлы
- •2.6.8. Размещение индексов для *sam-файлов
- •2.6.9. Метод доступа InnoDb
- •InnoDb в MySql 5.1
- •2.7.3. Сетевые структуры
- •3.1.4. Стандарты разработки бд/субд
- •3.1.5. Sql и его стандарты
- •3.1.6. Использование методологии idef1x
- •3.1.7. Пример логической и физической схемы в ErWin
- •3.1.8. Минимальный набор стандартных таблиц
- •3.1.8. Итог
- •3.2. Средства автоматизированного проектирования бд
- •3.2.1. Введение
- •3.2.2. Case-технологии
- •3.2.3. Достоинства case-технологий
- •3.2.4. Промежуточные выводы и определения
- •3.2.5. Методологии структурного моделирования
- •3.2.6. Методология sadt (idef0)
- •3.2.7. Методологии информационного моделирования
- •3.2.8. Нотация Чена
- •3.2.9. Нотация Мартина
- •3.2.10. Нотация ide1x
- •3.2.11. Нотация Баркера
- •3.2.12. Язык информационного моделирования
- •3.2.13. Case-средства
- •3.2.14. Процесс создания модели бд в ErWin
- •3.2.15. Процесс создания модели бд в Sparx ea
- •3.2.16. Итог
- •3.3. Особенности проектирования бд на логическом и физическом уровнях
- •3.3.1. Введение
- •3.3.2. Модель бд
- •3.3.4. Банки данных
- •3.3.5. Модели данных
- •3.3.6. Этапы проектирования бд
- •3.3.7. Проектирование бд: внешний уровень
- •Изучение процессов преобразования входных данных в выходные.
- •3.3.8. Проектирование бд: инфологический уровень
- •3.3.9. Проектирование бд: даталогический уровень
- •3.3.10. Уровни sql
- •3.3.11. Проектирование бд: физический уровень
- •3.4.3. Требования нормализации
- •3.4.4. Примеры аномалий
- •3.4.5. Нормальные формы
- •3.4.6. Зависимости
- •3.4.6. Первая нормальная форма
- •3.4.7. Вторая нормальная форма
- •3.4.8. Третья нормальная форма
- •3.4.9. Нормальная форма Бойса-Кодда
- •3.4.10. Четвёртая нормальная форма
- •3.4.11. Пятая нормальная форма
- •3.4.12. Доменно-ключевая нормальная форма
- •3.4.13. Ещё раз, кратко, все нормальные формы
- •3.4.14. Ещё раз, кратко, в ErWin
- •3.4.15. Обратное проектирование бд
- •3.4.16. Итог
- •3.5. Повышение качества бд на стадии проектирования
- •3.5.1. Памятки разработчикам бд
- •3.5.2. Показатели качества бд
- •Практическая часть
- •Указания по выбору варианта
- •Индивидуальные практические работы Индивидуальная практическая работа № 1 Общие сведения
- •Практическая часть
- •Указания по выбору варианта
- •Индивидуальная практическая работа № 2 Общие сведения
- •Указания по выбору варианта
- •Практическая часть
2.4.14. Промежуточный итог
Наш обзор некоторых структур хранения, допускаемых интерфейсом хранимых записей, завершён.
В заключение необходимо заметить, что не существует такого понятия, как «наилучшая» структура хранения.
Что является наилучшей структурой хранения, зависит от того, что важно для конкретной решаемой задачи.
Факторы, которые следует принимать во внимание, включают эффективность выборки, затраты на осуществление изменений, объём доступного пространства памяти, простоту реорганизации БД и требуемую частоту такой реорганизации, проблемы восстановления и т.д.
Чтобы ещё раз охватить взглядом то, что мы уже рассмотрели, и что ещё предстоит рассмотреть, посмотрим на следующий рисунок.
Рисунок 2.4.14.1 – Виды файлов БД
2.4.15. Методы индексирования
Интерфейс физических записей является интерфейсом между методом доступа и физической базой данных (файлом).
Единицей передачи через этот интерфейс является экземпляр физической записи.
Физическое следование записей является важным средством установления порядка экземпляров хранимых записей в хранимом файле за счёт:
физического порядка экземпляров хранимых записей в пределах одного блока;
физического порядка блоков на носителе.
Это имеет следующее значение для разработки индексов.
Во-первых, появляется возможность создавать т.н. «неплотные индексы». Их идея состоит в том, что индексируемый файл разбивается на группы, где каждая группа содержит несколько экземпляров хранимых записей.
При этом соблюдаются следующие условия:
для любых двух групп справедливо, что все экземпляры хранимых записей одной группы предшествуют всем экземплярам хранимых записей в другой группе (в отношении порядка, установленном в данном файле);
в пределах одной группы упорядочение файла определяется физическим следованием записей.
На практике в качестве группы может быть выбран один блок, одна дорожка или любая другая подходящая единица памяти.
Индекс содержит по одному элементу на группу, где указаны, как правило, наибольшее значение индексируемого поля в пределах группы и указатель на начало группы.
Последовательность групп представлена последовательностью элементов в индексе.
Термин «неплотный» (неплотный индекс) отражает тот факт, что индекс не содержит элементов для каждого экземпляра хранимой записи в индексируемом файле.
Вследствие этого каждый экземпляр хранимой записи должен содержать индексируемое поле (в противоположность случаю с плотным индексом).
Алгоритм поиска здесь таков:
Поиск по индексу ключа (первый найденный ключ ≥ требуемого ключа).
Переход на найденную область памяти.
Физически последовательный просмотр области памяти.
Последовательного просмотра хотелось бы избежать.
Наличие физического упорядочения позволяет строить многоуровневые индексы (древовидные индексы).
Причиной создания всякого индекса, прежде всего, является стремление избежать последовательного просмотра индексируемого файла.
Однако всё ещё необходимо последовательно просматривать если и не сам файл, то, по крайней мере, индекс.
Если индекс становится очень большим, возникает самостоятельная проблема эффективности этого просмотра.
Решение проблемы – создать «индекс для индекса».
Простой пример такого индекса изображён на следующем рисунке:
Рисунок 2.4.15.1 – Двухуровневый индекс
На этом рисунке индексируемый файл разделён на группы записей (их, например, можно физически привязать к дорожке на диске, если операционная система позволяет нам управлять расположением файлов на столь низком уровне).
Индекс групп в свою очередь разделён на подгруппы, каждая из которых состоит из некоторого числа элементов.
Вообще говоря, многоуровневый индекс может содержать произвольное число уровней, где каждый индекс является неплотным индексом следующего уровня.
Если бы мы хотели довести этот метод до логического завершения, то верхний уровень должен был бы состоять из единственного элемента (классическое «дерево»), однако на практике такой верхний уровень не делают (т.о. мы получаем т.н. «лес деревьев»).
Итак, уже рассмотренные нами «неплотное индексирование» и «многоуровневое индексирование», могут быть использованы на уровне интерфейса физических записей (для поиска непосредственно в физических файлах на диске, что реализуется методом доступа).
Теоретически их можно было бы также применять к интерфейсу хранимых записей (для того, чтобы СУБД было проще и быстрее искать «элементы таблиц»), но такое использование малополезно, так как эти методы сильно зависят от концепции физического следования записей.
Напротив, следующие методы могут быть использованы в индексах на любом уровне:
индексирование по комбинации полей;
селективный индекс;
индексирование по методу сжатия;
индексирование символическими указателями.
Рассмотрим их…