Формализация многомерного представления данных

Май 2000

Формализация многомерного представления данных

Максим Буркин

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

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

В основе технологии OLAP лежит интуитивно понятное человеку многомерное представление данных. В 1993 г. Кодд опубликовал труд под названием «OLAP для пользователей-аналитиков: каким он должен быть». В нем он изложил основные концепции оперативной аналитической обработки и определил 12 правил, которым должны удовлетворять продукты, предоставляющие возможность выполнения оперативной аналитической обработки.

Вот первое из этих правил (текст оригинала сохранен по возможности):

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

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

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

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

Введем символьное выражение гиперкуба:

где  — показатели гиперкуба,  — измерения гиперкуба.

Измерение гиперкуба — дискретное множество однотипных данных, образующих одну из граней гиперкуба:

 

где  — количество значений по измерению ,  — по , ...  — по измерению .

Количество элементов измерения есть мощность измерения.

Размерность гиперкуба — произведение мощностей его измерений:

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

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

Показатели гиперкуба — неизменный набор функций, характеризующий каждую элементарную ячейку гиперкуба.

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

Рисунок Гиперкуб данных баланса

Тогда, по нашим определениям,

 

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

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

 

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

 

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

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

Можно проиллюстрировать приведенное утверждение на следующем примере.

Допустим, существует полностью сформированный баланс банка за прошлый год, баланс за 250 дней, по 8 подразделениям и 1000 счетам. Балансовые данные находятся в многомерной базе данных — гиперкубе. Соответственно вес указанного гиперкуба 250x8x1000x4 = 8000000. Так как одна ячейка занимает 11 символов — 11 байт, то вся база занимает 88000000 байт, или  84 Mбайт. Допустим, по двадцати балансовым счетам за весь год оборотов по кредиту не было (это вполне реально, например, по счетам 91801, 91802, 91803, 60401 и т. п.), т. е. один из показателей в срезе гиперкуба равен 0. Тогда, проведя разложение гиперкубов, получаем два гиперкуба с весами:

250x8x980x4 = 7840000,
250x8x20x3 = 120000,
что в сумме составляет 7960000.

Соответственно объем занимаемого дискового пространства:

7960000x11 = 87560000 байт, или  83,5 Mбайт.

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

Теорема.

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

Доказательство.

Пусть имеется гиперкуб

 

где  — мощность k-го показателя.

Пусть срез по показателю  имеет вид

 

Тогда имеет место следующее разложение гиперкуба:

 

По определению весов имеем

 

Очевидно, что

Теорема доказана.

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

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

Об авторе:
Буркин Максим Игоревич — старший специалист отдела банковских технологий Тульского банка АК СБ РФ.