Задать вопрос:





Статьи

Статьи>> РАЦИОНАЛЬНАЯ ОРГАНИЗАЦИЯ ДАННЫХ АНАЛИТИЧЕСКОГО КОМПОНЕНТА В ИНДИВИДУАЛЬНЫХ ИНФОРМАЦИОННЫХ СИСТЕМАХ С ИСПОЛЬЗОВАНИЕМ АЛГОРИТМА УПАКОВКИ С ДИНАМИЧЕСКОЙ ВНУТРЕННЕЙ ГРАНИЦЕЙ ОБЪЕМА

РАЦИОНАЛЬНАЯ ОРГАНИЗАЦИЯ ДАННЫХ АНАЛИТИЧЕСКОГО КОМПОНЕНТА В ИНДИВИДУАЛЬНЫХ ИНФОРМАЦИОННЫХ СИСТЕМАХ С ИСПОЛЬЗОВАНИЕМ АЛГОРИТМА УПАКОВКИ С ДИНАМИЧЕСКОЙ ВНУТРЕННЕЙ ГРАНИЦЕЙ ОБЪЕМА

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

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

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

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

Как правило, в корпоративных информационных системах обработка текущих (транзакционных) данных и аналитическая обработка данных выполняются разными подсистемами, обладающими раздельными хранилищами данных [2], причем первые — реляционными, а вторые — либо реляционными (ROLAP, Relational OnLine Analytical Processing), либо многомерными хранилищами (MOLAP, Multidimensional OnLine Analytical Processing). Известно, что при низких и средних объемах данных, эффективность применения многомерных хранилищ выше, чем реляционных [3]. Хранилище данных аналитической подсистемы проектируется исходя из планируемой на него нагрузки: выбор измерений для агрегирования выполняют системные аналитики, прогнозируя спектр будущих запросов. Обновление агрегированных данных в аналитической БД на основе данных транзакционной БД выполняется с некоторой периодичностью. Исходные данные после агрегирования удаляются из транзакционной БД и переносятся в архивную БД, обладающую структурой, аналогичной транзакционной БД.

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

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

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

Прирост эффективности при данном подходе достигается за счет того, что "редкие" запросы имеют тенденцию к группированию во времени [4,5]: часто после того, как был выдан "редкий" запрос с некоторыми параметрами, этот же запрос повторяется с другими параметрами. Если в процессе выполнения первого запроса подготовиться к выполнению последующих аналогичных запросов, построив в динамическом разделе многомерную БД по требуемым измерениям, время выполнения последующих запросов может быть значительно сокращено.

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

Таким образом, возникает задача разбиения доступного объема ресурса общей памяти, выделенной для хранения аналитической БД, и размещения в квазистатическом разделе агрегированных данных в соответствии со статистикой запросов.

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

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

В смысле характеристики динамики возможно выделение следующих трех ситуаций по отношению к статистически определяемым значениям предпочтений:.

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

Система находится в процессе набора статистики предпочтений. Это ситуация такого временного этапа функционирования, когда оценка устойчивости статистики не попадает в доверительный интервал. Такие оценки могут быть получены на основе определения минимального объема выборки по известным критериям математической статистики, например при неизвестных дисперсиях с использованием критерия Стьюдента [7]. В этой ситуации получение точного решения задачи нецелесообразно изза статистической неточности исходных данных о предпочтениях. В качестве альтернативы возможно использование эвристических апгоритмов решения поставленной задачи с меньшей вычислительной сложностью и получением рациональных результатов.

Система находится в состоянии устойчивой статистики предпочтений. В этой ситуации возможно точное решение задачи о разбиении доступного объема ресурса общей памяти аналитической БД. Полученные результаты могут лежать в основе организации оптимальной процедуры управления разбиением аналитической БД ИИС на квазистатический и динамический разделы с учетом устойчивых предпочтений.

Алгоритмы решения задачи упаковки с динамической внутренней границей объема.

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

Пусть задано множество, где каждый элемент у{ обладает целочисленным линейным размером v,, или «объемом» в общепринятых терминах задачи упаковки, и ценовой характеристикой PJ, которая содержательно отражает практически значимые предпочтения для загрузки данного объекта. Целым числом задан так же основной объем упаковки V.

Y={yi}, |Y|=N,

yi={vi,pi}, i Є {1,2,...,N},

Реальная постановка задачи имеет смысл, если суммарный линейный размер (объем) элементов превышает основной объем упаковки; таким образом, должно быть выполнено следующее условие:

Для описания подмножества М загружаемых в объем К элементов из множества Y введем в рассмотрение следующий характеристический вектор:

Элементы, составляющие подмножество М, должны максимизировать суммарное предпочтение. Поскольку после загрузки в основном объеме должно остаться свободное место для размещения максимального по размеру незагруженного элемента yte YM , то постановка задачи формулируется следующим образом, при выполнении динамического условия максимизировать линейную форму

Условие (4) не является типичным для классической задачи оптимальной по стоимости упаковки [6]. В связи с динамическим изменением внутренней границы загружаемых в основной объем элементов, в зависимости от размера максимального незагруженного элемента, будем эту задачу называть в дальнейшем задачей упаковки с динамической внутренней границей объема.

Исследование задачи упаковки (3) с изменяющимся граничным значением объема показало, что она может быть решена на основе классической задачи упаковки для всех объемов от V1=Vmax{vi} до V2=Vmin{vi}, i Є {1,2,...,N}, которую будем в дальнейшем называть базовой, с последующим выбором той упаковки, которая удовлетворяет условию (4).

Для решения базовой задачи в указанных объемах может быть использован табличный алгоритм для классической задачи упаковки [6], позволяющий получить набор оптимальных решений для всех промежуточных дискретных значений основного объема. Базовая задача упаковки есть задача максимизации линейной формы (3) при ограничениях:

Решение табличным алгоритмом осуществляется на основе функционального уравнения метода динамического программирования, которое для базовой задачи имеет вид [5]:.

Результатом решения базовой задачи с ограничением (5) является набор оптимальных значений целевой функции fN(v) и соответствующих векторов оптимальной упаковки XNv для всех объемов от V1 до V2 исходными элементами из Y. Отметим, что вычисления по дискретным значениям объема при k = N могут быть сокращены, так как оптимальные упаковки для объемов от 0 до (V1 1) не содержат решений, интересующих нас в смысле условия (4).

Рассмотрим подзадачу определения максимального объема v , в котором выполняется условие (4). Поскольку базовая задача имеет целочисленный (по v и V) характер, то хотя в каждом решении для объема v и достигается максимум линейной формы (3), сам объем v может быть упакован не плотно. В связи с этим рассмотрим специальную функцию d(v), задающую остаток свободного пространства в оптимально упакованном объеме v:

Функция d(v) неотрицательна в силу выполнения условия аналогичного (5) для объема упаковки v при решении базовой задачи. Определим так же функцию R(v), задающую необходимый остаток объема для размещения максимального по объему неупакованного элемента:

R(v)=max{vi}, i:xiv, i Є {1,2,...,N}. (7)

Выполнение ограничения (4) сводится к нахождению максимального объема v такого, что:

Поскольку функция fN(v) является неубывающей в силу основного функционального уравнения, то должно быть выбрано наибольшее значение v, удовлетворяющее условию (8). Следовательно, оптимальное решение задачи упаковки с динамической внутренней границей объема задается тем вектором XNv* , для которого значение v* удовлетворяет условию:

Таким образом, предлагаемый алгоритм А\ является двухшаговым, при этом на первом шаге решается базовая задача упаковки (3) с ограничением (5), а на втором шаге определяется внутренняя динамическая граница упаковки, максимизирующая линейную форму (3) при ограничении (4) путем нахождения v* по условию (9).

Оценка сложности алгоритма А1 есть максимальная по асимптотике оценка сложности шагов. Решение базовой задачи реализуется с учетом бинарности компонент вектора X двумя вложенными циклами — по элементам yi, и по дискретам объема v. С учетом необходимости дублировать строки таблицы, содержащей вектор Хkv, имеем оценку для первого шага — 0(N2 V). Для второго шага вычисление функций R(v) и d(v) требует не более O(N) операций для каждой проверки условия (9), которая выполняется не более, чем М = V2 V1 раз. Очевидно, что М < V в силу определений V2 и V1, и в результате алгоритм А1 имеет сложность 0(N2 V).

Из оценки этой сложности очевидно, что сокращение количества операций (при фиксированном N может быть получено только решением задачи по выбору большего значения дискрета объема, уменьшающего численно значения vi и V. Для точного решения этой задачи необходимо нахождение НОД (V,v1,v2,...,vN). Однако такой путь бесперспективен, так как при большом значении ^вероятностьтого, что НОД (V,v1,v2,...,vN)=l близка к единице. Это предположение опирается на теорему Дирихле [8], утверждающую, что вероятность того, что два случайно выбранных натуральных числа взаимно просты, равна 6/п2=0,607927.

В качестве альтернативы рассмотрим следующий эвристический подход к определению рациональной единицы измерения объема в задаче упаковки. Пусть объемы vi и V заданы целыми числами в некоторых единицах объема, которые будем считать минимально возможными в рамках реальной задачи.Обозначим через k коэффициент упаковки объема К элементами со средним значением объема:

где [a] целая часть числа a.

Введем в рассмотрение новую единицу измерения объема, со значением равным m минимальных единиц.Обозначим через vi приращение объема элемента yi, выраженное в минимальных единицах, при переводе его в новую единицу измерения. Будем предполагать, что N велико, а распределение значений vi по классам эквивалентности по модулю m равномерно.

Тогда в среднем k/m элементов yi точно (без остатка) представляются в новых единицах измерения объема, a k(1 — 1/m) элементов уi должны быть округлены до ближайшего большего целого с увеличением в среднем на m/2. В силу предположения равномерности увеличение суммарного объема для k элементов, упакованных в объем V, составит в минимальных единицах:

Сам общий объем упаковки V при переводе в новые единицы объема будет увеличен в среднем на m/2. Поскольку в среднем после упаковки k элементов в объеме k останется свободное место размером v/2 минимальных единиц, то увеличение общего доступного объема составит:

Для сохранения старой упаковки общий объем V должен быть увеличен на V =(v+ V+) минимальных единиц. Условие выбора рационального значения m может быть задано как процентное ограничение увеличения общего объема V:

Подставляя (10) и (11) в (12), окончательно имеем следующее ограничение на выбор значения m:

Могут быть рассмотрены и другие подходы к определению рационального значения m. Например, в ситуации, когда коэффициент вариации для распределения vi. достаточно велик, можно положить m=min (vi).

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

Использование эвристических алгоритмов упаковки [9] позволяет получить рациональное решение с лучшей временной эффективностью. Достаточно хорошие результаты дает эвристический алгоритм, использующий предварительную сортировку элементов по удельному предпочтению на единицу объема (см. оценку Грэхема в [9]). Упаковка осуществляется в порядке расположения элементов в отсортированной последовательности с пошаговой проверкой выполнения ограничений.

Реализация ограничения (4) для такого алгоритма сводится к проверке возможности расположения максимального по объему незагруженного элемента в общий объем. Поскольку пошаговая загрузка осуществляется последовательно из отсортированного массива, то на шаге k должна быть выполнена проверка следующего условия:

где нумерация i Є {1,2,...,N} соответствует нумерации в отсортированной последовательности исходных элементов в порядке убывания значений pi/vi.

Если условие (14) не выполняется, начиная с некоторого значения k+1, то предыдущие упакованные элементы (с индексами 1, 2,..., К) в объеме V образуют рациональную упаковку с динамической внутренней границей объема.

Реализация условия (14) требует перевычисления максимума на каждом шаге добавления элемента в М . Определенное сокращение трудоемкости проверки условия (14) может быть получено за счет пошагового накопления суммы объемов упакованных элементов и более быстрому поиску. Такой быстрый поиск может быть осуществлен на основе следующих рассуждений. Если на некотором шаге упаковки выбирается очередной элемент с объемом, меньшим текущего максимума, то правая часть условия (14) может не пересчитываться. Для вычисления объема максимального неупакованного элемента введем в рассмотрение функцию Mk(v):

Тогда условие (14) принимает вид

Таким образом, предлагаемый эвристический алгоритм А2 является также двухшаговым. На первом шаге выполняется сортировка исходных элементов в порядке убывания значений —. На втором шаге определяется внутренняя динамическая граница упаковки, обеспечивающая рациональную суммарную стоимость путем нахождения v*k по условию (16), причем значение Mk(v) вычисляется в соответствии с (15).

Приведем оценку сложности алгоритма А2 для среднего случая. Сортировка на первом шаге при больших значениях N может быть выполнена методом пирамиды с оценкой в среднем случае O(NlnN) [9].

На втором шаге формирование вектора X требует не более k шагов и, следовательно, проверка условия (16) выполняется не более k раз, причем значение k не может превосходить N в силу постановки задачи. Покажем, что сложность второго шага не хуже O(NnN) в среднем. Вычисление левой части в условии (16) имеет сложность 0(1). Вычисление M0(v), выполняемое однократно, имеет сложность O(N). В предположении о равномерном случайном распределении N значений vi обычный алгоритм поиска максимума выполняет в среднем O(lnN) переприсваиваний [10], т.е. смен текущего максимума. Таким образом, пересчет Mk(v) будет выполнен, в среднем, с учетом условия kk(y) вычисляется путем присваивания старого значения со сложностью 0(1). Сам пересчет максимума для вычисления нового значения Mk(v) требует в соответствии с (16) не более O(N) шагов. Объединяя полученные результаты, имеем оценку сложности в среднем для второго шага алгоритма в виде:

O(N) + N * O(1) + O(lnN) * O(N)= O(NlnN).

Таким образом, оценка сложности алгоритма А2 в целом составляет O(NlnN), что асимптотически значительно лучше, чем у алгоритма А\, но при этом алгоритм А2 позволяет получить рациональное, но не оптимально точное решение.

Заключение. Авторами предложен подход к решению задачи рационализации структуры хранения аналитической БД ИИС, основанный на разбиении объема аналитической базы на квазистатический и динамический разделы. Формирование разделов производится на основе статистической информации об обращениях к агрегированным данным по отдельным измерениям. Оптимизация такого формирования по суммарной частоте обращений требует решения задачи упаковки с динамической внутренней границей объема. В зависимости от устойчивости статистики предпочтений предлагается использовать два алгоритма решения этой задачи — точный и эвристический, сложностные оценки которых (соответственно O(N2V) и O(NlnN)) позволяют осуществить их обоснованный выбор. Дополнительная временная эффективность программной реализации может быть получена на основе предложений по рациональному выбору значения единицы измерения для основного объема упаковки и объемов элементов. Предложенные решения используются при разработке программного обеспечения системы автоматизированного администрирования баз данных индивидуальных информационных систем.

Список литературы

  1. Брейман А.Д. Функциональные особенности со временных систем автоматизированного администрирования баз данных. Науч. тр. IV Всероссийской конф."Новые информационные технологии". М.:МГАПИ,2003.
  2. Codd E.F., Codd S.B., Salley C.T.Providing OLAP (online analytical processing) to useranalysts: An ITMandate. Technical report. E. F. Codd and Associates, San Jose 1993.
  3. Inmon W.H. Building the data warehouse: Third edition. New York: John Wiley and Sons, 2002.
  4. Deshpande P.M., Ramasamy K., Shukla A., Naughton J.F. Функциональные особенности современных систем автоматизированного администрирования баз данных. Науч. тр. IV Всероссийской конф."Новые информационные технологии". М.:МГАПИ,2003.
  5. Roy P., Vora J., Ramamritham K., Seshadri S., Sudarshan S. Query Result Caching in Data Warehouses and Data Marts. University of Massachusetts Computer Science,1999.
  6. Гмурман В.Е. Теория вероятностей и математическая статистика: Учеб. пособие для вузов. 9с изд., стер.М.: Высшая школа, 2003.
  7. Ноден П., Китте К. Алгебраическая алгоритмика:Пер. с франц. М.: Мир, 1999.
  8. Беллман Р., Дрейфус С. Прикладные задачи динамического программирования: Пер. с англ. М.: Наука,1965.
  9. Гудман С., Хидетниеми С. Ведение в разработку и анализ алгоритмов. М.: Мир, 1981.
  10. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 1999.

А.Д. Брейман, М.В. Ульянов
Справочник. Инженерный журнал. №12, 2004, с. 17-22

Статьи партнеров