СТРАТЕГІЯ ОРГАНІЗАЦІЇ РОБОТИ ЗА ПРИНЦИПОМ “розділяй і володарюй”

Як вже згадувалося вище, наприкінці розділу 184, реляційні вирази рекурсивно визначаються в термінах подвираженій, що дозволяє оптимізаторові застосовувати різні стратегії оптимізації за принципом розділяй і володарюй . Відзначимо, що використання подібних стратегій особливо привабливо в середовищах, що підтримують паралельні обчислення, зокрема, в розподілених системах, в яких різні частини запиту можуть виконуватися паралельно на різних процесорах [1856] – [1858] У даному розділі розглядається одна з подібних стратегій, що отримала назву декомпозиція запитів Вперше вона била застосована в прототипі системи Ingres [1834], [1835]

Основна ідея методу декомпозиції запитів полягає в тому, що запит, що включає велику кількість змінних області значеній6, розбивається на послідовність запитів меншого розміру зазвичай з однією або двома такими змінними в кожному Необхідна декомпозиція досягається за допомогою методів відділення і підстановки кортежів, які описані нижче

6 Нагадаємо, що в мові запитів QUEL системи INGRES використовуються засоби реляційного числення

■ Відділення – це процес видалення із запиту такого компонента, який має тільки одну загальну змінну з іншою частиною запиту

■&nbsp&nbsp&nbsp&nbsp Підстановка кортежу – Це процес підстановки значення однієї змінної в запиті (один кортеж за одну операцію)

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

Нижче розглянуто приклад декомпозиції (заснований на прикладі з [1834]) Словесне вираження цього запиту має наступний вигляд: Визначити імена постачальників з Лондона, що постачають деякі деталі червоного кольору вагою менше 25 фунтів в кількості більше 200 штук . Приведемо формулювання цього запиту на мові QUEL, на яку далі будемо посилатися, як на формулювання запиту Q0

Q0: RETRIEVE ( SSNAME) WHERE SCITY  = London AND  SS#     = SPS#

AND  SPQTY  &gt 200

AND  SPP#   = PP# AND  PCOLOR  = Red AND   PWEIGHT &lt 25

Тут змінними області значень є s, P і SP, причому кожна з них поширюється на всю базову змінну відносини з тим же імям

Виходячи з останніх двох порівнянь в виразі запиту можна укласти, що нас цікавлять тільки деталі червоного кольору вагою менше 25 фунтів Тому можна відокремити подзапрос з однією змінною (на самому справі є проекцією скорочення), в якому використовується змінна Р

Dl: RETRIEVE INTO P (PP #) WHERE РCOLOR = Red AND PWEIGHT < 25

Цей запит з єдиною змінної може бути відділений, оскільки в ньому присутня тільки одна змінна (а саме – змінна Р), спільно використовується з іншою частиною запиту Так як запит D1 повязаний з іншою частиною початкового запиту через атрибут Р # (в умови порівняння SP Р # = Р Р #), атрибут Р # повинен входити в кортеж-прототип (Див розділ 8) відокремленого запиту Іншими словами, відокремлений запит призначений для вибірки номерів тільки тих деталей червоного кольору, які важать менше 25 фунтів Відокремлений запит позначимо як запит D1, результатом виконання якого є тимчасова змінна відносини р . (Призначення конструкції INTO полягає в тому, щоб створити нову змінну відносини Р з єдиним атрибутом Р # Ця змінна відносини створюється автоматично і містить результат виконання операції RETRIEVE) Нарешті, замінимо посилання на змінну відносини Р у скороченій версії запиту Q0 посиланнями на змінну відносини р . Цю нову скорочену версію початкового запиту позначимо як запит Q1 (цей запит наведено нижче)

Ql: RETRIEVE (SSNAME) WHERE SCITY =    London AND  SS#  = SPS#

AND  SPQTY &gt 200

AND  SPP# = P1P#

Ще раз застосуємо аналогічний прийом до запиту Q1, відокремивши від нього запит, в якому використовується єдина змінна SP Привласнимо відокремленому запиту імя D2, а залишилася після Відділення частину запиту Q1 назвемо Q2, як показано нижче

D2: RETRIEVE INTO SP (SPS#, SPP#) WHERE SPQTY &gt 200

Q2: RETRIEVE (SSNAME) WHERE SCITY = London AND  SS#   =

SP.S# AND   SP.P#

= P.P#

Далі тим же способом відділимо запит з єдиної змінної S

D3: RETRIEVE INTO S (SS#, SSNAME) WHERE SCITY = London Q3: RETRIEVE (S.SNAME) WHERE S.S# = SP.S#

AND  SP.P# = P.P#

Нарешті, відокремимо ще один запит, в якому використовуються змінні SР і Р.

D4: RETRIEVE INTO SP’ (SP.S#) WHERE SP.P# = P.P# Q4: RETRIEVE (S.SNAME) WHERE S.S# = SP’.S#

У результаті вихідний запит Q0 виявився розбитим на три запити з однією змінною, Dl, D2 і D3 (кожен з яких є проекцією скорочення), і два запити з двома змінними, D4 і Q4 (кожен з яких є проекцією зєднання) Ситуацію, в результаті ситуацію можна схематично представити у вигляді дерева, що на рис 183

Рис 183 Дерево декомпозиції запиту Q0

Цю схему можна інтерпретувати, як описано нижче

■ У запитах Dl, D2 і D3 в якості вхідних даних використовуються змінні відносини Р, SP і S (а точніше, ті відносини, які є поточними значеннями змінних відносини р, SP і S), відповідно, які і поміщають результат свого виконання в тимчасові змінні відносини Р , SP і S , соответственноs

■ Далі виконується запит D4, що використовує в якості вхідних даних часів ві змінні відносини Р і SP1 і поміщає результат свого виконання ня в тимчасову змінну відносини SP .

■ Нарешті, виконується запит Q4, що використовує в якості вхідних даних пе ремінні відносини S і SP , результат виконання якого і є ре зультатом виконання вихідного запиту

Зверніть увагу на те, що запити Dl, D2 і D3 повністю незалежні один від іншого і їх можна обробляти в будь-якому порядку (навіть паралельно) Запити D3 і D4 також можна обробляти в будь-якому порядку, але тільки після отримання результатів виконання запитів D1 і D2 Але запити D4 і Q4 не можна піддати подальшій декомпозиції, тому їх слід обробляти за допомогою методу підстановки кортежів (Що зазвичай означає необхідність застосування послідовного пошуку, званого також підходом, заснованому на використанні грубої сили, пошуку за індексом або хешірованного пошуку-див розділ 187) Як приклад розглянемо виконання запиту Q4 Звернувшись до звичайного набору даних, що використовуються в цій книзі як приклади, можна визначити, що безліч номерів постачальників в атрибуті SP ‘. s # буде виглядати так: {SI, S2, S4} Кожне з цих трьох значень по черзі має бути підставлено в атрибут SP ‘. s # В результаті запит Q4 прийме такий вигляд, ніби він був записаний у такий спосіб

‘ S 2 OR                                        SS #     =    S4

В [1834] наведені алгоритми розбиття початкового запиту на менші запити і вибору змінних для підстановки кортежів Саме від вибору змінних в чому залежать фактичні результати оптимізації в [1834] наведені евристичні підходи для оцінки вартості того чи іншого варіанту (у системі Ingres зазвичай, але не завжди для підстановки використовується відношення з найменшою кардинальними) Основна задача процесу оптимізації – уникнути виконання декартових творів і мінімізувати кількість скануються кортежів на кожному етапі обчислення

В [1834] не розглядається оптимізація запитів з однією змінною Однак інформація про це рівні оптимізації присутній в загальному огляді системи Ingres [1811] По суті, ці методи нагадують аналогічні функції, що їх в інших системах, оскільки в них використовується статистична інформація, що зберігається в каталозі, на основі якої вибирається конкретний шлях доступу до необхідних даними (наприклад, на основі хешірованного або простого індексу) В [1835] представлені деякі експериментальні матеріали (наприклад, результати вимірювання продуктивності для еталонного набору запитів), що дозволяють зробити висновок, що описані вище методи оптимізації СУБД Ingres дають добрі результати і досить ефективні при застосуванні на практиці Нижче наведені деякі висновки, взяті з цієї роботи

1 Метод відділення – це найкраща з методик, яку можна застосовувати на першому етапі оптимізації

2 Якщо на першому етапі необхідно виконувати підстановку кортежів, то для цього найкраще використовувати змінну, по якій виконується зєднання

3 Якщо до однієї з змінних в запиті з двома змінними застосовувалася підстановка кортежів, то оптимальна тактика полягає у формуванні динамічно, в міру необхідності, простого або хешірованного індексу по атрибуту зєднання, приналежному іншому відношенню (такий метод фактично застосовується в СУБД Ingres)

Джерело: Дейт К Дж, Введення в системи баз даних, 8-е видання: Пер з англ – М: Видавничий дім «Вільямс», 2005 – 1328 с: Ил – Парал тит англ

Схожі статті:


Сподобалася стаття? Ви можете залишити відгук або підписатися на RSS , щоб автоматично отримувати інформацію про нові статтях.

Коментарів поки що немає.

Ваш отзыв

Поділ на параграфи відбувається автоматично, адреса електронної пошти ніколи не буде опублікований, допустимий HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

*