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

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

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

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

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

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

Улицы Города

города

люди

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

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

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

Что мы делали с формальной точки зрения? Главной операцией реляционной теории (алгебры) является операция соединения (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}

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

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