- •Общие сведения Сведения об эумк
- •Методические рекомендации по изучению дисциплины
- •Рабочая учебная программа
- •Учреждение образования
- •«Белорусский государственный университет
- •Информатики и радиоэлектроники»
- •Пояснительная записка
- •Содержание дисциплины
- •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.20. Сжатие окончания
Вторым методом сжатия является сжатие окончания.
Один способ использования сжатия окончания для данного примера заключается в устранении всех завершающих пробелов (опять-таки посредством их замещения соответствующим счётчиком).
Дальнейшее сжатие достигается за счёт пропуска всех знаков справа от тех знаков, которые отличают данный элемент от смежных с ним элементов.
Применение этого метода даёт:
0 – 7 – ROBERTO
6 – 2 – SO
7 – 1 –Т
3 –1 – I
где вторая цифра представляет собой счётчик количества записанных знаков.
Заметим, однако, что в данном случае имеет место потеря информации из индекса, т.е. после распаковки элементы будут иметь вид:
ROBERTO?????
ROBERTSO????
ROBERTST????
ROBI????????
где ? представляет собой неизвестный знак.
Это допустимо, только если эти значения записаны где-либо в полностью декодированном виде (в данном случае в индексируемом файле).
2.4.21. Символьные указатели
До сих пор в наших примерах предполагалось, что все указатели представляют собой адреса хранимых записей.
Однако адреса хранимых записей могут измениться при реорганизации хранимого файла. Поэтому, если хранимый файл реорганизуется, все файлы, указывающие на него, в частности все индексы, должны быть изменены, с тем чтобы содержать скорректированные адреса хранимых записей.
Все это может превратиться в большую проблему с производительностью и алгоритмической сложностью.
Для устранения этих неприятностей все указатели могут быть заменены, например, соответствующими значениями первичных ключей, за исключением тех указателей (если таковые есть), которые используются методом доступа в качестве основного механизма упорядочения файла.
Если метод доступа упорядочивает хранимый файл с помощью индекса по некоторому полю, то недостаточно, чтобы индекс содержал только значения из этого поля. Нужны ещё и вполне «числовые» параметры (файл, смещение и т.п.), т.к. иначе использование индекса не будет иметь смысла.
В общем случае, использование символьных указателей в любом случае требует некоторого механизма позволяющего «понять по символьному указателю, где лежит то, на что он указывает».
Аналогом символьных указателей на более высоких уровнях БД является организация связей на основе миграции ключей. Рассмотрим разницу «числовых» и «символьных» указателей на рисунке.
Рисунок 2.4.22.1 – Использование символьных указателей
2.4.23. Индексно-последовательная организация
Записи располагаются на внешнем запоминающем устройстве в конкретной физической последовательности, которую можно использовать в различных целях.
Обработка данных усложняется, если последовательность записей файла не соответствует последовательности их обработки.
При этом возникает необходимость сортировки записей, что требует значительных временных затрат, особенно, когда данных много.
Наиболее общий метод упорядочения записей заключается в размещении записей в соответствии с возрастанием их ключей, которые чаще всего используются для адресации этих записей (вспомните адресацию на основе хэш-функций).
Если же ключи следуют не в строго определённом порядке, то прямая адресация затруднительна и для выполнения поиска какой-нибудь записи требуется специальный индекс, чтобы не просматривать весь файл.
Для работы с индексно-последовательным файлом можно использовать два режима обработки:
Последовательную обработку, при которой записи обрабатываются в последовательности их размещения на внешнем запоминающем устройстве.
Произвольную обработку, при которой записи обрабатываются в произвольной последовательности, не связанной с физической организацией записей на внешнем устройстве.
Преобладание одного из режимов обработки отражается в используемых методах организации файлов.
Для первого типа файлов записи организованы последовательно и имеется дополнительный индекс, позволяющий обращаться к записям в произвольном порядке.
Для второго типа файлов стремятся максимизировать эффективность использования файла при произвольном обращении к записям, не заботясь об удобстве последовательной обработки записей.
Если записи упорядочены в соответствии с возрастанием их ключей, затраты памяти на индекс для этих ключей могут быть существенно меньшими, чем в случае, когда записи не упорядочены.
На двух следующих рисунках приведены индексы для последовательно расположенных записей (первый рисунок) и для тех же записей, но расположенных произвольно (возможно, в порядке поступления или по возрастанию другого ключа) (второй рисунок).
Рисунок 2.4.23.1 – Индексы для последовательно расположенных записей
Рисунок 2.4.23.2 – Индексы для произвольно расположенных записей