====== Модели данных и базы данных ======
=== С.Т.Главацкий, И.Г.Бурыкин ===

----

**Аннотация курса**: В спецкурсе будут изложены основы современной теории баз данных:
  * базовые модели данных (реляционная, иерархическая, сетевая);
  * принципы и методы моделирования данных;
  * построение и организация современных систем управления базами данных (СУБД), включая NoSQL базы данных и базы данных, использующие оперативную память компьютера в качестве основного хранилища (in-memory databases).

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

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

----

== Тематическое содержание курса ==
== 1 семестр ==
== Модели данных и основы систем баз данных ==
  - Основы баз данных. История развития. Понятие модели данных. СУБД, устройства хранения данных, языки манипулирования данными.
  - СУБД: основные функции, запросы, транзакции. Компоненты СУБД, архитектура современных СУБД.
  - Модели данных. Иерархическая, сетевая, реляционная и слабоструктурированная модели. Основы реляционной модели данных.
  - Реляционная алгебра, отношения, кортежи, основные операции.
  - Реляционная алгебра: представление сложных запросов. Мультимножества.
  - Язык определения данных и манипулирования данными SQL.
  - SQL: основные стандарты и особенности реализации.
  - Функциональные зависимости и их роль в устранении аномалий манипулирования в реляционных базах данных.
  - Исчисление функциональных зависимостей, алгоритмы вычисления замыканий.
  - Декомпозиция схем отношений. Свойства соединения без потерь и сохранения зависимостей.
  - Декомпозиция схем отношений. Основные алгоритмы.
  - Нормальные формы схем отношений. Основные теоремы о декомпозиции схем.
  - Алгоритмы приведения к 3-й нормальной форме и нормальной форме Бойса-Кодда.
  - Многозначные зависимости. Исчисление многозначных зависимостей. Замыкание множества функциональных и многозначных зависимостей.
  - Декомпозиции схем отношений, 4-я нормальная форма.
  - Проектирование схем баз данных. Концептуальные модели, модель сущностей-связей: основные понятия и представления.
  - Модель сущностей-связей: правила описания связей и ограничений.

----

== 2 семестр ==
== Базы данных: дополнительные данные ==
  - Модель сущностей-связей: принципы проектирования.
  - Прошлое, настоящее и будущее корпоративных приложений. Новые требования к корпоративным приложениям.
  - Методы хранения баз данных. Словарное кодирование.
  - Сжатие: Prefix Encoding / Run-Length Encoding / Cluster Encoding / Indirect Encoding / Delta Encoding.
  - Размещение данных в оперативной памяти. Секционирование.
  - Структуры и операции. Манипулирование данными (insert / update / delete / insert only).
  - Реконструкция кортежей. Поиск данных. Стратегии материализации.
  - Продвинутые техники баз данных. Архитектура базы данных: дифференциальный буфер, операция слияния.
  - Параллельная обработка данных.
  - Материализованные агрегаты, их кеширование. Управление рабочей нагрузкой и планирование.
  - Механизм старения данных. Актуальное и историческое хранение.
  - Внутренние механизмы базы данных. Индексы.
  - Журналирование. Восстановление. Репликация. Резервирование.
  - Введение в СУБД HANA. SAP S/4HANA. Структура данных: таблицы, представления и материализованные агрегаты.
  - СУБД HANA: введение в язык манипулирования данными SQLScript.
  - СУБД HANA: интерфейсы и сервисы для доступа к данным.
  - NoSQL. Идея NoSQL. SQL & NoSQL – теорема CAP.
  - NoSQL – data layout


----

== Типовые контрольные задания ==
  * Устройства хранения данных.
  * Понятие модели данных.
  * Языки манипулирования данными.
  * Ограничения данных.
  * СУБД: основные функции, запросы, транзакции.
  * Компоненты СУБД,
  * Архитектура современных СУБД
  * Реляционная модель данных.
  * Реляционная алгебра, отношения, кортежи, основные операции.
  * Язык определения данных и манипулирования данными SQL.
  * SQL: основные стандарты и особенности реализации.
  * Функциональные зависимости и их роль в устранении аномалий манипулирования в реляционных базах данных.
  * Исчисление функциональных зависимостей, алгоритмы вычисления замыканий.
  * Декомпозиция схем отношений.
  * Свойства соединения без потерь и сохранения зависимостей.
  * Основные алгоритмы.
  * Нормальные формы схем отношений.
  * Основные теоремы о декомпозиции схем.
  * Алгоритмы приведения к 3-й нормальной форме и нормальной форме Бойса-Кодда.
  * Многозначные зависимости. Исчисление многозначных зависимостей. Замыкание множества функциональных и многозначных зависимостей.
  * Декомпозиции схем отношений, 4-я нормальная форма.
  * Функциональные зависимости и их роль в устранении аномалий манипулирования в реляционных базах данных.
  * Исчисление функциональных зависимостей, алгоритмы вычисления замыканий.
  * Модель сущностей-связей:
  * – правила описания связей и ограничений,
  * – принципы проектирования.

**Задача 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, которые поставляют более пятидесяти различных товаров.

----

== Перечень учебной литературы ==
  * К. Дж. Дейт. Введение в системы баз данных. (Introduction to Database Systems.) — 8-е изд. — М.: Вильямс, 2006. — С. 1328. — ISBN 5-8459-0788-8.
  * Hector Garcia-Molina, Jeffrey D. Ullman, Jennifer Widom.  Database systems. The Complete Book. 2009, 2002 by Pearson Education Inc., Pearson Prentice Hall, Pearson Education, Inc. Upper Saddle River, NJ 07458. – ISBN 0-13-606701-8.
  * Гектор Гарсиа-Молина, Джеффри Ульман, Дженнифер Уидом. Системы баз данных. Полный курс. : Пер. с англ. — М.: Издательский дом “Вильямс”, 2002. — 1088 с. : ил. — Парал. тит. англ. –ISBN 5-8459-0384-X.
  * К. Дж. Дейт. SQL и реляционная теория. Как грамотно писать код на SQL. – Пер. с англ. – СПб.: Символ-Плюс, 2010. – 480 с., ил. – ISBN 978-5-93286-173-8.