Анотація до роботи:

Мельничин А. В. Моделювання та оптимізація доступу до інформації файлів баз даних. – Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 01.05.03 – „Математичне та програмне забезпечення обчислювальних машин і систем”. – Національний університет “Львівська політехніка”, Львів, 2009.

Дисертація присвячена дослідженню ефективності основних методів пошуку інформації у файлах баз даних, побудові оптимальних схем методів і розробці нових підходів до пошуку інформації у файлах великих БД. Вперше проведено дослідження ефективності методів послідовного перегляду, однорівневого, дворівневого, r - рівневого (r > 2) блочного та двійкового пошуку для різних законів розподілу ймовірностей звертання до записів (рівномірного, “бінарного”, Зіпфа та інших). Побудовано оптимальні схеми однорівневого, дворівневого, r - рівневого (r > 2) блочного пошуку. Визначено оптимальну кількість рівнів для r – рівневого блочного пошуку для усіх розглянутих законів розподілу ймовірностей звертання до записів. Запропоновано нові методи пошуку інформації у файлах БД, досліджено ефективність цих методів в порівнянні з відомими методами пошуку. Побудовано оптимальні схеми доступу до інформації послідовних і індексно-послідовних файлів для розглянутих законів розподілу ймовірностей звертання до записів. Встановлено залежність цих схем від зміни закону розподілу ймовірностей. Розроблено СКБД, в якій для кожного конкретного закону розподілу ймовірностей звертання до записів використовується найефективніший метод.

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

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.