Побудова та аналіз математичних моделей оптимальної організації та доступу до інформації великих баз даних

Размещено на http://www.allbest.ru/

Національний університет “Львівська політехніка”

УДК 519.68

Побудова та аналіз математичних моделей оптимальної організації та доступу до інформації великих баз даних

01.05.02 - Математичне моделювання та обчислювальні методи

Автореферат дисертації на здобуття наукового ступеня

кандидата технічних наук

Дороцька Христина Степанівна

Львів 2001

Дисертацією є рукопис

Робота виконана у Львівському національному університеті імені Івана Франка Міністерства освіти і науки України

Науковий керівник: Доктор фізико-математичних наук, професор Цегелик Григорій Григорович, завідувач кафедри обчислювальної математики Львівського національного університету імені Івана Франка

Офіційні опоненти:

Доктор технічних наук, старший науковий співробітник Яцимірський Михайло Миколайович, доцент кафедри ЕОМ національного університету «Львівська політехніка».

Доктор технічних наук, доцент Сеньківський Всеволод Миколайович, завідувач кафедри прикладної математики та комп'ютерних інформаційних систем Української академії друкарства (м. Львів).

Провідна установа:

Державний науково-дослідний інститут інформаційної інфраструктури Державного комітету зв'язку та інформатизації і НАН України (м. Львів).

Захист відбудеться 29 червня 2001 р. о 14 годині на засіданні спеціалізованої вченої ради Д 35.052.05 у національному університеті “Львівська політехніка” (79646, Львів-13, вул. С. Бандери, 12, ауд. 226 головного корпусу).

З дисертацією можна ознайомитися у науково-технічній бібліотеці національного університету Львівська політехніка (79013, Львів, вул. Професорська, 1)

Автореферат розісланий 29 травня 2001 р.

Вчений секретар

спеціалізованої вченої ради,

кандидат технічних наук, доцент Ткаченко С.П.

Загальна характеристика роботи

розподіл ймовірність індекс файл

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

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

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

Розвиток першого напрямку привів до створення обчислювальних систем, технічною базою яких стали однопроцесорні та багатопроцесорні ЕОМ, спеціалізовані процесори, машини баз даних і баз знань, мережі ЕОМ, систем розподілених та паралельних баз даних, що стають домінуючими інструментами для створення програм інтенсивної обробки даних.

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

Дана дисертаційна робота присвячена розв'язанню проблеми оптимальної організації та пошуку інформації в базах даних і базах знань, і є продовженням досліджень, розпочатих науковим керівником Г.Г. Цегеликом. В ній розглядається побудова та аналіз математичних моделей оптимальної організації та пошуку інформації в послідовних, одно- та багаторівневих індексно-послідовних файлах в залежності від вибраного варіанту пошуку записів та розподілу ймовірностей звертання до них.

Метою дисертаційної роботи є побудова та аналіз математичних моделей оптимальної організації і доступу до інформації послідовних та індексно-послідовних файлів великих баз даних для однопроцесорних ЕОМ для різних законів розподілу ймовірностей звертання до записів.

Для досягнення цієї мети необхідно розв'язати такі задачі:

побудова математичних моделей організації та пошуку інформації в послідовних на індексно-послідовних файлах для рівномірних та нерівномірних законів розподілу ймовірностей звертання до записів та різних методів пошуку записів в файлі та індексі;

дослідження ефективності методів послідовного перегляду, однорівневого та дворівневого блочного пошуку для різних законів розподілу ймовірностей звертання до записів;

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

визначення оптимальних значень параметрів величини блоків записів для послідовних файлів та величини блоків і підблоків записів файла та елементу індекса для одно- та багаторівневих індексно-послідовних файлів, для рівномірного і нерівномірних законів розподілу ймовірностей звертання до записів та різних методів пошуку;

визначення значень параметра числа рівнів індекса для багаторівневих індексно-послідовних файлів при якому математичне сподівання загального часу, необхідного для пошуку запису в файлі буде мінімальним;

- встановлення картини залежності оптимальних значень параметрів пошуку а також математичного сподівання від зміни варіанту пошуку і закону розподілу ймовірностей звертання до записів;

проведення експериментальних дослідженнь та порівняння їх результатів з одержаними шляхом математичного моделювання.

Об'єкт та предмет дослідження: Об'єктом дослідження є методи організації та пошуку інформації в великих базах даних. Предметом дослідження є методи організації і пошуку інформації в базах даних, записи яких розподілені рівномірно або на основі певних законів нерівномірного розподілу ймовірностей звертання до записів.

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

Наукова новизна одержаних результатів.

Досліджено ефективність методів послідовного перегляду, однорівневого та дворівневого блочного пошуку записів у файлах для таких законів розподілу ймовірностей звертання до записів, як рівномірний і “бінарний”, закон Зіпфа, розподіл, який наближено задовольняє правило “80-20”, та ін. За критерій ефективності прийнято математичне сподівання числа порівнянь, неообхідних для пошуку запису. Це дало можливість порівняти методи пошуку за ефективністю для згаданих законів розподілу ймовірностей звертання до записів і для кожного закону розподілу ймовірностей визначити свій найкращий метод пошуку;

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

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

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

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

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

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

Особистий внесок автора. Автором самостійно виконана основна частина теоретичних досліджень, а також повністю проведена експериментальна робота. В публікаціях, що написані у співавторстві, дисертантові належать: [2] - вивід аналітичних співвідношень для випадку нерівномірних законів розподілу, проведення експериментальних розрахунків; [3] - дослідження ефективності методу блочного пошуку для нерівномірних законів розподілу ймовірностей звертання до записів; [4]: - обчислення похибок наближень та побудова таблиць значень функції ; [5] - вивід основних аналітичних співвідношень для моделювання процесу пошуку інформації в послідовних файлах, визначення оптимальних значень математичного сподівання та параметрів організації та пошуку інформації; [6] - дослідження поведінки функції E/d0 в околі точки мінімуму математичного сподівання; [8] - встановлення оптимальних значень параметрів організації та пошуку інформації в послідовних файлах при яких математичне сподівання загального часу, необхідного для пошуку запису в файлі, буде мінімальним; [9] - вивід основних аналітичних співвідношень для моделювання процесу пошуку інформації в одно- та багаторівневих індексно-послідовних файлах, встановлення оптимальних значень параметрів організації та пошуку інформації, визначення проміжків зміни оптимальних значень параметрів пошуку, в яких математичне сподівання відхиляється від свого оптимального значення не більше ніж на задану величину, дослідження поведінки функції E/d в околі точки мінімуму; [10] - встановлення картини залежності математичного сподівання загального часу, необхідного для пошуку запису в файлі, від зміни закону розподілу ймовірностей та числа рівнів індекса файлу; [11] - розв'язання задачі вибору оптимального числа рівнів індекса в індексно-послідовній організації файлів для різних законів розподілу ймовірностей звертання до записів; [12] - апроксимація часткових сум та неперервними функціями та обчислення відносної похибки цих наближень; [13] - розробка рекомендації щодо вибору параметрів організації послідовного файла та методу доступу до інформації на основі результатів експерименту; [14] - розробка рекомендації щодо вибору параметрів організації однорівневого індексно-послідовного файла та методу доступу до інформації на основі результатів експерименту;

Апробація результатів досліджень. Основні результати досліджень доповідались і обговорювались на: міжнародній науковій конференції “Сучасні проблеми математики” (м. Чернівці, 1998), І-ій міжнародній науково-практичній конференції з програмування УкрПРог'98 (м. Київ, 1998), Всеукраїнській науковій конференції “Використаня обчислювальної техніки, математичного моделювання та математичних методів у наукових дослідженнях” (м. Львів, 1996, 1997, 1999), конференції молодих вчених (м. Львів, 1999 - 13.02.), семінарах з обчислювальної математики Львівського національного університету імені Івана Франка.

Зв'язок роботи з науковими програмами, планами, темами. Дисертація виконувалась в рамках науково-дослідної теми “Побудова та аналіз математичних моделей оптимальної організації та доступу до інформації баз даних для однопроцесорних та багатопроцесорних ЕОМ” та держбюджетної теми ПМ-56Б “Розробка нових підходів та методів чисельного розв'язання задач математичного аналізу, алгебри, диференціальних рівнянь та рівнянь математичної фізики” (номер державної реєстрації 0100U001425) кафедри обчислювальної математики Львівського національного університету ім. Івана Франка.

Публікації. Основні результати дисертації опубліковані в 15 друкованих працях загальним обсягом 170 сторінок, 3 праці написані без співавторів.

Структура і обсяг роботи. Дисертаційна робота складається із вступу і чотирьох розділів, висновку, та списку літературних джерел з 98 найменувань. Робота викладена на 153 сторінках, включаючи 66 рисунки та 45 таблиць.

Зміст дисертації

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

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

Оскільки в більшості систем обробки інформації типовими є випадки нерівномірного розподілу ймовірностей звертання до записів, то оптимальні стратегії пошуку інформації в послідовних файлах будуються як для рівномірного розподілу ймовірностей звертання до записів, так і для різних законів нерівномірного розподілу ймовірностей. Серед законів нерівномірного розподілу ймовірностей звертання до записів розглядаються:

Закон Зіпфа:

де pi - ймовірність звертання до і-го запису файла, N - число записів файла,

узагальнений закон розподілу:

де

0 < c < 1, (частковим випадком цього закону при с=0.8614 є розподіл, який приблизно задовольняє правилу "80-20");

"бінарний" розподіл :

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

Серед методів пошуку записів розглядаються послідовний перегляд, блочний пошук, дворівневий блочний пошук, блочний пошук з попередньою локалізацією блоків записів в основній та в зовнішній пам'яті.

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

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

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

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

У першому підрозділі розглядається побудова оптимальних стратегій пошуку записів в послідовних файлах. Використовуються такі варіанти пошуку: послідовне читання блоків записів в основну пам'ять і їх послідовний перегляд; послідовний перегляд записів блоку, який попередньо локалізований шляхом читання блоків записів в основну пам'ять і перегляду їх останніх записів; читання і послідовний перегляд записів блоку, який попередньо локалізований шляхом перегляду в зовнішній пам'яті останніх записів блоків.

Припускається, що послiдовний впоpядкований файл, який мiстить N записiв, збеpiгається у зовнішній пам'ятi ЕОМ. Всі записи файла pозбитi на n блокiв по m записiв у кожному. Hехай a=b+dm - час читання блоку записiв в основну пам'ять, де b, d - деякi константи; t i t1 - час пеpегляду запису вiдповiдно в основнiй i зовнішнiй пам'ятi (t1=t+b+d); pi -ймовipнiсть звеpтання до i-го запису файла; E - математичне сподiвання загального часу, необхiдного для пошуку запису в файлi. Тоді в залежності від варіанту пошуку Е виразиться такими формулами:

для першого варіанту пошуку

для другого варіанту пошуку

для третього варіанту пошуку

В роботі знайдений явний вираз для Е у цих трьох випадках для різних законів розподілу ймовірностей звертання до записів і виведені співвідношення для знаходження значень параметрів n і m, при яких математичне сподівання досягає мінімуму. Встановлено картину залежності оптимального значення математичного сподівання від варіанту пошуку і зміни закону розподілу ймовірностей звертання до записів (Рис. 1). Для всіх розглянутих законів розподілу ймовірностей звертання до записів, крім “бінарного”, найкращим варіантом пошуку є третій, який за ефективністю суттєво відрізняється від перших двох. Для “бінарного” закону розподілу ймовір-ностей найкращим є перший варіант пошуку.

У другому підрозділі побудовано математичні моделі пошуку в однорівневих індексно-послідовних файлахі, що містяться в зовнішній пам'яті ЕОМ. Як і у випадку послідовних файлів, N - число записів файла; m - розмір блоків записів файла; n - розмір індекса; t0 і t1 - час перегляду відповідно запису файла і елемента індекса; a0=b0+d0m і a1=b1+d1n - час доступу відповідно до блоку записів файла і індекса, де b0, b1, d0, d1 - деякі константи; pi - ймовірність звертання до і-го запису файла; Е - математичне сподівання загального часу, необхідного для пошуку записiв файлі. При побудові моделей оптимальної організації однорівневих індексно-послідовних файлів розглянуто три варіанти пошуку:

в індексі і блоках записів файла для пошуку використовується метод послідовного перегляду;

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

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

Тоді в залежності від вибраного варіанту пошуку Е виразиться такими формулами:

для першого варіанту пошуку

для другого варіанту пошуку

для третього варіанту пошуку

де l - розмір блоків індекса, а h - розмір підблоків записів файла.

Знайдено явний вираз для Е у цих трьох випадках для розглянутих законів розподілу ймовірностей звертання до записів і виведені співвідношення для знаходження значень параметрів, при яких математичне сподівання досягає мінімуму. Побудована картина залежності оптимального значення математичного сподівання від варіанту пошуку і зміни закону розподілу ймовірностей звертання до за-писів. В порівнянні з послідовними файлами однорівнева індексно-послідовна організація файлів набагато ефективніша для всіх законів розподілу ймовірностей звертання до записів (Рис. 2).

У третьому підрозділі розглядається r-рівневий індексно-послідовний файл (r>2), який знаходиться в зовнішній пам'яті ЕОМ. Нехай N - число записів файла, ni (i=1,2,...,r) - розмір блоків індекса на i-му рівні; n0 -розмір блоків записів файлу; ai=bi+dini (i=1,2,...,r) - час доступу до блоку індекса i-го рівня, де bi, di - деякі константи; a0=b0+d0n0 - час доступу до блоку записів файла, де b0, d0 - деякі константи; ti (i=1,2,...,r) - час перегляду елемента індекса на i-му рівні; t0 - час перегляду запису файла в локалізованому блоці; pi - ймовірність звертання до i-го запису файла; Е - математичне сподівання загального часу, необхідного для пошуку запису в файлі. Тоді при використанні в індексі і файлі методу послідовного перегляду Е виразиться формулою

Знайдено явний вираз для Е у випадку різних законів розподілу ймовірностей звертання до записів і виведені співвідношення для визначення параметрів ni (i=0,1,…,r), при яких математичне сподівання досягає мінімуму, а також для кожного конкретного закону розподілу ймовірностей звертання до записів знайдено оптимальне число рівнів індекса r (Рис. 3).

Рис. 3. Оптимальні значення математичного сподівання загального часу, необхідного для пошуку запису в багаторівневому індексно-послідовному файлі для різних значень числа рівнів індекса r для рівномірного закону розподілу ймовірностей та розподілу Зіпфа при N=104.

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

Основні результати роботи та висновки

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

У дисертаційній роботі одержано такі основні результати:

1. Визначені значення параметрів оптимальної організації і пошуку записів в послідовних, однорівневих та багаторівневих індексно-послідовних файлах баз даних, для яких математичне сподівання загального часу, необхідного для пошуку запису, досягає мінімуму, для рівномірного та різних законів нерівномірного розподілу ймовірностей звертання до записів (”бінарного” розподілу, закону Зіпфа, розподілу, що приблизно задовольняє правилу “80.20” та ін.);

2. Досліджена ефективність основних методів пошуку записів в файлах таких як послідовний перегляд, блочний пошук та дворівневий блочний пошук для різних законів розподілу ймовірностей звертання до записів. Для кожного закону розподілу ймовірностей визначено метод пошуку, при якому кількість порівнянь, необхідних для знаходження запису в файлі буде найменшою;

3. Удосконалено метод бісекції розв'язування трансцендентних рівнянь, для систем трансцендентних рівнянь складної конфігурації, до яких зводяться задачі побудови оптимальних моделей багаторівневих індексно-послідовних файлів для таких законів розподілу ймовірностей звертання до записів, як “бінарний”, закон Зіпфа, розподіл, який наближено задовольняє правило “80-20” та ін.;

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

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

6. Експериментально, шляхом комп'ютерного моделювання, розв'язана задача вибору оптимального числа рівнів індекса в індексно-послідовній організації файлів для різних законів розподілу ймовірностей звертання до записів;

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

Основні положення за темою дисертації опубліковано у 15 наукових працях

1. Дороцька Х.С. Побудова оптимальних моделей однорівневих індексно-послідовних файлів при використанні для пошуку в індексі і в файлі методу блочного пошуку // Вісн. держ. ун-ту “Львівська політехніка”. Сер. “Інформаційні системи і мережі”, вип. 3, №383, Львів 1999, С. 56-62.

2. Філяк М.І., Цегелик Г.Г., Дороцька Х.С. Порівняльний аналіз ефективності методу послідовного перегляду для різних законів розподілу ймовірностей звертання до записів // Вісн. держ. ун-ту “Львівська політехніка”. Сер. “ Інформаційні системи та мережі ”, №406, Львів 2000, С. 226 - 231.

3. Цегелик Г.Г., Філяк М.І., Дороцька Х.С. Порівняльний аналіз методу блочного пошуку для різних законів розподілу ймовірностей звертання до записів // Комп'ютерні технології друкарства, №5, 2000, С. 320-326.

4. Цегелик Г.Г., Кудеравець Х.С. Апроксимація часткових сум узагальнених гармонічних рядів неперервними функціями // Вісн. Львів. ун-ту. Сер. мех.-мат., 1995, вип. 42, С. 17-19.

5. Дороцька Х.С., Цегелик Г.Г. Побудова та аналіз оптимальних стратегій пошуку інформації в послідовних файлах для різних законів розподілу ймовірностей звертання до записів // Вісн. Львів. ун-ту. Сер. мех.-мат., 1997, вип. 46, С. 49-57.

6. Дороцька Х.С., Цегелик Г.Г. До побудови оптимальних моделей однорівневих індексно-послідовних файлів // Вісн. Львів. ун-ту. Сер. мех.-мат., 1998, вип. 50, С. 75-77.

7. Дороцька Х.С. Аналіз оптимальних моделей r -рівневих індексно-послідовних файлів для різних законів розподілу ймовірностей звертання до записів // Вісн. Львів. ун-ту. Сер. “Прикладна математика та інформатика”, 1999, вип. 1 С. 105-108.

8. Кудеравець Х.С., Цегелик Г.Г. Побудова та аналіз оптимальних стратегій пошуку записів в послідовних файлах для різних законів розподілу ймовірностей звертання до записів. Львів: 1997. 70 c. / Препринт (Львівський державний університет ім. І. Франка №1-97).

9. Дороцька Х.С, Цегелик Г.Г. Побудова та аналіз оптимальних стратегій пошуку інформації в однорівневих індексно-послідовних файлах для різних законів розподілу ймовірностей звертання до записів. Львів: 1998. 59 с. / Препринт (Львівський державний університет ім. І. Франка; №1-98).

10. Дороцька Х.С., Цегелик Г.Г. Математичне моделювання оптимального доступу до інформації файлів баз даних // Матер. Міжнар. наук. конф. "Сучасні проблеми математики", м.Чернівці, 22-28 червня 1998р. Чернівці-Київ, 1998, Ч.1, С. 187-190.

11. Цегелик Г.Г., Дороцька Х.С. Побудова та аналіз моделей оптимального доступу до інформації файлів баз даних для різних законів розподілу ймовірностей звертання до записів // Праці першої Міжнар. наук.-практ. конф. з програмування “УкрПрог'98”, м. Київ, 2-4 вересня 1998 р. Київ, 1998, С. 419-426.

12. Цегелик Г.Г., Кудеравець Х.С. Апроксимація часткових сум узагальнених гармонічних рядів неперервними функціями // Депоновано в ДНТБ України, 16 липня 1995 року, №1964-Ук95, 9 с.

13. Кудеравець Х.С., Цегелик Г.Г. Оптимальні стратегії пошуку записів в послідовних файлах // Тез. доп. Всеукр. наук. конф. „Використання обчислювальної техніки, математичного моделювання і математичнох методів в наукових дослідженнях“, м. Львів, 24-26 вересня 1996. Львів. 1996. С. 52.

14. Кудеравець Х.С., Цегелик Г.Г. Аналіз моделей оптимальної організації і пошуку інформації в однорівневих індексно-послідовних файлах // Тез. доп. Всеукр. наук. конф. „Використання обчислювальної техніки, математичного моделювання і математичних методів в наукових дослідженнях“, м.Львів, 16-18 вересня 1997. Львів. 1997. С. 54.

15. Дороцька Х.С. Аналіз оптимальних моделей r -рівневих індексно-послідовних файлів для різних законів розподілу ймовірностей звертання до записів // Тез. доп. Всеукр. наук. конф. „Використання обчислювальної техніки, математичного моделювання і математичнох методів в наукових дослідженнях“. м. Львів, 23 вересня 1999, С. 45.

Анотація

Дороцька Х.С. Побудова та аналіз математичних моделей оптимальної організації та доступу до інформації великих баз даних.-Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 01.05.02 - “Математичне моделювання та обчислювальні методи”. - національний університет “Львівська політехніка”, Львів, 2001.

Дисертація присвячена питанню побудови та аналізу математичних моделей різних варіантів доступу до записів послідовних, однорівневих, та багаторівневих індексно-послідовних файлів для різних законів розподілу ймовірностей звертання до записів (рівномірного і “бінарного”, закону Зіпфа, розподілу, який наближено задовольняє правилу “80-20” та ін.). Вперше розв'язано задачу вибору оптимального числа рівнів індекса для багаторівневих індексно-послідовних файлів. Проведено порівняльний аналіз оптимальних варіантів доступу та розроблено рекомендації щодо вибору оптимальної організації і доступу до інформації файлів баз даних для кожного конкретного закону розподілу ймовірностей звертання до записів.

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

Аннотация

Дороцкая К.С. Построение и анализ математических моделей оптимальной организации и доступа к информации больших баз данных.-Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 01.05.02 - “Математическое моделирование и вычислительные методы”. - национальнный университет “Львивська политехника”, Львов, 2001.

Диссертация посвящена вопросу построения и анализа математических моделей различных вариантов доступа к записям последовательных, одноуровневых, и многоуровневых индексно-последовательных файлов для различных законов распределения вероятностей обращения к записям (равномерного и “бинарного”, закона Зипфа, распределения, что приблизительно удовлетворяет правило “80-20” и др.). Впервые решено задачу выбора оптимального числа уровней индекса для многоуровневых индексно-последовательных файлов. Проведено сравнительный анализ оптимальных вариантов доступа и разработано рекомендации по выбору оптимальной организации и доступа к информации файлов баз данных для каждого конкретного закона распределения вероятностей обращения к записям.

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

Annotation

Dorotska Ch. S. Construction and analysis of mathematical models of optimal organization and access to the information in large databases. - Manuscript.

A thesis for a Ph.D. science degree by specialty 01.05.02 - “Mathematical modeling and calculating methods”. - National university "Lvivska Polytechnika", Lviv, 2001.

The thesis is dedicated to problems of optimal organization and search in sequential, one-level and multi-level index-sequential files of the large data bases for various laws of probabilities distribution of requesting to records. Because in the most systems of information processing typical are falls of not regular laws of distribution, the optimal strategy of information search were constructed for both regular and various not regular distribution of probabilities of requesting to records. For the first time was solved the problem of choice of optimal index level for multi-level index-sequential files. In the thesis was leaded the comparison analysis of optimal access variants and developed some recommendations for selection of optimal organization and access methods to the information in databases for each concrete law of probabilities distribution of requesting to records.

Besides was investigated the effectiveness of the main used search methods: sequential search, block search and two level block search. As criterion of optimum was supposed the mathematical expectation of the number of comparisons needed to find a record in the file. To solve the task of finding the minimum of the function of mathematical expectation it was necessary to approximate some partial sums of generalized harmonious serial with uninterrupted functions. Some such approximation was proposed and the related deviation was been calculated.

As mentioned above, the optimal strategy of information search were constructed for both regular and various not regular distribution of probabilities of requesting to records. As not regular laws of distribution of probabilities of requesting to records are considered: Zipfian law, binary law, law that approximate an “80-20” rule and some other.

This approach make possible not only construction of optimal strategies to access to the information for selected variant of search and a given law of probability distribution of requesting to records, but also found a dependence on this strategies from the change of search method and from the change of probability distribution laws.

As criterion of optimum by construction of optimal access methods are supposed the mathematical expectation of the whole time needed to search a record in the file.

For each search variant and each concrete law of probability distribution is founded the evident expression for the mathematical expectation. Using this expression will be founded this parameter values, for which the mathematical expectation function reaches its minimum. Besides was investigated the behaviour of this function in the environs of its minimum point and were built parameter change intervals, on which the mathematical expectation deviate from its optimal value not more, than in an in advance determined constant.

Using the optimal parameter values, for which the function reach its minimum, can be founded the dependence of optimal variants of searching from the law of probabilities distribution of requesting to records and from the searching strategies. For each specific law of probabilities distribution can be founded the best searching method. The best search time in case of sequential files was reached with using of block search method with previous location ob record-blocks in external memory. This result was better than with sequential checking algorithm. In case of one-level index-sequential files the difference between using of various search methods was not so high, though the shortest searching time is needed for search with two-level block search. If are used the multi-level index-sequential file organization, the searching time will be a little lower, and this difference decrease with increasing of index level number, until will be reached the optimal number of index level.

The last chapter of this thesis contains the description and the experimental results of use described in the theoretical part strategies of optimal organization of information, access and searching of records. The theoretical results were employed in the normative-inquiry information database that is used in the information and computer technologies department of “Iskra” company in Lviv. The database records were distributed in accordance with Zipfian model. The database files were organized as sequential and one-level index-sequential files. As searching methods were used sequential checking and block search with previous location ob record- blocks in main and in external memory.

Keywords: database, law of distribution of probabilities of requesting to records, mathematical expectation, index-sequential file organization, block search.

Размещено на Allbest.ru

...