Математическое моделирование OLAP-куба в контексте агрегирования простых и иерархических измерений

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

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

СПИСОК ЛИТЕРАТУРЫ

1. Евреинов Э.В. Однородные вычислительные системы, структуры и среды. - М.: Радио и связь, 1981. - 208 с.

2. Каляев И.А., Левин И.И., Семерников Е.А., Шмойлов В.И. Реконфигурируемые мультиконвейерные вычислительные структуры. - Ростов на Дону: ЮНЦ РАН, 2008. - 393 с. URL: http://parallel.ru/FPGA/papers/rmvs.pdf (дата обращения: 31.03.2010).

3. Giefers H., Platzner M. A Many-Core Implementation Based on the Reconfigurable Mesh Model // IEEE Xplore DIGITAL LIBRARY. 2010. URL: http://ieeexplore.ieee.org/Xplore/defdeny.jsp?url= http://ieeexplore.ieee.org/stamp/stamp.jsp%3Ftp%3D%26arnum-ber%3D4380623&denyReason=-134&arnumber=4380623&pro-ductsMatched=null (дата обращения: 31.03.2010).

4. Ячейка однородной структуры для решения дифференциальных уравнений в частных производных: а.с. 783811 СССР. № 2727694/18-24; заявл. 21.02.1979; опубл. 30.11.1980, Бюл. № 44. - 2 с.

5. Ячейка однородной структуры для решения дифференциальных уравнений в частных производных: пат. 2359322 Рос. Федерация. № 2007141832/09; заявл. 12.11.07; опубл. 20.06.09, Бюл. № 17. - 6 с.

6. Каляев А.В. Теория цифровых интегрирующих машин и структур. - М.: Советское радио, 1970. - 472 с.

7. Лисейкин В.Д. Передовые технологии построения разностных сеток // РФФИ. 2010. URL: http://www.rfbr.ru/de-fault.asp?doc_id=17662 (дата обращения: 31.03.2010).

8. Цифровые базовые матричные кристаллы. ОАО «Ангстрем» // 2010. URL: http://www.angstrem.ru/catalogue/ele-ment.php?IBLOCK_ID=2&SECTION_ID = 5&ELE-MENT_ID=120 (дата обращения: 31.03.2010).

Поступила 31.03.2010 г.

УДК 004.032.6;004.357

МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ OLAP-КУБА В КОНТЕКСТЕ АГРЕГИРОВАНИЯ ПРОСТЫХ И ИЕРАРХИЧЕСКИХ ИЗМЕРЕНИЙ

В.П. Кулагин, В.Т. Матчин*

Государственный научно-исследовательский институт информационных технологий и телекоммуникаций, г. Москва

E-mail: kvp@informika.ru

*Московский государственный институт радиотехники, электроники и автоматики

E-mail: matchin@mirea.ru

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

Ключевые слова:

Хранилище данных, база знаний, агрегирование данных, онтология, многомерный куб, иерархическое измерение. Key words:

Databank, knowledge base, data aggregation, ontology, multidimensional cube, hierarchical measurement

Известно, что основная цель управления знаниями - сделать знания доступными и повторно используемыми.

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

нилищ данных, чтобы использовать накопленные знания.

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

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

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

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

Разведка знаний - быстро развивающееся направление, использующее методы искусственного интеллекта, математики и статистики для извлечения знаний из хранилищ данных. Г. Пятецки-Ша-пиро и В. Фролей определяют термин «разведка знаний» как «нетривиальное извлечение точной, ранее неизвестной и потенциально полезной информации из данных». Метод включает инструментарий и различные подходы к анализу как текста, так и цифровых данных.

Метод в его современном прочтении опирается на использование в моделировании ОЬЛР-куба таких понятий, как онтология, показатель, измерение, количество сочетаний агрегатов и некоторых других терминов.

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

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

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

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

Член измерения - отдельная строка или столбец таблицы, содержащая показатели.

Количество сочетаний агрегатов

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

Общее количество сочетаний агрегатов для т измерений рассчитывается следующим образом:

А = Пп >

х-1 у=1

где х=1,2,...,т-1 - порядковый номер измерения, за исключением одного, по которому рассчитывается сумма; пх - указывает количество членов в х-м измерении; у - количество элементов в сочетании.

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

А = (пк ± /)П«х,

X=1 у=1

где I - количество появляющихся или исчезающих членов измерений.

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

А = (п ± /1)(п2 ± /2)...(п ± /)]ГСпут.

у=1

Формула (*) и ее производные формулы верны при любых положительных целых п.

Количество агрегатов

В случае трех измерений п1, п2, п3 количество агрегатов можно представить так:

п1= п010 п2 п001 п3= п100.

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

А *=п1*п2+п2*п3+п1*п3,

п1*п2=п0Ц п2*пз= п101 п1*пз= nllo,

или то же самое можно записать в форме двоичных индексов:

А = «011+«101+«110.

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

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

т-т»2

Хст

г-1

А = X «ггг х х , ¡=1

где х1х2х3...х!...хт - двоичный вектор, состоящий из т двоичных разрядов.

Ограничение т-г>2 указывает на необходимость двух и более измерений для агрегации. Верхний предел суммы для четырех измерений будет выглядеть следующим образом:

С41+С42, для пяти: С51+С52+С53.

Случай иерархических измерений

Иерархию можно представить как объединение членов измерений в одно множество.

В этом случае для каждого к-го измерения существует 4 уровней иерархии. Общее количество членов к-го измерения состоит из суммы всех членов этого измерения

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

А = Х П«х£су

=Х>

Количество агрегатов

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

к

ё = П т1-

1=1

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

А' = («11 + «12 + . . . + «1т)* («21 + «22 + • • •+ «2т ) * • • •

• • ^(«к1 + «к2 +• • • + «кт ) •

Количество сочетаний агрегатов

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

=1 у=1

и=Ш+Ш+... - множество всех иерархических уровней по всем измерениям

Формула является производной по отношению к формуле (*).

Количество информации

Каждый член измерения многомерного куба 1! вносит в модель, описывающую ОЬЛР-куб, дополнительную информацию о состоянии системы. Сумма всех членов измерений Ь будет представлять состояние системы

Ь = Х 1г

I

Тогда количество информации системы (по формуле Хартли):

I = 1СЕ2 Ьр,

где р - коэффициент эмерджентности Хартли.

Учитывая, что возможны смешанные состояния, являющиеся одновременной реализацией состояний системы «из Ь по т», всего возможно СЬт состояний системы, являющихся сочетаниями исходных состояний. Тогда формулу для количества информации системы можно представить в виде:

м

I = 1се2 X ст, при м < Ь.

т=1

При М=1 формула приобретает вид классической формулы Хартли. Остальные слагаемые при М>1 дают дополнительное количество информации за счет наличия внутренних взаимосвязей системы.

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

I = 10М2(СЬ + сЬ+••• + ст )•

Дополнительная информация является информацией о внутренних взаимосвязях системы, состоящей из ряда подсистем различных уровней сложности. При М=Ь:

м

X сьт = 2Ь -1.

т=1

Это выражение дает оценку максимального количества информации, которое может содержаться в системе с учетом взаимосвязей различных подсистем. Подставив в качестве подлогарифмического выражения значение 2Ь-1 и учитывая, что Ь-^да, получим, что количество информации стремится к Ь:

м

I = Хст = Ь^ 10Е2(2ь -1) ^ Ь.

т=1

Приравняем два выражения формулы Хартли:

т=1

м

I = 1об2 ьр = 1об2 £ ст.

т =1

Отсюда найдем коэффициент эмерджентности Хартли р:

м

^ £ ст р =-т=1—,

1об2 Ь

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

Применив полученное значение для коэффициента эмерджентности, получим:

м

1°Е2 £ ст

т=1

I = 1о§2 Ь 1062 Ь .

Учитывая, что получим:

L

I = log2 Llofe L = L.

Следовательно, количество информации в OLAP-кубе равно количеству членов измерения.

Коэффициент эмерджентности Хартли отражает уровень системности объекта и изменяется от

L

1 (системность минимальна) до --- (систем, log2L ность максимальна).

Выводы

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

СПИСОК ЛИТЕРАТУРЫ

1. Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. Определения, теоремы, формулы / под общей ред. И.Г. Арамановича. - М.: Наука, 1974. - 832 с.

2. Выгодский М.Я. Справочник по элементарной математике. -М.: Физматгиз, 1962. - 420 с.

Поступила 25.01.2010 г.

УДК 004.657

СЕМАНТИКО-ЭНТРОПИЙНОЕ РЕГУЛИРОВАНИЕ ИНФОРМАЦИОННОГО МОРФИЗМА РЕАЛИЗАЦИЙ xOLAP

А.А. Миронов, А.С. Сигов

Московский государственный институт радиотехники, электроники и автоматики

E-mail: mironov@mirea.ru

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

Ключевые слова:

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

физм.

Key words:

On-line analyticalprocessing, semantic break, entropy control, information morphism.

Разнообразие версий OLAP достаточно велико и расширяется. Модели OLAP обретают новые классификационные признаки, свойства, изменяющие их особенности, достоинства и недостатки, впрочем, оцениваемые в зависимости от специфики решаемых задач. Так, наряду с такими известными модификациями как ROLAP, MOLAP и HOLAP [1], в последние годы появились и находят широкое применение SOLAP (Spatial On-Line Analytical Processing) - пространственная аналитиче-

ская обработка, предназначенная для изучения пространственных данных, объединяющая понятия из существенно отличающихся друг от друга сфер знаний, а именно географических информационных систем и OLAP, разработанная для интерактивного и быстрого анализа больших объемов данных; R-ROLAP (Real-time ROLAP) - OLAP реального времени, в отличие от ROLAP в R-ROLAP для хранения агрегатов не создаются дополнительные реляционные таблицы, а агрегаты рассчитыва-