Модели данных и базы данных

С.Т.Главацкий, И.Г.Бурыкин

Аннотация курса: В спецкурсе будут изложены основы современной теории баз данных:

В первую очередь будет рассмотрена реляционная модель данных: реляционная алгебра, реляционное исчисление, язык определения и моделирования данными SQL.

Будут изложены основные подходы к проектированию баз данных (ER-моделирование структур данных, учет функциональных и многозначных зависимостей в реляционной модели, оптимизация основных запросов и т.д.).

Тематическое содержание курса
1 семестр
Модели данных и основы систем баз данных
  1. Основы баз данных. История развития. Понятие модели данных. СУБД, устройства хранения данных, языки манипулирования данными.
  2. СУБД: основные функции, запросы, транзакции. Компоненты СУБД, архитектура современных СУБД.
  3. Модели данных. Иерархическая, сетевая, реляционная и слабоструктурированная модели. Основы реляционной модели данных.
  4. Реляционная алгебра, отношения, кортежи, основные операции.
  5. Реляционная алгебра: представление сложных запросов. Мультимножества.
  6. Язык определения данных и манипулирования данными SQL.
  7. SQL: основные стандарты и особенности реализации.
  8. Функциональные зависимости и их роль в устранении аномалий манипулирования в реляционных базах данных.
  9. Исчисление функциональных зависимостей, алгоритмы вычисления замыканий.
  10. Декомпозиция схем отношений. Свойства соединения без потерь и сохранения зависимостей.
  11. Декомпозиция схем отношений. Основные алгоритмы.
  12. Нормальные формы схем отношений. Основные теоремы о декомпозиции схем.
  13. Алгоритмы приведения к 3-й нормальной форме и нормальной форме Бойса-Кодда.
  14. Многозначные зависимости. Исчисление многозначных зависимостей. Замыкание множества функциональных и многозначных зависимостей.
  15. Декомпозиции схем отношений, 4-я нормальная форма.
  16. Проектирование схем баз данных. Концептуальные модели, модель сущностей-связей: основные понятия и представления.
  17. Модель сущностей-связей: правила описания связей и ограничений.
2 семестр
Базы данных: дополнительные данные
  1. Модель сущностей-связей: принципы проектирования.
  2. Прошлое, настоящее и будущее корпоративных приложений. Новые требования к корпоративным приложениям.
  3. Методы хранения баз данных. Словарное кодирование.
  4. Сжатие: Prefix Encoding / Run-Length Encoding / Cluster Encoding / Indirect Encoding / Delta Encoding.
  5. Размещение данных в оперативной памяти. Секционирование.
  6. Структуры и операции. Манипулирование данными (insert / update / delete / insert only).
  7. Реконструкция кортежей. Поиск данных. Стратегии материализации.
  8. Продвинутые техники баз данных. Архитектура базы данных: дифференциальный буфер, операция слияния.
  9. Параллельная обработка данных.
  10. Материализованные агрегаты, их кеширование. Управление рабочей нагрузкой и планирование.
  11. Механизм старения данных. Актуальное и историческое хранение.
  12. Внутренние механизмы базы данных. Индексы.
  13. Журналирование. Восстановление. Репликация. Резервирование.
  14. Введение в СУБД HANA. SAP S/4HANA. Структура данных: таблицы, представления и материализованные агрегаты.
  15. СУБД HANA: введение в язык манипулирования данными SQLScript.
  16. СУБД HANA: интерфейсы и сервисы для доступа к данным.
  17. NoSQL. Идея NoSQL. SQL & NoSQL – теорема CAP.
  18. NoSQL – data layout
Типовые контрольные задания

Задача 1: Рассмотрим схему отношения R(A, B, C, D) и следующий набор FD: AB → C, C → D и D → A.

a) Каковы все нетривиальные FD, которые следуют из заданных FD? Ограничьтесь рассмотрением FD с единственным атрибутом в правой части.

b) Каковы все ключи отношения R?

c) Каковы все суперключи R, не являющиеся ключами?

Задача 2: Выполните задания предыдущего упражнения для следующих схем отношений и наборов FD:

i) S(A, B, C, D) с FD A → B, B → C и B → D.

ii) T(A, B, C, D) с FD AB → C, BC → D, CD → A и AD → B.

iii) U(A, B, C, D) с FD A → B, B → C, C → D и D → A.

Задача 3: Докажите, что (X +)+ = X +.

Задача 4: Пусть дано отношение R(A, B, C, D, E) с некоторым набором FD и необходимо отыскать FD, справедливые для отношения, которое получено проецированием R на схему S(A, B, C). Найдите FD, удовлетворяющие S, если наборы FD для R таковы:

a) AB → DE, C → E, D → C и E → A;

b) A → D, BD → E, AC → E и DE → B;

c) AB → D, AC → E, BC → D, D → A и E → B;

d) A → B, B → C, C → D, D → E и E → A.

В каждом из случаев достаточно предъявить минимальный базис для полного множества FD, справедливых для S.

Задача 5: Даны следующие схемы отношений и FD’s.

a) R(A, B, C,D) с FD's AB → C, C → D, and D → A.

b) R(A, B,C, D) с FD's B → C и B → D.

c) R(A, B,C, D) с FD's AB → C, BC → D, CD → A и AD → B.

d) R(A, B,C, D) с FD's A → B, B → C, C → D и D → A.

e) R(A, B, C, D, E) с FD's AB → C, DE → C, и B → D.

f) R(A, B, C, D, E) с FD's AB → C, C → D, D → B и D → E.

Выполнить:

i) Отметить все нарушения BCNF. Не забыть принять во внимание не только данные FD, но и логические следствия из них. Не нужно отмечать FD, содержащие в правой части более одного атрибута.

ii) Произвести декомпозицию (насколько это нужно) с получаемыми компонентами в BCNF.

iii) Отметить все нарушения 3NF.

iv) Произвести декомпозицию (насколько это нужно) с получаемыми компонентами в 3NF.

Задача 6: Спроектируйте структуру, адекватно описывающую университетскую базу данных, которая должна включать информацию о студентах, факультетах, профессорах, курсах, а также о том, какие студенты слушают какие курсы и какие профессора преподают эти курсы, какие курсы читаются на том или ином факультете, об отметках студентов и лучших достижениях студентов по каждому курсу. Вы вправе представить на ER-диаграмме и другие данные, которые покажутся вам уместными и значимыми. Это задание предусматривает большую свободу действий, нежели предыдущие, и при его выполнении вам придется принимать самостоятельные решения, касающиеся свойств множественности связей, выбора их типов и даже того, какого рода информация достойна представления в базе данных.

Задача 7: Пусть даны таблицы Государств, Поставщиков и Товаров. Построить SQL-запрос для выдачи всех поставщиков из государства N, которые поставляют более пятидесяти различных товаров.

Перечень учебной литературы