- •Общие сведения Сведения об эумк
- •Методические рекомендации по изучению дисциплины
- •Рабочая учебная программа
- •Учреждение образования
- •«Белорусский государственный университет
- •Информатики и радиоэлектроники»
- •Пояснительная записка
- •Содержание дисциплины
- •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.10. Многосписочные структуры
Вариант представления, изображенный на предыдущем рисунке (использующий цепочки указателей), является простым примером многосписочной организации.
Здесь мы соединили вместе всех поставщиков одного и того же города. Другими словами, для каждого города мы составили список соответствующих поставщиков.
Таким же способом (с помощью дополнительных указателей) можно организовать список поставщиков, имеющих одинаковое значение поля статуса. В общем случае многосписочная организация может содержать произвольное число списков.
2.4.11. Инвертированная организация
Вернёмся к рассмотрению вторичного индексирования. Так же, как это было сделано для списков в многосписочной организации, можно обеспечить произвольное число вторичных индексов. В предельном случае мы имеем ситуацию, иллюстрируемую следующим рисунком, где предусмотрен индекс по каждому вторичному полю (т.н. «инвертированную организацию»).
Рисунок 2.4.11.1 – Инвертированная организация
Однако, несмотря на то, что инвертированная организация обеспечивает хорошую производительность для запросов о всех поставщиках, обладающих определенным значением атрибута (например, значением статуса, равным 20), ответ на запрос о всех атрибутах конкретного поставщика потребует продолжительного времени.
Поэтому на практике часто используется компромиссный вариант, предусматривающий обычную организацию совместно со вторичными индексами по тем полям, которые являются важными с точки зрения администратора базы данных.
Такой вариант является одной из наиболее общих структур хранения, используемых в настоящее время.
2.4.12. Иерархическая организация
Другим вариантом представления является иерархическая организация, иллюстрируемая следующим рисунком:
Рисунок 2.4.12.1 – Иерархическая организация
Здесь также есть один хранимый файл, содержащий три экземпляра (иерархической) хранимой записи, по одному экземпляру на город.
Каждый экземпляр хранимой записи содержит список произвольной длины, каждый элемент которого содержит номер поставщика, его имя и статус.
Здесь мы осуществляем факторизацию (группировку) по значениям поля «город», но на этот раз для представления связи между городом и расположенными в нём поставщиками данные о городе и всех таких поставщиках размещены в одном экземпляре хранимой записи (вместо использования указателей).
2.4.13. Хэш-аресация
Последним вариантом представления, который мы будем рассматривать, является хэш-адресация.
Основная идея хэш-адресации состоит в том, что каждый экземпляр хранимой записи размещается в базе данных по адресу, который может быть вычислен как некоторая функция (хэш-функция) от значения некоторого поля в этом экземпляре записи – обычно значения первичного ключа.
Подробнее о хэш-функциях – в конце этой темы.
Таким образом, чтобы первоначально сохранить экземпляр записи, СУБД вычисляет адрес хранимой записи и заставляет метод доступа разместить этот экземпляр в соответствующей позиции; при поиске экземпляра СУБД выполняет те же самые вычисления и запрашивает метод доступа для вызова экземпляра из вычисленной позиции.
Преимущество такой организации заключается в очень быстром прямом доступе на основе значений хэшируемого поля.
Рассмотрим пример хэш-адресации.
Предположим, что значениями S# являются S100, S200, S300, S400, S500 (вместо S1, S2, S3, S4, S5).
Рассмотрим хэш-функцию:
АдресХранимойЗаписи = S# % 13
(остаток от деления значения S# на 13)
Это простой пример общего класса хэш-функций – «деление/остаток» (делителем обычно является простое число).
Адресами хранимых записей в данном случае будут 9, 5, 1, 10, 6 соответственно.
Рисунок 2.4.13.1 – Хэш-адресация
Теоретически возможно использовать числовое значение первичного ключа в качестве адреса хранимой записи.
Однако этот вариант неприемлем из-за того, что диапазон значений первичного ключа обычно много шире диапазона доступных адресов хранимых записей.
Например, предположим, что номера поставщиков являются трёхзначными, как это было определено ранее.
Теоретически это допускает 1000 различных поставщиков, в то время как на практике может существовать, допустим, 10.
Чтобы избежать колоссальных издержек памяти, в идеальном случае необходимо, чтобы хэш-функция переводила любое значение из диапазона 0-999 в значение из диапазона 0-9.
Чтобы учесть возможное расширение в будущем диапазон обычно увеличивают на 20%.
Так, в только что рассмотренном примере мы выбрали функцию, которая генерирует значения в диапазоне 0-12, а не в диапазоне 0-9.
Этот пример также иллюстрирует недостаток хэш-адресации: последовательность экземпляров хранимых записей в пределах хранимого файла не совпадает с последовательностью, определяемой первичным ключом (кроме того, могут существовать промежутки произвольного размера между следующими друг за другом экземплярами).
Фактически хранимый файл с хэш-адресацией обычно рассматривается как неупорядоченный.
Другим недостатком хэш-адресации является возможность коллизий, когда двум различным экземплярам хранимых записей назначается один и тот же адрес.
Например, предположим, что в наш пример включён поставщик со значением номера равным S1400.
Хранимые записи этого поставщика и поставщика S100 будут иметь, в соответствии с использованной нами хэш-функцией, одинаковый адрес хранимой записи – 9.
Выходом из подобного положения является усложнение хэш-функции с целью управления такими ситуациями.
Одна из возможностей заключается в использовании адреса хранимой записи, выработанного хэш-функцией, в качестве начальной точки для последовательного просмотра.
В этом случае для того, чтобы добавить запись о поставщике S1400 осуществляется поиск свободного места вперёд, начиная с позиции, определяемой адресом хранимой записи – 9.
В данном случае запись о новом поставщике будет размещена по адресу 11. При последующей выборке поставщика S1400 выполняются аналогичные действия.