Моделювання та оптимізація доступу до інформації файлів баз даних
Ефективність методів пошуку інформації у файлах баз даних для законів розподілу ймовірностей звертання до записів. Побудова схем методів та розробка нових підходів до пошуку інформації у файлах. Кількість рівнів для методу r–рівневого блочного пошуку.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | автореферат |
| Язык | украинский |
| Дата добавления | 26.08.2015 |
| Размер файла | 63,6 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Національний університет “Львівська політехніка”
УДК 004.451.53 + 004.658
Автореферат
дисертації на здобуття наукового ступеня
кандидата технічних наук
Моделювання та оптимізація доступу до інформації файлів баз даних
Спеціальність 01.05.03 - математичне та програмне
забезпечення обчислювальних машин і систем
Мельничин Андрій Володимирович
Львів - 2009
Дисертацією є рукопис
Робота виконана у Львівському національному університеті імені Івана Франка Міністерства освіти і науки України
Науковий керівник:
доктор фізико-математичних наук, професор
Цегелик Григорій Григорович,
Львівський національний університет імені Івана Франка, завідувач кафедри математичного моделювання соціально-економічних процесів
Офіційні опоненти:
доктор технічних наук, доцент
Романишин Юрій Михайлович,
Національний університет “Львівська політехніка”,
проф. кафедри електронних засобів інформаційно-комп'ютерних технологій
кандидат технічних наук, доцент
Томашевський Олег Михайлович,
Львівська філія Європейського університету,
завідувач кафедри математики та комп'ютерних дисциплін
Захист відбудеться “09” квітня 2009р. о 16 годині на засіданні спеціалізованої вченої ради Д 35.052.05 у Національному університеті “Львівська політехніка” (79013, м. Львів, вул. Степана Бандери, 12).
З дисертацією можна ознайомитися у науково-технічній бібліотеці Національного університету “Львівська політехніка” (79013, м. Львів, вул. Професорська, 1)
Автореферат розісланий “6” березня 2009 р.
Вчений секретар
спеціалізованої вченої ради,
доктор технічних наук, професор Р. А. Бунь
Загальна характеристика роботи
Актуальність теми. Однією з тенденцій розвитку сучасної індустрії інформатики є створення обчислювальних систем, здатних опрацьовувати величезні обсяги інформації в режимі реального або мінімального масштабу часу. Головна концепція проектування таких систем - забезпечення їх високої продуктивності. Одним із напрямів реалізації вказаної концепції є удосконалення технології опрацювання інформації в обчислювальних системах. Оскільки основу сучасних інформаційних технологій складають бази даних (БД) і системи керування базами даних (СКБД), то удосконалення технології опрацювання інформації з використанням концепції баз даних передбачає в першу чергу розв'язання проблеми оптимальної організації та пошуку інформації у файлах баз даних. Така організація забезпечує доступ користувачів до інформації БД за мінімально допустимий час і в значній мірі визначається ефективністю методів пошуку інформації у файлах БД.
Дисертаційна робота присвячена дослідженню ефективності основних методів пошуку інформації у файлах БД, побудові оптимальних схем методів і розробці нових підходів до пошуку інформації у файлах великих БД. Оскільки в багатьох системах опрацювання інформації типовими є випадки нерівномірного розподілу ймовірностей звертання до записів файлів, на що вказують багато зарубіжних авторів, зокрема, Д. Кнут, Б. Шнейдерман та ін., то дослідження ефективності та побудова оптимальних схем методів в роботі проводиться як для рівномірного розподілу ймовірностей звертання до записів, так і для низки законів нерівномірного розподілу, серед яких є такі близькі до дійсності розподіли, як закон Зіпфа, розподіл, що наближено задовольняє правило “80 - 20”, та ін. Такий підхід дає можливість не тільки дослідити ефективність того чи іншого методу пошуку і побудувати для нього оптимальну схему для конкретного закону розподілу ймовірностей звертання до записів, а й мати картину залежності ефективності методу від зміни закону розподілу ймовірностей.
Теоретичною та методологічною основою дослідження стали праці таких вчених, як В. М. Глушков, С. С. Лавров, А. А. Стогній, Д. Кнут, Дж. Мартін, Б. Шнейдерман та ін., а також аналіз існуючих систем опрацювання інформації, в основі яких лежить концепція БД та баз знань (БЗ). При проведенні дослідження використано підхід, запропонований керівником дисертаційної роботи Г. Г. Цегеликом.
Зв'язок роботи з науковими програмами, планами, темами
Дисертаційна робота виконана в рамках науково-дослідних тем кафедри математичного моделювання соціально-економічних процесів Львівського національного університету імені Івана Франка:
1. “Побудова та аналіз математичних моделей оптимальної організації та доступу до інформації баз даних для однопроцесорних та багатопроцесорних ЕОМ”, № держ. реєстрації 0103U001083 (1999 -2005рр.). Автором проведено дослідження ефективності методів пошуку для різних законів розподілу ймовірностей звертання до записів для однопроцесорних ЕОМ, розроблено оптимальні схеми цих методів.
2. “Математичне моделювання природничих, інформаційних та соціально-економічних процесів”, № держ. реєстрації 0106U005905 (2006 - 2008рр.). Автор розробив метод пошуку інформації у файлах баз даних, який враховує розподіл ймовірностей звертання до записів, та наближений метод пошуку інформації у файлах, який використовує апроксимацію значень ключа неперервними функціями. Реалізовано СКБД, яка, в залежності від закону розподілу ймовірностей звертання до записів, для пошуку записів використовує найефективніший метод.
Мета і завдання дослідження
Метою дисертаційної роботи є дослідження ефективності методів пошуку інформації у файлах баз даних для різних законів розподілу ймовірностей звертання до записів, побудова оптимальних схем методів та розробка нових підходів до пошуку інформації у файлах великих баз даних.
Мета дисертаційної роботи визначає необхідність розв'язання таких завдань:
· Проаналізувати відомі результати дослідження ефективності методів пошуку інформації у файлах баз даних.
· Вивести співвідношення для визначення параметрів оптимального пошуку записів для відомих методів у випадку різних законів розподілу ймовірностей звертання до записів.
· Провести порівняльний аналіз ефективності методів для різних законів розподілу ймовірностей звертання до записів і для кожного закону визначити найкращий метод пошуку.
· Для методу r - рівневого (r > 2) блочного пошуку визначити оптимальну кількість рівнів для різних законів розподілу ймовірностей звертання до записів.
· Розробити метод пошуку записів у файлах баз даних, який враховує
розподіл імовірностей звертання до записів.
· Дослідити можливість використання методу найменших квадратів для побудови наближених чисельних методів пошуку записів у файлах баз даних.
· Розробити систему керування базами даних, яка, використовуючи інформацію про закон розподілу ймовірностей звертання до записів, дала б можливість організувати ефективний пошук інформації.
Об'єктом дослідження є процес пошуку інформації у файлах баз даних.
Предметом дослідження є розробка оптимальних схем методів пошуку інформації у файлах баз даних для різних законів розподілу ймовірностей звертання до записів.
Методи дослідження. В основі досліджень лежить підхід, запропонований керівником дисертаційної роботи Г. Г. Цегеликом, для розв'язання задач в рамках проблеми оптимальної організації та пошуку інформації у файлах баз даних як для однопроцесорних, так і для багатопроцесорних ЕОМ. Результати дослідження одержані при використанні теорії організації баз даних та баз знань, чисельних методів аналізу, методів теорії ймовірностей, математичної статистики, дослідження операцій та системного аналізу, а також експериментальних методів досліджень. пошук інформація ймовірність блочний
Наукова новизна одержаних результатів. В результаті проведених досліджень в дисертації отримано такі нові наукові результати:
· вперше проведено дослідження ефективності методів послідовного перегляду, однорівневого, дворівневого, r - рівневого (r > 2) блочного та двійкового пошуку для таких законів розподілу ймовірностей звертання до записів, як рівномірний, “бінарний”, Зіпфа та узагальнений, частковим випадком якого є розподіл, що наближено задовольняє правило “80 - 20”, що дало можливість для кожного закону розподілу ймовірностей звертання до записів визначити свій найкращий метод пошуку;
· розроблено метод пошуку інформації у файлах баз даних, який враховує розподіл ймовірностей звертання до записів і є значно ефективнішим в порівнянні з відомими методами для усіх законів нерівномірного розподілу ймовірностей, крім рівномірного для методу двійкового пошуку і “бінарного” для методу послідовного перегляду; у випадку рівномірного розподілу ймовірностей метод збігається з методом двійкового пошуку; у випадку “бінарного” розподілу - з методом послідовного перегляду;
· вперше визначено оптимальну кількість рівнів для r - рівневого блочного пошуку для усіх розглянутих законів розподілу ймовірностей звертання до записів, що дало можливість побудувати оптимальні схеми методів, тобто схеми, за яких математичне сподівання кількості порівнянь, необхідних для пошуку запису, досягає мінімуму;
· розроблено підхід до побудови наближених методів пошуку інформації у файлах баз даних, що використовує апроксимацію значень ключа, яким характеризуються записи файла, що дало можливість розробляти методи, які враховують розподіл значень ключа і ефективність яких не залежить від розподілу ймовірностей звертання до записів.
Практичне значення одержаних результатів. Результати дослідження є значним внеском у розвиток практики створення систем баз даних та баз знань. На основі досліджень спроектовано та розроблено тестову систему керування базами даних, яка дає можливість організовувати ефективний пошук інформації, використовуючи інформацію про закон розподілу ймовірностей звертання до записів.
Впровадження результатів роботи. Основні результати, отримані при виконанні дисертаційної роботи, використано для розробки пошукової системи у портальній системі Львівської обласної державної телерадіокомпанії (м. Львів), а також впроваджені у навчальний процес на факультеті прикладної математики та інформатики Львівського національного університету імені Івана Франка: вони використовуються при читанні курсів “Основи інформаційних технологій” та “Сучасні інформаційні технології”, при написанні курсових та дипломних робіт.
Особистий внесок здобувача. Усі наукові результати, подані у дисертації, одержані здобувачем особисто. У друкованих працях, опублікованих у співавторстві, автору належать: [1, 8] - порівняльний аналіз ефективності методів послідовного перегляду, однорівневого та багаторівневого блочного і двійкового пошуку для різних законів розподілу ймовірностей звертання до записів, [2, 9] - формули для обчислення оптимальної кількості рівнів в методі r-рівневого блочного пошуку для різних законів розподілу ймовірностей звертання до записів, [3, 4] - алгоритм методу, який враховує розподіл ймовірностей звертання до записів, формули для обчислення математичного сподівання кількості порівнянь, необхідних для пошуку запису у файлі у випадку “бінарного” закону розподілу ймовірностей звертання до записів, [5] - розробка наближених методів пошуку інформації у файлах баз даних, [6] - порівняння ефективності різних методів пошуку з ефективністю методу, який враховує розподіл імовірностей звертання до записів, [7] - розробка оптимальних схем методів однорівневого та дворівневого блочного пошуку, [10, 15] - порівняльний аналіз ефективності методів пошуку для різних законів розподілу ймовірностей звертання до записів, [16 -18] - нові підходи до пошуку інформації у файлах великих баз даних.
Апробація результатів дисертації. Основні результати дисертаційної роботи представлялися та обговорювалися на:
Всеукраїнських наукових конференціях “Сучасні проблеми прикладної математики та інформатики” (Львів, 2004 - 2007 рр.), міжнародній науково-практичній конференції студентів, аспірантів та молодих вчених, присвяченої 60-річчю Великої Перемоги (Київ, 2005), Конференції молодих вчених, із сучасних проблем механіки і математики імені Я. С. Підстригача (Львів, 2005), Міжнародній науково-практичній конференції “Розвиток досліджень 2005” (Полтава, 2005), Всеукраїнській науковій конференції молодих науковців “ІТОНТ” (Черкаси, 2006), XIII міжнародній конференції з автоматичного управління “Автоматика 2006” (Вінниця, 2006), Четвертій міжнародній науково-практичній конференції студентів, аспірантів та молодих вчених (Київ, 2006), відкритій науково-технічній конференції молодих науковців і спеціалістів фізико-механічного інституту ім. Г. В. Карпенка НАН України „КМН - 2007” (Львів, 2007), а також на семінарах кафедри математичного моделювання соціально-економічних процесів і кафедри дискретного аналізу та інтелектуальних систем (2004 - 2008рр.).
Публікації. Основні результати дисертаційного дослідження опубліковані у 19 наукових публікаціях, в тому числі 8 праць у фахових наукових виданнях, (7 статей у фахових виданнях з технічних наук і одна стаття у фаховому збірнику з фізико-математичних наук) та 11 публікацій у матеріалах та тезах доповідей наукових конференцій.
Структура та обсяг роботи. Дисертація складається зі вступу, чотирьох розділів, висновків, додатків та списку використаної літератури. Загальний обсяг дисертації 147 сторінок, на яких представлено 14 таблиць, 51 рисунок, 3 додатки, 105 найменувань літературних джерел, що розміщені на 12 сторінках.
Основний зміст роботи
У вступі наведено загальну характеристику роботи, обґрунтовано її актуальність, сформульовано мету та основні задачі дослідження, наукову новизну роботи та практичну цінність одержаних результатів, її апробацію та публікації.
У першому розділі наведено огляд літературних джерел за темою дисертаційного дослідження, обґрунтовано вибір теми роботи, подано загальну постановку задачі та методи її розв'язання.
Оскільки у більшості систем опрацювання інформації типовими є випадки нерівномірного розподілу ймовірностей звертання до записів, то дослідження ефективності методів пошуку інформації у файлах баз даних здійснюється як для рівномірного, так і для різних законів нерівномірного розподілу ймовірностей звертання до записів. Серед законів нерівномірного розподілу ймовірностей в дисертаційній роботі розглянуто:
· закон Зіпфа , де _ ймовірність звертання до і _ го запису файла,
частинна сума гармонічного ряду, N _ кількість записів файла;
· узагальнений закон розподілу
,
де с _ будь-який параметр (), _ частинна сума узагальненого гармонічного ряду (при с = 0,8614 частковим випадком цього закону є розподіл, що наближено задовольняє правило “80-20”);
· “бінарний” розподіл , .
За критерій ефективності прийнято математичне сподівання кількості порівнянь, необхідних для пошуку запису у файлі. Обраний підхід дає можливість не тільки дослідити ефективність різних методів пошуку інформації у файлах баз даних для кожного конкретного закону розподілу ймовірностей звертання до записів, але й встановити картину залежності ефективності пошуку як від зміни методу, так і від зміни закону розподілу ймовірностей звертання до записів і для кожного конкретного закону розподілу ймовірностей звертання до записів визначити свій найкращий метод пошуку.
У другому розділі розглянуто такі методи пошуку, як послідовний перегляд, блочний пошук, дворівневий блочний пошук, r-рівневий (r > 2) блочний та двійковий пошук. Для кожного методу пошуку спочатку наведено формули для обчислення математичного сподівання для розглянутих законів розподілу ймовірностей звертання до записів, а після цього здійснено порівняльний аналіз ефективності методів. При цьому вважається, що послідовний файл, в якому здійснюється пошук, є впорядкованим при використанні всіх методів пошуку (крім послідовного перегляду) і містить N записів.
Для кожного методу пошуку наведено залежність математичного сподівання кількості порівнянь, необхідних для пошуку запису у файлі, від зміни закону розподілу ймовірностей звертання до записів, а також від зміни кількості записів у файлі. Для методів пошуку отримано значення параметрів, за яких математичне сподівання кількості порівнянь, необхідних для пошуку запису у файлі, досягає мінімуму. У випадку однорівневого, дворівневого та r - рівневого (r > 2) блочного пошуку розроблено оптимальні схеми методів для різних законів розподілу ймовірностей звертання до записів, тобто схеми, за яких математичне сподівання досягає мінімуму. Крім того, наведено оптимальні схеми доступу до інформації послідовних і індексно-послідовних файлів для різних законів розподілу ймовірностей звертання до записів, встановлена залежність цих схем від зміни закону розподілу ймовірностей звертання до записів.
Для методу послідовного перегляду математичне сподівання кількості порівнянь Е, необхідних для пошуку запису у файлі, для різних законів розподілу ймовірностей звертання до записів виражається формулами:
- у випадку рівномірного розподілу ймовірностей:
- для закону Зіпфа з точністю до нескінченно малої величини:
, де С=0,577… _ ейлерова стала;
- для „бінарного” розподілу ймовірностей:
- у випадку узагальненого закону розподілу ймовірностей з точністю до нескінченно малої величини:
де - певні сталі, - повільно зростаюча функція.
У випадку блочного пошуку з оптимальним розміром блоків формули обчислення математичного сподівання для різних законів розподілу ймовірностей звертання до записів є такими:
- для рівномірного розподілу ймовірностей: ;
- для закону Зіпфа з достатньо високою точністю:
,
де _ , n - додатний корінь рівняння ;
- у випадку „бінарного” розподілу ймовірностей з точністю до нескінченно малої величини:
де m - додатний корінь рівняння
- для узагальненого закону розподілу ймовірностей (з достатньо високою точністю):
де n - додатний корінь рівняння
.
Для методу дворівневого блочного пошуку з оптимальним розміром блоків і підблоків математичне сподівання для різних законів розподілу ймовірностей звертання до записів обчислюється за формулами:
- у випадку рівномірного розподілу ймовірностей: ;
- для закону Зіпфа з достатньо високою точністю:
- для „бінарного” розподілу ймовірностей з точністю до нескінченно малої величини , де l - кількість підблоків, s - кількість записів у кожному підблоці; при цьому показано, що при (на множині цілих чисел в області ,);
- у випадку узагальненого закону розподілу ймовірностей з достатньо високою точністю:
Зазначимо, що у випадку „бінарного” закону розподілу ймовірностей із ростом r математичне сподівання кількості порівнянь, необхідних для пошуку запису у файлі, при використанні r-рівневого блочного пошуку, зростає. Тому для r-рівневого блочного пошуку при випадок „бінарного” закону розподілу ймовірностей не розглядається.
Для r - рівневого (r > 2) блочного пошуку з оптимальним розміром блоків на всіх рівнях формули для знаходження математичного сподівання для різних законів розподілу ймовірностей звертання до записів є такими:
- у випадку рівномірного розподілу ймовірностей:
;
- для закону Зіпфа з достатньо високою точністю:
- у випадку узагальненого закону розподілу ймовірностей з достатньо високою точністю:
;
Визначено оптимальну кількість рівнів для r - рівневого блочного пошуку для усіх розглянутих законів розподілу ймовірностей звертання до записів. Зазначимо, що у випадку рівномірного закону розподілу ймовірностей обчислене на основі виведеного виразу , де - корінь рівняння , а у разі закону Зіпфа та узагальненого закону розподілу (для різних с), використовуючи числовий експеримент, знайдені інтервали для .
На рис. 1 показано залежність математичного сподівання кількості порівнянь, необхідних для пошуку запису в файлі, від зміни закону розподілу ймовірностей звертання до записів для деяких r при
Встановлено, що за рівномірного розподілу ймовірностей, пошук є оптимальним при r = 10, у разі закону Зіпфа - при r = 7, у випадку узагальненого закону розподілу, значення r зменшується від 10 до 7 при зростанні значень параметра с.
Для двійкового пошуку математичне сподівання у разі рівномірного розподілу ймовірностей звертання до записів виражається формулою
,.
У випадку нерівномірних законів розподілу ймовірностей звертання до записів отримано формулу для обчислення математичного сподівання
де l - будь-яке натуральне число, , . Обчислення математичного сподівання для будь-якого N проводилося за алгоритмом методу.
Проведено порівняльний аналіз ефективності різних методів пошуку інформації у файлах баз даних для різних законів розподілу ймовірностей звертання до записів (див. рис. 2). На цьому рисунку: 1 - метод послідовного перегляду; 2 - метод двійкового пошуку; 3 - метод блочного пошуку з оптимальним розміром блоків; 4 - метод дворівневого блочного пошуку з оптимальним розміром блоків і підблоків.
Крім того, для кожного конкретного закону розподілу ймовірностей визначено свій найкращий метод пошуку.
Так, у випадку рівномірного розподілу ймовірностей звертання до записів найкращим методом є двійковий пошук, у разі “бінарного” розподілу ймовірностей найкращим методом є послідовний перегляд, а у випадку закону Зіпфа та узагальненого розподілу ймовірностей найкращим методом є блочний пошук.
У третьому розділі розроблено нові підходи до пошуку інформації у файлах баз даних. Зокрема, пропонується метод пошуку інформації у файлах баз даних, який враховує розподіл імовірностей звертання до записів. Для цього методу введено поняття умовно середнього серед записів файла, виведено формули для його обчислення, формули для математичного сподівання. Здійснено порівняльний аналіз ефективності запропонованого методу для різних законів розподілу ймовірностей звертання до записів, а також із відомими методами пошуку інформації у файлах баз даних.
Метод пошуку, який враховує розподіл імовірностей звертання до записів. У випадку рівномірного розподілу ймовірностей звертання до записів метод збігається із методом двійкового пошуку.
Якщо ймовірності звертання до записів задовольняють “бінарний” закон розподілу, то для математичного сподівання при і одержано відповідно такі формули:
, .
Для знаходження математичного сподівання у разі закону Зіпфа та узагальненого розподілу використано алгоритм методу.
Проведено порівняльний аналіз ефективності методу пошуку, який враховує розподіл імовірностей звертання до записів, із відомими методами пошуку інформації (див. рис. 3).
Метод, що враховує розподіл ймовірностей звертання до записів, за ефективністю значно переважає відомі методи для всіх розглянутих законів розподілу ймовірностей звертання до записів, крім рівномірного для методу двійкового пошуку і “бінарного” для методу послідовного перегляду, блочного пошуку з оптимальним розміром блоків та дворівневого блочного пошуку з оптимальним розміром блоків і підблоків. Цей метод у випадку рівномірного розподілу ймовірностей збігається з методом двійкового пошуку, а у випадку “бінарного” розподілу - з методом послідовного перегляду.
Розроблено підхід до побудови наближених методів пошуку інформації у файлах баз даних, що використовує апроксимацію значень ключа, яким характеризуються записи файла, неперервними функціями.
Розглянемо послідовний упорядкований файл, який містить записів. Нехай - значення ключа, яким характеризується і - й запис файла. Позначимо , а через - функцію дискретного аргумента, визначену на множині натуральних чисел від 1 до : . Для функції на проміжку побудуємо апроксимуючу функцію таку, щоб величина досягала мінімуму. Для забезпечення єдиності розв'язку за братимемо лінійну комбінацію =, де - система функцій Чебишева на проміжку , . Для знаходження коефіцієнтів одержуємо таку систему лінійних алгебраїчних рівнянь
.
Вибираючи різним чином систему функцій Чебишева , одержимо різні апроксимуючі функції.
На основі реального файлу бази даних побудовано апроксимуючі функції, що використовуються для пошуку записів за значеннями ключа.
Проведено порівняння ефективності цього підходу із методами послідовного перегляду, блочного з оптимальним розміром блоків та двійкового пошуку. За критерій ефективності прийнято середню кількість порівнянь, необхідних для пошуку запису у файлі. У випадку методу послідовного перегляду, блочного з оптимальним розміром блоків та двійкового пошуку середня кількість порівнянь, необхідних для пошуку запису у файлі, відповідно, становить 8384.50, 130.49 та 13.05. Якщо пошук здійснювати, використовуючи лінійну, експоненційну та квадратичну апроксимації, то середня кількість порівнянь, необхідних для пошуку запису у файлі, відповідно, становить 1251.28, 702.82 та 701.09.
У четвертому розділі описано роботу спроектованої системи керування базами даних, яка для пошуку інформації у файлах БД використовує свій найефективніший метод пошуку у випадку кожного конкретного закону розподілу ймовірностей звертання до записів. Особливістю реалізованої СКБД є модуль збору статистики та її аналізатор. Пропрацювавши деякий час, зібрану статистику система апроксимує до певного закону розподілу ймовірностей звертань до записів, і, в залежності від отриманого результату, для пошуку обирає найефективніший метод у випадку цього конкретного розподілу ймовірностей звертань до записів. Сформульовано основні вимоги, яким задовольняє дана СКБД. Розроблене програмне забезпечення має простий, зручний у роботі і зрозумілий інтерфейс користувача.
У додатках подано відомості про результати впровадження дисертаційного дослідження.
ВИСНОВКИ
У роботі розв'язано актуальну науково-практичну задачу оптимальної організації пошуку інформації у файлах баз даних для різних законів розподілу ймовірностей звертання до записів. На базі теоретичних досліджень розроблено програмне забезпечення для організації оптимального пошуку інформації у файлах баз даних у випадку відомих законів розподілу ймовірностей звертання до записів. В процесі виконання цієї роботи одержано наступні результати:
1. Досліджено ефективність методів послідовного перегляду, однорівневого, дворівневого і r - рівневого (r > 2) блочного та двійкового пошуку у випадку таких законів розподілу ймовірностей звертання до записів, як рівномірний, “бінарний”, Зіпфа, узагальнений (який є пучком законів), частковим випадком якого є розподіл, що наближено задовольняє правило “80 - 20”.
2. Для різних законів розподілу ймовірностей звертання до записів побудовано схеми методів пошуку, за яких математичне сподівання досягає мінімуму. Для кожного закону розподілу ймовірностей визначено свій найефективніший метод. У випадку r - рівневого (r > 2) блочного пошуку визначено оптимальну кількість рівнів для різних законів розподілу ймовірностей звертання до записів.
3. Розроблено та досліджено ефективність методу пошуку записів у файлах баз даних, який суттєво враховує розподіл імовірностей звертання до записів. Проведено порівняння ефективності цього методу з відомими методами пошуку у випадку таких законів розподілу ймовірностей звертання до записів, як рівномірний, “бінарний”, Зіпфа та узагальнений.
4. Запропоновано та розроблено наближені методи пошуку, які враховують розподіл значень ключа, яким характеризуються записи файла, а їх ефективність не залежить від розподілу ймовірностей звертання до записів.
5. На базі створених математичних моделей розроблено систему керування базами даних, у якій пошук інформації, у випадку кожного конкретного закону розподілу ймовірностей, відбувається, використовуючи найефективніший метод.
СПИСОК ОпублікОВАНИХ ПРАЦЬ за темою дисертації
1. Цегелик Г. Г. Порівняльний аналіз ефективності методів пошуку інформації у файлах баз даних / Г. Г. Цегелик, А. В. Мельничин // Відбір і обробка інформації. - 2005. - №23(99). - С. 135-142.
2. Цегелик Г. Г. Ефективність методу r - рівневого блочного пошуку для різних законів розподілу ймовірностей звертання до записів / Г. Г. Цегелик, А. В. Мельничин // Вісник Національного університету “Львівська політехніка” : Інформаційні системи та мережі. - 2005. - № 549. - С. 184-192.
3. Мельничин А. В. Ефективність методу пошуку інформації у файлах баз даних, який враховує розподіл імовірностей звертання до записів / А. В. Мельничин, М. І. Філяк, Г. Г. Цегелик // Вісник Вінницького політехнічного інституту. - 2006. - №6. - С. 187-191.
4. Цегелик Г. Г. Метод пошуку інформації у файлах баз даних, який враховує розподіл імовірностей звертання до записів / Г. Г. Цегелик, А. В. Мельничин // Фізико-математичне моделювання та інформаційні технології. - 2006. - Вип. 4. - С. 169-177.
5. Мельничин А. В. Використання методу найменших квадратів для побудови наближених методів пошуку інформації у файлах баз даних / А. В. Мельничин, Г. Г. Цегелик // Фізико-математичне моделювання та інформаційні технології. - 2007. - Вип. 6. - С. 116-122.
6. Мельничин А. В. Методи пошуку інформації в файлах баз даних та їх ефективність для різних законів розподілу ймовірностей звертання до записів / А. В. Мельничин, Г. Г. Цегелик // Зб. наук. праць Української академії друкарства „Комп'ютерні технології друкарства”. - 2006. - №16. - С. 41-52.
7. Мельничин А. В. Аналіз методів пошуку інформації в файлах баз даних для різних законів розподілу ймовірностей звертання до записів / А. В. Мельничин, Г. Г. Цегелик // Зб. наук. праць Української академії друкарства „Комп'ютерні технології друкарства”. - 2006. - №15. - С. 95-112.
8. Мельничин А. В. Ефективність методу двійкового пошуку інформації у файлах баз даних для різних законів розподілу ймовірностей звертання до записів / А. В. Мельничин, Г. Г. Цегелик // Вісник Львівського університету. Сер. прикл. матем. та інформ. - 2006. - Вип. 11. - C. 225-229.
9. Мельничин А. В. Оптимальний r - рівневий блочний пошук записів у послідовних упорядкованих файлах / А. В. Мельничин, М. І. Філяк, Г. Г. Цегелик // Матеріали Всеукр. наук. конф. “Сучасні проблеми прикладної математики та інформатики”. - Львів, 2004. - С. 96.
10. Цегелик Г. Г. Порівняльний аналіз ефективності методів пошуку інформації у файлах баз даних для різних законів розподілу ймовірностей звертання до записів / Г. Г. Цегелик, А. В. Мельничин // Матеріали Міжнар. наук.-практичної конф. “Розвиток досліджень '2005”. - Полтава, 2005. - С. 130-134.
11. Мельничин А. В. Ефективність методів пошуку інформації у файлах баз даних для різних законів розподілу ймовірностей звертання до записів / А. В. Мельничин // Матеріали Міжнар. наук.-практ. конф. студентів, аспірантів та молодих вчених, присвяченої 60-річчю Великої Перемоги. Вип. ІІІ. - Ч. 2. - К.: Логос, 2005. - С. 235-236.
12. Мельничин А. В. Ефективність методів пошуку інформації у файлах баз даних для різних законів розподілу ймовірностей звертання до записів / А. В. Мельничин // Тези доп. конф. молодих вчених із сучасних проблем механіки і математики імені академіка Я. С. Підстригача. - Львів, 2005. - С. 150 - 151.
13. Мельничин А. В. Задача вибору оптимальної кількості рівнів багаторівневого блочного пошуку записів у файлах баз даних / А. В. Мельничин // Тези доп. Дванадцятої Всеукр. наук. конф. “Сучасні проблеми прикладної математики та інформатики”. - Львів, 2005. - С. 113.
14. Мельничин А. В. Порівняльний аналіз ефективності методів пошуку інформації у файлах баз даних для різних законів розподілу ймовірностей / А. В. Мельничин // Матеріали Четвертої міжнар. наук.-практ. конф. студентів, аспірантів та молодих вчених. - Київ, 2006. - С. 285-287.
15. Мельничин А. В. Аналіз ефективності методів пошуку інформації у файлах баз даних / А. В. Мельничин, Г. Г. Цегелик // Тези доп. XIII Всеукр. наук.-практичної конф. “Сучасні проблеми прикладної математики та інформатики”. - Львів, 2006. - С. 107.
16. Мельничин А. В. Ефективність методу пошуку інформації у файлах баз даних, який враховує розподіл ймовірностей звертання до записів / А. В. Мельничин, М. І. Філяк, Г. Г. Цегелик // Тези доп. XIII Міжнар. конф. з автоматичного управління “Автоматика 2006”. - Вінниця, 2006. - С. 339.
17. Мельничин А. В. Метод пошуку інформації у файлах баз даних, який враховує розподіл ймовірностей звертання до записів / А. В. Мельничин, Г. Г. Цегелик // Матеріали V Всеукр. наук. конф. молодих науковців ІТОНТ - 2006. - Черкаси: ЧНУ, 2006. - С. 61.
18. Мельничин А. В. Деякі підходи до побудови нових методів пошуку інформації у файлах баз даних / А. В. Мельничин, Г. Г. Цегелик // Матеріали XIV Всеукр. наук. конф. „Сучасні проблеми прикладної математики та інформатики”. - Львів, 2007. - С. 103-104.
19. Мельничин А. В. Моделювання та оптимізація доступу до інформації файлів баз даних / А. В. Мельничин // Матеріали Відкритої наук.-техн. конф. молодих науковців і спеціалістів Фіз.-мех. інституту ім. Г. В. Карпенка НАН України „КМН - 2007”. - Львів, 2007. - С. 266-268.
Анотації
Мельничин А. В. Моделювання та оптимізація доступу до інформації файлів баз даних. - Рукопис.
Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 01.05.03 - „Математичне та програмне забезпечення обчислювальних машин і систем”. - Національний університет “Львівська політехніка”, Львів, 2009.
Дисертація присвячена дослідженню ефективності основних методів пошуку інформації у файлах баз даних, побудові оптимальних схем методів і розробці нових підходів до пошуку інформації у файлах великих БД. Вперше проведено дослідження ефективності методів послідовного перегляду, однорівневого, дворівневого, r - рівневого (r > 2) блочного та двійкового пошуку для різних законів розподілу ймовірностей звертання до записів (рівномірного, “бінарного”, Зіпфа та інших). Побудовано оптимальні схеми однорівневого, дворівневого, r - рівневого (r > 2) блочного пошуку. Визначено оптимальну кількість рівнів для r - рівневого блочного пошуку для усіх розглянутих законів розподілу ймовірностей звертання до записів. Запропоновано нові методи пошуку інформації у файлах БД, досліджено ефективність цих методів в порівнянні з відомими методами пошуку. Побудовано оптимальні схеми доступу до інформації послідовних і індексно-послідовних файлів для розглянутих законів розподілу ймовірностей звертання до записів. Встановлено залежність цих схем від зміни закону розподілу ймовірностей. Розроблено СКБД, в якій для кожного конкретного закону розподілу ймовірностей звертання до записів використовується найефективніший метод.
Ключові слова: методи пошуку, база даних, закон розподілу ймовірностей звертання до записів, математичне сподівання.
Мельничин А. В. Моделирование и оптимизация доступа к информации файлов баз данных. - Рукопись.
Диссертация на соискание ученой степени кандидата технических наук по специальности 01.05.03 - «Математическое и программное обеспечение вычислительных машин и систем». - Национальный университет ”Львовская политехника”, Львов, 2009.
Диссертация посвящена исследованию эффективности основных методов поиска информации в файлах БД, построению оптимальных схем методов и разработке новых подходов к поиску информации в файлах больших БД. Впервые проведено исследование ефективности методов последовательного просмотра, одноуровневого, двухуровневого, r - уровневого (r > 2) блочного и двоичного поиска для разных законов распределения вероятностей обращения к записям (равномерного, “бинарного”, Зипфа и других). Для методов одноуровневого, двухуровневого, r - уровневого (r > 2) блочного поиска построены оптимальные схемы. Определено оптимальное количество уровней для r - уровневого блочного поиска для всех рассмотренных законов распределения вероятностей обращения к записям. Предложены новые подходы к поиску информации в файлах баз данных. Проведен сравнительный анализ эффективности предложенных подходов с известными методами поиска информации для рассмотренных законов распределения вероятностей обращения к записям. Построены оптимальные схемы доступа к информации последовательных и индексно-последовательных файлов для различных законов распределения вероятностей. Приведена зависимость этих схем от изменения закона распределения вероятностей. Реализована СУБД, в которой поиск информации осуществляется с учетом законов распределения вероятностей обращения к записям.
Ключевые слова: методы поиска, база данных, закон распределения вероятностей обращения к записям, математическое ожидание.
Melnychyn А. V. Modeling and optimization of request to information in database files. - Manuscript.
A thesis for a Ph. D. sciences degree by speciality 01.05.03 - „Mathematical and software support of computer machines and systems”. - Lviv Politechnic National University, Lviv, 2009.
This thesis addresses to investigation of the efficiency of the main methods of information search in database files, construction of the optimal method schemes, and development of new approaches to the information search in large database files.
Since in many information processing systems the case of uneven distribution probabilities of request to records are typical, investigation of the efficiency and construction of the optimal method schemes is done both for the even distribution probabilities of request to records, and the cluster of laws of uneven distribution. Such close to the reality of distribution laws, as Zipf law and distribution roughly satisfying rule “80-20” are among them.
Such approach allows not only to investigate the efficiency of any given method of search, and to construct the optimal scheme for any concrete law of distribution probabilities of request to records, but also to get a picture of dependency of the efficiency of the method on the change of law of distribution of probabilities.
For the methods of successive revision, and one-level, two-level, r - level (r > 2) block search and binary search, formula for computing mathematical expectation of the number of comparisons, which are necessary for records search in case of different laws of distribution probabilities of requests to records, are presented. For each method of search a separate picture of mathematical expectation dependency on the change of law of distribution probabilities of request to records, and on the change of the number of file records, is presented. For the methods mentioned the values of parameters are defined, under which mathematical expectation of the number of comparisons, necessary for request to records, reaches its minimum. In case of one-level, two-level, r - level (r > 2) block search, optimal method schemes for different laws of distribution of request to records probabilities (i.e. schemes, under which mathematical expectation reaches its minimum) are constructed.
Optimal number of levels for r - level block search for all considered laws of distribution probabilities of request to records is defined.
General comparative analysis of the efficiency of different methods of information search in database files for the mentioned laws of distribution of request to records probabilities is conducted. In addition, a separate best search method for each concrete distribution law is worked out.
New approaches to information search in database files are also suggested. In particular, a new method for the information search in database files is proposed, in which distribution of probabilities of request to records is taken into consideration. Comparative analysis of the efficiency of the method suggested for different laws of distribution probabilities of request to records, and also comparative analysis with the known information search methods in case of concrete laws of distribution probabilities of request to records are made.
A new approach to the construction of approximation methods of information search in database files, based on continuous functions, is suggested. In this approach approximation of the key value, by which database file recordings are characterized, is used. Approximation functions for the real database file are constructed. Comparative analysis of the efficiency of this approach is made.
For the examined laws of distribution of request to records probabilities a comparative analysis of the efficiency of suggested approaches, with the known methods of information search, has been worked out.
A DBMS has been designed and implemented, in which at the time of information search in database files the laws of distribution probabilities of request to records are taken into consideration.
Keywords: search methods, database, law of distribution probability of request to records, mathematical expectation.
Размещено на Allbest.ru
...Подобные документы
Технологія пошуку інформації в мережі Інтернет. Можливості спеціальних служб, індексів. Інформаційні ресурси у каталогах. Системи мета-пошуку, пошуку в конференціях Usenet, пошуку людей. Знаходження інформації із застосуванням серверів глобального пошуку.
реферат [38,8 K], добавлен 20.05.2011Розробка програми "Авто" для введення та збереження інформації про власників та їхні автомобілі. Побудова математичної моделі. Критерії вибору та пошуку даних. Структура введених та збережених у файлах програми даних. Алгоритм основної програми та її код.
курсовая работа [20,3 K], добавлен 07.10.2010Історія розвитку і створення Інтернет. Протоколи передачі даних. Способи організації пошуку інформації Інтернет. Пошукові системи та сервіси: Яндекс, Google, шукалка. Послідовність виконання пошуку необхідної інормації за допомогою браузера Mozilla.
дипломная работа [4,9 M], добавлен 22.07.2015Дослідження криптографічних методів захисту даних від небажаного доступу. Основи безпеки даних в комп'ютерних системах. Класифікаційні складові загроз безпеки інформації. Характеристика алгоритмів симетричного та асиметричного шифрування інформації.
курсовая работа [245,8 K], добавлен 01.06.2014Процеси пошуку інформацій та розробка структури даних для ефективного зберігання та обробки інформації. Як приклад розглянуто бінарне дерево. Бінарні структури широко використовуються у житті,широко використовуються в багатьох комп'ютерних завданнях.
курсовая работа [67,7 K], добавлен 24.06.2008Обробка масивів формалізованих записів, їх застосування у базах даних підприємств для пошуку інформації про об’єкт. Вимоги до програмного продукту і документації; його структура і функціональна схема. Посібник користувача, умови виконання програми.
курсовая работа [391,0 K], добавлен 13.10.2012База даних як організована структура, призначена для зберігання інформації. Проектування та реалізація в СУБД MS Access інформаційної системи "База даних Internet-ресурсів тестів з психології". Розробка логічної системи даних, інструкції користувача.
курсовая работа [5,3 M], добавлен 22.10.2012Робота користувача з базою даних, перегляд, редагування інформації в базі даних та здійснення пошуку у зручній формі. Інтерфейс системи сільській бібліотеці для обслуговування читачів і фіксування даних книжкового фонду. Структура реляційної бази.
контрольная работа [182,3 K], добавлен 08.03.2015Особливості та методика пошуку інформації та об’єктів у зовнішній пам’яті комп’ютера, в мережі або операційній системі Windows. Специфіка використання автономної й онлайнової довідки операційної системи. Параметри пошуку в прихованих або системних папках.
конспект урока [885,7 K], добавлен 03.01.2010Архітектура Web-баз даних. Загальні відомості про мову SQL. Створення таблиць баз даних. Використання бібліотеки для пошуку інформації. Аутентифікація за допомогою РНР й MySQL. Зберігання паролів в окремому файлі на сервері, використання бази даних.
курсовая работа [913,8 K], добавлен 12.01.2010Програма "Приватка" для збереження та перегляду всієї інформації, що стосується пошуку підприємства. Розробка алгоритму та програмування на мові Turbo Pascal. Формальна та неформальна постановка задачі. Структура зберігаючих даних. Вихідний код програми.
курсовая работа [20,9 K], добавлен 07.10.2010Розробка бази даних для автоматизації облікової інформації в системі управління базами даних Access з метою полегшення роботи з великими масивами даних, які існують на складах. Обґрунтування вибору системи управління. Алгоритм та лістинг програми.
курсовая работа [550,9 K], добавлен 04.12.2009Методи результативного пошуку інформації в Інтернеті. Уявлення про пошукові служби, їх призначення та структура. Основні типи пошукових служб: пошукові каталоги, рейтингові системи, індексні бази даних. Спрямованість тематики і широта охоплення ресурсів.
реферат [33,5 K], добавлен 23.04.2010Основи безпеки даних в комп'ютерних системах. Розробка програми для забезпечення захисту інформації від несанкціонованого доступу: шифрування та дешифрування даних за допомогою криптографічних алгоритмів RSA та DES. Проблеми і перспективи криптографії.
дипломная работа [823,1 K], добавлен 11.01.2011Аналіз предметної області. Розробка бази даних в середовищі Microsoft SQL Server 2008. Можливості інформаційної системи. Установка зв'язків між таблицями. Створення запитів для роботи з даними (введення, видалення, редагування) та пошуку інформації.
курсовая работа [2,6 M], добавлен 09.05.2016Розробка методів вирішення завдань аналізу, розпізнавання, оцінювання зображень як одних з провідних напрямків інформатики. Описання методу пошуку співпадіння об’єкту-цілі з міткою-прицілом на заданому відеоряді. Виявлення об’єкта на цифровому зображенні.
статья [138,7 K], добавлен 21.09.2017Дослідження можливостей пошуку в Google за тематикою. Використання можливості розширеного тематичного пошуку для підвищення релевантності пошуку за встановленим завданням. Розширений пошук зображень. Особливості пошуку щодо країн та наукових знань.
контрольная работа [4,6 M], добавлен 03.02.2014Проблема порушення авторських прав в Інтернеті. Системи та сервіси пошуку плагіату. Захист електронних видань від плагіату в Інтернеті. Алгоритми аналізу, подання і порівняння текстової інформації. Вибір методу пошуку текстових документів з запозиченнями.
магистерская работа [1,0 M], добавлен 14.06.2013Аналіз проектування баз даних та створення програми на тему IC "Туристичні агентства". Розробка простого для розуміння інтерфейсу, огляд реалізації додавання, редагування, видалення, пошуку інформації. Характеристика задач автоматизації і фізичної моделі.
курсовая работа [4,1 M], добавлен 12.01.2012Проектування в програмі Access бази даних мобільних телефонів, що пропонуються до продажу. Класифікація моделей по різним ознакам, що полегшують пошук в системі. Розробка програмного забезпечення, що гарантує підвищення швидкості пошуку інформації.
курсовая работа [2,3 M], добавлен 14.12.2010
