|
ОДЕСЬКИЙ НАЦІОНАЛЬНИЙ ПОЛІТЕХНІЧНИЙ УНІВЕРСИТЕТ
НГУЄН ЧАН КУОК ВІНЬ
УДК 681.3.06
Підвищення ефективності застосування матеріалізованих представлень в автоматизованих комп'ютерних системах з реляційними базами даних
05.13.06 – Автоматизовані системи управління і прогресивні інформаційні технології
Автореферат
дисертації на здобуття наукового ступеня кандидата
технічних наук
Одеса – 2005
Дисертацією є рукопис.
Робота виконана на кафедрі “Системне програмне забезпечення” Одеського національного політехнічного університету Міністерства освіти і науки України.
Науковий керівник кандидат технічних наук, доцент
Кунгурцев Олексій Борисович,
Одеський національний політехнічний університет, професор кафедри системного програмного забезпечення.
Офіційні опоненти: – доктор технічних наук, професор
Фісун Микола Тихонович,
Миколаївський державний гуманітарний університет ім. Петра Могили, завідувач кафедри інтелектуальних інформаційних систем;
– кандидат технічних наук, доцент
Малахов Євгеній Валерійович,
Одеський національний політехнічний університет, завідувач кафедри інформаційних систем у менеджменті.
Провідна установа: Харківський національний технічний університет “Харківський політехнічний інститут”.
Захист відбудеться “ 19 ” січня 2006 року о 1330 годинi на засіданні спеціалізованої вченої ради Д 41.052.01 Одеського національного політехнічного університету за адресою: 65044, м. Одеса, проспект Шевченка, 1, ауд. 400 - А.
З дисертацією можна ознайомитись у бібліотеці Одеського національного політехнічного університету за адресою: 65044, м. Одеса, проспект Шевченка, 1.
Автореферат розісланий “ 19 ” грудня 2005 року.
Вчений секретар спеціалізованої
вченої ради Ямпольський Ю.С.
ОСНОВНА ХАРАКТЕРИСТИКА РОБОТИ
Актуальність теми. У будь-якій реально використовуваній автоматизованій комп'ютерній системі (АКС) з реляційною базою даних (РБД) з часом зростає інтенсивність запитів, а часто і їх складність. У зв'язку з цим з'являється потреба підвищення продуктивності системи. Одним з найефективніших шляхів розв'язання цієї задачі є використовування матеріалізованих представлень (МП) – збережених результатів виконання запитів. Застосування МП для трудомістких і часто повторюваних запитів може значно скоротити час їх виконання і тим самим підвищити загальну продуктивність системи, а також зробити її такою, що відповідає вимогам окремих користувачів.
Ідея застосування МП з'явилася ще в дев'яностих роках минулого сторіччя. Проте тільки останніми роками МП стали упроваджуватися в комерційні системи управління базами даних (СУБД) (Oracle, Microsoft SQL Server, IBM DB2). Причиною такого повільного упровадження потенційно дуже ефективної технології з'явилося недостатнє теоретичне опрацьовування механізму проектування і використовування МП. Якщо проблемам синхронного оновлення даних в МП і, зокрема, інкрементальному оновленню (ІО) надано досить уваги в наукових працях, то над питаннями вибору кандидатів на МП, оцінками ефективності їх застосування, зниження додаткового навантаження на БД практично ніхто не займався.
До теперішнього часу залишалася нерозробленою методика дослідження АКС для обґрунтування застосування МП. Не створений гнучкий і орієнтований на наочну область механізм оновлення МП, відсутні способи оцінки ефективності застосування МП в різних режимах роботи АКС. Все це значно гальмує вирішення проблеми широкого застосування МП в АКС і робить актуальною дану наукову роботу.
Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконувалася відповідно до завдань НДР ОНПУ № 393-73 – “Інформаційні системи в проектуванні і управлінні” та НДР № 729-144 – “Розробка інформаційно-аналітичних систем та систем організації керування”.
Мета досліджень. Метою роботи є підвищення продуктивності АКС, використовуючих реляційні системи управління базами даних шляхом удосконалення технології застосування матеріалізованих представлень.
Для досягнення цієї мети в роботі поставлені і розв'язані такі задачі:
– розроблений метод аналізу АКС з мінімізацією кількості вибірок, які передбачає формування груп запитів з метою скорочення кількості обслуговуваних МП, спрощення структури і об'єму РБД;
– проаналізовані варіанти порівняння запитів в процесі аналізу і експлуатації АКС, розроблені математична модель представлення, методика порівняння і перерахунку запитів;
– запропонована класифікація даних в АКС з погляду вимог до їх актуальності і розроблений метод і методика асинхронного оновлення МП;
– вдосконалена модель ІО МП, заснована на лічильнику дублікатів записів МП типу SPJ;
– розроблене програмне забезпечення для реалізації механізму МП.
Об'єктом дослідження є автоматизовані комп'ютерні системи, що використовують реляційні СУБД.
Предмет дослідження. Методи, моделі і алгоритми підтримки МП в реляційних СУБД.
Методи дослідження. При аналізі АКС використані методи статистичного аналізу і теорії ймовірностей. При аналізі і порівнянні запитів використана теорія множин, дискретна математика, реляційна алгебра.
Наукова новизна одержаних результатів полягає в розвитку і поглибленні теоретичних і методологічних основ підвищення ефективності механізмів матеріалізованих представлень.
Новими науковими результатами є такі:
– вперше запропонований метод аналізу АКС для формування груп запитів, які ґрунтується на ітераційному процесі обробки множини запитів і визначенні частоти зміни даних для вибраних груп;
– одержала подальший розвиток математична модель представлення, порівняння і перерахунку запитів шляхом введення операцій перетину, різниці запитів і стратегій порівняння запитів;
– вперше запропонований механізм асинхронного оновлення МП, які ґрунтується на аналізі характеристик актуальності даних з погляду різних задач АКС;
– вдосконалений алгоритм інкрементального оновлення МП шляхом аналізу кратності повторень наборів значень полів базової таблиці, використовуваної в МП.
Практичне значення одержаних результатів
На основі запропонованого методу аналізу АКС і моделі формування груп запитів розроблена методика аналізу журналу транзакцій, створений блок аналізу АКС, який був використаний в лабораторії інформаційних систем ОНПУ для дослідження журналу транзакцій АКС університету. Одержані результати дозволили сформувати групи запитів і відповідні МП.
На базі математичної моделі представлення, порівняння і перерахунку запитів створені відповідні алгоритми і програми, використовувані в різних модулях реалізації механізму МП.
Реалізовано механізм МП для СУБД PostgreSQL v.8.0.
На основі методу асинхронного оновлення МП, відповідних алгоритмів і методик створено програмне забезпечення для зберігання, ініціалізації, перерахунку і асинхронного оновлення МП, яке використовується в підсистемі “Навчально-виробичного відділу” АКС ОНПУ, що дозволило значно (76%) розвантажити підсистему.
Розроблені методи, моделі і алгоритми упроваджені в навчальний процес дисципліни “Інформаційні системи та структури даних”, а також в методичні матеріали щодо дипломного проектування.
Особистий внесок здобувача. Автору належать такі наукові положення, висновки і рекомендації: математична модель представлення, порівняння і перерахунку запитів [1, 2, 3], спосіб комбінованого виконання запитів і визначення операцій над запитами [3], вдосконалений алгоритм інкрементального оновлення МП [7], розробка структури програмного забезпечення для підтримки МП [5]. У співавторстві розроблені: метод аналізу інформаційних систем і модель формування груп запитів [4], метод асинхронного оновлення МП [6].
Апробація результатів дисертації. Основні результати роботи доповідалися й обговорювалися на Міжнародній конференції “Нові інформаційні технології в навчальних закладах України “НИТУЗУ-2005””, Одеса, 2005; Міжнародній конференції “Сучасні інформаційні і електронні технології "СІЕТ-2005"”, Одеса, 2005; конференції “Могилянські читання – 2005”, Миколаїв, 2005; на двох семінарах “Інтелектуальна обробка інформації і сучасні комп'ютерні технології”, ОНПУ, 2005.
Публікації. За матеріалами дисертації опубліковано 5 наукових статей у фахових виданнях переліку ВАК України, а також матеріали двох конференцій.
Структура дисертації. Дисертація складається зі вступу, п’яти розділів, додатків. Обсяг дисертації - 142 с., додатків - 50 с. Дисертація містить 25 рисунків та посилання до 133 літературних джерел.
ОСНОВНИЙ ЗМІСТ РОБОТИ
У вступі висвітлена основна характеристика роботи, яка підкреслює її актуальність, відповідність вимогам ВАК України, наукову новизну і практичне значення; визначено предмет і об'єкт дослідження, його мету і задачі.
У першому розділі проаналізовані існуючі рішення в галузі застосування і оновлення МП, аналізу ефективності упровадження механізму МП.
Встановлено, що:
– у комерційних СУБД використовується тільки синхронне оновлення МП, а сам вибір МП здійснюється емпірично;
– відсутня методика дослідження АКС для визначення частоти появи запитів, а також частоти оновлення даних;
– відсутня методика аналізу даних і функцій АКС з метою визначення допустимих інтервалів оновлення і допустимих похибок даних при агрегації;
– немає загальної моделі і не доведені до рівня практичного застосування алгоритми порівняння запитів;
– відсутній механізм скорочення кількості МП за рахунок угруповання мало відмінних один від одного запитів.
На підставі проведеного аналізу сформульовані задачі дослідження.
У другому розділі сформульована необхідність аналізу і порівняння запитів. Запропонована процедура перетворення запитів у канонічну форму. Вдосконалена математична модель представлення, порівняння і угруповання запитів, а також визначені спеціальні операції, які призначені для порівняння запитів і перерахунку запитів з МП.
Вхідна множина запитів позначається
 ,
де N – потужність множини вхідних запитів.
Кожен запит пропонується характеризувати трійкою:
Zi(Fi, Ci, Si), (1)
де  – вектор полів таблиць, які вибирає запит Zi;
 – вектор умов вибору;
Si – вартість виконання запиту Zi.
Для спрощення операцій над запитами пропонується перетворювати фрази WHERE в канонічну форму представлення, яка може бути диз'юнктивною:
(V AND V ...AND V) OR (V AND...AND V) OR… (2)
або кон’юнктивною:
(V OR V…OR V) AND (V OR V…OR V) AND… (3)
де V – будь який вираз, що не містить логічних операцій AND та OR.
Для перетворення пропонується спеціальна функція, яка дозволяє кожну фразу умов вибору представити в диз'юнктивній формі:
  (4)
де  (5)
 – вираз відношення.
Для виділення загальної частини порівнюваних запитів (Zi, Zj), а також відмінностей між ними запропоновані операції перетину і різниці:
 ,
для векторів полів вибору.
Для векторів умов вибору, що містять тільки логічні операції OR, визначені операції перетину і різниці:
 ,
 .
Для векторів умов вибору, що містять тільки логічні операції AND, визначені операції об'єднання, перетину і різниці:
 ,
 ,
 .
На підставі цих визначень одержані операції перетину і різниці для запитів:
 ,
 .
Аналогічно одержана кон'юнктивна форма представлення фрази WHERE і визначені операції над виразами та запитами.
Визначені операції для запитів з агрегаціями, в яких замість вектора умов вибору WHERE використовується фраза HAVING.
Розв'язання задачі порівняння запитів пропонується розбити на такі етапи.
1) Виділення з журналу транзакцій множини M запитів типу SELECT.
2) Виділення з множини М підмножин запитів Мt, що використовують однакову множину таблиць (аналіз фрази FROM).
3) Виділення з множини Мt підмножин Мf, що використовують однакові набори полів (аналіз фрази SELECT).
4) Виділення з множини Мf підмножин  , що мають однакові умови вибірки полів (аналіз фрази WHERE).
5) Виділення з множини  підмножин  , володіючих умовами з “перекриттям”.
При реалізації другого етапу враховуються не тільки імена таблиць, але і їх псевдоніми.
На третьому етапі порівнюються множини використовуваних полів з урахуванням псевдонімів, знайдених на другому етапі.
Виконання четвертого етапу пропонується розбити на таку послідовність кроків.
A) Формування множини запитів з однаковими умовами вибірки, що базується на попарному порівнянні запитів. Процес порівняння передбачає перетворення Ci і Cj (фрази WHERE) порівнюваних запитів в канонічну форму. Далі виконується порівняння умов вибірки Ci і Cj для двох запитів. У разі збігу умов аналіз припиняється, інакше здійснюється перехід до наступного кроку.
B) Аналіз логічної структури фрази WHERE. Під логічною структурою розуміється вектор умов, де будь-який елемент, крім логічних операцій і дужок представлений деяким ідентифікатором. Для цієї умови вибірки двох запитів перетворяться в диз'юнктивну форму.
Якщо кількість елементів в двох фразах WHERE (4) однакова, то логічні структури умов на рівні диз'юнктивної форми збігаються, і аналіз перевірки ідентичності запитів продовжується на наступному рівні деталізації логічної структури.
C) Порівняння виразів відношення. У межах  і  відшукуються пари збіжних виразів. Якщо встановлена попарна рівність для всіх виразів відношення двох порівнюваних запитів, то робиться висновок про збіг цих запитів. У разі незбігу відбувається перехід до наступного кроку.
D) Розбиття кожного виразу відношення з множини незбіжних виразів відношення на два арифметичні вирази і операцію відношення. Для кожної пари незбіжних виразів відношень у межах  і  виконується перестановка місцями в одному з виразів лівої і правої частин з відповідною заміною знака операції відношення. Якщо після проведених операцій перестановки не залишилося незбіжних виразів за всіма  і  , то робиться висновок про збіг запитів. Інакше здійснюється перехід до наступного кроку.
E) Для кожної пари незбіжних виразів відношень в межах  і  виконується ряд перетворень.
Спочатку проводиться перетворення відношень у форму з нулем або константою (якщо вона є) в правій частині. Якщо знаки операцій відношення в двох порівнюваних виразах не збігаються, то один з виразів перетвориться у форму, аналогічну іншому виразу.
Потім розкриваються дужки в лівій частині і для кожного операнда операцій “+” і “-” проводиться впорядкування його компонентів, а також якщо можливо, виконання арифметичних операцій. Результат також слід упорядкувати.
На завершення виконується порівняння двох виразів як рядків.
Розроблені правила для визначення “перекриття” умов вибору.
Розроблена методика порівняння запитів з угрупованням (GROUP BY), сортуванням (ORDER BY), агрегуючими функціями, зовнішніми ключами.
Запропоновано модель угроповання запитів, що заснована на створенні одного запиту, який представляє усі запити групи. Надалі цей запит будемо називати центральним запитом групи. Використовування груп дозволяє значно скоротити кількість МП і підвищити ефективність їх застосування.
У третьому розділі розроблено метод аналізу АКС, направлений на підвищення продуктивності системи в цілому і при пікових навантаженнях зокрема.
Метод передбачає використовування такої інформації про кожен запит:
– текст запиту;
– час появи і виконання запиту;
– джерело запиту (робоче місце);
– використовувані дані;
– вимога до актуальності використовуваних даних.
Для вибірки запитів пропонується використовувати журнал транзакцій (або подібне джерело інформації). Отримання достовірної картини про розподіл типів запитів ґрунтується на аналізі запитів протягом тривалого інтервалу часу, що охоплює основний період діяльності підприємства. Для скорочення трудомісткості аналізу запропоновано алгоритм мінімізації кількості вибірок з одночасним формуванням груп запитів. Для отримання складу груп запропоновано алгоритм, що визначає частоту оновлення даних центральних запитів в групах.
Алгоритм мінімізації кількості вибірок передбачає такі кроки:
1. Визначення стартового мінімального числа вибірок (оброблюваних запитів) nmin. Реальна АКС має деяке число робочих місць r. Кожне робоче місце може утворити, як мінімум, m запитів до системи. Тоді мінімальне число вибірок не має сенсу робити менше, ніж 
Стартове значення вибираємо як найближче значення до nmin.
 , (6)
де x – найбільше допустиме для (6) ціле число.
Вибір nstart не впливає на похибку формування груп запитів, а тільки на час процесу їх формування.
2. Вибір з множини Z кожного 2x -го запиту для аналізу.
3. Формування множини груп  запитів відповідно до правил порівняння запитів. Тут  – кількість одержаних груп запитів на j–ї ітерації.
4. Визначення ймовірності попадання запиту Zi в групу Gh на j–ї ітерації:
де  – число запитів Zi, що входять до h–ї групи на j–ї ітерації.
5. Збільшення в два рази числа вибірок (x зменшується на 1). У цьому випадку результати попередньої вибірки доповнюються, а не переобчислюються.
6. Виконання розрахунків відповідно до п.3 і п.4 і обчислення похибки у визначенні ймовірності попадання запиту в групу на підставі двох останніх вибірок:
 .
7. Визначення інтегральних критеріїв закінчення процесу:
 ,  ,
де  – середнє значення похибки  ,
 – відносна зміна кількості груп.
8. Якщо похибки  і  перевищують деякі задані порогові значення  і , то пункти 5 і 6 повторюються, інакше процес завершується.
Розроблений спосіб визначення центрального запиту Zc для множини запитів групи
 .
Можливі такі варіанти визначення центрального запиту (рис. 1).
– Знаходження загальної частини для всіх запитів групи.
 .
– Вибір одного із запитів групи як центрального.
Для кожного запиту  групи визначається сумарна вартість перерахунку з нього всіх запитів:
де  – вартість перерахунку Zj з Zi.
Центральний запит визначається за якнайменшою сумарною вартістю виконання перерахунку:
 .
– Складання центрального запиту, що перекриває всі запити групи:
 ,
де  ,
 .
Якщо форма представлення умов вибору  кон'юнктивна, то потрібно виконати перетворення в кон'юнктивну форму:
 ,
де  – загальна частина фраз умов вибору;
 – індивідуальна частина фраз умов вибору.
Якщо діапазон вибору для якого-небудь поля перекриває всі значення домену цього поля, то умова для цього поля ігнорується.
| 
