Skip to content

Latest commit

 

History

History
1376 lines (856 loc) · 98.8 KB

databases_superconspect.md

File metadata and controls

1376 lines (856 loc) · 98.8 KB
Raw

Базы данных

Введение

Курс базы данных находится в цикле курсов "Управление данными" на направлении ИС

В отличие от математиков, перед которыми не стоят как таковые ограничения, у инженеров существуют ограничения, будь-то бюджет или время. Поэтому инженеры вынуждены искать компромиссы между тремя главными параметрами: надежность, производительность и безопасность.

В XX веке был сформулирован закон Мура, который прогнозировал увеличение числа транзисторов в два раза каждые два года, но в 10-ых годах закон Мура перестал работать из-за физических ограничений. Далее появилось большое желание увеличивать память, в следствие чего появились распределенные системы, но ограничениями стала теорема CAP

Британский учёный Эдгар Кодд в 70-ых сформулировал основы теории реляционных баз данных, на основе которой созданы современные реляционные базы данных

Лекция 1. Что такое данные?

Выделяют 5 информационных процессов:

  • Сбор
  • Обработка
  • Хранение
  • Передача
  • Представление

И эти процессы хотелось бы автоматизировать

До появления Computer Science как науки все эти процессы существовали в пределах небольших библиотеки, в которых книги искались линейным или двоичным поисками. После этого библиотеки увеличивались, появились картотеки, каталоги.

Тем не менее определение информации так и не сформулировалось по многим философским вопросам: что такое информация? Является ли информация атрибутом материи или энергии? Существует ли информация без человека? Поэтому информацию следует воспринимать как триединство сигнала, данных и знаний.

В начале XX века Гёдель, целью которого была создать систему доказательств в математике, и, следовательно, автоматизировать их, изобрел систему представления математических доказательств и доказал, что такая система не может быть полной (теорема о неполноте)

После Гёделя появился Джон фон Нейман, целью которого была представить информацию в конечном пространстве. Из этой идеи вывелась архитектура фон Неймана, где числа представлялись в двоичном виде. В итоге получается, что данные - это информация, которая закодирована заранее обговоренным способом:

Данные (ISO / IEC 2382:2015) - поддающееся многократной интерпретации представление информации в формализованном виде, пригодном для передачи, интерпретации или обработке

Из этого появляется потребность моделировать данные. Но у моделей появляются свои ограничения. Приведем пример таблицы студентов:

Студент Группа Дисциплина Преподаватель Аудитория Время

Поиск конкретного студента реализовать легко, но что если нам нужно иметь в виду несколько дисциплин для одного студента? Приходит другая реализация:

Студент Группа (Дисциплина1, ...) (Дисциплина2, ...)

Но в ней мы не сможем запросто составить расписание для какого-то преподавателя. Тогда приходит идея разделить на несколько табличек для студентов:

Номер студента ФИО студента

Для групп:

Номер группы Факультет группы

И для предметов:

Номер дисциплины Название дисциплины Преподаватель

В этом случае повышается целостность данных, но уменьшается производительность системы, и в итоге мы не сможем найти идеального решения

Лекция 2. Абстрагирование данных

Откуда появилась идея абстрагирования данных? Сначала все началось с архитектуры фон Неймана, где появилась однородность памяти - концепция хранения данных и инструкций в одном месте. Потом появилась первая абстракция данных - хранение в файле. Если же в оперативной памяти читаемость не нужна, то в постоянной она необходима для упрощенной работы - будь-то имя файла и имя каталога. И так появляется файло-серверная архитектура:

File-Server

Все хорошо, но что, если приложений будет N? Каждое из них будет блокировать этот файл, таким образом можно соблюдать целостность данных, но файл становиться большим и нельзя поддерживать параллельный доступ (эффект конкурентных транзакций), падает производительность

Можно хранить несколько файлов, каждый из них хранящий группу данных (например: студенты, группы, факультеты), но все равно почти все запросы запрашивают те комбинации файлов, которые так или иначе пересекутся

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

При этом данные растут, а если фрагментировать данные, то придется переписывать логику кода, что не является хорошей идеей. Да и к тому же возникает противоречие скоростей записи и чтения: нельзя обеспечить одинаково быстрые запись и чтение

В итоге появляется клиент-серверная архитектура, появляется СУБД (Система Управления Базой Данных) и моделирование данных, из-за чего мы избавляемся от привязанности к определенному формату файла

Client-Server

Появляется целостность данных, которая контролируется СУБД, и повышается производительность в следствие группировки запросов по времени и другим параметрам. Появляются правила моделирование бизнес-сущностей.

Но в чем состоит идея моделирования: выделение значимых аспектов у сущностей и для разных целей формирование различного моделирования

Выделяют 2 основания классификаций:

  • Трехуровневая архитектура (ANSI/SPARC):
    • Внешний
    • Концептуальный
    • Внутренний (физический, исходный)

Внешний уровень определяет базу данных с точки зрения конечного пользователя, например: для студофиса важно знать возраст определенного студента, но хранить возраст не удобно

Концептуальный уровень - на этом уровне накладываются ограничения на данные, определяются сущности и атрибуты, семантика данных (например: рейтинг компании на внешнем уровне может быть Excellent, Good, ..., а на концептуальном 5, 4, ... для упрощенной группировки)

Внутренний уровень - то, что организует производительность, безопасность, структуру файлов, шифрование и ограниченный доступ к щекотливым данным

  • И уровни моделей данных:
    • Сущность-связь
    • Логический (дата-логический) уровень
    • Физический уровень

Сущность-связь (ER, Entity-Relation) - абстрагирование объектов, появление связей

Логический уровень - то, как мы пытаемся описать сущность-связь, выделив какие-то формальные множества

Физический уровень - выбор СУБД на основе логического уровня (ограничения на типы данных, производительность, безопасность)

В конце концов появляется вот такой граф:

Relations

Сущность - множество экземпляров, реальных или абстрактных, однотипных объектов предметной области

Выделяют 2 типа сущности: сильная и слабая

Студент - сильная сущность, потому что может существовать без других

Группа - слабая сущность, потому что не может существовать без студентов (но группа может быть и сильной сущностью)

Также у сущностей могут быть атрибуты

  • Составные, например, ФИО
  • Простые, например, Фамилия и Имя по отдельности

А также:

  • Однозначными - хранят одно значение, например, телефон
  • Многозначными - хранят не меньше одного значения, например, контакт, хранящий JSON-объект с множеством телефонов

Появляются 3 вида связи:

  • One-To-One: студент -<>- паспорт (1 <-> 1) (паспорт можно выделить в отдельную сущность, чтобы ограничить к нему доступ)

  • One-To-Many: группа -<>- студент (1 <-> N)

  • Many-To-Many: группы -<>- студенты (M <-> N)

Получается такая картинка в нотации Чена:

Лекция 3. Модели данных

Прошлая лекция была про то, что моделировать данные надо с умом и с наделом на будущее, потому перестраивать модели и код будет очень дорого. Сейчас же приведем определение базы данных по нескольким разным источникам:

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

Здесь идет упор на то, что БД - это не только сами данные, но и их описание (схема, семантика), что подчеркивает целостность БД

  1. (по Дейту) База данных - набор постоянно хранимых данных, используемых прикладными системами предприятия

В определении по Дейту подчеркивается то, что данные где-то физически хранятся на постоянной основе

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

Хомоненко объединяет другие определения и указывает, что базы данных могут использовать и не предприятиями

Эти же авторы приводят разные определения для Системы Управления Базой Данных (СУБД):

  1. (по Коннолли, Беггу, Дейту) СУБД - ПО, с помощью которого пользователи могут определять, создавать и поддерживать базу данных, а также осуществлять контролируемый к ней доступ
  1. (по Хомоненко) СУБД - комплекс языковых и программных средств, предназначенный для создания, ведения и совместного использования базы данных многими пользователями

Теперь рассмотрим несколько способ, каким образом моделировать данные:

Иерархическая модель данных

Идея в иерархической модели данных состоит в том, чтобы хранить данные в деревьях. В 60-70 годах вместо таблицы все данные представлялись в виде деревьев, например, на предприятиях продукт изготавливался из компонентов, которые делались из деталей, которые создавались из заготовок. Чаще всего деталей было относительно немного, поэтому иерархическая модель подходила лучше всего. В итоге появляются:

Поле данных - атомарная (неделимая) единица данных

Сегмент данных - совокупность полей данных

Пример: ФИО, название отдела, телефон - это поля данных, сотрудник с этими полями - сегмент данных, а Иванов Иван Иванович с отделе маркетинга с телефоном +7(777)777-77-77 - экземпляр сегмента сотрудника. Тут же введем отдел с названием и именем начальника. В конце концов появляется огромное дерево, в котором можно узнать информацию об отделе от конкретного сотрудника.

Тут появляются достоинства:

  1. Легкость проектирования - в принципе все в этом мире можно представить как дерево

И недостатки:

  1. Дублирование данных - пример: сотрудник числится в нескольких отделах, так как сотрудник не может иметь двух родителей-отделов, то придется создавать нового сотрудника-дублера - тратим память и нарушаем целостности

  2. Сложность поиска сверху вниз - мы не сможем быстро получить всех сотрудников конкретного отдела; в этом случае мы можем создать кучу полей Сотрудник 1, Сотрудник 2, Сотрудник N, но число N может быть меньшим, чем нам надо, в таком случае надо будет двигать всю память, чтобы добавить новое поле, либо большая часть этих полей будут не задействованы (такая же проблема в файловых системах ex3, ex4 - количество файлов в них строго ограничено)

История из жизни:

4 курс, бакалавриат, девушка защищает диплом, решает выйти замуж и поменять фамилию. Приносит документы о смене, но базы данных разные, между ними период синхронизации. Данные об окончании образования отправляются в ФИС ГИА. Интеграция систем была раз в сутки, данные диплома из ФИС ГИА пришли со старой фамилией, а приложение к диплому печаталось с новой фамилией, но с тем же номером.

Сетевая модель данных

В сетевой модели мы разрешаем иметь у экземпляра сегмента нескольких родителей. В итоге получаем граф

Достоинства:

  1. Экономия памяти

  2. Целостность

Но мы можем присвоить каждому экземпляру идентификатор и хранить связи пар идентификаторов отдельно и данные отдельно

Недостатки:

  1. Обход графа медленный в больших графах - та же задача из иерархической модели, нам придется пройтись по всем сотрудникам, чтобы найти сотрудников конкретного отдела

Можно вспомнить пакетные менеджеры, где для загрузки зависимостей приложения строится граф зависимостей, который обходится, и менеджер принимает решение о загрузке пакетов.

Реляционная модель данных

Заметим, что большинство запросов очень однотипные: найти атрибуты конкретного сотрудника, агрегация сотрудников отдела; поэтому все наборы атрибутов можно хранить:

ID сотрудника ФИО Телефон ID отдела

И для отделов:

ID отдела Название ID начальника

И с точки зрения реляционной (сущность из таблицы образуют отношение эквивалентности (equivalency relation)) модели связей между таблицами нет - для СУБД ID отдела и ID сотрудника - это одинаковый вещи (например, в SQL возможна подобная конкатенация). Также в случае, если начальника уволили, а его ID отдали новому сотруднику, то возникнет ситуация, когда этот сотрудник будет восприниматься начальником

И тут возникает проблема с реляционной базой данных - она плохо масштабируется. Добавлять сотруднику еще один телефон - значит двигать всю память для выделения места под новый столбец

Постреляционная модель данных

В постреляционной модели мы снимаем ограничение на неделимость поля, тогда поле можно представить как структуру.

Например, предприятие продает книги с атрибутами "жанр", "кол-во страниц", "год издания", но внезапно начинает продавать ручки с атрибутом "цвет". В реляционной БД, помимо универсальных атрибутов цены, штрих-кода, большинство полей остается избыточными - ручке не определишь жанр и кол-во страниц.

Тогда можно хранить все индивидуальные атрибуты в структуре JSON или XML, сериализовать ее и хранить в бинарном виде. Но из-за этого появляются:

  1. Долгий поиск по второстепенным атрибутам

  2. Нарушение целостности - пример: компания, производящая ручки, сделала ребрендинг, теперь придется менять в каждой структуре бренд

Многомерная модель данных

Дается такая таблица фактов

Товар Сотрудник Месяц Количество проданных товаров
T1 C1 Янв 10
T2 C1 Янв 5
T3 C3 Фев 15

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

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

Анекдот:

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

Но почему же вы сдаетесь? - спрашивает профессор.

Да я вот экзамен точно не сдам, - отвечает студент.

Ну почему же, голубчик?

Да вот вы каждую теорему в 9-мерном пространстве доказываете, я ничего из этого не понимаю.

Хорошо, я вам еще один раз объясню, что 9-мерное пространство - это очень легко. Вот представьте обыкновенное n-мерное пространство, а потом возьмите n = 9.

Объектно-ориентированная модель данных

Вспомним, что объект - совокупность полей. Тогда появились ORM-модели (Object Relation Model) - создается таблица с атрибутами класса, объект записывается как строка в таблицу.

В этом случае целостность данных гарантируется тем, что данные изменяются только методами объекта, Но если изменить данные в табличке, в файле, получим нецелостный объект

Можно хранить в объекте вместо данных ключ, который ссылается на данные в бинарном файле, а в методах объекта данные сразу же записываются в файл

В конечном итоге большинство современных СУБД являются многопарадигмиальными - как компромисс в противоречии между целостностью, выборкой данных и записи данных. Но на данный момент реляционная модель является наиболее оптимальной из-за ее производительности и гарантии целостности данных

Лекция 4. Отношение

В конечном итоге появилась реляционная модель данных, созданная Эдгаром Коддом.

Введем следующие термины:

Отношение - двумерная таблица, содержащая данные

Столбец отношения - атрибут, некое свойство, характеризующее сущность

Строка отношения - кортеж, описывающий экземпляр сущности

Причем, не каждое отношение является сущностью - например: у нас есть производители (vendor) и продукты, которые они производят (product), так как разные производители могут производить одни и те же продукты, то необходимо отдельное отношение с парами vendor-product

И к тому же, не каждая сущность является отношением - например: паспорт - не сущность, но может быть выделен в отдельное отношение

Степень отношения - количество атрибутов

Кардинальность отношения - количество кортежей в отношении

Домен - множество допустимых значений атрибута

Эдгар Кодд сформулировал, что отношение - кортеж атрибутов, значений которых принадлежат некоторому домену

image1

И в отличие от иерархической и сетевой моделей, где хранятся связи (указатели на поля родителей), в реляционной связи связи прямым способом не хранятся

Схема отношений - заголовки отношений

В конечном итоге во время своей работы в IBM Эдгар Кодд сформулировал, что отношение R будет являться отношением тогда, когда выполняются 6 свойств:

  1. Каждое поле содержит только одно неделимое значение

    Здесь же появляется вопрос, что считать неделимым значение? Например, в SQL существуют строки, которые можно разделить на символы. Помимо этого строки в SQL можно сравнивать при помощи ключевого слова LIKE

  2. Каждый кортеж уникален

    На первый взгляд это свойство выглядит разумно, но при применении инструкции SELECT в SQL может создаться временная таблица, в которой могут существовать неуникальные кортежи. Это может быть решено при помощи ключевого слова DISTINCT, но дубликаты кортежей могут быть полезны для подсчета сущностей

  3. Уникальность имени отношения в реляционной схеме

    Тоже разумное свойство, но представим пример: поглощение СПбГУНиПТ университетом ИТМО в 2011 году, в те времена у обоих университетов были базы данных с таблицей Student, и казалось бы возникла проблема с объединением этих баз данных

  4. Уникальность имени атрибута в пределах отношения

    Еще одно очевидное свойство, но при операции JOIN (объединения таблиц) в SQL может создаться отношение с одинаковыми атрибутами

  5. Значения атрибута берутся из одного и того же домена

  6. Порядок следования атрибутов и порядок следования кортежей не имеют значения

    И от этого свойства сразу же отказались, использовать ORDER BY с указанием номера столбца (что означало бы, что атрибуты имеют порядок) было очень удобно

И как можно заметить, одновременно эти все свойства на практике реализовать нельзя было, да и к тому же было бы супер неудобно для пользователей

Теперь рассмотрим определения ключей:

Суперключ - атрибут или множество атрибутов, единственным образом идентифицирующий кортеж

ИСУ ФИО N группы Серия паспорта Номер паспорта

В этом случае, номер ИСУ - суперключ. Также очевидно, что в таблице с уникальными кортежами сам кортеж будет являться суперключом

Потенциальный ключ - суперключ, который не содержит подмножества, также являющегося суперключом данного отношения

В примере выше номер ИСУ - потенциальный суперключ, также, как и комбинация из серии и номера паспорта. Поэтому потенциальный ключ может не являться суперключом из таблицы, состоящим из минимального числа атрибутов

Потенциальный ключ из одного атрибута называют простыми, а из более одного - составным

Первичный ключ (Primary key) - потенциальный ключ, который выбран для уникальной идентификации кортежа в отношении

Внешний ключ (Foreign key) - атрибут или множество атрибутов, которые соответствуют потенциальному ключу некоторого (может быть того же самого) отношения

В случае со студентами, номер группы у студента - внешний ключ

Внешний ключ, в том числе, может соответствовать ключу в том же отношении:

ИСУ сотрудника PK ФИО ИСУ руководителя FK

При этом связи One-to-One и One-to-Many означают, что первичные ключи отношения являются внешними ключами в другом, например, номер ИСУ в таблице с паспортами студентов - внешний ключ; номер группы в таблице студентов - внешний ключ, который соотносится с первичным в таблице групп

А связь Many-to-Many требует уже таблицу-связку, как в примере выше про производителя и продукты (vendor-product)

Тут же выделяем два вида целостности:

  • Целостность сущности: ни один атрибут первичного ключа не может содержать null-значения
  • Ссылочная целостность: если в отношении есть внешний ключ, то либо значение внешнего ключа соответствует значению потенциального ключа, с которым он связан, либо внешний ключ полностью состоит из null-значений

Теперь необходимо от этой реляционной модели данных перейти к языку SQL. Но перед этим нужно ввести реляционную алгебру.

Лекция 5. Реляционная алгебра

Уже на протяжении выполнения лабораторных работ можно было столкнуться с теоретико-множественными операциями из реляционный алгебры, например, JOIN. Причем, стоит заметить, что реляционная алгебра - замкнутая.

Операции реляционной алгебры

Операции, которые ввел Кодд в реляционной алгебре, делятся на унарные и бинарные

  1. Проекция:

    Нотация проекции

    Результатом проекции является новое отношение, содержащее вертикальное подмножество исходного отношения, создаваемое посредством извлечения значений указанных атрибутов и исключения из результата строк-дубликатов

    В SQL проекция реализована через инструкцию SELECT и выбор определенных атрибутов

  2. Выборка

    Нотация выборки

    Результатом выборки является новое отношение, которое содержит только те кортежи из исходного отношения, которые удовлетворяют заданному предикату

    В SQL выборка реализована через инструкцию WHERE Condition

  3. Объединение (Union)

    Нотация объединения

    Объединение двух наборов кортежей определяет новое отношение, которое включает все кортежи из исходных отношений с исключением кортежей-дубликатов

    Отношения совместимы, если они состоят из одинаковых атрибутов и каждая пара атрибутов имеет одинаковый домен

    В SQL возможно сделать объединение так:

    SELECT * FROM Table1
UNION
SELECT * FROM Table2;

    Синтаксически такие запросы в SQL разрешены, но семантически они не имеют смысла. Приведем пример объединения на таблицах Item:

    ItemID ItemName
    1 Ball
    2 Pen
    3 Notebook

    И FavouriteItem:

    ItemID ItemName
    2 Pen
    3 Notebook
    4 Laptop

    Их объединение

    SELECT * FROM Item
UNION
SELECT * FROM FavouriteItem;

    даст такое отношение:

    ItemID ItemName
    1 Ball
    2 Pen
    3 Notebook
    4 Laptop

  4. Разность

    Нотация разности

    Разность отношений - новое отношение, которое включает кортежи из первого отношения и исключает кортежи, входящие во второе отношение

    Аналогично, отношения, к которым применяется разность, должны быть совместимы

    Разность отношений, приведенных выше:

    SELECT * FROM Item
EXCEPT
SELECT * FROM FavouriteItem;

    даст такое отношение:

    ItemID ItemName
    1 Ball

  5. Пересечение

    Нотация пересечения

    Пересечение определяет новое отношение, которое включает кортежи, входящие в обои отношения одновременно

    Аналогично, отношения, к которым применяется пересечение, должны быть совместимы

    Пересечение отношений, приведенных выше:

    SELECT * FROM Item
INTERSECT
SELECT * FROM FavouriteItem;

    даст такое отношение:

    ItemID ItemName
    2 Pen
    3 Notebook

    Дальше будут приводиться примеры операций на атрибуте DepartmentID (далее DepartID) на таблицах Employee1:

    EmplID FullName DepartID
    1 Albert Einstein 4
    2 Ernest Rutherford 4
    3 Marie Curie 10
    4 Igor Kurchatov NULL
    5 Alexander Fleming 13

    И Department:

    DepartID DepartName DirectorID
    4 Theoretical Physics 1
    10 Chemistry 3
    11 Nuclear Physics 2
    13 Biology 5

  6. Декартовое произведение

    Нотация декартового произведения

    Результатом декартового произведения является новое отношение, в которой кортежи являются результатом конкатенации кортежей из первого отношения и кортежей из второго произведения

    В SQL декартовое произведение можно сделать так:

    SELECT * FROM Table1, Table2

    Либо так:

    SELECT * FROM Table1 CROSS JOIN Table2

    Семантически декартовое произведение зачастую не имеет смысла. На таблицах выше декартовым произведением будет такое отношение:

    EmplID FullName DepartID DepartID DepartName DirectorID
    1 Albert Einstein 4 4 Theoretical Physics 1
    2 Ernest Rutherford 4 4 Theoretical Physics 1
    3 Marie Curie 10 4 Theoretical Physics 1
    4 Igor Kurchatov NULL 4 Theoretical Physics 1
    5 Alexander Fleming 13 4 Theoretical Physics 1
    1 Albert Einstein 4 10 Chemistry 3
    2 Ernest Rutherford 4 10 Chemistry 3
    3 Marie Curie 10 10 Chemistry 3
    4 Igor Kurchatov NULL 10 Chemistry 3
    5 Alexander Fleming 13 10 Chemistry 3
    1 Albert Einstein 4 11 Nuclear Physics 2
    2 Ernest Rutherford 4 11 Nuclear Physics 2
    3 Marie Curie 10 11 Nuclear Physics 2
    4 Igor Kurchatov NULL 11 Nuclear Physics 2
    5 Alexander Fleming 13 11 Nuclear Physics 2
    1 Albert Einstein 4 13 Biology 5
    2 Ernest Rutherford 4 13 Biology 5
    3 Marie Curie 10 13 Biology 5
    4 Igor Kurchatov NULL 13 Biology 5
    5 Alexander Fleming 13 13 Biology 5

  7. Тета-соединение

    Нотация тета-соединения Предикат

    Результатом тета-соединения является декартовое соединение, кортежи которого удовлетворяют предикату F

    Тета-соединение осуществимо в SQL с помощью инструкции

    FROM Table1 FULL JOIN Table2 ON Condition

  8. Эквисоединение

    Нотация эквисоединения

    Результатом эквисоединения является декартовое соединение, кортежи которого равны по какому-либо атрибуту

    Эквисоединение двух таблиц из примера будет таким результатом:

    EmplID FullName DepartID DepartID DepartName DirectorID
    1 Albert Einstein 4 4 Theoretical Physics 1
    2 Ernest Rutherford 4 4 Theoretical Physics 1
    3 Marie Curie 10 10 Chemistry 3
    5 Alexander Fleming 13 13 Biology 5 
    SELECT *
FROM Employee 
INNER JOIN Department 
ON Employee.DepartmentID = Department.DepartmentID;

  9. Естественное соединение (Natural Join)

    Нотация естественного соединения

    Естественное соединение - эквисоединение двух отношений, выполненное по всем общим атрибутам, из результатов которого исключается по одному экземпляру общего атрибута

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

    EmplID FullName DepartName DirectorID
    1 Albert Einstein Theoretical Physics 1
    2 Ernest Rutherford Theoretical Physics 1
    3 Marie Curie Chemistry 3
    5 Alexander Fleming Biology 5

  10. Левое внешнее соединение

    Нотация левого внешнего соединения

    Соединение, результирующее отношение которое содержит в себе все кортежи из отношения R, с конкатенации к ним тех кортежей из отношения из S, имеющих совпадающие значения в общих атрибутах

    В SQL левое внешнее соединение на таблицах выше осуществляется так:

    SELECT *
FROM Employee
LEFT JOIN Department
ON Employee.DepartmentID = Department.DepartmentID;
    EmplID FullName DepartID DepartID DepartName DirectorID
    1 Albert Einstein 4 4 Theoretical Physics 1
    2 Ernest Rutherford 4 4 Theoretical Physics 1
    3 Marie Curie 10 10 Chemistry 3
    4 Igor Kurchatov NULL NULL NULL NULL
    5 Alexander Fleming 13 13 Biology 5

    Аналогично в SQL можно сделать правое внешнее соединение:

    SELECT *
FROM Employee
RIGHT JOIN Department
ON Employee.DepartmentID = Department.DepartmentID;
    EmplID FullName DepartID DepartID DepartName DirectorID
    1 Albert Einstein 4 4 Theoretical Physics 1
    2 Ernest Rutherford 4 4 Theoretical Physics 1
    3 Marie Curie 10 10 Chemistry 3
    NULL NULL NULL 11 Nuclear Physics 2
    5 Alexander Fleming 13 13 Biology 5

  11. Полусоединение

    Нотация полусоединения

    Полусоединение - отношение, состоящее из кортежей R, которые входят в экви-соединение R и S

    В SQL полусоединение не реализовано2

Синтаксис SELECT

Рассмотрим запрос выборки в SQL - его можно разделить на 5 частей:

  1. Выбор столбцов отношения:

    SELECT [ DISTINCT | ALL ] { * | [ColumnExpression [AS NewName] ] [, ...]}

    Ключевое слово DISTINCT определяет выбор только уникальных кортежей, ALL - явный выбор кортежей с дубликатами

    Далее указываются имена столбцов (также возможны их алиасы) или *, которая определяет вывод всех столбцов отношения

  2. Выбор исходного отношения:3

    FROM TableName [AS NewTableName] 
[{INNER | LEFT OUTER | FULL} JOIN OuterTable [AS NewOuterTableName] 
ON Condition]

    Здесь же можно определить соединение и его тип на основе условия Condition

     ```sql
 FROM TableName [AS NewTableName] 
 [{INNER | { LEFT | RIGHT | FULL } [OUTER]} JOIN OuterTable [AS NewOuterTableName] 
 ON Condition]
 ```

  3. Фильтрация кортежей:

    [WHERE Condition]

    В инструкции WHERE определяются условия для фильтрации кортежей

  4. Группировка:

    [GROUP BY ColumnList [, ...] [HAVING Condition]]

    В инструкции GROUP BY производится группировка по указанному набору атрибутов и фильтрации через условие в HAVING

  5. Сортировка:

    [ORDER BY ColumnList [, ...] [{ASC | DESC}]]

    И, наконец, в инструкции ORDER BY происходит сортировка конечного отношения по указанному набору атрибутов

В конечном счете, получаем:

SELECT [ DISTINCT | ALL ] { * | [ColumnExpression [AS NewName] ] [, ...]}
FROM TableName [AS NewTableName] 
[{INNER | LEFT OUTER | FULL} JOIN OuterTable [AS NewOuterTableName] 
ON Condition]
[WHERE Condition]
[GROUP BY ColumnList [, ...] [HAVING Condition]]
[ORDER BY ColumnList [, ...] [{ASC | DESC}]]

Здесь стоит заметить, что желательно общие условия, которые имеют место в инструкции WHERE стоит размещать именно там, а не в HAVING, так как фильтрация кортежей после группировки работает медленнее и не обеспечивает производительность

Порядок выполнения инструкций в SELECT запросе таков:

  1. FROM
  2. ON
  3. JOIN
  4. WHERE
  5. GROUP BY
  6. HAVING
  7. SELECT
  8. DISTINCT
  9. ORDER BY

Рассмотрим две реализации JOIN:

  1. Наивная:

    for r in R:
    for s in S:
        if r.a_i Θ S.b_i:
            print(r + s)

  2. Слиянием:

    R.sort(a)
S.sort(b)

while not endof(R) and not endof(S):
    if R.a_i < S.b_i:
        next(R)
    if R.a_i > S.b_i:
        next(S)
    if R.a_i == S.b_i:
        print(r + s)
        next(R)

Обе реализации имеют свои достоинства и недостатки. Но так как SQL хранит кортежи уже отсортированными (чтобы поддерживать быстроту индексации), вторая реализация зачастую работает лучше

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

Лекция 6. Нормализация

На прошлой лекции мы рассматривали реляционную алгебру Кодда

Рассмотрим такое отношение:

ФИО N группы

Заметим, что здесь номера групп будут дублироваться - мы должны знать группу для каждого студента, поэтому это дублирование не избыточное. Теперь расширим таблицу - добавим столбец с образовательной программой:

ФИО N группы ОП

Добавление ОП добавляет избыточное дублирование: очевидно, что в одной группе студенты изучают одну образовательную программу

ФИО N группы ОП
С1 M3200 09.03.02
С2 M3200 X
С3 M3200 X

Здесь же (помимо избыточного выделения памяти) появляются 2 проблемы:

  1. Если номер ОП дублировать на все кортежи, то при изменении номера ОП в одном кортеже в других кортежах он не поменяется - нарушается целостность

  2. Если номер ОП хранить только в одном кортеже, то при поиске для другого кортежа придется искать именно тот кортеж - тратим больше времени

И в этом случае говорят, что у нашей модели появляется аномалия

Аномалия - состояние базы данных, которое приводит к противоречию или существенно усложняет обработку данных

Различают 3 типа аномалий:

  1. Аномалия модификации - изменение значения одной записи повлечет за собой изменение значения в другой записи

    Пример: при изменении у одного студента номера ОП, зависящего от группы, приходится изменять номер ОП в других местах

  2. Аномалия удаления - при удалении записи может пропасть и другая информация

    Пример: при удалении всех студентов связь "N группы"-"ОП" теряется

  3. Аномалия добавления - информацию в таблицу нельзя поместить, пока она не полная или требуется дополнительный просмотр таблицы

    Пример: при добавлении нового студента приходится искать номер ОП для других студентов из его группы

Аномалии приводят к нарушению целостности и дополнительным тратам по времени, поэтому, чтобы избежать этого, модели данных нужно нормализовать - избавить их.

Рассмотрим виды зависимостей атрибутов:

Функциональная зависимость: в некотором отношении x -> y (y зависит от x) тогда и только тогда, когда каждому значению x соответствует в точности одно значение y. Тогда x - детерминант, y - зависимая часть

В примере выше номер ОП зависит от номера группы

Частичная функциональная зависимость - зависимость неключевого атрибута от части составного потенциального ключа

Пример: создадим такое отношение студентов:

ФИО N группы ОП Факультет Форма обучения

В нем сделаем ФИО и N группы первичным ключом; тогда номер ОП частично зависит от этого ключа (потому что номер ОП зависит от номера группы)

Полная функциональная зависимость - зависимость неключевого атрибута от всего составного потенциального ключа

Транзитивная функциональная зависимость: атрибуты z транзитивно зависит от x, если найдется такой y, что z зависит от y, а y зависит от x (x -> z => Ǝ y : x -> y, y -> z)

Чтобы избежать зависимостей модели декомпозируют в нормальные формы. Разберем типы нормальных форм:

Отношение является первой нормальной формой (1НФ), если все его атрибуты являются простыми

Так как простоту атрибута мы определяем сами, то принадлежность отношения к 1-ой нормальной форме - чисто условность

Отношение является второй нормальной формой (2НФ), если оно находится в 1НФ и каждый неключевой атрибут функционально полно зависит от первичного ключа

Переделаем таблицу выше в две других: "Студент"

ФИО N группы Форма обучения

и "Группа"

N группы ОП Факультет

Все эти отношения являются вторыми нормальными формами. В этом случае мы выиграли по памяти (при большом кол-ве студентов не будет избыточно дублироваться номер ОП), но проигрываем по времени

Отношение является третьей нормальной формой (3НФ), если оно находится во 2НФ и все неключевые атрибуты взаимно независимы и полностью зависят от первичного ключа

Также существует другое эквивалентное определение

Отношение является третьей нормальной формой (3НФ), если оно находится во 2НФ и ни один неключевой атрибут не находится в транзитивной функциональной зависимости от потенциального ключа

Рассмотрим еще раз таблицу с группами:

N группы ОП Факультет

Здесь факультет транзитивно зависит от номер группы, исправим это:

Таблица "Группа":

N группы ОП

Таблица "Образовательная программа":

ОП Факультет

В итоге для получения связи Студент-Факультет нужно объединить целых 3 таблицы

Теперь рассмотрим более экзотические варианты. Введем отношение "Проект"

ИСУ Паспорт ID проекта Роль

Здесь потенциальными ключами являются пары либо "ИСУ"-"ID проекта", либо "Паспорт"-"ID проекта"

Роль студента в проекте функционально полно зависит от выбранного нами первичного ключа - соблюдается 3НФ

Но здесь возникает аномалия - студент поменял паспорт, в одном проекте это заменили, а в другом проекте нет

Отношение является нормальной формой Бойса-Кодда (БКНФ), если оно находится в 3НФ и детерминанты всех зависимостей являются потенциальными ключами

Паспорт зависит от номера ИСУ, но ИСУ - это не потенциальный ключ, а его часть. Поэтому переведем отношение в БКНФ:

Таблица "Проект"

ИСУ ID проекта Роль

Таблица "Паспорт"

ИСУ Паспорт

Приведем другой пример - таблица лекторов и практиков:

ID Дисциплины ID Лектора ID Практика

Здесь при замене лектора по причине болезни придется заменять его во всех кортежах соответствующей дисциплины.

Чтобы исправить это, определим четвертую нормальную форму:

Отношение является четвертой нормальной формой (4НФ), если оно находится в БКНФ и не содержит нетривиальных многозначных зависимостей

Изменим отношение на такое:

ID Дисциплины ID Преподавателя Роль

Здесь нет аномалии модификации, но при этом мы теряем связь лектор-практик (допускается, что некоторые лектора несовместимы с некоторыми практиками 🦆)

Заметим, что в отношении без неключевых атрибутов автоматически выполнена 2НФ и 3НФ.

Помимо этих нормальных форм выделяют 5НФ и 6НФ, но на этом курсе рассматриваться они не будут

Заметим, что в ходе декомпозиции модели мы увеличиваем количество отношений, из-за чего скорость поиска уменьшается (добавление дополнительных join не стоят бесплатно)

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

Лекция 7. Производительность

В прошлой лекции мы убедились, что нормализация (декомпозиция отношений) увеличивает целостность, но понижает производительность

На этой лекции посмотри на два подхода, позволяющие увеличить производительность

Индекс

Один из таких подходов - использование индекса

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

Поэтому, чтобы найти условного студента в файле при помощи условного двоичного поиска, нужно а) содержать файл сортированным, что дорого, и б) т. к. файлы на диске расположены блочно, то приходится прочитывать весь блок, что увеличивает время работы

А давайте придумаем некий индекс, который представим в виде двоичного дерева, в котором хранятся первичный ключ и адрес на место в диске. Помимо этого такой индекс мы можем размещать на оперативной памяти

Тут же можем выделить 3 типа индекса:

Первичный индекс - индекс, созданный по первичному ключу отношения, которое упорядочено по первичному ключу

И с первичным индексом можем найти недостаток: хранение отсортированного порядка отношения (дорого, но обеспечиваем дешевый джоин); и преимущество: скорость поиска

Индекс кластеризации - индекс, созданный по неключевому полю отношения, которое упорядочено по этому полю

Заметим, что индекс получается неплотным - он не указывает на каждый кортеж. Из-за этого отношение группируется в кластеры по значению избранного поля.

Вторичный индекс - индекс, построенный по полю не упорядоченного по нему отношения

Из определения очевидно, что поле должно быть уникальным ключом - отношение не упорядочено, значит, кластеров не будет.

Заметим, что при этом два индекса сразу мы не можем создать для одной таблицы - и на этом концепция индекса заканчивается

Индекс также различают по плотности на:

Плотный индекс - индекс, в котором одному узлу соответствует одна запись

Разреженный индекс - индекс, в которому одному узлу соответствуют несколько записей

А если мы начнем делать индекс для атрибута-строки, то мы неизбежно придем к хеш-фукнциям, и тут тоже есть свои нюансы, например, для электронных почтовых адресов используют хеш от реверса строки, чтобы не допускать естественную кластеризацию

Представление

Второй же подход - это представления

Допустим такую модель:

"Студент"

ИСУ ФИО N группы Форма обучения

"Группа"

N группы ОП

"Образовательная программа"

ОП Факультет

"Паспорт"

ИСУ Паспорт

Индексы в этом ситуации будут бесполезны

Появляется идея: что, если вместе с нормализованной моделью хранить и денормализованную:

ИСУ ФИО N группы Форма обучения ОП Факультет

Тут приходим к:

Представление - динамически сформированный результат одной или нескольких реляционных операций, выполненных с целью получения нового отношения

Представления делятся на материализованные и представления заменой

Материализованное представление хранится в памяти. В этом случае надо создавать некий таймер или триггер на пересоздание представления, НО:

  • нельзя это делать часто, иначе не получим выигрыш на производительность
  • нельзя делать редко - получится неконсисентность данных

По сути материализованное представление - это банальный кеш. И тут возникает проблема неактуальности кеша: допустим ситуацию, что база данных актуализируется ночью; студент в день комиссии утром подписывает заявление об академическом отпуске, а вечером комиссия, которая не знает о его уходе, отчисляет его🦆

Представление заменой хранится в виде запроса, на который в нужное время заменяется таблица, доступ к котором мы хотим получить.

Но, как мы знаем, дополнительные абстракции приводят к ухудшению производительности, но зато мы выигрываем в безопасности: мы можем отдать это представление другой конторе и выдать доступ к только нужным по нашему мнению полям

Представления могут быть обновляемыми и необновляемыми, но не все представления могут быть обновляемыми из-за race-condition. Хороший пример на эту тему - воскрешение студента: студент подал заявление на перевод между группами в июле, но эта транзакция перевода должна выполниться в сентябре, на комиссии его отчислили, но транзакция по переводу групп выполнилась после отчисления, и, таким образом, его зачислили обратно🦆

Но тем не менее также усложняется запись данных через представление - нам нужно знать его структуру

Здесь выделим преимущества представления:

  • Независимость данных - при рефакторинге базы данных бекенд не будет нуждаться в рефакторинге, так как он опирается на представление

  • Повышение защищенности данных - как в примерах выше

  • Снижение сложности доступа к данным - инженеры баз данных хранят эти сокральные знания об этой модели, и всем остальным разработчикам не надо спрашивать об этом их

И недостатки представления:

  • Ограниченные возможности обновления

  • Структурные ограничения - представления вводят ограничения на рефакторинг базы данных

  • Снижение производительности

И по большей части это все костыли, которые сломали невыполнимую идею Кодда. Но тем не менее все эти недостатки и преимущства - баланс, в котором мы ищем решение

Лекция 8. Надежность

На прошлой лекции велся разговор о производительности и то, каким способами она добивается (ну или нет)

На этой лекции поговорим о надежности, но казалось бы, что еще обсудить, если мы обсуждали нормализацию моделей данных. Но дело в том, что надежность - это обеспечение целостности не только в момент хранения данных

Различают два вида сохранности (целостности):

  1. Физическая сохранность - обеспечение сохранности данных в случае аппаратных и физических ошибок

  2. Логическая сохранность - обеспечение сохранности в ходе чтения и изменения данных

При этом мы пытаемся достичь надежности хранения (данные сохранились) и доступа (данные сохранились и к ним можно получить доступ)

Физическая сохранность

Чтобы достичь физической сохранности, нужно всего лишь воспользоваться простым советский методом: дублирование данных. Например, рассмотрим массив из 2 дисков - давайте один файл записывать параллельно целиком на два диска. В итоге мы, конечно же, не исключили аварию, но знатно уменьшили ее вероятность и получили массив RAID1

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

Можем сделать так: взять три диска, один из которых будет под избыточные данные; сами данные разделим на две части, которые параллельно будем записывать на два диска, а на избыточный диск записывать побитовый XOR этих двух частей. Таким образом, получается, что при отказе одного диска, мы можем восстановить данные. Помимо этого роль избыточного диска могут и принимают другие диски, чтобы балансировать нагрузку - мы получаем массив RAID5

Кроме этих двух типов RAID есть и другие, отличающиеся своей надежностью и количеством затраченных средств

Следующим шагом является создание системы хранения данных (СХД) - специального компьютера со своей операционной системой и десятками дисков, который анализирует, что ему приходит и куда это положить - например, более востребованные к доступу данные класть на более быстрый диск

Далее человечество пришло к дата-центрам - специальным зданиям, в которых в специальных условиях крутятся сотни болванок и хранят данные многих бизнесов. Дата-центры разделяют на тиры, которые раздает Uptime Institute, где 4-ый тир - самый крутой с самым большим временем безотказной работы

Логическая безопасность

Допустим, что мы работаем в банке:

Пользователь Остаток на счете
A 100
B 200

Чтобы пользователю A перевести пользователю B 50 шекелей, нужно совершить четыре (или больше) действия:

  1. Проверить, что у A есть 50 шекелей
  2. Проверить, что B живой, и его счет тоже живой
  3. Вычесть 50 шекелей у A
  4. Прибавить на счет B 50 шекелей

Заметим, что между 3 и 4 действиями база данных теряет свой инвариант - тогда объединим все эти действия в одну группу.

Транзакция - это последовательность действий с базой данных, в которой либо все действия выполняются успешно, либо не выполняется ни одно из них

Транзакция переводит базу данных из одного логически согласованное состояния в другое логически согласованное Результатом транзакции может быть либо совершение изменений (commit), либо откат к исходному состоянию (rollback)

Чтобы ваша последовательность действий называлась транзакцией, нужно соблюдение этих свойств ACID:

  • Atomicity - атомарность: транзакция неделима - либо выполняются все действия, либо ни одного

  • Consistency - согласованность: транзакция переводит одно согласованное состояние базы данных в другое согласованное состояние базы данных без соблюдения поддержки согласованности в промежуточных точках

  • Isolation - изоляция: если запущено несколько конкурирующих транзакций, то любой обновление, выполненное одной транзакцией, скрыто от других до ее завершения

  • Durability - долговечность: когда транзакция завершена, ее результаты сохраняются, даже если в следующий момент произойдет сбой

Ситуация: пользователи A и C захотели перевести пользователю B по 100 шекелей

Пользователь Остаток на счете
A 100
B 200
С 100

В итоге может произойти такая последовательность действий:

  • Пользователю A присвоили 0 шекелей
  • Пользователю С присвоили 0 шекелей
  • Пользователю B присвоили 300 шекелей (200 изначальных + 100 от A)
  • Пользователю B присвоили 300 шекелей (200 изначальных + 100 от C)

В итоге произошла гонка обновлений (race-condition) - вторая транзакция слишком рано прочитала баланс у пользователя B и изменила его баланс на 300, когда он и так уже был 300 в ходе работы первой транзакции. Это проблема получила название проблемы потерянного обновления

Решение - 1 уровень изоляции "Незавершенное чтение": требуем, что бы только одна транзакция могла записывать данные

Другой кейс: C решил перевести 100 шекелей к A, а A, получив от C деньги, захотел перевести 200 шекелей B

В итоге первая транзакция может где-то после начисления денег A откатиться, но вторая транзакция выполнилась до отката первой - у A уже нулевой баланс, поэтому у A в ходе отката получится -100

Возникает проблема грязного чтения, ее решение - 2 уровень изоляции "Завершенное чтение": если какая-то транзакция изменяет данные, то никакая другая не может их читать

Третий пример: наш банк зачисляет проценты от остатка на счету в конце месяца - есть необходимость прочитать всю таблицу, сгруппировать ее и сделать другую магию

Номер счета Пользователь Остаток на счете
123456 A 800
243698 A 200
190428 С 100

В этот момент, когда все счета A были уже прочитаны, происходит перевод, который меняет баланс пользователя A, после этого зачисляются проценты от остатка - но они выходят неактуальными

Произошла проблема неповторяемого чтения. Чтобы решить ее, обложим себя 3 уровнем изоляции - "Воспроизводимое чтение": если транзакция считывает данные, то никакая другая транзакция не может изменить их

Четвертый случай - пользователь A решил открыть новый счет:

Номер счета Пользователь Остаток на счете
123456 A 800
243698 A 100
190428 С 100
824082 A 1000

Расчет процентов начался перед созданием счета - транзакция не заблокировала действие на создание счета, поэтому начисленный процент опять остался неверным

Появилась проблема фантомного чтения и 4 уровень изоляции, который решает ее - "Сериализуемость" (или "Сериализация"): если транзакция выполняется к данным, то никакая другая транзакция не может изменять или добавлять записи, если они могут быть прочитаны изначальной транзакцией

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

Footnotes

  1. Таблицы из примера были созданы так:

    CREATE TABLE Employee (
    EmployeeID BIGINT PRIMARY KEY,
    FullName TEXT,
    DepartmentID BIGINT
);
CREATE TABLE Department (
    DepartmentID BIGINT PRIMARY KEY,
    DepartmentName TEXT,
    DirectorID BIGINT
);
INSERT INTO Employee VALUES 
    (1, 'Albert Eistein', 4), 
    (2, 'Ernest Rutherford', 5), 
    (3, 'Marie Curie', 10), 
    (5, 'Charles Darwin', 13), 
    (4, 'Igor Kurchatov', NULL);
INSERT INTO Department VALUES 
    (4, 'Theoretical Physics', 1), 
    (10, 'Chemistry', 3), 
    (13, 'Biology', 5),
    (11, 'Nuclear Physics', 2);
    ↩

  2. Несмотря на это, полусоединение можно реализовать в SQL при помощи INNER JOIN:

    SELECT *
FROM Employee
INNER JOIN Department
ON Employee.DepartmentID = Department.DepartmentID;

    На отношениях из примера получится такое полусоединение:

    EmplID FullName DepartID DepartID DepartName DirectorID
    1 Albert Einstein 4 4 Theoretical Physics 1
    2 Ernest Rutherford 4 4 Theoretical Physics 1
    3 Marie Curie 10 10 Chemistry 3
    5 Alexander Fleming 13 13 Biology 5
    ↩

  3. На самом деле синтаксис инструкции FROM немного шире: ↩