Метод розподілу таблиць реляційної бази даних рівного об'єму та різними ймовірностями звертання до них в інформаційно-обчислювальній мережі АСУ

Abstract

Анотація. Проведено аналіз функціонування сучасних систем управління базами даних (СУБД), що функціонують в інформаційно-обчислювальних мережах (ІОМ) автоматизованих систем управління (АСУ). Зроблено висновок про залежність продуктивності функціонування ІОМ АСУ від методу розподілу інформаційного ресурсу, який застосовується в ній. Відзначено, що в основу методу доцільно покласти багаторівневу ієрархічну модель виділення інформаційного ресурсу. Відмічено, що велика кількість параметрів,які впливають на розподіл інформаційного ресурсу, а також розмаїтість показників якості при визначенні характеристик розподілу і труднощі їх зведення до єдиного критерію, досить ускладнюють методи розв'язання задачі розподілу інформаційного ресурсу. При цьому суть цієї задачі полягає у раціональному розміщенні реляційних таблиць БД по різних типах апаратно-програмних засобів (АПЗ). Це дає можливість скоротити часові витрати на обробку запитів, з огляду на характер оброблюваних даних. Сформульовано задачу розподілу мінімізації часу доступу до таблиць розподіленої реляційної бази даних (РРБД) однакового об'єму та різними ймовірностями звертання до них. Зроблено висновок про неможливість її розв'язання стандартними методами внаслідок нелінійності обмежень в її постановці. Запропоновано метод рішення сформульованої задачі, який базується на специфіці обмежень задачі та цільової функції. Суть запропонованого методу полягає у звуженні допустимих рішень на основі врахування нелінійності зв'язків в обмеженнях задачі та методики ранжування блоків, що запропонована авторами.

-

Ключові слова: автоматизована система управління, інформаційнообчислювальна мережа, розподілена реляційна база даних Аналіз функціонування систем управління базами даних (СУБД) інформаційнообчислювальних мереж (ІОМ) автоматизованих систем управління (АСУ) [1, 2] показує, що метод розподілу інформаційного ресурсу ІОМ АСУ для забезпечення функціонування складових частин системи у значній мірі визначає її продуктивність.

Під час організації та функціонування СУБД використовується багаторівнева система обробки та зберігання даних. Для цього при проектуванні системи або її модернізації створюється модель ієрархічного виділення інформаційного ресурсу, яка може розглядатися досить автономно та незалежно від взаємодії із зовнішніми абонентами. Така модель застосовується в системах, де для більшості функціонуючих транзакцій існує порівняно великий припустимий час реакції на зовнішні впливи й потрібні більші об’єми пам’яті для зберігання масивів даних і програм.

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

Зміна характеристик ресурсу кожного рівня безпосередньо впливає на продуктивність і ефективність роботи ІОМ АСУ в цілому. Для кожної ІОМ АСУ потрібно розв’язувати оптимізаційну задачу розподілу обмеженого інформаційного ресурсу з метою одержання мінімального значення узагальненого показника.

Велика кількість параметрів, що впливають на розподіл інформаційного ресурсу, а також розмаїтість показників якості при визначенні характеристик розподілу і труднощі їх поєднання до єдиного критерію, досить ускладнюють методи розв’язання задачі розподілу інформаційного ресурсу. Тому доцільно розглядати процес розподілу інформаційного ресурсу у вигляді ряду часткових моделей, які безпосередньо пов’язані з характеристиками збережених даних [5]. Виділимо ряд особливостей функціонування СУБД в ІОМ АСУ: рівноймовірне звертання до деяких реляційних таблиць даних рівного об’єму внаслідок того, що час розв’язання задач ІОМ АСУ і періоди звертання до збереженої в БД інформації, є прогнозованими;

однократність завдання реляційних таблиць, причому відомо заздалегідь, що структура даних дозволяє мати ряд реляційних таблиць однакового об’єму для одного ієрархічного рівня пам’яті;

різний об’єм реляційних таблиць, тобто наявність реляційних таблиць різного об’єму, але однакової структури. У цьому випадку можлива декомпозиція різних за об’ємом реляційних таблиць на рівні.

Такий підхід застосовується при проектуванні СУБД, що відрізняються суворою періодичністю обробки інформації, яка є характерною для деяких ієрархічних рівнів підсистем комплексів задач, які не пов’язані з процесом управління.

Тому під моделлю розподіленої реляційної бази даних (РРБД) будемо розуміти модель, що характеризується реляційними таблицями рівного об’єму, причому ймовірності звертання до них є різними. Назвемо дану модель − модель РРБД з реляційними таблицями рівного об’єму та різними ймовірностями звертання до них.

При інтенсивному потоці запитів до СУБД фактична швидкодія виконання задач ІОМ АСУ у значній мірі визначається часом обробки кожного запиту. Операції по обробці запитів до різних типів апаратно-програмних засобів (АПЗ) можуть частково або повністю сполучатися за часом, тобто фактична швидкодія істотно залежить від обраного способу обробки реляційних таблиць бази даних (БД) різними типами АПЗ.

У сучасних РРБД при обробці великих інформаційних масивів швидкість обробки істотно залежить від розміщення реляційних таблиць, що описують однотипні об’єкти [1−4]. Відповідно до задач, які виконуються АСУ, при проектуванні складних запитів до РРБД великої інформаційної ємності, необхідно вкластися в задані часові границі.

При цьому суть задачі розподілу інформаційного ресурсу полягає у раціональному розміщенні реляційних таблиць БД по різних типах АПЗ. Це дає можливість скоротити часові витрати на обробку запитів, з огляду на характер оброблюваних даних. 2 Постановка задачі мінімізації часу доступу до таблиць розподіленої реляційної бази даних Для запиту, який формується на основі інформації, що отримується з М таблиць РРБД обсягу W, з ймовірністю звертання до s-ї таблиці − рs, (s  1, М ) ,  М    ps  1 , у випадку моделі розподілу реляційних таблиць БД рівного об’єму з  s1  різними ймовірностями звертання до них [4, 5], сумарний час доступу до реляційних таблиць складе:

M KC T    pi  xik  k , i1 k1 ( 1 ) де xik − булева змінна розподілу таблиць РРБД:

 1, якщо i - а таблиця розміщується в k - му блоці; xik  

 0, якщо i - а таблиця не використов ує k - й блок. При обмеженнях: – кожна реляційна таблиця обробляється тільки в одному блоці, що не впливає на загальність постановки задачі, тому що Vj  W j 1, N : (2) (3) (4) ( 5 ) ( 7 ) (8) KC  xik  1, i = 1, M ; k 1 yj  nj, j  1, N ;

N  f j y j  F ; j 1  (0)  0;  j1  ( j 1)  nk , j = 2, N .  k1

k (j1) = (j-1)+1.

N де KC   n j − загальна кількість доступних блоків;

j1 – кількість задіяних блоків типу j не повинна перевищувати максимально можливу кількість блоків даного типу, що необхідно з визначення змінних уj: – наведені сумарні витрати на необхідне число блоків АПЗ не повинні перевищувати максимально припустимого розміру витрат F, що задається нерівністю:

Функція зміщення номера дозволяє для обчислювального вузла типу j визначити порядковий номер першого з блоків, які представлені для запиту: З урахуванням цього, число реляційних таблиць, що розміщені у блоках типу j, дорівнює: – змінні задачі повинні належати заданій області та бути цілочисельними: xik 0,1, yj 0,1,...,nj.

– вимога про достатність числа блоків типу j для обробки реляційних таблиць БД задається нерівністю: де lj = [Vj / W] − число реляційних таблиць, які можуть оброблятися в одному блоці j-го типу;

(j) – функція зміщення номеру на множині {0, ..., N-1} типів обчислювальних вузлів:

M ( j1)y j  xik  l j  y j i1 k( j1)1  j 1,N , (6) Вимога щодо мінімізації часу доступу до розподілених таблиць БД при обробці та розміщенні РРБД приводить до задачі цілочисельного нелінійного програмування з цільовою функцією: .(9) ( 10 ) (11) Аналіз публікацій [8−11] показує, що незважаючи на те, що задача цілочисельного програмування має значну складність щодо її вирішення, для неї розроблено достатньо велику кількість алгоритмів. Деякі з цих алгоритмів ефективні для окремих класів задач цілочисельного програмування, однак, у загальному випадку можна стверджувати, що не існує загального алгоритму, який би знаходив оптимальне рішення за достатній час для задач великих розмірностей.

Тому для рішення оптимізаційної задачі ( 10 ) при обмеженнях ( 2−9 ) пропонується використовувати метод звуження області допустимих рішень, що базується на урахуванні нелінійного зв’язку змінних в обмеженнях ( 2−9 ) та методиці ранжування блоків, що була запропонована авторами.

Перший етап пропонованого методу полягає в розбивці області допустимих рішень на дві підмножини X та Y, де Y − цілочисельна множина векторів розподілу блоків та X − множина планів розподілу реляційних таблиць. Кожний елемент множини допустимих рішень задачі ( 10 ):

Z = {z = (x11, ..., xik, ..., X MKC , y1, ..., yj, ..., yN)}  M  (j-1)+yj     xik  / l j i1 k= (j-1)+1 

M KC T    pi  xik  k  min

i1 k 1 можна представити як конкатенацію плану розподілу реляційних таблиць по блоках вузлів ІОМ з множини X:

X = {x = (x11, ..., X MKC )}  

MKC

Кожен фіксований вектор розподілу yfix однозначно визначає план розподілу, виходячи з обраного способу впорядкування блоків: xik = 1 для i = (k - 1)lj + 1, ..., klj, i  M; k = (j - 1) + 1, ..., (j - 1) + yj, j  1, N; xik = 0 для i = (k - 1)lj + 1, ..., klj, i  M; k  (j - 1) + 1, ..., (j - 1) + yj, j  1, N; На другому етапі з множини векторів розподілу блоків вузлів видаляються всі елементи, що не задовольняють умові (2). Потім, використовуючи різні варіанти ранжування по типах вузлів, корегуються верхня та нижня межа розбивки множини Y по рівнях задіяних блоків таким чином, щоб в отриманій підмножині Y* містився вектор оптимального розподілу блоків y(опт) при умові, що card Y* << card Y.

Уведемо на множині Y бієктивне відображення на підмножині цілих невід’ємних N-розрядних p-х чисел: так, що: де p  1 max n j .

j1, N :YQp,

 N   y  rp   j1y j  p j1  ,   p (13) (14) (15) (16) (17) (18) З обмеження (2) та бієктивності введеного обмеження можна зробити висновок, що потужність множини Qp обмежена зверху нерівністю: Очевидно, що існує єдине розбиття  множини Qp на KC+1 підмножин, які не перетинаються та в кожному з яких є фіксована сума р-ічних цифр:

N cardQp  n j 1.

j1 Qp  Kc Qps,

Відмітимо, що серед елементів розбиття  знайдуться такі Q p min  та (19) (20)

N  min , max 1, Kc : min   y j   max.

j1 * У результаті до множини Q p потрапляють тільки ті p-ічні числа из Qp , в яких сума цифр знаходиться у межах від min до max, у тому числі й rpопт .

На третьому етапі з підмножини Y* гіперплощинами відсікаються елементи, що не вдовольняють обмеженню (3) задачі та визначається підмножина Y**  Y*, що містить y(опт).

Для подальшого зменшення потужності множини Q*p врахуємо специфіку обмеження (2) задачі, що розглядається.

~ ~ j Покажемо, що  j  N ,  ~  0, Kc : ~   y j .

j j j1 * Послідовно знаходячи верхню межу суми елементів Q p , отримаємо підмножину Q*p* , що містить число rpопт . Застосовуючи операцію зворотного відображення -1 до елементів множини Q*p* можна отримати підмножину векторів розподілу блоків Y** : ( Y **  Y * , y опт  Y ** , оскільки  1 r опт   yопт ) .

p Оптимальний план y(опт)  Y** розподілу реляційних таблиць по блоках вузлів ІОМ визначається на четвертому етапі за допомого введеної функції зміщення номера ( 7 ).

Використовуючи (14) визначаємо план оптимального розподілу інформаційного ресурсу по блокам вузлів − x(опт). Тоді рішенням задачі є вектор: zопт  xопт!!yопт.

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

Експериментальна перевірка запропонованого методу довела його ефективність. Так, при N = 5 різних типів вузлів ІОМ АСУ для обробки та розміщення M = 12 таблиць РРБД у відповідності з вимогами сформульованої задачі, максимально припустимому значенні сумарних витрат, виділених на розподіл інформаційного ресурсу F = 27, ймовірностями звертання до реляційних таблиць:p1= 0,19; p2= 0,15; p3 = 0,14; p4= 0,12; p5 = 0,10; p6 = 0,08; p7 = 0,07; p8 = 0,05; p9 = 0,04; p10 = 0,03; p11 = 0,02; p12 = 0,01 та характеристиками tj, fj, lj, nj типів вузлів, що наведено в таблиці 1, рішення задачі запропонованим методом приводить до отримання наступних результатів:

KС = 15; p = 5; min = 6; max = 7;  ~j  2 . Таблиця 1.Характеристики вузлів розміщення інформаційного ресурсу при N = 5. Номер типу вузла (j) Відповідно, yопт  1r опт  або yопт  0,2,1,1, 2 .

5 План розподілу інформаційного ресурсу по блокам вузла має вигляд:

Мінімальний час обробки запитів склав 7,04 мс. Було зроблено перебір 30 варіантів розміщення інформаційного ресурсу (таблиць реляційної бази даних). Повний перебір у даному випадку складає 900 варіантів розміщення таблиць.

Розглянемо рішення більш складного прикладу. При N = 10 різних типів вузлів ІОМ АСУ для обробки та розміщення M = 24 таблиць РРБД у відповідності з вимогами сформульованої задачі, максимально припустимому значенні сумарних витрат, виділених на розподіл інформаційного ресурсу F = 110, ймовірностями звертання до реляційних таблиць: p1 = 0.14; p2 = 0.097; p3 = 0.085; p4 = 0.077; p5 = 0.072; p6 = 0.063; p7 = 0.058; p8 = 0.054; p9 = 0.05; p10 = 0.047; p11 = 0.038; p12 = 0.035; p13 = 0.031; p14 = 0.027; p15 = 0.022; p16 = 0.019; p17 = 0.017; p18 = 0.016; p19 = 0.014; p20 = 0.012; p21 = 0.009; p22 = 0.007; p23 = 0.006; p24 = 0.004 та характеристиками tj, fj, lj, nj типів вузлів, що розглядаються задані в таблиці 2.

Таблиця 2. Характеристики вузлів розміщення інформаційного ресурсу при N = 10. yопт  1rопт тобто yопт  0,2,2,2,1,0,0,1,3,1 .

5 План розподілу інформаційного ресурсу має вигляд: Мінімальний час обробки запитів склав 7,78 мс. Приведені потужності множин показують, що перебір варіантів для розміщення інформаційного ресурсу скорочено приблизно у 20 разів. У таблиці 3 наведені результати тестування алгоритму описаного вище методу поетапного звуження допустимих рішень задачі при різних М і N.

Таблиця 3. Час рішення задачі, мс. У результаті проведених досліджень показано, що продуктивність функціонування АСУ значною мірою визначається ефективним розподілом таблиць розподіленої реляційної БД, що застосовується в інформаційнообчислювальній мережі.

Зроблено висновок, що в наслідок великої кількості параметрів, які впливають на розподіл таблиць розподіленої реляційної БД та розмаїтості показників якості під час визначення характеристик розподілу і труднощів їх зведення до єдиного критерію, процес розподілу таблиць розподіленої реляційної БД доцільно розглядати у вигляді часткових моделей, які безпосередньо пов’язані з характеристиками збереження даних.

Наведено формальну постановки задачі мінімізації часу доступу до таблиць розподіленої реляційної БД та показано, що вона відноситься до класу задач цілочисельного нелінійного програмування та, у наслідок не лінійності її обмежень, не може бути вирішеною відомими методами.

Запропоновано метод розподілу таблиць розподіленої реляційної БД в інформаційно-обчислювальній мережі АСУ, суть якого зводиться до звуження області допустимих рішень з урахуванням нелінійного зв’язку змінних в обмеженнях постановки задачі.

Експериментальна перевірка запропонованого методу довела його ефективність, завдяки зменшенню (у декілька десятків разів) кількості варіантів, які розглядаються для розміщення таблиць розподіленої реляційної БД в інформаційно-обчислювальній мережі АСУ для обробки запитів користувачів.

Запропонований метод можливо використовувати для реалізації більш складних моделей розподілу інформаційного ресурсу в ІОМ АСУ. Джерела

Igor Subach1 and Alexander Chauzov1 Abstract. The analysis of the functioning of modern database management systems functioning in information and computer networks of automated control systems is carried out. A conclusion is made about the dependence of the performance of information and computer networks of automated control systems on the method of distribution of the information resource, which is used in it. It is noted that in the basis of the method it is expedient to put a multilevel hierarchical model of allocation of information resource. Each subsequent level of this model is characterized by an increase in access time to information and a reduction in the cost of storing a unit of data. Changing the characteristics of the resource of each level directly affects the performance and efficiency of the information and computer network of the automated control system in general. Therefore, for each information and computer network, it is necessary to solve the optimization problem of the distribution of a limited information resource in order to obtain the minimum value of a generalized indicator. It is noted that a large number of parameters that influence the distribution of information resources, as well as the variety of quality indicators in determining the characteristics of distribution and the difficulties of their reduction to a single criterion, complicate the methods of solving the problem of information resource distribution rather complicated. At the same time, the essence of this problem is the rational allocation of relational database tables for different types of hardware and software. This allows you to reduce the time spent on processing requests, given the nature of the data processed. The distribution problem is formulated to minimize the access time to distributed relational database tables of the same volume and different probabilities of accessing them. The conclusion is made of the impossibility of its solution by standard methods due to the nonlinearity of restrictions in its production. The method of solving a formulated problem, which is based on the specifics of the limitations of the problem and the objective function, is proposed. The essence of the proposed method is the reduction of permissible solutions based on the account of nonlinearity of connections in the limitations of the problem and the method of ranking the blocks proposed by the authors. The results of experimental verification of the proposed method, which prove its effectiveness, are presented.

Key words: automated control system, information and computing network, distributed relational database

References

1. Кульба В .В. Теоретические основы проектирования оптимальных структур распределенных баз данных / [Кульба В .В., Ковалевский С .С., Косяченко С .А., Сиротюк В .О.] // Серия « Информатизация России на пороге ХХI века» . - М.: СИНТЕГ , 1999 . - 660 с.

5. Субач І .Ю. Моделі розподілу інформаційного ресурусу в АСУ спеціального призначення // І .Ю. Субач, О.М. Чаузов, Н.Г. Кучук // Information Technology and Security . - 2016 . - Vol 4 ., Iss. 1. - P. 74 - 83 .

7. Субач І .Ю. Метод рішення задачі розподілу інформаційного ресурсу в АСУ спеціального призначення при варіативному розмірі інформаційних блоків // І .Ю. Субач, О.М. Чаузов, Н.Г. Кучук // Information Technology and Security . - 2016 . - Vol 4 ., Iss. 2. - P. 269 - 276 .

10. Тжаскалик , Т. Введение в исследование операций с применением компьютера: Пер. с польск . И. Д. Рудинского. / Т. Тжаскалик - Москва : Горячая линия - Телеком , 2009 . - 440 c.

1 Institute for Special Communications and Information Protection of National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" , Kyiv, Ukraine [e-mail]