ALGORITHMS OF COMPOSITION OF THE INTEGRAL OLAP-MODEL IN OBJECT DOMAIN

Abstract

The algorithms of composition of an integral OLAP-model based on the search of cube-concepts and composition of concept lattice of OLAP- cubes are described. Suggested algorithms are supplemented for integral OLAP- model of scientific activity of an organization.

Full Text

Эффективность оперативной аналитической обра- ботки данных на основе технологии OLAP (On-Line Analytical Processing) во многом определяется адек- ватностью модели предметной области [1]. Как пра- вило, для оперативной аналитической обработки дан- ных создается набор локальных OLAP-моделей, пред- ставляющий собой фрагментарную аналитическую модель предметной области [2–4]. С точки зрения теории и практики интересно построение интеграль- ной аналитической модели, объединяющей множест- во частных OLAP-моделей, позволяющей манипули- ровать всеми аспектами и характеристиками анализи- руемого процесса и охватывающей максимальное число решаемых аналитических задач. Для построения интегральной аналитической мо- дели предметной области предложен метод концепту- ального OLAP-моделирования на основе анализа формальных концептов, позволяющий строить инте- гральную OLAP-модель предметной области в виде формальной решетки многомерных кубов [5]. Реали- зация предложенного метода требует разработки ал- горитмов поиска кубов-концептов на основе контек- ста предметной области и построения концептуальной решетки OLAP-кубов. Существующие на сегодняшний день алгоритмы генерации формальных концептов подробно рассмот- рены в работах [6–9]. Как правило, эти алгоритмы разработаны без учета требований быстродействия и не ориентированы на обработку объектов OLAP- анализа. В данной работе предлагаются алгоритм поиска кубов-концептов и алгоритм построения концепту- альной решетки кубов, позволяющие формировать интегральную OLAP-модель предметной области на множестве всех объектов анализа. Свойства концеп- туальной решетки дают возможность оперировать всеми объектами анализа и выявлять аналитические зависимости, что повышает эффективность оператив- ной аналитической обработки данных. Метод концептуального OLAP-моделирования предметной области. Метод концептуального OLAP- моделирования основан на интеграции технологии оперативной аналитической обработки многомерных данных и анализа формальных концептов [5; 10; 11]. Согласно предложенному методу, интегральная OLAP-модель предметной области представляет со- бой концептуальную решетку многомерных кубов. Основу интегральной модели составляет множество объектов оперативной аналитической обработки дан- ных: множество показателей F = {f1, f2, …, fm} и мно- жество измерений D = {d1, d2, …, dn}. Количествен- ные характеристики анализируемого процесса обра- зуют множество показателей, аспекты анализа пред- метной области образуют множество измерений. * Работа выполнена при финансовой поддержке гранта ФЦП «Научные и научно-педагогические кадры инновационной России на 2009−2013 годы» (ГК № 02.740.11.0621 от 29 марта 2010 г.). 49 Математика, механика, информатика Между элементами множеств F и D определяется отношение сопоставимости R – возможность совме- стной аналитической обработки показателей и изме- рений; R ⊆ F × D, (fi, dj) ∈ R, если показатель fi может быть проанализирован по измерению dj. Тройка (F, D, R), в соответствии с методами анализа фор- мальных концептов [12], представляет собой фор- мальный контекст K. Формальный контекст отражает знания эксперта об объектах анализа предметной об- ласти и о возможности их совместной аналитической обработки. На основе формального контекста K определяется множество кубов-концептов по признаку сопостави- мости объектов анализа. Для произвольных X ⊆ F и Y ⊆ D определяется операция «штрих» следующим образом: X&apos; = {d ∈ D | ∀f ∈ X (fRd)}; Y&apos; = {f ∈ F | ∀d ∈ Y (fRd)}. Пара (A, B), где A ⊆ F, B ⊆ D такие, что A = B&apos; и B = A&apos;, называется кубом-концептом контекста K. Множество A состоит из показателей одинаковой размерности, которые могут быть проанализированы по всем измерениям из B. Пара (A, B) – многомерный куб, полный относительно добавления показателей той же размерности и состава измерений. Это означа- ет, что невозможно включить в такой OLAP-куб до- полнительный показатель без уменьшения числа из- мерений, т. е. в рамках построенного формального контекста не существует других показателей, сопос- тавимых с тем же набором измерений. Множество показателей A представляет объем куба-концепта, а множество измерений B – содержание куба-концепта. Множество всех кубов-концептов частично упоря- дочено отношением подкуб-надкуб: (A1, B1) < (A2, B2) если A1 ⊆ A2 и B2 ⊆ B1. В этом случае будем говорить, что (A1, B1) – подкуб (A2, B2), а (A2, B2) – надкуб (A1, B1). Множество показателей надкуба включает множество показателей подкуба, а, в свою очередь, множество измерений подкуба включает множество измерений надкуба. Упорядоченное отношением под- куб-надкуб множество всех кубов-концептов образует решетку OLAP-кубов, которая представляет собой интегральную OLAP-модель предметной области. Для реализации метода концептуального OLAP- моделирования разработаны алгоритмы поиска кубов- концептов на основе контекста предметной области и построения концептуальной решетки OLAP-кубов. Алгоритм поиска кубов-концептов на основе контекста предметной области. Алгоритм поиска кубов-концептов на основе контекста предметной области представляет собой итеративную реализацию метода Крайеса [6]. Алгоритм поиска кубов-концептов заключается в пошаговом сравнении объемов ранее обнаруженных кубов-концептов с множеством показателей, доступ- ных для совместной аналитической обработки с каж- дым из измерений контекста. Рассмотрим блок-схему алгоритма поиска кубов-концептов на основе контек- ста предметной области (рис. 1). На первом шаге алгоритма множество кубов- концептов B (K) содержит точную верхнюю границу множества кубов-концептов (супремум) – куб- концепт (F, Ø), где F – множество всех показателей контекста K. Затем путем перебора измерений dj из D определя- ется множество показателей {dj}&apos;, доступных для со- вместной аналитической обработки с каждым измере- нием dj, и сравнивается с объемом Ak куба-концепта (Ak, Bk) из B (K), где k = 1,|B (K)|, где |B (K)| – мощ- ность множества B (K). При этом индекс j определяет- ся, как max {j | dj ∈ Bk} + 1 – следующий за макси- мальным индексом измерений из содержания Bk куба- концепта (Ak, Bk). Если сформированный объем {dj}&apos; и объем Ak существующего куба-концепта не пересекаются ({dj}&apos; ∩ Ak = Ø), то рассматривается следующее изме- рение. Если объемы совпадают ({dj}&apos; ∩ Ak = Ak), то содержание Bk куба-концепта (Ak, Bk) дополняется из- мерением dj и алгоритм переходит к рассмотрению следующего измерения. Процесс добавления измере- ний к содержанию ранее обнаруженного куба- концепта называется наполнением куба-концепта. В случае когда объемы не совпадают и их пересе- чение не пусто, формируется потенциально новый куб-концепт (Anew, Bnew), где Anew = {dj}&apos; ∩ Ak, Bnew = dj и алгоритм переходит к проверке уникальности най- денного куба-концепта. Для проверки уникальности куба-концепта, путем перебора di из D определяется множество показателей {di}&apos;, доступных для совместной аналитической обра- ботки с каждым измерением di, и сравнивается с объ- емом Anew потенциально нового куба-концепта. Ин- декс i = 1, j − 1 при условии, что di ∉ Bk. Если все показатели Anew могут быть совместно проанализированы с измерением di, то объем Anew найденного куба-концепта (Anew, Bnew) не является уникальным и алгоритм переходит к сравнению объ- ема Ak куба-концепта (Ak, Bk) с множеством показате- лей {dj + 1}&apos;. Если Anew содержит хотя бы один показатель, который не может быть совместно проанализирован с измерением di, то объем Anew найденного куба- концепта (Anew, Bnew) является уникальным относи- тельно измерения di и алгоритм продолжает проверку уникальности объема потенциально нового куба- концепта относительно измерения di + 1. Уникальность объема Anew потенциально нового куба-концепта относительно всех проверенных изме- рений di означает, что B (K) не содержит куба- концепта с таким набором показателей. Далее для найденного уникального объема Anew определяется Bnew, как объединение содержания Bk и измерений di. Проверенный новый куб-концепт (Anew, Bnew) добавляется в B (K) и алгоритм переходит к сравнению объема Ak куба-концепта (Ak, Bk) с мно- жеством показателей {dj + 1}&apos;. В ходе работы алгоритма осуществляется напол- нение ранее найденных кубов-концептов и обнаруже- ние новых кубов-концептов, которые подлежат даль- нейшему наполнению. 50 BecmHUK Cu6upcKozo zocyOapcmeeHHOGo a3poKocJvtu&apos;-/ecKozo yHueepcumema uJvteHu aKaiJeJvtuKaM. lfJ. PewemHeea B(K) {(F,0)} llA An w- 06bCII·I TIOTCHIIHU.lhHO HOBOrO Ky6a-KOHI(CTITa 1-------j{Jj}&apos;-\HTO)!{eCTBO TIOKa3aTeJieft, J]OCTYITTI1IX JUICOB\IeCTTIOft ana.lHTJ.IqecKOft o6pa60TKH C 113MCpCHHHM\1 Ji Ak- o6beM Ky6a-KoHuema (AkBk) j = 1 ,j- 1 -)lOTIO.lHHTe. bHb!i:J HH.&apos;leKC f-------1IIJMepeHHfi di ED .&apos;l;JUrI rpoBepKH )1A (J1}&apos; - MHO)KeCTBO IIOKa&apos;3aTeJiefi,.ilOCT}&apos;IIHbiX J]JUI >-+-----lCOBII·IeCTHOi:J aHa. HTH4eCKOi:J 06pa60Trm C II3MepeHHH\1H J; f------jB11e 1, - CO.llep)!{aHHe HOBOfO Ky6a-KOHUeiiTa B(K) B(K) u(Ancw, Bncw) KOHCI( PHC. 1. AJiropiiTM IIOHCKa :r<y60B-KOHIJ;eillOB Ha OCHOBe KOHTeKCTa rrpe.D;MeTHOfi 06JiaCTH 51 MameMamuKa, J>teXaHUKa, uHrjJopMamuKa Bee Ky6hi-KOHuenThi KOHTeKcTa K C&apos;!IITaJDTCll nonHhiMII TOJlhKO llO 3aBeprneHIIllpa60ThlaJirOpiiTMa. TaKIIM o6pa30M, npocMaTpiiBa5! MHO)KeCTBO noKaJaTeneil II ll3MepeHIIM <iJopManbHOro KOHTeKCTa npeJJ,MeTHOM 06JiaCTII, 4JopMnpyeTC5! MHO)KeCTBO ry6oB-KOH1lellTOB. AJiropnTM nocTpoenuH J.wuuenTyaJILnoii pemeTKH OLAP-Ky6os. AriropiiTM nocTpoeHII5! KOHIIemyanhHOM peweTKII OLAP-Ky6oB OCHOBaH Ha anropiiTMe 4JopMIIpoBaHII5! KOHuemyanhHOM peweTKII NEIGHBORS [7-9] (piiC. 2). L(K) = 0 k=1 min= F\Ak i= 1 L(K) = L(K) E ((Ak,Bk),(Aup,Bup)) IF! IB(K) I min - KOHTpOnbHOe MH0)1(8CTBO noKa3aTeneAns:J 1------lnpoBepKltl CTeneHltl 6nli130CTlt1 Ky6oB-KOH48nTOB B peweTK F- MHO.lKecrso noKa3areneKOHTeKcra K Ar o6beM Ky6a-KOH4enTa (AkBk) HET min = min\{fJ Pnc. 2. ArrropHTM rrocTpoeHHll KOHIJ;errTyam.Horr perneTKH OLAP-Ky6oB 52 Вестник Сибирского государственного аэрокосмического университета имени академика М. Ф. Решетнева Задача данного алгоритма заключается в форми- ровании пар кубов-концептов, находящихся в отно- шении частичного порядка подкуб-надкуб. Множест- во пар кубов-концептов из B(K) × B(K), упорядо- ченное отношением подкуб-надкуб, образует ре- шетку OLAP-кубов L(K) ⊆ B(K) × B(K). Согласно методам анализа формальных концептов, свойства решетки такие, что если кубы-концепты X = (Ax, Bx) и Y = (Ay, By) находятся в отношении подкуб-надкуб X < Y, то Ax ⊆ Ay и By ⊆ Bx. Исходя из данного свойства решетки, точная нижняя граница множества B(K) (инфимум) не имеет подкуба. Следовательно, алго- ритм заключается в поиске надкубов для каждого ку- ба-концепта (Ak, Bk) из множества B(K), начиная с ин- фимума и определении ближайшего надкуба, путем сопоставления объемов кубов-концептов. На первом шаге алгоритма решетка кубов L(K) не содержит ни одной пары кубов-концептов из B(K) × B(K). Затем для каждого куба-концепта (Ak, Bk) из мно- жества B(K) определяется min = F\Ak – контрольное множество показателей для проверки степени близо- сти текущего куба-концепта и его потенциального надкуба. Путем перебора показателей fi ∈ F, где i = 1,|F| при условии, что fi ∉ Ak, формируется потенциаль- ный надкуб (Aup, Bup) по следующему принципу: Bup = (Ak∪{fi})&apos;, Aup = (Bup)&apos;. На следующем шаге с помощью контрольного множества min проверяется степень близости найден- ного потенциального надкуба к текущему кубу- концепту. Если объем Aup потенциального надкуба помимо показателей из Ak ∪ {fi} содержит другие по- казатели из множества min, то из контрольного мно- жества исключается показатель fi, найденный потен- циальный надкуб не является ближайшим для куба- концепта (Ak, Bk) и алгоритм переходит к рассмотре- нию следующего показателя fi + 1 ∈ F. Иначе, найден- ный куб-концепт (Aup, Bup) считается надкубом для (Ak, Bk) и пара ((Aup, Bup), (Ak, Bk)) добавляется в ре- шетку L(K) и алгоритм переходит к рассмотрению следующего показателя fi + 1 ∈ F. После рассмотрения всех показателей fi ∈ F алго- ритм переходит к обработке следующего куба- концепта (Ak + 1, Bk + 1) из множества B(K). Таким образом, перебирая все кубы-концепты и сопоставляя их объемы, определяются ближайшие надкуб и подкуб, которые образуют ребро концепту- альной решетки кубов. При изменении контекста предметной области, связанного с добавлением (удалением) объектов ана- лиза или добавлением (удалением) отношения сопос- тавимости между показателями и измерениями, вы- полняется адаптация концептуальной решетки кубов по описанным выше алгоритмам поиска кубов- концептов и формирования решетки OLAP-кубов. Формирование интегральной OLAP-модели научной деятельности организации. Разработанные алгоритмы поиска формальных кубов-концептов и построения концептуальной решетки кубов приме- нены для формирования интегральной OLAP-модели научной деятельности организации. Исследование отчетных форм и решаемых анали- тических задач позволяет эксперту сформировать множество терминов предметной области и на их ос- нове определить объекты анализа: – множество показателей – число публикаций; число патентов; число статей; число учебных посо- бий; число грантов; число проведенных конференций; количество сотрудников и т. д.; – множество измерений – год; подразделение; тип пособия; город; название журнала; тип публикации; тип патента; статус конференции; автор и т. д. С учетом сопоставимости показателей и измере- ний построен формальный контекст научной деятель- ности, который отражает знания эксперта об объектах анализа и возможности их совместной аналитической обработки. В контексте определены следующие эле- менты множества F = {число публикаций, число про- веденных конференций, число патентов, число ста- тей, число учебных пособий} и элементы множества D = {год, подразделение, тип пособия, город, назва- ние журнала, тип публикации, тип патента, статус конференции, автор}. Используя сокращенные обо- значения, получены соответственно: F = {f1, f2, f3, f4, f5} и D = {d1, d2, d3, d4, d5, d6, d7, d8, d9}. С помощью алгоритма поиска формальных кубов- концептов на основе построенного контекста опреде- лены кубы-концепты. Для рассматриваемого контек- ста найдено 8 кубов-концептов (рис. 3). Концептуальная решетка OLAP-кубов, построен- ная с помощью разработанного алгоритма, представ- ляет собой интегральную OLAP-модель научной дея- тельности организации (рис. 4). Разработанные алгоритмы поиска кубов-концеп- тов на основе контекста предметной области и алго- ритм построения концептуальной решетки кубов позволяют реализовать метод концептуального OLAP-моделирования и формировать интегральную OLAP-модель предметной области на множестве всех объектов анализа. Свойства концептуальной решетки обеспечивают возможность оперировать одновремен- но всеми объектами анализа и выявлять аналитиче- ские зависимости, что позволяет повысить эффектив- ность оперативной аналитической обработки много- мерных данных. Практическим результатом работы стало построение интегральной OLAP-модели науч- ной деятельности организации на основе разработан- ных алгоритмов. 53 Математика, механика, информатика Рис. 3. Редактор формального контекста и сформированные кубы-концепты научной деятельности организации Рис. 4. Решетка кубов-концептов научной деятельности организации