Сжатие избыточной информации

Какую структуру БД считать оптимальной?

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

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

Вернёмся к примеру с жителями… При ожидаемом реальном наличии большого числа пересечений в записях таблицы «Дома»…

 

Код дома	Номер	Улица	Город

 

Естественно разложить эту таблицу на несколько. Например, завести справочные таблицы «Улицы» и «Города» и добавить в таблицу «Люди» ссылки: код улицы, код города и поле «номер дома».

Улицы Города

 

Код	Название

Код	Название

 

города

люди

 

 

 

Другой вариант: добавить в таблицу «Улицы» ссылку на код города, в котором она находится и добавить в таблицу «Люди» коды улицы и дома.

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

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

Что мы делали с формальной точки зрения? Главной операцией реляционной теории (алгебры) является операция соединения (join) таблиц, или композиции отношений.

Соединением двух таблиц PT и CT по ключам PK и FK соответственно будет таблица.

PTÌX₁´…´X_n

CTÌY₁´…´Y_m

IÌX₁´…´X_n´Y₁´…´Y_m :

{<X₁…X_n, Y₁…Y_m>, <X₁…X­_n>ÎPT, <Y₁…Y_m>ÎCT, FK=PK}

Пример соединения таблиц «Люди» и «Дома» по ключу «Код города» - таблица с полной информацией о людях и их адресах.

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

 

Нормализация баз данных

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

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

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

Считаем, что поле Y зависит от поля X, если таблица не содержит пары записей с одним значением поля X, но разными значениями поля Y.

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

Третья нормальная форма: в записи нет транзитивных зависимостей, то есть полей, которые зависят от не ключевого поля.

Проиллюстрируем процесс нормализации на примере проектирования БД сделки.

 

продавец фамилия (паспорт)

покупатель фамилия (паспорт)

заказ стоимость

товар стоимость

 

Продавец/заказ: исполняет

Покупатель/заказ: делает

Заказ/товар: состоит

 

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

 

Покупатель/заказ

Продавец/заказ

 

покупатель продавец

 

 

заказ

 

 

заказ/товар ® состоит

 

покупатель – customer

продавец – employee

заказ – order

OrderId	Date	Prod_Id1	Amount	Price1	Prod_Id2

 

Такая структура невозможна при переменном количестве товаров в заказе. Но даже если известно максимальное количество, такая структура явно неэффективна в плане компактности хранения. А формально она противоречит первой нормальной форме.

Замечание. Нормальные формы – лишь ориентир при проектировании. На практике реально запрещается фиксировать в структуре таблицы отношения с переменной кардинальностью.

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

 

OrderId

ODate

Состоит

OrderId

ProdId

Amount

Price

 

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

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

 

N^o

OrderId

ProdId

Amount

Price

 

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