Требования нормальных форм базы данных

Зачем нормализовать датасет для Data Mining и Machine Learning

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

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

После нормализации все числовые значения входных признаков будут приведены к одинаковой области их изменения – некоторому узкому диапазону. Это позволит свести их вместе в одной модели Machine Learning и обеспечит корректную работу вычислительных алгоритмов [1.

Нормализованные данные в диапазоне

Практическим приемам Feature Transformation посвящена наша следующая статья, где мы рассказываем, как именно выполняется нормализация данных: формулы, методы и средства. Все эти и другие вопросы Data Preparation рассматриваются в нашем новом курсе обучения для аналитиков Big Data: подготовка данных для Data Mining. Оставайтесь с нами!

Смотреть расписание
Записаться на курс

Источники

1. https://wiki.loginom.ru/articles/normalization.html
2. http://molbiol.ru/forums/lofiversion/index.php/t460759.html
3. https://btimes.ru/dictionary/normirovanie
4. https://neuronus.com/theory/nn/925-sposoby-normalizatsii-peremennykh.html
5. https://habr.com/ru/company/ods/blog/325422

Перед началом…

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

Избыточность

Одним из основных моментов, который нужно учитывать при проектировании таблиц — уменьшение пространства для хранения данных. Таблицы должны быть спроектированы таким образом, чтобы повторяющиеся данные хранились отдельно, в одной или нескольких таблицах. Хранение повторяющихся данных не только требует больше места, но также приводит к более серьезным проблемам.

Таблица с данными о сотрудниках из разных отделов, содержит избыточные данные

Обратите внимание, что данные в полях DNAME и DNO неоднократно повторяются в таблице. Такой вид избыточности данных приводит к аномалиям обновления, вставки и удаления

Аномалии вставки

Если нам понадобится добавить в таблицу информацию о новом сотруднике, который не «привязан» к какому-либо отделу, данные об отделе в добавляемой записи окажутся пустыми, а это явно неоправданная трата пространства. Кроме того, при вставке данных нового сотрудника, скажем, в отдел с идентификатором ‘4’, другие поля, относящиеся к отделу, также должны будут повториться. Пример: отдел 4, поле DNAME должно содержать значение ‘Administrator’, а поле MGR_SSN — содержимое должно быть равно ‘234567890’.

Аномалии обновления

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

Аномалии удаления

Предположим, мы удалим информацию об одном сотруднике, например, последнюю запись из представленной выше таблицы. Только у этой записи значение в поле DNO равно ‘1’, в результате этого действия получится, что информация об отделе будет потеряна. Это нелепо, потому что мы хотим удалить информацию о сотруднике, а не обо всем отделе.

Функциональные зависимости

Функциональные зависимости — основа нормализации баз данных. Под функциональной зависимостью подразумевается зависимость значения одного поля (столбца) от другого. Например, по значению поля SSN определенного работника, мы сможем найти его адрес. Это значит, что поле адрес функционально зависимо от поля SSN. Символическая запись этой зависимости выглядит так:

{SSN} → {ADDRESS}

Аналогично,

{SSN} → {ENAME, ADDRESS} {SSN, DNO} → {MGR_SSN}

Когда значение одного или нескольких полей точно идентифицируют запись, значение такого поля называется «первичным ключом».

Инфологическое проектирование

Инфологическое проектирование

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

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

Один из популярных способов построения инфологической модели – построение ER-диаграмм.

ER-диаграммы

В отличие от диаграмм атрибутов, ER-диаграммы, кроме непосредственно атрибутов, включают так же в явном виде “сущности” и “связи” между ними, откуда, собственно, и происходит название: entity-relationship diagram, или диаграмма сущности-связи.

И сущности, и связи могут обладать набором атрибутов. Сущности без атрибутов – явление достаточно бессмысленное, как Кантовская “вещь в себе”. Связи без атрибутов – явление, напротив, весьмя распространенное.

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

В наиболее распространенной нотации, атрибуты обозначаются овалами, сущности – прямоугольниками, а связи – ромбами.

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

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

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

Рассмотрим ER-диаграмму для примера с теннисными кортами.

Нормальные формы.

Правила нормализации, применяемые к таблице, уменьшают проблемные области, «поднимая» таблицы на более высокий уровень согласованности данных, особенно в процессе добавления, обновления и удаления записей. Первая нормальная форма (1NF) — является первым правилом, вторая — вторым и тд. Давайте рассмотрим эти правила подробнее.

Первая нормальная форма (1NF)

Первая нормальная форма основана на атомарности значений полей в таблице. Имеется ввиду, что в поле должна храниться только какая-либо одна сущность. Например, в представленной ниже таблице к записи о сотруднике «привязано» несколько телефонных номеров. Это результат ошибок в проектировании.

Вместо этого, мы должны разместить данные в таблице следующим образом:

В результате мы получили много записей со значением NULL, более того, мы не можем добавить другой номер телефона. Лучше разделим эту таблицу на 2, так, как показано ниже.

Вторая нормальная форма (2NF)

Вторая нормальная форма основана на идее полной функциональной зависимости, при условии, что таблица находится в первой нормальной форме (1NF). Сейчас нужно удалить все не ключевые значения, которые не имеют полной зависимости от значения первичного ключа. Например:

В таблице выше, существуют следующие зависимости:

{SSN} → {EMPLOYEE_NAME}{SSN} → {PROJ_HOURS}

Также,

{PROJECT_NO} → {PROJECT_NAME}{PROJECT_NO} → {PROJECT_HOURS}

Это грубое нарушение 2NF, потому что значение полей PROJECT_HOURS и PROJECT_NAME в каждой записи функционально зависимы от PROJECT_NO. Кроме того, EMPLOYEE_NAME и PROJ_HOURS однозначно определяются значением поля SSN. Чтобы привести данные к 2NF в данном случае мы можем «разложить» таблицу EMPLOYEE_PROJECT на несколько таблиц:

Третья нормальная форма (3NF)

Чтобы привести таблицу в третью нормальную форму (3NF), она должна находится во второй нормальной форме (2NF) и, самое главное, не должна содержать данные с транзитивными зависимостями. Транзитивная зависимость — это случай, когда X→Y, Y→Z, X→Z. Это значит, что любое не ключевое поле не должно быть зависимо от поля, которое не является первичным ключом таблицы. Например:

Здесь, существуют зависимости:

{SSN} → {EMPLOYEE_NAME}
{SSN} → {BIRTH_DATE}
{SSN} → {DEPT_NAME}
{SSN} → {DEPT_ADDRESS}

Однако, аномальной является следующая зависимость:

{DEPT_NAME} → {DEPT_ADDRESS}

потому что DEPT_NAME не является ключом. Мы можем устранить эту проблему, разделив таблицу на 2 таблицы.

Нормальная форма Бойса-Кодда (BCNF)

В большинстве случаев, BCNF — это эквивалент 3NF. Правда эта форма строже, чем третья нормальная форма. Любая таблица, находящаяся в BCNF, находится в 3NF, но не наоборот.

BCNF — это нетривиальная функциональная зависимость X→Y в которой X, находящийся в ее левой части, является первичным ключом.

Давайте разберемся в этом на примере нескольких таблиц. Некоторые из них находятся одновременно и в 3NF и в BCNF, другие же находятся в3NF, но не в BCNF.

{SSN} → {EMPLOYEE_NAME}
{SSN} → {BIRTH_DATE}

В таблице EMPLOYEE первичным ключом является поле SSN. Это нетривиальная функциональная зависимость, таблицы EMPLOYEE, в левой части которой находится атрибут SSN. Так как SSN является первичным ключом, функциональная зависимость не нарушает условий BCNF.

{PROJECT_NO} → {PROJECT_NAME}
{PROJECT_NO} → {PROJECT_DURATION}

Таблица PROJECT также находится в BCNF.

{DEPT_NO, SSN} → {PROJECT_NO, DURATION}
{PROJECT_NO} → {DURATION, DEPT_NO}

Однако, PROJECT_INFO не находится в BCNF, потому что PROJECT_NO не является первичным ключом. Не может быть пары строк, представляющих 2 разных SSN, работающих в том же PROJECT_NO и DEPT_NO. Например:

Функциональная зависимость PROJECT_NO → DURATION нетривиальна. Таким образом, таблица не удовлетворяет определению BCNF. Мы можем устранить эту проблему, если перепроектируем эту таблицу таким образом, чтобы все полученные в результате таблицы приняли BCNF. Например:

Рекомендации по использованию в средах отчетности

Хотя 3NF идеален для машинной обработки, сегментированный характер модели данных может быть трудным для восприятия человеком-пользователем. Аналитика с помощью запросов, отчетов и информационных панелей часто упрощалась с помощью модели данных другого типа, которая обеспечивала предварительно рассчитанный анализ, такой как линии тренда, расчеты за период до даты (за месяц, за квартал, за год до даты). на сегодняшний день), кумулятивные вычисления, базовая статистика (среднее, стандартное отклонение, скользящие средние) и сравнения за предыдущие периоды (год назад, месяц назад, неделя назад), например, размерное моделирование и не только размерное моделирование, сглаживание звезд с помощью Hadoop и анализ данных .

Демормализация в базе данных: «звезда» и «снежинка»

Как можно понять из вышеприведённых примеров, основными целями нормализации являются:

• устранение избыточности при хранении данных, приводящей к увеличению размера БД;
• исключение необходимости модификации данных в связных таблицах для минимизации времени и операций, проводящихся в одной транзакции. Или, как выражаются специалисты, уменьшить толщину транзакции, потому что толстые транзакции мешают при многопользовательской работе взаимными блокировками и увеличением времени отклика системы. Речь об этом пойдёт в отдельной главе.

Но список заявленных целей касается приложений транзакционных.

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

пример

Рассмотрим следующий пример:

Варианты доставки пиццы

Ресторан	Разнообразие пиццы	Зона доставки
А1 Пицца	Толстая корка	Springfield
А1 Пицца	Толстая корка	Shelbyville
А1 Пицца	Толстая корка	Столица
А1 Пицца	Фаршированная корочка	Springfield
А1 Пицца	Фаршированная корочка	Shelbyville
А1 Пицца	Фаршированная корочка	Столица
Элитная пицца	Тонкая корка	Столица
Элитная пицца	Фаршированная корочка	Столица
Пицца Винченцо	Толстая корка	Springfield
Пицца Винченцо	Толстая корка	Shelbyville
Пицца Винченцо	Тонкая корка	Springfield
Пицца Винченцо	Тонкая корка	Shelbyville

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

Таблица не имеет неключевых атрибутов, потому что ее единственный ключ — {Ресторан, Разнообразие пиццы, Зона доставки}. Следовательно, он соответствует всем нормальным формам вплоть до BCNF. Если мы предположим, однако, что на разновидности пиццы, предлагаемые рестораном, не влияет зона доставки (т. Е. Ресторан предлагает все разновидности пиццы, которые он готовит, во все области, которые он поставляет), то он не соответствует 4NF. Проблема в том, что в таблице есть две нетривиальные многозначные зависимости от атрибута {Restaurant} (который не является суперключом). Зависимости:

• {Restaurant} {Pizza Variety}↠{\ displaystyle \ twoheadrightarrow}
• {Restaurant} {Delivery Area}↠{\ displaystyle \ twoheadrightarrow}

Эти нетривиальные многозначные зависимости от не суперключей отражают тот факт, что разновидности пиццы, которые предлагает ресторан, не зависят от областей, в которые ресторан доставляет. Такое положение дел приводит к избыточности в таблице: например, нам трижды говорят, что A1 Pizza предлагает фаршированную корочку, и если A1 Pizza начнет производить пиццу с сырной корочкой, нам нужно будет добавить несколько строк, по одной для каждой из A1 Pizza. зоны доставки. Более того, ничто не мешает нам сделать это неправильно: мы можем добавить строки Cheese Crust для всех областей доставки A1 Pizza, кроме одной, тем самым не соблюдая многозначную зависимость {Restaurant} {Pizza Variety}.
↠{\ displaystyle \ twoheadrightarrow}

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

Разновидности по ресторанам

Ресторан	Разнообразие пиццы
А1 Пицца	Толстая корка
А1 Пицца	Фаршированная корочка
Элитная пицца	Тонкая корка
Элитная пицца	Фаршированная корочка
Пицца Винченцо	Толстая корка
Пицца Винченцо	Тонкая корка

Районы доставки по ресторану

Ресторан	Зона доставки
А1 Пицца	Springfield
А1 Пицца	Shelbyville
А1 Пицца	Столица
Элитная пицца	Столица
Пицца Винченцо	Springfield
Пицца Винченцо	Shelbyville

Напротив, если бы разновидности пиццы, предлагаемые рестораном, иногда действительно менялись от одной зоны доставки к другой, исходная таблица из трех столбцов удовлетворяла бы требованиям 4NF.

Рональд Феджин продемонстрировал, что достичь 4НФ всегда возможно. Теорема Риссанена также применима к многозначным зависимостям .

Алгоритмы, основанные на расстоянии

Стандартизация на основе дистанционных кластерных алгоритмов, таких как K-mean и K-NN, очень вероятно Алгоритм кластеризации должен рассчитывать расстояния между записями. Наиболее распространенное расстояние — это евклидово расстояние:

расстояние между i и j

Очевидно, что функция масштабирования изменит числовые расстояния между узлами.

Эксперимент:

Создайте набор данных, используя следующий код:

def random_2D_data(x,y,size):    x = (np.random.randn(size)/3.5)+x    y = (np.random.randn(size)*3.5)+y    return x,yx1,y1 = random_2D_data(2,20,50)x2,y2 = random_2D_data(2,-20,50)x3,y3 = random_2D_data(-2,20,50)x4,y4 = random_2D_data(-2,-20,50)x = np.concatenate((x1,x2,x3,x4))y = np.concatenate((y1,y2,y3,y4))

Кластеризация данных с использованием K-mean:

кластеризация без какого-либо масштабирования

Однако одно и то же для стандартизированных данных дает совершенно другой результат:

пострадавший результат

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

Стандартизация дает «равные» соображения для каждой функции.

Например, X имеет две функции x1 и x2

Если вычислить евклидово расстояние напрямую, узлы 1 и 2 будут дальше друг от друга, чем узлы 1 и 3. Однако узел 3 полностью отличается от 1, тогда как узлы 2 и 1 отличаются только по признаку 1 (6%), и доля та же самая особенность 2. Это потому, что особенность 1 — особенность ‘VIP’, доминирующая над результатом с его большим численным значением.

Поэтому, если мы не знаем, какие функции являются «бриллиантовыми», а какие «коралловыми», то хорошей практикой является их одинаковое использование с использованием стандартизации.

Проецирование функциональных зависимостей

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

Предположим, что имеется исходное отношение \(R\) с множеством ФЗ \(F\), и пусть \(S\) – некая проекция отношения \(R\): \ где A – некое множество атрибутов.

Тогда, множество \(G\) ФЗ, которые останутся в \(S\), это ФЗ, которые:

1. Следуют из \(F\)
2. Включают только атрибуты, принадлежащие \(A\)

Вполне вероятно, что множество всех ФЗ такого рода избыточно (не минимально). Сложность алгоритма поиска ФЗ отношения \(S\) в худшем случае экспоненциально зависит от количества атрибутов в \(A\).

Для нахождения всех ФЗ можно применять замыкание атрибутов из \(A\) по \(F\). Следует сделать два достаточно очевидных замечания:

• Замыкания пустого множества и множества всех атрибутов не приводят к получению нетривиальных ФЗ
• Если \(A \subset X^+\), то построение замыканий для надмножеств \(X\) не даст новых нетривиальных ФЗ в силу правила дополнения.

Так же понятно, что для любого замыкания \(X^+\), существуют ФЗ вида \(X \to B\), где \(B \subset X^+\).

Таким образом, мы можем начать с построения замыканий для единичных множеств атрибутов, и добавить все следующие из них ФЗ к множеству ФЗ \(G\), если они содержат только атрибуты из \(A\), а затем, при необходимости, построить замыкания для множеств атрибутов большей размерности.

Пример:

Пусть отношение \(R(A,B,C,D)\) имеет следующие ФЗ:

• \(A \to B\)
• \(B \to C\)
• \(C \to D\)

Пусть теперь мы получаем проекцию \(S = \pi_{A,C,D} R\). Найдем ФЗ \(G\) отношения \(S\).

Для этого, построим замыкания для всех атрибутов отношения \(S\) по \(F\). Поскольку \(B\) не входит в отношение \(S\), его замыкание не даст нам ФЗ, входящих в \(G\). \ \ \

Можем заметить, что \({A,C,D} \subset {A}^+\), соответственно, рассмотрение надмножеств \({A}\) не имеет смысла. Следовательно, единственное неединичное множество атрибутов, требующее рассмотрения это \

Запишем множество нетривиальных ФЗ \(S\), получающиеся из этих замыканий: \ \ \

Теперь найдем минимальное множество ФЗ. По правилу транзитивности, ФЗ \(A \to D\) следует из двух других, поэтому его можно исключить. В итоге, получаем минимальное множество ФЗ \(S\): \ \

Логическое (даталогическое) проектирование

Логическое проектирование

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

На этапе логического проектирования учитывается специфика конкретной модели данных, но может не учитываться специфика конкретной СУБД.

Переход от ER-диаграмм к ФЗ

ER-диаграммы вполне естественным образом могут быть преобразованы к ФЗ.

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

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

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

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

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

Таким образом:

1. Каждая сущность \(E\) преобразуется к ФЗ вида \ где \(K_E\) – множество ключевых (идентифицирующих) атрибутов сущности \(E\), а \(A_E\) – множество всех атрибутов сущности \(E\).
2. Каждая связь \(R\) между сущностями \(E_1,\ldots,E_n\), входящими в связь многократно и \(S_1,\ldots,S_m\), входящими в связь однократно, преобразуется к ФЗ вида \ где \(K_i\) – ключи соответствующих сущностей, \(A_R\) – атрибуты связи, и ФЗ вида \.

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

Это связано с тем, что связь многие-ко-многим является нефункциональной зависимостью. Решением этой проблемы может быть ввод фиктивного атрибута с пустым доменом, скажем, \(\theta\), уникального для данной связи. Это позволит формально анализировать функциональные зависимости для – фактически – неопределенной функции.

Диаграммы атрибутов

Кроме непосредственной записи ФЗ в столбик, существует более наглядный способ представления ФЗ отношений. Он так же может использоваться для нормализации отношения по крайней мере до 3НФ.

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

Например, построим диаграмму атрибутов для нашего примера с теннисными кортами.

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

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

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

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

Двойной линией обозначены внешние ключи.

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