Майстренко А.В., Майстренко Н.В.

Тамбовский государственный технический университет, Россия

Оптимизация размещения баз данных

сложных информационных систем

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

• сложность описания, требующая тщательного моделирования и анализа данных и процессов;

• наличие совокупности тесно взаимодействующих компонентов (подсистем), имеющих свои локальные задачи и цели функционирования;

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

• необходимость интеграции существующих и вновь разрабатываемых приложений;

• функционирование в неоднородной среде на нескольких аппаратных платформах;

• разобщенность и разнородность отдельных групп разработчиков по уровню квалификации и сложившимся традициям использования тех или иных инструментальных средств;

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

Работающая информационная система (ИС) подразумевает использование модели предметной области. В общем случае понятиями, формирующими модель, являются объекты и отношения между ними. Модель может иметь явное описание, хранимое полностью или частично в ЭВМ, и храниться (также полностью или частично) в ЭВМ сама. Хранимую в ЭВМ и используемую программно модель можно называть базой данных. Альтернативу явному хранимому описанию модели составляет ее неявное и часто некорректное описание "логикой прикладной программы".

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

Разбиение содержимого базы данных по отдельным файлам – сложная задача, формализуемая и решаемая при помощи дискретной математики и теории графов [1]. Представим базу данных, содержащую N атрибутов. Вес i атрибута W_i = l_i·m, где l_i – длина в байтах значения атрибута, m – число экземпляров, i = 1, 2,…, N.

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

Пусть задан неориентированный взвешенный граф G(X, V, w, d) порядка n, где X={x₁,…,x_n} – множество вершин; VÍX´X – множество ребер; w: V®R+ – отображение, определяющее вес каждого ребра; d: X ®R+ – отображение, определяющее вес каждой вершины, где R+ – множество действительных неотрицательных чисел.

Требуется определить разбиение множества вершин X графа G(X, V, w, d) на k подмножеств (X₁, X₂,…,X_k) таким образом, чтобы для кусков графа G₁(X₁, V₁, w₁, d₁), G₂(X₂, V₂, w₂, d₂), …, G_k(X_k, V_k, w_k, d_k) выполнялись требования:

XiÇXj=Æ, для " i¹j, где i,j =; ; |X1|=n1,…, |Xk|=nk, n1+…+nk=n.

(1)

В качестве первого критерия оптимальности F₁, определяющего эффективность k-разбиения (X₁,…,X_k), будем рассматривать суммарный вес всех ребер, целиком попавших в один из подграфов разбиения:

(2)

Суммарный вес вершин, принадлежащих одному подграфу, будем называть весом подграфа. Вес некоторого подграфа X_i будем обозначать через W(X_i). Для уравнивания весов получаемых подграфов будем использовать следующий критерий оптимальности F₂:

(3)

Таким образом имеем задача оптимизации БД может быть записана в виде:

(4)

Для решения задач разбиения графов используют алгоритм разбиения пополам, алгоритм деления с учетом связности, алгоритм разбиения Кернигана-Лина и их модификации.

Литература

1. Майстренко А.В., Майстренко Н.В., Ерохин О.И. К вопросу об оптимизации баз данных сложных информационных систем // Вопросы современной науки и практики. Университет им. В.И. Вернадского. 2009. №. 8 (22). С.126-130.