004.451.7.031.43

 

О.В. Скакаліна, канд. техн. наук

ПНТУ ім. Ю.Кондратюка, м. Полтава, Україна

ОРГАНІЗАЦІЯ ЕФЕКТИВНОГО ВИКОНАННЯ ЗАПИТІВ
У РЕЛЯЦІЙНИХ БАЗАХ ДАНИХ

Е.В. Скакалина, канд. техн. наук

ПНТУ им. Ю. Кондратюка, г. Полтава, Украина

ОРГАНИЗАЦИЯ ЭФФЕКТИВНОГО ВЫПОЛНЕНИЯ ЗАПРОСОВ
В РЕЛЯЦИОННЫХ БАЗАХ ДАННЫХ

О.V. Skakalina, Candidate of Technical Sciences

Poltava National Technical Yuri Kondratyuk University, Poltava, Ukraine

ORGANIZATION OF EFFICIENT PERFORMANSE OF QUERIES IN RELATIONAL DBMS

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

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

Проанализированы вопросы, связанные с эффективностью выполнения запросов в реляционных СУБД, которые выполняются на языках доступа высокого уровня, которые требуют одновременной обработки нескольких реляционных таблиц. Исследованы направления определения корректности таких запросов, рассмотрены пути определения оптимальной последовательности обработки реляционных таблиц.

Ключевые слова: реляционные базы данных, запросы, атрибуты, оптимальная последовательность.

The paper deals with questions related to the efficient execution of requests in relational database systems that run on the languages of high level of access, which require simultaneous processing of several relational tables. We consider the direction of determining the correctness of such requests, the ways of determining the optimal sequence of processing of relational tables.

Key words: relational DBMS, requests, trappings, the optimal sequence.

Вступ. На думку К.Д. Дейта [1], реляційна модель складається з трьох частин:

• структурної;

• цілісної;

• маніпуляційної.

Структурна частина описує, які об’єкти розглядаються реляційною моделлю. Постулюється, що єдиною структурою даних, що використовується в реляційної моделі, є нормалізовані n-арні відношення.

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

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

У цілісній частині реляційної моделі даних фіксуються дві базові вимоги цілісності, які повинні підтримуватися в будь-якій реляційній СКБД. Перша вимога називається вимогою цілісності сутностей. Об’єкту або сутності реального світу в реляційних БД відповідають кортежі відношення. Конкретно вимога полягає в тому, що довільний кортеж будь-якого відношення відрізняється від всіх інших кортежів цього відношення, тобто будь-яке відношення повинно мати один первинний ключ, причому альтернативних ключів може бути багато (або зовсім не бути).

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

Аналіз досліджень і публікацій. У реалізаціях конкретних реляційних СКБД нині не використовується в чистому вигляді ні реляційна алгебра, ні реляційне числення. Фактичним стандартом доступу до реляційних даних стала мова SQL (Structured Query Language). Мова SQL являє собою суміш операторів реляційної алгебри і виразів реляційного числення та використовує синтаксис, близький до фраз англійської мови, і розширений додатковими можливостями, відсутніми в реляційній алгебрі та реляційному численні [2]. Взагалі, мова доступу до даних називається реляційно повною, якщо вона за виразністю не поступається реляційній алгебрі (або, що те ж саме, реляційному численню), тобто будь-який оператор реляційної алгебри може бути виражений засобами цієї мови. Саме такою і є мова SQL.

Оптимізація запитів є найбільш важливим та цікавим напрямком досліджень та розробок по всій області баз даних [3]. Важливість цього напрямку визначається тим, що від розвиненості компонента оптимізації запитів критично залежить загальна ефективність будь-якої SQL-орієнтованої СУБД.

На першій фазі запит, поданий на мові запитів, піддається лексичному і синтаксичному аналізу. При цьому виробляється його внутрішнє подання у структуру запиту і містить інформацію, яка характеризує об’єкти бази даних, що зазначені в запиті (відносини, поля і константи). Інформація про збережених у базі даних об’єктів вибирається з каталогів бази даних. Внутрішнє подання запиту використовується і перетворюється на наступних стадіях оброблення запиту.

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

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

На четвертому етапі за внутрішнім поданням найбільш оптимального плану виконання запиту формується виконання подання плану. Подання плану, яке безпосередньо виконується, може мати вигляд програми в машинних кодах, якщо, як у випадку System R, система орієнтована на компіляцію запитів у машинні коди, або бути машинно-незалежним, але більш зручним для інтерпретації, якщо, як у випадку INGRES, система орієнтована на інтерпретацію запитів. Нарешті, на останньому, п’ятому етапі оброблення запиту відбувається його реальне виконання відповідно до виконуваного планом запиту. Це або виконання відповідної підпрограми, або виклик інтерпретатора з передачею йому для інтерпретації виконуваного плану [4].

Формулювання цілей статті. Метою роботи є визначення алгоритму оптимальної послідовності оброблення таблиць при виконанні запитів у реляційних СУБД.

Виклад основного матеріалу статті. Припустімо, що у базі даних зберігаються такі таблиці, що мають такі структури:

1. План_випуску_деталей* (Шифр_деталі*, Вид_виконання, План, Місяць, Рік).

2. Класифікатор_видів_виконання (Шифр, Найменування).

3. Довідник_найменувань (Шифр, Найменування).

4. Звітній місяць (Місяць, Рік).

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

SELECT Найменувань. Найменування, Довідник_найменувань. Шифр, Класифікатор_видів_виконання. Найменування

FROM План_випуску_деталей, Класифікатор_видів_виконання,

Довідник_найменувань, Звітній_місяць

WHERE (План_випуску_деталей. Шифр_деталі=Довідник_найменувань. Шифр AND

План_випуску_деталей. Вид_виконання=Класифікатор_видів_виконання. Шифр AND

План_випуску_деталей. Місяць=Звітній_місць. Місяць AND

План_випуску_деталей. Рік=Звітній_місяць. Рік)

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

Кожна вершина відповідає певному конкретному атрибуту, наприклад, Шифр_деталі з таблиці План_випуску_деталей або Місяць з таблиці Звітний_місяць*.

З’єднаємо ребрами вершини, що належать одній таблиці, і отримаємо таким чином К повних підграфів, вхідного графа G, де К – кількість таблиць, що беруть участь у запиті. Отже, в результаті цього кроку отримаємо К компонент зв’язності для графа G. З’єднаємо ребрами вершини із різних компонент зв’язності, якщо вони відповідають будь-якій елементарній операції порівняння умові пошуку. Причому, якщо така операція порівняння встановлює зв’язок між n таблицями, то це приводить до появи нового підграфа G = на n вершинах, де . Таким чином, якщо у запиті у декількох таблицях присутні m різних атрибутів, зв’язаних між собою в умові пошуку, то у відповідному графі G буде m повних підграфів на вершинах, відповідних цим атрибутам (рис.).

 

План випуску деталей	Класифікатор видів виконання	Довідник найменувань	Звітний місяць
ШД   ВИ   МЕС   ГОД	Ш	Ш	МЕС   ГОД

Рис. Графічне відображення зв’язків таблиць у запиті

Якщо у результаті наведених перетворень отриманий граф виявився зв’язним, то це вказує на логічний зв’язок усіх таблиць, що беруть участь у запиті, в іншому випадку запит є некоректним і його виконання не має сенсу. Отже, для визначення коректності запиту необхідно визначити зв’язність граф, заданого своїми повними підграфами. Нині відомо багато алгоритмів визначення зв’язності графа [5; 6; 7]. Найшвидші з них мають складність 0(|E|). Використовуючи техніку прямої адресації (або алгоритм хешування), розроблено алгоритм визначення зв’язності графа, що має обчислювальну складність 0(|V|) і будує основне дерево, на вершинах деякого графа , відповідних повним підграфам G.

Введемо такі позначки:

N – поточне ім’я підграфа;

NEXT(N) – Оператор вибору наступного по порядку підграфа. На першому кроку вибір першого підграфа;

V – Поточне ім’я вершини підграфа;

NEXT(N,V) – Вибір наступної вершини підграфа N;

M – Область, у якій зберігаються пари типу ;

E – Область, у якій зберігаються імена ребер типу ;

A=h(x) – Визначення точної адреси (або хеш-адреси) деякого імені X в області M або E;

∧ – Пусте значення. Є результатом оператора NEXT, якщо він не може вибрати наступне значення.

Алгоритм 1. Визначення зв’язності графа.

1. Встановити значення К. Обнулити М, Е, Т.

2. N:=NEXT(x). Якщо N=∧, то перейти до п. 5. PRED:=Nю

3. V:=NEXT(N, V). Якщо V= ∧, то перейти до п. 2. A:=h(V)’.

4. Якщо M(A,1)=0, то M(A,2):=V,M(A,1):=PRED.

Інакше А1:=h(). Якщо Е(А1)≠0, то перейти до п. 3.

Інакше Е(А1):= ,PRED:=M(A,1),T:=T+1.

Перейти до п. 3.

5. Якщо Т=К-1, то граф зв’язний, інакше – граф не зв’язний.

Другою задачею, як було вказано раніше, що виникає під час реалізації запитів дореляційних баз даних, є визначення оптимальної послідовності оброблення таблиць. Її сенс полягає у тому, що після вибору рядка з однієї таблиці стають відомими значення декількох атрибутів, що визначають значення в умовах пошуку для інших таблиць і відповідно зменшують перебір рядків у цій таблиці. Якщо на фізичному рівні як індекс використовується, наприклад, мультисписок, то пошук буде виконуватися за ключовим атрибутом, значення якого менш всього зустрічається в таблиці. Це, в загальному випадку, відповідає атрибуту з максимальною потужністю. Якщо максимальна потужність пошукового атрибуту рівна , то при пошуку по цьому атрибуту потрібно в середньому перебирати , де – число рядків в і таблиці. Якщо ж як ключ вибирається складений вторинний ключ [7; 8], то значення буде дорівнювати добутку коефіцієнтів R тих атрибутів, що визначені у складеному ключі. Зміна послідовності оброблення таблиць приводить до значних змін у кількості рядків, що обробляються, що в кінцевому підсумку впливає на загальний час реалізації такого запиту. На фізичному рівні зміна кількості рядків, що обробляються, веде до різноманітної кількості блоків зовнішньої пам’яті, до яких іде звернення. Отже, з погляду ефективної реалізації (з погляду часу) будь-якого запиту для реляційних СУБД необхідно визначити таку послідовність оброблення таблиць, що забезпечить мінімальну кількість блоків зовнішньої пам’яті, до яких іде звернення.

Відомо [9; 10], що випадковий розподіл n записів у М областях (блоках) підкоряється закону розподілу Пуассона за параметром λ=n/M. Отже, кількість блоків, в які не влучить жоден запис, і, які відповідно не будуть прочитані у процесі пошуку інформації, дорівнюватиме .

Якщо ж в оброблення включається k таблиць, то загальна кількість записів, які обробляються, буде дорівнювати

 (1)

де – наведена кількість блоків у таблиці (кількість блоків, що реально прочитуються при пошуку інформації за умовою).

Якщо у запиті беруть участь k документів, то загальна кількість можливих варіантів їхнього оброблення дорівнює k!. Складність обчислення значення Q за формулою (1) дорівнює O(k-1). Отже, загальна складність визначення оптимального рішення при розгляді усіх варіантів дорівнює. Очевидно, що навіть при не дуже великому значенні k  дуже швидко збільшується із зростанням k.

Для розв’язання поставленої задачі пропонується використати модель у вигляді орієнтованого графа G=, вершини А якого відповідають усім непустим підмножинам множини таблиць, що беруть участь у запиті, та визначити на них відношення безпосереднього передування R [11]. Якщо підмножині множини таблиць відповідає на графі крапка a і – крапка b, то дуга <a, b>єR, якщо та не існує такого , що . Граф G=, що відображає відношення R, є без контурним, і його вершини можна розмістити по рівням відповідно до порядкової функції. На і-му рівні буде знаходитися вершин. Кожній вершині графа припишемо два числа: перше – вага вершини, що характеризує мінімальне число блоків, які прочитуються під час оброблення усіх таблиць, що складають множину цієї вершини; другий – добуток «приведеного» числа блоків для тих же таблиць. . Кожній дузі графа припишемо вагу , що характеризує наведену кількість блоків для таблиці, що буде вибиратися після таблиці, якій відповідає вершина, з якої дуга виходить.

. Наприклад, для дуги, яка виходить з вершини {1,3,4 у вершину*{1,2,3,4 – вага буде характеризувати наведену кількість блоків для другої таблиці. Припишемо вершинам 1-го рівня . Вагу вершини на j рівні визначимо за формулою .

Твердження 1. Для будь-якої пари таблиць <i,j>, якщо , то і будь-яка послідовність оброблення таблиць, що починається із <i,j>, завжди краще, ніж будь-яка послідовність, що починається із <j,і>.

Доказ. Оскільки обчислення значення Q виконується за формулою (1), то , i . Треба довести, що за цих умов завжди виконується нерівність  де X – значення, одержуване у внутрішніх дужках формули (1). З (1) виходить, що , , а значить і виконується нерівність , оскільки значення X за своїм змістом є кількістю блоків, що обробляються, при пошуку інформації у 3-й та наступних таблицях і є числом позитивним більшим або рівним 1.

Проілюструємо роботу алгоритму на найпростішому прикладі. Наприклад, у запиті беруть участь чотири взаємопов’язані таблиці з кількістю зовнішніх блоків 120, 10, 40 і 1 відповідно. Значення Q і N для кожної вершини наведені у табл. 1, а ваги дуг V – у табл. 2.

Таблиця 1

Вага та добуток відповідних вершин графа

Вершина	1	2	3	4	21	31	41	23	42	43	213	421	431	423	4213
Q (вага)	120	10	40	1	130	160	121	410	11	41	250	131	161	411	251
N (добуток)	120	10	40	Наукова бібліотека ЧНТУ © 2012