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

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

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

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

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

1. Основы баз данных. История развития. Понятие модели данных. СУБД, устройства хранения данных, языки манипулирования данными.
2. СУБД: основные функции, запросы, транзакции. Компоненты СУБД, архитектура современных СУБД.
3. Модели данных. Иерархическая, сетевая, реляционная и слабоструктурированная модели. Основы реляционной модели данных.
4. Реляционная алгебра, отношения, кортежи, основные операции.
5. Реляционная алгебра: представление сложных запросов. Мультимножества.
6. Язык определения данных и манипулирования данными SQL.
7. SQL: основные стандарты и особенности реализации.
8. Функциональные зависимости и их роль в устранении аномалий манипулирования в реляционных базах данных.
9. Исчисление функциональных зависимостей, алгоритмы вычисления замыканий.
10. Декомпозиция схем отношений. Свойства соединения без потерь и сохранения зависимостей.
11. Декомпозиция схем отношений. Основные алгоритмы.
12. Нормальные формы схем отношений. Основные теоремы о декомпозиции схем.
13. Алгоритмы приведения к 3-й нормальной форме и нормальной форме Бойса-Кодда.
14. Многозначные зависимости. Исчисление многозначных зависимостей. Замыкание множества функциональных и многозначных зависимостей.
15. Декомпозиции схем отношений, 4-я нормальная форма.
16. Проектирование схем баз данных. Концептуальные модели, модель сущностей-связей: основные понятия и представления.
17. Модель сущностей-связей: правила описания связей и ограничений.

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

• Устройства хранения данных.
• Понятие модели данных.
• Языки манипулирования данными.
• Ограничения данных.
• СУБД: основные функции, запросы, транзакции.
• Компоненты СУБД,
• Архитектура современных СУБД
• Реляционная модель данных.
• Реляционная алгебра, отношения, кортежи, основные операции.
• Язык определения данных и манипулирования данными 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.