ПЕРЕТВОРЕННЯ ВИСЛОВІВ

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

Безумовно, слід враховувати, що в результаті застосування до якого-небудь висловом одного правила перетворення може бути отримано вираз, до якого застосовано інше правило перетворення Наприклад, серед вихідних запитів не надто часто зустрічаються запити, сформульовані з використанням двох послідовно виконуваних операцій проекції (мова про це піде нижче см друге правило з підрозділу Операція: скорочення і проекції) Однак при перетворенні запитів подібні вирази досить часто виникають як результат застосування інших правил перетворення (У цьому сенсі дуже важливим випадком є ​​опрацювання подань Наприклад, розглянемо запит Вибрати всі назви міст в поданні v, де уявлення V визначено як проекція змінної відносини постачальників за атрибутами S # і CITY) Інакше кажучи, починаючи з вихідного вираження, оптимізатор буде крок за кроком застосовувати різні правила перетворення доти, поки не буде отримано вираз, яке, згідно вбудованим в оптимізатор евристичним правилами, буде вважатися оптимальним для розглянутого запиту

Операції скорочення і проекції

Почнемо з правил перетворення, які включають лише операції скорочення і проекції

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

(A WHERE pi) WHERE p2 еквівалентно наступному вираженню: A WHERE pi AND p2

Таке перетворення бажано, оскільки початковий варіант вимагає двох проходів в процесі обробки змінної відносини А, тоді як перетворений варіант вимагає тільки одного проходу

2 У послідовності операцій проекції для одного і того ж відносини можна ігнорувати всі проекції, крім останньої Таким чином, вираз

(А {АС11}) {АС12} еквівалентно наступному вираженню: А {АС12}

Тут ас11іас12 – розділені комами списки імен атрибутів

Безумовно, щоб вихідне вираз мало сенс, кожен атрибут, присутній в проекції АС12, обовязково повинен бути присутнім і в проекції acll

3 Операцію скорочення для результату операції проекції можна перетворити в операцію проекції для результату операції скорочення Наприклад, виражніе

(А {acl}) WHERE p еквівалентно наступному вираженню: (A WHERE р) {acl}

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

Розподільний закон

Правило перетворення, яке використано в прикладі, наведеному вище, в розділі 182 (перетворення операції зєднання з наступною операцією скорочення в операцію скорочення, за якою слід операція зєднання), насправді є окремим випадком більш загального правила, званого розподільним законом Кажуть, що унарний оператор f розподіляється по бінарної операції про тоді і тільки тоді, коли для всіх А і B виконується наступне тотожність:

f  (  A  O  B  )  ≡  f  (  A  )  O  f  (  B  )

Наприклад, у звичайній арифметиці операція SQRT (витяг квадратного кореня з невідємного числа) розподіляється по операції множення, так як для всіх Aи B виконується наведене нижче тотожність:

SQRT (А * В)≡  SQRT (А) * SQRT (В)

Отже, виконуючи перетворення виразів, оптимізатор арифметичних виразів завжди може замінити одну частину цієї рівності інший Як зворотний приклад можна привести твердження, що операція SQRT нерозподіляється по операції додавання, так як в загальному квадратний корінь з суми А + В не дорівнює сумі квадратних коренів з А і B

У реляційній алгебрі операція скорочення розподіляється за операціями обєднання, перетину і різниці Вона також розподіляється по операціїзєднання, але лише тоді і тільки тоді, коли умова операції скорочення полягає (у найскладнішому випадку) з двох простих умов сокращенія4, зєднаних операцією AND – по одній умові скорочення для кожного операнда операції зєднання У прикладі, розглянутому в розділі 182, сформульоване вище умова дотримана (умова скорочення – дуже просте і відноситься лише до одного з операндів), завдяки чому стало можливим застосувати розподільний закон для заміни заданого виразу більш ефективним еквівалентом У силу цього закону, операція скорочення була виконана раніше інших операцій Попереднє виконання операцій скорочення майже завжди себе виправдовує, оскільки призводить до суттєвого зменшення кількості кортежів, оброблюваних наступною операцією, а також, можливо, до

зменшення кількості кортежів на виході цієї операції

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

4 Визначення терміна просте умова скорочення приведено в підрозділі Операція ограни-чення розділу

74 глави 7

(A UNION В) {acl} ≡ А {ac1} UNION В {acl}

(A INTERSECT В) {acl} ≡ А {acl} INTERSECT В {acl}

Тут A і B повинні мати однакові типи

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

(A JOIN В) {acl} (А {acl1}) JOIN (В {АС12})

Тут acll – обєднання атрибутів зєднання і тих атрибутів acl, які присутні тільки в Л, а АС12 – обєднання атрибутів зєднання і тих атрибутів acl, які присутні тільки в в

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

Комутативність і асоціативність

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

А Про У ≡ В О А

Наприклад, у звичайній арифметиці операції множення і додавання комутативні, а операції ділення і віднімання – ні У реляційній алгебрі комутативними є операції обєднання, перетину і зєднання, а операції різниці і ділення такими не є Наприклад, якщо запит включає зєднання двох відносин, А і В, то коммутативность означає, що байдуже, яке з відносин А і В вибрано як зовнішнього або внутрішнього Отже, при обчисленні конкретного зєднання системі надано право вибору в якості зовнішнього відносини, наприклад, меншого з двох відносин (див розділ 187) Перейдемо до асоціативності Прийнято вважати, що бінарна операція про є асоціативної тоді і тільки тоді, коли для всіх А, в і З істинно наступне тотожність:

А О (В О С) ≡ (А Про У) О С

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

Ідемпотентність і поглинання

Ще одним важливим загальним правилом є закон ідемпотентностіБінарну операцію про називають Ідемпотентний тоді і тільки тоді, коли для будь-якого А виконується наступне тотожність:

А О А ≡ А

Можна очікувати, що застосування закону ідемпотентності виявиться корисним в процесі перетворення виразів У реляційній алгебрі операції обєднання, перетину і зєднання є Ідемпотентний, а операції ділення і різниці – Ні

Операції обєднання і перетину підпорядковуються також наведеним нижче корисним правилам поглинання

A UNION (A INTERSECT В) ≡ А

A INTERSECT (A UNION В) ≡ А

Обчислювані вирази

Обєктом застосування законів перетворення є не тільки реляційні вирази Наприклад, вище вже згадувалося, що деякі закони перетворення застосовні і до арифметичним виразами Ось конкретний приклад Внаслідок того, що операція множення * розподіляється по операції додавання +, вираз

А * В + А * С

можна перетворити в такий вираз:

А * (В + С)

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

Слід зазначити, що наведений приклад ілюструє кілька більш загальну форму розподільного закону Вище було дано визначення поняття распределяемое ™ по відношенню до унарним операціями, що розподіляється забінарним операціями Проте в даному випадку обидві операції, * і +, є бінарними Кажуть, що бінарна операція 5 розподіляється по бінарної операції про тоді і тільки тоді, коли для всіх А, В і З істинно наступне тотожність:

A  6  (  B O C  )  ≡  (  A  6  B  )  O  (  A  5  C  )

(У наведеному вище арифметичному прикладі 5 можна розглядати як *, а про –

як +.)

Логічні вирази

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

А> У AND У> 3

безумовно, еквівалентно висловом

А> У AND У> 3 AND А> 3

і тому може бути перетворено в цей вислів

Дана еквівалентність заснована на тому, що операція > є транзитивної

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

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

Примітка Цей прийом реалізований в різних комерційних продуктах, включаючи СУБД DB2 (в якій його називають транзитивним замиканням предикатів), а також СУБД Ingres

Нижче наведено ще один приклад Внаслідок того, що операція OR розподіляється по операції AND, логічне вираження

А> У OR (С = D AND Е

можна перетворити в такий вираз:

(А> В OR С = D) AND (А> В OR Е

Цей приклад демонструє інший загальний закон: Будь-яке логічне вираз може бути перетворено в еквівалентну вираз, представлене в конюнктівной нормальній формі (КНФ) . Вираз в КНФ в загальному випадку має наступний вигляд:

Cl   AND   C2   AND   ..   AND   Cn

Тут все терми Cl, С2, .., Сп – це логічні вирази (звані Конюнктів), в яких не використовується логічна операція AND Перевага КНФ полягає в тому, що вираз в КНФ істинно тільки в тому випадку, якщо істинні всі його Конюнктів І навпаки, вираз в КНФ ложно, якщо брехнею є результат обчислення хоча бодногоКонюнктів Оскільки логічна операція AND коммутативна (вираз A AND в еквівалентно висловом BAND л), оптимізатор може обчислювати окремі Конюнктів в будь-якому порядку, зокрема, за зростанням їх складності (починаючи з найпростіших) Як тільки буде знайдений Конюнктів, результатом обчислення якого є брехня, процес обчислення виразу в КНФ можна припинити Більш того, в системах з паралельною обробкою можливо паралельне обчислення кожного з Конюнктів [1856] – [1858] Знову ж, як тільки буде знайдений перший Конюнктів, результатом обчислення якого є значення брехня, процес обчислення виразу в КНФ припиняється

З даного і попереднього підрозділу випливає, що оптимізатор повинен мати інформацію про те, як загальні властивості, такі як розподіленість, застосовуються не тільки до реляційним операціями, таким як зєднання, а й до операторів порівняння, наприклад >, до логічним операторам, наприклад AND і OR, до арифметичним операторам, наприклад + і тп

Семантичні перетворення Розглянемо наступний вираз (SP JOIN S) {Р #}

Дане зєднання відноситься до зєднань типуЗовнішній ключ-відповідний потенційний ключ. У ньому зовнішньому ключу у змінній відносини SP ставиться у відповідність потенційний ключ у змінній відносини S Тому кожен кортеж у змінній відносини SP зєднується з певним кортежем в змінної відносини S Таким чином, з кожного кортежу у змінній відносини SP в загальний результат надходить значення атрибута р # Іншими словами, зєднання

можна взагалі не виконувати Розглянуте вираз можна замінити наступним виразом

SP {Р #}

Проте, будьте уважні – подібне перетворення застосовно тільки в силу семантики (сенсу) конкретної ситуації У загальному випадку кожен операнд в операції зєднання вносить у зєднання кортежі, які не мають відповідних їм кортежів в інших операндах, і тому деякі кортежі не вносять свій внесок у загальний результат Таким чином, найчастіше перетворення подібного типу будуть неприпустимими Проте в даному конкретному випадку кожен кортеж у змінній відносини SP обовязково має відповідний йому кортеж у змінній відносини S згідно встановленому обмеження цілісності (фактично це обмеження посилальної цілісності), яке свідчить, що кожна поставка деталей повинна бути повязана з певним постачальником Отже, враховуючи це зауваження, можна стверджувати, що в даному випадку розглядається перетворення цілком допустимо

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

Важливо розуміти, що, в принципі, будь-яке обмеження цілісності може бути використано для семантичної оптимізації Іншими словами, цей прийом не обмежений використанням тільки обмежень посилальної цілісності, як в даному випадку Наприклад, припустимо, що в базі даних постачальників і деталей встановлено обмеження, згідно з яким всі деталі червоного кольору повинні зберігатися в Лондоні Розглянемо наступний запит

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

Це досить складний запит Але в силу розглянутого обмеження цілісності його можна привести до такого виду

Визначити всіх постачальників з Лондона, що постачають деталі лише червоного кольору

Примітка Наскільки відомо автору, семантична оптимізація належною мірою використовується лише в небагатьох сучасних комерційних продуктах Але, в принципі, семантична оптимізація здатна забезпечувати значне підвищення продуктивності (досить імовірно, набагато перевищує те, яке в даний час може бути досягнуто за допомогою будь-яких традиційних прийомів оптимізації) Більш докладно ідея семантичної оптимізації викладена в [1813], [1826] – [1828] і особливо – в [1825]

Заключні зауваження

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

Джерело: Дейт К Дж, Введення в системи баз даних, 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>

*

*