Питання оптимізації запитів завжди є актуальним як для розробників баз даних, так і для програмістів, які з ними працюють. В сучасних СКБД міститься компонент, який називається оптимізатором. Необхідно розглянути його роботу і вибрати можливі шляхи зміни запиту або бази даних (БД) таким чином, щоб оптимізатор витрачав менше часу і ресурсів на побудову плану виконання запиту і його реалізацію.
Існують кілька різних підходів і методів оптимізації запитів, але першочерговим є лексична оптимізація на рівні мови SQL з метою аналізу тексту запиту для виявлення надмірності.
Організація навчального процесу є глобальним завданням в університеті, яке складається з групи складових частин і вимагає багато ресурсів і часу. Тому дуже важливим завданням є автоматизація даного процесу.
Також актуальним питанням в рамках діючої АСК є оптимізація запитів на стадії їх розробки, так як в більшості завдань використовуються великі запити з множинною зв'язкою таблиць між різними базами даних. На виконання таких запитів може затрачуватись до декількох десятків секунд, так як відбувається багаторазове з'єднання з сервером від різних користувачів. Тому оптимізувавши запит на стадії проектування можна зняти навантаження з сервера і прискорити роботу програм.
Наукова новизна роботи полягає в підвищенні ефективності існуючих алгоритмів оптимізації запитів з метою поліпшення роботи діючої автоматизованої системи управління ДонНТУ.
Практична частина складається в розробці програми автоматизованого формування навантаження на кафедру в рамках всього університету, з метою зменшення трудовитрат персоналу кафедри.
Основним завданням в рамках даного проекту є розробка комп'ютерної програми для діючої АСК, що реалізує формування загального навантаження по кафедрі на базі інформації з навчальних планів на заданий семестр і забезпечує мінімізацію трудовитрат співробітників кафедри при формуванні навантаження.
Список цілей, які необхідно виконати в рамках магістерської роботи:
1) Вивчення технології складання і формування навчального процесу в університеті;
2) Вивчення технології формування навантаження на кафедру в даний час;
3) Розробка плану по автоматизації процесу формування навантаження на кафедру;
4) Розробка структури програмного забезпечення (ПЗ) і набору необхідних функцій.
5) Розробка структури бази даних (БД) для реалізації поставленого завдання.
Результатами успішного виконання магістерської роботи повинні бути:
1) Desktop — версія програми для автоматизованого формування навантаження на кафедру в рамках університету;
2) Web — версія програми для перегляду сформованого навантаження.
3) Необхідна структура таблиць в БД, які будуть зберігати отримані дані про навантаження і будуть брати участь у формуванні навантаження на викладачів та при складанні розкладу.
Існує безліч видів і методів оптимізації запитів, дослідженнями яких займаються безліч користувачів і програмістів, які працюють з базами даних.
Що стосується питання автоматизації процесу формування навантаження кафедри, то дана задача є досить специфічною. Відповідно розробок в цій області набагато менше.
3.1 Огляд міжнародних джерел
У світі існує безліч робіт і публікацій на тему оптимізації запитів. Публікацій на тему автоматизованої навантаження на кафедру знайдено не було. Нижче наведено список найбільш популярних публікацій, автори яких внесли вагомий вклад в розвиток даної галузі.
Публікація Ionnidis Y. E. Query Optimization // The Computer Science and Engineering Handbook. Найбільш поширена стаття, в якій йдеться про основні поняття і принципи оптимізації запитів [2].
Публікація Jarke M., Koch J. Query Optimization in Database Systems. Розглядається методи семантичної і логічної оптимізації запитів [5].
Публікація Chaudhari S. An Overview of Query Optimization in Relational Systems. Розглядаються методи оптимізації запитів в реляційних системах [6].
Публікація Graefe G. Query Evaluation Techniques for Large Databases. Розглянуто концепцію алгоритмів для управління системою доступу до великого набору даних [7].
Публікація Ozsu M. N., Valduriez P. Principles of Distributed Database Systems. У книзі йдеться про особливості роботи з розподіленими базами даних і СКБД [8].
3.2 Огляд національних джерел
У Росії і Україні також безліч вчених займається дослідженнями в області оптимізації запитів. Список найбільш популярних публікацій буде наведено нижче.
В області розробок автоматизованих систем формування навантаження кафедри є кілька розробок і публікацій російських авторів. Як приклад можна привести лабораторію математичного моделювання та інформаційних систем (ММІС). Дана лабораторія займається розробкою програмного забезпечення для автоматизації навчального процесу вищих навчальних закладів. Була розроблена автоматизована система "Навантаження ВНЗ", яка забезпечує комплексний підхід до формування та розподілу навчального навантаження [9].
Публікація Гаврилец Е.З., Медведева О.А. Автоматизированная система формирования учебных планов и распределения учебной нагрузки преподавателей кафедры вуза. У даній статті описані основні функції і можливості розробленої системи [10].
Публікація Каюгина С.М. Автоматизированная система расчета и распределения учебной нагрузки преподавателей кафедры вуза на базе платформы «1С». Стаття присвячена вирішенню питання автоматизації розрахунку обсягу навчального навантаження і її розподілу між викладачами кафедри ВНЗ [11].
Публікація Зверев Д. Л. Оптимизация потоков простых SQL-запросов. В роботі розглянуті питання синтезу складних запитів з безлічі простих [3].
3.3 Огляд локальних джерел
Студентів, які в рамках ДонНТУ займалися розробками в області автоматизації процесу формування навантаження на кафедру знайдено не було, однак є студенти, які займалися дослідженнями в області оптимізації запитів.
Робота магістра ДонНТУ Заславского В.А. Система оптимизации клиентских запросов к серверам распределённой базы данных. В роботі йдеться про застосування різних методів оптимізації запитів зокрема, мурашиний алгоритм [12].
Робота магістра ДонНТУ Стародубцева М.В. Исследование методов доступа к данным MS SQL Server. У роботі проводиться дослідження існуючих провайдерів даними БД MS SQL Server на швидкість доступу до записів таблиць [13].
Робота магістра ДонНТУ Бабич К.К. Оптимизации для высоконагруженных реляционных БД и альтернативные решения. В роботі йдеться про створення високонавантаженої веб-системи і застосуванні оптимізації реляційних баз даних, для вирішення завдання множинного доступу і високої відвідуваності [14].
Основоположним елементом у формуванні навчального процесу в семестрі після розробки навчальних планів є формування навантаження по кафедрам (рис.1). Реалізувавши автоматизацію даної проблеми, в подальшому можна буде автоматизувати завдання: «розрахунок навантаження по викладачах», «журнал обліку виконаних робіт викладача», а також вирішити дуже важливу задачу автоматичного складання розкладу занять університету.
Рисунок 1. Схема формування навчального процесу на семестр.
Програма буде здійснювати вибірку даних з набору навчальних планів, що зберігаються в БД центрального сервера вузу, згідно заданих параметрів відбору: (навчальний рік, семестр, кафедра і ін.), Формувати кафедральну навантаження з можливістю її редагування та затвердження.
4.1 Дослідження процесу формування навантаження в даний час
В даний час, кожен факультет, формує навантаження на семестр тільки в рамках свого факультету на базі інформації власних навчальних планів в локальній БД. Підсумковий документ з навантаженням факультетів в форматі EXCEL зберігається на центральний сервер в папку «Навантаження». Потім, кожна кафедра вручну з окремих файлів з навантаженням факультетів, формує документ із загальним навантаженням по кафедрі і редагує його, відповідно до методики від Навчального відділу (рис. 2). Проектуєма програма повинна мінімізувати роботу кафедри по формуванню зведеної навантаження і автоматизувати даний процес.
Рисунок 2 — Процес формування навантаження на кафедру в даний час
(анімація: 6 кадрів, 5 циклів повторення, 64 кілобайта)
4.2 Набір необхідних функцій
Встановлено, що програма повинна включати в себе наступні функції:
1) Авторизація та визначення програмної ролі користувача і пов'язаних з нею прав доступу і набору функцій;
2) Вибірка необхідних дисциплін в цілому по ВНЗ по кожній кафедрі зі збірки навчальних планів, що зберігаються на Центральному сервері, згідно із заданими параметрами (код кафедри, навчальний рік, семестр);
3) Виконання функцій об'єднання груп в потоки згідно встановлених методик у ВНЗ;
4) Розрахунок планованого кількості ставок по кафедрі в залежності від сформованого навантаження;
5) Збереження результатів роботи в базі даних;
6) Візуалізація навантаження по кафедрі у вигляді веб-сторінки;
7) Формування вихідних звітів по навантаженню кафедри;
Права користувача і набір доступних функцій програми буде встановлюватися в момент його авторизації при старті програми і визначатися по присвоєної логіну програмної ролі, закріпленої адміністратором системи. Знаючи необхідний набір функцій, можна скласти схему автоматизованного формування навантаження (рис. 3).
Рисунок 3 — Схема автоматичного формування навантаження на кафедру.
4.3 Вибір мови програмування, середовища розробки і бази даних для
Оскільки розробка буде частиною діючої АСК ВНЗ, то в якості бази даних буде використовуватися - Microsoft SQL Server 2012. Desktop версію програми доцільно розробляти на мові програмування C#, так як компанія Microsoft надає зручний інструмент і середу для розробки програм. Також, мову С# легко зв'язати з базою даних, не вдаючись до підключення сторонніх продуктів або бібліотек.
5.1 Дослідження роботи стандартного оптимізатора на прикладі MS SQL Server
Оптимізатор [1] — компонент системи управління базою даних, який приймає вхідний аргумент у вигляді тексту запиту і розглядає можливі стратегії виконання запиту, після чого вибирає з них найбільш ефективну. Обрана стратегія і буде планом виконання запиту. Оптимізатор приймає рішення, з огляду на такі чинники, як розмір таблиць, з яких проводиться вибірка, існуючі в таблицях індекси і всілякі логічні оператори (AND, OR, NOT), які використовуються у WHERE.
Основним завданням оптимізатора є вибірка найбільш ефективного плану виконання запиту. Це завдання розбивається на 4 основних етапи, які представлені на рисунку 4.
1) Синтаксичний розбір (parsing). При виконанні синтаксичного аналізу, перевіряється синтаксис запиту і запит перетворюється в дерево. Після цього, виконується перевірка всіх об'єктів бази даних, на які посилається запит. (Наприклад, перевірка наявності в базі даних стовпців, зазначених у запиті). Після завершення роботи створюється остаточне дерево запиту.
2) Компіляція запиту (query compilation). На цьому етапі дерево запиту компілюється оптимізатором.
3) Оптимізація запиту (query optimization). Оптимізатор в якості вхідних параметрів на даному етапі приймає скомпільоване дерево запиту і досліджує різні стратегії доступу до даних, перш ніж вирішити, як обробляти даний запит. Щоб відшукати оптимальний план виконання запиту, оптимізатор спочатку виконує аналіз запиту, в процесі якого шукає аргументи пошуку та операції з'єднання. Потім оптимізатор вирішує, які індекси використовувати. Далі, якщо в запиті є операції з'єднання, оптимізатор вибирає методи з'єднання і метод обробки.
4) Виконання запиту (query execution). Створений план виконання зберігається як основний і потім виконується.
Рисунок 4. Основні етапи обробки запиту.
5.2 Вивчення і застосування основних методів лексичної оптимізації запитів
Для виконання лексичної оптимізації [2, 3] запитів, єдиним джерелом інформації є сам текст запиту як лексична конструкція, а інші відомості про базу даних та її структурі в аналізі не використовуються. Процес лексичної оптимізації включає в себе аналіз обмеження запиту, порівнянь, які містяться в умові з метою виявлення надмірності.
Лексична оптимізація може усувати надмірність запиту трьома різними способами [4]:
1) Скорочення запиту - видалення надлишкових умов, наприклад, дублюючих одна одну, обробка яких є зайвою з точки зору виконання запиту, а також умов, які роблять запит нездійсненним, що суперечать один одному або тотожне помилкових. При виявленні таких умов все обмеження або його частина визнається помилковою і виключається з виконання запиту.
2) Удосконалення - дія, при якому в деякому роді ускладнюється структура запиту, але веде до оптимізації його виконання.
3) Перетворення запиту - зміна запиту, не відноситься ні до скорочень, ні до вдосконалень запиту, і грає роль, службову по відношенню до інших форм оптимізації запиту, наприклад, стандартизація форми подання запиту.
5.2.1. Лексична оптимізація шляхом скорочення запиті
Скорочення запитів є найбільш поширеним і передбачає собою підвищення лаконічності і зменшення умов вибірки при збереженні семантичної цілісності. Якщо врахувати те, що кожна умова в запиті вимагає певних витрат ресурсів на обробку, то будь-які семантичні повтори в обмеженні вибірки призводять до зростання затримок на обробку запиту. Відповідно, усунення подібних випадків надмірності на стадії написання запиту до його компіляції та виконання може істотно оптимізувати даний запит.
Основні ідеї лексичної оптимізації шляхом скорочення запитів зводяться до наступних:
• Виключення надлишкових операцій;
• Спрощення виразів, які використовують порожні відносини і тривіальні умови;
• Винесення загальних виразів "за дужки".
5.2.2. Лексична оптимізація шляхом вдосконалення запитів
Технологія вдосконалення запитів базується на ускладненні структури запиту, включення до нього нових табличних виразів, використання яких дозволяє скоротити витрати на обробку вихідного запиту. Більшість алгоритмів, які вирішують цю задачу, відносяться до технології "магічних множин".
Алгоритм магічних множин належить до алгоритмів лексичної оптимізації запиту. Він означає перезапис запиту, яка виключає генерацію нерелевантних зв'язків шляхом обчислення додаткових віртуальних таблиць, які містять зв'язування, використовувані для обмеження таблиці, і діють як фільтри.
Перезапис вихідного запиту з використанням цих фільтрів включає наступні основні етапи:
• аналіз і пошук неоптимальні зв'язків в рамках реалізації запиту;
• створення додаткових (магічних) таблиць;
5.2.3. Лексична оптимізація шляхом перетворення запитів
Критерієм класифікації алгоритму який відноситься до числа алгоритмів простого перетворення є його функціональне призначення. Якщо підсумком роботи деякого алгоритму має стати набуття запитом більш оптимальної форми з точки зору того чи іншого критерію (наприклад, числа умов в обмеженні), то алгоритм може бути віднесений до числа алгоритмів скорочення або удосконалення. Якщо ж алгоритм, перетворює запит до іншого виду, наприклад, змінюючи порядок операцій, то в даному випадку мова йде про просте перетворення запиту.
До технологій перетворення потрібно віднести алгоритми стандартизації запитів, приведення їх до універсальної стандартної формі з метою подальшої обробки. Найбільш поширеним видом перетворення запитів є перенесення логічних умов вниз по дереву запиту. Важливим аспектом є переміщення селективних операцій нижче конструктивних операцій, таких як з'єднання, щоб виконувати селективні операції якомога раніше, тому що на це витрачається менше ресурсів.
При вибірці багатозв'язкових даних великого обсягу в реляційних базах даних, питання оптимізації запитів є досить актуальним, тому що при великій завантаженості сервера час виконання запитів і витрати ресурсів можуть відігравати велику роль.
При дослідженні стандартного оптимізатора на прикладі Microsoft SQL Server були виявлені основні особливості і принципи його роботи.
Також були проаналізовані існуючі технології автоматизації навчального процесу, виявлені завдання, які необхідно реалізувати з метою подальшого розвитку АСК ВНЗ, обрані база даних і середовище розробки, за допомогою яких буде реалізований проект.
1. Microsoft SQL Server 2012. Руководство для начинающих: Пер. с англ. — СПб.:БХВ-Петербург, 2013, - 816 с.: ил.
2. Ionnidis Y. E. Query Optimization // The Computer Science and Engineering Handbook. Boca Raton: CRC Press, 1996. Pp. 1038-1054.
3. Зверев Д. Л. Оптимизация потоков простых SQL-запросов: Диссертация кандидата технических наук: 05.13.11. Санкт-Петербург: Санкт-Петербургский Государственный Университет Аэрокосмического Приборостроения, 2005. 169 сс.
4. Обзор развития методов лексической оптимизации запросов. Труды Института системного программирования РАН Том 23. 2012 г. Стр. 195-214.
5. Jarke M., Koch J. Query Optimization in Database Systems // ACM Computing Surveys (CSUR), 1984. March, Volume 16, Issue 2. Pp. 111-152.
6. Chaudhari S. An Overview of Query Optimization in Relational Systems // Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems. New York: SIGMOD, 1998. Pp. 34-43.
7. Graefe G. Query Evaluation Techniques for Large Databases // ACM Computing Surveys, 1993. Volume 25, Issue 2. P. 73-169.
8. Ozsu M. N., Valduriez P. Principles of Distributed Database Systems. Second Edition. New Jersey: Prentice Hall International, 1999. 666 pp.
9. Автоматизированная система «Нагрузка ВУЗа» [Электронный ресурс] // URL: http://www.mmis.ru/Default.aspx?tabid=170 (дата обращения: 03.05.2015).
10. Гаврилец Е.З., Медведева О.А. АВТОМАТИЗИРОВАННАЯ СИСТЕМА ФОРМИРОВАНИЯ УЧЕБНЫХ ПЛАНОВ И РАСПРЕДЕЛЕНИЯ УЧЕБНОЙ НАГРУЗКИ ПРЕПОДАВАТЕЛЕЙ КАФЕДРЫ ВУЗА // Современные наукоемкие технологии. — 2007. — № 2. — С. 40-41;
11. Каюгина С.М. Автоматизированная система расчета и распределения учебной нагрузки преподавателей кафедры вуза на базе платформы «1С» [Электронный ресурс] // Современные научные исследования и инновации. 2015. № 11, URL: http://web.snauka.ru/issues/2015/11/58943 (дата обращения: 03.05.2015).
12. Заславский В.А. Система оптимизации клиентских запросов к серверам распределённой базы данных. [Электронный ресурс] // Портал Магистров ДонНТУ, 2011г. URL: http://masters.donntu.ru/2011/fknt/zaslavskiy/ (дата обращения: 08.05.2015).
13. Стародубцев М.В. Исследование методов доступа к данным MS SQL Server. [Электронный ресурс] // Портал Магистров ДонНТУ, 2008г. URL: http://masters.donntu.ru/2008/fvti/starodubtsev/masterwork/index.htm (дата обращения: 08.05.2015).
14. Бабич К.К. Оптимизации для высоконагруженных реляционных БД и альтернативные решения. [Электронный ресурс] // Портал Магистров ДонНТУ, 2013г. URL: http://masters.donntu.ru/2013/fknt/babich/index.htm (дата обращения: 08.05.2015).
English
Русский